Game theory and strategy - completo

Game theory and strategy

Chapter 1

This chapter is organized into three sections in which there is a short introduction to game theory and strategy. In the last part of this chapter, there is also a detailed description of three games.

If game theory were a company, its corporate slogan would be "no man is an island". This is because the focus of game theory is interdependence, situations in which an entire group of people is affected by choices made by every individual within that group. If we stop ourselves and think about what game theory, in reality, is, we might understand that every choice made by a committee or an organization will use this "problem solutions".

Like every subject, also this has a precise vocabulary:

• Player: each decision maker.
• Interaction: what any one individual player does directly affect at least one other player.
• Strategic: an individual player accounts for this interdependence in deciding what action to take.
• Rational: while accounting for this interdependence, each player chooses her best action.

Nim and Marienbad

These are two parlour games in which there are two piles of matches and two players. When it is a player’s turn, he can remove any number of matches from either pile. Each player is required to remove some number of matches if either pile has matches remaining and he can only remove matches from one pile at a time. Now we have to distinguish every single game: in Nim, the winning player will be the one who removes the last match; in Marienbad, the losing player will be the one who removes the last match.

Analysis of Nim

Let’s start with a distinction: we should call balanced piles if there is an equal number of matches in each pile, and we should call unbalanced piles if there is not an equal number of matches in each pile. It turns out that if there is a balanced case, player 2 has a winning strategy; otherwise, if there is an unbalanced case, player 1 has a winning strategy.

Let’s start with the case in which there is only one match for each pile: it’s easy to see that player 2 has a winning strategy due to the rules of the game. Moreover, we can go on and on by adding an equal number of matches in each pile and the result will be always the same: using a strategic and rational turn, player 2 has always a winning strategy by only matching the number of matches of the other pile.

By using the same logic, we can easily see that in an unbalanced case, player 1 may balance the piles and have a winning strategy.

Analysis of Marienbad

If there is a balanced case with only one match for each pile, player 1 has a winning strategy. On the other hand, if there is a balanced case with at least two matches for each pile, player 2 has a winning strategy. In opposite, if there is an unbalanced case with at least two matches for each pile, player 1 has a winning strategy.

Voting

This exercise is an idealized version of committee voting. This is a manner of voting in which a voter thinks through what the other voters are likely to do rather than voting simply according to his preferences. Suppose that there are two competing bills, A and B, and three legislators, 1, 2 and 3. The voting proceeds as follows: at the first round bill A is set against bill B, the winner in the second round will be pitted against the status quo (neither or N). in each of the two rounds of voting, the bill that the majority of voters cast their vote for, wins. Now each legislator has preferences on the three status:

• VOTER 1: A > N > B
• VOTER 2: B > A > N
• VOTER 3: N > A > B (> should be read as “strictly preferred than”)

Note that if the voters voted according to their preferences, then A would win against B and then, in round two, would also win against N. However, voter 3 would be very unhappy with this state of affairs: she prefers the N status and can, in fact, enforce this outcome by voting B at the first round. Hence if we just look at the possible outcomes, we can easily face that if at the first round wins A, at the second round will always win A; otherwise, if at the first round wins B, at the second round will always win N. every rational legislator knows that, so, in fact, they are voting between A and N.

Prisoners’ dilemma

This story underlying the prisoners’ dilemma goes as follows: there are two prisoners, Calvin and Klein, are hauled in for a suspected crime. The lawyer speaks to each other separately, and she offers the same deal for both of them:

The entries into the table represent the number of years that they have to do. From the pair’s point of view, the best outcome is (NOT CONFESS , NOT CONFESS). The problem is that if Calvin thinks that Klein is not going to confess, he can avoid the prison by ratting on Klein. Surely the same logic is running through the mind of Klein. Consequently, they’re both end up confessing.

Chapter 2

This chapter will provide an introduction to the formal structures within which we can study interdependence. Every game has a set of rules that run the game:

• It should give who is playing in the group of players that strategically interacts.
• It should demonstrate what they are playing with the alternative actions and choices, the strategies that each player has available.
• It should notice when each player has to play and in what order.
• It should offer the gain or loss from the choices made in the game.

