This post is a sequel to my previous ad of a joint paper with Yaron, in which we prove existence of pure -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 and let
be the assertion that every
-player game with
strategies to every player admits a mixed Nash Equilibrium. Then
is a first order sentence in the language of ordered fields. The signature of this language is
where
are constant symbols,
is a relation symbol and
are binary function symbols. (Skip the next paragraph if this is obvious to you).
Indeed, let be a set of
variables, representing the payoff matrix of an
-player game with
strategies for every player, and let
be a set of
variables representing a mixed strategies profile. Then
where is a formula that says that
is a mixed Nash equilibrium in a game with payoff matrix
. This is a conjunction of formulas that assert that
is indeed a mixed strategy profile (nonnegative elements which sum to
), and that if player
plays action
with a positive probability under this profile then player
doesn’t gain from deviating to any pure strategy. The last assertion involved a somewhat unappealing term (the payoff for player
under profile
when the payoff matrix is
), 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 -equilibrium. Yaron and I defined the Lipschitz Constant of a game as the maximal change in a player’s payoff when one of her opponents changes his strategy. Theorem 2.2 in our paper says that if
then every game with Lipschitz constant smaller than
admits pure
-equilibrium.
Fix now integers and rational numbers
. Let
be the assertion that every
-player game with
strategies for every player and Lipschitz constant
admits an
-equilibrium. Then
is a first order sentence in the language of ordered fields without multiplication. (Again, skip the next paragraph if this is obvious)
Indeed, let be a set of
variables indexed
for every strategy profile
and player
, representing the payoff matrix of an
-player game with
strategies for every player. Then
The antecedent is a conjunction of linear inequalities , each asserts that the payoff of a certain player under a certain profile does not change by more than
if a certain opponent changes his strategy. Thus, each such
is of the form
, where
are two strategy profiles that differs in one of player
-s opponents. The consequent is a disjunction over all strategy profiles
, and for every such
a conjunction of linear inequalities
, that assert the fact that under
a certain player cannot gain more than
by a certain deviation. Thus, each of these
is of the form
, where
is a strategy profile that differs from
only in the
-th coordinate.
Now if then
is valid in
. Our proof for this theorem relies on Nash’s Theorem and so, again, on uncle Brouwer’s theorem, which seems even more outrageous than the mixed strategies case, since this time there is not even multiplication involved. It’s just a theorem about relationships between finite number of linear inequalities.
At this point I hope you are telling to yourself something like `Brouwer’s Theorem to show that a bunch of linear inequalities imply a bunch of other linear inequalities !? These guys are killing a mite with a cruise missile.’ But in fact we have an elementary argument that our theorem, which we prove by Nash’s Theorem, also implies Nash’s Theorem. The idea is very simple, and is based on replacing each player in a game by a large number of agents, such that a pure equilibrium in the game played by the agents translates to a mixed equilibrium in the original game. The details are in Section 8 of our paper(pdf).
Open Problem: We know that Nash’s Theorem is still valid when payoffs are in some real algebraic field. But in order to speak about pure -equilibrium, one only needs payoffs to be in an ordered commutative group. So let
be such that
(or some other similar inequality). Is it true that every game with payoffs in some ordered commutative group and Lipschitz Constant smaller than
admits pure
equilibrium ?
6 comments
October 7, 2010 at 9:28 pm
repeated games
Bewley and Kohlberg’s theorem covers zero-sum discounted stochastic games, but i guess an analogous result holds for the non-zero-sum case. Are you aware of any application of this beautiful result (in the non-zero-sum case)?
October 8, 2010 at 1:56 pm
Eran
Right, i hope i am not completely misunderstanding something here, but it seems to me that their result and proof hold for the non-zero sum case: the assertion that for every discount factor there exists a stationary equilibrium is a first order sentence, and so it is also valid in the field of real Puiseux series. But now i am a bit worried because i can’t find a reference for this and my memory clearly plays some nasty trick on me since i thought they had non-zero-sum games in their paper.
Maybe our house expert on stochastic games will pop up and save me, and bring some applications with him too.
October 12, 2010 at 12:44 am
Eran
This discussion paper of Abraham Neyman http://www.ratio.huji.ac.il/dp_files/dp272.pdf proves something slightly more general: Theorem 5 shows that the equilbirium strategies can be chosen to be semi-algebraic functions of the discount factor, and by Theorem 2 this implies that they can be represented as a Puiseux series in the discount factor for sufficiently small discount factor.
As I said, Bewely & Kohlberg proof seems to provide the Puiseux expansion also for the non zero-sum case. I guess the reason they wrote it for zero-sum games is that they used their theorem to prove the asymptotic behavior of the value of the game as a function of the discount factor
October 11, 2010 at 9:43 am
Anonymous
Holder’s theorem asserts that any Archimedean linearly ordered group is isomorphic to a subgroup of the additive group of the real numbers.
I guess it means that the above result extends to Archimedean linearly ordered groups, doesn’t it?
October 12, 2010 at 12:43 am
Eran
right. thanks ! I still think it might be true also for non-archimedean groups (for example, it is true for the additive group of every real closed fields)
January 4, 2011 at 4:31 pm
Computability of Nash Equilibrium « The Leisure of the Theory Class
[…] Tarski’s Theorem that real algebraic fields are elementary isomorphic (I also wrote about it here. Thus, Nash’s Theorem, being a first order statement, is also true in the field of computable […]