A Game-Theoretic Analysis of Strictly Competitive Multiagent Scenarios

Felix Brandt, Felix Fischer, Paul Harrenstein, Yoav Shoham

This paper is a comparative study of game-theoretic solution concepts in strictly competitive multiagent scenarios, as commonly encountered in the context of parlor games, competitive economic situations, and some social choice settings. We model these scenarios as ranking games in which every outcome is a ranking of the players, with higher ranks being preferred over lower ones. Rather than confining our attention to one particular solution concept, we give matching upper and lower bounds for various comparative ratios of solution concepts within ranking games. The solution concepts we consider in this context are security level strategies (maximin), Nash equilibrium, and correlated equilibrium. Additionally, we also examine quasi-strict equilibrium, an equilibrium refinement proposed by Harsanyi, which remedies some apparent shortcomings of Nash equilibrium when applied to ranking games. In particular, we compute the price of cautiousness, i.e., the worst-possible loss an agent may incur by playing maximin instead of the worst (quasi-strict) Nash equilibrium, the mediation value, i.e., the ratio between the social welfare obtained in the best correlated equilibrium and the best Nash equilibrium, and the enforcement value, i.e., the ratio between the highest obtainable social welfare and that of the best correlated equilibrium.