Pages

Tuesday, April 12, 2011

Game Theory (Part 2) - The Formal Ingredients



This is part two of my series on game theory. For an index, see here. The series follows the lectures of Ben Polak, which are available on the Open Yale Courses website.

Last time out, we had a gentle introduction to the kind of thinking required in game theory. Game theory can be a lot of fun since it frequently involves playing games. But there is also some serious mathematics underpinning the whole field. Game theorists use the formal language of mathematics to build models of real world situations. In this post we’ll introduce some of this formal language.


1. The Ingredients of a Game
A game is any interaction between two or more rational (or purposive) agents. In any such interaction, a rational decision-maker will have to take into consideration what the other agent is likely to do. In other words, he will have to anticipate the actions and choices of others. This differentiates a game from a decision problem, which involves no anticipation.

Whenever you set about modelling a strategic interaction, you must ask yourself four key questions:

  • (1) Who are the players?
  • (2) What are their strategies or actions?
  • (3) What are their payoffs?
  • (4) What kinds of information do the players have at their disposal?


A word or two must be said about these questions.

The first question is relatively straightforward and simply forces us to consider who the decision-making entities are in the game. One thing to be wary of is that the player in a game is not necessarily isomorphic with an individual human being or organism. Players could be entire organisations who, for the purposes of building the model, can be treated as one agent.

The second question raises the distinction between an action and a strategy. An action is simply a choice that an agent can take at a particular round or node in a game. A strategy is a set of actions covering every round or node in a game. In games which have only one round, actions and strategies are equivalent. In games that have two or more rounds, they are distinct.

The third question raises the thorny issue of what exactly is a payoff. For the purpose of this series we won’t get into this issue. A payoff is taken as a measure of the satisfaction or desirability of an outcome for a player. One distinction to keep in mind is that between ordinal and cardinal payoffs. An ordinal payoff is a ranking; a cardinal payoff is supposed to be some kind of real number value. If one is dealing with uncertainties or probabilities, cardinal payoffs are required.

The fourth question is about the knowledge that the players have of the formal structure of the game. For the first part of this series, we will assume that the players have perfect information about the games. This means that they know who the other players are, what actions and strategies are available to them, and what payoffs they associate with particular outcomes.

Formally, we use the notation in the following diagram to represent each of these elements (minus information).



2. Notation in Action
We can now employ this notation in the analysis of a game. We can also use it to define some of the concepts, such as strict domination, that we introduced in part 1. Consider the game in the following diagram. There is no particular story or scenario motivating the model; it is purely an abstract mathematical entity.



Now ask yourself, are there any strictly dominated strategies in this game? Consider it first from the perspective of player 1. Hold player 2’s strategies fixed and determine which of 1’s strategies is best response to each of player 2’s. It is pretty clear when you perform this exercise that none of player 1’s strategies are strictly dominated. Each is a best response under different assumptions about player 2.

Now look at the game from the perspective of player 2. Again, hold player 1’s strategies fixed and work out which of player 2’s strategies are best responses. If we perform this exercise it becomes clear that although no single one of 2’s strategies dominates all the others, the strategy “centre” does strictly dominate “right”. This is because centre always yields a higher payoff than right, irrespective of what player 1 does.

This leads us to the following definition of strict dominance. It is stated in the diagram above but since it is so important it deserves to be repeated here:

Strict Dominance: Player i’s strategy Si* is strictly dominated by player i’s strategy Si if: 
  • Ui (Si, S-i) > Ui (Si*, S-i) for all S-i

If we were to continue our analysis of the game given in the previous diagram, we would delete player 2’s strictly dominated strategy (Right) and continue to solve it as a 2 x 2 game, instead of as a 3 x 2. This leads us to the concept of iterated deletion of strictly dominated strategies, which we’ll be discussing in future entries.

No comments:

Post a Comment