Strong Nash equilibria and mixed strategies
- PDF / 962,947 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 234 Views
Strong Nash equilibria and mixed strategies Eleonora Braggion1 · Nicola Gatti1 · Roberto Lucchetti1 · Tuomas Sandholm2 · Bernhard von Stengel3 Accepted: 17 June 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We study strong Nash equilibria in mixed strategies in finite games. A Nash equilib‑ rium is strong if no coalition of players can jointly deviate so that all players in the coalition get strictly better payoffs. Our main result concerns games with two players and states that if a game admits a strong Nash equilibrium, then the payoff pairs in the support of the equilibrium lie on a straight line in the players’ utility space. As a consequence, the set of games that have a strong Nash equilibrium in which at least one player plays a mixed strategy has measure zero. We show that the same property holds for games with more than two players, already when no coalition of two play‑ ers can profitably deviate. Furthermore, we show that, in contrast to games with two players, in a strong Nash equilibrium an outcome that is strictly Pareto dominated may occur with positive probability. Keywords Noncooperative games · Strong Nash equilibrium · Mixed strategies · Pareto efficiency
* Nicola Gatti [email protected] Eleonora Braggion [email protected] Roberto Lucchetti [email protected] Tuomas Sandholm [email protected] Bernhard von Stengel b.von‑[email protected] 1
Politecnico di Milano, Milan, Italy
2
Carnegie Mellon University, Pittsburgh, USA
3
London School of Economics and Political Science, London, UK
13
Vol.:(0123456789)
E. Braggion et al.
1 Introduction It is well known that in a non-cooperative game, selfish behavior can cause players to be worse off than they could be by collaborating. The most famous example is the Prisoners’ Dilemma (Luce and Raiffa 1957), where strictly dominating strategies for the players lead to a bad outcome for both. The strong Nash equilibrium by Aumann (1959) gets around this paradox, as a solution concept that is resilient against coa‑ litional deviations. A strategy profile is a strong Nash equilibrium if no coalition of players can jointly deviate so that all players in the coalition get strictly better payoffs (because this applies to single-player coalitions, it is a Nash equilibrium). Strong Nash equilibrium outcomes are also called weakly Pareto efficient for each coalition (Miettinen 1999, Definition 2.5.1). A further refinement is super strong Nash equilibrium (Rozenfeld 2007), which requires Pareto efficiency for every coali‑ tion (that is, no coalition can improve a player’s payoff without hurting at least one other member of the coalition). There are classes of games that have a strong Nash equilibrium but no super strong Nash equilibrium (Gourvès and Monnot 2009), so the distinction between the two solution concepts is meaningful. The strong Nash equilibrium concept is commonly criticized as too demanding because it allows for unlimited private communication among the players. Moreover, in man
Data Loading...
