Equilibrium in Correlated Strategies

Robert Aumann (2010)

The equilibrium in correlated strategies (also known as the correlated equilibrium concept) is a solution concept developed by the mathematician Robert Aumann , which enables the strategies to be harmonized within the framework of game theory . In contrast to the Nash equilibrium , which allows neither binding contracts nor communication before the decision-making of the players involved and thus the choice of strategy of one player remains unaffected by the choice of strategy of the other player, the equilibrium in correlated strategies enables the strategies to be correlated with one another.

overview

The basic idea allows the consideration of the common randomizations of the players via the strategy set S and the disclosure of the correlated strategies. For illustrative purposes, a public probability mechanism is very often assumed (correlation device), on which the players align their strategy. This can be a simple coin toss, for example. Here correlation device is used strictly in the sense of the public correlation device . In contrast to this, it should be mentioned that, depending on the scientific question, the use of a private correlation device is possible.

Aumann's concept represents a stronger equilibrium concept than that of John Nash . For the players, even in the event that no binding contracts are possible, a higher payout potential results . A Nash equilibrium in mixed strategies can therefore be understood as a stable situation, which implies the randomization of the strategies in an uncorrelated way, i.e. in the statistically independent mode.

Aumann's great merit is that he has broken the rigidity of Nash's concept by demonstrating that a randomization of the players following a common random mechanism and thus the randomization of the strategies in the statistically dependent mode correlates both players can put better. Provided that the participants are willing to agree on a common mechanism for defining the strategy mix, and if under this premise no improvement is possible by resorting to uncorrelated strategies, one speaks of an equilibrium in correlated strategies .

example

The equilibrium in correlated strategies is illustrated using the example of the “ battle of the sexes ” problem .

Model assumptions

The model is initially based on the assumption that both players are participating in a game that is well known to them. Before this begins, both are assigned a signal that the utility units themselves will not change, but that they do, since both players correlate their strategies, i. H. can coordinate the outcome of the game and thus the benefit received by each player.

Crucial to the Aumann concept is the existence of an independent coordinator who assigns each player their strategy. Both players trust this, because in the model they ultimately have the certainty that the proposed strategy is a balance. Thus it is not worthwhile for any player to deviate from the proposed strategy.

model

The well-known game battle of the sexes is represented by a bimatrix :

		woman
		Football (s 21 )	Ballet (s 22 )
man	Football (s 11 )	3/1	0/0
	Ballet (s 12 )	0/0	1/3

The pure Nash equilibria are {soccer, soccer} and {ballet, ballet}. The probability that one of the players is correct in his guess as to which of the above two equilibria is chosen by the other player is low in a world without consultation.

Deviation from this is possible, for example, in an environment in which men dominate women, so that the couple always agree to attend the soccer game; This so-called focus-point effect (focal-point effect) was described by the US economist and Nobel Prize winner Thomas Schelling in his influential book on the social theory Strategy of Conflict (1960) and thus on the influence of environmental and cultural factors pointed to the rational behavior.

Opportunities for modeling strategic uncertainty

Strategic uncertainty exists in a game when neither the possibility is more explicit, i.e. H. verbal or implicit communication , such as is more or less strongly determined by habits in a cultural context, exists. This makes it necessary to resort to alternative solution concepts.

The first possible solution goes back to John Nash and represents the classic consideration of an equilibrium in mixed strategies . In the above bimatrix there is an equilibrium in mixed strategies according to Nash in and , but the expected payout is only 0.75, both for the man as well as for the woman. So everyone gets less than what is possible in the two Nash equilibria when playing pure strategies . ${\displaystyle \textstyle (s_{11},s_{12})=({\frac {3}{4}},{\frac {1}{4}})}$ ${\displaystyle \textstyle (s_{21},s_{22})=({\frac {1}{4}},{\frac {3}{4}})}$

Given the case that the players, in this case the couple, could agree to play one of two Nash equilibria in pure strategies and thus secure an expected benefit of 2 for each, then the agreement would be and indeed also Stable without a binding contract , because neither the man nor the woman would have an incentive to deviate. The communication thus proves to be extremely advantageous and paves the way to the second possible solution, namely the balance in correlated strategies, the core of Aumann's work.

