Утилитарный разрез торта

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

Пример

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

Правило утилитаризма отдает каждую часть партнеру с наибольшей полезностью. В этом случае правило утилитаризма отдает весь шоколад Элис, а всю ваниль Джорджу. Максимальная сумма равна 13.

Утилитарное деление несправедливо: оно непропорционально , поскольку Джордж получает меньше половины общей стоимости торта, и оно не свободно от зависти, поскольку Джордж завидует Элис.

Обозначение

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

Есть партнеры. У каждого партнера есть персональная функция ценности , которая отображает подмножества («части») в числа. ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle V_{i}}$ ${\displaystyle C}$

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

Деление называется утилитарным или утилитарно-максимальным или maxsum , если оно максимизирует следующее выражение: ${\displaystyle X}$

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

Концепция часто обобщается путем присвоения разного веса каждому партнеру. Разделение называется взвешенно-утилитарно-максимальным (WUM), если оно максимизирует следующее выражение: ${\displaystyle X}$

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

где даны положительные константы. ${\displaystyle w_{i}}$

Макссумма и Парето-эффективность

Каждое деление WUM с положительными весами, очевидно, является Парето-эффективным . Это происходит потому, что если деление Парето-доминирует деление , то взвешенная сумма полезностей в строго больше, чем в , поэтому не может быть делением WUM. ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$

Еще более удивительно то, что каждое эффективное по Парето деление является WUM для некоторого набора весов. ^[1]

Характеристика утилитарного правила

Кристофер П. Чемберс предлагает характеристику правила WUM. ^[2] Характеристика основана на следующих свойствах правила деления R :

• Эффективность по Парето (PE) : правило R возвращает только те подразделения, которые являются эффективными по Парето.
• Независимость деления (DI) : всякий раз, когда торт разделяется на несколько подтортов и каждый торт делится в соответствии с правилом R , результат будет таким же, как если бы исходный торт был разделен в соответствии с правилом R.
• Независимость от нецелевых земель (IIL) : всякий раз, когда часть пирога делится в соответствии с R , результат не зависит от полезности партнеров в других частях пирога.
• Положительное отношение к равным (PTE) : когда все партнеры имеют одинаковую функцию полезности, R рекомендует по крайней мере одно деление, которое дает положительную полезность каждому партнеру.
• Масштабная инвариантность (SI) : всякий раз, когда функции полезности партнеров умножаются на константы (возможно, разные константы для каждого партнера), рекомендации, данные R, не меняются.
• Непрерывность (CO) : для фиксированного куска пирога набор профилей полезности, которые сопоставляются с конкретным распределением, является замкнутым множеством при поточечной сходимости .

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

• Если R является PE DI и IIL, то существует последовательность весов, такая что все подразделения, рекомендованные R, являются WUM с этими весами (известно, что каждое подразделение PE является WUM с некоторыми весами; новость заключается в том, что все подразделения, рекомендованные R, являются WUM с теми же весами. Это следует из свойства DI). ${\displaystyle w_{1},\dots ,w_{n}}$
• Если R — это PE DI IIL и PTE, то все подразделения, рекомендуемые R, являются утилитарно-максимальными (другими словами, все подразделения должны быть WUM, и все агенты должны иметь равные веса. Это следует из свойства PTE).
• Если R равно PE DI IIL и SI, то R является диктаторским правилом — оно отдает весь пирог одному партнеру.
• Если R — это PE DI IIL и CO, то существует последовательность весов, такая что R является правилом WUM с этими весами (т.е. R рекомендует все и только подразделения WUM с этими весами). ${\displaystyle w_{1},\dots ,w_{n}}$

Нахождение утилитарных разделений

Разъединенные части

Когда функции ценности аддитивны, деления maxsum всегда существуют. Интуитивно, мы можем отдать каждую часть торта тому партнеру, который ценит ее больше всего, как в примере выше. Аналогично, деления WUM можно найти, отдав каждую часть торта тому партнеру, для которого это отношение больше всего. ${\displaystyle V_{i}/w_{i}}$

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

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

Maxsum деления все еще существуют. Это следствие теоремы о компактности Дубинса–Спаньера , и это также можно доказать с помощью множества Радона–Никодима .

Однако ни один конечный алгоритм не может найти деление maxsum. Доказательство : ^{[3] [4] : ​​Cor.2} Конечный алгоритм имеет данные о значении только о конечном числе кусков. Т.е. существует только конечное число подмножеств торта, для которых алгоритм знает оценки партнеров. Предположим, что алгоритм остановился, получив данные о значении подмножеств. Теперь может быть так, что все партнеры ответили на все запросы, как будто у них одинаковая мера ценности. В этом случае максимально возможное утилитарное значение, которого может достичь алгоритм, равно 1. Однако возможно, что глубоко внутри одного из кусков есть подмножество, которое два партнера оценивают по-разному. В этом случае существует сверхпропорциональное деление , при котором каждый партнер получает значение больше , поэтому сумма полезностей строго больше 1. Следовательно, деление, возвращаемое конечным алгоритмом, не является maxsum. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 1/n}$

