Common knowledge

Common knowledge or common prior knowledge , referred to in English as common knowledge , is a game theory concept about the information structure of players. Accordingly, the knowledge of the players consists in addition to the pure knowledge of a fact or an event also from the knowledge of the individual players about their knowledge of one another. For the analysis of games in the context of game theory, it is important to know what the players have as common knowledge and what is not.

term

definition

Common knowledge is information or events that every player knows and of which everyone also knows that they are known to everyone else, and also that everyone in turn knows that everyone knows that they are known to everyone, etc. The knowledge of the players is nested with each other infinitely. Accordingly, information is common knowledge if

• all players know the information
• all players know that all players know the information
• all players know that all players know that all players know the information

across an infinite number of levels of knowledge.

If the process is only available over a finite number of knowledge levels, it is called bounded knowledge . The difference can play a significant role, especially in subgame-perfect games . The information term bounded knowledge, however, has a far less importance in game theory than common knowledge.

example

This example illustrates the infinite regress required for common knowledge to arise. It is constructed based on the example in Rieck (2007).

Two inmates develop a plan to break out of prison. The prison is surrounded by a high wall with a barbed wire. Since both prisoners cannot overcome the wall alone, they are dependent on their mutual help. You can only successfully implement the escape plan together, the escape of a single person would be pointless. One evening prisoner A decides to put the escape plan into practice the next morning. Both inmates are housed in different cells and cannot communicate directly with each other. Prisoner A therefore decides to throw a piece of paper with the news of the planned outbreak in Prisoner B's cell. Since it is not clear to prisoner A whether prisoner B actually received the message, he asks for confirmation from prisoner B. Without the knowledge that both of them break out together the next morning, prisoner A will not risk an escape. The second prisoner receives the slip of paper and in turn replies by throwing a slip of paper in which he asks for confirmation of the confirmation. He too wants to be sure that both prisoners will break out together and will not dare to break out without this knowledge.

In the context of this example, the information that both prisoners want to break out the next morning can never become common knowledge . In order to make the information into common knowledge, the confirmations of receipt of the message would have to be available over an infinite number of levels. The number is limited here to a finite number of repetitions, so that an outbreak can never occur here. A finite number of steps, as is the case in the example, only leads to the bounded knowledge assumption. Assuming that prisoner A did not receive the confirmation of the confirmation, both would know about the planned outbreak the next day, but the information would not be common knowledge. The two prisoners would not attempt to escape.

history

Robert Aumann 2008

Thomas Schelling first established in 1960 that common knowledge arises from an infinite regress, the actual term common knowledge was first found in 1969 by the philosopher David Kellogg Lewis . However, he gives the term a more holistic meaning than a purely game-theoretical one. The first formal representation is provided by Robert Aumann in Agreeing to disagree (1976). In doing so, the mathematician develops the theorem that players who trust each other cannot, in hindsight, agree on their knowledge of an event, to disagree. In 2005, Aumann and Schelling were awarded the Swedish Reichsbank's Prize for Economics in memory of Alfred Nobel for their achievements in the field of game theory .

Formal representation

In his mathematical formalization, Aumann falls back on the laws of set theory . The following formalization is analogous to his.

A quantity of states is given . Let the event be a subset of . For each player represent a partition of . This partition should represent the level of knowledge of the player in one state. In the state , the player knows that the partition is in one of the sets , but not in which one. here stands for the one-element , which contains. ${\displaystyle S}$ ${\displaystyle e}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle s}$ ${\displaystyle i}$ ${\displaystyle P_{i}(s)}$ ${\displaystyle P_{i}(s)}$ ${\displaystyle P_{i}}$ ${\displaystyle s}$

One can now define a knowledge function as follows: ${\displaystyle K}$

${\displaystyle K_{i}(e)=\{s\in S|P_{i}(s)\subset e\}}$

${\displaystyle K_{i}(e)}$is the state in which the player knows that there is an event . ${\displaystyle i}$ ${\displaystyle e}$

For the case "everyone knows " the following formula can be defined: ${\displaystyle e}$

${\displaystyle E(e)=\bigcap _{i}K_{i}(e)}$

${\displaystyle K_{i}(e)}$applies to all players . ${\displaystyle i}$

The assumptions for the function , , then can be a common knowledge function define: ${\displaystyle E}$ ${\displaystyle E^{1}(e)=E(e)}$ ${\displaystyle E^{n+1}(e)=E(E^{n}(e))}$

${\displaystyle C(e)=\bigcap _{n=1}^{\infty }E^{n}(e)}$

example

The concept of common knowledge is often illustrated with a version of the following story.

In a small country there are people with freckles, the rest of the population have none. Among all residents there is at least one person with freckles . If a person finds they have freckles, they must leave the country that same day. There are no mirrors or other reflective objects in the country in which people could look at themselves. Since there is no talk about freckles either, the residents do not know whether they have freckles themselves or not. At the daily morning gathering of all residents, you can only see the condition of the others. ${\displaystyle k}$ ${\displaystyle (k\geq 1)}$

