Материал: 3082

6

возможный средний выигрыш (или минимально возможный средний проигрыш).

В зависимости от количества стратегий игры бывают конечные и

бесконечные.

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

Ограничимся рассмотрением конечных парных игр с нулевой суммой.

1.2.Матричные игры

1.2.1.Матричная игра задается матрицей размерности mxn, которая называется платежной матрицей. В игре участвуют два игрока.

Номер строки i (i =1, ) соответствует номеру стратегии Ai, которую может выбрать первый игрок P1 из m своих возможных стратегий. Второй игрок

проигрывает эту величину. Описанная игра однозначно определяется платежной матрицей. Такую игру называют конечной игрой размерности тхп.

1.2.2. Определение 1.3. Число α = maxminaij называется нижней чистой

ценой игры или максимином, а соответствующая ему стратегия (строка) —

максиминной.

7

Число β = minmaxaij называется верхней чистой ценой игры или

минимаксом , а соответствующая ему стратегия игрока (столбец) —

минимаксной.

Для пары стратегий Аi и Bj их чистые стратегии можно записать в виде: Pi = (0; …; 0; 1; 0; …; 0) и qi = (0; …; 0; 1; 0; …; 0).

Теорема 1.1. В матричной игре нижняя цена игры всегда не превосходит верхней цены игры, то есть α ≤ β.

Если для чистых стратегий выполняется условие: α = β = ν, то игра называется игрой с седловой точкой. Число ν называется ценой игры.

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

Пример 1.1. Найти решение матричной игры, заданной платежной матрицей

8 4 6 5

5 2 1 1

Решение. Найдем максимин и минимакс игры, для чего запишем задачу в табл.1.

8

β = min (8; 4; 6; 7) = 4,

следовательно, цена игры ν = α = β = 4. Для пары стратегий (A1; B2) чистыми стратегиями будут P1 = (0; 1; 0; 0) и q2 = (1; 0; 0; 0), которые являются оптимальными стратегиями игроков.

называется смешанной стратегией первого игрока. Каждая из компонент вектора p показывает относительную частоту использования игроком соответствующей чистой стратегии. Смешанная стратегия второго игрока —

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

Для смешанных стратегий цена игры является функцией смешанных стратегий ν = f(p, q) и определяется по формуле:

выигрышем ν, необходимо и достаточно выполнение неравенств:

9

Таким образом, чтобы проверить то, что (p·, q·, ν) являются решением матричной игры, достаточно проверить условие, удовлетворяют ли p· и q· неравенствам теоремы и уравнениям:

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

Теорема 1.5. Оптимальные смешанные стратегии p* и q* соответственно игроков A и B в матричной игре [aij]mxn с ценой игры ν будут оптимальными и в матричной игре [baij + c]mxn с ценой ν/ = bν + c, где b > 0.

1.3.Приведение матричной игры

кзадаче линейного программирования

1.3.1.Рассмотрим матричную игру размерности mxn с матрицей

Обозначим через р* = (p1; ...; рm) и q* = (q1; …; qn) — оптимальные смешанные стратегии игроков А и В. Стратегия игрока А гарантирует ему выигрыш не меньше ν, независимо от выбора стратегии βj игроком В. Согласно вышеизложенным теоремам запишем:

10

Аналогично стратегия q* игрока В гарантирует ему проигрыш не больше ν независимо от выбора стратегии Ai игроком А, то есть