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

Область V, которая удовлетворяет неравенству Vi = <A для всех i, называется «неограниченной областью». Теорема утверждает, что если область неограниченная, выбрано не менее трех альтернатив, а множество A альтернатив конечное, то не может быть реализовано ничего, помимо аффинных максимизаторов.

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

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

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

Разработчики алгоритмов не так сильно заботятся о достижении точки равновесия или выяснении того, что именно будут делать игроки; главная задача состоит в том, чтобы гарантировать оптимальность решения, принимая во внимание стратегическое поведение игроков. Действительно, один из способов достижения этой цели заключается в том, чтобы гарантировать хорошую точку равновесия. Но нет причин исключать механизмы, в которых для игроков существует несколько приемлемых стратегических вариантов, при условии, что аппроксимация будет достигнута в каждом из этих вариантов.

Определение 4 [ ]. Механизм M является «алгоритмической реализацией c-аппроксимации (в недоминируемых стратегиях)», если существует набор стратегий, D, такой, что (1) M получает c-аппроксимацию для любой комбинации стратегий из D за полиномиальное время, и (2) для любой стратегии, не входящей в D, существует стратегия в D, которая слабо доминирует над ней, и этот переход вычислим за полиномиальное время.

Согласно второму условию, разумно предположить, что игрок действительно будет играть, следуя некоторой стратегии из D; а, согласно первому условию, не имеет значения, какой набор стратегий из D будет выбран на самом деле, поскольку любая из них обеспечит аппроксимацию. Это переносит часть бремени с теоретико-игрового проектирования на алгоритмический дизайн, поскольку теперь гарантия аппроксимации должна обеспечиваться для большего диапазона стратегий. [ ] используют это понятие для разработки детерминированного комбинаторного аукциона для многомерных игроков, который достигает гарантии аппроксимации, близкой к оптимальной. Схожим по духу понятием, хотя и более слабым, является понятие «множества Нэша» [25].