Feb 10

Sequential games

In sequential games, a series of decisions are made, the outcome of each of which affects successive possibilities. In game theory, the analysis of sequential games is of great interest because they usually model reality better than simultaneous games: producers will usually observe demand before deciding how much output to produce, duopolists will observe each other’s decisions before dumping more goods in the market, etc. For example, let’s examine the decision a company faces when trying to break a market which is currently a monopoly. Sequential games are represented through decision trees, with successive nodes at each decision point:

The game represented in this decision tree shows firm 1 choosing whether to compete in a monopolistic market or not. As there are no existing competitors in the market, should they choose not to enter, its payoff will be zero and the existing monopoly will have a payoff of two. However, if firm 1 chooses to enter we reach node two, where the second decision must be made by the challenged player (the monopoly), whether to accommodate the new competitor or fight back to try and block its entry. In this particular example, if they choose to fight, both players will have a payoff of -1, whereas if the monopoly decides to accommodate the new player, our monopoly becomes a duopoly and the resulting drop in prices creates larger market demand, meaning that the existing company will still receive a payoff of one and the new player a payoff of two.

So, what can we assume will happen? We assume that both players dispose of complete and perfect information. They have both carried out a thorough market study and know the consequences of each outcome. In that case, what they can do is work backwards to know what the competition will do. If firm 1 enters the market, player 2 has no reason to fight back, as its payoff will suffer by two points. This means that player 2 knows what the outcome will be if they choose to enter, so all they have to do is choose between a payoff of two if the new firm enters the market or zero if it doesn’t. In this case, it is pretty clear what the outcome will be. The game would change again, of course, if successive nodes were introduced, where fighting could again flip the tables.

Feb 8

Lope Gallego

Folk theorem

Folk theorems are used in Economics specially in the field of game theory and specifically to repeated games. This theorem is said to be satisfactorily fulfilled when the equilibrium outcome in a game that is repeated an infinity number of times, is the same as the feasible and strongly individually rational outcome in the one-shot game. The outcome is said to be in equilibrium, because any attempt of trying to increase a player’s individual outcome will imply a decrease in at least another player’s individual outcome.

The origin of this theorem is unknown but it appeared in the late fifties, and became quickly known and spread within the game theory academia, and thus the reason why it became known as the folk theorem. James W. Friedman in his article “A Non-cooperative Equilibrium for Supergames”, 1971, was the first to write and publish a paper in which he thoroughly deals with the theorem.

The main issue that this theorem explains, is the strong relationship between repeated and cooperative games, revealing the enforcement mechanism characteristic of repetition. One of the first applications of the theorem was to collude when dealing with a Cournot duopoly:

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, that fair competition is regulated in almost all countries, with cartels being banned, and so most markets that lend themselves to reduced competition and price fixing, are closely monitored.

Feb 8

Lope Gallego

Collusion

Collusion makes allusion to the cooperation between different firms. This cooperation leads to a restrain of market competition, in any of its forms, which translates into higher profits for the firms in detriment of consumer’s welfare. A cartel is an example of firms belonging to the same industry structure which collude to some degree in setting prices and/or output levels. Agreements which have as their object or effect the prevention, restriction or distortion of perfect competition are prohibited. Such agreements include, but are not restricted to, activities such as:

-fixing purchase or selling prices or any other trading condition, directly or indirectly;

-controlling or limiting production levels, markets, technological advances or investments;

-sharing markets or resources supplies.

Legislation in different countries may consider different scenarios and penalties for such agreements, but the main idea is clear: firms behaviour shall not affect the correct functioning of market forces.

A clear example is to consider an industry where there are only two firms (duopoly). Both firms will set their levels of output and prices with the objective of maximizing their joint profits. Many strategies can be used in order to maximize profits which would lead to a multiple Nash equilibria solution. As seen in the figurebelow, collusion maximises aggregate profits for both firms, since the isoprofit curves are tangent. It’s a better equilibrium than the one in Cournot duopolies or Stackelberg duopolies.

However, cartels are not stable. There will always be incentives for each firm to trick the other, and change their output and/or price level in such a way, that they’ll increase their own profit in detriment of the other’s. To avoid this practice, any deviation by any party should be instantly punished; this is known as a trigger strategy. James W. Friedman demonstrated in his paper “A Non-cooperative Equilibrium for Supergames”, 1971, that in this context of infinite interactions, it is possible that collusion occurs due to this punishment strategy. That is, the cartel may endure as long as punishment strategies are so devastating that the benefits derived form deviation would end up being smaller than the benefits of keep colluding. J. W. Fridman put this idea in what is known in game theory as Folk theorem:

The sustainability of the equation will depend mainly in two factors: the credibility of the threat of punishment, and the discount factor. The former is easily understood as a credible threat will ensure no deviations are made, and the latter is related with how much does each party value the profits obtained from the results of following a collusive strategy, compared to the possible profits of changing their strategy.

Factors that guarantee collusion stability:

There are number of factors that affect this collusive equilibrium, such as:

-Number of firms in the market: the higher the degree of concentration in a market the higher the incentives to collude. Firms in highly concentrated markets will tend to collude since all the profits will be distributed amongst fewer firms.

-Multimarket contact: if firms compete in more than one market, the collusive agreement will be more stable. Firms that compete with other firms over many markets can establish trigger strategies that can be applied in all these markets, which will create a more devastating punishment strategy.

-Market transparency: the more transparent a market is, the easier it is to ensure that every firm is following the same strategy and is not deviating from the deal. Collusion will be more difficult in industries where it is harder to detect changes in firm’s prices or output.

-Asymmetry between firms: the bigger the asymmetry between firms, the harder it is for collusion to take place. If firms have different cost structures, the one with the lowest costs will be incentivised to lower its prices, and thus cause the other firm to have to exit the market.

Collusion agreement games:

In game theory, collusion agreements can be described using the extensive form, as depicted in the adjacent game tree. In this case, two firms share the market, already 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, as seen before.

Feb 7

Lope Gallego

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.