Essentiality and convexity in the ranking of opportunity sets

Abstract

This paper studies a class of binary relations on opportunity sets which we call opportunity relations (ORs). These are reflexive and transitive (pre-orders) and further satisfy a monotonicity and desirability condition. Associated with each OR is an essential element operator (Puppe, J Econ Theory 68:174–199, 1996). Our main results axiomatically characterise three important classes of ORs: those for which any opportunity set lies in the same indifference class as its set of essential elements—the essential ORs; those whose essential element operator is the extreme point operator for some closure space (Ando, Discrete Math 306:3181–3188, 2006)—the closed ORs; and those whose essential element operator is the extreme point operator for some abstract convex geometry (Edelman and Jamison, Geometriae Dedicata 19:247–270, 1985)—the convex ORs. Our characterisation of convex ORs generalises the analysis of Klemisch-Ahlert (Soc Choice Welf 10:189–207, 1993). Our results also provide complementary perspectives on the well-known characterisation of closure operators by Kreps (Econometrica 47:565–577, 1979), as well as the recent work of Danilov and Koshevoy (Order 26:69–94, 2009; Soc Choice Welf 45:51–69, 2015).

1 Introduction

In this paper we consider pre-orders (reflexive and transitive binary relations, denoted $\succsim$) on the subsets of a non-empty, finite set X. Subsets of X are opportunity sets, from which one alternative may—though not must—be chosen. If $A,B\in 2^{X}$, then $A\succsim B$ means that the opportunity, or freedom of choice, represented by A is weakly preferred to that represented by B. Given this interpretation, it is natural to restrict attention to pre-orders that are monotone with respect to set inclusion ($B\subseteq A$ implies $A\succsim B$). We further assume that any non-empty opportunity set is strictly preferred to the empty set. A pre-order satisfying these two additional requirements will be called an opportunity relation (OR). Opportunity relations are the objects of study in the paper.

We will not be prescriptive about the basis on which opportunities are ranked. Various logics are discussed in the literature, and ably surveyed elsewhere.¹ Rankings may follow the instrumentalist logic of indirect utility, or they might take account of factors other than the decision-maker’s preferences (if such exist) over X. If opportunity sets are given rather than chosen, then the decision-maker may feel happier about a social situation that allocates to him a wide freedom of choice even if he would reject most of the offered alternatives. He might also prefer to be offered additional alternatives—besides those he is inclined to choose—if he feels that respected others might find them attractive.

Our primary concern is the role of essential elements—a notion introduced by Puppe (1996)—in the ranking of opportunity sets. An element $x\in A$ is essential to opportunity set A if $A\succ A\diagdown \left\{ x\right\}$, where $\succ$ is the asymmetric part of $\succsim$. In other words, an element is essential if its removal strictly diminishes the value of opportunity. By focussing on the role of essential elements, our analysis is in the spirit of Puppe (1996) and Puppe and Xu (2010), and at somewhat further remove, that of van Hees (2010).

We define an essential opportunity relation (EOR) to be an OR for which every opportunity set is contained in the same indifference class as the set of its essential elements. For an EOR, the full value of an opportunity set is carried by its essential elements, and removal of any essential element will materially diminish this value. The notion of essentiality captures the idea of an OR for which opportunity sets are ordered on the basis of their sets of essential elements. In Sect. 3 we provide an axiomatic characterisation of the EORs.

An important sub-class of EORs is the class of convex opportunity relations. A convex OR is an EOR for which essentiality can be “rationalised” by a subjective convex structure on X. More precisely, an EOR is convex if there exists an abstract convex geometry (ACG) on X (Edelman and Jamison 1985) that rationalises essentiality in the following sense: the essential elements of any opportunity set are its “extreme points” relative to the ACG. A brief introduction to ACGs is provided in Appendix B and the interested reader may consult Edelman and Jamison (1985) for a more detailed account. An axiomatic characterisation of the convex ORs is given in Sect. 5.

The idea of rationalising essentiality through convexity was first proposed by Klemisch-Ahlert (1993). Our analysis generalises hers in two important respects.

First, Klemisch-Ahlert restricts attention to a sub-class of ACGs known as the convex shelling geometries. A convex shelling geometry is induced on X by specifying a one-to-one mapping $h:X\rightarrow \mathbb {R}^{n}$. A set $A\subseteq X$ is convex in the induced geometry if

$$\begin{aligned} h\left( X\right) \cap \mathrm {co}\left( h\left( A\right) \right) =h\left( A\right) \end{aligned}$$

where $\mathrm {co}\left( \cdot \right)$ denotes the usual (Euclidean) convex hull in $\mathbb {R}^{n}$. By varying the mapping h we can induce different convex geometries on X—different collections of convex subsets. However, there are many ACGs which are not convex shellings.² In Sect. 5, we construct an example to show that restricting attention to convex shelling geometries excludes some plausible and interesting convex ORs.

Second, Klemisch-Ahlert specifies the mapping h exogenously. (In fact, she assumes that $X\subseteq \mathbb {R}^{n}$ and takes h to be the identity function.) The associated convex geometry is therefore part of the objective description of X—it can be observed without observing preferences. In our framework, by contrast, the convex geometry that rationalises essentiality is subjective. Since essential elements are subjective entities—they are imputed from an individual’s preferences—it is natural to expect that the convex structure which rationalises essentiality should also be subjective. Different individuals may perceive different convex structure in X. We therefore ask when the notion of essentiality embodied in an EOR can be rationalised by some ACG.

En route to our main results, we also characterise another interesting class of ORs, which we call the closed opportunity relations, and we show that the class of convex ORs is the intersection of the EORs and the closed ORs.

The remainder of the Introduction elaborates on this summary of our objectives.

Let $e_{\succsim }\left( A\right)$ denote the (possibly empty) set of essential elements of A. An OR is essential (an EOR) if $A\sim e_{\succsim }\left( A\right)$ for any $A\subseteq X$ (where $\sim$ is the symmetric part of $\succsim$). For an EOR, there is an obvious sense in which the elements of $e_{\succsim }\left( A\right)$ may be interpreted as “extreme points” of A: removing an essential element from A strictly diminishes the value of the opportunity set, and the elements of $A\diagdown e_{\succsim }\left( A\right)$ are “opportunity-spanned” by $e_{\succsim }\left( A\right)$ in the sense that adding elements from $A\diagdown e_{\succsim }\left( A\right)$ to $e_{\succsim }\left( A\right)$ does not enhance value. This interpretation of essential elements recalls the connection between choice functions and abstract convex geometries, which was originally explored by Koshevoy (1999).

An ACG provides a natural environment for thinking about extreme points. It imposes convex structure on X by identifying the collection $\mathcal {K}\subseteq 2^{X}$ of its “convex” subsets. This collection must respect certain conditions to qualify as an ACG; for example, it must be closed under intersections. Unless $\left| X\right| =1$, there will be more than one collection that satisfies these conditions, so there are different ACGs—different convex structures—that may be imposed on X.

Associated with any abstract convex geometry, $\mathcal {K}$, is a closure operator $\sigma _{\mathcal {K}}:2^{X}\rightarrow 2^{X}$ and an extreme point operator $e_{\mathcal {K}}:2^{X}\rightarrow 2^{X}$ defined as follows:³

$$\begin{aligned} \sigma _{\mathcal {K}}\left( A\right)= & {} \bigcap \left\{ B\in \mathcal {K}\ \left| \ A\subseteq B\right. \right\} \end{aligned}$$

(1)

$$\begin{aligned} e_{\mathcal {K}}\left( A\right)= & {} \ \left\{ x\in A\ \left| \ x\notin \sigma _{\mathcal {K}}\left( A\diagdown x\right) \right. \right\} \text {.} \end{aligned}$$

(2)

Recalling that the collection $\mathcal {K}$ is closed under intersections, $\sigma _{\mathcal {K}}\left( A\right)$ is therefore the smallest convex set containing A—analogous to the “convex hull” of A—and $x\in A$ is an extreme point of A if its removal alters this convex hull.⁴

A convex opportunity relation (COR) is an EOR for which $e_{\succsim }$ is the extreme point operator for some ACG. An axiomatic characterisation of this class of ORs is provided in Theorem 3 (Sect. 5).

Inevitably, the conditions which determine the class of convex opportunity relations have mathematical links to other characterisations of ACGs, most notably with the recent work of Bossert et al. (2009), Danilov and Koshevoy (2009), Puppe and Xu (2010) and Danilov et al. (2015). These links are explored in Sect. 5.1. One contribution of the present paper is to emphasise the common mathematical foundations which underpin a range of disparate objects studied by economists, and to clarify the relationships amongst these structures.⁵

