7.8 Reasoning about Expectation

The basic ingredients for reasoning about expectation are quite similar to those for reasoning about likelihood. The syntax and semantics follow similar lines, and using the characterizations of expectation functions from Chapter 5, it is possible to get elegant complete axiomatizations.

7.8.1 Syntax and Semantics

What is a reasonable logic for reasoning about expectation? Note that, given a simple probability structure M = (W, , μ, π), a formula φ can be viewed as a gamble on W, which is 1 in worlds where φ is true and 0 in other worlds. That is, φ can be identified with the indicator function X_{[[φ]]_M}. A linear propositional gamble of the form a₁φ₁ + … + a_nφ_n can then also be viewed as a random variable in the obvious way. Moreover, if W is finite and every basic measurable set in is of the form [[φ]]_M for some formula φ, then every gamble on W is equivalent to one of the form a₁φ₁ + … + a_mφ_m. These observations motivate the definition of the language ^E_n for reasoning about expectation. ^E_n (Φ) is much like ^QU_n, except that instead of likelihood terms ℓ_i(Φ), it has expectation terms of the form e_i(γ), where γ is a linear propositional gamble. Formally, ^E_n (Φ) is the result of starting off with Φ and closing off under conjunction, negation, and basic expectation formulas of the form

where γ₁, …, γ_k are linear propositional gambles, and b₁, …, b_k, c are real numbers.

A formula such as e_i(a₁φ₁ + … + a_mφ_m) > c is interpreted as saying that the expectation (according to agent i) of the gamble a₁φ₁ + … + a_mφ_m is at least c. More precisely, given a propositional linear gamble γ = a₁φ₁ + … + a_kφ_k and a structure M, there is an obvious random variable associated with γ, namely, X^M_γ = a₁X_{[[φ₁]]_M} + … + a_mX_{[[φ_n]]_M}. Then e_i(γ) is interpreted in structure M as the expectation of X^M_γ. The notion of "expectation" depends, of course, on the representation of uncertainty being considered.

For example, for a probability structure M = (W, 풫₁, …, 풫_n, π) ∊ ^meas_n, not surprisingly,

where μ_{w, i} is the probability measure in 풫_i(w). Linear combinations of expectation terms are dealt with in the obvious way.

Just as in the case of the ℓ_i operator for likelihood, it is also possible to interpret e_i in lower probability structures, belief structures, arbitrary probability structures, and possibility structures. It then becomes lower expectation, expected belief, inner expectation, and expected possibility. I leave the obvious details of the semantics to the reader.

7.8.2 Expressive Power

As long as ν is a measure of uncertainty such that E_ν(X_U) = ν(U) (which is the case for all representations of uncertainty considered in Chapter 5), then ^E_n is at least as expressive as ^QU_n, since the likelihood term ℓ_i(Φ) is equivalent to the expectation term e_i(Φ). More precisely, by replacing each likelihood term ℓ_i(Φ) by the expectation term e_i(Φ), it immediately follows that, for every formula ψ ∊ ^QU_n, there is a formula ψ^T ∊ ^E_n such that, for any structure in ^meas_n, ^prob_n, ^bel_n, or ^poss_n, ψ is equivalent to ψ^T

What about the converse? Given a formula in ^QU_n, is it always possible to find an equivalent formula in ^E_n? That depends on the underlying semantics. It is easy to see that, when interpreted over measurable probability structures, it is. Note that the expectation term e_i(a₁φ₁ + … + a_mφ_m) is equivalent to the likelihood term a₁ℓ_i(Φ₁) + … + a_mℓ_i(Φ_m), when interpreted over (measurable) probability structures. The equivalence holds because E_μ is additive and affinely homogeneous.

