ГЛАВА 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. Таким обратом, множества
(для
) не пусты, и каждый элемент множества
есть выпуклая линейная комбинация элементов множества
. Поэтому, для того чтобы найти все элементы множества
, достаточно найти все элементы множества
. Позднее в этой главе мы покажем, что
есть конечное множество.