WikiDer > Монотонность (конструкция механизма)

Monotonicity (mechanism design)

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

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

Другими словами:[2]:227

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

Обозначение

Есть набор возможных результатов.

Есть агенты, которые имеют разные оценки для каждого результата. Оценка агента представлен как функция:

который выражает ценность, которую он присваивает каждой альтернативе.

Вектор всех ценностных функций обозначается .

Для каждого агента , вектор всех ценностных функций Другой агентов обозначается . Так .

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

В механизмах без денег

Функция общественного выбора удовлетворяет сильная монотонность свойство (SMON) если для каждого агента и каждый , если:

тогда:
(по начальным предпочтениям агент предпочитает исходный результат).
(по окончательным предпочтениям агент предпочитает конечный результат). эквивалентно:

Необходимость

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

ДОКАЗАТЕЛЬСТВО: исправить какой-нибудь агент и некоторый вектор оценки . Устойчивость к стратегии означает, что агент с реальной оценкой слабо предпочитает декларировать чем лгать и заявлять ; следовательно:

Точно так же агент с реальной оценкой слабо предпочитает декларировать чем лгать и заявлять ; следовательно:

В механизмах с деньгами

Когда механизму разрешено использовать деньги, свойство SMON больше не требуется для реализации, поскольку механизм может переключиться на альтернативу, которая менее предпочтительна для агента, и компенсировать этому агенту деньги.

Функция общественного выбора удовлетворяет слабая монотонность свойство (WMON) если для каждого агента и каждый , если:

тогда:

Необходимость

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

ДОКАЗАТЕЛЬСТВО:[2]:227 Исправить какой-нибудь агент и некоторый вектор оценки . Механизм защиты от стратегии имеет функцию цены , который определяет, сколько платежного агента получает, когда результат механизма ; эта цена зависит от результата, но не должна напрямую зависеть от . Устойчивость к стратегии означает, что игрок с оценкой слабо предпочитает декларировать за объявление ; следовательно:

Точно так же игрок с оценкой слабо предпочитает декларировать за объявление ; следовательно:
Вычитание второго неравенства из первого дает свойство WMON.

Достаточность

Монотонность не всегда является достаточным условием реализуемости, но в некоторых важных случаях ее достаточно (то есть может быть реализована любая функция социального выбора WMON):

  • Когда агенты однопараметрическая утилита функции.
  • Во многих выпуклых областях, особенно когда диапазон каждой функции значения равен .[1]
  • Когда диапазон каждой функции-значения равен , или куб (Gui, Müller, and Vohra (2004)).
  • В любой выпуклой области (Saks, Yu (2005)).
  • В любой области с выпуклым замыканием.[3]
  • В любой «области монотонности».[3]

Примеры

1. Когда агенты однозначные предпочтения, то медиана функция социального выбора (выбор медианы среди результатов, которые лучше всего подходят для агентов) сильно монотонный. Действительно, механизм выбора медианного голоса - это правдивый механизм без денег. Видеть теорема о среднем избирателе.

2. Когда у агентов есть общие предпочтения, представленные кардинальная полезность функции. то утилитарный функция общественного выбора (выбор результата, который максимизирует сумму оценок агентов) не является строго монотонной, но слабо монотонный. Действительно, это может быть реализовано Механизм VCG, который является правдивый механизм с деньгами.

3. Свойство слабой монотонности приобретает особую форму, когда агенты имеют однопараметрические функции полезности.

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

Смотрите также

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

  1. ^ а б Бихчандани, Сушил; Чаттерджи, Шуроджит; Лави, Рон; Му'Алем, Ахува; Нисан, Ноам; Сен, Арунава (2006). «Слабая монотонность характеризует реализацию детерминированной доминантной стратегии» (PDF). Econometrica. 74 (4): 1109. Дои:10.1111 / j.1468-0262.2006.00695.x.
  2. ^ а б Вазирани, Виджай В.; Нисан, Ноам; Roughgarden, Тим; Тардос, Ива (2007). Алгоритмическая теория игр (PDF). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
  3. ^ а б «Монотонность и реализуемость». Econometrica. 78 (5): 1749–1772. 2010. Дои:10.3982 / ECTA8882.