Extreme Correlated and Nash Equilibria in Two-Person Games

Martin W. Cripps ^{∗} University of Warwick, Coventry CV4 7AL, GB.

May 1992, This version November 1995

* My thanks are due to Françoise Forges and to Jean-François Mertens (for their encouragement, helpful suggestions and for spotting an error in an earlier version of this paper), to Jonathan Cave (who commented on this work in its early stages), to Ehud Kalai an associate editor and referee’s (who’s comments greatly improved the exposition) and finally to seminar participants at CORE.

Abstract: I show that if σ is the correlated equilibrium distribution generated by an extreme Nash equilibrium of a bimatrix game, then σ is an extreme point of the set of correlated equilibria of the bimatrix game. I provide simple conditions for the set of correlated equilibrium distributions to be different from the set of correlated equilibrium distributions derived from Nash equilibria.

Keywords: Correlated equilibrium.

JEL Classification Number: C70.

Running Head: Extreme Correlated and Nash Equilibria

Address: Martin Cripps, Department of Economics, University of Warwick, Coventry CV4 7AL, UK.

1. Introduction

The set of Nash equilibrium strategy pairs of a bimatrix game is a finite union of convex polytopes, called maximal Nash subsets. An extreme point of such a polytope is called an extreme equilibrium. I will show that each extreme equilibrium generates a correlated equilibrium distribution that is an extreme point of the set all correlated equilibrium distributions for the bimatrix.

I will also provide a sufficient condition for the existence of a correlated equilibrium distribution that cannot be written as a convex combination of Nash equilibria. First assume the game has a mixed, quasi-strict, extreme equilibrium and restrict the players to use actions in the support of this equilibrium. Choose a strategy pair for this submatrix so that each player plays a worst response to their opponent’s strategy (such a strategy pair is called an anti-Nash equilibrium here).^{1} I will show that provided the above two steps are possible and yield distinct strategies, then there is a linear combination of the anti-Nash equilibrium and the quasi-strict extreme equilibrium which generates a correlated equilibrium distribution.

2. The Derived Game

I study finite bimatrix games, denoted (A, B), where the row player has the pure strategies I := {1, 2, ..., m}, the column player has the pure strategies J := {1, 2, ..., n}, and the payoffs are described by the matrices (A, B), where A := {a_{ij}}_{i∈Ij∈J} and B := {b_{ij}}_{i∈Ij∈J}. I will also use p = (p_{1}, p_{2}, ..., p_{m})^{T} ∈ Δ^{m} and q = (q_{1}, q_{2}, ..., q_{n})^{T} ∈ Δ^{n} to denote the players’ mixed strategy vectors.^{2} The set of all Nash equilibria of (A, B) is denoted E(A, B) ⊆ Δ^{m} × Δ^{n}, where E(A, B) := {(p, q)|(p − p′)^{T} Aq ≥ 0 ∀p′ ∈ Δ^{m}; p^{T} B(q − q′) ≥ 0 ∀q′ ∈ Δ^{n}}.

A correlated strategy for (A, B) induces a distribution over the action pairs in I × J, the distribution of a correlated strategy is denoted by σ = (σ_{11}, ..., σ_{1n}, σ_{21}, ..., σ_{2n}, ...σ_{mn}) ∈ Δ^{nm}. The set of all correlated equilibrium distributions of (A, B) is denoted by C(A, B) ⊆ Δ^{mn} where C(A, B) := {σ| ∑_{j} σ_{ij}(a_{ij} − a_{kj}) ≥ 0 i, k ∈ I; ∑_{i} σ_{ij}(b_{ij} − b_{ih}) ≥ 0, j, h ∈ J}. Of course, when the players play the strategies (p, q) they induce a probability distribution over action pairs so I define σ(p, q) to be this distribution, that is σ_{ij}(p, q) := p_{i}q_{j} for all i ∈ I and j ∈ J. If (p, q) ∈ E(A, B) then σ(p, q) is a correlated equilibrium, and the set of correlated equilibria that use only convex combinations of Nash equilibria is C_{N}(A, B) := co{σ(p, q)|(p, q) ∈ E(A, B)}.^{3}

1My thanks are due to Jonathan Cave for suggesting this name to me.

