4. Прямоугольные игры с седловыми точками

Рассмотрим прямоугольную игру с матрицей порядка m x n

Если игрок в некоторой партии этой игры выбирает 1, то ему наверняка будет уплачен хотя бы минимальный элемент первой строки, то есть по меньшей мере

Вообще, если он выбирает число i, то ему обязательно будет уплачено по меньшей мере

Но поскольку он может выбрать i как угодно, он может, в частности, выбрать его так, чтобы сделать величину

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

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

Напомним теперь элементарное положение о максимумах и минимумах: если f — любая действительная функция и ее максимумы и минимумы существуют, то

и

Поскольку в рассматриваемом случае i и j имеют конечный интервал изменения и все максимумы и минимумы существуют, то справедливо соотношение

Поэтому может играть так, чтобы наверняка получить хотя бы

и, следовательно, так, что получит самое большее

Итак, может гарантировать себе, что он получит по меньшей мере

а может помешать ему получить больше, чем

Если оказывается, что

то должен понять, что он может получить v, а его противник может помешать ему получить больше чем v. Таким образом, если только у нет серьезных оснований полагать, что будет поступать необдуманно (а это должно быть основано на чем-то, не относящемся к самой игре, например на том, что у есть предрассудок, который заставляет его играть всегда определенным образом), может делать ставку на с; и играть так, чтобы получить v.

Аналогично, может делать ставку на — v и играть так, чтобы получить эту величину. Если бы равенство (1) было справедливо для всякой матрицы А, то на основании приведенных выше соображений поиски оптимального способа игры в прямоугольные игры на этом бы закончились. Но, к сожалению, положение не так просто; действительно, легко указать примеры матриц, для которых (1) неверно. Рассмотрим матрицу

где ; тогда

и

так что

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

Теорема 1.1. Пусть имеются множества А и В; f(x, у) есть вещественная функция двух переменных при , и существуют

и

Тогда

Доказательство. Для любых фиксированных x и у по определению минимума

и по определению максимума

Следовательно,

Поскольку левая часть неравенства (2) не зависит от у, мы заключаем, что

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

что и требовалось доказать.

Замечание 1.2. Возможность применения этого положения к матрицам основана на том, что матрицу

можно рассматривать как действительную функцию двух переменных , которая определена для равенством

Следствие 1.3. Пусть

произвольная матрица . Тогда

Доказательство следует из теоремы 1.1, если принять за А множество первых m положительных целых чисел, а за В множество первых n положительных целых чисел.

Для того чтобы сформулировать необходимое и достаточное условие справедливости равенства (1), удобно ввести новое понятие из теории действительных функций двух переменных.

Определение 1.4. Пусть — действительная функция, определенная для всех и . Точка , где , называется седловой точкой, если выполняются следующие условия:

Следовательно, функция имеет в качестве седловой точку , так как для всех действительных х и у

(Этот пример не удивителен, так как гиперболический параболоид

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

Теорема 1.5. Пусть — действительная функция, определенная для , и существуют

и

Тогда необходимое и достаточное условие того, чтобы

состоит в том, должна иметь седловую точку. Кроме того, если есть седловая точка функции , то

Доказательство. Докажем достаточность условия. Пусть — седловая точка функции . Тогда для всех и

Из (4) мы заключаем, что

а из (5) следует, что

так что

Поскольку

и

мы заключаем из (6), что

Но по теореме 1.1 первый член неравенства (7) не менее третьего; отсюда мы заключаем, что все три члена равны, что и требовалось доказать. Чтобы убедиться в том, что условие необходимо, допустим, что есть элемент множества А, при котором

имеет максимальное значение, а — элемент множества В, при котором

имеет минимальное значение; иначе говоря, пусть соответственно элементы множеств А и В, удовлетворяющие условиям

Покажем, что есть седловая точка функции .

Поскольку мы предполагаем, что

то из (8) следует равенство

Из определения минимума имеем

и, следовательно, учитывая (9), получаем

Из последнего неравенства и из определения максимума мы заключаем, что для всех

а это есть условие (1) определения 1.4. Аналогично доказывается условие (2) определения 1.4, что завершает доказательство.

Замечание 1.6. На основании интерпретации матрицы как действительной функции (замечание 1. 2) мы видим, что седловая точка матрицы есть пара целых чисел , таких, что в одно и то же время представляет минимум своей строки и максимум своего столбца. Таким образом, матрица

имеет седловую точку || 1 2 ||, так как 11 представляет наименьший элемент в первой строке и наибольший элемент во втором столбце. Матрица

имеет две седловые точки . Матрица

имеет лишь одну седловую точку, так как 12 не является максимумом третьего столбца.

Используя понятие седловой точки матрицы, мы выведем теперь из теоремы 1.5 следующее следствие. Следствие 1.7. Пусть

Необходимым и достаточным условием того, что

является существование седловой точки матрицы А, т. е. существование пары целых чисел , для которых является одновременно минимумом своей строки и максимумом своего столбца.

Кроме того, если — седловая точка матрицы А, то

Из следствия 1.7 мы видим, что (1) справедливо тогда и только тогда, когда матрица А имеет седловую точку. Поэтому, если матрица прямоугольной игры имеет седловую точку (в этом случае мы будем иногда говорить для краткости, что сама игра имеет седловую точку), то для лучше выбрать , а для — . Согласно этому назовем оптимальными выборами соответственно для , а величину ценой игры (для

Так, например, матрица

имеет седловую точку так как 4 является минимумом второй строки и максимумом третьего столбца. Следовательно, при игре в прямоугольную игру, имеющую такую матрицу, оптимальным выбором для является 2, для . Цена игры равна 4. Выбрав может быть уверен, что он получит по меньшей мере 4, а выбрав может не допустить, чтобы получил более 4.

Нужно заметить, что когда мы говорим, что оптимальным выбором для является 2, мы не имеем в виду, что для него всего разумнее будет выбирать 2 при всех обстоятельствах. Например, допустим, что знает, что выберет 4 (пусть знает, что всегда следует совету некоего человека, и подкупил последнего, чтобы он советовал выбирать 4); тогда, конечно, всего лучше для выбирать 1 вместо 2, так как при этом он получит 20 вместо 6. Но игрок может знать о намерениях своего противника лишь в исключительных случаях, поэтому вообще лучше играть математически оптимальным способом.

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

которая не имеет седловой точки. Этот вопрос будет рассмотрен в главе II.

Библиографические замечания

Первые работы по теории игр и применении этой теории к экономике принадлежат фон Нейману [88], Кальмару [54]. Теория была весьма полно разработана в книге фон Неймана и Моргенштерна [92], из которой многое вошло в эту книгу. Общий обзор этого вопроса был сделан в 1949 г. Паксоном [93], а более популярное изложение содержится в работах Макдональда [71], [72] и [73].