Максимальная доля

Максимальная доля (MMS) является критерием справедливого распределения предметов . Учитывая набор элементов с разными значениями, доля максимина 1 из n - это максимальное значение, которое можно получить, разделив элементы на n частей и выбрав часть с минимальным значением.

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

Мотивация и примеры [ править ]

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

Разные предметы. Предположим теперь, что предметы разные, и у каждого предмета своя ценность. Например, предположим, что n = 3 и m = 5, а значения элементов равны 1, 3, 5, 6, 9, в сумме получается 24. Если бы элементы были делимыми, мы дали бы каждому человеку значение 24/3 = 8 (или, если они делятся только на целые числа, как в предыдущем абзаце, по крайней мере, floor (24/3) = 8), но это невозможно. Наибольшее значение, которое может быть гарантировано всем трем агентам, равно 7 по разделу {1,6}, {3,5}, {9}. Неформально 7 - это общее значение, деленное на n, «округленное в меньшую сторону до ближайшего элемента».

Множество {1,6}, достигающее этого максимального значения, называется «максимин-доля 1 из 3» - это лучшее подмножество элементов, которое можно построить, разделив исходный набор на 3 части и взяв наименьшее ценная часть. Следовательно, в этом примере распределение является справедливым для MMS, если оно дает каждому агенту значение не менее 7.

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

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

Теперь у каждого агента разные MMS:

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

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

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

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

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

Наличие выставок MMS-ярмарок [ править ]

Когда все n агентов имеют одинаковые оценки, справедливое распределение MMS всегда существует по определению.

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

В частности, с двумя агентами всегда существует справедливое распределение MMS.

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

Двоичные оценки - каждый агент либо любит элемент (оценивает его на 1), либо не любит (оценивает его на 0).
Идентичные мультимножества - агенты могут оценивать элементы по-разному, но мультимножества значений агентов одинаковы.
Немногое - m ≤ n +3.

Прокачча и Ван ^[3] и Курокава ^[4] построили экземпляр с n = 3 агентами и m = 12 элементами, в котором никакое распределение не гарантирует каждому агенту MMS 1 из 3. В их случае есть 12 объектов, индексированных кнопками и . Каждый агент оценивает каждый объект по: ${\ Displaystyle я \ в [3]}$ ${\ displaystyle j \ in [4]}$ ${\ displaystyle k}$ ${\ displaystyle (я, j)}$

${\ displaystyle v_ {k} (i, j) = 1 000 000 + 1 000 \ cdot T_ {i, j} + E_ {i, j} ^ {(k)}}$

где - конкретные матрицы 3 на 4 со значениями меньше 100. Они доказывают, что каждый агент может разбить объекты на 3 подмножества по 4 объекта в каждом, так что сумма значений в каждом подмножестве составляет 4 055 000, что, следовательно, является MMS для все агенты. Они доказывают, что каждое выделение MMS должно давать каждому агенту ровно 4 конкретных объекта, но такого распределения не существует. ${\ displaystyle T, E ^ {(1)}, E ^ {(2)}, E ^ {(3)}}$

Они обобщили этот пример и показали, что для каждого n ≥ 3 существует такой экземпляр с 3 n +4 элементами.

Мультипликативное приближение [ править ]

Следуя результату отсутствия распределения для MMS, Прокачча и Ван ввели мультипликативное приближение для MMS: распределение представляет собой r-дробную часть MMS для некоторой доли r в [0,1], если значение каждого агента составляет по крайней мере долю r от стоимость его / ее MMS.

Они представили алгоритм, который всегда находит r _n -фракцию MMS, где

$r_{n}:={\frac {2\cdot {\text{oddfloor}}(n)}{3\cdot {\text{oddfloor}}(n)-1}}={\begin{cases}{\frac {2n}{3n-1}}&n~{\text{ odd}}\\{\frac {2n-2}{3n-4}}&n~{\text{ even}}\end{cases}}$

где oddfloor ( n ) - наибольшее нечетное целое число, меньшее или равное n . В частности, r ₃ = r ₄ = 3/4, оно уменьшается с увеличением n и всегда больше 2/3. Их алгоритм работает с полиномом времени от m , когда n является постоянным.

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

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

Азиз, Раучекер, Шрайен и Уолш ^[6] представили:

Доказательство того, что выделение MMS может не существовать для работы по дому (предметы с отрицательной полезностью).
Двухчастный алгоритм MMS для работы по дому (при отрицательных значениях полезности коэффициент аппроксимации больше 1).
Алгоритмы поиска оптимального приближения MMS для данного экземпляра, основанные на алгоритмах многостороннего разделения номеров .

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

