Честное случайное назначение

Справедливое случайное присвоение (также называемое вероятностным односторонним сопоставлением ) — это разновидность проблемы справедливого деления .

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

В общем, справедливого назначения может оказаться невозможным. Например, если Алиса и Батья оба предпочтут восточную комнату западной, только один из них получит ее, а другой будет завидовать. При случайном распределении справедливость достигается с помощью лотереи. Итак, в простом примере, приведенном выше, Алиса и Батья подбрасывают честную монету, и победитель получит восточную комнату.

История

Случайное распределение упоминается уже в Библии использовалась лотерея : для распределения земель Ханаана между коленами Израиля (Числа 26:55).

В США лотереи использовались для выделения государственных земель поселенцам (например, Оклахома в 1901 году) и для распределения радиоспектров радиовещательным компаниям (например, FCC 1981-1993). Лотерея до сих пор используется для присвоения грин-карт . ^[1]

Методы

Существует несколько способов распространить метод «подбрасывания монеты» на ситуации, в которых имеется более двух агентов, и они могут иметь разные отношения предпочтения к объектам:

Случайный приоритет (RP, он же случайная последовательная диктатура или RSD) — это очень простой механизм, который требует, чтобы агенты имели только порядковый номер по отдельным элементам. Он выбирает случайный порядок приоритетов элементов и позволяет каждому агенту по очереди выбрать свой любимый оставшийся элемент.
Вероятностный сериал (ПС) ^[2] — это еще один механизм, который работает только с порядковым ранжированием элементов. Агенты «съедают» свои любимые оставшиеся предметы с постоянной скоростью, и доля, которую удалось съесть каждому агенту, равна его/ее вероятности получить этот предмет.
Конкурентное равновесие при равных доходах (CEEI) ^[3] Это рыночный механизм: каждый предмет рассматривается как делимый товар. Каждому агенту предоставляется равный бюджет бумажной валюты, после чего агентам разрешается торговать до тех пор, пока не будет достигнуто ценовое равновесие . Это более сложный механизм, который требует от агентов наличия полных кардинальных функций полезности (или, альтернативно, порядкового ранжирования в лотереях).

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

Эффективность

Одним из желаемых свойств правила случайного назначения является эффективность по Парето (PE). Существует три варианта ПЭ:

Ex-post PE означает, что после определения окончательного распределения никакое другое распределение не будет лучше для одного агента и, по крайней мере, не будет столь же хорошим для других. Все три вышеперечисленных правила (RP, PS и CEEI) действуют по факту PE.
Ex-ante PE — более сильное свойство, актуальное для агентов с кардинальными полезностями. Это означает, что никакая другая лотерея не будет лучше для одного агента и, по крайней мере, не будет столь же хороша для других. CEEI — это ex-ante PE, когда агенты сравнивают лотереи на основе их ожидаемой полезности.
Возможный PE (или sd-PE) — промежуточное свойство, актуальное для агентов с порядковыми полезностями . Это означает, что распределение является ex-ante PE для некоторых функций оценки, соответствующих порядковому рангу агентов. PS можно-ПЭ, а РП нет.

Для PE последствия следующие: ex-ante → sd(возможно) → ex-post .

Справедливость

Еще одно желаемое свойство — отсутствие зависти (EF). Опять же, есть три варианта EF:

EF ex-post означает, что после определения окончательного распределения ни один агент не отдает предпочтение распределению другого агента. Ни одно правило не удовлетворяет этому сильному свойству; действительно, может оказаться невозможным найти распределение неделимых объектов в EF ex-post.
Ex-ante EF — более слабое свойство, актуальное для агентов с кардинальными полезностями. Это означает, что ни один агент не отдает предпочтение лотерее другого агента. CEEI представляет собой прогнозируемый EF относительно ожидаемых коммунальных услуг.
Необходимое EF (или sd-EF) — промежуточное свойство, актуальное для агентов с порядковыми полезностями . Это означает, что распределение является ожидаемым EF (см. ниже) для всех функций оценки, соответствующих порядковому рангу агентов. PS нужен-EF, а РП нет. RP является слабо ожидаемым sd-EF; это EF, когда агенты сравнивают лотереи по лексикографическому доминированию (ld-EF). ^[4]

Для EF направление импликации противоположно направлению эффективности: ex-post → sd(necessary) → ex-ante .

Правдивость

Третье желаемое свойство — правдивость (также называемая устойчивостью к стратегии). Опять же, есть три варианта:

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

