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

Не путать с распределением элементов Max-min .

Максимальная доля (MMS) является критерием справедливого распределения статей . Учитывая набор элементов с разными значениями, максимин-доля «1 из n» — это максимальное значение, которое можно получить, разделив элементы на $n$ частей и отбираем часть с минимальным значением. Распределение предметов среди $n$ Агенты с разными оценками называются MMS-справедливыми, 1 из n если каждый агент получает пакет, который по крайней мере не уступает его/ее максимин-доле . Справедливость MMS — это ослабление критерия пропорциональности : каждый агент получает пакет, который по крайней мере не хуже равного распределения ( $1/n$ каждого ресурса). Пропорциональность может быть гарантирована, когда статьи делимы, но не тогда, когда они неделимы, даже если все агенты имеют одинаковые оценки. Напротив, справедливость MMS всегда может быть гарантирована идентичным агентам, поэтому это естественная альтернатива пропорциональности, даже если агенты разные.

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

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

Разные предметы. Предположим теперь, что элементы разные и каждый элемент имеет разное значение. Например, предположим $n=3$ и $m=5$ и значения элементов $1,3,5,6,9$, складывая до $24$. Если бы эти предметы были делимыми, мы бы дали каждому человеку стоимость, равную $24/3=8$ (или, если бы они делились только на целые значения, как в предыдущем абзаце, по крайней мере $\lfloor 24/3\rfloor =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 Алисы все еще $7$ как указано выше;
• MMS Джорджа $8$, по перегородке $\{1,7\},\{2,6\},\{8\}$ (все эти связки для него равнозначны);
• MMS от Дины $3$, по перегородке $\{1,1,1\},\{4\},\{17\}$.

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

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

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

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

История

Теодор Хилл изучил максимин-долю в 1987 году. Он представил нижнюю границу максимин-доли агента как функцию наибольшей стоимости товара и доказал, что всегда существует распределение, при котором каждый агент получает по крайней мере эту нижнюю границу. Обратите внимание, что фактическая максимальная доля может быть выше нижней границы, поэтому распределение, найденное методом Хилла, может не быть справедливым для MMS.

буддист изучал MMS-справедливость в 2011 году в контексте распределения курсов . Он представил механизм A-CEEI , который обеспечивает примерно справедливое распределение MMS, если разрешено добавлять некоторые товары. В 2014 году Прокачча и Ван доказали, что точного MMS-справедливого распределения между тремя или более агентами может не существовать.

Формальное определение

Позволять $C$ быть набором, представляющим выделяемый ресурс. Позволять $v$ быть любой действительной функцией на подмножествах $C$, представляющий их «ценность». 1 из n Максимин- доля $v$ от $C$ определяется как:

$\operatorname {MMS} _{v}^{1{\text{-out-of-}}n}(C):=~~~\max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~v(Z_{j})$

Здесь максимум по всем разделам $C$ в $n$ непересекающиеся подмножества, а минимум приходится на все $n$ подмножества в разделе. В приведенных выше примерах $C$ представлял собой набор целых чисел, а $v$ была функцией суммы, то есть $v(Z)$ определялась как сумма целых чисел в $Z$. Например, мы показали, что $\operatorname {MMS} _{v}^{1{\text{-out-of-}}3}(\{1,3,5,6,9\}):=7$, где максимизирующий раздел $\{1,6\},\{3,5\},\{9\}$. В типичной задаче справедливого распределения есть несколько $n$ разные агенты с разными функциями ценности $v_{1},\dots ,v_{n}$ на том же ресурсе $C$. 1 из- $n$ Значение MMS агента $i$ обозначается $\operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C):=\operatorname {MMS} _{v_{i}}^{1{\text{-out-of-}}n}(C)$. Распределение представляет собой вектор из n попарно непересекающихся подмножеств $C$ -- одно подмножество на каждого агента. Распределение $Z_{1},\dots ,Z_{n}$ называется MMS-fair , или просто распределение MMS , если для каждого агента $i$,

$v_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)$.

Выделение называется разделом MMS агента. $i$ если это так $v_{i}(Z_{j})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)$ для всех $j$, т. е. распределение является одним из разделов, максимизирующим формулу для $i$MMS.

Нижняя граница

Холм доказал, что если ценность каждого предмета для агента не превышает $\alpha$ умноженное на стоимость всех элементов, то 1 из n MMS этого агента будет как минимум $V_{n}(\alpha )$, где $V_{n}(\alpha )$ представляет собой следующую кусочно-линейную функцию :

$V_{n}(\alpha )=1-k\cdot (n-1)\cdot \alpha$ для всех $\alpha \in \left[{\frac {1}{k(n-1/(k+1))}},{\frac {1}{k(n-1/k)}}\right]$, для всех $k\geq 1$.

