Skip to main content
Chemistry LibreTexts

Untitled Page 23

  • Page ID
    125025
  • Chapter 19Game Theory

    Chapter Overview

    In this chapter, you will learn to:

    1. Solve strictly determined games.

    2. Solve games involving mixed strategies.

    Strictly Determined Games

    Game theory is one of the newest branches of mathematics. It first came to light when a brilliant mathematician named Dr. John von Neumann co-authored with Dr. Morgenstern a book titled Theory of Games and Economic Behavior. Since then it has played an important role in decision making in business, economics, social sciences and other fields.

    In this chapter, we will study games that involve only two players. In these games, since a win for one person is a loss for the other, we refer to them as two-person zero-sum games. Although the games we will study here are fairly simple, they will provide us with an understanding of how games work and how they are applied in practical situations. We begin with an example.

    Example 19.1

    Robert and Carol decide to play a game using a dime and a quarter. Each chooses one of the two coins, puts it in their hand and closes their fist. At a given signal, they simultaneously open their fists. If the sum of the coins is less than thirty five cents, Robert gets both coins, otherwise, Carol gets both coins. Write the matrix for the game, determine the optimal strategies for each player, and find the expected payoff for Robert.

    Suppose Robert is the row player, that is, he plays the rows, and Carol is a column player. If Robert shows a dime and Carol shows a dime, the sum will be less than thirty five cents and Robert will win ten cents. But, if Robert shows a dime and Carol shows a quarter, the sum will not be less than thirty five cents and Carol will win ten cents or Robert will lose ten cents. The following matrix depicts all four cases and their corresponding payoffs for Robert. Remember a negative value is a loss for Robert and a win for Carol.

    graphics1.png
    Figure 19.0

    The best strategy for Robert is to always show a dime because this way the worst he can do is lose ten cents. And, the best strategy for Carol is to always show a quarter because that way the worst she can do is to lose ten cents. If both Robert and Carol play their optimal strategies, Robert will lose ten cents each time. Therefore, the value of the game is negative ten cents.

    In Example 19.1, since there is only one fixed optimal strategy for each player, regardless of their opponent's strategy, we say the game possesses a pure strategy and is strictly determined.

    Next, we formulate a method to find the optimal strategy for each player and the value of the game. The method involves considering the worst scenario for each player.

    To consider the worst situation, the row player considers the minimum value in each row, and the column player considers the maximum value in each column. Note that the maximum value really represents a minimum value for the column player because the game matrix depicts the payoffs for the row player. We list the method below.

    Finding the Optimal Strategy and the Value for Strictly Determined Games
    1. Put an asterisk(*) next to the minimum entry in each row.

    2. Put a box around the maximum entry in each column.

    3. The entry that has both an asterisk and a box represents the value of the game and is called a saddle point.

    4. The row that is associated with the saddle point represents the best strategy for the row player, and the column that is associated with the saddle point represents the best strategy for the column player.

    5. A game matrix can have more than one saddle point, but all saddle points have the same value.

    6. If no saddle point exists, the game is not strictly determined. Non-strictly determined games are the subject of the section called “Non-Strictly Determined Games”.

    Example 19.2

    Find the saddle points and optimal strategies for the following game.

    graphics2.png
    Figure 19.0

    We find the saddle point by placing an asterisk next to the minimum entry in each row, and by putting a box around the maximum entry in each column as shown below.

    graphics3.png
    Figure 19.0

    Since the second row, first column entry, which happens to be 10, has both an asterisk and a box, it is a saddle point. This implies that the value of the game is 10, and the optimal strategy for the row player is to always play row 2, and the optimal strategy for the column player is to always play column 1. If both players play their optimal strategies, the row player will win 10 units each time.

    The row player's strategy is written as _autogen-svg2png-0001.png indicating that he will play row 1 with a probability of 0 and row 2 with a probability of 1. Similarly the column player's strategy is written as _autogen-svg2png-0002.png implying that he will play column 1 with a probability of 1, and column 2 with a probability of 0.

    Non-Strictly Determined Games

    In this section, we study games that have no saddle points. Which means that these games do not possess a pure strategy. We call these games non-strictly determined games. If the game is played only once, it will make no difference what move is made. However, if the game is played repeatedly, a mixed strategy consisting of alternating random moves can be worked out.

    We consider the following example.

    Example 19.3

    Suppose Robert and Carol decide to play a game using a dime and a quarter. At a given signal, they simultaneously show one of the two coins. If the coins match, Robert gets both coins, but if they don't match, Carol gets both coins. Determine whether the game is strictly determined.

    We write the payoff matrix for Robert as follows:

    graphics4.png
    Figure 19.0

    To determine whether the game is strictly determined, we look for a saddle point. Again, we place an asterisk next to the minimum value in each row, and a box around the maximum value in each column. We get

    graphics5.png
    Figure 19.0

    Since there is no entry that has both an asterisk and a box, the game does not have a saddle point, and thus it is non-strictly determined.

    We wish to devise a strategy for Robert. If Robert consistently shows a dime, for example, Carol will see the pattern and will start showing a quarter, and Robert will lose. Conversely, if Carol repeatedly shows a quarter, Robert will start showing a quarter, thus resulting in Carol's loss. So a good strategy is to throw your opponent off by showing a dime some of the times and showing a quarter other times. Before we develop an optimal strategy for each player, we will consider an arbitrary strategy for each and determine the corresponding payoffs.

    Example 19.4

    Suppose in Example 19.3, Robert decides to show a dime with .20 probability and a quarter with .80 probability, and Carol decides to show a dime with .70 probability and a quarter with .30 probability. What is the expected payoff for Robert?

    Let R denote Robert's strategy and C denote Carol's strategy.

    Since Robert is a row player and Carol is a column player, their strategies are written as follows:

    _autogen-svg2png-0009.png and _autogen-svg2png-0010.png.

    To find the expected payoff, we use the following reasoning.

    Since Robert chooses to play row 1 with .20 probability and Carol chooses to play column 1 with .70 probability, the move row 1, column 1 will be chosen with (.20)(.70)=.14 probability. The fact that this move has a payoff of 10 cents for Robert, Robert's expected payoff for this move is (.14)(.10)=.014 cents. Similarly, we compute Robert's expected payoffs for the other cases. The table below lists expected payoffs for all four cases.

    Table 19.1.
    MoveProbabilityPayoffExpected Payoff
    Row 1, Column 1 ( . 20 ) ( . 70 ) = . 14 10 cents1.4 cents
    Row 1, Column 2 ( . 20 ) ( . 30 ) = . 06 -10 cents-.6 cents
    Row 2, Column 1 ( . 80 ) ( . 70 ) = . 56 -25 cents-14 cents
    Row 2, Column 2 ( . 80 ) ( . 30 ) = . 24 25 cents6.0 cents
    Totals1 -7.2 cents

    The above table shows that if Robert plays the game with the strategy _autogen-svg2png-0019.png and Carol plays with the strategy _autogen-svg2png-0020.png, Robert can expect to lose 7.2 cents for every game.

    Alternatively, if we call the game matrix G, then the expected payoff for the row player can be determined by multiplying matrices R, G and C. Thus, the expected payoff P for Robert is as follows:

    (19.1)
    _autogen-svg2png-0026.png

    Which is the same as the one obtained from the table.

    Example 19.5

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

    (19.2)
    _autogen-svg2png-0028.png

    Let us suppose that the row player uses the strategy _autogen-svg2png-0029.png. Now if the column player plays column 1, the expected payoff P for the row player is

    P(r)=1(r)+(−3)(1−r)=4r−3.

    Which can also be computed as follows:

    _autogen-svg2png-0032.png or 4r−3.

    If the row player plays the strategy _autogen-svg2png-0034.png and the column player plays column 2, the expected payoff P for the row player is

    _autogen-svg2png-0036.png.

    We have two equations

    P(r)=4r−3 and P(r)=−6r+4

    The row player is trying to improve upon his worst scenario, and that only happens when the two lines intersect. Any point other than the point of intersection will not result in optimal strategy as one of the expectations will fall short.

    Solving for r algebraically, we get

    (19.3)4r−3=−6r+4

    r=7/10.

    Therefore, the optimal strategy for the row player is _autogen-svg2png-0042.png .

    Alternatively, we can find the optimal strategy for the row player by, first, multiplying the row matrix with the game matrix as shown below.

    (19.4)
    _autogen-svg2png-0043.png

    And then by equating the two entries in the product matrix. Again, we get r=.7, which gives us the optimal strategy _autogen-svg2png-0045.png .

    We use the same technique to find the optimal strategy for the column player.

    Suppose the column player's optimal strategy is represented by _autogen-svg2png-0046.png. We, first, multiply the game matrix by the column matrix as shown below.

    (19.5)
    _autogen-svg2png-0047.png

    And then equate the entries in the product matrix. We get

    (19.6)3c−2=−7c+4
    (19.7)c=.6

    Therefore, the column player's optimal strategy is _autogen-svg2png-0050.png .

    To find the expected value, V, of the game, we find the product of the matrices R, G and C.

    (19.8)
    _autogen-svg2png-0055.png

    That is, if both players play their optimal strategies, the row player can expect to lose .2 units for every game.

    Example 19.6

    For the game in Example 19.3, 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.

    (19.9)
    _autogen-svg2png-0057.png

    Let _autogen-svg2png-0058.png be Robert's strategy, and _autogen-svg2png-0059.png be Carol's strategy.

    To find the optimal strategy for Robert, we, first, find the product _autogen-svg2png-0060.png as below.

    (19.10)
    _autogen-svg2png-0061.png

    By setting the entries equal, we get

    35r−25=−35r+25
    or r=5/7.

    Therefore, the optimal strategy for Robert is _autogen-svg2png-0064.png .

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

    (19.11)
    _autogen-svg2png-0065.png

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

    (19.12)20c−10=−50c+25

    or c=1/2

    Therefore, the optimal strategy for Carol is _autogen-svg2png-0068.png .

    To find the expected value, V, of the game, we find the product _autogen-svg2png-0070.png.

    (19.13)
    _autogen-svg2png-0071.png

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

    Reduction by Dominance

    Sometimes an m×n game matrix can be reduced to a 2×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.

    Example 19.7

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

    (19.14)
    _autogen-svg2png-0074.png

    We first look for a saddle point and determine that none exist. Next, we try to reduce the matrix to a 2×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

    (19.15)
    _autogen-svg2png-0076.png

    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, below.

    (19.16)
    _autogen-svg2png-0078.png

    To find the optimal strategy for both the row player and the column player, we use the method learned in the the section called “Strictly Determined Games”.

    Let the row player's strategy be _autogen-svg2png-0079.png, and the column player's be strategy be _autogen-svg2png-0080.png .

    To find the optimal strategy for the row player, we, first, find the product _autogen-svg2png-0081.png as below.

    (19.17)
    _autogen-svg2png-0082.png

    By setting the entries equal, we get

    (19.18)−3r+1=6r−2

    or r=1/3.

    Therefore, the optimal strategy for the row player is _autogen-svg2png-0085.png , but relative to the original game matrix it is _autogen-svg2png-0086.png .

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

    (19.19)
    _autogen-svg2png-0087.png

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

    (19.20)−6c+4=3c−2

    or c=2/3

    Therefore, the optimal strategy for the column player is _autogen-svg2png-0090.png , but relative to the original game matrix, the strategy for the column player is _autogen-svg2png-0091.png .

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

    (19.21)
    _autogen-svg2png-0096.png

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

    We summarize as follows:

    Reduction by Dominance
    1. Sometimes an m×n game matrix can be reduced to a 2×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.

    Solutions