Глава 2. Бескоалиционные игры

§2.1. Антагонистические игры

§2.1.1. Понятие антагонистической игры. Матричная игра.

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

Рассмотрим игру с постоянной суммой, в которой участвуют два игрока. Будем считать, что каждый игрок имеет конечное множество стратегий. Будем также считать, что при любом исходе игры, сумма выигрышей двух участников равна постоянному числу H. Тогда формальное описание игры будет следующим:

1. Множество участников

2. Множество стратегий

3. Множество исходов i – номер стратегии 1-го участника; j – номер стратегии 2-го участника.

4. Платёжная функция.

–выигрыш 1-го участника для исхода ;

–выигрыш 2-го участника для исхода

Предположим, что при некотором исходе выигрыш некоторого (1-го участника) равен:

.

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

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

(1.1)

Номер строки соответствует номеру стратегии 2-го участника, номер столбца соответствует номеру стратегии 1-го участника.Матрица A в называется платёжной матрицей. Представление игры с помощью платежной матрицы называют нормальной записью игры (или нормальным представлением игры).

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

§2.1.2. Доминирование стратегий. Редукция игры. Решение игры в доминирующих стратегиях.

В этом параграфе пойдет речь о попарном сравнении между собой стратегий игрока. Иногда в результате такого сравнения делается вывод о превосходстве (т.е. доминировании) одной стратегии над другой. Рассмотрим пример.

Пример. Дана платёжная матрица A:

Первый игрок выбирает строку,

второй выбирает столбец.

Второй игрок может заметить, что элементы 4-го столбцасоответствующих элементов 2-го столбца. А как было указано выше второй участник стремиться минимизироватьа_ij Значит, при любых действиях соперника 2-я стратегия оказывается лучше или не хуже, чем 4-я. В таких случаях говорят, что 2-я стратегия доминирует над 4-й. Следовательно, 4-ю стратегию 2-й участник может вычеркнуть, аналогично. продолжая рассуждения исравнивая 1 и 3 стратегии второго игрока, платёжная матрица примет следующий вид: случаях говорят, что 2-я стратегия доминирует над 4-й. Следовательно, 4-ю стратегию 2-й участник может вычеркнуть, аналогично. продолжая рассуждения исравнивая 1 и 3 стратегии второго игрока, платёжная матрица примет следующий вид:

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

Дадим общее определение доминирования стратегий.

Говорят, что стратегия l доминирует стратегию k для 1-го участника, если для всех значений j=1,2…,n справедливы неравенства a_lj≥a_kj, и хотя бы для одного значения j неравенство является строгим.

Аналогично:

Говорят, что стратегия l доминирует стратегию k для 2-го участника, если для всех значений i=1,2…,m справедливы неравенства a_il≤a_ik, и хотя бы для одного значения i неравенство является строгим.

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

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

Пример.Кот Базилио и лиса Алиса узнали, где спрятан золотой ключик. Каждый из них может сказать об этом либо Карабасу, либо черепахе Тортилле. Если оба расскажут черепахе, или оба расскажут Карабасу, то оба получат одинаковую награду (для простоты возьмем ее за 0). Если один расскажет черепахе, а другой Карабасу, то Карабас заберет один золотой у того, кто рассказал черепахе, и отдаст золотой тому, кто рассказал Карабасу. Найти рациональные стратегии Алисы и Базилио.

Решение. Составим платежную матрицу:

Базилио
		Карабасу		Черепахе
Алиса	Карабасу		0			1
	Черепахе		-1			0

Мы видим, что у Алисы 1-я стратегия доминирует 2-ю, т.к. 0>-1, 1>0. Поэтому Алиса выберет 1-ю стратегию. Базилио, как рациональный игрок, поймет это из анализа платежной матрицы, и тоже выберет 1-ю стратегию, т.к. в первой строке 1<0. В результате оба расскажут о ключике Карабасу.