Возможная правдивость — более слабое свойство, актуальное для агентов с порядковыми полезностями . Это означает, что агент не может получить стохастически доминирующую лотерею, сообщив о ложном рейтинге. Этому слабому свойству PS удовлетворяет, когда все ранжирования строгие и на человека приходится не более одного объекта. В этом контексте оно также правдиво в отношении лексикографического доминирования ( ld-truthful ). ^[4] Его не устраивает, когда рейтинги слабы. ^[5]
Необходимая правдивость — более сильное свойство, актуальное для агентов с порядковой полезностью . Это означает, что агент, сообщающий о ложном рейтинге, всегда получает лотерею с преобладанием стохастических чисел. Этому сильному свойству удовлетворяет RP, и его можно корректно распространить и на общий случай, когда объектов больше, чем людей.

В следующей таблице сравниваются свойства различных правил (столбцы RP и PS основаны на ^[6]):


	#предметы ≤ #агенты			#предметы > #агенты
	РП	ПС	ЦВЕИ	РП	ПС	ЦВЕИ
Эффективность:	Экс-пост ЧП	Возможное ЧП	предварительно EP	Нет	возможно ЧП	предварительно EP
Справедливость :	Слабый СД-ЭФ; ld-EF	Необходимый EF	предварительный EF	Слабый СД-ЭФ	СД-ЭФ	ЕСЛИ
Правдивость:	Необходимо правдивый	Возможен сд-правдивый; ld-truthful _{[строгие настройки]} Нет _{[слабые настройки]}	Нет	сд-правдивый*	Нет	Нет

Невозможные комбинации

Некоторые комбинации трех вышеуказанных свойств не могут быть одновременно удовлетворены ни одним механизмом:

Для агентов с кардинальными утилитами Чжоу ^[7] доказывает, что ни один механизм не удовлетворяет ожидаемой эффективности , ожидаемой правдивости и равному обращению с равными (= агенты с идентичными функциями полезности должны получать одинаковую полезность).
Для агентов со строгими порядковыми полезностями, Богомолная и Мулен ^[2] докажите, что ни один механизм не удовлетворяет возможной эффективности , необходимой правдивости и равному обращению с равными .
Для агентов со слабыми порядковыми полезностями Катта и Сетураман ^[5] докажите, что ни один механизм не удовлетворяет возможной эффективности , возможной правдивости и необходимой свободе от зависти .

Разложение дробного распределения

Правила PS и CEEI вычисляют матрицу ожидаемых назначений, т. е. предельные вероятности, с которыми каждый агент получает каждый объект. Однако, поскольку окончательное распределение должно быть сопоставлением, необходимо найти разложение этой матрицы в лотерею сопоставлений.

В классической ситуации, когда m = n , это можно сделать с помощью алгоритма Биркгофа . Он может разложить любую n матрицу вероятностей агента и объекта размером на n в выпуклую комбинацию O( n ²) матрицы перестановок , каждая из которых представляет собой паросочетание. Однако разложение не уникально, и некоторые разложения могут быть лучше других.

Будиш, Че, Кодзима и Милгром ^[1] обобщить алгоритм Биркгофа на произвольные m и n . Они также позволяют добавлять ограничения на назначения при максимальном наборе условий набора ограничений. Они также представляют метод декомпозиции, который минимизирует разницу в полезности, которую испытывают агенты при различных сопоставлениях.

Демельмейстер, Гуссенс, Херманс и Леус ^[8] представить алгоритм декомпозиции за полиномиальное время, который максимизирует наихудшее количество агентов, получающих объект. Их алгоритм гарантирует, что наихудшее количество агентов равно ожидаемому числу агентов, округленному в меньшую сторону, что является наилучшим из возможных. Они представляют другой алгоритм декомпозиции, который максимизирует количество назначенных агентов в наихудшем случае, гарантируя при этом, что все совпадения в декомпозиции будут ex-post PE; второй алгоритм можно использовать только для дробных присвоений, выдаваемых PS, но не соответствующих RP. Для RP возможно достичь только 1/2-факторного приближения к оптимальному числу назначенных агентов в наихудшем случае. Для общих дробных назначений максимизация наихудшего числа назначенных агентов, подлежащих ex-post PE, является NP-трудной. Они также представляют структуру генерации столбцов , которую можно использовать для оптимизации других критериев наихудшего случая.

Эмпирическое сравнение

Хоссейни, Ларсон и Коэн ^[6] сравните РП и ПС в различных настройках. Они показывают, что:

