Раскол консенсуса

Разделение консенсуса , также называемое точным разделением , ^[1]^: 127 — это разделение непрерывного ресурса (« торта ») на несколько k частей так, что каждый из n людей с разными вкусами сходится во мнении о ценности каждой из частей. Например, рассмотрим торт, наполовину шоколадный, наполовину ванильный. Алиса ценит только шоколад, а Джордж — только ваниль. Торт разделен на три части: одна часть содержит 20% шоколада и 20% ванили, вторая содержит 50% шоколада и 50% ванили, а третья содержит остальную часть торта. Это точное деление (с k = 3 и n = 2), поскольку и Алиса, и Джордж оценивают три части как 20%, 50% и 30% соответственно. Несколько распространенных вариантов и особых случаев известны под разными терминами:

Консенсусное разделение пополам — торт должен быть разделен на две части ( k = 2), и все агенты согласны с тем, что эти части имеют одинаковую ценность. ^[2]
Консенсус 1/ k -division , для любой константы k > 1 – торт должен быть разделен на k частей, и все агенты согласны с тем, что эти части имеют равные значения. ^[2] Другой термин – раскол консенсуса . ^[3]
Идеальное деление – количество кусков равно количеству агентов: торт должен быть разделен на n частей, и все агенты согласны с тем, что все части имеют одинаковую ценность.
$\varepsilon$ -почти точное деление для любой константы $\varepsilon >0$ , агенты могут расходиться во мнениях относительно стоимости фигур, но разница между значениями должна быть не более $\varepsilon$ . Аналогично называются приближенные варианты упомянутых выше задач. $\varepsilon$ -консенсус-деление пополам , $\varepsilon$ -консенсус 1/ k -разделение или $\varepsilon$ - разделение консенсуса и $\varepsilon$ -совершенное деление.
Проблема Нила – агентов бесконечно много.
Разделение ожерелья - ресурс, который нужно разделить, состоит из конечного числа неделимых объектов («бусинок»).

Когда и n , и k конечны, всегда существует консенсусное разделение. Однако они не могут быть найдены дискретными протоколами (с конечным числом запросов). В некоторых случаях точные деления можно найти с помощью протоколов движущегося ножа. Почти точные деления можно найти с помощью дискретных протоколов.

Определения

Позволять $w_{1},w_{2},\ldots ,w_{k}$ быть k весами, сумма которых равна 1. Предположим, что имеется n агентов, каждый из которых оценивает торт C как 1. Мера ценности агента i обозначается через $V_{i}$ . Предполагается, что это неатомарная мера на C . Точное разделение в соотношениях $w_{1},w_{2},\ldots ,w_{k}$ – это разбиение торта на k частей: $C=X_{1}\sqcup \cdots \sqcup X_{k}$ , такой, что для каждого агента i и каждой части j :

V_{i}(X_{j})=w_{j}

Это также называется консенсусным делением , поскольку среди всех агентов существует консенсус в том, что ценность части j в точности равна $w_{j}$ . ^[1]^: 127 Некоторые особые случаи:

Консенсус 1/ k разделение – особый случай, когда $w_{1}=\cdots =w_{n}=1/k$ .
Консенсусное сокращение вдвое – особый случай, при котором $k=2$ и $w_{1}=w_{2}=1/2$ .
Совершенное деление – особый случай, когда $k=n$ и $w_{1}=\cdots =w_{n}=1/n$ .

Почти точное деление

Для каждого $\varepsilon >0$ , Ан $\varepsilon$ -почти точное деление в соотношениях $w_{1},w_{2},\ldots ,w_{k}$ это подразделение, в котором:

|V_{i}(X_{j})-w_{j}|<\varepsilon

То есть среди всех партнеров существует консенсус в том, что ценность части j равна почти в точности $w_{j}$ , где разница меньше $\varepsilon$ . ^[1]^: 127 Некоторые особые случаи:

$\varepsilon$ -консенсус 1/ k деление – особый случай, при котором $w_{1}=\cdots =w_{n}=1/k$ .
$\varepsilon$ -консенсусное сокращение вдвое – особый случай, при котором $k=2$ и $w_{1}=w_{2}=1/2$ .
$\varepsilon$ -совершенное деление – частный случай, при котором $k=n$ и $w_{1}=\cdots =w_{n}=1/n$ .

Существование

Неограниченное количество разрезов

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

Разделите каждый регион на k подрегионов так, чтобы подрегион j содержал ровно $w_{j}$ регионов.
Пусть кусок j представляет собой объединение j -й подобласти во всех R регионах.

Количество необходимых разрезов $k\cdot R$ , где R — количество регионов. Этот алгоритм можно обобщить на кусочно-линейные оценки . ^[4]

Точное деление существует в более общей ситуации, когда агенты имеют счетно-аддитивные неатомарные меры . Это следствие теоремы Дубинса-Спанье о выпуклости (существование консенсусного 1/ k -деления было ранее отмечено Ежи Нейманом). ^[5]). Однако эта теорема ничего не говорит о количестве необходимых разрезов.

Вудалл ^[6] показал, что можно построить точное деление интервального торта как счетное объединение интервалов. Интуиция: рассмотрим описанную выше процедуру деления кусочно-однородных тортов. В целом торт не получается кусочно-однородным. Однако, поскольку меры стоимости непрерывны, можно разделить пирог на все более мелкие регионы, так что регионы становятся все более и более однородными. Когда $R\to \infty$ , этот процесс сводится к консенсусному разделению. Однако количество необходимых разрезов в пределе бесконечно. Позже Фремлин показал, что такое деление можно построить как конечное объединение интервалов.

Ограниченное количество разрезов

Предположим, что торт представляет собой интервал, состоящий из n районов (подинтервалов), и каждый из n партнеров ценит только один район. Тогда для консенсусного разделения торта на k подмножеств требуется $n\cdot (k-1)$ сокращений, так как каждый из районов необходимо разрезать на k частей, равных в глазах партнера, ценящего этот район. Это поднимает вопрос о том, всегда ли существует консенсусное разделение с таким точным количеством сокращений. Этот вопрос широко изучался, уделяя особое внимание одномерному торту (интервалу).

