Последовательного приближения цены игры

Решение матричных игр при размерах матриц n ´ m больших или равных 3´3 и отсутствии седловых точек в чистых стратегиях или возможности уменьшить размеры матрицы с помощью удаления доминируемых стратегий в общем случае возможно только с помощью численных методов. Рассмотрим один из таких методов - метод последовательного приближения цены игры. В этом методе последовательно разыгрывается множество партий. В каждой партии оба игрока выбирают те стратегии, которые дают им наибольший суммарный выигрыш во всех партиях, включая текущую. После каждой партии вычисляется среднее значение выигрыша v ₁ в одной партии первого игрока, среднее значение проигрыша v ₂ в одной партии второго игрока и полусумма v ₁ и v ₂, которая принимается за приближенное значение цены игры v:

(1)

(2)

(3)

где N - номер разыгрываемой партии; - выигрыши первого игрока в N партиях соответственно при применении своих первой, второй, …, n -й чистой стратегии; n - число чистых стратегий первого игрока; - проигрыши второго игрока в N партиях соответственно при применении своих первой, второй, …, m -й чистой стратегии; m - число чистых стратегий второго игрока.

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

Объем вычислений в этом методе пропорционален сумме числа строк и столбцов исходной матрицы игры.