One day an acquaintance from a neighboring country appears and calls everyone together. He proclaims: "There is at least one of you in this country who has freckles." All residents know that the acquaintance is completely trustworthy and always tells the truth and also know that everyone else on the island knows this, etc .: It is common knowledge that the stranger is telling the truth and so the information that at least one resident has freckles also becomes common knowledge. Furthermore, all residents of the country are completely rational and this is also common knowledge.

The question now arises as to what consequences the announcement of the acquaintance has.

${\displaystyle k=1}$

In the event that only one resident has freckles, the solution is very simple. The resident with the freckles will find that all other residents don't have any and conclude that only he can be the one with freckles. He will leave the country on the first day. ${\displaystyle (k=1)}$

${\displaystyle k=2}$

If so , nobody will leave the country on the first day. The two freckled residents will each recognize the other freckled person in the group and expect him or her to leave the country on the first day. But after neither of them left the country on the first day, both of them will find that the other must have seen someone with freckles too - they themselves. Both residents will then leave the country on the second day. ${\displaystyle k=2}$

${\displaystyle k=3}$

If there are three people with freckles among all residents, they will leave the country on the third day. On the first day, each of the three residents will make out two other people with freckles in the group and expect an identical course as in the case . After this performance, the two residents observed should leave the country on the second day. From the result that no one has left the country after the second day, all three residents will then conclude on the third day in a similar rational process as with that they must also have freckles. ${\displaystyle k=2}$ ${\displaystyle k=2}$

Conclusion

With the statement of the acquaintance, the information “There is at least one of you in this country who has freckles” becomes common knowledge. Knowing that the other residents also know this leads to a new situation and ultimately to the freckled residents leaving the country. This also applies to all cases , although the statement here is actually not a new finding: In these constellations, the residents actually already know that there is at least one person with freckles. ${\displaystyle k\geq 2}$

Significance for game theory

The concept of common knowledge is required in the development of solution concepts for games, especially in the area of non-cooperative game theory , the most important part of game theory, it is of the greatest importance. Non-cooperative games are games in which the players, in contrast to the cooperative game theory based on coalitions, cannot make binding agreements. The non-cooperative game theory is a sub-area of microeconomics and mainly deals with the actions and strategies of interacting players who try to maximize their utility in (partial) knowledge of their environment. It is of great importance what knowledge everyone here has. In almost all cases of non-cooperative game theory, common knowledge is included in the analysis as a basic assumption or prior knowledge. It is generally assumed that the rules of the game are always common knowledge. The rules of the game determine the exact course of a game. Furthermore, they also contain information about the payouts, the information areas , the probabilities of random moves etc. Usually it is also assumed that all players behave rationally and also know that everyone knows that everyone behaves rationally, etc. The rationality of the players is also common knowledge. It is relevant to the description of a game what information the players have at which point in the game. Different information at one decision point can lead to different decisions and payouts by the players. Common knowledge makes it possible to make statements about the information levels of the players.

In the area of ​​complete information

Games with complete information are usually easy to analyze. If, in addition to the common knowledge assumption, the strategy sets S _i and the payout function u _i (s) of all players are also common knowledge, a game with complete information is present by definition . The full information game contains information about the number of players, the strategy and the utility function and can be specified in the form . Players always choose the move that generates the greatest possible benefit for them, and this is known to all other players as well. Due to the complete transparency and the common knowledge assumption regarding the rationality, the players can guess the behavior of the other players in the individual game situations and adjust their own strategy accordingly. When analyzing games with complete information, use is made of the transparency that the common knowledge assumption creates. The solution concepts equilibrium in dominant strategies and Nash equilibrium are implicitly based on this. However, the disadvantage of games with complete information is that no games can be displayed in which some players have more or different information than others. ${\displaystyle \Gamma =(N,S,u)}$

The sub-game perfection developed by Reinhard Selten is a solution concept in which an analysis is determined by determining the Nash equilibria of all existing sub-games of a game by means of backward induction . The principle of the Nash equilibrium is refined in part-game perfection with the aim of eliminating untrustworthy equilibria (equilibria with untrustworthy threats). In principle, solving games with partial game perfection is compatible with the assumption of common knowledge. In some games, however, knots can be justified that could not be achieved by sub-game perfection by assuming that either

• at least one of the players is not rational or
• the rationality of the players is not common knowledge and is only available over a finite number of levels (bounded knowledge).

In the area of ​​incomplete information

