Матричные антагонистические игры с нулевой суммой в чистых стратегиях (стр. 5 из 16)

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

На примере бриджа и шахмат можно показать другой важный элемент игры. Именно, в шахматной игре каждый игрок знает любой ход, который был сделан до этого момента, в то время как в бридже это знание игрока обычно неполно. Таким образом, в некоторых играх игрок не в состоянии определить, какой из нескольких возможных ходов был фактически сделан, будь то ход одного из его противников или случайный ход. На практике это означает, что, когда игрок делает свой ход, он не знает точной позиции игры и должен делать ход с учетом того, что имеется несколько возможных позиций.

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

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

2 возможная недостаточность информации

3 функция выигрыша

Запишем теперь основные этапы поиска решения игры:

1 проверка наличия (или отсутствия) равновесия в чистых стратегиях (к этому вопросу вернёмся чуть позже). При наличии равновесной ситуации указываются соответствующие оптимальные стратегии игроков и цена игры.

2 поиск доминирующих стратегий (в случае успеха этого поиска – отбрасывание доминирующих строк и столбцов в исходной матрице игры).

3 замена игры на её смешанное расширение и отыскание оптимальных смешанных стратегий и цены игры.

Игрок 2 стратегия 1	Игрок 2 стратегия 2
Игрок 1 стратегия 1	4, 3	–1, –1
Игрок 1 стратегия 2	0, 0	3, 4
Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии.

Отметим, что нормальная форма антагонистической игры сводится к некоторой матрице А с числом строк равным числу стратегий игрока 1 и с числом столбцов, равным числу стратегий игрока 2. Выигрыш – если игрок 1 выбирает i-ю стратегию, а игрок 2 j-ю стратегию – представляет собой элемент

в i-ой строке и в j-ом столбце данной матрицы.

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

, можно употребить следующее обозначение Исходя из этого функцию на множестве всех возможных значений переменных можно выразить либо в форме соотношения, либо в виде n-мерной матрицы n-векторов. Такая n-мерная таблица называется нормальной формой игры Г. В нормальной (стратегической) форме игра описывается платёжной матрицей. Каждая сторона матрицы – это игрок, строки определяют стратегии первого игрока, а столбцы – второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки. На примере, если игрок 1 выбирает первую стратегию, а второй игрок – вторую, то на пересечении получится (1,-1). Это значит, что в результате хода игроки потеряли по одному очку.

Пример 1: игра «Орлянка».

X \ Y	Орел	Решка
Орел	-1, 1	1, -1
Решка	1, -1	-1, 1

Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает – платит первому одну денежную единицу, если угадывает – первый платит ему одну денежную единицу. В данной игре каждый игрок имеет две стратегии: «орёл» и «решка». Множество ситуаций в игре состоит из 4 элементов. В строках таблицы указаны стратегии первого игрока Х, в столбцах – стратегии второго игрока Y. Для каждой из ситуаций указаны выигрыши первого и второго игроков.

Рассмотрим основную теорему матричных игр.

Основная теорема теории матричных игр (по Дж. фон Нейману).

Для матричной игры с любой матрицей Авеличины

и равны между собой, т.е.

Более того, существует хотя бы одна ситуация в смешанных стратегиях

, для которой выполняется соотношение

Иными словами, любая матричная игра имеет решение в смешанных стратегиях. Поиск этого решения опирается на установленные факты.

Приведём доказательство данной теоремы (автор: Дж. Б. Данциг, 1951г.)

Теорема.Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число

и такие стратегии

и

игроков 1 и 2 соответственно, выполняются неравенства:

.(*)

Комментарий. Формула (*) означает, что: если игрок 1 отклоняется от своей оптимальной стратегии, то его выигрыш не увеличивается по сравнению с ценой игры; если от своей оптимальной стратегии отклоняется игрок 2, то по сравнению с ценой игры его проигрыш не уменьшается.

Доказательство.

Пусть матрица игры равна

. Всегда можно считать, что все коэффициенты . Если это не так, то предположим, что наименьший из всех отрицательных коэффициентов есть . Тогда увеличим все элементы платёжной матрицы на произвольное положительной число . Функция выигрыша при этом окажется равной

.

Из этого следует, что от увеличения всех элементов матрицы

на величину цена игры увеличивается на эту величину, причём оптимальные смешанные стратегии не изменяются.

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

.

1.3 Классификация игр

Различные виды игр можно классифицировать, основываясь на том или ином принципе: по числу игроков, по числу стратегий, по свойствам функций выигрыша, по возможности предварительных переговоров и взаимодействия между игроками в ходе игры. В зависимости от числа игроков различают игры с двумя, тремя и более участниками. Согласно другому принципу классификации (по количеству стратегий) различают конечные и бесконечные игры. В конечных играх игроки располагают конечным числом возможных стратегий (например, в игре в орлянку игроки имеют по два возможных хода - они могут выбрать "орел" или "решку"). Сами стратегии в конечных играх нередко называются чистыми стратегиями (смысл этого названия будет ясен далее).

Соответственно, в бесконечных играх игроки имеют бесконечное число возможных стратегий. Так в ситуации «Продавец-Покупатель» каждый из игроков может назвать любую устраивающую его цену и количество продаваемого (покупаемого) товара. Третий способ классификации игр-по свойствам функции выигрыша (платежных функций). Важным случаем в теории игр является ситуация, когда выигрыш одного из игроков равен проигрышу другого, т.е. налицо прямой конфликт между игроками. Подобные игры называются играми с нулевой суммой, или антагонистическими играми. Игры в орлянку или в шахматы - типичные примеры антагонистических игр. Прямой противоположностью играм такого типа являются игры с постоянной разностью, в которых игроки и выигрывают, и проигрывают одновременно, так что им выгодно действовать сообща. Между этими крайними случаями имеется множество игр с ненулевой суммой, где имеются и конфликты, и согласованные действия игроков. Можно также выделить 2 способа задания игры.

1 так называемая позиционная форма. При этом определяются:

· порядок ходов

· альтернативы (возможные ходы), доступные каждому из игроков на момент наступления его хода

· информация, которой владеет каждый из игроков на момент очередного хода

· выигрыши (для каждого игрока) как функции от выбранных ходов

· вероятностные распределения на множестве возможных состояний внешней среды