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

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

'''Определение 3 [8, 23]'''. Функция социального выбора <math>f: V \to A</math> является «слабо монотонной» (W-MON), если для любых <math>i, v_{- i} \in V_{- i}</math> и любых <math>v, v_{-i} \in V_i</math> выполняется следующее условие. Предположим, что <math>f(v_i, v_{-i}) = a</math> и <math>f(v'_i, v_{-i}) = b</math>. Тогда <math>v'_i(b) - v_i(b) \ge v'_i(a) - v_i(a)</math>.

Другими словами, это условие означает следующее. Предположим, что игрок i меняет свое объявление с <math>v_i</math> на <math>v'_i</math>, и это вызывает изменение социального выбора с a на b. Тогда должна иметь место следующая ситуация: стоимость i для b увеличивается при переходе от <math>v_i</math> к <math>v'_i</math> не меньше, чем стоимость i для a.