Lexicographic dominance

Statistical property

Lexicographic dominance is a total order between random variables. It is a form of stochastic ordering. It is defined as follows.[1]: 8 Random variable A has lexicographic dominance over random variable B (denoted  A ≻ l d B {\displaystyle A\succ _{ld}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

[edit]

Upward lexicographic dominance is defined as follows.[2] Random variable A has upward lexicographic dominance over random variable B (denoted  A ≻ u l B {\displaystyle A\succ _{ul}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 ≻ d l B {\displaystyle A\succ _{dl}B} .

## Relation to other dominance notions

[edit]

First-order stochastic dominance implies both downward-lexicographic and upward-lexicographic dominance.[3] 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 ≻ d l B {\displaystyle A\succ _{dl}B} , since they assign the same probability to z but A assigns more probability to y.
* B ≻ u l A {\displaystyle B\succ _{ul}A} , since B assigns less probability to the worst outcome w.
* A ⊁ s d B {\displaystyle A\not \succ _{sd}B} , since B assigns more probability to the three best outcomes {z,y,x}. 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 ⊁ s d A {\displaystyle B\not \succ _{sd}A} , since A assigns more probability to the two best outcomes {z,y}. 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

[edit]

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

Hosseini and Larson[6] analyse the properties of rules for fair random assignment based on lexicographic dominance.

## References

[edit]

1. ^ Chakrabarty, Deeparnab; Swamy, Chaitanya (2014-01-12). "Welfare maximization and truthfulness in mechanism design with ordinal preferences". Proceedings of the 5th conference on Innovations in theoretical computer science. ITCS '14. New York, NY, USA: Association for Computing Machinery. pp. 105–120. doi:10.1145/2554797.2554810. ISBN 978-1-4503-2698-8. S2CID 2428592.
2. ^ a b Cho, Wonki Jo (2016-01-01). "Incentive properties for ordinal mechanisms". Games and Economic Behavior. 95: 168–177. doi:10.1016/j.geb.2015.12.003. ISSN 0899-8256.
3. ^ a b Cho, Wonki Jo; Doğan, Battal (2016-09-01). "Equivalence of efficiency notions for ordinal assignment problems". Economics Letters. 146: 8–12. doi:10.1016/j.econlet.2016.07.007. ISSN 0165-1765.
4. ^ Aziz, Haris (2016-11-08). "Participation Incentives in Randomized Social Choice". arXiv:1602.02174 [cs.GT].
5. ^ Cho, Wonki Jo (2018-06-01). "Probabilistic assignment: an extension approach". Social Choice and Welfare. 51 (1): 137–162. doi:10.1007/s00355-018-1110-z. ISSN 1432-217X. S2CID 19700606.
6. ^ Hadi Hosseini, Kate Larson (2015-07-24). Strategyproof Quota Mechanisms for Multiple Assignment Problems. OCLC 1106222190.