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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Таблица 3.3

B j Ai
A1	4	–5
A2	–5	6

Для случая, когда игроку B известно о выборе игрока A (т.е. игра с полной информацией), получаем игру G(24), матричная форма которой представлена табл. 3.3.

Таблица 3.4

B j Ai
A1	4	–5	4	–5
A2	–5	6	6	–5

У игрока B добавились еще две стратегии: B₃ – отвечать стратегией с тем же номером, что выбрал игрок A (т.е. B₁ на A₁ и B₂ на A₂) и B₄ – отвечать стратегией с номером, отличным от выбора игрока A (т.е. B₂ на A₁ и B₁ на A₂).

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

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

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

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

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

Таблица 3.5

B j 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

B j 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

B j Ai
A1	4	–5	–5
A2	–5	6	–5
	4	6

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

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

3.3.1.Смешанные стратегии

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

,

где p_i и q_j – вероятности выбора стратегий A_i и B_j игроками A и B соответственно. Решением игры в данном случае является пара оптимальных смешанных стратегий (S_A^*, S_B^*), максимизирующих математическое ожидание цены игры (средний выигрыш).

Теорема 3.2 [6]. Любая антагонистическая игра имеет хотя бы одно оптимальное решение, т.е., пару в общем случае смешанных стратегий (S_A^*, S_B^*), дающих игроку А устойчивый выигрыш, равный цене игры V, α ≤ V ≤ β.

Чистую стратегию можно рассматривать как частный случай смешанной стратегии, когда одна вероятность имеет единичное значение, а все остальные – нулевое.

Рассмотрим матричную игру G(mn), не имеющую седловой точки, для которой необходимо найти решение – пару оптимальных смешанных стратегий S_A = (p₁, p₂, …, p_m) и S_B = (q₁, q₂, …, q_n) и соответствующую цену игры V.

Предварительно следует попытаться упростить матрицу игры. Для этого вводятся отношения предпочтения (доминирования) и безразличия (дублирования) на множестве стратегий.

Определение 3.3:

• стратегия A_i предпочтительнее стратегии A_k (доминирует A_k) (обозначается ), если все выигрыши, указанные в i-й строке матрицы игры, не меньше соответствующих выигрышей k-й строки, или формально ;

• стратегии A_i и A_k находятся в отношении безразличия (дублирования) (обозначается A_iA_k), если все выигрыши, указанные в i-й строке матрицы игры, совпадают с соответствующими выигрышами k-й строки, или формально ;

• стратегия B_j предпочтительнее стратегии B_r (доминирует B_r) (обозначается ), если все выигрыши, указанные в j-м столбце матрицы игры, не меньше соответствующих выигрышей r-го столбца, или формально ;

• отношение безразличия для стратегий игрока B вводится аналогично игроку A, т.е. .

Можно доказать следующую лемму [5].

Лемма 3.2. Для игры G(mn) число активных стратегий игроков равно min{m,n}. Другими словами, если, например, m>n, то в оптимальной стратегии S_A = (p₁, p₂, …, p_m) игрока A будет не более n отличных от нуля вероятностей p_i.

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

Рассмотрим данный этап на примере матричной игры G(55), представленной табл. 3.7.

Таблица 3.8

Т ак как справедливы соотношения , , , , , то удалим доминируемые и дублируемые стратегии A₄, A₅, B₂, B₄, B₅.

Характеристики

Список файлов книги