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

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

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

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

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

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

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

Решение о существовании распределения PROP: основные утилиты

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

Решение о существовании распределения PROP: порядковый номер

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

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

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

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

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

Распределения ПРОП1

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

$\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 ):

$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 :

$\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.

Aziz, Moulin and Sandomirskiy ^{[ 10 ]} представил алгоритм со строго полиномиальным временем для поиска распределения, которое является дробным PE (более сильным, чем PE) и PROP1, с общими смешанными оценками, даже если количество агентов или объектов не фиксировано, и даже если агенты имеют разные права .

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

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

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

PROP*( n -1) распределения

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

$\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 - дробь ММС (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 ]}

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

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

$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 ]}

$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 ]}

Ссылки

^ Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )
^ Суксомпонг, Варут (2016). «Асимптотическое существование пропорционально справедливого распределения». Математические социальные науки . 81 : 62–65. arXiv : 1806.00218 . doi : 10.1016/j.mathsocsci.2016.03.007 . S2CID 14055462 .
^ Бувере, Сильвен; Леметр, Мишель (2015). «Характеристика конфликтов при справедливом разделе неделимого блага по шкале критериев». Автономные агенты и мультиагентные системы . 30 (2): 259. doi : 10.1007/s10458-015-9287-3 . S2CID 16041218 .
^ Прус, Кирк; Вегингер, Герхард Дж. (2012). «Развод стал проще» . В Кранакисе, Евангелос; Кризанц, Дэнни; Люччио, Фламиния (ред.). Развлечение с алгоритмами . Конспекты лекций по информатике. Том. 7288. Берлин, Гейдельберг: Springer. стр. 305–314. дои : 10.1007/978-3-642-30347-0_30 . ISBN 978-3-642-30347-0 .
^ Jump up to: ^а ^б Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015). «Справедливое распределение неделимых объектов по порядковым предпочтениям». Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . дои : 10.1016/j.artint.2015.06.002 . S2CID 1408197 .
^ Jump up to: ^а ^б Конитцер, Винсент; Фриман, Руперт; Шах, Нисарг (2016). «Справедливое принятие общественных решений | Материалы конференции ACM 2017 по экономике и вычислениям». arXiv : 1611.04034 . дои : 10.1145/3033274.3085125 . S2CID 30188911 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Бармен, Сиддхарт; Кришнамурти, Санат Кумар (17 июля 2019 г.). «О близости рынков с интегральными равновесиями» . Материалы конференции AAAI по искусственному интеллекту . 33 (1): 1748–1755. arXiv : 1811.08673 . дои : 10.1609/aaai.v33i01.33011748 . ISSN 2374-3468 . S2CID 53793188 .
^ Брынзей, Симина; Сандомирский, Федор (03.07.2019). «Алгоритмы конкурентного разделения обязанностей». arXiv : 1907.01766 [ cs.GT ].
^ Азиз, Харис; Караяннис, Иоаннис; Игараси, Аюми; Уолш, Тоби (11 декабря 2018 г.). «Справедливое распределение комбинаций неделимых товаров и работ». arXiv : 1807.10684 [ cs.GT ].
^ Jump up to: ^а ^б Азиз, Харис; Мулен, Эрве; Сандомирский, Федор (02.09.2019). «Алгоритм с полиномиальным временем для расчета оптимального по Парето и почти пропорционального распределения». arXiv : 1909.00740 [ cs.GT ].
^ Азиз, Харис; Хуан, Синь; Маттеи, Николас; Сегал-Халеви, Эрель (07 декабря 2020 г.). «Расчет справедливого утилитарного распределения неделимых благ». arXiv : 2012.03979 [ cs.GT ].
^ Jump up to: ^а ^б ^с ^д Сегал-Халеви, Эрель; Суксомпонг, Варут (01 декабря 2019 г.). «Демократическое справедливое распределение неделимых благ». Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . дои : 10.1016/j.artint.2019.103167 . ISSN 0004-3702 . S2CID 203034477 .
^ Jump up to: ^а ^б Мулен, Эрве (2 августа 2019 г.). «Справедливое разделение в эпоху Интернета» . Ежегодный обзор экономики . 11 (1): 407–441. doi : 10.1146/annurev- Economics-080218-025559 . ISSN 1941-1383 . S2CID 189297304 .
^ Jump up to: ^а ^б Бакланов Артем; Гаримиди, Пранав; Гкацелис, Василис; Шепфлин, Дэниел (14 января 2021 г.). «Достижение пропорциональности до максимной позиции с неделимыми товарами». arXiv : 2009.09508 [ cs.GT ].

