Максиминимизация долей

Максиминимизация долей (ММД, англ. Maximin share, MMS) — это критерий справедливого распределения объектов. Если дано множество объектов с различными значениями, 1-из-n maximin-доля означает наибольшее значение, которое может быть получено путём разбиения объектов на n частей и выбора части с минимальным значением.

Распределение объектов среди n агентов с различными оценками называется ММД-справедливым, если каждый агент получает набор, который по меньшей мере так же хорош, как его 1-из-n maximin-доля. ММД-справедливость предложил Эрик Будиш^[1] как ослабление критерия пропорциональности — каждый агент получает набор со значением, не меньшим равного распределения (1/n каждого ресурса). Пропорциональность можно гарантировать, если объекты делимы, но не в случае их неделимости, даже если все агенты имеют идентичные оценки. Для контраста ММД-справедливость можно всегда гарантировать для идентичных агентов, так что это естественная альтернатива пропорциональности, если даже агенты различны.

Одинаковые объекты. Предположим для начала, что m одинаковых объектов следует распределить справедливо среди n человек. В идеале каждый человек должен получить m/n объектов, но может оказаться, если m не делится на n, это сделать невозможно, поскольку объекты неделимы. Естественным критерием второго уровня является округление m/n вниз до ближайшего целого и передача каждому лицу по меньшей мере floor(m/n) объектов. Получение менее floor(m/n) объектов будет «слишком несправедливым» — эту несправедливость уже не прикроешь неделимостью объектов.

Различающиеся объекты. Теперь предположим, что объекты различны и каждый из них имеет различную ценность. Теперь округление вниз до ближайшего целого может не дать требуемого решения. Например, предположим, что n=3 и m=5, а ценность объектов выражается значениями 1, 3, 5, 6, 9. Сумма значений равна 24 и это число делится на 3, так что в идеале следовало бы дать каждому участнику предметы, по ценности составляющие по меньшей мере 8, но это невозможно. Наибольшее значение, которое мы можем гарантировать всем агентам, это 7, что получается при распределении {1,6},{3,5},{9}.

Множество {1,6}, на котором достигается значение maximin, называется «1-из-3 maximin- долей» — это лучшее подмножество объектов, которое можно создать путём разбиения исходного множества на 3 части и выборе наименее значимого набора. Поэтому, в этом примере, распределение ММД-справедливо тогда и только тогда, когда значение, которое получает каждый агент, будет не менее 7.

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

• Алиса оценивает объекты в 1,3,5,6,9;
• Джордж оценивает их в 1,7,2,6,8;
• Дайна оценивает их в 1,1,1,4,17.

Теперь каждый агент имеет отличающийся набор ММД:

• ММД Алисы по-прежнему остаётся {1,6}, как и выше;
• ММД Джорджа будет {1,7}, {2,6} или {8} при разбиении {1,7},{2,6},{8} (все эти наборы для него эквивалентны);
• ММД Дайны будет {1,1,1} при разбиении {1,1,1},{4},{17}.

Здесь распределение ММД-справедливо, если оно даёт Алисе значение по меньшей мере 7, Джорджу по меньшей мере 8, а Дайне значение, не меньшее 3. Например, распределение, в котором Джордж получает первые два объекта {1,7}, Алиса получает следующие два {5,6}, а Дайна получает объект {17}, является ММД-справедливым.

Интерпретация. 1-из-n ММД агента можно интерпретировать как максимальная полезность, которую агент может надеяться получить от распределения, если другие агенты имеют те же самые предпочтения, если он всегда получит самую плохую долю. Это минимальная полезность, на которую агент имеет право (по его мнению), основываясь на следующих доводах: если другие агенты будут иметь те же предпочтения, что и я, имеется по меньшей мере одно распределение, которое предоставит мне такую полезность и которое даёт другим агентам не меньше, следовательно, у них нет причин дать мне меньше.

Альтернативная интерпретация: наиболее предпочтительный набор для агента, гарантируемый делящим в протоколе дели-и-выбирай среди соперничающих оппонентов — агент предлагает самое лучшее распределение и оставляет другим правило выбора наборов, а сам забирает оставшийся набор^[2].

ММД-справедливость можно описать также как результат следующего процесса переговоров. Предложено некоторое распределение. Каждый агент может пожаловаться на такое распределение и предложить своё. Однако, сделав это, он должен позволить остальным забрать свои доли, а сам забирает оставшийся набор. Следовательно, агент будет жаловаться на распределение только в случае, когда может предложить распределение, в котором все наборы лучше, чем в текущем. Распределение ММД-справедливо тогда и только тогда, когда ни один из агентов не жалуется на него, то есть для любого агента в любом распределении существует набор, который не лучше, чем доля, которую он получит в текущем распределении.

