zbMATH — the first resource for mathematics

Some anomalies of farsighted strategic behavior. (English) Zbl 1395.91008
Erlebach, Thomas (ed.) et al., Approximation and online algorithms. 10th international workshop, WAOA 2012, Ljubljana, Slovenia, September 13–14, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-38015-0/pbk). Lecture Notes in Computer Science 7846, 229-241 (2013).
Summary: We investigate subgame perfect equilibria, that better capture the rationality of the players in sequential games with respect to other more myopic dynamics like the classical Nash one. We prove that the sequential price of anarchy, that is the worst case ratio between the social performance at a subgame perfect equilibrium and the best possible one, is exactly 3 in cut and consensus games. Moreover, we improve the known \(\Omega (n)\) lower bound for unrelated scheduling to \(2^{\Omega(\sqrt{n})}\) and refine the corresponding upper bound to \(2^{n }\), where \(n\) is the number of players. Finally, we determine essentially tight bounds for fair cost sharing games by proving that the sequential price of anarchy is between \(n + 1 - H _{n }\) and \(n\). A surprising lower bound of \(\frac{n + 1}{2}\) is also determined for the singleton case.
Our results are quite interesting and counterintuitive, as they show that a farsighted behavior generally may lead to a worse performance with respect to myopic one; in fact, Nash equilibria and simple Nash rounds, consisting of a single (myopic) move per player starting from the empty state achieve a price of anarchy which result to be lower or equivalent to the sequential price of anarchy in almost all the considered cases.
For the entire collection see [Zbl 1271.68034].

91A10 Noncooperative games
91A06 \(n\)-person games, \(n>2\)
Full Text: DOI