Матричные антагонистические игры с нулевой суммой в чистых стратегиях
1.4 Матричные игры
В этом параграфе будет рассказано о принципе максимина, рациональном представлении матрицы игры, о решении игры при помощи фиктивного разыгрывания.
-
н/ч ч н/ч 1 -1 ч -1 1
Начнём
непосредственно
с матричных
игр. Тройка
(где x и y
– множества,
H – функция
от двух переменных
)
называется
антагонистической
игрой. Процесс
разыгрывания
конечной
антагонистической
игры (игра называется
конечной, если
тройка
конечна) состоит
в том, что игроки
1 и 2 независимо
друг от друга
выбирают
соответственно
некоторые
чистые стратегии
x и y, в
результате
чего складывается
ситуация (x,y).
Мы
знаем, что
антагонистическую
игру двух участников
с нулевой суммой
(напомним, что
нулевая сумма
– это когда
выигрыш одного
игрока равен
проигрышу
другого) удобно
задавать с
помощью, так
называемой
платёжной
матрицы. Каждый
элемент такой
матрицы
содержит числовое
значение выигрыша
игрока 1 (или
проигрыша
игрока 2) в ситуации,
когда первый
игрок применяет
стратегию i,
а второй – стратегию
j. Классическим
примером
антагонистической
игры является
игра с двумя
участниками,
которые независимо
друг от друга
загадывают
числа. Предполагается,
что если сумма
оказывается
чётной, то выигрыш
равный 1, достаётся
первому игроку,
а если нечётной,
то второму.
Если предположить,
что загадывание
нечётного числа
– стратегия
первого игрока,
а загадывание
чётного числа
– стратегия
второго игрока,
то платёжная
матрица выглядит
следующим
образом:
Строки
матрицы соответствуют
стратегиям
игрока 1, столбцы
– стратегиям
игрока 2, а её
элементы –
результатам
(т.е. выигрышам)
первого. Если
взять элементы
матрицы с обратным
знаком, то это
будут выигрыши
второго игрока.
Здесь надо
отметить, что
вопрос о выборе
стратегии
является основным
в теории игр.
Для примера
проанализируем
произвольную
игру
.
При выборе
игроком 1 стратегии
i, его выигрыш
в независимости
от игрока 2 составит
.
Стратегия I
произвольно,
поэтому главная
цель игрока
1 максимизировать
величину полученного
выигрыша, т.е.
получить
.
Такой принцип
получил название
принципа
максимина.
Напомним, что
максимин – это
выигрыш максимальный
из минимальных.
Надо также
отметить, что
принцип максимина
обеспечивает
игрокам гарантированный
«выигрыш» при
любых стратегиях
противников.
Теорема о принципе максимина.
Для
с
(где
- множества
чистых стратегий
игроков, (х, у)
– ситуация игры
- функции полезности
игроков, заданные
на множестве
ситуаций
игры
аналитически
)
общего вида
.
Доказательство.
Для

Для
игры, заданной
матрицей выигрышей
можно
записать следующее
равенство
.
Скажем ещё несколько слов о матричных играх. Для матричных игр доказано, что любая из них имеет решение, и оно может быть легко найдено путем сведения игры к задаче линейного программирования.
Матричная игра игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.
Первый игрок
имеет m
страте6гий i
= 1,2,...m, второй
имеет n
стратегий
j=1,2,...n.
Каждой паре
стратегий (i,
j) поставлено
в соответствии
число a
,
выражающее
выигрыш игрока
1 за счет игрока
2, если первый
игрок примет
свою i-ю
стратегию, а
2-ю j-ю стратегию.
Каждый из
игроков делает
один ход: игрок
1 выбирает свою
i-ю стратегию
(i=
),
2- свою j-ю
стратегию (j=
)
после чего
игрок 1 получает
выигрыш a
за счет игрока
2 ( если a
<0,
то это значит,
что игрок 1 платит
второму сумму
a![]()
).
На этом игра
заканчивается.
Каждая стратегия
игрока i=
;
j=
часто называется
чистой стратегией.
Если рассмотреть матрицу

