“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:

. A person states that he ranks the items according to the following total order:

But, one cannot deduce anything about the bundles

; we do not know which of them the person prefers.

The RS extension of the ranking

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

The RS extension of

is a partial order on

. It can be defined in several equivalent ways.^[1]

Responsive set (RS)

The original RS extension^[2]{{rp|44–48}} is constructed as follows. For every bundle

, every item

and every item

, take the following 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,

if-and-only-if there exists an Injective function

from

such that, for each

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.

If the bundles are discrete, the definition has a simpler form.

iff, for every item

Additive utility (AU)

Many different utility functions are compatible with a given ordering. For example, the order

is compatible with the following utility functions:

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:

The bundle

has less utility than

according to both utility functions. Moreover, for every utility function

compatible with the above ranking:

In contrast, the utility of the bundle

can be either less or more than the utility of

Equivalence

Responsiveness

A total order on bundles is called responsive^[4]{{rp|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.

For example,^[5] suppose there are four items with

. 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 nothing about bundles of different sizes that are not subsets of each other. So, for example, a responsive order can have both

and

. But this is incompatible with additivity: there is no additive function for which

while

See also

References

1. ^¹²³{{cite journal|doi=10.1016/j.artint.2015.06.002|title=Fair assignment of indivisible objects under ordinal preferences|journal=Artificial Intelligence|volume=227|pages=71|year=2015|last1=Aziz|first1=Haris|last2=Gaspers|first2=Serge|last3=MacKenzie|first3=Simon|last4=Walsh|first4=Toby|arxiv=1312.6546}}
2. ^{{cite book|last1=Barberà, S., Bossert, W., Pattanaik, P. K.|chapter=Ranking sets of objects.|title=Handbook of utility theory|date=2004|publisher=Springer US.|url=https://papyrus.bib.umontreal.ca/xmlui/bitstream/handle/1866/343/2001-02.pdf?sequence=1}}
3. ^{{cite journal |doi=10.1016/j.jet.2005.05.001 |title=A solution to the random assignment problem on the full preference domain |journal=Journal of Economic Theory |volume=131 |issue=1 |pages=231 |year=2006 |last1=Katta |first1=Akshay-Kumar |last2=Sethuraman |first2=Jay }}
4. ^{{Cite ComSoc Handbook 2016}}
5. ^{{Cite journal|last=Moshe|first=Babaioff,|last2=Noam|first2=Nisan,|last3=Inbal|first3=Talgam-Cohen,|date=2017-03-23|title=Competitive Equilibrium with Indivisible Goods and Generic Budgets|url=https://arxiv.org/abs/1703.08150|language=en}}