This can be implemented using various mechanisms. On the one hand, the couple can agree in advance to go to a football game when the weather is nice and to the ballet when the weather is bad, or to come back to the coin toss at the beginning, the presence of a trustworthy mediator who both can assume that the proposed Strategy is a balance and advises the couple to head to football and to tally to ballet, i.e. to play or alternatively . ${\displaystyle (s_{11},s_{21})}$ ${\displaystyle (s_{12},s_{22})}$

Since the probability is both heads and tails in the case of a perfect coin , and , before heads or tails have fallen, are equally probable. ${\displaystyle \textstyle {\frac {1}{2}}}$ ${\displaystyle (s_{11},s_{21})}$ ${\displaystyle (s_{12},s_{22})}$

Mathematical representation

Preliminary considerations for private and non-private signals

As already explained in the above sections, the concept of the Nash equilibrium can be used in mixed strategies to model games with non-deterministic player strategies and prescribed probability distributions of these strategies. The Nash equilibrium in mixed strategies can therefore be understood as a stationary situation in which the players make their pure strategies dependent on an external, private and mutually independent signal .

Aumann's work, on the other hand, is based on the premise that there are dependencies between the player signals in correlated equilibria, since these are no longer private. This implies the optimality of the pure strategy of every player once the information of the players is known.

Definitions

The following provides an overview of the mathematical aspects of Aumann's concept. To do this, consider a -player game with the finite (individual) strategies and the payout function (for each player). ${\displaystyle \textstyle N}$ ${\displaystyle \displaystyle (N,S,u)=(\{1,\cdots N\},S_{1}\times \cdots \times S_{N},u_{1}\times \cdots \times u_{N})}$ ${\displaystyle S_{i}}$ ${\displaystyle u}$

Definition of the correlated strategy

First, the definition of a correlated strategy itself is given. The starting point is a probability space . For each individual player one further defines: ${\displaystyle (\Omega ,P)}$

• one as well as a random variable . ${\displaystyle \Omega _{i}}$ ${\displaystyle X_{i}:\Omega \to \Omega _{i}}$
• a function ${\displaystyle {\tilde {k}}_{i}:\Omega _{i}\to S_{i}}$
• a resulting strategy . ${\displaystyle k_{i}={\tilde {k}}_{i}\circ X_{i}\ \to S_{i}}$

One then interprets (where is) as a signal generator that is known to all players. Now an individual player should not see a given signal in full, but only a part intended for him, plus the restrictions on means . With his strategy , each player finally gets a strategy in the original game for a specific signal . ${\displaystyle (\Omega ,P,X)}$ ${\displaystyle X=X_{1}\times \cdots \times X_{N}}$ ${\displaystyle \Omega _{i}}$ ${\displaystyle X_{i}}$ ${\displaystyle k}$ ${\displaystyle s_{i}\in S_{i}}$

The signal generator together with the resulting strategies is then called a correlated strategy.

Formal definition of equilibrium in correlated strategies

A strategic -player game is characterized by the possible actions and the utility function for each player . If the player 's strategy choice meets the underlying game and the following players choose a strategy by the tuple is characterized, then the benefit of the player was with called. A modification of the strategy for each player is represented by the function , consequently the player is able to modify his actions accordingly , i. H. follows the instruction to play . A finite probability space is given , where the set of states and a probability measure is on . ${\displaystyle N}$ ${\displaystyle \displaystyle (N,S_{i},u_{i})}$ ${\displaystyle \displaystyle S_{i}}$ ${\displaystyle u_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle s\in S_{i}}$ ${\displaystyle N-1}$ ${\displaystyle \displaystyle s_{-i}}$ ${\displaystyle i}$ ${\displaystyle \displaystyle u_{i}(s_{i},s_{-i})}$ ${\displaystyle i}$ ${\displaystyle \displaystyle \phi \colon S_{i}\to S_{i}}$ ${\displaystyle i}$ ${\displaystyle \displaystyle \phi }$ ${\displaystyle \displaystyle s_{i}}$ ${\displaystyle \displaystyle \phi (s_{i})}$
${\displaystyle \displaystyle (\Omega ,\pi )}$ ${\displaystyle \displaystyle \Omega }$ ${\displaystyle \displaystyle \pi }$ ${\displaystyle \displaystyle \Omega }$

Furthermore, be for every player ${\displaystyle i}$

• ${\displaystyle \displaystyle P_{i}}$its information partition ,
• the strategy is within the same partition information of the player included ${\displaystyle \displaystyle s_{i}\colon \Omega \rightarrow S_{i}}$ ${\displaystyle i}$
• and the probability distribution. ${\displaystyle \displaystyle q(w)}$

Then represents a correlated equilibrium of a strategic game for each player and for each modification of the strategy , if the following applies: ${\displaystyle \displaystyle ((\Omega ,\pi ),P_{i})}$ ${\displaystyle \displaystyle (N,S_{i},u_{i})}$ ${\displaystyle i}$ ${\displaystyle \phi }$

${\displaystyle \displaystyle \sum _{\omega \in \Omega }q(\omega )u_{i}(s_{i},s_{-i})\geq \sum _{\omega \in \Omega }q(\omega )u_{i}(\phi (s_{i}),s_{-i}).}$

Or to put it more simply: is a correlated equilibrium if no player can change his expected benefit by means of a strategy modification and thus has no incentive to deviate from the proposed strategy in order to return to the original model. ${\displaystyle \displaystyle ((\Omega ,\pi ),P_{i})}$

Relationship between the Nash equilibrium and the equilibrium in correlated strategies

It applies to every Nash equilibrium that it represents a special case of equilibrium in correlated strategies. The specialty lies in the independence of the probabilities in the choice of strategies by different players. The probabilities show no correlation here. So true in a two-player game for 2 players: . ${\displaystyle \displaystyle w(s)=w(s_{1})*w(s_{2})}$

Since pure Nash equilibria in turn produce an equilibrium in correlated strategies through convex combination, their set can be larger than that of the Nash equilibria.

The relationship between the correlated equilibria and Sunspot equilibria from the theory of rational expectations is also worth mentioning .

Efficient Correlated Strategies

Now, in various versions based on the popular Feiglingsspiels (English Chicken Game , below) that an efficient strategy is correlated. The coward game is about two people in two cars racing towards each other. The first to evade this test of courage is considered a coward. However, if neither evades, both die when they collide. First of all, it should be noted that the payout structure in the coward game differs from that of the Battle of Sexes due to the presence of a Pareto-optimal symmetrical payout combination that promises a higher payout amount.

Here the bimatrix:

		Player 2
		Evade (s 21 )	Continue (p 22 )
Player 1	Evade (s 11 )	3/3	1/4
	Continue (p 12 )	4/1	0/0

${\displaystyle (s_{11},s_{22})}$and , the two equilibria in pure strategies, are determined by a random mechanism such as B. the coin toss is chosen with the same probability, namely , but in the chicken game you can achieve the higher Pareto-optimal payout combination (3.3) with a more sophisticated approach, namely: ${\displaystyle (s_{12},s_{21})}$ ${\displaystyle \textstyle {\frac {1}{2}}}$

• Both players know the probabilities for the strategy combinations.
• After the random variable has been realized, each player learns which strategy to play. However, each of the two is uncertain about the other's strategy.

Assume that the probability distribution and is present and player 1 is instructed to choose the strategy . He anticipates that the player 2 with a conditional probability of the strategy selected. Player 1 could diverge on and secure, but playing the strategy results in expected payoff. ${\displaystyle w(s_{11},s_{21})=0{,}2}$ ${\displaystyle w(s_{11},s_{22})=w(s_{12},s_{21})=0{,}4}$ ${\displaystyle s_{11}}$ ${\displaystyle \textstyle {\frac {2}{3}}}$ ${\displaystyle s_{22}}$ ${\displaystyle s_{12}}$ ${\displaystyle \textstyle {\frac {1}{3}}*4+}$ ${\displaystyle \textstyle {\frac {2}{3}}*0=}$ ${\displaystyle \textstyle {\frac {4}{3}}}$ ${\displaystyle s_{11}}$ ${\displaystyle \textstyle {\frac {1}{3}}*3+}$ ${\displaystyle \textstyle {\frac {2}{3}}*1=}$ ${\displaystyle \textstyle {\frac {5}{3}}}$