In games with incomplete information, in contrast to games with complete information , aspects of game situations that arise from information asymmetries can also be captured . Incomplete information suggests that certain characteristics of a player i the other players are not known. These properties can be, for example, preferences, assumptions about other players or initial equipment. In this context, one speaks of the players' private information . When playing games with incomplete information, the common knowledge assumption is violated, since not all players fully have the rules of the game. For this reason, an alternative solution concept is being developed for games of this type. It is possible to transform a game with incomplete information into a game with complete but imperfect information. As a result of the transformation, the game is well defined and there is no longer any uncertainty about the rules. To imperfect information is when certain actions of players for others are not observable. However, if there is no private information in the game, one speaks of perfect information .

Bayesian games

→ Main article : Bayesian game

A game with incomplete information can also be referred to as a Bayesian game, since the solution concept used here is based on Bayes' theorem . It was developed by Harsanyi . The existing uncertainty in these games regarding the dissimilar information is circumvented by a trick: At the beginning of the game, a random move of nature (called player 0) is introduced, which determines the type of player . This specific type is only known to the player in question . The other players only have ideas about the likelihood that a player belongs to a certain type . These ideas are known as beliefs . By converting the games with incomplete information into games with imperfect information, the common knowledge assumption within the framework of the Bayesian games can be maintained. This makes it possible to solve games of this type. ${\displaystyle t_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle t_{i}}$

literature

• Christian Rieck: Game Theory - An Introduction . Rieck, Eschborn 2007, ISBN 978-3-924043-91-9 .
• Manfred J. Holler, Gerhard Illing: Introduction to game theory . 6th edition. Springer Verlag, Berlin 2005, ISBN 3-540-27880-X .
• Andreas Diekmann: Game theory: introduction, examples, experiments . Rowohlts Enzyklopädie, Reinbek bei Hamburg 2009, ISBN 978-3-499-55701-9 (latest social science introduction to game theory).
• Drew Fudenberg, Jean Tirole: Game Theory . MIT Press, Cambridge / MA 2002, ISBN 0-262-06141-4 (first edition: 1991).
• Aumann, Robert: Agreeing to disagree. Annals of Statistics Vol. 4, No. 6, 1976, pp. 1236-1239. Available at: http://www.jstor.org/stable/2958591
• Robert Gibbons: A Primer in Game Theory . Financial Times, Harlow 1992, ISBN 0-7450-1159-4 .
• Herbert Gintis: Game theory evolving . Princeton Univ. Press, Princeton 2000, ISBN 0-691-00943-0 .
• Dariusz Jemielniak: Common Knowledge? An Ethnography of Wikipedia . Stanford University Press, Stanford, CA 2014, ISBN 978-0-8047-8944-8 .

Web links

• wikiludia - Alternative presentation of common knowledge at the University of Munich
• Professor Rieck's game theory page - entry page for game theory
• Don Ross:  Common Knowledge. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy . - Alternative representation of common knowledge of Stanford Univercity
• Till Grüne-Yanoff:  Game Theory. In: Internet Encyclopedia of Philosophy .
• Gametheory.net

Individual evidence

1. ↑ ^{a b c} Manfred J. Holler, Gerhard Illing: Introduction to game theory . 6th edition. Springer Verlag, Berlin 2005, ISBN 3-540-27880-X , p. 42, 43 .
2. ↑ ^{a b c} Christian Rieck: Game theory - an introduction . Rieck, Eschborn 2007, ISBN 3-924043-91-4 , p. 135-138 .
3. ^ Christian Rieck: Game Theory - An Introduction . Rieck, Eschborn 2007, ISBN 3-924043-91-4 .
4. ^ Sergiu Hart: Robert Aumann's Game and Economic Theory . In: Scandinavian Journal of Economics. Vol. 108, No. 2, July 2006, p. 205.
5. ↑ Aumann, Robert: Agreeing to disagree. Annals of Statistics Vol. 4, No. 6, 1976, pp. 1236-1239. Retrieved from: http://www.jstor.org/stable/2958591
6. ^ Drew Fudenberg, Jean Tirole: Game Theory . MIT Press, Cambridge / MA 2002, ISBN 0-262-06141-4 (first edition: 1991).
7. ^ Herbert Gintis: Game theory evolving . Princeton Univ. Press, Princeton 2000, ISBN 0-691-00943-0 , pp. 53 and 408-409 .
8. ^ Christian Rieck: Game Theory - An Introduction . Rieck, Eschborn 2007, ISBN 978-3-924043-91-9 , pp. 127-130 .
9. ^ Herbert Gintis: Game theory evolving . Princeton Univ. Press, Princeton 2000, ISBN 0-691-00943-0 , pp. 13 .
10. ^ Christian Rieck: Game Theory - An Introduction . Rieck, Eschborn 2007, ISBN 978-3-924043-91-9 , pp. 225-237 .
11. ^ Christian Rieck: Game Theory - An Introduction . Rieck, Eschborn 2007, ISBN 978-3-924043-91-9 , pp. 138-147 .
12. ↑ Manfred J. Holler, Gerhard Illing: Introduction to game theory . 6th edition. Springer Verlag, Berlin 2005, ISBN 3-540-27880-X , p. 45-49 .