Честное распределение ресурсов

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

Модель

Имеется m ресурсов, которые предполагаются однородными и делимыми . Примеры:

  • Материалы, такие как дерево или металл;
  • Виртуальные ресурсы, такие как процессорное время или память компьютера;
  • Финансовые ресурсы, такие как акции компаний.

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

Часто предполагается, что функции ценности агентов линейны , так что если агент получает долю r j каждого ресурса j , то его ценность представляет собой сумму r j ∗ v j .

Цели дизайна

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

  • Эффективность по Парето (ПЭ);
  • Утилитарное социальное благосостояние  ———   определяется как сумма полезностей агентов. Распределение, максимизирующее эту сумму, называется утилитарным или max-sum ; это всегда PE.
  • Социальное благосостояние Нэша  —   определяется как произведение полезностей агентов. Распределение, максимизирующее этот продукт, называется оптимальным по Нэшу или максимальным продуктом или пропорционально-справедливым ; это всегда PE. Когда у агентов есть аддитивные полезности , это эквивалентно конкурентному равновесию из равных доходов .

Наиболее распространенными целями справедливости являются:

  • Равное отношение к равным (ETE)   —   если два агента имеют абсолютно одинаковую функцию полезности, то они должны получить абсолютно одинаковую полезность.
  • Свобода от зависти  ———   ни один агент не должен завидовать другому агенту. Это подразумевает ЭТЭ.

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

Тривиальные алгоритмы

Два простых правдивых алгоритма:

  • Алгоритм равного распределения ———   который дает каждому агенту ровно 1/ n каждого ресурса. Это распределение свободно от зависти (и, очевидно ,   ETE), но обычно оно очень неэффективно.
  • Алгоритм последовательной диктатуры ——— который     упорядочивает агентов произвольно и позволяет каждому агенту по очереди брать все ресурсы, которые он хочет, из оставшихся. Это распределение является PE, но обычно оно несправедливо.

Можно смешать эти два механизма и получить правдивый механизм, который будет отчасти справедливым и отчасти эффективным. [1] Но идеальный механизм будет удовлетворять всем трем свойствам одновременно: правдивости, эффективности и справедливости.

Максимум один объект на агента

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

Когда есть 2 агента и 2 объекта, следующий механизм удовлетворяет всем трем свойствам: если каждый агент предпочитает другой объект, дать каждому агенту его предпочтительный объект; если оба агента предпочитают один и тот же объект, дать каждому агенту 1/2 каждого объекта (это PE из-за ограничений по емкости). Однако, когда есть 3 или более агентов, может быть невозможно достичь всех трех свойств.

Чжоу [1] доказал, что при наличии 3 или более агентов, каждый агент должен получить не более 1 объекта, и каждый объект должен быть передан не более чем 1 агенту; ни один истинный механизм не удовлетворяет как PE, так и ETE.

  • Когда имеется несколько единиц каждого объекта (но каждый агент все равно должен получить не более 1 объекта), возникает более слабый результат невозможности: ни один механизм PE и ETE не удовлетворяет условию защищенности от групповой стратегии .
  • Он оставляет открытым более общую настройку распределения ресурсов, при которой каждый агент может получить более одного объекта.

Аналогичные результаты невозможности существуют для агентов с порядковыми полезностями :

  • Для агентов со строгой порядковой полезностью Богомольная и Мулен [2] доказывают, что ни один механизм не удовлетворяет возможной ПЭ, необходимой истинности и ЭТЕ.
  • Для агентов со слабой порядковой полезностью Катта и Сетураман [3] доказывают, что ни один механизм не удовлетворяет требованиям возможной эффективности, возможной правдивости и необходимой свободы от зависти.

См. также: Истинное одностороннее сопоставление. [4]

Алгоритмы аппроксимации

Существует несколько верных алгоритмов, которые находят приближение максимального утилитарного или Нэшовского благосостояния с постоянным множителем.

Го и Коницер [5] изучили особый случай n =2 агентов. Для случая m =2 ресурсов они показали истинный механизм, достигающий 0,828 максимального утилитарного благосостояния, и показали верхнюю границу 0,841. Для случая многих ресурсов они показали, что все истинные механизмы одного и того же вида приближаются к 0,5 максимального утилитарного благосостояния. Их механизмы являются полными — они распределяют все ресурсы.

Коул, Гкатцелис и Гоэль изучали механизмы другого типа - основанные на распределении максимального продукта. Для многих агентов с оценками, которые являются однородными функциями , они показывают правдивый механизм, называемый частичным распределением , который гарантирует каждому агенту по крайней мере 1/ e ≈ 0,368 его/ее полезности в распределении максимального продукта. Их механизм свободен от зависти , когда оценки являются аддитивными линейными функциями. Они показывают, что ни один правдивый механизм не может гарантировать всем агентам более 0,5 их полезности максимального продукта. [6]

Для особого случая n=2 агентов они показывают правдивый механизм, который достигает не менее 0,622 утилитарного благосостояния. [7] Они также показывают, что механизм, запускающий механизм равного распределения и механизм частичного распределения , и выбирающий результат с наивысшим общественным благосостоянием, по-прежнему является правдивым, поскольку оба агента всегда предпочитают один и тот же результат. Более того, он достигает не менее 2/3 оптимального благосостояния. [8] Они также показывают алгоритм для вычисления распределения максимального продукта и показывают, что оптимальное по Нэшу распределение само по себе достигает не менее 0,933 утилитарного благосостояния. О ( м бревно ⁡ м ) {\displaystyle O(м\log м)}

