Game Implementation: What Are the Obstructions?


  • Jiehua Chen TU Wien
  • Seyedeh Negar Layegh Khavidaki TU Wien
  • Sebastian Vincent Haydn TU Wien
  • Sofia Simola TU Wien
  • Manuel Sorge TU Wien



GTEP: Game Theory, CSO: Applications, GTEP: Mechanism Design, MAS: Applications, SO: Applications


In many applications, we want to influence the decisions of independent agents by designing incentives for their actions. We revisit a fundamental problem in this area, called GAME IMPLEMENTATION: Given a game in standard form and a set of desired strategies, can we design a set of payment promises such that if the players take the payment promises into account, then all undominated strategies are desired? Furthermore, we aim to minimize the cost, that is, the worst-case amount of payments. We study the tractability of computing such payment promises and determine more closely what obstructions we may have to overcome in doing so. We show that GAME IMPLEMENTATION is NP-hard even for two players, solving in particular a long-standing open question and suggesting more restrictions are necessary to obtain tractability results. We thus study the regime in which players have only a small constant number of strategies and obtain the following. First, this case remains NP-hard even if each player’s utility depends only on three others. Second, we repair a flawed efficient algorithm for the case of both small number of strategies and small number of players. Among further results, we characterize sets of desired strategies that can be implemented at zero cost as a generalization of Nash equilibria.




How to Cite

Chen, J., Layegh Khavidaki, S. N., Haydn, S. V., Simola, S., & Sorge, M. (2023). Game Implementation: What Are the Obstructions?. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 5557-5564.



AAAI Technical Track on Game Theory and Economic Paradigms