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

• Название: Учебное пособие по курсам Теория игр и исследование операций, Теория принятия решений
• Анкор: Теоретико-игровые методы принятия решений (Еремеев А. П.).doc
• Дата: 27.03.2018
• Размер: 1.18 Mb.
• Имя файла: Теоретико-игровые методы принятия решений (Еремеев А. П.).doc
• Тип: Учебное пособие; #17282
• Категория: Математика
• страница: 5 из 15

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

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

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

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

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

Таблица 3.5

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_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

Bj Ai
A1	4	–5	4	–5	–5
A2	–5	6	6	–5	–5
	4	6	6	–5

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

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

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

Таблица 3.7

Bj Ai
A1	4	–5	–5
A2	–5	6	–5
	4	6

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