Рассмотрим сначала случай консенсусного деления пополам : $k=2$ и равные веса. Нижняя граница количества разрезов равна $n\cdot (k-1)=n$ . Действительно, всегда существует консенсус пополам с не более чем n сокращениями. ^[7] Это прямое следствие теоремы Хобби–Райса . Это также можно доказать с помощью теоремы Борсука-Улама : ^[8]

Каждое разбиение интервала с помощью $n$ разрезы можно представить в виде вектора длины $n+1$ , в котором элементами являются длины подинтервалов.
Каждый элемент вектора может быть либо положительным (если он принадлежит фрагменту №1), либо отрицательным (если он принадлежит фрагменту №2).
Множество всех разбиений гомеоморфно сфере $S^{n}$ .
Определить функцию $V:S^{n}\to \mathbb {R} ^{n}$ следующим образом: для каждого раздела $x$ , $V(x)$ — вектор, $i$ -й элемент которого равен значению части № 1 в этом разделе в соответствии с партнером $i$ минус 1/2.
Функция $V$ непрерывна. Более того, для $x$ всех $V(x)+V(-x)=0$ .
Следовательно, по теореме Борсука-Улама существует $x$ такой, что $V(x)=0$ . В этом разделе все партнеры оценивают часть №1 (и часть №2) ровно в 1/2.

Хотя предпочтения агентов моделируются с помощью мер, доказательства не требуют, чтобы функции ценности были положительными или аддитивными по подмножествам; это могут быть любые непрерывные функции множества, определенные на сигма-алгебре Бореля. Таким образом, не требуется, чтобы оценки партнеров по подмножествам торта были аддитивно разделимы. ^[2]

Теперь рассмотрим 1/ k случай консенсусного деления : любое k >1 и равные веса. Нога Алон в своей статье 1987 года о проблеме расщепления ожерелья доказал следующий результат. Есть $n$ различные меры на отрезке, абсолютно непрерывные по длине. Размер всего ожерелья по мерке $i$ , является $k\cdot a_{i}$ . Тогда можно разбить интервал на $k$ части (не обязательно смежные), такие, что мера каждой части по мере $i$ , это точно $a_{i}$ . Максимум $(k-1)n$ необходимы сокращения, и это оптимально.

Рассмотрим теперь случай k =2 и произвольные веса. Стромквист и Вудалл ^[9] доказал, что существует точное деление пирога ( круглого пирога), в котором каждый кусок содержит не более n -1 интервалов; не более 2 n следовательно, необходимо -2 разрезов. См. теорему Стромквиста – Вудолла . Количество разрезов по существу оптимально для общих весов. Эту теорему можно применить рекурсивно для получения точного деления для любого k > 1 и любых весов, используя O( nk разрезы ).

Многомерный торт, много партнеров, много подмножеств, равный вес.

Теорема Стоуна-Тьюки утверждает, что, учитывая $n$ измеримых «объектов» в $n$ - мерном пространстве, можно разделить их все пополам (относительно их меры , т. е. объема) с помощью одной $(n - 1)$ -мерной гиперплоскости. .

Другими словами: если торт – это космос $\mathbb {R} ^{n}$ , а меры стоимости партнеров конечны и обращаются в нуль на любом $n-1$ мерная гиперплоскость, то существует полупространство, значение которого равно ровно 1/2 каждому партнеру. Следовательно, существует консенсусное разделение с использованием единого сокращения.

Исходная версия этой теоремы работает только в том случае, если количество размеров торта равно числу партнеров. Например, невозможно использовать эту теорему для разделения трехмерного сэндвича на 4 или более партнеров.

Однако существуют обобщения, допускающие такое разделение. Они используют не гиперплоский нож, а более сложную полиномиальную поверхность. ^[10]

Существуют также дискретные адаптации этих многомерных результатов. ^[11]

Вычисление точных делений

Невозможность использования дискретных процедур

Невозможно вычислить точное деление при конечном числе запросов, даже если агентов всего n =2 и частей k =2, веса равны 1/2. ^[1]^{: 103–104} Это означает, что лучшее, чего мы можем достичь с помощью дискретного алгоритма, — это почти точное деление.

Доказательство : когда протокол находится на шаге k , он имеет коллекцию, состоящую не более чем из k частей. Чтобы обеспечить точное деление, протокол должен найти точное подмножество – подмножество частей, которое оба партнера оценивают ровно как 1/2. Мы собираемся доказать, что для каждого k существуют ситуации, в которых на шаге k нет точного подмножества, и, следовательно, протокол, возможно, придется продолжать бесконечно.

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

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

Общее количество различных подмножеств теперь равно 2 ^к, и по предположению индукции ни один из них не является точным. На шаге k протокол может попросить Алису или Джорджа разрезать определенный кусок на две части. Предположим, что резчиком является Джордж и что он разрезает кусок X на две части: X1 и X2. Теперь общее количество подмножеств равно 2. ^{к +1}: половина из них уже существовала и, по предположению, они неточны, поэтому единственный шанс протокола найти точное подмножество — это просмотреть новые подмножества. Каждое новое подмножество состоит из старого подмножества, в котором деталь X заменена на X1 или X2. Поскольку Джордж является резчиком, он может разрезать так, чтобы одно из этих подмножеств стало для него точным подмножеством (например, если определенное подмножество, содержащее кусок X, имело ценность 3/4, Джордж может разрезать X так, что X1 имел значение по его мнению, 1/4, так что новое подмножество имеет значение ровно 1/2). Но Джордж не знает оценки Алисы и не может ее учесть при резке. Следовательно, существует несчетное множество различных значений, которые могут иметь для Алисы кусочки Х1 и Х2. Поскольку число новых подмножеств конечно, существует бесконечное число случаев, когда ни одно новое подмножество не имеет значения 1/2 для Алисы, следовательно, ни одно новое подмножество не является точным.

