A Savage-style Utility Theory for Belief Functions

1 Introduction

The problem of decision making under uncertainty is a fundamental issue for Artificial Intelligence. In this problem the decision maker (DM) is concerned with the selection of an appropriate decision alternative, in the face of uncertainty with respect to the environment. The uncertainty manifests itself in that a different payoff is obtained for different states of nature. Characterizing the behavior of DM using subjective expected utility was promoted and axiomatized by Savage [Savage, 1954] following previous work in [de Finetti, 1937] and [von Neumann and Morgenstern, 1944]. The theory of subjective expected utility combines two subjective concepts: first, a personal utility function (a measure of preferences over outcomes or consequences), and second a subjective probability distribution quantifying likelihood judgements about events. Different DMs may make different decisions because they may have different utility functions or different beliefs about the probabilities of different outcomes. Despite its achievements in economics and AI, experiments have shown that many DMs do not behave in a manner consistent with Savage's axioms of subjective expected utility for probability functions [Ellsberg, 1961].

∗Correspondence author.

In many uncertain situations, the Dempster-Shafer belief structure provides a more suitable representation framework a DMmay face in regards to the state of nature [Jaffray, 1989; Strat, 1990; Smets and Kennes, 1994; Ghirardato, 2001; Yager, 2008; Giang and Shenoy, 2003; Smets, 2005; Gul and Pesendorfer, 2014; Shafer, 2016; Giang, 2016; Ma et al., 2017]. Here we provide an axiomatic justification of decision making with belief functions by showing the counterpart of Savage's theorem. Among those semantics for belief functions in the literature, we choose Shafer's interpretation as allocations of probability [Shafer, 1979] or Fagin and Halpern's view of subjective belief functions as generalized probability [Fagin and Halpern, 1991], i.e., inner probability.

Our main contribution in this paper is to propose six axioms for a preference relation over acts, which are represented by functions from the state space S to the consequence set Z, and prove the Savage-style representation theorem (Theorem 3.12). The theorem shows that the axioms are equivalent to the existence of an interval utility function and a belief function (inner probability), such that decisions are being made as if to maximize the expectation of the utility relative to the belief function. Since finite domains are arguably those of most interest in AI applications, we assume that the state space is finite. The first part of our system consists of four axioms (Axioms 1-4), which are adapted directly from those for expected uncertain utility (EUU) theory in [Gul and Pesendorfer, 2014]. The most important concept in this part is called ideal events. They are intended to capture aspects of the uncertainty that the DM can quantify without difficulty. The Savage sure-thing principle does not hold generally for any events, but for ideal events. We show that Axiom 3 induces a preference relation on ideal events called a qualitative probability, and further derives a preference relation on general events called a qualitative belief function. Although a qualitative probability does not imply the existence of a (quantitative) probability function on the state space, a qualitative belief function guarantees the existence of a quantitative belief function [Wong et al., 1991].

The key axioms in our theory are the last two: uniformity (Axiom 5) and independence (Axiom 6). Axiom 5 implies that all acts with the same maximal and minimal consequences must be equivalent (Lemma 3.9). It formalizes the principle of choice under complete ignorance derived in [Arrow and Hurwicz, 1972; Jaffray and Wakker, 1994]. By using a technique called ideal splitting (Def. 3.8), we prove the neutrality theorem (Theorem 3.10) which says that two acts are equivalent whenever they generate the same belief functions on the consequences. This axiom also applies to infinite domains. It derives a similar Axiom 3 in [Gul and Pesendorfer, 2014] (Lemma 3.7) where the diffuse sets must be infinite, and hence is more general. Since Axiom 5 (Archimedean) in [Gul and Pesendorfer, 2014] rules out the possibility of a finite state space, we replace it with our independence axiom about acts here. This independence axiom is introduced to ensure the conditions for the mixture space theorem [Herstein and Milnor, 1953] and hence guarantees the existence of a linear function on acts as well as the uniqueness of the quantitative belief function on the state space. By using ideal splitting, we separate this linear function into an interval utility function and a belief function on consequences and show the representation theorem.

2 Belief Functions

