7.6 Reasoning about Knowledge and Probability

7.6 Reasoning about Knowledge and Probability

Although up to now I have considered modalities in isolation, it is often of interest to reason about combinations of modalities. For example, in (interpreted) systems, where time is represented explicitly, it is often useful to reason about both knowledge and time. In probabilistic interpreted systems, it is useful to reason about knowledge, probability, and time. In Chapter 8, I consider reasoning about knowledge and belief and about probability and counterfactuals.

In all these cases, there is no difficulty getting an appropriate syntax and semantics. The interest typically lies in the interaction between the accessibility relations for the various modalities. In this section, I focus on one type of multimodal reasoning—reasoning about knowledge and probability, with the intention of characterizing the properties CONS, SDP, UNIF, and CP considered in Chapter 6.

Constructing the syntax for a combined logic of knowledge and probability is straightforward. Let ^KQU_n be the result of combining the syntaxes of ^K_n and ^QU_n in the obvious way. ^KQU_n allows statements such as K₁(ℓ₂(Φ) = 1/3)—agent 1 knows that, according to agent 2, the probability of φ is 1/3. It also has facilities for asserting uncertainty regarding probability. For example,

says that agent 1 knows that the probability of φ is either 1/2 or 2/3, but he does not know which. It may seem unnecessary to have subscripts on both K and ℓ here. Would it not be possible to get rid of the subscript in ℓ, and write something like K₁(ℓ(Φ) = 1/2)? Doing this results in a significant loss of expressive power. For example, it seems perfectly reasonable for a formula such as K₁(ℓ₁(Φ) = 1/2) ∧ K₂(ℓ₂(Φ) = 2/3) to hold. Because of differences in information, agents 1 and 2 assign different (subjective) probabilities to φ. Replacing ℓ₁ and ℓ₂ by ℓ would result in a formula that is inconsistent with the Knowledge Axiom (K2).

The semantics of ^KQU_n can be given using epistemic probability structures, formed by adding an interpretation to an epistemic probability frame. Let ^K,prob_n consist of all epistemic probability structures for n agents, and let ^K,meas_n consist of all the epistemic probability structures for n agents where all sets are measurable. Let AX^{k, prob}_n consist of the axioms and inference rules of S5_n for knowledge together with the axioms and inference rules of AX^prob_n for probability. Let AX^{K, bel}_n consist of the axioms and consist of the axioms and inference rules of S5_n and AX^bel_n

Theorem 7.6.1

