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

Таким образом, разработчик должен стремиться к слабо монотонным алгоритмам, и ему не нужно беспокоиться о фактических ценах. Но насколько это сложно? Для одномерных областей оказывается, что 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. Более того, в этом случае цена выигрывающего игрока должна быть установлена на инфимум по всем выигрышным ценностям.

Довольно просто построить алгоритмы, удовлетворяющие условию W-MON для одномерных областей, и для таких областей было получено множество положительных результатов – как в классическом, так и в алгоритмическом дизайне механизмов. Но насколько сложно удовлетворить условие W-MON для многомерных областей? Этот вопрос пока неясен и, похоже, является одной из задач алгоритмического дизайна механизмов. Контраст между одномерностью и многомерностью проявляется во всех предметных областях, рассмотренных выше, и, похоже, отражает некоторую внутреннюю трудность, пока не вполне понятную. Пусть задана функция социального выбора f; она называется ''реализуемой'' (в доминирующих стратегиях), если существуют цены p такие, что M = (f, p) является правдивой. Основной вопрос заключается в том, ''какие формы функций социального выбора являются реализуемыми''.