# 9 Maximal Elements

This section studies the relationship between preference and choice. The standard assumption in rational choice models is that a decision maker will choose an element from a set of feasible alternatives \(A\) that is “best” according to her preference. There are two ways to define the “best” element of a set with respect to some relation \(R\) on that set.

**Definition 9.1 (Maximum) **Suppose that \(X\) is a set, \(R\subseteq X\times X\) is a relation on \(X\), and \(A\subseteq X\). We say that \(x\in A\) is a **maximum** element of \(A\) with respect to \(R\) provided that \[\mbox{for all $y\in A$, $x\mathrel{R} y$.}\]

**Definition 9.2 (Maximal) **Suppose that \(X\) is a set, \(R\subseteq X\times X\) is a relation on \(X\), and \(A\subseteq X\). We say that \(x\in A\) is a a **maximal** element of \(A\) with respect to \(R\) provided that \[\mbox{there is no $y\in A$ such that $y \mathrel{R} x$}.\]

The following examples illustrate the above definition: Suppose that \(X=\{a, b, c\}\).

- Let \(R=\{(a,b), (b, c), (a, c)\}\) and \(A=\{b, c\}\). Then,
- \(a\) is the only maximal element of \(X\) with respect to \(R\).
- \(b\) is the only maximal element of \(A\) with respect to \(R\).
- \(a\) is the only maximum element of \(X\) with respect to \(R\).
- \(b\) is the only maximum element of \(A\) with respect to \(R\).

- Let \(R=\{(a,b), (b, c), (c,a)\}\) and \(A=\{a, c\}\). Then,
- There are no maximal elements of \(X\) with respect to \(R\).
- \(c\) is the only maximal element of \(A\) with respect to \(R\).
- There is no maximum element of \(X\) with respect to \(R\).
- \(c\) is the only maximum element of \(A\) with respect to \(R\).

- Let \(R=\{(a, b), (c, b) \}\). Then,
- \(a\) and \(c\) are both maximal elements of \(X\) with respect to \(R\).
- There is no maximum element of \(X\) with respect to \(R\).

## 9.1 Rational Choice

Suppose that \(X\) is a set of alternatives and \(A\subseteq X\). We write \(C(A)\) for the set of *admissible*, or *choice-worthy*, elements of \(A\) for a decision maker. The interpretation is that when a decision maker must choose an alternative from a set \(A\) of feasible options, she will pick something from the set \(C(A)\subseteq A\).

A decision maker’s choice is **rational** when there is a rational preference \((P, I)\) on \(X\) such that for all \(A\subseteq X\), the set \(C(A)\) of choice-worthy elements of \(A\) is the set of maximal elements of \(A\) with respect to her strict preference \(P\).

The mathematical formalism does not specify whether a choice function \(C\) represents a decision maker’s *actual* or *hypothetical* choice. If it is the actual choices, then \(C\) is a record of the decision maker’s observed choice behavior. If it is the hypothetical choices, then \(C\) represents what the decision maker *would* chose if given the opportunity to select an element from a given menu.

### 9.1.1 Revealed Preference Theory

This section contains more advanced material and can be skipped on a first reading.

When a decision maker uniquely choses \(x\) from a set containing \(x\) and \(y\) (i.e., \(C(\{x, y\})=\{x\}\)), we say that she *reveals a preference* for \(x\) over \(y\). There is a elegant mathematical theory identifying the preferences revealed by the choices of a decision maker.

Standard economics focuses on revealed preference because economic data comes in this form. Economic data can—at best—reveal what the agent wants (or has chosen) in a particular situation. Such data do not enable the economist to distinguish between what the agent intended to choose and what he ended up choosing; what he chose and what he ought to have chosen. (Gul and Pesendorfer 2008)

**Definition 9.3 (Derived Choice Function) **Suppose that \(R\) is a relation on a finite set \(X\). The choice function derived from the relation \(R\) is \(C_R:\mathcal{P}(X)\rightarrow\mathcal{P}(X)\) is defined as follows: for all \(A\in\mathcal{P}(X)\setminus \varnothing\), \[C_R(A)=\{y\ |\ \text{$y\in A$ and there is no $x\in A$ such that $x\mathrel{R} y$}\}.\]

Definition Definition 9.3 can be applied to *any* relation on a set \(X\). In general, given an arbitrary relation \(R\) on \(X\), \(C_R\) may not necessarily be a *choice* function. This would happen when there is a finite subset \(Y\subseteq X\) such that \(C_R(Y)=\emptyset\). The following Lemma states precisely when a function derived from a relation is a choice function.

