Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

“НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

“ВЫСШАЯ ШКОЛА ЭКОНОМИКИ”

Международный Институт Экономики и Финансов

БАКАЛАВРСКАЯ РАБОТА

По направлению подготовки 38.03.01 “Экономика”

Образовательная программа

“Программа двух дипломов по экономике НИУ ВШЭ и Лондонского Университета”

Москва 2018

Аннотация к работе.

равновесие динамичный игра

Эта работа посвящена новому равновесию, которое используется в динамичных играх. В основу этого равновесия заложено сочетание идей скоррелировонного равновесия и подыгрового совершенного равновесия. Наряду с анализом работ, посвященных корреляции между действиями игроков в последовательных играх, в этой работе представлены два новых равновесия, примеры, демонстрирующие работу этих равновесий, а так же формальные определения. Динамичное скоррелированное равновесие расширяет множество стабильных решений в динамичных играх, а так же отличается от схожих равновесий строгостью требований к совместимости инициатив и удобством использования равновесия.

Table of Contents

• 1. Introduction
• 2. Literature review
• 3. Examples
• 3.1. Example 1. Public signals
• 3.2. Example 2. Private signals
• 4. Definitions
• 4.1. Preliminary definitions
• 4.2. Dynamic correlated equilibrium with private signals
• 4.3. Dynamic correlated equilibrium with public signals
• 4.3. Comparison of definitions
• 5. Conclusions and further steps
• 6. References
• 7. Appendix
• 7.1. Example 1
• 7.1.1. Equilibria of the stage game
• 7.1.2. Subgame Perfect Equilibria
• 7.1.3. Proof of payoff threshold
• 7.2. Example 1
• 7.2.1. Equilibria of the stage game
• 7.2.2. Subgame Perfect Equilibria
• 7.2.3. Proof of payoff threshold


1. Introduction

In static games, payoffs that cannot be achieved in pure or mixed strategies, can be achieved with the help of a randomization device that allows for correlations among the actions of players. In his paper “Subjectivity and Correlation in Randomized Strategies” (1974), Robert J. Aumann describes how correlation expands a hull of stable outcomes of a game and introduces the concept of correlated equilibrium. The concept of correlation in dynamic games has not yet been fully explored. The most widely used solution concepts for dynamic games with observable actions - subgame perfect equilibria in pure and mixed strategies assume that players' actions are not correlated. In my research I combine the ideas of subgame perfect equilibrium and correlated equilibrium. Such a combination allows to achieve Pareto improvement in outcomes that are not available in a simple subgame perfect equilibrium.

In static games, when players coordinate their actions using public signals, they can only play Nash equilibria. One may expect that in dynamic games, public signals only allow to coordinate on subgame perfect equilibria. I show that in dynamic games coordination via public or private signals allows to induce non-SPE paths. More generally, I characterize with a new solution concept the outcomes of the game that can be obtained when players reach an agreement that uses correlation devices. This agreement may include credible threats that cannot be made without using correlation among the actions of players.

The main motivation for this research is to introduce a solution concept which captures coordination that occurs in the process of a game. Equilibrium that includes a coordination, which exact nature is, to some extent, uncertain from an earlier perspective of a game, explicitly demonstrates the role of time dimension in sequential games.

The first to introduce a solution concept which combines correlation among actions of players and subgame perfection was Roger B. Myerson (“ Multistage games with communication”, Econometrica, 1986). However, this solution concept, sequential communication equilibrium, cannot be applied to dynamic games with observable actions and, therefore, cannot be compared with subgame prefect equilibrium. Besides, the definition of this concept is so sophisticated that ever since its introduction, it has barely been being used. In contrast, dynamic correlated equilibrium doesn't require introduction of any other players that would make moves in a modified game. The advantage of dynamic correlated equilibrium is that I model signals such that they coincide with the prescribed actions. In other words, signal modeling in DCE replicates simple and intuitive approach used in the canonical definition of correlated equilibrium in static games.

As mentioned above, subgame perfect equilibrium is an extension of Nash equilibrium to dynamic games. Basically, it is formed at the ex ante stage of a game. Nothing really changes as the game unfolds because rational players have no incentives to deviate from paths that they agreed on the ex ante stage. This solution concept doesn't take advantage of a game's dynamism. I will demonstrate that in the dynamic correlated equilibrium, the fact that a game is dynamic, makes an explicit difference.

2. Literature review