Простой и эффективный алгоритм для 2/3-дробных MMS с аддитивными оценками . Их алгоритм основан на «упорядочивании» экземпляров (т. Е. Сокращении экземпляра до такого, в котором все агенты согласовывают ранжирование товаров), а затем запуске процедуры графа зависти, начиная с наиболее ценного товара. Они доказывают, что результат EFX и гарантирует каждому агенту его MMS, что составляет не менее 2/3. ${\frac {2n}{3n-1}}$
Похожий алгоритм для дел по дому набирает 4/3 дробных MMS по хозяйству (точнее, ). ${\frac {4n-1}{3n}}$
Простой алгоритм для MMS с долей 1/10 для более сложного случая субмодульных оценок - на основе циклического распределения элементов .

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

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

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

Гарг и Таки ^[10] представили простой алгоритм для 3/4-дробного MMS, которому не нужно знать значение MMS, и поэтому он работает за строго полиномиальное время. Они также доказывают существование -фракции MMS. $({\frac {3}{4}}+{\frac {1}{12n}})$

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

Аманатидис, Бирмпас и Маркакис ^[11] представили правдивые механизмы для приблизительного распределения MMS-ярмарок (см. Также Стратегическое разделение ярмарок ):

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

Хуанг и Лу ^[12] доказывают, что распределение MMS для работы по дому составляет 11/9.

Порядковое приближение [ править ]

Будиш ^[1] представил другое приближение к MMS 1 из n - MMS 1 из ( $n+1$ ) (каждый агент получает по крайней мере столько, сколько он может получить, разбивая на n +1 пакетов и получая худший из них) . Он показал, что приблизительное конкурентное равновесие на основе равных доходов всегда гарантирует 1-из- ( $n+1$ ) MMS. Однако это распределение может иметь избыточное предложение и, что более важно, избыточный спрос: сумма пакетов, выделенных всем агентам, может быть немного больше, чем набор всех элементов. Такая ошибка оправдана при распределении мест на курсах между студентами, поскольку небольшой избыток предложения можно исправить, добавив небольшое количество мест. Но классическая задача справедливого деления предполагает, что предметы не могут быть добавлены.

Без избыточного спроса и предложения известны следующие приближения:

Распределение MMS 1 из (2 n -2) с использованием сопоставления без зависти . ^[13]
Распределение MMS 1 из (3 n / 2) с использованием другого алгоритма. ^[14]^{: sub.4.6, cor.2} Он может быть вычислен за разное время, когда n <6.

На сегодняшний день неизвестно, какое наименьшее N такое, чтобы всегда существовало выделение MMS « 1 из N» . Это может быть любое число от n +1 до 3 n / 2. Наименьший открытый случай - n = 4.

Условие порядкового номера MMS также может применяться к асимметричным агентам (агентам с разными правами). ^[15]

Методы и алгоритмы [ править ]

К исходной проблеме можно применить различные нормализации, не меняя решения. Ниже O - это набор всех объектов.

Масштабирование [ править ]

Если для каждого агента i все оценки масштабируются с коэффициентом k _i (который может быть разным для разных агентов), то MMS для каждого агента масштабируется с одинаковым коэффициентом; следовательно, каждое выделение MMS в исходном экземпляре является выделением MMS в масштабированном экземпляре. Обычно оценки масштабируются таким образом, что MMS агента каждого агента равняется ровно 1. После этого масштабирования проблемы приближения MMS могут быть сформулированы как:

r-доля MMS : общее значение O не менее n ; нам нужно дать каждому из n агентов связку стоимостью не менее r .
MMS «1 из N» : общее значение O не менее N ; нам нужно дать каждому из n агентов комплект стоимостью не менее 1.

Вышеупомянутое масштабирование требует вычисления MMS каждого агента, что является NP-трудной задачей ( многостороннее разделение номеров ). Альтернативное масштабирование, которое можно сделать быстрее, это: ^[9]

r-дробь MMS : общее значение O равно n ; MMS - не более 1; нам нужно дать каждому из n агентов связку стоимостью не менее r .
MMS 1 из N : общее значение O равно N ; MMS - не более 1; нам нужно дать каждому из n агентов комплект стоимостью не менее 1.

Выделение одного объекта [ править ]

