Теория игр

Согласно (2.3), седловой элемент    матрицы А одновременно минимален в строке  i*  и максимален в столбце j*. Этот вывод можно использовать как рабочее правило для нахождения седловых точек.

      Вывод. Если матрица выигрышей имеет седловую точку  (i*, j*), то  i*  и j* -  оптимальные стратегии первого и второго игрока,  v = - значение игры.

      Пример 2.1. Матрица 

 

имеет две седловые точки (2, 1) и (3, 1) с седловым элементом 1. Решение игры  i* Î {2, 3}, j* = 1, v = 1.

      Пример 2.2. Матрица 

 
 

не имеет  седловых точек. Решение игры в чистых стратегиях отсутствует.

     2.2. Понятие смешанных  стратегий. Чтобы понять суть смешанных стратегий, обратимся к примеру 1.2 игры в орлянку с матрицей выигрышей 

. 

Легко видеть, что матрица выигрышей  не имеет седловых точек, поэтому  оптимальные чистые стратегии игроков  не существуют.

     Изменим понятие решения игры так, чтобы  оно оставалось приемлемым для игроков  и обеспечивало разрешимость игры. Допустим, игроки выбирают свои чистые стратегии i = 1, 2  и j = 1, 2  случайно с вероятностями x₁, x₂  и y₁, y₂  соответственно. Тогда 

,     (2.4) 

.     (2.5) 

     Можно сказать, что игроки используют смешанные стратегии x = (x₁, x₂),  y = (y₁, y₂), задавая их так, чтобы выполнялись условия (2.4), (2.5). Множества смешанных стратегий игроков обозначим соответственно  X  и Y.

     Поскольку игроки выбирают теперь свои чистые стратегии случайно, то выигрыши игроков тоже становятся случайными. Подсчитаем математическое ожидание выигрыша первого игрока. В игре возможны четыре ситуации в чистых стратегиях: (1,1), (1,2), (2,1), (2,1). Вероятности появления этих ситуаций вычисляются с помощью теоремы умножения вероятностей и приведены в табл. 2.1.

Таблица 2.1

Вероятности выигрышей первого игрока в игре орлянка

 
 

Отсюда  по известной из теории вероятностей формуле находим математическое ожидание  M(x, y)  выигрыша первого игрока 

M(x, y) = (+1)x₁y₁ + (-1)x₁y₂ + (-1)x₂y₁ + (+1)x₂y₂. 

Таким образом, за счет случайного выбора стратегий  игроки переходят от первоначальной матричной игры  Г(А)  к новой антагонистической игре 

     Г

. 

     Покажем, что новая игра имеет решение. Искомые оптимальные стратегии  x*, y*  должны составлять седловую точку функции М  на  X × Y, т.е. удовлетворять неравенствам 

M(x, y*) ≤ M(x*, y*) ≤ M(x*, y) 

для всех смешанных стратегий  x, y. Преобразовав функцию выигрыша 

M(x, y) = x₁(y₁ - y₂) - x₂ (y₁ - y₂) = (x₁ - х₂) (y₁ - y₂), 

перепишем условия  для седловой точки в виде 

(x₁ - х₂) (y₁* - y₂*) ≤ (x₁* - х₂*) (y₁* - y₂*) ≤ (x₁* - х₂*) (y₁ - y₂).   (2.6) 

Множители  x₁ - х₂  и у₁ - у₂  на множествах  Х  и Y  могут независимо принимать значения разных знаков, поэтому неравенства (2.6) удовлетворяются лишь при 

x₁* - х₂* = 0,   y₁* - y₂* = 0. 

Отсюда  с учетом (2.4), (2.5) находим  x₁* = х₂* = y₁* = y₂* = . Следовательно, решение игры в смешанных стратегиях имеет вид 

x* = (

, ),   y* = ( , ),   M(x*, y*) = 0. 

     2.3. Смешанное расширение  матричной игры. После разобранного примера становится понятным формальный переход от матричной игры  Г(А)  с матрицей выигрыша  А  вида (2.1) к новой антагонистической игре  Г с множествами стратегий , заданными условиями 

,   (2.7) 

,   (2.8) 

и функцией выигрышей 

. 

      Цель  перехода прежняя – добиться разрешимости игр, в которых матрицы выигрышей  не имеют седловых точек. Прежней  остается и содержательная интерпретация  элементов новой игры: х_i  и y_j – вероятности выбора первым и вторым игроком чистых стратегий  i  и j  соответственно, - математическое ожидание выигрыша первого игрока в ситуации  .

      В дальнейшем удобно пользоваться векторно-матричной  формой записи функции выигрышей. Условимся  здесь и далее считать все векторы в формулах столбцами и использовать знак штрих (´) для обозначения транспонирования. Тогда 

