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

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

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

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

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

Обозначения

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

Есть $n$ агенты, которые имеют разные оценки для каждого результата. Оценка агента $i$ представляется в виде функции: $v_{i}:X\longrightarrow R_{+}$ который выражает ценность, которую он присваивает каждой альтернативе.

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

Для каждого агента $i$ вектор всех функций ценности других агентов обозначается через $v_{-i}$ . Так $v\equiv (v_{i},v_{-i})$ .

Функция социального выбора — это функция, которая принимает в качестве входных данных вектор ценностей. $v$ и возвращает результат $x\in X$ . Это обозначается ${\text{Outcome}}(v)$ или ${\text{Outcome}}(v_{i},v_{-i})$ .

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

Функция социального выбора удовлетворяет свойству сильной монотонности (SMON), если для каждого агента $i$ и каждый $v_{i},v_{i}',v_{-i}$ , если: $x={\text{Outcome}}(v_{i},v_{-i})$ $x'={\text{Outcome}}(v'_{i},v_{-i})$ затем: $x\succeq _{i}x'$ (по первоначальным предпочтениям агент предпочитает первоначальный результат). $x\preceq _{i'}x'$ (по окончательным предпочтениям агент предпочитает конечный результат). Или эквивалентно: $v_{i}(x)-v_{i}(x')\geq 0$ $v_{i}'(x)-v_{i}'(x')\leq 0$

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

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

ДОКАЗАТЕЛЬСТВО: почините какого-нибудь агента. $i$ и некоторый вектор оценки $v_{-i}$ . Стратегическая устойчивость означает, что агент с реальной оценкой $v_{i}$ слабо предпочитает заявлять $v_{i}$ чем лгать и заявлять $v_{i}'$ ; следовательно: $v_{i}(x)\geq v_{i}(x')$ Аналогично, агент с реальной оценкой $v_{i}'$ слабо предпочитает заявлять $v_{i}'$ чем лгать и заявлять $v_{i}$ ; следовательно: $v_{i}'(x')\geq v_{i}'(x)$

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

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

Функция социального выбора удовлетворяет свойству слабой монотонности (WMON), если для каждого агента $i$ и каждый $v_{i},v_{i}',v_{-i}$ , если: $x={\text{Outcome}}(v_{i},v_{-i})$ $x'={\text{Outcome}}(v'_{i},v_{-i})$ затем: $v_{i}(x)-v_{i}(x')\geq v_{i}'(x)-v_{i}'(x')$

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

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

ДОКАЗАТЕЛЬСТВО: ^[2]^: 227 Исправьте какого-нибудь агента $i$ и некоторый вектор оценки $v_{-i}$ . Устойчивый к стратегии механизм имеет функцию цены. $Price_{i}(x,v_{-i})$ , который определяет, сколько платежного агента $i$ получает, когда результат механизма $x$ ; эта цена зависит от результата, но не должна зависеть напрямую от $v_{i}$ . Устойчивость к стратегии означает, что игрок с оценкой $v_{i}$ слабо предпочитает заявлять $v_{i}$ чрезмерное объявление $v_{i}'$ ; следовательно: $v_{i}(x)+{\text{Price}}_{i}(x,v_{-i})\geq v_{i}(x')+{\text{Price}}_{i}(x',v_{-i})$ Аналогично, игрок с оценкой $v_{i}'$ слабо предпочитает заявлять $v_{i}'$ чрезмерное объявление $v_{i}$ ; следовательно: $v_{i}'(x)+{\text{Price}}_{i}(x,v_{-i})\leq v_{i}'(x')+{\text{Price}}_{i}(x',v_{-i})$ Вычитание второго неравенства из первого дает свойство WMON.

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

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

Когда агенты имеют служебные функции с одним параметром .
Во многих выпуклых областях, особенно когда диапазон каждой функции значения равен $\mathbb {R} ^{+}$ . ^[1]
Когда диапазон каждой функции значения равен $\mathbb {R}$ или куб (Ги, Мюллер и Вохра (2004)).
В любой выпуклой области (Сакс и Ю (2005)).
В любой области с выпуклым замыканием. ^[3]
В любой «области монотонности». ^[3]

Примеры

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

См. также

Критерий монотонности в системах голосования.
Маска монотонности
Другие значения монотонности в разных областях.

Ссылки

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

[wmon06-1] Jump up to: ^а ^б Бикчандани, Сушил; Чаттерджи, Шуроджит; Лави, Рон; Муалем, Ахува; Нисан, Ноам; Сен, Арунава (2006). «Слабая монотонность характеризует реализацию детерминированной доминантной стратегии» (PDF) . Эконометрика . 74 (4): 1109. doi : 10.1111/j.1468-0262.2006.00695.x . S2CID 6210226 .

[agt07-2] Jump up to: ^а ^б Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0 .

[Ashlagi12-3] Jump up to: ^а ^б «Монотонность и реализуемость». Эконометрика . 78 (5): 1749–1772. 2010. номер документа : 10.3982/ECTA8882 . S2CID 1024035 .

[1]

[2]

[3]