Common knowledge (logic)

Common knowledge is a special kind of knowledge for a group of agents. There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum. It can be denoted as . The concept was first introduced in the philosophical literature by David Kellogg Lewis in his study Convention (1969). The sociologist Morris Friedell defined common knowledge in a 1969 paper. It was first given a mathematical formulation in a set-theoretical framework by Robert Aumann (1976). Computer scientists grew an interest in the subject of epistemic logic in general – and of common knowledge in particular – starting in the 1980s. There are numerous puzzles based upon the concept which have been extensively investigated by mathematicians such as John Conway. The philosopher Stephen Schiffer, in his 1972 book Meaning, independently developed a notion he called "mutual knowledge" () which functions quite similarly to Lewis's and Friedel's 1969 "common knowledge". If a trustworthy announcement is made in public, then it becomes common knowledge; However, if it is transmitted to each agent in private, it becomes mutual knowledge but not common knowledge. Even if the fact that "every agent in the group knows p" () is transmitted to each agent in private, it is still not common knowledge: . But, if any agent publicly announces their knowledge of p, then it becomes common knowledge that they know p (viz. ). If every agent publicly announces their knowledge of p, p becomes common knowledge . The idea of common knowledge is often introduced by some variant of induction puzzles (e.g. Muddy children puzzle): On an island, there are k people who have blue eyes, and the rest of the people have green eyes. At the start of the puzzle, no one on the island ever knows their own eye color. By rule, if a person on the island ever discovers they have blue eyes, that person must leave the island at dawn; anyone not making such a discovery always sleeps until after dawn.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (2)

Related concepts (11)

Induction puzzles

Induction puzzles are logic puzzles, which are examples of multi-agent reasoning, where the solution evolves along with the principle of induction. A puzzle's scenario always involves multiple players with the same reasoning capability, who go through the same reasoning steps. According to the principle of induction, a solution to the simplest case makes the solution of the next complicated case obvious. Once the simplest case of the induction puzzle is solved, the whole puzzle is solved subsequently.

Epistemic modal logic

Epistemic modal logic is a subfield of modal logic that is concerned with reasoning about knowledge. While epistemology has a long philosophical tradition dating back to Ancient Greece, epistemic logic is a much more recent development with applications in many fields, including philosophy, theoretical computer science, artificial intelligence, economics and linguistics. While philosophers since Aristotle have discussed modal logic, and Medieval philosophers such as Avicenna, Ockham, and Duns Scotus developed many of their observations, it was C.

Strategy (game theory)

In game theory, a player's strategy is any of the options which they choose in a setting where the outcome depends not only on their own actions but on the actions of others. The discipline mainly concerns the action of a player in a game affecting the behavior or actions of other players. Some examples of "games" include chess, bridge, poker, monopoly, diplomacy or battleship. A player's strategy will determine the action which the player will take at any stage of the game.

Performance characterization of Altera and Xilinx 28 nm FPGAs at cryogenic temperatures

Edoardo Charbon, Harald Arjan Robert Homulle

Quantum computers enable a massive speed-up in calculations, thanks to the nature of quantum operations. To unlock quantum computation, a classical system infrastructure is required for the control of qubits and processing of their data. While qubits are g ...

2018

Model Checking Security Protocols: A Multiagent System Approach

Security protocols specify the communication required to achieve security objectives, e.g., data-privacy. Such protocols are used in electronic media: e-commerce, e-banking, e-voting, etc. Formal verification is used to discover protocol-design flaws. In t ...

Imperial College London2011