Симметричная ярмарка-разрезание торта
Симметричное справедливое разрезание торта — это вариант задачи о справедливом разрезании торта , в которой справедливость применяется не только к конечному результату, но и к распределению ролей в процедуре дележа.
В качестве примера рассмотрим праздничный торт, который нужно разделить между двумя детьми с разными вкусами так, чтобы каждый ребенок чувствовал, что его доля «справедлива», т. е. стоит как минимум 1/2 всего торта. Они могут использовать классическую процедуру «разделяй и выбирай» : Алиса разрезает торт на две части, стоящие в ее глазах ровно 1/2, а Джордж выбирает тот кусок, который он считает более ценным. Результат всегда справедлив. Однако процедура не симметрична: в то время как Алиса всегда получает значение, равное ровно 1/2 своего значения, Джордж может получить гораздо больше, чем 1/2 своего значения. Таким образом, хотя Алиса и не завидует доле Джорджа, она завидует роли Джорджа в процедуре.
Напротив, рассмотрим альтернативную процедуру, в которой Алиса и Джордж делают на торте половинные отметки, т. е. каждый из них отмечает место, в котором торт следует разрезать, так, чтобы в его/ее глазах эти два куска были равны. Затем торт разрезается точно между этими разрезами: если разрез Алисы равен a , а разрез Джорджа равен g , то торт разрезается по координате (a+g)/2. Если a < g , Алиса получает самый левый кусок, а Джордж — самый правый; в противном случае Алиса получает самый правый кусок, а Джордж — самый левый. Окончательный результат по-прежнему справедлив. И здесь роли симметричны: единственный случай, когда роли влияют на конечный результат, — это когда a = g , но в этом случае обе части имеют значение ровно 1/2 для обоих потомков, поэтому роли не влияют на окончательную стоимость. Следовательно, альтернативная процедура является одновременно справедливой и симметричной.
Идея была впервые предложена Манабэ и Окамото. [1] который назвал это свободным от метазависти .
Предложено несколько вариантов симметричного праздничного разрезания торта:
- Анонимное честное разрезание торта требует, чтобы были равны не только ценности, но и сами кусочки. [2] Это подразумевает симметричную справедливость, но она сильнее. Например, это не удовлетворяется приведенным выше симметричным принципом «разделяй и выбирай», поскольку в случае a = g первый агент всегда получает самый левый кусок, а второй агент всегда получает самый правый кусок.
- Аристотелевское справедливое разрезание пирога требует лишь того, чтобы агенты с одинаковыми мерами стоимости получали одинаковую стоимость. [3] Это подразумевается под симметричной справедливостью, но она слабее. Например, ему удовлетворяет асимметричная версия принципа «разделяй и выбирай»: если оценки агентов одинаковы, то оба они получают ценность ровно 1/2.
Определения
[ редактировать ]Существует торт C , который обычно считается одномерным интервалом. Есть n человек. У каждого человека i есть функция ценности Vi , которая отображает подмножества C в слабоположительные числа.
Процедура деления — это функция F которая отображает n функций значений в раздел C. , Часть, выделенная F агенту i, обозначается F ( V 1 ,..., V n ; i ).
Симметричная процедура
[ редактировать ]Процедура деления F называется симметричной , если для любой перестановки p из (1,..., n ) и для каждого i :
V я ( F ( V 1 ,..., V n ; я )) знак равно V я ( F ( V p(1) ,..., V p(n) ; p −1 ( я )))
В частности, когда n = 2, процедура является симметричной, если:
V 1 ( F ( V 1 , V 2 ; 1)) = V 1 ( F ( V 2 , V 1 ; 2)) и V 2 ( F ( V 1 , V 2 ; 2)) = V 2 ( F ( В 2 , В 1 ))
Это означает, что агент 1 получает одинаковую ценность независимо от того, играет ли он первым или вторым, и то же самое справедливо и для агента 2. Другой пример: когда n =3, требование симметрии подразумевает (среди прочего):
V 1 ( F ( V 1 , V 2 , V 3 ; 1)) знак равно V 1 ( F ( V 2 , V 3 ,V 1 ; 3)) знак равно V 1 ( F ( V 3 ,V 1 , V 2 ; 2)).
Анонимная процедура
[ редактировать ]Процедура деления F называется анонимной , если для любой перестановки p из (1,..., n ) и для каждого i :
F ( V 1 ,..., V n ; я ) = F ( V p(1) ,..., V p(n) ; p −1 ( я ))
Любая анонимная процедура симметрична, поскольку если части равны, то их значения заведомо равны.
Но обратное неверно: возможно, что перестановка даст агенту разные части равной ценности.
Аристотелевская процедура
[ редактировать ]Процедура деления F называется аристотелевской , если всякий раз, когда V i = V k :
V я (F ( V 1 ,..., V n ; я )) знак равно V k ( F ( V 1 ,..., V n ; k ))
Критерий назван в честь Аристотеля , который в своей книге по этике писал: «...именно тогда, когда равные владеют или распределяются неравными долями, или лица, не равные равными долями, возникают ссоры и жалобы». Любая симметричная процедура является аристотелевской. Пусть p будет перестановкой, которая меняет местами i и k . Симметрия подразумевает, что:
V я (F ( V 1 ,.... V я ,..., V k ,..., V n ; я )) знак равно V я ( F ( V 1 ,.... V k ,.. ., я ,..., В н ) В )
поскольку Vi , две последовательности мер стоимости идентичны, поэтому = Vk Но отсюда следует определение аристотелева. Более того, каждая процедура разрезания торта без зависти является аристотелевской: свобода от зависти подразумевает, что:
V я (F ( V 1 ,..., V n ; я )) ≥ V я ( F ( V 1 ,..., V n ; k )) V k ( F ( V 1 ,..., V n ; k )) ≥ V k ( F ( V 1 ,..., V n ; я ))
Но поскольку Vi , из двух неравенств следует , = V k что оба значения равны.
Однако процедура, удовлетворяющая более слабому условию пропорционального разрезания торта, не обязательно является аристотелевской. Чез [3] показан пример с 4 агентами, в котором процедура Эвен-Паза для пропорционального разрезания торта может давать разные значения агентам с одинаковыми мерами стоимости.
На следующей диаграмме суммированы отношения между критериями:
- Анонимный → Симметричный → Аристотелевский
- Без зависти → Аристотелевский
- Без зависти → Пропорционально
Процедуры
[ редактировать ]Любую процедуру можно сделать «симметричной заранее» путем рандомизации. Например, в асимметричной игре «разделяй и выбирай» разделитель можно выбрать, подбросив монету. Однако такая процедура не является симметричной постфактум. Поэтому исследования, касающиеся симметричного разрезания торта, фокусируются на детерминированных алгоритмах .
Манабе и Окамото [1] представили симметричные и свободные от зависти («без метазависти») детерминированные процедуры для двух и трех агентов.
Nicolo and Yu [2] представил анонимный, не вызывающий зависти и эффективный по Парето протокол разделения для двух агентов. Протокол реализует распределение в идеальном равновесии подигры , предполагая, что каждый агент имеет полную информацию об оценке другого агента.
Симметричная процедура «отрезай и выбирай» для двух агентов изучалась эмпирически в лабораторном эксперименте. [4] Альтернативные симметричные процедуры разрезания торта для двух агентов - крайняя правая отметка. [5] и крайние левые листья . [6]
Сыр [3] представил несколько процедур:
- Общая схема преобразования любой процедуры, свободной от зависти, в симметричную детерминированную процедуру: запустить исходную процедуру n ! раз, один раз для каждой перестановки агентов, и выбирать один из результатов в соответствии с некоторым топологическим критерием (например, минимизацией количества разрезов). Эта процедура непрактична, если n велико.
- Аристотелевская пропорциональная процедура для n агентов, требующая O( n 3 ) запросов и полиномиальное количество арифметических операций референта.
- Симметричная пропорциональная процедура для n агентов, требующая O( n 3 ) запросы, но может потребовать от рефери экспоненциального количества арифметических операций.
Аристотелевская пропорциональная процедура
[ редактировать ]Аристотелевская процедура Чезе [3] для пропорционального разрезания торта расширяется процедура одиночного делителя . Для удобства мы нормализуем оценки так, чтобы стоимость всего торта была равна n для всех агентов. Цель состоит в том, чтобы дать каждому агенту фишку стоимостью не менее 1.
- Один игрок, выбранный произвольно, называемый делителем , разрезает торт на n частей, ценность которых в его/ее глазах равна ровно 1.
- Постройте двудольный граф G = ( X+Y , E ), в котором каждая вершина в X является агентом, каждая вершина в Y является частью, и существует ребро между агентом x и частью y тогда и только тогда, когда x имеет значение y не менее 1.
- максимальной мощности паросочетание без зависти Найдите в G (сочетание, в котором ни один несовпадающий агент не соседствует с совпадающим фрагментом). Обратите внимание, что разделитель примыкает ко всем n частям, поэтому | N грамм ( Икс )|= п ≥ |X| (где NG ) ( X ) — множество соседей X в Y . Следовательно, существует непустое паросочетание без зависти. [7] Предположим, что EFM сопоставляет агентов 1,..., k с фрагментами X 1 ,...,X k и оставляет несопоставленными агентов и фрагменты от k +1 до n .
- Для каждого i из 1,..., k , для которого V i ( X i ) = 1 - передать X i агенту i . Теперь делителю и всем агентам, чья функция ценности идентична функции делителей, присваивается часть и они имеют одинаковое значение.
- Рассмотрим теперь агентов i в 1,..., k, для которых ( Vi X i ) > 1. Разделим их на подмножества с одинаковым вектором значений для частей X 1 ,...,X k . Для каждого подмножества рекурсивно разделите их части между собой (например, если агенты 1, 3, 4 договариваются о значениях всех частей 1,..., k , то разделите части X 1 ,X 3, X 4 рекурсивно между их). Теперь все агенты, чья функция ценности идентична, отнесены к одному и тому же подмножеству, и они делят подпирог, значение которого для них больше, чем их число, поэтому предварительное условие рекурсии удовлетворено.
- Рекурсивно разделите несовпадающие фрагменты X k +1 , ..., X n между несовпадающими агентами. Обратите внимание, что из-за отсутствия зависти при сопоставлении каждый несовпадающий агент оценивает каждую совпадающую часть меньше 1, поэтому он оценивает оставшиеся части больше, чем количество агентов, поэтому предварительное условие для рекурсии удовлетворено.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Манабе, Ёсифуми; Окамото, Тацуаки (2010). «Протоколы разрезания торта без метазависти» . Математические основы информатики 2010 . МФКС'10. Том. 6281. Берлин, Гейдельберг: Springer-Verlag. стр. 501–512. Бибкод : 2010LNCS.6281..501M . дои : 10.1007/978-3-642-15155-2_44 . ISBN 9783642151545 .
- ^ Перейти обратно: а б Николо, Антонио; Ю, Ян (01 сентября 2008 г.). «Стратегический разделяй и выбирай» (PDF) . Игры и экономическое поведение . 64 (1): 268–289. дои : 10.1016/j.geb.2008.01.006 . ISSN 0899-8256 .
- ^ Перейти обратно: а б с д Шез, Гийом (11 апреля 2018 г.). «Не плачь, чтобы быть первым! Симметричные алгоритмы справедливого дележа существуют». arXiv : 1804.03833 [ cs.GT ].
- ^ Киропулу, Мария; Ортега, Хосуэ; Сегал-Халеви, Эрель (2019). «Ярмарка разрезания торта на практике». Материалы конференции ACM по экономике и вычислениям 2019 года . ЕС '19. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 547–548. arXiv : 1810.08243 . дои : 10.1145/3328526.3329592 . ISBN 9781450367929 . S2CID 53041563 .
- ^ Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсная монотонность и популяционная монотонность в связанном разрезании торта». Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .
- ^ Ортега, Хосуэ (08 августа 2019 г.). «Очевидные манипуляции при разрезании торта». arXiv : 1908.02988 [ cs.GT ].
- ^ Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (2022). «Сопоставления без зависти в двудольных графах и их приложения к справедливому дележу». Информационные науки . 587 : 164–187. arXiv : 1901.09527 . дои : 10.1016/j.ins.2021.11.059 . S2CID 170079201 .