WikiDer > Точное деление

Exact division

An точное деление, также называемый четное деление или разделение консенсуса, представляет собой разделение разнородного ресурса ("торт") на несколько подмножеств, так что каждое из п люди с разными вкусами сходятся во мнении об оценке произведений.^[1]^:127

Например, возьмем торт, наполовину шоколадный и наполовину ванильный. Алиса ценит только шоколад, а Джордж ценит только ваниль. Торт делится на три части: одна часть содержит 20% шоколада и 20% ванили, вторая - 50% шоколада и 50% ванили, а третья - остальную часть торта. Это разделение консенсуса, поскольку и Алиса, и Джордж оценивают эти три части как 20%, 50% и 30% соответственно.

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

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

Определения

Позволять ${ displaystyle w_ {1}, w_ {2}, ldots, w_ {k}}$ быть k веса, сумма которых равна 1. Предположим, что все п партнеры ценят торт C как 1.

An точное деление (он же разделение консенсуса) в соотношениях ${ displaystyle w_ {1}, w_ {2}, ldots, w_ {k}}$ это раздел торта на k шт: ${ Displaystyle C = X_ {1} sqcup cdots sqcup X_ {k}}$ , так что для каждого партнера я и каждый кусок j:

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

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

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

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

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

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

Идеальное деление

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

Точное деление с произвольным количеством разрезов

Кусочно-однородный торт, много партнеров, любые веса

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

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

если торт кусочно-однородный (а оценки кусочно-постоянные), консенсусное разделение может быть достигнуто следующим образом:

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

Этот алгоритм может быть обобщен на несколько более общие семейства показателей стоимости, такие как кусочно-линейные.^[2]

Количество требуемых разрезов составляет ${ displaystyle kR}$ , где р - количество регионов.

Общий торт, много партнеров, любые веса

Когда меры стоимости счетно-аддитивный и неатомный, консенсусное разделение существует для каждого набора весов, сумма которых равна 1. Это следствие из теоремы Дубинса – Спаниера о выпуклости.

Woodall^[3] показал, что можно построить такое деление интервального торта как счетное объединение интервалов.

ИНТУИЦИЯ: Рассмотрим процедуру разделения кусочно-однородных коржей, описанную выше. В целом торт не получается кусочно-однородным. Однако, поскольку измерения стоимости являются непрерывными, можно разделить торт на все меньшие и меньшие области, так что области становятся все более и более однородными. Когда ${ displaystyle R to infty}$ , этот процесс сводится к разделению консенсуса.

Фремлин показал, что можно построить такое подразделение, как конечный объединение интервалов.

Стромквист и Вудалл^[4] показал, что это возможно с минимальный количество интервалов; видеть Теорема Стромквиста – Вудалла.

Точное деление с минимальным количеством разрезов

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

Интервальный торт, два партнера, много подмножеств, любые веса

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

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

Один и тот же протокол может использоваться для вырезания части, стоимость которой равна ${ displaystyle 1 / n}$ .

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

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

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

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

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

Предположим, торт представляет собой интервал стоимости 1. Его следует разделить на ${ displaystyle k = 2}$ подмножества, каждое из которых имеет значение ровно 1/2 для всех п партнеры. Мы хотим использовать минимальное количество разрезов, которое ${ Displaystyle п (к-1) = п}$ .

Такое разделение существует всегда.^[7] Это прямое следствие Теорема Хобби – Райса. Это также можно доказать на основе Теорема Борсука-Улама:^[8]

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

Разделение консенсуса на два подмножества может быть найдено на основе Лемма Такера, которая является дискретной версией Теорема Борсука-Улама.^[9]

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

Интервальный торт, много партнеров, много подмножеств, одинаковые веса

Теорема существования предыдущего пункта может быть обобщена из ${ displaystyle k = 2}$ штук на произвольное количество штук. Это было доказано Нога Алон в своей статье 1987 г. о проблема расщепления ожерелья.

Есть ${ displaystyle n}$ различные меры на интервале, все абсолютно непрерывные по длине. Размер всего ожерелья по мере ${ displaystyle i}$ , является ${ Displaystyle к cdot a_ {я}}$ . Тогда можно разбить интервал на ${ displaystyle k}$ частей (не обязательно смежных), так что размер каждой части в соответствии с размером ${ displaystyle i}$ , точно ${ displaystyle a_ {i}}$ . В большинстве ${ Displaystyle (к-1) п}$ разрезы нужны, и это оптимально.

Интервальный торт, много партнеров, два подмножества, произвольные веса

Теорема существования предыдущего пункта обобщается на произвольные веса с помощью Теорема Стромквиста – Вудалла.

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

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

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

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

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

Процедуры почти точного деления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Невозможность

Невозможно добиться точного разделения с конечным числом запросов, даже если есть только 2 партнера и веса ровно 1/2.^[1]^:103–104 Это означает, что лучшее, что мы можем достичь с помощью дискретного алгоритма, - это почти точное деление.

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

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

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

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

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

Точное деление с равными весами ( ${ displaystyle 1 / n}$ ), в частности, также пропорциональный, без зависти и справедливый.

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

Точное разделение намного проще, если участники будут сотрудничать в создании права а не соревноваться, как в справедливое разделение. Некоторые авторы называют это разделение консенсуса или сокращение вдвое консенсуса.^[14]

Таблица результатов

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

Navigation