Computing the Strategy to Commit to in Polymatrix Games (Extended Version)
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Aggregate Fictitious Play for Learning in Anonymous Polymatrix Games (Extended Version)
Fictitious play (FP) is a well-studied algorithm that enables agents to learn Nash equilibrium in games with certain reward structures. However, when agents have no prior knowledge of the reward functions, FP faces a maj…
Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability
Self-play is a technique for machine learning in multi-agent systems where a learning algorithm learns by interacting with copies of itself. Self-play is useful for generating large quantities of data for learning, but h…
Equilibrium with Internal Transfers
Nash equilibrium (NE) arises from selfish utility maximization, yet its social welfare can be arbitrarily far from optimal. Moreover, computing an NE is intractable in general. We study augmented game models in which pla…
The Complexity of Min-Max Optimization for Quadratic Polynomials
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at m…
Learning Sparse Polymatrix Games in Polynomial Time and Sample Complexity
We consider the problem of learning sparse polymatrix games from observations of strategic interactions. We show that a polynomial time method based on $\ell_{1,2}$-group regularized logistic regression recovers a game, …