Алгоритмический дизайн механизмов: различия между версиями

Как выглядит общий подход к разработке правдивого механизма? Самый простой способ – проверить, существуют ли для заданной функции социального выбора f правдивые цены. Если нет, то следует попытаться «исправить» f. Однако оказывается, что существует более структурированный способ – ''алгоритмическое'' условие, из которого будет следовать ''существование'' правдивых цен. Подобное условие возвращает разработчика на знакомую территорию алгоритмического дизайна. К счастью, такое условие существует, и лучше всего оно излагается в абстрактной постановке задачи социального выбора, описанного в разделе «Постановка задачи»:

Таким образом, разработчик должен стремиться к слабо монотонным алгоритмам, и ему не нужно беспокоиться о фактических ценах. Но насколько это сложно? Для одномерных областей оказывается, что условие W-MON оставляет разработчику алгоритмов достаточно гибкие возможности. Рассмотрим, например, случай, когда каждая альтернатива имеет либо стоимость 0 (игрок «проигрывает»), либо некоторое значение <math>v_i \in \mathfrak{R}</math> (игрок «выигрывает» и получает стоимость <math>v_i</math>). В таком случае нетрудно показать, что W-MON сводится к следующему условию монотонности: если игрок выигрывает при <math>v_i</math> и увеличивает свою стоимость до <math>v'_i > v_i</math> (при этом значение <math>v_{-i}</math> остается фиксированным), то он должен выиграть и при <math>v'_i</math>. Более того, в этом случае цена выигрывающего игрока должна быть установлена на инфимум по всем выигрышным стоимостям.

'''Теорема 11 [34]. Зафиксируем функцию социального выбора <math>f: V \to A</math>, такую, что (1) A конечна, <math>|A| \ge 3</math>, f отображается на A, и (2) <math>V_i = \mathfrak{R}^A</math> для всех i. Тогда функция f реализуема (в доминирующих стратегиях) тогда и только тогда, когда она является аффинным максимизатором.'''

Область V, которая удовлетворяет равенству <math>V_i = \mathfrak{R}^A</math> для всех i, называется ''неограниченной областью''. Теорема утверждает, что если область неограниченная, выбрано не менее трех альтернатив, а множество альтернатив A конечное, то не может быть реализовано ничего, помимо аффинных максимизаторов.