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.

12. Ситуация равновесия. Седловая точка игры. Седловая точка матрицы выигрышей.

Ситуация (Аi0, Bj0) – равновесная или устойчивая, или седловая точка игры, если она удовлетворительна для каждого из игроков А и В.

Выигрыш A_i0j0, (A_i0,B_j0) называется седловой точкой матрицы игры

Игра с седловой точкой – это игра, матрица которой содержит хотя бы одну седловую точку.

Для того чтобы f(x,y) имела седловую точку на декартовом произведении X и Y, необходимо и достаточно, чтобы существовали maxminff(x,y) и minmaxf(x,y) и чтоб выполнялось их равенство.

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

13. Доказательство теоремы о свойстве равнозначности седловых точек

Теорема: Если (x', y') и (x", y") – седловые точки функции f(x, y) на декартовом произведении X × Y, то значения данной функции в этих точках совпадают:

f(x', y') = f(x", y"). (1)

Доказательство: Так как (x', y'), (x", y")  X × Y, то и (x', y"), (x", y')  X × Y. В силу с одной стороны,

а, с другой стороны,

Система неравенств (2) и (3) эквивалентна равенству (1).