Наличие седловой точки

Определение 3.1.

Нижней оценкой цены игры называется величина ; верхней оценкой цены игры называется величина .

Лемма 3.1. Справедливо соотношение a ≤ b.

Для доказательства леммы представим игру G(m´n)в матричной формев виде табл. 3.4.

Таблица 3.4

Bj Ai	B1	…	Bj	…	Bk	…	Bn
A1	a11	…	a1j	…	a1k	…	a1n
…	…	…	…	…	…	…	…
Ai	ai1	…	aij	…	aik	…	ain
…	…	…	…	…	…	…	…
Al	a11	…	alj	…	alk	…	ain
…	…	…		…		…	…
Am	am1	…	amj	…	amk	…	amn

Пустьa= a_jk, b= a_lj .Из определения верхней и нижней границ следует, что элемент a_jk является минимальным в i-й строке, т.е. a= a_jk ≤ a_jj, а элемент a_lj является максимальным в j-м столбце, т.е. a_jj ≤ a_lj =b. Лемма доказана.

Определение 3.2.Если a=b= V, то игра имеет седловую точку, стратегии A_i, B_j, при которых достигается выигрыш V, называются оптимальными чистыми стратегиями, а пара стратегий (A_i, B_j) называется решением игрыG(m´n).

Решение игры обладает свойством устойчивости (равновесия), т.е. если один из игроков придерживается своей оптимальной стратегии, то другому игроку не выгодно отходить от своей, так как его положение при этом может только ухудшиться. Из леммы 3.1 непосредственно следует, что признаком наличия седловой точки является нахождение в матрице игры такого элемента a_ij, который является одновременно минимальным в i-й строке и максимальным в j-м столбце. Если такой элемент не единственный, то игра имеет не единственное решение, но все решения равнозначны, т.е. дают выигрыш, равный цене игры V.

Теорема 3.1[6]. Антагонистическая игра с полной информацией имеет седловую точку.

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

Рассмотрим в качестве примера матричную игру G(2´4)с полной информацией, представленную табл. 3.3. Дополним данную таблицу новыми строкой и столбцом, получив табл. 3.5.

Таблица 3.5

Bj Ai
A1		–5		–5	–5
A2	–5			–5	–5
				–5

Из таблицы видно, что , .

Имеем две седловые точки a₁₄и a₂₄,соответствующие решениям(A₁, B₄)и(A₂, B₄)с ценой игры V = –5.

Вернемся теперь к матричной игре G(2´2)с неполной информацией, представленной в табл. 3.2. Аналогично предыдущему примеру дополним табл. 3.2 до табл. 3.6.

Таблица 3.6

Bj Ai
A1		–5	–5
A2	–5		–5

Для данной таблицы , , т.е. a< b.Седловая точка, а, следовательно, и решение в чистых стратегиях, отсутствуют.

3.3. Методы решения матричных игр
при отсутствии седловой точки