ГЛАВА III. РЕШЕНИЯ ПРЯМОУГОЛЬНЫХ ИГР

1. Множество решений

В этой главе мы будем изучать множество решений произвольной прямоугольной игры Г. Поскольку пара является решением игры Г тогда и только тогда, когда X и У суть оптимальные стратегии соответственно для первого и второго игроков, то достаточно исследовать множество оптимальных стратегий игрока и множество оптимальных стратегий игрока Мы увидим, что если Г есть игра с матрицей порядка то есть выпуклая оболочка некоторого конечного множества точек -мерного пространства аналогично, есть выпуклая оболочка конечного множества точек -мерного пространства. Таким образом, множества имеют простую геометрическую интерпретацию — они представляют собою многогранники. Доказательство этого положения приведет нас к общему методу отыскания решений данной прямоугольной игры, более короткому и лучше приспособленному для машинного вычисления, чем способ, описанный в конце главы II.

Замечание 3.1. Некоторые доказательства этой главы, вероятно, окажутся более трудными, чем доказательства, приводимые в остальных главах книги, особенно для тех, кто мало знаком с матричной алгеброй. При первом чтении можно опустить Доказательства леммы 3.5 и теоремы 3.6, а также разделы 2 и 3, поскольку в остальном тексте на них нет ссылок.

Лемма 3.2. Если Г — прямоугольная игра с матрицей порядка , то и суть непустые ограниченные выпуклые и замкнутые подмножества соответственно -мерного и -мерного пространств.

Доказательство. Докажем лемму 3.2 толькодля ; доказательство для аналогично. Согласно теореме 2.3 — непустое.

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

где

и, следовательно,

так что лежит в гиперсфере радиуса 1 с центром в начале координат.

Пусть платежная матрица игры Г есть

и пусть математическое ожидание выигрыша игры Г равно Е, так что если

то

Пусть v — цена игры. Чтобы убедиться в том, что множество выпуклое, возьмем любые элементы множества и некоторый элемент множества ; образуем сумму

Нужно показать, что . Поскольку из , то по теореме 2.8 для всякого элемента Y множества

Поскольку то из неравенства (3) получаем, что

и следовательно,

ИЛИ

Из выражений (1) и (2) находим

а из (4) и (5) следует

Поскольку неравенство (6) справедливо для всякого элемента У множества то из теоремы 2.8 следует, что принадлежит множеству что и требовалось доказать.

Для доказательства замкнутости возьмем последовательность элементов множества сходящуюся к вектору X. Поскольку замкнуто, то, очевидно, нам нужно показать, что . Так как то на основании теоремы 2.8 для всякого элемента У множества

Но так как Е(X, У) есть линейная (и, следовательно, непрерывная) функция компонент X, то на основании неравенства (7)

Следовательно, по теореме 2.8 , что и требовалось доказать.

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

Из леммы 3.2 мы видим, что множества удовлетворяют условию теоремы 2.4. Таким обратом, множества (для ) не пусты, и каждый элемент множества есть выпуклая линейная комбинация элементов множества . Поэтому, для того чтобы найти все элементы множества , достаточно найти все элементы множества . Позднее в этой главе мы покажем, что есть конечное множество.