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

Правдивое распределение ресурсов - это проблема распределения ресурсов между агентами с разной оценкой ресурсов, таким образом, чтобы агенты были заинтересованы в раскрытии своих истинных оценок по сравнению с Ресурсы.

• 1 Модель
• 2 Цели проектирования
• 3 Алгоритмы
• 4 Связанные проблемы
• 5 Ссылки

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

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

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

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

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

• Утилитарное социальное благополучие --- определяемое как сумма полезностей агентов. Распределение, максимизирующее эту сумму, называется утилитарным или максимальной суммой.
• Социальное благосостояние Нэша --- определяется как продукт полезности агентов. Распределение, максимизирующее этот продукт, называется оптимальным по Нэшу, или максимальным продуктом, или пропорционально-справедливым, и во многих случаях оно эквивалентно конкурентному равновесию при равных доходах.

Простейшим правдивым справедливым механизмом является механизм равного разделения - он дает каждому агенту ровно 1 / n каждого ресурса. Поскольку набор каждого агента фиксированный, механизм правдивый. Однако это не очень эффективно.

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

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

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

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

Чунг улучшил показатели конкуренции в предыдущих работах:

• Соотношение двух агентов и двух ресурсов улучшилось с 0,828 до 5/6 ≈ 0,833 с с механизмом полного распределения и строго больше 5/6 с механизмом частичного распределения. Верхняя граница улучшилась с 0,841 до 5/6 + эпсилон для механизма полного распределения и до 0,8644 для частичного механизма.
• Соотношение для двух агентов и многих ресурсов улучшилось с 2/3 до 0,67776 за счет с использованием средневзвешенного значения двух механизмов: частичного распределения и максимального (частичное распределение, равное разделение).

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

1. ^Стратегия -устойчивое распределение нескольких предметов между двумя агентами без оплаты или предварительной оплаты
2. ^ Коул, Ричард; Гкацелис, Василис; Гоэль, Гаган (2013). «Дизайн механизма справедливого разделения: распределение делимых предметов без платежей». Труды четырнадцатой конференции ACM по электронной торговле. EC '13. Нью-Йорк, Нью-Йорк, США: ACM: 251–268. arXiv : 1212.1522. doi : 10.1145 / 2492002.2482582. ISBN 9781450319621.
3. ^Коул, Ричард; Гкацелис, Василис; Гоэль, Гаган (20.03.2012). «Правдивость, пропорциональная справедливость и эффективность». arXiv : 1203.4627 [cs.GT ].
4. ^Положительные результаты для разработки механизма без денег
5. ^Чунг, Юн Куен (18.04.2016). «Лучшие механизмы защиты от стратегии без платежей или предварительного анализа - аналитический подход». arXiv : 1604.05243 [cs.GT ].
6. ^Кавалло, Руджеро. Двухуровневое распределение ресурсов без денег, совместимое с стимулами. CiteSeerX 10.1.1.432.5462.
7. ^Абебе, Редиет; Коул, Ричард; Гкацелис, Василис; Хартлайн, Джейсон Д. (18 марта 2019 г.). «Правдивый кардинальный механизм для одностороннего сопоставления». arXiv : 1903.07797 [cs.GT ].
8. ^Карагианнис, Иоаннис; Какламанис, Христос; Канеллопулос, Панайотис; Киропулу, Мария (2009). Росси, Франческа; Цукиас, Алексис (ред.). «О низко-завистливых распределениях». Теория алгоритмических решений. Конспект лекций по информатике. Springer Berlin Heidelberg. 5783 : 111–119. DOI : 10.1007 / 978-3-642-04428-1_10. ISBN 9783642044281.
9. ^Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (12 мая 2016 г.). «Об истинных механизмах распределения акций Максимина». arXiv : 1605.04026 [cs.GT ].
10. ^Аманатидис, Георгиос; Бирмпас, Георгиос; Христодулу, Джордж; Маркакис, Евангелос (2017). «Правдивые механизмы распределения без платежей: характеристика и влияние на справедливость». Материалы конференции ACM по экономике и вычислениям 2017 года - EC '17: 545–562. arXiv : 1705.10706. Bibcode : 2017arXiv170510706A. doi :10.1145/3033274.3085147.