16
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I'll just point out that combinatorial game theory (one of the tags) is not the same thing as just plain game theory, and it seems that you are interested in the more general game theory. Could someone with the power to do so create a game-theory tag and apply it here? $\endgroup$
    – Gabe Cunningham
    Commented Nov 4, 2009 at 15:57
  • $\begingroup$ A small nitpick: yes/no questions beg for a yes/no answer (homepages.tesco.net/~J.deBoynePollard/FGA/…). $\endgroup$
    – Ilya Nikokoshev
    Commented Jan 5, 2010 at 1:38
  • 1
    $\begingroup$ Is there a category of games? Can I stabilize it? Let's just go ahead and stabilize it. Get to work. $\endgroup$
    – Jonathan Beardsley
    Commented Feb 13, 2013 at 3:22
  • $\begingroup$ I see what you mean $(s_i^*, s_{-i}^*)$ is kind of like taking a tuple and deleting the $i$ component, which happens in the standard complex similarly. I have come up with an integer homology involving primes / numbers, but haven't got far enough yet to any problems! So it's likely you will find the homology measure and then not be able to do anything with it. $\endgroup$
    – Daniel Donnelly
    Commented May 18 at 22:01

12 Answers 12

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For a proof of the existence of Nash equilibria using the Brouwer fixed point theorem, read Nash's thesis: princeton.edu/mudd/news/faq/topics/… (He also wrote a proof using the Kakutani fixed point theorem, published in a paper earlier than his thesis.) $\endgroup$
    – Omar Antolín-Camarena
    Commented Mar 16, 2012 at 2:20
16
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is really cool! $\endgroup$
    – GMRA
    Commented Nov 4, 2009 at 23:17
9
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ See also Eckmann, Beno, Social choice and topology: a case of pure and applied mathematics, Expo. Math. 22 (2004), no. 4, 385–393. $\endgroup$
    – Mark Grant
    Commented Mar 16, 2012 at 9:58
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The following papers by Metrens propose homological definitions for "stable equilibria": Mertens, Jean-François Stable equilibria---a reformulation. I. Definition and basic properties. Math. Oper. Res. 14 (1989), 575--625; Stable equilibria---a reformulation. II. Discussion of the definition, and further results, Math. Oper. Res. 16 (1991), no. 4, 694--753. $\endgroup$
    – Gil Kalai
    Commented Jan 5, 2010 at 12:04
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The paper by Candogan et al. as well as Jiang, Xiaoye, et al. "Statistical ranking and combinatorial Hodge theory." arXiv preprint arXiv:0811.1067 (2008) do provide a beautiful application of algebraic topology to game theory. The idea is that of representing a game as a 1-dimensional simplicial complex and performing a discrete Hodge decomposition. Both papers use an Euclidean inner product to implicitly identify chains spaces and cochains spaces, so there is room for polishing and generalisation. $\endgroup$
    – DavideL
    Commented Dec 4, 2022 at 11:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .