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

Критерий справедливого распределения предметов

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

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

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

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

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

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

• Элис оценивает их в ; ${\displaystyle 1,3,5,6,9}$
• Джордж оценивает их в ; ${\displaystyle 1,7,2,6,8}$
• Дина оценивает их в . ${\displaystyle 1,1,1,4,17}$

Теперь у каждого агента свой MMS:

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

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

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

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

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

История

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

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

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

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

${\displaystyle \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})}$

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

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

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

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

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

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

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

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

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

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

Наличие MMS-справедливых распределений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приближения

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

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

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

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

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

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

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

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

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

Прокачча и Ван ^[3] представили алгоритм, который всегда находит MMS размером r _n -дробь, где

${\displaystyle 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 постоянно, но его время выполнения может быть экспоненциальным по n .

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

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

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

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

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

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

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

Гарг и Таки ^[19] представили:

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

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

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

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

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

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

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

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

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

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

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

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

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

• Барман и Бисвас ^{[28] :10} представляют алгоритм, сводящий задачу к задаче без ограничений, но с субмодулярными оценками, а затем используют алгоритм ^[17] для достижения 1/3-доли MMS-справедливости.
• Хаммель и Хетланд ^[29] представляют улучшенный алгоритм полиномиального времени для 1/2-фракционной MMS-справедливости. Они адаптируют стандартные методы и сокращения из неограниченной настройки в настройку с ограничениями, а затем применяют вариант процедуры заполнения мешка.

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

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

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

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

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

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

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

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

Кулкарни, Мехта и Таки ^[35] изучают справедливое распределение MMS со смешанными оценками , т. е. когда есть и товары, и хлопоты. Они доказывают, что:

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

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

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

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

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

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

• ${\displaystyle r}$-фракционная MMS : общая стоимость составляет не менее ; нам необходимо предоставить каждому агенту пакет стоимостью не менее . ${\displaystyle O}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle r}$
• 1-of-d MMS : общая стоимость составляет не менее ; нам необходимо предоставить каждому агенту пакет стоимостью не менее . ${\displaystyle O}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle 1}$

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

• ${\displaystyle r}$-дробь MMS : общая стоимость составляет ровно ; MMS не более ; нам нужно предоставить каждому агенту пакет стоимостью не менее . ${\displaystyle O}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle r}$
• 1-of-d MMS : общая стоимость составляет ровно ; MMS не более ; нам нужно предоставить каждому агенту пакет стоимостью не менее . ${\displaystyle O}$ ${\displaystyle d}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle 1}$

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

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

• ${\displaystyle r}$-фракционная MMS  : значение каждого объекта для всех агентов меньше . ${\displaystyle r}$
• ${\displaystyle 1}$-of- MMS  : значение каждого объекта для всех агентов меньше . ${\displaystyle d}$ ${\displaystyle 1}$

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

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

Обозначим объект, который оценивается всеми агентами не более чем в -small object. Предположим, что все объекты -small. Возьмите пустой мешок и наполните его объектом за объектом, пока мешок не станет ценным по крайней мере для одного агента. Затем передайте мешок одному такому агенту произвольно. Поскольку все объекты -small, оставшиеся агенты оценивают мешок не более чем в ; если эта ценность достаточно мала, то оставшаяся ценность достаточно велика, чтобы мы могли действовать рекурсивно. ^[18] В частности, заполнение мешка дает следующие решения: ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle r+s}$

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

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

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

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

Заказ

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

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

Таким образом, при поиске распределений MMS в размере -дробной части мы можем предположить, что: ${\displaystyle r}$

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

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

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

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

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

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

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

Гарантию этого алгоритма можно сформулировать даже без упоминания MMS:

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

Алгоритмические проблемы

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

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

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

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

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

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

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

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

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

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

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

MMS для групп

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

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

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

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

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

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

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

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

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

${\displaystyle \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). Тогда путем разбиения ({1,3},{5,6},{9}); она оптимальна, поскольку значение каждой части равно . При том же разбиении и . Когда все n прав равны, . ${\displaystyle \operatorname {WMMS} _{1}^{t}(\{1,3,5,6,9\})=4}$ ${\displaystyle i}$ ${\displaystyle 24t_{i}}$ ${\displaystyle \operatorname {WMMS} _{2}^{t}=11}$ ${\displaystyle \operatorname {WMMS} _{3}^{t}=9}$ ${\displaystyle \operatorname {WMMS} _{i}^{t}\equiv \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}}$

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

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

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

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

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

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

${\displaystyle \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 на непересекающиеся подмножества, а минимум по всем объединениям частей . Например, по разбиению ({1,6},{3,5},{9}). Теперь Ordinal Maximin Share (OMMS) определяется как: ${\displaystyle d}$ ${\displaystyle l}$ ${\displaystyle \operatorname {MMS} _{V}^{2{\text{-out-of-}}3}(\{1,3,5,6,9\})=15}$

${\displaystyle \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 . Обратите внимание, что, хотя существует бесконечно много пар, удовлетворяющих , только конечное число из них не являются избыточными (не подразумеваются другими), поэтому возможно вычислить OMMS за конечное время. ^[44] Распределение Z ₁ ,..., Z _n называется OMMS-справедливым для вектора прав w , если значение каждого агента i составляет по крайней мере . ${\displaystyle l,d}$ ${\displaystyle l/d\leq t_{i}}$ ${\displaystyle \operatorname {OMMS} _{i}^{t}(C)}$

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

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

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

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

${\displaystyle \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. ^[45]

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

В некоторых случаях APS строго выше OMMS. Вот два примера:

• Простой пример с различными правами: пусть 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, в то время как каждая из 1 появляется в двух наборах с весом 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 может не существовать даже для 3 агентов с идентичными оценками и равными правами. Это контрастирует с 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.
• APS выше: 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}.

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

Теодор Хилл ^[1] представил версию MMS, которая зависит от наибольшего значения элемента.

Смотрите также

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

Ссылки

1. Hill, Theodore P. (1987). «Разбиение общих вероятностных мер». Анналы вероятности . 15 (2): 804–813. doi : 10.1214/aop/1176992173 . ISSN  0091-1798. JSTOR  2244076.
2. Budish, Eric (2011). «Комбинаторная задача о назначениях: приблизительное конкурентное равновесие из равных доходов». Журнал политической экономии . 119 (6): 1061–1103. doi : 10.1086/664613. S2CID  154703357.
3. Procaccia, AD; Wang, J (2014). «Достаточно справедливо: гарантия приблизительных максиминных долей». EC '14 Proceedings of the Fifteenth ACM Conference on Economics and Computation . pp. 675–692. doi :10.1145/2600057.2602835. ISBN 9781450325653. S2CID  53223172.
4. Маркакис, Эвангелос; Псомас, Христос-Александрос (2011). «О наихудшем случае распределения при наличии неделимых товаров». В Чен, Нин; Элкинд, Эдит; Куцупиас, Элиас (ред.). Интернет и сетевая экономика . Конспект лекций по информатике. Том 7090. Берлин, Гейдельберг: Springer. С. 278–289. doi :10.1007/978-3-642-25510-6_24. ISBN 978-3-642-25510-6.
5. Гурвес, Лоран; Монно, Жером; Тлилан, Лидия (2015-07-19). «Худшие компромиссы в матроидах с приложениями к распределению неделимых благ». Теоретическая информатика . 589 : 121–140. doi :10.1016/j.tcs.2015.04.029. ISSN  0304-3975.
6. Ли, Бо; Мулен, Эрве; Сунь, Анькан; Чжоу, Ю (2023). «Гарантия Хилла на случай наихудшего случая для неделимых плохих вещей». arXiv : 2302.00323 [cs.GT].
7. "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2019-07-28 . Получено 2019-11-29 .{{cite web}}: CS1 maint: archived copy as title (link)
8. Фейге, Уриэль; Сапир, Ариэль; Таубер, Лалив (2021-10-19). «Жесткий отрицательный пример справедливого распределения MMS». arXiv : 2104.04977 [cs.GT].
9. Курокава, Дэвид; Прокачча, Ариэль; Ван, Цзюньсин (2016-02-21). «Когда может быть гарантирована гарантия доли Максимина?». Труды конференции AAAI по искусственному интеллекту . 30 (1). doi : 10.1609/aaai.v30i1.10041 . ISSN  2374-3468. S2CID  7556264.
10. Дикерсон, Джон; Голдман, Джонатан; Карп, Джереми; Прокачча, Ариэль; Сандхолм, Туомас (2014-06-21). «Вычислительный взлет и падение справедливости». Труды конференции AAAI по искусственному интеллекту . 28 (1). doi : 10.1609/aaai.v28i1.8884 . ISSN  2374-3468. S2CID  3178022.
11. Аманатидис, Георгиос; Маркакис, Евангелос; Никзад, Афшин; Сабери, Амин (2017-12-04). «Алгоритмы аппроксимации для вычисления распределения акций по максимину». ACM Transactions on Algorithms . 13 (4): 1–28. arXiv : 1503.00941 . doi : 10.1145/3147173. S2CID  13366555.
12. Бувере, Сильвен; Лемэтр, Мишель (2015). «Характеристика конфликтов при справедливом разделе неделимых благ с использованием шкалы критериев». Автономные агенты и многоагентные системы . 30 (2): 259. doi :10.1007/s10458-015-9287-3. S2CID  16041218.
13. Хаммель, Халвард (2023-02-01). «О нижних границах гарантий акций максимина». arXiv : 2302.00264 [cs.GT].
14. https://www.wisdom.weizmann.ac.il/~feige/mypapers/MMSab.pdf ^{[ пустой URL-адрес PDF ]}
15. Барман, Сиддхарт; Кришнамурти, Санат Кумар (6 марта 2017 г.). «Алгоритмы аппроксимации для разделения ярмарки Максимина». arXiv : 1703.01851 [cs.GT].
16. Барман, Сиддхарт; Кришнамурти, Санат Кумар (2020-03-06). «Алгоритмы аппроксимации для справедливого деления по максимину». ACM Transactions on Economics and Computation . 8 (1): 5:1–5:28. arXiv : 1703.01851 . doi : 10.1145/3381525. ISSN  2167-8375. S2CID  217191332.
17. Годси, Мохаммад; Хаджиагайи, Мохаммадтаги; Седдигин, Масуд; Седдигин, Саид; Ями, Хади (2018-06-11). «Справедливое распределение неделимых благ: улучшения и обобщения». Труды конференции ACM 2018 года по экономике и вычислениям . EC '18. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 539–556. doi :10.1145/3219166.3219238. ISBN 978-1-4503-5829-3. S2CID  450827.
18. Гарг, Джугал; МакГлафлин, Питер; Таки, Сетаре (2018). Файнман, Джереми Т.; Митценмахер, Майкл (ред.). «Приблизительное распределение акций Maximin». 2-й симпозиум по простоте алгоритмов (SOSA 2019) . Серия OpenAccess по информатике (OASIcs). 69 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 20:1–20:11. doi : 10.4230/OASICs.SOSA.2019.20 . ISBN 978-3-95977-099-6.
19. Garg, Jugal; Taki, Setareh (2020-07-13). "Улучшенный алгоритм аппроксимации для максиминных акций". Труды 21-й конференции ACM по экономике и вычислениям . EC '20. Виртуальное мероприятие, Венгрия: Ассоциация вычислительной техники. стр. 379–380. arXiv : 1903.00029 . doi :10.1145/3391403.3399526. ISBN 978-1-4503-7975-5. S2CID  67855844.
20. Акрами, Ханнанех; Гарг, Джугал; Шарма, Эклавья; Таки, Сетарех (2023-03-29). «Упрощение и улучшение аппроксимации MMS». arXiv : 2303.16788 [cs.GT].
21. Фейге, Уриэль; Норкин, Алексей (2022-05-11). «Улучшенное максиминно справедливое распределение неделимых предметов трем агентам». arXiv : 2205.05363 [cs.GT].
22. Акрами, Ханнанех; Мельхорн, Курт; Седдигин, Масуд; Шахкарами, Голнуш (15.12.2023). «Рандомизированные и детерминированные максиминно-долевые аппроксимации для дробно-субаддитивных оценок» (PDF) . Достижения в области нейронных систем обработки информации . 36 : 58821–58832. arXiv : 2308.14545 .
23. Айгнер-Хорев, Элад; Сегал-Халеви, Эрель (2022). «Сочетания без зависти в двудольных графах и их применение к справедливому делению». Информационные науки . 587 : 164–187. arXiv : 1901.09527 . doi : 10.1016/j.ins.2021.11.059. S2CID  170079201.
24. Хоссейни, Хади; Сирнс, Эндрю (2020-12-01). «Гарантирование акций Maximin: некоторые агенты остались позади». arXiv : 2105.09383 [cs.GT].
25. Хоссейни, Хади; Сирнс, Эндрю; Сигал-Халеви, Эрель (19.01.2022). «Порядковая максиминная аппроксимация долей для домашних дел». arXiv : 2201.07424 [cs.GT].
26. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-01). «Необоснованная справедливость максимального благосостояния Нэша» (PDF) . ACM Trans. Econ. Comput . 7 (3): 12:1–12:32. doi :10.1145/3355902. ISSN  2167-8375. S2CID  202729326.
27. Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (2016-05-12). «О правдивых механизмах распределения акций по принципу максимина». arXiv : 1605.04026 [cs.GT].
28. Барман, Сиддхарт; Бисвас, Арпита (2018-04-25). «Справедливое деление при ограничениях мощности». arXiv : 1804.09521 [cs.GT].
29. Хаммель, Халвард; Хетланд, Магнус Ли (14 июня 2021 г.). «Гарантирование полумаксиминных акций при ограничениях на мощность». arXiv : 2106.07300 [cs.GT].
30. Хаммель, Халвард; Хетланд, Магнус Ли (2022). «Справедливое распределение конфликтующих элементов». Автономные агенты и многоагентные системы . 36. arXiv : 2104.06280 . doi :10.1007/s10458-021-09537-3. S2CID  233219836.
31. Бувере, Сильвен; Чехларова, Катарина; Элкинд, Эдит; Игараси, Аюми; Петерс, Доминик (06 июня 2017 г.). «Справедливое деление графа». arXiv : 1705.10239 [cs.GT].
32. Лонц, Збигнев; Трушинский, Мирослав (09.05.2019). «Распределение акций Maximin по циклам». arXiv : 1905.03038 [cs.SI].
33. Азиз, Харис; Раухекер, Герхард; Шрайен, Гвидо; Уолш, Тоби (2016-04-05). «Алгоритмы аппроксимации для распределения максимальных и минимальных долей неделимых задач и товаров». arXiv : 1604.01435 [cs.GT].
34. Хуан, Синь; Лу, Пиньян (2019-07-10). «Алгоритмическая структура для аппроксимации максиминного распределения долей домашних дел». arXiv : 1907.04505 [cs.GT].
35. Кулкарни, Руча; Мехта, Рута; Таки, Сетарех (2021-04-05). «Неделимая смешанная манна: о вычислимости распределений MMS + PO». arXiv : 2007.09133 [cs.GT].
36. Эбадиан, Соруш; Питерс, Доминик; Шах, Нисарг (2022-02-03), Как справедливо распределить легкие и сложные домашние обязанности , arXiv : 2110.11285
37. Ланг, Жером; Роте, Йорг (2016). «Справедливое разделение неделимых благ». В Роте, Йорг (ред.). Экономика и вычисления . Тексты Springer по бизнесу и экономике. Springer Berlin Heidelberg. стр. 493–550. doi :10.1007/978-3-662-47904-9_8. ISBN 9783662479049. {{cite book}}: |journal=проигнорировано ( помощь )
38. Хайнен, Тобиас; Нгуен, Нян-Там; Нгуен, Трунг Тхань; Роте, Йорг (2018-11-01). «Аппроксимация и сложность задач оптимизации и существования для максиминной доли, пропорциональной доли и минимаксной доли распределения неделимых благ». Автономные агенты и многоагентные системы . 32 (6): 741–778. doi :10.1007/s10458-018-9393-0. ISSN  1573-7454. S2CID  49479969.
39. Segal-Halevi, Erel; Suksompong, Warut (2019-12-01). "Демократическое справедливое распределение неделимых благ". Искусственный интеллект . 277 : 103167. arXiv : 1709.02564 . doi :10.1016/j.artint.2019.103167. ISSN  0004-3702. S2CID  203034477.
40. Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (2018-07-13). «Сравнение приблизительных релаксаций свободы от зависти». Труды 27-й Международной совместной конференции по искусственному интеллекту . IJCAI'18. Стокгольм, Швеция: AAAI Press: 42–48. arXiv : 1806.03114 . ISBN 978-0-9992411-2-7.
41. Барман, Сиддхарт; Бисвас, Арпита; Кришнамурти, Санат Кумар; Нарахари, Ю. (20 ноября 2017 г.). «Групповое максимально справедливое распределение неделимых благ». arXiv : 1711.07621 [cs.GT].
42. Фархади, Алиреза; Годси, Мохаммед; Хаджиагайи, Мохаммад Таги; Лаэ, Себастьен; Пеннок, Дэвид; Седдигин, Масуд; Седдигин, Саид; Ями, Хади (07 января 2019 г.). «Справедливое распределение неделимых товаров между асимметричными агентами». Журнал исследований искусственного интеллекта . 64 : 1–20. arXiv : 1703.01649 . дои : 10.1613/jair.1.11291 . ISSN  1076-9757. S2CID  15326855.
43. Бабаиофф, Моше; Нисан, Ноам; Талгам-Коэн, Инбал (2021-01-27). «Конкурентное равновесие с неделимыми товарами и общими бюджетами». Математика исследования операций . 46 (1): 382–403. arXiv : 1703.08150 . doi : 10.1287/moor.2020.1062. ISSN  0364-765X. S2CID  8514018.
44. Сегал-Халеви, Эрель (18 декабря 2019 г.). «Максиминные отношения доминирования». arXiv : 1912.08763 [math.CO].
45. Бабаиофф, Моше; Эзра, Томер; Фейге, Уриэль (2021-06-06). «Справедливое распределение для агентов с произвольными правами». arXiv : 2103.04304 [cs.GT].