The importance of convex structure for analysing the value of opportunity was first suggested (to the best of our knowledge) by Klemisch-Ahlert (1993). As noted above, Klemisch-Ahlert assumes an exogenous convex shelling geometry on X. She considers binary relations on opportunity sets which satisfy (inter alia) a condition that she calls convex hull monotonicity: for any $A\subseteq X$ and any $x\in X\diagdown A$, $A\cup \left\{ x\right\} \sim A$ if x is contained in the convex hull of A and $A\cup \left\{ x\right\} \succ A$ otherwise. Elements of X which lie in the convex hull of A (according to the convex shelling geometry) are “opportunity-spanned” by A, while additions to A that strictly expand the convex hull represent strictly valuable increments in opportunity.⁶ Likewise, in our framework a COR satisfies convex hull monotonicity with respect to the rationalising ACG (Lemma 6).

Abstract convex geometries are a sub-class of closure spaces. Closure spaces provide an algebraic abstraction of the notion of a closure operation. (See Appendix A for a brief introduction to closure spaces.) The elements of a closure space, $\mathcal {K}$, represent the sets which are “closed” with respect to some (unspecified) operation, and $\sigma _{\mathcal {K}}\left( A\right)$ is the closure of A. An ACG is closure space in which this underlying operation has the algebraic flavour of forming convex combinations.

Given on OR, $\succsim$, it is natural to interpret the following as the “opportunity closure” of $A\subseteq X$:

$$\begin{aligned} \sigma _{\succsim }\left( A\right) \ =\ \left\{ x\in X\ \left| \ A\sim A\cup x\right. \right\} \text {.} \end{aligned}$$

We say that $\succsim$ is a closed opportunity relation (ClOR) if $\succsim$ is an OR and $\sigma _{\succsim }=\sigma _{\mathcal {K}}$ for some closure space, $\mathcal {K}$. We provide an axiomatic characterisation of the closed ORs in Sect. 4 (Theorem 1). It turns out that a closed OR need not be essential. However, the set of ClOR’s which are essential coincides exactly with the set of COR’s (Theorem 3).

Just as our characterisation of the convex ORs has connections to other characterisations of ACGs, our characterisation of the closed ORs likewise recalls related results on closure spaces and closure operators. These connections are explored in Sect. 4.1, where our Theorem 1 is compared with closely related results by Kreps (1979) and Danilov et al. (2015).

The next section introduces the notion of an opportunity relation. The essential opportunity relations are characterised in Sect. 3. It is convenient to analyse closed opportunity relations before introducing convex opportunity relations (i.e., to progress from less restrictive to more restrictive classes of ORs), so the former are studied in Sect. 4 and the latter in Sect. 5. Section 6 concludes. The Appendices contain background material on closure spaces (Appendix A) and abstract convex geometries (Appendix B).

2 Opportunity relations

First, some notation. Throughout the paper, X will denote a non-empty, finite set and $\succsim$ will denote a pre-order (reflexive and transitive binary relation) on $2^{X}$. We define $\succ$, $\sim$, $\precsim$ and $\prec$ from $\succsim$ in the usual way. We also omit brackets around singleton subsets of X whenever convenient. Finally, we use $\subseteq$ and $\subset$ to denote subsets and proper subsets respectively.

Given that $\succsim$ is not required to be complete, the restriction imposed by transitivity is mild. If $\succsim$ reflects the rankings that would be elicited by direct interrogation of the individual (rather than imputed from choice behaviour),⁷ then it is reasonable to suppose that most individuals would abstain rather than knowingly express rankings which violate transitivity. Such intransitivities are unlikely to be found, under close scrutiny, to be compatible with fully determinate preferences.

We shall be exclusively concerned with pre-orders that satisfy two further properties:⁸

Definition 1

An opportunity relation (OR) is a pre-order $\succsim \subseteq 2^{X}\times 2^{X}$ satisfying the following desirability (D) and monotonicity (M) conditions:

$$\begin{aligned} A\succ \emptyset \quad \text { for all non-empty }A\subseteq X \end{aligned}$$

(D)

$$\begin{aligned} \text {If }\emptyset \ne B\subseteq A\text { then }A\succsim B \end{aligned}$$

(M)

Monotonicity is self-explanatory. If the terms “opportunity” and “freedom” have any ordinal significance at all, monotonicity must certainly lie at the heart of it. Puppe and Xu (2010, p. 671) remark that M “seems to be an uncontroversial condition and we expect any sensible freedom-ranking should satisfy this condition”. The desirability assumption D is standard when $\succsim$ is defined over all subsets of X, rather than just the non-empty subsets.⁹

While M and D are relatively uncontroversial assumptions in this literature, they are not without substance, and since they are the foundation for all that follows, we briefly rehearse the usual objections and present our defences against them.

The obvious objection—to both M and D—is that X might contain noxious alternatives whose presence degrades an opportunity set. We are not persuaded by this objection for the following reasons.¹⁰

We wish to understand “opportunity” or “freedom” as notions that delimit what the individual can do. Any compulsion should be determined by what is excluded from an opportunity set, not what is included. Objections to M or D rely on the confounding effect of implicit compulsions that are assumed to accompany the presentation of an opportunity set. These elements of compulsion muddy the waters, obscuring our view of what “opportunity” or “freedom” entails in its purest sense.

Consider monotonicity. If we add a noxious alternative to a non-empty opportunity set, this will degrade the set only if its inclusion somehow compels the decision-maker to contemplate the noxious alternative more vividly than she otherwise might. We assume otherwise. In other words, we assume that the elements of X have all been fully contemplated by the decision-maker before any opportunity set is presented to her. She fully understands the world in which she lives, including its darker elements, and making a conscious choice to avoid unpleasant alternatives imposes no higher psychic cost than being compelled to avoid them. With this interpretation, M is innocuous even if X contains noxious elements.

The desirability assumption is questionable if X contains noxious elements and we assume that choice is “forced”—that an alternative must be chosen from the opportunity set with which the decision-maker is presented. If so, then presenting the decision-maker with a singleton opportunity set means imposing the sole alternative upon her. To avoid the implied compulsion, we maintain the assumption—or rather, the interpretation—that abstention from choice is always an option. It is the only option if the opportunity set is empty. Opportunity can only compel by restricting choice, not by imposing it.

Our interpretation therefore requires that clear meaning can be attached to the notion of not choosing, but this does not seem unduly restrictive.

Given that abstention is allowed, there is minimal loss of generality in further assuming that X contains only elements that are individually desirable: for any $x\in X$, the decision-maker would strictly prefer to choose than not if her opportunity set were $\left\{ x\right\}$. We shall make this assumption throughout. Together with M, it implies D.¹¹

The rest of the paper characterises various classes of ORs.

As a prelude, it will be useful to define a pair of operators associated with an opportunity relation.

Let $\succsim$ be an OR and let $e_{\succsim }:2^{X}\rightarrow 2^{X}$ be defined from $\succsim$ as follows: for any $A\subseteq X$,

$$\begin{aligned} e_{\succsim }\left( A\right) \ =\ \left\{ x\in A\ \left| \right. \ A\succ A\diagdown x\right\} \end{aligned}$$

The members of $e_{\succsim }\left( A\right)$ are called the essential elements of A (Puppe 1996).¹² Removing an essential element reduces the value of the opportunity represented by the set. The following lemma gives an equivalent definition of $e_{\succsim }$.

Lemma 1

If $\succsim$ is an OR then

$$\begin{aligned} e_{\succsim }\left( A\right) \ =\ {\displaystyle \bigcap } \{ B\in 2^{X}\ \left| \ B\subseteq A\text { and }A\sim B\right. \} \end{aligned}$$

for any $A\subseteq X$.

Proof

Given M, $A\sim A\diagdown x$ iff $x\notin e_{\succsim }\left( A\right)$, so

$$\begin{aligned} {\displaystyle \bigcap } \{ B\in 2^{X}\ \vert \ B\subseteq A\text { and } \left| \ A\sim B\right. \} \ \subseteq \ e_{\succsim }\left( A\right) \text {.} \end{aligned}$$

To show the reverse inclusion, suppose $x\in e_{\succsim }\left( A\right)$ and $B\subseteq A\sim B$. We must prove that $x\in B$. If $x\notin B$ then

$$\begin{aligned} A\sim B\subseteq A\diagdown x\text {.} \end{aligned}$$

M and transitivity therefore give $A\sim A\diagdown x$, which contradicts $x\in e_{\succsim }\left( A\right)$.

The second operator is a natural “dual” to $e_{\succsim }$. Given $\succsim$, we define $\sigma _{\succsim }:2^{X}\rightarrow 2^{X}$ as follows: for any $A\subseteq X$,

$$\begin{aligned} \sigma _{\succsim }\left( A\right)&= \left\{ x\in X\ \left| \ A\sim A\cup x\right. \right\} \nonumber \\&= A\cup \left\{ x\in X\diagdown A\ \left| \ x\notin e\left( A\cup x\right) \right. \right\} \end{aligned}$$

(3)

The set $\sigma _{\succsim }\left( A\right)$ augments A with all of the elements which, individually, add no value. The following result, which mirrors Lemma 1, gives an equivalent definition of $\sigma _{\succsim }$.

Lemma 2