Let Ω be a frame of discernment and 2Ω be the powerset of Ω. A mass assignment (or mass function) is a mapping m : 2Ω → [0, 1] satisfying ∑A∈2Ω m(A) = 1. A mass function m is called normal if m(∅) = 0. Without further notice, all mass functions in this paper are assumed to be normal. A set A is called focal if m(A) > 0. A belief function is a function bel : 2Ω → [0, 1] satisfying the following conditions: bel(∅) = 0, bel(Ω) = 1; and bel(⋃ni=1 Ai) ≥ ∑∅̸=I⊆{1,··· ,n} (-1)|I|+1 bel(∩i∈IAi) where Ai ∈ 2Ω for all i ∈ {1, · · · , n}. A mapping f : 2Ω → [0, 1] is a belief function if and only if its M¨obius transform is a mass assignment [Shafer, 1976]. In other words, if m : 2Ω → [0, 1] is a mass assignment, then it determines a belief function bel : 2Ω → [0, 1] as follows: bel(A) = ∑B⊆A m(B) for all A ∈ 2Ω. Moreover, given a belief function bel, we can obtain its corresponding mass function m as follows: m(A) = ∑B⊆A(-1)|A\B| bel(B) for all A ∈ 2Ω. Intuitively, for a subset (or event) A, m(A) measures the belief that the DM commits exactly to A, not the total belief bel(A) that he commits to A. The corresponding plausibility function pl : 2Ω → [0, 1] is dual to bel in the sense that pl(A) = 1 - bel(A) for all A ⊆ Ω. Suppose that Θ is a finer frame than Ω. This means that the elements ω1, · · · , ω|Ω| of Ω correspond to a partition Π1, · · · ,Π|Ω| of Θ: a subset {ωi1 , · · · ωik } of Ω has the same meaning as the subset Πi1 ∪ · · · ∪Πik of Θ. This identification can represented by a mapping ρ : 2Ω → 2Θ such that ρ({ωi}) = Πi(1 ≤ i ≤ |Ω|) and ρ({ωi1 , · · · ωik }) = ∪kj=1ρ(ωij ) = ∪kj=1Πij . The partition Π1, · · · ,Π|Ω| of Θ as a basis defines a subalgebra Aρ of 2Θ as a Boolean algebra with set operations, which is isomorphic to the set algebra 2Ω. We call Θ a refinement of Ω and Ω a coarsening of Θ. Given a belief function bel over Θ

with the refining mapping ρ : 2Ω → 2Θ, its marginal bel ↾Ω over Ω is defined as follows: (bel ↾Ω)({ωi1 , · · · , ωik }) = bel(Πi1 ∪ · · · ∪ Πik ).

A probability space 〈S,A, pr〉 consists of a set S (called the sample space), a σ-algebra A of subsets of S and a probability measure pr : A → [0, 1]. The inner probability pr∗ associated with pr is defined as pr∗(A) = sup{pr(E) : E ⊆ A,E ∈ A} for any A ⊆ S. Without further notice, we assume that the space is finite in this paper.

Proposition 2.1 (Proposition 3.1 and Corollary 3.6 in [Fagin and Halpern, 1991])Belief functions and inner probabilities are equivalent in the following sense:

1. If 〈S,A, pr〉 is a probability space, then pr∗ is a belief function on S;
2. Given a belief function bel on a finite set S, there is a probability space 〈S′ ,A, pr〉 and a surjection f : S′ → S such that for each A ⊆ S, bel(A) = pr∗(f -1 (A)).

This proposition contains Shafer's interpretation of belief functions as allocations of probability [Shafer, 1979]: for each A ⊆ S, ρ : 2S → A defined as ρ(A) being the largest element of A contained in f -1 (A) is an allocation mapping. These semantics are related to but different from the multi-valued-mapping semantics and the coherentlower-probability interpretation (See Section 6 in [Fagin and Halpern, 1991]).

3 Representation Theorem

In this section, we first set up the background for decisionmaking and propose 6 axioms for the preference relations over acts. Next we prove the Savage-style representation theorem.

3.1 Decision-theoretic Setup and Axioms

There is a set of items X, and the DM is willing to express his preferences among these items by making paired comparisons of the form: "I strictly prefer x to y" which is written x ≻X y. A binary relation on X is called a preference relation if it is asymmetric, i.e., x ≻X y implies not y ≻X x and negatively transitive, i.e., if not x ≻X y and not y ≻X z, then not x ≻X z. With the strict preference relation ≻X, we define two other binary relations: x ≽X y if y ̸≻X x, and x ∼X y if x ≽X y and y ≽X x. The first is called weak preference relation and the second indifference relation. If ≻X is a preference relation on X, then (1) ≻X is transitive; (2) for all x and y in X, exactly one of x ≻X y, y ≻X x and x ∼X y holds; (3) ≽X is complete and transitive; (4) ∼X is reflexive, symmetric and transitive; and x ≽X y iff x ≻X y or x ∼X y. In the following, we drop the subscripts X whenever the context is clear.

