§ 4. Расширенная a – игра

Рассмотрим прямоугольную матрицу A размера n ´ m и отвечающую ей простую A–игру. Множества стратегий первого и второго игроков имеют вид

D = {d₁, ¼, d_n}, Q = {q₁, ¼, q_m}.

Назовем стратегии d_i чистыми стратегиями первого игрока, а q_j – чистыми стратегиями второго игрока.

Можно теперь расширить классы D, Q стратегий игроков, рассмотрев множества

Вектор x = (x₁, ¼, x_n) будем называть смешанной стратегией первого игрока, понимая под этим следующее: в соответствии с этой стратегией первый игрок с вероятностью x_i выбирает чистую стратегию d_i Î D.  Аналогично интерпретируется смешанная стратегия y = (y₁, ¼, y_m) для второго игрока.

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

где T означает транспонирование матрицы-строки y = (y₁, ¼, y_m), а запись xAy^T понимается как произведение трех прямоугольных матриц в соответствии с обычными правилами умножения матриц.

Рекомендуемые материалы

где            - классы смешанных стратегий первого и второго игроков соответственно, ã = ã(x, y) – функция потерь первого игрока вида (1).

Обозначим

Видно, что ã(x,­) – максимальные потери, которые понесет первый игрок, если он будет следовать стратегии x; ã(¯, y) –минимальные потери, которые он понесет, если второй игрок выберет стратегию y.

Определение 1. Число

назовем верхней ценой расширенной A–игры.

назовем нижней ценой расширенной A–игры.

Лемма 1. Имеет место следующее равенство

Стратегии                        , удовлетворяющие  неравенству

 называются оптимальными стратегиями, а  (x, y, ã) – решением игры.

Лемма 2. Пусть число ã является ценой расширенной A–игры.

1) Для  того,   чтобы     стратегия                                 была оптимальной, необходимо и достаточно, чтобы для

выполнялось неравенство:

2) Для того,  чтобы    стратегия                                     была оптимальной, необходимо и достаточно, чтобы  для                

выполнялось неравенство:

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

Лемма 3.   Пусть    число    ã,    стратегии    x = (x₁,¼, x_n),    y = (y₁,¼, y_m) удовлетворяют неравенствам (1), (2). Тогда они являются ценой игры и оптимальными стратегиями первого и второго игроков соответственно.

Если для некоторого индекса j в (1) выполняется строгое неравенство, т.е.                        то соответствующий y_j = 0.

Если для некоторого индекса i  в (2) выполняется строгое неравенство, т.е.                        то соответствующий x_i = 0.   

Доказательства этих лемм можно найти в [   ].

Задачи к § 4

4.1. Рассмотреть А-игру с матрицей потерь первого игрока:

а) найти а^*, а_* и убедиться, что в простой А-игре нет цены;

б) составить систему линейных уравнений и неравенств для

ã, x = (x₁, x₂, x₃),   y = (y₁, y₂, y₃)

в расширенной А-игре;

В лекции "4.9 Параметрические запросы" также много полезной информации.

в) найти решение ã, x, y в расширенной А-игре.

4.2. Для матрицы

решить задачу 4.1.