Feb 7

Repeated games

In game theory, repeated games, also known as supergames, are those that play out over and over for a period of time, and therefore are usually represented using the extensive form. As opposed to one-shot games, repeated games introduce a new series of incentives: the possibility of cooperating means that we may decide to compromise in order to carry on receiving a payoff over time, knowing that if we do not uphold our end of the deal, our opponent may decide not to either. Our offer of cooperation or our threat to cease cooperation has to be credible in order for our opponent to uphold their end of the bargain. Working out whether credibility is merited simply involves working out what weighs more: the payoff we stand to gain if we break our pact at any given moment and gain an exceptional, one off payoff, or continued cooperation with lower payoffs which may or may not add up to more over a given time. Therefore, each player must consider their opponent’s possible punishment strategies.

This means that the strategy space is greater than in any regular simultaneous or sequential game. Each player will determine their strategies or moves taking into account all previous moves up until that moment. Also, since each player will take into account this information, they will play the game based on the behaviour of the opponent, and therefore must consider also possible changes in the behaviour of the latter when making choices.

Repeated games provide different payoffs at each repetition, depending on each player’s moves. Since these payoffs are given at different points in time, in order to analyse repeated games, we must compare each player’s discounted sum of payoffs, which for infinite repetitions and finite repetitions are calculated using the following formulae:

Where: -P: the discounted sum of payoffs;

-t: the number of the repetition being considered;

-n: the total number of repetitions for finite repeated games;

-p_t: the payoff at the repetition being considered;

-r: the discount rate.

Repeated Prisoner’s dilemma:

In the game known as the Prisoner’s dilemma, the Nash equilibrium is Confess-Confess (defect-defect). In order to see what equilibrium will be reached in a repeated game of the prisoner’s dilemma, we must analyse two cases: the game is repeated a finite number of times, and the game is repeated an infinite number of times.

When the prisoners know the number of repetitions, it’s interesting to operate a backwards induction to solve the game. Consider the strategies of each player when they realise the next round is going to be the last. They behave as if it was a one-shot game, thus the Nash equilibrium applies, and the equilibrium would be confess-confess, just like in the one-time game. Now consider the game before the last. Since each player knows in the next, final round they are going to confess, there’s no advantage to lie (cooperate with each other) on this round either. The same logic applies for prior moves. Therefore, confess-confess is the Nash equilibrium for all rounds.

The situation with an infinite number of repetitions is different, since there will be no last round, a backwards induction reasoning does not work here. At each round, both prisoners reckon there will be another round and therefore there are always benefits arising form the cooperate (lie) strategy. However, prisoners must take into account punishment strategies, in case the other player confesses in any round.

Collusion agreement games:

If we assume the game can be played ad infinitum, we can apply it in a collusion agreement game, where two firms collude, forming a cartel. Consider two firms (a duopoly) that may either behave as Cournot duopolists earning profits π_Cournot each, or collude and act as a cartel, earning π_Cartel each, which correspond to the profits of a monopoly divided into the number of firms colluding (two in our example).

In this case, we simply need to apply the formula for calculating an infinite sequence and a discount factor to compensate for the fact that the gains to be derived are over time (accounting for impatience, inflation, loss of interest, etc.):

The left hand side represents the payoff derived from collusion, which can be held infinitely over time, with δ being the discount factor to bring future benefits forward to the present. For our threats or offers to be credible, this left hand side must be greater than the right hand side, which represents the one off payoff to be gained from deviating and breaking our cartel. The higher δ is, the higher the value assigned to future benefits and therefore the greater the chances of collusion. It is worth reminding here that fair competition is regulated in almost all countries, with cartels being banned, so most markets that lend themselves to reduced competition and price fixing are closely monitored.

Although this example is widely used in game theory and for the analysis of market structures, it can be easily seen that it does not represent a real situation. Let’s consider the same example: any of the colluding firms might deviate, in order to dump more output in the market at lower prices, in order to gain market share. This move will allow that firm to sell more products than the other firms, which directly contradicts Cournot’s premise that each duopolist will produce the same quantity. Therefore, considering a Stackelberg duopoly might seem more realistic. This would obviously change the analysis and outcome of the game.