Связанные части

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

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

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

Макссум и справедливость

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

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

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

Поиск утилитарно-справедливого распределения

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

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

Свойства утилитарно-справедливого распределения

Brams, Feldman, Lai, Morgenstern и Procaccia ^[7] изучают как свободные от зависти (EF), так и справедливые (EQ) дележи торта и связывают их с maxsum и оптимальностью по Парето (PO). Как объяснялось выше, распределения maxsum всегда являются PO. Однако, когда maxsum ограничена справедливостью, это не обязательно так. Они доказывают следующее:

• При наличии двух агентов распределения maxsum-EF, maximum-EQ и maximum-EF-EQ всегда равны PO.
• Когда есть три или более агентов с кусочно-равномерными оценками , распределения maxsum-EF всегда являются PO (поскольку EF эквивалентно пропорциональности , которая сохраняется при улучшениях по Парето). Однако может не быть распределений maxsum-EQ и maxsum-EQ-EF, которые являются PO.
• Когда есть три или более агентов с кусочно-постоянными оценками , может даже не быть распределений maxsum-EF, которые являются PO. Например, рассмотрим торт с тремя регионами и тремя агентами со значениями:

Правило maxsum дает регион i агенту i, но это не EF, так как Карл завидует Алисе. Используя линейную программу, можно найти уникальное распределение maxsum-EF и показать, что оно должно делить как регион 1, так и регион 2 между Алисой и Бобом. Однако такое распределение не может быть PO, так как Алиса и Боб оба могут выиграть, обменявшись своими долями в этих регионах.

• Когда все агенты имеют кусочно-линейные оценки , сумма полезности распределения maxsum-EF по крайней мере такая же большая, как и распределение maxsum-EQ. Этот результат распространяется на общие оценки вплоть до аддитивного приближения (т. е. распределения ε -EF имеют сумму полезности по крайней мере распределения EQ − ε ).

Свойства монотонности утилитарного разрезания торта

Когда части могут быть разъединены , абсолютно-утилитарное правило (максимизация суммы ненормализованных полезностей) является ресурсно-монотонным и популяционно-монотонным . Относительно-утилитарное правило (максимизация суммы нормализованных полезностей) является популяционно-монотонным, но не ресурсно-монотонным. ^[8]

Это больше не выполняется, когда части соединены. ^[9]

Смотрите также

• Эффективная нарезка торта
• Справедливое разрезание торта
• Теорема Веллера
• Парето-эффективное разделение без зависти
• Максимально ранговое распределение
• Утилитарный голос – утилитарный принцип в ином контексте.

Ссылки

1. Барбанель, Юлиус Б.; Цвикер, Уильям С. (1997). «Два применения теоремы Дворецкого, Вальда и Вольфовица к делению торта». Теория и решение . 43 (2): 203. doi :10.1023/a:1004966624893. S2CID  118505359.. См. также теорему Веллера . Похожий результат, связанный с проблемой однородного распределения ресурсов, см. в теоремах Вариана .
2. Чемберс, Кристофер П. (2005). «Правила распределения для разделения земли». Журнал экономической теории . 121 (2): 236–258. doi :10.1016/j.jet.2004.04.008.
3. Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение [ От разрезания торта до разрешения споров ]. стр. 48. ISBN 978-0521556446.
4. Яновский, Егор (01.03.2012). «Механизмы резки торта». arXiv : 1203.0100 [cs.GT].
5. Ауманн, Йонатан; Домб, Яир; Хассидим, Авинатан (2013). Вычисление социально эффективных делений торта. AAMAS.
6. Колер, Юга Джулиан; Лай, Джон Кванг; Паркс, Дэвид С.; Прокачча, Ариэль (2011). Оптимальное разрезание торта без зависти. AAAI.
7. Стивен Дж. Брамс; Михал Фельдман ; Джон К. Лай; Джейми Моргенштерн; Ариэль Д. Прокачча (2012). О Maxsum Fair Cake Divisions. Труды 26-й конференции AAAI по искусственному интеллекту (AAAI-12). стр. 1285–1291 . Получено 6 декабря 2015 г.
8. Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2019 г.). «Монотонность и конкурентное равновесие в разрезании тортов». Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6. ISSN  1432-0479. S2CID  179618.
9. Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсная монотонность и популяционная монотонность в связанном разрезании торта». Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001. ISSN  0165-4896. S2CID  16282641.