Natural Extension of Choice Functions

Abstract

We extend the notion of natural extension, that gives the least committal extension of a given assessment, from the theory of sets of desirable gambles to that of choice functions. We give an expression of this natural extension and characterise its existence by means of a property called avoiding complete rejection. We prove that our notion reduces indeed to the standard one in the case of choice functions determined by binary comparisons, and that these are not general enough to determine all coherent choice function. Finally, we investigate the compatibility of the notion of natural extension with the structural assessment of indifference between a set of options.

1 Introduction

Since the publication of the seminal works in [1, 2], coherent choice functions have been used widely as a model of the rational behaviour of an individual or a group. In particular, [3] established an axiomatisation of coherent choice functions, generalising the axioms in [4] to allow for incomparability.

In previous works [5, 6], we have investigated some of the properties of coherent choice functions, their connection with the models considered earlier by Seidenfeld et al. [3] and also those particular coherent choice functions that are related to the optimality criteria of maximality and E-admissibility. In all those cases we took for granted that the choice function is given on the full class of option sets, and that it is coherent. However, it is somewhat unrealistic to assume that the subject always specifies an entire choice function: this means that he would have to specify for every option set which are the options he chooses, and this in a manner that is coherent in the sense that we shall discuss later on. Rather, a subject will typically specify a choice function only partially, by specifying the rejection of some options from some option sets. We call this partial specification of a choice function his assessment. Such an assessment can consist of an arbitrary amount of rejection statements; we do not rule out here the possibility that the subject’s assessment consists of an uncountable collection of rejection statements.

The question we shall tackle in this paper is the following: given such an assessment, what is the implied choice between other option sets, using only the consequences of coherence?

To answer this question, after giving some preliminary notions in Sect. 2, we shall define in Sect. 3 the natural extension, when it exists, as the least committal coherent choice function that ‘extends’ a given assessment. In Sect. 4 we shall show that our notion is compatible with the eponymous notion established in the theory of sets of desirable gambles, that correspond to choice functions determined by binary comparisons. Then in Sect. 5 we use our work to show (i) that a coherent choice function may not be determined as the infima of a family of binary choice functions; and (ii) that the notion of natural extension can also be made compatible with a structural assessment of indifference. Finally, some additional comments are given in Sect. 6. Due to the space constraints, proofs have been omitted.

2 Preliminary Concepts

Consider a real vector space provided with the vector addition $+$ and scalar multiplication. We denote its additive identity by 0. Elements of are intended as abstract representation of options between which a subject can express his preferences, by specifying choice functions. We therefore call also the option space. We denote by the set of all non-empty finite subsets of , a strict subset of the power set of . Elements of are the option sets amongst which a subject can choose his preferred options. When it is clear what option space we are considering, we will also use the simpler notation $\mathcal {Q}$, and use $\mathcal {Q}_0$ to denote those option sets that include 0. We will assume throughout that is ordered by a vector ordering . We will associate with it the strict partial order , as follows: , for all and in . For notational convenience, we let , , and .

Definition 1

A choice function on an option space is a map

The idea underlying this simple definition is that a choice function  selects the set of ‘best’ options in the option set . Our definition resembles the one commonly used in the literature [3, 7, 8], except perhaps for an also not entirely unusual restriction to finite option sets [9,10,11].

Equivalently to a choice function , we may consider its associated rejection function , defined by for all in $\mathcal {Q}$. It returns the options that are rejected—not selected—by . We collect all the rejection functions in the set $\mathbf {R}$. For technical reasons, we shall focus on rejection functions in this paper. Moreover, we shall restrict our attention to those rejection functions that satisfy a number of rationality requirements; they are called coherent. For brevity, we will commonly refer to choice functions and rejection functions as choice models, in order to distinguish them from models of desirability (see Sect. 4).

Definition 2

(Coherent rejection function). We call a rejection function  on coherent if for all , and in $\mathcal {Q}$, all and in , and all $\lambda$ in $\mathbb {R}_{>0}$:

$\mathrm {R1.}$ :

;

$\mathrm {R2.}$ :

if then ;