Если удалить один объект O от O . Тогда для каждого агента, в 1-из-of ( п -1) MMS - WRT оставшегося множества O \ O есть по крайней мере , его 1-внеконкурсных п MMS WRT исходного множества O . Это связано с тем, что в исходном разделе MMS n -1 частей остаются нетронутыми. ^[2] Теперь предположим, что мы хотим дать каждому агенту значение r . Если какой-то объект o ₁ стоит как минимум r хотя бы для одного агента, то мы можем дать o ₁одному такому агенту произвольно и приступить к распределению оставшихся объектов между оставшимися агентами. Следовательно, мы можем предположить, что wlog:

r-дробь MMS : значение каждого объекта для всех агентов меньше r .
MMS 1 из N : значение каждого объекта для всех агентов меньше 1.

Эта нормализация работает даже с быстрым масштабированием и с произвольными монотонными оценками (даже неаддитивными). ^[8]

Наполнение мешков [ править ]

Обозначим объект, который не более s оценивается всеми агентами, как « s -маленький объект». Предположим, что все объекты s -маленькие. Возьмите пустой мешок и наполняйте его предметом за предметом, пока мешок не будет стоить как минимум r хотя бы одному агенту. Затем произвольно передайте сумку одному из таких агентов. Поскольку все объекты s -маленькие, остальные агенты оценивают сумку не более r + s ; если это значение достаточно мало, то оставшееся значение достаточно велико, чтобы мы могли действовать рекурсивно. ^[9] В частности, наполнение мешков дает следующие решения:

1/2 фракции MMS : принять s = r = 1/2; обратите внимание, что с помощью предыдущей нормализации мы можем предположить, что все объекты имеют размер 1/2. Изначально имеется n агентов, и их общая ценность не менее n . После того, как мешок выделен, оставшиеся n -1 агентов оценивают оставшиеся объекты как минимум n - ( r + s ) = n -1, поэтому мы можем действовать рекурсивно. ^[8]
1-из- (2n) MMS : принять s = r = 1; обратите внимание, что с помощью предыдущей нормализации мы можем считать, что все объекты 1-маленькие. Изначально имеется n агентов, и их общая стоимость не менее 2 n . После того, как мешок выделен, оставшиеся n -1 агентов оценивают оставшиеся объекты как минимум 2 n - ( r + s ) = 2n -2 = 2 ( n -1), поэтому мы можем действовать рекурсивно.

Эти алгоритмы заполнения пакетов работают даже с быстрым масштабированием, поэтому они работают за полиномиальное время - им не нужно знать точное значение MMS. ^[9] Фактически, оба алгоритма можно сформулировать без упоминания MMS:

Каждый агент, для которого каждый объект стоит не более 1 / (2 n ) от общей стоимости, получает не менее 1 / (2 n ) от общей стоимости.

Модифицированное наполнение мешка : условие, что все объекты s- маленькие, можно смягчить следующим образом. ^[9] Возьмите s < r . Обозначим объект, который не является s -маленьким (т. Е. Оценивается по крайней мере s по крайней мере одним агентом) как « s -большой объект». Предположим, что не более n объектов s -большие. Возьмите один s- большой объект o ₁ , положите его в сумку и наполните его s-маленькими объектами, пока один агент не укажет, что он стоит как минимум r . Должен быть хотя бы один такой агент, так как некоторый агент i имеет значение o₁ при некотором x > s . Для этого агента остается не более n -1 s -больших объектов. Согласно предыдущей нормализации, эти объекты все еще r -маленькие, поэтому их общее значение для i не превышает r (n -1) , поэтому значение оставшихся s -малых объектов составляет не менее nr (n -1) - x = г ( п -1) + rx ≥ rx.

Заказ [ править ]

экземпляр будет приказано , если все агенты имеют один и тот же порядковый номер рейтинга на объекты, т.е. объекты могут быть пронумерованы O ₁ , ..., о _т таким образом, что, для каждого агента я , v _я ( O ₁ ) ≥ ... ≥ v _i ( о _м ). Интуитивно понятно, что упорядоченные экземпляры сложнее всего, поскольку конфликт между агентами является самым большим. Действительно, отрицательный экземпляр ^[3] упорядочен - порядок объектов определяется матрицей , которая одинакова для всех агентов. Это тоже можно доказать формально. Предположим, у нас есть алгоритм, который для каждого заказанного экземпляра находит $T$ r -доля распределения MMS. Теперь нам дан общий экземпляр P для распределения элементов . Решаем это следующим образом. ^[2]^[7]