Они также показывают механизм, называемый Strong Demand Matching, который адаптирован для условий с большим количеством агентов и небольшим количеством ресурсов (например, приватизационный аукцион в Чешской Республике ). Механизм гарантирует каждому агенту по крайней мере p / ( p +1) максимальной полезности продукта, когда p является наименьшей равновесной ценой ресурса, когда каждый агент имеет единичный бюджет. Когда агентов намного больше, чем ресурсов, цена каждого ресурса обычно высока, поэтому коэффициент аппроксимации приближается к 1. В частности, когда есть два ресурса, эта доля составляет по крайней мере n / ( n +1). Этот механизм назначает каждому агенту долю одного ресурса. [6]

Чунг [9] улучшил показатели конкурентоспособности предыдущих работ:

  • Соотношение для двух агентов и двух ресурсов улучшилось с 0,828 до 5/6 ≈ 0,833 с механизмом полного распределения и строго больше 5/6 с механизмом частичного распределения. Верхняя граница улучшилась с 0,841 до 5/6+ε для механизма полного распределения и до 0,8644 для частичного механизма.
  • Соотношение для двух агентов и большого количества ресурсов улучшилось с 2/3 до 0,67776 за счет использования средневзвешенного значения двух механизмов: частичного распределения и максимального (частичного распределения, равного разделения).
  • Истинное разрезание торта — вариант задачи, в которой имеется один неоднородный ресурс («торт»), и каждый агент имеет личную меру ценности этого ресурса.
  • Стратегический справедливый раздел — изучение равновесий в играх справедливого раздела, когда агенты действуют стратегически, а не искренне.
  • Справедливое распределение двух видов ресурсов – обильных и дефицитных. [10]
  • Правдивое справедливое разделение неделимых вещей. [11] [12] [13]

Ссылки

  1. ^ ab Zhou, Lin (1990-10-01). «О гипотезе Гейла об односторонних задачах сопоставления». Журнал экономической теории . 52 (1): 123–135. doi :10.1016/0022-0531(90)90070-Z. ISSN  0022-0531.
  2. ^ Богомольная, Анна ; Мулен, Эрве (2001). «Новое решение проблемы случайного назначения». Журнал экономической теории . 100 (2): 295. doi :10.1006/jeth.2000.2710.
  3. ^ Катта, Акшай-Кумар; Сетхураман, Джей (2006). «Решение проблемы случайного назначения в полной области предпочтений». Журнал экономической теории . 131 : 231–250. doi :10.1016/j.jet.2005.05.001.
  4. ^ Абебе, Редьет; Коул, Ричард; Гкацелис, Василис; Хартлайн, Джейсон Д. (18 марта 2019 г.). «Правдивый кардинальный механизм одностороннего сопоставления». arXiv : 1903.07797 [cs.GT].
  5. ^ Го, Минюй; Конитцер, Винсент (2010-05-10). «Стратегически надежное распределение нескольких элементов между двумя агентами без платежей или априорных требований». Труды 9-й Международной конференции по автономным агентам и многоагентным системам: Том 1 - Том 1. AAMAS '10. Richland, SC: Международный фонд автономных агентов и многоагентных систем: 881–888. ISBN 978-0-9826571-1-9.
  6. ^ ab Cole, Richard; Gkatzelis, Vasilis; Goel, Gagan (2013). «Разработка механизма для справедливого разделения». Труды четырнадцатой конференции ACM по электронной коммерции . EC '13. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 251–268. arXiv : 1212.1522 . doi :10.1145/2492002.2482582. ISBN 9781450319621.
  7. ^ Коул, Ричард; Гкатцелис, Василис; Гоэль, Гаган (2012-03-20). «Правдивость, пропорциональная справедливость и эффективность». arXiv : 1203.4627 [cs.GT].
  8. ^ Коул, Ричард; Гкатцелис, Василис; Гоэль, Гаган (2013-05-06). «Положительные результаты для проектирования механизмов без денег». Труды Международной конференции 2013 года по автономным агентам и многоагентным системам . AAMAS '13. Ричленд, Южная Каролина: Международный фонд автономных агентов и многоагентных систем: 1165–1166. ISBN 978-1-4503-1993-5.
  9. ^ Чунг, Юн Куэн (18.04.2016). «Лучшие механизмы, защищающие от стратегий, без платежей или априорных платежей — аналитический подход». arXiv : 1604.05243 [cs.GT].
  10. ^ Кавалло, Руджеро. Совместимое со стимулами двухуровневое распределение ресурсов без денег . CiteSeerX 10.1.1.432.5462 . 
  11. ^ Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria (2009). «On Low-Envy Truthful Allocations». В Rossi, Francesca; Tsoukias, Alexis (ред.). Algorithmic Decision Theory . Lecture Notes in Computer Science. Vol. 5783. Springer Berlin Heidelberg. pp. 111–119. doi :10.1007/978-3-642-04428-1_10. ISBN 9783642044281.
  12. ^ Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (2016-07-09). «О правдивых механизмах распределения максиминных долей». Труды Двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 31–37. arXiv : 1605.04026 . ISBN 978-1-57735-770-4.
  13. ^ Аманатидис, Георгиос; Бирмпас, Георгиос; Христодулу, Джордж; Маркакис, Евангелос (2017). «Механизмы честного распределения без платежей: характеристика и последствия для справедливости». Труды конференции ACM 2017 года по экономике и вычислениям . С. 545–562. arXiv : 1705.10706 . Bibcode :2017arXiv170510706A. doi :10.1145/3033274.3085147. ISBN 9781450345279. S2CID  27249301.
Взято с "https://en.wikipedia.org/w/index.php?title=Истинное_распределение_ресурсов&oldid=1245950768"