6
$\begingroup$

Consider a normal form game with $n$ players (and finitely many options per player) defined by finite option sets $A_1,\ldots,A_n$ and payoff matrices $u_1,\ldots,u_n: \prod_{j=1}^n A_j \to \mathbb{R}$. Let $N$ be the set of Nash equilibria, which is a subset of the set $S := \prod_{j=1}^n S_j$ of mixed strategy profiles where $S_j$ is the linear simplex with vertex set $A_j$ (=set of mixed strategies on $A_j$).

General question: What interesting things can be said about this set $N$ of Nash equilibria, from a topological point of view?

Obviously it need not be connected (it can be a finite set of $>1$ points), and it's pretty clear that it's compact. But, to ask a specific question, is there an example where it has non-trivial $H_1$ (first homology group): can it be homeomorphic to a circle or an annulus?

[I asked this some time ago on MSE but received no response.]

$\endgroup$
  • 6
    $\begingroup$ Kohlberg & Mertens (Econometrica 1986) Show that the graph of the Nash Equilibrium correspondence is homotopic to a homeomorphism (Theorem 1). They also give an example of an particular game where the set of NE's is homeomorphic to a circle. $\endgroup$ – martin cripps Feb 21 '17 at 15:00
  • $\begingroup$ A very interesting corollary to this question has to do with the implications of the structure of the equilibrium manifold $E$ discussed by @kipper and in my answer below: given every extensive-form game admits a normal form representation, is it possible to define a suitable solution concept for extensive form games solely in terms of the topology of the equilibrium manifold at their normal form representation. $\endgroup$ – Pete Caradonna Mar 5 '17 at 22:31
4
$\begingroup$

Nash-equilibria satisfy a universality theorem. This is due to Ruchira Datta's paper "Universality Of Nash Equilibria", https://arxiv.org/pdf/math/0301001.pdf. From her abstract:

Every real algebraic variety is isomorphic to the set of totally mixed Nash equilibria of some three-person game, and also to the set of totally mixed Nash equilibria of an N-person game in which each player has two pure strategies.

$\endgroup$
4
$\begingroup$

To elaborate off Martin's comment, one can generally say a number of interesting things. Consider a fixed, finite set of players $N$ and, for each, a finite set of actions $S_i$ for $i \in N$. Then the space of all payoff functions for agent $i$ with these agents/actions can be identified with $\Gamma_i = \mathbb{R}^{\prod_i |S_i|}$, and the space of games with $\prod_i \Gamma_i$. Let $\Sigma = \prod_i \Delta(S_i)$, and define: $$E= \{(g,\sigma) \in \Gamma \times \Sigma : \textrm{$\sigma$ is a Nash equilibrium of $g$} \}.$$ Finally, for any locally compact space $K$, denote its one-point compactification as $\bar{K}$.

Now, results-wise, firstly it is straightforward from the definition of Nash equilibrium that $E$ is the graph of the 'equilibrium correspondence' $\phi: \Gamma \to \Sigma$, which is upper-hemicontinous in $g$. It is not, however, everywhere lower-hemicontinuous.$^1$

The result Martin cites may be formally stated as:

Theorem: (Kohlberg & Mertens 1986 Econometrica) Let $\bar{p}: \bar{E} \to \bar{\Gamma}$ denote the continuous extension of the projection $p:E \to \Gamma$ with $p(\infty) = \infty$. Then $\bar{p}$ is homotopic to a homeomorphism (under a homotopy taking $\infty$ to $\infty$ and $E$ to $\Gamma$).

This structure theorem tells us a great deal. For starters, there necessarily always exists a subset of Nash equilibria which are robust to any perturbation of payoffs as $\bar{E}$ is basically a deformed rubber sphere above/enclosing the sphere of games (in the sense that a nearby game has a nearby equilibrium).

Moreover, we have a particularly nice structure to work with: by the definition of von Neumann-Morgenstern utilities, the graph of $\phi$ may be defined as a finite collection of polynomial equalities and inequalities, and hence $\phi$ is a semi-algebraic correspondence (correspondence whose graph is a semi-algebraic set). In particular, for every game $g$, $\phi(g)$ admits a finite triangulation, i.e. there are finitely many connected components of equilibria for any game.

In light of this, at any point $g$ of lower-hemicontinuity of $\phi$, $\bar{p}^{-1}(g)$ is finite and there exists a neighborhood of $g$, $U$, for which $\bar{p}^{-1}(U)$ is a finite disjoint union of open balls. As deg$(\bar{p})=1$, then one obtains that at any point of lower-hemicontinuity of $\phi$, the set of Nash equilibria is finite and odd in number.

Furthermore, a result of Blume and Zame$^2$, the semi-algebraicity of $\phi$ implies that the set on which $\phi$ fails to be lower-hemicontinuous is strictly lower dimensional and hence of measure zero (note that we cannot just appeal to Sard's theorem to get this result as $E$ is not a smooth manifold). Hence the number of equilibria of a finite normal form game is generically finite and odd.

Thus to conclude, for generic games, not much interesting topologically happens (though to reach this point, in the spirit of your question, at least a little topology in the form of Brouwer degree rears its head). But for more interesting games, plenty can happen, within the purviews outlined above.


$^1$ For an example of this, it suffices to consider a 2x2 game with upper-left payoff pair $(1,1)$, lower-right $(t,t)$ for $t < 0$, and off-diagonal payoffs $(0,0)$. There is a unique Nash equilibrium, but at $t=0$ there are two.

$^2$ A lemma on page 3 of this paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.