Создайте упорядоченный экземпляр ord (P) следующим образом: для каждого агента i определите v _i ( o _j ) в ord ( P ) как j-е наивысшее значение в наборе значений агента i в P. Это требует O ( нм log ( м )) время.
Находят г группы фракций MMS распределения Ord ( A) в Ord ( Р ).
Постройте последовательность выбора, в которой агент, получивший o ₁ в ord (A), выбирает первым, агент, получивший o ₂ в ord (A), выбирает вторым и т. Д.
Позвольте агентам выбрать свои лучшие предметы в соответствии с последовательностью выбора. Пусть A будет полученным распределением. В A каждый агент получает точно такое же количество элементов, что и в ord ( A ). Кроме того, каждый агент , который получил о _J в Ord ( ), принимает один из его главных J элементов в A . Следовательно, его ценность для каждого предмета, который он получил в A , по крайней мере, равна его ценности для соответствующего предмета в ord ( A ). Следовательно, ценность каждого агента в A не меньше, чем в ord ( A ). Поскольку порядок не изменяет значения MMS, новое распределение Aпо-прежнему остается r -доля MMS.

Поэтому при поиске распределения MMS с r- долей мы можем предположить, что wlog:

Порядковый рейтинг объектов одинаков для всех агентов.

Размещение двух объектов [ править ]

Предположим, мы нашли два объекта o ₁ и o ₂ , у которых один агент i имеет значение не менее r , а другие агенты - не более 1. Затем эти два объекта могут быть назначены для i . Для других агентов, в 1-вне-of ( п -1) MMS - WRT оставшегося набора, по крайней мере его 1-внеконкурсных п MMS WRT исходного множества O . Это связано с тем, что в исходном разделе MMS по крайней мере n -2 частей остаются нетронутыми, в то время как две части, которые не являются неповрежденными, могут быть объединены в одну часть со значением не менее 1. Эта нормализация работает только с аддитивными оценками. . ^[8]^{: Лем.3.2}

Кроме того, предположим , что экземпляр упорядочен, и предположим , что мы удалить из O двух объектов о _п , о _п_{+ 1} (то есть, п -го и ( п + 1) -го высшего ценных предметов). Тогда для каждого агента, в 1-из-of ( п -1) MMS - WRT оставшегося набора, по крайней мере его 1-внеконкурсных п MMS WRT исходного множества O . Это связано с тем, что по принципу «ячеек», по крайней мере, одна часть MMS каждого агента должна содержать два или более объекта из набора { o ₁ , ..., o _n₊₁ }. Эти предметы могут использоваться для замены переданных предметов, что приводит кп -1 части со значением по крайней мере , 1. Это означает , что, если объекты O _н , О _п₊₁ имеет значение , по меньшей мере, MMS для некоторого агента я , мы можем дать им I и приступить к выделить оставшиеся объекты оставшимся агентам. Следовательно, мы можем предположить, что wlog:

r-дробь MMS : общее значение o _n , o _n₊₁ для всех агентов меньше r . В частности, значение o _n₊₁ и всех объектов после него в упорядочении меньше r / 2.
MMS 1 из N : общее значение o _N , o _N₊₁ для всех агентов меньше 1. В частности, значение o _N₊₁ и всех объектов после него в упорядочении меньше 1/2. .

Эта нормализация работает даже при быстром масштабировании. Сочетание этого с модифицированным наполнением мешков приводит к следующему простому алгоритму для 2/3-фракционного MMS. ^[9]

Если один объект стоит как минимум 2/3 для некоторого агента, выделите его.
Закажите экземпляр.
Пока О _п , о _п₊₁ стоит , по крайней мере 2/3 в какой - то агент, выделить их.
Наконец, имеется не более n объектов со значением не менее 1/3; распределить их с помощью модифицированного наполнения пакетов.

О гарантии этого алгоритма можно сказать и без упоминания MMS:

Каждый агент, для которого o ₁ стоит не более 2 / (3 n ) от общей стоимости и o _n + o _{n + 1} вместе составляет не более 2 / (3 n ) от общей стоимости, получает не менее 2 / (3 п ) от общей стоимости.

Алгоритмические проблемы [ править ]

Несколько основных алгоритмов, связанных с MMS:

