logo

Решение контрольных по математике!!!

Home Методички по математике Введение в теорию и методы Принятия решений (Дмитриенко В.Д., Кравец В.А., Леонов С.Ю.) 36. Решение матричных игр методом последовательного приближения цены игры

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-й партии имеем следующие приближенные значения цены игры и компонент смешанных стратегий соответственно первого и второго игроков: = 30,40; X = (0,280; 0,640; 0,080); Y = (0,400; 0,320; 0,280). Сопоставление с точным решением этой матричной игры методом линейного программирования (= 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.

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

 
Яндекс.Метрика
Наверх