It is now the case that and . If player 2 now receives the recommendation to evade, he will anticipate that player 1 will also play evasive with a conditional probability . In this case, however, there is absolutely no incentive for player 2 to adhere to the recommendation given by the correlation device. ${\displaystyle w(s_{11},s_{21})=0{,}5}$ ${\displaystyle w(s_{11},s_{22})=w(s_{12},s_{21})=0{,}25}$ ${\displaystyle \textstyle {\frac {2}{3}}}$

From the above you can see that the payouts are maximized if the probability is determined to be high enough by the probability distribution , but at the same time there is no reason for the players to deviate from the specification of the correlation device. Otherwise the correlated strategy is not efficient. ${\displaystyle (s_{11},s_{21})}$

The above example can be summarized in formal mathematical language. Finding efficient correlated strategies is done by maximizing the weighted utility of all players, with the inequality

${\displaystyle \displaystyle \sum _{\omega \in \Omega }q(\omega )u_{i}(s_{i},s_{-i})\geq \sum _{\omega \in \Omega }q(\omega )u_{i}(\phi (s_{i}),s_{-i})}$must be fulfilled. Naturally, it is a simple convex linear optimization problem, since linearity can be determined for both the constraint and the objective function. ${\displaystyle w}$

Application of Aumann's concept of equilibrium to other areas

The concept of equilibrium has found and is still very popular in many other areas of scientific research.

Aumann's preliminary work leads to the Agreement Theorem

Aumann established with his 1976 written theorem inability to agree on the disagreement (english The Agreement theorem ), the interactive knowledge algebra and thus laid the foundation for further research in philosophy, logic, economics and many other fields of science. Using a formal definition of common knowledge, he succeeded in proving that it is not possible for two individuals to agree to disagree, in the following sense:

Let it be the case that the players have a common a priori probability distribution . If, in addition, the a posteriori probabilities for an event E represent common knowledge of both players, then these a posteriori probabilities must also be identical.

Building a bridge to Bayesian rational behavior

In 1987, Aumann finally succeeded in building a bridge to Bayesian rational behavior through the preliminary work discussed above . A player then acts rationally in the Bayesian sense if his action is optimally given his information. The theorem put forward by Aumann in this context postulates the following:

Consider a game that the players start with the same beliefs , but receive different information in the course of the game. If it common knowledge (English common knowledge group), all players that rational in the sense of Bayes behave, this a correlated equilibrium play the game. In other words: equilibria in correlated strategies are to be viewed as the result of Bayesian rational behavior. Aumann himself postulates in his main theorem of this work: “ If each player is Bayes rational at each state of the world, then the distribution of the action n-tuple s is a correlated equilibrium distribution. ", Which was given a little less formally in German above.

Importance of equilibrium in correlated strategies in situations with information asymmetry

Equilibria in correlated strategies are of particular importance in situations that are associated with moral risk or adverse selection in insurance , for example . Moral hazard is the hidden action (English hidden action due) in the case of adverse selection, especially playing hidden information (English hidden information ,) very good at Lemons problem by George A. Akerlof , represented the supporting role. Both can lead to market failure , since there is non-observability and / or non-contractability of interaction situations.

It should be noted that Aumann relates the concept of the correlated equilibrium mainly to the pure problem of moral risk, while Bayes' concept was initially associated primarily with the problem area of ​​adverse selection. The US Nobel Prize winner Roger B. Myerson brought the two together in the Bayesian incentive-compatible mechanism .

The great importance of Aumann's work lies in the fact that a solution for the incentive tolerance of contracts is offered via the equilibrium in correlated strategies, so that despite the existing information asymmetry, such a design of contracts and the associated incentives are successful, so that it is possible for the Player pays to stick to the agreements. According to Holler / Illing, the search for the incentive-compatible mechanisms is then synonymous with “ determining efficient Bayesian equilibria in correlated strategies. "

“ If there is any direct application of game theory for the practice of capital markets, it is this: The crucial thing about game theory and all economic applications is the incentive system. Incentives are the driving force for all economic activities - worldwide. "

