Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 4. Прямоугольные игры с седловыми точкамиРассмотрим прямоугольную игру с матрицей порядка m x n
Если игрок
Вообще, если он выбирает число i, то ему обязательно будет уплачено по меньшей мере
Но поскольку он может выбрать i как угодно, он может, в частности, выбрать его так, чтобы сделать величину
возможно большей. Итак, для
Аналогично, платежи игроку
Напомним теперь элементарное положение о максимумах и минимумах: если f — любая действительная функция и ее максимумы и минимумы существуют, то
и
Поскольку в рассматриваемом случае i и j имеют конечный интервал изменения и все максимумы и минимумы существуют, то справедливо соотношение
Поэтому
и, следовательно, так, что
Итак,
а
Если оказывается, что
то Аналогично,
где
и
так что
Ввиду важности равенства (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) справедливо тогда и только тогда, когда матрица А имеет седловую точку. Поэтому, если матрица прямоугольной игры имеет седловую точку Так, например, матрица
имеет седловую точку Нужно заметить, что когда мы говорим, что оптимальным выбором для Таким образом, для того случая, когда матрица прямоугольной игры имеет седловую точку, мы получаем теорию, указывающую, как всего лучше играть в эту игру. Однако у нас остается вопрос о том, как играть в игру с матрицей, например
которая не имеет седловой точки. Этот вопрос будет рассмотрен в главе II. Библиографические замечанияПервые работы по теории игр и применении этой теории к экономике принадлежат фон Нейману [88], Кальмару [54]. Теория была весьма полно разработана в книге фон Неймана и Моргенштерна [92], из которой многое вошло в эту книгу. Общий обзор этого вопроса был сделан в 1949 г. Паксоном [93], а более популярное изложение содержится в работах Макдональда [71], [72] и [73].
|
1 |
Оглавление
|