PII: 0022-247X(91)90214-K JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS 159, 55&594 (1991) On the Scoring Approach to Admissibility of Uncertainty Measures in Expert Systems IRWIN R. GOODMAN Naval Ocean Systems Center, San Diego, California 92152 HUNG T. NGUYEN AND GERALD S. ROGERS Department of Mathematical Sciences, New Mexico State University, Las Cruces, New Mexico 88003 Submitted by L. Zadeh Received March 19, 1990 This paper arose from our need to rigorize, clarify, and address fully the results of Lindley’s paper (Scoring rules and the inevitability of probability, Znternat. Statist. Rev. SO, (1982), l-26). Herein, we develop a calculus of admissibility in a game theoretic setting. In the case of an additive aggregation function, it is shown that decomposable measures, such as those used in fuzzy logics, are admissible. Also, the problem of the admissibility of the Dempster-Shafer belief functions is investigated via the concept of random sets. It is shown that the class of admissible measures in a scoring framework depends on the assumptions concerning the aggregation function in use. In particular, for nonadditive aggregation functions, an admissible measure may not be transformable to a finitely additive probability measure. 0 1991 Academic Press, Inc. 1. INTRODUCTION With the advent of Artificial Intelligence and the development of expert systems, a number of schools of thought has arisen concerning how uncer- tainties in complex real-world situations are to be modeled. In addition to probability in all of its variants [34], approaches to uncertainty modeling now include the Dempster-Shafer theory of belief functions [26], Zadeh fuzzy logic [32], and nonmonotonic logics [20]; a survey of these approaches is in [28]. Roughly speaking, the choice of a set-function to model the uncertainty involved in a problem at hand is related to the pragmatic aspects or, at a deeper level, to the semantic nature of the type of uncertainty under consideration. Lindley [16, 173 proposed a simple but novel approach, extending DeFinetti’s original considerations on coherence of uncertainties to a more 550 0022-247X/91 $3.00 Copyright 0 1991 by Academic Press, Inc. All rights of reproduction in any form reserved. SCORING APPROACH TO ADMISSIBILITY 551 general setting, for judging the usefulness of different competing uncertainty measures. DeFinetti’s original work [6] may be viewed as a two-person zero-sum game, played between player I, “nature” or “the master of ceremonies,” and player II, “decision-maker” or “you” or “bookie” as denoted variously in the literature [8, 13, 221. DeFinetti’s uncertainty game has great appeal: it is determined by the cumulative amount of the bets. The concept of admissibility in DeFinetti’s game is in fact a type of uniform local admissibility (see also [ 141) which is commonly expressed as the coherence axiom. DeFinetti’s chief result is that the only coherent uncertainty measures are finitely additive conditional probability measures. Lindley’s main contribution to the situation was to investigate DeFinetti’s game by replacing the squared loss functions by a more general score function. For the most part, DeFinetti and Lindley assumed addition for the overall loss function (or aggregation function). Lindley’s chief results are as follows: (i) If an uncertainty measure p is admissible with respect to a score function f, then p can be transformed into a finitely additive conditional probability measure via a known transform depending on f, say Pf; (ii) Within the class of score functions f such that Pf is increasing, the necessary condition in (i) is also sufficient. Roughly speaking, an admissible uncertainty measure has to be a func- tion of a probability measure, i.e., one cannot avoid probability ! However, note that such an admissible uncertainty measure need not be a probability measure ! (See also the axiomatic work of Cox [S].) (iii) As implications from (i), the Dempster-Shafer belief function, Zadeh’s possibility measure, confidence values and significant statements are all inadmissible ! The purpose of our work is threefold: (a) To analyze Lindley’s results and implications, for which we recast Lindley’s somewhat informal arguments and concepts totally within a game theoretic setting. It is pointed out in this paper that DeFinetti in his earlier [6] more restricted work and later, Lindley [ 161 in his generalization of DeFinetti’s efforts, both tacitly assumed: (I) “measure-free” conditional events exist independent of any par- ticular choice of probability measure, but are compatible with the usual evaluation of conditional probability. (II) The usual (unconditional) event indicator function can be extended to be well defined upon conditional events. 552 GOODMAN,NGUYEN, AND ROGERS (III) A natural conjunctive chaining relation holds between condi- tional events. As a consequence of the above assumptions, in carrying out the analysis here, basically two cases are considered apropos to choosing an uncertainty measure in the DeFinetti-Lindley uncertainty game: (1) all finite sequences of conditional events, where each such sequence possesses a common antecedent-this includes as a special case all finite sequences of (uncondi- tional) events, by identifying unconditional events as conditional ones having a universal antecedent-and (2) all finite sequences of conditional events with possibly differing antecedents-this case obviously includes the first as a special case. The structure of uncertainty games is rigorously spelled out in Section 2. In Section 3, a calculus of admissibility, from an analytic viewpoint, is developed for games with arbitrary aggregation functions. In Section 4, uncertainty games with an additive aggregation function are considered in detail together with a Bayesian analysis. (b) To show, contrary to Lindley’s conclusions outlined in (iii) above, that there are rather large classes of nonadditive uncertainty measures, such as belief functions and decomposable measures in fuzzy logics, which are admissible. Also, Zadeh’s max-possibility measures are shown to be uniform limits of admissible measures (Sections 5 and 6). (c) To study the effects of the assumption of additive score functions, we present, in Section 7, various examples of non-additive aggregation functions. These illustrate the fact that the class of admissible measures in a scoring framework depends heavily on the nature of the aggregation functions. In particular, there exist aggregation functions such that admissible measures cannot be transformed into finitely additive probability measures (as opposed to the case of the additive aggregation function in Lindley’s work). In summary, by formalizing Lindley’s work within a general and rigorous game theory framework, we develop a calculus of admissibility which can be used to compare competing uncertainty measures in Artificial Intelligence. We shed light on controversial conclusions concerning the inadmissibility of some well-known uncertainty measures and on the position of the “inevitability of probability.” 2. STRUCTURE OF UNCERTAINTY GAMES In this section, we will formalize Lindley’s scoring approach in a game theory setting. Since the scoring approach involves concepts such as SCORING APPROACH TO ADMISSIBILITY 553 “conditional events,” uncertainty measures, score functions, aggregation functions (implicitly), and admissibility, we need to define these terms rigorously. 2.1. Conditional Events Let Q be a set and d a Boolean (or 0~ ) algebra of subsets of 52. Elements of d are called events. The set complement of A in 52 is denoted by A’; the intersection of A, B in 52 is AB; and their union is A u B. For A E&‘, the indicator function has values ifoEA if cuEA’ In certain forms, it is simpler to identify A with I, so that A = 1 if A “occurs” and A = 0 if A “does not occur.” For A, BE d, the “measure-free” conditional event A ) B is defined by DeFinetti [6] (see also [22]) as the restriction of I, to B, i.e., (AlB)(o)= 0 i 1 if weAB if UEA’B (undefined) if o E B”. Except when B = Sz and (A IQ) is identified with A, these conditional events are not elements of d. The above definition implies the invariant form (A 1 B) = (ABI B). Assume, also the fundamental homomorphic-like forms compatible with any fixed antecedent conditional probability (A I B)” = (A’1 Bh (AuC)lB)=(AlB)u(CIB), MCI B) = (-4 I @(Cl B). Although DeFinetti recognized the potential use of measure-free condi- tional events, in obtaining his key results a formal calculus of relations was not developed. (Again, see [6, especially Vol. 1, Chap. 4, Vol. 2, pp. 266 et passim to 3333.) However, DeFinetti and Lindley implicitly recognized the natural conjunctive chaining relation among conditional events mentioned earlier. (Specifically, see the remark at the end of Section 2.3 and Theorems 554 GOODMAN, NGUYEN, AND ROGERS 3.23 and 4.21’.) For a general treatment of conditional events, see [24] or cw Goodman and Nguyen have derived a full calculus of operators and relations extending the unconditional counterparts for boolean algebras of events to the conditional case. In addition, a wide variety of desirable mathematical properties of these entities have been proven to hold based upon a minimal set of elementary assumptions, including the tacitly assumed conjunctive chaining relation mentioned above. In the context of uncertainty modeling, the uncertainty of an event A is, in general, assigned on the basis of additional information, another event B. But, a priori, conditional uncertainty measure p need not be a probability so that an algebra of measure-free conditional events has to be investigated as a domain for p. Now let d be the class of all conditional events, i.e., d= ((A(B BE&~. By the identification of (A 10) with A, we obtain d c 2. For any set X, and n 2 1, X” denotes the product space Xx Xx . . . x X (n times). We will use the notation A’, to denote the space of all finite n-tuples {a,: f, = (x,, . . . . x,,), xi E A’}. Unless otherwise indicated, “xi E x” and the like will always mean xi, . . . . x, for a generic n. For Al, = (A 1) . . . . A,,)EJP, we identify A, with its indicator function A,(o) defined as (A,(o), . . . . A,(w))E (0, l}“. For example, as(o) = (1, 1, 0, 0, 0,O) indicates that A,, A2 occurred but A3, Ah, A,, A, did not occur. Similarly, we identify with the function a,: B + (0, 1, u}” having values -&w = ((4 I F,)(o), .*a, (J% I J-n)(o)) E (0, 1, q. 2.2. Uncertainty Games We proceed now to formalize a special class of games called uncertainty games. Roughly speaking, these are triples (A,, A,, L) in which A I is a set of configurations (or realizations) of finite collections of (conditional) events, A, is a collection of “set’‘-functions representing “uncertainty measures,” and L is a real-valued loss (or penalty) function. Specifically, A, = Jm x Q. This set A I is regarded as the space of all possible “moves” or “pure strategies” of player I. Next, fix, once for all, four real numbers, a2 < a, < a, -+ R (the real numbers), a score function if the following are satisfied: (i) For each Jo (0, l}, f(., j): [a,, a31 -+ If3 satisfies the following “regularity” conditions: f( ., j) is continuously differentiable, with a unique global minimum in [a,, a,] at aj, (decreasing over [a,, ai] and increasing over Cq, ~~1); (ii) .f(x, 24) = 0, Vx E [a,, ax]. For example, we may interpret the score function as follows: player I has selected A E & and o E Q and player II has selected p E AZ, then the score for player II is &(A), 1) if A happens to occur, f(p(A), 0) if A does not occur. Now we need to extend f as a map from the space {(a,, 2,): n B 1, jZ.,E [a,, a31n, i,E (0, 1, 24}“> to the space IR,: for each n 2 1, J?,, = (x,, . . . . x,), i, = (tl, . . . . t,), fcL~,) = (f(XlY t,), *..9 fkY, 47)). Similarly, each uncertainty map (or measure) p: d -+ [a,, a,] is extended to a map from ZZ& to [al, a3100 as follows: for each n 2 1, i,=(A 1, . . . . A,) Ed”, c((A^,) = (AA I), . ..t AA,)) E [a,, dn. An obvious way of combining individual scores &(A ;), Ai( (i’ 1, 2, . ..) n) to obtain the total score is using addition on R, i.e., take Lf, +(a,, w, p) = Cr= 1 f(p(Ai), Ai(o Thus the loss function L,., + depends on two functions: f (score) and + (aggregation), This special case will be referred to as the additive aggregation case. In general, by an aggregation function, we mean a mapping ~9: IR, --t R such that (a) II/ is continuously differentiable in all of its arguments; (b) 1+9 is increasing in each of its arguments. (c) $(O,,) = 0, Vn 2 1, where 0, is the zero vector in R”. Note that the additive aggregation function is generated by ordinary addi- tion on R: II/ = + is equivalent to the sequence of functions (g,, n 2 l), where g,: IR’ + R, g(x,, . . . . xn) = CF= 1 xi. Similarly, we identify an aggrega- tion function $ with the sequence (+,, n 3 l), where (I/, is the restriction of II/ to R”. Note also that, while the additive aggregation function is 409’15912-IX 556 GOODMAN, NGUYEN, AND ROGERS symmetric, there is no a priori reason to impose such a condition on arbitrary aggregation functions. Now, given a score functionf and an aggregation function II/, we define the loss function Lf,, as follows: (Note that fand ,u are used in the extended sense.) The triple (A 1, AZ, Lf,$) is called an uncertainty game and is denoted by Gf,,. In DeFinetti’s game [6], a, = a2 = 0, a, = a3 = 1, and fb,A= {b”-i” ; ;I$ndefined); here $ = + . In Lindley’s extension of DeFinetti’s game, uj, j = 0, 1,2, 3, are not restricted to [0, 11, $ = + , and f is an arbitrary score function. 2.3. Subgames To formalize various concepts of admissibility in an uncertainty game Gr,$, we first introduce the concept of subgame. Suppose we are interested only in some given finite collection of condi- tional events, say a, then we need to look only at the subgame where and For example, we can view A,E$ as a set a,= {A,, . . . . A,} se. Then [a*, a31An= {p: {A,, . . . . A,} --* [az, a,]} so that each p in [a,, ujlAn is the restriction of a p in [a,, a3]“. In a subgame, the finite collection of conditional events in a is specified; if player II chooses p to express an uncertainty about these conditional events, then the overall loss would be Lf,ti,,dw ~1. The subgame Gf,+.,i is regarded as a game with partial infor- mation, namely player II does know that a is to be considered. For example, if a=((ElF), (E”(F)) and $= +, ~(u)=((EIP)(~), (EC1 F)(o)), and the set of configurations of a giving rise to non-zero losses (f (x, u) z 0) is {(EIF), 11, ((E”IF), 01, ((EIF), O), ((E”IF), l,}. SCORING APPROACH TO ADMISSIBILITY 557 For is {(AO), (0, l)}, 2 = (x1, x,), where x1 = p(EI F), .x2 = p(E’I F), we have two overall scores: f(xr, l)+f(Xz, 0) (if EIF occurs) and f(X,? 0) +f(x*, 1) (if E” 1 F occurs). It should be noted that so far only those finite sequences of events have been considered which have a common antecedent. Relevant to this, denote for any Fe ZZZ’, d-fF= {(EIF): EEL}. The reason for this is that if one wished to determine the possible indicator evaluation combinations among any sequence such as ((E, I F,), (E, / F2), (E, I F3)), until recently, no standard technique existed for dealing with this issue. However, Goodman, Nguyen, and Walker [ 121 and Schay [24] have proposed independent nonstandard syntactic approaches for treating this and related problems. Only one such situation will be considered in this paper, namely the fundamental natural conjunctive chaining relation, (El FG)(F( G) = (EFI G), which is obviously true for all corresponding conditional probability evaluations AEI =I .PV’I (3 =PPI G) for p(G) > 0. More details of this will be seen in Theorem 3.2.3 et passim. 2.4. Equivalent Reduced Forms of Games and Subgames The space /1 r = J&, x 52 in the game G/,@ is infinite, in general, but for each R E Jm, the space of configurations of a, namely a(Q) is finite, a sub- set of 10, 1, u}lA^‘, where Ial denotes the “dimension” of 8; e.g., if A E d”, then IAl = n. On the other hand, the domain of Lf,$ involves a, but since Lf,JA, ., p) is constant on each (A)-’ (t), t E A(Q), 8 can be replaced by the finite d-partition (of Q) generated by a. Specifically, for each a E Jm, say A = ((E, IF,), . . . . (E, I F,)), consider the finite collection of events %(A^)= {E;F,, E;F;, F;, i= 1, . . . . n}. Let z(a) denote the canonical parti- tion of Q generated by +?(A) (which reduces to A^ = { Ei} when all F; = Q. Then, rc(a)= {B,,j= 1, 2, . . . . 23n}, where each B, is of the form nr=, 02, Dk E %‘(A^), sk = 1 or c; 0: = Dk, 0: is the set complement of D,. Also, each D, is a union of the Bis. (See [23, p. 12-153.) Note that because the E’s and F’s are not necessarily distinct, the cardinality of z(a), say m = ITCH, is most often ~2~“, but at least 2. The cardinality of rc(a) may be less than n = I Al as we now demonstrate. 558 GOODMAN, NGUYEN, AND ROGERS Let Then a = (EF, E”F, F”, F). SF@) = {Dl = EF, D, = E”F, D, = F”, D, = F}. Only the following configurations of “occurrences” can arise so that m=l7c(A)l=3<4=lAj: 1 0 0 1 for B, =EF, 0 1 0 1 for B, = E”F, 0 0 0 1 for B,=F”. Thus, B’BcBC=EF 1 2 3 BCBIBC=ECF 1 2 3 B;B;B,=F” B1B;B;uB;B2B;=F. Of~ourse,m=3>2when~=((ElF),(Ec~F))for~(~)={EF,EcF,FcJ= W ). The (equivalent) reduced form of GY,$ is G:, = (A:, AZ, L&l, where where n:={(a,B):a~~~,B~.(a)}, I I a Lj!&k 4 ~0 = W(P(A), A(B))), a(B) = t E (0, 1, u}‘“’ -=-B={o:&)=t}, i.e., /i(B) = &II) for any choice of w in B. Similarly, the (equivalent) reduced form G,,,, A is G&A = (Ata, Az,a, L&A), where ny,=?T(A) SCORING APPROACH TO ADMISSIBILITY 559 and 3. ANALYTIC STUDY OF ADMISSIBILITY In this section, we will introduce various concepts of admissibility for Gf,$ and then develop analytic techniques for (weak) local admissibility with arbitrary aggregation functions $. This also extends Lindley’s results in the case of an additive aggregation function, namely, giving sufficient conditions for (weak) local admissibility. For related works in Statistics, see [4, 143. For the concept of Pareto optimality, see [2, 271. 3.1. Concepts of Admissibility In this subsection, we spell out relevant forms of admissibility in the reduced form of the game First, ,LL E A, is (ordinary) admissible with respect to GTIL if there is no VIZ,~, such that Lz$(A, B, v) <,!,;+.(A, B, p) for all (A, B) E /1: with the strict inequality for at least one (a, B). Similarly with respect to the subgame Gzti,~, PE/~*,A = [a,, as]” is a-admissible (A-AD) if there is no v E AZ,2 such that for all BE ~(2) with strict inequality for at least one B. More generally, let 8 belong to the power set 9(Jm). Then p E A2 is b-admissible with respect to _Gf:+ if p is a-admissible for all 2 E 8’. (Note that A2,~ E A,.) When d = SZ!~, p is uniformly admissible. It is easy to see that uniform admissibility implies ordinary admissibility. Continuing with the subgame where 2 is fixed, we note that p(A) E IR” for which there is the usual topology based on the Euclidean norm 11 /I. Thus we may have a neighborhood of p WP,~)= {vEA~,A: Ilv(~)--~(~)ll 0 there is an r = r(Z, $, a) > 0 such that there is no t E (0, r) for which L”‘(?i++g)-L”‘(.?),< -atl,. (2) Here 1, is a k by 1 vector all of whose components are 1. SCORING APPROACH TO ADMISSIBILITY 561 Note that -at 1, cs 0 in Rk. It is convenient to refer to such j as a direction. Then, locally, z? cannot be “beat linearly in any direction.” Of course, A-WAD implies &WLAD: if (2) holds for some j, a, t, then L”‘(i + tf) 0, choosing t = r/(r + jl j - ill ) makes /) t(j - a)\\ < r whence .? is not J-LAD. (ii) If i is not A-WAD, there is a j such that L(‘)(p) cs L(‘)(i). Then a=min(Lj”(f)-Lj’)(j),j= l(l)k} >O and L~l~(~) 0 such that for all r so there is a t, < r for which L(2+ t,jq- L(i)< -E&l,. Since t,+O as r-+0, J$<,O. 1 Recall that for 2 = (A,, . . . . A,), PE [a,, a31A is identified with P = (X,) ..*, x,) E D = [a,, asIn. In view of Theorem 3.2.1, the analytic study of weak local admissibility of p or 2 is reduced to finding conditions on J(a) so that there is no 9 E Iw” for which J(Z). $ cs 0. It is well known that the solutions of a system like Ji, = i depend heavily on the rank p of J. Also, the columns of J and the rows of J, 9 and i can be permuted without changing the rank or character of the solutions; these can also be partitioned. In the following, we assume that this has been done so that when the rank is p, the system is where J, is p by p and nonsingular, C is p by n-p and R is k-p by p. Of course, if p = n, the columns involving C do not appear and if p = k, the rows involving R do not appear. The following theorem contains several results relevant to this work. SCORING APPROACH TO ADMISSIBILITY 563 THEOREM 3.2.2. (a) Zf p =n = k, then i is not WLAD. (Indeed, if J is non-singular, then the system Jy = i has a solution j for every i, in particular 2 <,s 0.) (b) Zf n = k and .? is WLAD, then det J= 0. (cl ,%? is WLAD zf and only zf there is no i E IV’ such that J, [ 1 RJI i<,O. (d) Zf p = 1, then 2 is WLAD if and only if the vector has both positive and negative components or at least a zero component. (e) In case k = n = 3, j? is WLAD if and only if det J = 0 and either (i) p = 1 and J, [ 1 RJ, has a zero component or contains both positive and negative components or (ii) p=2 and R 0 when x = a, ; for XE (a,, a,), this column has both positive and negative components. Hence 1 is &WLAD. (b) If p = 2, permute the second and third columns of J to obtain the partition where J = f’(x, 1) f’k 1) l C f’h 0) f’k 1) 1 and RJ, = (f’(x, 0), f’(z, 0)). Then det J,=f’(x, l)f’(z, l)-f’(x,O)f’(z, l)>O when z #a,. In this case, we have R = 0) .I-‘(% 1) -S’k 0) f’k 0) f’k 1) f’k 0) -S’(x, 0) f’(Z, 1) det J, > det J, 1 with f’(x, O)[f'(z, 1) - f’(z, 0)] 6 0. Look at f’(x, 1) f’(z, 0) -f’(x, 0) f’(z, 1). (*) 566 GOODMAN, NGUYEN, AND ROGERS By hypothesis, det J= 0 and this is equivalent to P,(z) = P,-(x) + P/(y), where P,-: [ao, a,] -+ [0, l] is given by f ‘(x9 0) pf(x) =f’(x, 0) -f’(x, 1)’ Thus Pf(x) 0, and R = (0,O). 1 The following result is actually an application of Corollary 3.2.3. However, as it is basic for most of the rest of our work, we state it as a theorem. From now on, PE [a,, u,]~. We say that: p is g2-WLAD if p is a-WLAD for 2 of the form { (E( F), (EC ( 8’)); SCORING APPROACH TO ADMISSIBILITY 567 .H is &&WLAD if p is A-WLAD for a of the form ((E, I F), L% I F), (El u J% I F)} with El 4 = fzr. Also, P,-(x) is always given by (* * ) above. THEOREM 3.2.2’ (Equal Antecedent Counterpart of [16, Lemma 51). Suppose $ = + . Then the following are equivalent. (i) p is &‘* and &- WLAD, (ii). Prop: ~4~4 [0, l] is afinitely add‘ ltive probability measure, for all FE&, where ,Q1’F=d ((E(F): EEL}. Proof. (i)= (ii). Since p is gZ-WLAD, we have, for any E, FE&‘, p(EI F) = x, ,u(EC 1 F) = y, det J= 0, where J= [ f'h 1) f'(Y,O) f'(-%O) f'(Y, 1) 1 (1) then, P,(x) + P,-(y) = 1. In particular, for F= Q, we have Pfop(E) + P,+(EC) = 1. Next, since p is &s-WLAD, for any E,, E,, FE d with E, E, = a, we have, det J = 0, where, x = p(E, 1 F), y = p(E, I F), z = p(E, u E, 1 F) and so that Pr(z) = Pf(x) + Pr( y), by computation. In particular, for F = Q, PpdE, u Ed = Pp/.@,) + P,oP(&). Thus Q = P,o p: &- + [0, l] is a finitely additive probability measure, for all FE&. (ii) =z- (i). First note that p: & + [0, 11, (ii) means that the restric- tion of p to &F (still denoted by p) is such that Pfop is a finitely additive probability on JZ?~, say QF = P,o p, for all FE .r4. Thus which means det J = 0, where J is as in (1). The rank p of J is therefore 1. Since x E [a,, a,], each column of J contains a zero component or has 568 GOODMAN,NGUYEN, ANDROGERS both positive and negative components, and hence (x, y) is a-WLAD, VA = {(EJF), (E’)F)}, i.e., p is $-WLAD. The fact that p is &WLAD follows from Corollary 3.2.3, since for any E,, E,, FE -01, with E, E2 = a, the condition 0, for all E E ~4, (+PMEI F)) = U’p/WlF) = f’,MWYPfMF)). Proof: Follows a similar format as for the proof of Theorem 3.2.2’, where now, in addition to Eqs. (1) and (2) holding when (i) is assumed, one has due to p being G$‘,-WLAD, 1) f’(h 1) f’(w 1) J= 0) f’(o, 1) f’(w, 0) 1 , (3) f’(u, 0) S’(w, 0) where u=p(EJFG), v=p(FIG), w=p(EF(G). 1 SCORING APPROACH TO ADMISSIBILITY 569 4. GAMES WITH AN ADDITIVE AGGREGATION FUNCTION AND BAYESIAN ANALYSIS This section is devoted to a detailed investigation of games with an additive aggregation function; to be complete, we consider also their mixed extensions. Under an additional assumption on the score functions, we establish the equivalences among different concepts of admissibility, including Bayesian decision functions and DeFinetti’s coherence measures. We also show that nonatomic probability measures are not “coherent” in games with improper score functions. 4.1. Mixed Extensions of Uncertainty Games Consider the game G,+ in its equivalent reduced form (A :, A 2, Lf+) with Because of the nature of /i:, mixed strategies or prior probability measures on A: will be defined as follows. Player I will first pick an A^ E J& according to some probability measure 4 on (s&,, SJ), where 3 is some a-algebra of subsets of s&, and then depending upon a, pick a configuration of occurrences of A^ (as a finite collection of conditional events, equivalently) an element of the partition n(A), according to some probability measure rA on the power class 9y7c(A)) of 7c(A). Now, since ~(a) is finite, each probability measure on 9(x(a)) is identified by its probability density function on X(A), i.e., 6: {B,,j= 1, . . . . m} -+ [0, 11, f QB,)= 1, j= 1 where Bis are some listing of the elements of n(a), and m = In(a Next, each such 8 generates a probability measure P, on (Sz, &) such that PdBj) = e(Bj), Vj = 1, . . . . m. Indeed, for each j = 1, 2, . . . . m, let Pj be a probability measure on B,, i.e., on the a-algebra trace {A Bj: A E &} with Pj( Bj) = 1. Define, for A E A’, P,(A) = CJ’= , O( Bj) Pj(ABj). Note that PO(A_) is completely determined by 8, Vi = 1, . . . . n, where a = (A r, . . . . A,), n= IAJ. Then, since each Aims? in general, the probability measure P, on d is extended to d via the condi- tional probability operation. For a rigorous treatment of this extension, see c121. 570 GOODMAN, NGUYEN, AND ROGERS If (X, 9) is a measurable space, we will denote by P(X, X) the collection of all probability measures on it. The collection of probability density func- tions on z(a) is denoted by P(rc(a)). Thus, we have, by identification, P(7Q)) c P(Q, a). The space of prior probability measures on Ai+ is The expected loss of p E AZ, with respect to a prior (q( .), z.( ., +)) is so that the mixed extension of G;, is Similarly, the mixed extension of the subgame CT,,, is where ~~,+,a(& PL) = Cj$’ Lf,S,A(Bj, P) NBj). Now, we view the subgame GTti,~=(n(A), [a,, uSI’, L!$,J) as a statistical game coupled with the random variable X whose distribution P, depends on BE n(a); when X is constant, on each BE n(a), the risk is L(B, p)+ On the other hand, since ~(2) is finite, standard results from decision theory (for finite games) hold for Gzti,A (see, e.g., [7, 31). Then the risk set L(D) is closed and bounded since D is compact in R” and L is continuous. For convenience, we state below some definitions and basic results. (i) ,U~E [a,, al] A is Bayes with respect to a prior distribution r on .(A) if which is the minimum Bayes risk; E, denotes the expectation with respect to t. We write ,nL, for the Bayes uncertainty measure with respect to r. SCORING APPROACH TO ADMISSIBILITY 571 (ii) r0 is a least favorable prior if infE,,L(.,~)=supinfE,L(.,~) P 7 p which is the lower value of the game. (iii) %?L ~cz,, a,ld is complete if for each ALE [a,, a,]“--%‘, there is v E %? which is “better” than p, i.e., L( ., VI cw L( ., P) (A-AD). V is minimal complete if %’ is complete but no proper subclass of 5%’ is complete. (iv) For admissibility of Bayes rules in G~,.A, we have (a) If pL, exists uniquely up to equivalence (p - v if and only if L( ., p) = L( ., v)), then pL, is admissible (A-AD). (b) If the prior r is strictly positive (i.e., r(B) > 0, VBE n(a)), then pz exists, and is A-AD. (v) If p is A-AD, then p = pr for some r. (vi) The class of Bayes rules is complete, and the class of admissible Bayes rules is minimal complete. (vii) Let 6r~&; then p is said to be b-Bayes if p is Bayes with respect to Gzi,~ for all a E 8’. In particular, p is uniform Buyes if d = s&. Note that p is Bayes with respect to G,!, when the prior is in P(/l,), i.e., of the form r = q( .), r.( ., .). 4.2. Equivalences of Various Concepts of Admissibility In the rest of this section, we consider $ = +. THEOREM 4.2.1 (Equal Antecedent Form of [ 16, Theorem 21). Consider the game Gl + with f such that PY is increasing. Let p E [a,, alId. The following are equivalent. (i) u is uniformly admissible, w.r.t. all finite equal antecedent condi- tional event sequences. (ii) p is & and &-weak local admissible. (iii) u is untform Bayes, w.r.t. all finite equal antecedent conditional event sequences. tttve probability measure, for all PEvL Prop: ~4~ [0, l] is a finitely add’ Proof (i) =S (ii). Obvious by definition. W/l 5912. I9 572 GOODMAN,NGUYEN, ANDROGERS (i) =z. (iii). Follows by standard results of the game GT +, 2, namely if p is A-AD, then ,u is Bayes (with respect to some prior z on .(a)), and conversely, if p is Bayes (p = ,u~), then since ,u~ is unique, pL, is R-AD. The uniqueness of e, (up to equivalence) can be seen as follows. Let ZE P’(a(A)), a = ((EiJFi), i= 1, . . . . n); we have E7L(a, PI= i C fCP(Ai)3 Ai(B)I T(B) i=l Ben(A) =,$, {fCP(ai)9 ll C r(B) +fCPCAih Ol C BE QlW BE Q2(G Q,(i)= {BE7C(A) : BGEiFi) Then Qz(i) = (BE X(A) I BEiF,= a}. since 2 r(B)=l- c t(B). BE PAi) BE Ql(i) Therefore, p(Ai) = P;l[&EQ,cil r(B)] is uniquely determined by r. (ii) * (iv). By Theorem 3.2.2’. (ii)* (iii). Assume (ii). Then (iv) holds. Since Cecnc~) r(B)= 1, r = Prop can be taken as a prior for x(a). Then p = ~1~ and hence (iii) holds. Conversely, when (iii) holds, (i) also holds, and, a fortiori, (ii). 1 THEOREM 4.2.1’ (Corresponds to [16, Theorem 21). Make the same assumptions as in Theorem 4.2.1. Then Theorem 4.2.1 holds with the folIowing strengthening. (1) Omit the constraint “w.r.t. all finite equal antecedent conditional event sequences” in both (i) and (iii). (2) Add the property that p is gh-weak local admissible to (ii). (3) Replace s&., for each FE d by simply d in (iv). SCORING APPROACH TO ADMISSIBILITY 573 Proof: Obvious by inspection of the proof of Theorem 4.2.1 and the role that &WLAD plays in making stronger Theorem 4.2.1 (iv). 1 Remark. For any a E J&, relative to CT + ,A, (i) A least favorable prior rOg p(rr(A)) can be obtained by minimizing the objective function Pf, +,,it59 Pu)’ 1 C fCPtA,), Ai(B)I t(B) i=l Bcsn(A) subject to the constraint CBEkCAI z(B) = 1. (ii) Using the proof of the uniqueness of pr in the above theorem, we can obtain a minimax uncertainty measure p0 E n 2,A, where inf sup P.f, +,A(? PL) = sup PEA2.A’ rEP(Tc(a)) rtP(n(A)) Pr, +,A(? PO). (iii) G T +,A has the value V,(f, a), where Vo(f9 4 = sup reP(n(A)) Pr. +,,.&r, /%I) = P/, +,A(%3 I%J. THEOREM 4.2.2. Consider the game GT + with PJ increasing. Suppose that f is not a proper score function (i.e., P,(x) E x) andf is twice differentiable. Then no nonatomic conditional probability measure p on d can be Gf +- uniformly admissible. Proof. Assume the contrary, i.e., the nonatomic probability p on d is uniformly admissible with respect to GT + . By Theorem 4.2.1, we should have, by the nonatomicity of p, x, Vx E (0, 1). SCORING APPROACH TO ADMISSIBILITY 575 Some examples of t-conorms are x if y=O T(x, Y)’ Y if x=0 (not continuous) 1 otherwise T(x, Y) = Max(x, Y) (not Archimedean) T(x, y) = Min(x + y, 1) (Archimedean). For the related concept of copulas in Statistics, see, e.g., [9, 10, 191. An Archimedean t-conorm T has the following representation [ 181: T is an Archimedean l-conorm if and only if there exists an increasing, con- tinuous function g (called the additive generator or generator of T) which maps [0, l] -+ [0, + co] with g(0) = 0, and such that vx, YE lx, 11, T(x> Y) =g*Mx) +gb)L where the pseudo-inuerse g*: [0, + co] + [0, l] is detined by g*(x)= 1 i g-‘(x) if XE CO, g(l)1 if x>g(l). For example, (i) For p>O, Tp(x, Y) = W’ + Y’ - x~Y~)“~ =g;(g,(x) + g,(y)), where g,(x) = - (l/p) log( 1 - xp), g;‘(x) = (1 - eppx)“P =g,*(x); note that g,( 1) = + co here. (ii) For p B 1, T,(x, JJ) = [Min(xP -I- yp, l)]“” has generator g,(x) = xp, 1 x’IP g*(x)= 1 if xE[O, l] if x>l with g,( 1) = 1 here. Since a t-conorm T is associative and commutative, we can extend T to T: co, 11, + co, 11, where T(x) = x, by convention, T(x I, -*-, xx) = Tb,, T(x,, . . . . x,)1, n 2 2. The representation of an Archimedean t-conorm T becomes W,, x2, . . . . x,) =g* 0 1. 576 GOODMAN, NGUYEN, AND ROGERS Now, let (52, J&‘) be a measurable space. A mapping p from & to some interval of R, say [a,, a,], is called a decomposable measure if there exists T: [a,, a31 x [a,, a31 + [a,, a,] such that, for A, BE d with AB= a, p(A u B) = T(p(A), p(B)) (see, e.g., [31]). When such a Texists, it is called the composition law of p. As a generic example of a decomposable measure, begin with any fuzzy set membership function 01: D --, [0, l] and any t-conorm T. Then, if 0 is finite, one can make the extension of a as ,u,,~: P(Q) + [0, 11, where for any AcSZ, ,ua, T(A) = T(a(o) : w E A). (+I P is clearly decomposable. Conversely, given any decomposable measure pa’G.r.t. some t-conorm T, for any finite A as above, Eq. (+ ) holds with h,T=k In fuzzy logics, composition laws are t-conorms (with [a,, a3] = (0, 11). Note that probability measures are decomposable measures with T(x, y) = Min(x + y, 1); this is an Archimedean t-conorm with generator g(x)= -log(l-x) and g*(x)=g-‘(x)=1-e-“, since g(l)= +oo. Indeed, let P be a probability measure on d, and A, BE d with AB = 0. Since P(A) + P(B) = P(A u B) < 1, we have P(A u B) = P(A) + P(B) = Min(P(A) + P(B), 1). Furthermore, in the case of probability measures, the generator g is such that g( 1) = + co (and hence g* =g-r); the corresponding t-conorm T is called a strict (Archimedean) t-conorm. For a t-conorm T, a T-possibility measure is defined to be a map from d to [0, 1 J with T as composition law. For example, (Zadeh) max- possibility measure is a decomposable measure with T(x, y) = Max(x, y). Let B be discrete and a: Q + [0, 11. Let T be an Archimedean t-conorm with generator g. We denote by ,u~,~ the T-possibility measure defined as follows. For A E Q, finite, p,,T(A)= T(a(o), wEA)=g* [I &44)]. A For A countably infinite, PL,,r(A)=g* [z da(w))]. A Note that CA g(a(w)) < + CCL 5.2. General Admissibility under Additive Aggregation In order to discuss Lindley’s conclusions about the inadmissibility of uncertainty measures, we consider G, + . In view of the results of Sections SCORING APPROACH TO ADMISSIBILITY 577 3 and 4, we have to consider the concept of admissibility of a given uncer- tainty measure in a wide sense. Specifically, an uncertainty measure I-L E [a,, aIlJ is said to be general admissible if there is a game Gf, + such that p is uniformly admissible with respect to that game. In this sense, any probability measure is general admissible by taking the score functionf to be a proper score function ! But for a proper score function f, the associated probability transform P,-(x) = x, Vx E [0, 11, is increasing, and hence I’;’ exists. So we require, in general admissibility, the existence of a score function f such that Py ’ exists. It is seen that with respect to a game G’,.+ with Pf increasing, p is general admissible if and only if P,o p is a limtely additive probability. It is this equivalent property that we will use as a definition for general admissibility. In discussing possibility measures on discrete spaces, we can even consider a stronger concept of admissibility, namely general admissibility in the a-additive sense, i.e., Prop is a a-additive probability measure. It will be shown in this subsection that operations in fuzzy logics are, in general, “admissible,” and even (Zadeh)-max possibility measures are (uniform) limits of admissible decomposable measures. For related works in Statistics see, e.g., [lS]. Throughout this subsection, Q is a discrete space (finite or countably infinite), d = P(Q) and restrict d to all &,,, FE d. For CL: P(Q) + [0, 11, we write p( (0)) = p(w), so that the restriction of p to singletons is regarded as a function, still denoted as p, from Q to [0, 11. We also omit, from now on, the qualification “w.r.t. all finite equal antecedent conditional event sequences.” THEOREM 5.2.1. Let p’: 8(Q) + [0, 11. Then the following are equivalent: (i) p is general admissible in the a-additive sense. (ii) p is a decomposable measure with composition law T being an Archimedean t-conorm with generator g such that g( 1) = 1, and ; gtAw)) = 1. (*I ProojI (i) * (ii). Let f be a score function such that tr is increasing and such that P,.op is a o-additive probability measure. For A E 9(Q), we have P,WW = 2 P/tA~)), A and hence p(A) = PF ‘(CA P&(o)). By taking g = Pr, we have g( 1) = 1, and we see that p is decomposable with Ttx, Y) = P?tP,tx) + Prty)). 578 GOODMAN,NGUYEN,ANDRoGERS Of course, (ii)*(i). Since p is T-decomposable on a discrete space, we have VA E LqQ), p(A)= T(P(~), WEA). Take P,-= g (noting that we can solve for f), we have PpPc(~)=dm4~)? meA) = g [g* (; g(cw)] =; dP(W)) since, by hypothesis CA g(p(o)) < C, g@(w)) = 1 = g( 1). Thus Pro ,u is a a-additive probability measure. 1 Remark. In view of the above theorem, we see that if p is T-composable (or equivalently, if p is generated by its restriction to singletons and T) and if p is general admissible in the o-additive sense, then p = 6,,, the Dirac (probability) measure at o0 E R when v(wO) = 1. The following result provides a necessary and sufficient condition for p to be general admissible in the o-additive sense when sup, p(o) < 1. THEOREM 5.2.2. Let CC 52 -+ [0, l] with Q countably infinite, such that sup, U(O) < 1 (a f 0). Then a necessary and sufficient condition for the existence of a T-possibility measure ,u, generated by c1 and some T, which is general admissible in the o-additive sense, is that VXE(O, 11, a-‘[x, 1]={o:x~fx(o)~1} (**) is finite. In particular, if S is finite and sup, M(W) < 1, then there exists T such that pa,= is general admissible in the o-additive sense. Proof: (a) Necessity. If there is X,,E [O, l] such that cr-‘C.-C,, l] is infinite, then lim 1 g(Ao))= + ~0, n-t +m 4 where A,cc~[x,,, 11. For, although A, is finite, and A,~c~[x,, l] for each n > 1, & g(p(o))>g(x,) [A,(. Thus (*) of Theorem 5.2.1 will not hold. (b) Sufficiency. In view of Theorem 5.2.1, we need to show only the existence of a generator g such that g( 1) = 1 and Cn g(a(w)) = 1. Then we SCORING APPROACH TO ADMISSIBILITY 579 can take pd, r(A) = g* [CA g(cl(w))], where T is the Archimedean t-conorm with generator g. Let O0)={~:01(~)>O}=U~~~K,, where K, = {o : l/n < a(o) d l/(n - l)}, n > 2. Let n, k 2 such that l/n, < x0< l/(n,-- 1). By (**), cr-‘[l/n,,, 1) is finite; thus (a(u) :coEKno} = 1 Xl 9 x2, . ..1 x,~} for some n, . We can assume 1 1 - a(d) =x,, , then 0” E K,,. and hence contradicts the definition x,, = M$x a(w)). Since [0, 1 ] = [0, l/no] u (l/n,, 11, we first construct g on [0, l/n,]. For n an, and r>O, define g,(O) = 0 and Then l/m < l/n =z. g,( l/m) < g,( l/n) and lim, _ o. g,( l/n) = 0. Thus we construct a continuous, increasing function on [0, l/n,] by extending g, continuously on each [l/n, l/(n - l)], for n > no, (say by joining g,(l/n) and g,( l/(n - 1)) by a straight line). On [l/n,, 11, we proceed as follows. Let a(r) = 1 s,(a(o)). G Since x0 E K,, K&= {o : a(w) < l/n,}; i.e., for OE K’n,, a(o) e [0, l/n,], which is the domain of g, defined above. We have OGa(r)= +c” 1 g,(a(o)) n=n,,+l K. < y (lK,l)g, < +f 1 n=ng+ 1 n=no+l (n- 1)’ Thus lim, _ o1 u(r) = 0. 580 GOODMAN, NGUYEN, AND ROGERS Let r be large enough so that where C,=a-‘(xi)cK,,,, Vj= 1, . . ..n.. There exist real numbers yj, j = 1, . ..) n such that max(,(,),g,(~))o, j=l j= 1 Thus qo 1, T, is an Archimedean t-conorm with generator g,(x) = xp, g,( 1) = 1. As usual, we extend T, to n arguments, as T,(x,, x2, . . . . x,) = T,(x,, T,(x,, . . . . -4). Then for each fixed n, T,(x,, x2, . . . . x,) + Max(x,, x2, . . . . x,) as p + + cc, uniformly in (x,, x2, . . . . x,). Indeed, since we have Max(x,, x2, . . . . x,1 d T,(x,, x2, . . . . x,) < Min[Max(x,, . . . . xn)n’Ip, 11 0~ T,(x,, x2, . . . . x,) = Max(x,, x2, . . . . x,) d nlip - 1. Thus, if Q is finite, and CL: Y(Q) + [0, l] has Max(x, y) as composition law, i.e., VA C Q, p(A) = My P(W), 582 then GOODMAN,NGUYEN, AND ROGERS uniformly in A. Now, it is easy to see that, in Theorem 52.1, if we require only general admissibility in the additive sense (which is equivalent to uniform admissibility) the condition (*) can be weakened to Thus, assuming in addition that En p(w) < 1, for all Vpa 1, v,(A) = T,(p(o), o E A) is general admissible in the additive sense, since Therefore, in this case, Max-possibility measures are uniform limits of general admissible T,-possibility measures. More generally, for Sz countably infinite, and a: D + [0, l] such that sup, a(o) < 1, the max-possibility measure generated by tl is Pa(A) = sup a(o) A and this can be approximated by admissible measures, Specifically, THEOREM 5.2.3. Let l2 be countably infinite and a: Sz + [O, l] such that sup, a(o) -C 1. Suppose that there are non-negative reals a, b such that Then (i) For A EP(Q), such that Aa-‘(t, p=(A)=lim,,, +m p,,=,(A), the limit being uniform in all such A with (Al in,, for any fixed positive integer n,; also t, = sup, u.(o). (ii) For Aa-‘(t,)# 0, SCORING APPROACH TO ADMISSIBILITY 583 Proof. (i) We are now going to construct generators g,, for suf- ficiently large p, such that kp(A)=gpl [I g,(a(w))] A are general admissible in the o-additive sense. More specifically, not only is g, such that g,( 1) = 1 and C, g,(a(o)) = 1, but precisely g,(x) = xp on [0, t,], where t, > t,, t, = sup a(0) CT (>O by assumption) and C, = a-‘(t,). First Vp > 0, define g,(x) = xp on [O, t,]. We will extend gP to [0, l] by defining a value for g,(tl) such that tz -==a(3/2)b +f n-(~-b). n=2 2 np n=2 Thus lim, _ + o. @P,3 = 0. Let p be large enough so that @P,3 < $ and f; < l/2() C1) + ) CJ ). Define g,(t,)=(l--~,,)/IC,I. We have t$‘ 0 since f2 > 0). Also, by construction, we have 1 = Qp,2 + ICll &#l) =c gpke4). 52 Thus, if Aa-‘( $3, = T,(a(w), w E A) with 7’,(x, y) = [Min(xP + yP, l)]““. Hence lim, ~ + o. ~~,~$A)=Max(a(o), weA} for any finite A. (ii) For Aa-‘(t,)#@, we have t, = Max{a(o), ok A} < T,(cr(w), o~,4) < 1 and hence I/4z,Tp(4-P12(~)l G 1 -t,. I Remarks. (i) Let (Sz, ~44) be an arbitrary measurable space, and ,u: d + [a,, a,] be general admissible in the a-additive sense with Prop = Q, where Q is a discrete probability measure on (0, ,pP). Then p has the same representation as in the discrete case. Indeed, let B0 CO, countable such that Q(sZ,) = 1. Then VA E &, SCORING APPROACH TO ADMISSIBILITY 585 (ii) A continuous analog is as follows. Let (~2, ~4) = (R, B), ho: R + CO, 11, Fe(x) = Q(( - co, xl) and F,: R --) [a,, a,], F,,(x) = p(( - 00, xl). Since p = P; ’ 0 Q, and P; ’ is increasing, /J is a nondecreasing set-function; hence F, is nondecreasing, and A E 93, p(A) = 9;’ [j,, d(P,o F,(x))]. If, in addition, P,- is differentiable, then P(A) = PF1 j P;-(F,(x)) dl;,(x) . A 1 6. ADMISSIBILITY OF DEMPSTER-SHAFER BELIEF FUNCTIONS Dempster-Shafer belief functions have become very popular in recent years for modeling aspects of expert systems and combination of evidence problems in AI. The purpose of this section is to respond to Lindley’s comments about the inadmissibility of belief functions [16]. For simplicity let C2 be a finite set. A belief function Be1 on P(a), the power class of G, can be defined as follows. Let m: Y’(n) -+ [0, l] such that m(0) = 0, Cscn, m(A) = 1. Then, Bel(B)= 1 m(A). AGE m is the probability allocation for Bel. By the Mobius inversion formula, m can be recovered from Bel, m(A)= c (-l)'"-"I Bel(B), BCA where JA( denotes the cardinality of A. Note that if p: B(G) -+ [0, l] is such that p(sZ) = 1 and VAGQ, 2 (-l)‘“-B’/@)>O Bc_A then p is a belief function. If we think of “sets” as “points,” then m plays the role of a probability mass function, and Be1 is a “cumulative distribution function.” Since Sz is finite, we have Bel(A)= P(Xe.tT(A)), VAEQ, where X is a random set, defined on some probability space (a, 9, P), and taking values in P(s2) with “density” m, i.e., P(B:X(O)=A)=m(A). 586 GOODMAN,NGIJYEN, ANDROGERS Note that Bel(A) + Bel(A”) < 1. We extend Be1 to conditional events s’(Q) as follows. For E, FEY(G), define Bel(E)F)=P(XcEjXGF) when P(Xs F) > 0. For more information on belief functions, we refer the reader to 126, 21, 11, 303. As in Section 5, we consider Gf,, with Pr increasing. By the nature of belief functions, we consider [a,, a,] = [O, 11. Note also that the existence of f such that Pr is increasing is equivalent to that of a (surjective) continuous, increasing function h: [O, 1 ] + [O, 11. Thus, in view of Theorem 4.2.1, p E [0, 1 ] d is general admissible if and only if there is such an h for which h 0 p is a finitely additive probability measure. In discussing the admissibility of belief functions on Sz finite, & = P(Q), it should be noted that the range of a belief function is not the whole inter- val [O, 1 ] ! As we will see, as in the case of fuzzy logics, some classes of belief functions are admissible while others are not. Thus, if DeFinetti’s coherence principle is viewed as a rational way of choosing “reasonable” uncertainty measures, the following analysis will provide criteria for selecting “good” belief functions. First, a simple condition of inadmissibility. THEOREM 6.1. Let (0, d) be a measurable space and p E [0, 1 ] d. Zf there is E, FE d such that I@) = P(F) and AEC) Z ,W”)> then p is not general admissible. Proof. If /J were general admissible, then there would be an h: [0, l] + [O, 11, (surjective) continuous, increasing, such that h 0 ,u is a finitely additive probability measure. Thus and hence h 0 ,u(E”) = h 0 p(FC) which contradicts the hypothesis, since h-’ exists. 1 SCORING APPROACH TO ADMISSIBILITY 587 EXAMPLES. (a) 0 = (ml, 02, w3, m4, w5, w6}. Let E = {wl, w2}, F= {03, w4}. Let m: P(Q) + [0, l] with m(w1) = m(w3) =p, > 0 m(w2) = m(w4) =p2 > 0 m({w,,w,})=m({w,,o,))=p,>O ~({w,~w,~%))=P4~O m({w,Y%))=P,>O ~({%~4))=P,~O m(A)=0 for all other subsets and Pl+Pz+P3+P4+P5+!76=f. We have Bel(E)=Bel(F)=p,+p,+p,. Bel(Ec)=p,+p,+p,+p4+p,, but Bel(F”) =pl +pZ +p3 # Bel(E”). (b) Consider the degenerate belief function focused on A, Bel,(B) = 1 if AcB and zero otherwise. Let B, A # @ and B,A = @. Then Bel,(B,) = Bel,(B,) = 0, but Bel,(B;)=O# 1 =Bel,(B”,). The hypothesis of Theorem 6.1 expresses the fact that p(E”) is not a function of p(E). Thus, an uncertainty measure p is not general admissible if there is no rp: [0, l] + [0, l] such that YE, FE d, AE” I -F) = cpbWl F)). (*) A typical example is the Max-possibility measure (which explains its inadmissibility mentioned in Section 5). The relation (*) always holds for probability measures, but as we have just seen, (*) might fail in the case of belief functions. The Theorem 6.1 provides a necessary condition for general admissibility: If p is general admissible, then necessarily, (*) must hold. The following result provides sufficient conditions for general admissibility of belief functions. THEOREM 6.2. Let l2 be finite and d = P(Q). 409/159/2-20 588 GOODMAN, NGUYEN, AND ROGERS (i) Zf Bel: J? + [O, l] (extended to d as mentioned previously) is such that VE, FE s#‘, with Bel(F) > 0, Bel(E’IF)=q[Bel(ElF)], (**) where cp: [0, 11 + [O, 1 ] is differentiable, then Be1 is general admissible. (ii) For each, r B 1 and Q: STJ’ + [0, 1 ] a finitely additive probability measure, Qr is a belief function on zl which is general admissible. Proof: (i) The proof of (i) follows from [S]: let E,, E,, FE& with Bel(F) > 0. Using the conditional extension of Bel, we have where A: [0, l]* + [0, 11, A(x, y) = xy. We also have Bel(F( F) = 1. Thus, together with (**), Bel’ is a finitely additive probability measure on d for some positive real r. Since (.)‘: [0, l] -+ [0, l] is surjective, continuous and increasing, Be1 is general admissible. (ii) For r > 1 and Q a finitely additive probability measure in 52 (finite), Q’ is a belief function if VAGQ, m,(A)= c (-l)lA-BI Q’(B)>O. BEA For JAI =0, i.e., A=@, we have m,(@)=O. For IAl = 1, say, A = (or>, we have m,(~~l~)=Q’(~~l~)~O. For IAJ =2, say A= {CD,, co,}, mr({~~~~2~)=Q'({ o,,w,>,-Q'((ol>,-Q'((~2}) =CQ({o,>,+Q({o,>,lr-Q'({o,>> -QW4)N. Since the function u(tl) = CZ” + (1 - a)l is such that u(O) = u( 1) = 1 and u( . ) is convex with minimum at LI = i, u(f) < 1, we have SCORING APPROACH TO ADMISSIBILITY 589 For IAl=3, say A={w,~~,w~}, let a=Q{w,), b=Q({w2}), c=Q((c+}). Then m,(A)=(a+b+c)‘-(a+h)‘-(a+~)‘-(b+c)’+ u’ + b’ + c’. Thus m’(A) 3 0 if (a+b+c)‘>(u+b)‘-a’+(u+c)‘-c’+(b+c)’-b’. (*) Now, if r = n >, 1 is integral, then the right hand side of (*) is uibJck, where S = {(i, j, k) : i+ j + k = n and not all the i, j, k are positive}. Thus (* ) holds since a, b, c 3 0 and Sc{(i,j,k):i+j+k=n}. For r > 1, real, we rewrite (*) as (u+b+c)‘+a’+b’+c’~(u+b)‘+(u+c)‘+(b+c)’. (**) Let u(r), w(r) be the left and right hand sides of (** ), respectively. Observe that u(r) and w(r) are convex functions on [ 1, + cc), since Ofu+b+c 1. The above argument applies to the case IAl > 4 as well. 1 Remarks. (i) Of course if Be1 = Q’ where Q is a finitely additive probability measure and r > 1, then Be1 is general admissible by Theorem 6.2 (i): VE, FE .ra2, Bel(E’ 1 F) is a function of Bel(E 1 F), namely cp(x)=(l -x)‘. (ii) We have seen that, in the scoring approach to admissibility of uncertainty measures, if the aggregation function is taken to be addition (as in Lindley’s work), then well-known measures such as Max-possibility measures (which are consonant plausibility functions) and degenerate belief functions are not general admissible (i.e., they are incoherent in DeFinetti’s sense). Although, we have shown that, in this case, there exist admissible T-possibility measures and admissible belief functions, it is useful to consider arbitrary aggregation functions in order to set up a general framework for studying the question of admissibility, i.e., a general concept 590 GOODMAN, NGUYEN, AND ROGERS of coherence. From a logical viewpoint, this is precisely the concern of AZ researchers as well as statisticians dealing with applications of belief functions to statistical inference (e.g., [30, p. 1061071). Section 7 will give some insights in this direction. 7. UNCERTAINTY GAMES WITH NONADDITIVE AGGREGATION FUNCTIONS In this section, some specific nonadditive aggregation functions are considered. In Example 1 it is shown that a simple nonadditive form of aggregation leads to a corresponding uncertainty game for which uniformly admissible measures are not transformable to probabilities; this is in opposition to Lindley’s games with an additive aggregation function. Example 2 presents a situation in which a nonadditive aggregation function has a general additive form. In this case, uniformly admissible measures have probability-like characterizations. In Example 3, we present some specialized cases of Example 2. EXAMPLE 1. Consider a = ((E, 1 F), (E, ( F), (E, u Ez 1 t;)), with E,E,=@. Let x = WI If’), Y = AE2 I J’), z = WI u E2 IF). We will discuss the weak local admissibility of 2 = (x, y, z) with respect to the game GJti,~, where the game is specified as follows. Recall that $: [w, + [w is specified by the sequence Ic/, : BY --t 58, n > 1. For our purpose here, it suffices to consider ti3: R3 + R. We take $Ju, u, w) = uu + w. For the score function f, we take a, = 0, a, = 1 and f(x, 0) =x2, f(x, 1)=(x-1)2 on CO, 11, We are going to show that there is no transform h: [0, l] -+ [0, l] such that h(z) = h(x) + h(Y) when (x, y, z) is WLAD. As a consequence, if p is uniformly admissible, p need not be transformable to a finitely additive probability measure. With the notation of Section 3, we have [ (x-l)y2 (x-1)2y z-l J=2 x(y-1)2 x2+ 1) z-l . XY2 X’Y Z 1 To find 2 = (x, y, z) - WLAD, we use the sufficient condition given in Theorem 3.2.2 (e). SCORING APPROACH TO ADMISSIBILITY 591 First, det J = 0 gives x*+-y*-xy(x+y) ‘(” ‘)= 2(x+y)-3xy- 1 for xy#O, 1. (*) ForO~x~l,y=l,wehavez=1.For~=(x,1,l)withO~x~l,Jhas rank p = 2 with R = (0, 0), and so (x, 1, 1) is WLAD. If h: [0, l] -+ [0, I] is such that h(z) =h(x)-th(y) for any (x, y, z) - WLAD, then, in particular, h(l)=h(x)+h(l), VXE(O, l), implying that h(x) = 0, Vx E (0, 1). From (*), we see that when x= y= i, we have z= 1. For x= ($, i, I), and p = 2. For with and RJ, = ($, -a), we have R = ( - LO), so that f = (4, 4, 1) is WLAD, and hence Now it can be seen that i = (0, 0,O) is WLAD, since P’L and contains one zero component. Thus h(O)= h(O)+ h(O), implying that h(O) = 0. Therefore, h c 0 on [0, 11. 592 GOODMAN,NGUYEN, AND ROGERS EXAMPLE 2. Consider a as in Example 1. Let f be an arbitrary score function and ti3(& u, w) = 4%(401(~) + e(u) + %(W))> where ‘pi: R + R, j = 0, 1,2, 3 are four surjective, increasing, continuously differentiable functions. This is a generalized form of the additive aggrega- tion function. Note that 11/3(~, v, w) = UD + w in Example 1 is not of this form. Large classes of functions of several variables can be represented, or approximated, by general forms of addition of simple argument functions as above; see, e.g., the survey paper of Sprecher 1291 on the work of Kolmogorov and others in considering the related 13th-problem of Hilbert. If $ = (x, y, z) is WLAD then det J= 0, implying that p~p,of(4 = Pqp,&) + p,,of(Y)7 where Pa,&) = dCf(c 011 f’(c 0) cp: Cf(k O)l f’(c 0) - dCf(& 1 )I f’(t, 1)’ EXAMPLE 3. As a special case of Example 2, one can consider uncer- tainty games with symmetric aggregation functions as follows. Let g: R + R be a (surjective), increasing, continuously differentiable function. For n 2 1, define as IClg,ntXIY ae.9 xn)=g-l ,i gtxi) L > The game Gs,*, can be identified with G,,, + , where II/, is specified by $g,n, n > 1. For example, for a fixed p > 1, take gpw = tP for t>O. Note that Max(x,, x2, . . . . However, II/ = Max yields x,) is a limiting case of tigptn when p + + co. essentially only trivial admissible uncertainty measures and hence is not a good candidate for being a viable nonadditive aggregation function. SCORING APPROACH TO ADMISSIBILITY 593 ACKNOWLEDGMENTS We thank D. V. Lindley and L. A. Zadeh for their kind discussion on an earlier draft of this work. REFERENCES 1. J. ACZEL, “Lectures on Functional Equations and Their Applications,” Academic Press, New York, 1966. 2. J. P. AUL~N, A Pareto minimum principle, in “Differential Games and Related Topics” (H. W. Kuhn and G. P. Szego, Eds.), pp. 147-175, North-Holland, Amsterdam, 1971. 3. D. BLACKWELL AND M. A. GIRSHICK, “Theory of Games and Statistical Decisions,” Dover, New York, 1979. 4. L. D. BROWN, A heuristic method for determining admissibility of estimators-with applications, Ann. Sfatisi. 7, No. 5 (1979), 96&994. 5. R. T. Cox, “The Algebra of Probable Inference,” The Johns Hopkins Press, Baltimore. 1961. 6. B. DEFINETTI, “Theory of Probability,” Vols. 1 and 2, Wiley, New York, 1974. 7. T. S. FERGUSON, “Mathematical Statistics,” Academic Press, New York, 1967. 8. D. A. FREEDMAN AND R. A. F?JRVES, Bayes’ method for bookies, Ann, Math. Statist. 40 (1969), 1177-1186. 9. C. GENES AND R. J. MACKAY, Copules ArchimCdiennes et families de lois bidimension- nelles dont les marges sent donnkes, Canad. J. Statist. 14 (1986), 145-159. 10. C. GENEST AND R. J. MACKAY, The joy of copulas: bivariate distributions with uniform marginals, Amer. Statist. 40 (1986), 28&283. 11. I. R. GOODMAN AND H. T. NGUYEN, “Uncertainty Models for Knowledge-Based Systems,” North-Holland, Amsterdam, 1985. 12. I. R. GOODMAN, H. T. NGUYEN, AND E. A. WALKER, ‘*Conditional Inference and Logic for Intelligent Systems: A Theory of Measure-Free Conditioning,” North-Holland, Amsterdam, 1991. 13. D. HEATH AND W. SUDDERTH, On finitely additive priors, coherence, and extended admissibility, Ann. Sfafisr. 6 (1978), 333-345. 14. A. KOZEK, Towards a calculus for admissibility, Ann. Statist. 10, No. 3 (1982), 825-837. 15. R. B. LATTA, Composition rules for probabilities from paired comparisons, Ann. Sfafisf. 7, No. 2 (1979), 349-371. 16. D. V. LINDLEY, Scoring rules and the inevitability of probability, Intern. Statist. Reo. 50 (1982), l-26. 17. D. V. LINDLEY, The probability approach to the treatment of uncertainty in Artilicial Intelligence and expert systems, Statist. Sci. 2, No. 1 (1987), 17-24. 18. C. H. LING, Representation of associative functions, Puhl. Math. Debrecen 12 (1965), 189-2 12. 19. A. W. MARSHALL AND I. OLKIN, Families of multivariate distributions, J. Amer. Stofisf. Assoc. 83, No. 403 (1988), 834-841. 20. D. MCDERMOTT AND J. DOYLE, Non-monotonic logic, I, Artificial Intelligence 13, No. 1 (1980), 41-72. 21. H. T. NGUYEN, On random sets and belief functions, J. Math. Anal. Appl. 65, No. 3 (1978), 531-542. 22. E. REGAZZINI, DeFinetti’s coherence and statistical inference, Ann. Sratisf. 15, No. 2 (1987). 845-864. 594 GOODMAN, NGUYEN, AND ROGERS 23. A. RENYI, “Foundations of Probability,” Holden-Day, San Francisco, 1970. 24. G. SWAY, An algebra of conditional events, J. Math. Anal. Appl. 24, No. 2 (1968), 334344. 25. B. SCHWEIZER AND A. SKLAR, “Probabilistic Metric Spaces,” North-Holland, Amsterdam, 1983. 26. G. SHAFER, “A Mathematical Theory of Evidence,” Princeton Univ. Press, Princeton, NJ, 1976. 27. S. SMALE, Global analysis and economics, I, Pareto optimum and a generalization of Morse theory, in “Dynamical Systems” (M. M. Peixoto, Ed.), pp. 531-544, Academic Press, New York, 1973. 28. D. J. SPIEGELHALTER, A statistical view of uncertainty in expert systems, in “Artificial Intelligence and Statistics” (W. A. Gale, Ed.), pp. 17-56, Addison-Wesley, Reading, MA, 1986. 29. D. A. SPRECHER, A survey of solved and unsolved problems on super-positions of functions, J. Approx. Theory 6 (1972), 123-134. 30. L. A. WASSERMAN, “Some Applications of Belief Functions to Statistical Inference,” Ph.D. thesis, Univ. of Toronto, Ontario, 1987. 31. S. WEBER, I-decomposable measures and integrals for archimedean f-conorms I, J. Math. Anal. Appl. 101 (1984), 114-138. 32. L. A. ZADEH, The role of fuzzy logic in the management of uncertainty in expert systems, Fuzzy Sets and Systems 11 (1983), 199-227. 33. L. A. ZADEH, Possibility theory and soft data analysis, in “Mathematical Frontier of the Social and Policy Sciences” (L. Cobb and R. M. Thrall, Eds.), pp. 69-129, Westview, Boulder, CO, 1981. 34. T. L. FINE, “Theories of Probability,” Academic Press, New York, 1973.