Просмотр кода страницы Разрезание торта согласно полезности

'''Разрезание торта согласно полезности''' (или '''разрезание торта по maxsum''') — это правило дележа неоднородных [[ресурс]]ов, таких как [[торт]] или земельная [[недвижимость]], между несколькими участниками с различными функциями [[Кардиналистская теория полезности|количественной полезности]] так, что ''сумма'' полезности для участников будет как можно больше. Такое разрезание было вдохновлено философией [[утилитаризм]]а. Разрезание торта согласно полезности часто бывает «несправедливым». Следовательно, утилитаризм конфликтует со [[Задача справедливого разрезания торта|справедливым разрезанием торта]].

== Пример ==
Представим торт, состоящий из двух частей — шоколадной и ванильной. Пусть имеется два участника — Алиса и Джордж со следующими оценками

{| class="wikitable"
|-
! Участник !! Шоколад !! Ваниль
|-
| Алиса || <big>9</big> || <big>1</big>
|-
| Джордж || <big>6</big> || <big>4</big>
|}

Правило полезности отдаёт каждую часть участнику с наивысшей [http://www.rriai.org.ru/shkalyi-poleznosti-i-otsenka-poleznosti-3.html оценкой полезности]. В данном случае по правилу полезности вся шоколадная часть достанется Алисе, а всю ванильная — Джорджу. Значение maxsum будет равно 13.

Разрезание согласно полезности несправедливо — оно не [[Задача пропорционального разрезания торта|пропорционально]], поскольку Джордж получает менее половины полной оценки. Оно также не [[Завистливое разрезание торта|свободно от зависти]], поскольку Джордж завидует Алисе.

== Обозначения ==
Обозначим торт буквой <math>C</math>. Обычно предполагается, что это либо конечный одномерный отрезок, двумерный [[многоугольник]], или конечное [[подмножество]] многомерного евклидова пространства <math>\mathbb{R}^d</math>.

Имеется <math>n</math> участников. Каждый участник <math>i</math> имеет личную функцию оценок <math>V_i</math>, которая отображает подмножества <math>C</math> («куски торта») в числа.

<math>C</math> нужно разделить на <math>n</math> непересекающихся частей, по одному на участника. Часть, передаваемая участнику <math>i</math>, обозначается как <math>X_i</math> и <math>C = X_1 \sqcup ... \sqcup X_n</math>.

Разбиение <math>X</math> называется разбиением по ''полезности'', или ''максимально полезным'' (МП), или ''maxsum'', если оно максимизирует следующее выражение:

: <math>\sum_{i=1}^{n}{V_i(X_i)}</math>

Концепция часто обобщается путём назначения различных весов каждому участнику. Разбиение <math>X</math> называется ''максимально взвешенно полезным'' (МВП, {{lang-en|weighted-utilitarian-maximal}}, WUM), если оно максимизирует следующее выражение:

: <math>\sum_{i=1}^{n}\frac{V_i(X_i)}{w_i}</math>,

где <math>w_i</math> являются заданными положительными константами.

== Maxsum и эффективность по Парето ==
Любое МВП разбиение с положительными весами очевидно [[Эффективность по Парето|эффективно по Парето]]. Если разбиение <math>Y</math> доминирует по Парето разбиение <math>X</math>, то [[Весовая функция|взвешенная сумма]] полезностей в <math>Y</math> строго больше, чем в <math>X</math>, так что <math>X</math> не может быть МВП разбиением.

Что более удивительно: ''любое'' эффективное по Парето разбиения является МВП при некотором выборе весов{{sfn|Barbanel, Zwicker|1997|с=203}}{{r|WV}}.

== Характерные признаки правила maxsum ==
Христофер П. Чамберс предложил характерные признаки правила МВП{{sfn|Chambers|2005|с=236–258}}. Признаки основаны на следующем свойстве правила разбиения ''R'':
* '''Эффективность по Парето''' (ПЭ, {{lang-en|Pareto-efficiency}}, PE): правило ''R'' возвращает только разбиения, которые эффективны по Парето.
* '''Независимость от деления''' (НД, {{lang-en|Division independence}}, DI)''': если торт разделён на несколько кусков и каждый из них разрезан согласно правилу ''R'', результат будет тем же самым, как если бы исходный торт был разрезан по правилу ''R''.
* '''Независимость недостижимой страны''' (ННС, {{lang-en|Independence of infeasible land}}, IIL): когда подторт разделён согласно правилу ''R'', результат не зависит от пользы участников в других подтортах.
* '''Положительная обработка равных''' (ПОР, {{lang-en|Positive treatment of equals}}, PTE): если все участники имеют одинаковые функции полезности, правило ''R'' рекомендует по меньшей мере одно разбиение, которое даёт положительную полезность каждому участнику.
* '''Независимость от масштаба''' (НШ, {{lang-en|Scale-invariance}}, SI): когда функции оценки участников умножаются на постоянную величину (для разных участников допустимы различные константы), рекомендации, задаваемые правилом ''R'', не меняются.
* '''Непрерывность''' (НП, {{lang-rn|Continuity}}, CO): для фиксированного куска торта множество схем полезности, которые отображают в специфичное распределение, является [[Замкнутое множество|замкнутым множеством]] по [[Поточечная сходимость|поточечной сходимости]].

Следующие факты доказаны для участников, которые назначают положительную полезность любому куску торта с положительным размером:
* Если правило ''R'' обладает свойствами ПЭ, НД и ННС, то существует последовательность весов <math>w_1,\dots,w_n</math>, такая, что все разбиения, рекомендованные правилом ''R'', являются МВП с этими весами (было показано, что любое ПЭ разбиение является МВП с ''некоторыми'' весами. Новым является то, что все разбиения, рекомендованные правилом ''R'', являются МВП с ''теми же'' весами. Это следует из НД свойствами).
* Если правило ''R'' обладает свойствами ПЭ, НД, ННС и ПОР, то все разбиения, рекомендованные правилом ''R'', являются максимально полезными (другими словами, все дележи должны быть МВП и все агенты должны иметь равные веса. Это следует из свойства ПОР).
* Если правило ''R'' обладает свойствами ПЭ, НД, ННС и НШ, то правило ''R'' является диктаторским правилом — оно отдаёт весь торт одному участнику.
* Если правило ''R'' обладает свойствами ПЭ, НД, ННС и НП, то существует последовательность весов <math>w_1,\dots,w_n</math>, такая, что правило ''R'' является МВП правилом с этими весами (то есть ''R'' рекомендует только МВП дележи с этими весами).

== Нахождение maxsum разбиений ==

=== Несвязные куски ===
Если функции оценок [[Аддитивность (математика)|аддитивны]], maxsum дележи всегда существуют. Интуитивно мы можем дать каждую часть торта участнику, который оценивает его максимально, как в [[#Пример|примере выше]]. Аналогично, МВП делёж может быть найден путём передачи каждой части торта партнёру, для которого значение отношения <math>V_i / w_i</math> самое большое.

Этот процесс легко осуществить, если торт ''кусочно-однороден'', то есть его можно разбить на конечное число кусков, для которых плотность функций значений для всех участников постоянна.

Если торт не является кусочно-однородным, алгоритм выше не работает, поскольку имеется бесконечное число различных «кусков» для рассмотрения.

В этом случае maxsum разбиение всё же существует. Это следствие [[Теоремы Дубинса — Спеньера|теоремы компактности Дубинса — Спеньера]] и это может быть доказано с помощью [[Множество Радона — Никодима|множества Радона — Никодима]].

Однако никакой конечный алгоритм не может найти maxsum разбиение. '''Доказательство'''{{sfn|Brams, Taylor|1996|с=48}}. Конечный [[алгоритм]] имеет данные о ценности конечного числа кусков. То есть имеется только конечное число подмножеств торта, для которых алгоритм знает оценки участников. Предположим, что алгоритм остановился после получения данных о <math>k</math> подмножеств. Теперь возможен случай, когда все участники ответили, что они имеют ''те же самые'' оценки кусков. В этом случае наибольшее возможное значение полезности, которое может быть достигнуто алгоритмом, равно 1. Однако возможно, что глубоко внутри одного из <math>k</math> кусков имеется подмножество, которое два участника оценивают по-разному. В этом случае существует [[суперпропорциональный делёж]], в котором каждый участник получает значение, большее <math>1/n</math>, так что сумма полезностей строго больше 1. Следовательно, деление, возвращаемое конечным алгоритмом, не будет maxsum.

=== Связные куски ===
Если торт одномерен и куски должны быть связными, простой алгоритм назначения каждого наиболее ценного куска агенту больше не работает, даже если куски кусочно-постоянны. В этом случае задача нахождения МП дележа [[NP-трудная задача|NP-трудна]], и более того, никакой схемы [[Приближённая схема полиномиального времени|FPTAS]] невозможно, если только не P=NP.

Существует 8-кратный аппроксимационный алгоритм и {{не переведено 5|Параметризованная сложность|фиксированно-параметрически разрешимый||fixed-parameter tractable}} алгоритм, который экспоненциален от числа игроков{{sfn|Aumann, Dombb, Hassidim|2013}}.

Для любого множества положительных весов существует МВП разбиение и оно может быть найдено аналогичным образом.

== Maxsum и справедливость ==
Делёж maxsum не всегда справедлив, см. [[#Пример|пример выше]]. Аналогично, справедливый делёж не всегда maxsum.

Одним из подходов разрешения конфликта является ограничение «цены справедливости» — вычисляем верхнюю и нижнюю границы уменьшения суммы полезности, чтобы получить справедливое разбиение. Для деталей см. статью «[[Цена справедливости]]».

Другим подходом комбинации эффективности и справедливости является поиск среди всех возможных справедливых дележей дележа с максимальной суммой полезности:

=== Нахождение справедливых maxsum распределений ===
Следующие алгоритмы можно использовать для поиска [[Завистливое разрезание торта|свободного от зависти разрезания]] с максимальной суммарной полезностью для торта в виде одномерного интервала, если каждый участник может получить разрозненные (несвязные) куски торта и функции оценок аддитивны{{sfn|Cohler, Lai, Parkes, Procaccia|2011}}:

# Для <math>n</math> участников с ''кусочно-постоянными'' оценками: делим торт на ''m'' полностью константных областей (). Решаем задачу [[Линейное программирование|линейного программирования]] с ''nm'' переменными — каждая пара (агент, область) имеет переменную, которая определяет долю области, передаваемую агенту. Для каждой области имеется ограничение, утверждающее, что сумма всех частей области равна 1. Для каждой пары (агент, агент) имеется ограничение, утверждающее, что первый агент не завидует второму агенту. Заметим, что разбиение торта, получаемое такой процедурой, может оказаться крайне мелким.
# Для <math>2</math> участников с ''кусочно-линейными'' оценками: для каждой точки торта вычисляем отношение между полезностями: <math>r=u_1/u_2</math>. Отдаём участнику 1 точки с <math>r\geqslant r^*</math>, а участнику 2 точки с <math>r<r^*</math>, где <math>r^*</math> является порогом, вычисленным так, что делёж будет свободным от зависти. В общем случае <math>r^*</math> не может быть вычислен, поскольку может быть [[Иррациональное число|иррациональным]], но на практике, когда оценки кусочно-линейны, <math>r^*</math> можно аппроксимировать аппроксимационным алгоритмом «иррационального поиска». Для любого <math>\epsilon > 0</math> алгоритм находит распределение, которое является <math>\epsilon</math>-СЗ (значение для каждого агента не меньше значения для любого другого агента ''минус'' <math>\epsilon</math>) и сумма достигает как минимум максимальной суммы СЗ распределений. Время работы алгоритма полиномиально зависит от входных данных и от <math>\log(1/\epsilon)</math>.
# Для <math>n</math> участников с оценками общего вида: аддитивная аппроксимация для получения свободного от зависти и эффективного распределения, основываясь на алгоритме кусочно-линейной оценки.

=== Свойства maxsum-справедливых распределений ===
В статье Брамса с соавторами{{sfn|Brams, Feldman и др.|2012|с=1285–1291}} изучаются как свободный от зависти (СЗ, {{lang-en|envy-free}}, EF), так и [[беспристрастный делёж|беспристрастный]] (БД, {{lang-en|equitable}}, EQ) дележи торта, и устанавливается их связь с maxsum и оптимальными по Парето (ОП, {{lang-en|Pareto-optimality}}, PO) дележами. Как было объяснено выше, maxsum распределения всегда ОП. Однако, когда maxsum ограничено условием справедливости, это не обязательно верно. Брамс с соавторами доказали следующее

* Когда имеется два агента, СЗ максимальное, БД максимальное и СЗ-БД максимальное распределение всегда будут ОП.
* Когда имеется три и более агентов с ''кусочно-однородными'' оценками, СЗ максимальные распределения всегда ОП (поскольку СЗ эквивалентно [[Задача пропорционального разрезания торта|пропорциональности]], что сохраняется при улучшениях по Парето). Однако может ''не быть'' БД максимального и БД-СЗ максимального распределений, которые были бы ОП.
* Если имеется три или более агентов с ''кусочно-константными'' функциями оценок (то есть имеющими кусочно-константные плотности), может не быть СЗ максимального распределения, являющегося ОП. Например, рассмотрим торт с тремя областями и тремя агентами со значениями: '''Алиса''': 51/101, 50/101, 0 '''Боб''': 50/101, 51/101, 0 '''Карл''': 51/111, 10/111, 50/111. Правило maxsum даёт область i агенту i, но такой делёж не без зависти, поскольку Карл завидует Алисе. Используя линейное программирование, можно найти единственное СЗ максимальное распределение и показать, что оно должно дать паи в регионе 1 и регионе 2 и Алисе и Бобу. Однако такое распределение не может быть ОП, поскольку Алиса и Боб могли бы выиграть от обмена паёв в этих регионах.
* Если все агенты имеют ''кусочно-линейные'' функции оценок, сумма полезностей СЗ максимального распределения не меньше полезностей БД максимального распределения. Этот результат расширяется до общих оценок для аддитивных [[Аппроксимация|аппроксимаций]] (то есть <math>\epsilon</math>-СЗ распределения имеют сумму полезностей, не меньшую полезностей БД распределений минус <math>\epsilon</math>).

== См. также ==
* {{не переведено 5|Подсчёт удовольствия|||Felicific calculus}} — попытка определить полезности с помощью математических формул.
* [[Эффективное разрезание торта]]
* [[Задача справедливого разрезания торта]]
* [[Теорема Веллера]]
* [[Эффективное по Парето распределение без зависти]]
* [[Максимальное по рангу распределение]]

== Примечания ==
{{примечания|refs=
<ref name=WV>See also [[Теорема Веллера]]. О похожих результатах, связанных с задачей неоднородного распределения ресурса, см. [[Эффективное по Парето распределение без зависти|теоремы Вариана]].</ref>}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{статья
|заглавие=Two applications of a theorem of Dvoretsky, Wald, and Wolfovitz to cake division
|doi=10.1023/a:1004966624893
|год=1997
|ref=Barbanel, Zwicker
|автор=Julius B. Barbanel, William S. Zwicker
|издание=Theory and Decision
|том=43
|выпуск=2 
}}
* {{статья
|doi=10.1016/j.jet.2004.04.008
|заглавие=Allocation rules for land division
|издание=Journal of Economic Theory
|том=121
|выпуск=2
|год=2005
|ref=Chambers
|автор=Christopher P. Chambers
}}
* {{книга
|isbn=978-0521556446
|заглавие=Fair Division; From cake-cutting to dispute resolution
|ref=Brams, Taylor
|автор=Steven J. Brams, Alan D. Taylor
|год=1996
}}
* {{книга
|автор=Yonatan Aumann, Yair Dombb, Avinatan Hassidim
|ref=Aumann, Dombb, Hassidim
|часть=Computing Socially-Efficient Cake Divisions
|заглавие=AAMAS
|год=2013
|ссылка=http://dl.acm.org/citation.cfm?id=2484976
}}
* {{книга
|автор=Yuga Julian Cohler, John Kwang Lai, David C. Parkes, Ariel Procaccia 
|ref=Cohler, Lai, Parkes, Procaccia 
|часть=Optimal Envy-Free Cake Cutting
|заглавие=AAAI
|год=2011
|ссылка=http://dash.harvard.edu/handle/1/4892932
}}
* {{книга
|ссылка=http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/download/4876/5459 
|часть=On Maxsum Fair Cake Divisions
|заглавие=Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12)
|год=2012
|accessdate=6 December 2015
|автор=Steven J. Brams, Michal Feldman, John K. Lai, Jamie Morgenstern, Ariel D. Procaccia 
|ref=Brams, Feldman и др.
}}
{{refend}}

{{rq|checktranslate|style}}

[[Категория:Утилитаризм]]
[[Категория:Справедливый делёж]]