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

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

Как уже было сказано в начале, функция социального выбора, максимизирующая благосостояние, является реализуемой. Эта конкретная функция может быть слегка обобщена при помощи добавления весовых коэффициентов следующим образом: зафиксируйте некоторые неотрицательные вещественные константы fwigni=1 (не все они равны нулю) и {ya}aeA> и выберите альтернативу, которая максимизирует взвешенное социальное благосостояние, т. е. f(v) 2 argmaxa2A Pi wivi(a) + Ya-. Этот класс функций иногда называют «аффинными максимизаторами». Оказывается, что эти функции также реализуемы, с ценами, близкими по духу к алгоритму ВКГ. В контексте вышеупомянутого вопроса о характеристиках выделяется один особенный результат:

Теорема 11 [ ]. Зафиксируем функцию социального выбора f: V ! A, таких, что (i) A конечна, |A| > 3, и f отображается на A, и (ii) Vi = <A для всех i. Тогда f реализуема (в доминирующих стратегиях) тогда и только тогда, когда она является аффинным максимизатором.