**Lemma 9.1 **Suppose that \(X\) is finite. A binary relation \(R\subseteq X\times X\) is acyclic if and only if \(C_R\) is a choice function.

*Proof*. Suppose that \(R\subseteq X\times X\) is acyclic. By definition, for any nonempty set \(S\in \mathcal{P}(X)\), \(C_R(S)\subseteq S\). We must show \(C_R(S)\ne \emptyset\). Suppose that \(C_R(S)=\emptyset\). Choose an element \(x_0\in S\). Since \(C_R(S)=\emptyset\), there is an element \(x_1\in S\) such that \(x_1\mathrel{R} x\). Again, since \(C_R(S)=\emptyset\) there must be some element \(x_2\in S\) such that \(x_2\mathrel{R} x_1\). Since \(R\) is acyclic, we must have \(x_2\ne x\) (otherwise, \(x\mathrel{R} x_1\mathrel{R} x\) is a cycle). Continue in this manner selecting elements of \(S\). Since \(S\) is finite, eventually all elements of \(S\) are selected. That is, we have \(S=\{x_0,x_1,x_2,\ldots, x_n\}\) and \[x_n\mathrel{R} x_{n-1}\mathrel{R}\cdots x_2\mathrel{R} x_1\mathrel{R} x_0\] Since \(C_R(S)=\emptyset\) there must be some element \(x\in S\) such that \(x\mathrel{R} x_n\). Thus, \(x=x_i\) for some \(i=0,\ldots, n\), which implies \(R\) has a cycle. This contradicts the assumption that \(C_R(S)=\emptyset\). Hence \(C_R(S)\ne\emptyset\).

Suppose that \(C_R\) is a choice function. This means that for all \(S\in\mathcal{P}(X)\), \(C_R(S)\ne\emptyset\). Suppose that \(R\) is not acyclic. Then, there is a set of distinct elements \(x_1,x_2,\ldots, x_n\in S\) such that \[x_1\mathrel{R} x_2\mathrel{R}\cdots x_{n-1}\mathrel{R} x_n\mathrel{R} x_1.\] But this means that \(C_R(\{x_1,\ldots, x_n\})=\emptyset\). (The above cycle means that there is no maximal element of \(\{x_1,\ldots, x_n\}\).) This contradicts the assumption that \(C_R\) is a choice function. Thus, \(R\) is acyclic.

Suppose that \((P, I)\) are the rational preference on \(X\) for a decision maker. Since \(P\) is acyclic, by Lemma 1, \(C_P\) is a choice function. A choice function represents the choices of a decision maker when there is some rational preference that generates the choices. \(\Box\)

**Definition 9.4 (Rationalizable Choice Functions) **A choice function \(C:\mathcal{P}(X)\rightarrow \mathcal{P}(X)\) is **rationalizable** if there is a rational preference \((P, I)\) on \(X\) such that for all \(A\in \mathcal{P}\), \(C(A)=C_P(A)\).

Not every choice function is rationalizable. There are two key properties that completely characterize rationalizable choice functions. Suppose that \(C\) is a choice function on \(X\). We say that \(C\) satisfies:

**Sen’s property**\(\mathbf{\alpha}\) provided that for all \(A, B\subseteq X\), for all \(x\in X\), if \(x\in B\subseteq A\) and \(x\in C(A)\), then \(x\in C(B)\)**Sen’s property**\(\mathbf{\beta}\) provided that for all \(A, B, \subseteq X\), for all \(x,y\in X\) if \(x,y\in C(A)\), \(A\subseteq B\) and \(y\in C(B)\), then \(x\in C(B)\).

The first result is that Sen’s \(\alpha\) and \(\beta\) are together equivalent to a single axiom knowns as the *weak axiom of revealed preference* (WARP). Suppose that \(C\) is a choice function on \(X\). We say that \(C\) satisfies:

**Weak Axiom of Revealed Preference**(also known as WARP or Houthakker’s Axiom) provided that for all \(A, B, \subseteq X\), for all \(x,y\in X\), if \(x\) and \(y\) are both contained in \(A\) and \(B\) and if \(x\in C(A)\) and \(y\in C(B)\) then \(x\in C(B)\).

**Lemma 9.2 **A choice function \(C\) satisfies WARP if and only if \(C\) satisfies Sen’s properties \(\alpha\) and \(\beta\).

*Proof*. Suppose that \(C\) satisfies WARP. We must show \(C\) satisfies Sen’s \(\alpha\) and \(\beta\):

