Правдивое распределение ресурсов - это проблема распределения ресурсов между агентами с разной оценкой ресурсов, чтобы у агентов был стимул раскрыть свою истинную оценку ресурсов.
Модель
Предполагается, что есть m ресурсов, которые являются однородными и делимыми . Примеры:
- Материалы, такие как дерево или металл;
- Виртуальные ресурсы, такие как процессорное время или память компьютера;
- Финансовые ресурсы, такие как акции фирм.
Есть n агентов. У каждого агента есть функция, которая присваивает числовое значение каждому «пакету» (комбинации ресурсов).
Часто предполагается, что функции ценности агентов линейны , так что если агент получает долю r j от каждого ресурса j , то его / ее ценность является суммой r j * v j .
Цели дизайна
Цель состоит в том, чтобы разработать правдивый механизм , который побудит агентов раскрыть свои истинные функции ценности, а затем вычислить распределение, которое максимизирует некоторую глобальную цель. Две наиболее изученные цели:
- Утилитаристское социальное благосостояние - определяется как сумма полезностей агентов. Распределение, максимизирующее эту сумму, называется утилитарным или максимальной суммой .
- Социальное благосостояние Нэша --- определяется как продукт полезности агентов. Распределение, максимизирующее этот продукт, называется оптимальным по Нэшу, или максимальным продуктом, или пропорционально-справедливым , и во многих случаях оно эквивалентно конкурентному равновесию при равных доходах .
Алгоритмы
Простейшим правдивым справедливым механизмом является механизм равного разделения - он дает каждому агенту ровно 1 / n каждого ресурса. Поскольку набор каждого агента фиксирован, механизм правдивый. Однако это не очень эффективно.
Гуо и Конитцер [1] изучали частный случай n = 2 агентов. Для случая m = 2 ресурсов они показали истинный механизм достижения 0,828 максимального утилитарного благосостояния и показали верхнюю границу 0,841. На примере многих ресурсов они показали, что все правдивые механизмы одного и того же вида приближаются к 0,5 от максимального утилитарного благосостояния. Их механизмы завершены - они распределяют все ресурсы.
Коул, Гкатзелис и Гоэл изучали механизмы другого типа - на основе распределения max-product. Для многих агентов с оценками, которые являются однородными функциями , они демонстрируют правдивый механизм, называемый частичным распределением, который гарантирует каждому агенту по крайней мере 1 / e ≈ 0,368 его / ее полезности в распределении максимального продукта. Их механизм не вызывает зависти, когда оценки являются аддитивными линейными функциями. Они показывают, что никакой правдивый механизм не может гарантировать всем агентам более 0,5 их максимальной полезности продукта. [2]
Для частного случая n = 2 агентов они демонстрируют правдивый механизм, который достигает по крайней мере 0,622 утилитарного благосостояния. [3] Они также показывают, что механизм, запускающий механизм равного разделения и механизм частичного распределения , и выбор результата с наивысшим социальным благосостоянием, по-прежнему правдив, поскольку оба агента всегда предпочитают один и тот же результат. Более того, он достигает не менее 2/3 оптимального уровня благосостояния. [4] Они также показывают алгоритм O ( m log m ) для вычисления распределения максимального продукта и показывают, что само оптимальное распределение по Нэшу достигает по крайней мере 0,933 утилитарного благосостояния.
Они также демонстрируют механизм под названием Strong Demand Matching, который адаптирован для условий с большим количеством агентов и небольшими ресурсами (например, приватизационный аукцион в Чешской республике ). Механизм гарантирует каждому агенту по крайней мере p / ( p +1) максимальной полезности продукта, когда p - наименьшая равновесная цена ресурса, когда каждый агент имеет единичный бюджет. Когда агентов намного больше, чем ресурсов, цена каждого ресурса обычно высока, поэтому коэффициент приближения приближается к 1. В частности, при наличии двух ресурсов эта доля составляет не менее n / ( n +1). Этот механизм назначает каждому агенту долю одного ресурса. [2]
Чунг [5] улучшил конкурентоспособность предыдущих работ:
- Соотношение для двух агентов и двух ресурсов улучшилось с 0,828 до 5/6 ≈ 0,833 с механизмом полного распределения и строго более 5/6 с механизмом частичного распределения. Верхняя граница улучшилась с 0,841 до 5/6 + эпсилон для механизма полного распределения и до 0,8644 для частичного механизма.
- Отношение для двух агентов и многих ресурсов улучшилось с 2/3 до 0,67776 за счет использования средневзвешенного значения двух механизмов: частичного распределения и максимального (частичное распределение, равное разделение).
Связанные проблемы
- Правдивое разрезание торта - вариант проблемы, в котором есть единственный разнородный ресурс («пирог»), и каждый агент имеет личную меру ценности над ресурсом.
- Стратегическое справедливое разделение - исследование равновесий в играх с честным разделением, когда агенты действуют стратегически, а не искренне.
- Правдивое распределение двух видов ресурсов - обильных и дефицитных. [6]
- Правдивое одностороннее сопоставление. [7]
- Правдивое честное разделение неделимых предметов. [8] [9] [10]
Рекомендации
- ^ Стратегически обоснованное распределение нескольких предметов между двумя агентами без платежей или предварительных требований
- ^ a b Коул, Ричард; Гкацелис, Василис; Гоэль, Гаган (2013). «Дизайн механизма справедливого разделения: распределение делимых предметов без платежей». Материалы четырнадцатой конференции ACM по электронной торговле . EC '13. Нью-Йорк, Нью-Йорк, США: ACM: 251–268. arXiv : 1212.1522 . DOI : 10.1145 / 2492002.2482582 . ISBN 9781450319621.
- ^ Коул, Ричард; Гкацелис, Василис; Гоэль, Гаган (2012-03-20). «Правдивость, пропорциональная справедливость и эффективность». arXiv : 1203.4627 [ cs.GT ].
- ^ Положительные результаты по конструкции механизма без денег
- ^ Чунг, Юн Куен (18.04.2016). «Лучшие механизмы защиты от стратегии без платежей или предварительного анализа - аналитический подход». arXiv : 1604.05243 [ cs.GT ].
- ^ Кавалло, Руджеро. Двухуровневое распределение ресурсов без денег, совместимое с поощрением . CiteSeerX 10.1.1.432.5462 .
- ^ Абебе, Редиет; Коул, Ричард; Гкацелис, Василис; Хартлайн, Джейсон Д. (18 марта 2019 г.). «Правдивый кардинальный механизм для одностороннего сопоставления». arXiv : 1903.07797 [ cs.GT ].
- ^ Карагианнис, Иоаннис; Какламанис, Христос; Канеллопулос, Панайотис; Киропулу, Мария (2009). Росси, Франческа; Цукиас, Алексис (ред.). «О незавидных правдивых распределениях». Теория алгоритмических решений . Конспект лекций по информатике. Springer Berlin Heidelberg. 5783 : 111–119. DOI : 10.1007 / 978-3-642-04428-1_10 . ISBN 9783642044281.
- ^ Аманатидис, Георгиос; Бирмпас, Георгиос; Маркакис, Евангелос (12 мая 2016 г.). «Об истинных механизмах распределения акций Максимина». arXiv : 1605.04026 [ cs.GT ].
- ^ Аманатидис, Георгиос; Бирмпас, Георгиос; Христодулу, Джордж; Маркакис, Евангелос (2017). «Правдивые механизмы распределения без платежей: характеристика и влияние на справедливость». Труды конференции ACM по экономике и вычислениям 2017 года - EC '17 : 545–562. arXiv : 1705.10706 . Bibcode : 2017arXiv170510706A . DOI : 10.1145 / 3033274.3085147 .