Методические указания.

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

Игру иногда удается упростить, если уменьшить в ней число стратегий путем вычеркивания некоторых излишних стратегий. Излишние стратегии – это

1. Дублирующие.
2. Заведомо невыгодные.
3. Пример. Пусть задана матрица игры

Проанализируем строки этой матрицы, т.е. стратегии первого игрока. В этой матрице х₁=х₃ – дублирующие стратегии, оставим одну, например, х₁. При любой стратегии второго игрока (индекс j) f_2j£ f_1j: стратегия х₁ предпочтительнее стратегии х₂. Получилась матрица

Встанем теперь на точку зрения второго игрока и проанализируем столбцы. При любой стратегии первого игрока f_i4£ f_i3 – проигрыш второго игрока в случае y₄ меньше, чем для y₃. Значит, стратегия y₃ – заведомо невыгодная, ее можно убрать. Следовательно, окончательный вид матрицы

От матрицы 4х4 мы пришли к матрице 2х3.В этой игре , – седловой точки нет. Решение игры надо искать в смешанных стратегиях.

Как же найти смешанные стратегии игроков?

Если хотя бы у одного игрока число стратегий не превышает двух, то такие игры могут быть решены аналитически. Рассмотрим решение игр 2х2.

Пусть матрица игры, или платежная матрица А= , и пусть в игре нет седловой точки (иначе она бы решалась очень просто). Тогда решение игры будем искать в смешанных стратегиях: P=(p₁, p₂) - для первого игрока и Q=(q₁, q₂) – для второго. Это значит, что первый игрок будет применять свою первую стратегию х₁ с вероятностью р₁, а свою вторую стратегию х₂ – с вероятностью р₂, причем р₁+р₂=1. Аналогично для второго игрока. Решим эту игру в общем виде с точки зрения второго игрока. Перепишем матрицу игры в следующем виде:

Найдем средний проигрыш второго игрока при первой стратегии первого игрока:

а_11× q₁+a_12× q₂=n

а_21× q₁+a_22× q₂=n, - решим эту систему, вычитая второе уравнение из первого:

(а₁₁-а₂₁)× q₁+(a₁₂-а₂₂)× q₂=0, учитывая, что q₂=1-q₁, получим

(а₁₁-а₂₁-а₁₂+а₂₂)× q₁+(a₁₂-а₂₂)=0.

Отсюдаq₁=(a₁₂-а₂₂)/(а₁₁-а₂₁-а₁₂+а₂₂). Подставляя это значение Q в любое из уравнений, получим значение цены игры n.

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

а_11× p₁+a_21× p₂=n - при первой стратегии второго игрока

а_12× p₁+a_22× p₂=n, - при второй стратегии второго игрока. Дальше решаем систему уравнений любым способом.

Рассмотрим пример. Матрица игрыА= . Составим систему уравнений для второго игрока:

6q₁+2q₂=n

4q₁+8q₂=n, - решая совместно, получим 2q₁-6(1-q₁)=0, или 8q₁=6, или q₁=3/4. Отсюда Q=(3/4, 1/4). Цена игры n =6× 3/4+2× 1/4=5Î [4, 6]. Найдем оптимальную стратегию первого игрока. Поскольку цена игры уже известна, то достаточно написать только одно уравнение для среднего выигрыша:

6p₁+4p₂=5, p₂=1-p₁, откуда р₁=1/2. Следовательно, Р=(1/2, 1/2).

Ответ: P=(1/2, 1/2), Q=(3/4, 1/4), n =5.

Систему уравнений, описывающих средний выигрыш первого игрока или средний проигрыш второго, можно решить также методом Крамера. Во втором случае матрица А= , ее определитель ½ А½ =6× 8-4× 2=40. Тогда q₁= =6n /40, q₂== =2n /40. Поскольку q₁+q₂=1, то из 8n /40=1 следует n =5, а значит Q={3/4; 1/4}. Вероятности P можно найти аналогично, но из транспонированной матрицы А*= , тогда p₁= =4n /40=1/2, учитывая, что цена игры уже определена (n =5), т.е. P={1/2; 1/2}.

КОНТРОЛЬНЫЕ ВОПРОСЫ:

1. Элементы игры.

2. Что такое конфликт?

3. Классификация игр. По каким признакам проводят классификацию?

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

5.Что такое ситуация равновесия?

6. Чем характеризуется гарантированный результат?

7. Алгоритм решения игры.

8. Упрощение игры.