Skip to main content. Example: Odds and Evens Consider the simple game called odds and evens. A two-person game is characterized by the strategies of each player and the payoff matrix. The payoff matrix shows the gain positive or negative for player 1 that would result from each combination of strategies for the two players.
Note that the matrix for player 2 is the negative of the matrix for player 1 in a zero-sum game. The entries in the payoff matrix can be in any units as long as they represent the utility or value to the player.
There are two key assumptions about the behavior of the players. The first is that both players are rational. Additionally, zero sum games and prudent strategies will be discussed. Mixed-Strategies In this section, we introduce the notion of mixed-strategies. One important motivator for mixed-strategies is that not every game has a pure strategies Nash equilibrium. Consider the matching pennies game:. In any pure strategy profile, one player incurs utility and the other player incurs utility.
The player incurring utility can unilaterally deviate by switching its choice to improve its utility. This inverts the payoffs- the first player incurs utility while the second player incurs utility. Iterating on the above argument, we see that no Nash equilibrium exists in pure strategies. Mixed Strategies: Let be a normal form game. A mixed strategy is a sequence and a probability distribution where player selects strategy with probability. Note that. The set of mixed strategies for player is denoted , where is the simplex in.
That is,. Note that pure strategies are a special case of mixed strategies. The mixed extension will now be defined, to formalize the notion of games with mixed strategies. A mixed strategies Nash equilibrium in a normal form game is equivalent to a pure strategies Nash equilibrium in a mixed extension.
Mixed Extension: Let be a normal form game. The mixed extension of is the three-tuple , where. The notion of mixed strategies is rather unintuitive from a behavioral perspective, as a normal form game is played simultaneously. So how is a mixed strategies Nash equilibrium formulated? Recall that each player is a rational, utility maximizing agent that is aware of the structure of the game.
Each player still seeks to mix its strategies in such a way to maximize its utility. In mixing strategies, a player runs the risk that another player can take advantage of a given mixing. Thus, in a Nash equilibrium, each player mixes strategies such that is indifferent to whichever pure strategy ends up being played. This is formalized as follows.
Theorem 2. A mixed strategy profile is a mixed strategy Nash equilibrium if and only if, for each player , the following two conditions are satisfied:. Proof: Suppose first that the mixed-strategy profile satisfies conditions 1 and 2. Let be the set of strategies given positive probability by. By condition 1 , each pure strategy in results in the same expected utility.
Thus, any mixing of strategies in results in expected utility:. Thus, player cannot unilaterally deviate and improve its outcome, so is a mixed strategies Nash equilibrium. Conversely, suppose is a mixed-strategies Nash equilibrium. As no player can unilaterally deviate and improve its outcome, condition 2 follows immediately.
Suppose to the contrary that condition 1 does not hold. Let and such that the. If , then player could assign more weight to in and improve its outcome.
Similarly, if , then player could assign less weight to in and improve its outcome. Either occurrence contradicts the assumption that is a mixed-strategies Nash equilibrium. Player mixes strategies such that Player is indifferent to and.
Suppose Player plays with probability and with probability. In equilibrium, Player is indifferent between playing and. By symmetry, we have Player mixing between and with frequencies as well.
In addition to guaranteeing the existence of a Nash equilibrium, mixed strategies are also useful in selecting realistic Nash equilibria. Consider the following example.
Example 2: Consider a traffic routing game on the following network. The weight of each edge denotes the latency cost of traversing that edge. The variable denotes the number of players traversing the edge , and the variable denotes the number of players using the edge.
So for example, if , then the latency cost of is for every each of the players. Each player starts at and ends at , seeking to minimize latency. Suppose there are players in the game. Denote as the number of players choosing the path , as the number of players choosing the path , and as the number of players choosing. Consider first the pure strategies Nash equilibrium of.
Both the edges and have players traversing them, and so have latency costs. Players of each type incur latency cost. If a player of type unilaterally deviates, he increases the latency cost of the edge to , resulting in a total latency cost of. By similar argument, players of type and cannot unilaterally deviate and decrease their costs as well. While and is a pure strategies Nash equilibrium, it is unlikely the players will end up playing this strategy profile.
However, this pure strategies equilibrium does provide the probabilities for a mixed strategies equilibrium. As the game is symmetric, there exists a Nash equilibrium in which each player selects the same strategy. Suppose each player selects the mixed strategy with probabilities. We apply Theorem 2. First, observe that. Consider each of the pure strategies. Thus, is a mixed-strategies Nash equilibrium.
Zero-Sum Games In this section, we examine zero-sum games. For example, cutting a larger slice of cake for one person leaves less cake for the others.
This notion is formalized as follows:. Zero-Sum Games: Let be a normal form game. Recall the Matching Pennies game from the previous section. In any strategy profile, one player earns utility while the other player earns utility. Thus, the Matching Pennies game is a zero-sum game. Another example of a zero-sum game is Rock-Paper-Scissors. The winner of the game earns utility while the loser earns utility. In the event of a tie, each player earns utility.
So how are zero-sum games solved? We can solve zero-sum games in the same manner as any other normal form game. Of particular interest, however, are prudent strategies. Intuitively, players who play prudently seek to minimize potential losses. We define prudent strategies as follows:. Prudent Strategies: Let be a finite, normal form game.
A prudent strategy of player is a mixed strategy that satisfies. Note that the definition of prudent strategies did not restrict to zero-sum games. We discuss them in the context of zero-sum games; however, as they are most useful here.
In the case of a two-player game, saddle points are equivalent to prudent strategies. We define a saddle point as follows. Saddle Point: Let be a two-player zero-sum game.
A saddle point is a strategy profile satisfying for all , all , and each.
0コメント