2The superscript T denotes the transpose of a vector and Δ^{k} := {x ∈ ℜ^{k}|x ≥ 0, 1^{T} x = 1}, where 1 = (1, 1, ..., 1)^{T}.

Hart and Schmeidler (1989) introduce a two-person zero-sum game with payoffs derived from (A, B). The (expected) payoff function in this game is P (σ, θ) where

P (σ, θ) = ρ ∑_{i∈I} ∑_{k∈I} ∑_{j∈J} σ_{ij}π_{ik}(a_{ij} −a_{kj})+(1−ρ) ∑_{j∈J} ∑_{h∈J} ∑_{i∈I} σ_{ij}τ_{jh}(b_{ij} −b_{ih}). (1)

Here σ ∈ Δ^{mn} is the mixed strategy of the row player and θ^{T} := (ρπ^{T} , (1 − ρ)τ^{T}) ∈ Δ^{mm+nn} is the mixed strategy of the column player, where 0 ≤ ρ ≤ 1. Thus σ = (σ_{11}, ..., σ_{1n}, σ_{21}, ...σ_{2n}, ...σ_{mn}) is the same dimension as a correlated strategy for (A, B) whereas π = (π_{11}, ..., π_{1m}, π_{21}, ...π_{2m}, ...π_{mm}) and τ = (τ_{11}, ..., τ_{1n}, τ_{21}, ...τ_{2n}, ...τ_{nn}) are not. The payoff function P (σ, θ) is a bilinear form and can be written P (σ, θ) = σ^{T} Gθ where the matrix G is described below.

G = [G_{1}|G_{2}]

where

G_{1} = [ \begin{matrix}a_{11} − a_{11} & ⋯ & a_{11} − a_{m1} \\ a_{12} − a_{12} & ⋯ & a_{12} − a_{m2} \\ ⋮ & & ⋮ & & & & & & 0 \\ a_{1n} − a_{1n} & ⋯ & a_{1n} − a_{mn} \\ & & & . & . & . \\ & & & & & & a_{m1} − a_{11} & ⋯ & a_{m1} − a_{m1} \\ & 0 & & & & & a_{m2} − a_{12} & ⋯ & a_{m2} − a_{m2} \\ & & & & & & ⋮ & & ⋮ \\ & & & & & & a_{mn} − a_{1n} & ⋯ & a_{mn} − a_{mn} \end{matrix} ]

3co{.} is used to denote the convex hull of the set.

G_{2} = [ \begin{matrix}b_{11} − b_{11} & ⋯ & b_{11} − b_{1n} & 0 & ⋯ & 0 & ⋯ \\ 0 & ⋯ & 0 & b_{12} − b_{11} & ⋯ & b_{12} − b_{1n} & 0 \\ ⋮ & & ⋮ & 0 & ⋯ & 0 & b_{13} − b_{11} \\ b_{21} − b_{21} & ⋯ & b_{21} − b_{2n} & ⋮ & & ⋮ \\ 0 & ⋯ & 0 & b_{22} − b_{21} & ⋯ & b_{22} − b_{2n} & 0 \\ ⋮ & & ⋮ & 0 & ⋯ & 0 & b_{23} − b_{21} \\ & ⋮ & & & ⋮ \\ b_{m1} − b_{m1} & ⋯ & b_{m1} − b_{mn} & 0 & ⋯ & 0 & ⋯ \\ 0 & ⋯ & 0 & b_{m2} − b_{m1} & ⋯ & b_{m2} − b_{mn} & ⋯ \\ & ⋮ & & & ⋮ \end{matrix} ]

I will use (G, −G) to denote the derived game. The conventions used for ordering the players’ actions in (G, −G) give the matrices G_{1} and G_{2} their form. The nm × m^{2} matrix G_{1} is block-diagonal with m blocks along the diagonal. The ith diagonal block of G_{1} has m columns that give expected payoffs − ∑_{j∈J} σ_{ij}(a_{ij} − a_{kj}) to the column player in (G, −G). These payoffs are identical to the linear functions in the definition of a correlated equilibrium distribution. The nm × n^{2} matrix G_{2} does not have a block-diagonal structure (because of the ordering chosen for σ), but there is a permutation of the rows which will give it a block-diagonal structure. The expected payoffs from the columns are − ∑_{i∈I} σ_{ij}(b_{ij} −b_{ih}) and these are the other linear functions in the definition of a correlated equilibrium. The derived game (G, −G) is important because of the following result.