AX^{K, prob}_n (resp., AX^{K, bel}_n) is a sound and complete axiomatization with respect to ^K,meas_n (resp., ^K,prob_n for the language ^KQU_n.

Proof Soundness is immediate from the soundness of S5_n and AX^prob_n; completeness is beyond the scope of the book.

Now what happens in the presence of conditions like CONS or SDP? There are axioms that characterize each of CONS, SDP, and UNIF. Recall from Section 7.3 that an i-likelihood formula is one of the form a₁ℓ(Φ₁) + … + a_kℓ_i(Φ_k) ≥ b. That is, it is a formula where the outermost likelihood terms involve only agent i. Consider the following three axioms:

• KP1. K_iφ ⇒ (ℓ_i(Φ) = 1).

• KP2. φ ⇒ K_iφ if φ is an i-likelihood formula.

• KP3. φ ⇒ (ℓ_i(Φ) = 1) if φ is an i-likelihood formula or the negation of an i-likelihood formula.

In a precise sense, KP1 captures CONS, KP2 captures SDP, and KP3 captures UNIF. KP1 essentially says that the set of worlds that agent i considers possible has probability 1 (according to agent i). It is easy to see that KP1 is sound in structures satisfying CONS. Since SDP says that agent i knows his probability space (in that it is the same for all worlds in K_i(w)), it is easy to see that SDP implies that in a given world, agent i knows all i-likelihood formulas that are true in that world. Thus, KP2 is sound in structures satisfying SDP. Finally, since a given i-likelihood formula has the same truth value at all worlds where agent i's probability assignment is the same, the soundness of KP3 in structures satisfying UNIF is easy to verify.

As stated, KP3 applies to both i-likelihood formulas and their negations, while KP2 as stated applies to only i-likelihood formulas. It is straightforward to show, using the axioms of S5_n, that KP2 also applies to negated i-likelihood formulas (Exercise 7.19). With this observation, it is almost immediate that KP1 and KP2 together imply KP3, which is reasonable since CONS and SDP together imply UNIF (Exercise 7.20).

The next theorem makes the correspondence between various properties and axioms precise.

Theorem 7.6.2

Let 풜 be a subset of {CONS, SDP, UNIF} and let A be the corresponding subset of {KP1,KP2,KP3}. Then AX^{K, prob}_n ∪ A (resp., AX^{K, bel}_n ∪ A) is a sound and complete axiomatization for the language ^KQU_n with respect to structures in ^K,meas_n (resp., ^K,prob_n) satisfying 풜.

Proof As usual, soundness is straightforward (Exercise 7.21) and completeness is beyond the scope of this book.

Despite the fact that CP puts some nontrivial constraints on structures, it turns out that CP adds no new properties in the language ^KQU_n beyond those already implied by CONS and SDP.

Theorem 7.6.3

AX^{K, prob}_n ∪{KP 1, KP 2} is a sound and complete axiomatization for the language ^KQU_n with respect to structures in ^K,meas_n satisfying CP.

Although CP does not lead to any new axioms in the language ^KQU_n, things change significantly if common knowledge is added to the language. Common knowledge of φ holds if everyone knows φ, everyone knows that everyone knows φ, everyone knows that everyone knows that everyone knows, and so on. It is straightforward to extend the logic of knowledge introduced in Section 7.2 to capture common knowledge. Add the modal operator C (for common knowledge) to the language ^KQU_n to get the language ^KQUC_n. Let E¹φ be an abbreviation for K₁φ ∧ … ∧ K_nφ, and let E^m+1φ be an abbreviation E¹(E^mΦ). Thus, EΦ is true if all the agents in {1, …, n} know φ, while E³φ, for example, is true if everyone knows that everyone knows that everyone knows φ. Given a structure M ∊ ^K,prob_n, define

In the language ^KQUC_n, CP does result in interesting new axioms. In particular, in the presence of CP, agents cannot disagree on the expected value of random variables. For example, if Alice and Bob have a common prior, then it cannot be common knowledge that the expected value of a random variable X is 1/2 according to Alice and 2/3 according to Bob (Exercise 7.22). On the other hand, without a common prior, this can easily happen. For a simple example, suppose that there are two possible worlds, w₁ and w₂, and it is common knowledge that Alice assigns them equal probability while Bob assigns probability 2/3 to w₁ and 1/3 to w₂. (Such an assignment of probabilities is easily seen to be impossible with a common prior.) If X is the random variable such that X(w₁) = 1 and X(w₂) = 0, then it is common knowledge that the expected value of X is 1/2 according to Alice and 2/3 according to Bob.

The fact that two agents cannot disagree on the expected value of a random variable can essentially be expressed in the language ^KQUC₂. Consider the following axiom:

CP₂. If φ₁, …, φ_m are pairwise mutually exclusive formulas (i.e., if (Φ_i ∧ φ_j) is an instance of a propositional tautology for i ≠ j), then

Notice that a₁ℓ₁(Φ₁) + … + a_mℓ₁(Φ_m) is the expected value according to agent 1 of a random variable that takes on the value a_i in the worlds where φ_i is true, while a₁ℓ₂(Φ₁) + … + a_mℓ₂(Φ_m) is the expected value of the same random variable according to agent 2. Thus, CP₂ says that it cannot be common knowledge that the expected value of this random variable according to agent 1 is positive while the expected value according to agent 2 is negative.

It can be shown that CP₂ is valid in structures in ^K,meas_n satisfying CP; moreover, there is a natural generalization CP_n that is valid in structures ^K,meas_n satisfying CP (Exercise 7.23). It is worth noting that the validity depends on the assumption that μ_W (C(w)) > 0 for all w ∊ W ; that is, the prior probability of the set of worlds reachable from any given world is positive. To see why, consider an arbitrary structure M = (W, …). Now construct a new structure M′ by adding one more world w^* such that 풦_i(w*) = {w*} for i = 1, …, n. It is easy to see that C(w^*) ={w^*}, and for each world w ∊ W, the set of worlds reachable from w in M is the same as the set of worlds reachable from w in M′. Without the requirement that C(w) must have positive prior probability, then it is possible that, in M′, all the worlds in W have probability 0. But then CP can hold in M′, although μ_{w, i} can be arbitrary for each w ∊ W and agent i; CP₂ need not hold in this case (Exercise 7.24).

What about completeness? It turns out that CP_n (together with standard axioms for reasoning about knowledge and common knowledge) is still not quite enough to get completeness. A slight strengthening of CP_n is needed, although the details are beyond the scope of this book.