Reasoning About Knowledge (MIT Press)

Reasoning About Knowledge (MIT Press)

Joseph Y. Halpern

Language: English

Pages: 536

ISBN: 0262562006

Format: PDF / Kindle (mobi) / ePub

Reasoning about knowledge--particularly the knowledge of agents who reason about the world and each other's knowledge--was once the exclusive province of philosophers and puzzle solvers. More recently, this type of reasoning has been shown to play a key role in a surprising number of contexts, from understanding conversations to the analysis of distributed computer algorithms.Reasoning About Knowledge is the first book to provide a general discussion of approaches to reasoning about knowledge and its applications to distributed systems, artificial intelligence, and game theory. It brings eight years of work by the authors into a cohesive framework for understanding and analyzing reasoning about knowledge that is intuitive, mathematically well founded, useful in practice, and widely applicable. The book is almost completely self-contained and should be accessible to readers in a variety of disciplines, including computer science, artificial intelligence, linguistics, philosophy, cognitive science, and game theory. Each chapter includes exercises and bibliographic notes.





















of distributed knowledge were discussed in Chapter 2: D1. D{i} ϕ ⇔ Ki ϕ, i = 1, . . . , n D2. DG ϕ ⇒ DG ϕ if G ⊆ G In addition, the DG operator has all the properties of the knowledge operator. What these are depends on the system we consider. Thus, for example, in all cases A2 applies to DG , so that the following axiom is valid: (DG ϕ ∧ DG (ϕ ⇒ ψ)) ⇒ DG ψ. If in addition we take the Ki relations to be reflexive, so that knowledge satisfies A3, then so does distributed knowledge; that is, we

t, t ∈ S }. Since |F | < |Sub(ϕ)| ≤ |ϕ|, it follows that S ≤ |ϕ|. We now show that for all states s ∈ S and for all subformulas ψ of ϕ (including ϕ itself), (M, s ) |= ψ iff (M , s ) |= ψ. As usual, we proceed by induction on the structure of ψ. The only nontrivial case is when ψ is of the form K1 ψ . Suppose that s ∈ S . If (M, s ) |= K1 ψ , then (M, t) |= ψ for all t ∈ S, so, in particular, (M, t) |= ψ for all t ∈ S . By the induction hypothesis, (M , t) |= ψ for all 3.6 NP -Completeness

this is the first thing the KB will be told. This places a restriction on the set of possible runs, eliminating runs with global states of the form (α, ϕ1 , . . . , ϕk , ·) such that k ≥ 1 and p is true under the truth assignment α, but ϕ1 = p. It is easy to construct other examples of how what information is given or the order in which it is given might impart knowledge beyond the facts themselves. By allowing all runs consistent with KB1 and KB2 in R, we are saying that there is no such

is an abstraction of a situation where players interact by making “moves.” Based on the moves made by the players, there is an outcome, or payoff, to the game. It should be clear that standard games such as poker, chess, and bridge are games in this sense. For example, the “moves” in bridge consist of bidding and playing the cards. There are rules for computing how many points each side gets at the end of a hand of bridge; this is the payoff. The game theorists’ notion of game, however,

includes states such as (σ11 , ), (σ12 , a2 ), (σ21 , a1 , b1 ), etc. Again, all the relevant information in the system is captured by the players’ local states, so we can take the environment’s state to be the constant λ. There are eight initial states, corresponding to all pairs of strategies, so G0 consists of these eight states. The actions of the players 5.2 179 Protocols and Contexts are a1 , a2 , b1 , b2 , and ; the last is the null action and the other actions have the obvious

Download sample