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: ${\displaystyle w,x,y,z}$. A person states that he ranks the items according to the following total order:

${\displaystyle 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:

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

${\displaystyle \{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 ${\displaystyle \{w,z\},\{x,y\}}$; we do not know which of them the person prefers.

The RS extension of the ranking ${\displaystyle 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 ${\displaystyle O}$ be a set of objects and ${\displaystyle \preceq }$ a total order on ${\displaystyle O}$.

The RS extension of ${\displaystyle \preceq }$ is a partial order on ${\displaystyle 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 ${\displaystyle X\subseteq O}$, every item ${\displaystyle x\in X}$ and every item ${\displaystyle y\notin X}$, take the following relations:

• ${\displaystyle X\setminus \{x\}\prec ^{RS}X}$ (- adding an item improves the bundle)
• If ${\displaystyle x\preceq y}$ then ${\displaystyle 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, ${\displaystyle X\preceq ^{PD}Y}$ if-and-only-if there exists an Injective function ${\displaystyle f}$ from ${\displaystyle X}$ to ${\displaystyle Y}$ such that, for each ${\displaystyle x\in X}$, ${\displaystyle 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, ${\displaystyle X\preceq ^{SD}Y}$ iff, for every item ${\displaystyle z}$:

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

where ${\displaystyle X[x]}$ is the fraction of item ${\displaystyle x}$ in the bundle ${\displaystyle X}$.

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

${\displaystyle |\{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 ${\displaystyle w\prec x\prec y\prec z}$ is compatible with the following utility functions:

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

${\displaystyle 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:

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

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

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

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

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

This motivates the following definition:

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

${\displaystyle u(X)\leq u(Y)}$

Equivalence

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

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

Responsive orders and valuations

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. I.e., it contains all the relations that are implied by the underlying ordering of the items, and adds some more relations that are not implied nor contradicted.

Similarly, a utility function on bundles is called responsive if it induces a responsive order. To be more explicit, ^[5] a utility function u is responsive if for every bundle X and every two items y,z that are not in X: ${\displaystyle u(y)\geq u(z)\implies u(X\cup \{y\})\geq u(X\cup \{z\})}$.

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 ${\displaystyle \preceq ^{AU}}$, which is equivalent to ${\displaystyle \preceq ^{RS}}$, so it is responsive. Similarly, if a utility function is additive, then ${\displaystyle u(X\cup \{y\})-u(X\cup \{z\})=u(y)-u(z)}$, so responsiveness is satisfied.
• 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.

For example, ^[6] suppose there are four items with ${\displaystyle w\prec x\prec y\prec z}$. Responsiveness constrains only the relation between bundles of the same size with one item replaced, or bundles of different sizes where the small is contained in the large. It says nothing about bundles of different sizes that are not subsets of each other. So, for example, a responsive order can have both ${\displaystyle \{z\}\prec \{x,y\}}$ and ${\displaystyle \{w,z\}\succ \{w,x,y\}}$. But this is incompatible with additivity: there is no additive function for which ${\displaystyle u(\{z\})<u(\{x,y\})}$ while ${\displaystyle u(\{w,z\})>u(\{w,x,y\})}$.

See also

• Weakly additive
• Picking sequence

References

1. Aziz, Haris; Gaspers, Serge; MacKenzie, Simon; Walsh, Toby (2015). "Fair assignment of indivisible objects under ordinal preferences". Artificial Intelligence. 227: 71–92. arXiv: 1312.6546 . doi:10.1016/j.artint.2015.06.002. S2CID   1408197.
2. Barberà, S., Bossert, W., Pattanaik, P. K. (2004). "Ranking sets of objects." (PDF). Handbook of utility theory. Springer US.
3. Katta, Akshay-Kumar; Sethuraman, Jay (2006). "A solution to the random assignment problem on the full preference domain". Journal of Economic Theory . 131 (1): 231. doi:10.1016/j.jet.2005.05.001.
4. 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 )
5. Kyropoulou, Maria; Suksompong, Warut; Voudouris, Alexandros A. (2020-11-12). "Almost envy-freeness in group resource allocation". Theoretical Computer Science. 841: 110–123. doi:10.1016/j.tcs.2020.07.008. ISSN   0304-3975. S2CID   59222796.
6. Moshe, Babaioff; Noam, Nisan; Inbal, Talgam-Cohen (2017-03-23). "Competitive Equilibrium with Indivisible Goods and Generic Budgets". arXiv: 1703.08150 . Bibcode:2017arXiv170308150B.