Теория игр

    Действительно, если игрок 1 выбирает с равными вероятностями  стратегии 1 и 3, то при применении любой из двух чистых стратегий игроком 2 математическое ожидание выигрыша игрока 1 будет равным либо

    

,

либо

    

. 

Аналогично, если игрок 2 использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно . Следовательно, указанные стратегии являются оптимальными в игре G³, а величины – значением игры G³. Из предыдущего следует, что эти стратегии оптимальны и в G¹.

    Таким образом, стратегия Х = ( , 0, , 0) является оптимальной стратегией игрока 1, стратегия Y = (0, , , 0) – оптимальной стратегией игрока 2 в игре G¹, а значение игры G¹ равно . В силу свойства 4 решением игры G будет тройка  (Х,Y, ).

    § 4.  ИГРЫ  ПОРЯДКА 2 ^х 2.

 

    В общем случае игра  2 2  определяется матрицей

    

Прежде  всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например 1) имеет чистую оптимальную стратегию, а другой – только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Далее,  по свойству  1  следует, что а₁₁ = а₁₂ = u  и матрица имеет вид

    

.

Легко видеть, что для матриц такого вида одна из стратегий игрока 2 является доминируемой. Следовательно, по свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению.

    Пусть Х = (x, 1 - x) – оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см. также свойство 7)

    

Отсюда  следует, что при  u ¹ 0  столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица А принимает вид

    

и игрок 1 имеет чистую оптимальную стратегию (он выбирает с вероятностью 1 ту из строк, элементы которой не меньше соответствующих элементов другой), что противоречит предположению. Следовательно, если u ¹ 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы А отличен от нуля. Из этого следует, что последняя система уравнений имеет единственное решение. Решая её, находим

    

;

    

.

    Аналогичные рассуждения приводят нас  к  тому,  что  оптимальная  стратегия  игрока  2 Y = (h, 1 - h)  удовлетворяет системе уравнений

    

откуда

    

.

    §5. СВЕДЕНИЕ МАТРИЧНОЙ ИГРЫ К ЗАДАЧЕ 

    ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

    Предположим, что цена игры положительна (u > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

    Итак, пусть дана матричная игра с матрицей А порядка m ^х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х₁, ..., х_m), y = (y₁, ..., y_n) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.

    

                                            

    

                                             

Разделим  все уравнения и неравенства  в (1) и (2) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения :

    

     ,          ,

Тогда (1) и (2) перепишется в виде :

    

,     ,     ,     ,

    

,     ,     ,     .

Поскольку первый игрок стремится найти  такие значения х_i и, следовательно, p_i , чтобы цена игры u была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений  p_i  , при которых

    

,   .                                           

Поскольку второй игрок стремится найти  такие значения y_j и, следовательно, q_j, чтобы цена игры u была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений  q_j,  , при которых

    

,   .                                          

Формулы (3) и (4) выражают двойственные друг другу  задачи  линейного программирования (ЛП).

    Решив эти задачи, получим значения  p_i ,  q_j и u.Тогда смешанные стратегии, т.е. x_i и y_j получаются по формулам :

    

                                                        

    Пример. Найти решение игры, определяемой матрицей.

    

    Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

    

Составим  теперь пару взаимно-двойственных задач :

    

                    

Решим вторую из них 

 
 
 

Из оптимальной  симплекс-таблицы следует, что

    (q₁, q₂, q₃) = (0;

; 1),

а из соотношений  двойственности следует, что 

    ( p₁, p₂, p₃) = (

; 1; 0).

Следовательно, цена игры с платёжной матрицей А₁ равна

    

.          ,

а игры с платёжной матрицей А :

    

.

При этом оптимальные стратегии игроков  имеют вид: