Равновесие по Нэшу - Программа построения равновесных стратегий для игры

В теории игр равновесием по Нэшу называется ситуация при который ни один из игроков не может увеличить свой выигрыш, в одностороннем порядке меняя свое решение. Допустим - игра n лиц в нормальной форме, где - набор чистых стратегий, а - набор выигрышей. Когда каждый игрок выбирает стратегию в профиле стратегий, игрок получает выигрыш. Профиль стратегий является равновесным по Нэшу, если изменения своей стратегии с на не выгодно ни одному игроку, то есть для любого :

В 1951 году Д. Нэш в своей работе по некорпоративным играм доказал, что в любой конечной игре будет существовать хотя бы одно равновесие в чистых или смешанных (то есть при выборе чистой стратегии стохастический с фиксированной частотой) стратегиях. Так как игра Omaha в модели Jam-Fold является конечной, то в ней будет существовать хотя бы одно равновесие по Нэшу.

Существует несколько методов нахождения равновесия по Нэшу в игре. В основном они основываются на работе с матричным представлением игры. Но так как у решаемой нами игры огромное количество чистых стратегий, использовать ее матричное представление проблематично. Для поиска равновесия Нэша в данной игре хорошо подойдет метод фиктивного разыгрывания. Суть этого метода в том, что для каждого игрока находится оптимальная чистая стратегия против смешанной стратегии соперника, потом эта стратегия добавляют в смешанную стратегию игрока. В 1951 году было доказано, что в антагонистической игре для двух игроков при многократном повторении этого алгоритма смешанные стратегии игроков будут стремится к равновесию по Нэшу [13]. Таким образом с помощью этого метода за конечное число итераций возможно найти равновесие по Нэшу в заданной игре.

Для того что бы определить оптимальную стратегию игрока A против стратегии игрока B, нам необходимо найти множество играемых кластеров карт для которых математическое ожидание игры против стратегии игрока B будет больше ноля:

, где

- множество кластеров начальных комбинаций при которых стратегия игрока A будет играть AllIn,

- множество кластеров начальных комбинаций при которых стратегия игрока B будет играть AllIn,

- множество кластеров возможных начальных комбинаций,

- множество исходов при вскрытии карт у двух игроков,

- множество выигрышей при конкретных исходах,

- множество вероятностей начальных комбинаций двух игроков,

- таблица предрасчетных данных.

Таким образом в самом худшем случае нам понадобится не более вариантов перебора.

Похожие статьи




Равновесие по Нэшу - Программа построения равновесных стратегий для игры

Предыдущая | Следующая