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

Другими словами, это условие означает следующее. Предположим, что игрок i меняет свое объявление с vi на vi0, и это вызывает изменение социального выбора с a на b. Тогда должнм иметь место следующая ситуация: ценность i для b увеличивается при переходе от vi к vi0 не меньше, чем ценность i для a.

Теорема 10 [35]. Зафиксируем функцию социального выбора f: V ! A, где V – выпуклая, а A – конечная. Тогда существуют цены p такие, что M = (f; p) правдива тогда и только тогда, когда f слабо монотонна.

Таким образом, разработчик должен стремиться к слабо монотонным алгоритмам, и ему не нужно беспокоиться о фактических ценах. Но насколько это сложно? Для одномерных областей оказывается, что W-MON оставляет разработчику алгоритмов достаточно гибкие возможности. Рассмотрим, например, случай, когда каждая альтернатива имеет значение либо 0 (игрок «проигрывает»), либо некоторое v i 2< (игрок «выигрывает» и получает ценность vi). В таком случае нетрудно показать, что W-MON сводится к следующему условию монотонности: если игрок выигрывает при vi и увеличивает свою ценность до v0i > vi (при этом v_, остается фиксированным), то он должен выиграть и при v0i. Более того, в этом случае цена выигрывающего игрока должна быть установлена на инфимум по всем выигрышным ценностям.