Приемлемое подмножество

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

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

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

Определения

Приемлемое подмножество

Существует множество S, содержащее m объектов. Есть n которым нужно выбрать подмножество S. агентов , Каждый агент характеризуется отношением предпочтения на S. подмножествах Предполагается, что отношение предпочтения монотонно : агент всегда слабо предпочитает набор всем его подмножествам. Подмножество T из S называется согласным , если все агенты предпочитают T вместо S \ T .

Если отношение предпочтения агента представлено полезности субаддитивной функцией u , то для любого приемлемого подмножества T u( T ) ≥ u( S )/2. ^{[ 2 ]}

В качестве примера предположим, что есть два объекта — хлеб и вино и два агента — Алиса и Джордж. Отношение предпочтений Алисы: {хлеб,вино} > {хлеб} > {вино} > {}. Если отношение предпочтения Джорджа такое же, то есть два приятных подмножества: {хлеб,вино} и {хлеб}. Но если отношение предпочтения Джорджа — {хлеб, вино} > {вино} > {хлеб} > {}, то единственным приемлемым подмножеством будет {хлеб, вино}.

Обязательно согласованное подмножество

Если заданы отношения предпочтения агентов на подмножествах, легко проверить, является ли подмножество приемлемым. только отношения предпочтений агентов по отдельным объектам Но часто задаются . В этом случае часто предполагается, что предпочтения агентов не только монотонны, но и отзывчивы . Подмножество T из S называется обязательно согласным , если все агенты предпочитают T вместо S \ T в соответствии с ответным расширением множества их предпочтений на отдельные объекты.

Близким свойством подмножеств является:

(*) Для каждого k из 1,..., m подмножество T содержит не менее k /2 лучших k объектов для агента i .

Чтобы удовлетворить свойству (*), подмножество T должно содержать лучший объект в S ; хотя бы два из трёх лучших объектов в S ; минимум три из пяти лучших объектов в S ; и т. д.

Если подмножество T удовлетворяет (*) для всех агентов, то оно обязательно согласовано. Обратный вывод справедлив, если отношения предпочтения агентов в отношении неделимых объектов строгие. ^{[ 3 ]}^{[ 4 ]}

Наихудшие границы приемлемого размера подмножества

Какое наименьшее приемлемое подмножество мы можем найти?

Приемлемые подмножества

Рассмотрим сначала одного агента. В некоторых случаях приемлемое подмножество должно содержать по крайней мере $\lceil m/2\rceil$ объекты. Пример: все m объектов идентичны. Более того, всегда существует приемлемое подмножество, содержащее $\lceil m/2\rceil$ объекты. Это следует из следующей леммы:

Для каждого агента i , если два подмножества V ₁ и V ₂ не пересекаются, то хотя бы одно из S\ V ₁ или S\ V ₂ согласовано с i .

(это потому, что S\ V2 _{содержит} , а _S \ V2 _V1 содержит V1 _и предпочтения монотонны).

Это можно обобщить: для любых n агентов и m объектов всегда существует приемлемое подмножество размера. ${\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }$ , и оно тесно (для некоторых предпочтений это наименьший размер приемлемого подмножества). Доказательство для двух агентов конструктивно. Доказательство для n агентов использует граф Кнезера . Позволять $k:={\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }$ , и пусть G — граф Кнезера $KG(m,m-k)$ , то есть граф, вершины которого являются подмножествами m - k объектов, причем два подмножества связаны тогда и только тогда, когда они не пересекаются. Если существует вершина V такая, что все агенты предпочитают S\ V V , то S\ V — приемлемое подмножество размера k . В противном случае мы можем определить цвет для каждого агента и раскрасить каждую вершину V графа G агентом, который предпочитает V вместо S\V. По теореме о хроматическом числе графов Кнезера хроматическое число G равно $m-2(m-k)+2=n+1$ ; это означает, что в только что определенной n -раскраске есть две соседние вершины одного цвета. Другими словами, существуют два непересекающихся подмножества, так что один агент i предпочитает каждое из них своему дополнению. Но это противоречит приведенной выше лемме. Следовательно, должно существовать приемлемое подмножество размера k . ^{[ 2 ]}^{: Thm.1}

Когда агентов не более трех и их предпочтения отзывчивы, приемлемое подмножество размера ${\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }$ можно вычислить за полиномиальное время, используя полиномиально множество запросов вида «какое из этих двух подмножеств лучше?». ^{[ 2 ]}^{: Thm.2-3}

Когда существует любое количество агентов с аддитивными полезностями или постоянное число агентов с монотонными полезностями, приемлемое подмножество размера ${\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }$ может быть найдено за полиномиальное время, используя результаты консенсусного деления пополам . ^{[ 5 ]}

Обязательно согласованные подмножества

Когда есть два агента с отзывчивыми предпочтениями, обязательно согласованное подмножество размера. ${\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }$ существует и может быть вычислено за полиномиальное время.

Когда имеется n ≥ 3 агентов с отзывчивыми предпочтениями, обязательно приемлемого подмножества такого размера может не существовать. Однако всегда существует обязательно приемлемое подмножество размеров $m/2+(n+1)\lceil 4n\log {m}\rceil$ , и такой набор можно вычислить за полиномиальное время. С другой стороны, для каждого m , являющегося степенью 3, существуют порядковые предпочтения 3 агентов такие, что каждое обязательно согласованное подмножество имеет размер не менее $m/2+(\log _{3}{m})/4$ . Оба доказательства используют теоремы о неточности перестановок .