If $\succsim$ is an OR then

$$\begin{aligned} \sigma _{\succsim }\left( A\right) = {\displaystyle \bigcup } \left\{ B\in 2^{X}\ \left| \ A\subseteq B\text { and }A\sim B\right. \right\} \end{aligned}$$

for any $A\subseteq X$.

Proof

Since $A\sim A\cup x$ for every $x\in \sigma _{\succsim }\left( A\right)$, it is obvious that

$$\begin{aligned} \sigma _{\succsim }\left( A\right) \ \subseteq \ {\displaystyle \bigcup } \left\{ B\in 2^{X}\ \left| \ A\subseteq B\text { and }A\sim B\right. \right\} \text {.} \end{aligned}$$

Conversely, suppose $A\subseteq B\sim A$ and $z\in B$. Then

$$\begin{aligned} A\subseteq A\cup z\subseteq B\sim A\text {.} \end{aligned}$$

Using M and transitivity we deduce $A\sim A\cup z$. That is, $z\in \sigma _{\succsim }\left( A\right)$.$\square$

Note that the proofs of Lemmas 1 and 2 only make use of transitivity and monotonicity (M); the desirability condition (D) is not needed.

3 Essential opportunity relations

The elements of $e_{\succsim }\left( A\right)$ are individually essential to the opportunity represented by A. However, they may not be collectively sufficient. It is possible that $A\succ e_{\succsim }\left( A\right)$.

Example 1

Suppose $X=\left\{ a,b,c\right\}$ and $\succsim$ is the weak order (i.e., complete pre-order) satisfying

$$\begin{aligned} \emptyset \prec a\sim b\sim c\sim \left\{ b,c\right\} \prec \left\{ a,b\right\} \sim \left\{ a,c\right\} \sim X\text {.} \end{aligned}$$

This is an OR but $e_{\succsim }\left( X\right) =\left\{ a\right\} \prec X$.

If $A\sim e_{\succsim }\left( A\right)$ for all $A\subseteq X$, then $\succsim$ is said to satisfy the Independence of Non-Essential alternatives (INE) property (Puppe 1996).¹³ We call an opportunity relation that satisfies INE an essential opportunity relation (EOR). For an EOR, the essential elements of A carry the full value of the opportunity represented by A.

The following lemma gives some useful properties of EORs.

Lemma 3

Let $\succsim$ be an EOR with essential element operator $e_{\succsim }$. Then the following hold for any $A,B\in 2^{X}$:

• (i) If $A\ne \emptyset$ then $e_{\succsim }\left( A\right) \ne \emptyset$.

• (ii) If $B\subseteq A$ then $A\sim B$ iff $e_{\succsim }\left( A\right) =e_{\succsim }\left( B\right)$.

• (iii) If $e_{\succsim }\left( A\right) \subseteq B\subseteq A$ then $e_{\succsim }\left( B\right) =e_{\succsim }\left( A\right)$.

Proof

To show (i), suppose $A\ne \emptyset$. If $e_{\succsim }\left( A\right) =\emptyset$ then INE implies $A\sim \emptyset$ which contradicts desirability (D).

Next, consider (ii). If $e_{\succsim }\left( A\right) =e_{\succsim }\left( B\right)$ then $A\sim B$ follows by INE and transitivity. Conversely, suppose $B\subseteq A\sim B$. Then transitivity and Lemma 1 imply $e_{\succsim }\left( A\right) \subseteq e_{\succsim }\left( B\right)$. Hence $e_{\succsim }\left( A\right) \subseteq B$ and $e_{\succsim }\left( A\right) \sim A\sim B$, so $e_{\succsim }\left( B\right) \subseteq e_{\succsim }\left( A\right)$ by another application of Lemma 1.

Finally, consider (iii). If $e\left( A\right) \subseteq B\subseteq A$ then INE and M imply $A\sim B$ and the result follows by (ii). $\square$

Property (i) is Axiom F in Puppe (1996). As the proof of Lemma 3 makes clear, Axiom F is a logical consequence of desirability (D) and the INE property. Property (iii) says that removing non-essential elements does not alter the set of essential elements;¹⁴ while property (ii) says that adding new elements leads to a material improvement in opportunity if and only if it changes the set of essential elements.¹⁵

INE is imposed as an axiom in Puppe (1996) and Puppe and Xu (2010), but is easily deduced from more elementary properties. Consider the following property, which appears (unnamed) in Bossert et al. (2009; henceforth BRS):¹⁶

Definition 2

An OR $\succsim$ satisfies Collective Contraction Non-essentiality (CCN) if, for all $A\subseteq X$ and all $x,y\in A$,

$$\begin{aligned} A\sim A\diagdown x\sim A\diagdown y~~~\Rightarrow ~~~A\sim A\diagdown \left\{ x,y\right\} \text {.} \end{aligned}$$

Lemma 4

Let $\succsim$ be an OR. Then $\succsim$ is an EOR iff $\succsim$ satisfies CCN.

Proof

To show the “if” part, suppose CCN holds and $A=e_{\succsim }\left( A\right) \cup \left\{ x_{1},\ldots ,x_{n}\right\}$. Thus $A\sim A\diagdown x_{i}$ for each $i\in \left\{ 1,\ldots ,n\right\}$. We show that $A\sim A\diagdown B$ for any $B\subseteq \left\{ x_{1},\ldots ,x_{n}\right\}$ by induction on $\left| B\right|$. If $\left| B\right| =1$ this follows by assumption. Let $k\in \left\{ 1,\ldots ,n-1\right\}$ and suppose it is true for $\left| B\right| \in \left\{ 1,\ldots ,k\right\}$. Let $B\subseteq \left\{ x_{1},\ldots ,x_{n}\right\}$ with $\left| B\right| =k+1$. It is without loss of generality (WLOG) to assume that $B=\left\{ x_{1},\ldots ,x_{k+1}\right\}$. By transitivity and the inductive hypothesis

$$\begin{aligned} A\sim A\diagdown \left\{ x_{1},\ldots ,x_{k-1}\right\} \sim A\diagdown \left\{ x_{1},\ldots ,x_{k}\right\} \sim A\diagdown \left\{ x_{1},\ldots ,x_{k-1},x_{k+1}\right\} \end{aligned}$$

Hence CCN implies

$$\begin{aligned} A\sim A\diagdown \left\{ x_{1},\ldots ,x_{k-1}\right\} \sim A\diagdown \left\{ x_{1},\ldots ,x_{k+1}\right\} =A\diagdown B\text {.} \end{aligned}$$

Conversely, suppose CCN does not hold. Then there exists $A\subseteq X$ and $x,y\in A$ such that $A\sim A\diagdown x\sim A\diagdown y$ but $A\succ A\diagdown \left\{ x,y\right\}$. It follows that $e_{\succsim }(A) \subseteq A\diagdown \{x,y\}$ so M implies

$$\begin{aligned} A\succ A\diagdown \left\{ x,y\right\} \succsim e_{\succsim }\left( A\right) \end{aligned}$$

Hence $A\succ e_{\succsim }\left( A\right)$ by transitivity. $\square$

If $\succsim$ is an EOR, then Lemmas 2 and 3 imply that

$$\begin{aligned} \sigma _{\succsim }\left( A\right) \ =\ {\displaystyle \bigcup } \left\{ B\in 2^{X}\ \left| \ A\subseteq B\text { and }e\left( A\right) =e\left( B\right) \right. \right\} \end{aligned}$$

(4)

for any $A\subseteq X$. It is therefore tempting to interpret $\sigma _{\succsim }\left( A\right)$ as the “opportunity span” (or “opportunity closure”) of A, and the elements of $e_{\succsim }\left( A\right)$ as the critical (or “extreme”) points that support this opportunity span. However, as we show in the next section, not all EORs are able to bear this interpretation. The ones that are will be characterised in Sect. 5.

4 Closed opportunity relations

The notion of a closure space (Appendix A) provides an abstract algebraic characterisation of closure operations. Every closure space has an associated closure operator and extreme point operator. The closure operator maps each subset of X to its closure. The extreme points of a set are the elements whose individual removal would strictly diminish the closure (or span) of the set. Formal definitions are given in Appendix A.

While it is natural to interpret $\sigma _{\succsim }\left( A\right)$ as the “opportunity closure” of A, the operator $\sigma _{\succsim }$ need not possess the formal properties of a closure operator—properties (CC0)-(CC3) in Appendix A—even if $\succsim$ is an EOR (Example 2). An OR for which $\sigma _{\succsim }$ is a closure operator will be called a closed opportunity relation (ClOR). The following result implies that we could equally well define a closed OR to be an OR whose essential element operator is the extreme point operator for some closure space.

Lemma 5

Let $\succsim$ be an OR. If $\sigma _{\succsim }$ is the closure operator for some closure space on X then $e_{\succsim }$ is the associated extreme point operator for that closure space. Likewise, if $e_{\succsim }$ is the extreme point operator for some closure space on X , then $\sigma _{\succsim }$ is the associated closure operator.

