Как имитировать равновесие Нэша

Question

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

Может кто-нибудь, пожалуйста, скажите мне, как я могу найти одну из этих точек равновесия путем численного моделирования?

Я не могу найти в книге какое-либо объяснение того, как имитировать. Мне просто нужно основное направление.

Я задал этот вопрос в math.stackexchange, но решил задать здесь также, если это подходящее место для алгоритмов.

спасибо.

Answer 1

Это зависит от того, что у вас есть, в некоторых случаях это невозможно, а в других (2xN игры с нулевой суммой, потенциальная игра) это может быть дорого.

Если в игре есть чистое равновесие Нэша, то алгоритм фиктивной игры Брауна, а затем улучшенный Бергером, может найти его [G. У. Браун, Итеративное решение игр фиктивной игрой, MIT Press, 1998 и Бергер, оригинальная фиктивная игра Брауна, Journal of Economic Theory, 2007]. Стихастическая версия была предложена Смирнакисом & Лесли [Michail Smyrnakis et David Leslie, Stochastic Fictitious Play с использованием фильтров частиц для обновления убеждений стратегий противников, 2008]. Сначала вы можете просмотреть страницу википедии: http://en.wikipedia.org/wiki/Fictitious_play.

Если вы ищете смешанный NE, это еще более сложно, и некоторый алгоритм обучения может быть довольно плохим, в то время как другие лучше. Мне лично нравится книга Цеза-Бьянки и Лугоши, Прогнозирование, Обучение и Игры, http://homes.di.unimi.it/~cesabian/predbook/. Другие люди любят также Алгоритмическую Теорию игры Нисана.