A is a nXm matrix. Alice has a choice of n so-called pure strategies and Bob has a choice of

m pure strategy. If Alice picks strategy i and Bob picks strategy j, the payoff is Aij, meaning

Aij dollars are transferred from Alice to Bob. Thus, Alice want to pick a strategy to minimize

the payoff while Bob wants a strategy to maximize the payoff. The matrix A is called the payoff

matrix. It’s well known that to play the game well, you need to use a mixed strategy–a random

choice from among pure strategies. A mixed strategy is just a particular probability distribution

over pure strategies. Say Alice’s maxed strategy is vector X and Bob’s is Y, then Alice and Bob

try to solve two problems below to find their best X and Y, respectively.

Min{Max{XAY|Y}|X} s.t. Sigma{X}=Sigma{Y}=1 X>=0 Y>=0 (1)

Max{Min{XAY|X}|Y} s.t. Sigma{X}=Sigma{Y}=1 X>=0 Y>=0 (2)

For (1), whatever X Alice picks, Bob can always pick a Y such that (XA)Y=Max{element of XA}.

So we can convert (1) to a linear programming

Minimize Z s.t. XA<=Z Sigma{X}=1 X>=0 (A)

Likewise, (2) can be converted to

Maximize Z s.t. AY>=Z Sigma{Y}=1 Y>=0 (B)

It’s surprising that (A) and (B) are duality linear programming of each other, so they are equal.

It means Alice and Bob can’t improve their payoff even if he/she know the other’s strategy. It’s

called they are in Nash Equilibrium.

m pure strategy. If Alice picks strategy i and Bob picks strategy j, the payoff is Aij, meaning

Aij dollars are transferred from Alice to Bob. Thus, Alice want to pick a strategy to minimize

the payoff while Bob wants a strategy to maximize the payoff. The matrix A is called the payoff

matrix. It’s well known that to play the game well, you need to use a mixed strategy–a random

choice from among pure strategies. A mixed strategy is just a particular probability distribution

over pure strategies. Say Alice’s maxed strategy is vector X and Bob’s is Y, then Alice and Bob

try to solve two problems below to find their best X and Y, respectively.

Min{Max{XAY|Y}|X} s.t. Sigma{X}=Sigma{Y}=1 X>=0 Y>=0 (1)

Max{Min{XAY|X}|Y} s.t. Sigma{X}=Sigma{Y}=1 X>=0 Y>=0 (2)

For (1), whatever X Alice picks, Bob can always pick a Y such that (XA)Y=Max{element of XA}.

So we can convert (1) to a linear programming

Minimize Z s.t. XA<=Z Sigma{X}=1 X>=0 (A)

Likewise, (2) can be converted to

Maximize Z s.t. AY>=Z Sigma{Y}=1 Y>=0 (B)

It’s surprising that (A) and (B) are duality linear programming of each other, so they are equal.

It means Alice and Bob can’t improve their payoff even if he/she know the other’s strategy. It’s

called they are in Nash Equilibrium.

Advertisements