Result 1 (Hart and Schmeidler) σ ∈ C(A, B) if and only if σ is an optimal strategy for the row player in the zero-sum game (G, −G). The value of (G, −G) is zero.

3. Extreme Correlated Equilibrium Distributions in Two-Person Games

In Proposition 1 I use the Shapley-Snow Theorem applied to (G, −G) to characterize the extreme points of C(A, B). In the main result, Proposition 2, I then show that any extreme equilibrium generates a correlated equilibrium that satisfies this characterization.

For any zero-sum game (D, −D) the set E(D, −D) is the Cartesian product of the set of optimal strategies for the row player and the set of optimal strategies for the column player. The Shapley-Snow Theorem, quoted below, characterizes the extreme points of E(D, −D).

Result 2 (Shapley-Snow) In a zero-sum game (D, −D) with the value v ≠ 0: (i) The set E(D, −D) is convex and has a finite number of extreme points. (ii) (p, q) ∈ E(D, −D) is an extreme point of E(D, −D), if and only if , D has a non-singular submatrix D′ such that: the rows of D′ contain the support of p, the columns of D′ contain the support of q, D′q′ = v1, (p′)^{T} D′ = v1^{T}, where p′,q′ are vectors obtained from p,q with appropriate deletions of zeros.

By Result 1 the game (G, −G) has a zero value, so to apply the Shapley-Snow Theorem to this game it is necessary to add a constant δ ≠ 0 to every payoff. Let U be defined to be the matrix with unity in every entry, then the zero-sum game (G + δU, −G − δU) has a value δ and E(G, −G) = E(G + δU, −G − δU), by linearity.

Proposition 1 σ is an extreme point of C(A, B) if and only if σ is an optimal strategy for the row player in (G, −G) and there exists a non-singular submatrix R of G + δU with rows that contain the support of σ such that (σ′)^{T} R = δ1^{T}, where σ′ is σ with appropriate zero elements deleted.

\underline{Proof:} If σ is an extreme point of C(A, B) then it is an extreme point of the set of optimal strategies for the row player in (G + δU, −G − δU) (by Result 1). The existence of R then follows from Result 2.

Let σ be an optimal strategy for the row player in (G, −G) and (σ′)^{T} R = δ1^{T} where R is a non-singular submatrix of G+δU. (i) If R contains a column of δ’s then there exists an optimal strategy, θ, for the column player (play the column of δ’s) such that Rθ′ = δ1. By Result 2 (σ, θ) is an extreme point of E(G + δU, −G − δU) and E(G, −G). This set is a Cartesian product so σ is an extreme point of the set of optimal strategies for the row player and an extreme point of C(A,B). (ii) If R does not contain a column of δ’s and (σ′)^{T} R = δ1^{T} then R has at least two columns. Call the last two columns of R the vectors r_{1} and r_{2}, R = [Y r_{1}r_{2}]. Let S be the matrix R with the last column replaced by δ1 and let T be the matrix R with the second from last column replaced by δ1. Both S and T are also submatrices of G + δU. One of the matrices S and T is non-singular. Suppose not, then there exists weights (a_{1}, a_{2}, b_{1}, b_{2}) such that Y a_{1} + r_{1}a_{2} + δ1 = Y b_{1} + r_{2}b_{2} + δ1 = 0. (Without loss of generality the weight on the vector δ1 can be normalised to unity.) Subtract the middle from the left above to show that the columns of R are linearly dependent, which is a contradiction. Thus either S or T is non-singular. This gives a non-singular submatrix R′ of G + δU and an optimal strategy θ (play the column of δ’s) for the column player such that: (σ′)^{T} R′ = δ1^{T} and R′q′ = δ1. Q.E.D.

The set E(A, B) does not have as simple a structure as E(G, −G). In general E(A, B) is a union of convex sets of strategies. Let S be a subset of E(A, B). If S has the property that (p, q), (p′, q′) ∈ S implies (p, q′), (p′, q) ∈ S, then S is called a Nash subset. A maximal Nash subset, is a Nash subset S with the property that there is no Nash subset S′ that properly contains S. Each maximal Nash subset is the Cartesian product of two convex polytopes (Jansen 1981). Thus maximal Nash subsets have a finite number of extreme points and I will call these extreme points extreme equilibria. (Notice that these extreme points are defined relative to the maximal Nash subsets and are not necessarily extreme points of the larger set E(A, B).) Below I quote the characterization of the extreme equilibria in E(A, B) which is due to Kuhn and Vorobev and can also be found in Jansen (1981).

