Лексикографическое доминирование

Лексикографическое доминирование – это полный порядок между случайными величинами . Это форма стохастического упорядочения . Оно определяется следующим образом. ^{[ 1 ]}^: 8 Случайная величина A имеет лексикографическое доминирование над случайной величиной B (обозначается $A\succ _{ld}B$ ), если выполняется одно из следующих условий:

A имеет более высокую вероятность, чем B, получить лучший результат.
A и B имеют равную вероятность получения наилучшего результата, но A имеет более высокую вероятность получения второго лучшего результата.
A и B имеют равную вероятность получения лучшего и 2-го лучшего результата, но A имеет более высокую вероятность получения 3-го лучшего результата.

Другими словами: пусть k — первый индекс, для которого вероятность получения k-го лучшего результата различна для A и B. Тогда эта вероятность должна быть выше для A.

Варианты

Восходящее лексикографическое доминирование определяется следующим образом. ^{[ 2 ]} Случайная величина A имеет восходящее лексикографическое доминирование над случайной величиной B (обозначается $A\succ _{ul}B$ ), если выполняется одно из следующих условий:

А имеет меньшую вероятность, чем Б, получить наихудший результат.
A и B имеют равную вероятность получения наихудшего результата, но A имеет меньшую вероятность получения второго наихудшего результата.
A и B имеют равную вероятность получения наихудшего и 2-го наихудшего исхода, но A имеет меньшую вероятность получения 3-го наихудшего результата.

Чтобы различать эти два понятия, стандартное понятие лексикографического доминирования иногда называют нисходящим лексикографическим доминированием и обозначают $A\succ _{dl}B$ .

Связь с другими понятиями доминирования

первого порядка Стохастическое доминирование подразумевает как нисходящее, так и восходящее лексикографическое доминирование. ^{[ 3 ]} Обратное неверно. Например, предположим, что есть четыре результата с рангом z > y > x > w. Рассмотрим две лотереи, которые присваивают z, y, x, w следующие вероятности:

А: .2, .4, .2, .2
Б: .2, .3, .4, .1

Тогда имеет место следующее:

$A\succ _{dl}B$ , поскольку они присваивают z ту же вероятность, но A присваивает большую вероятность y.
$B\succ _{ul}A$ , поскольку B приписывает меньшую вероятность наихудшему исходу w.
$A\not \succ _{sd}B$ , поскольку B присваивает большую вероятность трем лучшим результатам {z,y,x}. Если, например, значение z,y,x очень близко к 1, а значение w равно 0, то ожидаемое значение B около 0,9, а ожидаемое значение A около 0,8.
$B\not \succ _{sd}A$ , поскольку A присваивает большую вероятность двум лучшим результатам {z,y}. Если, например, значение z,y очень близко к 1, а значение x,w равно 0, то ожидаемое значение B около 0,5, а ожидаемое значение A около 0,6.

Приложения

Лексикографические отношения доминирования используются в теории социального выбора для определения понятий устойчивости стратегии . ^{[ 2 ]} стимулы для участия, ^{[ 4 ]} порядковая эффективность ^{[ 3 ]} и свобода от зависти . ^{[ 5 ]}

Хоссейни и Ларсон ^{[ 6 ]} проанализировать свойства правил справедливого случайного назначения на основе лексикографического доминирования.

Ссылки

^ Чакрабарти, Дипарнаб; Свами, Чайтанья (12 января 2014 г.). «Максимализация благосостояния и правдивость в конструкции механизмов с порядковыми предпочтениями» . Материалы 5-й конференции «Инновации в теоретической информатике» . ИТКС '14. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 105–120. дои : 10.1145/2554797.2554810 . ISBN 978-1-4503-2698-8 . S2CID 2428592 .
^ Перейти обратно: ^а ^б Чо, Вонки Джо (01 января 2016 г.). «Стимулирующие свойства для ординальных механизмов» . Игры и экономическое поведение . 95 : 168–177. дои : 10.1016/j.geb.2015.12.003 . ISSN 0899-8256 .
^ Перейти обратно: ^а ^б Чо, Вонки Джо; Доган, Баттал (01 сентября 2016 г.). «Эквивалентность понятий эффективности для порядковых задач назначения» . Письма по экономике . 146 : 8–12. дои : 10.1016/j.econlet.2016.07.007 . ISSN 0165-1765 .
^ Азиз, Харис (08 ноября 2016 г.). «Стимулы к участию в рандомизированном социальном выборе». arXiv : 1602.02174 [ cs.GT ].
^ Чо, Вонки Джо (01.06.2018). «Вероятностное задание: расширенный подход» . Социальный выбор и благосостояние . 51 (1): 137–162. дои : 10.1007/s00355-018-1110-z . ISSN 1432-217X . S2CID 19700606 .
^ Хади Хоссейни, Кейт Ларсон (24 июля 2015 г.). Устойчивые к стратегии механизмы квотирования для решения задач множественного назначения . OCLC 1106222190 .

[:02-1] Чакрабарти, Дипарнаб; Свами, Чайтанья (12 января 2014 г.). «Максимализация благосостояния и правдивость в конструкции механизмов с порядковыми предпочтениями» . Материалы 5-й конференции «Инновации в теоретической информатике» . ИТКС '14. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 105–120. дои : 10.1145/2554797.2554810 . ISBN 978-1-4503-2698-8 . S2CID 2428592 .

[:0-2] Перейти обратно: ^а ^б Чо, Вонки Джо (01 января 2016 г.). «Стимулирующие свойства для ординальных механизмов» . Игры и экономическое поведение . 95 : 168–177. дои : 10.1016/j.geb.2015.12.003 . ISSN 0899-8256 .

[:1-3] Перейти обратно: ^а ^б Чо, Вонки Джо; Доган, Баттал (01 сентября 2016 г.). «Эквивалентность понятий эффективности для порядковых задач назначения» . Письма по экономике . 146 : 8–12. дои : 10.1016/j.econlet.2016.07.007 . ISSN 0165-1765 .

[4] Азиз, Харис (08 ноября 2016 г.). «Стимулы к участию в рандомизированном социальном выборе». arXiv : 1602.02174 [ cs.GT ].

[5] Чо, Вонки Джо (01.06.2018). «Вероятностное задание: расширенный подход» . Социальный выбор и благосостояние . 51 (1): 137–162. дои : 10.1007/s00355-018-1110-z . ISSN 1432-217X . S2CID 19700606 .

[:12-6] Хади Хоссейни, Кейт Ларсон (24 июля 2015 г.). Устойчивые к стратегии механизмы квотирования для решения задач множественного назначения . OCLC 1106222190 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]