The concept, which is the closest to the idea of dynamic correlated equilibrium was introduced by Roger Bruce Myerson in his paper “Multistage games with communication” (Econometrica, 1986). This paper explores properties of correlation among actions of players in multistage games. Myerson's idea is to develop a solution concept that would capture both subgame perfection and communication among players. This idea is embodied in the sequential communication equilibrium. It should be noted that sequential communication equilibrium defines a more general set of solutions than dynamic correlated equilibrium. However, there is a number of crucial differences between two solution concepts. Firstly, Myerson does not show examples of correlation by public signals. In his paper, only correlation by private signals is described. This is an important point, as public signals represent a less demanding coordination tool. Secondly, in examples 4 and 5, one can see, that after introduction of a mediator, which carries out communication, a game with observable actions is transformed into a game with unobservable actions:

Рисунок 1. Example 4

Рисунок 2. Example 5.

First of all, it should be pointed out that despite the fact that Player 4 doesn't know whether Player 3 played e or f, Example 4 doesn't represent a game with unobservable actions. This is because a subgame which is reached by the path (a,c) can be interpreted as a static game between players 3 and 4. Secondly, one can see, that, if Player 1 chooses a and Player 2 chooses c, players 3 and 4 face a subgame which has the unique Nash equilibrium. In this equilibrium, players 3 and 4 use randomized strategies in which each action is played with probability Ѕ. So, using backward induction procedure, one can find the only subgame perfect equilibrium in which Player 1 chooses a and Player 2 chooses d. Myerson's idea is to introduce the following agreement: with probability 1/2, Player 1 chooses b, Player 2 plans to choose c, Player 3 plans to choose e and Player 4 plans to randomize between g and h; with probability 1/2, subgame perfect equilibrium is played On the picture 2, . Such an agreement cannot be implemented without correlation among actions of players because Player 4's best reply to e is playing h rather than randomizing. This leads to the introduction of coordination among players 1, 2 and 3, which is presented in Example 5. This coordination is realized via random event observed by players 1, 2 and 3, but not Player 4. Basically, it is a move by Player 0 (Up or Down). The agreement is such that, if the move of Player 0 is Up, Player 1 chooses b, Player 2 plans to choose c and Player 3 plans to choose e. If the move is Down, Player 1 chooses a, Player 2 chooses d and Player 3 plans to choose f. Now, once Player 4 observes that she gets to make a move, she concludes that either Player 1 or Player 2 made a mistake. However, since Player 4 cannot observe action of Player 0, she best replies to the belief that player 1 and 2 make their mistakes with equal probabilities. And the best reply is to randomize between g and h. The desirable outcome is reached but the game is transformed into a game with unobservable actions.

I argue that such an agreement can be reached without transforming the game. This can be done via dynamic correlated equilibrium. Consider a randomization device that is able to coordinate actions of players using private signals. Such a device can implement the following agreement: Player 1 receives signals to play a or b with equal probabilities; if Player 1's prescription is to play a, then Player 2 is signaled to play d and Player 3 is signaled to play f; if Player 1's prescription is to play b, then Player 2 is signaled to play c and Player 3 is signaled to play e. Player 4 doesn't receive any signal and she doesn't know the exact realization of the randomization. So once she gets to move, she best replies to the belief that Player 1 fails to follow the prescription with probability Ѕ and Player 2 makes a mistake with the same probability. As one can see, a simple agreement proposed by DCE allows to implement the same outcome without game transformation.

So, we've demonstrated that in Myerson's paper, the analysis of simple games becomes artificially complicated, to the point that one cannot apply simple solution concepts like subgame perfect equilibrium when introducing correlations among actions of players at different stages. In other words, an explicit demonstration of how the concept of subgame perfect equilibrium can be combined with coordination between players in games with observable actions is absent from Myerson's paper. This demonstration, though, is carried out by the concept of dynamic correlated equilibrium.

Another concept relatively close to DCE was introduced by Bernard von Stengel and Francoise Forges in their paper “Extensive Form Correlated Equilibrium: Definition and Computational Complexity” (Mathematics of Operations Research, 2008). In this paper, von Stengel and Forges develop extensive form correlated equilibrium, an extension of correlated equilibrium (Aumann, 1974) for dynamic games. EFCE is defined as a correlation device that generates a move for each information set at the ex ante stage of a game. This move is recommended to a player only if she reaches this information set. An important difference of this solution concept from dynamic correlated equilibrium is that the correlation device introduced by von Stengel and Forges makes only one randomization over strategies of players before the start of a game. In dynamic correlated equilibrium, however, a randomization over action profiles happens before each stage of a game. So, in EFCE, if a deviation from prescription of mediator happens, and players reach an information set which has a zero probability of being reached in equilibrium, players cannot update their beliefs about deviator and her further behavior. While in DCE, a randomization realization occurs even after deviation, so players can form new beliefs.

