You are currently browsing the tag archive for the ‘fixed point’ 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.

This post is a sequel to my previous ad of a joint paper with Yaron, in which we prove existence of pure ${\epsilon}$-equilibria in certain games. I am now going to make a fuss over the fact that our result is essentially a collection of logical relations between linear inequalities, yet its proof seems to require Brouwer’s fixed point theorem.

I start with emphasizing game theory’s reliance on Brouwer’s Theorem to prove Nash’s Theorem, an outrage with which I have more or less already learned to live. I call this an outrage because Nash’s Theorem is essentially a theorem about logical relationships between algebraic inequalities. More formally, fix integers ${n,m}$ and let ${\xi_{n,m}}$ be the assertion that every ${n}$-player game with ${m}$ strategies to every player admits a mixed Nash Equilibrium. Then ${\xi_{n,m}}$ is a first order sentence in the language of ordered fields. The signature of this language is ${(0,1,<,+,\times)}$ where ${0,1}$ are constant symbols, ${\leq}$ is a relation symbol and ${+,\times}$ are binary function symbols. (Skip the next paragraph if this is obvious to you).

Indeed, let ${\bar x}$ be a set of ${(m^n)\cdot n}$ variables, representing the payoff matrix of an ${n}$-player game with ${m}$ strategies for every player, and let ${\bar p}$ be a set of ${n\cdot m}$ variables representing a mixed strategies profile. Then

$\displaystyle \xi_{n,m}=\forall \bar x~\exists \bar p ~\phi(\bar x,\bar p)$

where ${\phi(\bar x,\bar p)}$ is a formula that says that ${\bar p}$ is a mixed Nash equilibrium in a game with payoff matrix ${\bar x}$. This is a conjunction of formulas that assert that ${\bar p}$ is indeed a mixed strategy profile (nonnegative elements which sum to ${1}$), and that if player ${i}$ plays action ${j}$ with a positive probability under this profile then player ${i}$ doesn’t gain from deviating to any pure strategy. The last assertion involved a somewhat unappealing term (the payoff for player ${i}$ under profile ${p}$ when the payoff matrix is ${\bar x}$), but this term is just products and additions of variables.

Now since by Tarski’s Theorem all real closed fields satisfy the same first order sentences, it follows that Nash’s Theorem is true in every real closed field ! Here is an interesting corollary of this conclusion: Every game in which the payoffs are algebraic numbers has an equilibrium in which the probabilities are algebraic numbers. Here is a more interesting corollary: In discounted stochastic games, an equilibrium strategy can be expressed as a fractional laurent series of the discount factor. This appears in a seminal paper (jstor) of Bewley and Kohlberg, who are to my knowledge the first to make this observation. I presented this paper in a students seminar back in grad school, probably the first paper in game theory I have ever read, and it is still one of my favorites.

Anyway, back to pure ${\epsilon}$-equilibrium. Read the rest of this entry »