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

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

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

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

Bj Ai	B 1	B 2	…	Bn	αi
A 1	a 11	a 12	…	a 1 n	α 1
A 2	a 21	a 22	…	a 2 n	α 2
…	…	…	…	…	…
Am	am 1	am 2	…	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)

 

 

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

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

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

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

Теорема. Ситуация (A_i0, B_jo) будет удовлетворительна для игрока В Тогда и только тогда, когда его проигрыш совпадет с показателем эффективности стратегии A_io игрока A: , то есть будет минимален в i-ой строке матрицы игры

Д-во: Если ситауция (A_i0, B_jo) удовлетворительна для игрока В, то из нер-ва и равенства при i=i₀ получим и рав-во доказано

Если же это справедливо то по при i=i₀ будем иметь то есть доказано неравенство

Ситуация (A_i0, B_j0) будет удовлетворительной для игрока B тогда, и только тогда, когда его проигрыш a_i0j0 совпадет с показателем эффективности α_i0 стратегии A_i0 игрока A: a_i0j0= α_i0, т.е. будет минимальным в i₀-й строке матрицы игры.

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

1) В каждой строке A_i0 матрицы игры находим наименьший элемент α_i0.

2) Ищем столбец B_j0, в котором находится этот элемент.

3) (A_i0, B_j0) – удовлетворительная ситуация.

Число удовлетворительных для игрока В ситуаций не меньше m и не больше mn.