The most crucial distinction between two equilibria is in incentive compatibility requirements. As von Stengel and Forges write themselves, extensive form correlated equilibrium “generalizes Nash equilibrium in behavioral strategies”. Indeed, as there is only one randomization, incentive analysis doesn't include subgame perfection. In EFCE, players' best reply strategies are to follow prescriptions as long as others players do. However, this requirement shows that the game itself basically happens at the ex ante stage and that this equilibrium doesn't use reasoning of SPE, since it doesn't account for what happens if players fail to follow their prescriptions.

3. Examples

3.1 Example 1. Public Signals

Consider the following twice repeated game:

Таблица 1. Example 1.

Consider the following three-players twice repeated game:

4.1 Preliminary definitions

A dynamic game with observable actions is a structure:

· I is the set of players

· is the set of actions potentially available to the player i

· is the set of non-terminal histories

· is the set of terminal histories

· is the correspondence that assigns to player i at each non-terminal histories a non-empty subset of available actions

· is the payoff function of player i.

4.2 Dynamic correlated equilibrium with private signals

Definition 1. A system of correlated actions is a function

:

Definition 2. Dynamic correlated equilibrium with private signals is a system of correlated actions , such that for every hH, iI and is a best reply to the belief that:

1. at h, opponents play according to

2. at every such that , the probabilities of action profiles are given by

A system of correlated actions is a function that assigns to each non-terminal history a probability distribution over action profiles conditional on the sequence of previous plays. In other words, this is a randomization device that, at each non-terminal history, generates a set of prescriptions that coordinate actions of players. The randomization conditions on what was played at each history preceding h. So, DCE with private signals is a system of correlated actions such that for every player at every history, if a player follows a prescription from the mediator, he best replies to the belief that other players play actions that may be prescribed by the mediator and that at every history following the given one, the probabilities of action profiles will be drawn from the same equilibrium system of correlated actions. In Example 2, dynamic correlated equilibrium is formed as follows:

.

4.3 Dynamic correlated equilibrium with public signals

Definition 1. A system of actions correlated by public signals is a function

, where

Definition 2. Dynamic correlated equilibrium with public signals is a system of actions correlated by public signals , such that for every and is a best reply to the belief that:

1. at h, opponents play

2. at every such that , the probabilities of action profiles are given by

A system of actions correlated by public signals is a function that assigns to each pair of a history of plays, h, and a history of prescriptions, , a conditional probability distribution over action profiles. This probability distribution conditions on the sequence of previous pairs of histories. The history of prescriptions is a sequence of past realizations of the same collection of conditional probability distributions up to a given history. The probability distribution over action profile conditions on both histories of past actions and prescriptions as it allows the mediator to “detect” the deviator. This is an important issue because at some histories, it is impossible to identify the deviator without knowing an exact realization of probability distribution. For example, consider some repeated game with the following stage game:

Таблица 3. Stage game of some repeated game.

The definition of dynamic correlated equilibrium with private signals seems to be easier as the randomization over action profiles that it uses does not condition on the history of previous prescriptions. There are several reasons for that. Firstly, the signals are private, hence, the players cannot condition their beliefs about the current randomization as they don't observe what was prescribed to other players at preceding stages of the game. It is possible to introduce a Bayesian system of beliefs for every player, though. It will slightly complicate the definition but such a step is planned to be done for the sake of generality.

On the other hand, in dynamic correlated equilibrium with public signals, players posses more information, as they know what is prescribed to other players once they get their own signals. Therefore, players best reply to a deterministic belief.

I believe that both definitions are simpler and to some extent more explicit than the definition given by Myerson. Introduction of the definition that will combine two concepts described above will allow to get rid of a little loss of generality in games with observable actions in comparison with the equilibrium presented in the Myerson's paper.

5. Conclusions and further steps

This paper introduces a new solution concept which explores some important properties of dynamic games. First of all, dynamic correlated equilibrium doesn't require any additional assumptions compared to subgame perfect equilibrium. One can easily check that any subgame perfect equilibrium is also dynamic correlated equilibrium. Hence, this concept expands the set of stable outcomes that can be achieved in a sequential game with observable actions.

Second, dynamic correlated equilibrium allows to define an explicit way of combining the idea of subgame perfection with coordination among action of players. The examples presented in this paper demonstrate that correlation allows to achieve at least weak Pareto improvement in the outcomes of a dynamic game. In Example 2, a credible threat that would help to secure a Pareto-dominant outcome of the game can only be made with the help of the mediator which carries out the coordination among actions of players 2 and 3.

