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

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

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

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

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

Таблица 3.5

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

Определение 3.2. Если =  = 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.6

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

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

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

Таблица 3.7

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