$\mathrm {R3.}$ :

$\mathrm {a.}$ :

if and then ;

$\mathrm {b.}$ :

if and then ;

$\mathrm {R4.}$ :

$\mathrm {a.}$ :

if then ;

$\mathrm {b.}$ :

if then .

We collect all coherent rejection functions on in the set , often simply denoted as $\overline{\mathbf {R}}$ when it is clear from the context which vector space we are using.

These axioms constitute a subset of the ones introduced by Seidenfeld et al. [3], duly translated from horse lotteries to our abstract options, which are more general as shown in earlier work of ours [5, Sect. 3]. In this respect, our notion of coherence is less restrictive than theirs. On the other hand, our Axiom R2 is more restrictive than the corresponding one in [3]. This is necessary in order to link coherent choice functions and coherent sets of desirable gambles (see [5, Sect. 4]).

In order to be able to use choice models for conservative reasoning, as we will do, we provide them with a partial order having the interpretation of ‘being at most as informative as’. For any and in $\mathbf {R}$, we let . For any collection of rejection functions, the infimum is the rejection function given by for every in $\mathcal {Q}$.

3 Natural Extension of Rejection Functions

We consider now a rejection function that is defined on some subset of the class $\mathcal {Q}$ of all option sets, and investigate under which conditions it is possible to extend it to a rejection function on $\mathcal {Q}$ that satisfies the coherence axioms. Taking into account Axiom R4b, we can assume without loss of generality that our assessment is made in terms of option sets that reject the option 0.

To be more specific, we assume that an assessment $\mathcal {B}$ is a subset of $\mathcal {Q}_0$. It consists of an arbitrary collection of option sets that include 0. Its interpretation is that 0 should be rejected from every option set in $\mathcal {B}$. We are looking for the least informative coherent rejection function that extends the assessment $\mathcal {B}$, by which we mean that for all in $\mathcal {B}$.¹

Definition 3

(Natural extension). Given any assessment $\mathcal {B}\subseteq \mathcal {Q}_0$, the natural extension of $\mathcal {B}$ is the rejection function

where we let $\inf \emptyset$ be equal to , the identity rejection function that maps every option set to itself.

We can equivalently define the natural extension as a choice function instead of a rejection function, but that turns out to be notationally more involved, which is why we have decided to use rejection functions in this paper.

The above definition is not very useful for practical inference purposes: it does not provide an explicit expression for . To try and remedy this, consider the special rejection function based on the assessment $\mathcal {B}$, defined as:

(1.1)

for all in $\mathcal {Q}$. From here on, we let $\preccurlyeq$ be the ordering on $\mathcal {Q}$ defined by .

Proposition 1

Consider $\mathcal {B}\subseteq \mathcal {Q}_0$. Then is the least informative rejection function that satisfies Axioms R2–R4 and extends $\mathcal {B}$.

After inspection of the rationality Axioms R1–R4, we see that all axioms but the first are productive, in the sense that application of these axioms allow us to identify new rejected options within, possibly, new option sets. Axiom R1 however is a destructive one: it indicates how far our rejections can go, and where the inferences should stop. Indeed, it requires that, within a given option set , not every element of should be rejected. In other words, it requires that, for any given option set, we should choose at least one of its elements. Therefore we need to be careful and avoid assessments that lead to a violation of Axiom R1, or to a complete rejection of some option set.

Definition 4

(Avoiding complete rejection). Given any assessment $\mathcal {B}\subseteq \mathcal {Q}_0$, we say that $\mathcal {B}$ avoids complete rejection when satisfies Axiom R1.

To see that this notion is not trivial, consider the following example:

Example 1

As an example of an assessment that does not avoid complete rejection, consider for an arbitrary in . By Proposition 1, extends $\mathcal {B}$ (so and ) and satisfies Axioms R2–R4. By Axiom R4b, from we infer that . Using that , we infer that , contradicting Axiom R1. Therefore $\mathcal {B}$ does not avoid complete rejection. $\lozenge$

Theorem 1

Consider any assessment $\mathcal {B}\subseteq \mathcal {Q}_0$. Then the following statements are equivalent:

$\mathrm {(i)}$ :

$\mathcal {B}$ avoids complete rejection;

$\mathrm {(ii)}$ :

There is a coherent extension of $\mathcal {B}$: ;

$\mathrm {(iii)}$ :

;

$\mathrm {(iv)}$ :

;

$\mathrm {(v)}$ :

is the least informative rejection function that is coherent and extends $\mathcal {B}$.

When any of these equivalent statements hold, then .

4 Connection with Desirability

Let us compare our discussion of natural extension with the case of binary preferences and desirability. A desirability assessment is usually (see for instance Sect. 1.2 of Ref. [12], and also Ref. [13]) a set of options that the agent finds desirable—strictly prefers to the zero option. As we did for choice functions, we pay special attention to coherent sets of desirable options. The following is an immediate generalisation of existing coherence definitions [12, 13] from gambles to abstract options.

Definition 5

(Coherent set of desirable options). We call a set of desirable options  coherent if for all and in and $\lambda$ in $\mathbb {R}_{>0}$:

$\mathrm {D1.}$ :

;

$\mathrm {D2.}$ :

if then ;

$\mathrm {D3.}$ :

if then ;

$\mathrm {D4.}$ :

if then .

We collect all coherent sets of desirable options in the set , often simply denoted as $\overline{\mathbf {D}}$ when it is clear from the context which vector space we are using.

Any coherent set of desirable options gives rise to a coherent rejection function given by for all in $\mathcal {Q}$.

Of course, any desirability assessment can be transformed into an assessment for rejection functions: we simply assess that 0 is rejected in the binary choice between 0 and , for every option in . The assessment based on is therefore given by ; clearly and are in a one-to-one correspondence: given an assessment that consists of an arbitrary family of binary option sets, we retrieve as .

Given any desirability assessment and any set of desirable options , we say that extends if . Our next proposition expresses this in terms of rejection functions.

Proposition 2

Consider any desirability assessment and any set of desirable options . Then extends if and only if extends .

For desirability, Axioms D2–D4 are the productive ones, while the only destructive axiom is Axiom D1. The property for desirability that corresponds to avoiding complete rejection for choice models is avoiding non-positivity, commonly formulated as (see for instance Ref. [13, Definition 1])

(1.2)

for the desirability assessment . Here, $\mathrm {posi}$ stands for ‘positive hull’, and is defined by

Theorem 1 is the equivalent for choice models of the natural extension theorem for desirability. Let us state this natural extension theorem for desirability.

Theorem 2

[13, Theorem 1]. Consider any desirability assessment , and define its natural extension as

(1.3)

where we let . Then the following statements are equivalent:

$\mathrm {(i)}$ :

avoids non-positivity;

$\mathrm {(ii)}$ :

is included in some coherent set of desirable options;

$\mathrm {(iii)}$ :

;

$\mathrm {(iv)}$ :

;

$\mathrm {(v)}$ :

is the least informative set of desirable options that is coherent and includes .

When any of these equivalent statements hold, .

Our next result tells us that the procedure of natural extension we have established for rejection functions is an extension of the procedure of natural extension for coherent sets of desirable gambles considered above.

Theorem 3

Consider any desirability assessment . Then avoids non-positivity if and only if avoids complete rejection, and if this is the case, then .

To summarise these statements, consider the commuting diagram in Fig. 1, where we have used the maps

Start with a desirability assessment that avoids non-positivity. Taking the natural extension for desirability commutes with taking the corresponding assessment (for choice models), then the natural extension, and eventually going back to the set of desirable options corresponding to this natural extension. Furthermore, taking the natural extension of the corresponding assessment (for choice models) commutes with taking the natural extension for desirability, and then going to the corresponding rejection function.

Fig. 1.

Commuting diagram for the case of binary assessments

5 Examples

5.1 Choice Functions That Are No Infima of Binary Choice Functions