Feb 6

Lope Gallego

Subgame

In game theory, a subgame is a subset of any game that includes an initial node (which has to be independent from any information set) and all its successor nodes. It’s quite easy to understand how subgames work using the extensive form when describing the game. In the following game tree there are six separate subgames other than the game itself, two of them containing two subgames each.

A subgame-perfect equilibrium is an equilibrium not only overall, but also for each subgame, while Nash equilibria can be calculated for each subgame. Consider the following game: player 1 has to decide between going up or down (U/D), while player 2 has to decide between going left or right (L/R). In this case, we can represent this game using the strategic form by laying down all the possible strategies for player 2:

-go Right if player 1 goes Up, go Left otherwise;

-go Left if player 1 goes Up, go Right otherwise;

-go Right no matter what;

-go Left no matter what.

We can see how this game is described using the extensive form (game tree on the left) and using the strategic form (game matrix on the left). Since this is a sequential game, we must describe all possible outcomes depending on player 2 decisions, as seen in the game matrix.

If we look for the equilibrium of this game, considered as a whole, we find that Up-Left is a Nash equilibrium (red). However, it’s not a perfect equilibrium. In order to find the subgame-perfect equilibrium, we must do a backwards induction, starting at the last move of the game, then proceed to the second to last move, and so on. In this particular case, we know that player 2 will choose Left if player 1 goes Up, and Right if player 1 goes Down, since these are the moves that maximise his utility. Because there is complete information (and therefore each player’s payoffs are known), player 1 knows these choices in advance, and will therefore choose to go Down, because the payoff will be greater. Therefore, Down-Right is the perfect subgame equilibrium (green).

Feb 5

Lope Gallego

Stackelberg duopoly

Stackelberg duopoly, also called Stackelberg competition, is a model of imperfect competition based on a non-cooperative game. It was developed in 1934 by Heinrich Stackelberg in his “Market Structure and Equilibrium” and represented a breaking point in the study of market structure, particularly the analysis of duopolies since it was a model based on different starting assumptions and gave different conclusions to those of the Cournot’s and Bertrand’s duopoly models.

In game theory, a Stackelberg duopoly is a sequential game (not simultaneous as in Cournot’s model). There are two firms, which sell homogeneous products, and are subject to the same demand and cost functions. One firm, the leader, is perhaps better known or has greater brand equity, and is, therefore, better placed to decide first which quantity q₁ to sell, and the other firm, the follower, observes this and decides on its production quantity q₂. To find the Nash equilibrium of the game we need to use backward induction, as in any sequential game. That is, start analyzing the decision of the follower.

For firm 2 (follower), the problem is similar to the Cournot’ model. The reaction as a function of q₁(blue lines) is as follows:

Firm 1 (leader) anticipates the follower’s behaviour and takes it into consideration to make the strategic choice of q₁:

Therefore, the quantities sold by each firm at equilibrium are:

The perfect equilibrium of the game is the Stackelberg equilibrium. In this game, the leader has decided not to behave as in the Cournot’s model, however, we cannot ensure that the leader is going to produce more and make more profits than the follower (production will be larger for the firm with lower marginal costs). Total production will be greater and prices lower, but player one will be better off than player two, which serves to highlight two things: the importance of accurate market information when defining a strategy, and the interdependence of each player’s strategies, especially when there is a market leader (with the benefit of moving first) and a follower.

When it comes to economic efficiency, the result is similar to Cournot’s duopoly model. The Nash equilibrium is not Pareto efficient (isoprofit curves, green curves, are not tangent to each other) and therefore, there is a loss in economic efficiency. Nevertheless, the loss is lower in the Stackelberg duopoly than in Cournot’s.

Stackelberg and Cournot equilibria are stable in a static model of just one period. In a dynamic context (repeated games), the models need to be reconsidered.

Comparison with Cournot duopolies:

-Stackelberg’s model is a sequential game, Cournot’s is a simultaneous game;

-In Stackelberg duopolies, the quantity sold by the leader is greater than the quantity sold by the follower, while in Cournot duopolies quantity is the same for both firms;

