2017/11/21 by Christian Kroer, Gabriele Farina, Kroer, Christian +3
Engineering · #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Infrastructure Resilience and Vulnerability Analysis #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.1711.08080
openalex publication_date 2017/11/21 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Stackelberg equilibria have become increasingly important as a solution\nconcept in computational game theory, largely inspired by practical problems\nsuch as security settings. In practice, however, there is typically uncertainty\nregarding the model about the opponent. This paper is, to our knowledge, the\nfirst to investigate Stackelberg equilibria under uncertainty in extensive-form\ngames, one of the broadest classes of game. We introduce robust Stackelberg\nequilibria, where the uncertainty is about the opponent's payoffs, as well as\nones where the opponent has limited lookahead and the uncertainty is about the\nopponent's node evaluation function. We develop a new mixed-integer program for\nthe deterministic limited-lookahead setting. We then extend the program to the\nrobust setting for Stackelberg equilibrium under unlimited and under limited\nlookahead by the opponent. We show that for the specific case of interval\nuncertainty about the opponent's payoffs (or about the opponent's node\nevaluations in the case of limited lookahead), robust Stackelberg equilibria\ncan be computed with a mixed-integer program that is of the same asymptotic\nsize as that for the deterministic setting.\n