Just as in Savage's theorem for probability functions, uncertainty is viewed as being subjective in our Savage-style models and belief functions will be supplied by a decision maker (DM) on the basis of his subjective preferences. Our model includes two primitive concepts:

• a finite set of states of nature denoted by S = {s1, · · · , sK} with typical element denoted by s.

• a set of outcomes or consequences, denoted by Z. Following [Gul and Pesendorfer, 2014], we assume that Z = [l,M] ⊆ R where l < M. For technical reasons, we assume that l = 0 in this paper.

From S and Z, we construct the choice space, which is denoted by F, as the set of all functions from S to Z. Formally, we would write F = Z S = {f : f is a function from S to Z}. Elements of F are called acts. For any property P, let {P} denote the set of all states where P holds. For example, {f > g} = {s ∈ S : f(s) > g(s)}. For {P} = S, we simply write P; that is, f ∈ [x, y] means {s ∈ S : f(s) ∈ [x, y]} = S. We identify z ∈ Z with the constant act f = z. In other words, z ∈ Z is also understood as z(s) = z for all s ∈ S. The DM cannot fully specify the consequences that ensue from the action chosen. Instead, his choice of action sets up a function f from states of nature to the consequences-he chooses one such action from some set of available actions, and his preferences over actions are modeled by a binary relation ≻ (⊆ F × F) defined on F. First we describe axioms and explain the basic logic behind whenever necessary.

• AXIOM 1 (Weak order): The binary relation ≻ is a preference relation.
• AXIOM 2 (Dominance): For any two acts f and g ∈ F, if f > g, then f ≻ g.

For any f, g ∈ F and A ⊆ S, let fAg denote the act that agrees with f on A and with g on Ac , the complement of A. Formally,

The axiom that is most characteristic of subjective probabilities is Savage's sure-thing principle [Savage, 1954]. As pointed out in [Jaffray and Wakker, 1994], the belief-function approach violates this principle. Although the sure thing principle does not hold for all events of S, it does for a smaller set of ideal events.

Definition 3.1 An event E is ideal if, for all acts f, g, h and h′ ∈ F, fEh′ ≽ gEh′ and h′Ef ≽ h′Eg provided that fEh ≽ gEh and hEf ≽ hEg. An event A is null if fAh ∼ gAh for all f, g, h ∈ F. ✁

Let E denote the set of all ideal events and E+ that of ideal events that are not null. So E is the domain where the sure thing principle holds. We wish to measure not only the ranking of outcomes, but also of the events. Specifically, we wish to find out whether DM thinks that event A is more likely than event B. The main hypothesis is that the DM uses elements of E+ to quantify the uncertainty of all events. For any event A, A∗ = ⋃{E ∈ E+ : E ∩ A ̸= ∅} and A∗ = ⋃{E ∈ E+ : E ⊆ A} are called respectively the upper and lower approximations of A w.r.t. E+. Axiom 3 below is Savage's comparative probability axiom (P4) applied to ideal events.

• AXIOM 3 (Comparative Belief): For any x, y, w, z ∈ Z and any ideal events E,E′ ∈ E, if y > x and w > z, then wEz ≽ wE′ z provided that yEx ≽ yE′x.

For any two ideal events E and E′ ∈ E, say that E is preferred to E′ , if, for all x and y from Z such that x ≻ y, xEy ≻ xE′ y. According to Axiom 3, it doesn't matter which x and y are used to define the preference. Axiom 3 imposes a natural requirement that the betting preferences be independent of the specific consequences that define the bets. From Axioms 1-3, we know that the above relation is a preference relation, which is also denoted by ≻. Recall that S = {s1, · · · , sK}. Since Z is a subset of real numbers, we view each act f ∈ F as an element (f(s1), · · · , f(sK)) ∈ RK and hence F as a subset of RK . A subset G of acts is called closed if it is a closed subset of RK in the usual topology induced by the Euclidean metric.

• AXIOM 4 (Continuity): For any act f, both U(f) := {g ∈ F : g ≽ f} and L(f) := {g ∈ F : f ≽ g} are closed.

AXIOM 4 compensates for Savage's (P6) and is needed to ensure the continuity of the von-Neumann-Morgenstern utility index when proving the following Savage-style theorem in a setting with real-valued outcomes.

Proposition 3.2 (Lemmas B1 and B2 in [Gul and Pesendorfer, 2014] ) Assume that the collection F of acts satisfies the above four axioms Axioms 1-4. Let f and g be two acts in F. Then

1. f ≥ g implies f ≽ g;
2. f ≻ g implies f ≻ z ≻ g for some z ∈ Z;
3. if E ∈ E+ and y > x, then yEh ≻ xEh for all h ∈ F;
4. if E ∈ E+ and f ∈ F, there exists a unique cE(f) ∈ Z such that cE(f)Ef ∼ f.
5. The set E of ideal events is a σ-algebra.

E is called an atom if it is an indecomposable ideal event, i.e., E ∈ E and no other nonempty ideal event is contained in E. Let E0 denote the set of atoms in E.

Lemma 3.3 The above defined preference relation on E is a qualitative probability. That is to say, ≻ is a preference relation; E ≽ ∅ for all ideal events E ∈ E; S ≻ ∅, and, if E ∩ (E1 ∪ E2) = ∅, then E1 ≻ E2 iff E1 ∪ E ≻ E2 ∪ E. Moreover,

1. If E1 ∼ E2,E3 ∼ E4 and E1 ∩ E3 = E2 ∩ E4 = ∅, then E1 ∪ E3 ∼ E2 ∪ E4.
2. For any ideal events E1,E2,E3,E4 ∈ E, if E1 ≽ E2, E3 ≻ E4 and E1∩E3 = ∅, then E1∪E3 ≻ E2∪E4.
3. For any ideal events E and E′ , if E ⊇ E′ , then S ≽ E ≽ E′ ≽ ∅.

Proof. The propositions follow from Axioms 1-3. The proof is similar to that in Savage's theory about qualitative probabilities (refer to Proposition 9.12 (Page 133) and Proposition 8.4 (Page 119) of [Kreps, 1988]). QED

Now we extend the preference relation on ideal events to that on general events. An ideal event E ∈ E is called the core of event A if E ⊆ A and E is the largest ideal event contained in A. It is easy to see that, for any event A, its core always exists and is unique because the core is simply the union of all ideal events contained in A. Let A◦ denote the core. Now we express comparative beliefs in terms of cores. For any two events A and B, A is called preferred to B (denoted as A ≻ B) if A◦ is preferred to B◦ .

Lemma 3.4 For any event A, B, C ⊆ S,

1. ≻ is a preference relation,
2. (dominance) A ⊇ B implies A ≽ B,
3. (partial monotonicity) if A ⊇ B and A ∩ C = ∅, then A ≻ B implies A ∪ C ≻ B ∪ C, and
4. (nontriviality) S ≻ ∅.

Proof. Here we mainly prove partial monotonicity (Part 3). All the other parts are straightforward. Assume that A ⊇ B,A ≻ B and A ∩ C = ∅. It follows that A◦ ⊋ B◦ ,A◦ \ B◦ ̸= ∅ and A◦ ≻ B◦ . From Lemma 3.3, we know that A◦ \ B◦ ≻ ∅. Note (B ∪ C)◦ ∩ (A◦ \ B◦ ) = ∅. Since A∪C ⊇ B∪C, (A∪C)◦ ⊇ (B∪C)◦ . In addition, (A∪C)◦ ⊇ (A◦ \B◦ ). So (A∪C)◦ ⊇ [(B∪C)◦ ∪(A◦ \B◦ )] and hence (A∪C)◦ ≽ [(B∪C)◦ ∪(A◦ \B◦ )] (Lemma 3.3). We already know that (A◦ \ B◦ ) ≻ ∅ and (B ∪ C)◦ ∩ (A◦ \ B◦ ) = ∅. It follows from Lemma 3.3 that (B ∪ C)◦ ∪ (A◦ \ B◦ ) ≻ (B∪C)◦ . So we have shown that (A∪C)◦ ≻ (B∪C)◦ and hence (A ∪ C) ≻ (B ∪ C). QED

A binary relation R ⊆ S × S is called a qualitative belief function if it satisfies the four conditions in Lemma 3.4. The following theorem follows directly from Lemma 3.4 and Theorem 4 in [Wong et al., 1991].

Theorem 3.5 (Qualitative Belief Theorem) There exists a belief function Bel : 2S → [0, 1] such that, for any two events A, B ∈ 2S , A ≻ B ⇔ Bel(A) > Bel(B).

Such a belief function Bel is called prior and is not unique. The existence of such a quantitative belief function as Bel is equivalent to the solvability of a group of linear (in)equalities. From the Fourier-Motzkin Lemma, we know that a solution, if it exists, is not unique and hence the quantitative belief function is not unique. We need Axiom 6 to ensure the uniqueness (Theorem 3.12). Note that the belief function Bel ↿E restricted to the σ-algebra E is a probability measure, which is not unique. So Bel is actually an inner probability associated with the probability measure Bel ↿E .

Definition 3.6 Let E be an ideal event in E. An event D is called E-diffuse if it satisfies the following conditions:

1. D ⊆ E;
2. D∩E′ ̸= ∅ andDc∩E′ ̸= ∅ for all E′ such that E′ ∈ E+ and E′ ⊆ E.

Let DE denote the set of all E-diffuse sets. Note that DE may be empty. ✁

• AXIOM 5 (Uniformity): For any x, y ∈ Z,E,E′ ∈ E, D ∈ DE and D′ ∈ DE′ , if (xDy)Ef ∼ cEf and (xD′ y)E′ f ∼ c′E′ f, then c = c′ .

Since E and E′ are ideal, the constant c depends only on x and y. The upper and lower approximations of any E-diffuse D are E and ∅, respectively and hence each E-diffuse event represents a state of complete ignorance regarding E. Axiom 5 formalizes the principle of complete ignorance regarding betting on D.

Lemma 3.7 For any x, y ∈ Z, D ∈ DE and D′ ∈ DE′ ,

1. if E ∼ E′ , then xDy ∼ xD′ y for any x, y ∈ Z.
2. (xDy)Ef ∼ (xD′ y)E′ f.

Proof. This lemma follows from Prop. 3.2 and Axiom 4. QED

Since the consequence set Z ⊆ R, we can define convex combinations of acts. Let f and g be two acts in F. For α ∈ [0, 1], the convex combination αf + (1 - α)g of f and g is defined as: for any s ∈ S, (αf + (1 - α)g)(s) = αf(s) + (1 - α)g(s) ∈ Z.

• AXIOM 6 (Independence): For any α ∈ (0, 1] and any acts f, g, h ∈ F, f ≻ g implies αf + (1 - α)h ≻ αg + (1 - α)h.

It follows that f1 ∼ f2 and g1 ∼ g2 implies αf1+(1-α)g1 ∼ αf2 + (1 - α)g2.

3.2 Representation Theorem

With the prior Bel, for any act h : S → Z, we define an associated belief function Belh on the range R(h) of h. For any A ⊆ R(h),

Since {h-1 (z) : z ∈ R(h)} defines a partition of S, h-1 can be viewed as refining and Belh is the marginal of Bel over R(h). In other words, Belh = Bel ↾R(h). Belh may also be identified with the belief function Bel restricted to the subalgebra generated by the sets {h-1 (z) : z ∈ R(h)} of preimages of h. Now we introduce a technique to qualitatively represent a mass function over outcomes in terms of inner probabilities.

Definition 3.8 (Ideal Splitting) Let E ∈ E,N = {1, · · · , n} and {A1, · · · ,An} is a finite partition of E. The ideal split {EJ : ∅ ̸= J ⊆ N} of {A1, · · · ,An} is inductively defined as follows:

• for all i ∈ N, E{i} := (Ai)◦ ;
• for all J ⊆ N such that J ̸= ∅ and |J| > 1, EJ := (⋃j∈J Aj)◦ \ ⋃∅̸=L⊊J EL.

✁

For any act f with the range {z1, · · · , zn}(z1 < · · · < zn), let {SJ f : ∅ ̸= J ⊆ N} denote the ideal split of the partition {Ai = f -1 (zi) : 1 ≤ i ≤ n} of S. Let D(J,j) f denote SJ f ∩ f -1 (zj) where j ∈ J. Note that, for any nonempty E ⊆ SJ f , f(E) = {zi : i ∈ J} and D(J,j) f ∈ DSJ f . For any A ⊆ S, define

Lemma 3.9 Let |J| > 1, maxJ and minJ be the maximal and minimal numbers in J. f ↿SJ f ∼ c ↿SJ f for some constant c ∈ Z which depends only on zmaxJ and zminJ .

Proof. By Proposition 3.2, f ↿SJ f ∼ c ↿SJ f for some constant c ∈ Z. Since zminJ (⋃j∈J\{minJ} D(J,j) f )zmaxJ ↿SJ f ≤ f ↿SJ f ≤ (zminJ D(J,minJ) f zmaxJ ) ↿SJ f , f ↿SJ f ∼ (zminJ D(J,minJ ) f zmaxJ ) ↿SJ f ∼ c ↿SJ f . From Lemma 3.7, we know that c depends only on zminJ and zmaxJ . QED So we write this c as c(zminJ , zmaxJ ) to emphasize its dependency. Moreover, a similar argument on SJ∪J ′ f shows that, for another J ′ such that ∅ ̸= J ′ ⊆ N, if minJ < minJ ′ and maxJ < maxJ ′ , then c(zminJ , zmaxJ ) < c(zminJ′ , zmaxJ′ ). Now we prove the following important neutrality theorem without Axiom 6.

Theorem 3.10 (Neutrality Theorem) For any two acts f, g ∈ F, if Belf = Belg, then f ∼ g.

Proof. Without loss of generality, we assume that both ranges R(f) = R(g) = {z1, z2}(z1 < z2) and Belf = Belg. This implies that Bel(f -1 (z1)) = Belf(z1) = Belg(z1) = Belg(g-1 (z1)) and Bel(f -1 (z2)) = Belf(z2) = Belg(z2) = Belg(g-1 (z2)). From Theorem 3.5, we know that f -1 (z1) ∼ g-1 (z1) and f -1 (z2) ∼ g-1 (z2). So we need to show that f = z1f -1 (z1)z2 ∼ z1g-1 (z1)z2 = g. Note that it is not necessarily the case that f -1 (z1), g-1 (z1) ∈ E. Let {S{1} f , S{2} f , S{1,2} f } and {S{1} g , S{2} g , S{1,2} g } be the ideal splits of the partitions {f -1 (zi)} and {g-1 (zi)}, respectively. Without loss of generality, we assume that all these ideal events are not null. It immediately follows that S{1} f ∼ S{1} g , S{2} f ∼ S{2} g and S{1,2} f ∼ S{1,2} g . Note that, for any nonempty ideal event E ⊆ S{1,2} f , f(E) = {z1, z2}. So D1 f := S{1,2} f ∩ f -1 (1) and D2 f := S{1,2} f ∩ f -1 (2) are both S{1,2} f -diffuse. Similarly, D1 g := S{1,2} g ∩ g-1 (1) and D2 g := S{1,2} g ∩ g-1 (2) are both S{1,2} g -diffuse. It is easy to see that g = (z1D1 g z2)S{1,2} g (z1S{1} g z2), and f = (z1D1 f z2)S{1,2} f (z1S{1} f z2). According to Lemma 3.7, (z1D1 g z2)S{1,2} g z2 = z1D1 g z2 ∼ z1D1 f z2 = (z1D1 f z2)S{1,2} f z2. It follows from Lemma 3.2 that there are constants c{1,2} g and c{1,2} f such that (z1D1 g z2)S{1,2} g z2 ∼ c{1,2} g S{1,2} g z2 and (z1D1 f z2)S{1,2} f z2 ∼ c{1,2} f S{1,2} f z2. Axiom 5 tells us that c{1,2} g = c{1,2} f . For simplicity, we use c{1,2} denote this constant. So g ∼ c{1,2}S{1,2} g (z1S{1} g z2) and f ∼ c{1,2}S{1,2} f (z1S{1} f z2). Since S{1,2} g ∪ S{1} g ∼ S{1,2} f ∪ S{1} f , z1S{1,2} g (z1S{1} g z2) ∼ z1S{1,2} f (z1S{1} f z2).

Using a similar argument, we show that there is a constant c such that z1 < c < z2 and z1(S{1,2} g )c ∼ z1(S{1,2} g )(z1S{1} g z2), z1(S{1,2} f )c ∼ z1(S{1,2} f )(z1S{1} f z2). This implies c{1,2} (S{1,2} g )c ∼ c{1,2} (S{1,2} g )(z1S{1} g z2), and c{1,2} (S{1,2} f )c ∼ c{1,2} (S{1,2} f )(z1S{1} g z2). Sowe have shown that f ∼ g. The general case when |R(f)| > 2 can be proved similarly by an induction on the ideal split. QED

Let BF denote the set {Belf : f ∈ F} of belief functions associated with all acts. It is not necessarily true that αBelf + (1 - α)Belg ∈ BF. In other words, αBelf + (1 - α)Belg is not necessarily generated by an act. For any α ∈ [0, 1], define hα : BF ×BF → BF as hα(Belf , Belg) = Bel+α(f,g) where +α denotes the convex-combination function mapping (f, g) to αf + (1 - α)g. Since ∼ is an equivalence relation on acts, convex combination +α is well defined on the equivalence classes according to Axiom 6. Let f∼ and g∼ denote the equivalence classes including acts f and g, respectively. αf∼ + (1 - α)g∼ := (αf + (1 - α)g)∼. It is easy to check that Bel(·) : F → BF defined as Bel(·)(f) = Belf is a homomorphism from 〈F∼, (+α)α∈[0,1]〉 to 〈BF, (hα)α∈[0,1]〉 where F∼ = {f∼ : f ∈ F}. It is easy to show that 〈F∼, (+α)α∈[0,1]〉 is a mixture space, and so is 〈BF, (hα)α∈[0,1]〉[Herstein and Milnor, 1953]. For simplicity, we will omit the subscript ∼ for equivalence classes in the following whenever no confusion arises. For any two Belf ,Belg ∈ BF, Belf ≻ Belg if f ≻ g. Assume that f ≻ g ≻ h. According to Lemma 3.2, f ∼ zf , g ∼ zg, h ∼ zh for some constants zf , zg, zh ∈ Z such that zf > zg > zh. There exists α ∈ (0, 1) such that αzf + (1 - α)zh > zg. From Axiom 6, we know that +α(f, h) ∼ (αzf + (1 - α)zh) > zg. It follows that +α(f, h) ≻ g. Similarly, we can show that there exists β ∈ (0, 1) such that +β(f, h) ≺ g. From Axioms 1 and 6, we know that both 〈F∼, (+α)α∈[0,1]〉 and 〈BF, (hα)α∈[0,1]〉 satisfy the conditions for the mixture space theorem ([Herstein and Milnor, 1953] or Theorem 5.11 p. 54 in [Kreps, 1988]).

Theorem 3.11 (Mixture Space Theorem) For the above mixture space 〈F, (+α)α∈[0,1]〉, there exists a function F : F → R such that (1) f ≻ g iff F(f) > F(g); and (2) F(αf + (1 - α)g)) = αF(f) + (1 - α)F(g). We say that F represents ≻ on F. Moreover, F is unique up to a positive affine transformation: F ′ : F → R is a representation of ≻ iff F ′ = aF + b for constants a > 0 and b.

The above theorem has a more general form: F(∑ni=1 aifi) = ∑ni=1 aiF(fi) for any acts f1, · · · , fn ∈ F and nonnegative a1, · · · , an such that ∑ni=1 ai = 1. Since F is unique up to positive affine transformation, we assume that F(0) = 0 and F(M) = M for simplicity. With this assumption, the commutativity of F with convex combinations implies that F(z) = z for any z ∈ Z (this is the reason why we assume l = 0). Note that any constant in Z is viewed as a constant act here. A function u : I = {(l,m) : 0 ≤ l < m ≤ M} → R is called an interval utility if it is continuous and strictly increasing,i.e., u(z1, z2) > u(z′1 , z′2 ) whenever z1 > z′1 and z2 > z′2 .

Theorem 3.12 (Representation Theorem) If the preference relation ≻ on F satisfies Axioms 1-6, then there exists a belief function Bel on the state space S and an interval utility u such that f ≻ g iff ∑A⊆S u(minf (A), maxf (A))mf (A) > ∑A⊆S u(min(g(A)),max(g(A)))mg(A) where mf and mg are the corresponding mass functions of Belf and Belg generated by Bel w.r.t. f and g (Eq. 1), respectively. Moreover, Bel is unique and u is unique up to a positive affine transformation.

Proof. For any α ∈ [0, 1] and f ∈ F, F(αf) = F(αf + (1-α)0) = αF(f). Consider the ideal partition E0 := {Ei : i ≤ i ≤ n} of S, each element of which is an atom. Since fn = f↿Ei n +· · ·+ f↿En n , F(f) = F(f ↿Ei )+· · ·+F(f ↿En ). In particular, M = ∑ni=1 F(M ↿Ei ). From Axiom 6, we know that F(z↿Ei ) z = F(z′ ↿Ei ) z′ for any z, z′ ∈ Z and hence F (M↿Ei ) M is independent of the consequence M ∈ Z. Let Pr(Ei) := F(M↿Ei ) M . So F(z ↿Ei ) = zPr(Ei) for any z ∈ Z. Such defined Pr is a probability measure on E0 and represents the preference relation ≻ on the ideal events. It is easy to show that, for any two ideal events E and E′ , E ≻ E′ iff M ↿E≻ M ↿E′ . This equivalence implies that the combination of Axiom 6 and those properties in Lemma 3.3 meets the necessary and sufficient conditions for existence of a unique measure strictly agreeing with a qualitative probability ordering in [Suppes and Zanotti, 1976]. So Pr is the unique probability measure that represents the preference relation ≻ on ideal events and Bel := (Pr)∗ is also the unique belief function that is derived from qualitative belief function in Lemma 3.4 and satisfies Axiom 6. Let R(f) = {z1, · · · , zn} be the range of f such that z1 < · · · < zn and Ai := f -1 (zi)(1 ≤ i ≤ n). It is easy to see that {Ai : 1 ≤ i ≤ n} is a partition of S. Let N = {1, · · · , n} and {SJ f : ∅ ̸= J ⊆ N} be the ideal split (Definition 3.8) of the partition {Ai : 1 ≤ i ≤ n}. Recall that, for any nonempty ideal E ⊆ SJ f , f(E) = {j : j ∈ J}. It follows from Lemma 3.9 that F(f) = ∑ki=1 F(f ↿SJ f ) = ∑ki=1 F(c(zminJ , zmaxJ ) ↿SJ f ) = ∑ki=1 c(zminJ , zmaxJ )Pr(SJ f ). Note that Pr(SJ f ) = mf({zj : j ∈ J}). Define u : {(l,m) : 0 ≤ l <m≤M} → R as u(x, y) = c(x, y). From Axiom 4 and Lemma 3.9,we have that u is continuous and strictly increasing. Also we obtain a version of von Neumann-Morgenstern theorem for the mixture space 〈BF , (hα)α∈[0,1]〉 with Bel = P r∗.

QED

It is easy to check that the converse to Representation Theorem also holds.

4 RelatedWorks and Conclusion

To the best of our knowledge, we are the first to provide the belief-function counterpart of Savage's theorem in a classical decision model (the set-up in Section 3.1) where the state space is finite. A decision foundation for belief functions was given by Ghirardato [Ghirardato, 2001], however using a different framework from the classical decision model. He assumed that acts are correspondences, assigning sets of outcomes rather than one outcome, to states. With the expected uncertain utility theory from [Gul and Pesendorfer, 2014], we advance Jaffray's theory about decision making with belief functions [Jaffray, 1989; Jaffray and Wakker, 1994]. The conception and structure of our theory mainly comes from [Jaffray and Wakker, 1994]. Jaffray's model is also finite but his semantics is Dempster's model of multi-valued mappings which is different from our generalized probability semantics. In his set-up, the DM uses a two-stage approach to process the information. The first stage deals with the probabilistic information. A deviation from the Bayesian approach occurs in the second stage where the principle of complete ignorance applies. In order to achieve the von NeumannMorgenstern theorem for belief functions, he did not show but postulated the "neutrality axiom" that acts are indifferent whenever they generate the same belief functions over the consequence space. Jaffray demonstrated the incompatibility of Savage's sure thing principle with belief functions and assumed a weakened version by restricting Savage's principle to unambiguous events. But his unambiguous events are too sparse for decision making because a belief function with all nonempty events being focal possesses only two trivial unambiguous events: ∅ and the state space S. This is the main reason why we choose to restrict the sure-thing principle to ideal events in a larger state space with an inner-probability interpretation (Part 2 of Proposition 2.1). The state space in [Gul and Pesendorfer, 2014] must be infinite because of the Archimedean axiom (Axiom 5 there). The development of their theory is quite different from the familiar EU theory for probability functions. They first proved Savage's theorem on ideal events and then defined the interval utility function without considering the two important theorems in the classical EU theory: qualitative belief theorem and the neutrality theorem as we do in this paper. The extensive literature about expected utilities includes many related works including [Schmeidler, 1989; Gilboa and Schmeidler, 1989; Zhang, 2002]. There is also a rich literature about decision making with belief functions (See Introduction). But none of them provides an axiomatization based on preferences over acts in a finite classical decision model as in this paper.

Our axiomatic system (Axiom 6) extends the language of expected (uncertain) utility theories with a definable convexcombination operator on acts. The extension is motivated by both our neutrality theorem and Jaffray's idea of equating acts with the belief functions that they generate over outcomes [Jaffray, 1991]. One may replace Axiom 6 here with an axiom which is similar to the state-independent preference intensity axiom in Wakker's model [Wakker, 1989] or to Assumption 3 in [Gul, 1992] without the convex-combination operator. We would like to achieve a Savage-style theorem for belief functions without any probabilistic interpretation [Smets and Kennes, 1994] which incorporates recent results on deFinetti-style and von-Neumann-Morgenstern-style methods [Flaminio et al., 2015; Coletti et al., 2015].

Acknowledgments

The first author is partly supported by NSFC No.61732006 and NSFC No.61772538, the second is partly supported by NSFC No. 61472425 and the third by NSFC No.61432006.