Эгалитарное разрезание торта — это разновидность справедливого разрезания торта , в котором критерием справедливости является эгалитарное правило . Торт представляет собой непрерывный ресурс (такой как земля или время), который должен быть распределен между людьми с разными оценками частей ресурса. Цель эгалитарное разрезание торта — максимизировать наименьшую ценность агента; при этом максимизировать следующую наименьшую ценность; и так далее. Это также называется лексиминным разрезанием торта , поскольку оптимизация выполняется с использованием лексиминного порядка на векторах полезностей.
Концепция равноправного разделения торта была впервые описана Дубинсом и Спаниером , которые назвали ее «оптимальным разделом». [1]
Лексимин-оптимальные распределения существуют всякий раз, когда набор распределений представляет собой компактное пространство . Это всегда так при распределении дискретных объектов, и это легко доказать при распределении конечного числа непрерывных однородных ресурсов. Дубинс и Спаниер доказали , что при непрерывном неоднородном ресурсе (« торте ») набор распределений компактен. [1] Следовательно, лексимин-оптимальные распределения тортов всегда существуют. По этой причине правило лексиминного распределения тортов иногда называют правилом Дубинса–Спанье . [2]
Когда оценки агентов не нормализованы (т. е. разные агенты могут присваивать разную ценность всему торту), существует разница между абсолютным профилем полезности распределения (где элемент i — это просто полезность агента i ) и его относительным профилем полезности (где элемент i — это полезность агента i , деленная на общую ценность для агента i ). Абсолютное правило лексимина выбирает распределение, в котором абсолютный профиль полезности является лексимин-максимальным, а относительное правило лексимина выбирает распределение, в котором относительный профиль полезности является лексимин-максимальным.
Оба варианта правила лексимина являются Парето-оптимальными и популяционно монотонными . Однако они различаются по другим свойствам: [3]
Оба варианта правила лексимина могут давать распределения, которые не являются свободными от зависти . Например, предположим, что есть 5 агентов, торт кусочно-однородный с 3 областями, а оценки агентов следующие (отсутствующие значения — нули):
Все агенты оценивают весь торт в 15, поэтому абсолютный лексимин и относительный лексимин эквивалентны. Наибольшее возможное минимальное значение равно 5, поэтому распределение лексимина должно дать всем агентам не менее 5. Это означает, что Право должно быть разделено поровну между агентами C, D, E, а Середина должна быть полностью отдана агенту B. Но тогда A завидует 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) от оптимума с использованием запросов. Это экспоненциально по n , но полиномиально по количеству цифр точности.
С другой стороны, они доказывают, что, если P=NP, невозможно приблизить оптимальное эгалитарное значение к множителю, лучшему 2, за время, полиномиальное по n . Доказательство основано на редукции из 3-мерного сопоставления (3DM). Для каждого экземпляра 3DM-сопоставления с m гиперребрами они строят экземпляр разрезания торта с n агентами, где 4 m ≤ n ≤ 5 m . Они доказывают, что если экземпляр 3DM допускает идеальное сопоставление, то существует распределение торта с эгалитарным значением не менее 1/ m ; в противном случае не существует распределения торта с эгалитарным значением больше 1/(2 m ).
