Misplaced Pages

#115884

54-736: DSE may refer to: Economy [ edit ] Dominant strategy equilibrium , an economic term in game theory Stock exchanges [ edit ] Dar es Salaam Stock Exchange Dhaka Stock Exchange , the main Stock Exchange of Dhaka, Bangladesh Damascus Securities Exchange , the main Stock Exchange of Damascus, Syria Government and administration [ edit ] Discover Science & Engineering , an Irish Government initiative Department of Sustainability and Environment in Victoria, Australia Data Services Environment ,

108-494: A {\displaystyle a} publicly announces their knowledge of p , then it becomes common knowledge that they know p (viz. C G K a p {\displaystyle C_{G}K_{a}p} ). If every agent publicly announces their knowledge of p , p becomes common knowledge C G E G p ⇒ C G p {\displaystyle C_{G}E_{G}p\Rightarrow C_{G}p} . The idea of common knowledge

162-484: A ) ( B l x ) {\displaystyle \exists x\!\in \!(G-a)(Bl_{x})} ), will leave on the second dawn. Inductively, it can be reasoned that no one will leave at the first k  − 1 dawns if and only if there are at least k blue-eyed people. Those with blue eyes, seeing k  − 1 blue-eyed people among the others and knowing there must be at least k , will reason that they must have blue eyes and leave. For k  > 1,

216-545: A truth value , in each state, to each primitive proposition in the language. The Kripke semantics for the knowledge operator is given by stipulating that K i φ {\displaystyle K_{i}\varphi } is true at state s iff φ {\displaystyle \varphi } is true at all states t such that ( s , t ) ∈ R i {\displaystyle (s,t)\in R_{i}} . The semantics for

270-424: A Nash equilibrium. The iterated elimination (or deletion, or removal) of dominated strategies (also denominated as IESDS, or IDSDS, or IRSDS) is one common technique for solving games that involves iteratively removing dominated strategies. In the first step, all dominated strategies are removed from the strategy space of each of the players, since no rational player would ever play these strategies. This results in

324-478: A San Francisco running club Science and medicine [ edit ] DSE (gene) , human gene which codes for dermatan-sulfate epimerase Dobutamine Stress Echo, a cardiac stress test Dark septate endophytes , a group of fungi that are symbiotic within vascular plant roots Design space exploration , systematic analysis and pruning of unwanted design points based on parameters of interest Discrete skeleton evolution , an iterative approach to reducing

378-471: A discovery always sleeps until after dawn. On the island, each person knows every other person's eye color, there are no reflective surfaces, and there is no communication of eye color. At some point, an outsider comes to the island, calls together all the people on the island, and makes the following public announcement : "At least one of you has blue eyes". The outsider, furthermore, is known by all to be truthful, and all know that all know this, and so on: it

432-412: A first-order logic incorporating epistemic and temporal operators) or van der Hoek et al. "Alternating Time Epistemic Logic". In his 2007 book, The Stuff of Thought: Language as a Window into Human Nature , Steven Pinker uses the notion of common knowledge to analyze the kind of indirect speech involved in innuendoes. The comedy movie Hot Lead and Cold Feet has an example of a chain of logic that

486-604: A morphological or topological skeleton Computing and electronics [ edit ] Dead Space: Extraction , a 2009 videogame available for the Nintendo Wii and the PlayStation 3 Dick Smith Electronics , an electronics company Other uses [ edit ] Dimokratikos Stratos Elladas , the Greek Civil War Communist army ('Democratic Army of Greece') Dry Sheep Equivalent ,

540-433: A new, smaller game. Some strategies—that were not dominated before—may be dominated in the smaller game. The first step is repeated, creating a new even smaller game, and so on. This process is valid since it is assumed that rationality among players is common knowledge , that is, each player knows that the rest of the players are rational, and each player knows that the rest of the players know that he knows that

594-403: A second blue-eyed person knows that a third blue-eyed person knows that.... (repeat for a total of k  − 1 levels) a k th person has blue eyes, but no one knows that there is a " k th" blue-eyed person with that knowledge, until the outsider makes his statement. The notion of common knowledge therefore has a palpable effect. Knowing that everyone knows does make a difference. When

SECTION 10

#1732765200116

648-522: A second blue-eyed person knows that a third person has blue eyes, but no one knows that there is a third blue-eyed person with that knowledge, until the outsider makes their statement. In general: For k  > 1, it is "( k  − 1)th order" knowledge ( E G k − 1 [ ∃ x ∈ G ( B l x ) ] {\displaystyle E_{G}^{k-1}[\exists x\!\in \!G(Bl_{x})]} ). Each blue-eyed person knows that

702-753: A service of the Defense Information Systems Agency, United States Education [ edit ] Delhi School of Economics Disability Studies in Education Hong Kong Diploma of Secondary Education , an examination after completing secondary education in Hong Kong Sports [ edit ] Dream Stage Entertainment , a Japanese company that promotes MMA and wrestling matches Dolphin South End Running Club ,

756-467: A set of states S . An event E can then be defined as a subset of the set of states S . For each agent i , define a partition on S , P i . This partition represents the state of knowledge of an agent in a state. Intuitively, if two states s 1 and s 2 are elements of the same part of partition of an agent, it means that s 1 and s 2 are indistinguishable to that agent. In general, in state s , agent i knows that one of

810-653: A standard unit frequently used in Australia Combolcha Airport in Ethiopia Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title DSE . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=DSE&oldid=1194408812 " Category : Disambiguation pages Hidden categories: Short description

864-565: 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 " ( E G p {\displaystyle E_{G}p} ) is transmitted to each agent in private, it is still not common knowledge: E G E G p ⇏ C G p {\displaystyle E_{G}E_{G}p\not \Rightarrow C_{G}p} . But, if any agent

918-504: A valuation function such that it yields value true to the primitive proposition p in all and only the states s such that s ∈ E p {\displaystyle s\in E^{p}} , where E p {\displaystyle E^{p}} is the event of the Aumann structure corresponding to the primitive proposition p . It is not difficult to see that

972-415: Is a Nash equilibrium. Suppose both players choose D . Neither player will do any better by unilaterally deviating—if a player switches to playing C, they will still get 0. This satisfies the requirements of a Nash equilibrium. Suppose both players choose C. Neither player will do better by unilaterally deviating—if a player switches to playing D, they will get 0. This also satisfies the requirements of

1026-707: Is a formula of the logical calculus) is read "agent i knows φ {\displaystyle \varphi } ." We can define an operator E G with the intended meaning of "everyone in group G knows" by defining it with the axiom By abbreviating the expression E G E G n − 1 φ {\displaystyle E_{G}E_{G}^{n-1}\varphi } with E G n φ {\displaystyle E_{G}^{n}\varphi } and defining E G 0 φ = φ {\displaystyle E_{G}^{0}\varphi =\varphi } , common knowledge could then be defined with

1080-552: Is a full specification of a player's behavior, describing each action a player would take at every possible decision point. Because information sets represent points in a game where a player must make a decision, a player's strategy describes what that player will do at each information set. Rationality: The assumption that each player acts in a way that is designed to bring about what he or she most prefers given probabilities of various outcomes; von Neumann and Morgenstern showed that if these preferences satisfy certain conditions, this

1134-535: Is collapsed by common knowledge. The Denver Kid tells his allies that Rattlesnake is in town, but that he [the Kid] has “the edge”: “He's here and I know he's here, and he knows I know he's here, but he doesn't know I know he knows I know he's here.” So both protagonists know the main fact (Rattlesnake is here), but it is not “common knowledge”. Note that this is true even if the Kid is wrong: maybe Rattlesnake does know that

SECTION 20

#1732765200116