Proof

Suppose $\sigma _{\succsim }$ is the closure operator for some closure space and $x\in e_{\succsim }\left( A\right)$. That is, $A\succ A\diagdown x$ and hence $x\notin \sigma _{\succsim }(A\diagdown x)$. Since $\sigma _{\succsim }$ is monotone with respect to set inclusion (see property (CC2) in Appendix A) and $x\in \sigma _{\succsim }\left( A\right)$, it follows that $\sigma _{\succsim }(A\diagdown x) \subset \sigma _{\succsim }\left( A\right)$. That is, x is an extreme point of A. Conversely, suppose x is an extreme point of A, so $\sigma _{\succsim }(A\diagdown x) \subset \sigma _{\succsim }\left( A\right)$. If $x\in \sigma _{\succsim }(A\diagdown x)$ then $A\subseteq \sigma _{\succsim }(A\diagdown x)$ and hence

$$\begin{aligned} \sigma _{\succsim }\left( A\right) \subseteq \sigma _{\succsim }(\sigma _{\succsim }(A\diagdown x)) =\sigma _{\succsim }(A\diagdown x) \end{aligned}$$

by the monotonicity and idempotency of $\sigma _{\succsim }$ (properties (CC2) and (CC3) in Appendix A). This contradicts $\sigma _{\succsim }( A\diagdown x) \subset \sigma _{\succsim }\left( A\right)$, so we must have $x\notin \sigma _{\succsim }(A\diagdown x)$. It follows that $A\succ A\diagdown x$, and therefore $x\in e_{\succsim }( A)$. This proves the first claim. The second follows directly from (3) above and (19) in Appendix A. $\square$

The following example shows that not every EOR is closed.

Example 2

Suppose $X=\left\{ a,b,c\right\}$ and let $\succsim$ be the following weak order:

$$\begin{aligned} \emptyset \prec b\sim c\prec a\sim \left\{ a,b\right\} \prec \left\{ a,c\right\} \prec \left\{ b,c\right\} \prec X\text {.} \end{aligned}$$

This is an OR and satisfies CCN. In fact, it is easily verified that

$$\begin{aligned} A\sim \sigma _{\succsim }\left( A\right) \sim e_{\succsim }\left( A\right) \end{aligned}$$

for all $A\subseteq X$. However, $\sigma _{\succsim }\left( a\right) =\left\{ a,b\right\}$ while $\sigma _{\succsim }\left( \left\{ a,c\right\} \right) =\left\{ a,c\right\}$, so $\sigma _{\succsim }$ violates the monotonicity property of a closure operator (Property (CC2) in Appendix A) which requires that $\sigma _{\succsim }\left( A\right) \subseteq \sigma _{\succsim }\left( B\right)$ whenever $A\subseteq B$.

The following condition is necessary and sufficient for an OR to be closed (Theorem 1).

Definition 3

An OR $\succsim$ satisfies Expansion Monotonicity (EM) if, for all $A\subseteq X$ and all $x,y\in X\diagdown A$,

$$\begin{aligned} A\sim A\cup x \Rightarrow A\cup y\sim A\cup \left\{ x,y\right\} \text {.} \end{aligned}$$

Note that the OR in Example 2 violates EM: take $A=\left\{ a\right\}$, $x=b$ and $y=c$.

Lemma 6 illustrates some useful consequences of EM. To state this result we first introduce the following generalisation of convex hull monotonicity (Klemisch-Ahlert 1993):

Definition 4

An OR $\succsim$ satisfies closure monotonicity (CM) if the following hold for any $A,B\in 2^{X}$:

$$\begin{aligned} \sigma _{\succsim }\left( B\right) \subseteq \sigma _{\succsim }\left( A\right) \Rightarrow A\succsim B \end{aligned}$$

and

$$\begin{aligned} \sigma _{\succsim }\left( B\right) \subset \sigma _{\succsim }\left( A\right) \Rightarrow A\succ B\text {.} \end{aligned}$$

Lemma 6

If $\succsim$ is an OR satisfying EM then:

• (i) $A\sim \sigma _{\succsim }\left( A\right)$ for any $A\subseteq X$.¹⁷

• (ii) $\succsim$ satisfies CM.

Proof

Consider (i). Let $\sigma _{\succsim }\left( A\right) =A\cup \left\{ x_{1},\ldots ,x_{n}\right\}$. Thus $A\sim A\cup x_{i}$ for each $i\in \left\{ 1,\ldots ,n\right\}$. We show that $A\sim A\cup B$ for any $B\subseteq \left\{ x_{1},\ldots ,x_{n}\right\}$ by induction on $\left| B\right|$. If $\left| B\right| =1$ this follows by assumption. Let $k\in \left\{ 1,\ldots ,n-1\right\}$ and suppose it is true for $\left| B\right| \in \left\{ 1,\ldots ,k\right\}$. Let $B\subseteq \left\{ x_{1},\ldots ,x_{n}\right\}$ with $\left| B\right| =k+1$. It is WLOG to assume that $B=\left\{ x_{1},\ldots ,x_{k+1}\right\}$. By transitivity and the inductive hypothesis

$$\begin{aligned} A\sim A\cup \left\{ x_{1},\ldots ,x_{k-1}\right\} \sim A\cup \left\{ x_{1},\ldots ,x_{k}\right\} \sim A\cup \left\{ x_{1},\ldots ,x_{k-1},x_{k+1}\right\} \end{aligned}$$

Hence EM implies

$$\begin{aligned} A\sim A\cup \left\{ x_{1},\ldots ,x_{k-1}\right\} \sim A\cup \left\{ x_{1},\ldots ,x_{k+1}\right\} =A\cup B\text {.} \end{aligned}$$

Next, we show (ii). If $\sigma _{\succsim }\left( B\right) \subseteq \sigma _{\succsim }\left( A\right)$ then $\sigma _{\succsim }\left( A\right) \succsim \sigma _{\succsim }\left( B\right)$ by M. Applying Lemma 6(i) and transitivity we deduce $A\succsim B$. If $\sigma _{\succsim }\left( B\right) \subset \sigma _{\succsim }\left( A\right)$ then $A\succsim B$ as just shown. Suppose $A\sim B$. Then Lemma 6(i) and transitivity imply $\sigma _{\succsim }\left( A\right) \sim B$. Since $B\subseteq \sigma _{\succsim }\left( B\right) \subset \sigma _{\succsim }\left( A\right)$ we have $B\subseteq \sigma _{\succsim }\left( A\right) \sim B$, and therefore $\sigma _{\succsim }\left( A\right) \subseteq \sigma _{\succsim }\left( B\right)$ by Lemma 2. This is a contradiction, so we must have $A\succ B$. $\square$

The EM property appears (unnamed) in BRS. For binary relations which are transitive and satisfy M (such as ORs), EM is equivalent to a number of variant conditions that have appeared elsewhere in the literature. For example, taking the contrapositive of EM and applying M, we obtain the following property: for all $B\subseteq X$ and all $x,y\in B$ with $x\ne y$

$$\begin{aligned} B\succ B\diagdown x \Rightarrow B\diagdown y\succ B\diagdown \left\{ x,y\right\} \end{aligned}$$

Given transitivity, this is equivalent to the Contraction Consistency (CC) condition of Nehring and Puppe (1999):¹⁸ for all $A,B\in 2^{X}$ with $A\subseteq B$ and all $x\in A$

$$\begin{aligned} B\succ B\diagdown x~~~\Rightarrow ~~~A\succ A\diagdown x \end{aligned}$$

(6)

Given M and transitivity, (6) is equivalent to the strict contraction monotonicity condition (Ryan 2014):¹⁹ for all $A,B,C\in 2^{X}$ with $C\subseteq A\subseteq B$

$$\begin{aligned} B\succ B\diagdown C\ \ \ \Rightarrow \ \ \ A\succ A\diagdown C \end{aligned}$$

(7)

Taking the contrapositive of (7), we obtain property (1.5) from Kreps (1979):²⁰ for all $A,B,C\in 2^{X}$ with $A\subseteq B$

$$\begin{aligned} A\sim B\ \ \ \Rightarrow \ \ \ A\cup C\sim B\cup C \end{aligned}$$

(8)

Moreover, if we re-express (6) in terms of essential elements, we obtain the Heritage Axiom (also known as the Chernoff Property or Property $\alpha$), which is familiar from the literature on choice functions (Moulin 1985): for all $A,B\in 2^{X}$

$$\begin{aligned} A\subseteq B \Rightarrow e_{\succsim }\left( B\right) \cap A\subseteq e_{\succsim }\left( A\right) \end{aligned}$$

(9)

Theorem 1

Let $\succsim$ be an OR. Then $\succsim$ satisfies EM iff $\succsim$ is closed.

Proof

