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 tells us 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 z). Assuming the items are independent goods, we can deduce that:

\{w,x\}\prec \{y,z\}

- the person preferes his two best items to his two worse items;

\{w,y\}\prec \{x,z\}

- the person preferes his best and 3rd-best items to his 2nd- and 4th-best items.

But, we 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.^[1]

Responsive Set (RS)

The original RS extension^[2]^:44–48 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$ .^[1]
$X\preceq ^{RS}Y$ and $X\preceq ^{PD}Y$ are equivalent.^[1]
$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)$ .^[1]
It is known that $\preceq ^{AU}$ and $\preceq ^{SD}$ are equivalent, see e.g.^[3]

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^[4]^:287–288 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.

References

1 2 3 4 Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (2015). "Fair assignment of indivisible objects under ordinal preferences". Artificial Intelligence. 227: 71. arXiv:1312.6546. doi:10.1016/j.artint.2015.06.002.
↑ Barberà, S., Bossert, W., Pattanaik, P. K. (2004). "Ranking sets of objects.". Handbook of utility theory (PDF). Springer US.
↑ Katta, Akshay-Kumar; Sethuraman, Jay (2006). "A solution to the random assignment problem on the full preference domain". Journal of Economic Theory. 131: 231. doi:10.1016/j.jet.2005.05.001.
↑ Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (free online version)

This article is issued from Wikipedia - version of the 11/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.