Two-Person Zero-Sum Game

From NEOS

Jump to: navigation, search

(2A) Mixed Strategies

-When the game does not posses a saddle point one must use probabilities over strategies in order to determine the payout

Xi = P(player A will use strategy i) (i = 1, 2,…m)

Yj = P(player B will use strategy j) (j = 1, 2,…n)

-m and n are the total number of available strategies

Expected Payoff for player A = \sum_{i=1}^m \sum_{j=1}^n p_i p_j x_i y_j


-Possible Strategy names:

-Minimax: Minimize the maximum expected loss

-Maximin: Maximize the minimum expected payoff


(2B) Graphical Solution Method

Example: The following is an example of a two player mixed strategy game that is solved using linear programming and the Simplex Method. This example illustrates a situation where on of the players, (Player A) has two pure strategies, namely x1 and x2 , where x2 = 1- x1. Player B wants to minimize the payoff for Player A by choosing the one of the pure strategies to counter. Expected payoffs for Player A are as follows:

Table (2B-1)

Image:Payoff_table_1.JPG‎

Image:Table 2.JPG‎

Figure (2B-A)


-Next we want to graph the equations we found by from our expected payoffs in order to find the optimal solution

Image:G1.JPG‎

(2C) Solving by Linear Programming (LP)

-Any game with mixed strategies can be transformed into a linear programming problem

Expected Payoff for Player A = \sum_{i=1}^m \sum_{j=1}^n p_i p_j x_i y_j, (Equation 2)

and optimal if;

\sum_{i=1}^m \sum_{j=1}^n p_i p_j x_i y_j \geq \underline{\upsilon} = \upsilon, (Equation 3)

-Where υ is x*m+1, or the optimal solution to the linear program.

Example: Graphing becomes difficult to due with multi dimensions, so we can use a method called the Simplex Method to solve a LP. For simplicity purposes we will use the example from section (2B) to illustrate the simplex method. The equations below are numerical representations of (Equation 2) and (Equation 3). The numerical equations below represent the primal and dual problems respectively.

Maximize x3,

2x1, – x2, - x3, ≥ 0

-2x1, + 3x2, - x3, ≥ 0

2x2, - x3, ≥ 0

x1, + x2, = 1

and

x1, ≥ 0, x2, ≥ 0


-Before applying the simplex method to this primal linear program, we must first add the constraint that x3 ≥ 0. By adding this constraint we ensure that our solution yielded will be non-negative -After applying the simplex method, the linear program above yields x1 = ½, x2 = ½, x3 = ½ as its optimal solution mixed solution


(2C-1) Duality

-To obtain the dual of a primal problem, we must follow three main steps:

1.) The coefficients in the objective function, or the function we are trying to maximize or minimize, become the right hand side coefficients of the dual.

2.) The right hand side coefficients of the primal become the coefficients of the objective function in the dual.

3.) The coefficients of a variable in the functional constraints of the primal become the coefficients of the functional constraints in the dual.


Weak duality property: If x is a feasible solution to the primal and y is a feasible solution to the dual, then: 

      cx ≤ yb

-This means that the maximum feasible solution to the primal is the minimum feasible solution to the dual

Strong duality property: If x* is an optimal feasible solution to the primal and y* is an optimal feasible solution to the dual, then: 

      cx* = y*b

Complimentary solutions property: At each iteration in the simplex method, a Critical Point Feasible (CPF) solution x found for the primal problem. There is also a complimentary solution y found for the dual. 

      cx = yb


-This means that if x is not optimal for the primal, then y is not a feasible solution to the dual and vice-versa between the dual and the primal

Duality Theorem:

1.) If a problem has feasible solutions and a bounded objective function (with an optimal solution), then the other problem has the same properties. In this instance both weak duality and strong duality hold.

2.) If a problem has feasible solutions and an unbounded objective function ( with no optimal solution), then the other problem will have no feasible solutions.

3.) If a problem has no feasible solutions, then the other problem has either no feasible solutions or an unbounded objective function.

-These are the only possible relationships between primal and dual problems

Minimize y4,

2y1 – 2y2 - y4 ≤ 0

-1y1 + 3y2 + 2y3 - y4 ≤ 0

-1y1 + 3y2 + 2y3 - y4 ≤ 0

y1 + y2 + y3 = 1

and

y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


-Again before we can solve the dual to the primal linear program with the Simplex Method, we must first add the constraint y4, ≥ 0 to ensure that our solution is non-negative

-After applying the Simplex Method, the linear program yields y1 = 5/8, y2 = 3/8, y3 = 0, y4 = 1/2 as the optimal solution

-In this instance υ − = y*n+1

-According to strong duality, defined in section (2C-1), x*m+1 = y*n+1, which means that the optimal solution for the primal linear program is the optimal solution for the dual of the linear program. By definition this also reinforces the definition of the minimax theorem, which says that \underline{\upsilon} = \upsilon^{-}

Retrieved from "http://wiki.mcs.anl.gov/NEOS/index.php/Two-Person_Zero-Sum_Game"