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

Пусть первый игрок имеет m стратегий, второй n стратегий. Обозначим через , i - стратегию игрока 1, через , j - стратегию игрока 2. Паре стратегий поставим в соответствие число - выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою стратегию i, а второй – j.

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

Каждая стратегия , называется чистой стратегией.

В каждой партии делается ход: игрок 1 выбирает стратегию i, игрок 2– стратегию j. После чего игрок 1 получает выигрыш (за счёт игрока 2). Если , значит, игрок 1 платит игроку 2 сумму и игра заканчивается.

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

Возможные действия игроков называются чистыми стратегиями.

Что думает игрок 1?

		Стратегии игрока 2	Минимальный элемент в строке
B1	B2	B3
Стратегии игрока 1	A1
A2	-3		-5	-5
A3		-5	-6	-6

 

Игрок 1 использует логику, которая гарантирует ему максимальный выигрыш вне зависимости от поведения игрока 2.
Свой выбор, игрок 1 остановит на стратегии A1, которая обеспечит ему выигрыш 4, т.е. доход не менее 4 ден.ед.

Значение, равное 4, называется нижней ценой игры.

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

Затем отыскивается такая стратегия , которая гарантирует ему выигрыш

.

Стратегия называется максиминной (осторожной) стратегией игрока 1

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

 

Что думает игрок 2?

		Стратегии игрока 2	Минимальный элемент в строке
B1	B2	B3
Стратегии игрока 1	A1
A2	-3		-5	-5
A3		-5	-6	-6
Максимальный элемент в столбце

Игрок 2 использует логику, которая гарантирует ему минимальный проигрыш вне зависимости от поведения игрока 1. Свой выбор, игрок 2 остановит на стратегии В1, которая обеспечит ему проигрыш 4, т.е. потерю не более 4 ден.ед.

Значение равное 4, называется верхней ценой игры.

Стратегия игрока 2 максимально уменьшить выигрыш игрока 1 (за счёт своих стратегий). Поэтому для игрока 2 необходимо определить значение:

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

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

Если = = v, то говорят, что игра имеет решение в чистых стратегиях, а стратегии , при которых достигается цена игры = v – оптимальными чистыми стратегиями. Пара чистых стратегий называется седловой точкой. Седловой элемент является минимальным в i- строке и максимальным в j - столбце платёжной матрицы. Значение v называется чистой ценой игры.

Пример 1. Найти решение игры, заданной платёжной матрицей A в чистых стратегиях

Решение:

Найдём минимальные элементы в каждой строке и максимальные элементы в каждом столбце. Затем найдём максимальный элемент среди минимальных и минимальный среди максимальных. Занесём всё в следующую таблицу

	B1	B2	B3	min j
A1
A2
A3
max i

В нашей задаче = = v. Пара образует седловую точку. Таким образом, оптимальной стратегией для игрока 1 будет стратегия A ₁, а для игрока 2 – стратегия В 3. Цена игры v= 4.

Пример 2. Показать, что данная платёжная матрица не имеет решения в чистых стратегиях

Решение: Также как и в предыдущей задаче составим таблицу

	B1	B2	min j
A1
A2
max i

 

Решения в чистых стратегиях не существует, так как нижняя цена игры достигается в стратегии A ₂ и её значение равно 30, в то время как верхняя цена игры достигается в стратегии B ₂ и её значение равно 40.