Теория игр: Текст лекций. Саакян Г.Р. - 8 стр.

                                                                                           7

      2-й шаг. Среди чисел   β1 , β 2 ,..., β n выбирается минимальное число
                                             β = min
                                                   k
                                                      βk ,
или, подробнее,
                                        β = min
                                             k
                                                max aik .
                                                 i

      Выбранное число β также является одним из элементов заданной матрицы A .
      Пояснение. Действуя наиболее осторожно и рассчитывая на наиболее разумное пове-
дение противника, игрок B должен остановиться на той стратегии Bk , для которой число
β k является минимальным.
       Если игрок B будет придерживаться стратегии, выбранной описанным выше спосо-
бом, то при любом поведении игрока A игроку B гарантирован проигрыш, не превышаю-
щий β . Число β называется верхней ценой игры.
       Принцип построения стратегии игрока B , основанный на минимизации максималь-
ных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принци-
пом стратегия Bk 0 – минимаксной стратегией игрока B .
      Нижняя цена игры α и ее верхняя цена    β всегда связаны неравенством
                                            α≤β.
      Если α =    β , или, подробнее,
                             max min
                                  k
                                     aik = ai k = min
                                               0 0 k
                                                      max aik ,
                               i                            i

то ситуация { Ai 0 , Bk 0 } оказывается равновесной, и ни один из игроков не заинтересован в
том, чтобы ее нарушить (в этом нетрудно убедиться путем рассуждений, подобных прове-
денным при анализе игры в примере 2).
       В том случае, когда нижняя цена игры равна верхней цене игры, их общее значение
называется просто ценой игры и обозначается через v .
       Цена игры совпадает с элементом ai0 k0 матрицы игры A , расположенным на пересе-
чении i0 -й строки (стратегия Ai0 игрока A ) и k0 -го столбца (стратегия Bk0 игрока B ), –
минимальным в своей строке и максимальным в своем столбце.
       Этот элемент называют седловой точкой матрицы A (или точкой равновесия), а про
игру говорят, что она имеет седловую точку.
       Термин «седловая точка» взят из геометрии. Среди алгебраических поверхностей 2-го
порядка есть поверхность, называемая гиперболическим параболоидом (она задается урав-
          x2 y2
нением z = 2 − 2 ). В окрестности начала поверхность своей формой напоминает седло, а
          a b
само начало координат представляет собой точку поверхности, в которой одновременно дос-
тигается минимум по х-координате и максимум по у-координате.
       Стратегии Ai0 и Bk0 , соответствующие седловой точке, называются оптимальными
чистыми стратегиями, а совокупность пары оптимальных стратегий и цены игры – решени-
ем матричной игры с седловой точкой. Про саму игру в этом случае говорят, что она реша-
ется в чистых стратегиях.
       Замечание. Седловых точек (и значит, пар оптимальных стратегий) в матричной игре
может быть несколько, но все они имеют одно и то же значение.
       Матричные игры с седловой точкой привлекают своей простотой, однако, более ти-
пичным является случай, когда применение описанного алгоритма приводит к неравенству
                                        α<β.