WikiDer > Цены без зависти

Envy-free pricing

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

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

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

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

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

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

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

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

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

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

  1. ^ «О ценообразовании без зависти с целью максимизации прибыли | Материалы шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам». dl.acm.org. Получено 2020-01-16.
  2. ^ Балкан, Мария-Флорина; Блюм, Аврим; Mansour, Yishay (2008), «Цены на товары для максимизации дохода», в Fortnow, Lance; Ридл, Джон; Сандхольм, Туомас (ред.), Труды 9-й конференции ACM по электронной торговле (EC-2008), Чикаго, Иллинойс, США, 8-12 июня 2008 г., стр. 50–59, Дои:10.1145/1386790.1386802