Most importantly, the introduced solution concept demonstrates the role of time dimension in a dynamic game. In Example 1, at the ex ante stage, it is impossible to secure play (U;L) without correlation. Both players have incentives to deviate from this action profile. However, an agreement that includes correlation allows to make a credible threat for both players, since they don't know the realization of randomization until the terminal stage of the game. The fact that this exact realization is unknown at the ex ante stage of the game allows players to reach a better agreement.

As we know from Catonini, “not all subgame perfect equilibria are self-enforcing agreements when players are assumed to do strategic reasoning” (E. Catonini, Self-enforcing agreements and forward induction reasoning, 2017, working paper). Therefore, the next step in my research is to refine the set of dynamic correlated equilibria to take into account forward induction considerations. In particular, credible threats must best reply to potentially profitable deviator's plays following a deviation.

Also, a definition that combines two definitions presented in this paper should be derived. I believe that a definition, which doesn't specify the type of signals used to coordinate actions of players, will help to complete the picture of dynamic correlated equilibrium and to show explicitly the generality of this solution concept.

6. References

1. R. Aumann, Subjectivity and correlation in randomized strategies, Journal of Mathematical Economics 1 (1974), 67-96.

2. E. Catonini, Self-enforcing agreements and forward induction reasoning, (2017) working paper.

3. R.B. Myerson, Multistage games with communication, Econometrica (1986).

4. M. J. Osborne & A. Rubinstein, A Course in Game Theory, The MIT Press, 1994.

5. R. Selten, Reexamination of the perfectness concept for equilibrium points in extensive games, Internat. J. Game Theory 4 (1975), 25-55.

6. B. von Stengel & F. Forges, Extensive Form Correlated Equilibrium: Definition and Computational Complexity, Mathematics of Operations Research (2008).

7. Appendix

7.1 Example 1

7.1.1 Equilibria of the stage game

The stage game in Example 1 has the following equilibria: (M;C), (D;R) and the mixed equilibrium, in which Player 1 plays M with probability 7/8 and D with probability 1/8, and Player 2 plays C with probability 1/8 and R with probability 7/8. In Nash equilibria players get the following payoffs: (M;C) - (4;1); (D;R) - (1;4). The expected payoffs of players in the mixed equilibrium are calculated as follows. Expected payoff of Player 1 is: 7/8*(1/8*4 + 7/8*1/2) + 1/8(1/8*1/2 + 7/8*1) = 15/16; expected payoff of Player 2 is: 1/8*(7/8*1 + 1/8*1/2) + 7/8*(7/8*1/2 + 1/8*4) = 15/16. Expected payoffs of players in mixed equilibrium of the stage game are (15/16;15/16).

7.1.2 Subgame Perfect Equilibria

Using backward induction reasoning, one can find the following SPE paths, formed by repetitions and mixes of the equilibria of the stage game (expected payoffs of players are following paths):

· ((M;C);(M;C)) - (8;2)

· ((M;C);(D;R)) - (5;5)

· ((D;R);(M;C)) - (5;5)

· ((D;R);(D;R)) - (2;8)

· ((M;C);(mixed)) - (79/16;31/16)

· ((mixed);(M;C)) - (79/16;31/16)

· ((D;R);(mixed)) - (31/16;79/16)

· ((mixed);(D;R)) - (31/16;79/16)

· ((mixed);(mixed)) - (30/16;30/16)

As mentioned above, there are also two SPE, which include not playing any equilibria of the stage game at the first stage. In this equilibria, players play (M;L) at the first stage of the game. At the second stage of the game, they play (D;R), following (M;L), and either (M;C) or the mixed equilibrium, following any other play. In this equilibrium, players' payoffs are (8;4). As one can see, in neither of listed above equilibria, none of the players get a payoff exceeding 8.

7.1.3 Proof of payoff threshold

Now the goal is to prove, that in Example 1, none of the players can get a payoff more that 8 without using correlations. First, let us take the view of Player 1. In order to give him a payoff equal to or more than 8, we need to take a few logical steps. First of all, an equilibrium of the stage game (M;C) should be played at the terminal stage following some action profiles played at the first stage, because otherwise Player 1 will not be able to get a payoff of 8 or higher. Since we've checked all the subgame perfect equilibria in pure strategies in the previous section of the Appendix, we can state that our “target equilibrium” should include randomization at the first stage of the game. However, this randomization should not include playing D because it would give Player 1 too low expected payoffs. Hence, at the first stage, Player 1 randomizes between U and M. The next step in the equilibrium build up is to say that on path, action profiles (U;L) and (M;L) should be followed by an equilibrium (M;C), since it is the only way to give Player 1 expected payoff of more that 8. Once we fixed such a path, one can see, that no matter what equilibria would follow action profiles (U;C) and (M;C), action C will always dominate action L for Player 2 at the first stage of the game. This leads us to a conclusion that it is impossible to find a subgame perfect equilibrium that would include playing (M;C) after (U;L) and (M;L). Therefore, there is no SPE in which Player 1 would get a payoff more than 8.

