Симметричное справедливое разрезание торта: различия между версиями

отклонено последнее 1 изменение (Stanhamster): Вы знаете что такое ыакториал? Так вот он, как раз, и пишется n!
(орфография)
Метки: визуальный редактор Задача для новичков отменено
(отклонено последнее 1 изменение (Stanhamster): Вы знаете что такое ыакториал? Так вот он, как раз, и пишется n!)
Метка: ручная отмена
 
== Определения ==
Имеется ''торт'' ''C'', обычно представляемый как одномерныйодномерый отрезок. Имеется ''n'' человек, и каждый участник дележа ''i'' имеет функцию оценки ''V<sub>i</sub>'', которая отображает подмножества ''C'' в неотрицательные числа.
 
''Процедура дележа'' — это функция ''F'', которая отображает ''n'' функций оценок в разбиение отрезка ''C''. Кусок, который функция ''F'' выделяет агенту ''i'', обозначим как <math>F(V_1,\dots,V_n; i)</math>.
Процедура дележа ''F'' называется '''''анонимной''''', если для любой перестановки ''p'' индексов (1,...,''n'') и для любого <math>i</math>
:<math>F(V_1,\dots,V_n; i) = F(V_{p(1)},\dots,V_{p(n)}; p^{-1}(i))</math>
Любая анонимная процедура симметрична, поскольку в случае равенства кусков ихиз оценки заведомо равны.
 
Обратное, однако, не верно — возможно, что перестановка даёт агенту различные куски с одинаковыми значениями.
Критерий называется по имени [[Аристотель|Аристотеля]], который писал в своей книге по этике: «... когда при одинаковом владении предоставляются неравные доли, или когда лица не равны при равных долях, растёт число споров и жалоб».
 
Любая симметричная процедура аристотелева. Пусть ''p'' будет перестановкой, меняющей местами ''i'' и ''k''. Из симметриисимметерии следует, что
:<math>V_i(F(V_1,\dots,V_i,\dots,V_k,\dots,V_n; i)) = V_i(F(V_1,\dots,V_k,\dots,V_i,\dots,V_n; k))</math>
Но, поскольку ''V<sub>i</sub>''=''V<sub>k</sub>'', эти две последовательности мер идентичны, откуда следует определение аристотелевости.
Чиз{{sfn|Chèze|2018}} предложил несколько процедур:
 
* Общая схема преобразования любой процедуры завистливого дележа в симметричную детерминированную процедуру: проводим исходную процедуру ''n''! раз, по разу для каждой перестановки агентов, и выбираем результат согласно топологическому критерию (то есть, по минимуму разрезов). Эта процедура становится практически неприменимой при больших ''n''.
* Аристотелева пропорциональная процедура для ''n'' агентов, которая требует <math>O(n^3)</math> запросов и полиномиальное число арифметических операций.
* Симметричная пропорциональная процедура для ''n'' агентов, которая требует <math>O(n^3)</math> запросов, но может требовать экспоненциальное число арифметических операций.
# Выбирается один игрок произвольным образом, который называется '''делящим''', он режет торт на ''n'' частей, которые он/она оценивает ровно в 1.
# Строится [[двудольный граф]] <math>G = (X+Y, E) </math>, в котором каждая вершина ''X'' является агентом, каждая вершина ''Y'' является куском торта и имеется ребро между агентом ''x'' и куском торта ''y'' тогда и только тогда, когда ''x'' оценивает кусок ''y'' по меньшей мере в 1.
# Ищем максимальное по размеру ''[[паросочетание без зависти]] (ПБЗ)'' в ''G'' (паросочетание, в котором нет агента, не принадлежащего паросочетанию, но смежного принадлежащемупринадлежащено паросочетаниюпаросоченанию куску торта). Заметим, что делящий смежен всем ''n'' кускам торта, так что <math>|N_G(X)|= n \geqslant |X|</math> (где <math>N_G(X)</math> является множеством соседей ''X'' в ''Y''). Следовательно, непустое паросочетание без зависти существует{{sfn|Segal-Halevi, Aigner-Horev|2019}}. Предположим без потери общности, что ПБЗ сопоставляет агентов 1,...,''k'' кускам <math>X_1,\dots,X_k</math>, оставляя без соответствия агентов и куски от ''k''+1 др ''n''.
# Для любого ''i'' из 1,...,''k'', для которого <math>V_i(X_i) = 1</math>, отдаём ''X<sub>i</sub>'' агенту ''i''. Теперь делящему и всем агентам, чьи функции оценок идентичны функции делящего, назначены куски, имеющие одинаковые значения.
# Рассмотрим теперь агентов ''i'' из 1,...,''k'', для которых <math>V_i(X_i) > 1</math>. Разобьём их на подмножества с равными векторами оценок кусков <math>X_1,\dots,X_n</math>. Для каждого подмножества рекурсивно делим их куски среди них (например, если агенты 1, 3, 4 согласны со значениями всех кусков 1,...,''k'', то делим куски <math>X_1,X_3,X_4</math> рекурсивно среди них). Теперь все агенты, функции оценок которых идентичны, назначены тем же самым подмножествам и они делят подторт, значение которого среди них больше, чем их число, так что предусловие для рекурсии выполнено.