Stanford MS&E 316 - Solving Bimatrix Games (49 pages)

Previewing pages 1, 2, 3, 23, 24, 25, 26, 47, 48, 49 of 49 page document View the full content.
View Full Document

Solving Bimatrix Games



Previewing pages 1, 2, 3, 23, 24, 25, 26, 47, 48, 49 of actual document.

View the full content.
View Full Document
View Full Document

Solving Bimatrix Games

37 views


Pages:
49
School:
Stanford University
Course:
Ms&E 316 - Discrete Mathematics and Algorithms
Discrete Mathematics and Algorithms Documents

Unformatted text preview:

Solving Bimatrix Games The LCP for a bimatrix game u em Ay 0 x 0 xTu 0 v en B Tx 0 y 0 y Tv 0 The corresponding LCP q M has data em 0 A q and M en BT 0 where we assume that A and B are positive m n matrices Notice that the matrix M is copositive but not copositive plus It is also obviously not sufficient The Lemke Howson Algorithm Algorithm Lemke Howson Step 0 Initialization Input the LCP q M of order m n as above Select an index k 1 m Let s arg min1 j n bkj Pivot hvs xk i This yields an almost complementary but infeasible solution Let r arg min1 i m ais Pivot hur ysi The solution is now almost complementary and feasible The basic pair is xk uk and the nonbasic pair is ur xr If r k stop A solution has been found Otherwise let xr be the driving variable Step 1 Determine the blocking variable if any Use the minimum ratio test to determine whether there is a basic variable that blocks the increase of the driving variable If not stop Step 2 Pivoting The driving variable is blocked Pivot h blocking variable driving variable i If the blocking variable belongs to the basic pair a solution to q M is at hand Otherwise return to Step 1 using the complement of the most recent blocking variable as the new driving variable There s Good News and Bad News First the good news The Lemke Howson Algorithm finds a solution of every nondegenerate instance of the LCP corresponding to a bimatrix game Theorem Hence the Lemke Howson algorithm can find a Nash Equilibrium Point for a finite two person nonzero sum game The proof is rather similar in spirit to that for the Lemke Algorithm for the LCP But note that in the bimatrix game case no covering vector is needed This is because of the positivity of the modified payoff matrices and the block structure of the problem The Bad News The LCP with tableau 1 z1 z2 z3 z4 w1 1 0 0 10 20 w2 1 0 0 30 15 w3 1 10 20 0 0 w4 1 30 15 0 0 corresponds to a bimatrix game A B z1 x1 z2 x2 z3 y1 z4 y2 w1 u1 w2 u2 w3 v1 w4 v2 From the four choices of initial



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Solving Bimatrix Games and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Solving Bimatrix Games and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?