So much for Aumann's statement in an interview carried out in 2011, in which he said that the bailouts created false incentives for the banks, because they “ can win but cannot lose. “The topicality of the financial market crisis, which began to show its visible effects in 2008, shows once again how important game theory and, above all, the understanding of the right incentives is for the global economy. Aumann's concept expanded this understanding even further by contributing an important piece of the puzzle to complete the overall picture.

literature

• Robert Aumann : Subjectivity and Correlation in Randomized Strategies. Elsevier, Journal of Mathematical Economics, Vol. 1, No. 1., The Hebrew University of Jerusalem, Jerusalem, Israel, 1974.
• Manfred J. Holler , Gerhard Illing: Introduction to game theory . 6th, revised edition. Springer Verlag, Berlin and Heidelberg 2006, ISBN 3-540-27880-X .
• John Bone, Michaelis Drouvelis, Indrajit Ray: Avoiding Coordination-Failure using Correlation Devices: Experimental Evidences. Department of Economics, University of Michigan, USA, 2011.
• Robert Aumann: Correlated Equilibrium as an Expression of Bayesian Rationality. Econometrica, Econometric Society, Vol. 55, No. 1, The Hebrew University of Jerusalem, Jerusalem, Israel, 1987.
• Sergiu Hart: Robert Aumann's Game and Economic Theory. Wiley-Blackwell, Scandinavian Journal of Economics, Vol. 108, No. 2, London, England, 2006.
• Roger Myerson: Learning from Schelling's strategy of conflict. Department of Economics, University of Chicago, USA, 2009.
• Martin J. Osborne, Ariel Rubinstein : A Course in Game Theory . MIT Press, London, England 1994.
• Sandip Sen, Stephane Airiau, Rajatish Mukherjee: Towards a Pareto-optimal Solution in General-Sum Games. Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, Melbourne, Australia, 2003.
• Robert Aumann: Agreeing to disagree. Annals of Statistics Vol. 4, No. 1, Institute of Mathematical Statistics, Beachwood, USA, 1976.
• Roger Guesnerie, Pierre Picard, Patrick Rey: Adverse selection and moral hazard with risk-neutral agents. Elsevier, European Economic Review, Vol. 33, No. 4, Département d'Économie (Economics Department), École Polytechnique, Palaiseau, France, 1989.
• Robert S. Pindyck, Daniel L. Rubinfeld: Microeconomics . 7th, updated edition. Pearson Education, Munich [u. a.] 2009, ISBN 978-3-8273-7282-6 .
• Roger B. Myerson: Multistage Games with Communication. Econometrica, Econometric Society, Vol. 54, No. 2, Department of Economics, University of Chicago, USA, 1986.
• Institutional Money, FONDS professionell Multimedia GmbH, edition 3/2011, Vienna, Austria, 2011.

Web links

• Professor Rieck's game theory page - entry page for game theory
• Section of Robert Aumann of the Hebrew University of Jerusalem
• Gametheory.net - Nice Java applet for solving normal-form games with the option of preselecting well-known games
• Spieltheorie-Software.de ( Memento from July 18, 2013 in the Internet Archive ) - Java software for the extensive analysis of 2-person games

Individual evidence

