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

Согласованное подмножество — это подмножество элементов, которое, по мнению всех людей в определенной группе, по крайней мере так же хорошо, как и его дополнение. Поиск небольшого согласованного подмножества — это проблема вычислительного социального выбора . ^{[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]}

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

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

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

(это потому, что S\ V ₁ содержит V ₂ , а S\ V ₂ содержит V ₁ , и предпочтения монотонны).

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

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

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

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

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

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

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

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

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

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

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