Are there any interesting connections between Game Theory and Algebraic Topology? - MathOverflow

Are there any interesting connections between Game Theory and Algebraic Topology?

2009-11-03T21:00:01Z

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?

Answer by Alon Amit for Are there any interesting connections between Game Theory and Algebraic Topology?

2009-11-03T21:11:41Z

The Banach-Mazur game is an example of a game in a topological setting. There are various other games of this nature which are mostly related to foundational questions in point-set topology.

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.

Answer by Martin M. W. for Are there any interesting connections between Game Theory and Algebraic Topology?

2009-11-03T21:12:46Z

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.)

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.

Answer by Yemon Choi for Are there any interesting connections between Game Theory and Algebraic Topology?

2009-11-03T21:36:59Z

I haven't read the paper, and am not competent to judge its worth or novelty, but math.AG/0301001 might be of interest here.

Answer by Jim Fowler for Are there any interesting connections between Game Theory and Algebraic Topology?

2009-11-03T22:26:08Z

Game theory makes me think of economics, so here's a paper you might be interested in:

Weinberger, Shmuel. On the topological social choice model. J. Econom. Theory 115 (2004), no. 2, 377--384. 91B14 (55P20 55Q05 57N60) MR2044787.

This paper looks at social choice (aggregating the desires of many people into a single outcome) from a topological perspective.

Answer by Elisha Peterson for Are there any interesting connections between Game Theory and Algebraic Topology?

2009-11-04T15:38:36Z

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 (http://www.math.hmc.edu/~su/papers.html).

Answer by Kristal Cantwell for Are there any interesting connections between Game Theory and Algebraic Topology?

2009-11-04T20:08:15Z

Here is an article on topology and game theory:

Social choice and game theory: recent results with a topological approach

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.

Here is the abstract:

Abstract

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.

It is available here:

http://mpra.ub.uni-muenchen.de/8059/1/MPRA_paper_8059.pdf

Answer by Dan Piponi for Are there any interesting connections between Game Theory and Algebraic Topology?

2009-11-04T22:50:13Z

There's a neat paper by David Gale on the connection between Brouwer's fixed point theorem and the game of Hex. The fixed point theorem is 'equivalent' to the theorem that the game cannot end in a tie.

Answer by Michael Greinecker for Are there any interesting connections between Game Theory and Algebraic Topology?

2010-01-04T22:27:44Z

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.

There is work by Jean-Jacques Herings on computation of Nash equilibria using homotopy methods.

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.

Answer by Q.Q.J. for Are there any interesting connections between Game Theory and Algebraic Topology?

2010-02-27T11:59:20Z

Borel Determinacy and more modern improvements link game theory to topology, but more along the measure theory vein than algebraic topology

Answer by Anonymous for Are there any interesting connections between Game Theory and Algebraic Topology?

2010-06-08T01:02:13Z

You may also want to see http://arxiv.org/abs/1005.2405

Flows and Decompositions of Games: Harmonic and Potential Games Authors: Ozan Candogan, Ishai Menache, Asuman Ozdaglar, Pablo A. Parrilo

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.

Answer by James Propp for Are there any interesting connections between Game Theory and Algebraic Topology?

2012-03-15T22:34:23Z

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.

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$.

I have no idea whether there's an way to cash in on this formal resemblance.

Answer by isomorphismes for Are there any interesting connections between Game Theory and Algebraic Topology?

2013-02-12T17:42:52Z

I'm coming from the other side: familiar with game theory and learning about algebraic topology.

I know Kakutani's fixed point theorem was used to simplify Nash's seminal paper.
If you think about a simple normal-form game like Prisoner's Dilemma or Coordination Game, 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.