Обратите внимание, что $V_{n}(\alpha )$ является непрерывной и невозрастающей функцией $\alpha$, с $V_{n}(0)=1/n$ и $V_{n}(1)=0$ (см. в статье график $V_{2}(\alpha )$ и $V_{3}(\alpha )$)

Хилл также доказал, что для каждых n и $\alpha$, и для любых n агентов, которые ценят каждый элемент не более $\alpha$ умноженное на общее значение, существует раздел, в котором каждый агент получает значение не менее $V_{n}(\alpha )$. Более того, эта гарантия жесткая: для каждых n и $\alpha$, бывают случаи, когда невозможно гарантировать больше, чем $V_{n}(\alpha )$ для всех, даже если все оценки одинаковы.

Маркакис и Псомас усилил гарантию Хилла и предоставил алгоритм с полиномиальным временем для вычисления распределения, удовлетворяющего этой более сильной гарантии. Они также показали, что ни один правдивый механизм не может получить приближение 2/3 к этой гарантии и представить правдивую аппроксимацию постоянного коэффициента для ограниченного числа товаров. Гурвес, Монно и Тлилан расширил алгоритм Маркакиса и Псомаса, чтобы получить более строгую гарантию справедливости, которая работает для более общей задачи выделения базиса матроида .

Ли, Мулен, Сунь и Чжоу расширили нижнюю границу Хилла на плохие и представили более точную оценку, которая также зависит от количества плохих . Они также представили алгоритм с полиномиальным временем, позволяющий достичь этой границы.

Существование распределений на ярмарке MMS

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

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

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

Файги, Сапир и Таубер улучшил результат несуществования, построив экземпляр с $n=3$ агенты и $m=9$ позиции, в которых нет выделения MMS. В этом случае каждый агент имеет MMS 40, но можно гарантировать только наихудшие элементы агента с совокупной стоимостью 39. Они также показывают, что для любого $n\geq 3$, есть экземпляр с $3n+3$ элементы, для которых не существует распределения MMS. Если $n$ четно, они улучшают границу $3n+1$ предметы. В таких случаях худший из агентов может получить самое большее $1-1/n^{4}$ долю своих MMS.

Оценки на негативном примере Файги, Сапира и Таубера с $n=3$ агенты и $m=9$ предметы

Агент\Предмет	1	2	3	4	5	6	7	8	9
1	26	23	19	16	12	10	9	4	1
2	26	22	20	16	13	9	9	4	1
3	25	23	20	15	13	10	9	4	1

Хотя существование распределений MMS не гарантируется, было доказано, что в случайных случаях распределения MMS существуют с высокой вероятностью . Курокава, Прокачча и Ван показал, что это справедливо для двух случаев:

• Есть много предметов: $m\geq \alpha \cdot n\ln {n}$ для некоторой константы $\alpha$ это зависит от распределения вероятностей. Тогда, по предыдущему результату, существует распределение предметов без зависти с высокой вероятностью; такое распределение всегда является MMS.
• Есть несколько предметов: $m<n^{8/7}$ [обратите внимание, что этот случай частично перекрывает предыдущий случай]. Для этого случая они представляют алгоритм, называемый согласованным черновиком . Он основан на построении двудольного графа агентов и предметов и поиске в нем идеального соответствия . Они доказывают, что (1) вероятность того, что согласованный проект окажется успешным, равна 1, поскольку $n$ уходит в бесконечность. (2) Если сопоставленный проект успешен, то ценность каждого агента равна как минимум его MMS.

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

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

Бувере и Леметр доказано, что выделения MMS существуют в следующих случаях:

• Бинарные оценки – каждый агент либо любит предмет (оценивает его по $1$) или не любит (ценит на уровне $0$).
• Идентичные мультимножества – агенты могут оценивать элементы по-разному, но мультимножества значений агентов одинаковы.
• Мало предметов – $m\leq n+3$.

Последний результат позже был улучшен до $m\leq n+4$ Курокава, Прокачча и Ван и $m\leq n+5$ Файги, Сапира и Таубера. Из-за отрицательного примера с тремя агентами и девятью предметами это самая большая константа. $c$ который существует, такой, что все экземпляры с $n$ агенты и $m\leq n+c$ элементам всегда назначаются MMS, независимо от значения $n$. Хуммель далее показано, что распределения MMS существуют в следующих случаях:

• Есть $m\leq n+6$ предметы и $n\neq 3$ агенты.
• Есть $m\leq n+7$ предметы и $n\geq 8$ агенты.
• Есть $m\leq n+c$ предметы и $n\geq \lfloor 0.6597c(c!)\rfloor$ агенты.

Аманатидис, Маркакис, Никзад и Сабери показал, что распределения MMS существуют и могут быть найдены за полиномиальное время для случая троичных оценок , в которых каждый элемент оценивается в 0, 1 или 2.