-When comparing each firm’s output and prices, we have:

Leader: q^S₁ > q^C₁ and π^S₁ > π^C₁

Follower: q^S₂ < q^C₂ and π^S₂ < π^C₂

-With regard to total output and prices we have the following:

Q_M < Q_C < Q_S < Q_PC

P_M > P_C > P_S > P_PC = MC

with:

Q_C: total Cournot output
Q_S: total Stackelberg output
Q_PC: total perfect competition output
Q_M: total monopoly output
P_C: Cournot price
P_S: Stackelberg price
P_PC: perfect competition price
P_M: monopoly price
MC: marginal cost

Feb 1

Lope Gallego

Simultaneous game

Simultaneous games are those where decisions are simultaneous: both we and the other ‘player’ choose at the same time. The simplest example of this is probably ‘rock, paper, scissors’. Complete information means that we know what we stand to win or lose: we know that rock beats scissors and that this will give us some form of utility (we might get to pick the plan for that evening or simply feel a warm glow of superiority). We also know that our opponent has this same information, this is, the rules of the game and each player’s payoffs are common knowledge. Simultaneous games are usually described using the strategic (or normal) form.

What this all means is that we only have one chance to get it right, but that we can play smart by knowing what our opponent will do and acting accordingly. An equilibrium is reached when both players will rationally make a decision that they have no reason to change: whatever else they do, they will only be worse off. Our situation can only be improved if our opponent chooses to do something else. These equilibria are known as Nash equilibria after John Nash, an economist from the early/mid 20^th century. The most famous example of this is the prisoner’s dilemma.

In this game, two prisoners are locked up in separate cells where they have no chance of communicating (imperfect information). They are both given the same (complete) information, which is summarised in the following game matrix:

In this example, the outcomes represented are years of freedom lost. If both prisoners confess, they will both receive an 8 year sentence. However, if neither confess, charges will have to be mitigated and both will receive low sentences. If one confesses and the other doesn’t, only one will receive punishment. Obviously, the best social outcome is for neither to confess, which would be the Pareto optimal situation. However, we can see that this is not a stable equilibrium. Both prisoners have an incentive to confess: if we are prisoner 2 (the vertical player) and we assume that prisoner 1 is going to confess, we have two possible outcomes: -8 if we confess and -10 if we lie. If we assume that prisoner1 is going to lie, we again have two outcomes: 0 if we confess or -1 if we lie. This means that, independently of the choice our opponent makes, we always have an incentive to tell the truth. Because we know this, we will choose to confess, and, because our opponent is in the same situation, chances are they will do the same. Once at this equilibrium, neither opponent has an incentive to change. This means we have one clear Nash equilibrium: where both players confess.

The process we have just followed in order to reach this conclusion is based on finding a dominant strategy (confess) which always overpowers the alternative under any choice the other player makes (whether our opponent confesses or lies). This allows us to rule out the overpowered strategy. In static games, we can have countless options, but this rational strategy will allow us to see our options more clearly and eliminate undesirable options in a systematic way.

What this process and what Nash equilibria do not allow us necessarily to do are to reach social optimums. The social optimum in this case would be for both players to lie and have charges mitigated: they would both be out within a year. But game theory tells us that social inefficiencies are common when dominant strategies are not for the common good.

Jan 31

Lope Gallego

Cournot duopoly

Cournot duopoly, also called Cournot competition, is a model of imperfect competition in which two firms with identical cost functions compete with homogeneous products in a static setting. It was developed by Antoine A. Cournot in his “Researches Into the Mathematical principles of the Theory of Wealth”, 1838. Cournot’s duopoly represented the creation of the study of oligopolies, more particularly duopolies, and expanded the analysis of market structures which, until then, had concentrated on the extremes: perfect competition and monopolies.

Cournot really invented the concept of game theory almost 100 years before John Nash, when he looked at the case of how businesses might behave in a duopoly. There are two firms operating in a limited market. Market production is: P(Q)=a-bQ, where Q=q₁+q₂ for two firms. Both companies will receive profits derived from a simultaneous decision made by both on how much to produce, and also based on their cost functions: TC_i=C-q_i.

