Материал: 4539

При защите лабораторной работы уметь объяснить изменение резуль-

татов в различных постановках задачи оптимизации.

Практическое занятие 4 Антагонистические игры

Цель работы Получить навыки решения игровых ситуация и их пред-

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

Пусть игрок А имеет m чистых стратегий А1, А2, … Аi,…Аm, а игрок В имеет n чистых стратегий B1, B2, … Bj,…Bn. Такая игра называется игрой m n . Если игрок А пользуется стратегией Аi, а игрок В пользуется стратеги-

ей Вj, то обозначим через аij выигрыш игрока А, если аij > 0, или проигрыш игрока А, если аij < 0. Очевидно, что – это одновременно проигрыш игрока В, если аij > 0, и выигрыш игрока В, если аij < 0.

Тогда мы можем привести игру к матричной форме, т.е. составить мат-

рицу, которая называется платежной матрицей, или матрицей игры:

Каждая строка этой матрицы соответствует некоторой стратегии игро-

ка А, а каждый столбец – некоторой стратегии игрока В.

Пример игры. Два игрока выкидывают на пальцах числа, причем чет-

ное число пальцев – это выигрыш игрока А, нечетное – проигрыш игрока А.

Для простоты введем ограничение – игроки выкидывают от 1 до 3 пальцев.

15

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

i = min аij. j

В нашем примере = -3, т.е. игрок А проигрывает 3 очка. Это число называется нижней ценой игры, а соответствующая ему стратегия называется максиминной. В нашем примере стратегия А1 максиминная, т.е. из всех наи-

худших ситуаций выбирают наилучшую. Эта величина ( ) – гарантирован-

ный «выигрыш» игрока А, какую бы стратегию ни выбрал игрок В.

Меньше нижней цены игры игрок А никогда не «выиграет».

Игрок В старается максимально уменьшить свой проигрыш. Для этого

определяется верхняя цена игры

Соответствующая стратегия называется минимаксной. В нашем приме-

ре будет две минимаксных стратегии В1 и В2. При этом игрок В проигрывает

4 очка.

16

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

Игра с седловой точкой

Пример. Пусть игра задана следующей платежной матрицей:

цена игры = = = 4 min max - лучшая стратегия для игрока В – (В2)

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

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

Рассмотрим платежную матрицу (1). Пусть игрок А использует чистые стратегии А1, А2, … Аi,…Аm с вероятностями p1, p2, … pi,…pm, причем

m

pi =1, а игрок В использует свои чистые стратегии В1, В2, … Вj,…Bn с ве-

i 1

n

роятностями q1, q2, … qj,… qn, причем q j = 1.

j 1

Тогда набор SA ( p1, p2 , pi , pm ) называется смешанной стратеги-

ей игрока А, а набор SB = (q1, q2, … qj,… qn) - смешанной стратегией игрока В.

17

Поскольку игроки выбирают свои стратегии случайным образом, то вероятность выбрать комбинацию АiВj по теории вероятности равна (Pi qj).

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

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

ции (2), т.е. если выполняется следующее условие:

f(SA, S*B ) f(S*A ,S*B ) f(S*A , SB).

Величина = f(S*A , SB) называется ценой игры.

Утверждение. В смешанных стратегиях любая матричная игра имеет

седловую точку, или каждая матричная игра с нулевой суммой имеет реше-

ние в смешанных стратегиях.

Решение игры в смешанных стратегиях

Утверждение. Для того чтобы смешанные стратегии S*A и S*B были оп-

тимальными в игре с матрицей (1) и ценой игры , необходимо и достаточно,

чтобы выполнялись следующие неравенства:

18

(аij >0, i=1, m ,j = 1, n ), тогда цена игры > 0. Найдем оптимальную стратегию

игрока А – (S*A ).

Разделим левую и правую части в выражении (3) на положительную величину :

меньше ( min), тогда имеем следующую задачу линейного программирования:

Если Х* = ( X1* , X*2 ,… X*i … X*m ) – оптимальный план задачи (5) – (7), а

минимум функции f(x) = f(x*) = f*, то цена игры при этом составит = f1* ,

шанная стратегия игрока А.

Для игрока В используя выражение (4), получим

n

g(y) = y j max.

j 1

n

а ij yj 1, i = 1, m .

j 1

yj 0; j = 1, n .

19