[comsoc-1] Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )

[2] Суксомпонг, Варут (2016). «Асимптотическое существование пропорционально справедливого распределения». Математические социальные науки . 81 : 62–65. arXiv : 1806.00218 . doi : 10.1016/j.mathsocsci.2016.03.007 . S2CID 14055462 .

[bl15-3] Бувере, Сильвен; Леметр, Мишель (2015). «Характеристика конфликтов при справедливом разделе неделимого блага по шкале критериев». Автономные агенты и мультиагентные системы . 30 (2): 259. doi : 10.1007/s10458-015-9287-3 . S2CID 16041218 .

[4] Прус, Кирк; Вегингер, Герхард Дж. (2012). «Развод стал проще» . В Кранакисе, Евангелос; Кризанц, Дэнни; Люччио, Фламиния (ред.). Развлечение с алгоритмами . Конспекты лекций по информатике. Том. 7288. Берлин, Гейдельберг: Springer. стр. 305–314. дои : 10.1007/978-3-642-30347-0_30 . ISBN 978-3-642-30347-0 .

[agmw15-5] Jump up to: ^а ^б Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015). «Справедливое распределение неделимых объектов по порядковым предпочтениям». Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . дои : 10.1016/j.artint.2015.06.002 . S2CID 1408197 .

[:0-6] Jump up to: ^а ^б Конитцер, Винсент; Фриман, Руперт; Шах, Нисарг (2016). «Справедливое принятие общественных решений | Материалы конференции ACM 2017 по экономике и вычислениям». arXiv : 1611.04034 . дои : 10.1145/3033274.3085125 . S2CID 30188911 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[7] Бармен, Сиддхарт; Кришнамурти, Санат Кумар (17 июля 2019 г.). «О близости рынков с интегральными равновесиями» . Материалы конференции AAAI по искусственному интеллекту . 33 (1): 1748–1755. arXiv : 1811.08673 . дои : 10.1609/aaai.v33i01.33011748 . ISSN 2374-3468 . S2CID 53793188 .

[8] Брынзей, Симина; Сандомирский, Федор (03.07.2019). «Алгоритмы конкурентного разделения обязанностей». arXiv : 1907.01766 [ cs.GT ].

[:2-9] Азиз, Харис; Караяннис, Иоаннис; Игараси, Аюми; Уолш, Тоби (11 декабря 2018 г.). «Справедливое распределение комбинаций неделимых товаров и работ». arXiv : 1807.10684 [ cs.GT ].

[:1-10] Jump up to: ^а ^б Азиз, Харис; Мулен, Эрве; Сандомирский, Федор (02.09.2019). «Алгоритм с полиномиальным временем для расчета оптимального по Парето и почти пропорционального распределения». arXiv : 1909.00740 [ cs.GT ].

[11] Азиз, Харис; Хуан, Синь; Маттеи, Николас; Сегал-Халеви, Эрель (07 декабря 2020 г.). «Расчет справедливого утилитарного распределения неделимых благ». arXiv : 2012.03979 [ cs.GT ].

[:6-12] Jump up to: ^а ^б ^с ^д Сегал-Халеви, Эрель; Суксомпонг, Варут (01 декабря 2019 г.). «Демократическое справедливое распределение неделимых благ». Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . дои : 10.1016/j.artint.2019.103167 . ISSN 0004-3702 . S2CID 203034477 .

[:3-13] Jump up to: ^а ^б Мулен, Эрве (2 августа 2019 г.). «Справедливое разделение в эпоху Интернета» . Ежегодный обзор экономики . 11 (1): 407–441. doi : 10.1146/annurev- Economics-080218-025559 . ISSN 1941-1383 . S2CID 189297304 .

[:4-14] Jump up to: ^а ^б Бакланов Артем; Гаримиди, Пранав; Гкацелис, Василис; Шепфлин, Дэниел (14 января 2021 г.). «Достижение пропорциональности до максимной позиции с неделимыми товарами». arXiv : 2009.09508 [ cs.GT ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]