Вычислительный ли 1-of п MMS данного агента составляет по меньшей мере некоторое целое число К . Он находится в NP, поскольку может быть подтвержден за полиномиальное время при любом распределении с минимальным значением не менее K ; это NP-сложно по редукции из проблемы разбиения . Следовательно, он является NP-полным для любого n ≥ 2. ^[2] Следовательно, вычисление MMS данного агента является NP-трудным . Woeginger ^[16] разработал для этого PTAS .
Решение о том, является ли данное распределение справедливым для MMS, является co-NP полным для агентов с аддитивными оценками (оно находится в co-NP, поскольку можно доказать за полиномиальное время, что данное распределение не является справедливым для MMS, учитывая разделение MMS. одного из агентов, что показывает, что значение MMS агента больше, чем его значение в распределении). ^[17]
Решение о том, допускает ли данный экземпляр какое-либо распределение MMS, учитывая значения MMS всех агентов. Он находится в NP, поскольку может быть проверен за полиномиальное время с учетом распределения; его точная сложность выполнения неизвестна. Следовательно, решение о том, допускает ли данный экземпляр какое-либо выделение MMS, находится в состоянии , т. Е. Оно может быть решено за недетерминированно-полиномиальное время с использованием оракула для задачи NP (оракул необходим для вычисления MMS агента). Однако точная вычислительная сложность этой задачи до сих пор неизвестна: это может быть уровень 2, 1 или даже 0 полиномиальной иерархии . ^[2] $NP^{NP}$
Проблема решения проверки наличия минимаксного распределения долей является NP-трудной. Обе проблемы могут быть аппроксимированы PTAS , предполагая, что количество агентов фиксировано. Когда оценки агентов являются бинарными или аддитивными и основаны на оценке Борда , распределение максимальных долей всегда может быть эффективно найдено. Когда их оценки неаддитивны, бывают случаи, когда распределение MMS r- доли не существует ни для какого положительного r . Однако для класса симметричных субмодульных утилит существует жесткое распределение MMS, составляющее 1/2 доли, и оно может быть аппроксимировано с точностью до 1/4. ^[18]

Справедливость MMS для групп [ править ]

Распределение называется парной-ярмаркой-максимином (PMMS-ярмаркой), если для каждых двух агентов i и j агент i получает по крайней мере свою максимальную долю 1 из 2, ограниченную элементами, полученными i и j . Неизвестно, всегда ли существует распределение PMMS, но всегда существует приближение 0,618. ^[19]

Распределение называется групповой-ярмаркой-максимином-долей (GMMS-ярмаркой), если для каждой подгруппы агентов размера k каждый член подгруппы получает свою 1-из- k максимальную долю, ограниченную элементами. полученные этой подгруппой. ^[20]

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

Свобода от зависти предполагает GMMS-справедливость; ^[20]
Справедливость GMMS подразумевает справедливость MMS (за счет подгруппы размера n ) и справедливость PMMS (за счет подгруппы размера 2);
Справедливость PMMS подразумевает справедливость 2/3-MMS для трех агентов и справедливость 4/7-MMS в целом; ^[21]
PMMS-справедливость подразумевает EFX, что подразумевает EF1.
EF1 подразумевает 1/2-PMMS, а EFX подразумевает 2/3-PMMS. ^[21]^{: Prop.3.7–3.8} Следовательно, распределение 1/2 PMMS может быть найдено за полиномиальное время.
Справедливость MMS и Справедливость PMMS не подразумевают друг друга.

Распределение GMMS гарантированно существует, когда оценки агентов либо бинарны, либо идентичны. При общих аддитивных оценках существуют распределения 1/2-GMMS, которые могут быть найдены за полиномиальное время. ^[20]

Отношение к другим критериям справедливости [ править ]

Распределение называется envy-free-except-c-items (EF c ) для агента i, если для каждого другого агента j существует набор не более c элементов, которые, если они удалены из пакета j , то i остальным не завидует. Распределение EF0 просто называется свободным от зависти . Распределение EF1 может быть найдено, например, с помощью циклического распределения элементов или с помощью процедуры envy-graph .

Распределение называется пропорциональным-за исключением-c-элементов (PROP * c ) для агента i, если существует набор не более c элементов вне пакета i , который, если он удален из набора всех элементов, тогда i оценивает его связать не менее 1 / н остатка. Распределение PROP * 0 просто называется пропорциональным .

EF0 подразумевает PROP * 0, а EF1 подразумевает PROP * ( n -1). Более того, для любого целого c 0 из EF c следует PROP * (( n -1) c ). ^[22]^{: Лемика.2.3} Противоположная импликация верна при n = 2, но не при n > 2.

Следующие аппроксимации максимальной доли подразумеваются из PROP * ( n -1), а значит, и из EF1: ^[22]^{: Лем.2.7}