So, algebraically:

In order to maximise, the first order condition will be:

And, if q_i=q_j, then both equal:

Therefore, the reaction functions (blue lines), where the key variable is the quantity set by the other firm, will take the following form:

What all this explains is a very basic principle. Both companies are vying for maximum benefits. These benefits are derived from both maximum sales volume (a larger share of the market) and higher prices (higher profitability). The problem stems from the fact that increasing profitability through higher prices can damage revenue by losing market share. What Cournot’s approach does is maximise both market share and profitability by defining optimum prices. This price will be the same for both companies, as otherwise the one with the lower price will obtain full market share, which makes this a Nash equilibrium, also known for this model the Cournot-Nash equilibrium.

If we consider isoprofit curves (those which show the combinations of quantities that will render the same profit to the firm, red curves) we can see that the equilibrium of the game is not Pareto efficient, since isoprofit curves are not tangent. The outcome is below that of perfect competition and therefore is not socially optimal, but it is better than the monopoly outcome.

Extending the model to more than two firms, we can observe that the equilibrium of the game gets closer to the perfect competition outcome as the number of firms increases, decreasing market concentration.

Comparison with Stackelberg duopolies:

-Cournot’s model is a simultaneous game, Stackelberg’s is a sequential game;

-In Cournot duopolies quantity sold is the same for both firms, while in Stackelberg duopolies, the quantity sold by the leader is greater than the quantity sold by the follower;

-When comparing each firm’s output and prices, we have:

Leader: q^S₁ > q^C₁ and π^S₁ > π^C₁

Follower: q^S₂ < q^C₂ and π^S₂ < π^C₂

-With regard to total output and prices we have the following:

Q_M < Q_C < Q_S < Q_PC

P_M > P_C > P_S > P_PC = MC

with:

Jan 31

Lope Gallego

Battle of the sexes

In the battle of the sexes, a couple argues over what to do over the weekend. Both know that they want to spend the weekend together, but they cannot agree over what to do. The man prefers to go watch a boxing match, whereas the woman wants to go shopping. This is a classical example of a coordination game, analysed in game theory for its applications in many fields, such as business management or military operations.

Since the couple wants to spend time together, if they go separate ways, they will receive no utility (set of payoffs will be 0,0). If they go either shopping or to a boxing match, both will receive some utility from the fact that they’re together, but one of them will actually enjoy the activity. The description of this game in strategic form is therefore as follows:

In this case, knowing your opponent’s strategy will not help you decide on your own course of action, and there is a chance an equilibrium may not be reached. This can be easily seen by looking for a dominant strategy, eliminating all dominated strategies. However, there will be two dominant strategies, two Nash equilibria (underlined in red). The way to solve this dilemma is through the use of mixed strategies, in which we look at the probability of our opponent choosing one or the other strategy and balance our pay off against it.

Jan 30

Lope Gallego

Mixed strategies

Mixed strategies need to be analysed in game theory when there are many possible equilibria, which is especially the case for coordination games. The battle of the sexes is a common example of a coordination game where two Nash equilibria appear (underlined in red), meaning that no real equilibrium can be reached.

In the battle of the sexes, a couple argues over what to do over the weekend. Both know that they want to spend the weekend together, but they cannot agree over what to do. The woman prefers to go shopping for a new pair of shoes, whereas the man wants to go a boxing match. The game matrix is therefore as follows:

In this case, knowing your opponent’s strategy will not help you decide on your own course of action, and there is a chance an equilibrium may not be reached. The way to solve this dilemma is through the use of mixed strategies, in which we look at the probability of our opponent choosing one or the other strategy and balance our pay off against it.

Let’s suppose that the woman is likely to choose boxing with probability q and shopping with probability (1-q). Likewise, the man is likely to choose boxing with a probability of r and shopping with a probability of (1-r). In that case, our outcomes are as follows:

Boxing-Boxing: qr
Shopping-boxing: (1-r) q
Boxing-shopping: r (1-q)
Shopping-shopping: (1-q) (1-r)

The man’s chances of going to a boxing match, his expected utility, will be 2r (payoff*probability) and, of shopping, 1-r (because his utility from shopping is 1), therefore r= 1/3.

