Jiří Čermák
ABSTRACT
Game theory describes the conditions for the strategies of rational agents to form an equilibrium. However, game theory can fail from the prescriptive viewpoint and can serve only as a heuristic recommendation for agents. There exists a plethora of game theoretic solution concepts, however, their effectiveness has never been compared; hence, there is no guideline for selecting correct algorithm for a given domain. Therefore, we compare the effectiveness of solution-concept strategies and strategies computed by Counterfactual regret minimization (CFR) and Monte-Carlo tree search in practice. Our results show that (1) CFR strategies are typically the best, and (2) the effectiveness of the refinements of NE depends on the utility structure of the game.
- C. Audet, S. Belhaiza, and P. Hansen. A new sequence form approach for the enumeration and refinement of all extreme Nash equilibria for extensive form games. International Game Theory Review 11, 2009.Google Scholar
- H. Baier and M. H. M. Winands. Nested Monte-Carlo Tree Search for Online Planning in Large MDPs. In ECAI, 2012.Google Scholar
- L. Kocsis, C. Szepesvári, and J. Willemson. Improved Monte-Carlo Search. Tech. Rep 1, 2006.Google Scholar
- D. Koller, N. Megiddo, and B. von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 1996.Google ScholarCross Ref
- R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6--38, 1995.Google Scholar
- P. B. Miltersen and T. B. Sørensen. Computing a quasi-perfect equilibrium of a two-player game. Economic Theory, 2008.Google Scholar
- E. van Damme. A relation between perfect equilibria in extensive form games and proper equilibria in normal form games. Game Theory, 13:1--13, 1984.Google ScholarCross Ref
- M. Zinkevich, M. Bowling, and N. Burch. A new algorithm for generating equilibria in massive zero-sum games. In AAAI, 2007. Google ScholarDigital Library
- J. Čermák, B. Bošanskÿ, and V. Lisÿ. Practical Performance of Refinements of Nash Equilibria in Extensive-Form Zero-Sum Games. In ECAI, 2014.Google Scholar
Index Terms
- Strategy Effectiveness of Game-Theoretical Solution Concepts in Extensive-Form General-Sum Games
Recommendations
Double-oracle algorithm for computing an exact nash equilibrium in zero-sum extensive-form games
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systemsWe investigate an iterative algorithm for computing an exact Nash equilibrium in two-player zero-sum extensive-form games with imperfect information. The approach uses the sequence-form representation of extensive-form games and the double-oracle ...
Ranking games
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 ...
Solving extensive-form games with double-oracle methods
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systemsWe investigate iterative algorithms for computing exact Nash equilibria in two-player zero-sum extensive-form games. The algorithms use an algorithmic framework of double-oracle methods. The main idea is to restrict the game by allowing the players to ...
Comments