то проведение
каждой партии
матричной игры
с матрицей А
сводится к
выбору игроком
1 i- строки,
а игроком 2 j-го
столбца и получения
игроком 1 (за
счет игрока
2) выигрыша a
.
Главным в
исследовании
игр является
понятие оптимальных
стратегий
игроков. В это
понятие вкладывается
следующий
смысл: обеспечивается
наибольший
гарантированный
выигрыш при
всевозможных
стратегиях
другого игрока.
Исходя из этих
позиций, игрок
1 исследует
матрицу выигрышей
А следующим
образом: для
каждого значения
i (i=
)
определяется
минимальное
значение выигрыша
в зависимости
от применяемых
стратегий
игрока 2
min a
(i=
)
j
т.е определяется
минимальный
выигрыш для
игрока 1 при
условии, что
он примет свою
i-ю чистую
стратегию,
затем из этих
минимальных
выигрышей
отыскивается
такая стратегия
i=i
,
при которой
этот минимальный
выигрыш будет
максимальным,
т.е. находится
max min
a
= a
![]()
=
(1)
Определение:
Число
,
определенное
по формуле (1)
называется
чистой нижней
ценой игры
показывает,
какой минимальный
выигрыш может
гарантировать
себе игрок 1,
применяя свои
чистые стратегии
при всевозможных
действиях
игрока 2.
Игрок 2 при оптимальном своем поведении должен стремиться по возможности за счет своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается
max a![]()
i
т.е. определяется
max выигрыш
игрока 1, при
условии, что
игрок 2 применит
свою j-ю
чистую стратегию,
затем игрок
2 отыскивает
свою j=j
стратегию, при
которой игрок
1 получит min
выигрыш, т.е.
находит
min max a
=a![]()
=
(2)
j i
Определение.
Число
,
определяемое
по формуле (2),
называется
чистой верхней
ценой игры
и показывает,
какой максимальный
выигрыш за счет
своих стратегий
может себе
гарантировать
игрок 1.
Другими
словами, применяя
свои чистые
стратегии,
игрок 1 может
обеспечить
себе выигрыш
не меньше
,
а игрок 2 за счет
применения
своих чистых
стратегий может
не допустить
выигрыш игрока
1 больше, чем
.
Переходя к рациональному представлению матрицы игры, отметим, что стратегии двух игроков сводятся в таблицу, а непосредственно само представление упрощает поиск решения матричных игр.
ПРИМЕР 3: Провести SP-разбиение матрицы игры (Н)
-
X1 2 3 4 5 X2 1 4 0 5 X3 1 0 6 7 X4 1 2 3 4 Y1 Y2 Y3 Y4
![]()
|
|
|
|
|
|
|
|
|
2 |
3 | 4 | 5 |
2 |
|
|
1 | 4 | 0 | 5 | 0 |
|
|
1 | 0 | 6 | 7 | 0 |
|
|
1 | 2 | 3 | 4 | 1 |
|
|
2 |
4 | 6 | 7 |
|
Решение: вычисляем верхнюю и нижнюю цену игры
Исходная
игра имеет SP
(x1,y1) в
чистых стратегиях.
Существование
SP в чистых
стратегиях
матричной игры
с полной информацией
позволяет
провести SP-разбиение
(Н) исходной
игры:
.
Формирование SP- разбиения матричной игры с SP по существу и является рациональным представлением исходной матрицы (Н) игры. Значит, понятие рациональности представления матрицы игры преследует цель сформулировать методы рационального преобразования платёжной матрицы с целью вычисления цены игры v или упрощения построения подыгры-решения.
Далее
рассмотрим
такое понятие,
как решение,
при помощи
фиктивного
разыгрывания.
Есть 2 игрока,
которые без
теории игр,
хотят сделать
игру несколько
раз, причём
каждый из них
склонен к статистике
и оценивает
стратегию
своего противника.
При каждом
разыгрывании
противоборствующие
стороны стремятся
максимизировать
свой ожидаемый
выигрыш против
наблюдаемого
вероятностного
распределения
противника:
если игрок 2
использует
j-ю стратегию
раз, то игрок
1 выберет i-ю
стратегию,
чтобы максимизировать
.
Аналогично,
если игрок 1
использует
i-ю стратегию
раз, то игрок
2 выберет j-ю
стратегию,
чтобы минимизировать
.
Условно эмпирические
распределения
сходятся к
оптимальным
стратегиям.
Точнее, пусть
- число использований
первым игроком
i-ой стратегии
в течение первых
N розыгрышей.
Пусть
,
то тогда
является смешанной
стратегией.
Здесь справедливо
утверждение
о том, что предел
любой сходящейся
подпоследовательности
является оптимальной
стратегией,
т.е. если
и
полученные
стратегии
игроков 1 и 2, то
выполняется
равенство
.
Такой метод
полезен в случае
игры с большим
числом стратегий.
Опишем
некоторые
свойства решений
матричных игр.
Пусть G(X,Y,A)
– игра двух лиц
с нулевой суммой,
в которой игрок
1 выбирает стратегию
,
а игрок 2 -
,
после чего
игрок 1 получает
выигрыш A=A(x,y)
за счёт игрока
2.
Свойство 1: Если чистая стратегия одного из игроков содержится в спектре (спектр – множество чистых стратегий, вероятность которых положительна) некоторой его оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной стратегией и любой оптимальной стратегией другого игрока, равен значению конечной антагонистической игры.
Свойство 2: Ни одна доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.
Свойство
3: Если
– конечная
антагонистическая
игра, а
,
подыгра игры
G причём
- чистая стратегия
игрока 1 в игре
G, доминируемая
над некоторой
стратегией
,
спектр которой
не содержит
.
Тогда всякое
решение
игры
является решением
игры G.
Свойство
4: Тройка
является
решением игры
<=>, когда
является
решением игры
,
где а – любое
вещественное
число, к>0
ГЛАВА 2. Игры с нулевой суммой в чистых стратегиях
2.1 Вычисление оптимальных стратегий на примере решения задач
Используя теорему о минимаксе, можно утверждать, что каждая антагонистическая игра имеет оптимальные стратегии.
Теорема:
пусть А – матричная
игра и строки
данной матрицы
являются
доминирующими.
Тогда игрок
1 имеет такую
оптимальную
стратегию х,
что
;
кроме того,
любая оптимальная
стратегия для
игры, получающаяся
в результате
удаления доминирующих
строк, будет
также оптимальной
для первоначальной
игры.
Пример 1. Игра доминирования
Рассмотрим
игру с матрицей
.
Здесь второй
столбец доминирует
4 и игрок 2 соответственно
не будет использовать
4 стратегию.
Поэтому можно
рассмотреть
матрицу следующего
вида
.
В этой матрице
третья строка
доминирует
первую. При
удалении получается
матрица
.
А в этой матрице
третий столбец
доминируется
вторым. Следовательно,
исходная матрица
сводится к
следующей
матрице
.
Пример 2. Игра на уклонение.
Предполагается,
что игроки
выбирают целые
числа i
и j между
1 и n, а игрок
1 выигрывает
величину
,
т.е. расстояние
между i
и j. Пусть
первый игрок
придерживается
стратегии
,
тогда
для всех
((
- значение игры).
Пусть
нечётно, тогда
игрок 2 имеет
чистую стратегию
для всех

Предположим, что
чётно, тогда
игрок 2 имеет
такую стратегию
где
,
,
,
,
,
для всех
.
Теперь используя
теорему можно
убедиться, что
значение игры
.
Игрок 1 имеет
оптимальную
стратегию
,
а оптимальная
стратегия
игрока 2 равна
,
если
и
если
Приведём
теорему, по
которой решалась
эта игра. Теорема:
для того, чтобы
ситуация
была
равновесной
в игре
,
а число
- значение игры
,
необходимо
и достаточно
выполнение
следующего
неравенства.
Для всех
и
:
).
Ситуация
называется
ситуацией
равновесия
в чистых стратегиях,
если для любых
выполнено
двойное неравенство
(*).
Если каждый
из игроков
стремится
достичь ситуации
равновесия,
то принцип,
которому они
следуют, называют
принципом
равновесия.
Для игры, заданной
матрицей
равенство
(т.е. верхнее
значение игры
равно нижнему
значению)
записывается
в виде
,
а неравенство
(*) – в виде
,
где
чистые максиминная
и минимаксная
стратегии
соответственно
игроков I
и I I.
Пример 3. Игра «Дуэль».
Два дуэлянта
(игроки А и В)
начинают сходиться
в момент времени
t=0. Встреча
произойдёт
в момент времени
t=1. У каждого
есть возможность
выстрелить
в любой момент
времени. Если
одному из них
удастся выстрелить
раньше соперника,
то он становится
победителем.
Если же оба
выстрелят
одновременно,
то дуэль закончится
вничью. Если
игрок А произведёт
выстрел в момент
времени x
(
)
то его выстрел
будет успешным
с вероятностью
р(x). Подобным
образом будет
вероятным
выстрел игрока
В в момент
времени y
(
)
c вероятностью
q(y).
При условии
игрок
А выиграет
с вероятностью
р(x), а
проиграет с
вероятностью
(1- р(x)) q(y).
Тем самым его
средний выигрыш
при