Проиллюстрируем итерационный метод Брауна-Робинсон на при мере игры, заданной матрицей

(здесь maxmin =0, minmax =2, следовательно, седловой точки нет).

Опишем правила выбора ходов игроками, предположив, для определенности, что начинает игрок А.

1-й шаг.

Ход игрока А - стратегия Ах

2-й шаг.

Игрок В выбирает свою стратегию так, чтобы выигрыш игрока А был минимален (отмечен выше полужирным шрифтом). Ход игрока В - стратегия 2?2

с. 27).

(2 0 3).

Замечание. Выводя теорему о разрешимости любой матричной игры из теоремы двойственности линейного программирования, мы обращаем реальную историческую последовательность событий. Дело в том, что фон Нейман доказал свою теорему о минимаксе задолго до появления линейного программирования. Более того, первое доказательство теоремы двойственности, предложенное Гейлом, Куном и Таккером в 1951 году, опиралось на результаты фон Неймана ([3], с 403).

Итерационный метод решения матричных игр

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

Метод был предложен Г. Брауном в 1949 году [4]. Позже, в 1950 году, Дж. Робинсон опубликовала доказательство его сходимости (см. [5],

Игрок Л выбирает свою стратегию так, чтобы его выигрыш при стратегии В2 игрока В был максимален (отмечен выше полужирным шрифтом).

Ход игрока А - стратегия А2

(1 3 -3).

Игрок В выбирает свою стратегию так, чтобы накопленный выигрыш игрока А при стратегиях Ах и А2,

(2 0 3) + (1 3 - 3) = (3 3 0),

был минимален. 3-й шаг.

Ход игрока В - стратегия В3

Игрок А выбирает свою стратегию так, чтобы его накопленный выигрыш при стратегиях Bi и В3 игрока В9

был максимален.

Ход игрока А - стратегия Ах

(2 0 3).

Игрок В выбирает свою стратегию так, чтобы накопленный выигрыш игрока А при стратегиях Аи А2 и Аи

(3 3 0) + (2 0 3) = (5 3 3),

был минимален.

Ход игрока В - стратегия J?2

и т.д.

Разобьем последовательные ходы игроков А и В на пары (ход игрока А, ход игрока В) и запишем результаты первых десяти шагов в таблице

Описание таблицы.

1-й столбец - номер п шага (пары последовательных ходов игроков А п В),

2-й столбец - номер / стратегии, выбранной игроком А,

3-й столбец - накопленный суммарный выигрыш игрока А за первые п шагов при выборе игроком В стратегии Ви

4-й столбец - накопленный суммарный выигрыш игрока А за первые п шагов при выборе игроком В стратегии В2,

5-й столбец - накопленный суммарный выигрыш игрока А за первые п шагов при выборе игроком В стратегии В3 (минимальный из этих выигрышей выделяется полужирным шрифтом),

6-й столбец - минимальный средний выигрыш игрока А, равный минимальному накопленному им выигрышу за первые п шагов, деленному на число этих шагов,

7-й столбец - номер к стратегии, выбранной игроком Я,

8-й столбец - накопленный суммарный выигрыш игрока А за первые п шагов при выборе им стратегии Ai9

9-й столбец - накопленный суммарный выигрыш игрока А за первые п шагов при выборе им стратегии А2 (максимальный из этих выигрышей выделяется полужирным шрифтом),

10-й столбец - максимальный средний выигрыш игрока А, равный максимальному накопленному им выигрышу за первые п шагов, деленному на число этих шагов,

11-й столбец - среднее арифметическое минимального среднего выигрыша и максимального среднего выигрыша игрока А.

Значение игры определяется приближенно по окончании любого из шагов.