In order to show that Player 2 cannot get a payoff more than 8 in any SPE, one can use similar logic. Players should randomize at the first stage and play some equilibria of the stage game at the terminal stage. This potential equilibrium must include path, at which players play (D;R) after (U;L) and (U;C). Otherwise, Player 2 will not be able to get an expected payoff higher that 8. One can easily check, that if we fix an equilibrium of the stage game (D;R) after (U;L) and (U;C), then for Player 1, U is dominated by M, which means that there is no such equilibrium in which (D;R) will follow (U;L) and (U;C). Hence, Player 2 also cannot get more that 8 in any subgame perfect equilibria.

7.2 Example 1

7.2.1 Equilibria of the stage game

The stage game has one Nash equilibria: (U,R,B). It also has two mixed equilibria. In the first one, Player 1 plays U with probability 1/2 and D with probability 1/2, player 2 plays L with probability 1 and Player 3 plays A with probability 5/8 and B with probability 3/8. In the second mixed equilibrium, Player 1 plays U with probability 1, Player 2 plays L with probability 2/3 and R with probability 1/3, Player 3 plays A and B with equal probabilities. The payoffs of three players if Nash equilibrium is played are: (2,2,2). Expected payoffs of the players if mixed equilibria are played are calculated as follows:

Mixed equilibrium 1: expected payoff of Player 1 is: (-1*(1/2*5/8) + 2*(1/2*5/8) + 5*(1/2*3/8)) = 1.25; expected payoff of Player 2 is: (2*(5/8) + 1*(1/2*3/8) + 3*(1/2*3/8)) = 2; expected payoff of Player 3 is: (2*(1/2*5/8) + 1*(1/2*5/8) + 1*(1/2*3/8) + 2*(1/2*3/8)) = 1.5. Expected payoffs of three players are: (1.25;2;1.5).

Mixed equilibrium 2: expected payoff of Player 1 is: 1/2*((-1)*2/3+ 4*1/3) + 1/2*(5*2/3+ 2*1/3) = 7/3; expected payoff of Player 2 is: 1/2*(2*2/3 + 1*1/3) + 1/2*(1*2/3 + 2*1/3) = 1.5; expected payoff of Player 3 is: 1/2*(2/3*2) + 1/2*(1*2/3 + 2*1/3) = 4/3. Expected payoffs of three players are: (7/3;1.5;4/3).

7.2.2 Subgame Perfect Equilibria

Using backward induction reasoning, one can find the following SPE paths, formed by repetitions and mixes of the equilibria on the stage game (expected payoffs of players are following paths):

· ((U;R;B);(U;R;B)) - (4;4;4)

· ((U;R;B);(M1)) - (3.25;4;3.5)

· ((M1);(U;R;B)) - (3.25;4;3.5)

· ((U;R;B);(M2)) - (13/3:3.5;10/3)

· ((M2);(U;R;B)) - (13/3;3.5;10/3)

· ((M1);(M1)) - (2.5;4;3)

· ((M2);(M2)) - (14/3;3;8/3)

· ((M1);(M2)) - (3.583;3.5;2.83)

· ((M2);(M1)) - (3.583;3.5;2.83)

As one can see, in neither of the listed above equilibria, none of the players get a payoff of 5 or higher.

7.2.3 Proof of payoff threshold

We can see that the only player that can get a payoff more than 5 without using correlation among actions of players is Player 1. An equilibrium, in which Player 1 could get a payoff more that 5, should includea path in which at the first stage players play either (U;R;A) or (U;L;B) with some probabilities. However, no matter which equilibria of the stage game are played after these action profiles, players 2 and 3 will always have incentives to deviate from such a path. For example, if players 1 and 3 agree on equilibrium in which they play U and A respectively at the first stage, L will dominate R for Player 2 no matter which equilibria of the stage game are played at the terminal stage. Similarly, if players 1 and 2 agree on some equilibrium that would include playing U and L respectively at the first stage, A will always dominate B for player 3. So, there are no subgame perfect equilibria which would include playing (U;R;A) and (U;L;B) at the first stage of the game. Therefore, there are no subgame perfect equilibria in which at least one player would get a payoff of 5 or higher.

Размещено на Allbest.ru