Мультипликативное приближение: 1 / п группы фракций MMS (1 / п плотно); ^[21]^{: Предложение 3.6}
Порядковое приближение: 1-из- (2 n -1) MMS (2 n -1 - точное значение). Точно так же для каждого целого числа c PROP * c подразумевает 1-из- ( c + n ) MMS.
MMS, когда функция значения является двоичной. Верно и обратное утверждение.

Вышеупомянутые последствия проиллюстрированы ниже:

Без зависти	→	Пропорциональный	→	Максимин-доля
↓		↓		↓
↓		↓	→	1 / n -фракция MMS
EF1	→	ПРОП * ( n -1)	↔	MMS для двоичной оценки
↓		↓	→	1 из - (2 n -1) MMS
↓		↓		↓
EF c	→	ПРОП * (( n -1) c )	→	1 из - (( n -1) c + n ) MMS

Распределение называется свободным от зависти, кроме любого элемента (EF x ) для агента i, если для любого другого агента j для любого отдельного элемента, удаленного из пакета j , i не завидует остатку. EFx строго сильнее, чем EF1. Это подразумевает следующие приближения MMS: ^[21]^{: Prop.3.3–3.4}

2/3-фракционный MMS на 2 или 3 агента (герметично);
4/7-фракционный MMS для любого количества агентов (не известно, является ли он жестким; верхняя граница - 8/13).

См. Также [ править ]

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

Ссылки [ править ]

