Example: bachelor of science

# 9.1 Strictly Determined Games - Governors State …

Strictly Determined Games Game theory is a relatively new branch of mathematics designed to help people who are in conflict situations determine the best course of action out of several possible choices. It has applications in the business world, warfare and political science. The pioneers of game theory are John Von Neumann and Oskar Morgenstern. Von Neumann { Von Neumann's awareness of results obtained by other mathematicians and the inherent possibilities which they offer is astonishing. Early in his work, a paper by Borel on the minimax property led him to develop .. ideas which culminated later in one of his most original creations, the theory of Games .}

9.1 Strictly Determined Games Game theory is a relatively new branch of mathematics designed to help people who are in conflict situations determine the best course

### Information

Domain:

Source:

Please notify us if you found a problem with this document:

### Transcription of 9.1 Strictly Determined Games - Governors State …

1 Strictly Determined Games Game theory is a relatively new branch of mathematics designed to help people who are in conflict situations determine the best course of action out of several possible choices. It has applications in the business world, warfare and political science. The pioneers of game theory are John Von Neumann and Oskar Morgenstern. Von Neumann { Von Neumann's awareness of results obtained by other mathematicians and the inherent possibilities which they offer is astonishing. Early in his work, a paper by Borel on the minimax property led him to develop .. ideas which culminated later in one of his most original creations, the theory of Games .}

2 { In game theory von Neumann proved the minimax theorem. He gradually expanded his work in game theory, and with co-author Oskar Morgenstern, he wrote the classic text Theory of Games and Economic Behaviour (1944). Fundamental principle of Game Theory { 1. A matrix game is played repeatedly. { 2. Player R tries to maximize winnings. { 3. Player C tries to minimize losses. Two-person zero-sum matrix { 1. R chooses (plays) any one of m rows. { 2. C chooses (plays) any one of m columns. An example { Suppose you have \$10,000 to invest for a period of 5. years. After some investigation and advice from a financial counselor, you arrive at the following game matrix where you ( R ) are playing against the economy ( C).}}}}}}}

3 Each entry in the matrix is the expected payoff after 5 years for an investment of \$10,000 in the corresponding row designation with the future State of the economy in the corresponding column section. The economy is regarded as a rational player who can make decisions against the investor in any case, the investor would like to do the best possible irrespective of what happens to the economy. Find saddle values and optimal strategies for each player. Finding the saddle point(s) if they exist 1. R strategy: circle the lowest number in each row (worst case scenario). C's strategy: Put a square around the greatest value of each column. There are two saddle values located in the first row.

4 So R should choose the first row. C (the economy) can either fall or have no change. In either case the gain of R is the corresponding loss to the economy. The value of the game is 5870 and since this value is not equal to zero, the game is considered to be not fair.. Mixed Strategy Games In this section, we look at non- Strictly Determined Games . For these type of Games the payoff matrix has no saddle points. Non- Strictly Determined matrix Games { A strategy consisting of possible moves and a probability distribution (collection of weights) which corresponds to how frequently each move is to be played. A player would only use a mixed strategy when she is indifferent between several pure strategies, and when keeping the opponent guessing is desirable - that is, when the opponent can benefit from knowing the next move.}

5 Penny matching game { Two players R and C each have a penny , and they simultaneously choose to show the side of the coin of their choice. (H = heads, T = tails) If the pennies match, R wins ( C. loses) 1cent. If the pennies do not match, R loses (C wins) 1. cent. In terms of a game matrix , we have { Determination of Strategy Because there is no saddle point for the penny-matching game, there is no pure strategy for R. We will assign probabilities corresponding to the likelihood that R will choose row 1 or row 2. Similarly, probabilities will be found for C's likelihood of choosing column one or column 2. The strategy will be to choose the row with a probability that will yield the largest expected value.}}

6 Expected Value of a Matrix Game For R. { For the matrix game a b . M = . c d . { and strategies q1 . P = [ p1 p2 ] Q= . 2 . q { for R and C, respectively, the expected value of the game for R is given by E ( P , Q ) = PMQ. Fundamental Theorem of Game Theory (The number v is the value of the game. If v = 0, the game is said to be fair. ). For every m x n matrix game , M , there exists strategies P * and Q* for R and C , respectively, and a unique number v such that P MQ v *. for every strategy Q of C and PMQ v *. for every strategy P of R. Solution to a 2 x 2 Non- Strictly Determined Matrix Game { For the non- Strictly Determined game a b.}}}}

7 M = . c d . { the optimal strategies P * and * and the value of the game are given by Q. d b . * = d c a b D . { *. *. P = p1 p2 D D . q1* . Q = * = a c . *. {. q2 D . ad bc v=. D. { where D = (a + d ) (b + c ). Original problem : { 1. Identify a,b,c,d : a = 1, b = -1, c= -1, d = 1. { 2. Find D: (a+d)-(b+c)=4 (not zero). { 3. The value of the game is v = ad bc v=. { v = 0 so it is a fair game D. d c a b . { 4. Find P * = p1* p2* = = [ , ]. D D . d b . { 5. Find q1* = D = . Q = * . *.. q2 . a c . D . { 6. Find the expected value of game: E(P,Q)=PMQ=0. Linear programming and 2 x 2 Games : A geometric approach This section will introduce the method of solving a non- Strictly Determined matrix game without recessive rows or columns.}}}}}}}}}}}

8 All such Games can be converted into linear programming problems. The method applies to a matrix game M that has all positive payoffs. The method of this section will be illustrated by an example. { For the payoff matrix M 2 4 . 1 3 = M.. { find the optimal strategies for the two players. Continued . { Add 5 to each entry of M { Minimize y subject to to make all values the given constraints: positive: 7 1 1. 4 8 = new M y = = x1 + x2. v ax1 + cx2 1. bx1 + dx2 1. x1 , x2 0. Continued . { Substitute the values { . for a, b, c, d into the inequalities . y = x1 + x2. 7 x1 + 4 x2 1. 1 x1 + 8 x2 1. x1 , x2 0. Solve the linear programming problem { Solution is (2/26, 3/26).}}}}}}}

9 Value of the game, v and probability values { The value of the game is given by the equation { -This is the probability 1 26 matrix for R: v= =. x1 + x2 5. 2 3 . p = [ vx1. *. vx2 ] = . { The value of the original 5 5 . matrix with negative values is 26/5 5 = 1/5. Solve the second linear programming problem to find the probability matrix for the second player { - { - y = z1 + z2. 7 z1 + 1z2 1. 4 z1 + 8 z2 1. z1 , z2 0. Value of the game and probability matrix for second player { - { - 52 7 52 3 . v=. 1. =. 52 q = [ vz1. *. vz2 ] = . z1 + z2 10 10 52 10 52 . 7 3 . = . 10 10 . Linear programming and m x n Games : Simplex Method and the Dual Problem In this section, the process of solving 2 x 2 matrix Games will be generalized to solving m x n matrix Games .}}}}}}}

10 The procedure will be essentially the same as the process for the 2 x 2 case, but the solution of the linear programming problem will incorporate the simplex method and the dual. Procedure: { Given the non- Strictly Determined matrix game M, free of recessive rows and columns, r1 r2 r3 . M = . q1 s1 s2 s3 . { to find P = [ p1 p2 ] Q* = q2 . *. and v . { proceed as follows: q3 . { 1. If M is not a positive matrix, add a suitable positive constant k to each element of M to get a new matrix M1. a1 a2 a3 . M1 = . 1 2 3 . b b b { If v1 is the value of game M1 , then the value of the original game M is given by v = v1 k Procedure continued: { 2.}}}}}}