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

'''Теорема 11 [34]. Зафиксируем функцию социального выбора <math>f: V \to A</math>, таких, что (1) A конечна, <math>|A| \ge 3</math>, и f отображается на A, и (2) <math>V_i = \mathfrak{R}^A</math> для всех i. Тогда f реализуема (в доминирующих стратегиях) тогда и только тогда, когда она является аффинным максимизатором.'''

Область V, которая удовлетворяет неравенству <math>V_i = \mathfrak{R}^A</math> для всех i, называется «неограниченной областью». Теорема утверждает, что если область неограниченная, выбрано не менее трех альтернатив, а множество A альтернатив конечное, то не может быть реализовано ничего, помимо аффинных максимизаторов.

'''Теорема 12 [23]. Любой правдивый комбинаторный аукцион или многотоварный аукцион между двумя игроками, который всегда должен распределять все имеющиеся товары и который аппроксимирует благосостояние на коэффициент лучше 2, должен быть аффинным максимизатором.'''

Конечно, это далеко не полный ответ. Что произойдет, если игроков будет больше двух? Что будет, если часть предметов можно будет «выбросить»? Эти вопросы, а также более общий и абстрактный вопрос о характеристиках, все еще остаются открытыми.