Many important choice functions are infima of purely binary choice models: consider, for instance, the E-admissible or M-admissible choice functions [6]. It is an important question whether all coherent choice functions are infima of purely binary choice functions; if this question answered positively, this would immediately imply a representation theorem. If this question is answered in the negative, choice functions would constitute a theory that is more general than sets of desirable gambles in two ways: not only because it allows for more than binary choice, also because it is capable of expressing preferences that can never be retrieved as an infimum of purely binary preferences.

Below we will answer this question in the negative: we will define a special rejection function , based some particular assessment $\mathcal {B}\subseteq \mathcal {Q}_0$, and prove that it is no infimum of purely binary rejection functions.

Example 2

We will work with the special vector space of gambles on a binary possibility space , ordered by the standard point-wise ordering $\le$: for any f, g in $\mathcal {L}$, we let .

We consider a single assessment , where consists of a gamble and one scaled variant of it, together with 0: the assessment we consider is with a gamble and $\lambda$ an element of $\mathbb {R}_{>0}$ and different from 1. We assume that , and that $\lambda >1$. The idea is that consists of 0 and two gambles that lie on the same line through 0, and on the same side of that line; see Fig. 2 for an illustration of the assessment.

Fig. 2.

Illustration of the assessment

Note that this assessment indeed avoids complete rejection: for instance, the coherent set of desirable options satisfies . Therefore, is a coherent rejection function. To prove that is no infimum of purely binary rejection functions, we first show the intermediate result that , where . To prove this, assume ex absurdo that , and infer using Eq. (1.1) that then there would be some in $\mathcal {Q}$ such that

(1.4)

At this point, remark already that : indeed, if ex absurdo , then , so we need only consider . Infer that and , leading to a contradiction. Therefore, .

Without loss of generality, we let where n belongs to $\mathbb {N}$ and to $\mathcal {L}$, so .

It then follows that .

Let us prove as an intermediate result that . To see this, since , infer that , and assume ex absurdo that . Let be an element of , then , so is undominated in whence for all $\mu$ in $\mathbb {R}_{>0}$. Note that, since belongs to , also belongs to for every $\mu$ in $\mathbb {R}_{>0}$. Therefore, since an element of can never be dominated by an element of , also for all $\mu$ in $\mathbb {R}_{>0}$. We deduce that also for all $\mu$ in $\mathbb {R}_{>0}$. Since belongs to , also , a contradiction. So we have that , and therefore, again because an element of can never be dominated by an element of , also .

Now we go back to Eq. (1.4), and consider first . Then or . Since , in particular , so the only possibility left is , or, in other words, for some $\mu$ in $\mathbb {R}_{>0}$. There are three possibilities: if (i) $\mu =1$, then —and therefore, since , necessarily —for some i in ; if (ii) $\mu =\frac{1}{\lambda }$ then —and therefore, since , necessarily —for some j in ; and finally, if (iii) , then and —and therefore, since , necessarily and —for some k and $\ell$ in . These are illustrated in Fig. 3.

Fig. 3.

Illustration of the three different cases mentioned

In any case, we find that . Without loss of generality, let be the unique gamble in with highest value in $\mathrm {T}$: . Then, since , by Eq. (1.4) we have that or . Since and , we find in particular , whence . Therefore necessarily for some $\mu$ in $\mathbb {R}_{>0}$. Note that both and belong to , and have a value in $\mathrm {T}$ that is strictly higher than . But at least one of or is not equal to , and therefore an element of , a contradiction with the fact that . Therefore indeed .

So we have found a rejection function such that but . However, any rejection function that is defined by means of a coherent set of desirable options satisfies that

(1.5)

and Eq. (1.5) is preserved when taking infima of rejection functions. As a consequence, is no infimum of purely binary rejection functions. $\lozenge$

5.2 Natural Extension and Indifference

Next we investigate if it is possible to obtain an extension of a given assessment that takes into account not only the implications of coherence, as we did with the natural extension, but also some assessments of indifference between a set of options. To see how this comes about, note that, in addition to a subject’s set of desirable options —the options he strictly prefers to the zero option—we can also consider the options that he considers to be equivalent to the zero option. We call these options indifferent. A set of indifferent options is simply a subset of , but as before with desirable options, we pay special attention to coherent sets of indifferent options.

Definition 6

