Archive for January, 2008

0-Sum 2-Player Game

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

Max{Min{XAY|X}|Y}   s.t. Sigma{X}=Sigma{Y}=1  X>=0 Y>=0 
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
Likewise,  (2) can be converted to 

Maximize Z s.t. AY>=Z Sigma{Y}=1 Y>=0
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.

Read Full Post »