Когда имеется не более 2 объектов и не более 3 агентов, RP и PS возвращают одинаковое распределение.
Когда существует не более 2 объектов, для любого количества агентов, PS является sd-правдивым, а RP является sd-свободным от зависти, и в большинстве случаев PS доминирует над RP, особенно с 4 или более агентами.
Когда существует 3 или более объектов (и 3 или более агентов), RP и PS могут возвращать разные распределения, и ни одно распределение не доминирует по Парето над другим. Например, предположим, что есть три объекта a,b,c и три агента с рангами предпочтений (1) a>c>b, (2) a>b>c, (3) b>a>c. Тогда агенту (1) и RP, и PS дают 1/2 a + 1/2 c; агенту (2) RP дает 1/2 a + 1/6 b + 1/3 c, тогда как PS дает 1/2 a + 1/4 b + 1/4 c, что является стохастически-доминантным ; и агенту (3) RP дает 5/6 b + 1/6 c, тогда как PS дает 3/4 b + 1/4 c, что является стохастически доминирующим. Итак, (1) безразличен, (2) строго предпочитает PS и (3) строго предпочитает RP.
Доля профилей предпочтений, для которых PS sd-доминирует над RP, велика, когда число агентов и объектов различается, но приближается к 0, когда числа равны. То же самое справедливо и для ld-доминирования.
Когда агенты нейтральны к риску , ожидаемое социальное благосостояние PS больше, чем RP, но разница существенна только тогда, когда n≠m . При РП доля завистников близка к нулю при n ≥ m. PS можно манипулировать, и выгода от манипуляций увеличивается, когда m > n .
Когда агенты стремятся к риску , ожидаемое социальное благосостояние PS больше, чем RP, и разница быстро растет, когда n≠m. Напротив, когда n = m достигает более высокого RP в большинстве случаев социального благосостояния. При РП доля завистливых агентов близка к нулю, когда n ≥ m, но порождает зависть, когда m>n. Зависть к РП уменьшается по мере увеличения стремления к риску. Выгода от манипулирования PS снижается, когда агенты более склонны к риску.
Когда агенты не склонны к риску , разрыв в социальном благосостоянии между RP и PS становится меньше (хотя все еще статистически значим). Доля завистников в РП увеличивается, но зависть остается ниже 0,01 при n ≥ m . Манипулируемость PS переходит к 1 при росте m / n .

Расширения

Тао и Коул ^[9] изучить существование случайных распределений PE и EF, когда полезности нелинейны (могут иметь дополнения).

Йылмаз ^[10] изучает проблему случайного назначения, когда агенты обладают способностями.

Шен, Ван, Чжу, Файн и Мунагала ^[11] изучите проблему случайного назначения, когда у агентов есть приоритеты (агенты с более высокими приоритетами должны получить предпочтительные товары раньше агентов с более низкими приоритетами), но приоритеты неопределенны.

Дадди ^[12] изучает эгалитарное случайное распределение.

См. также

Гармония аренды — это вариант задачи о назначении, в которой справедливость достигается за счет денежных выплат, а не рандомизации.
Справедливое распределение предметов — это ситуация, при которой агенты могут получить более одного предмета.
Жеребьевка - случайный отбор политических деятелей.
Случайное двустороннее совпадение – в основном используется для спортивных турниров.

Ссылки