Remember that these rules are assumptions of the games and if you ask a question to each player separately about them, they will answer in the same way. This does not mean that each player has the same complete information. In each example described in the first chapter this stuff was given verbally; however in this subject there are two representations to describe the games: normal or strategic form and extensive form.

Extensive form

It’s a pictorial representation of the rules and its main pictorial form is called game tree. Much like an ordinary tree, a game tree starts from a “root”, so one of the players has to make a choice. The various choices are represented like the branches of a tree emanated from the root.

This is the simplest tree that we could find, on the other hand the branches could become a root and so on. In this case the branches split into two new branches but they can split into more branches. The result is that the first choice affects the second one: just following the lines or the branches the result can be reached. In other terms the choices are sequential. The end of one of the first is called decision node.

Of greater interest is the case in which a second player has to make the second choice. For instance suppose that two players are on their way to see a musical that is in great demand. Suppose also that there is only one ticket left and whoever arrives first will get the ticket. Player 1 leaves a little bit earlier than player 2 so in that sense he makes the choice at the root of the tree and subsequently the second player makes his choice.

The extensive forms discussed above permit only one player to play at a time, what happens if the game is simultaneous? The key idea here is that a player will act in the same way in either of two circumstances: firstly, if they literally choose at the same time, so simultaneously, secondly, if player 2 chooses after 1 but is unaware of his choice.

Normal or strategic form

It’s a complete list of who the players are, what strategies are available to each of them and how much each gets. Using the same instance above, the musical, the representation is a table in which the three rows correspond to the strategies of player one, and the 33 columns correspond to the strategies of player 2. In every cell of the table we’ll write the payoffs related to the pair of strategies.

In this case, into the cells we will write the payoff that comes from each pair of strategies. (N = no ticket, T = ticket). Thinking about the order of the players, normally this form represents a simultaneous game, but with a more difficult table with more strategies can be also represented as sequentially game which describes who plays first.

The last thing that we might describe is how much does each player stand to gain or lose by playing the game. In other words what is the payoff or utility function of a player. We will use the Von Neumann-Morgenstern utility function. When the outcome of a game is monetary, each player pays out or receives an amount of money. But what happens in games in which the outcome is not monetary? At the beginning we have to note that each player will typically have opinions about which strategy combinations are preferable. Hence we could attach into the matrix only numbers and call them the payoffs. A higher payoff would signify a preferred alternative. For instance, using the prisoners’ dilemma, the result will be:

In the cells we may note that all the numbers are preceded by a minus: this represents that is a loss of utility of the player. In fact the number of years in prison is a loss of utility.

Chapter 3

In this chapter we are going to study in greater detail the strategic form representation of a game and the dominant strategy solution. The strategic form of a game is specified by three objects:

• The list of players in the game.
• The set of strategies available to each player.
• The payoff associated to any strategy combination.

The payoffs should be thought of as Von Neumann-Morgenstern utilities. Let’s assume that we’re in the simplest case: two players, labelled as player 1 and player 2, and two strategies.

When there are more than two players or more than two strategies it helps to have a symbolic representation, because the matrix representation can be very cumbersome very quickly. So let’s find some symbols that may help us in the future:

• Player 1 → i
• Player 2 → 2
• Player i’s strategies → s_i
• Player i’s specific strategy → s*_i
• Player i’s payoff function → p_i

Let’s use some examples like the prisoners’ dilemma: in here “C” stays for “confess” and “NC” stays for “not confess”.

Now we’re going to face an example with more than two strategies: Colonel Blotto. In here we might find two players: Colonel Blotto and Colonel Tlobbothat are fighting against each other in a war. The first colonel has two infantry units that he can send to any pair of locations (1,2 for instance means that the units go to locations 1 and 2); the second one has only one unit and he can send it to just a location. A unit wins a location if arrive there uncontested, otherwise a unit fights to a standstill if an enemy unit also comes to the same location. The yield of the standstill is zero and the yield of the winning is one.

Using the previously example prisoners’ dilemma, now we’re going to study the dominant strategy solution.

Definition: Strategy strongly dominates all other strategies of player I if the payoff s is strictly greater than the payoff to any other strategy, regardless of which strategy is chosen by the other player. In fact we see:

