Lexikografisk dominans

Lexikografisk dominans är en total ordning mellan slumpvariabler . Det är en form av stokastisk beställning . Den definieras enligt följande. Slumpvariabel A har lexikografisk dominans över slumpvariabel B (betecknad $A\succ _{ld}B$ ) om något av följande gäller:

A har högre sannolikhet än B att få det bästa resultatet.
A och B har lika sannolikhet att få det bästa resultatet, men A har en högre sannolikhet att få det 2:a bästa resultatet.
A och B har lika sannolikhet att få det bästa och 2:a bästa resultatet, men A har en högre sannolikhet att få det 3:e bästa resultatet.

Med andra ord: låt k vara det första indexet för vilket sannolikheten att få det k:te bästa utfallet är olika för A och B. Då borde denna sannolikhet vara högre för A.

Varianter

Uppåtriktad lexikografisk dominans definieras enligt följande. Slumpvariabel A har uppåtriktad lexikografisk dominans över slumpvariabel B (betecknad $A\succ _{ul}B$ ) om något av följande gäller:

A har lägre sannolikhet än B att få det sämsta resultatet.
A och B har lika sannolikhet att få det sämsta resultatet, men A har en lägre sannolikhet att få det 2:a sämsta resultatet.
A och B har lika sannolikhet att få de sämsta och 2:a sämsta resultaten, men A har en lägre sannolikhet att få de 3:e sämsta resultaten.

För att skilja mellan de två föreställningarna kallas den vanliga lexikografiska dominansuppfattningen ibland nedåtriktad lexikografisk dominans och betecknas $A\succ _{dl}B$ .

Relation till andra dominansuppfattningar

Första ordningens stokastisk dominans innebär både nedåt-lexikografisk och uppåt-lexikografisk dominans. Det motsatta är inte sant. Anta till exempel att det finns fyra resultat rangordnade z > y > x > w. Betrakta de två lotterierna som tilldelar z, y, x, w följande sannolikheter:

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

Då gäller följande:

$A\succ _{dl}B$ , eftersom de tilldelar samma sannolikhet till z men A tilldelar y mer sannolikhet.
$B\succ _{ul}A$ , eftersom B tilldelar mindre sannolikhet till det sämsta resultatet w.
$A\not \succ _{sd}B$ , eftersom B tilldelar mer sannolikhet till de tre bästa resultaten {z,y,x}. Om till exempel värdet på z,y,x är mycket nära 1, och värdet på w är 0, så är det förväntade värdet på B nära 0,9 medan det förväntade värdet på A är nära 0,8.
$B\not \succ _{sd}A$ , eftersom A tilldelar mer sannolikhet till de två bästa resultaten {z,y}. Om till exempel värdet av z,y är mycket nära 1, och värdet av x,w är 0, så är det förväntade värdet för B nära 0,5 medan det förväntade värdet av A är nära 0,6.

Ansökningar

Lexikografiska dominansrelationer används i teorin om sociala val för att definiera föreställningar om strategisäkerhet , incitament för deltagande, ordinal effektivitet och avundsfrihet .

Hosseini och Larson analyserar egenskaperna hos regler för rättvis slumpmässig tilldelning baserat på lexikografisk dominans.

^ Chakrabarty, Deeparnab; Swamy, Chaitanya (2014-01-12). "Välfärdsmaximering och sanningsenlighet i mekanismdesign med ordinarie preferenser" . Proceedings of the 5th Conference on Innovations in Theoretical Computer Science . ITCS '14. New York, NY, USA: Association for Computing Machinery: 105–120. doi : 10.1145/2554797.2554810 . ISBN 978-1-4503-2698-8 . S2CID 2428592 .
^ ^a ^b Cho, Wonki Jo (2016-01-01). "Incitamentegenskaper för ordinalmekanismer" . Spel och ekonomiskt beteende . 95 : 168–177. doi : 10.1016/j.geb.2015.12.003 . ISSN 0899-8256 .
^ ^a ^b Cho, Wonki Jo; Doğan, Battal (2016-09-01). "Ekvivalens av effektivitetsbegrepp för ordinala tilldelningsproblem" . Ekonomibrev . 146 : 8–12. doi : 10.1016/j.econlet.2016.07.007 . ISSN 0165-1765 .
^ Aziz, Haris (2016-11-08). "Incitament för deltagande i randomiserade sociala val". arXiv : 1602.02174 [ cs.GT ].
^ Cho, Wonki Jo (2018-06-01). "Probabilistiskt uppdrag: ett förlängningssätt" . Socialt val och välfärd . 51 (1): 137–162. doi : 10.1007/s00355-018-1110-z . ISSN 1432-217X . S2CID 19700606 .
^ Hadi Hosseini, Kate Larson (2015-07-24). Strategisäkra kvotmekanismer för problem med flera tilldelningar . OCLC 1106222190 .

[:02-1] Chakrabarty, Deeparnab; Swamy, Chaitanya (2014-01-12). "Välfärdsmaximering och sanningsenlighet i mekanismdesign med ordinarie preferenser" . Proceedings of the 5th Conference on Innovations in Theoretical Computer Science . ITCS '14. New York, NY, USA: Association for Computing Machinery: 105–120. doi : 10.1145/2554797.2554810 . ISBN 978-1-4503-2698-8 . S2CID 2428592 .

[:0-2] Cho, Wonki Jo (2016-01-01). "Incitamentegenskaper för ordinalmekanismer" . Spel och ekonomiskt beteende . 95 : 168–177. doi : 10.1016/j.geb.2015.12.003 . ISSN 0899-8256 .

[:1-3] Cho, Wonki Jo; Doğan, Battal (2016-09-01). "Ekvivalens av effektivitetsbegrepp för ordinala tilldelningsproblem" . Ekonomibrev . 146 : 8–12. doi : 10.1016/j.econlet.2016.07.007 . ISSN 0165-1765 .

[4] Aziz, Haris (2016-11-08). "Incitament för deltagande i randomiserade sociala val". arXiv : 1602.02174 [ cs.GT ].

[5] Cho, Wonki Jo (2018-06-01). "Probabilistiskt uppdrag: ett förlängningssätt" . Socialt val och välfärd . 51 (1): 137–162. doi : 10.1007/s00355-018-1110-z . ISSN 1432-217X . S2CID 19700606 .

[:12-6] Hadi Hosseini, Kate Larson (2015-07-24). Strategisäkra kvotmekanismer för problem med flera tilldelningar . OCLC 1106222190 .