Responsive set extension

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 ≺ x ≺ y ≺ 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 } ≺ { y , z } – the person prefers his two best items to his two worst items; { w , y } ≺ { 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 ≺ x ≺ y ≺ 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 ⪯ a total order on O .

The RS extension of ⪯ 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 ⊆ O , every item x ∈ X and every item y ∉ X , take the following relations:

X ∖ { x } ≺ R S X (- adding an item improves the bundle)

If x ⪯ y then X ⪯ R S ( X ∖ { x } ) ∪ { 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 ⪯ P D Y if-and-only-if there exists an Injective function f from X to Y such that, for each x ∈ X , x ⪯ 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 ⪯ S D Y iff, for every item z :

∑ x ⪰ z X [ x ] ≤ ∑ y ⪰ 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 ⪯ S D Y iff, for every item z :

| { x ∈ X | x ⪰ z } | ≤ | { y ∈ Y | y ⪰ 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 ≺ x ≺ y ≺ 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 ⪯ A U Y iff, for every additive utility function u compatible with ⪯ :

u ( X ) ≤ u ( Y )

Equivalence

X ⪯ S D Y implies X ⪯ R S Y .

X ⪯ R S Y and X ⪯ P D Y are equivalent.

X ⪯ P D Y implies X ⪯ A U Y . Proof: If X ⪯ P D Y , then there is an injection f : X → Y such that, for all x ∈ X , x ⪯ f ( x ) . Therefore, for every utility function u compatible with ⪯ , u ( x ) ≤ u ( f ( x ) ) . Therefore, if u is additive, then u ( X ) ≤ u ( Y ) .

It is known that ⪯ A U and ⪯ S D are equivalent, see e.g.

Therefore, the four extensions ⪯ R S and ⪯ P D and ⪯ S D and ⪯ A U 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 ⪯ A U , which is equivalent to ⪯ R S , 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.