2026-08-07T03:51:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14386 2024-03-06T10:54:16Z ddc:004 open_access

Fragility and Robustness in Mean-Payoff Adversarial Stackelberg Games Balachander, Mrudula Guha, Shibashis Raskin, Jean-François mean-payoff Stackelberg games synthesis Two-player mean-payoff Stackelberg games are nonzero-sum infinite duration games played on a bi-weighted graph by Leader (Player 0) and Follower (Player 1). Such games are played sequentially: first, Leader announces her strategy, second, Follower chooses his best-response. If we cannot impose which best-response is chosen by Follower, we say that Follower, though strategic, is adversarial towards Leader. The maximal value that Leader can get in this nonzero-sum game is called the adversarial Stackelberg value (ASV) of the game. We study the robustness of strategies for Leader in these games against two types of deviations: (i) Modeling imprecision - the weights on the edges of the game arena may not be exactly correct, they may be delta-away from the right one. (ii) Sub-optimal response - Follower may play epsilon-optimal best-responses instead of perfect best-responses. First, we show that if the game is zero-sum then robustness is guaranteed while in the nonzero-sum case, optimal strategies for ASV are fragile. Second, we provide a solution concept to obtain strategies for Leader that are robust to both modeling imprecision, and as well as to the epsilon-optimal responses of Follower, and study several properties and algorithmic problems related to this solution concept. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mrudula Balachander and Shibashis Guha and Jean-François Raskin 2021 Is Part Of LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2021.9 urn:nbn:de:0030-drops-143863 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.9 eng https://creativecommons.org/licenses/by/4.0/legalcode