1. ↑ ^{a b c} Aumann, Robert: Subjectivity and Correlation in Randomized Strategies. Journal of Mathematical Economics 1, 1974: pp. 67-96.
2. ↑ Holler, Manfred / Illing, Gerhard: Introduction to game theory. 6th, revised edition, Springer Verlag, Berlin and Heidelberg, 2006: pp. 87ff.
3. ↑ Bone, John / Drouvelis, Micaelis / Ray, Indrajit: Avoiding Coordination Failure using Correlation Devices: Experimental Evidences. Department of Economics, University of Michigan, last version September 2011: pp. 1–13. Available at: http://www.isid.ac.in/~pu/conference/dec_11_conf/Papers/IndrajitRay.pdf
4. ^ Aumann, Robert: Correlated Equilibrium as an Expression of Bayesian Rationality. Econometrica , Econometric Society, Vol. 55, No. 1, 1987: pp. 1-6.
5. ↑ Holler, Manfred / Illing, Gerhard: Introduction to game theory. 6th, revised edition, Springer Verlag, Berlin and Heidelberg, 2006: p. 88.
6. ^ Hart, Sergiu: Robert Aumann's Game and Economic Theory . Scandinavian Journal of Economics, Vol. 108, No. 2, July 2006: p. 202.Available at: http://www.ma.huji.ac.il/hart/papers/aumann-n.pdf
7. ^ Myerson, Roger: Learning from Schelling's strategy of conflict . Department of Economics, University of Chicago, last version April 2009: p. 5. Available at: http://home.uchicago.edu/~rmyerson/research/stratofc.pdf
8. ↑ [1] Java applet for solving normal form games
9. ^ Osborne, Martin J. / Rubinstein, Ariel: A Course in Game Theory. MIT Press Books, The MIT Press, edition 1, Vol 1, No. 0262650401, 1994: pp. 31, 32, 38.
10. ^ Osborne, Martin J. / Rubinstein, Ariel: A Course in Game Theory. MIT Press Books, The MIT Press, edition 1, Vol. 1, No. 0262650401, 1994: pp. 39-41.
11. ^ Hart, Sergiu: Robert Aumann's Game and Economic Theory . Scandinavian Journal of Economics, Vol. 108, No. 2, July 2006: pp. 202-204.
12. ^ Osborne, Martin J. / Rubinstein, Ariel: A Course in Game Theory. MIT Press Books, The MIT Press, edition 1, Vol. 1, No. 0262650401, 1994: p. 45.
13. ↑ Holler, Manfred / Illing, Gerhard: Introduction to game theory. 6th, revised edition, Springer Verlag, Berlin and Heidelberg, 2006: p. 89.
14. ↑ Holler / Illing (2006): p. 90.
15. ↑ Sen, Sandip / Airiau, Stephane / Mukherjee, Rajatish: Towards a Pareto-optimal Solution in General-Sum Games , Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, Melbourne, Australia, July 2003: p. 153– 160. Available at: http://dl.acm.org/citation.cfm?id=860600
16. ↑ Holler / Illing (2006): pp. 91, 92.
17. ^ Osborne, Martin J. / Rubinstein, Ariel: A Course in Game Theory. MIT Press Books, The MIT Press, edition 1, Vol. 1, No. 0262650401, 1994: pp. 45-48.
18. ↑ Holler / Illing (2006): p. 93.
19. ↑ Aumann, Robert: Agreeing to disagree. Annals of Statistics Vol. 4, No. 6, 1976: pp. 1236-1239. Available at: http://www.jstor.org/stable/2958591
20. ^ Hart, Sergiu: Robert Aumann's Game and Economic Theory . Scandinavian Journal of Economics, Vol. 108, No. 2, July 2006: p. 205.
21. ^ Aumann, Robert: Correlated Equilibrium as an Expression of Bayesian Rationality. Econometrica , Econometric Society, Vol. 55, No. 1, 1987: pp. 1-18.
22. ^ Aumann, Robert: Correlated Equilibrium as an Expression of Bayesian Rationality. Econometrica , Econometric Society, Vol. 55, No. 1, 1987: p. 7.
23. ↑ Guesnerie, Roger / Picard, Pierre / Rey, Patrick: Adverse selection and moral hazard with risk-neutral agents. European Economic Review, Vol. 33, No. 4, 1989: pp. 807-823. Available at: http://www.sciencedirect.com/science/article/pii/0014292189900275
24. ↑ Pindyck, Robert S. / Rubinfeld, Daniel L.: microeconomics. Pearson Education, 2009: 803.
25. ^ Myerson, B. Roger: Multistage Games with Communication. Econometrica , Econometric Society, Vol. 54, No. March 2, 1986: pp. 323-358. Available at: http://www.jstor.org/sici?sici=0012-9682%28198603%2954%3A2%3C323%3AMGWC%3E2.0.CO%3B2-P
26. ↑ Holler / Illing (2006): p. 94.
27. ^ Institutional Money, 3/2011 edition, interview with Robert Aumann, pp. 42–46.