Разрезание торта согласно полезности

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

Пример

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

Участник	Шоколад	Ваниль
Алиса	9	1
Джордж	6	4

Правило полезности отдаёт каждую часть участнику с наивысшей оценкой полезности. В данном случае по правилу полезности вся шоколадная часть достанется Алисе, а всю ванильная — Джорджу. Значение maxsum будет равно 13.

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

Обозначения

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

Имеется $n$ участников. Каждый участник $i$ имеет личную функцию оценок $V_{i}$, которая отображает подмножества $C$ («куски торта») в числа.

$C$ нужно разделить на $n$ непересекающихся частей, по одному на участника. Часть, передаваемая участнику $i$, обозначается как $X_{i}$ и $C=X_{1}\sqcup ...\sqcup X_{n}$.

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

$\sum _{i=1}^{n}{V_{i}(X_{i})}$

Концепция часто обобщается путём назначения различных весов каждому участнику. Разбиение $X$ называется максимально взвешенно полезным (МВП, англ. weighted-utilitarian-maximal, WUM), если оно максимизирует следующее выражение:

$\sum _{i=1}^{n}{\frac {V_{i}(X_{i})}{w_{i}}}$,

где $w_{i}$ являются заданными положительными константами.

Maxsum и эффективность по Парето

Любое МВП разбиение с положительными весами очевидно эффективно по Парето. Если разбиение $Y$ доминирует по Парето разбиение $X$, то взвешенная сумма полезностей в $Y$ строго больше, чем в $X$, так что $X$ не может быть МВП разбиением.

Что более удивительно: любое эффективное по Парето разбиения является МВП при некотором выборе весов.

Характерные признаки правила maxsum

Христофер П. Чамберс предложил характерные признаки правила МВП. Признаки основаны на следующем свойстве правила разбиения R:

• Эффективность по Парето (ПЭ, англ. Pareto-efficiency, PE): правило R возвращает только разбиения, которые эффективны по Парето.
• Независимость от деления (НД, англ. Division independence, DI): если торт разделён на несколько кусков и каждый из них разрезан согласно правилу R, результат будет тем же самым, как если бы исходный торт был разрезан по правилу R.
• Независимость недостижимой страны (ННС, англ. Independence of infeasible land, IIL): когда подторт разделён согласно правилу R, результат не зависит от пользы участников в других подтортах.
• Положительная обработка равных (ПОР, англ. Positive treatment of equals, PTE): если все участники имеют одинаковые функции полезности, правило R рекомендует по меньшей мере одно разбиение, которое даёт положительную полезность каждому участнику.
• Независимость от масштаба (НШ, англ. Scale-invariance, SI): когда функции оценки участников умножаются на постоянную величину (для разных участников допустимы различные константы), рекомендации, задаваемые правилом R, не меняются.
• Непрерывность (НП, рунди Continuity, CO): для фиксированного куска торта множество схем полезности, которые отображают в специфичное распределение, является замкнутым множеством по поточечной сходимости.

Следующие факты доказаны для участников, которые назначают положительную полезность любому куску торта с положительным размером:

• Если правило R обладает свойствами ПЭ, НД и ННС, то существует последовательность весов $w_{1},\dots ,w_{n}$, такая, что все разбиения, рекомендованные правилом R, являются МВП с этими весами (было показано, что любое ПЭ разбиение является МВП с некоторыми весами. Новым является то, что все разбиения, рекомендованные правилом R, являются МВП с теми же весами. Это следует из НД свойствами).
• Если правило R обладает свойствами ПЭ, НД, ННС и ПОР, то все разбиения, рекомендованные правилом R, являются максимально полезными (другими словами, все дележи должны быть МВП и все агенты должны иметь равные веса. Это следует из свойства ПОР).
• Если правило R обладает свойствами ПЭ, НД, ННС и НШ, то правило R является диктаторским правилом — оно отдаёт весь торт одному участнику.
• Если правило R обладает свойствами ПЭ, НД, ННС и НП, то существует последовательность весов $w_{1},\dots ,w_{n}$, такая, что правило R является МВП правилом с этими весами (то есть R рекомендует только МВП дележи с этими весами).

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

Несвязные куски

Если функции оценок аддитивны, maxsum дележи всегда существуют. Интуитивно мы можем дать каждую часть торта участнику, который оценивает его максимально, как в примере выше. Аналогично, МВП делёж может быть найден путём передачи каждой части торта партнёру, для которого значение отношения $V_{i}/w_{i}$ самое большое.

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

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

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

Однако никакой конечный алгоритм не может найти maxsum разбиение. Доказательство. Конечный алгоритм имеет данные о ценности конечного числа кусков. То есть имеется только конечное число подмножеств торта, для которых алгоритм знает оценки участников. Предположим, что алгоритм остановился после получения данных о $k$ подмножеств. Теперь возможен случай, когда все участники ответили, что они имеют те же самые оценки кусков. В этом случае наибольшее возможное значение полезности, которое может быть достигнуто алгоритмом, равно 1. Однако возможно, что глубоко внутри одного из $k$ кусков имеется подмножество, которое два участника оценивают по-разному. В этом случае существует суперпропорциональный делёж, в котором каждый участник получает значение, большее $1/n$, так что сумма полезностей строго больше 1. Следовательно, деление, возвращаемое конечным алгоритмом, не будет maxsum.

Связные куски

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

Существует 8-кратный аппроксимационный алгоритм и фиксированно-параметрически разрешимый алгоритм, который экспоненциален от числа игроков.

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

Maxsum и справедливость

Делёж maxsum не всегда справедлив, см. пример выше. Аналогично, справедливый делёж не всегда maxsum.

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

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

Нахождение справедливых maxsum распределений

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

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

Свойства maxsum-справедливых распределений

В статье Брамса с соавторами изучаются как свободный от зависти (СЗ, англ. envy-free, EF), так и беспристрастный (БД, англ. equitable, EQ) дележи торта, и устанавливается их связь с maxsum и оптимальными по Парето (ОП, англ. 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 и Алисе и Бобу. Однако такое распределение не может быть ОП, поскольку Алиса и Боб могли бы выиграть от обмена паёв в этих регионах.
• Если все агенты имеют кусочно-линейные функции оценок, сумма полезностей СЗ максимального распределения не меньше полезностей БД максимального распределения. Этот результат расширяется до общих оценок для аддитивных аппроксимаций (то есть $\epsilon$-СЗ распределения имеют сумму полезностей, не меньшую полезностей БД распределений минус $\epsilon$).

См. также

• Подсчёт удовольствия — попытка определить полезности с помощью математических формул.
• Эффективное разрезание торта
• Задача справедливого разрезания торта
• Теорема Веллера
• Эффективное по Парето распределение без зависти
• Максимальное по рангу распределение