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

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

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

В качестве первого шага возникает соблазн позволить игрокам попытаться улучшить базовый результат, разрешив им лгать. Однако это может привести к неожиданной динамике процесса, поскольку каждый игрок выбирает свое ложное действие, исходя из некоторых предположений о ложных действиях остальных, и этот процесс становится самоподдерживающимся. Чтобы избежать подобной непредсказуемой ситуации, важно настаивать на использовании строгих теоретико-игровых рассуждений, чтобы точно объяснить, почему результат будет удовлетворительным.