Пропорциональное распределение предметов

Проблема справедливого распределения предметов

Пропорциональное распределение предметов — это задача справедливого распределения предметов , в которой критерием справедливости является пропорциональность : каждый агент должен получить набор, который он оценивает не менее чем 1/ n от всего распределения, где n — количество агентов. ^{[1] : 296–297}

Поскольку элементы неделимы, пропорциональное назначение может не существовать. Самый простой случай — когда есть один элемент и по крайней мере два агента: если элемент назначен одному агенту, другой будет иметь значение 0, что меньше 1/2. Поэтому в литературе рассматриваются различные смягчения требования пропорциональности.

Пропорциональное распределение

Распределение объектов называется пропорциональным (PROP), если каждый агент i оценивает свой набор не менее чем в 1/ n от общей суммы. Формально, для всех i (где M — множество всех благ):

• ${\displaystyle V_{i}(X_{i})\geq V_{i}(M)/n}$.

Пропорциональное деление может не существовать. Например, если количество людей больше количества предметов, то некоторые люди вообще не получат предмета, и их ценность будет равна нулю. Тем не менее, такое деление существует с высокой вероятностью для неделимых предметов при определенных предположениях относительно оценок агентов. ^[2]

Принятие решения о наличии распределения PROP: основные полезности

Предположим, что агенты имеют кардинальные функции полезности по элементам. Тогда проблема принятия решения о том, существует ли пропорциональное распределение, является NP-полной : ее можно свести к проблеме разделения . ^[3]

Принятие решения о наличии распределения PROP: порядковые рейтинги

Предположим, что агенты имеют порядковые ранги по элементам. Распределение называется необходимо-пропорциональным (или sd-пропорциональным ), если оно пропорционально согласно всем оценкам, согласующимся с ранжированием. Оно называется возможно-пропорциональным, если оно пропорционально согласно по крайней мере одному набору согласованных оценок.

• Прухс и Вёгингер ^[4] представляют поливременной алгоритм для принятия решения о том, существует ли необходимое пропорциональное распределение, когда агенты имеют строгие ранги. Алгоритм проще, когда есть два агента.
• Азиз, Гасперс, Маккензи и Уолш ^[5] расширяют этот алгоритм на агентов со слабыми предпочтениями и, возможно, с различными правами : они показывают, что проблема принятия решения о том, существует ли обязательно пропорциональное распределение, может быть сведена к проблеме проверки того, допускает ли двудольный граф осуществимое b-сопоставление ( сопоставление, когда ребра имеют пропускную способность).
• Они также представляют алгоритмы для принятия решения о том, существует ли возможно-пропорциональное распределение. Его время выполнения является полиномиальным, если предпочтения строгие , или число агентов является константой . Открытым является вопрос о том, находится ли проблема в P, когда число агентов является переменным, а предпочтения имеют безразличия. ^[5]

Отношение к другим критериям справедливости

С аддитивными оценками:

• Каждое распределение предметов без зависти также пропорционально. Противоположное следствие верно, когда n =2, но не когда n >2.
• Каждое пропорциональное распределение удовлетворяет максиминной доле . Обратное утверждение неверно.

Распределения PROP1

Распределение называется пропорциональным до лучших c элементов (PROPc) , если для каждого агента i существует подмножество из не более чем c элементов, которое, будучи передано i , доводит общую стоимость i до не менее 1/ n от общей суммы. Формально, для всех i (где M — множество всех товаров): ^[6]

• ${\displaystyle \exists Y\subseteq M\setminus X_{i}:~~~|Y|\leq c,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}$.

Эквивалентное определение: ценность каждого агента i составляет не менее (1/ n от общей суммы) минус ( c наиболее ценных элементов, не назначенных i ):

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{Y\subseteq M\setminus X_{i},|Y|\leq c}V_{i}(Y)}$

PROP0 эквивалентно пропорциональности, которая может не существовать. Напротив, распределение PROP1 всегда существует и может быть найдено, например, с помощью циклического распределения элементов . Интересный вопрос заключается в том, как объединить его с условиями эффективности, такими как эффективность по Парето (PE).

Поиск эффективного распределения PROP1

Конитцер, Фримен и Шах ^[6] доказали, что в контексте справедливого принятия государственных решений распределение PROP1, которое также является PE.

Барман и Кришнамурти ^[7] представили алгоритм с сильным полиномиальным временем, находящий распределение PE+PROP1 для товаров (объектов с положительной полезностью).

