Матричные игры с нулевой суммой. Платежная матрица игры

§ 1. Матричные игры с нулевой суммой. Платежная матрица игры

     Во  многих практических задачах возникают  ситуации, когда требуется принять решение, не имея достаточной информации. Неизвестными могут быть как условия осуществления какой-либо операции, так и сознательные действия лиц, от которых зависит успех этой операции.

       Ситуации, в которых сталкиваются интересы двух сторон и результат любой операции, осуществляемой одной из сторон, зависит от действий другой стороны, называются конфликтными.

     Математическая модель конфликтной ситуации называется игрой, а математическая теория, помогающая принимать рациональные решения в конфликтной ситуации, - теорией игр.

     Конфликтующие стороны называются игроками, а действия, которые могут выполнять игроки, - стратегиями. От реальной ситуации игра отличается тем, что в игре противники действуют по строго определенным правилам.

     Матричной игрой называется игра, осуществляемая по следующим правилам:

     1. В игре участвуют два игрока;

     2. Каждый из игроков обладает конечным набором стратегий;

     3. Игра заключается в том, что каждый из игроков, не имея информации о действиях противника, делает один ход (выбирает одну из своих стратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.

     4. И выигрыш, и проигрыш выражаются числами.

  Матричная игра называется игрой с нулевой суммой, если в этой игре выигрыш одного игрока равняется проигрышу другого игрока.

     Каждая  матричная игра с нулевой суммой имеет платежную матрицу. Для того чтобы построить эту матрицу, обозначим одного из игроков символом A, а другого - символом B, и предположим, что …, - стратегии, которые может применять игрок A, а …, - стратегии, которые может применять игрок B.

     Матричная игра, в которой у игрока A имеется m стратегий, а у игрока    B - n стратегий, называется игрой типа m n .

Рассмотрим  матрицу

C =

у которой  элементы   (i =1,2,...,m; j =1,2,...,n) равны выигрышам игрока A (и проигрышам игрока B) при применении игроками стратегий и соответственно.

   Матрица C называется платежной матрицей игры.

   Пример 1.1.  Игра, называемая «Открывание пальцев», заключается в следующем. Два игрока одновременно из сжатого кулака правой руки открывают по нескольку пальцев. Общее количество открытых пальцев является суммой выигрыша, причем, если общее количество открытых пальцев четно, то выигрывает первый игрок, если же общее количество открытых пальцев нечетно, то выигрывает второй игрок.

   Составить платежную матрицу игры.

   Решение. Поскольку каждый из игроков может открыть 1, 2, 3, 4 или 5 пальцев, то у каждого из них имеется по 5 соответствующих стратегий: стратегии у первого игрока, и - у второго. Таким образом, рассматриваемая игра является матричной игрой типа 5 5, и можно составить таблицу выигрышей, в зависимости от стратегий, применяемых игроками:

Т а б  л и ц а 1.1

   

 

Из таблицы 1.1 следует, что платежная матрица  игры имеет вид

C =

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

§ 2. Нижняя и верхняя цена игры. Принцип минимакса

     Рассмотрим  матричную игру типа m n с платежной матрицей

C =

Если  игрок A выберет стратегию , то все его возможные выигрыши будут элементами i - й строки матрицы C. В наихудшем для игрока A случае, когда игрок B применяет стратегию, соответствующую минимальному элементу этой строки, выигрыш игрока A будет равен числу .

     Следовательно, для получения наибольшего выигрыша, игроку A нужно выбирать ту из стратегий, для которой число максимально.

  Число

называется  нижней ценой игры, а стратегия игрока A, соответствующая наибольшему из чисел  ,  называется  максиминной.

     Таким образом, если игрок A будет придерживаться максиминной стратегии, то ему гарантирован выигрыш, не меньший, чем , при любом поведении   игрока  В.

     Проанализируем  теперь платежную  матрицу с точки зрения игрока  B, заинтересованного в том, чтобы игрок A выиграл, как можно меньше. 

     Если  игрок B выберет стратегию , то все возможные выигрыши игрока A будут элементами  j - го столбца платежной матрицы С. В наихудшем для  игрока B случае, когда игрок A применяет стратегию, соответствующую максимальному элементу этого столбца, выигрыш игрока B будет равен числу .   

     Следовательно, игроку B нужно выбрать такую стратегию, для которой число   минимально.

     Число  

называется  верхней ценой игры, а стратегия игрока B, соответствующая наименьшему из чисел  , называется минимаксной.

     Таким образом, если игрок B применяет минимаксную стратегию, то игрок A не может выиграть больше, чем β.

     Принцип  осторожности,  заставляющий  игроков  придерживаться максиминной  и  минимаксной  стратегий  соответственно,  называют «Принципом минимакса», а минимаксную стратегию и максиминную стратегию называют общим термином  «Минимаксные стратегии».

     Пример 2.1. Найти нижнюю и верхнюю цены игры с платежной матрицей

   

= .

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

Нижняя  цена игры

 

= max{1,3,-2} = 3

Верхняя цена игры

= min{10,4,3,10} = 3

§ 3. Игры с седловой точкой

     Игра  называется  игрой с седловой точкой, если ее нижняя и верхняя цены совпадают, то есть выполняется равенство

= = .

     Для игры с седловой точкой общее значение  нижней и верхней цены игры

V= =

называется  ценой игры.

     Замечание 1. В Примере 2.1. нижняя и верхняя цены игры совпадают и равны 3, т.е. рассмотренная игра является игрой с седловой точкой. 

     Замечание 2. Максиминной стратегией в Примере 2.1. является стратегия ,  минимаксной стратегией является стратегия .

     Рассмотрим  теперь для игры с седловой точкой такой элемент платежной  матрицы , который соответствует минимаксным стратегиям . Этот элемент является одновременно минимальным в своей строке и максимальным в своем столбце, и выполняются неравенства

     V=

= = = .

Следовательно, выполняется равенство =V.

   Элемент платежной матрицы    называется  седловой точкой.

   Замечание 3.В Примере.2.1. седловой точкой является элемент   платежной матрицы. Этот элемент равен 3 и, конечно же, совпадает с ценой игры.  
 
 
 
 
 
 

§ 4. Игры без седловой точки

Рассмотрим  следующий пример:

Пример 4.1. Найти нижнюю и верхнюю цены игры с платежной матрицей 

C=

.

Решение. Действуя аналогично Примеру  2.1., получаем

Нижняя  цена игры

= max {-1, 2,-2, 1} = 2.

Верхняя цена игры

 

= min {5, 4, 5} = 4.

     Замечание 1.  В Примере 4.1. нижняя цена игры отличается от верхней  цены игры, следовательно, игра является игрой без седловой точки. Максиминной стратегией является стратегия . Минимаксной стратегией является стратегия .

     Замечание 2.  Для любой игры без седловой точки выполнено неравенство < . 
 
 
 
 
 

§ 5. Игры, повторяемые многократно. Смешанные стратегии

     Если  партнеры играют только один раз, то игрокам целесообразно придерживаться принципа минимакса, как в игре с седловой точкой, так и в игре без седловой точки. 

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

     Если  же многократно повторяется  игра без седловой точки, то постоянное использование минимаксных стратегий становится невыгодным. 

     Действительно, в игре без седловой точки элемент  платежной матрицы  , соответствующий минимаксной стратегии игрока A, не обязан быть минимальным в своей строке. Следовательно, игрок B, зная о том, что игрок A в следующей игре будет использовать минимаксную стратегию , может выбрать стратегию, отвечающую минимальному элементу строки .  В результате выигрыш игрока A уменьшится от величины  до величины  . Аналогично может поступить и игрок A, неожиданно применив против игрока B стратегию, соответствующую максимальному элементу столбца .

     Более того, доказано, что при многократно повторяемой игре без cедловой точки игроку A, для обеспечения среднего выигрыша, большего, чем , следует чередовать свои стратегии . Игроку  B для улучшения результата также целесообразно чередовать свои стратегии .

     По  этой причине для многократно  повторяемых игр без седловой точки вводится следующее определение.

   В играх, которые  повторяются многократно,  каждая из стратегий  называется чистой стратегией. 

   Стратегия игрока A, обозначаемая

=

и состоящая  в том, чтобы применять чистые стратегии  , чередуя их  по  случайному  закону  с частотами , называется    смешанной стратегией. Частоты удовлетворяют соотношению

+ + + = 1 .

   Чистые  и смешанные стратегии игрока  B определяются аналогично.

   Замечание. Каждая чистая стратегия является частным случаем смешанной стратегии, когда одна из стратегий применяется с частотой 1, а все остальные − с частотой 0.