Definition 1 The pair (p, q) ∈ E(A, B) is an extreme equilibrium if (p, q) is an extreme point of a maximal Nash subset.

Result 3 (Kuhn-Vorobev) If (p, q) is an extreme equilibrium of (A, B), then there exists square submatrices A′,B′ of A and B such that: (i) The columns of A′ are the support of q and the rows of B′ are the support of p. (ii) A′q′ = a1, (q′)^{T} B′ = b1^{T} where p′,q′ are vectors obtained from p,q with appropriate deletions of zeros. (iii) The matrices H,K are non-singular, where

H = [ \begin{matrix}A′ & −1 \\ 1^{T} & 0 \end{matrix} ] , K = [ \begin{matrix}B′ & −1 \\ 1^{T} & 0 \end{matrix} ] .

The main result shows that if (p, q) is an extreme equilibrium then σ(p, q) satisfies the necessary and sufficient conditions for an extreme point of C(A, B) given in Proposition 1. It follows that the extreme points of C_{N}(A, B) are extreme points of C(A, B) and that no extreme point of C_{N}(A, B) can be written as a non-trivial convex combination of points in C(A,B).

Proposition 2 Let (p, q) ∈ E(A, B) be an extreme equilibrium, then σ(p, q) is an extreme point of C(A, B).

\underline{Proof:} Let (p, q) ∈ E(A, B) be an extreme equilibrium, without loss of generality assume p_{i} > 0 iff i = 1, 2, ..., c ≤ m and q_{j} > 0 iff j = 1, 2, ..., d ≤ n. The distribution σ(p, q) plays rows 1, 2, ..., d, n+1, n+2, ..., n+d, ..., cn+1, cn+ 2, ..., cn + d of G + δU with positive probability, cd rows in total. Suppose that there exists weights: μ_{1}, ..., μ_{d}, μ_{n+1}, ..., μ_{n+d}, ..., μ_{cn+d} so that a linear combination of these cd rows sums to zero. As the first column of G + δU is δ1 we have ∑_{t} μ_{t} = 0 (where the summation ranges over all the weights μ_{t}).

Consider the rows 1,2,...,d of G + δU. These are the only rows with weights μ_{d} that have non-δ entries in the first d columns. Inspection of G_{1} shows that the first d entries of the first d rows of G + δU are the vectors: (δ + a_{11})1^{T} − (a_{.1})^{T}, (δ + a_{12})1^{T} − (a_{.2})^{T}, ..., (δ + a_{1d})1^{T} − (a_{.d})^{T}, where a_{.j} is a vector containing the first d entries of the jth column of A. If the cd rows of G+δU with weights μ_{t} sum to zero, then the first d columns satisfy ∑_{t=1}^{d} μ_{t}[(δ+ a_{1t})1 − a_{.t}] + ∑_{t>d} μ_{t}δ1 = 0, or equivalently ∑_{t=1}^{d} μ_{t}a_{.1} − ∑_{t=1}^{d} a_{1t}μ_{t}1 = 0. This will be satisfied if μ_{t} = 0 for t = 1, 2, ..., d. Suppose that μ_{t} ≠ 0 for some t. Since (p, q) is an extreme equilibrium the vectors (a_{.1}, a_{.2}, ..., a_{.d}) are the columns of the matrix A′ described in Result 3. Thus the above expression gives a linear combination of the columns that make up the first d rows of the matrix H in Result 3. As H is non-singular there is no non-trivial combination of the columns of H that sum to zero so this implies ∑_{t=1}^{d} μ_{t} ≠ 0. Define λ = (λ_{1}, ..., λ_{d})^{T} so that λ_{t} = μ_{t}/ ∑_{t=1}^{d} μ_{t}, then from above A′λ = α1 where α = ∑_{t=1}^{d} a_{1t}λ_{t}. The pair (p, q) is an extreme equilibrium so by Result 3 A′q′ = a1, where q′ is q with zero elements deleted. The vector ((q′−λ)^{T} , α−a) therefore gives a linear combination of the columns of H so that they sum to zero. The columns of H are linearly independent so q_{j} = μ_{j}/ ∑_{t=1}^{d} μ_{t} for j = 1, 2, ..., d. Thus if one of the weights μ_{t} for t = 1, 2, ..., d is non-zero they must all have the same sign and be proportional to the equilibrium strategy q.

