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

Статистическая собственность

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

Ссылки

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

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

[:0-2] Cho, Wonki Jo (2016-01-01). «Свойства стимулов для порядковых механизмов». Игры и экономическое поведение . 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). «Эквивалентность понятий эффективности для задач порядкового назначения». Economics Letters . 146 : 8– 12. doi :10.1016/j.econlet.2016.07.007. ISSN 0165-1765.

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

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

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