36. Решение матричных игр методом последовательного приближения цены игры

Решение матричных игр при размерах матриц N ´ M больших или равных 3 ´ 3 и отсутствии седловых точек в чистых стратегиях или возможности уменьшить размеры матрицы с помощью удаления доминируемых стратегий в общем случае возможно только с помощью численных методов. Рассмотрим один из таких методов - метод последовательного приближения цены игры. В этом методе последовательно разыгрывается много партий. В каждой партии оба игрока выбирают те стратегии, которые дают им наибольший суммарный выигрыш во всех партиях, включая текущую. После каждой партии матричной игры вычисляется среднее значение выигрыша V1 в одной партии первого игрока, среднее значение проигрыша V2 в одной партии второго игрока и полусумма V1 и V2, которая принимается за приближенное значение цены матричной игры V:

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

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

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

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

Пример 3.11. Рассмотрим пример решения игры этим методом. Пусть игра задана следующей матрицей

Применение любого численного метода для решения матричной игры необходимо начинать с определения нижней чистой цены игры a и верхней чистой цены игры b. Это позволит избежать применения численных методов решения матричных игр в тех случаях, когда решение может быть найдено в чистых стратегиях. В нашем случае имеем:

Итак, и решение матричной игры необходимо искать численным методом. Предположим, что в первой партии второй игрок выбрал свою первую стратегию, тогда, если первый игрок выберет свою первую стратегию, то он выиграет 50, если вторую - 25, если третью - 10. Сведем полученные результаты в таблицу (табл. 3.3). Из анализа колонки ²Суммарный выигрыш первого игрока по стратегиям² следует, что первая стратегия первого игрока приносит ему наибольший выигрыш. Поэтому первый игрок и должен выбрать свою первую чистую стратегию (см. колонку ²Стратегия первого игрока²). В этом случае, если второй игрок выбирает свою первую стратегию, то он проигрывает 50, если вторую - 15, если третью - 20. Наибольший выигрыш, который может получить первый игрок в первой партии, равен 50, поскольку

Аналогично, получается наименьший возможный проигрыш второго игрока

Зная и , несложно вычислить их полусумму, т. е. приближенное значение цены игры после первой партии: V = (50 + 15)/2 = 32,5.

Поскольку лучший результат в первой партии второму игроку принесла вторая стратегия (проигрыш равен 15), то он ее и должен выбрать во второй партии. В этом случае применение первой стратегии первым игроком принесет ему выигрыш в 15 единиц, суммируя его с выигрышем, полученным с помощью этой же стратегии в первой партии, получаем 65.

Таблица 3.3

Применение первым игроком своей второй стратегии в текущей партии приносит ему выигрыш в 40 единиц и суммарный выигрыш в двух партиях - 65. Аналогично, применение третьей стратегии первым игроком приносит ему выигрыш в текущей партии в 30 единиц и суммарный выигрыш в двух партиях - 40. Наибольший выигрыш в двух партиях первому игроку обеспечили сразу две стратегии: первая и вторая.

В общем случае с точки зрения обеспечения устойчивости решения в следующей партии лучше выбирать ту стратегию, которая была в предшествующей партии. Поэтому во второй партии первый игрок применяет свою первую стратегию. Если в ответ на это второй игрок выбирает свою первую стратегию, то он проигрывает в текущей партии 50 и 100 в двух партиях, если выбирает вторую стратегию, то проигрывает во второй партии 15 и 30 в двух партиях, если выбирает третью стратегию, то соответственно проигрывает 20 и 40. Средний выигрыш первого игрока в двух партиях равен: = 65/2 = 32,5; средний проигрыш второго игрока в двух партиях: =30/2 = 15. Приближенное значение цены игры по результатам двух партий

В третьей и последующих партиях процесс вычислений и заполнения таблицы происходит аналогично.

После 25-й партии имеем следующие приближенные значения цены игры и компонент смешанных стратегий соответственно первого и второго игроков: V = 30,40; X = (0,280; 0,640; 0,080); Y = (0,400; 0,320; 0,280). Сопоставление с точным решением этой матричной игры методом линейного программирования (V = 30,77; X = (0,314; 0,554; 0,132); Y = (0,409; 0,289; 0,302)) показывает удовлетворительную точность в определении цены игры и значительную погрешность в определении компонент смешанных стратегий обоих игроков. Эта погрешность объясняется тем, что в рассматриваемом численном методе применяемые игроками стратегии изменяются не после одной, двух или трех партий, а нерегулярно: восемь раз подряд в партиях с 14-й по 21-ю применялась стратегия два первым игроком; пять раз подряд (партии 8 – 12) - стратегия один второго игрока; в 18 партиях подряд (с 8-й по 25-ю) не применялась третья стратегия первого игрока и т. д. Для того чтобы эта нерегулярность не оказывала существенного влияния на конечный результат, необходим расчет сотен партий. Действительно, если потребовать, чтобы погрешность d определения компонент смешанных стратегий не превышала, допустим, 0,01, а в последовательности партий наблюдаются M‑Кратные появления подряд одной из стратегий любого из игроков, то, в первом приближении, число партий N можно оценить следующим образом:

,

Где M - наибольшая кратность появления подряд одной из стратегий любого из игроков.

При M = 8, d = 0,01 получаем, что число партий должно быть не менее 800.

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

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