Suppose $\succsim$ is an OR that satisfies EM. It is obvious that $\sigma _{\succsim }\left( \emptyset \right) =\emptyset$ and that $A\subseteq \sigma _{\succsim }\left( A\right)$ for any $A\subseteq X$. It remains to verify monotonicity and idempotency—properties (CC2) and (CC3) in Appendix A. Let $A\subseteq B$ and let $x\in X$ be such that $A\sim A\cup x$. If $x\in B$ then $B\sim B\cup x$ by reflexivity. If $x\in X\diagdown B$ then $B\sim B\cup x$ by iterative application of EM for each $y\in B\diagdown A$. Hence $\sigma _{\succsim }\left( A\right) \subseteq \sigma _{\succsim }\left( B\right)$. This proves that $\sigma _{\succsim }$ is monotone. It follows that $\sigma _{\succsim }\left( A\right) \subseteq \sigma _{\succsim }( \sigma _{\succsim }\left( A\right) )$ for any $A\subseteq X$. To verify idempotency it suffices to show that $\sigma _{\succsim }( \sigma _{\succsim }\left( A\right) ) \subseteq \sigma _{\succsim }\left( A\right)$. Suppose there exists $x\in \sigma _{\succsim }( \sigma _{\succsim }\left( A\right) ) \diagdown \sigma _{\succsim }\left( A\right)$. Then $A\cup x\succ A$. Since $\sigma _{\succsim }\left( A\right) \cup x\succsim A\cup x$ by M, we have

$$\begin{aligned} \sigma _{\succsim }\left( A\right) \cup x\succ A \end{aligned}$$

(10)

by transitivity. By applying Lemma 6(i) and transitivity to (10), we have $\sigma _{\succsim }\left( A\right) \cup x\succ \sigma _{\succsim }\left( A\right)$, which contradicts $x\in \sigma _{\succsim }( \sigma _{\succsim }\left( A\right) )$.

Conversely, let $\succsim$ be a ClOR. Suppose $A\sim A\cup x$. Then $x\in \sigma _{\succsim }\left( A\right) \subseteq \sigma _{\succsim }\left( A\cup y\right)$, so $A\cup y\sim A\cup \left\{ x,y\right\}$. $\square$

Theorem 1 shows that the defining characteristic of a closed opportunity relation is the Heritage property: an essential element remains essential if other elements (essential or otherwise) are removed. Furthermore, Lemma 6(ii) says that the Heritage property implies closure monotonicity: if the closure of A (properly) contains the closure of B, then A is (strictly) preferred to B.

It is important to observe that EM does not imply CCN: not every ClOR is an EOR.

Example 3

Let $X=\left\{ x,y\right\}$ and consider the weak order on $2^{X}$ given by

$$\begin{aligned} \emptyset \prec x\sim y\sim X\text {.} \end{aligned}$$

It is trivial to confirm that this is an OR which satisfies EM but violates CCN.

The next section characterises the ClORs which are also EORs.

Before concluding this section, let us observe that a complete ClOR has an expected indirect utility representation. This follows from Kreps (1979, Theorem 1) and the fact that an OR satisfies EM if and only if it satisfies (8). In fact, we can say more: if $\succsim$ is a ClOR then there exists a complete ClOR $\succsim ^{\prime }$ that extends $\succsim$ (in the sense that $\succ \subseteq \succ ^{\prime }$ and $\sim \subseteq \sim ^{\prime }$) and has an expected indirect utility representation. It is straightforward to show that any pre-order on $2^{X}$ can be extended to a weak order. If the original pre-order is a ClOR then so is any extension, since D, M and EM only restrict its non-extended part.

4.1 Related results

Closure spaces arise in many contexts and may be characterised in many ways. Ando (2006, Theorem 2) gives an axiomatic characterisation of the extreme point operators associated with closure spaces,²¹ and hence, implicitly, a characterisation of the essential element operators associated with ClORs.²²

Theorem 1 characterises the ORs for which the mapping (3) determines a closure operator. This result is a close relative of Proposition 5 in Danilov et al. (2015) (henceforth DKS), who also study closure operators constructed from binary relations. As DKS observe, the same result has been independently re-discovered in variant forms by several authors, with Kreps (1979, Lemmas 1 and 2) being its first appearance in the economics literature.

DKS characterise various classes of what they call hyper-relations, which are binary relations on $2^{X}$. One of these is the class of transitive decent hyper-relations. In our terminology, a transitive decent hyper-relation $\succsim ^{*}$ is an OR which satisfies the following Union property: for any $A,B,C\in 2^{X}$

$$\begin{aligned}{}[ C\succsim ^{*}A\ \ \text {and}\ \ C\succsim ^{*}B] \ \ \ \Rightarrow \ \ \ C\succsim ^{*}A\cup B \end{aligned}$$

Proposition 5 in DKS shows that if $\succsim ^{*}$ is a transitive decent hyper-relation, then the operator $\mu :2^{X}\rightarrow 2^{X}$ defined by

$$\begin{aligned} \mu \left( A\right) \ =\ \{ x\in X\ \left| \ A\succsim ^{*}x\right. \} \end{aligned}$$

(11)

is a closure operator.

To connect the DKS result with our Theorem 1, recall that the dominance (or domination) relation $\succsim ^{*}\subseteq 2^{X}\times 2^{X}$ associated with a given binary relation $\succsim \subseteq 2^{X}\times 2^{X}$ is defined thus (Kreps 1979):

$$\begin{aligned} A\succsim ^{*}B\ \ \ \Leftrightarrow \ \ \ A\succsim A\cup B \end{aligned}$$

Observe that $\mu$ coincides with the operator $\sigma _{\succsim }$ expressed in terms of the associated dominance relation, since (given M) we have:

$$\begin{aligned} A\succsim ^{*}x\ \ \Leftrightarrow \ \ A\succsim A\cup x\ \ \Leftrightarrow \ \ A\sim A\cup x \end{aligned}$$

for any $A\subseteq X$ and any $x\in X$.

The dominance relation associated with an OR will obviously satisfy M (hence reflexivity) and also D, but need not be transitive.²³ If it is transitive (hence, itself an OR), then $\mu$ is equivalent to the mapping $\phi :2^{X}\rightarrow 2^{X}$ given by

$$\begin{aligned} \phi \left( A\right) \ =\ {\displaystyle \bigcup } \{ B\in 2^{X}\ \left| \ A\succsim ^{*}B\right. \} \end{aligned}$$

Kreps (1979) proves that if $\succsim$ is a complete OR satisfying EM,²⁴ then its dominance relation $\succsim ^{*}$ is transitive (ibid., Lemma 1) and $\phi$ is a closure operator (ibid., Lemma 2).

The following result therefore ties together our Theorem 1 with Kreps (1979, Lemmas 1 and 2) and DKS (Proposition 5):

Theorem 2

Let $\succsim$ be an OR with associated dominance relation $\succsim ^{*}$. The following are equivalent:

• (a) $\succsim$ is a ClOR

• (b) $\succsim ^{*}$ is transitive.

• (c) $\succsim ^{*}$ is transitive and satisfies the Union property.

Proof

Let $\succsim$ be a ClOR. Puppe (1996, Lemma 1) implies that $\succsim ^{*}$ is transitive.²⁵ We next show that $\succsim ^{*}$ also satisfies the Union property. If $A\succsim ^{*}B$ and $A\succsim ^{*}C$ then M implies $A\sim A\cup B$ and $A\sim A\cup C$. Using Lemma 2 and Lemma 6(i), we therefore deduce that $A\cup B\cup C\subseteq \sigma _{\succsim }\left( A\right) \sim A$. Applying M and transitivity (of $\succsim$) gives $A\succsim ^{*}B\cup C$.

We have thus established that (a) implies (c). Since the latter obviously implies (b), it remains to show that (b) implies (a). Suppose that $\succsim$ is an OR and $\succsim ^{*}$ is transitive. The EM condition may be expressed as follows:

$$\begin{aligned} A\succsim ^{*}x\ \ \ \Rightarrow \ \ \ A\cup y\succsim ^{*}x \end{aligned}$$

(EM)

for any $A\subseteq X$ and any $x,y\in X\diagdown A$. Since M implies $A\cup y\succsim ^{*}A$ for any $A\subseteq X$ and any $y\in X$, EM follows by the transitivity of $\succsim ^{*}$. $\square$

Kreps (1979) studies pre-orders on opportunity sets which are also complete (i.e., weak orders). However, this distinction is inconsequential in the present context, since, as noted above, any ClOR may be extended to a complete ClOR and the extension will have the same dominance relation as the original, since the latter satisfies M. Thus, our Theorem 1 is essentially the result of Kreps (1979), albeit in disguised form and without the redundant assumption of completeness.

The result of DKS is complementary. DKS work with objects which are most naturally interpreted as dominance relations. Their Proposition 5 provides (implicitly) a characterisation of the dominance relations associated with ClORs:²⁶ for a given OR, its dominance relation is transitive and satisfies the Union property if and only if the OR is closed. The connection between the EM property of $\succsim$ and transitivity of the associated dominance relation $\succsim ^{*}$ was established by Kreps (1979) and Puppe (1996). The connection between EM and the Union property of $\succsim ^{*}$ is even easier to see. The EM condition and transitivity of $\succsim$ imply that the following holds for any $A\in 2^{X}$ and any $x,y\in X$:

$$\begin{aligned}{}[ A\succsim ^{*}x\ \ \text {and}\ \ A\succsim ^{*}y] \ \ \Rightarrow \ \ A\succsim ^{*}\left\{ x,y\right\} \end{aligned}$$

(12)

This is already limited form of the Union property. The proof of Theorem 2 shows that it can be leveraged into the full strength of the Union property without additional assumptions on $\succsim$.

It is also worthy of note that condition (12) may be equivalently expressed as follows: for any $A\in 2^{X}$ and any $x,y\in X$

$$\begin{aligned} x\in \sigma _{\succsim }\left( A\right) \ \ \Rightarrow \ \ \sigma _{\succsim }\left( A\cup x\right) \subseteq \sigma _{\succsim }\left( A\right) \end{aligned}$$

(T)

In this form, it will be recognised as the transitivity property of the operator $\sigma _{\succsim }$ (Danilov and Koshevoy 2009). Danilov and Koshevoy (2009, Lemma 2) prove that idempotency—condition (CC3) in Appendix A—may be replaced by (T) in the axiomatic characterisation of closure operators.

Proposition 5 of DKS implies not only that the dominance relation of any ClOR is a transitive decent hyper-relation, but also that any transitive decent hyper-relation induces a closure operator via (11). This leaves open the question of whether every transitive decent hyper-relation is the dominance relation for some ClOR. The following result provides an affirmative answer.

Proposition 1

If $\succsim ^{*}$ is a transitive decent hyper-relation (i.e., an OR that satisfies the Union property), then it is a ClOR and it coincides with its own dominance relation.

Proof

We will show that

$$\begin{aligned} A\succsim ^{*}B\ \ \ \Leftrightarrow \ \ \ A\succsim ^{*}A\cup B\ \ \ \Leftrightarrow \ \ \ A\sim ^{*}A\cup B \end{aligned}$$

(13)

for all $A,B\in 2^{X}$, from which the result follows. In particular, the equivalence of the first and last expressions in (13) implies that $\mu =\sigma _{\succsim ^{*}}$ and hence that $\succsim ^{*}$ is a ClOR. The first equivalence in (13) says that $\succsim ^{*}$ coincides with its dominance relation.

The second equivalence in (13) follows by monotonicity (M). If $A\succsim ^{*}B$, then reflexivity (in particular, $A\succsim ^{*}A$) and the Union property give $A\succsim ^{*}A\cup B$. Conversely, if $A\succsim ^{*}A\cup B$ we deduce $A\succsim ^{*}B$ from M (in particular, $A\cup B\succsim ^{*}B$) and transitivity. This establishes the first equivalence. $\square$

The transitive decent hyper-relations therefore constitute a subset of the closed opportunity relations. As the following example shows, it is a proper subset: an OR that satisfies the Union property necessarily satisfies EM, but the converse implication is false.

Example 4

Let $X=\left\{ x_{1},\ldots ,x_{n}\right\}$ with $n\ge 3$ and define $\succsim \subseteq 2^{X}\times 2^{X}$ as follows:

$$\begin{aligned} A\succsim B\ \ \ \Leftrightarrow \ \ \ \left| A\right| \ge \left| B\right| \end{aligned}$$

where $\left| E\right|$ denotes the cardinality of the set E. This is clearly an OR. It is also obvious that $\sigma _{\succsim }$ is the identity operator, which is the closure operator for the closure space $\mathcal {K}=2^{X}$. Hence, $\succsim$ is a ClOR. However, $\succsim$ does not satisfy the Union property: if $A=\left\{ x_{1}\right\}$, $B=\left\{ x_{2}\right\}$ and $C=\left\{ x_{3}\right\}$, then $A\succsim B$ and $A\succsim C$, but $B\cup C\succ A$. Note that the dominance relation for $\succsim$ is the set inclusion relation: $A\succsim ^{*}B$ iff $A\supseteq B$. This, of course, does satisfy the Union property.

5 Convex opportunity relations

An abstract convex geometry (ACG) is a special type of closure space for which the (implicit) closure operation is analogous to forming a convex hull—see Appendix B. An OR, $\succsim$, will be called a convex opportunity relation (COR) if $\sigma _{\succsim }$ is the closure operator for some ACG. The convex opportunity relations therefore comprise a subset of the closed opportunity relations. More precisely, the convex opportunity relations consist of the closed opportunity relations which are also essential (Theorem 3). In other words, within the universe of ORs, the set of CORs is the intersection of the set of ClORs with the set of EORs.

Theorem 3

Let $\succsim$ be a ClOR. Then $\succsim$ is a COR iff $\succsim$ satisfies CCN.

Proof

Since $\succsim$ is a ClOR, $\sigma _{\succsim }$ is a closure operator (Theorem 1) and $e_{\succsim }$ its associated extreme point operator (Lemma 5). We must therefore show that $\sigma _{\succsim }$ satisfies the anti-exchange property (condition (CC4) in Appendix B) iff $\succsim$ satisfies CCN.

Suppose $\sigma _{\succsim }$ satisfies the anti-exchange property and $A\sim A\diagdown x\sim A\diagdown y$, where $\left\{ x,y\right\} \subseteq A\subseteq X$. Then

$$\begin{aligned} x\in \sigma _{\succsim }[(A\diagdown \left\{ x,y\right\} ) \cup y] \ \ \text {and}\ \ y\in \sigma _{\succsim }[ (A\diagdown \{x,y\})\cup x] \end{aligned}$$

(14)

Defining $E=\sigma _{\succsim }(A\diagdown \left\{ x,y\right\} ),$ the monotonicity of $\sigma _{\succsim }$ and (14) imply $x\in \sigma _{\succsim }\left( E\cup y\right)$ and $y\in \sigma _{\succsim }\left( E\cup x\right)$. Since $\sigma _{\succsim }$ satisfies the anti-exchange property, we must have $x\in E$ or $y\in E$. Thus, either $A\diagdown \left\{ x,y\right\} \sim A\diagdown x$ or $A\diagdown \left\{ x,y\right\} \sim A\diagdown y$, from which we deduce $A\diagdown \left\{ x,y\right\} \sim A$.

Conversely, suppose $\succsim$ is a ClOR that satisfies CCN. Let E be a closed set in the associated closure space (Appendix A) and let $x,y\in X\diagdown E$. Then $E\cup \left\{ x,y\right\} \succ E$ by CM (Lemma 6). Suppose $x\in \sigma _{\succsim }\left( E\cup y\right)$. We cannot have $y\in \sigma _{\succsim }\left( E\cup x\right)$ since this would imply

$$\begin{aligned} E\cup \left\{ x,y\right\} \sim E\cup y\sim E\cup x \end{aligned}$$

from which $E\cup \left\{ x,y\right\} \sim E$ follows by CCN.$\square$

Thus, when an OR satisfies both CCN and EM, the value of opportunity resides entirely within its set of essential elements (INE) and there is a subjective ACG, $\mathcal {K}$, such that $e_{\succsim }=e_{\mathcal {K}}$. In particular, CORs satisfy closure monotonicity (Lemma 6). This generalises Klemisch-Ahlert’s (1993) notion of convex hull monotonicity from convex shelling geometries to general ACGs. Theorem 3 also endogenises the convex structure that determines the decision-maker’s personal notion of essentiality.

There exist ACGs which cannot be realised as convex shelling geometries (Kashiwabara et al. 2005). The following example shows that ACGs outside the convex shelling class are not without interest for our purposes.

Example 5

Let $X=\left\{ a,b,c,d\right\}$, where the elements of X correspond to the pure strategies of Player 2 (the column player) in the following two-player game:²⁷

	a	b	c	d
$\alpha$	$-\ ,\ 1$	$-\ ,\ 6$	$-\ ,\ 3$	$-\ ,\ 4$
$\beta$	$-\ ,\ 6$	$-\ ,\ 1$	$-\ ,\ 3$	$-\ ,\ 0$

We may therefore identify each $x\in X$ with a vector in $\mathbb {R}^{2}$. Define $\kappa :2^{X}\rightarrow 2^{X}$ as follows: $\kappa \left( A\right)$ consists of A together with any elements of $X\diagdown A$ which are strictly dominated by some mixture over the pure strategies in A. It can be shown that $\kappa$ is the closure operator for an ACG over X (Kukushkin 2004). Now, for each $A\subseteq X$, define $\kappa ^{*}\left( A\right)$ to be the convex shell of $\kappa \left( A\right) \subseteq \mathbb {R}^{2}$ in X; that is,

$$\begin{aligned} \kappa ^{*}\left( A\right) \ =\ \mathrm {co}\left( \kappa \left( A\right) \right) \cap X \end{aligned}$$

