Русская Википедия:Максиминимизация долей

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Распределение объектов среди n агентов с различными оценками называется ММД-справедливым, если каждый агент получает набор, который по меньшей мере так же хорош, как его 1-из-n maximin-доля. ММД-справедливость предложил Эрик БудишШаблон:Sfn как ослабление критерия пропорциональности — каждый агент получает набор со значением, не меньшим равного распределения (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 ММД агента можно интерпретировать как максимальная полезность, которую агент может надеяться получить от распределения, если другие агенты имеют те же самые предпочтения, если он всегда получит самую плохую долю. Это минимальная полезность, на которую агент имеет право (по его мнению), основываясь на следующих доводах: если другие агенты будут иметь те же предпочтения, что и я, имеется по меньшей мере одно распределение, которое предоставит мне такую полезность и которое даёт другим агентам не меньше, следовательно, у них нет причин дать мне меньше.

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

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

Существование ММД-справедливых распределений

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

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

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

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

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

Прокачча и ВонШаблон:Sfn, а также КурокаваШаблон:R, построили пример с n=3 агентами и m=12 объектами, в котором распределение гарантирует каждому агенту 1-из-3 ММД. Более того, они показали, что для любого <math>n \geqslant 3</math> существует пример с <math>3n+4</math> объектами.

Мультипликативная аппроксимация

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

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

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

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

Барман и КришнамуртиШаблон:Sfn представили

Годси, Хаджигойи, Седигин и ЯмиШаблон:Sfn предложили

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

Гарг, Макглафлин и ТакиШаблон:Sfn предложили простой алгоритм для 2/3-долевого ММД, анализ которого прост.

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

Аманатидис, Бёрмпас и МаркакисШаблон:Sfn предложили Шаблон:Не переведено 5 для приближённых ММД-справедливых распределений (см. также Шаблон:Не переведено 5):

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

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

Ординальная аппроксимация

БудишШаблон:Sfn предложил другую аппроксимацию 1-из-n ММД распределения — 1-из-(<math>n+1</math>) ММД (каждый агент получает по меньшей мере столько, сколько он мог бы получить путём разбиения на n+1 наборов и выбор худшего из них). Он показал, что Шаблон:Не переведено 5 всегда гарантирует 1-из-(<math>n+1</math>) ММД. Однако это распределение может превысить имеющееся число объектов, и, что более важно, превысить потребности — сумма наборов, распределённых всем агентам, может быть слегка больше суммы всех объектов. Такая ошибка допустима при распределении мест для студентов курса, поскольку малая нехватка может быть скорректирована путём добавления небольшого числа стульев. Но классическая задача справедливого дележа предполагает, что предметы не могут быть добавлены.

Для любого числа агентов с аддитивными оценками любое cвободное от зависти справедливое распределение при исключением одного (БЗ1, Шаблон:Lang-en, EF1) даёт каждому агенту по меньшей мере 1-из-(2n-1) ММДШаблон:Sfn. БЗ1 распределение может быть найдено, например, с помощью циклического распределения объектов или процедуры циклов зависти.

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

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

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

Другие алгоритмические задачи

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

  • Вычисление ММД данного агента. Эта задача NP-трудна даже для агентов с аддитивными оценками — она может быть сведена из задачи разбиения множества чисел. ВогингерШаблон:Sfn разработал алгоритм со сложностью PTAS для этой задачи.
  • Задача выявления, является ли данное распределение 1-из-<math>n</math> ММД, co-NP полна для агентов с аддитивными оценками.
  • Выявление, позволяет ли данная задача какое-либо ММД-распределение, принадлежит классу <math>NP^{NP}</math>, то есть задача может быть решена за недетерминированно полиномиальное время с помощью оракла для NP задачи (предсказатель нужен для вычисления ММД-агента). Однако точная вычислительная сложность этой задачи неизвестна — она может иметь уровень 2, 1 или даже 0 полиномиальной иерархииШаблон:Sfn Шаблон:Sfn.

ММД-справедливость для групп

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

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

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

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ БЗX = Отсутствие зависти до наименее ценного объекта (Шаблон:Lang-en). См. статью Caragiannis, Kurokawa и др.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Максиминимизация_долей&oldid=10318694