\(C\) satisfies Sen’s \(\alpha\): Suppose that \(x\in X\) with \(x\in B\subseteq A\subseteq X\) and \(x\in C(A)\). Suppose that \(x\not\in C(B)\). Then there is some \(y\in B\) such that \(y\in C(B)\) and \(y\ne x\). Since \(y\in B\) and \(B\subseteq A\), we have \(y\in A\). Hence, \(x\) and \(y\) are in both \(A\) and \(B\). By the WARP axiom, since \(x\in C(A)\) and \(y\in C(B)\), we must have \(x\in C(B)\). This contradicts the assumption that \(x\not\in C(B)\). Thus, \(x\in c(B)\), as desired.

\(C\) satisfies Sen’s \(\beta\): Suppose that \(x,y\in X\) with \(x,y\in C(A)\), \(A\subseteq B\subseteq X\) and \(y\in C(B)\). Since \(C(A)\subseteq A\), we have \(x, y\in A\); and since \(A\subseteq B\), we have \(x, y\in B\). Thus, \(x\) and \(y\) are in both \(A\) and \(B\). By the WARP axiom, since \(x\in C(A)\) and \(y\in C(B)\), we must have \(x\in C(B)\), as desired.

Now, suppose that \(C\) satisfies Sen’s \(\alpha\) and \(\beta\). We must show that \(C\) satisfies WARP. Suppose that \(x,y\in A\cap B\), \(x\in C(A)\) and \(y\in C(B)\). We must show that \(x\in C(B)\). Since, \(A\cap B\subseteq B\) and \(y\in C(B)\), by Sen’s \(\alpha\), \(y\in C(A\cap B)\). Similarly, since \(A\cap B\subseteq A\) and \(x\in C(A)\), by Sen’s \(\alpha\), \(x\in C(A\cap B)\). Finally, Since \(x, y\in C(A\cap B)\), \(A\cap B\subseteq B\) and \(y\in C(B)\), by Sen’s \(\beta\), we have that \(x\in C(B)\), as desired.

The main result of this section is that WARP is equivalent to rationalizability.

**Theorem 9.1 **Suppose that \(X\) is a finite set and \(C\) is a choice function on \(X\). Then, \(C\) satisfies WARP if and only if \(C\) is rationalizable.

*Proof*. Suppose \(C\) is a choice function on \(X\), and that \(C\) is rationalizable. Then there is a rational preference \((P, I)\) such that \(C=C_P\). We must show that \(C\) satisfies WARP. Suppose that \(A, B\subseteq X\) and \(x,y\in A\cap B\), \(x\in C(A)\) and \(y\in C(B)\). We must show that \(x\in C(B)\). Since \(C=C_P\), we have that \(x\) is a maximal element in \(A\) with respect to \(P\) and that \(y\) is a maximal element in \(B\) with respect to \(P\). This means that there is no \(z\in A\) such that \(z P x\) and there is no \(z\in B\) such that \(z P y\). Suppose that \(w\in B\). We will show that not-\(w P x\). Since \(w\in B\) and \(y\) is maximal in \(B\) with respect to \(P\), we have that not-\(w P y\). Since \((P, I)\) is complete, this means that \(y P w\) or \(y I w\) (i.e, \(y R_P w\)). Furthermore, since \(y\in A\) and \(x\) is maximal in \(A\) with respect to \(P\), we have that not-\(y P x\). Since \((P, I)\) is complete, this means that either \(x P y\) or \(x I y\) (i.e., \(x R_P y\)). Since \(R_P\) is transitive and \(x \mathrel{R_P} y\) and \(y \mathrel{R_P} w\), we have that \(x \mathrel{R_P} w\). This implies that not-\(wPx\). That is, \(x\) is maximal in \(B\) with respect to \(P\), i.e., \(x\in C(B)\).

Suppose that \(C\) satisfies WARP. Then by Lemma 2, \(C\) satisfies Sen’s \(\alpha\) and \(\beta\). Define a relation \(R_C\subseteq X\times X\) as follows: for all \(x,y\in X\), \[x\mathrel{R_C} y \text{ if and only if } x\in C(\{x,y\}).\]

We must show that 1. \(R_C\) is a rational weak preference relation and 2. for all \(S\in\mathcal{P}(X)\), \(C(S)=C_{P_C}(S)\), where \(P_C\) is the strict preference relation derived from \(R_C\). To see that 1. holds:

\(R_C\) is connected: For any \(x,y\in X\), since \(C(\{x,y\})\) is non-empty we have that \(C(\{x,y\})=\{x\}\), \(C(\{x,y\})=\{y\}\) or \(C(\{x,y\})=\{x,y\}\). Thus, either \(x \mathrel{R_C} y\) or \(y \mathrel{R_C} x\) (or both).