^ Перейти обратно: ^а ^б Будиш, Эрик; Че, Ён Ку; Кодзима, Фухито; Милгром, Пол (1 апреля 2013 г.). «Проектирование механизмов случайного распределения: теория и приложения» . Американский экономический обзор . 103 (2): 585–623. дои : 10.1257/aer.103.2.585 . ISSN 0002-8282 .
^ Перейти обратно: ^а ^б Богомольная, Анна ; Мулен, Эрве (2001). «Новое решение проблемы случайного назначения». Журнал экономической теории . 100 (2): 295. doi : 10.1006/jeth.2000.2710 .
^ Хайланд, Анунд; Зекхаузер, Ричард (1979). «Эффективное распределение людей по должностям». Журнал политической экономии . 87 (2): 293. дои : 10.1086/260757 . S2CID 154167284 .
^ Перейти обратно: ^а ^б Кейт, Хоссейни, Хади Ларсон (24 июля 2015 г.). Устойчивые к стратегии механизмы квотирования для решения задач множественного назначения . OCLC 1106222190 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Перейти обратно: ^а ^б Катта, Акшай-Кумар; Сетураман, Джей (2006). «Решение проблемы случайного назначения в области полных предпочтений». Журнал экономической теории . 131 : 231–250. дои : 10.1016/j.jet.2005.05.001 .
^ Перейти обратно: ^а ^б Хади Хоссейни, Кейт Ларсон, Робин Коэн (2018). «Исследование особенностей механизмов одностороннего сопоставления при различных предпочтениях и отношениях к риску» . Автономные агенты и мультиагентные системы . 32 (4): 534–567. arXiv : 1703.00320 . дои : 10.1007/s10458-018-9387-y . S2CID 14041902 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Чжоу, Линь (1 октября 1990 г.). «О гипотезе Гейла об односторонних задачах совмещения» . Журнал экономической теории . 52 (1): 123–135. дои : 10.1016/0022-0531(90)90070-Z . ISSN 0022-0531 .
^ Демельмейстер, Том; Гуссенс, Дрис; Херманс, Бен; Леус, Роэл (2023). «Подход пессимиста к одностороннему сопоставлению». Европейский журнал операционных исследований . 305 (3): 1087–1099. arXiv : 2101.00579 . дои : 10.1016/j.ejor.2022.07.013 . S2CID 245669132 .
^ Коул, Ричард; Тао, Исинь (01 апреля 2021 г.). «О существовании Парето-эффективных и свободных от зависти распределений» . Журнал экономической теории . 193 : 105207. arXiv : 1906.07257 . дои : 10.1016/j.jet.2021.105207 . ISSN 0022-0531 . S2CID 189999837 .
^ Йылмаз, Озгюр (2009). «Случайное назначение при слабых предпочтениях» . Игры и экономическое поведение . 66 : 546–558. дои : 10.1016/j.geb.2008.04.017 .
^ Шен, Зею; Ван, Чжии; Чжу, Синъюй; Фейн, Брэндон; Мунагала, Камеш (2023). «Справедливость в задаче назначения с неопределенными приоритетами». arXiv : 2301.13804 [ cs.GT ].
^ Дадди, Конал (2022). «Эгалитарное случайное распределение» . дои : 10.2139/ssrn.4197224 . S2CID 252192116 . ССНН 4197224 .

[:12-1] Перейти обратно: ^а ^б Будиш, Эрик; Че, Ён Ку; Кодзима, Фухито; Милгром, Пол (1 апреля 2013 г.). «Проектирование механизмов случайного распределения: теория и приложения» . Американский экономический обзор . 103 (2): 585–623. дои : 10.1257/aer.103.2.585 . ISSN 0002-8282 .

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

[hz79-3] Хайланд, Анунд; Зекхаузер, Ричард (1979). «Эффективное распределение людей по должностям». Журнал политической экономии . 87 (2): 293. дои : 10.1086/260757 . S2CID 154167284 .

[:1-4] Перейти обратно: ^а ^б Кейт, Хоссейни, Хади Ларсон (24 июля 2015 г.). Устойчивые к стратегии механизмы квотирования для решения задач множественного назначения . OCLC 1106222190 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[ks06-5] Перейти обратно: ^а ^б Катта, Акшай-Кумар; Сетураман, Джей (2006). «Решение проблемы случайного назначения в области полных предпочтений». Журнал экономической теории . 131 : 231–250. дои : 10.1016/j.jet.2005.05.001 .

[:0-6] Перейти обратно: ^а ^б Хади Хоссейни, Кейт Ларсон, Робин Коэн (2018). «Исследование особенностей механизмов одностороннего сопоставления при различных предпочтениях и отношениях к риску» . Автономные агенты и мультиагентные системы . 32 (4): 534–567. arXiv : 1703.00320 . дои : 10.1007/s10458-018-9387-y . S2CID 14041902 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

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

[8] Демельмейстер, Том; Гуссенс, Дрис; Херманс, Бен; Леус, Роэл (2023). «Подход пессимиста к одностороннему сопоставлению». Европейский журнал операционных исследований . 305 (3): 1087–1099. arXiv : 2101.00579 . дои : 10.1016/j.ejor.2022.07.013 . S2CID 245669132 .

[9] Коул, Ричард; Тао, Исинь (01 апреля 2021 г.). «О существовании Парето-эффективных и свободных от зависти распределений» . Журнал экономической теории . 193 : 105207. arXiv : 1906.07257 . дои : 10.1016/j.jet.2021.105207 . ISSN 0022-0531 . S2CID 189999837 .

[y09-10] Йылмаз, Озгюр (2009). «Случайное назначение при слабых предпочтениях» . Игры и экономическое поведение . 66 : 546–558. дои : 10.1016/j.geb.2008.04.017 .

[11] Шен, Зею; Ван, Чжии; Чжу, Синъюй; Фейн, Брэндон; Мунагала, Камеш (2023). «Справедливость в задаче назначения с неопределенными приоритетами». arXiv : 2301.13804 [ cs.GT ].

[12] Дадди, Конал (2022). «Эгалитарное случайное распределение» . дои : 10.2139/ssrn.4197224 . S2CID 252192116 . ССНН 4197224 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]