You are currently browsing the tag archive for the ‘Nash equilibrium’ tag.

They say that when Alfred Tarski came up with his theorem that the axiom of choice is equivalent to the statement that, for every set ${A}$, ${A}$ and ${A\times A}$ have the same cardinality, he first tried to publish it in the French PNAS. Both venerable referees rejected the paper: Frechet argued there is no novelty in equivalence between two well known theorems; Lebesgue argued that there is no interest in equivalence between two false statments. I don’t know if this ever happened but it’s a cool story. I like to think about it everytime a paper of mine is rejected and the referees contradict each other.

Back to game theory, one often hears that the existence of Nash Equilibrium is equivalent to Brouwer’s fixed point theorem. Of course we all know that Brouwer implies Nash but the other direction is more tricky less known. I heard a satisfying argument for the first time a couple of months ago from Rida. I don’t know whether this is a folk theorem or somebody’s theorem but it is pretty awesome and should appear in every game theory textbook.

So, assume Nash’s Theorem and let ${X}$ be a compact convex set in ${\mathbf{R}^n}$ and ${f:X\rightarrow X}$ be a continuous function. We claim that ${f}$ has a fixed point. Indeed, consider the two-player normal-form game in which the set of pure strategies of every player is ${X}$, and the payoffs under strategy profile ${(x,y)\in X^2}$ is ${-\|x-y\|^2}$ for player I and ${-\|f(x)-y\|^2}$ for player II. Since strategy sets are compact and the payoff function is continuous, the game has an equilibrium in mixed strategies. In fact, the equilibrium strategies must be pure. (Indeed, for every mixed strategy ${\mu}$ of player II, player 1 has a unique best response, the one concentrated on the barycenter of ${\mu}$). But if ${(x,y)}$ is a pure equilibrium then it is immediate that ${x=y=f(x)}$.

Update I should add that I believe that the transition from existence of mixed Nash Equilibrium in games with finite strategy sets to existence of mixed Nash Equilibrium in games with compact strategy sets and continuous payoffs is not hard. In the case of the game that I defined above, if ${\{x_0,x_1,\dots\}}$ is a dense subset of ${X}$ and ${(\mu_n,\nu_n)\in \Delta(X)\times\Delta(X)}$ is a mixed equilibrium profile in the finite game with the same payoff functions and in which both players are restricted to the pure strategy set ${\{x_1,\dots,x_n\}}$, then an accumulation point of the sequence ${\{(\mu_n,\nu_n)\}_{n\geq 1}}$ in the weak${^\ast}$ topology is a mixed strategy equilibrium in the original game.

There are two equivalent ways to understand the best response property of a Nash Equilibrium strategy. First, we can say that the player plays a mixed strategy whose expected payoff is maximal among all possible mixed strategies. Second, we can say that the player randomly chooses a pure strategy from the set of pure strategies whose expected payoff is maximal among all possible pure strategies.

So far so good, and every student of game theory is aware of this equivalence. What I think is less known is that the two perspectives are not identical for ${\epsilon}$-best response and ${\epsilon}$-equilibrium: A mixed strategy whose expected payoff is almost optimal might put some positive (though small) probability on a pure strategy which gives a horrible payoff. In this post I am going to explain why I used to think the difference between the two perspectives is inconsequential, and why, following a conversation with Ayala Mashiah-Yaakovi about her work on subgame perfect equilibrium in Borel games, I changed my mind.

This is the most frustrating part in academic career: You come up with a cool idea, google around a bit for references, and discover that the Simpsons did it twenty years ago. It happened to Ronen and I recently when we were talking about computability of Nash equilibrium. Only thing left is to blog about it, so here we are.

A good starting point is the omitted paragraph from John Nash’ Thesis (scanned pdf), in which Nash motivates his new idea. The paragraph is not included in the published version of the thesis, it is not clear whether because of editorial intervention or Nash’ own initiative.