# 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 Full Document

## Solving Bimatrix Games

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

View Full Document
View Full Document

## Solving Bimatrix Games

58 views

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

• 33 pages

• 16 pages

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 pivot column we obtain two and 1 0 and z only two distinct solutions of this LCP z 101 0 10 1 1 2 1 2 0 151 But there is an elusive solution z 90 45 90 45 0 15 More Bad News The Famous Prisoner s Dilemma Problem This problem originated with Melvin Dresher and Merrill Flood at the RAND Corportation The Prisoner s Dilemma is a particular type of bimatrix game problem that has been used to illustrate the shortcomings of the Nash equilibrium concept The name for the problem and the accompanying story are due to A W Tucker In 1950 he used this in a talk before an audience of psychologists here at Stanford Story goes something like this Two criminals are caught and held in separate cells unable to communicate with each other They are each offered the same deal and each knows that the other is offered this deal They can each confess and be a witness against the other person or they can each deny their guilt If they both confess they will each get 5 years in jail If one confesses and the other denies guilt then the one who confessed will get 1 year in jail and the other will get 6 years in jail If they both deny guilt they will each get 2 years in jail What should they do Here we have a case where 5 1 BT A 6 2 Confess Deny Confess 5 1 Deny 6 2 BT A 5 1 6 2 Confess Deny Confess 5 1 Deny 6 2 It can be shown that there is one and only one Nash Equilibrium point for this game Both criminals confess BT A 5 1 6 2 Confess Deny Confess 5 1 Deny 6 2 It can be shown that there is one and only one Nash Equilibrium point for this game Both criminals confess Unless of course they are both game theorists who trust each other Notice that for each criminal the strategy Deny is dominated by the strategy Confess If both criminals use the other strategy Deny each will get a lower sentence Keller s Symmetric Quadratic Programming Algorithm We shall discuss the quadratic programming problem QP minimize f x cTx 12 xTQx subject to Ax b x 0 Assume A Rm n and Q QT Rn n otherwise general The KKT conditions give the LCP u c Qx ATy 0 v b Ax 0 x 0 y 0 uTx 0 v Ty 0 Observations 1 The above system is an instance of an LCP finding a solution of it is the aim of the algorithm to be discussed here 2 If x is a local minimum of QP there exist a y such that x y satisfies the conditions of LCP In the case where Q PSD is the conditions of LCP are also sufficient for x to be a global minimum for QP 3 The first two equations define the variables u and v 4 There is a pairing between uj and xj j 1 n and a pairing between vi and yi i 1 m They are called complementary pairs and each is said to be the complement of the other 5 The first two equations of LCP imply that 2f x cTx bTy uTx v Ty Tabular form Letting 2f x uTx v Ty we can represent the problem at hand in a tabular tableau form as follows 1 x y 0 cT bT u c Q AT v b A 0 Notice how the basic variables u and v are written on the left hand side and the constants and nonbasic variables are written on the righthand side This makes it easy to understand the effect that the variation of a nonbasic variable has on the basic variables Terminal sign configurations In a tableau such as the one above the column headed by 1 is called the constant column It would be the right hand side if all the nonbasic variables were written on the left Now if the constant column c b is nonnegative then x y 0 0 solves LCP and we can terminate the process Pre processing We can carry out a Phase I procedure on the constraints of QP so as to transform b into a nonnegative vector and then modify the rest of the data accordingly Hereafter we assume that the linear inequalities Ax b x 0 have been pre processed so that b 0 If this cannot be done then QP is infeasible Accordingly we consider the case where cj 0 for some index j Now if qjj 0 and aij 0 for all i i m then by letting xj we …

View Full Document

Unlocking...