TY - JOUR
T1 - Ranking games
AU - Brandt, Felix
AU - Fischer, Felix
AU - Harrenstein, Paul
AU - Shoham, Yoav
N1 - Funding Information:
The authors thank Vincent Conitzer, Markus Holzer, Samuel Ieong, Eugene Nudelman, and Rob Powers, and the anonymous referees for valuable comments. This article is based upon work supported by the Deutsche Forschungsgemeinschaft under grants BR 2312/1-1 and BR 2312/3-1, and by the National Science Foundation under ITR grant IIS-0205633. Research on this topic was initiated during a post-doctoral stay of the first author at Stanford University.
PY - 2009/2
Y1 - 2009/2
N2 - The outcomes of many strategic situations such as parlor games or competitive economic scenarios are rankings of the participants, with higher ranks generally at least as desirable as lower ranks. Here we define ranking games as a class of n-player normal-form games with a payoff structure reflecting the players' von Neumann-Morgenstern preferences over their individual ranks. We investigate the computational complexity of a variety of common game-theoretic solution concepts in ranking games and deliver hardness results for iterated weak dominance and mixed Nash equilibrium when there are more than two players, and for pure Nash equilibrium when the number of players is unbounded but the game is described succinctly. This dashes hope that multi-player ranking games can be solved efficiently, despite their profound structural restrictions. Based on these findings, we provide matching upper and lower bounds for three comparative ratios, each of which relates two different solution concepts: the price of cautiousness, the mediation value, and the enforcement value.
AB - The outcomes of many strategic situations such as parlor games or competitive economic scenarios are rankings of the participants, with higher ranks generally at least as desirable as lower ranks. Here we define ranking games as a class of n-player normal-form games with a payoff structure reflecting the players' von Neumann-Morgenstern preferences over their individual ranks. We investigate the computational complexity of a variety of common game-theoretic solution concepts in ranking games and deliver hardness results for iterated weak dominance and mixed Nash equilibrium when there are more than two players, and for pure Nash equilibrium when the number of players is unbounded but the game is described succinctly. This dashes hope that multi-player ranking games can be solved efficiently, despite their profound structural restrictions. Based on these findings, we provide matching upper and lower bounds for three comparative ratios, each of which relates two different solution concepts: the price of cautiousness, the mediation value, and the enforcement value.
KW - Computational complexity
KW - Game theory
KW - Multi-agent systems
KW - Solution concepts
KW - Strict competitiveness
KW - n-player games
UR - http://www.scopus.com/inward/record.url?scp=57749111849&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2008.10.008
DO - 10.1016/j.artint.2008.10.008
M3 - Article
AN - SCOPUS:57749111849
SN - 0004-3702
VL - 173
SP - 221
EP - 239
JO - Artificial Intelligence
JF - Artificial Intelligence
IS - 2
ER -