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

Однако предположение о том, что область является неограниченной, оказывается очень ограничивающим. Все приведенные выше примеры областей имеют некоторую базовую комбинаторную структуру и, следовательно, в той или иной степени ограничены. И, как обсуждалось выше, для многих ограниченных областей теорема просто не верна. Где же пролегает граница возможного и невозможного? Как уже говорилось выше, это нерешенная проблема. Лави, Муалем и Нисан [23] исследовали этот вопрос для комбинаторных аукционов и подобных ограниченных областей и получили частичные ответы. Например:

В свете выводов, сделанных в предыдущем разделе, естественной идеей будет пересмотр используемой ''концепции решения''. Правдивость опирается на сильную концепцию доминирующих стратегий: для каждого игрока существует уникальная стратегия, которая максимизирует его полезность независимо от того, что делают другие игроки. Это очень сильная концепция, но она очень хорошо подходит способам мышления в вычислительных науках, относящихся к наихудшему случаю. Какие еще концепции решения могут быть использованы? Как упомянуто выше, могут оказаться полезными рандомизация и ожидаемая правдивость. Родственной концепцией, опять же связанной с рандомизированными механизмами, является правдивость с высокой вероятностью. Другим направлением является рассмотрение механизмов, в которых игроки не могут ''слишком сильно'' улучшить свою полезность за счет отклонения от стратегии правдивости [21].