Lexicographic Dominance

Lexicographic dominance is a total order between random variables. It is a form of stochastic ordering. It is defined as follows. Random variable A has lexicographic dominance over random variable B (denoted $A \succ_ B$) if one of the following holds:

* A has a higher probability than B of receiving the best outcome.
* A and B have an equal probability of receiving the best outcome, but A has a higher probability of receiving the 2nd-best outcome.
* A and B have an equal probability of receiving the best and 2nd-best outcomes, but A has a higher probability of receiving the 3rd-best outcome.
In other words: let ''k'' be the first index for which the probability of receiving the k-th best outcome is different for A and B. Then this probability should be higher for A.

Variants

Upward lexicographic dominance is defined as follows. Random variable A has upward lexicographic dominance over random variable B (denoted $A \succ_ B$) if one of the following holds:
* A has a ''lower'' probability than B of receiving the ''worst'' outcome.
* A and B have an equal probability of receiving the worst outcome, but A has a lower probability of receiving the 2nd-worst outcome.
* A and B have an equal probability of receiving the worst and 2nd-worst outcomes, but A has a lower probability of receiving the 3rd-worst outcomes.

To distinguish between the two notions, the standard lexicographic dominance notion is sometimes called downward lexicographic dominance and denoted $A \succ_ B$.

Relation to other dominance notions

First-order stochastic dominance implies both downward-lexicographic and upward-lexicographic dominance. The opposite is not true. For example, suppose there are four outcomes ranked z > y > x > w. Consider the two lotteries that assign to z, y, x, w the following probabilities:

* A: .2, .4, .2, .2
* B: .2, .3, .4, .1

Then the following holds:

* $A \succ_ B$, since they assign the same probability to z but A assigns more probability to y.
* $B \succ_ A$, since B assigns less probability to the worst outcome w.
* $A \not\succ_ B$, since B assigns more probability to the three best outcomes . If, for example, the value of z,y,x is very near 1, and the value of w is 0, then the expected value of B is near 0.9 while the expected value of A is near 0.8.
* $B \not\succ_ A$, since A assigns more probability to the two best outcomes . If, for example, the value of z,y is very near 1, and the value of x,w is 0, then the expected value of B is near 0.5 while the expected value of A is near 0.6.

Applications

Lexicographic dominance relations are used in social choice theory to define notions of strategyproofness, incentives for participation, ordinal efficiency and envy-freeness.

Hosseini and Larson{{Cite book , last=Hadi Hosseini, Kate Larson , url=http://worldcat.org/oclc/1106222190 , title=Strategyproof Quota Mechanisms for Multiple Assignment Problems , date=2015-07-24 , oclc=1106222190 analyse the properties of rules for fair random assignment based on lexicographic dominance.

References

Random variable ordering