Repeat the above argument for each of the c blocks of d rows in G_{1} + δU that are in the support of σ(p, q) This shows that for i = 1, 2, ..., c the weights (μ_{in+1}, μ_{in+2}, ..., μ_{in+d}) are either all zero or all have the same sign.

There is a permutation of the rows which transforms G_{2} into block-diagonal form. After this permutation perform the same analysis on the first block of c rows of G_{2} + δU. By using the fact that the matrix K, of Result 3, is nonsingular it can be shown that either the vector (μ_{1}, μ_{d+1}, ..., μ_{(c−1)d+1}) is zero or all of its elements have the same sign. Thus either μ_{t} has the same sign for all t or μ_{t} = 0 for all t. If all the μ_{t}’s have the same sign then this contradicts ∑_{t} μ_{t} = 0. Thus μ_{t} = 0 for all t and the rows of G + δU in the support of σ are linearly independent.

This not only shows that the rows in the support of σ are linearly independent but that only columns of G giving a payoff of δ to the column player in (G + δU, −G − δU) were used in the calculation. Thus, because (p, q) is a Nash equilibrium, there exists a non- singular cd-dimensional submatrix R of G+δU such that (σ′)^{T} R = δ1^{T} (where σ′ is σ(p, q) with appropriate deletions). By Proposition 1 σ(p, q) is an extreme point of C(A, B). Q.E.D.

4. Correlated Equilibrium Distributions and C_{N}(A, B)

In this final section I give one explanation for why C_{N}(A, B) ≠ C(A, B) and, in general, some private information is necessary at a correlated equilibrium. It is not, however, a complete explanation of the differences between C(A, B) and C_{N}(A, B), because Forges (1985 p.143) gives an example of a game (A, B) where an action profile (i, j) is played with positive probability at a correlated equilibrium distribution but the game (A, B) has no Nash equilibrium that plays (i, j) with positive probability.

Consider the game (A, B) described below.

(A, B) = [ \begin{matrix}(4, 4) & (1, 5) \\ (5, 1) & (0, 0) \end{matrix} ]  (2)

This game has one mixed strategy Nash equilibrium; p = q = (1/2, 1/2). Define (Â, B̂) to be the submatrix of (A, B) where the agents can only use pure strategies in the support of (p, q), in this case (Â, B̂) = (A, B). Now calculate the Nash equilibria of (−Â, −B̂): (û, v̂) = (p, q), ((1, 0), (1, 0)), ((0, 1)(0, 1)). Each equilibrium (û, v̂) can be interpreted as an anti-Nash equilibrium of (Â, B̂), because it gives a pair of strategies where each player uses a worst response to their opponent’s actions. Proposition 3 shows that a (non-convex) linear combination of the Nash equilibrium and the anti-Nash equilibrium, [σ(p, q) − μσ(û, v̂)](1 − μ)^{−1}, is a correlated equilibrium of (A, B) when μ is sufficiently small, and the linear combination can determine an extreme point of C(A, B). In the example μ = 0.25 determines all of the extreme points of C(A, B) not in C_{N}(A, B).

Proposition 3 Suppose that (p, q) ∈ E(A, B) is a quasi-strict, extreme equilibrium. Let (Â, B̂) be the submatrix of (A, B) defined by the support of σ(p, q). If (û, v̂) ∈ E(−Â, −B̂) is an extreme equilibrium in E(−Â, −B̂) satisfying (u, v) ≠ (p, q), then there exists μ̄ > 0 such that

(a) σ^{μ} := (1 − μ)^{−1}(σ(p, q) − μσ(u, v)) ∈ C(A, B) for 0 < μ ≤ μ̄,

(b) Define σ̄ := σ^{μ} when μ = μ̄, then this is an extreme point of C(A, B) if suppσ̄ ≠ suppσ(p, q),

