Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 40

Метод фиктивных розыгрышей.

Предположим, что игроки уже сыграли N раз, причем игрок x k_i^x раз выбрал свою i-ю стратегию, а игрок y k_j^y раз выбрал свою j-ю стратегию. å k_i^x=å k_j^y=N.

Как играть в N+1 раз? В этой ситуации игрок x считает, что y играет по смешанной стратегии q=(k₁^y/N, k₂^y/N,…, k_m^y/N). Тогда математическое ожидание выигрыша 1-ого игрока при условии, что он выберет стратегию i, равно

. Поэтому игрок x выберет свою чистую стратегию   . Аналогично, игрок y выберет свою чистую стратегию   .

Добавляем в текущие суммы таблицы строку I* и столбец j* матрицы f_ij.

Посчитаем кратности и относительные частоты стратегий игроков за 9 шагов:

k^y =(2, 2, 5) ;  k^x =(3, 2, 1, 3).Þ p⁹_опт=(3/9, 2/9, 1/9, 3/9), q⁹_опт=(2/9, 2/9, 5/9).

Теорема (Робинсона-Монро) о методе фиктивных розыгрышей:

1)  Если рассмотреть последовательности частотных векторов : p^N={p^N_i}={ k_i^x/N }, q^N={q^N_j}={ k_j^y/N },  то все предельные точки этих последовательностей являются оптимальными стратегиями:  p^N®p*, q^N®q*.

u(p^N)-u(q^N)®0, где u(p^N)-оптимальный выигрыш второго игрока при условии, что первый играет по стратегии p^N, u(q^N)- оптимальный выигрыш первого игрока при условии, что второй играет по стратегии q^N.
1,56,3,54,5,52,7,50,9,48,11,46,13,44,15,42,17,40,19,38,21,36,23,34,25,32,27,30

2,55,4,53,6,51,8,49,10,47,12,45,14,43,16,41,18,39,20,37,22,35,24,33,26,31,28,29

1,52,3,50,5,48,7,46,9,44,11,42,13,40,15,38,17,36,19,34,21,32,23,30,25,28

2,51,4,49,6,47,8,45,10,43,12,41,14,39,16,37,18,35,20,33,22,31,24,29,26,27