В конструкции механизма , монотонность является свойством общественного выбора функции. Это необходимое условие для реализации функции с использованием механизма защиты от стратегии . Его словесное описание: [1]
Если изменение типа одного агента (при сохранении типов других агентов фиксированными) изменяет результат в соответствии с функцией социального выбора, то результирующая разница в полезности нового и исходного исходов, оцененных для нового типа этого агента, должна быть не менее как эта разница в утилитах оценивается по исходному типу этого агента.
Другими словами: [2] : 227
Если социальный выбор меняется, когда один игрок меняет свою оценку, то это должно происходить из-за того, что игрок увеличил свою ценность нового выбора по сравнению со своей ценностью старого выбора.
Обозначение
Есть набор возможных результатов.
Есть агенты, которые имеют разные оценки для каждого результата. Оценка агента представлен как функция:
который выражает ценность, которую он присваивает каждой альтернативе.
Вектор всех стоимостных функций обозначается как .
Для каждого агента , вектор всех ценностных функций других агентов обозначается через. Так.
Функция общественного выбора - это функция, которая принимает на вход вектор-значение. и возвращает результат . Обозначается он или же .
В механизмах без денег
Функция социального выбора удовлетворяет свойству сильной монотонности (SMON), если для каждого агента и каждый , если:
Необходимость
Если существует устойчивый к стратегии механизм без денег, с функцией результата, то эта функция должна быть SMON.
ДОКАЗАТЕЛЬСТВО: исправить какой-нибудь агент и некоторый вектор оценки . Устойчивость к стратегии означает, что агент с реальной оценкой слабо предпочитает декларировать чем лгать и заявлять ; следовательно:
В механизмах с деньгами
Когда механизму разрешено использовать деньги, свойство SMON больше не требуется для реализации, поскольку механизм может переключиться на альтернативу, которая менее предпочтительна для агента, и компенсировать этому агенту деньги.
Функция общественного выбора удовлетворяет свойству слабой монотонности (WMON), если для каждого агента и каждый , если:
Необходимость
Если существует устойчивый к стратегии механизм с функцией результата, то эта функция должна быть WMON.
ДОКАЗАТЕЛЬСТВО: [2] : 227 Исправьте какой-нибудь агент и некоторый вектор оценки . Механизм защиты от стратегии имеет функцию цены., который определяет, сколько платежного агента получает, когда результат механизма ; эта цена зависит от результата, но не должна напрямую зависеть от. Устойчивость к стратегии означает, что игрок с оценкой слабо предпочитает декларировать за объявление ; следовательно:
Достаточность
Монотонность не всегда является достаточным условием реализуемости, но в некоторых важных случаях ее достаточно (то есть может быть реализована любая функция социального выбора WMON):
- Когда агенты имеют однопараметрические служебные функции.
- Во многих выпуклых областях, особенно когда диапазон каждой функции значения равен . [1]
- Когда диапазон каждой функции-значения равен , или куб (Gui, Müller, and Vohra (2004)).
- В любой выпуклой области (Saks, Yu (2005)).
- В любой области с выпуклым замыканием. [3]
- В любой «области монотонности». [3]
Примеры
1. Когда агенты имеют предпочтения с одним пиком , функция медианного социального выбора (выбор медианы среди результатов, которые являются лучшими для агентов) сильно монотонна . Действительно, механизм выбора медианного голоса - это правдивый механизм без денег. См. Теорему о среднем избирателе .
2. Когда у агентов есть общие предпочтения, представленные кардинальными функциями полезности . утилитарная функция общественного выбора (выбор результата , который максимизирует сумму оценок агентурных) не сильно монотонная , но это слабо монотонно . В самом деле, это может быть реализовано с помощью механизма VCG , который является надежным механизмом с деньгами.
3. Свойство слабой монотонности имеет особую форму, когда агенты имеют однопараметрические функции полезности .
4. В планировании работы функция социального выбора по минимизации продолжительности работы не является ни сильно монотонной, ни слабо-монотонной. В самом деле, это не может быть реализовано с помощью правдивого механизма; увидеть правдивое планирование работы .
Смотрите также
- Критерий монотонности в системах голосования.
- Монотонность маскина
- Другие значения монотонности в разных областях.
Рекомендации
- ^ а б Бихчандани, Сушил; Чаттерджи, Шуроджит; Лави, Рон; Му'Алем, Ахува; Нисан, Ноам; Сен, Арунава (2006). «Слабая монотонность характеризует реализацию детерминированной доминантной стратегии» (PDF) . Econometrica . 74 (4): 1109. DOI : 10.1111 / j.1468-0262.2006.00695.x .
- ^ а б Вазирани, Виджай В .; Нисан, Ноам ; Roughgarden, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
- ^ а б «Монотонность и реализуемость». Econometrica . 78 (5): 1749–1772. 2010. DOI : 10,3982 / ECTA8882 .