1. Home
  2. Applied finite mathematics
  3. Applied finite mathematics
  4. Game theory

0.18 Game theory  (Page 4/4)

<< Chapter < Page
  Applied finite mathematics     Page 4 / 4
Chapter >> Page >

For the game in [link] , determine the optimal strategy for both Robert and Carol, and find the value of the game.

Since we have already determined that the game is non-strictly determined, we proceed to determine the optimal strategy for the game. We rewrite the game matrix.

G = 10 − 10 − 25 25 size 12{G= left [ matrix { "10" {} # - "10" {} ##- "25" {} # "25"{} } right ]} {}

Let R = r 1 − r size 12{R= left [ matrix { r {} # 1 - r{}} right ]} {} be Robert's strategy, and C = c 1 − c size 12{C= left [ matrix { c {} ##1 - c } right ]} {} be Carol's strategy.

To find the optimal strategy for Robert, we, first, find the product RG size 12{ ital "RG"} {} as below.

r 1 − r 10 − 10 − 25 25 = 35 r − 25 − 35 r + 25 size 12{ left [ matrix { r {} # 1 - r{}} right ] left [ matrix {"10" {} # - "10" {} ## - "25" {} # "25"{}} right ]= left [ matrix {"35"r - "25" {} # - "35"r+"25"{} } right ]} {}

By setting the entries equal, we get

35 r − 25 = − 35 r + 25 size 12{"35"r - "25"= - "35"r+"25"} {}
or r = 5 / 7 size 12{r=5/7} {} .

Therefore, the optimal strategy for Robert is 5 / 7 2 / 7 size 12{ left [ matrix { 5/7 {} # 2/7{}} right ]} {} .

To find the optimal strategy for Carol, we, first, find the following product.

10 − 10 − 25 25 c 1 − c = 20 c − 10 − 50 c + 25 size 12{ left [ matrix { "10" {} # - "10" {} ##- "25" {} # "25"{} } right ]left [ matrix { c {} ##1 - c } right ]= left [ matrix { "20"c - "10" {} ##- "50"c+"25" } right ]} {}

We now set the entries equal to each other, and we get,

20 c − 10 = − 50 c + 25 size 12{"20"c - "10"= - "50"c+"25"} {}

or c = 1 / 2 size 12{c=1/2} {}

Therefore, the optimal strategy for Carol is 1 / 2 1 / 2 size 12{ left [ matrix { 1/2 {} ##1/2 } right ]} {} .

To find the expected value, V size 12{V} {} , of the game, we find the product RGC size 12{ ital "RGC"} {} .

V = 5 / 7 2 / 7 10 − 10 − 25 25 1 / 2 1 / 2 = 0 size 12{ matrix { V {} # ={} {} # left [ matrix {5/7 {} # 2/7{} } right ]left [ matrix { "10" {} # - "10" {} ##- "25" {} # "25"{} } right ]left [ matrix { 1/2 {} ##1/2 } right ]{} ## {} # ={} {} # left [0 right ]{} } } {}

If both players play their optimal strategy, the value of the game is zero. In such case, the game is called fair .

Got questions? Get instant answers now!
Got questions? Get instant answers now!

Reduction by dominance

Sometimes an m × n size 12{m times n} {} game matrix can be reduced to a 2 × 2 size 12{2 times 2} {} matrix by deleting certain rows and columns. A row can be deleted if there exists another row that will produce a payoff of an equal or better value. Similarly, a column can be deleted if there is another column that will produce a payoff of an equal or better value for the column player. The row or column that produces a better payoff for its corresponding player is said to dominate the row or column with the lesser payoff.

For the following game, determine the optimal strategy for both the row player and the column player, and find the value of the game.

G = − 2 6 4 − 1 − 2 − 3 1 2 − 2 size 12{G= left [ matrix { - 2 {} # 6 {} # 4 {} ##- 1 {} # - 2 {} # - 3 {} ## 1 {} # 2 {} # - 2{}} right ]} {}

We first look for a saddle point and determine that none exist. Next, we try to reduce the matrix to a 2 × 2 size 12{2 times 2} {} matrix by eliminating the dominated row.

Since every entry in row 3 is larger than the corresponding entry in row 2, row 3 dominates row 2. Therefore, a rational row player will never play row 2, and we eliminate row 2. We get

− 2 6 4 1 2 − 2 size 12{ left [ matrix { - 2 {} # 6 {} # 4 {} ##1 {} # 2 {} # - 2{} } right ]} {}

Now we try to eliminate a column. Remember that the game matrix represents the payoffs for the row player and not the column player; therefore, the larger the number in the column, the smaller the payoff for the column player.

The column player will never play column 2, because it is dominated by both column 1 and column 3. Therefore, we eliminate column 2 and get the modified matrix, M size 12{M} {} , below.

M = − 2 4 1 − 2 size 12{M= left [ matrix { - 2 {} # 4 {} ##1 {} # - 2{} } right ]} {}

To find the optimal strategy for both the row player and the column player, we use the method learned in the [link] .

Let the row player's strategy be R = r 1 − r size 12{R= left [ matrix { r {} # 1 - r{}} right ]} {} , and the column player's be strategy be C = c 1 − c size 12{C= left [ matrix { c {} ##1 - c } right ]} {} .

To find the optimal strategy for the row player, we, first, find the product RM size 12{ ital "RM"} {} as below.

r 1 − r − 2 4 1 − 2 = − 3r + 1 6r − 2 size 12{ left [ matrix { r {} # 1 - r{}} right ] left [ matrix {- 2 {} # 4 {} ## 1 {} # - 2{}} right ]= left [ matrix {- 3r+1 {} # 6r - 2{} } right ]} {}

By setting the entries equal, we get

− 3r + 1 = 6r − 2 size 12{ - 3r+1=6r - 2} {}

or r = 1 / 3 size 12{r=1/3} {} .

Therefore, the optimal strategy for the row player is 1 / 3 2 / 3 size 12{ left [ matrix { 1/3 {} # 2/3{}} right ]} {} , but relative to the original game matrix it is 1 / 3 0 2 / 3 size 12{ left [ matrix { 1/3 {} # 0 {} # 2/3{}} right ]} {} .

To find the optimal strategy for the column player we, first, find the following product.

− 2 4 1 − 2 c 1 − c = − 6c + 4 3c − 2 size 12{ left [ matrix { - 2 {} # 4 {} ##1 {} # - 2{} } right ]left [ matrix { c {} ##1 - c } right ]= left [ matrix { - 6c+4 {} ##3c - 2 } right ]} {}

We set the entries in the product matrix equal to each other, and we get,

− 6c + 4 = 3c − 2 size 12{ - 6c+4=3c - 2} {}

or c = 2 / 3 size 12{c=2/3} {}

Therefore, the optimal strategy for the column player is 2 / 3 1 / 3 size 12{ left [ matrix { 2/3 {} ##1/3 } right ]} {} , but relative to the original game matrix, the strategy for the column player is 2 / 3 0 1 / 3 size 12{ left [ matrix { 2/3 {} ##0 {} ## 1/3} right ]} {} .

To find the expected value, V size 12{V} {} , of the game, we have two choices: either to find the product of matrices R size 12{R} {} , M size 12{M} {} and C size 12{C} {} , or multiply the optimal strategies relative to the original matrix to the original matrix. We choose the first, and get

V = 1 / 3 2 / 3 − 2 4 1 − 2 2 / 3 1 / 3 = 0 size 12{ matrix { V {} # ={} {} # left [ matrix {1/3 {} # 2/3{} } right ]left [ matrix { - 2 {} # 4 {} ##1 {} # - 2{} } right ]left [ matrix { 2/3 {} ##1/3 } right ]{} ## {} # ={} {} # left [0 right ]{} } } {}

Therefore, if both players play their optimal strategy, the value of the game is zero.

Got questions? Get instant answers now!

We summarize as follows:

Reduction by dominance

  1. Sometimes an m × n size 12{m times n} {} game matrix can be reduced to a 2 × 2 size 12{2 times 2} {} matrix by deleting dominated rows and columns.
  2. A row is called a dominated row if there exists another row that will produce a payoff of an equal or better value. That happens when there exists a row whose every entry is larger than the corresponding entry of the dominated row.
  3. A column is called a dominated column if there exists another column that will produce a payoff of an equal or better value. This happens when there exists a column whose every entry is smaller than the corresponding entry of the dominated row.
<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Applied finite mathematics. OpenStax CNX. Jul 16, 2011 Download for free at http://cnx.org/content/col10613/1.5
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Applied finite mathematics' conversation and receive update notifications?

Ask