1188-446: Is common knowledge that he is truthful, and thus it becomes common knowledge that there is at least one islander who has blue eyes ( C G [ ∃ x ∈ G ( B l x ) ] {\displaystyle C_{G}[\exists x\!\in \!G(Bl_{x})]} ). The problem: finding the eventual outcome, assuming all persons on the island are completely logical (every participant's knowledge obeys

1242-413: Is common knowledge, then φ {\displaystyle \varphi } is also common knowledge ( C G E G φ ⇒ C G φ {\displaystyle C_{G}E_{G}\varphi \Rightarrow C_{G}\varphi } ). This syntactic characterization is given semantic content through so-called Kripke structures . A Kripke structure

1296-428: Is different from Wikidata All article disambiguation pages All disambiguation pages Dominant strategy equilibrium A player can compare two strategies, A and B, to determine which one is better. The result of the comparison is one of: This notion can be generalized beyond the comparison of two strategies. Strategy: A complete contingent plan for a player in the game. A complete contingent plan

1350-465: Is given by a set of states (or possible worlds) S , n accessibility relations R 1 , … , R n {\displaystyle R_{1},\dots ,R_{n}} , defined on S × S {\displaystyle S\times S} , intuitively representing what states agent i considers possible from any given state, and a valuation function π {\displaystyle \pi } assigning

1404-694: Is impossible. The concept of common knowledge is central in game theory . For several years it has been thought that the assumption of common knowledge of rationality for the players in the game was fundamental. It turns out (Aumann and Brandenburger 1995) that, in two-player games, common knowledge of rationality is not needed as an epistemic condition for Nash equilibrium strategies . Computer scientists use languages incorporating epistemic logics (and common knowledge) to reason about distributed systems. Such systems can be based on logics more complicated than simple propositional epistemic logic, see Wooldridge Reasoning about Artificial Agents , 2000 (in which he uses

1458-424: Is mathematically equivalent to maximizing a payoff. A straightforward example of maximizing payoff is that of monetary gain, but for the purpose of a game theory analysis, this payoff can take any desired outcome—cash reward, minimization of exertion or discomfort, or promoting justice can all be modeled as amassing an overall “utility” for the player. The assumption of rationality states that players will always act in

1512-491: Is not necessarily "efficient", meaning that there may be non-equilibrium outcomes of the game that would be better for both players. The classic game used to illustrate this is the Prisoner's Dilemma . Strictly dominated strategies cannot be a part of a Nash equilibrium, and as such, it is irrational for any player to play them. On the other hand, weakly dominated strategies may be part of Nash equilibria. For instance, consider

1566-410: 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

1620-567: Is someone with blue eyes, but each blue eyed person does not know that the other blue-eyed person has this same knowledge. For k  = 3, it is "second order" knowledge ( E G E G [ ∃ x ∈ G ( B l x ) ] = E G 2 [ ∃ x ∈ G ( B l x ) ] {\displaystyle E_{G}E_{G}[\exists x\!\in \!G(Bl_{x})]=E_{G}^{2}[\exists x\!\in \!G(Bl_{x})]} ). Each blue-eyed person knows that

1674-598: Is the Aleph-naught . In this way, it is possible to find a formula ψ {\displaystyle \psi } implying E G ( φ ∧ C G φ ) {\displaystyle E_{G}(\varphi \wedge C_{G}\varphi )} from which, in the limit, we can infer common knowledge of φ {\displaystyle \varphi } . From this definition it can be seen that if E G φ {\displaystyle E_{G}\varphi }

DSE - Misplaced Pages Continue

1728-409: Is the set of states where the agent will know that event e obtains. It is a subset of e . Similar to the modal logic formulation above, an operator for the idea that "everyone knows can be defined as e ". E ( e ) = ⋂ i K i ( e ) {\displaystyle E(e)=\bigcap _{i}K_{i}(e)} As with the modal operator, we will iterate

1782-532: Is true at state s iff φ {\displaystyle \varphi } is true at all states t such that ( s , t ) ∈ R G {\displaystyle (s,t)\in R_{G}} . Alternatively (yet equivalently) common knowledge can be formalized using set theory (this was the path taken by the Nobel laureate Robert Aumann in his seminal 1976 paper). Starting with

1836-570: The E function, E 1 ( e ) = E ( e ) {\displaystyle E^{1}(e)=E(e)} and E n + 1 ( e ) = E ( E n ( e ) ) {\displaystyle E^{n+1}(e)=E(E^{n}(e))} . Using this we can then define a common knowledge function, C ( e ) = ⋂ n = 1 ∞ E n ( e ) . {\displaystyle C(e)=\bigcap _{n=1}^{\infty }E^{n}(e).} The equivalence with

1890-405: The axiom schemata for epistemic logic ) and that this too is common knowledge. The answer is that, on the k th dawn after the announcement, all the blue-eyed people will leave the island. The solution can be seen with an inductive argument. If k  = 1 (that is, there is exactly one blue-eyed person), the person will recognize that they alone have blue eyes (by seeing only green eyes in

1944-455: The payoff matrix pictured at the right. Strategy C weakly dominates strategy D. Consider playing C : If one's opponent plays C, one gets 1; if one's opponent plays D, one gets 0. Compare this to D, where one gets 0 regardless. Since in one case, one does better by playing C instead of D and never does worse, C weakly dominates D . Despite this, ⁠ ( D , D ) {\displaystyle (D,D)} ⁠

1998-406: The "equation" C G φ = [ φ ∧ E G ( C G φ ) ] = E G ℵ 0 φ {\displaystyle C_{G}\varphi =[\varphi \wedge E_{G}(C_{G}\varphi )]=E_{G}^{\aleph _{0}}\varphi } . Here, ℵ 0 {\displaystyle \aleph _{0}}

2052-406: The 1976 article. Common knowledge was used by David Lewis in his pioneering game-theoretical account of convention. In this sense, common knowledge is a concept still central for linguists and philosophers of language (see Clark 1996) maintaining a Lewisian, conventionalist account of language. Robert Aumann introduced a set theoretical formulation of common knowledge (theoretically equivalent to

2106-434: 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 " ( E G p {\displaystyle E_{G}p} ) which functions quite similarly to Lewis's and Friedel's 1969 "common knowledge". If

2160-399: The assumption of rationality, into consideration when selecting an action. If a strictly dominant strategy exists for one player in a game, that player will play that strategy in each of the game's Nash equilibria . If both players have a strictly dominant strategy, the game has only one unique Nash equilibrium, referred to as a "dominant strategy equilibrium". However, that Nash equilibrium

2214-401: The axiom There is, however, a complication. The languages of epistemic logic are usually finitary , whereas the axiom above defines common knowledge as an infinite conjunction of formulas, hence not a well-formed formula of the language. To overcome this difficulty, a fixed-point definition of common knowledge can be given. Intuitively, common knowledge is thought of as the fixed point of

DSE - Misplaced Pages Continue

2268-471: The common knowledge accessibility function R G {\displaystyle R_{G}} defined in the previous section corresponds to the finest common coarsening of the partitions P i {\displaystyle P_{i}} for all i ∈ G {\displaystyle i\in G} , which is the finitary characterization of common knowledge also given by Aumann in

2322-443: The common knowledge operator, then, is given by taking, for each group of agents G , the reflexive (modal axiom T ) and transitive closure (modal axiom 4 ) of the R i {\displaystyle R_{i}} , for all agents i in G , call such a relation R G {\displaystyle R_{G}} , and stipulating that C G φ {\displaystyle C_{G}\varphi }

2376-493: The first dawn (and thus that k  > 1; and also that the other blue-eyed person does not think that everyone except themself are not blue-eyed ¬ K a [ ∀ x ∈ ( G − a ) ( ¬ B l x ) ] {\displaystyle \neg K_{a}[\forall x\!\in \!(G-a)(\neg Bl_{x})]} , so another blue-eyed person ∃ x ∈ ( G −

2430-404: The one given above) and proved the so-called agreement theorem through which: if two agents have common prior probability over a certain event, and the posterior probabilities are common knowledge, then such posterior probabilities are equal. A result based on the agreement theorem and proven by Milgrom shows that, given certain conditions on market efficiency and information, speculative trade

2484-548: The others) and leave at the first dawn. If k  = 2, no one will leave at the first dawn, and the inaction (and the implied lack of knowledge for every agent) is observed by everyone, which then becomes common knowledge as well ( C G [ ∀ x ∈ G ( ¬ K x B l x ) ] {\displaystyle C_{G}[\forall x\!\in \!G(\neg K_{x}Bl_{x})]} ). The two blue-eyed people, seeing only one person with blue eyes, and that no one left on

2538-502: The outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge , but instead mutual knowledge . For k  = 2, it is merely "first-order" knowledge ( E G [ ∃ x ∈ G ( B l x ) ] {\displaystyle E_{G}[\exists x\!\in \!G(Bl_{x})]} ). Each blue-eyed person knows that there

2592-420: The outsider's public announcement (a fact already known to all, unless k=1 then the one person with blue eyes would not know until the announcement) becomes common knowledge, the blue-eyed people on this island eventually deduce their status, and leave. In particular: Common knowledge can be given a logical definition in multi-modal logic systems in which the modal operators are interpreted epistemically . At

2646-405: The propositional level, such systems are extensions of propositional logic . The extension consists of the introduction of a group G of agents , and of n modal operators K i (with i = 1, ...,  n ) with the intended meaning that "agent i knows." Thus K i φ {\displaystyle \varphi } (where φ {\displaystyle \varphi }

2700-511: The rest of the players are rational, and so on ad infinitum (see Aumann, 1976). 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 C G p {\displaystyle C_{G}p} . The concept

2754-594: The states in P i ( s ) obtains, but not which one. (Here P i ( s ) denotes the unique element of P i containing s . This model excludes cases in which agents know things that are not true.) A knowledge function K can now be defined in the following way: K i ( e ) = { s ∈ S ∣ P i ( s ) ⊂ e } {\displaystyle K_{i}(e)=\{s\in S\mid P_{i}(s)\subset e\}} That is, K i ( e )

SECTION 50

#1732765200116

2808-411: The syntactic approach sketched above can easily be seen: consider an Aumann structure as the one just defined. We can define a correspondent Kripke structure by taking the same space S , accessibility relations R i {\displaystyle R_{i}} that define the equivalence classes corresponding to the partitions P i {\displaystyle P_{i}} , and

2862-427: The way that best satisfies their ordering from best to worst of various possible outcomes. Common Knowledge : The assumption that each player has knowledge of the game, knows the rules and payoffs associated with each course of action, and realizes that every other player has this same level of understanding. This is the premise that allows a player to make a value judgment on the actions of another player, backed by

2916-444: 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

#115884