Симметричное справедливое разрезание торта: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
орфография |
Jumpow (обсуждение | вклад) отклонено последнее 1 изменение (Stanhamster): Вы знаете что такое ыакториал? Так вот он, как раз, и пишется n! Метка: ручная отмена |
||
Строка 13:
== Определения ==
Имеется ''торт'' ''C'', обычно представляемый как
''Процедура дележа'' — это функция ''F'', которая отображает ''n'' функций оценок в разбиение отрезка ''C''. Кусок, который функция ''F'' выделяет агенту ''i'', обозначим как <math>F(V_1,\dots,V_n; i)</math>.
Строка 30:
Процедура дележа ''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>
Любая анонимная процедура симметрична, поскольку в случае равенства кусков
Обратное, однако, не верно — возможно, что перестановка даёт агенту различные куски с одинаковыми значениями.
Строка 39:
Критерий называется по имени [[Аристотель|Аристотеля]], который писал в своей книге по этике: «... когда при одинаковом владении предоставляются неравные доли, или когда лица не равны при равных долях, растёт число споров и жалоб».
Любая симметричная процедура аристотелева. Пусть ''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>'', эти две последовательности мер идентичны, откуда следует определение аристотелевости.
Строка 66:
Чиз{{sfn|Chèze|2018}} предложил несколько процедур:
* Общая схема преобразования любой процедуры завистливого дележа в симметричную детерминированную процедуру: проводим исходную процедуру ''n''! раз, по разу для каждой перестановки агентов, и выбираем результат согласно топологическому критерию (то есть, по минимуму разрезов). Эта процедура становится практически неприменимой при больших ''n''.
* Аристотелева пропорциональная процедура для ''n'' агентов, которая требует <math>O(n^3)</math> запросов и полиномиальное число арифметических операций.
* Симметричная пропорциональная процедура для ''n'' агентов, которая требует <math>O(n^3)</math> запросов, но может требовать экспоненциальное число арифметических операций.
Строка 75:
# Выбирается один игрок произвольным образом, который называется '''делящим''', он режет торт на ''n'' частей, которые он/она оценивает ровно в 1.
# Строится [[двудольный граф]] <math>G = (X+Y, E) </math>, в котором каждая вершина ''X'' является агентом, каждая вершина ''Y'' является куском торта и имеется ребро между агентом ''x'' и куском торта ''y'' тогда и только тогда, когда ''x'' оценивает кусок ''y'' по меньшей мере в 1.
# Ищем максимальное по размеру ''[[паросочетание без зависти]] (ПБЗ)'' в ''G'' (паросочетание, в котором нет агента, не принадлежащего паросочетанию, но смежного
# Для любого ''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> рекурсивно среди них). Теперь все агенты, функции оценок которых идентичны, назначены тем же самым подмножествам и они делят подторт, значение которого среди них больше, чем их число, так что предусловие для рекурсии выполнено.
| |||