Механизм частичного распределения
Механизм частичного распределения (PAM) — это механизм для справедливого распределения ресурсов . Он основан на распределении максимального продукта — распределении, максимизирующем продукт полезности агентов (также известном как оптимальное по Нэшу распределение или пропорционально-справедливое решение; во многих случаях оно эквивалентно конкурентному равновесию из равных доходов). Он гарантирует каждому агенту не менее 0,368 его/ее полезности при распределении максимального продукта. Он был разработан Коулом, Гкатцелисом и Гоэлем. [1]
Параметр
Имеется m ресурсов, которые предполагаются однородными и делимыми .
Есть n агентов, каждый из которых имеет персональную функцию, которая присваивает числовое значение каждому «связке» (комбинации ресурсов). Оценки предполагаются однородными функциями .
Цель состоит в том, чтобы решить, какой «набор» предоставить каждому агенту, при этом набор может содержать дробное количество каждого ресурса.
Важно отметить, что от некоторых ресурсов, возможно, придется отказаться, т.е. предполагается их бесплатная утилизация .
Денежные выплаты не допускаются.
Алгоритм
PAM работает следующим образом.
- Рассчитайте распределение максимального продукта; обозначьте его z .
- Для каждого агента i :
- Рассчитайте распределение максимального продукта, когда i отсутствует .
- Пусть f i = (произведение других агентов в z ) / (максимальное произведение других агентов, когда i отсутствует).
- Дайте агенту i долю f i каждого ресурса, который он получает в z .
Характеристики
PAM обладает следующими свойствами.
- Это правдивый механизм — полезность каждого агента максимизируется за счет раскрытия его/ее истинных оценок.
- Для каждого агента i полезность i составляет не менее 1/ e ≈ 0,368 от его/ее полезности при распределении максимального продукта.
- Когда агенты имеют аддитивные линейные оценки, распределение является свободным от зависти .
PA против VCG
Механизм PA, не использующий платежи, аналогичен механизму VCG , использующему денежные платежи. VCG начинает с выбора распределения максимальной суммы , а затем для каждого агента i вычисляет распределение максимальной суммы, когда i отсутствует, и выплачивает i разницу ( максимальная сумма, когда i присутствует)-(максимальная сумма, когда i отсутствует). Поскольку агенты квазилинейны, полезность i уменьшается на аддитивный фактор.
Напротив, ПА не использует денежные выплаты, а полезность агентов уменьшается мультипликативным образом за счет изъятия части их ресурсов.
Оптимальность
Неизвестно, является ли дробь 0,368 оптимальной. Однако, доказуемо, не существует правдивого механизма, который может гарантировать каждому агенту более 0,5 от полезности максимального продукта.
Расширения
PAM использовался как подпрограмма в истинном кардинальном механизме для одностороннего сопоставления. [2]
Ссылки
- ^ Коул, Ричард; Гкатцелис, Василис; Гоэль, Гаган (2013). «Разработка механизма для справедливого дележа». Труды четырнадцатой конференции ACM по электронной коммерции . EC '13. Нью-Йорк, штат Нью-Йорк, США: ACM. С. 251–268. arXiv : 1212.1522 . doi :10.1145/2492002.2482582. ISBN 9781450319621.
- ^ Абебе, Редьет; Коул, Ричард; Гкацелис, Василис; Хартлайн, Джейсон Д. (18 марта 2019 г.). «Правдивый кардинальный механизм одностороннего сопоставления». arXiv : 1903.07797 [cs.GT].