Бранзеи и Сандомирский ^[8] распространили условие PROP1 на рутину (объекты с отрицательной полезностью). Формально, для всех i :

• ${\displaystyle \exists Y\subseteq X_{i}:~~~|Y|\leq 1,~~~V_{i}(X_{i}\setminus Y)\geq V_{i}(M)/n}$.

Они представили алгоритм, находящий распределение PE+PROP1 для работы. Алгоритм является строго полиномиальным по времени, если фиксировано либо количество объектов, либо количество агентов (или и то, и другое).

Азиз, Карагианнис, Игараши и Уолш ^[9] расширили условие PROP1 до смешанных оценок (объекты могут иметь как положительные, так и отрицательные полезности). В этой настройке распределение называется PROP1, если для каждого агента i , если мы удалим один отрицательный элемент из набора i или добавим один положительный элемент в набор i, то полезность i составит не менее 1/ n от общей суммы. Их обобщенный алгоритм скорректированного победителя находит распределение PE+EF1 для двух агентов; такое распределение также называется PROP1.

Азиз, Мулен и Сандомирский ^[10] представили алгоритм с сильным полиномиальным временем для поиска распределения, которое является дробно-PE (сильнее, чем PE) и PROP1, с общими смешанными оценками, даже если число агентов или объектов не фиксировано, и даже если агенты имеют разные права.

Отношение к другим критериям справедливости

С аддитивными оценками:

• Каждое распределение EF1 также является PROP1, но обратное не обязательно верно даже при наличии двух агентов. ^{[11] : App.A}
• То же самое верно для любого c ≥ 1: каждое распределение EF c также является PROP c , но обратное не обязательно верно даже при наличии двух агентов.

ПРОП*(н-1) распределения

Распределение называется пропорциональным из всех, кроме c элементов (PROP* c ) для агента i , если существует набор из не более чем c элементов, который, если его удалить из набора всех элементов, то i оценивает свой набор не менее чем в 1/ n остатка. Формально, для всех i : ^[12]

• ${\displaystyle \exists Y\subseteq M:~~~|Y|\leq c,~~~V_{i}(X_{i})\geq V_{i}(M\setminus Y)/n}$.

PROP*( n -1) немного сильнее, чем PROP1: когда n =2, PROP*( n -1) эквивалентно EF1, но PROP1 слабее. Распределение PROP*( n -1) всегда существует и может быть найдено, например, с помощью циклического распределения элементов .

Отношение к другим критериям справедливости

С аддитивными оценками:

• EF1 подразумевает PROP*( n -1). Противоположное следствие верно, когда n =2, но не когда n >2. Таким образом, отношение между EF1 и PROP*( n -1) аналогично отношению между свободой от зависти и пропорциональностью, что показывает, что PROP*( n -1) является более естественным ослаблением пропорциональности, чем PROP1.
• Более того, для любого целого числа c ≥ 0, EF c подразумевает PROP*(( n -1) c ). Противоположное следствие верно, когда n = 2, но не когда n > 2. ^{[12] : Лем.2.3}

Следующие приближения максиминной доли подразумеваются PROP*( n -1): ^{[12] : Лем.2.7}

• Мультипликативное приближение: 1/ n - дробь MMS (1/ n тесно); ^{[12] : Предложение 3.6}
• Порядковая аппроксимация: 1-из-(2 n -1) MMS (2 n -1 тесно). Аналогично, для каждого целого числа c , PROP* c подразумевает 1-из-( c + n ) MMS.
• MMS, когда функция значения является бинарной. Противоположное следствие также имеет место.

Распределения PROPx

Распределение называется пропорциональным до наихудшего элемента (PROPx) , если для каждого агента i , для любого подмножества с одним элементом, не распределенным для i , если подмножество дано i , то оно приносит его значение по крайней мере до 1/ n от общего числа. Формально, для всех i : ^[13]

• ${\displaystyle \forall Y\subseteq M\setminus X_{i}:~~~|Y|=1,~~~V_{i}(X_{i}\cup Y)\geq V_{i}(M)/n}$

Эквивалентное определение: ценность каждого агента i составляет не менее (1/ n от общей суммы) минус ( наименее ценный элемент, не назначенный i ):

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\min _{Y\subseteq M\setminus X_{i},|Y|=1}V_{i}(Y)}$

Очевидно, PROPx сильнее, чем PROP1. Более того, в то время как распределения PROP1 всегда существуют, распределения PROPx могут не существовать. ^{[13] [10]}