Существует рандомизированный алгоритм , который вычисляет обязательно приемлемое подмножество размера. $m/2+O({\sqrt {m}})$ . ^{[ 2 ]}^{: Thm.4-6}

Вычисление наименьшего приемлемого подмножества

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

Для агентов с общими монотонными предпочтениями не существует алгоритма, который вычисляет наименьшее приемлемое множество с использованием полиномиального числа запросов. Более того, для каждой константы c не существует алгоритма, который делает не более m ^с^/8 запрашивает и находит подходящее подмножество с ожидаемым размером не более m /( c log m ) от минимального, даже с одним агентом. Это очень сложно: существует алгоритм за полиномиальное время, который находит приемлемое подмножество размером не более O( m /log m ) от минимума.

Даже для агентов с аддитивными полезностями решение о существовании приемлемого подмножества размера m /2 является NP-трудным; доказательство проводится путем редукции проблемы сбалансированного разделения . Для любого фиксированного числа аддитивных агентов для этой задачи существует псевдополиномиальное время; но если число агентов не фиксировано, то задача является сильно NP-трудной. Существует алгоритм аппроксимации O(log n ) с полиномиальным временем. ^{[ 2 ]}^{: Thm.7-13}

Расширения

Задача о приемлемом подмножестве изучалась с дополнительным ограничением, представленным матроидом . ^{[ 6 ]}

См. также

Распределение предметов без зависти
Алгоритм совместного бюджетирования
Выборы с несколькими победителями
Консенсусное сокращение вдвое
Справедливое разделение между группами — вариант справедливого дележа, при котором части ресурса раздаются заранее определенным группам, а не отдельным лицам.

Ссылки

^ Суксомпонг, Варут (9 июля 2016 г.). «Назначение небольшого приятного набора неделимых предметов нескольким игрокам» . Материалы двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 489–495. arXiv : 1606.08077 . дои : 10.1016/j.artint.2018.10.001 . ISBN 978-1-57735-770-4 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Мануранси, Пасин; Суксомпонг, Варут (01 марта 2019 г.). «Вычисление небольшого приятного набора неделимых элементов» . Искусственный интеллект . 268 : 96–114. arXiv : 1606.08077 . дои : 10.1016/j.artint.2018.10.001 . ISSN 0004-3702 . S2CID 124836295 .
^ Брамс, Стивен Дж.; Килгур, Д. Марк; Кламлер, Кристиан (2011). «Процедура подрезания: алгоритм разделения неделимых предметов без зависти» (PDF) . Социальный выбор и благосостояние . 39 (2–3): 615. doi : 10.1007/s00355-011-0599-1 . S2CID 253844146 .
^ Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015). «Справедливое распределение неделимых объектов по порядковым предпочтениям». Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . дои : 10.1016/j.artint.2015.06.002 . S2CID 1408197 .
^ Голдберг, Пол В.; Холлендер, Александрос; Игараси, Аюми; Мануранси, Пасин; Суксомпонг, Варут (2020). «Консенсусное сокращение вдвое наборов предметов». В Чене, Сюйджин; Гравин, Николай; Хофер, Мартин; Мехта, Рута (ред.). Экономика Интернета и Интернета . Конспекты лекций по информатике. Том. 12495. Чам: Springer International Publishing. стр. 384–397. arXiv : 2007.06754 . дои : 10.1007/978-3-030-64946-3_27 . ISBN 978-3-030-64946-3 .
^ Гурвес, Лоран (01 апреля 2019 г.). «Согласованные множества с матроидными ограничениями» . Журнал комбинаторной оптимизации . 37 (3): 866–888. дои : 10.1007/s10878-018-0327-1 . ISSN 1573-2886 . S2CID 254654045 .

[1] Суксомпонг, Варут (9 июля 2016 г.). «Назначение небольшого приятного набора неделимых предметов нескольким игрокам» . Материалы двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 489–495. arXiv : 1606.08077 . дои : 10.1016/j.artint.2018.10.001 . ISBN 978-1-57735-770-4 .

[:0-2] Jump up to: ^а ^б ^с ^д ^и ^ж Мануранси, Пасин; Суксомпонг, Варут (01 марта 2019 г.). «Вычисление небольшого приятного набора неделимых элементов» . Искусственный интеллект . 268 : 96–114. arXiv : 1606.08077 . дои : 10.1016/j.artint.2018.10.001 . ISSN 0004-3702 . S2CID 124836295 .

[bkk12-3] Брамс, Стивен Дж.; Килгур, Д. Марк; Кламлер, Кристиан (2011). «Процедура подрезания: алгоритм разделения неделимых предметов без зависти» (PDF) . Социальный выбор и благосостояние . 39 (2–3): 615. doi : 10.1007/s00355-011-0599-1 . S2CID 253844146 .

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

[5] Голдберг, Пол В.; Холлендер, Александрос; Игараси, Аюми; Мануранси, Пасин; Суксомпонг, Варут (2020). «Консенсусное сокращение вдвое наборов предметов». В Чене, Сюйджин; Гравин, Николай; Хофер, Мартин; Мехта, Рута (ред.). Экономика Интернета и Интернета . Конспекты лекций по информатике. Том. 12495. Чам: Springer International Publishing. стр. 384–397. arXiv : 2007.06754 . дои : 10.1007/978-3-030-64946-3_27 . ISBN 978-3-030-64946-3 .

[6] Гурвес, Лоран (01 апреля 2019 г.). «Согласованные множества с матроидными ограничениями» . Журнал комбинаторной оптимизации . 37 (3): 866–888. дои : 10.1007/s10878-018-0327-1 . ISSN 1573-2886 . S2CID 254654045 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]