(c) σ̄ ∉ C_{N}(A, B) if suppσ̄ ≠ suppσ(p, q),

(where (u, v) is (û, v̂) with appropriate zeros added and suppσ = {(i, j)|σ_{ij} > 0}).

\underline{Proof:} Let (p, q),(û, v̂),(u, v) satisfying the conditions above be given. Assume: p_{i} > 0 for i = 1, 2, ..., c; u_{i} > 0 for i = c′ +1, c′ +2, ..., c; q_{j} > 0 for j = 1, 2, ..., d; v_{j} > 0 for j = d′ + 1, d′ + 2, ..., d. (a) For μ < 1 define σ^{μ} as above, then

∑_{j} σ_{ij}^{μ}(a_{ij} − a_{kj}) = (1 − μ)^{−1}p_{i} ∑_{j} q_{j}(a_{ij} − a_{kj}) − μ(1 − μ)^{−1}u_{i} ∑_{j} v_{j}(a_{ij} − a_{kj}).

We have the following cases: (i) If p_{i} > 0, p_{k} > 0 then p_{i} ∑_{j} q_{j}(a_{ij} − a_{kj}) = 0 and −u_{i} ∑_{j} v_{j}(a_{ij} − a_{kj}) ≥ 0 by definition of (p, q), (u, v). (ii) If p_{i} > 0, p_{k} = 0 then p_{i} ∑_{j} q_{j}(a_{ij} − a_{kj}) > 0 (as (p, q) is quasi-strict) and −u_{i} ∑_{j} v_{j}(a_{ij} − a_{kj}) is indeterminate. (iii) If p_{i} = p_{k} = 0 then both terms above are zero. Thus ∑_{j} σ_{ij}^{μ}(a_{ij} − a_{kj}) ≥ 0 for all i, k ∈ I and for some 0 < μ, choose μ_{1} to be the maximal value of μ for which this holds (and if no such maximum exists let μ_{1} = 1). An identical argument allows one to find μ_{2} > 0 such that ∑_{i} σ_{ij}^{μ}(b_{ij} − b_{ih}) ≥ 0 for all j, h ∈ J and 0 < μ ≤ μ_{2}. Define μ_{3} so that min_{(i,j)∈supp(σ(p,q))}(p_{i}q_{j} − μ_{3}u_{i}v_{j}) = 0, and let μ̄ := min{μ_{1}, μ_{2}, μ_{3}}. Then σ^{μ} ∈ Δ^{mn} and σ^{μ} ∈ C(A, B) for all 0 < μ ≤ μ̄. .

(b) Let (−Ĝ, Ĝ) denote the zero-sum game derived from (−Â, −B̂). (û, v̂) ∈ E(−Â, −B̂) is an extreme equilibrium so there exists Y, a non-singular submatrix of Ĝ + δU, such that [σ(û, v̂)′]^{T} Y = δ1^{T} (throughout this proof ′ indicates that appropriate zero elements have been deleted). By construction Ĝ is a submatrix of G, thus Y is a non-singular submatrix of G + δU such that [σ(u, v)′]^{T} Y = δ1^{T}. There are cd−(c−c′)(d−d′) rows of G+δU in suppσ(p, q) not in suppσ(u, v). Let σ_{1} be σ(p, q) restricted to these rows of G + δU and let σ_{2} be σ(p, q) restricted to the rows in suppσ(u, v). As (p, q) is an extreme equilibrium the construction used in Proposition 2 applied to the rows in σ_{1} determines X, a non-singular submatrix of G + δU, such that σ_{1}^{T} X = ϵ1^{T}, where ϵ = δ1^{T} σ_{1}. The columns of G + δU that are included in X have δ’s in the rows played by σ(u, v)′. It follows that the matrix R, given in partitioned form below, is a submatrix of G + δU

R = [ \begin{matrix}X & Z \\ δU & Y \end{matrix} ] ,

where Z is an unspecified collection of elements of G + δU. As (p, q) and (û, v̂) are Nash equilibria it follows that (σ̄′)^{T} R = (σ(p, q)′)^{T} R = δ1^{T} .

Assume there exists a non-zero vector λ such that λ^{T} R = 0. Partition the vector so that