where $\mathrm {co}\left( E\right)$ denotes the Euclidean convex hull of $E\subseteq \mathbb {R}^{2}$. It is straightforward (and not too tedious) to verify that $\kappa ^{*}\equiv \kappa$ for this example.²⁸ Finally, define a binary relation $\succsim$ as follows: $A\succsim B$ iff $\left| \kappa ^{*}\left( A\right) \right| \ge \left| \kappa ^{*}\left( B\right) \right|$.²⁹

It is easy to verify that $\succsim$ is an EOR.³⁰ Furthermore,

$$\begin{aligned} e_{\succsim }\left( A\right) \ =\ \left\{ x\in A\ \left| \ \kappa ^{*}\left( A\diagdown x\right) \subset \kappa ^{*}\left( A\right) \right. \right\} \end{aligned}$$

for any $A\subseteq X$, so $e_{\succsim }$ is the extreme point operator associated with $\kappa ^{*}$. It follows that $\succsim$ is a COR and $\sigma _{\succsim }=\kappa ^{*}$ (Lemma 5). In other words, the decision-maker regards a pure strategy $x\in A$ to be essential to A iff it is neither payoff-equivalent to, nor strictly dominated by, any mixture of the other elements of A.

To see that $\kappa ^{*}$ cannot be the closure operator for any convex shelling geometry, observe that

$$\begin{aligned} \kappa ^{*}\left( \left\{ a,b\right\} \right) \ =\ X \end{aligned}$$

(15)

(since the equal mixture of a and b strictly dominates c) and

$$\begin{aligned} \kappa ^{*}\left( \left\{ b,d\right\} \right) \ =\ \left\{ b,d\right\} \end{aligned}$$

(16)

If $\kappa ^{*}$ were the closure operator for some convex shelling geometry, then the elements of X could be identified with points in $\mathbb {R}^{n}$ (for some n) such that $\kappa ^{*}\left( A\right)$ is the intersection of X with the (Euclidean) convex hull of A. From (15) we would therefore deduce that points c and d lie on the line segment in $\mathbb {R}^{n}$ joining a to b. Hence, (16) implies that c is between a and d. However, the latter implication is contradicted by the fact that³¹

$$\begin{aligned} \kappa ^{*}\left( \left\{ a,d\right\} \right) \ =\ \left\{ a,d\right\} \text {.} \end{aligned}$$

One of the three justifications provided by Klemisch-Ahlert (1993, p. 196) for assuming that the value of a set is the same as that of its convex hull, is that the decision-maker is able to choose by explicit randomisation and may regard the associated lottery as value-equivalent to its “expected realization”. Example 5 is entirely consistent with this justification, since mixtures are regarded as equivalent to pure strategies that deliver the same expected payoff for each rival strategy. In particular, $\mathrm {co}\left( A\right) \cap X\subseteq \kappa ^{*}\left( A\right)$ for any $A\subseteq X$. But this does not exclude the possibility that the decision-maker might perceive a “coarser” convex structure, such that $\mathrm {co}\left( A\right) \cap X$ may be strictly contained in the closure of A. As in Example 5, it will not always be possible to describe this coarser structure with a convex shelling geometry.

5.1 Related results

Combining Lemma 5 and Theorems 1, 3 and 4 we obtain:

Corollary 1

Let $\succsim$ be an OR. Then $\succsim$ satisfies EM and CCN iff $\sigma _{\succsim }$ is an anti-exchange closure operator and $A\sim e_{\succsim }\left( A\right)$ for all $A\subseteq X$.

Corollary 2

Let $\succsim$ be an OR. Then $e_{\succsim }$ is the extreme point operator for some ACG iff $\succsim$ satisfies EM and INE.

Corollary 1 is a variation on the main result in BRS. In the BRS version, $\succsim$ is assumed to be a weak order (i.e., a complete pre-order) that satisfies D but not necessarily M.

Corollary 2 strengthens Corollary 4.4 in Puppe and Xu (2010) by demonstrating the redundancy of Axiom F. (Recall that an OR satisfies EM iff it satisfies (9), which is Sen’s (1971) Property $\alpha$.) Likewise, Axiom F may be dropped from Puppe and Xu’s Proposition 4.7; less obviously, also from Puppe (1996, Proposition 2).³²

DKS provide a complementary perspective on Theorem 3. They characterise the dominance relations associated with CORs.³³ Section 6 of DKS considers the sub-class of transitive, decent hyper-relations which also satisfy the following condition:³⁴ for any $A,B\in 2^{X}$

$$\begin{aligned} A\sim ^{*}B\ \ \ \Rightarrow \ \ \ A\cap B\succsim ^{*}A \end{aligned}$$

(17)

DKS refer to these as ample hyper-relations.

Proposition 1 and Theorem 3 in DKS show that $\succsim ^{*}$ is an ample hyper-relation if and only if the operator $\psi :2^{X}\rightarrow 2^{X}$ defined by

$$\begin{aligned} \psi \left( A\right) \ =\ \{ x\in A\ \left| \ (A\diagdown x,x) \notin \succsim ^{*}\right. \} \end{aligned}$$

is the extreme point operator for some ACG. Observe that if $\succsim$ is an OR with associated dominance relation $\succsim ^{*}$, then $\psi =e_{\succsim }$: given $x\in A\subseteq X$

$$\begin{aligned} (A\diagdown x,x) \notin \succsim ^{*}\ \ \ \Leftrightarrow \ \ \ A\succ A\diagdown x\ \ \ \Leftrightarrow \ \ \ x\in e_{\succsim }\left( A\right) \end{aligned}$$

(where we have made use of M). Given our Theorem 2, the following is therefore a corollary of the DKS result, but we provide a direct proof.

Proposition 2

Let $\succsim$ be a ClOR with dominance relation $\succsim ^{*}$. Then $\succsim$ is a COR iff $\succsim ^{*}$ satisfies (17).

Proof

Let $\succsim$ be a COR. Then $\succsim$ is essential (Theorems 3, 4). Suppose $A\sim ^{*}B$. Then $A\sim A\cup B\sim B$ so Lemma 3(ii) implies $e_{\succsim }\left( A\cap B\right) =e_{\succsim }\left( A\right)$. Applying INE and transitivity we conclude that $A\cap B\sim A$, from which $A\cap B\succsim ^{*}A$ follows.

Conversely, let $\succsim$ be a ClOR whose dominance relation $\succsim ^{*}$ satisfies (17). We must show that $\succsim$ satisfies CCN (Theorem 3). Let $\left\{ x,y\right\} \subseteq A\subseteq X$ with $A\sim A\diagdown x\sim A\diagdown y$. Then $A\diagdown x\sim ^{*}A$ and $A\diagdown y\sim ^{*}A$. Since $\succsim ^{*}$ is transitive (Theorem 2), $A\diagdown x\sim ^{*}A\diagdown y$. Hence (17) implies $A\diagdown \left\{ x,y\right\} \succsim ^{*}A$, which is the desired conclusion. $\square$

There is also a close connection between our Theorem 3 and some results of Danilov and Koshevoy (2009). Their Proposition 5 and Corollary 3 imply the following:

Proposition 3

(Danilov and Koshevoy 2009) Let $e:2^{X}\rightarrow 2^{X}$ be an operator such that $e=e_{\mathcal {K}}$ for some closure space $\mathcal {K}$. Then e is the extreme point operator for an ACG iff it satisfies

$$\begin{aligned} \left[ x\in e\left( B\cup x\right) \ \ \text {and}\ \ y\in e\left( B\cup y\right) \right] \ \ \Rightarrow \ \ e\left( B\cup \left\{ x,y\right\} \right) \cap \left\{ x,y\right\} \ne \emptyset \end{aligned}$$

(N)

for any $B\in 2^{X}$ and any $x,y\in X\diagdown B$ with $x\ne y$.

Defining $A=B\cup \left\{ x,y\right\}$, the contrapositive of Danilov and Koshevoy’s condition N is:

$$\begin{aligned} e\left( A\right) \cap \left\{ x,y\right\} =\emptyset \quad \Rightarrow \quad [ x\notin e(A\diagdown y) \quad \text {or}\quad y\notin e(A\diagdown x)]. \end{aligned}$$

When $e=e_{\succsim }$ for some OR, this condition is easily seen to be equivalent to CCN, given the monotonicity and transitivity of $\succsim$.

6 Concluding remarks

The class of opportunity relations provides a simple and natural environment for exploring the ranking of opportunity sets. Our analysis reveals how two restrictions on ORs—the CCN and EM properties—underpin a range of important principles in the analysis of “freedom rankings”, including Puppe’s (1996) Axiom F and the Independence of Non-Essential alternatives (INE) property, as well as a generalised version of Klemisch-Ahlert’s (1993) convex hull monotonicity. Both of these conditions (EM and CCN) are simple and transparent. They also delineate the opportunity relations whose essential element mappings are the extreme point operators of closure spaces (EM alone) or ACG’s (EM and CCN). Our results, in this latter respect, complement the analysis of DKS, whose characterisations take the form of restrictions on dominance relations. Our Theorem 1 is also a close relative of Lemmas 1 and 2 in Kreps (1979).

