Responsive set extension

In utility theory, the responsive set (RS) extension is an extension of a preference-relation on individual items, to a partial preference-relation of item-bundles.

Example

Suppose there are four items: $w,x,y,z$. A person states that he ranks the items according to the following total order:

$w\prec x\prec y\prec z$

(i.e., z is his best item, then y, then x, then w). Assuming the items are independent goods, one can deduce that:

$\{w,x\}\prec \{y,z\}$ – the person prefers his two best items to his two worst items;

$\{w,y\}\prec \{x,z\}$ – the person prefers his best and third-best items to his second-best and fourth-best items.

But, one cannot deduce anything about the bundles $\{w,z\},\{x,y\}$; we do not know which of them the person prefers.

The RS extension of the ranking $w\prec x\prec y\prec z$ is a partial order on the bundles of items, that includes all relations that can be deduced from the item-ranking and the independence assumption.

Definitions

Let $O$ be a set of objects and $\preceq$ a total order on $O$.

The RS extension of $\preceq$ is a partial order on $2^{O}$. It can be defined in several equivalent ways.

Responsive set (RS)

The original RS extension is constructed as follows. For every bundle $X\subseteq O$, every item $x\in X$ and every item $y\notin X$, take the following relations:

• $X\setminus \{x\}\prec ^{RS}X$ (- adding an item improves the bundle)
• If $x\preceq y$ then $X\preceq ^{RS}(X\setminus \{x\})\cup \{y\}$ (- replacing an item with a better item improves the bundle).

The RS extension is the transitive closure of these relations.

Pairwise dominance (PD)

The PD extension is based on a pairing of the items in one bundle with the items in the other bundle.

Formally, $X\preceq ^{PD}Y$ if-and-only-if there exists an Injective function $f$ from $X$ to $Y$ such that, for each $x\in X$, $x\preceq f(x)$.

Stochastic dominance (SD)

The SD extension (named after stochastic dominance) is defined not only on discrete bundles but also on fractional bundles (bundles that contains fractions of items). Informally, a bundle Y is SD-preferred to a bundle X if, for each item z, the bundle Y contains at least as many objects, that are at least as good as z, as the bundle X.

Formally, $X\preceq ^{SD}Y$ iff, for every item $z$:

$\sum _{x\succeq z}X[x]\leq \sum _{y\succeq z}Y[y]$

where $X[x]$ is the fraction of item $x$ in the bundle $X$.

If the bundles are discrete, the definition has a simpler form. $X\preceq ^{SD}Y$ iff, for every item $z$:

$|\{x\in X|x\succeq z\}|\leq |\{y\in Y|y\succeq z\}|$

Additive utility (AU)

The AU extension is based on the notion of an additive utility function.

Many different utility functions are compatible with a given ordering. For example, the order $w\prec x\prec y\prec z$ is compatible with the following utility functions:

$u_{1}(w)=0,u_{1}(x)=2,u_{1}(y)=4,u_{1}(z)=7$

$u_{2}(w)=0,u_{2}(x)=2,u_{2}(y)=4,u_{2}(z)=5$

Assuming the items are independent, the utility function on bundles is additive, so the utility of a bundle is the sum of the utilities of its items, for example:

$u_{1}(\{w,x\})=2,u_{1}(\{w,z\})=7,u_{1}(\{x,y\})=6$

$u_{2}(\{w,x\})=2,u_{2}(\{w,z\})=5,u_{2}(\{x,y\})=6$

The bundle $\{w,x\}$ has less utility than $\{w.z\}$ according to both utility functions. Moreover, for every utility function $u$ compatible with the above ranking:

$u(\{w,x\})<u(\{w,z\})$.

In contrast, the utility of the bundle $\{w,z\}$ can be either less or more than the utility of $\{x,y\}$.

This motivates the following definition:

$X\preceq ^{AU}Y$ iff, for every additive utility function $u$ compatible with $\preceq$:

$u(X)\leq u(Y)$

Equivalence

• $X\preceq ^{SD}Y$ implies $X\preceq ^{RS}Y$.
• $X\preceq ^{RS}Y$ and $X\preceq ^{PD}Y$ are equivalent.
• $X\preceq ^{PD}Y$ implies $X\preceq ^{AU}Y$. Proof: If $X\preceq ^{PD}Y$, then there is an injection $f:X\to Y$ such that, for all $x\in X$, $x\preceq f(x)$. Therefore, for every utility function $u$ compatible with $\preceq$, $u(x)\leq u(f(x))$. Therefore, if $u$ is additive, then $u(X)\leq u(Y)$.
• It is known that $\preceq ^{AU}$ and $\preceq ^{SD}$ are equivalent, see e.g.

Therefore, the four extensions $\preceq ^{RS}$ and $\preceq ^{PD}$ and $\preceq ^{SD}$ and $\preceq ^{AU}$ are all equivalent.

Responsiveness

A total order on bundles is called responsive if it is contains the responsive-set-extension of some total order on items.

Responsiveness is implied by additivity, but not vice versa:

• If a total order is additive (represented by an additive function) then by definition it contains the AU extension $\preceq ^{AU}$, which is equivalent to $\preceq ^{RS}$, so it is responsive.
• On the other hand, a total order may responsive but not additive: it may contain the AU extension which is consistent with all additive functions, but may also contain other relations that are inconsistent with a single additive function.

See also

• Weakly additive