Are there any interesting connections between Game Theory and Algebraic Topology? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T10:05:46Z http://mathoverflow.net/feeds/question/3997 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology Are there any interesting connections between Game Theory and Algebraic Topology? paarshad 2009-11-03T21:00:01Z 2013-02-12T17:42:52Z <p>I've been learning game theory on my own and was just curious how it connected with previous things I've learned. So are there any interesting connections between Game Theory and Algebraic Topology? or possibly other branches of topology?</p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/3998#3998 Answer by Alon Amit for Are there any interesting connections between Game Theory and Algebraic Topology? Alon Amit 2009-11-03T21:11:41Z 2009-11-03T21:11:41Z <p>The <a href="http://en.wikipedia.org/wiki/Banach-Mazur%5Fgame" rel="nofollow">Banach-Mazur game</a> is an example of a game in a topological setting. There are various <a href="http://en.wikipedia.org/wiki/Topological%5Fgame" rel="nofollow">other games of this nature</a> which are mostly related to foundational questions in point-set topology.</p> <p>I'm afraid I can't think of a meaningful connection between game theory and algebraic topology. I think that real algebraic geometry plays a part in the study of various types of equilibria in a game-theoretic context, but that's about alll I can say about this.</p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/3999#3999 Answer by Martin M. W. for Are there any interesting connections between Game Theory and Algebraic Topology? Martin M. W. 2009-11-03T21:12:46Z 2009-11-03T21:30:30Z <p>One example is in the concept of a Nash equilibrium, whose existence can be proved using various (topological) fixed point theorems. (Google "nash equilibrium proof" for a wide variety of examples... the main topological machinery that comes up is the Kakutani fixed point theorem or the plain-vanilla Brouwer theorem.) </p> <p>Fixed point theorems come up in many other, similar settings; you see them a lot in certain kinds of mathematical economics. The overall intuition is that given a current set of known player strategies, people will generally want to change to better strategies. This defines a function on the "space of strategies". A fixed point of this function is interesting because it indicates an "equlibrium" of strategies that are in a sense optimal. Often topology is the best way to prove a fixed point exists.</p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/4002#4002 Answer by Yemon Choi for Are there any interesting connections between Game Theory and Algebraic Topology? Yemon Choi 2009-11-03T21:36:59Z 2009-11-03T21:36:59Z <p>I haven't read the paper, and am not competent to judge its worth or novelty, but <a href="http://arxiv.org/abs/math.AG/0301001" rel="nofollow">math.AG/0301001</a> might be of interest here.</p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/4009#4009 Answer by Jim Fowler for Are there any interesting connections between Game Theory and Algebraic Topology? Jim Fowler 2009-11-03T22:26:08Z 2009-11-03T22:26:08Z <p>Game theory makes me think of economics, so here's a paper you might be interested in:</p> <blockquote> <p>Weinberger, Shmuel. On the topological social choice model. J. Econom. Theory 115 (2004), no. 2, 377--384. 91B14 (55P20 55Q05 57N60) <a href="http://www.ams.org/mathscinet-getitem?mr=2044787" rel="nofollow">MR2044787</a>.</p> </blockquote> <p>This paper looks at social choice (aggregating the desires of many people into a single outcome) from a topological perspective.</p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/4101#4101 Answer by Elisha Peterson for Are there any interesting connections between Game Theory and Algebraic Topology? Elisha Peterson 2009-11-04T15:38:36Z 2009-11-04T15:38:36Z <p>Sperner's Lemma comes to mind. It can be used to prove various results about fair division (being strongly related to the Brouwer Fixed Point Theorem). Ideas from homology can be used to simplify proofs of its generalized form. See Francis Su's papers (<a href="http://www.math.hmc.edu/~su/papers.html" rel="nofollow">http://www.math.hmc.edu/~su/papers.html</a>). </p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/4144#4144 Answer by Kristal Cantwell for Are there any interesting connections between Game Theory and Algebraic Topology? Kristal Cantwell 2009-11-04T20:08:15Z 2009-11-04T20:08:15Z <p>Here is an article on topology and game theory:</p> <p>Social choice and game theory: recent results with a topological approach</p> <p>Chichilnisky, Graciela (1983): Social choice and game theory: recent results with a topological approach. Published in: Social Choice and Welfare Chap. 6 (1983): pp. 79-102.</p> <p>Here is the abstract:</p> <p>Abstract</p> <p>This chapter presents a summary of recent results obtained in game and social choice theories, and highlights the application and the development of tools in algebraic topology. The purpose is expository: no attempt is made to provide complete proofs, for which references are given, nor to review the previous work in this area, which covers a significant subset of the economic literature. The aim is to provide an oriented guide to recent results, through economic examples with geometric interpretations, and to indicate possible fruitful avenues of research.</p> <p>It is available here:</p> <p><a href="http://mpra.ub.uni-muenchen.de/8059/1/MPRA%5Fpaper%5F8059.pdf" rel="nofollow">http://mpra.ub.uni-muenchen.de/8059/1/MPRA_paper_8059.pdf</a></p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/4163#4163 Answer by Dan Piponi for Are there any interesting connections between Game Theory and Algebraic Topology? Dan Piponi 2009-11-04T22:50:13Z 2009-11-04T22:50:13Z <p>There's a neat <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/brouwer-hex.pdf" rel="nofollow">paper</a> by David Gale on the connection between Brouwer's fixed point theorem and the game of <a href="http://en.wikipedia.org/wiki/Hex_(board_game)" rel="nofollow">Hex</a>. The fixed point theorem is 'equivalent' to the theorem that the game cannot end in a tie.</p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/10744#10744 Answer by Michael Greinecker for Are there any interesting connections between Game Theory and Algebraic Topology? Michael Greinecker 2010-01-04T22:27:44Z 2010-01-04T22:27:44Z <p>In the theory of refinements of the Nash equilibrium concepts, people have looked at the topological structure of the Nash correspondence (the map from games to the set of equilibra). The seminal paper is by Kohlberg and Mertens in Econometrica 1986. They also introduced a refinement, stable sets. The theory of stable sets has been further developed, often using ideas and concepts from algebraic topology. </p> <p>There is work by Jean-Jacques Herings on computation of Nash equilibria using homotopy methods.</p> <p>In evolutionary game theory, one often studies complex dynamical systems and these sometimes give rise to problems where algebraic topology is useful. Stefano Demichelis did some work related to this. </p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/16593#16593 Answer by Q.Q.J. for Are there any interesting connections between Game Theory and Algebraic Topology? Q.Q.J. 2010-02-27T11:59:20Z 2010-02-27T11:59:20Z <p><a href="http://en.wikipedia.org/wiki/Borel_determinacy_theorem" rel="nofollow">Borel Determinacy</a> and more modern improvements link game theory to topology, but more along the measure theory vein than algebraic topology</p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/27412#27412 Answer by Anonymous for Are there any interesting connections between Game Theory and Algebraic Topology? Anonymous 2010-06-08T01:02:13Z 2010-06-08T01:02:13Z <p>You may also want to see <a href="http://arxiv.org/abs/1005.2405" rel="nofollow">http://arxiv.org/abs/1005.2405</a></p> <p>Flows and Decompositions of Games: Harmonic and Potential Games Authors: Ozan Candogan, Ishai Menache, Asuman Ozdaglar, Pablo A. Parrilo</p> <p>Abstract: In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and study the structural and equilibrium properties of this new class of games. Intuitively, the potential component of a game describes the possibility of agreement and coordination between players, while the harmonic part represents the conflicts between their interests. We make this intuition precise, by studying the properties of these two classes, and show that indeed they have quite distinct and remarkable characteristics. For instance, while finite potential games always have pure Nash equilibria, harmonic games generically never do. Moreover, we show that the nonstrategic component does not affect the equilibria of a game, but plays a fundamental role in their efficiency properties, thus decoupling the location of equilibria and their payoff-related properties. Exploiting the properties of the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the properties of potential and harmonic games to 'nearby' games. We exemplify this point by showing that the set of approximate equilibria of an arbitrary game can be characterized through the equilibria of its projection onto the set of potential games. </p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/91334#91334 Answer by James Propp for Are there any interesting connections between Game Theory and Algebraic Topology? James Propp 2012-03-15T22:34:23Z 2012-03-15T22:34:23Z <p>In combinatorial game theory (more specifically, the theory of impartial games), the set of winning options of a winning option is the empty set, which reminds me of the fact that the boundary of the boundary of a manifold-with-boundary is empty. </p> <p>Also, when one takes a disjunctive sum of two impartial games $G$ and $H$, an option of $G+H$ is of the form $G'+H$ or $G+H'$, where $G'$ is an option of $G$ and $H'$ is an option of $H$. This reminds me of the definition of a derivation: $D(fg) = (Df)g + f(Dg)$. The two examples of derivations that come to mind are differentiation of functions and, as above, the boundary operation $\partial$ applied to manifolds-with-boundary: the boundary of $M_1 \times M_2$ is $\partial M_1 \times M_2 \cup M_1 \times \partial M_2$.</p> <p>I have no idea whether there's an way to cash in on this formal resemblance.</p> http://mathoverflow.net/questions/3997/are-there-any-interesting-connections-between-game-theory-and-algebraic-topology/121627#121627 Answer by isomorphismes for Are there any interesting connections between Game Theory and Algebraic Topology? isomorphismes 2013-02-12T17:42:52Z 2013-02-12T17:42:52Z <p>I'm coming from the other side: familiar with game theory and learning about algebraic topology.</p> <ul> <li>I know Kakutani's fixed point theorem was used to simplify <a href="http://web.mit.edu/linguistics/events/iap07/Nash-Eqm.pdf" rel="nofollow">Nash's seminal paper</a>.</li> <li>If you think about a simple normal-form game like Prisoner's Dilemma or Coordination Game, <img src="http://epress.anu.edu.au/cs/chap5Newth-final-10.jpg" alt="prisoner's dilemma"> the arrows between the payoff matrix are governed by $>_A$ and $>_B$ meaning the ordering of payoffs by players A and B. I know topological spaces aren't necessarily orderable, but this seems topological in flavour since distance doesn't matter. (Whether you lose £3 or get your head chopped off, I don't care as long as it doesn't affect me.) I think of this as like a "topological gravity" creating the Nash equilibria.</li> </ul>