Лекция 10. Антагонистические игры

Это игры, которые часто встречаются в военном деле.

Антагонистические игры – игры с нулевой суммой.

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

или

Игра полностью определяется одной платежной матрицей:

Которую можно одновременно интерпретировать как матрицу выигрышей первого игрока или как матрицу проигрышей второго игрока (поэтому такие игры называются также матричными).

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

Рассмотрим пример платежной матрицы антагонистической игры.

				min
	5	1	3	1
	3	2	4	2
	-3	0	1	-3
max	5	2	4

Пусть дана платежная матрица

			…		min
			…
			…
…	…	…	…	…	…
			…

В основе рассуждений игроков лежит принцип гарантированного результата:

Первый игрок: «Выбираю стратегию , максимизирующую мой гарантированный выигрыш»

,

т.е. выбираю стратегию из условия

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

В примере , т.е. максиминной статегией является стратегия .

Второй игрок: «Выбираю стратегию , минимизирующую гарантированный проигрыш»

,

т.е. выбираю стратегию из условия:

;

Величина называется верхним проигрышем 2-го игрока в чистых стратегиях, а стратегия , вытекающая из принципа гарантированного результата – его минимаксной стратегией.

В примере , т.е. минимаксной статегией является стратегия .

Для произвольной платежной матрицы A:

Действительно,

,

т.к.

то

то

Сравнивая, получаем:

т.е.

Если , т.е. если

то говорят, что матрица A=( имеет седловую точку (i*,j*) и платеж в этой точке

называют ценой игры.

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

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

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

Равновесная ситуация ( в чистых стратегиях игроков называется парой их оптимальных стратегий игры.

Решением антагонистической игры называют определение оптимальных стратегий игроков в игре и значения цены игры.

Лекция 11. Особенность игр с седловым элементом.

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

К сожалению, не всякая платежная матрица имеет седловой элемент.

Рассмотрим пример

			min
	4	2	2
	1	3	1
max	4	3

= 2 при

= 3 при

- седловой элемент отсутствует.

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

Смешанную стратегию первого игрока будем обозначать вектором:

с компонентами:

удовлетворяющими ограничению:

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

Смешанную стратегию второго игрока будем обозначать вектором:

,

Математическое ожидание выигрыша 1-го игрока в ситуации игры ( имеет следующее выражение:

Выигрыш второго игрока в той же ситуации:

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

Тогда как = 2

Переход первого игрока к смешанной стратегии привел к росту его выигрыша сверх гарантированного минимума. Если второй игрок также перейдет к смешанной стратегии, например, , то он может уменьшить свой проигрыш:

Сформулируем правило выбора первым и вторым игроком maxmin-ой и minmax-ой стратегий, вытекающих из принципа гарантированного результата:

1. первый игрок, выбирая , ориентируется на наихудший для себя ответ противника на его выбор :

2. из всех стратегий первый игрок выбирает стратегию из условия :

Величину называют нижним выигрышем первого игрока в классе смешанных стратегий игры, а стратегию – его maxmin-ой смешанной стратегией.

3. второй игрок, выбирая ориентируется на наихудший для него ответ первого игрока на свой выбор

4. из всех стратегий второй игрок выбирает ту , которая минимизирует верхнюю границу его проигрыша:

Величину называют верхним проигрышем второго игрока в классе смешанных стратегий игры, а стратегию – его minmax-ой смешанной стратегией.

Можно доказать, что , а также, что maxmin и minmax стратегии игроков в классах смешанных стратегий более эффективны для них по сравнению с их аналогичными стратегиями в классе чистых стратегий, т.е.