Если все n агентов имеют идентичные оценки, ММД-справедливое распределение всегда существует по определению.

Если только n-1 агентов имеют идентичные оценки, ММД-справедливое распределение всё ещё существует и может быть найдено с помощью протокола дели-и-выбирай — n-1 идентичных агентов разбивают объекты на n наборов, каждый из которых не хуже, чем ММД, затем n-ый агент выбирает набор с наивысшей оценкой, а идентичные агенты разбирают оставшиеся n-1 наборов.

В частности, при двух агентах ММД-справедливое распределение существует всегда.

Бувре и Леметр^[2] осуществили интенсивное моделирование на случайных данных для более чем 2 агентов и обнаружили, что ММД-справедливые распределения существовали в каждой попытке. Они доказали, что ММД-справедливые распределения существуют в следующих случаях:

• Двоичные оценки — агенту либо нравится объект (значение равно 1), либо не нравится (значение равно 0).
• Идентичные мультимножества — агенты могут оценивать объекты по-разному, но мультимножества оценок агентов те же самые.
• Мало объектов — ${\displaystyle m\leqslant n+3}$.

Прокачча и Вон^[3], а также Курокава^[4], построили пример с n=3 агентами и m=12 объектами, в котором распределение гарантирует каждому агенту 1-из-3 ММД. Более того, они показали, что для любого ${\displaystyle n\geqslant 3}$ существует пример с ${\displaystyle 3n+4}$ объектами.

Для случая несуществования ММД распределений Прокачча и Вон предложили мультипликативную аппроксимацию для ММД — распределение называется r-долевым ММД для некоторой дроби r из [0,1], если значение любого агента не меньше доли r значения его/её ММД.

Они представили алгоритм, который всегда находит ${\displaystyle r_{n}}$-долевое ММД, где ${\displaystyle r_{n}:={\tfrac {2\cdot {\text{oddfloor}}(n)}{3\cdot {\text{oddfloor}}(n)-1}}}$, а oddfloor(n) является наибольшим нечётным целым, не превосходящим n. В частности, ${\displaystyle r_{3}=r_{4}={\tfrac {3}{4}}}$, оно уменьшается при увеличении n и всегда больше ${\displaystyle {\tfrac {2}{3}}}$. Их алгоритм работает за полиномиальное время от m, если n постоянно.

Аманатидис, Маркакис, Никзад и Сабери^[5] доказали, что в случайно сгенерированных задачах ММД-справедливые распределения существуют с высокой вероятностью. Они предложили несколько улучшенных алгоритмов

• Простой и быстрый 1/2-долевой ММД алгоритм;
• 2/3-долевой ММД алгоритм, работающий за полиномиальное время как по m, так и по n;
• 7/8-долевой ММД алгоритм для 3 агентов;
• ММД-справедливый алгоритм для случая тернарных оценок — когда значение равно одному из трёх чисел — 0, 1 или 2.

Барман и Кришнамурти^[6] представили

• Простой и эффективный алгоритм для 2/3-долевого ММД с аддитивнымы оценками^[англ.], основанный на процедуре циклов зависти.
• Простой алгоритм для 1/10-долевого ММД для более сложного случая субмодулярных функций множеств^[англ.], основанный на распределении объектов по кругу (Round-robin).

Годси, Хаджигойи, Седигин и Ями^[7] предложили

• Для аддитивных оценок: алгоритм полиномиального времени для 3/4-долевого ММД.
• Для n=4 аддитивных агентов: алгоритм для 4/5-долевого ММД.
• Для субмодулярных оценок: алгоритм полиномиального времени для 1/3-долевого ММД и верхнюю оценку для 3/4-долевого ММД.
• Для оценок с дробной субаддитивностью^[англ.]: алгоритм полиномиального времени для 1/8-долевого ММД, доказательство существования 1/5-долевого ММД и верхнюю границу для 1/2-долевого ММД.
• Для полуаддитивных оценок: доказательство существования log(m)/10-долевого ММД и верхнюю оценку 1/2-долевого ММД.

Гарг, Макглафлин и Таки^[8] предложили простой алгоритм для 2/3-долевого ММД, анализ которого прост.

В настоящее время неизвестно, каково наибольшее значение r, при котором r-долевое ММД распределение всегда существует. Это может быть число между 3/4 и 1 (не включая 1).

