From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory
In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer’s (or, in another version Kakutani’s) fixed point theorem,...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-10-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1099-4300/20/10/782 |
| _version_ | 1828369166559608832 |
|---|---|
| author | Christos Papadimitriou Georgios Piliouras |
| author_facet | Christos Papadimitriou Georgios Piliouras |
| author_sort | Christos Papadimitriou |
| collection | DOAJ |
| description | In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer’s (or, in another version Kakutani’s) fixed point theorem, the most sophisticated result in his era’s topology—in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept—this notion of “the outcome of the game”—every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games. |
| first_indexed | 2024-04-14T06:20:07Z |
| format | Article |
| id | doaj.art-c38c026000c746c59e8ca5cc5aeac37b |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-14T06:20:07Z |
| publishDate | 2018-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-c38c026000c746c59e8ca5cc5aeac37b2022-12-22T02:08:04ZengMDPI AGEntropy1099-43002018-10-01201078210.3390/e20100782e20100782From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game TheoryChristos Papadimitriou0Georgios Piliouras1Computer Science Department, Columbia University, New York, NY 10027, USAEngineering Systems and Design (ESD), Singapore University of Technology and Design, Singapore 487372, SingaporeIn 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer’s (or, in another version Kakutani’s) fixed point theorem, the most sophisticated result in his era’s topology—in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept—this notion of “the outcome of the game”—every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games.http://www.mdpi.com/1099-4300/20/10/782algorithmic game theoryreplicator dynamicsinvariantKullback–Leibler divergence |
| spellingShingle | Christos Papadimitriou Georgios Piliouras From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory Entropy algorithmic game theory replicator dynamics invariant Kullback–Leibler divergence |
| title | From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory |
| title_full | From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory |
| title_fullStr | From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory |
| title_full_unstemmed | From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory |
| title_short | From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory |
| title_sort | from nash equilibria to chain recurrent sets an algorithmic solution concept for game theory |
| topic | algorithmic game theory replicator dynamics invariant Kullback–Leibler divergence |
| url | http://www.mdpi.com/1099-4300/20/10/782 |
| work_keys_str_mv | AT christospapadimitriou fromnashequilibriatochainrecurrentsetsanalgorithmicsolutionconceptforgametheory AT georgiospiliouras fromnashequilibriatochainrecurrentsetsanalgorithmicsolutionconceptforgametheory |