Эгалитарное разрезание торта

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

Концепция эгалитарного разделения торта была впервые описана Дубинсом и Спэньером , которые назвали ее «оптимальным разделением». ^{[ 1 ]}

Существование

Лексимин-оптимальные распределения существуют, когда множество распределений представляет собой компактное пространство . Это всегда имеет место при распределении дискретных объектов, и это легко доказать при распределении конечного числа непрерывных однородных ресурсов. Дубинс и Спэньер доказали , что при непрерывном гетерогенном ресурсе (« торте ») множество распределений компактно. ^{[ 1 ]} Следовательно, всегда существуют оптимальные для лексимина распределения тортов. По этой причине правило распределения лексиминов иногда называют правилом Дубинса-Спанье . ^{[ 2 ]}

Варианты

Когда оценки агентов не нормализованы (т. е. разные агенты могут присваивать разную стоимость всему торту), существует разница между профилем абсолютной полезности распределения (где элемент i — это просто полезность агента i ) и его относительный профиль полезности (где элемент i — это полезность агента i, деленная на общую стоимость агента i ). Правило абсолютного лексимина выбирает распределение, в котором профиль абсолютной полезности является лексимин-максимальным, а правило относительного лексимина выбирает распределение, в котором профиль относительной полезности является лексимин-максимальным.

Характеристики

Оба варианта правила лексимина являются Парето-оптимальными и популяционно монотонными . Однако они отличаются другими свойствами: ^{[ 3 ]}

Правило абсолютного лексимина является монотонным , но не пропорциональным по ресурсам ;
Правило относительного лексимина пропорционально, но не монотонно по ресурсам.

Отношение к свободе от зависти

Оба варианта правила лексимина могут привести к распределению ресурсов, которое не является свободным от зависти . Например, предположим, что имеется 5 агентов, торт кусочно-однороден с 3 регионами, а оценки агентов составляют (пропущенные значения — нули):

Агент	Левый	Середина	Верно
А	6	9
Б		5	10
С			15
Д			15
И			15

Все агенты оценивают весь торт в 15, поэтому абсолютный и относительный лексимин эквивалентны. Максимально возможное минимальное значение равно 5, поэтому распределение лексиминов должно давать всем агентам не менее 5. Это означает, что право должно быть разделено поровну между агентами C, D, E, а среднее должно быть полностью отдано агенту B. Но тогда А завидует Б. ^{[ 3 ]}

Дубинс и Спэньер ^{[ 1 ]} доказал, что, когда все меры ценности строго положительны, любое распределение относительного лексимина не вызывает зависти. ^{[ 4 ]}^{: Раздел 4}

Веллер ^{[ 4 ]}^{: Раздел 4} продемонстрировал свободное от зависти и эффективное распределение тортов, не относящееся к относительному лексимину. Пирог равен [0,1], агентов три, а их меры ценности представляют собой треугольные распределения с центрами 1/4, 1/2 и 3/4 соответственно. Распределение ([0,3/8],[3/8,5/8],[5/8,1]) имеет профиль полезности (3/8,7/16,7/16). Он свободен от зависти и утилитарно оптимален, а значит, эффективен по Парето. Однако существует другое распределение ([0,5/16],[5/16,11/16],[11/16,1]) с лучшим профилем полезности лексимина.

Вычисление

Из чеснока ^{[ 2 ]} представляет алгоритм вычисления оптимального для лексимина распределения ресурсов.

Ауманн, Домбб и хасиды ^{[ 5 ]} представить алгоритм, который для каждого e > 0 вычисляет распределение с эгалитарным благосостоянием не менее (1-e) от оптимума, используя $2^{n}\cdot n\cdot \log _{2}(n/\epsilon )$ запросы. Это экспоненциально по n , но полиномиально по количеству цифр точности.