Аманатидис, Бёрмпас и Маркакис^[9] предложили неуязвимые стратегии^[англ.] для приближённых ММД-справедливых распределений (см. также Стратегически справедливый делёж^[англ.]):

• Для n агентов: 1/O(m)-долевое ММД.
• Для 2 агентов: 1/2-долевое ММД и доказательство, что никакой неуязвимый механизм не даст более 1/2.

Синь и Пиньян^[10] изучали ММД-справедливое распределение обязанностей (объектов с отрицательными оценками) и показали, что 9/11-долевое ММД распределение всегда существует.

Будиш^[1] предложил другую аппроксимацию 1-из-n ММД распределения — 1-из-(${\displaystyle n+1}$) ММД (каждый агент получает по меньшей мере столько, сколько он мог бы получить путём разбиения на n+1 наборов и выбор худшего из них). Он показал, что приблизительное конкурентное равновесие при равных доходах^[англ.] всегда гарантирует 1-из-(${\displaystyle n+1}$) ММД. Однако это распределение может превысить имеющееся число объектов, и, что более важно, превысить потребности — сумма наборов, распределённых всем агентам, может быть слегка больше суммы всех объектов. Такая ошибка допустима при распределении мест для студентов курса, поскольку малая нехватка может быть скорректирована путём добавления небольшого числа стульев. Но классическая задача справедливого дележа предполагает, что предметы не могут быть добавлены.

Для любого числа агентов с аддитивными оценками любое cвободное от зависти справедливое распределение при исключением одного (БЗ1, англ. envy-free-except-1, EF1) даёт каждому агенту по меньшей мере 1-из-(2n-1) ММД^[11]. БЗ1 распределение может быть найдено, например, с помощью циклического распределения объектов или процедуры циклов зависти.

Более того, 1-из-(2n-2) ММД распределение можно найти с помощью паросочетания без зависти^[12].

На сегодня не известно, каково минимальное N, при котором 1-из-N ММД распределение всегда существует. Оно может быть любым числом между n+1 и 2n-2. Наименьшее значение n, при котором уже не известно такое N, равно 4.

Исходное условие ММД может быть использовано для несимметричных агентов (агентов с различными полагающимися им долями)^[13].

Некоторые базовые алгоритмы, связанные с ММД:

• Вычисление ММД данного агента. Эта задача NP-трудна даже для агентов с аддитивными оценками — она может быть сведена из задачи разбиения множества чисел. Вогингер^[14] разработал алгоритм со сложностью PTAS для этой задачи.
• Задача выявления, является ли данное распределение 1-из-${\displaystyle n}$ ММД, co-NP полна для агентов с аддитивными оценками.
• Выявление, позволяет ли данная задача какое-либо ММД-распределение, принадлежит классу ${\displaystyle NP^{NP}}$, то есть задача может быть решена за недетерминированно полиномиальное время с помощью оракла для NP задачи (предсказатель нужен для вычисления ММД-агента). Однако точная вычислительная сложность этой задачи неизвестна — она может иметь уровень 2, 1 или даже 0 полиномиальной иерархии^{[2] [15]}.

Распределение называется попарно справедливым с максиминимизацией долей (ПММД-справедливым, англ. pairwise-maximin-share-fair, PMMS-fair), если для любой пары агентов i и j, агент i получает по меньшей мере его 1-из-2 maximin-долю, ограниченную объектами, из общего множества объектов i и j^[16].

Распределение называется групповым справедливым с максиминимизацией долей (ГММД-справедливость, англ. groupwise-maximin-share-fair, GMMS-fair), если для любой подгруппы агентов размера k каждый участник подгруппы получают его/её 1-из-k maximin-долю, ограниченную объектами, полученными этой подгруппой^[17].

С аддитивными оценками различные понятия справедливости связаны следующим образом

• Из справедливости с отсутствием зависти вытекает ГММД-справедливость, ^[17];
• Из ГММД-справедливости следует ММД-справедливость (если взять группу размера n) и ПММД-справедливость (если взять размер групп 2);
• Из ПММД-справедливости следует 1/2- ГММД-справедливость^[16];
• Из ПММД-справедливости следует БЗX^[18], из которого следует БЗ1.
• Из ММД-справедливости не следует ПММД-справедливости, то же и для ПММД=>ММД.

ГММД-распределения гарантированно существуют, когда оценки агентов либо бинарны, либо идентичны. С аддитивными оценками общего вида 1/2-ГММД-распределения существуют и могут быть найдены за полиномиальное время^[17].

• Завистливое распределение объектов