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

'''Теорема 10 [35]. Зафиксируем функцию социального выбора <math>f: V \to A</math>, где V – выпуклая, а A – конечная. Тогда существуют цены p такие, что M = (f, p) правдива тогда и только тогда, когда 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>, остается фиксированным), то он должен выиграть и при v0i. Более того, в этом случае цена выигрывающего игрока должна быть установлена на инфимум по всем выигрышным ценностям.