Глава 1. Теория антагонистических игр.

1.1. Основные понятия.

1.1.1. Минимаксные стратегии. Седловая точка.

Рассматриваются игры двух лиц с нулевой суммой. Игрок А располагает p чистыми стратегиями а игрок В соответственно q чистыми стратегиями Первый игрок может выбрать любую стратегию второй игрок может выбрать любую стратегию В этом случае игра считается сыгранной, и ее результат выражается некоторым числом («платежом»), который обозначим через и будем называть его «выигрышем» игрока А. Игра с «нулевой суммой» означает, что при этом «выигрыш» игрока В составит (числа могут быть и отрицательными). Матрица порядка называется платежной матрицей или матрицей игры.

Таблица 1.1

		Стратегии игрока В
			…		…
			…		…
			…		…
			…		…
			…		…
			…		…
			…		…

Числа и указывают минимально гарантированный выигрыш для игрока А, применяющего стратегию , и максимально «гарантированный» проигрыш игроком В при использовании им стратегии .

Величина

(1.1)

называется нижней ценой игры, максимальным выигрышем А, или коротко максимином, а соответствующая ему стратегия (строка) – максиминной. Аналогично

(1.2)

называется верхней ценой игры, минимаксным проигрышем В, или минимаксом, а соответствующая стратегия (столбец) игрока В – минимаксной. Всегда . Принцип, согласно которому игроки выбирают эти стратегии, называется принципом максимина (для А) или минимакса (для В).

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

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

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

Пример 1.1

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

Решение.

Согласно условию, каждому игроку доступны четыре стратегии:

• не зажимать в кулаке монету, считать, что сумма равна нулю

• не зажимать монету, считать, что сумма равна 1

• зажимать монету, считать, что сумма равна 1

• зажимать монету, считать сумму равной 2

Поэтому платежная матрица имеет следующий вид:

Таблица 1.2

		0	1	-1	0	-1
		-1	0	0	1	-1
		1	0	0	-1	-1
		0	-1	1	0	-1
		1	1	1	1	1	-1

Нижняя цена игры:

верхняя цена игры:

Следовательно, для обоих игроков максиминными являются все их стратегии, при этом каждому из них обеспечен «выигрыш» не менее – 1 (т.е. проигрыш не более 1). Игра не имеет седловой точки

Пример 1.2

Пусть платежная матрица игры имеет вид таблицы 1.3

Таблица 1.3

		4	5	3	3
		6	7	4	4
		5	2	3	2
		6	7	4	4	4

Определить верхнюю и нижнюю цену игры и минимаксные стратегии.

Решение.

Нижняя цена игры:

верхняя цена игры:

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

Для игрока В соответственно минимаксной стратегией является , которая гарантирует ему проигрыш не более 4. Так как , то игра имеет седловую точку и цена игры равна 4. Оптимальным решением игры будет выбор стратегии игроком А и игроком В.

Упражнение 1.1

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

1)	2)
3)	4)
5)	6)

Упражнение 1.2

Жаклин и Робер получили в наследство автомобиль стоимостью 800 франков и согласились решить вопрос о том, кому достанется машина, с помощью объявленных ставок в запечатанных конвертах. Тот из них, кто предложит более высокую сумму, получает автомобиль и уплачивает эту сумму другому наследнику. Если же назначенные суммы окажутся одинаковыми (что вполне возможно, так как они договорились, чтобы ставки отличались друг от друга не менее чем на сто франков), то вопрос о владельце определяется жеребьевкой с помощью монеты. При этом они ничего не платят друг другу. У Жаклин на руках имеется 500 франков, в то время как у Робера есть 800 франков. Как следует им назначать свои ставки?

В случае, когда вопрос о владельце решается с помощью монеты, их шансы на выигрыш одинаковы. Так как машина стоит 800 франков, то эти шансы можно оценить в 400 франков.