С другой стороны, они доказывают, что, если только P = NP, невозможно аппроксимировать оптимальное эгалитарное значение с коэффициентом лучше 2 за полиномиальное по n время . Доказательство основано на методе трехмерного сопоставления (3DM). Для каждого экземпляра 3DM-сопоставления с m гиперребрами они создают экземпляр-разрезание торта с n агентами, где 4 m ≤ n ≤ 5 m . Они доказывают, что если экземпляр 3DM допускает идеальное совпадение, то существует распределение торта с эгалитарной ценностью не менее 1/ m ; в противном случае не существует распределения торта с эгалитарным значением, превышающим 1/(2 m ).

См. также

Справедливое разделение пирога – распределение, дающее каждому агенту равную полезность. Часто эгалитарное распределение совпадает со справедливым распределением, поскольку, если полезности различны, меньшую полезность можно улучшить, отдав часть пирога от агента с большей полезностью.
Эгалитарная эквивалентность — аналогичная концепция в контексте однородного распределения ресурсов.

Ссылки

^ Jump up to: ^а ^б ^с Дубинс, Лестер Эли ; Спэньер, Эдвин Генри (1961). «Как красиво разрезать торт». Американский математический ежемесячник . 68 (1): 1–17. дои : 10.2307/2311357 . JSTOR 2311357 .
^ Jump up to: ^а ^б Далл'Альо, Марко (1 мая 2001 г.). «Задача оптимизации Дубинса-Спанье в теории справедливого дележа» . Журнал вычислительной и прикладной математики . 130 (1–2): 17–40. Бибкод : 2001JCoAM.130...17D . дои : 10.1016/S0377-0427(99)00393-3 . ISSN 0377-0427 .
^ Jump up to: ^а ^б Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2019 г.). «Монотонность и конкурентное равновесие в разрезании тортов» . Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6 . ISSN 1432-0479 . S2CID 179618 .
^ Jump up to: ^а ^б Веллер, Дитрих (1 января 1985 г.). «Справедливое деление измеримого пространства» . Журнал математической экономики . 14 (1): 5–17. дои : 10.1016/0304-4068(85)90023-0 . ISSN 0304-4068 .
^ Ауманн, Йонатан; Домбб, Яир; Хасидим, Авинатан (06 мая 2013 г.). «Расчет социально-эффективного разделения тортов» . Материалы Международной конференции по автономным агентам и мультиагентным системам 2013 г. ААМАС '13. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем: 343–350. ISBN 978-1-4503-1993-5 .

[DS2-1] Jump up to: ^а ^б ^с Дубинс, Лестер Эли ; Спэньер, Эдвин Генри (1961). «Как красиво разрезать торт». Американский математический ежемесячник . 68 (1): 1–17. дои : 10.2307/2311357 . JSTOR 2311357 .

[:3-2] Jump up to: ^а ^б Далл'Альо, Марко (1 мая 2001 г.). «Задача оптимизации Дубинса-Спанье в теории справедливого дележа» . Журнал вычислительной и прикладной математики . 130 (1–2): 17–40. Бибкод : 2001JCoAM.130...17D . дои : 10.1016/S0377-0427(99)00393-3 . ISSN 0377-0427 .

[:0-3] Jump up to: ^а ^б Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2019 г.). «Монотонность и конкурентное равновесие в разрезании тортов» . Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6 . ISSN 1432-0479 . S2CID 179618 .

[:1-4] Jump up to: ^а ^б Веллер, Дитрих (1 января 1985 г.). «Справедливое деление измеримого пространства» . Журнал математической экономики . 14 (1): 5–17. дои : 10.1016/0304-4068(85)90023-0 . ISSN 0304-4068 .

[5] Ауманн, Йонатан; Домбб, Яир; Хасидим, Авинатан (06 мая 2013 г.). «Расчет социально-эффективного разделения тортов» . Материалы Международной конференции по автономным агентам и мультиагентным системам 2013 г. ААМАС '13. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем: 343–350. ISBN 978-1-4503-1993-5 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]