A set of indifferent options is called coherent if for all in and $\lambda$ in $\mathbb {R}$:

$\mathrm {I}_{1}.$ :

;

$\mathrm {I}_{2}.$ :

if then ;

$\mathrm {I}_{3}.$ :

if then ;

$\mathrm {I}_{4}.$ :

if then .

Taken together, Axioms I₃ and I₄ are equivalent to , and due to Axiom I₁, is non-empty and therefore a linear subspace of .

The interaction between indifferent and desirable options is subject to rationality criteria as well: they should be compatible with one another.

Definition 7

Given a set of desirable options and a coherent set of indifferent options , we call compatible with if .

We collect all options that are indifferent to an option into the equivalence class . We also denote as . Of course, is a linear subspace, and the classes are affine subspaces of . The set of all these equivalence classes is the quotient space . This quotient space is a vector space under the vector addition and the scalar multiplication. is the additive identity of .

Definition 8

We call a rejection function on compatible with a coherent set of indifferent options  if there is some representing rejection function on such that for all in .

We refer to an earlier paper [6] of ours for a study of the compatibility of the structural assessment of coherence with the theory of coherent rejection functions, and to [14, 15] for other works on this topic.

The natural extension under indifference, if it is coherent, is the least informative coherent rejection function that extends the assessment and is compatible with the set of indifferent options .

Definition 9

Given any assessment and any coherent set of indifferent options , the natural extension of $\mathcal {B}$ under is the rejection function

where, as usual, we let , the identity rejection function that maps every option set to itself.

To help link this definition with a more constructive and explicit expression, consider the special rejection function , defined by:

(1.6)

where we let , being—loosely speaking—the assessment $\mathcal {B}$ expressed in the quotient space . Recall that , as defined in Eq. (1.1), is relative to a given but otherwise arbitrary vector space . Our special rejection function uses the version on instead of .

The following is the counterpart of Proposition 1 under indifference:

Proposition 3

Consider any assessment and any coherent set of indifferent options . Then is the least informative rejection function that satisfies Axioms R2–R4, extends $\mathcal {B}$, and is compatible with .

Recall from our results on the (normal) natural extension from Sect. 3 that not every assessment is extendible to a coherent rejection function: this is only the case if the assessment avoids complete rejection. Here too, when we deal with the natural extension under indifference, something similar occurs.

Definition 10

(Avoiding complete rejection under indifference). Given any assessment and any coherent set of indifferent options , we say that $\mathcal {B}$ avoids complete rejection under when satisfies Axiom R1.

However, and perhaps surprisingly, avoiding complete rejection under indifference is sufficient for avoiding complete rejection:

Proposition 4

Consider any assessment and any coherent set if indifferent options . Then $\mathcal {B}$ avoids complete rejection under if and only if avoids complete rejection, and both those equivalent conditions imply that $\mathcal {B}$ avoids complete rejection.

This allows us to formulate a counterpart to Theorem 1 for natural extension under indifference:

Theorem 4

Consider any assessment $\mathcal {B}\subseteq \mathcal {Q}_0$ and any coherent set of indifferent options . Then the following statements are equivalent:

$\mathrm {(i)}$ :

$\mathcal {B}$ avoids complete rejection under ;

$\mathrm {(ii)}$ :

There is some in that extends $\mathcal {B}$ that is compatible with , meaning that and

$\mathrm {(iii)}$ :

;

$\mathrm {(iv)}$ :

;

$\mathrm {(v)}$ :

is the least informative rejection function that is coherent, extends $\mathcal {B}$, and is compatible with .

When any of these equivalent statements hold, then .

6 Conclusions

In this paper, we have investigated the natural extension of choice functions, found an expression for it, and characterised the assessments that have coherent extensions. We made the connection with binary choice, and showed how the well-known natural extension for desirability follows from our natural extension.

As future lines of research, we would like to study the compatibility of the notion of natural extension with other structural assessments; in this respect, we have already investigated the compatibility with a notion of irrelevance when modelling multivariate choice functions. It is an open problem to study whether something similar can be made with respect to the exchangeable choice functions we have considered in [16].