Матричные игры

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

,

где a_i,j - выигрыш игрока А ( проигрыш игрока В) в случае, когда игрок А выбирает стратегию А_i, а игрок В - стратегию В_j.

В качестве примера рассмотрим известную "пальцевую" игру "камень-ножницы-бумага".

Суть игры заключается в следующем: играют двое, сделав ставки, например, по одной условной единице. Одновременно каждый из игроков "выкидывает" (изображает) на пальцах один из указанных предметов, не зная выбора другого. При выпадении одноименных предметов считается, что игра закончена вничью. Когда выпали разноименные предметы, один из игроков забирает выигрыш, при этом "камень" побеждает "ножницы", "ножницы" "бумагу", "бумага"  "камень". Все возможные варианты могут быть отображены с помощью платежной матрицы, в которой буквами К, Н, Б отображены соответствующие стратегии (рис.5.1):

		Игрок В
		К		Н	Б
Игрок А	К	0	+1		-1
	Н	-1	0		+1
	Б	+1	-1		0

Рис.5.1. Платежная матрица для "пальцевой" игры

Решение матричной игры в чистых стратегиях

Рассмотрим процесс принятия решений обеими сторонами более детально, предполагая, что игроки действуют рационально. При принятии решения в условиях неопределенности разумно исходить из того, что сложится наименее благоприятная ситуация. Рассмотрим величины и , которые называются соответственно нижней и верхней ценами игры, а стратегии А_i0 и В_j0, на которых достигается максимин и минимакс - чистыми максиминной и минимаксной стратегиями.

Выбор стратегии А_i0 гарантирует игроку А получение выигрыша не меньшего, чем нижняя цена игры, независимо от стратегии, выбранной игроком В. Аналогично и выбор игроком В стратегии В_j0 гарантирует ему проигрыш, не больший , независимо от стратегии, выбранной игроком  А.

Если , то  называется ценой игры, тройка (А_i0,В_j0, )  решением игры в чистых стратегиях, а сами А_i0, В_j0  оптимальными чистыми стратегиями. Стратегии А_i0 и В_j0 являются оптимальными в том смысле, что при их выборе достигается разумный компромисс между игроками А и В, когда гарантированный выигрыш одного равен гарантированному проигрышу другого.

Если = 0, то игра называется справедливой.

Элемент матрицы называется седловой точкой, если , i = 1,...,m ; j = 1,...,n. В седловой точке элемент матрицы является одновременно наименьшим в строке и наибольшим в столбце

Справедлива следующая ключевая для теории игр теорема. Для того чтобы игра имела решение в чистых стратегиях, необходимо и достаточно, чтобы платежная матрица имела седловую точку. При этом тройка (А_i0, В_j0, a _i0 j0) оказывается решением игры.

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

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

Пример.

Парная игра задана матрицей, приведенной на рис.5.2 в интервале ячеек A2:D6. Найти решение игры.

Рис.5.2. Парная игра и ее решение.

Решение.

Все вычисления удобно провести, используя электронные таблицы MS Excel, возможный вариант решения приведен на рис.2 .

Вычислим верхнюю и нижнюю цены игры.

Нижняя цена содержится в ячейке С14. Для ее вычисления использованы значения ячеек Е9:Е11, в которых вычисляются минимальные значения по соответствующей строке платежной матрицы. Далее выбираем наибольшее значение из них max8;6;6 = 8.

Верхняя цена содержится в ячейке С15. Для ее вычисления использованы значения ячеек B12:D12, в которых вычисляется максимальное значение по соответствующему столбцу платежной матрицы. Далее выбираем наименьшее значение из них min8;11;10 =8.

Нижняя и верхняя цены игры равны , из этого следует, что существует решение в чистых стратегиях. Таким образом, цена игры . Чистой максиминной стратегией для игрока А является первая стратегия А₁, чистой минимаксной стратегией для игрока В является первая стратегия В₁. Решением игры является тройка (А_1,В_1,8).