The strategy “confess” has the property that it gives Calvin a higher payoff than “not confess” rather than if Klein does not confess. It also gives a higher payoff rather than if Klein does confess. Hence, no matter what Klein does, Calvin always gets a higher payoff confessing. Similar logic could be used for Klein. As a result of this game it’s therefore reasonable to predict that both players will end up confessing.

If we do not have a strictly dominant strategy, we might have a weakly dominant strategy.

Definition: A strategy weakly dominates another strategy, given s*, if it does at least as well as s against every strategy of the other players, and against some it does strictly.

Chapter 4

In this chapter we’re going to study a second solution concept form strategic form games: iterated elimination of dominated strategies (IEDS).

Definition: A strategy s is dominated by another strategy s' if the latter does at least as well as s against every strategy of the other players, and against some it does strictly better. If a strategy is not dominated by any other, it’s called an undominated strategy.

Consider the same example from chapter 3: in this strategic form “low” is dominated by “high” if and only if (H , N) π ≥ π (L , N) and (H , S) π ≥ π (L , S) with at least one of those inequalities being strict. Generally consider a game in which player i has many strategies: if there is a dominant strategy, all the remaining strategies are dominated; if there is not a dominant strategy there may not be any best strategy. Now using the IEDS let’s find the solution of the following problem:

Let’s start with player 1: we can easily see that “down” is dominated by “up” and “middle” because she gets always a lower payoff, no matter what the other player will choose. It’s important to remember that for a player is useless to play a dominated strategy because there will be always a strategy that gets a higher payoff, so we can “eliminate” “down”. Now it’s player 2 turn and he has to choose between “left” and “right” related to the two other strategies remained. “Left” will always offer a higher payoff than “right” for player 2 so, in order to reach the final result, we have to consider a third stage in which player 1 have to choose between “up” and “middle”. For him, the best strategy is always “up” rather than “middle”. The chosen strategy (UP , LEFT) is said to be reached by iterated elimination of dominated strategies (IEDS), the game itself is said to be dominance solvable.

The advantage of this concept is inherent in the simplicity of the dominance concept: in fact if a player is convinced that a strategy always does worse than some alternative strategy, then he will never use it. The disadvantages of this concept are the layers of rationality. Let’s assume that the strategy (UP , LEFT) costs a fee for player 1: he will not want to choose it anymore, so the game is not anymore rational.

Chapter 5

In this chapter we will look to the most famous solution concept for strategic form games: Nash equilibrium.

Suppose that you have a strategy B that is dominated by another strategy, say A. We have seen that the player will always choose strategy A due to the different and higher payoff than strategy B. Now suppose that the player has some ideas about the other player’s intentions. In that case he would choose A provided it does better than strategy B, given what the other player is going to do. Hence, you do not know that strategy A is always better than strategy B against all the enemy’s strategies, what is important to know is that strategy A performs better than strategy B against a specific strategy. Indeed strategy A is called best response against the known opponent’s strategy. Typically you will not have the certain strategy of the enemy, you will have a guess about his possible strategy choice. Of course, the guess might be wrong. If it is correct and also the other player plays a best response, you will be in a Nash equilibrium.

Two questions about Nash equilibrium arise:

1. Do we know that every game has a Nash equilibrium? Recalling the dominant strategy solution or the IEDS, we can easily see that these concepts yield no solution in many games.
2. Do we know that a given game will have exactly one Nash equilibrium? We know that in many games there is more than one Nash equilibrium, but the question is which one of them is the most reasonable?

Let us now show several examples:

Example 1: Battle of the sexes

We can easily see that using the concept of best response, in green we might see the best responses of player 1 against the two opponent’s strategies and in red we might find the best responses of player 2 against the two opponent’s strategies. In this game (FOOTBALL , FOOTBALL) and (OPERA , OPERA) are both a Nash equilibrium.

Example 2: Prisoners’ dilemma

Without using the concept of best response, we may use the previously stuff about this game: we know that confess is a dominant strategy, but this is the same thing as saying that both players are choosing the best response. Hence, the only solution of this game is (CONFESS, CONFESS).