Analogously, for the woman, q= 2/3. Now she must balance what q (the man’s chances of valuing his own happiness over hers) really is. If r>1/3, they’ll go to a boxing match. If r=1/3, either could happen, and if r<1/3, the woman will get her own way and they’ll go shopping. She must balance this carefully, because if she makes a mistake in valuing his probability (likewise for the man) then, as this is still a simultaneous game and there are no second chances, they could end up spending the weekend apart, which would mean less utility for both.

Jan 30

Lope Gallego

Dominant strategies

Dominant strategies are considered as better than other strategies, no matter what other players might do. In game theory, there are two kinds of strategic dominance:

-a strictly dominant strategy is that strategy that always provides greater utility to a the player, no matter what the other player’s strategy is;

-a weakly dominant strategy is that strategy that provides at least the same utility for all the other player’s strategies, and strictly greater for some strategy.

A dominant strategy equilibrium is reached when each player chooses their own dominant strategy. In the prisoner’s dilemma, the dominant strategy for both players is to confess, which means that confess-confess is the dominant strategy equilibrium (underlined in red), even if this equilibrium is not a Pareto optimal equilibrium (underlined in green).

It must be noted that any dominant strategy equilibrium is always a Nash equilibrium. However, not all Nash equilibria are dominant strategy equilibria.

The elimination of dominated strategies is commonly used to simplify the analysis of any game. The way to proceed is to eliminate for each player every strategy that seems ‘unreasonable’, which will greatly reduce the number of equilibria. This method is quite easy to use when only strictly dominated strategies are in place, but the elimination of weakly dominated strategies can turn problematic, ending up with a game that does not resembles the original one from a strategic point of view.

A good example of elimination of dominated strategy is the analysis of the Battle of the Bismarck Sea. In this game, as depicted in the adjacent game matrix, Kenney has no dominant strategy (the sum of the payoffs of the first strategy equals the sum of the second strategy), but the Japanese do have a weakly dominating strategy, which is to go North (the payoffs are equal for one strategy but strictly better for the other). Since only one of them has a dominant strategy, there is no dominant strategy equilibrium. We must then proceed by eliminating dominated strategies. As we’ve already mentioned, for the Japanese strategy ‘go North’ weakly dominates strategy ‘go South’. Therefore, we eliminate the strategy ‘go South’ for the Japanese, who will go North. Now that we only consider the Japanese going North, Kenney’s strategy ‘go North’ is strictly dominant over strategy ‘go South’, which will be eliminated. Therefore, North-North is the weak-dominance equilibrium.

However, as it was mentioned before, it can be easily seen that the game has lost its strategic nature.

Jan 30

Lope Gallego

Prisoner’s dilemma

The prisoner’s dilemma is probably the most widely used game in game theory. Its use has transcended Economics, being used in fields such as business management, psychology or biology, to name a few. Nicknamed in 1950 by Albert W. Tucker, who developed it from earlier works, it describes a situation where two prisoners, suspected of burglary, are taken into custody. However, policemen do not have enough evidence to convict them of that crime, only to convict them on the charge of possession of stolen goods.

If none of them confesses (they cooperate with each other), they will both be charged the lesser sentence, a year of prison each. The police will question them on separate interrogation rooms, which means that the two prisoners cannot communicate (hence imperfect information). The police will try to convince each prisoner to confess the crime by offering them a “get out of jail free card”, while the other prisoner will be sentenced to a ten years term. If both prisoners confess (and therefore they defect), each prisoner will be sentenced to eight years. Both prisoners are offered the same deal and know the consequences of each action (complete information) and are completely aware that the other prisoner has been offered the exact same deal (therefore, it’s common knowledge).

Description:

Since prisoners cannot communicate and will (supposedly) make their decision at the same time, this is considered to be a simultaneous game, and can be analysed using the strategic form, as in the adjacent game matrix. As described before, if both prisoners confess the crime they will be charged an eight years sentence each. If neither confesses, they will be charged one year each. If only one confesses, that prisoner will go free, while the other will be charged a ten years sentence. These can be seen as the respective payoffs for each set of strategies.