Уриэль Файги доказал, что распределения MMS всегда существуют в двузначных экземплярах , в которых есть два значения a и b , и каждый агент оценивает каждый элемент либо по a, либо по b .

Приближения

буддист представил приближение к MMS «1 из n» — 1 из ( $n+1$) MMS - каждый агент получает как минимум столько, сколько он мог бы получить, разбив на n +1 пакет и получив худший. В общем, для любого d > n можно рассматривать MMS «1 из d» как приближение к MMS «1 из n» и искать распределение, в котором для каждого агента i :

$V_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}d}(C)$

Обратите внимание, что значение MMS 1 из d является слабо убывающей функцией d . Это называется порядковым приближением , поскольку оно зависит только от ранга связок, а не от их точных значений.Прокачча и Ван ввел другой вид аппроксимации — мультипликативную аппроксимацию MMS: распределение является r-долей MMS -справедливым для некоторой дроби r в [0,1], если ценность каждого агента составляет хотя бы долю r от значения его / ее MMS, то есть для каждого агента i :

$V_{i}(Z_{i})\geq r\cdot \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)$

Предположим, можно выбирать между двумя алгоритмами: первый гарантирует мультипликативную аппроксимацию (например, MMS 3/4 дроби), а второй гарантирует порядковую аппроксимацию (например, 1 из (3 n /2) MMS). Какая из двух гарантий выше? Ответ зависит от ценностей.

• Мультипликативное приближение является более высоким, например, когда имеется n одинаковых товаров со стоимостью 1. Тогда 1 из $d$ MMS равен 0 для любого d > n , но 1 из $n$ MMS равен 1, поэтому любое положительное мультипликативное приближение лучше.
• Порядковое приближение выше, например, когда имеется d одинаковых товаров со стоимостью 1, для некоторого d из { n +1,...,2 n -1}. Тогда MMS 1 из d равен 1, а MMS 1 из d $n$ MMS тоже равен 1, поэтому любое r его -мультипликативное приближение с r <1 хуже.

В общем, для любого целого числа k MMS «1 из n» как минимум в k раз превышает MMS «1 из nk» : возьмите оптимальный раздел MMS «1 из nk» и сгруппируйте пакеты в n суперпакетов, каждый из которых из которых содержит k исходных пучков. Стоимость каждого из этих супернаборов как минимум в k раз превышает наименьший исходный набор. Следовательно, 1/ k -мультипликативная аппроксимация по крайней мере такая же большая, как порядковая аппроксимация 1 из nk , но может быть меньше, чем порядковая аппроксимация 1 из ( nk -1), как в приведенном выше примере. В частности, любое r -мультипликативное приближение для r ≥ 1/2 по крайней мере так же хорошо, как порядковое приближение 1 из (2 n ), но может быть хуже, чем порядковое приближение 1 из (2 n -1).

MMS-ярмарка распределения товаров

Мультипликативные приближения

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

$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}}$

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

Аманатидис, Маркакис, Никзад и Сабери представил несколько улучшенных алгоритмов:

• Простой и быстрый 1/2-фракционный алгоритм MMS;
• Алгоритм MMS с делением 2/3, который работает за полиномиальное время как по m, так и по n ;
• Алгоритм MMS 7/8 для 3 агентов;

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

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

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

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

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

Гарг и Таки представлено:

• Простой алгоритм для 3/4-фракционного MMS, которому не нужно знать значение MMS, и поэтому он работает за строго полиномиальное время.
• Доказательство существования $({\frac {3}{4}}+{\frac {1}{12n}})$-фракция ММС.

Акрами, Гарг, Шарма и Таки улучшить анализ алгоритма, представленного Гаргом и Таки, упростив анализ и улучшив гарантию существования ${\frac {3}{4}}+\min \left({\frac {1}{36}},{\frac {3}{16n-4}}\right)$.

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

Результаты мультипликативной аппроксимации для MMS

оценки	Нижняя граница			Верхняя граница		Алгоритм полиномиального времени
	$n=3$	$n=4$	$n\geq 5$	$n=3$	$n\geq 4$
Добавка	$11/12$	$4/5$	${\frac {3}{4}}+\min \left({\frac {1}{36}},{\frac {3}{16n-4}}\right)$	$39/40$	$1-{\frac {1}{n^{4}}}$	${\frac {3}{4}}+{\frac {1}{12n}}-\epsilon$
Субмодульный	$1/3$			$3/4$		$1/3$
ХАРАКТЕРИСТИКА	$3/13$			$1/2$		$1/8$
субаддитивный	$1/(10\lceil \log(m)\rceil )$			$1/2$		–

Порядковые приближения

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

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

• Распределение товаров по MMS « 1 из (2 n 1 из (2 n -2)» и распределение домашних дел по MMS « /3)» с использованием сопоставления без зависти .
• 1 из (3 n /2), Распределение товаров MMS который можно вычислить за политайм, когда n <6.
• Распределение товаров MMS 1 из (3 n /2) за полиномиальное время и результат существования распределения MMS L - из ([ L +1/2] n ).
• 1 из (3 n /4). Распределение дел по MMS

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

Дополнительные ограничения

Максимизация продукта : Караяннис, Курокава, Мулен, Прокачча, Шах и Ван. показал, что распределение максимального благосостояния по Нэшу (распределение, максимизирующее продукт полезностей) всегда ${\frac {2}{1+{\sqrt {4n-3}}}}$-фракция MMS честная, и она тугая.

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

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

Ограничения по количеству элементов : элементы разделены на категории, и каждый агент может получить не более k _h элементов из каждой категории h . Другими словами, расслоения должны быть независимыми множествами матроида разбиения .

• Бармен и Бисвас представить алгоритм, сводящий проблему к задаче без ограничений, но с субмодулярными оценками, а затем использовать алгоритм для достижения 1/3-доли MMS-справедливости.
• Хуммель и Хетланд представляют улучшенный алгоритм с полиномиальным временем для обеспечения справедливости MMS на уровне 1/2. Они адаптируют стандартные методы и сокращения от условий без ограничений к условиям с ограничениями, а затем применяют вариант процедуры наполнения мешка.

График конфликтов : Хаммель и Хетланд изучите другую настройку, в которой существует граф конфликтов между элементами (например: элементы представляют события, а агент не может присутствовать на двух одновременных событиях). Они показывают, что если степень графа конфликтов равна d и он находится в (2, n ), то распределение MMS 1/ d -доли может быть найдено за полиномиальное время, а распределение MMS 1/3-доли всегда существует. .

Связность : элементы расположены на графе, и каждая часть должна быть связным подграфом.

• Бувере, Чехларова, Элкинд, Игараси и Петерс докажите, что если граф ациклический, то справедливое распределение MMS всегда существует и может быть эффективно найдено. В общих графах справедливое распределение MMS может не существовать, и его может быть NP-трудно найти.
• Лонц и Трушинский сосредоточьтесь на случае, когда граф представляет собой цикл, и представьте алгоритм примерно справедливого распределения MMS.

MMS-справедливое распределение обязанностей по дому

Азиз, Раучекер, Шрайен и Уолш распространил понятие MMS на работу по дому (предметы с отрицательной полезностью). Обратите внимание, что для работ мультипликативные коэффициенты аппроксимации больше 1 (поскольку меньшее количество работ имеет более высокую полезность), а порядковые коэффициенты аппроксимации меньше n . Они представили:

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

Бармен и Кришнамурти представил алгоритм достижения MMS 4/3 фракции (точнее, ${\frac {4n-1}{3n}}$). Алгоритм можно рассматривать как обобщение алгоритма LPT для планирования идентичных машин.

Хуан и Лу докажите, что справедливое распределение MMS в размере 11/9 для домашних дел всегда существует, а распределение MMS в размере 5/4 может быть найдено за полиномиальное время. Их алгоритм можно рассматривать как обобщение алгоритма Multifit для планирования идентичных машин.

Кулкарни, Мехта и Таки изучите MMS-справедливое распределение со смешанными оценками , т. е. когда имеются и товары, и дела. Они доказывают это:

• Мультипликативное приближение невозможно. Они продолжают пример Прокаччиа и Ванга. добавив три работы по дому со значением -4 054 999,75. 1 из 3 MMS каждого агента составляет 0,25 (каждый пакет MMS содержит четыре товара на сумму 4 055 000 и одну работу). Однако каждое распределение товаров дает по крайней мере одному агенту стоимость товаров не более 4 054 999. Мы должны поручить каждому агенту одну работу; следовательно, по крайней мере один агент имеет отрицательное значение.
• Они также представляют условия, при которых вычисление α-MMS и оптимального по Парето распределения для наилучшего возможного α в конкретном случае может быть выполнено за полиномиальное время.

Эбадиан, Питерс и Шах докажите, что распределение MMS всегда существует в двузначных случаях, когда каждый агент i делит работу на «легкую» (оценивается как 1 для всех) или «сложную» (оценивается некоторым целым числом p _i > 1).

Методики и алгоритмы

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

Масштабирование

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

• $r$-фракция MMS : общая стоимость $O$ по крайней мере $n$; нам нужно дать каждому из $n$ агенты, пакет стоит как минимум $r$.
• 1-е MMS : общая стоимость $O$ по крайней мере $d$; нам нужно дать каждому из $n$ агенты, пакет стоит как минимум $1$.

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

• $r$-фракция MMS : общая стоимость $O$ это точно $n$; MMS максимум $1$; нам нужно дать каждому из $n$ агенты, пакет стоит как минимум $r$.
• 1-е MMS : общая стоимость $O$ это точно $d$; MMS максимум $1$; нам нужно дать каждому из $n$ агенты, пакет стоит как минимум $1$.

Выделение одного объекта

Если мы удалим один объект $o$ от $O$. Тогда для каждого агента $1$-вне-( $n-1$) MMS относительно оставшегося набора $O\setminus o$ по крайней мере его $1$-из- $n$ MMS относительно оригинального набора $O$. Это связано с тем, что в исходном разделе MMS $n-1$ детали остаются целыми. Теперь предположим, что мы стремимся дать каждому агенту значение $r$. Если какой-то объект $o_{1}$ стоит как минимум $r$ хотя бы одному агенту, то мы можем дать $o_{1}$ одному такому агенту произвольно и приступим к распределению остальных объектов по оставшимся агентам. Таким образом, мы можем предположить, что:

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

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

Наполнение мешка

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

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

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

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

Модифицированное заполнение мешка : условие, что все предметы $s$-маленький можно расслабить следующим образом. Возьми немного $s<r$. Обозначьте объект, которого нет $s$-маленький (т.е. оцениваемый как минимум $s$ хотя бы одним агентом) как " $s$-большой объект». Предположим, что не более $n$ объекты $s$-большой. Возьми один $s$-большой объект $o_{1}$, положи в мешок и наполни его $s$-мелкие предметы, пока один агент не укажет, что для него это стоит как минимум $r$. Должен быть хотя бы один такой агент, так как какой-то агент $i$ ценности $o_{1}$ в какой-то момент $x>s$. Для этого агента существует не более $n-1$ оставшийся $s$-крупные предметы. Согласно предыдущей нормализации, эти объекты все еще $r$-небольшие, поэтому их общая стоимость за $i$ самое большее $r(n-1)$, поэтому значение оставшегося $s$-минимум мелкие предметы $n-r(n-1)-x=r(n-1)+r-x\geq r-x$.

Заказ

Экземпляр считается упорядоченным, если все агенты имеют одинаковый порядковый номер объектов, т. е. объекты могут быть пронумерованы. $o_{1},\dots ,o_{m}$ такая, что для каждого агента $i$, $v_{i}(o_{1})\geq \dots \geq v_{i}(o_{m})$. Интуитивно понятно, что упорядоченные экземпляры сложнее всего, поскольку конфликт между агентами самый большой. Действительно, отрицательный пример упорядочен – порядок объектов определяется матрицей $T$, который одинаков для всех агентов. Это можно доказать и формально. Предположим, у нас есть алгоритм, который находит для каждого упорядоченного экземпляра $r$-дробное распределение MMS. Теперь нам предоставлен общий экземпляр распределения элементов. $P$. Решаем ее следующим образом.

1. Создайте упорядоченный экземпляр $\mathrm {ord} (P)$ следующим образом: для каждого агента i определите $v_{i}(o_{j})$ в $\mathrm {ord} (P)$ как $j$-th самое высокое значение в наборе значений агента $i$ в $P$. Это требует $O(nm\lg m)$ время.
2. Найдите $r$-дробное распределение MMS $\mathrm {ord} (A)$ в $\mathrm {ord} (P)$.
3. Постройте последовательность комплектования , в которой агент, получивший $o_{1}$ в $\mathrm {ord} (A)$ первым выбирает агента, получившего $o_{2}$ в $\mathrm {ord} (A)$ выбирает второе и т. д.
4. Позвольте агентам выбирать свои лучшие предметы в соответствии с последовательностью выбора. Позволять $A$ быть результирующим распределением. В $A$, каждый агент получает точно такое же количество предметов, как и в $\mathrm {ord} (A)$. При этом каждый агент, получивший $o_{j}$ в $\mathrm {ord} (A)$, получает один из своих лучших $j$ предметы в $A$. Следовательно, его ценность за каждый предмет, который он получил, $A$ по крайней мере так же велик, как его значение для соответствующего элемента в $\mathrm {ord} (A)$. Следовательно, ценность каждого агента в $A$ по крайней мере так же высок, как и в $\mathrm {ord} (A)$. Поскольку порядок не меняет значения MMS, новое распределение $A$ все еще $r$-фракция ММС.

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

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

Выделение двух объектов

Предположим, мы нашли два объекта o ₁ и o ₂ , значение которых для одного агента i не ниже r , а для других агентов значение не выше 1. Тогда эти два объекта можно присвоить i . Для других агентов MMS «1 из ( n -1) относительно оставшегося набора — это, по крайней мере, его MMS из 1 из n относительно исходного набора O» . Это связано с тем, что в исходном разделе MMS по крайней мере n -2 частей остаются неповрежденными, а две неповрежденные части могут быть объединены в одну часть со значением не менее 1. Эта нормализация работает только с аддитивными оценками. .

Более того, предположим, что экземпляр упорядочен, и предположим, что мы удалили из O два объекта on _n , on _{n +1} (т. е. n -й и ( n +1)-й элементы с наибольшим значением). Тогда для каждого агента 1 из ( n -1) MMS относительно оставшегося набора будет, по крайней мере, его 1 из n MMS относительно исходного набора O . Это связано с тем, что по принципу «ячейки» по крайней мере одна часть MMS каждого агента должна содержать два или более объектов из набора { o ₁ , ..., o _{n +1} }. Эти предметы можно использовать для замены отданных объектов, в результате чего получается n -1 частей со значением не менее 1. Это означает, что если объекты on _n , on _{n +1} имеют значение не менее MMS для некоторому агенту i , мы можем передать их i и приступить к распределению оставшихся объектов между оставшимися агентами. Таким образом, мы можем предположить, что:

• r-фракция MMS общее значение on _n , on _{+1 r} для всех агентов меньше : . , значение on _{+1 В частности} и всех объектов после него в порядке меньше r /2.
• 1-of-d MMS : общее значение od , o _{d +1} для всех агентов меньше 1. В частности, значение o _{d +1} и всех объектов после него в порядке меньше 1/2.

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

• Если для какого-либо агента один объект стоит не менее 2/3, выделите его.
• Закажите экземпляр.
• Пока on _n , on _{+1 .} приносят какому-то агенту не менее 2/3, выделите их
• Наконец, существует не более n объектов со стоимостью не менее 1/3; распределите их с помощью модифицированного мешка-наполнителя.

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

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

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

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

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

Связь с другими критериями справедливости

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

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

EF0 подразумевает PROP*0, а EF1 подразумевает PROP*( n -1). Более того, для любого целого числа c 0 из EF c следует PROP*(( n -1) c ). Противоположный вывод верен, когда n =2, но не когда n >2.

Следующие приближения максимин-доли подразумеваются PROP*( n -1), а следовательно, и EF1:

• Мультипликативное приближение: 1/ n - дробь ММС (1/ n плотная);
• Порядковое приближение: 1 из (2 n -1) MMS (2 n -1 плотно). Аналогично, для каждого целого числа c PROP* c подразумевает 1 из ( c + n ) MMS.
• MMS, когда функция значения является двоичной. Противоположный вывод также имеет место.

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

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

Распределение называется «без зависти, кроме любого элемента » (EF x ) для агента i , если для каждого другого агента j для любого отдельного элемента, удаленного из я пакета j, не завидую остатку. EFx строго сильнее, чем EF1. Это подразумевает следующие приближения MMS:

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

MMS для групп

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

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

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

• Отсутствие зависти подразумевает GMMS-справедливость;
• GMMS-справедливость подразумевает MMS-справедливость (путем взятия подгруппы размера n ) и PMMS-справедливость (путем взятия подгрупп размера 2);
• Справедливость PMMS подразумевает справедливость 2/3 MMS для трех агентов и справедливость 4/7 MMS в целом;
• Справедливость PMMS подразумевает EFX, что подразумевает EF1.
• EF1 подразумевает 1/2-PMMS, а EFX подразумевает 2/3-PMMS. Следовательно, распределение 1/2-PMMS может быть найдено за полиномиальное время.
• Справедливость MMS и честность PMMS не предполагают друг друга.

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

MMS для агентов с разными правами

Когда агенты имеют разные права (также называемые неравными долями или асимметричными правами ), справедливость MMS должна быть адаптирована так, чтобы гарантировать более высокую долю агентам с более высокими правами. Были предложены различные адаптации. Ниже мы предполагаем, что права задаются вектором $t=(t_{1},\ldots ,t_{n})$, где $t_{i}$ представляет собой право агента $i$.

Справедливость взвешенных MMS

Фархади, Годси, Хаджиагайи, Лахайе, Пеннок, Седдигин и Седдигин ввести взвешенную долю максимина (WMMS), определяемую следующим образом:

$\operatorname {WMMS} _{i}^{t}(C):=~~~\max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~{\frac {t_{i}}{t_{j}}}V(Z_{j})=~~~t_{i}\cdot \max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~{\frac {V(Z_{j})}{t_{j}}}$

Интуитивно понятно, что оптимальный WMMS достигается за счет разделения, в котором значение части j пропорционально правам агента j . Например, предположим, что все функции стоимости представляют собой суммы, а вектор прав равен t = (1/6, 11/24, 9/24). Затем $\operatorname {WMMS} _{1}^{t}(\{1,3,5,6,9\})=4$ по разделу ({1,3},{5,6},{9}); это оптимально, так как значение каждой части $i$ равно $24t_{i}$. По тому же разделу $\operatorname {WMMS} _{2}^{t}=11$ и $\operatorname {WMMS} _{3}^{t}=9$. Когда все n прав равны, $\operatorname {WMMS} _{i}^{t}\equiv \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}$.

