Справедливое деление ресурсов: от теории к практике

Введение

Процесс справедливого распределения ресурсов

Разделение торта без зависти – это разновидность справедливого разделения. Это разделение гетерогенного ресурса ("торта"), которое удовлетворяет критерию отсутствия зависти, а именно, каждый участник считает свою долю не хуже любой другой, согласно собственной субъективной оценке. Когда участников всего двое, проблема проста и была решена еще в древности протоколом "разделяй и выбирай". Когда участников три и более, проблема становится значительно сложнее. Были изучены два основных варианта задачи: связанные части, например, если торт представляет собой одномерный интервал, то каждый участник должен получить один подинтервал. Если участников *n*, требуется всего *n-1* разрезов. Общие части, например, если торт представляет собой одномерный интервал, то каждый участник может получить объединение непересекающихся подинтервалов.

Краткая история

Современные исследования проблемы справедливого деления торта начались в 1940-х годах. Первым изученным критерием справедливости было пропорциональное разделение, и вскоре была найдена процедура для n участников. Более строгий критерий отсутствия зависти был введен в задачу деления торта Джорджем Гамоу и Марвином Стерном в 1950-х годах. Процедура для трех участников и произвольных кусков была найдена в 1960 году. Процедура для трех участников и связных кусков была найдена только в 1980 году. Отсутствие зависти при делении между четырьмя или более участниками оставалось открытой проблемой до 1990-х годов, когда были опубликованы три процедуры для произвольных кусков и процедура для связных кусков. Все эти процедуры не ограничены – они могут потребовать количества шагов, которое не ограничено заранее. Процедура для связных кусков может даже потребовать бесконечного числа шагов. В 2000-х годах были опубликованы два нижних ограничения на временную сложность отсутствия зависти. Для произвольных кусков нижняя граница составляет Ω(n2). Для связных кусков нижняя граница – бесконечность, то есть не существует конечного протокола для трех и более участников. В 2010-х годах было опубликовано несколько приближенных процедур и процедур для частных случаев. Вопрос о существовании процедур с ограниченным временем выполнения для случая произвольных кусков оставался открытым в течение долгого времени. Проблема была окончательно решена в 2016 году. Харис Азиз и Саймон Маккензи представили дискретный протокол, требующий не более двух запросов. Между нижней границей и процедурой по-прежнему существует очень большой разрыв. По состоянию на февраль 2024 года точная временная сложность отсутствия зависти все еще неизвестна. Для случая связных кусков было отмечено, что результат о сложности предполагает, что весь торт должен быть разделен. Если это требование заменить более слабым требованием, согласно которому каждый участник получает пропорциональную долю (не менее 1/n от общей стоимости торта, согласно их собственной оценке), то известна ограниченная процедура для трех участников, но остается открытым вопрос о существовании процедур с ограниченным временем выполнения для четырех и более участников.

Modern research into the fair cake cutting problem started in the 1940s. The first fairness criterion studied was proportional division, and a procedure for n partners was soon found. The stronger criterion of envy freeness was introduced into the cake cutting problem by George Gamow and Marvin Stern in 1950s. A procedure for three partners and general pieces was found in 1960. A procedure for three partners and connected pieces was found only in 1980. Envy free division for four or more partners had been an open problem until the 1990s, when three procedures for general pieces and a procedure for connected pieces were published. All these procedures are unbounded they may require a number of steps which is not bounded in advance. The procedure for connected pieces may even require an infinite number of steps. Two lower bounds on the run time complexity of envy freeness were published in the 2000s. For general pieces, the lower bound is Ω(n2). For connected pieces the lower bound is infinity – there is provably no finite protocol for three or more partners. In the 2010s, several approximation procedures and procedures for special cases were published. The question whether bounded time procedures exist for the case of general pieces had remained open for a long time. The problem was finally solved in 2016. Haris Aziz and Simon Mackenzie presented a discrete envy free protocol that requires at most or queries. There is still a very large gap between the lower bound and the procedure. As of Feb 2024, the exact run time complexity of envy freeness is still unknown. For the case of connected pieces, it was noted that the hardness result assumes that the entire cake must be divided. If this requirement is replaced by the weaker requirement that every partner receives a proportional value (at least 1/n of the total cake value according to their own valuation), then a bounded procedure for three partners is known, but it has remained an open problem whether there exist bounded time procedures for four or more partners.

Приближения и частичные решения

Возвращающийся вариант последнего протокола уменьшителя находит аддитивное приближение к разделу без зависти за конечное время. В частности, для каждой константы ε, он возвращает раздел, в котором оценка каждого участника не меньше максимальной оценки минус ε, за время O(1/ε).
Если все функции оценки кусочно-линейны, существует алгоритм, полиномиальный по размеру представления этих функций. Количество запросов к функциям равно N, где N – количество точек разрыва в производных функций плотности оценки.

Результат твердости

Каждая процедура для n человек требует не менее Ω(n²) запросов в модели запросов Робертсона — Уэбба. Доказательство основывается на тщательном анализе объема информации, которой обладает алгоритм о каждом партнере. А. Предположим, что торт представляет собой одномерный интервал [0,1], и что значение всего торта для каждого из партнеров нормализовано до 1. На каждом шаге алгоритм просит определенного партнера либо оценить определенный интервал, содержащийся в [0,1], либо указать значение для определенного интервала. В обоих случаях алгоритм получает информацию только об интервалах, конечные точки которых были упомянуты в запросе или в ответе. Назовем эти конечные точки опорными точками. Изначально единственными опорными точками для i являются 0 и 1, поскольку алгоритм знает о партнере i только то, что vi([0,1]) = 1. Если алгоритм просит партнера i оценить интервал [0.2, 1], то после ответа опорные точки для i станут {0, 0.2, 1}. Алгоритм может вычислить vi([0, 0.2]), но не значение любого интервала, конечная точка которого отличается от 0.2. Количество опорных точек увеличивается не более чем на 2 с каждым запросом. В частности, значение интервала [0, 0.2] может быть сосредоточено полностью около 0, или полностью около 0.2, или где-то между ними. B. Интервал между двумя последовательными опорными точками партнера i называется опорным интервалом партнера i. Когда алгоритм решает выделить кусок торта партнеру i, он должен выделить кусок, суммарное значение которого для i не меньше, чем значение любого опорного интервала i. Доказательство ведется от противного: предположим, что существует опорный интервал J, значение которого для i больше, чем значение, фактически выделенное i. Тогда другой партнер, скажем j, обязательно получит часть опорного интервала J. Согласно пункту A, возможно, что все значение интервала J сосредоточено в доле, выделенной партнеру j. Таким образом, i завидует j, и разделение не является свободным от зависти. C. Предположим, что все партнеры отвечают на все запросы так, как если бы их мера ценности была равномерной (то есть значение интервала равно его длине). Согласно пункту B, алгоритм может назначить кусок партнеру i только в том случае, если он длиннее всех опорных интервалов i. По крайней мере n/2 партнеров должны получить интервал длиной не более 2/n; следовательно, все их опорные интервалы должны иметь длину не более 2/n; следовательно, у них должно быть не менее n/2 опорных интервалов; следовательно, у них должно быть не менее n/2 опорных точек. D. Каждый запрос, на который отвечает партнер i, включает в себя не более двух новых конечных точек, поэтому увеличивает количество опорных точек i не более чем на 2. Следовательно, в случае, описанном в пункте C, алгоритм должен задать каждому из n/2 партнеров не менее n/4 запросов. Таким образом, общее количество запросов составляет не менее n²/8 = Ω(n²).

Every envy free procedure for n people requires at least Ω(n2) queries in the Robertson–Webb query model. The proof relies on a careful analysis of the amount of information the algorithm has on each partner. A. Assume that the cake is the 1 dimensional interval [0,1], and that the value of the entire cake for each of the partners is normalized 1. In each step, the algorithm asks a certain partner either to evaluate a certain interval contained in [0,1], or to mark an interval with a specified value. In both cases, the algorithm gathers information only about intervals whose end points were mentioned in the query or in the reply. Let's call these endpoints landmarks. Initially the only landmarks of i are 0 and 1 since the only thing the algorithm knows about partner i is that vi([0,1])=1. If the algorithm asks partner i to evaluate the interval [0.2,1], then after the reply the landmarks of i are {0,0.2,1}. The algorithm can calculate vi([0,0.2]), but not the value of any interval whose endpoint is different than 0.2. The number of landmarks increases by at most 2 in each query. In particular, the value of the interval [0,0.2] might be concentrated entirely near 0, or entirely near 0.2, or anywhere in between. B. An interval between two consecutive landmarks of partner i is called a landmark interval of partner i, When the algorithm decides to allocate a piece of cake to partner i, it must allocate a piece whose total value for i is at least as large as any landmark interval of i. The proof is by contradiction: suppose there is a certain landmark interval J whose value for i is more than the value actually allocated to i. Some other partner, say j, will necessarily receive some part of the landmark interval J. By paragraph A, it is possible that all the value of interval J is concentrated inside the share allocated to partner j. Thus, i envies j and the division is not envy free. C. Suppose all partners answer all queries as if their value measure is uniform (i. e. the value of an interval is equal to its length). By paragraph B, the algorithm may assign a piece to partner i, only if it is longer than all landmark intervals of i. At least n/2 partners must receive an interval with a length of at most 2/n; hence all their landmark intervals must have a length of at most 2/n; hence they must have at least n/2 landmark intervals; hence they must have at least n/2 landmarks. D. Each query answered by partner i involves at most two new endpoints, so it increases the number of landmarks of i by at most 2. Hence, in the case described by paragraph C, the algorithm must ask each of n/2 partners, at least n/4 queries. The total number of queries is thus at least n2/8 = Ω(n2).

Разделение без зависти с различными правами

Общее обобщение критерия отсутствия зависти заключается в том, что каждый из партнеров имеет разную долю. То есть, для каждого партнера i существует вес wi, описывающий часть торта, на которую он имеет право (сумма всех wi равна 1). Тогда взвешенное деление без зависти определяется следующим образом. Для каждого агента i с функцией оценки Vi и для каждого другого агента j: То есть, каждый партнер считает, что его доля относительно его доли участия не меньше, чем доля любого другого партнера относительно его доли участия. Когда все веса одинаковы (и равны 1/n), это определение сводится к стандартному определению отсутствия зависти. Когда куски могут быть не связными, взвешенное деление без зависти всегда существует и может быть найдено протоколом Робертсона — Уэбба для любого набора весов. Чжэн представил альтернативный алгоритм для приближенного взвешенного деления без зависти, требующий меньшего числа разрезов. Но когда куски должны быть связными, взвешенное деление без зависти может не существовать. Чтобы увидеть это, заметим, что любое взвешенное деление без зависти также является взвешенным пропорциональным делением с тем же вектором весов; это означает, что для каждого агента i с функцией оценки Vi: Известно, что взвешенное пропорциональное деление со связными кусками может не существовать: см. пропорциональное деление торта с разными долями для примера. Обратите внимание, что существует альтернативное определение взвешенного деления без зависти, где веса присваиваются кускам, а не агентам. При этом определении взвешенное деление без зависти известно в следующих случаях (каждый случай обобщает предыдущий): Аддитивные функции оценки, 1-мерный торт (интервал), и куски должны быть связными интервалами. Аддитивные функции оценки, многомерный симплексный торт, и куски должны быть симплексами. В доказательстве используются теорема Спернера, лемма ККМ, лемма Гейла и лемма Кай Фана о точках совпадения.

Разделяем "плохой" торт

В некоторых случаях "пирог", который предстоит разделить, имеет отрицательную ценность. Например, это может быть участок газона, который нужно скосить, или заброшенный участок, который необходимо очистить. Тогда "пирог" представляет собой "неоднородное зло", а не "неоднородное благо". Некоторые процедуры справедливого деления "пирога" без зависти могут быть адаптированы для работы с "плохим пирогом", но такая адаптация часто не является простой. Подробнее см. раздел о справедливом распределении обязанностей без зависти.