\(R_C\) is transitive: Suppose that \(x \mathrel{R_C} y\) and \(y \mathrel{R_C} z\). Then, \(x\in C(\{x,y\})\) and \(y\in C(\{y, z\})\). We must show that \(x\mathrel{R_C} z\); that is, \(x\in C(\{x,z\})\). By Sen’s \(\alpha\), if \(x\in C(\{x,y,z\})\), then \(x\in C(\{x,z\})\). Thus, if we show that \(x\in C(\{x,y,z\})\), then we are done. There are three cases:

- Suppose that \(C(\{x,y,z\})=\{y\}\). By Sen’s \(\alpha\), since \(\{x,y\}\subseteq \{x,y,z\}\) and \(y\in C(\{x,y,z\})\) we must have \(y\in C(\{x,y\})\). Thus, \(C(\{x,y\})=\{x,y\}\). By Sen’s \(\beta\), this implies that \(x\in C(\{x,y,z\})\) (this follows since \(\{x,y\}\subseteq \{x,y,z\}\), \(x,y\in C(\{x,y\})\) and \(y\in C(\{x,y,z\})\)). This contradicts the assumption that \(C(\{x,y,z\})=\{y\}\). Thus, \(C(\{x,y,z\}\ne\{y\}\).

- A similar argument shows that \(C(\{x,y,z\})\ne\{z\}\).

- Suppose that \(C(\{x,y,z\})=\{y,z\}\). Then, \(y\in C(\{x,y,z\})\), and, as above, by Sen’s \(\alpha\), we have \(C(\{x,y\})=\{x,y\}\). This implies, by Sen’s \(\beta\), that \(x\in C(\{x,y,z\})\), which contradicts that assumption that \(C(\{x,y,z\})=\{y,z\}\).

Hence, \(x\in C(\{x,y,z\}\). By Sen’s \(\alpha\), since \(\{x,z\}\subseteq \{x,y,z\}\), we have \(x\in C(\{x,z\})\). That is, \(x\mathrel{R_C} z\). This completes the proof that \(R_C\) is transitive.

Let \(P_C\) be the strict preference relation derived from \(R_C\). Suppose that \(S\in\mathcal{P}(X)\). First of all, if \(S\) is a singleton (i.e., \(S=\{x\}\) for some \(x\in X\)), then by definition \(C(S)=S=C_{P_C}(S)\). Thus, in what follows we assume that \(S\) has at least two elements. We must show that \(C(S)=C_{P_C}(S)\). We first show that \(C(S)\subseteq C_{P_C}(S)\). Suppose that \(x\in C(S)\). We must show that \(x\in C_{P_C}(S)\). Let \(y\in S\). We must show that not-\(y \mathrel{P_C} x\). Since \(R_C\) is connected, this is equivalent to showing that \(x\mathrel{R_C} y\). Since \(\{x,y\}\subseteq S\) and \(x\in C(S)\), by Sen’s \(\alpha\), we have \(x\in C(\{x,y\})\). Thus, \(x\mathrel{R_C} y\); and so, not-\(y\mathrel{P_C} x\), which implies that \(x\in C_{P_C}(S)\). Next, we show that \(C_{P_C}(S)\subseteq C(S)\). Suppose that \(x\in C_{P_C}(S)\). Suppose that \(x\not\in C(S)\). Then there is some \(y\ne x\) such that \(y\in C(S)\). By Sen’s \(\alpha\), this implies that \(y\in C(\{x,y\})\). Furthermore, if \(C(\{x,y\})=\{x,y\}\), then, by Sen’s \(\beta\), \(x\in C(S)\). This contradicts the assumption that \(x\not\in C(S)\). Thus, \(C(\{x,y\})=\{y\}\). By definition, this means that \(y\mathrel{R_C} x\) but not-\(x \mathrel{R_C} y\); i.e., \(y P_C x\). This contradicts the assumption that \(x\in C_{P_C}(S)\). Thus, \(x\in C(S)\), as desired.

## 9.2 Exercises

Suppose that \(X=\{a, b, c, d\}\) and \(R=\{(a, b), (b, c), (a, c)\}\). What are the set of maximal elements in \(A=\{a, b, c\}\) according to \(R\)? What are the set of maximal elements in \(A=\{a, b, c, d\}\) according to \(R\)?

Is it possible to find a relation \(R\) on \(X\) that has a cycle and such that there is a non-empty set of maximal elements of \(X\) according to \(R\)?

Is it possible to find a relation \(R\) on a set \(X\) that is reflexive and such that there is a non-empty set of maximal elements of \(X\) according to \(R\)?

Suppose that \(X=\{a, b, c\}\). Consider the a decision maker that makes the following choices:

- From \(\{a, c\}\) the decision maker chooses uniquely \(a\)
- From \(\{a, b, c\}\) the decision maker chooses uniquely \(b\)

Is there a rational preference \((P, I)\) on \(X\) such that the decision maker chooses according to that preference?

Suppose that \(X=\{a, b, c, d\}\). Consider the a decision maker that makes the following choices:

- From \(\{a, c\}\) the decision maker chooses uniquely \(a\)
- From \(\{a, b, c, d\}\) the decision maker chooses both \(a\) and \(b\)

Is there a rational preference \((P, I)\) on \(X\) such that the decision maker chooses according to that preference?

Suppose that \(X=\{a, b, c, d\}\). Consider the a decision maker that makes the following choices:

- From \(\{a, c\}\) the decision maker chooses uniquely \(a\)
- From \(\{a, b, c, d\}\) the decision maker chooses uniquely \(c\)

Is there a rational preference \((P, I)\) on \(X\) such that the decision maker chooses according to that preference?

Suppose that \(X=\{a, b, c, d\}\). Consider the a decision maker that makes the following choices:

- From \(\{a, c\}\) the decision maker chooses uniquely \(a\)
- From \(\{a, b, c, d\}\) the decision maker chooses uniquely \(d\)

Suppose that \(X=\{a, b, c, d\}\) and \(R=\{(a, b), (b, c), (a, c)\}\). What are the set of maximal elements in \(A=\{a, b, c\}\) according to \(R\)? What are the set of maximal elements in \(A=\{a, b, c, d\}\) according to \(R\)?

The maximal element of \(\{a, b, c\}\) according to \(R\) is \(a\).

The maximal elements of \(\{a, b, c, d\}\) according to \(R\) are \(a\) and \(d\).

Is it possible to find a relation that has a cycle and a non-empty set of maximal elements?

Yes, suppose that \(X=\{a, b, c, d\}\) and \[R=\{(a, b), (a, c), (a, d), (b, c), (c, d), (d, b)\}\] The maximal element of \(X\) is \(a\) according to \(R\) and there is a cycle \((b, c, d)\) in \(R\).

Is it possible to find a relation \(R\) on a set \(X\) that is reflexive and such that there is a non-empty set of maximal elements of \(X\) according to \(R\)?

No, if \(R\) is reflexive then for all \(x\), \(x\mathrel{R} x\), so there cannot be any maximal elements in \(X\) according to \(R\).

Suppose that \(X=\{a, b, c\}\). Consider the a decision maker that makes the following choices:

- From \(\{a, c\}\) the decision maker chooses uniquely \(a\)
- From \(\{a, b, c\}\) the decision maker chooses uniquely \(b\)

Yes, suppose that the decision maker’s strict preference is \(P=\{(a, c), (b, a), (b, c)\}\) and indfference is \(I=\{(a,a), (b,b), (c,c)\}\)

Suppose that \(X=\{a, b, c, d\}\). Consider the a decision maker that makes the following choices:

- From \(\{a, c\}\) the decision maker chooses uniquely \(a\)
- From \(\{a, b, c, d\}\) the decision maker chooses both \(a\) and \(b\)

Yes, suppose that the decision maker’s strict preference is \(P=\{(a, c), (b, c), (c, d), (a, d), (b,d)\}\) and indfference is \(I=\{(a,a), (b,b), (c,c), (a, b), (b, a)\}\).

Suppose that \(X=\{a, b, c, d\}\). Consider the a decision maker that makes the following choices:

- From \(\{a, c\}\) the decision maker chooses uniquely \(a\)
- From \(\{a, b, c, d\}\) the decision maker chooses uniquely \(c\)

No, since \(\{a, c\}\subseteq \{a, b, c, d\}\) and if \(c\) is maximal in \(\{a, b, c, d\}\) according to the decision maker’s strict preferences, then \(c\) should be maximal in \(\{a, c\}\) according to the decision maker’s strict preferences.

Suppose that \(X=\{a, b, c, d\}\). Consider the a decision maker that makes the following choices:

- From \(\{a, c\}\) the decision maker chooses uniquely \(a\)
- From \(\{a, b, c, d\}\) the decision maker chooses uniquely \(d\)

Yes, suppose that the decision maker’s strict preference is \(P=\{(a, c), (d, a), (d, c), (c, b), (a, b), (d, b)\}\) and indfference is \(I=\{(a,a), (b,b), (c,c)\}\)