Interestingly, ^QU_n continues to be just as expressive as ^E_n when interpreted over belief structures, possibility structures, and general probability structures (where ℓ_i is interpreted as inner measure and e_i is interpreted as inner expectation). The argument is essentially the same in all cases. Given a formula f ∊ ^E_n, (5.12) can be used to give a formula f′ ∊ ^E_n equivalent to f (in structures in ^bel_n, ^prob_n, and ^poss_n) such that e is applied only to propositional formulas in f′ (Exercise 7.25). It is then easy to find a formula f^T ∊ ^QU_n equivalent to f′ with respect to structures in ^bel_n, ^prob_n, and ^poss_n. However, unlike the case of probability, the translation from f to f^T can cause an exponential blowup in the size of the formula.

What about lower expectation/probability? In this case, ^E_n is strictly more expressive than ^QU_n. It is not hard to construct two structures in ^lp_n that agree on all formulas in ^QU_n but disagree on the formula e_i(p + q) > 1/2 (Exercise 7.26). That means that there cannot be a formula in ^QU_n equivalent to e_i(p + q) > 1/2.

The following theorem summarizes this discussion:

Theorem 7.8.1

^E_n and ^QU_n are equivalent in expressive power with respect to ^meas_n, ^prob_n, ^bel_n, and ^poss_n. ^E_n is strictly more expressive than ^QU_n with respect to ^lp_n

7.8.3 Axiomatizations

The fact that ^E_n is no more expressive than ^QU_n in probability structures means that a complete axiomatization for ^E_n can be obtained essentially by translating the axioms in AX^prob_n to ^E_n, as well as by giving axioms that capture the translation. The same is true for expected belief, inner expectation, and expected possibility. However, it is instructive to consider a complete axiomatization for ^E_n with respect to all these structures, using the characterization theorems proved in Chapter 5.

I start with the measurable probabilistic case. Just as in the case of probability, the axiomatization splits into three parts. There are axioms and inference rules for propositional reasoning, for reasoning about inequalities, and for reasoning about expectation. As before, propositional reasoning is captured by Prop and MP, and reasoning about linear inequalities is captured by Ineq. (However, Prop now consists of all instances of propositional tautologies in the language ^E_n; Ineq is similarly relativized to ^E_n.) The interesting new axioms capture reasoning about expectation. Consider the following axioms, where γ₁ and γ₂ represent linear propositional gambles:

EXP1. e_i(γ₁ + γ₂) = e_i(γ₁) + e_i(γ₂).
EXP2. e_i(aΦ) = ae_i(Φ) for a ∊ .
EXP3. e_i(false) = 0.
EXP4. e_i(true) = 1.
EXP5. e_i(γ₁) ≤ e_i(γ₂) if γ₁ ≤ γ₂ is an instance of a valid propositional gamble inequality. (Propositional gamble inequalities are discussed shortly.)

EXP1 is simply additivity of expectations. EXP2, EXP3, and EXP4, in conjunction with additivity, capture affine homogeneity. EXP5 captures monotonicity. A propositional gamble inequality is a formula of the form γ₁ ≤ γ₂, where γ₁ and γ₂ are linear propositional gambles. The inequality is valid if the random variable represented by γ₁ is less than the random variable represented by γ₂ in all structures. Examples of valid propositional gamble inequalities are p = p ∧ q + p ∧ q, φ ≤ φ + ψ, and φ ≤ φ ∨ ψ. As in the case of Ineq, EXP5 can be replaced by a sound and complete axiomatization for Boolean combinations of gamble inequalities, but describing it is beyond the scope of this book.

Let AX^{e, prob}_n consist of the axioms Prop, Ineq, and EXP1–5 and the rule of inference MP.

Theorem 7.8.2

AX^{e, prob}_n is a sound and complete axiomatization with respect to ^meas_n for the language ^E_n.

Again, as for the language ^QU_n, there is no need to add extra axioms to deal with continuity if the probability measures are countably additive.

The characterization of Theorems 5.2.2 suggests a complete axiomatization for lower expectation. Consider the following axioms:

EXP6. e_i(γ₁ + γ₂) ≥ e_i(γ₁) + e_i(γ₂).
EXP7. e_i(aγ + b true) = ae_i(γ) + b, where a, b ∊ , a ≥ 0.
EXP8. e_i(aγ + b false) = ae_i(γ), where a, b ∊ , a ≥ 0.

