Механизм частичного распределения - Википедия - Partial allocation mechanism

В Механизм частичного распределения (ПАМ) это механизм для правдивое распределение ресурсов. Он основан на максимальное распределение продукта - распределение, максимизирующее продукт полезностей агентов (также известное как оптимальное по Нэшу распределение или пропорционально-справедливое решение; во многих случаях оно эквивалентно конкурентное равновесие от равных доходов). Он гарантирует каждому агенту не менее 0,368 его / ее полезности в распределении максимального продукта. Его разработали Коул, Гкатзелис и Гоэл.[1]

Параметр

Есть м ресурсы, которые предполагается однородный и делимый.

Есть п агенты, каждый из которых выполняет персональную функцию, которая присваивает числовое значение каждому «пучку» (комбинации ресурсов). Предполагается, что оценки будут однородные функции.

Цель состоит в том, чтобы решить, какой «пакет» передать каждому агенту, где пакет может содержать дробное количество каждого ресурса.

Важно отметить, что от некоторых ресурсов, возможно, придется отказаться, т. Е. бесплатная утилизация предполагается.

Денежные платежи не допускаются.

Алгоритм

РАМ работает следующим образом.

  • Рассчитайте максимальное количество продуктов; обозначим это z.
  • Для каждого агента я:
    • Рассчитайте максимальное распределение продукта, когда я нет.
    • Позволять жя = (произведение других агентов в z) / (max-произведение других агентов, когда я нет).
    • Передать агенту я фракция жя каждого ресурса, который он получает z.

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

PAM имеет следующие свойства.

  • Это правдивый механизм - полезность каждого агента увеличивается путем раскрытия его истинных оценок.
  • Для каждого агента я, полезность я не менее 1 /е ≈ 0,368 его полезности в распределении max-product.
  • Когда агенты имеют аддитивные линейные оценки, распределение равно без зависти.

PA против VCG

Механизм PA, не использующий платежи, аналогичен Механизм VCG, который использует денежные выплаты. VCG начинается с выбора максимальная сумма распределения, а затем для каждого агента я он вычисляет распределение максимальной суммы, когда я нет, а платит я в разница (максимальная сумма, когда я присутствует) - (максимальная сумма, когда я нет). Поскольку агенты квазилинейны, полезность я уменьшается на добавка фактор.

Напротив, PA не использует денежные платежи, а коммунальные услуги агентов снижаются на мультипликативный фактор, забирая часть их ресурсов.

Оптимальность

Неизвестно, оптимальна ли дробь 0,368. Однако не существует достоверного механизма, который мог бы гарантировать каждому агенту более 0,5 полезности max-product.

Расширения

PAM использовался как подпрограмма в истинном кардинальном механизме одностороннего сопоставления.[2]

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

  1. ^ Коул, Ричард; Гкацелис, Василис; Гоэль, Гаган (2013). «Дизайн механизма справедливого разделения: распределение делимых предметов без платежей». Материалы четырнадцатой конференции ACM по электронной торговле. EC '13. Нью-Йорк, Нью-Йорк, США: ACM: 251–268. arXiv:1212.1522. Дои:10.1145/2492002.2482582. ISBN  9781450319621.
  2. ^ Абебе, Редиет; Коул, Ричард; Гкацелис, Василис; Хартлайн, Джейсон Д. (18 марта 2019 г.). «Правдивый кардинальный механизм для одностороннего сопоставления». arXiv:1903.07797 [cs.GT ].