^ a b Budish, Эрик (2011). «Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов». Журнал политической экономии . 119 (6): 1061–1103. DOI : 10.1086 / 664613 . S2CID 154703357 .
^ a b c d e f Бувере, Сильвен; Лемэтр, Мишель (2015). «Характеристика конфликтов при справедливом разделении неделимых товаров по шкале критериев». Автономные агенты и мультиагентные системы . 30 (2): 259. DOI : 10.1007 / s10458-015-9287-3 . S2CID 16041218 .
^ a b Procaccia AD, Ван Дж (2014). Достаточно справедливо: гарантия примерных максимальных акций . EC '14 Труды пятнадцатой конференции ACM по экономике и вычислениям . С. 675–692. DOI : 10.1145 / 2600057.2602835 . ISBN 9781450325653 .
^ http://procaccia.info/papers/mms.jacm.pdf
^ Аманатидис, Георгиос; Маркакис, Евангелос; Никзад, Афшин; Сабери, Амин (2017-12-04). «Алгоритмы приближения для расчета максимальных распределений долей». ACM-транзакции по алгоритмам . 13 (4): 1-28. arXiv : 1503.00941 . DOI : 10.1145 / 3147173 . S2CID 13366555 .
^ Азиз, Харис; Раучекер, Герхард; Шрайен, Гвидо; Уолш, Тоби (2016-04-05). «Алгоритмы аппроксимации для максимального и минимального распределения долей в неделимых работах и товарах». arXiv : 1604.01435 [ cs.GT ].
^ a b Бармен, Сиддхартх; Кришнамурти, Санат Кумар (2017-03-06). «Алгоритмы аппроксимации для максимального деления справедливости». arXiv : 1703.01851 [ cs.GT ].
^ a b c d Годси, Мохаммад; Хаджиагайи, Мохаммад Таги; Седдигин, Масуд; Седдигин, Саид; Ями, Хади (2017-04-01). «Справедливое распределение неделимых благ: улучшение и обобщение». arXiv : 1704.00222 [ cs.GT ].
^ a b c d e f Гарг, Джугал; МакГлафлин, Питер; Таки, Сетарех (2018). Fineman, Джереми Т .; Митценмахер, Майкл (ред.). «Приблизительное распределение максимальных долей». 2-й симпозиум по простоте алгоритмов (SOSA 2019) . Серия OpenAccess в информатике (OASIcs). Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. 69 : 20: 1–20: 11. DOI : 10.4230 / OASIcs.SOSA.2019.20 . ISBN 978-3-95977-099-6.
^ Гарг, Джугал; Таки, Сетарех (13.07.2020). «Улучшенный алгоритм аппроксимации для максимальных акций» . Материалы 21-й конференции ACM по экономике и вычислениям . EC '20. Виртуальное событие, Венгрия: Ассоциация вычислительной техники: 379–380. DOI : 10.1145 / 3391403.3399526 . ISBN 978-1-4503-7975-5.
^ Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (12 мая 2016 г.). «Об истинных механизмах распределения акций Максимина». arXiv : 1605.04026 [ cs.GT ].
^ Хуанг, Синь; Лу, Пиньян (10.07.2019). «Алгоритмическая основа для аппроксимации распределения максимальной доли работы по дому». arXiv : 1907.04505 [ cs.GT ].
↑ Айгнер-Хорев, Элад; Сегал-Халеви, Эрель (28.01.2019). «Соответствия без зависти в двудольных графах и их приложения к справедливому делению». arXiv : 1901.09527 [ cs.DS ].
^ Сирнс, Эндрю (2020-12-01). «Переосмысление распределения ресурсов: справедливость и вычислимость» . Тезисы .
^ Segal-Галеви, Эрэл (2019-12-18). «Отношение доминирования максимальной доли». arXiv : 1912.08763 [ math.CO ].
^ Woeginger, Герхард Дж (1997-05-01). «Схема полиномиального приближения для максимизации минимального времени завершения машины». Письма об исследованиях операций . 20 (4): 149–154. DOI : 10.1016 / S0167-6377 (96) 00055-7 . ISSN 0167-6377 .
^ Ланг, Жером; Роте, Йорг (2016), Роте, Йорг (редактор), «Справедливое разделение неделимых товаров», экономика и вычисления: введение в теорию алгоритмических игр, вычислительный социальный выбор и справедливое подразделение , Springer Texts in Business and Economics, Springer . Berlin Heidelberg, стр 493-550, DOI : 10.1007 / 978-3-662-47904-9_8 , ISBN 9783662479049
^ Хайнен, Тобиас; Нгуен, Нхан-Там; Нгуен, Трунг Тхань; Роте, Йорг (2018-11-01). «Аппроксимация и сложность задач оптимизации и существования для максимального, пропорционального и минимального долевого распределения неделимых товаров» . Автономные агенты и мультиагентные системы . 32 (6): 741–778. DOI : 10.1007 / s10458-018-9393-0 . ISSN 1573-7454 .
^ Карагианнис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Procaccia, Ariel D .; Шах, Нисарг; Ван, Цзюньсин (2019-09-01). "Необоснованная справедливость максимального благосостояния Нэша" (PDF) . ACM Trans. Экон. Comput . 7 (3): 12: 1–12: 32. DOI : 10.1145 / 3355902 . ISSN 2167-8375 . S2CID 202729326 .
^ a b c Бармен, Сиддхартх; Бисвас, Арпита; Кришнамурти, Санат Кумар; Нарахари, Ю. (20 ноября 2017 г.). «Групповое максимальное справедливое распределение неделимых товаров». arXiv : 1711.07621 [ cs.GT ].
^ a b c d Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (13.07.2018). «Сравнение примерных расслаблений от зависти» . Материалы 27-й Международной совместной конференции по искусственному интеллекту . IJCAI'18. Стокгольм, Швеция: AAAI Press: 42–48. arXiv : 1806.03114 . ISBN 978-0-9992411-2-7.
^ а б Сегал-Халеви, Эрель; Суксомпонг, Варут (01.12.2019). «Демократическое справедливое размещение неделимых товаров». Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . DOI : 10.1016 / j.artint.2019.103167 . ISSN 0004-3702 . S2CID 203034477 .

[b11-1] Budish, Эрик (2011). «Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов». Журнал политической экономии . 119 (6): 1061–1103. DOI : 10.1086 / 664613 . S2CID 154703357 .

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

[pw14-3] Procaccia AD, Ван Дж (2014). Достаточно справедливо: гарантия примерных максимальных акций . EC '14 Труды пятнадцатой конференции ACM по экономике и вычислениям . С. 675–692. DOI : 10.1145 / 2600057.2602835 . ISBN 9781450325653 .

[4] ttp://procaccia.info/papers/mms.jacm.pdf

[5] Аманатидис, Георгиос; Маркакис, Евангелос; Никзад, Афшин; Сабери, Амин (2017-12-04). «Алгоритмы приближения для расчета максимальных распределений долей». ACM-транзакции по алгоритмам . 13 (4): 1-28. arXiv : 1503.00941 . DOI : 10.1145 / 3147173 . S2CID 13366555 .

[6] Азиз, Харис; Раучекер, Герхард; Шрайен, Гвидо; Уолш, Тоби (2016-04-05). «Алгоритмы аппроксимации для максимального и минимального распределения долей в неделимых работах и товарах». arXiv : 1604.01435 [ cs.GT ].