EXP6 expresses superadditivity. EXP7 and EXP8 capture positive affine homogeneity; without additivity, simpler axioms such as EXP2–4 are insufficient. Monotonicity is captured, as in the case of probability measures, by EXP5. Let AX^{e, lp}_n consist of the axioms Prop, Ineq, EXP5, EXP6, EXP7, and EXP8, together with the inference rule MP.

Theorem 7.8.3

AX^{e, lp}_n is a sound and complete axiomatization with respect to ^lp_n for the language ^E_n.

Although it would seem that Theorem 7.8.3 should follow easily from Proposition 5.2.1, this is, unfortunately, not the case. Of course, it is the case that any expectation function that satisfies the constraints in the formula f and also every instance of EXP6, EXP7, and EXP8 must be a lower expectation, by Theorem 5.2.2. The problem is that, a priori, there are infinitely many relevant instances of the axioms. To get completeness, it is necessary to reduce this to a finite number of instances of these axioms. It turns out that this can be done, although it is surprisingly difficult; see the notes for references.

It is also worth noting that, although ^E_n is a more expressive language than ^QU_n in the case of lower probability/expectation, the axiomatization for ^E_n is much more elegant than the corresponding axiomatization for ^QU_n given in Section 7.4. There is no need for an ugly axiom like QU8. Sometimes having a richer language leads to simpler axioms!

Next, consider reasoning about expected belief. As expected, the axioms capturing expected belief rely on the properties pointed out in Proposition 5.2.7. Dealing with the inclusion-exclusion property (5.11) requires a way to express the max and min of two propositional gambles. Fortunately, given linear propositional gambles γ₁ and γ₂, it is not difficult to construct gambles γ₁ ∨ γ₂ and γ₁ ∧ γ₂ such that, in all structures (Exercise 7.27). With this definition, the following axiom accounts for the property (5.11):

To deal with the comonotonic additivity property (5.12), it seems that comonotonicity must be expressed in the logic. It turns out that it suffices to capture only a restricted form of comonotonicity. Note that if φ₁, …, φ_m are pairwise mutually exclusive, a₁ ≤ … ≤ a_m, and b₁ ≤ … ≤ b_m, γ₁ = a₁φ₁ + … + a_mφ_m, and γ₂ = b₁φ₁ + … + b_mφ_m, then in all structures M, the gambles X^M_γ₁ and X^M_γ₂ are comonotonic (Exercise 7.28). Thus, by (5.12), it follows that E_Bel((X^M_γ₁₊_γ₂) = E_Bel((X^M_γ₁) + E_Bel((X^M_γ₂). The argument that E_Bel satisfies comonotonic additivity sketched in Exercise 5.19 shows that it suffices to consider only gambles of this form. These observations lead to the following axiom:

Let AX^{e, bel}_n consist of the axioms Ineq, EXP5, EXP7, EXP8, EXP9, and EXP10, and the rule of inference MP. As expected, AX^{e, bel}_n is a sound and complete axiomatization with respect to ^prob_n. Perhaps somewhat surprisingly, just as in the case of likelihood, it is also a complete axiomatization with respect to ^prob_n (where e_i is interpreted as inner expectation). Although inner expectation has an extra property over and above expected belief, expressed in Lemma 5.2.13, this extra property is not expressible in the language ^E_n.

Theorem 7.8.4

AX^{e, bel}_n is a sound and complete axiomatization with respect to ^poss_n and ^prob_n for the language ^E_n.

Finally, consider expectation with respect to possibility. The axioms capturing the interpretation of possibilistic expectation E_Poss rely on the properties given in Proposition 5.2.15. The following axiom accounts for the max property (5.13):

Let AX^poss_n consist of the axioms Prop, Ineq, EXP5, EXP7, EXP8, EXP10, and EXP11, and the inference rule MP.

Theorem 7.8.5

AX^poss_n is a sound and complete axiomatization with respect to ^poss_n for ^E_n.