Процедуры с подвижным ножом

Два агента могут достичь консенсусного разделения, используя процедуру «движущегося ножа» Остина .

Самый простой случай — когда веса равны 1/2, т. е. они хотят отрезать кусок, который, по их мнению, будет составлять половину стоимости торта. Это делается следующим образом. Один агент перемещает два ножа по торту слева направо, всегда сохраняя соотношение между ножами ровно 1/2. Можно доказать (по теореме о промежуточной стоимости ), что в какой-то момент ценность куска между ножами для другого партнера также будет равна ровно 1/2. Другой агент кричит «Стоп!» в этот момент кусок разрезается.

Тот же протокол можно использовать для того, чтобы отрезать кусок, значение которого, по мнению обоих агентов, точно равно $1/n$ . Объединив несколько таких кусочков, можно добиться консенсусного деления с любыми соотношениями, являющимися рациональными числами. Но для этого может потребоваться большое количество разрезов.

Лучший способ добиться консенсусного разделения — определить две конечные точки торта и рассматривать его как круг. Т.е. когда правый нож попадает на правую сторону, он сразу уходит на левую сторону, и кусок между ножами теперь фактически является объединением куска справа от правого ножа и куска слева. левого ножа. Таким образом, можно найти консенсусное разделение для каждого $p\in [0,1]$ . Один агент циклически перемещает ножи вокруг торта, всегда сохраняя значение между ними ровно на уровне p . Можно доказать, что в какой-то момент ценность фигуры между ножами для другого партнера также будет равна ровно p . ^[12] Другой агент кричит «Стоп!» в этот момент кусок разрезается. Для этого потребуется всего два разреза.

Повторно применяя описанную выше процедуру, можно добиться консенсусного разделения между n =2 партнерами и любыми k >1 подмножествами. Количество разрезов $2(k-1)$ .

По состоянию на 2015 год не существует известного обобщения этой процедуры движущегося ножа на n >2 агентов. ^[13]

Вычисление почти точных делений с неограниченным количеством разрезов

Процедура измельчения и упаковки

Для любого данного $\varepsilon >0$ , можно дать каждому партнеру кусок так, чтобы все партнеры считали, что их ценности различаются менее чем $\varepsilon$ , т. е. для каждого i и каждого j : ^[1]^: 127

|V_{i}(X_{j})-w_{j}|<\varepsilon

Процедура почти точного деления состоит из двух этапов: измельчения и упаковки .

Шаг измельчения : цель состоит в том, чтобы разрезать торт на крошечные кусочки («крошки») так, чтобы каждый партнер присвоил каждой крошке достаточно маленькое значение. Это делается следующим образом. Пусть k — некоторая константа. Попросите партнера №1 разрезать торт на k частей, которые он оценивает как 1/ k . Попросите партнера №2 обрезать куски по мере необходимости (используя не более k -1 разрезов) так, чтобы каждый кусок имел ценность не более 1/ k . Эти новые фигуры, конечно, по-прежнему имеют ценность не более 1/ k для партнера №1. Продолжайте с партнерами №3, №4, …, №n . Наконец, все n партнеров оценивают каждую полученную крошку не более чем в 1/ k .

Шаг упаковки : цель здесь — разделить крошки на n подмножеств так, чтобы сумма значений в каждом подмножестве j была близка к w _j . Вот интуитивное объяснение этапа упаковки для двух партнеров (Алисы и Джорджа), когда веса равны 1/2. ^[1]^: 68–71

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

По индукции можно доказать, что разница в оценке чаши между Алисой и Джорджем всегда не превышает 1/ k . Следовательно, когда один из партнеров получает чашу, ее ценность для обоих партнеров составляет от 1/2-1/ k до 1/2+1/ k .

Формально каждую часть можно представить как вектор значений, по одному на каждого партнера. Длина каждого вектора ограничена, т.е. для каждого такого вектора v : $||v||\leq {\sqrt {n}}/k$ . Наша цель — создать для каждого партнера j вектор, все элементы которого находятся рядом с w _j . Для этого нам нужно разделить векторы на подмножества так, чтобы сумма векторов в каждом подмножестве j была достаточно близка к вектору, все элементы которого равны w _j . Это возможно благодаря теореме В.Бергстрема: ^[14]^[1]^{: 126–128}

Процедура Crumb-and-Pack — это подпрограмма протокола Робертсона-Уэбба . Последний протокол генерирует деление, которое одновременно является почти точным и не вызывает зависти .

Другое объяснение процедуры «крошки и упаковки» дают Брэмс и Тейлор. ^[15]

Вычисление почти точных делений с ограниченным количеством разрезов

Большинство результатов для ограниченного числа разрезов относятся к случаю, когда веса равны.

Два подмножества (консенсусное сокращение вдвое)

ε - приблизительное консенсусное сокращение пополам можно вычислить с помощью алгоритма, основанного на лемме Такера , которая является дискретной версией теоремы Борсука-Улама . ^[2] Адаптация этого алгоритма показывает, что проблема находится в классе сложности PPA . ^[16] Это справедливо даже для произвольных ограниченных и неатомарных нормирований. Однако время выполнения этого алгоритма может быть экспоненциальным по параметрам задачи. Фактически, консенсусное сокращение вдвое является вычислительно сложным в нескольких отношениях.

Во-первых, предположим, что ε может быть обратно-экспоненциальной по n (т. е. 1/ ε является экспоненциальной функцией от n ). Тогда найти ε -приблизительное консенсусное сокращение вдвое будет PPA-сложно . Твердость сохраняется даже при следующих дополнительных условиях: ^[16]

Агенты имеют кусочно-постоянные оценки . Входные данные задачи содержат для каждого агента конечные точки и значения его кусочно-постоянной оценки; и все числа (включая точность аппроксимации ε ) представлены в двоичном формате .

