Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 120 стр.

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


i Î {1,L, m},     j Î {1,L, n} . Тогда математическое ожидание платы M : U ´V ® R1 ,

как функция «смешанных» стратегий игроков, имеет вид

                      M (u, v ) = åå aij u i v j = u, Av = AT u , v , u Î U , v Î V .
                                    m       n


                                    i =1 j =1


       Определение 10. Антагонистическая игра двух лиц (U ,V , A) называется
матричной игрой в «смешанных» стратегиях (с матрицей A ).
       Седловая точка (u0 , v0 ) Î U ´V в матричной игре в «смешанных» стратегиях

удовлетворяет двойному неравенству
                                                                     æ u1 ö÷              æ 1ö
                                                                     çç ÷               çç v ÷÷
                                                                            ÷                   ÷
     åå        aij u0i v j £ åå aij u0i v0j £ åå aij u i v0j , "u = çç L ÷÷ Î U , "v = ççL÷÷ Î V .
      m   n              m      n                   m   n

                                                                      ç     ÷            ç            (1)
     i =1 j =1               i =1 j =1        i =1 j =1               çç m ÷÷            çç n ÷÷÷
                                                                       èu ø÷              èu ÷ø

       Покажем, что в двойном неравенстве (1) перебор всех «смешанных»
стратегий игроков достаточно проводить лишь по множеству «чистых»
стратегий. Действительно, справедливо следующее утверждение.
       Теорема 4. Пара «смешанных» стратегий (u0 , v0 ) Î U ´V                                       образует

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

                        å aij u0i £ åå aij u0i v0j £ å aij v0j , "j Î {1,L, n} , "i Î {1,L, m} .
                         m              m       n            n
                                                                                                            (2)
                         i =1           i =1 j =1           j =1


       Доказательство. Необходимость. Пусть (u0 , v0 ) Î U ´V - седловая точка.

Неравенство (1) справедливо для всех «смешанных» стратегий игроков. В
частности, оно будет верно и для «чистых» стратегий ui , v j , i Î {1,L, m},

j Î {1,L, n} . Подставляя эти стратегии в (1), получим двойное неравенство (2).

Необходимость доказана.
       Достаточность. Пусть для некоторой пары стратегий (u0 , v0 ) Î U ´V
выполнено условие (2). Перепишем это условие в виде
                                         AT u0 £ d n , d m £ Av0 ,                                          (3)




                                                            120