Расщепление консенсуса

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

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

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

Определения

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

${\displaystyle V_{i}(X_{j})=w_{j}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Процедура крошки и упаковки

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

${\displaystyle |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. Положите в миску одну из крошек.
3. Если сумма в миске становится больше 1/2 у одного из партнеров, отдайте миску этому партнеру, а остальные крошки отдайте другому партнеру.
4. В противном случае (стоимость в миске меньше 1/2 для обоих партнеров), если стоимость в миске больше для Алисы, чем для Джорджа, то найдите крошку, стоимость которой для Джорджа больше, чем ее стоимость для Алисы (такая крошка должна существовать, потому что сумма стоимостей всех крошек равна 1 как для Алисы, так и для Джорджа). Добавьте эту крошку в миску и вернитесь к шагу 2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Нахождение разбиения таким образом, чтобы каждый агент оценивал каждую часть не менее 1/ 2n , используя разрезы. ${\displaystyle n}$
• Нахождение разбиения таким образом, чтобы каждый агент оценивал каждую часть в 1/2 ± ε , с использованием сокращений в онлайн-алгоритме или с использованием сокращений в офлайн-алгоритме . ${\displaystyle O((n\log {n})/(\varepsilon ^{2}))}$ ${\displaystyle 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-деление)

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

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

С использованием полиномиального числа запросов Робертсона-Уэбба можно вычислить два типа приближений : ^[3]

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

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

Точное деление с равными весами ( ) является, в частности, также пропорциональным , свободным от зависти и справедливым . Однако оно не обязательно является эффективным по Парето , поскольку во многих случаях можно воспользоваться субъективными оценками и разделить ресурсы таким образом, что все партнеры получат больше, чем их справедливая доля . ${\displaystyle 1/n}$ ${\displaystyle 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 , можно построить с использованием любого существующего алгоритма (или оракула) для нахождения консенсусного деления:

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

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

См. также: правдивое разрезание торта .

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

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

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

Ссылки

1. Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: AK Peters. ISBN 978-1-56881-076-8. LCCN  97041258. OL  2730675W.
2. Симмонс, Форест В.; Су, Фрэнсис Эдвард (2003). «Разделение половины консенсуса с помощью теорем Борсука-Улама и Такера». Математические социальные науки . 45 : 15–25. CiteSeerX 10.1.1.203.1189 . дои : 10.1016/S0165-4896(02)00087-2. 
3. Алон, Нога ; Граур, Андрей (2020-06-30). «Эффективное разделение мер и ожерелий». arXiv : 2006.16613 [cs.DS].
4. Chen, Yiling ; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013). «Истина, справедливость и разрезание торта». Игры и экономическое поведение . 77 (1): 284–297. doi :10.1016/j.geb.2012.10.009. S2CID  2096977.
5. Нейман, Ежи (январь 1946 г.). «Теорема существования». Comptes Rendus de l'Académie des Sciences . 222 : 843–845.
6. Woodall, DR (1980). «Справедливое разделение пирога». Журнал математического анализа и приложений . 78 : 233–247. doi : 10.1016/0022-247x(80)90225-5 .
7. Голдберг, Чарльз Х.; Уэст, Дуглас Б. (1985). «Деление пополам раскрасок кругов». Журнал SIAM по алгебраическим и дискретным методам . 6 : 93–106. doi :10.1137/0606010.
8. Алон, Нога; Уэст, Дуглас Б. (1986). "Теорема Борсука-Улама и деление ожерелий пополам" (PDF) . Труды Американского математического общества . 98 (4): 623. doi : 10.1090/s0002-9939-1986-0861764-9 .
9. Стромквист, Уолтер; Вудалл, DR (1985). «Наборы, на которых согласуются несколько мер». Журнал математического анализа и приложений . 108 : 241–248. doi :10.1016/0022-247x(85)90021-6.
10. Б. Грюнбаум (1960). «Разбиения масс–распределений и выпуклых тел гиперплоскостями». Pacific J. Math . 10 (4): 1257–1261. doi : 10.2140/pjm.1960.10.1257 . MR  0124818.
11. де Лонгвиль, Марк; Живальевич, Раде Т. (2008). «Разделение многомерных ожерелий». Успехи в математике . 218 (3): 926–939. arXiv : math/0610800 . doi : 10.1016/j.aim.2008.02.003 .
12. Фишер, Дэниел. "Консенсусное разделение торта между двумя людьми в произвольных пропорциях". Math.SE. Получено 23 июня 2015 г.
13. Существует обобщение, которое дает каждому из n партнеров кусок, стоящий ровно для него. Но это не консенсусное разделение, потому что партнеры могут не договориться о ценности других частей, кроме части, выделенной им. См. процедуры Остина с подвижным ножом#Многие партнеры . ${\displaystyle 1/n}$
14. В. Бергстрем (1930). «Zwei Sätze über ebene Vectorpolygone». Гамбургские Абхандлунгены . 8 : 205–219.
15. Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение [ От разрезания торта до разрешения споров ]. Cambridge University Press. С. 131–133. ISBN 978-0-521-55644-6.
16. Филос-Рацикас, Арис; Голдберг, Пол В. (2018-06-20). «Консенсусное деление пополам — это PPA-complete». Труды 50-го ежегодного симпозиума ACM SIGACT по теории вычислений . STOC 2018. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 51–64. arXiv : 1711.04503 . doi :10.1145/3188745.3188880. ISBN 978-1-4503-5559-9. S2CID  8111195.
17. Filos-Ratsikas, Aris; Goldberg, Paul W. (2019-06-23). ​​«Сложность разделения ожерелий и деления сэндвичей с ветчиной». Труды 51-го ежегодного симпозиума ACM SIGACT по теории вычислений. STOC 2019. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 638–649. doi :10.1145/3313276.3316334. ISBN 978-1-4503-6705-9. S2CID  44085263.
18. Филос-Рацикас, Арис; Холлендер, Александрос; Сотираки, Катерина; Зампетакис, Манолис (13 июля 2020 г.). «Консенсус-Халвинг: становится ли это когда-нибудь проще?». Труды 21-й конференции ACM по экономике и вычислениям . EC '20. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 381–399. arXiv : 2002.11437 . doi : 10.1145/3391403.3399527. hdl : 1721.1/146185. ISBN 978-1-4503-7975-5. S2CID  211505917.
19. Deligkas, Argyrios; Filos-Ratsikas, Aris; Hollender, Alexandros (2021-07-18). «Двое — компания, трое — толпа: консенсус-сокращение вдвое для постоянного числа агентов». Труды 22-й конференции ACM по экономике и вычислениям . EC '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 347–368. arXiv : 2007.15125 . doi : 10.1145/3465456.3467625. hdl : 20.500.11820/f92c933a-c6bd-4f93-b56f-de38970860e7. ISBN 978-1-4503-8554-1. S2CID  220871193.
20. Филос-Рацикас, Арис; Фредериксен, Сорен Кристоффер Стейл; Голдберг, Пол В.; Чжан, Цзе (08 августа 2018 г.). «Результаты твердости для консенсусного сокращения вдвое». arXiv : 1609.05136 [cs.GT].
21. Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. (2021-05-01). «Вычисление точных решений консенсусного деления пополам и теоремы Борсука-Улама». Журнал компьютерных и системных наук . 117 : 75–98. arXiv : 1903.03101 . doi : 10.1016/j.jcss.2020.10.006. ISSN  0022-0000. S2CID  228908526.
22. Batziou, Eleni; Hansen, Kristoffer Arnsfelt; Høgh, Kasper (2021-03-07). «Сильное приближенное консенсусное деление пополам и теорема Борсука-Улама». arXiv : 2103.04452 [cs.GT].
23. Голдберг, Пол В.; Холлендер, Александрос; Игараси, Аюми; Манурангси, Пасин; Суксомпонг, Варут (2022). «Консенсусное деление пополам для наборов элементов». Математика исследования операций . 47 (4): 3357–3379. arXiv : 2007.06754 . doi : 10.1287/moor.2021.1249. S2CID  246764981.
24. Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis (2021-01-01), "Топологическая характеристика аргументов по модулю p и их последствия для разделения ожерелья", Труды симпозиума ACM-SIAM 2021 года по дискретным алгоритмам (SODA) , Труды, Общество промышленной и прикладной математики, стр. 2615–2634, doi : 10.1137/1.9781611976465.155 , ISBN 978-1-61197-646-5, S2CID  214667000
25. Segal-Halevi, Erel; Nitzan, Shmuel (2019-12-01). «Справедливое разрезание торта среди семей». Social Choice and Welfare . 53 (4): 709–740. arXiv : 1510.03903 . doi : 10.1007/s00355-019-01210-9. ISSN  1432-217X. S2CID  1602396.
26. Mossel, Elchanan; Tamuz, Omer (2010). «Истинное честное деление». Алгоритмическая теория игр . Конспект лекций по информатике. Том 6386. С. 288–299. arXiv : 1003.5480 . doi :10.1007/978-3-642-16170-4_25. ISBN 978-3-642-16169-8. S2CID  11732339.
27. Предпосылки для функций ценности партнеров. Меньше предпосылок означает, что результат более общий. Con=Continuous является наиболее общим; Con+Add=Additive является менее общим; Con+Add+Pwl=Piecewise-linear является наименее общим.