
The Library
Optimally deceiving a learning leader in Stackelberg games
Tools
Birmpas, Georgios, Gan, Jiarui, Hollender, Alexandros, Marmolejo-Cossío, Francisco J., Rajgopal, Ninad and Voudouris, Alexandros A. (2021) Optimally deceiving a learning leader in Stackelberg games. Journal of Artificial Intelligence Research, 72 . pp. 507-531. doi:10.1613/jair.1.12542 ISSN 1076-9757.
|
PDF
WRAP-optimally-deceiving-learning-leader-Stackelberg-games-Rajgopal-2021.pdf - Published Version - Requires a PDF viewer. Download (559Kb) | Preview |
Official URL: http://dx.doi.org/10.1613/jair.1.12542
Abstract
Recent results have shown that algorithms for learning the optimal commitment in a Stackelberg game are susceptible to manipulation by the follower. These learning algorithms operate by querying the best responses of the follower, who consequently can deceive the algorithm by using fake best responses, typically by responding according to fake payoffs that are different from the actual ones. For this strategic behavior to be successful, the main challenge faced by the follower is to pinpoint the fake payoffs that would make the learning algorithm output a commitment that benefits them the most. While this problem has been considered before, the related literature has only focused on a simple setting where the follower can only choose from a finite set of payoff matrices, thus leaving the general version of the problem unanswered. In this paper, we fill this gap by showing that it is always possible for the follower to efficiently compute (near-)optimal fake payoffs, for various scenarios of learning interaction between the leader and the follower. Our results also establish an interesting connection between the follower’s deception and the leader’s maximin utility: through deception, the follower can induce almost any (fake) Stackelberg equilibrium if and only if the leader obtains at least their maximin utility in this equilibrium.
Item Type: | Journal Article | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | H Social Sciences > HB Economic Theory Q Science > Q Science (General) Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Neural networks (Computer science) , Game theory, Game theory -- Mathematical models, Noncooperative games (Mathematics), Equilibrium (Economics), Machine learning , Mathematical optimization | |||||||||||||||||||||
Journal or Publication Title: | Journal of Artificial Intelligence Research | |||||||||||||||||||||
Publisher: | A A A I Press | |||||||||||||||||||||
ISSN: | 1076-9757 | |||||||||||||||||||||
Official Date: | 27 October 2021 | |||||||||||||||||||||
Dates: |
|
|||||||||||||||||||||
Volume: | 72 | |||||||||||||||||||||
Page Range: | pp. 507-531 | |||||||||||||||||||||
DOI: | 10.1613/jair.1.12542 | |||||||||||||||||||||
Status: | Peer Reviewed | |||||||||||||||||||||
Publication Status: | Published | |||||||||||||||||||||
Reuse Statement (publisher, data, author rights): | ©2021 AI Access Foundation. All rights reserved https://jair.org/index.php/jair/about#jair-license | |||||||||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||||||||
Date of first compliant deposit: | 7 December 2021 | |||||||||||||||||||||
Date of first compliant Open Access: | 8 December 2021 | |||||||||||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year