Цены без зависти - Envy-free pricing

Цены без зависти это подход к справедливому распределению дискретных объектов среди людей с разными предпочтениями. Это частный случай проблемы справедливое распределение предметов, со следующими отличительными свойствами:

Денежные выплаты разрешены. В частности, разрешено назначать цену каждому объекту и взимать с каждого человека полную стоимость выделенных ему объектов.
Предполагается, что люди квазилинейны по деньгам. Это означает, что полезность, которую получает агент от набора объектов, равна его ценности для набора за вычетом общей цены элементов в пакете.
Распределение должно быть без зависти: для каждого агента его полезность от его собственного пакета, по крайней мере, равна полезности, которую он может получить от любого другого возможного пакета (в частности, от пакетов, предоставленных другим агентам).
Некоторые предметы разрешается оставлять нераспределенными. Тем не менее, это требуется для максимизации социального обеспечения и / или дохода продавца (при условии отсутствия зависти).

Термин был изобретен^[1] Гурусвами, Хартлайн, Карлин, Кемпе, Кеньон и МакШерри. Они сосредоточились на максимизации дохода продавца. Для двух классов функций полезности: удельный спрос и целеустремленный, они показали:

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

Позднее результаты были расширены Мария-Флорина Балкан, Аврим Блюм и Ишай Мансур. Они показали, что:^[2]

При неограниченном количестве единиц на единицу случайной единственной цены достигается ожидаемый доход в пределах логарифмического фактора общего общественного благосостояния, даже для агентов с Общее оценочные функции (даже не монотонные). В частности, для одного агента доход составляет не менее 4 log (2м) максимального благосостояния (где м количество типов элементов), а для п агентов, это не менее O (log (п) + журнал (м)) максимального благосостояния.
С ограниченным предложением, для субаддитивные оценки, случайная цена приносит доход с коэффициентом 2^{O (√ (журнал п журнал п))} от общего социальное обеспечение.
Нижняя граница, показывающая последовательность субаддитивных (и даже дробно субаддитивный ) агентов, для которых любая цена имеет коэффициент аппроксимации 2^{Ω (журнал^1/4п)}
В случае с несколькими единицами, пока ни один покупатель не требует доли товаров более 1-ε, случайная единичная цена приносит доход в пределах O (log п) фактор максимального социального благополучия.

С тех пор проблема исследовалась в различных вариантах в различных работах.

Сравнение с похожими проблемами

В распределение предметов без зависти, денежные выплаты не допускаются.

в арендная гармония проблема, денежные выплаты разрешены, но все объекты должны быть размещены (и каждый агент должен получить ровно один объект).

А Вальрасовское равновесие это похоже на ценообразование без зависти, с дополнительным требованием, что все объекты с положительной ценой должны быть распределены (все нераспределенные объекты должны иметь нулевую цену).

Цены без зависти - Envy-free pricing

Сравнение с похожими проблемами

Рекомендации