Reasoned Assumptions and Pareto Optimality

Reasoned Assumptions and Pareto Optimality*

Jon Doyle

C01n puter Scienr.r Department Carnegie-Mellon University l'itt·hurgh, Pennsy lvania 15213, U.S.A.

2. What are reasoned assumptions for!

Abstract

Defau lt and non-monotonic infe1·ence rules are not really epis­ ternological statements, hut are in~it~ad desires or pr<:f<~rences of t.he agent. about. the trJ akcup ol' its ow11 uwntal st.at.e (epbt,crnic or oLhcrwiHe). Th<' rundaJJICrtl..a.l relation in 11011-fll{)fJOiouic logic i~ not so 1!1Udl ""lf-knowl<!dgc as self-choice or sdl'-detcrminalion, and the fu nJamcntal justilkation of the int.erpretati<)n'!. and structures in­ volved coniC from decision theory and cconc.mics rather than from logic a nd epistemology.

l. Introduction

Non-monot,onic logic and other formula.l,ions of non-rnonoLonic rca..~on ing sehemc~ have usually been prcH(~ nted a .. 'i stu die~ of a logi­ r.al or cpisicrnologi,:a.l topic, that is, conc:err.ed with bt·lief, self­ knowledge, and self-consistcney. While some t.opics in th<! litera­ ture arc proper ly logi<:al orws (ror exarnplc <:ireum~cription ---scc [DOYLI<: 1981]), r<!ccnt work 011 rea.·oncd all·urnptinns (ii>OYLE 1982]) i11dicatcs that non-monoto11ic logic and reason maintenance arc more p·ychological topics than logical or r.pistcrnological ones, and arc closer to cconom ics and decision thmry than to logic. This paper reviews the work on rca-·oned a."sumptions to point out Lhcsc connections. Rel ated con!'\idcraLions appear to motivate recent work by llorgida and lmiclinski it 984], who relate non­ monotonic logi c to committee decisions but do not draw on the decision-making Jitcra.t.ure.

To sumrn :\r iw the present view, default rules and non-mono· tonic infcrcnr.e; arc not really epistemological statements (such as generalizations and inductive hypotheses from which one draws conclusions in a statistical or inductive logic), but arc instead desires or preferences of the agent about the makeup of its own mental state (epistemir. or otherwise). The fundamental relation is not so much "''If-knowledge as self-choice or self-determination, and the fundamental just ification of the interpretations and struc­ tures involved come from decision theory and economics rather than from logic and epistemology . Self-consistency is prominent in non-monotonic logic simply by accident, b~causc it is one con­ venient encoding of prescnc" and absence of beliefs within the logi­ cal language, not because the issues involve il. Other cncodings do not involve self-consistency at all (sec [DOYL~; 1982]).

· @ Copyright 1981 , 1985 by Jon Doyle. This rescarr.h was sup­ ported hy the Defense Advanced Rescareh Projeds Agr.ncy (DOD), ARI'i\ Order No. 3597. monitored by the Air Forre Avionics Laboratory under Contract 1·'3:W15-81-K - 153!J. The views and con­ clusions contained iri this document are those of the author, and should not be interpreted as representi ng the omcial policietl , either cxpr<'sscd or implied, of the Defense Advanr.ecl Research Projects Agency or the Government of the United States of America.

One basic problem faced in thinking about what to do is that there arc too rrHU·Y things to think about, and not enough (or too much) known about them. One approach to this problem taken in artificial intelligence i· to reduce Lhc required efTort and circumstantial uncertainty by using "habitual" rules of thumb. Standard &~sumptions are ·Js~d to r€move uncertainties (rnlc· of anti-agnosticism), and standard decisions arc used to resolve con­ flicts (rules of anti-confusion). These rules of thumb arc either formulated ahead of time and applied when needed to get the assumptions and decisions, or are formulated and applied when needed, or both. Th~~e rules of thumb have many applications in artificial intelligence system·, especially as sources ol' defaults and expectations in plans, frames, and inheritance hicrarchiC!I, but we will not go into any applications here.

3. What are reasoned assumptions!

We con·ider her<' only a very simple sort of rule of thumb, the .·im11lc rw.·on. A simple re;~'on ;\ II H If- C (read "A witl10ut /J ~ivcs G 11 ) mean~, iu the <:a.Hc that. A, 1.1, and Care ~wt~ of pol.f!niia.1 hdids, that the items in C should be believed if each ol' those in ,\ arc bdir:ved a.nd none or Lho!-'c in /J arc believed. ConeJugionM drawn from ~implc rca..~OTIS are ealled rea:wued a.'lo'IU11tTJtion.OJ, rca~JOncd bc­ ca.uHc they arc derived f'rom rca:.iOII~, and a.:mumptiot1H bcca.u~c they may depend on the absen<:e of defeating or qualify in~ information. Simple rca .. ·.;ons have corrcspondiug mcaitillg~ in case other mental clcmcnl~ like desires, intentions, concepts, rear~, etc. arc involved, but we treat only the case of belief to simplify the discussion.

For example, one simple rea.,on might be

If- {lJEl,(Frcd can fly)}.

The intent of this reason is to make the assumption that !<'red can fly as long as there arc rca.·ons for bel ieving that Fred i:1 a hird anci no known reasons for believing that Fred can't fly.

The precise interpretation of a simple reason has two principal parts. The first partial interprdation is as one of the agent's sclf­ spccificat.ions, as a possibly non-monotonk "cimmrc rondition" on the agent's set of beliefs. We say that a mental state iH admis·ible (with rc"pcct to simple reasons) ifT it satislies ear.h of its component simple reasons. That is, a state S is admissible just in case for each simple rea.·on rES, if A(r) ~Sand B(r)n S = 0 , then C(r) ~ s.

For example, let So = {0 II {1} !f-· {2}, 0 I! {2} If- {1}}, where I and 2 stand for fJOssible beliefs. Then So i.' not admissible, but its three supersets 5 1 = s~ u {1 }, S2 = Sou {2}, and 812 = SoU {I, 2} arc admissihle. 5 1 , 5 2 , and Su arc called expansion· of S 0 . (Expansions are just admissible supcrsets. [DOYLE 1982] uses the t.crrn ({extension" instead of expansion.)

The ~e<:ond partial int.t!qHPiaLion of a ~imple rea..~on i~ a. . ~ one of the agent'~ re~trid, ion~ on deriva.hility or arguabilit.y of eonclusions, that, is, a. .... non-morwtoni<: "inf<·reru:e records." 'A'c ~ay that a. ~tate /~' is an culmi.'f.'fiblr: expanl·ion of a ~et S iff eaeh dement of the sta.t.c is "grounded'' in 8. There a.re ~<·vera! diflCrent interesting notions of groundedncss. The two principal ones are local groundedncss, in which each clement has an immediate argument from 8 and E, ancl ,'flrict groundcdncss, in which caeh clement has a noncircnlar argument from 8 alone. Formally,];' is locally grounded in S just in case for each x E J~.J~, either x E 8 or x E C(1·) for some r E E with A(r) ~ /~ ~ [H(r)J'. E is strictly ground~d inS just in c"'>e for each x E ];'there is a finite aequcnec (go, ... , Yn) of clements of 8 such that x = Yn and for each i :S n, either g; E S or there is some j < i such that(!) g; E C(gj), (2) for eaeh y E A(gj), y = Yk for some k < j, and (:!) z 9'0 E for each z E B(gj)·

Continuing the example above, 8 1 and 82 arc each locally and strictly grounded in So, while 812 is not locally grounded or strictly grounded in So, but is locally (;rounclcd and strictly grounded in itself. Let 8b ={{I} 110 If- {2}, {2} II v> I~- {1}}, 8~ = Sb u {1}, S~ ~~ S'b LJ {2}, and 8'12 = Sb U {1,2}. Then only 8~2 is an expansion or Sb, and it is locally but not strictly grounded in Sti. Moreover, 8' 12 is strictly grounded in each of S\ and 82.

The theory of simple reasons, clements of which arc developed in [DOYLll 1982], reveals several important fact.s about the struc­ ture of admissible expansions. Recall that one can intuitively inter­ pret each simple reason a.· a wrt of closure condition. One theorem is that these "local" clo~urc <'.onditions can be combined into one "global" one. That is, the strictly grounded expansions of a set at·e exactly the fixed points of a natural "closure" operator. These fixed points arc not always limit,, of the operator, and non-limits arc sometimes non-computable (as in non-monotonic logic). But conn;ptually, thi· result. permits ouc to think of strictly grouncl­ eJ expansions a.· equilibria. From this point of view, they are reminiscent or the more abstract notion of "reflective equilibrium" described by Rawls [1971]- the conscious agreement of principles and judgments-·-and of the decision-theoretic nol.ion of "ratifiable" decision proposed by Jeffrey [1 !183]·-dceisions rationally chosen for the person one expects to be once one has chosen. In the follow­ ing, we will sec that these similarities to nominally political and economic theories are no accident.

4. Group decision making

The furul:uncntal problem in the theory of group decision­ rnakillg is that, of cwnhining individual att.iiudcs (beJiefH, prcfcr­ eru:es, cL<:.) to gel Uw corre~ponding att,itudeH or the group. Po\\gtcr~, elcd, ion~, markets, and committees are some of the most respec:ied mean~ commonly used; burcauc:rats, politicians, dic­ tators, and prophets arc other means. The underlying theory de­ veloped by economist" abstrad.s from the burly-burly of actual decision-rna.king in groups of people by studying "decision rules," mat.hernatical funetions that desrribe the input-output behavior of decision (>TOCe8ses, the inputs being the attitudes of the individuals, the outputs being the re,ulting group attitudes. Due to the abstrac­ tions commonly used, !'conomists typically discuss only the <:asc of combining individual preferences to get group preferences, and we will also conccntrat.e on that. case here. (Sec [ARROW 196:l] and [D EBIW U 195!J] for classk treatments.)

Economists abstract from humans and other biological species and base their theories on a creature ealled hom'o economir.us, or economic man. ~conomic men (a.nd presumably ceonornic WOfllP.Il and children too) arc marvels of consist.eu<:y and calculation, but their powers of calculation arc not relevant here. For our purposes, the most. important property of the economist's abstraction is it requirement of consistent preferences. We write x < y to mean that the agent prefers x to y. If the agent is an economic man, then its preferences :>re consistent, that is, it does not prefer x toy andy to x. Econornic man's preferences arc also transitive (x < y and :~ < z cnta.il ,: < z). If ncithPr x < y nor y < x we say that the agent is indifferent about the choice of x or· y (or in the common corruption, "x and y arc indifferent.").

In the theory of group decision-making, r:ach individual is internally consistent in the above sense, but different individuals may contradict. each other. Tbat is, as long "-" Alice and Bob are individually consistent, we may have in some case that x <Alice y and y <Bob x. !"deed, if we never did, group choice would not be a very interesting topic . But people do disagree, and group choice is diffictdt for t.hc theory requires that group preferences be consistent "-" well, that is, that the results of choice result in a composite economic man, a "group individual." The conflicts must somehow be resolved.

In mathem:·.tical form, the ilu~ory of group deci~ion-makin~~ coll:·dder::; f'unctioiiH (deeision rult~H) f'rom set!-! of consistent. sets or prcl'creru:t~8 (tho~c of the group lrl<'lllher~) io <:on~i~tcnt RCt:i of prc:ferenn's (tho·e of t.he ~roup as a whole). In addit.;on to rc~trictiug; the input and output pref'en ~ nce set~ to he con~ist.ent, the t.hcory also "'"trids the oort." of fundions allow<·d. This is done because there are many dec:ision rules the ccollomiHi deems uninterl'sting or urHkHirablr. For ex:!.mple, one such rule is the rule of ua.pa.thy," namely l,hc rule yielding the <:onstant r-e:-,ult of t.hr. empty set. of preferences. !I avin!; no preferences a t. all is perfectly consistent., and this rule say~ t.ha.i all groups arc indifferent about all choices. Tlli:-> ~ori of rule i~ noL very useful in practice, and to avoid it (among ot.lH~ rs) the economist restricts consideration of decision rules t.o those satisfyin~ t.he Pareto condition (named after Vilfrcdo Paret.u, an ltaliau economist of the last century). The Pareto condi~ion is tha t if all members prefer x Loy, then the group prefers x to y, that, is , the group agrees with unanirno~>s opinion. The rule of apathy fails to satisfy this condition, since it admits no group preferences, even when the inUividua!s arc unanimous.

l'arcto optimality i" an even stronger condition than the Pareto condition. Paret.o optimality means the group preferences agree with as many individual preferences a." possible, or more prcci·cly, that any change to the group preferences that better satisfies one member must ·atisfy another member less. Satisfying the Pareto condition implies Pareto optimality when agents arc never i11difTcrcnt. To sec this, suppose the group preference· include x < y, and that Ali<:e I> as the opposite preference, y <Alice x. Since the group preferences satisfy the J>areto eonditinn, we know that some other member rnust disagree with Alice. Othcrwi·e, the mem­ bers would be unanimous about y < x, and the group preferences would have to agree. Let us a.·sume x <neb y. Then it. is easy to sec that if we changed the group preference to y < x t.o make Alice happier , we would violate Bob's preference and make him unhappier. That's Pareto optimality.

5. Reasoned assumptions and Pareto optimality

w~ :tr<' !lOW ill a posilioll to i11di<:ale the Ji11k helwee!l these t.opif~~ - Con~idt>r a group de<:ision c:onccruing iuvit.at.ion~ t..o a party. We a."'':-ttJIJJe thai each per~c.m ]J haH a very Himple Ht~ L of prP.fereru~eH, whirh W<' abbreviate :L· A{p) II /J(I') If- C{p), """'"i11g that p prefers set.· 8 of i11vitations that saliHfy the condition

to those sets not satisfyi11g this co11dition, a11d is indifferent to choices within these two cla.·scs. We might express r·'s preferences a.· "if we i11vitc the A's and don 't i11vite the /J's, we should invite the C's." What arc reasonable choices for i11vit.alions if we take the preferences of the guests "-" seriously as the preferences of the hosts?

This decision about party invitations should look familiar. It is uot hard to prove that with these individual preferences, the Pareto optimal sets arc exactly the admissible stales defined earlier. {[DOYLE 1982] employs the term "sati·faction optimal" for this result.) Put another way, interpreting sirrople reasons as preferences about mental states leads naturally to tbe idea of admissible states, and to the interpretation of mental states as decisions by the agent about what to be. The moral is that reasoned a.·sumptions are economic entities. {This docs not exclude them from being logical or other sorts of entities as well.)

It is worth noting that these interpretations take some liberties with the standard formulations of group decision-making. In our applications, th" group membership may vary with the choice, and preferences about preferences {reasons about reasons) arc basic. These differences lead to an interesting extension of the usual economic theory {in preparation).

One may carry the economic interpretation of reasons further. Consider agents like the party-goers before, except that among the sets of invitees satisfying the individual conditions, these folks prefer ''validating" satisfying sets to "invalidating" satisfying sets, that is, p prders sets S such that A(p) ~ S ~ [B(p)]' to those failing this condition. With these more refined preferences, one can prove that E is Parete optimal among the strictly grounded expansions of 8 whenever 11· is a strictly grounded expansion of S. (Sec [DOYLE 1982] on validity optimality.) I do not know if the converse is true, but the moral here extends the previous one. Not only are the admissible menta.) ~tatcs natura.) economic entities, but the derivability relation of strictly grounded expansion is an economic notion as well.

6. Rellectiona on economic theory

T'lu:~ preceding ha.H indieat..cd the economic nature of Home im­ port.a.ral.. notion~ in arlific:ial int.dligcru~c. lu t.hi~ MCct.ion, we draw MOITH~ cooduHion~ about t..lw role of economi<: theory in a.rt.illcial in­ telli~cne<:, :tnd about the possible inllueJH:c of artifkial intelligence on <·con om ic theory .

l·'if"l , the identification of rca.'!>ncd "-""lllnptions a.' the results of 1~rot1p choices constitutes a substantial regression of the usual theory of individual choice. Current economics is based on the cconom ic man idealization of humam. Since humans fall short of this ideal , some people arc tempted !.o dismiss economic theory as llselcHs if not wrong. But !.he previous discussion suggests that whatcvn their value "-' a model of humans, the sta11dard idealiza­ tions of <"conomics may be quite useful at a lower level than the whole ht~man. Tlw elementary building blocks (e.g. rea.~ons, proce­ dures, etc.) may all be consiMLcnt., if ~implc, individuals, with 1norc complex me11tal facu lties and tlu· mind as a whole stemming from the activity of these clements, that is, as group choice (sec [DOYI,I·; l!l8:!u]). Mi11sky has urged something like this view for years with his "society of mind." It is instructive to find a very similar proposal {even including some neurodevclopmental epistemology) in the works of the economist Robert Mundell [1968, Cu. 18]. Once one grasps this point of view, it becomes clear that much of artificial intelligcucc has labored under an enormously restrictive methodol­ ogy, that of seckil!g purely bureaucratic organiz::.tions. With few exceptions {notably Minsky's "hcterarchy" and society theories, pcrrc·pt.ron-cla.'9 tlJI·orics, and more rrcently the work of Thomas Malone), artificial intelligence has ignored market-like structures, which appear to have great information· transmission advantage:~ over bureaucracies in rna.ny circuJnst.a.ncc!s. Bureaucratic organiza· tion may be best for large numbers of specific computational prob­ lems, but it seems uurcasonable to i~;nore other organizations for tasks as complex as thinking until that. is shown to be reasonable. This ignorance is especially dangerous if one attempts to adapt artificial intelligence ideas to the design of human organizations.

If the <!c:onomic: inicrprcialion of f<'asoncd :L'iMIIrnpiion:\ pro­ vide~ a role for Hta.nda.rd economic Lhcory in ariifir.ial iniclliJ~<~ IH:c, other art.i[icial intelligence not,ion:; might be u:-;ed io broaden t!CO­ nomir t.heory. l·'or example, non-monotonic rulcH of rca. .. 'ioning arc perv:c·ivc in art.ifidal int.elligcnno, hut viol:tte most of the c<:ononlist..'H idealizing axioms. Speciflcally, an n.gt!nl. based 011 the theory of ·im ple rea.·ons v iolatcs axioms :thou t the eonsistency and transitivity of prcfcrenrl.':ll and about. l.lu· indcpcndeJu:c of irrelcv:tnt alt.erna.tiv~s. A simple rea.Mons agent may easily accommodate conflicting preferences {defaults) . and cumc to dill(,.enl. {possibly inconsiRt.enL) conclw~ions dcp<:nding on the complete set of reasons involved. Thi· i·n't some undesirable sidc-cflc<:t of t.he artillcial in­ telligence ideas. These properties arc wl.at non-ononolonicity is all about. gvcntua.lly artificial intclligeilf.C may provide ucw idealized psychologies on which to baH<' economics, psychologies"-" precisely formulated as that of homo et:onomicu>, bul mtH:h closer to the informational, computational, and logical limitations of humans. I am studying such possibilities in my work on ra.t.ional psychology, and a comprehensive treatment is in preparation.

7. Conclusion

We have seen how the important artificial intelligence concept of reasoned a.'"umption has a natural economic interpretation, in which rca.·ons and defaults express preferences of the agent about the composition of its own state of mind, and in which the ad­ misBiblc states of mind are the results of decisions based on these preferences.

As a final note, we remark that because artifir.ial intelligence agents are non-atomic and these decisions are group decisions, the results may be ambiguous in the sense that several incomparable outcomes arc possible. {In fact, except in dictatorhtl organizations, such ambiguities may be hard to avoid.) [DOYLE 1982] shows how one may develop a theory of degree of belief or subjective probability by measuring these ambiguities. This "epiphenomenal" role for subjective probabilities appears to fit t.hc practical needs of artificial intelligence much better than the "foundational" role given to them in standard applications of decision theory, as the qualitative information used in reasons is often easier to obtain and to modify than the quantitative information derived from it. See [DOYLE 1983A] and [DOYLE 1983c] for more on this idea.

Acknowlcgemcnts

Thi" paper iR baRed on a talk preRcnted at the CSLI Workshop on Planning and Pradit:al ltca"o11ing, Stanl"ord lJ11ivcrRity, June l!lH1 . I thank .JoReph Srh:d., for his advir.e and '"'""""ntH, and Monnett llanvey and one of Uw IJCAI referees for diseovering an error in an earlier draft..