Normal form games

If both thieves cooperate and do not divulge any information they will each get a short sentence with a utility value of 3. If one defects they are offered a deal utility value of 5 while the other thief will get a long sentence utility value of 0. If they both defect they both get a medium length sentence utility value of 1.

Suppose two birds of prey must share a limited resource. The birds can act like a hawk or a dove. Two doves can share the resource both getting a utility value of 2.

Consider two pigs. One dominant pig and one subservient pig. These pigs share a pen. There is a lever in the pen that delivers food but if either pig pushes the lever it will take them a little while to get to the food. If the dominant pig pushes the lever, the subservient pig has some time to eat most of the food before being pushed out of the way. The dominant pig gets a utility value of 2 and the subservient pig gets a utility value of 3. If the subservient pig pushes the lever, the dominant pig will eat all the food.

Informally, the concept of a best response refers to the best strategy that an agent could select if it know how all of the other agents in the game were going to play. Using this, we can define the Nash equilibrium of a game, which is named after the famous mathematician John Nash, who in his PhD thesis provide that all finite normal form games have a Nash equilibrium. If the strategies in a Nash equilibrium are all pure strategies, then we call this a pure-strategy Nash equilibrium.

Otherwise, if is a mixed-strategy Nash equilibrium. The set of best responses for a normal form game can be calculated by searching through all strategies to find those with the highest payoff. Clearly, the best response for both agents is the unique strategy to admit.

Finding Nash equilibria involves searching through all strategy profiles and finding those in which all agents strategies are a best response in that profile. Here is an algorithm for finding the Nash equilibria for a two-player normal form game:. In fact, for any game in which all agents have a dominant strategy, that will form a unique Nash equilibrium.

Therefore, this is a Nash equilibrium. Therefore, this is NOT a Nash equilibrium. Split or steal is a game in which two agents need to decide whether to split a pot of prize money, or try to steal it from the other. If they share, both receive half of the prize money. If one steals and one shares, the stealer receives all of the prize and the other agent receives nothing. If they both steal, both receive nothing. The game matrix for this can be described as follows:.

What are the Nash equilibria. There are in fact three Nash equilibria for this game, highlighted using the square brackets above.! Recall from earlier in this chapter where we defined mixed strategies , which are strategies that use randomisation. To illustrate why these are necessary, consider the following simple game. We can model this as follows:. It is clear that neither agent has a dominant strategy and there are no pure-strategy equilibria: in every call, there is an incentive for the agent receiving -1 to deviate from their strategy.

So, what strategy should we play? Intuitively, we would choose each with probability 0. To do this, we need to define the concepts of expected utility and indifference. Expected utility is the weighted average received by an playing a particular pure strategy.

In theory, we can maximise our overall utility by picking the pure strategy with the highest expected utility. However, in a game, we do not know the probabilities that our opponents will play those moves! This is where indifference comes in.

Informally, this states that an agent is indifferent between a set of pure strategies if the expected return of all strategies is the same. The agent is therefore indifferent between these pure strategies because it does not matter which action they choose. Informally, this states that each agent should choose a mixed strategy such that it makes their opponents indifferent to their own actions.

However, if we analyse it from the perspective of the opponent, it becomes clear: if we select the probabilities for a mixed strategy such that our opponent is not indifferent, then this means there is at least one strategy that has a higher expected utility than all others. In that case, the opponent would play that strategy. In this example, the probabilities of the game are reasonably clear without having to solve.

Branches from each node describe how the game evolves as players make their decisions. After every player exhausts their successive decisions, the terminal or final node specifies the payoffs or utility that each player receives. The decision tree above is an example of a sequential game between two hunters: Yosemite and Elmer. Yosemite, the first mover, decides between hunting stags or hare. Upon seeing this decision, Elmer must decide whether he too will hunt stags or hares.

The payoffs associated with their choices are presented at the end of each path. For example, if Yosemite chooses stag, but Elmer chooses hare, then Yosemite gets a payoff of zero, while Elmer gets one. In this story, stag is valuable only when both players hunt together. Notice the payoffs jump to two each if both of them choose to hunt stag.

Put simply, strategies are decision rules that players can use in a given strategic situation. In game theory, a complete strategy specifies a response at every information set. It accounts for every contingency, even if the decision node is unlikely to materialise in game. In the example above, Yosemite has two strategies to choose from: Stag or Hunt. Elmer, by contrast, has four strategies to choose from: 1 Always choose stag; 2 Always choose hare; 3 Choose the opposite of Yosemite — hare if stag, and stag if hare; and 4 Choose the same as Yosemite — stag if stag, and hare if hare.

In games like chess, specifying strategies in a game theoretic sense is impossible. There are just too many permutations and possibilities. Human players have to rely on their experience, knowing and intuition to sample a manageable set of strategies to select their preferred course of action.

Introductory game theory, by contrast, focuses on a few options and permutations. In truth, though, there are probably infinite options to consider in life and business. For better and worse, we have no choice but to simplify the game into manageable components. Game theory is as much an art as it is a social science. Those that know how to scope, simplify, and focus will enjoy an edge in decision-making.

If an extensive form game has perfect information, then players know the decisions that everyone has made prior to their turn.