Распределение C называется WMMS-справедливым для вектора прав t , если ценность каждого агента i не менее $\operatorname {WMMS} _{i}^{t}(C)$. Когда все n агентов имеют одинаковые оценки, справедливое распределение WMMS всегда существует по определению. Но при разных оценках наилучшее мультипликативное приближение — 1/ n . Верхняя оценка доказывается на следующем примере с 2 n -1 товарами и n агентами, где ε>0 — очень маленькая константа:

Агент	Право	Значение для пунктов 1, ..., n -1	Значение для позиции n	Значение для элементов n +1, ..., 2 n -1
1, ..., п -1	е	е	1-( n -1) е	0
н	1-( n -1) е	[1-( n -1) e ]/ n	[1-( n -1) e ]/ n	е

Все агенты имеют оптимальный раздел WMMS: для «маленьких» агентов (1,..., n -1) это раздел ({1},...,{ n -1},{ n }), а для «большой» агент ( n ) это ({ n +1}, ..., {2 n -1}, {1,..., n }). Поэтому, $\operatorname {WMMS} _{i}^{t}=t_{i}$ для всех агентов i (для сравнения заметим, что $\operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=\epsilon =t_{i}$ для мелких агентов, но $\operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=[1-(n-1)\epsilon ]/n=t_{i}/n$ для крупного агента).

В любом мультипликативном приближении WMMS все агенты должны получить положительное значение. Это означает, что мелкие агенты берут не менее n -1 предметов 1,..., n , поэтому у крупного агента остается не более одного такого предмета, и его стоимость составляет примерно 1/ n, а не почти 1.

WMMS Справедливое распределение всегда существует и может быть найдено путем циклического распределения элементов . В ограниченном случае, когда каждый агент i оценивает каждый товар не более чем на $\operatorname {WMMS} _{i}^{t}$, справедливое распределение WMMS существует и может быть найдено с помощью алгоритма, аналогичного наполнению мешка: оценки каждого агента i умножаются на $t_{i}/\operatorname {WMMS} _{i}^{t}$; и на каждой итерации предмет передается неудовлетворенному агенту (агенту со стоимостью менее $\operatorname {WMMS} _{i}^{t}/2$), который ценит это больше всего. Этот алгоритм выделяет каждому агенту i как минимум $\operatorname {WMMS} _{i}^{t}/2$ и самое большее $\operatorname {WMMS} _{i}^{t}$. На практике почти всегда существует справедливое распределение WMMS.

Справедливость порядкового номера MMS

Бабаев, Нисан и Талгам-Коэн. представляют собой естественное расширение порядкового приближения MMS для агентов с различными правами. Для любых двух целых чисел $l,d$, установите C и функцию значения V , определите

$\operatorname {MMS} _{V}^{l{\text{-out-of-}}d}(C):=~~~\max _{P\in \operatorname {Partitions} (C,d)}~~~\min _{Z\in \operatorname {Unions} (P,l)}~~~V(Z)$

Здесь максимум приходится на все разбиения C на $d$ непересекающиеся подмножества, а минимум приходится на объединения все $l$ части. Например, $\operatorname {MMS} _{V}^{2{\text{-out-of-}}3}(\{1,3,5,6,9\})=15$ по разделу ({1,6},{3,5},{9}). Теперь порядковая доля максимина (OMMS) определяется следующим образом:

$\operatorname {OMMS} _{i}^{t}(C):=~~~\max _{l,d:~l/d\leq t_{i}}\operatorname {MMS} _{i}^{l{\text{-out-of-}}d}(C)$

Например, если право агента i представляет собой любое действительное число, по крайней мере, равное 2/3, то он имеет право по крайней мере на 2 из 3 MMS C . Заметим, что хотя пар бесконечно много $l,d$ удовлетворение с $l/d\leq t_{i}$, только конечное число из них не являются избыточными (не подразумеваемыми другими), поэтому можно вычислить OMMS за конечное время. Распределение Z ₁ ,..., Z _n называется OMMS-справедливым для вектора прав w, если значение каждого агента i не менее $\operatorname {OMMS} _{i}^{t}(C)$.

OMMS может быть выше или ниже WMMS в зависимости от значений:

• В качестве примера, в котором WMMS выше, предположим, что C = {40, 60} и t = (0,4, 0,6) . Тогда очевидно, что WMMS ₁ = 40 и WMMS ₂ = 60, поэтому единственное справедливое распределение WMMS дает 40 к 1 и 60 к 2. Однако OMMS ₁ = 0, поскольку дроби, удовлетворяющие $l/d\leq 0.4$ равны 1/3, 2/5, 3/7 и т. д., и во всех случаях при любом разбиении C на $d$ подмножества, есть как минимум $l$ пустые подмножества. Кроме того, OMMS ₂ =40, поскольку дроби, удовлетворяющие $l/d\leq 0.6$ равны 1/2, 2/4, 3/5, 4/7 и т. д., и во всех случаях в любом разбиении C на $d$ подмножества, $l$ наименее ценные подмножества не содержат 60. Таким образом, справедливое распределение по OMMS может дать 40 к 2 и 60 к 1 или ничего не дать 1, и то и другое кажется несправедливым.
• В качестве примера, в котором OMMS выше, предположим, что C = {40, 60} и t = (0,2, 0,2, 0,6) . Тогда WMMS _i =0 для всех i , поскольку в любом 3-разделе C хотя бы один пучок пуст. Так что критерий справедливости WMMS бесполезен. Аналогично, OMMS ₁ =OMMS ₂ =0. Однако OMMS ₃ =40 по паре $l/d=1/2$ и раздел ({40},{60}), поэтому справедливость OMMS требует передать хотя бы один элемент агенту 3, что кажется более справедливым.

Справедливость AnyPrice-Share

Бабайофф, Эзра и Файги представили третий критерий справедливости, который они называют AnyPrice Share (APS) . Они определяют это двумя эквивалентными способами; один из них – явно усиление доли максимина. Вместо того, чтобы разбивать элементы на d непересекающиеся пакеты, агенту разрешено выбирать любой набор пакетов, которые могут перекрываться. Но затем агент должен присвоить вес каждому пакету так, чтобы сумма весов была не менее 1, и каждый элемент принадлежал к пакетам, общий вес которых не превышает права агента. APS — это стоимость наименее ценного пакета с положительным весом. Формально:

$\operatorname {APS} _{V}^{t}(C):=~~~\max _{P\in \operatorname {AllowedBundleSets} (C,t_{i})}~~~\min _{Z\in P}~~~V(Z)$

где максимум приходится на все наборы пакетов, так что при некотором присвоении весов пакетам общий вес всех пакетов равен не менее 1, а общий вес каждого элемента не превышает t _i . Существует алгоритм с полиомиальным временем, который гарантирует каждому агенту не менее 3/5 его APS.

APS всегда не ниже OMMS: при оптимальном разбиении l -out-of- d , где l/d ≤ t _i , можно присвоить вес 1/ d объединению частей 1,... ., l , объединение частей 2,..., l +1 и т. д. (циклическим образом), такое, что каждая часть входит ровно в l объединений. Следовательно, каждый предмет принадлежит к связкам, общий вес которых не превышает l / d , что не превышает t _i . Агенту гарантируется наименее ценный такой пакет, который представляет собой как минимум l -из- d MMS.

В некоторых случаях АПС строго выше ОММС. Вот два примера:

• Простой пример с разными правами: пусть C = {2,1,1,1,0} и t _i = 2/5 . OMMS не более 1 (достаточно проверить l/d в {1/3, 2/5}). Но APS равен 2 по следующим весам: 0,4*{2}, 0,2*{1,1}, 0,2*{1,1}, 0,2*{1,1}. Обратите внимание, что сумма весов равна 1. 2 появляются в одном наборе с весом 0,4, а каждая единица появляется в двух наборах с весом 0,2, 0,2.
• Более сложный пример с равными правами: пусть C = {5, 5, 5, 7, 7, 7, 11, 17, 23, 23, 23, 31, 31, 31, 65} и t _i = 1/3 . OMMS равен 1 из 3 MMS и не превышает 96; это можно проверить, проверив все 3 раздела. APS равен 97, поскольку можно составить 6 комплектов по 5 предметов в каждом с общей стоимостью 97, так что каждый предмет появляется ровно в двух комплектах. Затем каждому пакету можно присвоить вес 1/6.
  • Этот пример также показывает, что распределение APS может отсутствовать даже для трех агентов с одинаковыми оценками и равными правами. В этом отличие от OMMS, которая всегда существует с одинаковыми оценками и равными правами, и WMMS, которая всегда существует с идентичными оценками и произвольными правами.

APS может быть выше или ниже WMMS; примеры такие же, как и для OMMS и WMMS:

• WMMS выше: C = {40, 60} и t = (0,4, 0,6) . Тогда WMMS ₁ =40 и WMMS ₂ =60. Но APS ₁ =0, так как каждый предмет должен иметь вес не более 0,4, поэтому пустой комплект должен иметь вес не менее 0,2. Кроме того, APS ₂ =40, поскольку каждый предмет должен иметь вес не более 0,6, поэтому {40} и пустая связка должны иметь общий вес не менее 0,4.
• АПС выше: C = {40, 60} и t = (0,2, 0,2, 0,6) . Тогда WMMS _i =0 для всех i . Аналогично, APS ₁ =APS ₂ =0, как указано выше. Однако APS ₃ =40, например, по весам 0,5*{40}, 0,5*{60}.

Максимин доля как функция наибольшей стоимости товара

Теодор Хилл представили версию MMS, зависящую от наибольшей стоимости товара.

См. также

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