λ^{T} R = [λ_{1}^{T} X + λ_{2}^{T} δU, λ_{1}^{T} Z + λ_{2}^{T} Y] = 0

Since X is non-singular we must choose λ_{1} = ησ_{1}, for some η ≠ 0. By construction ησ(p, q)^{′T} R = ηδ1^{T}, so the above implies λ_{1}^{T} Z = ηδ1^{T} −ησ_{2}^{T} Y. Then λ_{1}^{T} Z + λ_{2}^{T} Y = 0 only if (ησ_{2} − λ_{2})^{T} Y = ηδ1^{T}. By the definition of Y this implies λ_{2} = ησ_{2} − ησ(u, v)′. Thus λ must be of the form η[σ_{1}, σ_{2} − σ(u, v)′]. It follows that R has rank = #suppσ(p, q) − 1. If suppσ(p, q) ≠ suppσ̄, it is then possible to delete one row from R and find a non-singular submatrix R^{∗} of R so that (σ̄′)^{T} R^{∗} = δ1.

(c) From (b) σ̄ is an extreme point of C(A, B) so if the claim is false σ̄ is an extreme point of C_{N}(A, B). All extreme points of C_{N}(A, B) can be written in the form σ(p^{∗}, q^{∗}) for some (p^{∗}, q^{∗}) ∈ E(A, B), however, it is only possible for σ̄ = σ(p^{∗}, q^{∗}) if supp(p) = supp(u) and supp(q) = supp(v). In this case (û, v̂) and (p, q) are both Nash equilibria of (−Â, −B̂), as (û, v̂) is an extreme Nash equilibrium there is a non-singular submatrix A′ so that (û)^{T} Â′ = a1 and (p′)^{T} Â′ = a1 this implies û = p; a contradiction. Q.E.D.

References

Aumann, R.J. (1974). “Subjectivity and Correlation in Randomized Strategies,” J. Math. Econ. 1, 67-96.

Aumann, R.J. (1987). “Correlated Equilibrium as an Expression of Bayesian Rationality,” Econometrica 55, 1-18.

Chin, H.H., Parthasarathy, T. and Raghavan, T.E.S. (1974). “Structure of Equilibria in n-Person Cooperative Games,” Int. J. Game Theory 3, 1-19.

Forges, F. (1985). “Correlated Equilibria in a Class of Repeated Games with Incomplete Information,” Int. J. Game Theory 14, 129-150.

Forges, F. (1990). ”Correlated Equilibrium in Two-Person Zero-Sum Games,” Econometrica 58, 515.

Hart, S. and Schmeidler, D. (1989). “Existence of Correlated Equilibria,” Math. Op. Res. 14, 18-25.

Jansen, M.J.M. (1981). “Regularity and Stability of Equilibrium Points of Bimatrix Games,” Math. Op. Res. 6, 530-550.

Kuhn, H.W. (1961). “An Algorithm for Equilibrium Points in Bi-Matrix Games,” Proceedings of the National Academy of Science US. 47, 1657-1662.

Parthasarathy, T. and Raghavan, T.E.S. (1971). Some Topics in Two-Person Games. New York: American Elsevier.

Shapley, L.S. and Snow, R.N. (1950). “Basic Solutions of Discrete Games,” in Contributions to the Theory of Games (H.W. Kuhn and A.W. Tucker, Eds.) vol 1 27-35. Princeton: Princeton University Press.

Van Damme, E.E.C. (1987). Stability and Perfection of Nash Equilibria. Springer-Verlag: Berlin.

Vorobev, N.N. (1958). “Equilibrium Points in Bi-Matrix Games,” in Theory of Probability and its Applications. (English Translation) 3, 297-309.

Footnotes

* My thanks are due to Françoise Forges and to Jean-François Mertens (for their encouragement, helpful suggestions and for spotting an error in an earlier version of this paper), to Jonathan Cave (who commented on this work in its early stages), to Ehud Kalai an associate editor and referee’s (who’s comments greatly improved the exposition) and finally to seminar participants at CORE.

(1) My thanks are due to Jonathan Cave for suggesting this name to me.

(2) Δ^{m} := {x ∈ ℜ^{m}|x ≥ 0, 1^{T} x = 1} where 1^{T} := (1, 1, 1, ..., 1).

(3) co{.} is used to denote the convex hull of a set.