Случайное распределение предметов по приоритету

Случайный приоритет (RP), ^[1] также называемая случайной серийной диктатурой (RSD), ^[2] — это процедура справедливого случайного распределения — справедливого разделения неделимых предметов между людьми.

Предполагать $n$ партнеры должны разделить $n$ (или меньше) разных предметов среди них. Поскольку предметы неделимы, некоторые партнеры обязательно получат менее предпочтительные предметы (или вообще не получат предметов). RSD пытается внести справедливость в эту ситуацию следующим образом. Нарисуйте случайную перестановку агентов из равномерного распределения. Затем позвольте им последовательно выбрать объект в этом порядке (так что первый агент в этом порядке получит первый выбор и так далее).

Характеристики

RSD — это правдивый механизм , когда количество предметов не превышает числа агентов, поскольку у вас есть только одна возможность выбрать предмет, и очевидно доминирующей стратегией в этой возможности является выбор наилучшего доступного предмета.

по RSD всегда дает результат, эффективный Парето (PE). Более того, в задаче о назначениях каждое детерминированное PE-назначение является результатом SD для некоторого упорядочения агентов. ^[1]^{: Лем.1}

Однако RSD не является ex-ante PE, когда у агентов есть полезность фон Неймана-Моргенштерна при случайном распределении, т. е. лотереи по объектам (обратите внимание, что ex-ante свобода от зависти слабее , чем ex-post свобода от зависти, но ex-ante Парето-эффективность сильнее , чем парето-эффективность постфактум). В качестве примера предположим, что имеется три агента, три элемента и утилиты VNM:

	Товар х	Пункт y
Алиса	1	0.8
Боб	1	0.2
Карл	1	0.2

RSD дает каждому агенту вероятность 1/3 каждого объекта (поскольку их предпочтения в отношении определенных объектов совпадают) и профиль ожидаемого вектора полезности (0,6, 0,4, 0,4). Но присвоение предмета y Алисе наверняка и предметов x,z случайным образом между Бобом и Карлом дает ожидаемый вектор полезности (0,8, 0,5, 0,5). Таким образом, исходный вектор полезности не эффективен по Парето .

Более того, когда агенты имеют порядковый ранг, RSD не соответствует даже более слабому свойству sd-efficiency . ^[1]^{: Раздел 2}

Когда ранги агентов по объектам формируются равномерно и случайным образом, вероятность того, что распределение, заданное RSD, является ожидаемым PE, приближается к нулю по мере роста числа агентов. ^[3]

Альтернативное правило, вероятностно-последовательное правило , является sd-эффективным (что подразумевает фактическое PE) и sd -свободным от зависти (что предполагает отсутствие зависти ex-ante), но оно неверно. Невозможно воспользоваться преимуществами обоих механизмов:

При наличии кардинальных аддитивных функций полезности ни один механизм не является симметричным, правдивым и ожидаемым PE. ^[4]
При использовании порядковых функций полезности ни один механизм не является устойчиво-эффективным, стратегически устойчивым и не обращается с равными одинаково. ^[1]^{: Thm.2}

Обобщения

Больше объектов, чем агентов

Когда их больше, чем $n$ объекты, некоторые агенты могут получить более одного объекта. Существует несколько способов распространить RSD на этот случай.

Один из способов — определить квоту для каждого агента (так, чтобы сумма квот равнялась количеству объектов) и позволить каждому агенту по очереди выбирать элементы в пределах своей квоты. Эта процедура остается нестратегической , но она очень несправедлива.
Другой способ — позволить каждому агенту выбрать один объект, а затем провести еще один раунд, в котором каждый агент выбирает один объект, пока все объекты не будут взяты; это приводит к процедуре распределения элементов по циклическому принципу . Эта процедура более справедлива, но она не является стратегической .
Обе процедуры являются частными случаями последовательности выбора .

Общее принятие решений

RSD может быть определен для более общей ситуации, в которой группа должна выбрать одну альтернативу из набора альтернатив. В этом случае RSD работает следующим образом: сначала агенты переставляются случайным образом. Начиная с набора всех альтернатив, попросите каждого агента в порядке перестановки выбрать свою любимую альтернативу (альтернативы) среди оставшихся альтернатив. Если после учета предпочтений всех агентов остается более одной альтернативы, RSD равномерно рандомизирует эти альтернативы. В упомянутой ранее настройке разделения товаров альтернативы соответствуют распределению товаров между агентами. Каждый агент имеет в своих предпочтениях большие классы эквивалентности, поскольку ему безразличны все распределения, при которых он получает один и тот же элемент.