According to Theorem 3, if the value of opportunity resides precisely in essential elements—the INE property—and coincides with the “opportunity span” of these essential elements according to some coherent subjective spanning criterion (i.e., some well-defined closure operator), then essential elements behave as extreme points relative to some underlying ACG. Convex structure therefore lies at the heart of such opportunity relations. This is arguably surprising, but certainty convenient: convex structure brings with it many useful and well-known properties.

While convex shellings provide a rich class of convex structures for discrete environments, they do not exhaust the ACGs. Example 5 shows that ACGs outside the convex shelling class may be necessary to describe ORs that are far from exotic. Restricting attention to convex shellings, as in Klemisch-Ahlert (1993), imposes substantive restrictions.

Finally, as will be clear from our discussion of the Related Literature (Sects. 4.1, 5.1), many of our results are synthetic rather than organic. They could have been derived in large part by suitable translations from existing results. Nevertheless, this would have been a needlessly circuitous route. ORs are straightforward to interpret, and axioms CCN and EM are simple and clear. The connections between CCN, EM and the important notions of essentiality, closedness and convexity of an OR are obscure in the extant literature. We hope that our clarification of these connections will stimulate further research.

Appendices

Appendices

The following Appendices review some basic facts about closure spaces and abstract convex geometries. Further details, including omitted proofs, can be found in Edelman and Jamison (1985).

A Closure spaces

Given a finite set X, a closure space on X is a collection $\mathcal {K}$ of subsets of X satisfying, for all $A,B\subseteq X$:

• (C0) $\emptyset ,X\in \mathcal {K}$,

• (C1) If $\left\{ A,B\right\} \subseteq \mathcal {K}$, then $A\cap B\in \mathcal {K}$.

We take X as given from now on and omit the qualifier “on X” when discussing closure spaces.

A closure space is an abstract generalisation of the notion of closing a set with respect to some underlying operation, such as forming linear combinations. The elements of $\mathcal {K}$ are interpreted as the subsets of X which are closed with respect to the underlying operation. They are therefore called the closed subsets of X.

Given a closure space $\mathcal {K}$ and a set $A\subseteq X$, we define $\sigma _{\mathcal {K}}\left( A\right)$ to be the smallest element of $\mathcal {K}$ containing A. This is well-defined by (C1):

$$\begin{aligned} \sigma _{\mathcal {K}}\left( A\right) \ =\ \bigcap \left\{ B\in \mathcal {K}\ \left| \ A\subseteq B\right. \right\} \text {.} \end{aligned}$$

We say that $\sigma _{\mathcal {K}}\left( A\right)$ is the closure of A. It is easy to see that $\mathcal {K}$ and $\sigma _{\mathcal {K}}$ contain the same information: given $\sigma _{\mathcal {K}}$ we may recover $\mathcal {K}$ by the rule: $A\in \mathcal {K}$ iff $\sigma _{\mathcal {K}}\left( A\right) =A$.

More generally, we call $\sigma :2^{X}\rightarrow 2^{X}$ a closure operator if it satisfies, for all $A,B\subseteq X$:

• (CC0) $\sigma \left( \emptyset \right) =\emptyset$,

• (CC1) $A\subseteq \sigma (A)$,

• (CC2) $A\subseteq B$ implies $\sigma (A)\subseteq \sigma (B)$,

• (CC3) $\sigma (\sigma (A))=\sigma (A)$.

If $\sigma$ is a closure operator, then it is easily shown that the collection

$$\begin{aligned} \mathcal {K}_{\sigma }\ =\ \{ A\in 2^{X}\ \left| \ \sigma \left( A\right) =A\right. \} \end{aligned}$$

is a closure space;³⁵ and given any closure space $\mathcal {K}$, it is clear that $\sigma _{\mathcal {K}}$ satisfies (CC0)–(CC3). Indeed:

Theorem A.1

Given a closure space $\mathcal {K}$, the operator $\sigma _{\mathcal {K}}$ is a closure operator and $\mathcal {K}=\mathcal {K}_{\sigma _{\mathcal {K}}}$.

Proof

We already observed that $\sigma _{\mathcal {K}}$ is a closure operator. If $A\in \mathcal {K}$, then $\sigma _{\mathcal {K}}\left( A\right) =A$. Conversely, if $\sigma _{\mathcal {K}}\left( A\right) =A$ then A is the intersection of sets in $\mathcal {K}$ and hence $A\in \mathcal {K}$. $\square$

Given a closure space $\mathcal {K}$, we may also define an operator $e_{\mathcal {K}}:2^{X}\rightarrow 2^{X}$ as follows:³⁶

$$\begin{aligned} e_{\mathcal {K}}\left( A\right)= & {} \{ x\in A\ \vert \ \sigma _{\mathcal {K}}\left( A\right) \ne \sigma _{\mathcal {K}}( A\diagdown x) \} \nonumber \\= & {} \{ x\in A\ \vert \ x\notin \sigma _{\mathcal {K}}( A\diagdown x) \} \end{aligned}$$

(18)

The elements of $e_{\mathcal {K}}\left( A\right)$ are called the extreme points of A.

The closure operator $\sigma _{\mathcal {K}}$ can be recovered from $e_{\mathcal {K}}$ as follows:³⁷

$$\begin{aligned} \sigma _{\mathcal {K}}\left( A\right) \ =\ A\cup \{ x\in X\diagdown A\ |\ x\notin e_{\mathcal {K}}\left( A\cup x\right) \} \end{aligned}$$

(19)

Thus, $\mathcal {K}$, $\sigma _{\mathcal {K}}$ and $e_{\mathcal {K}}$ all encode the same information.

We should also mention the recent work of Danilov and Koshevoy (2009), who study pairs of operators $\left( \sigma ,e\right)$ satisfying $e\left( A\right) \subseteq A\subseteq \sigma \left( A\right)$ for any $A\in 2^{X}$ and related by the analogue of condition (18):

$$\begin{aligned} x\in e\left( A\right) \ \ \ \Leftrightarrow \ \ \ x\notin \sigma ( A\diagdown x) \end{aligned}$$

(20)

Danilov and Koshevoy do not assume that these operators are derived from an underlying closure space. By directly investigating the duality (20), they are able to map properties of $\sigma$ into the corresponding properties of e and vice versa, obtaining a novel characterisation of closure operators (Danilov and Koshevoy 2009, Lemma 2) and a new derivation of Ando’s (2006) axiomatisation of the extreme point operators associated with closure spaces (Danilov and Koshevoy 2009, Proposition 5). We comment on a connection between their Lemma 2 and our characterisation of closed opportunity relations in Sect. 4.1.

B Abstract convex geometries

An abstract convex geometry (ACG) is a closure space for which the closure operation has the (algebraic) flavour of forming a convex hull. If $\mathcal {K}$ is an ACG, then the elements of $\mathcal {K}$ are usually referred to as the convex subsets of X, rather than the closed sets.

Formally, an ACG is a closure space $\mathcal {K}$ that satisfies:

• (C2) If $A\in \mathcal {K}\diagdown \left\{ X\right\}$, then $A\cup x\in \mathcal {K}$ for some $x\in X\diagdown A$.

The sense in which (C2) captures the idea of convexity is clarified by the following important result:

Theorem B.1

If $\mathcal {K}$ is an ACG, then the associated closure operator $\sigma =\sigma _{\mathcal {K}}$ satisfies:

• (CC4) For any $A\subseteq X$ with $\sigma \left( A\right) =A$ and any $x,y\in X\diagdown A$ with $x\ne y$, if $y\in \sigma (A\cup x)$, then $x\notin \sigma (A\cup y)$.

  Conversely, if $\sigma$ is a closure operator satisfying (CC4), then $\mathcal {K}_{\sigma }$ satisfies (C2).

Condition (CC4) is called the anti-exchange property.

Edelman and Jamison (1985) provide a range of other conditions on a closure space that are equivalent to the anti-exchange property of its associated closure operator. For our purposes, the most important of these is the following generalisation of the Minkowski–Krein–Milman property:

Theorem B.2

(Edelman and Jamison, Theorem 2.1) A closure space $\mathcal {K}$ is an ACG iff $\sigma _{\mathcal {K}}\left( A\right) =\sigma _{\mathcal {K}}\left( e_{\mathcal {K}}\left( A\right) \right)$ for any $A\subseteq X$.

Thus, the extreme points of A “carry” the convex hull (closure) of A.

Recall that Ando (2006) and Danilov and Koshevoy (2009) give an axiomatic characterisation of the class of extreme point operators associated with closure spaces. Given an operator within this class, Danilov and Koshevoy (2009, Proposition 5, Corollary 3) provide necessary and sufficient conditions for it to be the extreme point operator for some ACG. We discuss a connection between their result and our characterisation of convex opportunity relations in Sect. 5.1.