Reformulation of Nash Equilibrium with an
Application to Interchangeability
Yosuke YASUDA
Osaka University, Department of Economics [email protected]
August, 2015
Summary of My Talk
What is Reformulation? (1st Part)
The set of Nash equilibria, if it is nonempty, is identical to the set of minimizers of real-valued function.
Connect equilibrium problem to optimization problem.
→ Similar characterizations are known in the literature.
Is it Useful? (2nd Part)
Existing results on interchangeability can be derived, in a unified fashion, by lattice structure of optimal solutions.
→ Completely new results (re-interpretations)!
Main Messages
Please use/apply/extend my characterizationof NE!
2 / 23
Existing Formulations of NE: Equilibrium Approach
Strategy profile x∗ ∈ X is called Nash equilibrium if and only if,
1 Inequality (Incentive) Constraints
ui(x∗i, x∗−i) ≥ ui(xi, x∗−i) for all xi ∈ Xi and for all i ∈ N.
2 Solution to Multivariate Function ui(x∗i, x∗−i) = max
xi∈Xi
ui(xi, x∗−i) for all i ∈ N.
3 Fixed Point of BR Correspondence x∗ ∈ BR(x∗),
where BRi(x−i) = arg max
x′i∈Xi
ui(x′i, x−i).
Another Characterization: Optimization Approach
Definef : X →R, which aggregates maximum deviation gains (from a fixed action profile x ∈ X) across players.
f (x) =X
i∈N
max
x′
i∈Xi
ui(x′i, x−i) − ui(xi, x−i)
. (1)
Theorem 1
A strategy profile x∗ is a Nash equilibrium iff f (x∗) = 0. Theorem 2
If there exists an NE, the set of Nash equilibriaE∗ is identical to the set ofminimum solutionsto f , arg minx∈Xf (x).
4 / 23
Slight Modifications
Let g(x) = −f (x). The set of Nash equilibria, if it is nonempty, is identical to the set of maximum solutionsto g.
arg max
x∈X g(x).
Let t be a parameter contained in a parameter set T . Then, (1) can be rewritten to incorporate this parameterization.
f (x, t) =X
i∈N
max
x′i∈Xi
ui(x′i, x−i; t) − ui(xi, x−i; t)
. (2)
Could be useful for (monotone) comparative statics: e.g., to analyze conditions under which the set of optimal solutions, or its selection, is increasing in t ∈ T .
Special Case: Best Reply
Our formulation can also incorporatebest reply, since it is just a (degenerated) Nash equilibriumwhen there is one strategic player.
fi(x, t) = fi(xi; x−i, t)
= max
x′i∈Xi
ui(x′i; x−i, t) − ui(xi; x−i, t),
(Note x−i is fixed and considered as a parameter of the model.) Solving arg minxi∈Xifi(xi; x−i, t)is equivalent to deriving arg maxxi∈Xiui(xi; x−i, t).
Comparative statics analysis on best replies can be regarded as a special case of (2) above.
Our approach can reproduceall results in the literature, e.g., Milgrom and Roberts (1990); Milgrom and Shannon (1994).
6 / 23
Upper-hemi Continuity
TheNash correspondence, a mapping from parameter to Nash equilibria, is upper-hemi continuous under weak assumptions.
f (x, t) =X
i∈N
max
x′i∈Xi
ui(x′i, x−i; t) − ui(x; t)
.
Upper-hemi continuity of optimal solutions is given by theorem of the maximum by Berge (1963).
Continuityis preserved under addition.
Given that ui is continuous (for all i ∈ N ), f is continuous whenever max ui is continuous (for all i ∈ N ).
⇒ Conditions for continuity of max ui guarantees UHC of NE.
Further Characterization
For each i ∈ N , consider a functionψi :R+→R+ such that ψi(0) = 0, and define f : X →˜ R, using {ψi}i∈N as follows.
f (x) =˜ X
i∈N
ψi
xmax′ i∈Xi
ui(x′i, x−i) − ui(xi, x−i)
. (3)
LetZi be a set of nonnegative real numbers such that ψi takes 0. Zi = {z ∈R+|ψi(z) = 0}.
Theorem 3
Fix {ψi}i∈N in (3). Then, the following holds.
(i) For any game, everyNE x∗ must satisfyf (x˜ ∗) = 0.
(ii) Strategy profile x that satisfies ˜f (x) = 0 must be an NE for any game, iffZi = {0}for all i ∈ N .
(iii) If Zi = {0} for all i ∈ N and there is an NE, E∗ is identical to the set ofminimum solutions to ˜f , arg minx∈Xf (x).˜
8 / 23
From “Sum” to “Product”
The parallel characterization can be available when the objective function is replaced with theproduct of deviation gains.
f (x) =Πi∈N
1 + max
x′i∈Xi
ui(x′i, x−i) − ui(xi, x−i)
. (4)
Note by construction thatf (x) ≥ 1holds for any x ∈ X. Theorem 4
A strategy profile x∗ is an NE ifff (x∗) = 1. If there is an NE, E∗ is identical to the set ofminimum solutions to f ,arg minx∈Xf (x).
1 can be replaced with anyε > 0. (Then, f (x∗) = εn)
As ε goes to 0, (4) converges to the product of players’ payoff differences, which may look similarto the Nash product.
Relation with Nash Demand Game
Each player i = 1, 2 chooses herdemand, di(> ui).
(d1, d2) realizes iff (d1, d2) ∈ B, the set of feasible payoffs. If (d1, d2) /∈ B, players receive (u1, u2).
⇒ Multiplicity of equilibria due to payoff discontinuity.
Introducingh(d1, d2), Nash (1953) considers the smoothed game. Payoff becomes dih(d1, d2), where h(d1, d2) = 1 for d ∈ B. h rapidly shrinks to 0 as d move away from B.
Fact 5 (Nash, 1953)
NE of the smoothed game isunique and characterized by arg max
d>u (d1− u1)(d2− u2)h(d1, d2) ← Potential Function which converges to the Nash barging solution.
arg max
u(>u)∈B(u1− u1)(u2− u2). 10 / 23
Interchangeability for Two-Person Games
Let x = (x1, x2) and x′ = (x′1, x′2) be two distinct NE. Definition 6
A pair of Nash equilibia x and x′ is called interchangeable if (x1, x′2) and(x′1, x2)constitute NE of the same game. Our approach can explain the following existing results on interchangeability,independently derived in the literature:
1 for a zero-sum game any pairs of its mixed strategy Nash equilibria are interchangeable (Luce and Raiffa, 1957).
2 for a supermodular game where each player’s strategy space is totally ordered, any unordered pairs of the pure strategy Nash equilibria are interchangeable (Echenique, 2003).
3 equilibrium set of astrictly supermodular game with totally ordered strategy spaces, is totally ordered (Vives, 1985).
Introduction to Lattice
Let ≧ be abinary relation on a non-empty set S. Definition 7
The pair (S, ≧) is a partially ordered set if, for x, y, z in S, ≧ is reflexive: x ≧ x.
transitive: x ≧ y and y ≧ z implies x ≧ z. antisymmetric: x ≧ y and y ≧ x implies x = y.
A partially ordered set (S, ≧) is
totally ordered if for x and y in S either x ≧ y or y ≧ x is satisfied, and is called chain.
called lattice if any two elements have a least upper bound (join, ∨) and a greatest lower bound (meet, ∧) in the set. A subset S∗(⊂ S) is called sublattice if x′∧ x′′∈ S∗ and x′∨ x′′∈ S∗ hold for any x′, x′′ ∈ S∗.
12 / 23
Sublattice and Interchangeability
Assume each player’s strategy istotally ordered, e.g., Xi ⊂R.
→ For any pair of strategy profiles, its meet/join constitutes strategy profilewhere every player takes smaller/larger strategy. 0. If E∗ is (non-empty)lattice, then
The existence of maximumandminimumNE is guaranteed. 1. If E∗ is sublattice, then
Any unorderedpairs of the NE must be interchangeable.
← Let x = (x1, x2) and x′ = (x′1, x′2) be two unordered NE. Sublattice property implies that both (x′1, x2) and (x1, x′2) must be elements in E∗ and hence NE.
→ This doesnotimply interchangeability of ordered NE. 2. If E∗ is chain, then
All NE must be totally ordered.
Submodular and Supermodular Functions
Definition 8
A real-valued function h defined over alattice S is called a submodular function if, for any x′, x′′∈ S, h satisfies
h(x′∧ x′′) + h(x′∨ x′′) − {h(x′) + h(x′′)} ≤ 0. (5)
(5) trivially holds with equalitywhenever x′ and x′′ are ordered, i.e., x′ ≧ x′′ or x′ ≦ x′′.
If ≤ in (5) is replaced with ≥, h is called supermodular. h : S →R becomes a strictly submodular function if, for any unorderedpair x′, x′′∈ S, i.e., x′ x′′ and x′ x′′, h satisfies
h(x′∧ x′′) + h(x′∨ x′′) − {h(x′) + h(x′′)} < 0. (6) If < in (6) is replaced with >, h is strictly supermodular.
14 / 23
Lattice Properties
Fact 9 (Topkis, 1978)
If h is asubmodularfunction on a lattice S, then the set S∗ of points at which h attains its minimum on S is asublattice of S. Fact 10 (Topkis, 1978)
If h isst. submodularon a lattice S, then the set S∗ of points at which h attains its minimum on S is achain.
Assume X is a lattice. The above facts imply the following. Lemma 11
Suppose that f is defined by (1) and E∗ is nonempty. Then, (i) If f is submodularon X, then E∗ is asublattice of X. (ii) If f is st. submodularon X, then E∗ is achain.
Supermodularity and Complementarity
If, for all i ∈ N , ui is a
supermodular function ⇐⇒ Supermodular game.
st. supermodular function ⇐⇒ St. supermodular game. h : X →R is called a quasi-supermodular function if, for all x and x′ in X,
h(x) ≥ h(x ∧ x′) implies h(x ∨ x′) ≥ h(x′), and h(x) > h(x ∧ x′) implies h(x ∨ x′) > h(x′).
A game with strategic complementarities (GSC) is aweaker notion than supermodular game, which requires that each player’s best reply is (weakly) increasingin other players’ strategies. Fact 12 (Milgrom and Shannon, 1994)
A quasi-supermodular game is identical to a GSC.
16 / 23
Supermodular Game
Let us define u as the sum of the payoff functions. u(x) = u1(x) + u2(x) for all x ∈ X.
Lemma 13
u (= u1+ u2) is supermodular for any supermodular games, and u is st. supermodular for any st. supermodular games.
Supermodularity is preserved under addition. The converse is not true, e.g.,zero-sum game. Theorem 14
For any two-person game with totally ordered strategy space for each player,
(i) f is submodulariff u is supermodular. (ii) f is st. submodulariff u is st. supermodular.
Proof (1)
Recall that f is a submodular function if, for any x′, x′′∈ X, f (x′∧ x′′) + f (x′∨ x′′) − {f (x′) + f (x′′)} ≤ 0. (7) If the above inequality is strict for anyunorderedpairs, f is a st. submodularfunction. Since we consider two-person games,
f (x) = max
x1∈X1
u1(x1, x2) − u1(x1, x2) + max
x2∈X2u2(x1, x2) − u2(x1, x2).
Now consider a pair ofunordered strategy profiles, x′= (x′1, x′2) and x′′= (x′′1, x′′2). W.o.l.g, assume x′1≧1 x′′1 and x′2≦2 x′′2.
Join: x′∧ x′′ = (x′′1, x′2) Meet: x′∨ x′′= (x′1, x′′2)
18 / 23
Proof (2)
The corresponding values of f are expressed by f (x′∧ x′′) = max
x1∈X1
u1(x1, x′2) − u1(x′′1, x′2) + max
x2∈X2u2(x
′′
1, x2) − u2(x
′′ 1, x
′ 2).
f (x′∨ x′′) = max
x1∈X1u1(x1, x
′′
2) − u1(x′1, x′′2)
+ max
x2∈X2
u2(x′′1, x2) − u2(x′1, x′′2).
Substituting them into (7), max ui parts will be canceled out. The next equality illustrates that the (st.) submodularity of f is completely characterized by the (st.) supermodularityof u.
Proof (3)
f (x′∧ x′′) + f (x′∨ x′′) − {f (x′) + f (x′′)}
= − { u1(x′′1, x′2) + u2(x′′1, x′2) + u1(x′1, x′′2) + u2(x′1, x′′2)} +u1(x′1, x2′) + u2(x′1, x′2) + u1(x′′1, x′′2) + u2(x′′1, x′′2)
= − { u1(x′∧ x′′) + u2(x′∧ x′′) + u1(x′∨ x′′) + u2(x′∨ x′′)} +u1(x′) + u2(x′) + u1(x′′) + u2(x′′)
= u(x′) + u(x′′) − {u(x′∧ x′′) + u(x′∨ x′′)}.
Lemma 13, combined with Theorem 14, implies the following. Corollary 15
For any two-person
(i) supermodular games, f issubmodular. (ii) st. supermodular games, f isst. submoduler.
20 / 23
Interchangeability for Zero-Sum Game
Theorem 16
For a zero-sum game,anypairs of its (mixed strategy) Nash equilibria areinterchangeable.
Proof.
E∗ is nonempty.
Existence of NE by Nash (1950)
Existence of minimax solution by Neumann (1928).
Suppose that x = (x1, x2) and x′ = (x′1, x′2) are two distinct NE. We can always construct an orderthat satisfies
x1≧1 x′1 and x2 ≦2 x′2.
By Lemma 11 (i), E∗ issublattice.
⇒ x ∧ x′ = (x′1, x2) and x ∨ x′= (x1, x′2) are both NE.
Interchangeability for Supermodular Game
Since the existence of (pure strategy) NE for supermodular games is guaranteed by Topkis (1979), we obtain the next theorem. Theorem 17
Assume strategy space for each player is totally ordered. Then, (i) For a two-person supermodular game, anyunordered pairs of
its pure strategy NE are interchangeable.
(ii) For a two-person st. supermodular game, all pure strategy NE are totally ordered.
Theorem 18
Assume that strategy space for each player is totally ordered. Then, for a two-person GSC, anyunorderedpairs of its pure strategy NE areinterchangeable.
22 / 23
Conclusion
Summary: I provide a reformulation/reinterpretation of NE. Enables us to analyze Nash equilibrium as a solution to a simple optimization problemwithout any constraints. May bridge a gap (if it exists) between non-cooperative game theory and otherrelated fields such as OR and CS.
Natural Reaction: So what? Is it really useful?
→ As an application, I revisit interchangeability of NE. Existing results on two person (i) zero-sum games and (ii) supermodular games can be derived, in a unified fashion, by lattice structure of optimal solutions:
The set of minimizers of submodular function is sublattice.