Распределения PROPm

Распределение называется пропорциональным до максиминного элемента (PROPm) , если ценность каждого агента i составляет не менее (1/ n от общего числа) минус ( максиминный элемент, не назначенный i ), где максиминный элемент — это максимум среди всех остальных n -1 агентов j , наименее ценного элемента, назначенного j . Формально: ^[14]

• ${\displaystyle V_{i}(X_{i})~\geq ~V_{i}(M)/n~-~\max _{j\neq i}\min _{Y\subseteq X_{j},|Y|=1}V_{i}(Y)}$

Очевидно, что PROPx сильнее, чем PROPm, который сильнее, чем PROP1. Распределение PROPm существует, когда число агентов не превышает 5. ^[14]

Ссылки

1. Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору. Cambridge University Press. ISBN 9781107060432.(бесплатная онлайн-версия)
2. Suksompong, Warut (2016). «Асимптотическое существование пропорционально справедливых распределений». Математические социальные науки . 81 : 62–65. arXiv : 1806.00218 . doi : 10.1016/j.mathsocsci.2016.03.007. S2CID  14055462.
3. Бувере, Сильвен; Лемэтр, Мишель (2015). «Характеристика конфликтов при справедливом разделе неделимых благ с использованием шкалы критериев». Автономные агенты и многоагентные системы . 30 (2): 259. doi :10.1007/s10458-015-9287-3. S2CID  16041218.
4. Pruhs, Kirk; Woeginger, Gerhard J. (2012). «Развод стал проще». В Kranakis, Evangelos; Krizanc, Danny; Luccio, Flaminia (ред.). Развлечения с алгоритмами . Конспект лекций по информатике. Том 7288. Берлин, Гейдельберг: Springer. С. 305–314. doi :10.1007/978-3-642-30347-0_30. ISBN 978-3-642-30347-0.
5. Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015). «Справедливое назначение неделимых объектов при порядковых предпочтениях». Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . doi : 10.1016/j.artint.2015.06.002. S2CID  1408197.
6. Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2016). «Справедливое принятие государственных решений | Труды конференции ACM 2017 года по экономике и вычислениям». arXiv : 1611.04034 . doi :10.1145/3033274.3085125. S2CID  30188911. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
7. Барман, Сиддхарт; Кришнамурти, Санат Кумар (17 июля 2019 г.). «О близости рынков с интегральными равновесиями». Труды конференции AAAI по искусственному интеллекту . 33 (1): 1748–1755. arXiv : 1811.08673 . doi : 10.1609/aaai.v33i01.33011748 . ISSN  2374-3468. S2CID  53793188.
8. Брынзей, Симина; Сандомирский, Федор (03.07.2019). «Алгоритмы конкурентного разделения обязанностей». arXiv : 1907.01766 [cs.GT].
9. Азиз, Харис; Карагианнис, Иоаннис; Игараси, Аюми; Уолш, Тоби (11.12.2018). «Справедливое распределение комбинаций неделимых благ и обязанностей». arXiv : 1807.10684 [cs.GT].
10. Азиз, Харис; Мулен, Эрве; Сандомирский, Федор (2019-09-02). "Алгоритм полиномиального времени для вычисления оптимального по Парето и почти пропорционального распределения". arXiv : 1909.00740 [cs.GT].
11. Азиз, Харис; Хуан, Синь; Маттей, Николас; Сегал-Халеви, Эрель (2023). «Вычисление благосостояния — максимизация справедливого распределения неделимых благ». Европейский журнал операционных исследований . 307 (2): 773–784. arXiv : 2012.03979 . doi : 10.1016/j.ejor.2022.10.013.
12. Сегал-Халеви, Эрел; Суксомпонг, Варут (2019-12-01). «Демократическое справедливое распределение неделимых благ». Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . doi : 10.1016/j.artint.2019.103167. ISSN  0004-3702. S2CID  203034477.
13. Moulin, Hervé (2019-08-02). «Справедливое разделение в эпоху Интернета». Annual Review of Economics . 11 (1): 407–441. doi : 10.1146/annurev-economics-080218-025559 . ISSN  1941-1383. S2CID  189297304.
14. Бакланов, Артем; Гаримиди, Пранав; Гкатцелис, Василис; Шёпфлин, Даниэль (14.01.2021). «Достижение пропорциональности вплоть до максиминного элемента с неделимыми товарами». arXiv : 2009.09508 [cs.GT].