9. Нижняя и верхняя цены игры в чистых стратегиях. Доказательство теоремы о сравнении нижней и верхней цен игры в чистых стратегиях. Цена игры в чистых стратегиях.

Если игрок В придерживается своей минимаксной стратегии а игрок А - любой своей стратегии A_k, k = 1, ..., т, то для проигрыша игрока В в ситуации (A_k, ), с использованием равенств и , получим неравенство

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

Для нахождения нижней и верхней цен игры удобно матрицу игры увеличить в размерах, приписав (n+1)-й столбец показателей эффективности α_i: стратегий А_i игрока А и (т+1)-ю строку показателей неэффективности β_j стратегий B_j игрока В. В результате получим следующую матрицу:

Bj Ai	B1	B2	…	Bn	αi
A1	a11	a12	…	a1n	α1
A2	a21	a22	…	a2n	α2
…	…	…	…	…	…
Am	am1	am2	…	amn	αm

Ниже представлена теорема, которая устанавливает соотношение между показателями эффективности α_i стратегий A_i игрока А, показателями неэффективности β_j стратегий B_j игрока В и выигрышами а_ij и, как следствие этого соотношения, - неравенство между нижней и верхней ценами игры в чистых стратегиях.

Теорема: Для элементов матрицы имеют место неравенства

α_i ≤ a_ij ≤ β_j, i = 1, ..., m, j = 1, ...,n,

и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях:

α ≤ β.

Доказательство. По определению показателей эффективности α_i стратегий А_i игрока А и определению показателей неэффективности β_j стратегий B_j игрока В имеем

следовательно, неравенства α_i ≤ a_ij ≤ β_j, i = 1, ..., m, j = 1, ...,n, доказаны.

Так как доказанное неравенство α_i ≤ β_j справедливо для любых i = 1, ..., т, j =1, ..., п, то оно будет справедливым в частности для номеров i = i₀ и j = j₀ соответственно максиминной и минимаксной стратегий и .

Тогда в силу равенств и получим требуемое неравенство α ≤ β.

Стратегии и игроков А и В, создающие равновесную ситуацию , называются оптимальными. Обозначим через и - множества чистых оптимальных стратегий соответственно игроков А и В.

Если нижняя цена игры α равна верхней цене β, то их общее значение γ = α = β называется ценой игры в чистых стратегиях.

Для того чтобы существовала цена игры в чистых стратегиях, т. е. для того чтобы нижняя цена игры α равнялась верхней цене игры β, необходимо и достаточно существование у матрицы этой игры седловой точки.

10. Понятие игровой ситуации. Игровая ситуация, удовлетворительная для игрока , и доказательство ее критерия. Алгоритм поиска игровых ситуаций, удовлетворительных для игрока .

Ситуация – набор стратегий игроков А и В.

Устойчивая ситуация или ситуация равновесия – ситуация, удовлетворительна для обоих игроков, т.е. когда игроки А и В придерживаются своих максиминной и минимаксной стратегий соответственно, то ни один из них не может увеличить свой выигрыш отступая от своей стратегии: a_ij0≤a_i0j0≤a_i0j , i=1…m, j=1,…,n, или α_i0=a_i0j0=β_jo

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

Теорема Ситуация (Ai0, Bjo) будет удовлетворительна для игрока А Тогда и только тогда, когда его выигрыш совпадет с показателем неэффективности стратегии Bjo игрока В: , то есть будет максимальной в j-ом столбце матрицы игры

Д-во: Пусть ситауция (Ai0, Bjo) удовлетворительна для игрока А. Тогда по определению справедливо нер-во .Из этого неравенства и по определению (1) показателя неэффективности стратегии Bj0 следует, что , то есть нер-во доказано. Тогда применяя (1) при j=j0 получим , то есть доказано

Алгоритм нахождения удовлетворительной ситуации для игрока А:

1. В каждом столбце B_j матрицы А найти max элемент β_j

2. Найти строку α_i, в которой находится этот элемент.

3. Тогда {A_i; B_j}является удовлетворительной для игрока А.

Причем количество удовлетворительных ситуаций для А больше числа столбцов, но меньше общего числа элементов (n ≤ N^A_удовл≤ mn)