Computing the Strategy to Commit to in Polymatrix Games

Authors

  • Giuseppe De Nittis Politecnico di Milano
  • Alberto Marchesi Politecnico di Milano
  • Nicola Gatti Politecnico di Milano

DOI:

https://doi.org/10.1609/aaai.v32i1.11456

Keywords:

Equilibrium Computation, Leader-Follower, Polymatrix Games

Abstract

Leadership games provide a powerful paradigm to model many real-world settings. Most literature focuses on games with a single follower who acts optimistically, breaking ties in favour of the leader. Unfortunately, for real-world applications, this is unlikely. In this paper, we look for efficiently solvable games with multiple followers who play either optimistically or pessimistically, i.e., breaking ties in favour or against the leader. We study the computational complexity of finding or approximating an optimistic or pessimistic leader-follower equilibrium in specific classes of succinct games—polymatrix like—which are equivalent to 2-player Bayesian games with uncertainty over the follower, with interdependent or independent types. Furthermore, we provide an exact algorithm to find a pessimistic equilibrium for those game classes. Finally, we show that in general polymatrix games the computation is harder even when players are forced to play pure strategies.

Downloads

Published

2018-04-25

How to Cite

De Nittis, G., Marchesi, A., & Gatti, N. (2018). Computing the Strategy to Commit to in Polymatrix Games. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11456

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms