<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Language-based decisions</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>2021 June</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10238280</idno>
					<idno type="doi"></idno>
					<title level='j'>Proceedings of Eighteenth   Conference on Theoretical Aspects of Rationality  and Knowledge (TARK)</title>
<idno></idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>A. Bjorndahl</author><author>J. Y. Halpern</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[In Savage's classic decision-theoretic framework, actions are formally defined as functions from states to outcomes. But where do the state space and outcome space come from? Expanding on recent work by Blume, Easley, and Halpern [2006], we consider alanguage-based framework in which actions are identified with (conditional) descriptions in a simple underlying language, while states and outcomes (along with probabilities and utilities) are constructed as part of a representation theorem. Our work expands therole of language from that of Blume, Easley, and Halpern  by using it not only for the conditions that determine which actions are taken, but also the effects. More precisely, we take the set of actions to be built from those of the form do(phi), for formulas phi in theunderlying language. This presents a problem: how do we interpret the result of do(phi) when phi is underspecified (i.e., compatible with multiple states)? We answer this using tools familiar from the semantics of counterfactuals; roughly speaking, do(phi) maps each state to the ``closest'' phi-state. This notion of ``closest'' is also something we construct as part of the representation theorem; in effect, then, we prove that (under appropriate assumptions) the agent is acting as if each underspecified action is first made definite and then evaluated (i.e., by maximizing expected utility). Of course, actions in the real world are often not presented in a fully precise manner, yet agents reason about and form preferences among them all the same. Our work brings the abstract tools of decision theory into closer contact with such real-world scenarios.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Motivation</head><p>In Savage's classic decision-theoretic framework [12] actions are formally defined as functions from states to outcomes. States are conceptualized as encoding the possible uncertainty the decision-maker may have about the world, while outcomes correspond intuitively to the payoff-relevant ways things might turn out. Thus, an action &#945; can be viewed as a kind of long list: for each way the world might be (i.e., each state s), &#945; specifies what will happen-namely, the outcome &#945;(s)-in case action &#945; is actually performed in state s.</p><p>One might ask: where do the state space and outcome space come from? Is it reasonable to model an agent using a mathematical apparatus they presumably have no access to? Questions like these tap into a long tradition of challenging the idealizations involved in models like Savage's (see, e.g., [1, 2, 4, 5, 6,  7, 8, 9, 10, 14]). One response might be that we are not trying to duplicate the decision-making process going on "in the agent's head", but rather to represent it, mathematically-to show that under certain conditions it can be tracked with a certain type of formalism (in this case, as a form of expected utility maximization).</p><p>Although this reply might assuage some worries about the use of abstract mathematical frameworks for reasoning about decision making in general, it remains problematic that actions-the objects over which agents are supposed to "reveal" their preferences, through concrete, binary choices-cannot themselves be described except by reference to the background state and outcome spaces, which might not be the states and outcomes that the agent is actually thinking of. In such models, although outcomes are what agents are supposed to ultimately care about, actions are the means by which they bring outcomes about. This makes an agent's preferences regarding actions arguably the closest point of contact that these models have to the empirical, observable reality of choosing between alternatives. Indeed, this interpretation of actions is what underlies many of the intuitions brought to bear to justify the various axioms of decision making that Savage postulates and relies upon to prove his celebrated representation theorem.</p><p>The concern with where the states and outcomes are coming from motivated Blume, Easley, and Halpern [3] (henceforth BEH) to consider a model where acts and language are taken to be primary in a sense that we explain shortly, while the state and outcome space are constructed as part of the representation rather than specified exogenously. In more detail, BEH assumed that acts were programs in a simple programming language formed by closing off a set of primitive programs using if . . . then . . . else . . . , so that if a and b are programs and t is a test (intuitively, a formula in a propositional language), then if t then a else b is a program. Thus, rather than conditioning actions on events (i.e., subsets of a state space), they are conditioned on descriptions of events, namely, tests. This approach allows BEH to not only circumvent a fixed, exogenous specification of the state space and outcome space (instead, they are constructed as part of a representation theorem, and programs are identified with maps from from these states to outcomes), but also (as they illustrate with several examples) makes it possible to capture a variety of framing effects, which basically derive from a mismatch between how the modeler conceives of the world and how the agent does, as manifested in different ways that descriptions of events might map onto actual events.</p><p>Our work is perhaps best understood as an extension of their work in which the role of language is even more central. Specifically, while BEH allowed arbitrary primitive programs, we take the primitive programs to have the form do(&#981;), where &#981; is a formula. The do(&#981;) notation follows Pearl [11]; intuitively, do(&#981;) means that the agent somehow makes &#981; true. Note that this action is somewhat underspecified; it does not say what else becomes true as a result of &#981; being true; for example, if &#968; is independent of &#981;, it does not tell us whether &#968; or &#172;&#968; is true. In our representation theorem, we assume that the agent has a way of specifying the effects of do(&#981;). In more detail, we take states in our state space to be characterized by formulas in the language (this is similar to the canonical model used in BEH's representation theorem), and take the outcome space to be the same as the state space, so that a program maps states to states. As part of the representation theorem, the agent must decide what state do(&#981;) maps each state &#969; to. We follow standard approaches to giving semantics to counterfactuals [13]  by taking do(&#981;) to map &#969; to the "closest" state to &#969; (according to some measure of closeness) where &#981; is true. Of course, what counts as "closest" depends on the agent's subjective view of the world, and is constructed from their preferences over acts.</p><p>This approach allows us to model choices in a way that seems to us closer to how agents perceive and reason about the options available to them. To illustrate, consider a policy-maker trying to decide whether to raise the minimum wage to $15 or to leave it as is. In our framework, this amounts to comparing the acts do(MW = $15) and do(true) (where do(true) amounts to doing nothing). Of course, different agents may disagree about the side-effects of increasing the minimum wage (businesses may close, there may be more automation so jobs may be lost, and so on). This amounts to saying that different agents will interpret do(MW = $15) differently as a function from states to states, although all will agree that it will result in a state where the minimum wage is $15. <ref type="bibr">1</ref> We can also express contingent policies in our framework, for example, raising the minimum wage if the economy is healthy.</p><p>By making both the acts and the test conditions formulas, we can capture framing and coarseness effects not only in the test conditions, but also in the choices. For example, we might imagine agents reacting differently to statements like "we will require that every citizen is paid at least $15 dollars for each hour they work" versus "we will require every business owner to pay their employees at least $15 for each hour they work", even if we can see that these are equivalent statements. Our framework would allow this.</p><p>The rest of this paper is organized as follows. We present our approach as an extension of the work of BEH. This has the benefit of allowing us to apply their representation theorem directly and focus our efforts on the novel aspects of our extension. We begin in Section 2 by reviewing the relevant definitions from BEH and augmenting them with the new ones we need to capture language-based, underspecified effects of actions. Then in Section 3 we articulate the representation theorem we are aiming at, introduce decision-theoretic axioms that allow us to achieve it-including axioms from BEH (Section 3.1) as well as several new axioms (Section 3.2)-and finally prove the theorem (Section 3.3). Section 4 concludes with a discussion of future work. Appendix A collects proofs omitted from the main text.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Language, Actions, and Models</head><p>Our first step is to import the relevant definitions from BEH so as to present our extension of their work in context. In order to emphasize the changes that we make and to streamline the presentation, we alter some of their notation and terminology, and focus on the special case of their system without randomization.</p><p>Let &#934; denote a finite set of primitive propositions, and L = L(&#934;) the propositional language consisting of all Boolean combinations of these primitives. Although of course it is possible (and interesting) to consider other languages, in this work we focus on languages of this form as the underlying language of action-intuitively, the language in which both the conditions and the results of actions are specified.</p><p>A basic model (over</p><p>where &#8486; is a nonempty set of states and</p><p>The valuation is recursively extended to all formulas in L in the usual way. Intuitively, [[&#981;]] M is the set of states where &#981; is true. Using [[&#8226;]] M allows us to interpret descriptions in the language L (what BEH call "tests") as events: &#981; is interpreted as the subset [[&#981;]] M &#8838; &#8486; of the state space &#8486;. We sometimes drop the subscript when the model is clear from context, and write</p><p>] M = &#8486;, and write |= &#981; to indicate that &#981; is valid in all basic models. Finally, we define the theory of &#969; (in M) to be the set of all formulas true at &#969;, denoted T h(&#969;) = {&#981; : &#969; |= &#981;}, and write &#969; &#8801; &#969; iff T h(&#969;) = T h(&#969; ).</p><p>Up to now, everything we have defined has followed BEH exactly-their "primitive tests" are our primitive propositions &#934;; their "tests" are our formulas L(&#934;); their "test interpretations" are our valuations [[&#8226;]] M . Next we define our version of their "primitive choices". This is where our development begins to diverge, since we take these to be actions of the form do(&#981;); in other words, we specify primitive choices using the same underlying language L(&#934;) that corresponds to tests, rather than treating them as a brand new set of primitives.</p><p>Formally, given a finite set of formulas F &#8838; L, the set of actions (over F), denoted by A F , is defined recursively as follows: for each &#981; &#8712; F, do(&#981;) is an action (called a primitive action), and for all &#968; &#8712; L and &#945;, &#946; &#8712; A L , if &#968; then &#945; else &#946; is an action. Following BEH, we take F to be finite (who take the set of primitive choices to be finite). It is also convenient because it allows us to exclude logical inconsistencies from F, obviating the need to interpret actions like do(false). For the propositional languages under consideration in this paper, up to logical equivalence, there are only finitely many formulas in any case.</p><p>Naturally, we also wish to interpret our actions in a way that respects their connection to the underlying language. This is the topic we turn to next.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1">Selection models</head><p>In a given basic model M, we want do(&#981;) to correspond to a function whose range is contained in [[&#981;]] M , the set of &#981;-states. Thus, we restrict our attention to basic models in which each &#981; &#8712; F is satisfiable-in this case we say that M is F-rich. But this is not enough: as discussed, do(&#981;) is underspecified; it does not in general determine a unique function. In order to interpret such actions and compare them to others, we must in some sense "fill in" the missing details. We formalize this with the concept of a selection model (for F), which is a basic model</p><p>Selection functions were introduced by Stalnaker [13] as a mechanism to interpret counterfactual conditionals. Following this tradition, we think of c(&#969;, &#981;) as representing the "closest" state to &#969; where &#981; is true. There are many other properties one might insist c have, aside from c(&#969;, &#981;) &#8712; [[&#981;]] (which is called success). For example, one may require that if &#969; &#8712; [[&#981;]], then c(&#969;, &#981;) = &#969; (i.e., if &#981; is true in &#969;, then the closest state to &#969; where &#981; is true is &#969; itself); this property is called centering.</p><p>In this paper we will also consider a relatively strong condition on c, namely, that it is derived from a parametrized family of well-orders<ref type="foot">foot_1</ref> on the state space, one for each state:</p><p>which case it is also easy to see that the induced selection function satisfies centering). Finally, we say that &#8804; is language-based if the relations &#969; on the quotient &#8486;/&#8801; given by</p><p>are well-defined well-orders, and moreover, whenever &#969; &#8801; &#969; , we have &#969; = &#969; . Note that in this case &#969; &#8801; &#969; implies c(&#969;, &#981;) &#8801; c(&#969; , &#981;). <ref type="bibr">3</ref> Intuitively, if &#8804; is language-based then what counts as the closest state essentially depends only on the formulas that are true at a state. We cannot have two states &#969; 1 and &#969; 2 that agree on all formulas (so that &#969; 1 &#8801; &#969; 2 ) and a third state &#969; 3 that does not agree with &#969; 1 and &#969; 2 on all formulas such that &#969; 3 is between &#969; 1 and &#969; 2 in terms of distance from some state &#969; (i.e., we cannot have</p><p>The purpose of the selection function in our models is to take an underspecified transition from states to states and "resolve the ambiguity". Specifically, given a transition that starts in state &#969; and ends up in a &#981;-state, the selection function c can then by applied to specify the exact &#981;-state, namely c(&#969;, &#981;), where it actually ends up. In this way, given a basic, F-rich model M, each action of the form do(&#981;) can be interpreted in any selection model (M, c) based on M as a function [[do(&#981;)]] M,c : &#8486; &#8594; &#8486; defined by:</p><p>Of course, we can extend this interpretation to all actions in A F in the obvious way (and exactly as BEH do):</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Representation</head><p>We begin as usual with a binary relation on A F , where &#945; &#946; says that &#945; is "at least as good as" &#946; .</p><p>Following standard conventions, we define &#945; &#946; as an abbreviation for &#945; &#946; and &#946; &#945;, and &#945; &#8764; &#946; for &#945; &#946; and &#946; &#945;, representing "strict preference" and "indifference", respectively. We also assume that is complete, that is, all elements are comparable, so that for all acts &#945; and &#946; , either &#945; &#946; or &#946; &#945;. Although BEH consider incomplete relations, we focus here on the simpler case of complete relations in order to streamline the presentation and highlight the novel components of our model. A language-based SEU (Subjective Expected Utility) representation for a relation on A F is a finite selection model (M, c) together with a probability measure &#960; on &#8486; and a utility function u :</p><p>We note the key differences between the representation theorem BEH establish and what we are aiming at. First, their result produces a separate outcome space and state space, whereas for us, these spaces coincide. More importantly, their result treats "primitive choices" (namely, our actions do(&#981;), for &#981; &#8712; F) as true primitives in the sense that each is assigned to an arbitrary function from states to outcomes. By contrast, we want to respect the structure of an action like do(&#981;)-specifically, its connection to the formula &#981;-by requiring that do(&#981;) correspond to a map from &#8486; to &#8486; such that &#969; &#8594; c(&#969;, &#981;) for a suitable selection function c. One of the novel aspects of our proof consists in showing how to determine the selection function from preferences on acts.</p><p>Since our framework can be viewed a specialization of the BEH framework (with our actions having additional, language-based structure as described), rather than proving our representation theorem from scratch, we can reuse much of their construction. Thus, we will present the same axioms (adapted to our notation) that BEH present, and subseqently augment them with new principles that allow us to construct the selection function.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1">Cancellation</head><p>BEH's main axiom is a cancellation law. Explaining this requires a few preliminary definitions, beginning with the notion of a multiset, which can be thought of as a set that allows for multiple instances of each of its elements; two multisets are equal just in case they contain the same elements with the same multiplicities. For example, the multiset { {a, a, a, b, b} } is different from the multiset { {a, b, b, b, b} }: both multisets have five elements, but the mulitiplicity of a and b differ.</p><p>Given any subset X &#8838; &#934;, let &#981; X = p&#8712;X p &#8743; q / &#8712;X &#172;q. Intuitively, &#981; X is a "complete description" of the truth values of all primitive propositions in the language L(&#934;), namely the description that says for each primitive proposition p that it is true iff it belongs to X. An atom is any formula of the form &#981; X . Since L(&#934;) is a propositional language and we use classical semantics for propositional logic, for all formulas &#981; &#8712; L(&#934;) and atoms &#981; X , the truth of &#981; is determined by &#981; X : either |= &#981; X &#8594; &#981;, or |= &#981; X &#8594; &#172;&#981;.</p><p>It is therefore not surprising that every action in &#945; &#8712; A F can be identified with a function f &#945; : 2 &#934; &#8594; F, defined recursively as follows:</p><p>BEH define atoms in the same way and use them to define functions from atoms to primitive choices just as we did above (replace do(&#981;) by an arbitrary primitive choice). <ref type="bibr">4</ref> Now we can state the central cancellation law that enables us to apply the BEH representation theorem:</p><p>(Canc) Let &#945; 1 , . . . , &#945; n , &#946; 1 , . . . , &#946; n &#8712; A F , and suppose that for each X &#8838; &#934; we have</p><p>Intuitively, this says that if we get the same collection of outcomes with &#945; 1 , . . . , &#945; n as with &#946; 1 , . . . , &#946; n (taking multiplicity into account) in each state, then we should view the collection { {&#945; 1 , . . . , &#945; n } } and { {&#946; 1 , . . . , &#946; n } } as equally good. Thus, if &#945; i is at least as good as &#946; i for i = 1, . . . , n -1, then, to balance things out, &#946; n should be at least as good as &#945; n .</p><p>As pointed out by BEH, Cancellation is a surprisingly powerful axiom. In particular, BEH show that we can use (Canc) to derive many simpler (and more classical) principles of choice: that is reflexive and transitive, that independence holds, <ref type="bibr">5</ref> and that if &#945; and &#946; are equivalent in the sense that f &#945; = f &#946; , then &#945; &#8764; &#946; . (However, it should be noted that Cancellation seems stronger than the conjunection of these axioms.)</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2">Selection axioms</head><p>To present the new axioms that will allow us to construct an appropriate selection function as part of the representation theorem, it will be helpful to introduce some new notation. To begin, we write if &#981; then &#945; as a shorthand for if &#981; then &#945; else do(true). Intuitively, the action do(true) corresponds to doing "nothing", since true is true no matter what, so we might think of "otherwise nothing" as being the default in case no explicit else... clause is given. Of course, for this to make sense we must have true &#8712; F; we make this assumption henceforth.</p><p>Next we define an abbreviation for conditional preference, familiar from Savage's classical development [12]: write &#945; &#981; &#946; as an abbreviation for (if &#981; then &#945;) (if &#981; then &#946; ). <ref type="bibr">6</ref> When &#981; = &#981; X , we write &#945; X &#946; for &#945; &#981; X &#946; , and we extend this notation to strict conditional preference and conditional indifference in the obvious way.</p><p>Our first axiom is related to the centering constraint for selection functions (i.e., that if &#981; is true at a state, then that state automatically counts the "closest" &#981;-state):</p><p>4 Techncially, we are not mapping atoms to primitive acts, but since there is an obvious bijection X &#8594; &#981; X beween sets of primitive proposition and atoms, and an obvious bijection &#981; &#8594; do(&#981;) between elements of F and primitive acts, we really can be thought of as doing just that. <ref type="bibr">5</ref> That is, for all &#945;, &#946; , &#947;, &#947; &#8712; A F and all &#981; &#8712; F,</p><p>To build intuition it's helpful to consider the special case where &#968; = &#981;, in which case (Cent) just says that doing &#981; precisely when &#981; is already the case (and otherwise doing nothing) is the same as doing nothing. Here of course by "the same" what is really meant is that the agent is indifferent between those two acts. Since we are trying to bootstrap properties of a selection function from the agent's preferences, all our principles will ultimately need to bottom out in statements about what the agent does or does not have a preference between. The general statement of (Cent) simply expands this reasoning to cases where the condition &#968; entails the result of the action, &#981;, and so again in this case do(&#981;) happens only in cases where &#981; is already true. </p><p>Our second axiom is meant to capture the idea that sufficiently specific conditions resolve any ambiguity (expressible in the underlying language) about the effect of an action:</p><p>This requires some unpacking. As above, it is illuminating to begin by considering the special case where &#968; = &#981;. Then |= &#968; &#8594; &#981; holds trivially and |= &#981; i &#8594; &#968; is true by assumption, so we can read (SSC) intuitively as follows: If &#981; is ambiguous between a variety of (potentially) more precise statements (namely, &#981; 1 , . . . , &#981; n ), then for any sufficiently specific condition (i.e., any atom &#981; X ), there is at least one precisification &#981; i of &#981; such that, conditional on &#981; X , doing &#981; is equivalent to doing &#981; i (from the agent's perspective).</p><p>This, as well as the more general statement of (SSC), follows from the assumption that the selection function c is induced by a language-based family of well-orders. </p><p>The next idea is crucial to the ultimate construction of our selection function. For each atom &#981; W , we will define a total preorder <ref type="bibr">7</ref> W on the set of atoms that will in turn be extended to a linear order and used to specify the selection function. Formally, we define:</p><p>Loosely speaking, &#981; X W &#981; Y says that in &#981; W -states, the ambiguity inherent in doing &#981; X &#8744; &#981; Y is resolved in the agent's mind in favour of doing &#981; X ; this is why the agent is indifferent (conditional on &#981; W ) between doing &#981; X &#8744; &#981; Y and just doing &#981; X . In this sense we think of &#981; X as being at least as "close" to &#981; W as &#981; Y is.</p><p>Note that the definition above requires F to contain all atoms as well as all pairwise disjunctions of atoms. This richness in F is what allows us to use the agent's preferences on actions to define an appropriate preorder. We make this assumption henceforth. It is an interesting question to what extent the ensuing construction can be carried out without this assumption; we return to this point in Section 4. Now we can state our third axiom, which simply says that this notion of closeness is transitive:</p><p>Lemma 3. (SSC) implies that each W is complete.</p><p>Lemma 4. If (SSC) and (Trans) hold, then each W is a total preorder and can be extended to a wellorder &#8804; W on the set of atoms; if, in addition, (Cent) holds, then each &#8804; W can be defined so that &#981; W is the &#8804; W -minimal element.</p><p>Given a family of well-orders {&#8804; W : W &#8838; &#934;} as defined in Lemma 4, let min &#8804; (W, &#981;) denote the unique X &#8838; &#934; such that &#981; X is &#8804; W -minimal in {&#981; Y : |= &#981; Y &#8594; &#981;}. So &#981; X is the "closest" atom compatible with &#981; to &#981; W ; intuitively, then, doing &#981; in a &#981; W situation should essentially amount to doing &#981; X . This is precisely what the next lemma asserts.</p><p>Lemma 5. If (SSC) and (Trans) hold, then do(&#981;) &#8764; W do(&#981; min &#8804; (W,&#981;) ).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.3">The representation theorem</head><p>Theorem 1. If is a complete binary relation on A F satisfying (Canc), (Cent), (SSC), and (Trans), then there is a language-based SEU representation .</p><p>Proof. We begin by following the proof in [3, Theorem 2] to obtain a state-dependent representation with state space 2 &#934; and outcome space F. <ref type="bibr">8</ref> More precisely, we consider the set of functions F = { f &#945; : &#945; &#8712; A F } defined in Section 3.1, which can be viewed as Savage acts in the classical sense [12]. The relation on A F induces a relation * on F defined as follows:</p><p>As discussed, (Canc) implies that &#945; &#8764; &#945; whenever f &#945; = f &#945; , so * is well-defined; moreover, as BEH show, (Canc) is strong enough to yield the desired state-dependent representation result for * , namely, that there exists a function u * : 2 &#934; &#215; F &#8594; R such that, for all f , g &#8712; F,</p><p>u * (X, g(X)).</p><p>Up to now we have mirrored the proof given by BEH exactly, which has given us a utility function u * but also an outcome space that we don't want. Moreover, the utility function is state-dependent; it takes as arguments both a state and an outcome. We want a utility function that depends only on states (which for us are the same as outcomes). Thus, our task now is to transform this result into a selection model that we can use to give a language-based SEU representation of (including a utility function defined only on states).</p><p>Set &#8486; = 2 &#934; &#215; 2 &#934; ; so our state space is isomorphic to pairs of atoms. This is a technical maneuver that allows us to "factor out" probabilities from the state-dependent utility function u * we already have. Loosely speaking, given (X,Y ) &#8712; &#8486;, the first component X represents how things are, while the second component Y represents how things were. This intuition should become clearer as we continue.</p><p>We define a basic model M = (&#8486;, [[&#8226;]] M ) by specifying the valuation on &#8486; as follows:</p><p>In other words, p is true at (X,Y ) just in case &#981; X entails p. Note that the valuation only depends on the first component X of the state (X,Y ).</p><p>Note that in the above W can be any element of 2 &#934; , since it's not taken into account in determining the result of an action. That means we can rewrite the above as</p><p>Of course, an analogous equation holds for u * (W, f &#946; (W )). Thus, (3) is equivalent to:</p><p>which is exactly the right-hand side of (1), completing the proof.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">Discussion</head><p>We have considered a framework in which both the conditions for and the results of an action are given by simple descriptions in a fixed language. These descriptions may not be maximally specific, so the results of actions can be underspecified and therefore "open to interpretation". We have shown that, in this context, agents whose preferences satisfy certain constraints can be represented as if they are expected utility maximizers who interpret each underspecified action using a selection function identical to that employed in standard semantics for counterfactual conditionals.</p><p>The representation theorem presented in this extended abstract might be viewed as a sort of "proof of concept", namely, that such representation results are possible and even natural. This opens the door for a variety of related results connecting different assumptions about the selection function to different constraints on the agent's preferences. As we mentioned above, there are a number of standard assumptions along these lines in the literature on counterfactuals.</p><p>The underlying language we chose to work with can also be altered. Perhaps most obviously, we might consider allowing countably-many primitive propositions. In this case, we cannot straightforwardly use atoms as the basis for the state space in the representation theorem, and in general we might need to relax the notion of a "complete description" to something like a "sufficiently detailed description". Going in the other direction, we might also considering dropping some of the richness constraints we imposed. For instance, we assumed that F contains all atoms (and all pairwise disjunctions of atoms). Can this assumption be relaxed?</p><p>In our framework, because we use the same descriptions for both states and outcomes, we found it convenient to identify the two. This in turn makes it straightforward to extend to a richer language of acts, where we allow sequential actions, implemented directly by function composition. That is, we can allow actions of the form do(&#981;); do(&#968;) ("first do &#981;, then do &#968;"), or more generally, &#945;; &#946; . Thus, the (underspecified!) results of the first action are directly relevant to the conditions under which the second action is executed, which may allow for entirely new and intriguing ways of encoding modeling features via constraints on preferences.</p><p>Finally, generalizing this framework to multiple agents is of interest. Indeed, the original motivation for this work is doubly relevant in multi-agent settings: two different decision-makers might conceive of the same action in different ways, by associating it with different functions. For example, we should be able to model two agents who agree about their values and have the same beliefs about the likelihoods of uncertain events, but still have different preferences over actions-intuitively, because they interpret the "default" way of implementing actions differently (in other words, they have the same utility function and probability measure, but different selection functions).</p><p>In short, this area is ripe for further exploration, with many theoretical and practical applications.</p><p>then we apply it in the case where &#968; = &#981; = &#981; W to obtain (if &#981; W then do(&#981; W )) &#8764; do(true). Transitivity of &#8764; therefore yields (if &#981; W then do(&#981; W &#8744; &#981; X )) &#8764; (if &#981; W then do(&#981; W )), which by definition is equivalent to do(&#981; W &#8744; &#981; X ) &#8764; W do(&#981; W ).</p><p>Lemma 5. If (SSC) and (Trans) hold, then do(&#981;) &#8764; W do(&#981; min &#8804; (W,&#981;) ).</p><p>Proof. Let X = min &#8804; (W, &#981;), and let &#981; X 1 , . . . , &#981; X n enumerate all the atoms compatible with &#981;. Then by definition we know that X = X j for some j. We also clearly have |= &#981; &#8596; (&#981; X 1 &#8744; &#8226; &#8226; &#8226; &#8744; &#981; X n ), so we can apply (SSC) (taking &#968; = &#981;) to find an i such that do(&#981;) &#8764; W do(&#981; X i ).</p><p>By definition of X, we know that &#981; X &#8804; W &#981; X i , which means do(&#981; X &#8744; &#981; X i ) &#8764; W do(&#981; X ). On the other hand, since |= &#981; X i &#8594; (&#981; X &#8744; &#981; X i ) and |= (&#981; X &#8744; &#981; X i ) &#8594; &#981;, (SSC) also tells us (taking &#968; = &#981; X &#8744; &#981; X i this time) that do(&#981; X &#8744; &#981; X i ) &#8764; W do(&#981; X i ). By transitivity of &#8764; W we therefore have do(&#981; X i ) &#8764; W do(&#981; X ), and therefore do(&#981;) &#8764; W do(&#981; X ), as desired. Lemma 6. The function u is well-defined.</p><p>Proof. What we need to show that is that if min &#8804; (W, &#981;) = X and also min &#8804; (W, &#981; ) = X, then u * (W, &#981;) = u * (W, &#981; ). By Lemma 5, we know that do(&#981;) &#8764; W do(&#981; X ), and also that do(&#981; ) &#8764; W do(&#981; X ). Focusing on the first of these two indifferences to begin with, by definition we have if &#981; W then do(&#981;) &#8764; if &#981; W then do(&#981; X ).</p><p>Setting &#945; = if &#981; W then do(&#981;) and &#946; = if &#981; W then do(&#981; X ), it follows that f &#945; &#8764; * f &#946; (by definition of * ). Thus, from the state-dependent representation result, we can deduce that</p><p>But it's easy to see that whenever Z = W , f &#945; (Z) = f &#946; (Z), so we can cancel all those terms in the equality above to arrive at u * (W, f &#945; (W )) = u * (W, f &#946; (W )). This yields u * (W, &#981;) = u * (W, &#981; X ), since clearly f &#945; (W ) = &#981; and f &#946; (W ) = &#981; X . Analogous reasoning starting from the fact that do(&#981; ) &#8764; W do(&#981; X ) leads us to u * (W, &#981; ) = u * (W, &#981; X ). Putting these together gives u * (W, &#981;) = u * (W, &#981; ), as desired.</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_0"><p>We remark that in this paper we consider only the single-agent case, but we find the multi-agent case, and specifically the effect of disagreements about what the closest state is, an exciting direction for future work.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_1"><p>A binary relation &#8804; on a set is called a linear order if it is complete, transitive, and antisymmetric (i.e., x &#8804; y and y &#8804; x implies x = y). A well-order is a linear order in which every nonempty subset has a least element.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="3" xml:id="foot_2"><p>Here's why: since c(&#969;, &#981;)is the &#8804; &#969; -minimal element of [[&#981;]], it must also be that [c(&#969;, &#981;)] is the &#969; -minimal element of {[&#969; ] : &#969; |= &#981;}. Similarly, [c(&#969; , &#981;)] is the &#969; -minimal element of {[&#969; ] : &#969; |= &#981;}. Since &#969; = &#969; , these must coincide, so we have [c(&#969;, &#981;)] = [c(&#969; , &#981;)].Can we drop this moreover/</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="6" xml:id="foot_3"><p>As BEH show, the cancellation law implies independence, so in fact we have &#945; &#981; &#946; iff for all &#947;, if &#981; then &#945; else &#947; if &#981; then &#946; else &#947;.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="7" xml:id="foot_4"><p>A total preorder is a complete and transitive relation (so, unlike a linear order, it need not be antisymmetric).</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="8" xml:id="foot_5"><p>"State-dependent" here means that the utility function constructed will depend not only on outcomes but on states as well.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="9" xml:id="foot_6"><p>Though this isn't quite right-it's more like the product of that utility with the probability of W , which is why we have to factor that probability out in defining our utility function.</p></note>
		</body>
		</text>
</TEI>