Eliminating all dominated strategies, in order to get the dominant strategy, can solve this game. This is, each prisoner will analyse their best strategy given the other prisoner’s possible strategies. Prisoner 1 (P1) has to build a belief about what choice P2 is going to make, in order to choose the best strategy. If P2 confesses (P2_C), he will get either -8 or 0, and if he lies (P2_L) he will get either -10 or -1. It can be easily seen that P2 will choose to confess, since he will be better off. Therefore, P1 must choose the best strategy given that P2 will choose to confess: P1 can either confess (P1_C, which pays -8) or lie (P1_L, which pays -10). The rational thing to do for P1 is to confess. Proceeding inversely, we analyse the beliefs of P2 about P1’s strategies, which gets us to the same point: the rational thing to do for P2 is to confess. Therefore, “to confess” is the dominant strategy. P1_C, P2_C is the Nash equilibrium in this game (underlined in red), since it is the set of strategies that maximise each prisoner’s utility given the other prisoner’s strategy.

Nash equilibriums can be used to predict the outcome of finite games, whenever such equilibrium exists. On the downside, we find the issue that arises when dealing with a Nash equilibrium that is neither social nor ethical, and where efficiency may be subjective, which is the case in the prisoner’s dilemma, where the Nash equilibrium does not meet the criteria for being Pareto optimal (underlined in green).

Generalisation of the game:

The prisoner’s dilemma is not always presented as we have seen in this case. Payoffs for each set of strategies will vary, depending on each person. However, there are a few rules that can be used to build a “proper” prisoner’s dilemma game.

In the adjacent game matrix, we’ve renamed each player’s payoffs, in order to determine the conditions needed to design a prisoner’s dilemma game. In a traditional prisoner’s dilemma, we have: A > B > C > D (in absolute terms). In our previous example, this condition is met (A=10, B=8, C=1 and D=0). In every case, A>B and C>D imply that confess-confess is a Nash equilibrium.

It must be noted that the asymmetry of the game is not the important part of the prisoner’s dilemma. The interesting thing about this game is the fact that its Nash equilibrium is not socially optimum.

Repeated prisoner’s dilemma games:

In order to see what equilibrium will be reached in a repeated game of the prisoner’s dilemma kind, we must analyse two cases: the game is repeated a finite number of times, and the game is repeated an infinite number of times.

Jan 27

Lope Gallego

Extensive form

In game theory, the extensive form is away of describing a game using a game tree. It’s simply a diagram that shows that choices are made at different points in time (corresponding to each node). The payoffs are represented at the end of each branch. Since the extensive form represents decisions at different moments, it’s usually used to describe sequential games, while simultaneous games are described using the strategic form. Since sequential games imply making decisions at different moments for each player, information is perfect since each player can see the decision taken by the previous player, complete and the rules of the game and each player’s payoffs are common knowledge.

In the first game tree we can see how player 1 is the first to decide, while player 2 will make a decision after observing what player 1 has decided. The payoffs represented at the end of each brand represent all possible outcomes. For instance, if player 1 chooses strategy A and player 2 chooses strategy B, the set of payoffs will be p_1A,p_2B.

A good example of a sequential game described with the extensive form is when considering collusion agreements, as depicted in the second game tree.

Two firms share the market, colluding and maintaining high prices. Each firm can decide to stop colluding and start a price war, in order to increase their market share, even force the other to quit the market. Firm 1 can either keep colluding with firm 2, or start a price war. If firm 1 decides to keep colluding, firm 2 will need to make a decision. If they both agree to collude, they will get 5,5. However, if one of them decides to start a price war, the set of payoffs will be either 4,3 or 3,4, depending on which one starts the war (and therefore acquires a greater market share). It’s easy to see that collude-collude is both the Nash equilibrium and a Pareto optimum situation. This result may change when considering repeated games.

It’s worth mentioning that the extensive form can be used also to describe simultaneous games, by using information sets, as shown in the third game tree. These information sets, usually represented by a dashed line uniting two nodes or by encircling them, mean that the player does not know in which node he is, which implies imperfect information, like when using the strategic form.