[:3-7] Бармен, Сиддхартх; Кришнамурти, Санат Кумар (2017-03-06). «Алгоритмы аппроксимации для максимального деления справедливости». arXiv : 1703.01851 [ cs.GT ].

[:4-8] Годси, Мохаммад; Хаджиагайи, Мохаммад Таги; Седдигин, Масуд; Седдигин, Саид; Ями, Хади (2017-04-01). «Справедливое распределение неделимых благ: улучшение и обобщение». arXiv : 1704.00222 [ cs.GT ].

[:5-9] Гарг, Джугал; МакГлафлин, Питер; Таки, Сетарех (2018). Fineman, Джереми Т .; Митценмахер, Майкл (ред.). «Приблизительное распределение максимальных долей». 2-й симпозиум по простоте алгоритмов (SOSA 2019) . Серия OpenAccess в информатике (OASIcs). Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. 69 : 20: 1–20: 11. DOI : 10.4230 / OASIcs.SOSA.2019.20 . ISBN 978-3-95977-099-6.

[10] Гарг, Джугал; Таки, Сетарех (13.07.2020). «Улучшенный алгоритм аппроксимации для максимальных акций» . Материалы 21-й конференции ACM по экономике и вычислениям . EC '20. Виртуальное событие, Венгрия: Ассоциация вычислительной техники: 379–380. DOI : 10.1145 / 3391403.3399526 . ISBN 978-1-4503-7975-5.

[11] Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (12 мая 2016 г.). «Об истинных механизмах распределения акций Максимина». arXiv : 1605.04026 [ cs.GT ].

[12] Хуанг, Синь; Лу, Пиньян (10.07.2019). «Алгоритмическая основа для аппроксимации распределения максимальной доли работы по дому». arXiv : 1907.04505 [ cs.GT ].

[:1-13] Айгнер-Хорев, Элад; Сегал-Халеви, Эрель (28.01.2019). «Соответствия без зависти в двудольных графах и их приложения к справедливому делению». arXiv : 1901.09527 [ cs.DS ].

[14] Сирнс, Эндрю (2020-12-01). «Переосмысление распределения ресурсов: справедливость и вычислимость» . Тезисы .

[15] Segal-Галеви, Эрэл (2019-12-18). «Отношение доминирования максимальной доли». arXiv : 1912.08763 [ math.CO ].

[16] Woeginger, Герхард Дж (1997-05-01). «Схема полиномиального приближения для максимизации минимального времени завершения машины». Письма об исследованиях операций . 20 (4): 149–154. DOI : 10.1016 / S0167-6377 (96) 00055-7 . ISSN 0167-6377 .

[17] Ланг, Жером; Роте, Йорг (2016), Роте, Йорг (редактор), «Справедливое разделение неделимых товаров», экономика и вычисления: введение в теорию алгоритмических игр, вычислительный социальный выбор и справедливое подразделение , Springer Texts in Business and Economics, Springer . Berlin Heidelberg, стр 493-550, DOI : 10.1007 / 978-3-662-47904-9_8 , ISBN 9783662479049

[18] Хайнен, Тобиас; Нгуен, Нхан-Там; Нгуен, Трунг Тхань; Роте, Йорг (2018-11-01). «Аппроксимация и сложность задач оптимизации и существования для максимального, пропорционального и минимального долевого распределения неделимых товаров» . Автономные агенты и мультиагентные системы . 32 (6): 741–778. DOI : 10.1007 / s10458-018-9393-0 . ISSN 1573-7454 .

[:0-19] Карагианнис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Procaccia, Ariel D .; Шах, Нисарг; Ван, Цзюньсин (2019-09-01). "Необоснованная справедливость максимального благосостояния Нэша" (PDF) . ACM Trans. Экон. Comput . 7 (3): 12: 1–12: 32. DOI : 10.1145 / 3355902 . ISSN 2167-8375 . S2CID 202729326 .

[:2-20] Бармен, Сиддхартх; Бисвас, Арпита; Кришнамурти, Санат Кумар; Нарахари, Ю. (20 ноября 2017 г.). «Групповое максимальное справедливое распределение неделимых товаров». arXiv : 1711.07621 [ cs.GT ].

[:7-21] Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (13.07.2018). «Сравнение примерных расслаблений от зависти» . Материалы 27-й Международной совместной конференции по искусственному интеллекту . IJCAI'18. Стокгольм, Швеция: AAAI Press: 42–48. arXiv : 1806.03114 . ISBN 978-0-9992411-2-7.

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

[1]