В этой общей ситуации, если все агенты имеют строгие предпочтения по отношению к альтернативам, то RSD сводится к выбору случайного агента и выбору альтернативы, которая нравится агенту больше всего. Эта процедура известна как случайная диктатура (RD) и является уникальной процедурой, которая эффективна и не дает стратегии , когда предпочтения строгие. ^[5] Однако, когда агенты могут иметь слабые предпочтения, ни одна процедура, расширяющая RD (включая RSD), не удовлетворяет как эффективности, так и стратегической устойчивости. ^[6]

См. также

На странице справедливого случайного назначения RSD сравнивается с другими процедурами решения той же задачи, такими как вероятностно-последовательное правило .
На странице, посвященной механизму диктатуры, описывается RSD — это общее правило социального выбора, а не обязательно распределения предметов.

Ссылки

^ Jump up to: ^а ^б ^с ^д Богомольная, Анна ; Мулен, Эрве (2001). «Новое решение проблемы случайного назначения». Журнал экономической теории . 100 (2): 295. doi : 10.1006/jeth.2000.2710 .
^ Абдулкадироглу, Атила; Сонмез, Тайфун (1998). «Случайная серийная диктатура и ядро случайных пожертвований в проблемах распределения домов». Эконометрика . 66 (3): 689. дои : 10.2307/2998580 . JSTOR 2998580 .
^ Манеа, Михай (2009). «Асимптотическая порядковая неэффективность случайной серийной диктатуры». Теоретическая экономика . 4 (2): 165–197. hdl : 10419/150127 .
^ Чжоу, Линь (1990). «О гипотезе Гейла об односторонних задачах совмещения». Журнал экономической теории . 52 : 123–135. дои : 10.1016/0022-0531(90)90070-Z .
^ Гиббард, Аллан (1977). «Манипулирование схемами, в которых голосование сочетается со случайностью» (PDF) . Эконометрика . 45 (3): 665–681. дои : 10.2307/1911681 . JSTOR 1911681 .
^ Брандл, Флориан; Брандт, Феликс; Суксомпонг, Варут (2016). «Невозможность распространения случайной диктатуры на слабые предпочтения». Письма по экономике . 141 : 44–47. arXiv : 1510.07424 . дои : 10.1016/j.econlet.2016.01.028 . S2CID 4917725 .

[bm01-1] Jump up to: ^а ^б ^с ^д Богомольная, Анна ; Мулен, Эрве (2001). «Новое решение проблемы случайного назначения». Журнал экономической теории . 100 (2): 295. doi : 10.1006/jeth.2000.2710 .

[as98-2] Абдулкадироглу, Атила; Сонмез, Тайфун (1998). «Случайная серийная диктатура и ядро случайных пожертвований в проблемах распределения домов». Эконометрика . 66 (3): 689. дои : 10.2307/2998580 . JSTOR 2998580 .

[m09-3] Манеа, Михай (2009). «Асимптотическая порядковая неэффективность случайной серийной диктатуры». Теоретическая экономика . 4 (2): 165–197. hdl : 10419/150127 .

[z90-4] Чжоу, Линь (1990). «О гипотезе Гейла об односторонних задачах совмещения». Журнал экономической теории . 52 : 123–135. дои : 10.1016/0022-0531(90)90070-Z .

[g77-5] Гиббард, Аллан (1977). «Манипулирование схемами, в которых голосование сочетается со случайностью» (PDF) . Эконометрика . 45 (3): 665–681. дои : 10.2307/1911681 . JSTOR 1911681 .

[bbs16-6] Брандл, Флориан; Брандт, Феликс; Суксомпонг, Варут (2016). «Невозможность распространения случайной диктатуры на слабые предпочтения». Письма по экономике . 141 : 44–47. arXiv : 1510.07424 . дои : 10.1016/j.econlet.2016.01.028 . S2CID 4917725 .

[1]

[2]

[3]

[4]

[5]

[6]