.      (2.9) 

     Действительно, в принятых соглашениях по правилам перемножения матриц имеем 

 

      Смешанное расширение  Г   включает в себя исходную матричную игру  Г(А). В самом деле, если ввести специальные смешанные стратегии 

,   ,  (2.10) 

у которых  i-я и j-я координаты векторов соответственно равны 1,то 

, 

т.е. вектора (2.10) в игре  Г   аналогичны чистым стратегиям в игре Г(А).

      Разрешимость  игры  Г   в смешанных стратегиях сразу же вытекает из теоремы 1.4. Действительно, в данной игре множества   стратегий, заданные условиями (2.7), (2.8), выпуклые и замкнутые и функция выигрышей (2.9) непрерывная и вогнуто-выпуклая на  X × Y. Поэтому по теореме 1.4 наилучшие гарантированные выигрыши игроков существуют и равны. Сформулируем полученный вывод в такой форме.

      Теорема 2.1 (Дж. фон Нейман). Каждая матричная игра разрешима в смешанных стратегиях.

      Этот  факт установлен в 1929 году. Теорему 2.1 часто  называют основной теоремой матричных игр.

      Остановимся в заключение на практическом значении смешанных стратегий. Допустим, матричная  игра  Г(А)  не имеет решения в чистых стратегиях, и игрокам известно ее решение x*, y*, v  в смешанных стратегиях. Как они должны ими руководствоваться при выборе чистых стратегий? Очевидно, если игра разыгрывается один раз, то практическая польза от смешанных оптимальных стратегий, вообще говоря, не велика. Однако, положение меняется при многократном розыгрыше игры. Пусть она играется  N  раз и каждый раз игроки выбирают свои чистые стратегии i, j, ориентируясь на соответствующие координаты  x_i*, y_j*  оптимальных смешанных стратегий. Это значит, что за  N  розыгрышей чистые стратегии i  и j  должны применяться соответственно    и   раз так, чтобы частота выбора чистых стратегий была близка расчетным вероятностям 

;   . 

Если  при    все приближенные равенства становятся точными, то среднее арифметическое    выигрышей первого игрока за  N  розыгрышей стремится к значению  v  игры. Это непосредственно следует из определения математического ожидания. Итак, если при достаточно большом количестве розыгрышей матричной игры игроки выбирают чистые стратегии с предписанными оптимальными вероятностями, то среднее арифметическое их выигрышей будет близко значению игры. В этом и состоит практическая польза смешанных стратегий.

     2.4. Признаки оптимальности  стратегий. Установим вначале один вспомогательный факт.

      Лемма 2.1 (о переходе к смешанным стратегиям). Если смешанная стратегия  y  и число b  таковы, что справедливы неравенства 

,     (2.11)

то

      (2.12) 

для любой смешанной  стратегии  х.

      Доказательство. Пусть выполнены неравенства (2.11). Тогда для любой смешанной  стратегии  х  со свойствами (2.7) имеем 

. 

Суммируя  данные неравенства, получим 

 

что с  учетом равенства (2.7) равносильно (2.12). Лемма доказана.

      Аналогично  проверяются импликации, которые  тоже будем относить к лемме 2.1: 

; 

; 

. 

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

      Теорема 2.2. Для того, чтобы стратегии  х*, у*  и число  v  были решением игры  Г   необходимо и  достаточно выполнения неравенств 

      .  (2.13) 

      Доказательство. Необходимость. Пусть тройка  х*, у*, v – решение игры, т.е. 

          (2.14) 

для любых  стратегий  х, у  и . Отсюда и из (2.14) при   вытекает (2.13).

      Достаточность. Пусть некоторые стратегии  х*, у*  и число  v  удовлетворяют неравенствам (2.13). Покажем, что они образуют решение игры  Г . Переходя в неравенствах (2.13) к смешанным стратегиям (лемма 2.1), получим 

           (2.15) 

для любых  стратегий  х, у. В частности, полагая здесь х = х*,  у = у*, находим . Следовательно, неравенство (2.15) можно представить в виде (2.14), что свидетельствует об оптимальности стратегий х*, у*. Тогда число   есть значение игры  Г . Теорема доказана.

      Покажем, как пользоваться критерием оптимальности (2.13).

      Пример 2.1. Убедимся, что тройка 

    (2.16) 

составляет  решение игры с матрицей 

. 

      Предварительно  заметим, что множители  в критерии оптимальности (2.13) есть  i-я строка и j-й столбец матрицы  А. Следовательно, выражения - это скалярные произведения  i-й строки и j-го столбца матрицы А  на стратегии x*  и y*  соответственно. Пользуясь этими замечаниями, находим