Число частей в кусочно-постоянных оценках полиномиально по n (сами значения могут быть экспоненциальными по n ).
Коэффициент аппроксимации ε может быть обратным полиномом от n . ^[17]
Оценки агентов кусочно-равномерны только с двумя блоками (Однако, когда агенты имеют кусочно-равномерные оценки с одним блоком, задача может быть решена за параметризованно-полиномиальное время для n разрезов и за полиномиальное время для 2 n - d разрезы для любой константы d) . ^[18]
Количество агентов постоянно и не менее 3 (однако с двумя агентами задачу можно решить за полиномиальное время). ^[19]

Далее предположим, что ε — константа (не зависит от n ). Тогда найти ε- приблизительное консенсусное сокращение вдвое будет PPAD-трудно , что теоретически слабее, чем PPA-трудно. Доказательство основано на ε -приближенной задаче обобщенной схемы . Твердость сохраняется даже в следующих условиях:

Оценки кусочно-постоянны;
Разрешено использовать постоянное количество дополнительных сокращений (то есть мы ищем консенсусное сокращение пополам для n агентов с помощью n + d сокращений, для некоторой константы d ). ^[20]
Когда ε является константой, остается открытым вопрос о том, является ли ε -приблизительное консенсусное разделение пополам PPA-жестким (что сильнее, чем PPAD-hard) . ^[16]
Кроме того, решить, существует ли ε -приблизительное консенсусное разделение пополам с n -1 разрезами, NP-трудно, даже если ε является константой. Доказательство проводится путем сокращения из 3SAT . ^[20]

Когда ε является константой, два типа аппроксимации могут быть вычислены за полиномиальное время. Алгоритмы работают для общих аддитивных оценок (не обязательно кусочно-постоянных); Доступ к оценкам осуществляется с помощью запросов в модели запросов Робертсона-Уэбба , включая mark -запрос к сумме всех n оценок. ^[3] Могут быть достигнуты следующие приближения:

Нахождение раздела, в котором каждый агент оценивает каждую часть не менее 1/ 2n , используя $n$ порезы.
Нахождение раздела, в котором каждый агент оценивает каждую часть в 1/2 ± ε , используя $O((n\log {n})/(\varepsilon ^{2}))$ $O((n\log {n})/(\varepsilon ^{2}))$ сокращения в онлайн-алгоритме или с помощью $n\cdot \lceil 2+\log _{2}(1/\epsilon )\rceil$ $n\cdot \lceil 2+\log _ {2}(1/\epsilon)\rceil$ сокращения в автономном алгоритме .
- Обратите внимание, что существует разрыв между PPAD-трудностью для n + d разрезов для любой константы d и алгоритмом с полиномиальным временем для 2 n +O(log( ε)).

Когда ε является постоянным или обратным полиномом от n , ε -приблизительное консенсусное разделение пополам вычислительно эквивалентно проблеме разделения ожерелья - каждое из них можно свести к другому за полиномиальное время (это означает, что разделение ожерелья сложно PPAD). ^[16]
Если мы заинтересованы в поиске точного решения, то консенсусное разделение пополам гораздо сложнее: найти решение с n разрезами сложно с помощью FIXP, а определить, существует ли решение с разрезами с n -1, является ETR-полным. ^[21]
Когда оценки агентов представлены алгебраическими схемами , ε -приблизительное консенсусное разделение пополам эквивалентно за полиномиальное время вычислению приближения к точному решению задачи поиска Борсука-Улама. Это означает, что он является полным для класса сложности BU – суперкласса FIXP , который включает в себя решения задач, существование которых гарантируется теоремой Борсука-Улама. ^[22]

Когда ресурс, который нужно разделить, — это не пирог, а набор делимых ресурсов, проблема становится проще: ^[23]

Для агентов с аддитивными утилитами существует алгоритм с полиномиальным временем для вычисления консенсусного деления пополам с не более чем n разрезами, а также для вычисления консенсусного k -деления с не более чем ( k -1) n разрезами.
Вычислить консенсусное сокращение пополам с оптимальным количеством сокращений для данного экземпляра NP-трудно. Более того, NP-трудно вычислить консенсусное сокращение пополам с использованием не более OPT+ n -1 сокращений, где OPT — оптимальное количество сокращений для данного экземпляра.
n Сокращения почти наверняка необходимы для достижения консенсуса в два раза, когда полезности агентов рассчитываются из вероятностного распределения.
Для агентов с неаддитивными монотонными утилитами консенсусное сокращение пополам по-прежнему сложно с точки зрения PPAD, но существуют алгоритмы с полиномиальным временем для фиксированного числа агентов.

Множество подмножеств (консенсус 1/k-деление)

С вычислительной точки зрения о вычислении точного деления на $(k-1)n$ сокращения для $k\geq 3$ . Обратите внимание, что задача не обязательно сложнее, чем для $k\geq 2$ , так как нам разрешено использовать большее количество разрезов. На данный момент известно следующее:

Проблема в PPA- k для любого k . ^[24]
Задача является PPA-сложной для k =3, когда 1/ ε может быть экспоненциальной функцией от n. ^[18]

Два типа аппроксимации могут быть вычислены с использованием полиномиального числа запросов Робертсона-Уэбба : ^[3]

Нахождение раздела, в котором каждый агент оценивает каждую часть не менее 1/ kn , используя $(k-1)n$ $(k-1)n$ сокращения в онлайн-алгоритме .
- 1/ кн Вопрос о том, можно ли улучшить , остается открытым. В частности, остается открытым вопрос, существует ли эффективный (онлайн или офлайн) алгоритм, такой, что каждый агент оценивает каждую часть как минимум 1/ c ( k ), где c(k) — некоторая функция от k (независимая от n ), используя $(k-1)n$ порезы.
Нахождение разделения такого, что каждый агент оценивает каждую часть в 1/ k ± ε , используя $O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})$ $O({\frac {kn\log {(kn)}}{\varepsilon ^{2}}})$ сокращения в онлайн-алгоритме или с помощью $n\cdot (k-1)\cdot \lceil 2+\log _{2}(3k/\epsilon )\rceil$ $n\cdot (k-1)\cdot \lceil 2+\log _ {2}(3k/\epsilon)\rceil$ порезы. ^[3]^{: Раздел 6}
- Вопрос о том, можно ли улучшить количество сокращений, остается открытым. Для онлайн-алгоритмов нижняя граница количества разрезов для k = 2 равна $O({\frac {n}{\varepsilon ^{2}}})$ , поэтому существует логарифмический разрыв.

Результаты вычислений для ε -приблизительного консенсусного деления пополам для n агентов
#кусочки к	# агентов n	Точность 1/ ε	# сокращений	оценки	Статус
2	$n$	$O({\text{poly}}(n))$	$n$	любой непрерывный	В ППА. ^[2]^[20]
2	$n$	$\Omega (1)$	$n+d$ , $d\geq 0$	кусочно-постоянный	PPAD-жесткий; ^[20] Открыт ли PPA-хард.
2	$n$	$\Omega ({\text{poly}}(n))$	$n+n^{1-d}$ , $d>0$	кусочно-равномерный с 2 блоками	PPA-жесткий. ^[18] _{(PPAD-жесткий ^[20];} _{PPA-трудно для $\varepsilon \in \Omega (2^{n})$ ; ^[16]} _{PPA-hard для кусочно-постоянных оценок ^[17]).}
2	$n$	$O({\text{poly}}(n))$	$n$	кусочно-равномерный с 1 блоком	Параметризованный полином. ^[18]
2	$n$	$O({\text{poly}}(n))$	$2n-d$ , $d\geq 0$	кусочно-равномерный с 1 блоком	Полиномиальный. ^[18]
2	$n$	$\Omega (1)$	$n-1$	кусочно-постоянный	НП-трудно определиться с существованием. ^[20]
2	$n$	$\Omega (1)$	$2n$	кусочно-постоянный	Открыть. ^[20]
2	$n$	?	$n$	алгебраические схемы	Сильная аппроксимация BU _a -полна. ^[22]
2	$n$	∞ [Точный]	$n$	алгебраические схемы	FIXP-жесткий. ^[21]
2	$n$	∞ [Точный]	$n-1$	алгебраические схемы	ETR-полный, чтобы решить существование. ^[21]
н исправлено:
2	2	$O({\text{poly}}(n))$	$n$	монотонный	Полиномиальный; Полиномиальные #запросы. ^[19]
2	3	$O({\text{poly}}(n))$	$n$	монотонный	PPA-жесткий; По крайней мере, экспоненциальные #запросы. ^[19]
2	2	$O({\text{poly}}(n))$	$n$	общий	PPA-жесткий; По крайней мере, экспоненциальные #запросы. ^[19]
к > 2:
3	$n$	$O({\text{poly}}(n))$	$2n$	кусочно-постоянный	PPAD-жесткий. ^[18]
основная власть	$n$	$O({\text{poly}}(n))$	$(k-1)n$	кусочно-постоянный	В ППА- к . ^[24]

Сравнение с другими критериями

Точное деление с равными весами ( $1/n$ ) является, в частности, также пропорциональным , свободным от зависти и справедливым . Однако это не обязательно эффективно по Парето , поскольку во многих случаях можно воспользоваться субъективными оценками и разделить ресурсы так, что все партнеры получат больше, чем им справедливая доля. $1/n$ .

Точное разделение с разными весами не обязательно справедливо. Возвращаясь к первому примеру, если 20%-ная часть отдается Алисе, а две другие части (50% и 30%) отдаются Джорджу, это явно несправедливо по отношению к Алисе. Но такие деления можно использовать как подпрограммы для честного разрезания торта .

Единогласная пропорциональность

В проблеме разрезания торта среди семей , ^[25] имеется n агентов, сгруппированных в k семейств; Цель состоит в том, чтобы разделить торт на k частей и распределить по одному куску на семью. Естественным критерием справедливости в этой ситуации является единогласная пропорциональность , что означает, что все члены всех семей оценивают долю своей семьи как минимум 1/ k (другие критерии и связанные с ними проблемы см. в разделе справедливое разделение между группами ). Задача эквивалентна точному делению в следующем смысле:

Для каждых n и k решение единогласно-пропорционального деления среди n ( k -1)+1 агентов, сгруппированных в k семей, подразумевает решение точного разделения между n агентами с k частями (и равными весами). В частности, это означает, что единогласно-пропорциональное разделение требует как минимум n -1 сокращений и что найти приблизительное единогласно-пропорциональное разделение сложно по PPA.
Для каждых n и k решение точного разделения между n агентами и k частями подразумевает решение единогласно-пропорционального разделения между n+1 агентами, сгруппированными в k семейств. В частности, это означает, что точное единогласно-пропорциональное деление может быть выполнено с помощью ( n -1)( k -1) сокращений и что нахождение приблизительного единогласно-пропорционального деления находится в PPA. Число разрезов ограничено для k семейств =2, но не для k >2. ^[25]

Правдивые механизмы

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

Самый простой механизм правдивого дележа: выберите случайным образом одного партнера (с вероятностью, определяемой весами) и отдайте ему весь торт. Этот механизм тривиально правдив, поскольку не задает вопросов. Более того, это консенсус в ожидании: ожидаемая ценность каждого партнера равна именно его весу, и это справедливо по всем меркам ценности. Однако возникающее в результате разделение, конечно, не является консенсусным разделением.

Более правдивый механизм, работающий в случае, когда все веса равны 1/ n , может быть построен на основе любого существующего алгоритма (или оракула) для поиска консенсусного деления:

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

Здесь ожидаемая ценность каждого партнера по-прежнему равна 1/ n независимо от заявленной функции значения, поэтому механизм по-прежнему правдив – ни один партнер не может ничего получить от лжи. Более того, правдивому партнеру гарантировано значение ровно 1/ n с вероятностью 1 (не только в ожидании). Следовательно, у партнеров появляется стимул раскрыть свои истинные ценностные функции.

Читайте также: Правдивое разрезание торта .

Сводная таблица

Имя	Тип	Торт	оценки ^[27]	#партнеры ( $н$ )	#подмножества ( $к$ )	#порезы	гири
Остин	Процедура с подвижным ножом	Интервал	С	2	Много	$2(k-1)$ (оптимально)	Любой
Кусочно-однородный	Дискретная процедура	Кусочно-однородный	С+Добавить+Pwl	Много	Много	Число. районов	Любой
Дубинс – Испанцы	Доказательство существования	Любой	Кон+Добавить	Много	Много	Неограниченный	Любой
Консенсус-деление пополам	Бесконечная процедура	Интервал	С	Много	2	$н$ (оптимально)	Равный
Расщепление ожерелья	Доказательство существования	Интервал	Мин(+Добавить?)	Много	Много	$n(k-1)$ (оптимально)	Равный
Стромквист Вудалл	Доказательство существования	Круг	Кон+Добавить	Много	2	$2n-2$ (оптимально для некоторых весов)	Любой
Стоун-Тьюки	Доказательство существования	$n$ -мерный	Мин(+Добавить?)	$н$	2	1 полуплоскость	Равный
Крошка и упаковка	Почти точная процедура	Любой	Кон+Добавить	Много	Много	Неограниченный	Любой

См. также

Проблема Нила

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .
^ Jump up to: ^а ^б ^с ^д ^и Симмонс, Форест В.; Су, Фрэнсис Эдвард (2003). «Разделение половины консенсуса с помощью теорем Борсука-Улама и Такера». Математические социальные науки . 45 : 15–25. CiteSeerX 10.1.1.203.1189 . дои : 10.1016/S0165-4896(02)00087-2 .
^ Jump up to: ^а ^б ^с ^д Алон, Нога ; Граур, Андрей (30 июня 2020 г.). «Эффективное разделение мер и ожерелья». arXiv : 2006.16613 [ cs.DS ].
^ Jump up to: ^а ^б Чен, Илин ; Лай, Джон К.; Паркс, Дэвид К.; Прокачча, Ариэль Д. (2013). «Правда, справедливость и разрезание торта» . Игры и экономическое поведение . 77 (1): 284–297. дои : 10.1016/j.geb.2012.10.009 . S2CID 2096977 .
^ Нейман, Ежи (январь 1946 г.). «Теорема существования». Известия Академии наук . 222 : 843–845.
^ Вудалл, ДР (1980). «Деление торта по справедливости» . Журнал математического анализа и приложений . 78 : 233–247. дои : 10.1016/0022-247x(80)90225-5 .
^ Голдберг, Чарльз Х.; Уэст, Дуглас Б. (1985). «Деление раскрасок круга пополам». SIAM Journal по алгебраическим и дискретным методам . 6 : 93–106. дои : 10.1137/0606010 .
^ Алон, Нога; Уэст, Дуглас Б. (1986). «Теорема Борсука-Улама и деление ожерелья пополам» (PDF) . Труды Американского математического общества . 98 (4): 623. doi : 10.1090/s0002-9939-1986-0861764-9 .
^ Стромквист, Уолтер; Вудалл, ДР (1985). «Наборы, по которым согласуются несколько мер». Журнал математического анализа и приложений . 108 : 241–248. дои : 10.1016/0022-247x(85)90021-6 .
^ Б. Грюнбаум (1960). «Разбиения массораспределений и выпуклых тел гиперплоскостями» . Пасифик Дж. Математика . 10 (4): 1257–1261. дои : 10.2140/pjm.1960.10.1257 . МР 0124818 .
^ де Лонгвиль, Марк; Живальевич, Раде Т. (2008). «Расщепление многомерных ожерелий» . Достижения в математике . 218 (3): 926–939. arXiv : math/0610800 . дои : 10.1016/j.aim.2008.02.003 .
^ Фишер, Дэниел. «Консенсусное разделение торта на двоих в произвольных пропорциях» . Математика.SE . Проверено 23 июня 2015 г.
^ Существует обобщение, которое дает каждому из n партнеров кусок, стоящий ровно $1/n$ для него. Но это не консенсусное разделение, потому что партнеры могут не прийти к согласию относительно ценности других частей, помимо той, которая им выделена. См. процедуры Остина с использованием движущегося ножа#Множество партнеров .
^ В. Бергстрем (1930). «Две теоремы о плоских векторных многоугольниках». Гамбургские трактаты . 8 :205-219.
^ Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение [ От разрезания торта до разрешения споров ]. Издательство Кембриджского университета. стр. 131–133. ISBN 978-0-521-55644-6 .
^ Jump up to: ^а ^б ^с ^д ^и Филос-Рацикас, Арис; Голдберг, Пол В. (20 июня 2018 г.). «Консенсусное сокращение вдвое является PPA-полным» . Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений . STOC 2018. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 51–64. arXiv : 1711.04503 . дои : 10.1145/3188745.3188880 . ISBN 978-1-4503-5559-9 . S2CID 8111195 .
^ Jump up to: ^а ^б Филос-Рацикас, Арис; Голдберг, Пол В. (23 июня 2019 г.). «Сложность разделения ожерелья и разрезания бутербродов с ветчиной пополам» . Материалы 51-го ежегодного симпозиума ACM SIGACT по теории вычислений . STOC 2019. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 638–649. дои : 10.1145/3313276.3316334 . ISBN 978-1-4503-6705-9 . S2CID 44085263 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Филос-Рацикас, Арис; Холлендер, Александрос; Сотираки, Катерина; Зампетакис, Манолис (13 июля 2020 г.). «Халвинг консенсуса: бывает ли когда-нибудь проще?» . Материалы 21-й конференции ACM по экономике и вычислениям . ЕС '20. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 381–399. arXiv : 2002.11437 . дои : 10.1145/3391403.3399527 . hdl : 1721.1/146185 . ISBN 978-1-4503-7975-5 . S2CID 211505917 .
^ Jump up to: ^а ^б ^с ^д Делигкас, Аргириос; Филос-Рацикас, Арис; Холлендер, Александрос (18 июля 2021 г.). «Компания двоих, толпа троих: сокращение консенсуса вдвое для постоянного числа агентов» . Материалы 22-й конференции ACM по экономике и вычислениям . ЭК '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 347–368. arXiv : 2007.15125 . дои : 10.1145/3465456.3467625 . hdl : 20.500.11820/f92c933a-c6bd-4f93-b56f-de38970860e7 . ISBN 978-1-4503-8554-1 . S2CID 220871193 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Филос-Рацикас, Арис; Фредериксен, Сорен Кристоффер Стейл; Голдберг, Пол В.; Чжан, Цзе (08 августа 2018 г.). «Результаты твердости для консенсусного сокращения вдвое». arXiv : 1609.05136 [ cs.GT ].
^ Jump up to: ^а ^б ^с Делигкас, Аргириос; Фернли, Джон; Мелиссург, Фемистоклис; Спиракис, Пол Г. (1 мая 2021 г.). «Вычисление точных решений консенсусного деления пополам и теоремы Борсука-Улама» . Журнал компьютерных и системных наук . 117 : 75–98. arXiv : 1903.03101 . дои : 10.1016/j.jcss.2020.10.006 . ISSN 0022-0000 . S2CID 228908526 .
^ Jump up to: ^а ^б Бациу, Элени; Хансен, Кристоффер Арнсфельт; Хёг, Каспер (07 марта 2021 г.). «Сильный приближенный консенсус пополам и теорема Борсука-Улама». arXiv : 2103.04452 [ cs.GT ].
^ Голдберг, Пол В.; Холлендер, Александрос; Игараси, Аюми; Мануранси, Пасин; Суксомпонг, Варут (2022 г.). «Консенсусное сокращение вдвое наборов предметов». Математика исследования операций . 47 (4): 3357–3379. arXiv : 2007.06754 . дои : 10.1287/moor.2021.1249 . S2CID 246764981 .
^ Jump up to: ^а ^б Филос-Рацикас, Арис; Холлендер, Александрос; Сотираки, Катерина; Зампетакис, Манолис (01.01.2021), «Топологическая характеристика аргументов по модулю-p и последствия для разделения ожерелья», Труды симпозиума ACM-SIAM 2021 года по дискретным алгоритмам (SODA) , Труды, Общество промышленной и прикладной математики , стр. 2615–2634, doi : 10.1137/1.9781611976465.155 , ISBN 978-1-61197-646-5 , S2CID 214667000
^ Jump up to: ^а ^б Сегал-Халеви, Эрель; Ницан, Шмуэль (01 декабря 2019 г.). «Ярмарка разрезания торта среди семей» . Социальный выбор и благосостояние . 53 (4): 709–740. arXiv : 1510.03903 . дои : 10.1007/s00355-019-01210-9 . ISSN 1432-217X . S2CID 1602396 .
^ Моссель, Эльханан; Тамуз, Омер (2010). «Правдиво-честный отдел». Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 6386. стр. 288–299. arXiv : 1003.5480 . дои : 10.1007/978-3-642-16170-4_25 . ISBN 978-3-642-16169-8 . S2CID 11732339 .
^ Предпосылки по ценностным функциям партнеров. Меньшее количество предварительных условий означает, что результат является более общим. Con=Continious является наиболее общим; Con+Add=Добавка менее общая; Con+Add+Pwl=Кусочно-линейный вариант является наименее общим.

[rw98-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .

[SimmonsSu03-2] Jump up to: ^а ^б ^с ^д ^и Симмонс, Форест В.; Су, Фрэнсис Эдвард (2003). «Разделение половины консенсуса с помощью теорем Борсука-Улама и Такера». Математические социальные науки . 45 : 15–25. CiteSeerX 10.1.1.203.1189 . дои : 10.1016/S0165-4896(02)00087-2 .

[:8-3] Jump up to: ^а ^б ^с ^д Алон, Нога ; Граур, Андрей (30 июня 2020 г.). «Эффективное разделение мер и ожерелья». arXiv : 2006.16613 [ cs.DS ].

[clpp13-4] Jump up to: ^а ^б Чен, Илин ; Лай, Джон К.; Паркс, Дэвид К.; Прокачча, Ариэль Д. (2013). «Правда, справедливость и разрезание торта» . Игры и экономическое поведение . 77 (1): 284–297. дои : 10.1016/j.geb.2012.10.009 . S2CID 2096977 .

[5] Нейман, Ежи (январь 1946 г.). «Теорема существования». Известия Академии наук . 222 : 843–845.

[woodall80-6] Вудалл, ДР (1980). «Деление торта по справедливости» . Журнал математического анализа и приложений . 78 : 233–247. дои : 10.1016/0022-247x(80)90225-5 .

[goldbergwest85-7] Голдберг, Чарльз Х.; Уэст, Дуглас Б. (1985). «Деление раскрасок круга пополам». SIAM Journal по алгебраическим и дискретным методам . 6 : 93–106. дои : 10.1137/0606010 .

[alonwest86-8] Алон, Нога; Уэст, Дуглас Б. (1986). «Теорема Борсука-Улама и деление ожерелья пополам» (PDF) . Труды Американского математического общества . 98 (4): 623. doi : 10.1090/s0002-9939-1986-0861764-9 .

[stromquistwoodall85-9] Стромквист, Уолтер; Вудалл, ДР (1985). «Наборы, по которым согласуются несколько мер». Журнал математического анализа и приложений . 108 : 241–248. дои : 10.1016/0022-247x(85)90021-6 .

[10] Б. Грюнбаум (1960). «Разбиения массораспределений и выпуклых тел гиперплоскостями» . Пасифик Дж. Математика . 10 (4): 1257–1261. дои : 10.2140/pjm.1960.10.1257 . МР 0124818 .

[11] де Лонгвиль, Марк; Живальевич, Раде Т. (2008). «Расщепление многомерных ожерелий» . Достижения в математике . 218 (3): 926–939. arXiv : math/0610800 . дои : 10.1016/j.aim.2008.02.003 .

[12] Фишер, Дэниел. «Консенсусное разделение торта на двоих в произвольных пропорциях» . Математика.SE . Проверено 23 июня 2015 г.

[13] Существует обобщение, которое дает каждому из n партнеров кусок, стоящий ровно $1/n$ для него. Но это не консенсусное разделение, потому что партнеры могут не прийти к согласию относительно ценности других частей, помимо той, которая им выделена. См. процедуры Остина с использованием движущегося ножа#Множество партнеров .

[14] В. Бергстрем (1930). «Две теоремы о плоских векторных многоугольниках». Гамбургские трактаты . 8 :205-219.

[bramstaylor131-15] Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение [ От разрезания торта до разрешения споров ]. Издательство Кембриджского университета. стр. 131–133. ISBN 978-0-521-55644-6 .

[:1-16] Jump up to: ^а ^б ^с ^д ^и Филос-Рацикас, Арис; Голдберг, Пол В. (20 июня 2018 г.). «Консенсусное сокращение вдвое является PPA-полным» . Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений . STOC 2018. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 51–64. arXiv : 1711.04503 . дои : 10.1145/3188745.3188880 . ISBN 978-1-4503-5559-9 . S2CID 8111195 .

[:4-17] Jump up to: ^а ^б Филос-Рацикас, Арис; Голдберг, Пол В. (23 июня 2019 г.). «Сложность разделения ожерелья и разрезания бутербродов с ветчиной пополам» . Материалы 51-го ежегодного симпозиума ACM SIGACT по теории вычислений . STOC 2019. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 638–649. дои : 10.1145/3313276.3316334 . ISBN 978-1-4503-6705-9 . S2CID 44085263 .

[:6-18] Jump up to: ^а ^б ^с ^д ^и ^ж Филос-Рацикас, Арис; Холлендер, Александрос; Сотираки, Катерина; Зампетакис, Манолис (13 июля 2020 г.). «Халвинг консенсуса: бывает ли когда-нибудь проще?» . Материалы 21-й конференции ACM по экономике и вычислениям . ЕС '20. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 381–399. arXiv : 2002.11437 . дои : 10.1145/3391403.3399527 . hdl : 1721.1/146185 . ISBN 978-1-4503-7975-5 . S2CID 211505917 .

[:5-19] Jump up to: ^а ^б ^с ^д Делигкас, Аргириос; Филос-Рацикас, Арис; Холлендер, Александрос (18 июля 2021 г.). «Компания двоих, толпа троих: сокращение консенсуса вдвое для постоянного числа агентов» . Материалы 22-й конференции ACM по экономике и вычислениям . ЭК '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 347–368. arXiv : 2007.15125 . дои : 10.1145/3465456.3467625 . hdl : 20.500.11820/f92c933a-c6bd-4f93-b56f-de38970860e7 . ISBN 978-1-4503-8554-1 . S2CID 220871193 .

[:0-20] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Филос-Рацикас, Арис; Фредериксен, Сорен Кристоффер Стейл; Голдберг, Пол В.; Чжан, Цзе (08 августа 2018 г.). «Результаты твердости для консенсусного сокращения вдвое». arXiv : 1609.05136 [ cs.GT ].

[:3-21] Jump up to: ^а ^б ^с Делигкас, Аргириос; Фернли, Джон; Мелиссург, Фемистоклис; Спиракис, Пол Г. (1 мая 2021 г.). «Вычисление точных решений консенсусного деления пополам и теоремы Борсука-Улама» . Журнал компьютерных и системных наук . 117 : 75–98. arXiv : 1903.03101 . дои : 10.1016/j.jcss.2020.10.006 . ISSN 0022-0000 . S2CID 228908526 .

[:2-22] Jump up to: ^а ^б Бациу, Элени; Хансен, Кристоффер Арнсфельт; Хёг, Каспер (07 марта 2021 г.). «Сильный приближенный консенсус пополам и теорема Борсука-Улама». arXiv : 2103.04452 [ cs.GT ].

[23] Голдберг, Пол В.; Холлендер, Александрос; Игараси, Аюми; Мануранси, Пасин; Суксомпонг, Варут (2022 г.). «Консенсусное сокращение вдвое наборов предметов». Математика исследования операций . 47 (4): 3357–3379. arXiv : 2007.06754 . дои : 10.1287/moor.2021.1249 . S2CID 246764981 .

[:7-24] Jump up to: ^а ^б Филос-Рацикас, Арис; Холлендер, Александрос; Сотираки, Катерина; Зампетакис, Манолис (01.01.2021), «Топологическая характеристика аргументов по модулю-p и последствия для разделения ожерелья», Труды симпозиума ACM-SIAM 2021 года по дискретным алгоритмам (SODA) , Труды, Общество промышленной и прикладной математики , стр. 2615–2634, doi : 10.1137/1.9781611976465.155 , ISBN 978-1-61197-646-5 , S2CID 214667000

[:02-25] Jump up to: ^а ^б Сегал-Халеви, Эрель; Ницан, Шмуэль (01 декабря 2019 г.). «Ярмарка разрезания торта среди семей» . Социальный выбор и благосостояние . 53 (4): 709–740. arXiv : 1510.03903 . дои : 10.1007/s00355-019-01210-9 . ISSN 1432-217X . S2CID 1602396 .

[mt10-26] Моссель, Эльханан; Тамуз, Омер (2010). «Правдиво-честный отдел». Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 6386. стр. 288–299. arXiv : 1003.5480 . дои : 10.1007/978-3-642-16170-4_25 . ISBN 978-3-642-16169-8 . S2CID 11732339 .

[27] Предпосылки по ценностным функциям партнеров. Меньшее количество предварительных условий означает, что результат является более общим. Con=Continious является наиболее общим; Con+Add=Добавка менее общая; Con+Add+Pwl=Кусочно-линейный вариант является наименее общим.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]