WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 


Pages:   || 2 |

«ИГР Дж МАК-КИНСИ ВВЕДЕНИЕ В ТЕОРИЮ ИГР ПЕРЕВОД С АНГЛИЙСКОГО ‘ Й^^СфІОЙ ЬЕВА пвд Фе^ акцией Д. Б. ЮДИНА т ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1960 INTRODUCTION TO THE ...»

-- [ Страница 1 ] --

ВВЕДЕНИЕ

В ТЕОРИЮ

ИГР

Дж МАК-КИНСИ

ВВЕДЕНИЕ

В ТЕОРИЮ ИГР

ПЕРЕВОД С АНГЛИЙСКОГО

‘ Й^^СфІОЙ ЬЕВА

пвд Фе^ акцией

Д. Б. ЮДИНА

т

ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО

ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

МОСКВА 1960

INTRODUCTION

TO THE THEORY

OF GAMES

J. C. C. McKINSEY T H E R A ^ n r.O R F f in “ ITTOM _ I f if d ЕоЯ КЮ i E K A j NEW YORK. TORONTO. LONDON McGRAW-HILL BOOK COMPANY, INC .

Д ж. Мак-Кинси. Введение в теорию игр .

Редактор А. Н. Копылова .

Технический редактор С. Н. Ахламов. Корректор Л. О. Сечейко .

Сдано в набор 21/Х І 1960 г. Подписано к печати 16/Х І 1960 г .

Бумага 84x108 1/з2- Физ. печ. л. 13,125. Условн. печ. л. 21,53 .

Уч.-изд. л. 19,19. Тираж 15 ООО экз. Т-08987. Цена книги 11 руб. 10 коп .

С 1/1 1961 г. цена 1 р. И к. Заказ № 584 .

Государственное издательство физико-математической литературы .

Москва, В-71, Ленинский проспект, 15 .

Московская типография № 5 Мосгорсовнархоза. Москва, ТрехпрудныГі п е р., 9 .

ОГЛАВЛЕНИЕ П р е д и с л о в и е р е д а к т о р а п е р е в о д а

Предисловие автора

ГЛАВА I ^ ПРЯМОУГОЛЬНЫЕ ИГРЫ (11)

1. В в е д е н и е



2. Терминология и клдссификация и г р

3. Определение прямоугольных и г р

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

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

У п р а ж н е н и я

ГЛАВА II ^ ОСНОВНАЯ ТЕОРЕМА ДЛЯ ПРЯМОУГОЛЬНЫХ ИГР (33)

1. Смешанные стр атеги и

2. Геометрическое о б о с н о в а н и е

3. Доказательство основной теоремы для произвольных прямоугольных и г р

4. Свойства оптимальных с т р а т ег и й

5. Соотношения п р ев осходств а

6. Графический метод р е ш е н и я

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

У п р а ж н ен и я

–  –  –

ГЛАВА XI РАЗДЕЛИМЫЕ ИГРЫ (250)

1. Метод о т о б р а ж е н и я

2. Пояснительный п р и м е р

3. Фиксированные т о ч к и

4. Дальнейшие п р и м е р ы

5. Решение прямоугольной игры как разделимой игры... 287

6. Решение игры с ограничениями как разделимой игры.. 290 Библиографические за м е ч а н и я

У п р а ж н е н и я

г л А в А XII ИГРЫ С ВЫ ПУКЛЫ М И ПЛАТЕЖНЫМИ ФУНКЦИЯМ И (295)

1. Выпуклые ф у н к ц и и

2. Единственная стратегия для одного и г р о к а

3. Стратегии для другого и г р о к а

4. Замечания и п р и м е р ы

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

У п р а ж н ен и я

Г Л А В А XIII ПРИМЕНЕНИЯ ТЕОРИИ ИГР К СТАТИСТИКЕ (315) Библиографические за м еч а н и я

У п р а ж н ен и я

ГЛАВА XIY ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (332) Библиографические замечания

У п р а ж н ен и я

ГЛАВА XV ИГРЫ п ЛИЦ С НУЛЕВОЙ СУММОЙ (344)

1. Характеристические ф у н к ц и и

2. Приведенная ф о р м а

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

У п р а ж н е н и я

ГЛАВА XVI РЕШ ЕНИЯ ИГР п ЛИЦ (368)

1. И с х о д





2. Определение р е ш е н и я

3. Изоморфные игры

4. Игры трех л и ц

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

У п р а ж н е н и я

ГЛАВА XVII

ИГРЫ, В КОТОРЫХ СУММА ВЫИГРЫШЕЙ МОЖЕТ

БЫТЬ НЕ РАВНА НУЛЮ. ТЕОРИЯ ФОН Н Е Й М А Н А МОРГЕНШТЕРНА (386)

1. Характеристические ф у н к ц и и

2. Исходы и р е ш е н и я

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

У п р а ж н е н и я

ГЛАВА XVIII НЕКОТОРЫЕ НЕРЕШЕННЫЕ ЗАДАЧИ (400)

1. Два вида з а д а ч

2. Игры, проводимые на пространстве ф у н к ц и й

3. П сев д о и гр ы

4. Игры с ненулевой суммой и игры п лиц

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

Л и т е р а т у р а

Дополнительный список л и т е р а т у р ы

Литература на русском я з ы к е

Предметный указатель

Первые работы по теории игр принадлежат Цермело и Борелю и относятся к началу X X в. В 1928 г. фон Нейман доказал основную теорему теории игр. Но только появление и широкое распространение быстродействую­ щих электронных вычислительных машин, обеспечиваю­ щих возможность эффективноно решения громоздких игро­ вых задач, привлекло к теории игр внимание широкого круга специалистов и прикладников .

В послевоенные годы за рубежом опубликовано боль­ шое количество статей и книг по теории игр. Естественно, не салонные игры определили интерес к этой науке .

Теория игр — совокупность математических методов ана­ лиза и оценки конфликтных ситуаций — находит широкое применение к вопросам бизнеса в условиях конкуренции, к планированию военных операций и управлению воен­ ной техникой. Многочисленные исследования последних лет еще больше расширили рамки приложения игровых методов. В частности, установленная связь теории игр и линейного программирования позволяет применять ме­ тоды решения игр к самым разнообразным задачам пла­ нирования народного хозяйства и управления производ­ ством .

В предлагаемой вниманию читателя книге Мак-Кинси систематически излагаются основные понятия теории игр, наиболее развитые методы решения игр и некоторые при­ ложения теории .

Курс Мак-Кинси не является первой книгой по тео­ рии игр на русском языке. Недавно издательством ино­ странной двдературы выпущен перевод монографии Блекуэлла и Гиршика «Теория игр и статистических реше­ ний». Монография рассчитана на специалистов по теории вероятностей. Теория игр здесь излагается в связи со ста­ тистическими задачами и далеко не все результаты тео­ рии, представляющие интерес для анализа экономических и военных задач, включены в монографию. В настоящее время подготавливается также к печати перевод чрезвы­ чайно интересной книги Льюса и Райфа «Игры и реше­ ния», содержащей критический обзор важнейших матема­ тических проблем теории игр и возможных приложений этой дисциплины к анализу экономических и социальных явлений. Однако’ эта богатая идеями книга по самой своей структуре вряд ли может служить учебным руко­ водством для изучения основ теории игр. Нам представ­ ляется, что курс Мак-Кинси «Введение в теорию игр», построенный как относительно элементарный учебник и охватывающий основные сложившиеся к настоящему вре­ мени направления развития теории соревнования, найдет широкий круг читателей .

По-видимому, целесообразно, чтобы изучение курса Мак-Кинси предшествовало работе над более специаль­ ной монографией Блекуэлла и Гришика и более широки­ ми проблемами книги Льюса и Райфа .

В курсе Мак-Кинси удачно сочетаются математическая строгость и наглядность изложения. Большое количество примеров иллюстрирует не только основные понятия и методы решения теории игр, но и игровые постановки прикладных задач .

Материал книги вполне доступен инженеру. Специаль­ ные математические вопросы, обычно не включаемые в курсы технических вузов, выделены в книге в отдель­ ные параграфы и главы .

Курс представляет безусловный интерес для широ­ кого круга научных работников различных специаль­ ностей .

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

Ссылки на непереведенную литературу по специальным вопросам заменены ссылками на соответствующую оте­ чественную литературу* Эта книга предназначена служить учебником для аспирантов и студентов старших курсов университета .

Предполагается, что учащиеся имеют по меньшей мере сведения из анализа в объеме курсов дифференциального и интегрального исчисления. Поэтому я пользуюсь без разъяснений такими понятиями, как сходимость, непре­ рывность, производная, интеграл Римана, ниж няя и верх­ няя грани, максимум и минимум. При этом я использую без особых ссылок наиболее известные теоремы, связан­ ные с этими понятиями .

Д ля понимания главы III полезно некоторое знаком­ ство с классической алгеброй и теорией матриц. Для студентов, не знакомых с этой областью математики, я включил в эту главу краткий очерк основных операций над матрицами. Нужно отметить, что содержание после­ дующих глав не зависит сколько-нибудь существенно от выводов главы III, так что читатель вполне может просто опустить эту главу .

Чтобы сделать книгу доступной более широкому кругу учащихся, я подробно останавливаюсь на некоторых менее известных понятиях. Это относится, в частности, к функциям распределения и интегралу Стилтьеса, которым я посвятил отдельные главы, и к некоторым основ­ ным топологическим понятиям, объяснение которых дано в § 2 главы III, Я старался отдать должное авторам сформулирован­ ных здесь выводов, указывая их в исторических и библио­ графических замечаниях, приведенных в конце некото­ рых глав. Помимо этой дани общего характера, я хочу выразить свою благодарность ряду друзей, без помощи которых книга вряд ли была бы написана. М-р Оливер Гросс из Рэнд Корпорейшн предоставил мне несколько примеров для главы X; м-р Д. Д. Уильямс, также из Рэнд Корпорейшн, любезно познакомил меня с несколь­ кими примерами игр, которые он собрал для своей буду­ щей книги; д-р А. В. Мартин из Калифорнийского уни­ верситета к д-р Д. Г. Вендель из Рэнд Корпорейшн сде­ лали несколько ценных указаний относительно глав IX и X; профессор Дэвид Блэквелл из Гарвардского уни­ верситета помог «формулировать изложение теории ста­ тистических выводов в главе X III; д-р Норман Дальки и д-р Ф. М. Томпсон — оба из Рэнд Корпорейшн — помогли мне при составлении глав V и VI; м-р JI. С. Шепли из Принстонского университета тщательно просмотрел всю рукопись, устранив много нелепостей и ошибок .

Наконец, особенную благодарность я должен выразить д-ру Мельвину Дрешеру и д-ру Олафу Хельмеру, работ­ никам Рэнд Корпорейшн, часто отрывавшимся от своей собственной работы, чтобы помочь мне. Их помощь не­ оценима .

Д -р М ак-Кинси Станфорд. Калифорния Январь 1952 г .

ГЛАВА I

П РЯМ О У ГО ЛЬН Ы Е ИГРЫ

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

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

Существенная разница между стратегическими играми и играми чисто случайными заключается в том, что в играх первого рода можно использовать мастерство и умствен­ ные способности игроков, а во вторых они бесполезны .

Поэтому любитель поступил бы очень неразумно, если бы стал играть в шахматы на высокую ставку против мастера:

он почти наверное разорился бы. Наоборот, вопреки обычным ^ м к а з н я м (которые, вероятнее всего, распро­ страняют содержатели игорных домов), «системы» игры в рулетку на несмещенном колесе не существует: идиот имеет такие же шансы на выигрыш в этой игре, как и умный человек (из этого, однако, не следует, что в случайных играх нет нерешенных математических задач; существуют некоторые стандартные методы подхода к этим задачам, разбирать которые мы здесь не будем) .

Хотя наше внимание будет почти полностью посвящено чисто математической стороне теории стратегических игр, по-видимому, все-таки, уместно начать с кратких заме­ чаний об истории экономики. Эти замечания помогут убедиться в том, что теория игр не совсем вздорна, ибо купля и продажа обычно считаются более серьезными и почтенными занятиями, чем игра в покер или даже в шахматы .

В своей науке экономисты в течение многих десятиле­ тий принимали за образец положение Робинзона Крузо, выброшенного на необитаемый остров и стремящегося поступать так, чтобы получить максимум возможных благ от природы. Считалось, что можно получить поня­ тие о поведении групп индивидуумов, начав с подроб­ ного анализа поведения индивидуума в этом простейшем возможном случае — случае одинокого индивидуума, бо­ рющегося с природой. Однако этот подход к экономиче­ ским вопросам имеет тот недостаток, что при переходе от общества из одного человека даже к обществу из двух человек возникают качественно различные положения, которые вряд ли можно предвидеть из рассмотрения пове­ дения одиночки*). В обществе, состоящем из двух чле­ нов, может оказаться, что каждый из них хочет иметь некоторый продукт (запасы которого недостаточны для обоих) и управлять хотя бы некоторыми факторами, опре­ деляющими распределение этого продукта. Тогда пове­ дение каждого, если оно разумно, должно определиться с учетом предполагаемого поведения другого. Такого положения не может быть для одного человека, так как он просто стремится к тому, чтобы получить максималь­ *) Это равносильно тому, как если бы мы пытались изучить природу окружностей путем изучения точек, представляющих, в конце концов, один из видов окружностей — окружности нуле­ вого радиуса. Обычные окружности слишком радикально отли­ чаются от окружностей нулевого радиуса, чтобы можно было использовать такой подход .

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

В обществе, состоящем из двух или нескольких чле­ нов, появляются совершенно новые проблемы, которые коренным образом отличаются от всего того, что мы нахо­ дим в обществе, состоящем из одного человека. По этой причине свойства обычного человеческого общества нельзя определить путем простого распространения на него свойств общества, состоящего из одного Робинзона Крузо .

Рассуждения подобного рода и привели двадцать лет назад математика Джона фон Неймана к убеждению, что экономику лучше всего изучать посредством аналогии с салонными (стратегическими) играми, чем посредством простой аналогии с аналитической задачей нахождения максимумов и минимумов. Этот подход к экономике в на­ стоящий момент исследован довольно основательно как математиками, так и экономистами. В библиографии в конце книги можно найти ссылки на соответствующие книги и статьи* .

(В связи с вопросом об определении экономических законов общества, состоящего из п членов, с помощью законов общества, состоящего из одного человека, можно заметить, что, как это ни парадоксально, этот способ дает лучшее приближение, когда п велико * чем в том случае, когда п мало, но больше единицы. Действительно, если у Смита один конкурент, то он должен учитывать вполне реальную возможность того, что этот конкурент будет поступать разумно (то есть будет пытаться опре­ делить, что собирается сделать Смит, и соответственно этому строить свое поведение). Если же Смит имеет не­ много конкурентов, он не должен упускать из вида, что все они могут поступать разумно или могут вступить в союз п р в« в -н его и, таким образом, поступать так, как если бы это был один человек. Но когда п становится очень большим, вероятность того, что большая часть конкурентов Смита будет поступать разумно, очень мала, так как выгода, которую они могут получить от союза против него, становится ничтожной. Поэтому Смит с пол­ ным основанием может предполагать, что среднее пове­ дение остального населения определяется, например, господствующими суевериями и заблуждениями или сред­ ним умственным уровнем, и может доверять своим пред­ видениям поведения конкурентов, например предвиде­ нию, основанному на их прошлом поведении, и рассма­ тривать остальное человечество как часть природы. Но стороннику экономического учения Робинзона Крузо не следует слишком обольщаться по поводу этого малень­ кого парадокса; он должен подумать о том, что в совре­ менном обществе люди стремятся объединиться в не­ сколько больших коалиций, корпораций, кооперативов, профессиональных союзов и тому подобное, которые во многих отношениях поступают подобно отдельным чело­ веческим индивидуумам.) Наконец, нужно упомянуть, что теория стратегиче­ ских игр может найти приложение в таких областях, которые обычно не считаются относящимися к эконо­ мике, например при решении вопросов, связанных с уха­ живанием и браком, когда необязательно имеется в виду денежная выгода, или в задачах, возникающих при выбо­ рах в парламент, когда баллотироваться могут несколько человек. Возможно', что эта теория может пролить свет на все виды ситуаций, в которых участвуют люди, имею­ щие противоположные цели, причем каждый из них хотя, возможно, и оказывает некоторое влияние на тече­ ние событий, но полностью не может им управлять .

2. Терминология и классификация игр Мы будем применять слово «игра» для обозначения некоторого набора правил и соглашений, составляющих данный вид игры, например шахматы, и будем употреб­ лять слово «партия» для обозначения возможной реали­ зации этих правил .

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

Существует огромное число всевозможных стратегиче­ ских игр. Рассмотрим некоторые способы их классификации .

Во-первых, мы различаем игры по числу игроков:

игра одного лица, игра двух лиц и др. Например, пась­ янс — игра одного лица, шахматы — игра двух лиц .

Когда мы говорим «игра п лиц», мы не обязательно под­ разумеваем, что в каждой партии игры участвуют п чело­ век, просто согласно правилам игры игроки распадаются на п непересекающихся множеств таким образом, что игроки, входящие в каждое множество, имеют одинако­ вые интересы. Эти п множеств людей с одинаковыми интересами называются «лицами» (так же, как в судеб­ ном деле корпорация считается лицом). Например, хотя в шахматы обычно играют два игрока, в них также могут играть две «команды», каж дая из трех человек; но и в этом случае игра все же будет игрой двух, а не шести лиц .

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

При игре в общественные игры игроки иногда решают, что в конце партии они произведут между собой денеж­ ные платежи так, как определено правилами щгры. Так почти всегда поступают в совершенно случайных играх, например при игре в кости (так как иначе не будет заин­ тересованности), в покере и часто в бридже. В других случаях игроки ведут счет очков и в конце партии нахо­ дят числа, измеряющие относительное умение, проявлен­ ное участниками игры, но никаких денег не выплачи­ вают, так часто поступают при игре в бридж. Наконец, в некоторых случаях не подсчитывают никаких очков, а просто объявляют, кто «выиграл» и кто «проиграл»;

так обычно делают, например, при играх в тик-так-ту* ), шашки и шахматы. Однако нам удобно пренебречь вто­ *) Tick~4aclc-toe — детская игра, состоящая в том, чтобы с закрытыми глазами попасть на одно из чисел, написанных на грифельной доске. (Прим. перев.) рым и третьим вариантом и говорить об игре так, как будто во все игры играют ради денег; таким образом, мы будем обычно говорить о «платежах», производимых между игроками в конце партии, и будем представлять эти платежи как денежные суммы. (Предположение о н а­ личии денежных платежей может показаться ограничением поля нашего исследования, однако это не верно:

если даже деньги не переходят из рук в руки, игроки получают от своих относительных очков какое-то удовле­ творение или огорчение, и таким образом можно было бы установить денежную ценность испытываемых ими ощу­ щений, следовательно, игру можно представить себе так, как будто она ведется ради этих эквивалентных денежных сумм. Мы не будем здесь вдаваться в эти вопросы, которые скорее относятся к области экономической науки или философии, чем к математике.) Предположим, что мы рассматриваем партию п лиц с игроками Р х, Р 2,..., Р п, и пусть p t (г= И,..., п) — пла­ теж игроку Р { в конце партии (если Р { сам должен пла­ тить, то р { отрицательно). Если при этом

2 Рг = о, г—1

то мы называем партию партией с нулевой суммой. Если любая возможная партия некоторой игры имеет нулевую сумму, то и саму игру мы называем игрой с нулевой сум­ мой *). Ясно, что все обычные салонные игры, в которых игра ведется на деньги, есть игры с нулевой суммой, так как в процессе игры сумма взносов всех игроков не воз­ растает и не уменьшается. Игры с ненулевой суммой дают нам возможность изучать при помощи теории игр модели экономических процессов, так как экономические про­ цессы обычно создают (или уничтожают) богатство. Может даже случиться, что экономический процесс увеличивает или уменьшает богатство каждого из его участников .

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

Например, тик-так-ту, если играть до самого конца, имеет девять ходов, из которых пять делает один игрок *) Более широкое определение «игры с нулевой суммой» будет ано в главе VI после введение понятия стратегии .

\

–  –  –

L / о том, какой выбор сделал первый игрок, выбирает чДсло из первых п положительных чисел. Затем эти два числа сравниваются, и один из игроков платит другому сумму, которая зависит от сделанных выборов и определяется правилами игры. Чтобы иметь какое-нибудь обозначение для таких игр, мы будем называть их прямоугольными играми. (Позднее мы увидим, что прямоугольные игры не составляют обособленного класса игр, как может показаться с первого взгляда: множество других весьма разнообразных игр можно привести к форме прямо­ угольных игр.) Приведем пример прямоугольной игры. Игрок Р г выбирает число из множества {1, 2, 3}, а игрок Р 2 выбирает число из множества {1, 2, 3, 4}, не будучи информирован о том, какой выбор сделал Р После того как * ^ выборы были сделаны, игрок Р 2 платит игроку Р г сумму, определяемую следующей таблицей: **

–  –  –

—1 —5 Иначе говоря, если Р 19 например, выбирает 1, а Р 2 выби­ рает 3, то игрок Р 2 платит игроку Р г десять долларов (или десять центов, или десять любых других денежных единиц). Если Р 1 выбирает 3, а Р 2 выбирает 2, то игрок Р 2 платит игроку Р г минус пять долларов, т. е. игрок Р х пла­ тит игроку Рг пять долларов. Мы будем описывать впредь такую игру, указывая просто ее платежную матрицу

–  –  –

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

Оказывается, что в случае первого примера на этот вопрос очень легко ответить. Действительно, мы заме­ чаем, что каждый элемент первой строки больше соответ­ ствующего элемента второй строки и также больше соот­ ветствующего элемента третьей строки. Следовательно, независимо от того, какое число выбирает Р 2, для Р г лучше выбрать 1, чем 2 или 3, так что оптимальный способ игры для Р г — это выбрать 1. Точно так же каждый элемент второго столбца меньше соответствующего эле­ мента каждого из других столбцов; поэтому посколь­ ку Р 2 хочет играть таким образом, чтобы платеж был возможно меньшим, оптимальный способ игры для Р 2 — выбрать 2 .

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

–  –  –

имеет седловую точку || 2 3 ||, так как 4 является мини­ мумом второй строки и максимумом третьего столбца .

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

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

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

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

–  –  –

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

У пражнения

1. Как вы считаете, экономика Робинзона Крузо приближается больше к британской экономике 1900 года или 1952 года? Почему?

2. Если А — множество действительных чисел, то нижней г р а ­ ницей множества А мы называем число у такое, что у ^ х для любого х A; точной нижней границей (или нижне й гранью) множества А мы называем такую нижнюю границу, которая не меньше, чем любая другая нижняя граница. Укаж ите пример множества, не имеющего нижней границы. Покажите, что никакое множество действительных чисел не может иметь больше одной точной нижней границы .

3. Определите верхнюю границу и точную верхнюю границу множества действительных чисел, аналогичные нижним границам и точным нижним границам, и докажите утверждения, аналогич­ ные утверждениям упражнения 2 .

4. Если / ( х ) — действительная функция, определенная на мно­ жестве А, то inf / (х)

–  –  –

Поскольку матрица не имеет седловой точки, наши прежние методы недостаточны, ^тобы позволить нам опре­ делить оптимальные способы игры для Р г и Р 2. Кроме того, безразлично, выберет ли Р г 1 или 2, так как в обоих случаях он получит 1 или — 1, если, соответ­ ственно, Р 2 сделает такой же или противоположный выбор .

С другой стороны, если Р 2 знает, какой выбор сделает Р то Р2 может поступить так, что Р г должен будет заплатить ему 1 (для этого он должен сделать противо­ положный выбор). Таким образом, оказывается, что для Рх весьма важно сделать так, чтобы Р 2 было трудно угадать, какой выбор он намеревается сделать. Один из способов, которым Рх может этого достичь, является слу­ чайный выбор .

Допустим, например, что Р г решает сделать свой вы­ бор путем бросания монеты, выбирая 1, если монета показывает герб, и выбирая 2, если она показывает решку. В этом случае, поскольку вероятность того, что Рх выберет 1, равна 1/ а и вероятность того, что он выбе­ рет 2, такая же, математическое ожидание выигрыша 3 Дж. Мак-Кинси 34 г л. II. ОСНОВНАЯ TEOPMA ДЛЯ ПРЯМОУГОЛЬНЫХ ИГР для Рг в случае, если Р 2 выбирает 1, равно і 'т+ ( и оно будет таким же, если Р г выберет 2. Следовательно, если Р г выбирает этим способом, то математическое ожи­ дание его выигрыша будет равно нулю, независимо от того, что предпринимает Р2 .

В действительности это единственный способ, кото­ рым Р х может играть в рассматриваемую игру, не под­ вергаясь риску проигрыша, даже в том случае, если Р 2 узнает, какой выбор он собирается сделать. Допустим, что Р г применяет метод случайного выбора, который определяет, что вероятность выбора 1 равна х и вероят­ ность выбора 2 равна 1 —, предположим, что Р2 знает, какой случайный механизм применяет Р Тогда матема­ тическое ожидание выигрыша игрока Р если Р2 выби­ рает 1, равно

1.Я5-НХ — 1) ( l - * ) = 2 & - l f и если Р 2 выбирает 2, математическое ожидание выиг­ рыша игрока Р г равно ( - 1 ) я + (1) ( 1 - я ) = 1 - 2 я .

А Если ж у, то 1 — 2а; 0, так что математическое ожидание выигрыша Р если Р2 выбирает 2, меньше нуля; и если х -і-, то 2х — 1 0, математическое ожи­ дание выигрыша Р если Р 2 выбирает 1, тоже меньше нуля .

Отсюда следует, что оптимальный вариант игры в эту игру для (и, по тем же причинам, для Р 2) — выбирать 1 или 2, каждое с вероятностью у. Цена игры для Р 1 (т. е. математическое ожидание его выигрыша, если он играет оптимальным способом) равна нулю .

В приведенных выше рассуждениях мы все время говорили об использовании случайных механизмов кото­ рые определяют вероятности различных выборов. Однако иногда интуитивно проще говорить об относительных частотах различных выборов. На следующих страницах

1. СМЕШАННЫЕ СТРАТЕГИИ мы часто будем употреблять этот менее точный способ выражения .

Рассмотрим теперь несколько более сложный пример:

прямоугольную игру с матрицей Поскольку матрица не имеет седловой точки, то, повидимому, для Р г и Р 2 желательно играть только с опре­ деленными частотами. Предположим, что jРг выбирает 1 с частотой X и 2 с частотой 1 — х (так что ни х, ни 1 — х не отрицательны), а Р 2 выбирает 1 с частотой у и 2 с частотой 1 — у. Тогда математическое ожидание выиг­ рыша для Р г равно Е (X, у) = 1х у + Ъх (1 — у) + 4 (1 — х) у + 2 (1 - х) (1 — у) .

Перед нами возникает задача — придать точный матема­ тический смысл интуитивному понятию оптимального вы­ бора величины X (для Рг) и оптимального выбора вели­ чины у (для Р 2) .

Выполняя элементарные алгебраические преобразова­ ния, получим у )= ~-4яг/ + я + 2 г / + 2 = ( 1) + =

–  –  –

причем числа можно рассматривать как частоты, с ко­ торыми Р г выбирает числа 1, 2, т. Будем впредь употреблять символ Sm для обозначения этого множества m-мерных векторов (смешанных стратегий) .

Аналогично, смешанной стратегией для Р 2 мы будем называть элемент множества Sn, т. е. упорядоченную систему неотрицательных действительных чисел || у х... уп |j, удовлетворяющих условию і=і Иногда мы будем называть сами числа 1,..., т чистыми стратегиями игрока Р а числа 1,..., п — чистыми стратегиями игрока Р2. Очевидно, что для Р г игра с чистой стратегией к эквивалентна игре со сме­ шанной стратегией || х 1... хт ||, где = 1 и х { = 0 для і ф к .

Если Р г применяет смешанную стратегию X = || х г... хт |, а Р 2 применяет смешанную стратегию У = || у г... у п |, то математическое ожидание выигрыша для Р г опреде­ ляется формулой п т E ( X, Y ) = 2 S аііх іУі .

j—\ i=l Если оказывается, что для некоторого X* Sm и неко­ торого У* Sn и для всех X и всех У Sn Е (X, У*) Е (X*, У*) Е (X*, У), (3) то мы называем X* и У* оптимальными смешанными стратегиями для P L и Р 2, а Е(Х* У*) — ценой игры для Р Если X* и У * — оптимальные стратегии соот­ г ветственно для Р. и Р 2, то мы называем иногда упоря­ доченную пару |] X*, У* II решением игры или страте­ гической седловой точкой .

Интуитивная адекватность вышеизложенных опреде­ лений заключается в следующем. Если X* и У* —сме­ тан н ы е стратегии, удовлетворяющие условию (3), то, п р и м е н я я с ь !, Р± может гарантировать себе, что он получит по меньшей мере І?(Х*, У*), независимо от того, как поступит Р 2. Аналогично, используя У*, Р 2 может не дать Р г получить больше чем Е ( Х *, У *). Итак, Е ( Х *, У*) представляет ту сумму, которую Р г может надеяться получить — он может получить ее, выбирая X*, а Р 2 может ограничить его этой суммой, выбирая У* .

Если две величины л = m ax m in Е (X, У) xesm r s n и ' v2 = min max E (X y Y) Y&n X&m существуют и равны между собой, то на основании тео­ ремы 1.5 существуют сметанны е стратегии, удовлетво­ ряющие условию (3), так что игра имеет цену и имеются оптимальные стратегии для обоих игроков. Таким обра­ зом, вопрос о существовании г и 2 и равенстве их между собой является очень важным. В § 3 мы пока­ жем, что они всегда существуют и равны между собой, и, следовательно, определений этого параграфа доста­ точно для того, чтобы найти цену произвольной прямо­ угольной игры и ее оптимальные стратегии. Прежде чем обратиться к доказательству этого положения, удобно ввести некоторые геометрические понятия и теоремы, которые понадобятся нам в дальнейшем .

–  –  –

Легко доказать, что необходимым и достаточным условием ограниченности множества является нахождение его в некоторой гиперсфере, т. е. существование точки а множества Еп и числа R таких, что для всякого x X d (x, Назовем точку х пространства Еп предельной тонкой подмножества А из Еп, если для всякого положитель­ ного 8 существует точка A, отличная от х и /т а к а я, что d (я, у) е. ух Т ак, если А есть множество точек \\х у у. простран­ ства Е 2, для которых У х 2 + У2 1, то любая точка ||0 у 0\\, для которой выполняется ра­ венство * ;+ » ! - 1 .

есть предельная точка множества А. Следует обратить внимание, что конечное множество точек не имеет пре­ дельных точек: С другой стороны, всякое ограниченное бесконечное множество точек имеет по меньшей мере одну предельную точку .

Замыканием множества называется множество, полу­ ченное путем добавления к данному множеству всех его предельных точек. Т ак, замыкание множества А упомя­ нутых выше точек есть множество точек \\х у || простран­ ства Е2, таких, что r2 + 2 l .

Конечное множество совпадает со своим замыканием .

Множество называется замкнутым, если оно совпадает со своим замыканием. Таким образом, всякое конечное множество замкнуто, так же как, например, множество, состоящее из всех точек \\х, у\\ пространства Е2, для которых х 2 + у2 1 .

Множ№аа~называется открытым, если его дополнение замкнуто. Так, множество А, упомянутое выше, откры­ то. Некотррые множества не являются ни открытыми, ни замкнутыми. Множество точек х пространства для которых 0 1, не открыто и не замкнуто .

В нут ренняя часть множества есть дополнение замы* кания его дополнения. Следовательно, внутренней частью множества точек х пространства Е2, для которых 0 я 1, является множество точек х пространства Ех, таких, что 0 я 1. Внутренней частью любого конеч­ ного множества является пустое множество. Легко ви­ деть, что замыкание любого множества замкнуто и внутренняя часть любого множества открыта. Дополне­ ние любого замкнутого множества открыто, а дополне­ ние любого открытого множества замкнуто .

Множество Еп для любого п открыто и замкнуто, и то же справедливо для пустого множества; это един­ ственные множества, которые и открыты, и замкнуты .

Границей множества мы называем пересечение его замыкания с замыканием его дополнения. Так, границей упомянутого выше множества А является множество всех точек \\х у || пространства Е2, таких, что х 2 + у 2 = 1 .

Если В есть множество всех точек \\х у || простран­ ства Е2, таких, что x и у суть рациональные числа, то граница множества есть все пространство Е2 .

Множество называется связным, если его нельзя представить в виде суммы двух непересекающихся мно­ жеств, ни одно из которых не содержит предельной точки другого. Т ак, упомянутое выше множество А — связное; то же справедливо, например, для множества всех точек \\х у z\\ пространства Е3, для которых Зх + 2у + 5z = 7 .

Если С есть множество всех точек \\х у || простран­ ства Е2, для которых x Ф 0, то множество С не связное;

действительно, если С1 есть множество всех точек | х у |, для которых x 0, и С2 есть множество всех точек j x у |, для которых x 0, то С есть сумма множеств Сг и С2, и ни одно из множеств С3 и С2 не содержит предель­ ной точки другого .

Помимо этих общих понятий, мы используем также более специальные понятия, относящиеся к евклидову про­ странству. Эти понятия связаны с теорией выпуклых множеств, которая сама по себе представляет хорошо разработанную, весьма специальную область матема­ тики; мы дадим здесь лишь основы этой дисциплины и ограничимся теми положениями, которые будут по­ лезны в связи с теорией игр .

Пусть

–  –  –

является вся плоскость Е2 .

Поскольку пространство Еп выпуклое, очевидно, лю­ бое множество содержится по меньшей мере в одном выпуклом множестве, и, следовательно, любое множе­ ство имеет выпуклую оболочку. Нетрудно показать, что выпуклая оболочка множества X состоит как раз из тех точек, которые являются выпуклыми линейными комби­ нациями точек множества X. В этом разделе мы не бу­ дем приводить ни одного доказательства, так как теория выпуклых множеств представляет лишь математический подготовительный аппарат к теории игр. Теорема Френ­ келя, которую мы здесь приводим, не будет использо­ вана в этой главе, на она нам будёт необходима позднее при доказательстве теоремы И. 5 .

Т е о р е м а 2.1 .

Если X есть некоторое подмноже­ ство пространства Е п, то любая точка выпуклой обо­ лочки подмножества X может быть представлена как выпуклая линейная комбинация п + 1 точек из X. Е сли, кроме того, подмножество X связно, то любая точка выпуклой оболочки подмножества X может быть пред­ ставлена как выпуклая линейная комбинация п точек X .

З а м е ч а н и е 2.2. Для пояснения теоремы допустим, что X состоит из четырех точек ||0 0 ||, (|0 1 1|, || 1 1 1 | и II1 О Л пространства Е2, то есть X состоит из четырех вершин квадрата (рис. 1). Тогда выпуклой оболоч­ кой X, очевидно, является весь квадрат, включая его границу. Каждую точку треугольника abd можно представить как выпуклую линейную комбинацию трех точек а, Ъ и d и аналогично любую точку треуголь­ ника bed можно представить как выпуклую линейную I1 1 комбинаі^ию^трех точек 6, с и d. Точка I, не на­ ходящаяся ни на границе квадрата, ни на одной из диагоналей ас и bd, не может быть представлена как 44 г л. II. ОСНОВНАЯ т е о р е м а д л я п р я м о у г о л ь н ы х и г р

–  –  –

4. Свойства оптимальных стратегий Иногда можно определить цену игры из интуитивных соображений или из непосредственного рассмотрения игры. В таких случаях для отыскания оптимальных стратегий для обоіих игроков часто бывает удобно поль­ зоваться следующей теоремой .

Т е о р е м а 2.8 .

Пусть Е — математическое ожида­ ние выигрыша в прямоугольной игре с матрицей порядка т Х п, имеющей цену. Тогда, для того чтобы элемент множества Sm был оптимальной стратегией для Р г, r* необходимо и достаточно, чтобы для каждого элемента У множества Sn имело место неравенство Е ( Х * У) .

Аналогично, для того чтобы элемент У* множества Sn был оптимальной стратегией для Р 2, необходимо и достаточно, чтобы для всякого элемента X множест­ ва Sm имело место неравенство Е ( Х, У*) v .

4. СВОЙСТВА ОПТИМАЛЬНЫХ СТРАТЕГИЙ

–  –  –

5. Соотношения превосходства Как мы видели в разделе 3 главы I, иногда на осно­ вании простого рассмотрения матрицы прямоугольной игры можнд^а&дазать, что некоторые чистые стратегии могут войти в оптимальные смешанные стратегии лишь с нулевой вероятностью. Так, например, если 62 7 (34) —матрица прямоугольной игры, то, как подсказывают ин­ туитивные соображения, ни при какой оптимальной стра­ тегии игрока Р і не следует приписывать положительную вероятность третьей строке, ибо, что бы ни делал Р 2, для Р г лучше выбирать вторую строку, чем третью строку. Таким образом, оказывается, что для решения этой игры нам достаточно найти решение игры с матрицей (35) Цены обеих игр должны быть одинаковы; Р2 должен иметь в обеих играх одинаковые оптимальные стратегии .

Если У х2 II есть оптимальная стратегия для Рг во вто­ рой игре, то оптимальная стратегия для Р г в первой игре будет \\х1 х2 0|| .

Поскольку каждый элемент первого столбца матрицы (35) меньше соответствующего элемента третьего столбца, и поскольку Р 2 хочет свести платеж к минимуму, то мы можем вычеркнуть третий столбец матрицы (35) и полу­ чить матрицу 4 1 7 (36)

–  –  –

5 fO + f.8, и, следовательно, для Р г будет неразумно ставить на третью строку, он поступит лучше, разделив между пер­ выми двумя строками (в отношении 1 к 3) вероятность, которую он мог бы приписать третьей строке. В этом случае мы опять можем найти цену и оптимальные стра­ тегии, решая игру с матрицей 24 О О8 Поскольку цена последней игры равна 6 и поскольку есть оптимальная стратегия для каждого игрока, мы заключаем, что игра, имеющая матрицу (37), также имеет цену, равную б, ^ ^ 0 есть оптимальная стратегия для Р х и -J -г 0 есть оптимальная ' стратегия для Р 2 .

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

Если а = у ах... ап || и b = || Ьг...'Ьп || есть векторы (или строки, или столбцы матрицы) и если а{ Ь{ ( = 1,..., п), то мы говорим, что а превосходит Ъ ;

если аі 'Ъі (і==1,..., ri), мы говорим, что а строго превосходит Ъ. Оба эти соотношения транзитивны: если а превосходит Ъ и Ъ превосходит с, то а превосходит с, и такое же соотношение имеет место для строгого пре­ восходства. Мы замечаем также, что соотношение пре­ восходства рефлексивно, так что всякая величина превос­ ходит сама себя, а соотношение строгого превосходства нерефлексивно, так что никакая величина строго не пре­ восходит сама себя. Однако, применяя эти понятия, всегда нужно иметь в виду, что когда два вектора раз­ личны, из этого не следует, что один из них обязательно превосходит другой: например, это видно на векторах ||1 2 II и II2 1 || .

Введем также понятие расширения смешанной стра­ тегии на і-м месте. Если х = \\хг... хп \\ есть элемент множества Sn и 1 л + 1, то расширением элемента X на і-м месте называется вектор \\х... хі_10 х і... хп \\ .

Так, расширением элемента 10 6 10 Iна 2‘м месте яв‘ ляется вектор і. и — — 0 расширением на 1-м месте является вектор 0 10 10 10 ; расширением на 4-м ІІІ0 Очевидно, если х есть месте —вектор 10 10 10 какой-либо элемент множества Sn, то всякое расшире­ ние элемента х на і-м месте является элементом мно­ жества Sn+1 .

Т е о р е м а 2.16 .

Пусть Г — прямоугольная игра с матрицей А. Предположим, что і-ю строку матрицы А для некоторого і превосходит некоторая выпуклая линейнал комбинация других строк матрицы А; пусть A' — матрица, получающаяся из А после исключения і-й строки, и пусть Г' —прямоугольная игра, матрица которой есть А \ Тогда цена игры I ' —такая ж е, как цена игры Г;

всякая оптимальная стратегия игрока Р 2 в Г' есть также оптимальная стратегия игрока Р2 в Г; если w — любая оптимальная стратегия игрока Р\ в Г' и х —расшире­ ние стратегии w на і-м месте, то х есть оптималь­ ная стратегия игрока Р г в Г. Далее, если і-ю строку матрицы А строго ' превосходит выпуклая линейная ком­ бинация других строк матрицы А, то любое решение игры Г можно получить указанным способом из реше­ ния игры Г' .

Доказательство. Пусть

–  –  –

Пусть V — цена игры Г ', w = || w 1... wm | —оптимальная стратегия игрока Р г в Г' и г/ = | г/х... г/п || — оптимальная стратегия игрока в Г'. Тогда* по тео­ реме 2.9

–  –  –

Следовательно, из теоремы 2.12 вытекает, что у всякой оптимальной стратегии игрока Р г в Г тгг-я компонента будет равна нулю .

Доказательство следуйлцей теоремы аналогично, и мы его опустим .

Т е о р е м а 2.17 .

Пусть Y —прямоугольная игра с матрицей А. Предположим, что і-й столбец матрицы А для некоторого / превосходит некоторую выпуклую линейную комбинацию других столбцов матрицы А\ пусть — матрица, получающаяся из А после исключения /-го столбца, и пусть Г' — прямоугольная игра с матрицей А' .

Тогда цена игры Г' такая же, как цена игры Г; всякая оптимальная стратегия игрока Р х в Г' есть также оптимальная стратегия игрока Р г в Г; если z —любая оптимальная стратегия игрока Р2 в Г и у —расширение стратегии z на f -м месте, то у есть оптимальная стратегия игрока. Р 2 в Г. Далее, если j -й столбец матрицы А строго превосходит выпуклую линейную ком­ бинацию других столбцов матрицы, то любое решение игры Г можно получить этим способом из решения игры Г' .

Приведем несколько более сложный пример примене­ ния этих теорем .

П р и м е р 2.18 .

Дана следующая платежная матрица прямоугольной игры:

3 4Так как третья строка матрицы превосходит первую, то, вычеркивая первую строку,, мы получаем:

В новой матрице первый столбец превосходит третий;

вычеркивая первый столбец, мы получаем:

В этой матрице никакая строка (и никакой столбец) не превосходит другие строки (и столбцы); по первый столбец ifpwtjcходит выпуклую линейную комбинацию второго и третьего столбцов, потому что 4 1.2 + 1.4, .

2 ~ Г 4 + Т*0* 4 = 1. ° + і-.8 .

–  –  –

В свою очередь в этой матрице выпуклая линейная ком­ бинация второй и третьей строк превосходит первую строку, так как 2=4. 4 + -І.0,

–  –  –

Цена игры с этой матрицей равна у, а оптимальная стратегия для первого игрока (и для второго игрока) будет равна у у. Следовательно, поскольку мы полу­ чили матрицу 2 x 2 из первоначальной матрицы 4 x 4 путем вычеркивания первых двух строк и первых двух столбцов, мы заключаем, что оптимальная стратегия для первого игрока (и для второго игрока) в первоначальной 2 1I игре будет О О у у .

З а м е ч а н и е 2.19. Из теорем 2.16 и 2.17 можно заметить, что когда мы вычеркиваем строку (или стол­ бец), которая строго превосходит что-либо, мы получаем матрицу, которая приводит к точно такой же системе решений, которая получилась бы при решении перво­ начальной игры. Однако это не имеет места, когда соот­ ношение превосходства не является строгим; в этом слу­ чае мы можем «потерять» некоторые из решений перво­ начальной матрицы, В качестве примера рассмотрим игру с платежной матрицей 0 -1

-1 Легко убедиться, что любой элемент множества S3 вида II а ЪЬ]| будет оптимальной стратегией для Р г. С дру­ гой стороны, если мы вычеркнем первую строку (кото­ рую превосходит, но не строго, выпуклая линейная ком­ бинация двух других строк) и затем вычеркнем первый столбец, мы получим матрицу 1 -1

-1 1

–  –  –

В этом разделе мы опишем графический метод нахо­ ждения решений прямоугольной игры. Этот метод очень просто применять к играм, имеющим матрицы 2 х п или т х 2. Его можно также применять (тому, кто умеет чертить трехмерные диаграммы) к играм, имеющим матрицы 3 X гг и т х 3; но он непригоден для матриц т х п, когда т и п больше 3. Мы поясним этот метод на нескольких ярщ ерах решения игр 2 х П р и м р. 2.20. Рассмотрим игру с платежной матрицей

–  –  –

Здесь под номерами і 1 1 и т. д. подразу­ меваются различные стратегии обоих игроков. Если Р л применяет смещанную стратегию || x 1 —х ||, а Р 2— чистую стратегию [ jN, то ожидаемый платеж игроку Р, будет

–  –  –

Далее, из рисунка видно, что стратегия (_lj не войдет % оптимальную смешанную стратегию игрока Р 2. Следо­ в вательно, мы можем найти оптимальную стратегию для Р 2 при помощи матрицы 3И ^гак что оптимальная стратегия для Р2 равна oll И 11 З а м е ч а н и е 2.21. Пена игры в приведенном выше примере находится следующим образом:' берем макси­ мальную ординату выпуклого множества, которое огра­ ничено сверху прямыми линиями. Такой же способ при­ меняется для любой игры с матрицей порядка 2 х я .

Для игры с матрицей порядка m X 2 графическое построе­ ние, очевидно, аналогично, но в этом случае цена игры равна минимальной ординате выпуклого множества, огра­ ниченного снизу прямыми линиями .

Перейдем«я«*внеръ к примеру, когда Р 1 имеет много оптимальных стратегий .

П р и м е р 2.22 .

Рассмотрим игру с платежной матрицей 24 И 74 2[ Обозначив стратегии, как в примере 2.20, и проведя соответствующие прямые, как в предыдущем примере, мы получим рис. 3 .

У'

О Рис* 3*

Из рис. 3 видно, что цена игры равна 4 и что любое x, удовлетворяющее условию 0 ^ 1 л : 0 Л 2, будет оптимальным для Р Решая совместно уравнения | 2 [ ~2, находим соответственно, что ОАг = -g-, а ОЛ2 = у. Итак, оптимальной стратегией для Д является любая пара \\х'і — х\\, г д е - д - ж у. Оптимальная стра­ тегия для Р 2 в этой игре равна || 0 1 0|| .

З а м е ч а н и е 2.23. В примере 2.22 мы нашли, что множество оптимальных смешанных стратегий игрока Рг состоит из точек прямолинейного отрезка; очевидно, это всегда будет иметь место для игры 2 х п (хотя, конечно, отрезок может стянуться в одну точку, как в примере 2.20) .

Далее,- с полным основанием можно предположить, что для игры с матрицей порядка т х п множеством опти­ мальных стратегий каждого игрока будет естественное обобщение отрезка прямой в пространстве более высокой размерности, а именно выпуклая оболочка конечного множества точек (многогранник). Подробное доказатель­ ство этого читатель найдет в следующей главе .

Библиографические замечания Первое доказательство основной теоремы (теоремы 2.6) было дано фон Нейманом [88], это доказательство было основано на топологической теореме Брауэра о неподвиж­ ной точке; позднее Билль [109] дал элементарное дока­ зательство. В книге фон Неймана и Моргенштерна [92] было дано простое доказательство, основанное на теории выпуклых множеств; доказательство, приведенное выше, по существу есть доказательство, фон Неймана и Морген­ штерна. Другие доказательства этой теоремы или ее обобщения мо}кно найти у Боненблуста и Карлина [9], у Брауна и фон Неймана [19] и у Вейля [122] .

Для дальнейших сведений по теории выпуклых мно­ жеств рекомендуется обратиться к работам Глезермана и Понтрягина [46] или Боннезена и Фенхеля [12] .

У пражнения

1. Пусть А — множество всех точек пространства Е3, коорди­ наты которых ||a?t/z|| удовлетворяют условиям я2+ 2 2 2 4, ^—y + z 0 .

/2+ Найдите замыкание, внутреннюю часть и границу множества А .

2. Покажите, что всякое выпуклое множество является связ­ ным. Дайте пример связного множества, которое не является выпуклым .

3. Найдите экстремальное множество множества А, описан­ ного в упражнении 1 .

4. Постройте доказательство теоремы 2.3 или • найдите его в литературе .

5. Покажите, что теорема 2.3 не будет справедлива, если мы опустим условие, что X есть выпуклое множество .

6. Покажите, что теорема 2.3 не будет справедлива, если мы опустим условие, что X есть замкнутое множество .

7. Докажите теорему 2.3 для п = 2. (Указание: пусть у есть точка множества X, ближайшая к х ; рассмотрите прямую, прохо­ дящую через X и перпендикулярную к прямой, соединяющей х и у.) Затем попробуйте обобщить это доказательство так, чтобы уста­ новить справедливость теоремы для произвольного п .

8. Докайгите^-теорему 2.4 для частного случая, когда гра­ ница множества X не содержит прямолинейных отрезков .

9. Найдите цены прямоугольных игр, матрицы которых ука­ заны ниже, и найдите оптимальные стратегии для обоих игроков:

а) 2 0 1 t б) 31• в) 2

–  –  –

2. Некоторые свойства матриц В утверждениях и доказательствах следующих двух лемм мы будем широко пользоваться теорией матриц .

Обозначим через І п матрицу порядка п X п, каждый элемент главной диагонали которой равен 1, а все дру­ гие—нулю; например:

h = \ 111, '

–  –  –

Кроме того, очевидно, что равенство (8) непосредственно следует из равенства (11).

Чтобы установить справедли­ вость равенства (9), заметим, что из равенства (10) вы­ текает:

–  –  –

И, наконецг^ёвнюставляя последнее выражение и равен­ ство (12), получаем, что член в квадратных скобках в выражении (13) равен J r adj AJ'r .

3. Определение всех решений Л е м м а. 3.5. Пусть Г —прямоугольная игра, платежная матрица которой есть А, пусть (Т) — цена игры, и T2(Г). Тогда, для отличная от нуля, того чтобы Х ^ К [ Т г (Г)] ft У К [ Т 2(Г)], необходимо и достаточно, чтобы существовала невырожденная подмат­ рица В матрицы А такая, *шо (14)

–  –  –

Чтобы убедиться в достаточности нашего условия, пред­ положим, что имеется невырожденная матрица /?, удов­ летворяющая условиям (14), (15) и (16), и что при этом условия Х ^ К [ Т х(Г)] и У К [ Т 2(Г)] не выполняются одновременно, так что либо X К [Т г (Г)]* либо У f К [Т2 (Г)] .

Покажем, что предположение, будто -X f К [Тг (Г)], при­ T водит к противоречию; доказательство противоречивости предположения У f К [Т2 (Г)] аналогично .

Поскольку задача определения решений игры не ме­ няется существенно при перестановке строк или столб­ цов, мы можем, не нарушая общности, положить, что В находится в левом верхнем углу матрицы А, то есть что а 11... alr

–  –  –

то Х ? К [ Т 1(Г)], что противоречит условию. Отсюда за­ ключаем, что матрица В невырожденная, что и требова­ лось д о к а з а т ь Для завершения доказательства остается проверить выполнение для В равенств (14), (15) и (16). Поскольку матрица В невырожденная, s = t\ положим r = s = J, тогда а11 • '• а1г

–  –  –

где X есть вектор, полученный из X путем вычеркива­ ния элементов, соответствующих вычеркнутым строкам при образовании В из A, a Y есть вектор, получен­ ный из Y путем вычеркивания элементов, соответ­ ствующих вычеркнутым столбцам при образовании В из А .

Д о к а з а т е л ь с т в о. Для р ( Г ) ^ 0 теорему легко вывести из леммы 3.5, если вспомнить, что для невырож­ денной матрицы В в - г _ adjJS

–  –  –

где II II — произвольный элемент множества S2. Цена игры равна 1 .

З а м е ч а н и е 3.12. Следует отметить, что метод ре­ шения прямоугольных игр, изложенный в этой главе, хотя и весьма прозрачен (и, конечно, более эффективен, чем трудоемкий метод, указанный в главе II), все же приводит к громоздким вычислениям для игр с большими платежными матрицами, ибо число квадратных подмат­ риц, имеющихся у матриц высокого порядка, само очень велико, и поэтому чрезвычайно утомительно вычислять присоединенную матрицу квадратной матрицы высокого порядка. Число арифметических операций, необходимых при этом способе, так быстро возрастает с повышением порядка матрицы, что представляется мало вероятным применение даже современных электронных вычислитель­ ных машин для решения игр порядка, скажем, 100 х 100 .

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

Предположим, что когда первый игрок выбирает сме­ шанную стратегию X, а второй —чистую стратегию /, математическое ожидание выигрыша первого игрока равно Е (X, /) .

Мы говорим, что сметанная стратегия X превосходит смешанную стратегию X ', если для каждой чистой стра­ тегии / игрока Р2 (Х,/)(Х',/), и существует по меньшей мере одна стратегия / игрока Р 2 такая, что Е ( Х, ] ' ) Е ( Х ', у) .

Мы называем стратегию X наилучшей, если она опти­ мальна и никакая другая стратегия не превосходит ее .

Аналогично определяются соотношения превосходства и наилучшие стратегии для Р2 .

Интуитивное обоснование этих определений заключает­ ся в том, что если X превосходит X ', то, независимо от того, как решает поступить игрок Р 2, Р 1 заведомо посту­ пит не хуже при использовании X, чем при использова­ нии X '. Далее, если Р 2 делает какие-то ошибки, для Рг лучше применять X, чем X '. Итак, стратегия X по­ зволяет лучше, чем X ', использовать возможные ошибки противника. Поэтому игрок может вполне выбрать стра­ тегию из класса «наилучших». Легко показать, что во всякой прямоугольной игре существуют наилучшие стра­ тегии. Доказательство этого мы оставляем в качестве упражнения .

П р и м е р 3.14 .

Рассмотрим игру с платежной матрицей 25 6* Поскольку каждый из элементов первого столбца яв­ ляется седловой точкой, то любая смешанная стратегия первого игрока оптимальна .

Если Р г применяет стратегию Ц^АІІ» то математиче­ ское ожидание его выигрыша в зависимости от того, какой столбец выбирает Р2, будет:

Е ( II хг х2||. 1) = 2хг + 2х2 = 2,,,(|| хх х21, 2) •= 3#j Ъх2, 1 = Е { \\хг зс2\\, 3) = 4х1+ 6х2 .

В частности, Е ( ||0 l | | f l ) « 2, Е ( \ \ 0 1 1|, 2) = 5, Е ( II 0 1 ||f 3) = 6 .

Поскольку для всех ||х 2 х2\\ из S2 2 2, 5 ^ 3^2 ~ 5х2 j~ 6 4 ^ - f 6х2, мы заключаем, что ||0 1 1 есть единственная наилучшая | стратегия для Р Для Р 2 имеется лишь одна оптимальная стратегия, а именно || 1 0 0||, и, следовательно, также лишь одна наилучшая стратегия .

Библиографические замечания Материал этой главы был взят в основном из работы Щепли и Сноу [101]. С задачей, которой мы здесь зани­ маемся, Т&вню связана такая задача: найти условия, которым должны удовлетворять два множества X и Y для того, чтобы для некоторой прямоугольной игры имели место равенства Х ^ Т ^ Г ) и У = Т 2(Г). Эта задача ре­ шена в работе Боненблуста, Карлина и Шепли [10] и в работе Гейла и Шермана [42] .

Полную теорию можно найти в книгах Бохера [8] и Мак-Даффи [68]*) .

У пражнения

–  –  –

Сетевая игра определяется следующим образом: имеются п 9 .

точек; некоторые пары этих точек соединены стрелками, как пока­ зано на рис. 4. Оба игрока одновременно выбирают по точке; если они выбирают одну и ту же точку или разные, но не соединенные .

–  –  –

стрелкой, платеж равен нулю: если они выбирают связную пару точек, то игрок, выбравший острие стрелки, получает от своего противника 1 .

Решите сетевую игру, соответствующую рис. 5 .

10. Решите сетевую игру (см. предыдущий пример), соответ­ ствующую р и с ^ и рис. 7 .

11. Найдите наилучшую стратегию для каждого игрока в пря­ моугольной игре, имеющей матрицу —1

12. Покажите, что каждый игрок во всякой прямоугольной игре имеет по меньшей мере одну наилучшую стратегию .

13. Покажите, что множество наилучших стратегий данного игрока замкнуто .

МЕТОД ПРИБЛИЖЕННОГО ОПРЕДЕЛЕНИЯ

ЦЕНЫ ИГРЫ В этой главе мы изложим метод приближенного реше­ ния прямоугольной игры, который позволит нам нахо­ дить цену и оптимальные стратегии с какой угодно сте­ пенью точности. Затрата труда при использовании этого метода растет, грубо говоря, пропорционально числу строк и столбцов матрицы, так что для игры с очень боль­ шой матрицей этот способ значительно быстрее позволит найти решение игры, чем точный метод, описанный в гла­ ве III. Мы не будем доказывать, что указанный метод действительно приводит к приближенному решению, по­ скольку этот вопрос довольно специален .

Описываемый нами приближенный метод основан на следующих интуитивных соображениях. Допустим, что два человека играют ряд; партий данной игры, причем пи один из них не знает оптимальной стратегии (возможно, потому, что они не знают теории игры или потому, что матрица игры слишком велика, чтобы они смогли про­ извести необходимые вычисления), тогда может слу­ читься, что каждый из них решает вести себя так, как если бы он имел дело с неодушевленным предметом, а не с разумным противником, то есть играть таким обра­ зом, чтобы максимально увеличить свой выигрыш, пред­ полагая, что «будущее будет походить на прошлое». Если известно, что сделал каждый из игроков в первой пар­ тии, то этот принцип максимизации приведет к опре­ деленной последовательности партий игры. Для каждой партии этой последовательности можно вычислить верх­ нюю и нижнюю границы цены игры, а также прибли­ женную оігкшшіьную стратегию для каждого игрока .

, Не пытаясь давать подробное и точное описание этого способа в общем случае, мы объясним его лишь для не­ которой игры с матрицей порядка 3 x 3 .

Пусть дана игра с матрицей

–  –  –

—2 —3 А —1 В —1 —4 0

–  –  –

Дш.

Мак-Кинси Наиболее благоприятные из найденных таким образом неравенств:

°Ъ -Г-2 ^ т г - п - 1 '8 1 2 5 Итак, мы получаем довольно хорошую апроксимацию для цены игры (которая на самом деле равна 1,85) .

Можно также показать, что есть точная нижняя граница величины ~ и точная верхняя граница величины .

і і Это дает нам уверенность в том, что, проведя способ приближения достаточно далеко, мы можем найти цену игры V с какой угодно степенью точности .

Приняв во внимание число выборов каждой чистой стратегии в і ступенях вышеописанного способа прибли­ жений, мы можем также найти апроксимацию для опти­ мальной стратегии. Так, мы видим, что в первых восьми строках таблиц 4 и 5 Р г выбирает стратегию А один раз, стратегию В три раза, стратегию С четыре раза; следо­ вательно, апроксимация оптимальной стратегии для Р 1 будет • Пусть для каждого і

–  –  –

Можно показать, что если у Р г имеется единственная оптимальная стратегия X, то последовательность Х(1), Х (2), Х (і),... (1) сходится к X ; аналогично, если у Р2 имеется единствен­ ная оптимальная стратегия, то соответствующая после­ довательность сходится к ней. Если же jPx имеет больше чем одну оптимальную стратегию, то может случится, что последовательность (1) не сходится. Можно, однако, показать, что в любом случае всякая сходящаяся подпо­ следовательность последовательности (1) сходится к оп­ тимальной стратегии для Рг .

–  –  –

Описанный в этой главе способ отыскания приближен­ ных решений прямоугольных игр был сформулирован в работе Брауна [17]. Сходимость процесса была доказана в работе Робинсона [96] .

–  –  –

1. Нормальная и развернутая формы Выше мы успешно рассмотрели решение прямоуголь­ ной игры двух лиц, то есть дали интуитивно приемлемое определение цены и оптимальных стратегий для такой игры, доказали, что решения всегда существуют, и даже показали, как их можно вычислить. Но рассуждения, к которым мы прибегали, хотя большей частью и элемен­ тарны, не всегда вполне тривиальны; и читателя, воз­ можно, пугает задача распространения этих выводов на игры более общего вида, то есть с числом игроков 2 и такие, в которых некоторые ходы, возможно, связаны с применением случайных механизмов, игроки могут иметь по нескольку ходов каждый, и знание о ранее происшедшем может меняться от хода к ходу .

Однако положение не так уж плохо, как может пока­ заться с первого взгляда, ибо оказывается, что задача решения игры, в которой игроки делают выборы из ко­ нечных множеств (мы будем называть такие игры конеч­ ными), всегда тождественна с задачей решения некоторой прямоугольной игры. Поэтому наши выводы о прямо­ угольных играх можно применить в более общем виде к любой игре двух лиц с нулевой суммой. Этот процесс отыскания прямоугольной игры, эквивалентной некото­ рой произвольной игре, называется нормализацией, а по­ лучающаяся прямоугольная игра называется игрой в нормальной форме; когда нужно провести различие между *) В отещщ$&енной литературе игры в развернутой форме на­ зываются также позиционными играми. (Прим. ред.) этими видами игр, мы будем называть произвольные игры играми в развернутой форме. Начнем с примера игры в развернутой форме .

П р и м е р 5.1 .

Ход I. Игрок Р г выбирает число х из множества {1, 2} .

Ход II. Игрок Р 2, будучи информирован о том, какое число x было выбрано на первом ходу, в свою очередь выбирает число у из множества {1, 2} .

Ход III. Игрок Р 1, будучи информирован о том, что второй игрок выбрал у, и помня, что сам он выбрал на первом ходу х, выбирает число 2 из множества {1, 2} .

После того как были выбраны три числа х, у и z, игрок Р 2 платит игроку Р г сумму М(х, у, z), где М есть функция, определенная следующим образом:

М { 1, 1, 1 )= - 2, М (2, 1, 1) = 5, М ( 1, 1, 2) = — 1, М (2, 1, 2) = 2, М ( 1, 2, 1) = 3, М (2, 2, 1) = 2, М(1, 2, 2 ) = - 4, М (2, 2, 2) = 6 .

Чтобы объяснить, как привести игру к прямоугольной форме, введем общее понятие стратегии, которое мы рас­ сматривали до сих пор лишь для прямоугольных игр .

Стратегией данного игрока в данной игре мы назовем полный набор указаний, которые говорят ему, как нужно поступить во всех мыслимых ситуациях или, вернее го­ воря, при любом мыслимом состоянии* информации, кото­ рую он может иметь а любой момент партии. Так, напри­ мер, одна из стратегий, которую может применять Р г в рассматриваемой игре, состоит в том, чтобы выбирать 1 во время обоих ходов (независимо от того, что делает Р 2 на втором ходу). Другая возможная стратегия для Р г— выбирать 1 на первом ходу и затем на третьем выбирать то же число, которое выбрал Р 2 на втором ходу. Возмож­ ная стратегия для Р 2 — выбрать 1 на втором ходу, неза­ висимо от того, какой выбор сделал Р г на первом ходу;

другая возможная стратегия для Р 2 — выбрать 1 на вто­ ром ходу, если на первом ходу было выбрано 2, и вы­ брать 2, если на первом ходу была выбрана единица .

Легко видеть, что у игрока Р 2 в этой игре четыре стратегии, то есть как раз столько, сколько имеется спо­ собов отображения множества {1, 2} в себя. Если мы обозначим через /і;- такую функцию, что / w ( l ) = і, /ij (2) = /, то четыре стратегии игрока Р 2 СУТЬ /п* / 1 2 » / 2 1 и / 2 2 - Говоря, что jP2 применяет, например, стратегию / 21(#), мы под­ разумеваем, что он решил выбрать 2 на втором ходу, если Р ! выбрал 1 на первом, и выбрать 1 на втором ходу, если ^Р ! выбрал 2 на первом .

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

Поскольку первому ходу ничто не предшествовало, у него нет сведений, которые позволили бы ему отличать раз­ ные случаи; поэтому стратегия должна просто указы­ вать ему, нужно ли выбрать 1 или 2. Перед третьим ходом стратегия должна сказать ему, какое z нужно выбрать для каждого возможного выбора величин х н у. Итак, стратегию игрока Р г можно представить как систему l|* 0 II *11 *12 *21 *22 1 II »

где i0 — число, которое ему нужно выбрать на первом ходу, a ijk — число, которое ему нужно выбрать на третьем ходу в том случае, если / было выбрано на пер­ вом ходу и & на втором (поскольку каждое і может иметь два значения, у Р г имеется всего 32 возможные страте­ гии). Если говорится, что Р г применяет, например, стра­ тегию II1 II 2 1 2 1 И И, то это значит, что Р г выбирает 1 на первом ходу; затем, если на первом ходу была выбрана 1 и на втором ходу Р 2 также выбрал 1, то игроку Р г на третьем ходу нужно выбрать 2, и аналогично для трех других возможностей для третьего хода .

В этой игре описанные нами стратегии игрока Р г обладают некоторой избыточностью; так, второе «2» в дан­ ном примере бесполезно, так как оно означает, что если на втором ходу была выбрана 1, а на первом 2 (чего не могло быть, так как данная стратегия указывает игроку Р1 что на iBJUTm ходу нужно выбрать 1), то на третьем У ходу нужно выбрать 2 .

(Следовательно, это «2» говорит игроку Р ц что делать в таком случае, какого не может быть, если он применяет данную стратегию!). Эту избы­ точность можно устранить, считая стратегией игрока Р г систему II і ІІ^ і2 У К где i — число, которое нужно, выбрать игроку Р х на первом ходу, a и г2 — числа, кото­ рые ему нужно выбрать на третьем ходу, соответственно тому, выбрал ли Р 2 на втором ходу 1 или 2. Итак, в этом случае мы могли бы упростить описание стратегий игро­ ка Р и если учесть, что он помнит свой первый ход .

Но наличие этих избыточных сведений не приносит существенного вреда, а описание стратегий для общего случая весьма усложнится, если мы будем пытаться всегда избегать их. Полный разбор этого вопроса смотрите в работе Крентеля, Мак-Кинси и Куайна [61] и в работе Дэлки [22] .

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

Предположим, что в рассматриваемой игре игрок Р 1 решает применять стратегию II1 II 2 1 2 2 II II, а игрок Р 2 решает применять стратегию / 21. Из описания стратегии игрока Р г мы видим, что на первом ходу он выбирает 1; из описания стратегии игрока Р 2 следует, что на втором ходу он выбирает 2. Возвращаясь к стра­ тегии игрока Р г мы заключаем, что на третьем ходу Р г выбирает 1. Тогда, поскольку ІІ/(1, 2, 1) = 3, мы видим, что если игроки применяют эту пару стратегий, то игрок Р 2 должен будет заплатить 3 игроку Р Рассуждая анало­ гичным образом для других возможных пар стратегий, мы можем записать матрицу стратегий (матрица 1) для прямоугольной игры, к которой приводится данная игра Матрица 1

–  –  –

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

–  –  –

отрезков. Каждый узел соединяется только с одним узлом на нижнем уровне, а на самом низшем уровне имеется всего один узел (термин «дерево» применяется в топологии в несколько более общем смысле). Узлы изображают ходы; с ними мы связываем символы, указывающие, какой игрок делает соответствующий ход .

Так, только что рассмотренная игра изображена на рис. 8 .

Около нижнего узла стоит символ «Р^), который указы­ вает, что первый ход делает игрок Р ^ два узла на втором уровне изображают второй ход, который делает игрок Р 2;

четыре узла на третьем уровне изображают третий ход, который делает Р г и т. д. Два отрезка, идущие вверх

Рис. 9 .

из нижнего узла, изображают два выбора, имеющиеся у игрока Р х на первом ходу; они соответствуют 1 и 2, если идти против часовой стрелки; таким образом, прямая с положительным наклоном означает, что игрок Р х выби­ рает 1, а прямая с отрицательным наклоном означает, что игрок Р х выбирает 2. Если у Р г на первом ходу три альтер­ нативы, игра изображалась бы как на рис. 9 .

В этом графическом представлении вся партия игры изображается ломаной, идущей от нижнего узла к одному из верхних. Поскольку число таких путей равно числу верхних узл8й7**мы видим, что в игре, изображенной на рис. 8, восемь возможных партий, а в игре, изображен­ ной на рис. 9, двенадцать. При изучении таких диаграмм обычно удобнее писать не «і и «jP2», а просто «1» и «2» .

Таким образом вместо рис. 9 мы получаем рис. 10 .

Игра, разобранная в примере 5.1, есть так называе­ мая игра с «полной информацией», то есть игра, в кото­ рой каждый игрок всегда осведомлен о всей предшествую­ щей истории игры. То, что матрица стратегий для этой игры оказалась имеющей седловую точку, не есть простая случайность; в главе VI мы покажем, что всякая игра с полной информацией обладает этим свойством .

3. Информационные множества Следующим примером будет игра, в которой доступ­ ная игрокам информация не является полной. Игрок Р г, делая третий ход, не знает, какой выбор сделал Р 2 на втором ходу, и даже не помнит, какой выбор делал он сам на первом ходу. Этот пробел памяти со стороны Р 1 может осуществиться на практике, если игроком является команда из двух человек, из которых один делает первый ход, а другой — третий .

П р и м е р 5.2 .

Ход I. Игрок Р 1 выбирает число х из множества {1, 2) .

Ход II. Игрок Р 2, зная, какое число х было выбрано в первый ход, в свою очередь выбирает число у из мно­ жества fl, 2} .

Ход III. Игрок' Р не зная о выборе числа у и забыв, какое было выбрано х, выбирает число 2 из множест­ ва fl, 2} .

После того как были выбраны три числа х, у и 2, игрок Р 2 платит игроку Р 1 сумму М(х, у, z), где М(х, г/, z) — функция, определенная в примере 5.1 .

Чтобы получить графическое представление этой игры, необходимо каким-то образом указать, что, когда Р х делает третий ход, он не знает о прошлых ходах, то есть, делая третий ход, Р х не знает, в каком именно узле рис. 8 он находится. Это дополнительное условие учтено на рис. И ; здесь четыре узла, которые Р г не может разли­ чить, делая третий ход, окружены пунктиром .

Однако мы несколько видоизменим это изображение, обозначив пунктирными линиями некоторое разбиение всего множества узлов (за исключением самых верхних узлов, изображающих конечные точки игры, когда ни­ каких выборов делать не нужно). Так мы получаем рис. 12 .

–  –  –

На нем самый нижний узел является в своей области единственным. Это показывает, что Р г во время первого хода знает точно, в какой точке дерева он находится;

–  –  –

то же имеет место для двух узлов, соответствующих второму ходу. Мы будем обозначать множества, на кото­ рые разбиты узлы, информационными множествами .

Перейдем теперь к описанию стратегий этой игры .

Очевидно, у Р 2 имеются те же стратегии, что и в при­ мере 5.1, а именно, четыре функции / п, / 12, / 21 и /22. Но поскольку Р ! ничего не знает о предыдущем течении игры, его стратегией будет просто одна из упорядочен­ ных пар чисел: || 1 1 ||, || 1 2 ||, || 2 1 ||, || 2 2 || .

Например, когда говорят, что Р г применяет стратегию II 1 2 К, то это значит, что он выбирает 1 на первом ходу и. 2 на втором .

ИспользуЭ**0пределение функции М, легко написать для новой игры матрицу стратегий .

Матрица 2 /1 2 /2 1 /2 2 /1 1

–  –  –

Мы замечаем, что эта игра не имеет седловой точки .

С помощью теоремы 2.9 учащийся может проверить, что 26 п цена игры равна у, оптимальная стратегия для Р х— О ~ 4- II и оптимальная стратегия для Р 2— т т о о Таким образом, в этой игре Р г должен рассчитывать на меньший выигрыш, чем в игре, описанной в примере это и неудивительно, так как он находится теперь в менее выгодном положении .

З а м е ч а н и е 5.3. В примере 5.2 матрица игры в нормальной форме имеет порядок лишь 4 x 4, тогда как в примере 5.1 матрица игры порядка 32X4. Вообще при уменьшении количества доступной информации умень­ шается число возможных стратегий и тем самым умень­ шается размер матрицы. Это иногда кажется учащимся парадоксальным, так как уменьшение информации долж­ но было бы привести к увеличению трудностей, а не к их уменьшению. Но размер матрицы не является верным показателем трудности игры; кроме того (это почти все­ общая истина), чем меньше мы знаем, тем легче нам ре­ шиться на что-нибудь (папример, глухому человеку легче выбрать жену, чем человеку с нормальным слухом) .

Изменив информационные множества, можно полу­ чить другие модификации игры, описанной в примере 5.1 .

П р и м е р 5.4 .

Ход I. Игрок Р г выбирает х из мно­ жества, fl, 2} .

Ход II. Игрок Р 2 не зная значения х, выбирает у из множества fl, 2} .

Ход III. Игрок Р г, зная значение х и у, выбирает z из множества fl, 2} .

Платежная функция игры такая же, как в примере 5.1 .

J .

Для этой игры мы получаем диаграмму, изображен­ ную на рис. 13; здесь мы включили два узла, соответ­ ствующие второму ходу, в одно и то же информационное множество, потому что во время второго хода игрок Р 2 не знает, в какой из этих точек он находится. Мы оста­ вляем в качестве упражнения описание стратегий этой игры и определение матрицы стратегий .

–  –  –

Платежная функция игры такая же, как в примере 5.1 .

Для этой игры мы получаем диаграмму, изображен­ ную на рис. 14 .

В этой игре стратегия игрока Р г состоит просто из пары чисел [f / II» где і — его выбор на первом ходу, а / — на третьВм. Стратегией игрока Р 2 является число і, представляющее его выбор на втором ходу. Итак, у Р і имеются четыре стратегии, у Р 2— две. Матрицей страте­ гий является матрица 3 .

Матрица 3 —2 3 II1 111 —1 —4 2 II 112 1 II 112 2 II Можно легко проверить, что цена игры равна у,о п т и ОО 7 и оптимальная мальная стратегия для Р г 7. Таким образом, оказывается, стратегия для Р 2 7 7 что цена этой игры такая же, как цена игры, описан­ ной в примере 5.2; итак, мы видим, что сведения, кото­ рыми обладает Р г в этой игре, не приносят ему пользы .

Но это просто случайность, которая вызвана тем, что для определения платежной функции были взяты именно эти числа. Очевидно, вообще Р г может быть в лучшем положении в игре такого типа, как описанная в при­ мере 5.2, чем в такой игре, как в -примере 5.5 .

Может показаться, что пример 5.5 представляет край­ нюю степень неведения, в каком могут оказаться игроки, ибо ни один из них ни в один момент не знает, каковы были прошлые выборы. Но это не совсем так, поскольку игрок Р делая третий ход, знает хотя бы то, что этому ходу предшествовали два. Нижеследующий пример пока­ зывает, что могут быть положения, когда нет даже этих сведений .

П р и м е р 5.6 .

Дана игра двух лиц, в которой Р г— один человек, а Р 2 — команда из двух человек А и В .

Эти три человека изолированы друг от друга в отдель­ ных комнатах и во время игры не могут сообщаться между собой. В начале партии судья входит в комнату, в которой находится Р 19 и предлагает ему выбрать число х из множества {1, 2}. Если Р г выбирает 1, то судья идет в ком­ нату, в которой находится А, и предлагает ему выбрать число у из множества {1, 2); если же Р х выбирает 2, судья идет в комнату, в которой находится В, и предла­ гает ему выбрать число у из множества {1, 2]. После того как было выбрано, судья идет в комнату, в кото­ рой находится другой член команды Р 21 и предлагает ему выбрать число z из множества (1, 2}. После того как выбраны три числа, Р 2 платит игроку Р г сумму

М(х, у, z), где М определено следующим образом:

М ( 1, 1, 1) = О, М ( 2, 1, 1) = 4, М ( 1, 1, 2) = 2, М (2, 1, 2) = 0, A f(l, 2, 1) = 6, М ( 2, 2, 1) = 5, М ( 1, 2, 2) = 8, 'Af(2f 2, 2)--=6 .

При рассмотрении этой игры нужно иметь в виду, что когда члену команды Р 2 предлагают сделать выбор, он не

–  –  –

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

Случайные ходы могут входить в игру тремя способами:

1) изменяя платеж, 2) изменяя размер и природу мно­ жеств, из которых игроки могут делать выборы, и 3) опре­ деляя порядок, в котором игроки будут делать ходы .

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

П р и м е р 5.7 .

Ход I. Бросается монета .

Ход II, Игрок Р г, не зная, выпала ли монета гербом или решкой, выбирает число х из множества {1, 2} .

Ход III. Игрок Р 2, не зная исхода бросания монеты, но зная, какое число х было выбрано на втором ходу, выбирает число у из множества {1, 2}. Герб мы будем изображать единицей, а решку двойкой. Тогда, если выборы за три хода были соответственно гг, х, у, игроку Р г уплачивается М ( и, х, у ), где М есть функция, определен­ ная в примере 5.1. (Таким образом, М( 1,1, 1) = —2 озна­ чает, что если монета выпадает гербом, а Р х и Р 2 оба выбирают 1, то игрок Р г платит игроку Р 2 2.)

Рис. 16 .

Игра представлена на рис. 16, где у нижнего узла стоит символ «О», который указывает, что этот ход опре­ деляется случаем (а не игроками 1 или 2). (Ради общности мы также заключаем этот узел в круг, как если бы это было информационное множество — хотя, конечно, слу­ чай ничего не знает.) Стратегия игрока Р г есть функция, указывающая ему выбор 1 или 2, в зависимости от того, какой стороной упала монета. Таким образом, стратегия есть функция Д (см. пример 5.1), которая отображает,множество {1, 2) в себя. Аналогично, стратегия игрока Р 2 есть функция / і;, указывающая ему, какой сделать выбор в зависимости от выбора Р г на втором ходу .

Предположим, например, что Р г применяет страте­ гию /21, а Р 2 — стратегию / 12. Тогда мы должны разли­ чать два случая в зависимости от того, что показывает монета— или решку. Если герб (то есть «1»), то стратегия /21 указывает игроку P lf что нужно выбрать 2, о* а стратегия / 1 указывает игроку 2 что нужно также выбрать 2; таким образом, поскольку М( 1, 2, 2) = —4, платеж игроку Р г равен —4. Если же монета выпадет решкой, то Р х выберет 1 и, следовательно, Р 2 выберет 1;

поскольку М ( 2,1,1 ) = 5, платеж игроку Р 1 будет равен 5 .

Мы предполагаем, что монета «правильная», то есть та­ кая, для которой вероятность выпадения герба и решки одинакова (и равна 1/2). Математическое ожидание выиг­ рыша Р г равно / /X 1 Iс1 1 ( 4) 2 + 5 2 — 2 • Естественно рассматривать это математическое ожидание как платеж игроку Р г в том случае, если выбраны эти стратегии .

Аналогичным способом мы можем вычислить платеж игроку Р г для других пар стратегий; таким образом, мы получаем матрицу 5:

Матрица 5

–  –  –

Матрица не имеет седловой точки. Вычисление цены и оптимальных смешанных стратегий мы оставляем в ка­ честве упражнения .

В следующем примере перед нами простая игра, в ко­ торой число альтернатив, имеющихся у одного из игро­ ков, зависит от случая .

П р и м е р 5.8 .

Ход I. Игрок Р г выбирает число х из множества {1, 2} .

Ход II. Выбирается число у из множества{ 1, 2} по­ средством случайного механизма, такого, что вероят­ ность выбора единицы равна 4 (следовательно, вероят­ ность выбора двойки равна 3/4) .

Ход III. Игрок Р 2, зная значение г/, но не зная х, выбирает число z из множества {1, 2], если у = 1, и из множества {1, 2, 3}, если у = 2 .

После того как были сделаны три хода, игрок Р 2 уплачивает игроку Р г сумму М(х, у, z), где М есть функ­ ция, определенная следующим образом:

М ( 1, 1, 1) = 2, М (2, 1, 1 ) - 0, M (1, 1, 2) = —2, АГ(2, 1, 2) = 5, М(1, 2, 1) = 1, Af (2, 2, 1 ) = - 1, М (1, 2, 2) = 0, М (2, 2, 2) = - 3, АГ(1, 2, 3) = —2, М (2, 2, 3) = 3 .

(Мы не указываем значение М( 1, 1, 3) и АГ(2, 1,3 ), так как Р 2 не может выбрать 3, если случайный механизм выбрал 1.) На рис. 17 изображена диаграмма этой игры .

Здесь символами «1/4» и «3/4» обозначены две альтерна­ тивы, из которых случайный механизм делает выбор .

Задачу описания стратегий и составления матрицы стратегий мы оставляем в качестве упражнения .

В следующем примере описана игра, в которой слу­ чайный механизм определяет, какой из игроков сделает следующий ход .

П р и м е р 5.9 .

Ход I. Игрок Р х выбирает число х из множества fl, 2} .

Ход II. Выбирается число у из множества {1, 2} по­ средством случайного механизма такого, что вероятность выбора единицы равна х/5 (следовательно, вероятность выбора двойки равна 4/5) .

Если на втором ходу выбрана единица, то на послед­ нем ходу Р 2, зная значения х и г/, выбирает число 2 из множества (1, 2}; если же на втором ходу было выбра­ но 2, то последний ход делает Р который, зная значе­ ния X и у, ’га^ирает число z из множества {1, 2}. После трех ходов игроку Р х уплачивается сумма М(х, y, z ), где М есть функция, определенная в примере 5.1. Диа­ грамма этой игры представлена на рис. 18 .

–  –  –

Задачу вычисления матрицы стратегий мы оставляем в качестве упражнения .

Поскольку эта игра с полной информацией, матрица стратегий имеет седловую точку .

–  –  –

До сих пор мы рассматривали лишь^игры двух лиц, но, очевидно, наши замечания применимы с соответ­ ствующими видоизменениями к игре п лиц, где п 2 .

В частности, для нее можно начертить диаграмму, вполне аналогичную описанным выше диаграммам для игр двух лиц. Введя понятие стратегии, можно привести игру п лиц к нормальной форме (хотя до сих пор мы еще не указали никакого способа «решения» таких игр в нор­ мальной форме). Эти замечания мы поясним на следую­ щем примере .

П р и м е р 5.10 .

Первый ход заключается в том, что случайный механизм, назначающий числам 1 и 2 вероят­ ности соответственно */з и 2/з, выбирает число х из мно­ жества {1, 2}. Если х = і, то на втором ходу игрок зная значение х, выбирает число у из множества {1, 2, 3] .

Если X = 2, то на втором ходу игрок Р 2, зная значение х, выбирает число у из множества {1, 2, 3}. Если у = 1, то на третьем ходу игрок Р в, зная значение у, но не зная х, выбирает число z из множества {1, 2). Если у Ф 1, то на третьем ходу игрок Р 4, зная значение х и зная, было ли выбрано у — 1 или у Ф 1, выбирает число z из множества {1, 2}. После того как были выбраны х, у и z, игрокам Р х, Р 2,-Рзи Р^ уплачиваются соответственно суммы М г(х, у, z), М 2(х, у, z), М 3(х, у, z) и М ^ х, у, z), где М и М 2, М 3 и АГ4 — некоторые действительные функции. Диаграмма этой игры изображена на рис. 19 .

Стратегия игрока Р г есть одно из чисел 1, 2, 3. Тако­ ва же стратегия игрока Р 2. Стратегия игрока Р 3 есть 1 или 2. Стратегия игрока Р 4 должна указать ему, какое значение z из множества {1,2} выбирать при х = 1 и х == 2 .

Обозначим четыре возможные стратегии для P через /и»

/і2 h i и / ^ : Н алРимеР» когда говорят, что Р^ применяет стратегию т^^то это значит, что он выберет z = 2, если z = 1, и z = 1, если X = 2, « Чтобы понять, как вычислять элементы матрицы стра­ тегий, предположим, что Р г применяет стратегию 1, Р 2 — стратегию 3, Р 3 — стратегию 2 и — стратегию /21 .

Как и при разборе примера 5.7, нужно рассмотреть отдельно случаи, когда х = 1 и когда х = 2 .

Рис. 19 .

Если я = 1, то второй ход делает Р и, следовательно, г/ — 1. Тогда третий ход делает Р 3, и, следовательно, z = 2. В этом случае платеж игроку Р { (где і = 1, 2, 3, 4) равен А/Д1, 1, 2) .

Если x — 2, то второй ход делает Р 2, и, следовательно, у — 3. Тогда третий ход делает и, следовательно, z ~ 2\{x ) “ /21(2) == В этом случае платеж игроку (для i = 1, 2, 3, 4) равен ft(2, 3,1). Поскольку вероятность того, что x == 1, равна 1/3, мы заключаем, что если игроки применяют указанные стратегии, то математическое ожи­ дание выигрыша игрока Р { будет у Л М І, 1, 2 )+ 4 Л/, (2, з, 1) .

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

Рис. 20 .

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

Это значит, что никакая игра не может иметь такой диа­ граммы, как, например, на рис. 20, на которой из трех узлов А, В и С, составляю­ щих партию, два узла, А и С, Рис. 21 .

принадлежат одному инфор­ мационному множеству. Это условие исключает также возможность такой диаграммы, как изображенная на рис. 21 .

Чтобы понять, почему должно быть наложено такое условие, предположим, например, что мы пытаемся соста­ вить действительную партию игры, имеющей диаграмму, представленную на рис. 21. Очевидно, для роли игро­ ка Р г нужщялметь двух человек, ибо если он один, то при втором выборе он вспомнит свой первый выбор и, следовательно, будет знать, в какой точке диаграммы он находится, тогда как информационное множество указы­ вает, что он не должен этого знать .

Допустим теперь, что Р 1 состоит из двух человек А и В, которые помещены в отдельные комнаты и не могут сообщаться между собой. В начале игры судья должен пойти в одну комнату и предложить находящемуся в ней человеку выбрать число из множества {1, 2}; затем он идет в другую комнату и предлагает другому человеку выбрать число из множества fl, 2}. В результате игро­ ку будет уплачена сумма М(х, у ), где х есть первое выбранное число, у — второе, а М — некоторая дей­ ствительная функция, определенная на декартовом про­ изведении множества {1, 2} на себя .

Игрокам А и В не разрешается сообщаться между собой во время игры, но мы предположим, что перед нача­ лом игры они встретились, чтобы договориться о том, как им следует поступать. Они должны решить, выберут ли они оба 1 или 2, или А выберет 1, а В — 2, или А выбе­ рет 2, а В — 1. Игроки не знают, кого выберет судья сначала, А или В, и поэтому не знают, будет ли число, выбранное игроком А, называться «г» или «г/»; причем, конечно, вовсе не обязательно будет М ( х, у ) = М ( у, х ) .

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

Можно подумать, что затруднений такого рода можно мвбежать, рассматривая абстрактные игры, то есть игры не людей, а каких-то машин, не имеющих памяти. В этом случае получим: если машина установлена так, чтобы выбрать правую альтернативу в изображенной выше игре, она выберет эту альтернативу оба раза и, следова­ тельно, закончит партию в если она установлена на выбор левой альтернативы, она обязательно закончит партию в 4. Следовательно,— и это является непреодо­ лимым препятствием — узлы и s никогда не будут достигнуты, и их можно с таким же успехом исключить из диаграммы .

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

–  –  –

Подробное описание игр в развернутой форме приве­ дено в книге фон Неймана и Моргенштерна [92]. Мы в своем изложении опирались на формулировки, приве денные в работе Куна [63] .

–  –  –

1. Найдите цену и оптимальные стратегии для игры, описан­ ной в примере 5.7 .

2. Определите матрицы стратегий и решения для игр, описан­ ных в примерах 5.4 и 5.8 .

3. Опишите матрицу стратегий для игры, описанной в при­ мере 5.3. Найдите оптимальные чистые стратегии обоих игроков .

4. Начертите диаграмму игры, в которой происходят следую­ щие ходы:

Ход I. Pj выбирает число х из множества {1, 2, 3, 4} .

–  –  –

Опишите стратегии этой игры, найдите ожидаемый платеж каждому из игроков для каждой возможной пары стратегий и най­ дите условия, которым должны удовлетворять а, М х и М 2, чтобы игра была игрой с нулевой суммой (то есть чтобы сумма матема­ тических ожиданий выигрыша игроков Р 1 и Р 2 всегда была равна нулю) .

Какие условия нужно наложить на М г и М 2, чтобы игра имела нулевую сумму независимо от значения а?

9. Каким условиям должны удовлетворять функции М ц M z и ikf4, чтобы игра, оиисанная в примере 5.10, была игрой с нуле­ вой суммой (то есть чтобы для всех стратегий сумма математиче­ ских ожиданий выигрышей четырех игроков была равна нулю)?

1. Общее определение конечных игр В примерах главы V было очень полезно представлять игры в развернутой форме посредством диаграмм, кото­ рые часто оказываются понятней, чем словесные описа­ ния. Поэтому с формальной стороны удобно просто отожде­ ствлять игры с диаграммами, служащими для их изобра­ жения, что мы и будем делать в этой главе, посвященной точному определению игр в развернутой форме и дока­ зательству важной теоремы относительно этих игр .

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

1. Дерево Т (в том смысле, как было объяснено в главе V) .

2. п действительных функций F x,..., Fn, определен­ ных в каждой из вершин дерева Т таким образом, что если t есть вершина, то F{(t) есть сумма, которая должна быть уплачена игроку Р {, если партия заканчивается в точке t .

3. Набор чисел 0, 1,..., п, таких, что каждой точке разветвления дерева Т ставится в соответствие число, указывающее, какой игрок делает очередной ход в рас­ сматриваемой точке (число означает, что в этой точке применяется случайный механизм) .

4. Каждой точке q разветвления дерева Г, которой, согласно пункту 3, ставится в соответствие число О, соответствует элемент || х х... x k \\ множества Sk. Здесь к есть число*д$ьтернатив в точке g, то есть число прямых, выходящих из q .

5. Разбиения точек разветвления на непресекающиеся и полные множества (информационные множества), удовлетворяющие следующим условиям:

а) Все точки разветвления, принадлежащие данному информационному множеству, относятся, согласно пунк­ ту 3, к одному игроку .

б) Все точки разветвления, принадлежащие одному информационному множеству, имеют одинаковое число альтернатив, которые мы будем нумеровать справа налево .

в) Если (см. пункт 3) точке разветвления q поставлено в соответствие число 0, то информационное множество, в котором находится g, состоит только из этой точки .

г) Если iS — партия игры, то есть ломаная линия, * идущая от основания дерева к одной из его вершин, и если А — любое информационное множество, то суще­ ствует самое большее одна точка разветвления, принад­ лежащая обоим множествам S и А .

Из примеров, приведенных в главе V, должно быть ясно, какие функции выполняют различные части этого информационного аппарата и какие причины побудили нас принять четыре вышеуказанных условия для инфор­ мационных множеств. Впрочем, как легко видеть, усло­ вие в) вполне произвольно и принято лишь для опре­ деленности .

Пользуясь этим общим определением игр, мы можем теперь так определить стратегии: стратегией игрока Р х (для і = 1,..., п) мы* называем функцию, которая опре­ делена для каждого информационного множества, соот­ ветствующего игроку Р и значение которой для каждого такого информационного множества представляет одну из альтернатив, имеющихся у Р Таким образом, страте­ гия указывает игроку, что нужно делать при любой возможной информации .

Рассмотрим игру, диаграмма которой приведена на рис. 23 (на этом рисунке по причинам, изложенным ниже, мы дали обозначения точкам разветвления и конечным точкам) .

Здесь имеются два информационных множества для Р г:

{q2, и ( 78, ql0, n }, и два информационных множества 7з} для Р 2: (д4, q7} и {q5, g6}. Следовательно, стратегией игрока Р 1 является любая из четырех функций, определенных для аргументов {^2, q3} и {#8, #10, q n } и прини­ мающих значения 1 и 1. Стратегией игрока Р 2 является

–  –  –

то ясно, что р (X, t) есть вероятность того, что партия закончится в точке t, если игроки применяют упорядо­ ченное множество стратегий х. Использование одной и той же буквы р для обеих функций не может внести путаницы, так как в одном случае это функция двух переменных, а в другом —трех. Так, для игры, изобра­ женной на рис. 23, используя то же множество страте­ гий а, как и раньше, мы имеем:

–  –  –

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

Ц ий

Мы имеем теперь платежные функции двух видов:

1) функции Я ь..., Я п, которые определены на мно­ жестве вершин диаграммы игры и указывают, сколько получит каждый игрок, если игра закончится в данной вершине; 2) ^ щ к ц и и М г,..., М п, которые определены на множестве упорядоченных чистых стратегий и указывают, сколько получит каждый игрок (в среднем), если игроки будут применять данные чистые стратегии .

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

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

Следует заметить, что правильное определение игры с нулевой суммой — это определение посредством пла­ тежных функций стратегии, а не платежных функций партии. Игра называется игрой с нулевой суммой, если для всякого n-мерного набора х стратегий игроков Р х,..., Р п мы имеем

–  –  –

где М х,..., М п суть платежные функции стратегии .

Из упражнений 8 и 9 главы V видно, что это условие может быть выполнено в некоторых случаях и тогда, когда соответствующее уравнение для платежных функ­ ций партии не будет справедливо .

2. Игры с полной информацией. Точки равновесия Обратимся теперь к играм особого рода — к так назы­ ваемым играм с «прлной информацией». Эти игры харак­ теризуются тем, что во всякой точке в любой партии игрок, чья очередь делать ход, точно знает, какие выборы были сделаны раньше. По отношению к диаграмме игры это значит, что любое информационное множество со­ стоит из одного элемента. Так, например, игра, изобра­ женная на рис. 24, есть игра с полной информацией .

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

Учащийся сам может распознать, какие из обычных салонных игр являются играми с полной информацией .

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

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

–  –  –

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

Каждый игрок в тик-так-ту может играть таким образом, что он выигщет (если другой игрок будет играть непра­ вильно) или добьется ничьей. По этой причине взрослые редко играют в тик-так-ту: после того как они узнали оптимальные стратегии для этой игры, она уже не ставит ііеред ними умственных задач. Чтобы найти такие опти­ мальные стратегии игры, нужно лишь переписать все стратегии игры, написать матрицу (поставив «1», «0»

и «—1» для «выигрыша», «ничьей» и «проигрыша») и вы­ брать седловую точку. Но число возможных стратегий для шахмат так велико, что вряд ли возможно про­ вести такое перечисление. Поэтому, вероятно, люди будут еще долгое время увлекаться игрой в шах­ маты .

Вследствие того, что наше доказательство будет про­ водиться путем математической индукции, оказывается удобнее доказать несколько более сильное утверждение, чем упомянутое выше, — теорему, относящуюся ко всем иг­ рам двух ^лиц с полной информацией, а не только к играм двух лиц с нулевой суммой и полной информацией. Для формулировки этой более сильной теоремы необходимо вве­ сти понятие точки равновесия, являющееся обобщением понятия седловой точки .

Пусть платежные функции стратегии игры п лиц суть М г,..., Afn, множество чистых стратегий игрока Р { (для і = 1,..., п) есть А|, и А —декартово произведение мно­ жеств А..., Ап. Мы говорим, что элемент || хг... хп || множества А есть точка равновесия, если для каждого і и для любого элемента у множества А*

М і (х..., х п) М { (х.., x i+v..., x n) .

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

В случае игры двух лиц с нулевой суммой точка рав­ новесия есть то же самое, что и седловая точка матрицы для игры в нормальной форме. Действительно, предполо­ жим, что II хг х 2 II есть точка равновесия игры двух лиц с нулевой суммой и платежными функциями М г и М 2, и пусть Aj и А2 — стратегии, имеющиеся у игроков Р г и Р 2 .

Поскольку у х г х2 II есть точка равновесия, мы имеем для любого элемента у л множества А, и любого элемента у 2

2. И ГРЫ С ПОЛНОЙ И Н Ф О РМ АЦ И ЕЙ. ТОЧКИ РАВН О ВЕ С И Я

–  –  –

^Итак, чтобы показать, что всякая игра двух лиц с ну­ левой суммой и полной информацией имеет седловую точку, достаточно показать, что всякая игра двух лиц с полной информацией имеет точку равновесия; это мы сейчас и сделаем .

Чтобы щ щ ести наше доказательство, удобно ввести цоцятие усечения игры с полной информацией. Мы под­ разумеваем под этим игру, которая получается из данной исключением первого хода. Так, предположим, что игра имеет диаграмму, показанную на рис. 26, и платежная функция для Р { (для і = 1, 2) выражается действительной функцией # f, определенной в точках t x,..., t15. Тогда

–  –  –

в частности, § *) = м п п, *?. (12)

Из равенства (5) мы имеем:

(13) M i f h g t ) M r ( f t gt) .

Из (9), (13), первого неравенства (1) и из (12) мы за­ ключаем, что М а ( / * f g* } в М а ( / * } М а, ( /* ? g {) № l' V i, g i ) = M1' ( f, g * ). (14) Из (11) и (14) мы видим, что || /*g* || есть точка равно­ весия игры Г, что и требовалось доказать .

С л у ч а й 3 аналогичен случаю 2 .

Теорема доказана .

С л е д с т в и е 6.2. Матрица любой игры в нормаль­ ной форме двух лиц с нулевой суммой и полной информа­ цией имеет седловую точку .

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

З а м е ч а н и е 6.3. Теорему 6.1 можно столь же легко доказать для игр п лиц, но обозначения будут не­ сколько сложнее. Это расширение теоремы мы оставляем в качестве упражнения .

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

Не принимая полностью эту точку зрения, мы можем, по крайней мере, сделать следующее замечание. Когда группа лиц часто и в течение долгого времени играет в некоторую игру, они иногда приобретают привычку выбирать точку равновесия. Если кто-нибудь играет в эту игру с членами данной группы, самое лучшее для него — самому выбрать точку равновесия. Таким образом, точка равновесия представляет, так сказать, принятую норму поведения для группы: нарушающий соглашение рискует проиграть, еслв«^му не удастся убедить и других нару­ шить соглашение .

158 г л.. ОБЩАЯ ТЕОРИЯ ИГР В РАЗВЕРНУТОЙ ФОРМЕ Ч

3. Игры с и стратегии и деальн ой пам ятью поведен ия Интересным и полезным обобщением игр с полной информацией является понятие игр с идеальной памятью .

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

Это понятие игры с идеальной памятью можно опре­ делить точно через информационные множества игры .

Игра с идеальной памятью — это игра, удовлетворяющая следующему условию: пусть Р и Q — любые два хода, которые делает один игрок, и такие, что в некоторой пар­ тии игры ход Р предшествует ходу Q; U и V — инфор­ мационные множества, содержащие соответственно Р и Q; каждая точка множества U дает к альтернатив;

U| (і= 1,..., А — множество всех узлов дерева (то :) есть ходов), которых можно достигнуть, выбрав і-ю аль­ тернативу в некоторой точке множества U; тогда для любого і мы имеем VZU* .

Обратимся теперь к понятию % стратегии поведения .

Очевидно, выбор ^смешанной стратегии равнозначен при­ менению случайного механизма для того, чтобы выбрать чистую стратегию, то есть решить, что делать на каждом ходу игры. Подобно этому можно применять случайный механизм на каждом ходу, чтобы решить, какую альтер­ нативу выбрать на этом ходу. Такая система игры назы­ вается стратегией поведения. В широком смысле стра­ тегия поведения данного игрока есть функция, опреде­ ленная на классе его информационных множеств, кото­ рая назначает каждому информационному множеству U элемент множества Sr, где г есть число альтернатив, которое дает U. Очевидно, по данной стратегии поведе­ ния одного игрока и по данной чистой или смешанной стратегии или стратегии поведения другого игрока можно вычислить ожидаемый выигрыш каждого игрока .

Рассмотрим, например, игру, диаграмма которой изо­ бражена на рис. 30; здесь цифрами у вершин дерева мы обозначили платеж первому игроку при различных воз­ можных исходах. Стратегия поведения для первого игрока есть функция, определенная на {1^, U2, Us}, элементы

-4 -3 -7 +7 +/ -/ -4 -3

–  –  –

и подобно этому для игрока Р 2 лучший выход — взять Итак, оптимальная система игры для Р г— бросить монету, чтобы решить, какую альтернативу выбрать в Ux, выбирать всегда левую альтернативу в U2 и выби­ рать всегда правую альтернативу в U3 .

З а м е ч а н и е 6.5. Следует заметить, что вообще число параметров, которые нужно определить при вычис­ лении оптимальных стратегий поведения, гораздо меньше, чем число параметров, связанных с вычислением опти­ мальных смешанных стратегий. Так, в примере 6.4 при вычислении оптимальной стратегии поведения для Р х нам нужно было иметь дело лишь с тремя параметрами .

С другой стороны, поскольку игрок Р г в этой игре имеет восемь чистых стратегий, смешанная стратегия есть эле­ мент множества S8 и, следовательно, вычисление опти­ мальных смешанных стратегий связано с семью незави­ симыми параметрами .

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

Библиографические замечания Данное выше формальное определение игр в развер­ нутой форме весьма сходно с определением, которое при­ ведено в работе Куна [63]. Там же приведено доказа­ тельство теоремы 6.1. Понятие точки равновесия было введено в работе Нэша [85]. Он же дал доказательство того, что во всякой игре п лиц среди смешанных страте­ гий имеется точка равновесия .

Доказательство того, что игра с идеальной памятью имеет оптимальные стратегии поведения, можно найти у Куна [63]. .

У пражнения

1. Сформулируйте и докажите обобщение теоремы 6,1 для игры п лиц .

–  –  –

7. Найдите платежную функцию для игры с нулевой суммой, диаграмма которой изображена на рис. 32 и у которой нет седло­ вой точки (в чистых стратегиях) .

–  –  –

8. Найдите оптимальные стратегии поведения для игры с та­ кой же диаграммой, как на рис. 30, но в которой платежи, считая слева направо, такие:

— 10, — 9, — 1, + 1, + 3, — 2, - 1 0, — 9 вместо

-4, -3, -1, +1, +1, -1, -4, -3 .

9. Постройте пример игры, не имеющей оптимальной страте­ гии поведения для Р

10. ИмеіЁЩ^гури одинаковые колоды из п карт; каждый набор карт обозначен положительными числами х..., хп. Каждый из двух игроков держит.одну колоду, а третья положена вниз лицом .

Игра имеет три этапа, состоящие в следующем:

1. Верхняя карта третьей колоды переворачивается вверх лицом .

2. Игроки выбирают одновременно по одной карте из своих колод .

3. Игрок, положивший старшую карту, выигрывает у своего противника стоимость перевернутой карты из колоды (если они кладут карты с одинаковым номером, то никто не платит). Игра, очевидно, имеет цену нуль, так как она симметрична .

Постройте диаграмму этой игры для п — 2 и покажите, что в этом случае существуют оптимальные чистые стратегии. Пока­ жите, кроме того, что имеются чистые стратегии для п = 3, если # 1 = 1, х 2 = 2 и х 3'— 3. Найдите оптимальные стратегии для п ~ 3, если х1 = 2, х 2 — 3 и х 3 = 4 .

До сих пор мы ограничивались рассмотрением конеч­ ных игр. Однако в некоторых практически важных ситуа­ циях, которые удобно изучать с точки зрения теории игр, участники производят выборы из бесконечных мно­ жеств. Так, предположим, например, что предпринима­ тель сталкивается с вопросом, какой величины делать кусок мыла, который он намеревается продать за десять центов. Ему хотелось бы сделать его достаточно боль­ шим, чтобы быть в состоянии успешно соревноваться с другими предпринимателями и, таким образом, продать много кусков, но, конечно, он не хочет делать его столь большим, чтобы терпеть убыток на каждом проданном куске. Поскольку он должен стремиться как-то угады­ вать действия других предпринимателей, интересы кото­ рых противоположны его интересам, получается нечто подобное игре. А поскольку кусок мыла может иметь бес­ конечное число весов (или такое большое конечное число, что его удобно рассматривать как бесконечное), мы стал­ киваемся с игроподобной ситуацией, в которой игроки производят выборы из бесконечных множеств. Поэтому представляется полезным расширить наше понятие игры так, чтобы включить также бесконечные игры, то есть игры, в которых некоторые из выборов игроки совер­ шают из бесконечных множеств. Однако мы их будем разбирать далеко не в такой общей форме, в какой мы рассматривали конечные игры. Во-первых, мы будем рассматривать лишь игры с одним ходом для каждого игрока и такие, что ни один из игроков не получает инфор­ мации о вьЖоре другого. Таким образом, мы будем иметь дело лишь с играми, в которых; как в прямоугольных играх, определенных в главе I, игрок Р х выбирает эле­ мент X из множества А, а игрок Р 2 выбирает элемент у из множества В. Кроме того, как и для прямоугольных игр, мы предположим, что имеется действительная функ­ ция М двух переменных, такая, что если игрок Р г выби­ рает X, а игрок Р 2 выбирает г/, то игрок Р 2 платит игро­ ку Р г сумму М(х, у ). Итак, мы обобщаем понятие прямо­ угольных игр только в том отношении, что допускаем бесконечные множества А и В .

Наше внимание будет почти исключительно ограничено случаем, когда оба множества А и В суть замкнутые интервалы [0, 1]; мы будем называть такие игры непре­ рывными. Это название происходит оттого, что замкну­ тый интервал (точек или действительных чисел) иногда называют континуумом, а не оттого, что на функцию М налагаются какие-либо свойства непрерывности.

Следует заметить, что это ограничение для множеств А и*В не так существенно, как может показаться с первого взгляда:

если А и В — любые замкнутые интервалы, то простым переименованием элементов множеств А и В мы полу­ чим игру, в которой выборы совершаются из замкнутого интервала [0, 1]. Итак, непрерывной игрой (или игрой, которая может быть приведена к непрерывной игре) называется игра, подобная прямоугольной, но в которой игроки делают выборы из конечных замкнутых интервалов .

П р и м е р 7.1 .

Рассмотрим, напрймер, игру, в кото­ рой Р х выбирает число х из интервала [0, 1], а игрок Р 2 независимо от него выбирает число у из того же интер­ вала и в которой платеж игроку Р г равен M (X, у) = 2х2 —г/2 .

Эта игра по существу так проста, что мы можем сразу узнать оптимальные стратегии игроков: Р г, желая обес­ печить максимум функции М(х, у ), выберет я = 1, а Р 21 чтобы обеспечить минимум функции М ( х, у), также выбе­ рет у = 1; тогда платеж будет равен 1 .

П р и м е р 7.2 .

В качестве примера немного более сложной непрерывной игры рассмотрим следующую си­ туацию: некий полковник, назовем его Блотто, хочет атаковать две равноценные позиции А и В, послав часть х своего полка к Л, а остальную часть (1—х) — к В. Его противник, защитник этих позиций, имеет в своем рас­ поряжении лишь часть полка а, где 0 а 1, которую ему нужно разделить между позициями А и В. Допустим, что защитник выделяет долю у своих сил на А и (1—у) на 2?, так что обороняющие силы равны соответственно а у и а(1—у) полка. Допустим, что все схватки смертельны, и обе стороны потеряли одинаковое число людей — число, равное численности меньшего отряда, и позиции в резуль­ тате захватывает больший отряд. Для каждой позиции выигрышем победителя считается сама позиция (оцени­ ваемая в один полк) плюс число уцелевших солдат; если никто не захватил позицию, выигрыши равны нулю .

Следовательно, мы можем записать выигрыши полков­ ника Блотто таким образом:

М { х, у) = sg n [х —ау] + я — ау + + Sgn [1 —ж —а (1 —у)] + 1 - x — а (1 — у ) г где sgnz определяется так:

— 1, если z О, sgn z = если z = 0, 1, если z 0 .

–  –  –

Тогда, рассуждая, как в главе I, мы видим, что Р г мо­ жет сделать выбор, который обеспечит ему получение по меньшей мере а Р 2 может позаботиться о том, чтобы Р х получил не больше 2. Если 1 = 2, то на основании теоремы 1.5 мы видим, что М имеет седловую точку II М ( Х о, у 0) = 1 = 2 .

В этом случае естественно назвать х 0 и у 0 оптимальными способами игры для Р г и Р 21 a 1 (и, следовательно, 2) ценой игры.

Так, в примере 7.1 мы имели:

M (X, у) = 2х2 — i .

Эта функция имеет седловую точку || 1 1 ||; отсюда М( 1, \ ) = і г=2 = \ .

Напротив, в примере 7.2, как можно показать, седловой точки нет .

Нам остались два более трудных случая: 1) случай, когда 1 и 2 не существуют, и 2) случай, когда обе эти величины существуют, но не одинаковы. Второй случай будет рассмотрен в главе X после того, как в главах V III и IX мы введем некоторые необходимые чисто математические понятия. Что касается первого случая, то мы ограничимся тем, что покажем возможность такой ситу­ ации .

Часто, когда 1 и 2 не существуют, мы знаем, как определить цену игры или оптимальные стратегии для обоих игроков .

Пример 7.3 .

Платежная функция непрерывной игры определена следующим образом:

М (х, у) —--------, если X ф 0 и у ф О, у X ^

–  –  –

обе существуют и равны. Если у непрерывной игры имеется подобная платежная функция, то, хотя игра и не имеет седловой точки, общее значение величин (3) и (4) иногда называют ц е н о й и г р ы. В таком случае Р 1 вообще не может выбрать стратегию х0, которая гаранти­ ровала бы ему, что для любой стратегии г/0, выбранной игроком Р 2, М (х0, у) 0, но он может, тем не менее, для любого е 0 выбрать стра­ тегию хг, такую, что для любого у, выбранного игроком Р 2, М (хе, у ) — е .

Таким образом, Р г может подойти как угодно близко к оптимальному способу игры .

П р и м е р 7.5 .

Платежная функция М непрерывной игры определена следующими условиями:

М ( х, у) = х + у для х ф 1 и у ф 0,

–  –  –

М справедливы для всех х и у, лежащих в замкнутом интервале [0, 1]. Отсюда выведите, что цена игры (для Р х) равна — и что оптимальный способ игры для Р х— взять, а оптимальный способ игры для Р 2— взять у = — .

2. Непрерывная игра имеет платежную функцию, определен­ ную следующим образом:

* - [ ( * - ! ) * ] [•+(»— »]+ «»,

–  –  –

График этой функции представлен на рис. 36 .

Мы замечаем, что обе эти функции неубывающие, то есть F (хг) F (xz), при х г ^, х 2 (на графике это выра­ жается характером кривых, идущих направо вверх). Как мы сразу видим, это справедливо Для всякой функции распределения, ибо если то вероятность того, что вы­ FfJ бранное число лежит в интер­ вале [0, х2], должна быть по меньшей мере равна вероятно­ сти того, что оно лежит в интер­ вале [0, х г] .

Рассмотренные нами две частные функции суть так на­ зываемые возрастающие функ­ ции, то есть F(xx)iF(x2), когда Жі#2. Но это не всегда выпол­ няется для функций распреде­ ления. Так, например, функ­ ция распределения может иметь такой график, как на рис. 37. Горизонтальный отрезок на этом графике пока­ зывает, что

–  –  –

График этой функции пред­ % ставлен на рис. 39 (жирная точка в левом конце верх­ него отрезка указывает, что О ъ % Рис. 39 .

^ (1/4) = 5/ 8 а не Vs)* График, изображенный на рис. 39, имеет скачок при х = 4, то есть в точке, кото­ рой функция распределения приписывает конечную (не нулевую) вероятность. Легко видеть, что точки, которым* приписывается конечная вероятность, всегда соответст­ вуют точкам разрыва графика функции распределения .

Все рассмотренные до сих пор функции распределе­ ния имели графики, состоящие либо из прямолинейного отрезка, либо из ряда таких отрезков. Но из следующего примера можно видеть, что это не всегда так. Допустим, что в устройстве, изображенном на рис. 33, кончик стрелки сделан из стали и в плоскости круга помещен небольшой магнит справа от точки с f(X J отметкой «2». Тогда стрел­ ка будет чаще останавли­ ваться вблизи от 2, чем в других местах (но вероят­ ность остановки в одной данной точке по-прежнему равна 0). При этом, очевид­ но, функция распределения будет иметь криволинейный график, подобный изобра- ____ женному на рис. 40 .

Рассмотрим, наконец, не­ сколько менее элементарное свойство функций распреде­ ления. Для этого введем одно определение. Функция F называется непрерывной справа в точке х, если lim F (я + е) ~ F ( x ) .

г-4-0 Аналогично мы называем функцию непрерывной слева в точке x, если lim F (x — е) = F (x) .

8-»0 Мы замечаем, что функция, изображенная на рис. 39, в точке x = 4 непрерывна справа, но не непрерывна слева .

Функция, изображенная на рис. 38, в точке х = 0 не не­ прерывна справа .

Мьі имеем следующую теорему .

Т е о р е м а 8.1 .

Всякая функция распределения не­ прерывна j;jyjaea во всех точках открытого интервала (0, 1) .

Д о к а з а т е л ь с т в о. Пусть F — функция рас­ пределения, и пусть 0 я 1. Мы хотим показать, что 1im [ F (x -h e) —F (x)] = 0 .

e-»0 Величина F (x + e) — F (.r) по определению функции распределения равна вероят­ ности того, что число z, выбранное согласно этой функ­ ции распределения, удовлетворяет неравенству x z х + е .

Но для любого заданного 2 можно найти такое малое положительное е, чтобы это неравенство стало невоз­ можным. Следовательно, вероятность того, что z будет удовлетворять этому неравенству, стремится к нулю, когда е стремится к нулю, что завершает доказательство .

2. Формальные выводы Итак, мы видим, что функция распределения F всегда удовлетворяет следующим условиям: I) F ( x ) 0 для лю­ бого x из [0, 1]; 2) / ’(О) = 0 и і?(1) = 1 ; 3) F(x) есть неубы­ вающая функция в замкнутом интервале [0, 1]; 4) F(x) непрерывна справа в открытом интервале (0, 1) .

С точки зрения наших интуитивных.догадок о вероят­ ности представляется, возможным такое утверждение:

любая функция, удовлетворяющая условиям (1), (2), (3) и (4), есть функция распределения, то есть если F — некоторая функция, удовлетворяющая этим условиям, то существует способ выбора чисел из интервала [0, 1], имеющий своей функцией распределения функцию F .

Во всяком случае, понятие функции распределения станет математически строгим, если мы будем впредь применять этот термин просто для обозначения функции, удовле­ творяющей указанным четырем условиям. Итак, чтобы проверить, что некоторая функция есть функция распре­ деления, нам не нужно описывать сам случайный про­ цесс, который ее порождает, а следует лишь проверить, что она определена на замкнутом интервале [0, 1], не принимает отрицательных значений, не убывает п т. д .

Мы будем применять букву D для обозначения мно­ жества всех функций распределения, то есть множества всех функций, которые удовлетворяют указанным четы­ рем условиям .

Приведем теорему, полезную в дальнейшем .

Т е о р е м а 8.2 .

В сякая последовательность ф ункций распределения -содержит подпоследовательность, сходя­ щуюся к некоторой ф ункции распределения F во всякой точке непрерывности ф ункции F .

Д о к а з а т е л ь с т в о. Известно, что правильные дроби можно расположить в упорядоченную бесконечную после­ довательность.

Мы можем это сделать, например, так:

на первое место поместим единственную правильную дробь, имеющую знаменатель 2 ^ а именно—^ ; затем в порядке возрастания расположим правильные дроби, имеющие знаменатель 3; затем дроби со знаменателем 4 (пропуская уже записанные) и т. д. Так мы получим:

2’ 3’ 3’ 4’ 4, 5’ 5’ 5’ 5, 6 ’ 6 ’ 7 ’ *“

–  –  –

Пусть дана непрерывная игра с платежной функцией Af, и Р2 выбирает число у 0. Тогда для каждого х, которое может выбрать Р выигрыш Р1 определяется функцией G(x) = M ( x, ?/0) Предположим теперь, что Р вместо того чтобы всегда выбирать одно и то же число х, решает применить слу­ чайный механизм, которому соответствует функция рас­ пределения F. Очевидно, игроку jP1 для того чтобы сде­ ?

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

Итак, перед нами следующая задача .

Пусть G (x) для 0 1 есть сумма, которую полу­ чит если он выберет х (причем Р г делает выборы по функции распределения F). Каково математическое ожи­ дание выигрыша у iPj?

Очевидно, мы не можем сказать, что это математиче­ ское ожидание равно сумме всех произведений G(x) Р ( х ), где Р( х) есть вероятность того, что будет выбрано х, ибо, как мы видели в предыдущей главе, вероятность Р(х) может быть равна нулю для всех х .

С другой стороны, математическое ожидание выиг­ рыша мы можем выразить приближенно следующим образом.

Берем три значения х, скажем, х = 0, х = у и х = 1, и составляем следующее выражение:

йШ К т ) -"°]+й['»-'(*)] • Первый член этой суммы равен выигрышу Р если он выберет у, умноженному на вероятность того, что он

–  –  –

И у х 2 1. Если G изменяется незначительно в интер­ вале или в интервале [ у * ’ то эти ПРИ~ ближения не будут сильно отличаться друг от друга. Если мы будем считать, что минимальное значение в интервале 0 х у G принимает при zv а в интервале у я 1 при z2, то наше интуитивное представление подсказывает, что математическое ожидание выигрыша для Р г равно по меньшей мере

–  –  –

Аналогично, если G принимает максимальные значения в этих двух интервалах соответственно при z { и z2, то математическое ожидание выигрыша для Р г равно самое большее

–  –  –

Поскольку интеграл Стилтьеса определен путем сложного предельного перехода, не удивительно, что он не всегда существует. В частности, легко показать, что он не существует, если G и F имеют общую точку разрыва .

Например, пусть F(x) = G(x) = 0 (0 я 1 ), и пусть F (x) = G(x) = 1 (1 я 2 ) .

Здесь одна из разностей F (xh) —F (хк_г) при 0 х к_г 1, 1 #fe 2 не может быть сделана меньше 1. G(zh) может быть равна либо 0, либо 1, в зависимости от выбора zk .

Следовательно, в этом случае сумма (1) равна либо О, либо 1, в зависимости от того, равна G (zk) нулю или единице. Итак, предел (3) зависит от выбора zv и, сле­ довательно, интеграл ^ G (x) dF (х) о не существует .

13 Дда. Мак-Кинси Теперь мы сформулируем и докажем теорему, кото­ рая указывает достаточные условия существования интеграла Стилтьеса .

Т е о р е м а 9.2 .

Если функция G непрерывна в интер­ вале [а, 6] и функция F — неубывающая, то интеграл ъ ^ G ( x ) dF(x) а существует .

З а м е ч а н и е 9.3. В частном случае, когда F {х) = х, теорема 9.2 сводится к известной теореме интегрального исчисления, которая гласит, что если G непрерывна на ь интервале [a, b], то интеграл Римана ^ G( x )d x сущеста вует. Ввиду этого соотношения естественно, что дока­ зательство теоремы 9.2 весьма похоже на доказательство соответствующей теоремы для интеграла Римана, хотя и несколько сложнее. Доказательство теоремы 9.2 мы дадим полностью, но опустим доказательства других теорем, аналогичных соответствующим теоремам относи­ тельно интегралов Римана .

Введем некоторые дополнительные обозначения, кото­ рые будут применяться в доказательстве теоремы 9.2 и некоторых вспомогательных лемм. Мы принимаем везде, что Д, Д,, Д2 и т. д. суть ^разбиения интервала [а, b], G непрерывна на [а, Ъ и F —неубывающая на [а, Ъ] .

]

Мы определяем:

M h — max G (x),

–  –  –

З а м е ч а н и е 9.24. При доказательстве этой теоремы мы применим обозначение, введенное перед леммой 9.4, конкретизируя его для случая, когда интервал [а, Ъ] совпадает с отрезком [0, 1]. Мы используем также сле­ дующую лемму, доказательство которой не представляет труда и здесь не приводится (см. упражнение 5 главы VIII) .

Л е м м а 9.25 .

Если F — функция распределения и — положительное число, то существуют точки 0 = жо х 1... х п_г х п = 19 непрерывна при х і ( і = 1,..., n — 1) и такие, что F (і==1 ••• л)Д о к а з а т е л ь с т в о т е о р е м ы 9.23. Пусть задано положительное число 8, и пусть —положительное число, такое, что если Ax —любое разбиение интервала [0, 1], для которого II К то S Al — $Ді е. Выберем разбие­, ние Д интервала [0, 1], для которого | | Д | | 0 и такое, что точки х 0, х..., хп, образующие разбиение Д (за исключением, быть может, х 0 и хп), суть точки непре­ рывности функции F (лемма гарантирует нам, что такое разбиение существует) .

Поскольку последовательность F t (xt) (t = 1, 2,... ) сходится к F (х{) для любого г, то отсюда следует, что существует целое Т, такое, что если 7 \ то

–  –  –

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

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

О п р е д е л е н и е 9.26. Пусть / ’ —функция, опреде­ ленная в интервале [a — h, а], где h —положительное число. Предположим, что для всякой убывающей после­ довательности е е2,...

неотрицательных чисел, стремя­ щихся к нулю при п оо, для которых e j C /г, мы имеем:

Тогда мы говорим, что с есть производная функции F в точке а слева .

Аналогично, пусть F определена в интервале [а, а + /г], где h —любое положительное число, и пусть для всякой убывающей последовательности ех, е2,...

неотрицатель­ ных чисел, стремящихся к нулю, для которых ех/г, мы имеем:

Тогда мы говорим, что d есть производная функции F в точке а справа. Очевидно, если производная функции F в точке а существует, то существуют обе односторонние производные, равные этой производной. Обратно, если обе односторонние производные существуют и равны между собой, то и обычная производная функции F также существует. Поскольку функция распределения неубы­ вающая, она не может иметь отрицательной производной ни слева, UffiT'справа .

206 ГЛ. IX. ИНТЕГРАЛ СТИЛТЬЕСА

–  –  –

F (0) = 0 .

Покажите, что при а = 0 функция F не имеет ни одной односто­ ?

ронней производной .

13. Постройте функцию, которая имела бы при произ­ водную справа, но не имела бы производной слева .

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

Предположим, что М есть платежная функция непре­ рывной игры, и пусть Р х выбирает х из [0, 1] согласно функции распределения F, а Р2 выбирает у из [0, 1] согласно функции распределения G. Тогда для любого заданного у математическое ожидание выигрыша у игро­ ка Р г будет i J М ( х, у) dF (х),

–  –  –

оба существуют, то, как можно убедиться (путем рас­ суждения, аналогичного использованному в главе I в связи с прямоугольными играми), Р г может выбрать функцию распределения так, чтобы быть уверенным, что он полу­ чит по меньшей мере и а Р2 может выбрать такую функцию распределения, которая воспрепятствует игроку Р г получить больше чем 2. Если г и 2 равны, то P может получить в точности г ( = 2) и не может надеяться получить больше, если только Р 2 не совершает глупостей .

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

Когда величины г и 2 существуют и равны между собою, мы называем их общее значение ценой игры (для і \ ). В этом случае, как было показано в теореме 1.5, существует седловая точка і|/?оіі ФУНКЦИИ E ( F, G), то есть имеется пара функций распределения F Q и GQ таких, что для всех функций распределения F и G Е (F, G0) E ( F 0, G0) E ( F 0, G) .

Такая F0 или такая G0 называется оптимальной смешанной стратегией соответственно для Р г или Р 2 .

Мы называем иногда упорядоченную пару Ц/ ^оІІ опти­ мальных стратегий обоих игроков решением игры .

–  –  –

аналогично .

Остается показать, что [х =.

Если О есть любой эле­ мент множества D, то из (1) и (2) мы видим, что число Xq удовлетворяет следующему условию:

i i ^ M (xG, у) dG (у) = max ^ М (х, у) dG (у) =

–  –  –

4. Способы вычисления и проверки решений Хотя мы теперь уверены в том, что непрерывные игры с непрерывными платежными функциями имеют решения (то есть имеют цены и оптимальные стратегии), у нас еще нет никакого способа вычисления решений для заданных платежных функций. Это вообще трудная задача, так как для ее решения нужно найти максималь­ ное значение интеграла Стилтьеса относительно множе­ ства всех функций распределения. Вполне общих мето­ дов решения этой задачи у нас нет, но в следующих двух главах мы рассмотрим два частных случая, в кото­ рых можно найти решения .

Докажем некоторые теоремы, с помощью которых можно решить, являются ли данные стратегии действи­ тельно оптимальными .

Т е о р МялЛ0.5. Пусть М — непрерывная платежная функция непрерывной игры, и пусть F Q и G0— функции распределения.

Тогда имеют место следуюгцие равносиль­ ные условия:

1) F 0 есть оптимальная стратегия для Pv a G0 есть оптимальная стратегия для Р 2;

2) если F и G — любые функции распределения, то ii

–  –  –

Д о к а з а т е л ь с т в о. Равносильность условий (1) и (2) следует прямо из теоремы 10.4 и йз определения седловой точки. Чтобы убедиться в том, что из условия (2) вытекает условие (3), мы берем F (х) = І х (х) и G (у) = I w\y) и применяем теорему 9.20.

Чтобы убедиться в том, что из условия (3) вытекает условие (2), предположим, что для всех z и w в [0, 1] мы имеем:

11 .

о

–  –  –

М { х, у) dF0 (x) dG0(y) .

Оо Аналогичным образом мы можем получить вторую часть неравенства (2) из второй части неравенства (3), что завершает доказательство .

Т е о р е м а 10.6. Пусть М — непрерывная платежная функция непрерывной игры, цена которой равна. Функ­ ция распределения F 0 есть оптимальная стратегия для первого игрока тогда и только тогда, когда для всякого у из [0, 1]

–  –  –

а последнее, очевидно, выполняется для всех у из [0, 1] .

Аналогичным образом, умножая обе части неравен­ ства (33) на произведение знаменателей входящих в него дробей (это произведение положительно) и производя очевидные упрощения, приходим к равносильному нера­ венству 84 — 163-f 14я2 —6х + 1 О, которое можно также записать так:

(2х - I)2 [х2 + (# — I)2] 0 .

Поскольку последнее неравенство, очевидно, имеет место для всех х, мы заключаем, что (33) выполняется и, следовательно, предложенные величины действительно представляют решение данной игры .

Т е о р е м а 10.9. Пусть М —непрерывная платежная функция непрерывной игры, цена которой равна, и пусть F0 и G0 —оптимальные стратегии соответ­ ственно для первого и второго игрока. Если мы положим і Н ( х ) = \ м ( х, у) dG0 (у) и К ( у ) = J М ( х, у) dF0 (х),

–  –  –

Доказательство остальной части теоремы аналогично .

Следующий пример указывает достаточно общий метод действительного нахождения решения данной игры. Метод состоит в основном в том, что пытаются найти решение данного 'ВВДа (в нашем случае в виде ступенчатых функ­ ций). Если метод не дает решения данной формы, мц можем продолжать пробовать функции другого вида (например, ступенчатые функции с большим числом ступеней) .

П р и м е р 10.11 .

Дана платежная функция непрерыв­ ной игры М ( х, у ) = ----- --- -------- .

1+ 4- (*—У)2 Мы хотим найти оптимальные стратегии обоих игроков в виде F0 (x) = I a (x), ) e!w -p.w + (i-B /.w.} (34)

Допуская, что имеется решение вида (34), мы получим:

і і

–  –  –

(52) Теперь легко проверить, как в примере 10.12, что (52) действительно есть решение данной игры .

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

Платежная функция непрерывной игры М такова:

м (х, у) = X — у + ху для X у, М ( х, у ) —0 для х = у, М (х, у) = X — у - ху для X у .

Мы хотим найти непрерывную оптимальную стратегию F0 для первого игрока, удовлетворяющую следующим усло­ виям:

F0 (x) = 0 для 0 я а, (53) F0 (х) дважды дифференцируема при х Ф а, (54)

–  –  –

Итак, если имеется какая-либо оптимальная стратегия, удовлетворяющая условиям (53), (54) и (55), то решение игры определяется следующими равенствами:

= 0,

–  –  –

(» * ) .

О G.()-|- T Проверим теперь, что равенства (67) действительно дают решение, то есть покажем, что если F я G суть любые функции распределения, то Jf, G 0) E ( F 0, G 0) E ( F 0, G) (68) e E ( F o, G o) = 0. (69) Легко убедиться, что (69) справедливо; легко также по­ казать, что (68) справедливо для всех функций распре­ деления, непрерывных в интервале (0, 1]. Но из того, что М (х, у) разрывна при х = у Ф 0, мы видим, что ве­ личины Е (F, G0) и Е (F 0, G) не существуют, если F и G имеют разрывы в полуоткрытом интервале (0, 1] .

Следовательно, в силу определения интеграла Стилтьеса неравенства (68) не имеют смысла, если F и G имеют разрывы в (0, 1], поэтому мы можем лишь сказать, что неравенству (68) удовлетворяют все функции распределе­ ния F и G, непрерывные в (0, 1]. Однако мы можем устранить это затруднение, обобщив наше определение интеграла Стилтьеса, а именно, введя понятие интеграла Лебега — Стилтьеса, который связан с интегралом Стилтьеса (иногда называемым интегралом Римана — Стилтьеса) при­ мерно так же, как интеграл Лебега связан с интегралом

Римана. Если мы положим:

ii E ( F, G ) = \ ^ M (x, у) d F (x) dG (у), Оо где интегралы понимаются в смысле Лебега — Стилтьеса, то неравенство (68) имеет смысл и справедливо для всех функций F и G, даже для разрывных .

В этой книге кы не будем вводить интегралы Лебе­ га — Стилтьеса, потому что для изложения надлежащей теории этих интегралов необходимо основательное зна­ комство с другими разделами математики.

Но и не вводя это понятие, мы можем сказать, что данные функции распределения представляют оптимальные стратегии для обоих игроков в том смысле, что для всякого x и у из [О, 1] мы имеем:

Е (х, Go) Е (F о, G0) Е (F 0, у) .

З а м е ч а н и е 10.16. В примере 10.15 нам удалось найти решение непрерывной игры с разрывной платеж­ ной функцией. Таким образом, оказывается, что теорему

10.4 можно обобщить так, чтобы охватить некоторые разрывные функции. В математической литературе можно найти подобные примеры, но мы не собираемся их при­ водить. Следует лишь отметить, что можно интуитивно прийти к обобщению теоремы 10.4. Пусть имеется игра Г, платежная функция М которой не непрерывна; суще­ ствуют функции и Ф, взаимно однозначно отобража­ ющие интервал [0, 1] на себя, и функция М ' ( х, у) = М (©(*), Ф( у ) ) непрерывна. Поскольку M ' непрерывна, то игра Г', имею­ щая платежную функцию М \ имеет решение. Но так как Г получается из Г' путем переименования х и у, мы видим, что игра Г также имеет решение .

Итак, пусть имеется игра, у которой разрывная пла­ тежная функция М определена следующим образом:

для 0 а; у и 0 у у, (*-г/)2 для 0 Ж у и у у, М (х, у) = для у х и 0 у у, (*+»-г )’ (х-у)а для у X и у у .

<

–  –  –

Для последующих ссылок мы включим две теоремы, ко­ торые будут использованы в главе X I. Доказательства этих теорем мы оставляем в качестве упражнений .

Т е о р е м а 10.20. Лю бая вы пуклая линейн ая комби­ нация опт имальны х ст ратегий есть опт имальная стра­ тегия .

Т е о р е м а 10.21'. Е сли F v F......... • • • последовательность оптимальных ст рат егий, которая сходится к ф ункции распределения F во всякой точке непрерывности ф ункции F, то F есть опт имальная ст ратегия .

–  –  –

для всякой функции распределения G, и не имеет значе­ ния, применяет ли Р г стратегию F или стратегию F .

Поэтому, когда два данных вектора одинаковы, мы будем называть стратегии Р І и F i2) эквивалентными (конечно, относительно данной игры). Таким образом, если имеется непрерывная игра, платежная функция которой удовле­ творяет уравнению (1), то, как мы видим, для Р г выбор смешанной стратегии F a) сводится к выбору точки I и[1,..., Um I из некоторого подмножества U т-мерного IУ евклидова пространства. Это множество U, которое мы будем иногда называть пространством U, состоит из всех точек I и..., ит I таких, что д л я некоторой функции распределения F (4) i Когда и == I и х... ит I и F удовлетворяет равенствам (4), I I мы говорим, что и я F соответствуют друг друг у (дан­ ная точка в пространстве U будет, вообще говоря, соот­ ветствовать различным функциям распределения) .

Аналогично, для Р 2 выбор смешанной стратегии Gcl) сводится к выбору точки I I... Wn} Il из множества, которое мы назовем пространством W, то есть из мно­ жества всех точек || w x... wn \\ n-мерного евклидова про­ странства таких, что для некоторой функции распреде­ ления о о Следует заметить, что множества U и W относятся к дан­ ному частному представлению платежной функции М .

Как мы видели раньше, одна и та же функция. М может удовлетворять как равенству м (x, у) = 2 X au ri (х ) si (у) .

і=і так и равенству М(Х, у ) = 2 rl ( x ) t i (y) .

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

До сих пор мы считали функцию математического ожидания выигрыша Е определенной только для функций распределения (в качестве аргументов). Однако для не­ которых дальнейших рассуждений уместно говорить также о математическом ожидании выигрыша игрока і \, когда Р г выбирает точку и из пространства U, а Р 2 выбирает точку w из пространства W.

Поэтому мы расширяем область определения функции Е следующим образом:

если гг — любая точка пространства U, a w — любая точка пространства W и если /" — любая функция распределе­ ния, соответствующая точке іг, a G — любая функция рас­ пределения, соответствующая точке w, то мы полагаем:

Е (гг, w) = E (F, G) .

–  –  –

где rt и s3 — непрерывные ф ункции соответственно от х и у. Тогда множество U* (по отношению к данному пред­ ставлению) состоит из всех точек || гг1..., ит ||, т аких, чт.о для некоторого t из [0, 1]

–  –  –

Доказательство второй части теоремы аналогично .

С л е д с т в и е 11.3. Множества U* и W* для любой разделимой игры суть ограниченные, замкнутые, связные множества .

Доказательство вытекает из того, что функции г. и Sj суть непрерывные функции, определенные на замкнутом интервале .

Т е о р е м а 11.4. П рост ранст во U д ля любой разде­ лимой игры есть вы пуклая оболочка множества хJ*, а про­ странство V f — вы пуклая оболочка множества W* (сле­ довательно, пространство U — и аналогично пространство W — есть замкнутое ограниченное выпуклое множество) .

Д о к а з а т е л ь с т в о. Пусть U' — выпуклая оболочка множества U*. Мы хотим показать, что U' совпа­ дает с пространством U, то есть U' = U. Поскольку U* CI U, мы видим непосредственно из теоремы 11.1, что U ' U. Поэтому остается лишь показать, что U C U ' .

Допустйзйгу^ то имеется точка z = || zx... zm ||, при­ надлежащая U, но не принадлежащая U '. Поскольку, согласно следствию 11.3, U* ограничено и замкнуто, мы видим, что U' также замкнуто и ограничено; кроме того, U' — выпуклое. Поскольку z = \\z1... zm \\ не находится в U ', то из теоремы 2.3 мы заключаем, что существуют постоянные а..., a m, b и, где 0, такие, что a lzl + • • • + a mz m Ь 0, (8 )

–  –  –

Поскольку и ^ \..., то имеются ступенчатые функции /*, I t n, такие, что (для г = 1,..., п) соответствует функции /*.. Тогда по теореме 11.1 мы ви­ дим, что функция /, определенная равенством

–  –  –

соответствует точке и. Очевидно, I есть ступенчатая функ­ ция, имеющая самое большее п ступеней, ж I ж F эквива­ лентны, поскольку обе функции соответствуют одной и той ж е точке пространства U .

В частности, любая оптимальная стратегия F (по тео­ реме 10.4 такая существует) эквивалентна ступенчатой функции /, имеющей самое большее ^ ступеней, и такая функция /, конечно, сама оптимальна .

Охарактеризуем теперь те точки пространств U и W, которые соответствуют оптимальным стратегиям. Для этого уместно определить отображение точек пространства U в множество точек пространства W и отображение точек пространства W в множество точек пространства U. Если гг — любая точка пространства U, то образом точки и мы будем называть множество точек до пространства W та­ ких, что Е ( и, до) = min.E (и, у), yew Будем обозначать образ точки и через W (и). Аналогично, если до — любая точка пространства W, то образом точки w мы будем называть множество всех точек и простран*« ства U таких, что Е ( и, до) = m axi? (я, до) .

жGU Образ точки до обозначим через Щдо) .

Если точка и пространства U и,точка до пространст­ ва W таковы, что ayW(w) и u U ( w ), то мы называем точку и фиксированной точкой пространства U, а точку до — фиксированной точкой пространства W .

Т е о р е м а 11.6. Е сли F — любая ф ункция распреде­ л ен и я и если и — соответствующая ей точка прост ран­ ст вах}, то F есть опт имальная ст рат егия д л я Р г тогда и только тогда, когда точка и ф иксированная. (Анало­ гично, функция распределения G есть оптимальная стра­ тегия для Р 2 тогда и только тогда, когда соответствую­ щая точка до пространства W есть фиксированная точка.) Д о к а з а т е л ь с т в о. Пусть F 1 — функция распреде­ ления, и пусть и — соответствующая ей точка простран­ ства U. Если говорится, что и есть фиксированная точка пространства U, то это значит, что для некоторой точки до пространства W мы имеем до W (и) и и U (до), то есть

–  –  –

Е (в, до) - m a x Е (х до), хеи = min Е (в, у), yew а это значит, что в^ІІ(до) и до^\ (в), что и требовалось доказать .

2. Пояснительный пример Доказанные нами теоремы достаточны для того, чтобы дать общий метод подхода к задаче отыскания решений для разделимых игр: а) мы чертим кривые U* и W* (соответственно в m-мерном и w-мерном пространствах) и определяем их выпуклые оболочки, каковыми по теореме

11.4 являются соответственно U и W; б) мы находим W (гг) для любой точки и U и U (w ) для любой точки w W (это равнозначно отысканию точек в некоторых замкнутых выпуклых множествах, где данные линейные формы принимают свои минимальные и максимальные значения); в) используя результаты пункта б), мы нахо­ дим фиксированные точки пространств U и W; г) мы представляем фиксированные точки как выпуклые линей­ ные комбинации точек множеств U* и W* соответствен­ но и с помощью теоремы 11.1 находим функции распре­ деления, которым соответствуют фиксированные точки. .

Эти функции распределения будут оптимальными страте­ гиями. Поясним этот метод на примере .

п Ри м е р 11.8 .

Платежная функция М разделимой игры определяется следующим равенством (для любой точки \\ ху I замкнутого единичного квадрата):

I

М (Ху у) = cos 2п х cos 2щ + х + уЗдесь мы примем:

гг (ж) = X, s; (у) = у, г2 (х) = cos 2itXy s2 (у) = cos 2пуу r3 {x) = 1, * з(2/) = 1 .

так что М представлена следующим образом: .

м {X, у) = Г2 (x) s2 (у) f (x ) ss (у) 4- r3 (x) st (y) .

Очевидно, пространство U лежит в плоскости м3 = 1, а пространство W —в плоскости w3 = 1. Начертим для про­ стоты двумерное изображение этих пространств .

Кривая U* выражается следующими параметрическими уравнениями:

U^ty Пространство И есть выпуклая оболочка кривой U*, пред­ ставляющая часть плоскости м3 = 1, ограниченную пря­ молинейными отрезками A B, АС и B D и дугой коси­ нусоиды CQD, как изображено на рис. 42 (на том же рисунке показано пространство W, которое тождественно пространству U) .

иг Шг

–  –  –

С л у ч а й л Ц ^ В этом случае мы опять находим, что W (a) = ||0 1 1 ||, используя по существу метод, применявшийся выше. Единственное различие состоит в том, что теперь прямые (21) имеют отрицательный наклон; но поскольку абсолютная величина этого наклона больше наклона т прямой А 'С ', то отсюда следует, как и рань­ ше, что если прямая проводится как можно левее, но так, чтобы она пересекала пространство W, то у нее будет лишь одна общая точка с пространством W — точ­ ка А ' .

С л у ч а й 2. В этом случае прямые (21) имеют все такой же наклон, как прямая А 'С ' .

Следовательно, к минимально, когда (21) совпадает с А 'С *. Очевидно, в этом случае W (а) состоит из всех точек прямолинейного отрезка А 'С ' .

С л у ч а й 3. В этом случае прямые (21) имеют отри­ цательный наклон, который по абсолютной величине меньше, чем наклон прямой А 'С ' .

Поэтому точка w = \\w 1 w 2 1 I в пространстве W, для которой к мини­ I мально, должна быть точкой касания кривой C 'Q ' с са­ мой нижней прямой семейства (21), еще пересекающей пространство W. Эта точка касания единственная, если а2 выбрано так, что имеет место случай 3. Следователь­ но, в этом случае W (а) состоит из одной точки кривой C 'D ', которая, очевидно, определяется выбором точки а .

Итак, мы показали, как находить образ W (а) всех то­ чек а, лежащих на правой границе Q D B пространства U .

Путем точно такого ж е анализа ^можно найти образ U (Ъ) любой точки; лежащей на левой границе A 'C 'Q ' пространства W. Приведем без доказательства следую­ щие результаты этого анализа .

Пусть 6 = 116! Ь2 1|| — точка левой границы A 'C 'Q ' пространства W. Если Ь2 0, то U (b) есть точка |j 1 1 1 1 | пространства U.

Еслц Ъ2 0, то мы имеем следующие условия:

1) Если наклон — прямых иг + Ь2и3 = к (22) меньше, чем наклон— m прямой D B, то U (6) — единст­ венная точка, лежащая на кривой QD границы прост­ ранства U .

2) Если наклон прямых (21) больше, чем — m, то U (b) есть точка В пространства U .

3) Если — у == — т, то U (Ь) есть весь прямолиней­ ный отрезок D B .

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

П режде всего мы замечаем, что A ' не есть фиксиро­ ванная точка, так как I ] ( А ' ) = В, и W (В) есть точка кривой C 'Q '. Следовательно, по теореме 11.7 никакая точка а пространства U, для которой W ( a ) = A ' y не мо­ жет быть фиксированной точкой .

Далее мы замечаем, что ни одна точка кривой C 'Q ' не есть фиксированная, ибо для любой такой точки b U (b) состоит из одной точки а на кривой Q D, a W (а) для любой точки а на кривой QD есть точка А \ Следо­ вательно, по теореме 11.7 никакая точка а пространства U, для которой U (а) есть точка кривой C 'Q \ не может быть фиксированной точкой. Это значит, что никакая точка а = \\ аг а2 1 1 отрезка D B, для которой | не может быть фиксированной точкой пространства U .

Из этого мы заключаем, что единственные фиксиро­ ванные точки пространства. U суть те точки, которые предусматриваются случаем 2, то есть те точки а, для которых

–  –  –

Решения этой системы, очевидно, такие: /? = ||0 0 || и q = || 0 Q||. Итак, первая критическая точка принадле­ жит множеству / ( UJ, а вторая — мнджеству / ( W ). Сле­ довательно, по теореме 11.16, р — единственная фикси­ рованная точка пространства U, a q — единственная фик­ сированная точка пространства W .

Таким образом, задача отыскания решений данной «гры сводится к. задаче отыскания функций распреде­ ления, которым соответствует точка ||0 0 ||. Чтобы най­ ти конкретную оптимальную стратегию для Р 19 мы за­ мечаем, что точка у 0 0 I есть выпуклая линейная ком­ I бинация двух точек II1 0 I и (| — 1 0 1|. Действительно, I

–  –  –

Обобщая это рассуждение, мы находим, что наиболее общий вид функции распределения с двумя ступенями, соответствующей точке ||0 0 || пространства U, такой:

–  –  –

где ах, а2 и аз определяются уравнениями (35), есть оптимальная стратегия для Р г .

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

–  –  –

Первая и вторая критические точки суть ||0 0 ||. По­ скольку начало координат не лежит ни в пространстве U, ни в пространстве W, мы видим из следствия 11.15, что фиксированные точки пространств U и W находятся на границе. Далее, граница пространства U есть окружность (Иі — 1)* + (и« — Если бы U содержало две различные фиксированные точки (которые обе должны были бы лежать на этой окружности), то по теореме 11.9 все точки хорды, соеди­ няющей эти фиксированные точки, также были бы фиксированными. Это противоречило бы утверждению, что всякая фиксированная точка пространства U лежит на границе U. Поэтому пространство U содержит лишь одну фиксированную точку. Аналогично пространство W содержит тоже лишь одну фиксированную точку .

Поскольку в этом примере U* совпадает с ( U ), мы заключаем, что существуют оптимальные чистые стра­ тегии для первого и второго игроков, то есть игра имеет седловую точку .

Следующий пример показывает, что когда В (U) и В (W) содержат прямолинейные отрезки, то может быть бесконечное число фиксированных точек — если даж е пер­ вая критическая точка не принадлежит пространству U, а вторая — пространству W .

П р и м е Р'^44.21.

Платежная функция разделимой игры удовлетворяет (для любой точки \\х у || замкнутого единичного квадрата) следующему равенству:

М (x, у) = 5 [2 + cos я (1 + х)] [sin ny] -f + 2 [sin я (1 + x)] [ — 2 4- cos ny] + [sin я (1 + )] [sin ny] .

Положив г г (x) = 2 - f cos я (1 - f x), () = — 2 -f cos яг/, r2 (ж) = sin я (1 + x), s2 (y) = sin яу, мы имеем:

M (х,у) = 5гг (x) s 2 (г/) + 2r2 (x ) sx(y) + r2 (x) s 2 (у), и отсюда Е (и, ) = Kja + 2и2г + и22 .

И первая, и вторая критические точки суть ||0 0 ||. Мы легко можем убедиться в том, что пространства U и W изображаются заштрихованными областями соответствен­ но на рис. 45 и на рис. 46. Далее, всякая точка отрезка A B есть фиксированная точка пространства U, а всякая фиксированная точка отрезка А 'В ' есть фиксированная точка пространства W .

Рис. 46. Рис. 45 .

В примере 11.20 мы видели, как можно использовать следствие 11 15 для разбора некоторых игр, в которых ни одно из пространств U или W не содержит в себе, своих критических точек. Следующий пример поясняет, как можно использовать это следствие для исследования игр, у которых одна критическая точка лежит в соот­ ветствующем ей пространстве, а другая не лежит .

П р и м е р 11.22 .

Платежная функция М разделимой игры (для любой точки Иод И замкнутого единичного квадрата) удовлетворяет следующему равенству:

M (x, у) ~ 3[cos 2пх] [2 + со 8 2 я у ]+ 5 [cos 2пх] [2 + sin 2яу] + + 2 [sin 2пх] [2 + cos 2mj] + [sin 2пх] [2 + sin 2яу] .

Положив (х) = cos 2яя, $х (у) = 2 + cos 2яг/, (я) = sin 2яя, s2 (у) = 2 + sin 2яу, мы можем легко убедиться*, что пространство U пред­ ставляет окружность и\ + и\ = 1 вместе с ее внутренней частью, а пространство W пред­ ставляет окружность (а»1- 2)* + ( а ;, - 2)* = 1 вместе с ее внутренней частью. В этом случае крити­ ческая точка есть ||0 0 1|. Эта точка не находится в W, но лежит внутри пространства U .

Поскольку вторая критическая точка не принадлежит пространству W, то на основании следствия 11.15 мы видим, что фиксированные точки пространства U нахо­ дятся только в (U). При помощи рассуждения, анало­ гичного тем, которые мы применяли для этой цели в примере 11.20, мы докажем, что в U есть лишь одна фиксированная точка, скажем, гг*. Но если бы в I (W) находилась фиксированная точка пространства W, то по теореме 11.14 первая критическая точка )|0 0|| была бы фиксированной точкой пространства U. Это противоречит утверждению, что единственная фиксированная точка пространства U лежит в ( U ). Следовательно, фиксиро­ ванные точки пространства W должны лежать только в В (W); а поскольку W есть круг, мы заключаем (опять при помощи таких же рассуждений, как в примере 11.20), что в W имеется лишь одна фиксированная точка. Итак, мы видим, как и в примере 11.20, что игра имеет седловую точку .

5. Решение прямоугольной игры как разделимой игры

–  –  –

С помощью этих таблиц мы можем определить, какие точки пространств U и W суть фиксированные и, следо­ вательно, какие точки являются оптимальными страте­ гиями для Р г и для Р 2. Например, мы замечаем, что ни одна точка области не является фиксированной точ­ кой, ибо W (гг) = || 0 0 ||, тогда как U (|| 0 0||) = ||0 1 1|, и эти точки принадлежат области U 2, а не U r Подобно этому мы м^щем показать, что ни одна точка областей U2, U3 и U4 не является фиксированной. Рассмотрим теперь область U 5. Для нее мы имеем W (и) = || а 0 || .

Полагаем д о = | | а 0 ||, тогда

–  –  –

Цена игры равна 1 .

6. Решение игры с ограничениями как разделимой игры Предположим, что смешанные стратегии прямоуголь­ ной игры должны удовлетворять некоторым дополнитель­ ным линейным неравенствам, помимо тех, которые опре­ деляют смешанную стратегию; тогда мы имеем игру с ограничениям и. Такие игры встречаются часто в мате­ матической статистике (см. главу XIII), когда рассма­ триваются задачи статистического решения как игры между статистиком и природой, ибо статистик обычно имеет в памяти достаточно опытных данных относительно прошлого поведения природы в данной области, чтобы суметь по крайней мере установить верхние и нижние границы для частот ожидаемых явлений .

Дополнительные линейные неравенства в игре с огра­ ничениями приводят к тому, что пространство U и про­ странство W изменяются, но они по-прежнему остаются замкнутыми, ограниченными и выпуклыми. Платежная функция, конечно, остается неизменной и, в частности, билинейной. Поэтому можно применять методы, исполь­ зуемые для разделимых игр .

–  –  –

Мы можем решать игру путем исследования фикси­ рованных точек. Например, рассмотрим игру, разобран­ ную в предыдущем параграфе.

Допустим, что мы нала­ гаем следующие дополнительные линейные ограничения на смешанные стратегии:

–  –  –

Цена игры равна —-g- .

Библиографические замечания Эта глава основана в большой степени на выводах, приведенных в работах Дрешера, Карлина и Шепли [35] и Дрешера и Карлина [34], а также на некоторых част­ ных сообщениях Дрешера. См. также работу Дрешера [32] .

–  –  –

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

Функция / действительной переменной называется выпуклой в интервале (a, b)t если для всякого элемента II % 1 множества S2 и для любой пары различных чисел 2| х х и х 2 интервала (a, b) мы имеем:

/ (^і#і + ^2^2) ^ / (х і) + ^2/ (#2)* Если для ^ ^ 0 Д 2 ^ 0 всегда имеет место лишь строгое неравенство, то функция / называется строго вы пуклой .

Чтобы понять геометрический смысл понятия выпук­ лости, рассмотрим график на рис. 49 .

Поскольку абсцисса точки Р г равна х ордйната кри­ вой в точке Р г равна / ( х х), то есть P 1A = f ( x 1) .

Аналогично Р%С — / (х2) и QD = / (%1 1 + % 2) .

х 2х Поскольку a ^ f c c a точки Q равна ^Зж1 + Х2ж2, очевидно, Q делит отрезок Р гР 2 в отношении : Х2; кроме того, поскольку числа ^ и оба положительны, Q лежит между Р х и Р 2. На основании подобия треугольников мы заключаем, что В делит АС в отношении : Х2 и, следовательно, QB = (хг) + X2f (я2) • Итак, из неравенства, определяющего выпуклую функ­ цию, вытекает, что QDQB, то есть график функции не может лежать выше прямо­ линейного отрезка, соединяющего ліббые две точки гра­ фика. Функция является строго выпуклой, если график функции всегда лежит ниж е данного прямолинейного отрезка .

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

Следующие функции выпуклы в ин­ тервале ( — оо, + о о ), то есть во всяком конечном интер­ вале:

x 4, 3 — 7х + х 2, ех, е~х у \ х\ .

Все эти функции, за исключением последней, строго выпуклые .

Очевидно, могут быть функции, выпуклые лишь в некоторых интервалах. Например, функция sin # выпукла в интервале ( — я, 0), но она не является выпук­ лой в интервале (0, я) .

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

Так, например, функция /, определенная условиями:

/ (я) = 2 + (я + 4)г ( ж 0 ), f ( x ) = 2 + (х — 4)а (х 0), не имеет второй производной (и даже первой при ж = 0), но легко проверить, что эта функция строго выпуклая в интервале ( — от, + от) .

Если у функции двух переменных одна переменная фиксирована, то мы получаем функцию одной перемен­ ной, и эта функция может оказаться выпуклой (или строго выпуклой); так, функция f ( x, у) = Ъхг — І 0 у г строго выпуклая по х для любого у у так как но она не выпуклая по у для любого х, так как

–  –  –

Как и в случае функции одной переменной, мы назы­ ваем функцию / строго вы пуклой, если при Ф О, % Ф О имеет место строгое неравенство .

Это понятие выпуклости не сводится к понятию выпуклости по каждой переменной в отдельности. Так, функция f ( x, у) может быть выпуклой по х Для любого у и выпуклой по у для любого х у -не будучи выпуклой по двум переменным одновременно. Например, функция / (х х 2) = ХІ + ХІ — 3XjX2 + 1 есть выпуклая функция по х г для любого х 2 и выпуклая функция по х 2 для любого х но она не является выпук­ лой функцией по х г и х 2 одновременно, в чем легко убедиться, если взять Х1 — І 2 — -2 || х і х ъ || = || — 1 — 1 I и К I I Уі Уа I = I I 1 1 IIВ некотором смысле обратным понятию выпуклости является понятие вогнутости. Функция / называется во­ гн ут о й, если функция — / выпуклая. Можно также гово­ рить о вогнутости по нескольким переменным, строгой вогнутости и т. д. Свойства вогнутости легко вывести из соответствующих *свойств выпуклости .

Л е м м а 12.1 .

П уст ь ф ункция / непрерывна и строго выпукла в замкнутом инт ервале. Тогда / принимает минимальное значение в одной и только в одной точке инт ервала .

Д о к а з а т е л ь с т в о. Поскольку / непрерывна, она принимает минимальное значение по меньшей мере в одной точке интервала.

Но если / принимает минимальное зна­ чение в двух различных точках а и Ь, то мы должны иметь в силу строгой выпуклости функции:

f(нг) i f'а+i f(b =i f{a +i f{a =f{a {) ) ) ) )’ что противоречит тому условию, что в точке а дости­ гается минимум,

2. Единственная стратегия для одного игрока Обратимся теперь к рассмотрению непрерывных игр, у которых платежные функции выпуклы для игрока, добивающегося минимума платежа .

Т е о р е м а 12.2. П уст ь М (х, у) — плат еж ная ф унк­ ция непрерывной игры, непрерывная по двум переменным и строго вы пуклая по у для любого х. Тогда имеется единственная опт им альная ст рат егия д ля второго игро­ ка, являю щ аяся ступенчатой функцией первого порядка, то есть имеется число c [0, 1] такое, что единственной оптимальной стратегией для второго игрока являет ся ст упенчат ая ф ункция / с. Ц ена игры определяется фор­ мулой

–  –  –

Из непрерывности функции М можно легко вывести, что ф есть непрерывная функция от у.

В самом деле, если М непрерывна, то для всякого г имеется такое, что для J г/і — г/2 I ^ м ы и м е е м :

–  –  –

Поскольку мы ограничиваемся функциями, определен­ ными на замкнутом единичном квадрате (0 х 1, 0 у 1), то производные М ш (0, у), М а} (1, у ), М (2) (х 0) и М (2) (x, 1), согласно этим определениям, не имели бы смысла. Поэтому под М (1) (0, у) мы будем подразумевать предел выражения (4), когда z принимает лить положи­ тельные значения, а под М с1)( 1, у) мы будем подразу­ мевать предел этого выражения, когда z принимает лишь отрицательные значения. Аналогично определяются М Ц х, 0) и М ™ (х, 1) .

Т е о р е м а 12.5. Пусть М — платежная функция непрерывной игры, непрерывная по двум переменным;

М (2) (x, ?/) существует для любых х и у в единичном квадрате и М (х, у) строго выпукла по у для любого х .

П уст ь Іу — единственная оптимальная стратегия для у0 = 0 или г/0 = 1, второго игрока, и — цена игры .

т оу первого игрока имеется оптимальная стратегия І х^у где константой x Q может быть любое число, удовлетворяю­ щее условиям:

0 х^ ^ 1,

–  –  –

Тогда для всякого x [0, 1] существует положительное е такое, что м {х, у) V для 0 у е. (8) Для каждого х мы определяем 8 (х) как верхнюю грань всех чисел е, удовлетворяющих неравенству* (7). Из непрерывности функции М следует непрерывность функ­ ции 8 (ж) по x в замкнутом интервале [0, 1]; кроме то­ го, 8 (х) всегда положительна и, следовательно, имеет положительный минимум. Пусть е0 0 — мицимальное 20 д*к. Мак-Кинер значение г( х ). Если мы выберем у х так, что 0 у х е0, то max М (х, у г), 0зс1

–  –  –

есть оптимальная стратегия для первого игрока. Из того, что функция М (x, у) непрерывна по у для любо­ го x, мы Зсщщочаем, что функция g (У) = аМ (х у) + (1 - а) М (х2, у) выпукла по у. Кроме того, из уравнения (15) мы видим, что производная функции g (у) равна нулю при г/ = у0 .

Следовательно, g (у) принимает минимальное значение в точке у 0.

Итак, поскольку на основании (13) и (14) мы имеем:

ёІУо) = а М К - У0) + ( і - а ) М ( Х ъ, у 0) = а + ( і - а ) =,

–  –  –

4. Замечания и примеры З а м е ч а н и е 12.7. Следует заметить, что оптималь­ ные стратегии, существование которых было установлено в двух предыдущих теоремах, не обязательно являются единственными. Так, например, пусть Функция М удовлетворяет условию теоремы 12.5, так что у первого игрока существует оптимальная стратегия вида

–  –  –

суть 0 и 1 и поскольку и то мы заключаем, что у г — 0 и г/2 = 1. Из уравнения ат со8[т(т+0)] +(1- а СТт(т+1)]=0 )т О мы заключаем далее, что а =. Поэтому оптимальной стратегией для второго игрока является функция рас­ пределения

–  –  –

1 6 ( т ) 6 - 3 ( т ) ж+а ; 2==й Мы сразу видим, что решение будет такое: #==0 и х = і .

Ввиду того, что М2(х, у) = дМ~ ^ ~ ~ = 96г/5 — Ъх, мы имеем:

Следовательно, применяя обозначения теоремы 12.5, мы можем взять = 0 и х2 = 1 .

Решая теперь уравнение аМ2 (0, - і ) + ( 1 - а ) А Г « ( і, | ) = 0, мы находим, что а = щ. Следовательно, оптимальной стратегией для первого игрока является функция рас­ пределения 211 г / \ i 32 г / \ ’ 243 0 (Ж) 243 i (ж) ' З а м е ч а н и е 12.10. Мы сформулировали теоремы о выпуклых функциях в довольно слабой и частной фор­ ме из тех лишь соображений, чтобы избежать слишком сложных доказательств. Положения, установленные в этой главе, можно усилить и обобщить в нескольких напра­ влениях .

Во-первых, можно опустить в теоремах 12.5 и 12.6 условие существования производных. Но в этом случае нужно использовать то положение, что выпуклая или вогнутая функция всегда имеет обе односторонние производ­ ные в каждой точке интервала определения функции, за исключением, быть может, конечного числа точек .

Тогда условия, наложенные в заключительных предло­ жениях этих теорем на М М (х0, г/х), (ж0, г/2), М2(хг, у 0) и М (2(х2, у0), заменяются соответствующими условиями для односторонних производных в указанных точках .

Во-вторых, условие строгой выпуклости или строгой вогнутости платёжной функции можно ослабить, заменив условием, что она соответственно просто выпукла или вогнута. Но в этом случае оптимальная стратегия для второго игрока, указанная в теореме 12.2 (или для пер­ вого игрока в теореме 12.3), вообще уже не является единственной .

Наконец, выводы могут быть распространены на слу­ чай, когда игроки вместо того, чтобы выбирать просто числа из замкнутого единичного интервала, выбирают точки из n-мерного единичного куба. В этом случае необ­ ходимо применять более общее понятие выпуклости (выпуклости по нескольким переменным) .

Библиографические замечания Теоремы, доказанные в этой главе, являются част­ ными случаями более общих теорем, доказательства которых можно найти в работе Боненблуста, Карлина и Шепли [11] .

У пражнения

1. Приведите пример функции, строго выпуклой в интервале ( — оо, + о о ), но не имеющей производной в точках а?=0, х = 1 и х — 2 .

2. Приведите пример функции / двух переменных такой, что f ( x, у) вогнута по х для любого у и вогнута по у для любого х 1 но не является вогнутой одновременно по совокупности х и у .

3. Покажите, что если функция / непрерывна и строго вогну­ та в замкнутом интервале, то имеется одна и только одна точка интервала, в которой функция принимает свое максимальное зна­ чение .

4. Покажите, что сумма двух выпуклых функций выпукла, а произведение двух выпуклых функций не обязательно выпукло .

5. Платежная функция непрерывной игры есть М ( х, 2/) = sin (2х + у) Найдите цену игры и оптимальные стратегии для обоих игроков .

6. Решите уравнение 5 главы XI способами, изложенными в настоящей главе .

7. Платежная функция непрерывной игры есть М ( х, i/) == 80г/8— Ьху-\-х* .

Найдите цену игры и оптимальные стратегии для обоих игроков .

8. Платежная функция непрерывной игры есть М ( х, у) = Л г/10— 4жг/ я6, где А — число, удовлетворяющее неравенствам °лтНайдите цену игры и оптимальные стратегии для обоих игро­ ков (конечно, некоторые ответы могут быть выражены через пара­ метр А) .

9. Докажите следующую теорему:

Пусть М ( х, у), M i (я, у), М 2 (я, У), • • • непрерывны на единич­ ном квадрате и I М п ( x, у ) — M (x, у) I

–  –  –

строго выпукла по у для любого х .

И. Покажите (используя выводы упражнений 9 и 10), как можно усилить теоремы 12.2 и 12.5, заменив слова «строго выпуклые» словом «выпуклые» .

12. Покажите, что функция, выпуклая в открытом интервале, непрерывна, и приведите пример функции, выпуклой в замкнутом интервале, но имеющей разрыв .

13. Покажите, что выпуклая функция имеет обе односторон­ ние производные (не обязательно равные) в любой точке интер­ вала определения, за исключением, быть может, конечного числа точек .

14. Сформулируйте и докажите (исполвяуя выводы упражне­ ния 13) обобщение теоремы 12.5, в котором не предполагается существование производной М ^ (х, у) .

15. В некоторую игру играют следующим образом: первый игрок выбирает точку || х ± х 2 \\ из замкнутого единичного квадра­ та, а второй игрок, не зная выбора первого игрока, выбирает точку КУі у 2 Il из того же квадрата. При этом выигрыш первого игрока равен М (хъ хъ у г, у 2), где функция M (хъ х 2, у І9 у 2) строго вогнута по || х х х2 \\ для любых I Уі у 2 \\ и строго выпукла по || у^ у 2 \\ для любых \ \ х1 х2 \\ .

I Покажите, что у каждого игрока имеется единственная чистая стратегия .

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

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

Подобные ситуации возникают, в частности, в стати­ стике, ибо статистик часто занимается задачами следую­ щего типа: добиться максимальной точности в опреде­ лении данн0#**етоимости; свести к минимуму стоимость определения какой-либо величины с данной точностью;

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

Связь теории игр со статистикой оказалась столь тес­ ной, что в последние годы математики-статистики уделили этому вопросу много внимания. Мы тем не менее не будем формулировать общие теоремы по этому вопросу, огра­ ничиваясь рассмотрением некоторых специфических при­ меров применения теории игр к статистическим задачам .

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

Обычно статистик сталкивается с задачей составле­ ния некоторой оценки большого класса предметов на основе исследования выборки. (Так, например, полити­ ческий деятель может попытаться предсказать исход приближающихся выборов на основании интервью с изби­ рателями.) Статистик обычно может увеличить надеж­ ность своей оценки, увеличив размер выборки; но прове­ дение большего числа испытаний связано с дополнитель­ ными расходами. Цоэтому перед статистиком встает во­ прос — какой величины выборку ему лучше всего взять .

В следующем примере приведена упрощенная идеализи­ рованная модель такой задачи .

П р и м е р 13.1 .

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

Статистик S должен определить, сколько там черных шаров. Если его предположение правильно, ему должно быть уплачено а; если его ответ отличается от правиль­ ного ответа на 1 (например, он указывает 1, когда в дей­ ствительности 2 черных шара, или указывает 2, когда в действительности 1 шар, и т. д.), то ему должно быть уплачено ; если его ответ отличается от правильного ответа на 2 (указывает 0, когда в действительности 2 шара, или наоборот), ему должно быть уплачено у. Мы полагаем, ч т о а р у ; н о мы не делаем никаких предположе­ ний о том, положительны эти величины или отрицательны .

Стоимость исследования одного шара для статистика равна В описываемом случае естественно предполо­ .

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

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

У S имеется восемь возможных способов составить предположение о количестве черных шаров (то есть у него восемь чистых стратегий):

I. Не делать испытаний и предположить, что оба шара черные .

И. Не делать испытаний и предположить, что один шар черный и один белый .

III. Не делать испытаний и предположить, что оба шара белые .

IV. Проверить один шар и предположить, что другой шар такого же цвета, что и проверенный .

V. Проверить один шар и независимо от того, какого он цвета, предположить, что другой шар черный .

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

VII. Проверить один шар и предположить, что другой шар противоположного цвета .

VIII. Проверить оба шара и объявить правильное число черных шаров (которое, конечно, теперь известно) .

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

Далее, у природы имеются три возможности: нет ни одного черного шара, один шар черный и оба шара чер­ ные. Мы обозначаем эти стратегии номерами 0, 1 и 2 .

Рассмотрим платеж статистику S при различных соче­ таниях этих стратегий .

Если &»*ц*именяет стратегию I, а природа применяет стратегию 0, то это значит, что S предполагает, что два шара черные, а в действительности нет ни одного черного шара. Таким образом, S ошибается на два, и ему упла­ чивается у. Аналогичные простые рассуждения позво­ ляют нам учесть все случаи, когда S применяет страте­ гии I, И, III или VIII, и случаи, когда природа приме­ няет стратегию 0 или стратегию 2 .

# Чтобы понять, как вычисляется платеж в других слу­ чаях, допустим, например, что S применяет стратегию V, а природа — стратегию 1. Тогда, если S делает одно испытание, вероятность того, что испытываемый шар будет черным (как и вероятность того, что он будет бе­ лым), равна 2. Если он черный, то, поскольку S приме­ няет стратегию V, он предполагает, что оба шара черные, и, следовательно, ошибается на 1; итак, платеж в этом случае, с учетом стоимости проведения испытания, будет равен — Если же испытываемый шар оказывается .

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

Итак, математическое ожидание выигрыша для S равно

–  –  –

Следовательно, если 2а f 2 4а —8, то есть если у ( а — ), то S должен проверить оба шара; если —(а —), ему не следует проводить никаких испы­ таний, но просто предположить, что один шар черный и один шар белый. Этот способ для матриц 2 и 3 при­ водит к такому же ответу, как и теоретико-игровой под­ ход, а в случае матрицы 4 —к другому ответу. В по­ следнем случае «довод от незнания» предписывает игроку S всегда применять стратегию II. В этом случае, если природа действительно применяет смешанную стратегию Т ~ Т ’ ^ получит 50, то есть больше 25, которые он может себе гарантировать, применяя смешанную стра­ тегию 0 у 0 | 0 0 0 0 но следует заметить, что применяя исключительно стратегию II, S не может га~ рантировать себе даже 25, так как при этом, если при­ рода будет применять стратегию || 1 0 0||, он может надеяться получить лишь 0. Итак, оказывается, что в этом случае «довод от незнания» не дает для S такой же надежной стратегии, как стратегия, основанная на теории игр .

З а м е ч а н и е 13.3. Хотя мы рассмотрели пример 13.1 как обычную игру двух лиц с нулевой суммой, нужно помнить, что природа на самом деле не является созна­ тельным разумным существом. Когда игрок S применяет свою оптимальную стратегию для этой игры, он просто устанавливает нижнюю грань математического ожидания своего выигрыша; он может сознавать, что для него разумно поступать таким образом, но это не значит, что он считает природу недоброжелательным разумным существом. Его положение несколько походит на поло­ жение человека, который хочет поместить свои капиталы так, чтобы не оказаться банкротом ни от инфляции, ни от дефляции. Это не означает, что он непременно думает, что рынок будет всегда меняться наиболее неблагоприятпым цля него образом; но если он не в состоянии пред­ сказать сколько-нибудь точно движение цен, он, возможно, захочет должным образом подготовиться к любой случай­ ности .

Таким образом, если Ах — множество смешанных стра­ тегий, имеющихся у S, а А2— множество смешанных стра­ тегий, имеющихся у природы, то S может вычислить величину і = шах min Е (|, г|), ІЕАі тіеАз где Е — математическое ожидание выигрыша; и, возможно, если он осторожен, он захочет поступать так, чтобы не­ пременно получить Его не очень интересует величина 2 = min max Е (g, tj), T a S6Ai ieA и он не особенно стремится к тому, чтобы 2 = г .

Это замечание находит практическое применение в том случае, когда S имеет некоторые сведения относительно возможных смешанных стратегий природы и на основе этих сведений S может ограничиться рассмотрением лишь некоторого подмножества логически возможных смешан­ ных стратегий природы; так, он может знать, что любая применяемая природой смешанная стратегия || % т]2 т]3|| будет такой, что, например, 0 т ] ! - ^ - и или Л + Л + Лз = х - в этом случае перед нами игра с огра­ іа 2 ничениями, для которой теорема о минимаксе может быть неверной (как было показано, теорема вообще неверна, если множества стратегий, имеющихся у природы, не являются выпуклыми подмножествами евклидова простран­ ства). Все это не будет интересовать статистика, кото­ рый занимается лишь вопросом существования и значения величины max mini? (, ц) fcgAi Т16А2 (где, конечно, А2 означает теперь множество стратегий, которыми 4Щаничена природа на основании сведений, имеющихся у S), Обратимся теперь к примеру, поясняющему приме­ нение теории игр к контролю качества .

П р и м е р 13.4 .

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

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

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

Испытание состоит в следующем: А признает колесо удовлетворительным тогда и только тогда, когда каждая спица, подвергаемая испытанию, выдержит его .

Теперь перед М встает вопрос о том, испытывать не­ которые или все спицы, прежде чем принять колесо (то есть прежде чем передать его Л).

У него имеются четыре возможные линии поведения (четыре стратегии):

I. Принять колесо без испытания .

II. Выбрать наудачу одну из спиц и испытать ее .

Если спица удовлетворительна, принять колесо. Если она неудовлетворительна, забраковать .

III. Испытать выбранную наудачу спицу. Если она негодная, забраковать колесо. Если она удовлетвори­ тельна, выбрать наудачу одну из остальных спиц и испы­ тать ее. Если эта спица негодная, забраковать колесо .

Если она удовлетворительна, принять .

IV. Испытать выбранную наудачу спицу. Если она негодная, забраковать колесо, если удовлетворительна, выбрать наудачу одну из остальных спиц и испытать ее;

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

Далее, у природы имеются четыре возможности: может быть негодной ни одна, одна, две или три спицы. Мы обо­ значим эти стратегии природы номерами 0, 1, 2 и 3 .

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

Если М применяет стратегию I, а природа — страте­ гию 0, то М не производит испытаний и нет ни одной не­ исправной спицы. Следовательно, А признает колесо удовлетворительным и заплатит предпринимателю а .

Выигрыш предпринимателя в этом случае равен а .

Если М применяет стратегию II, а природа — страте­ гию 0, то М производит одно испытание и А признает колесо удовлетворительным. Тогда М получит от А сумму а, но ему нужно будет израсходовать на испы­ тание. Следовательно, выигрыш предпринимателя ра­ вен а — .

Если М применяет стратегию III, а природа — страте­ гию 0, то выигрыш предпринимателя будет а — 2, a если М применяет стратегию IV, а природа — стратегию О, то выигрыш предпринимателя будет а — 3 .

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

Очевидно, когда М применяет стратегию I, а при­ рода — стратегию 2 или 3, выигрыш предпринимателя также равен — .

Если природа применяет стратегию 3, то все спицы негодные. Тогда, если М производит любое испытание, он обнаружит при первом испытании, что колесо негод­ ное и, следовательно, забракует его. Таким образом, пла­ теж предпринимателю М равен лишь стоимости испы­ тания одной спицы, а именно — у. Это относится к тому случаю, когда природа применяет стратегию 3, а М при­ меняет стратегию II, III или IV .

Если М применяет стратегию II, а природа—страте­ гию 1, то вероятность того, что М обнаружит негодную спицу, равна, а вероятность того, что он не обнаружит ее, равна -g-. Если он обнаружит негодную спицу, он получит — у. Если М не обнаружит ее, он должен упла­ тить штраф, помимо расхода на испытание; итак, в этом случае платеж равен — —у. Следовательно, математи­ ческое ожидание выигрыша для М равно

–  –  –

Если М применяет стратегию III, а природа — стра­ тегию 1, то вероятность того, что М обнаружит негодную спицу при первом испытании, равна ; вероятность того, что он обнаружит ее при втором испытании, равна, 2.11 следовательно, ^ ; вероятность того, что негодная О ш О сгшца пройдет необнаруженной, равна 1 — + Если негодную спицу обнаруживают при первом испы­ тании, выигрыш М равен — у\ если ее обнаруживают при втором испытании, то выигрыш равен —2у; а если она остается необнаруженной, то выигрыш равен — — —2у. Следовательно, математическое ожидание выигрыша предпринимателя М равно

–  –  –

Цена игры для М и его оптимальные стратегии в этой игре зависят от соотношения величин а, и у* Так, например, если мы берем а = 100, = 3 0 0 и у = 3 (так что штраф за поставку негодного колеса очень велик по сравнению со стоимостью испытания), то мы получим матрицу 6 .

Элемент матрицы, отмеченный звездочкой, предста­ вляет седловую точку. Итак, самое худшее, что может оказаться дJЩ^пpeдпpинимaтeля — это одна негодная э спица колеса и лучше всего для М применять стратегию IV М атрица 6

–  –  –

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

Если же а —100, —ЗООи у —303 (так что производить испытание дорого), то мы получим матрицу 7 .

М атрица 7 2'

–  –  –

Здесь три элемента, отмеченные звездочками, суть седловые точки. Таким образом, худшее, что может еделать природа предпринимателю — это сделать негод­ ными одну или большее число спиц (безразлично, сколько именно). Для М всего лучше применять стратегию I (то есть совсем не производить испытаний). Итак, при уве­ личенной стоимости испытаний он уже может гаранти­ ровать лишь то, что его убыток будет не больше 300 .

При соответствующем выборе а, и у может даже оказаться, что матрица не имеет седловой точки. Так, если мы возьмем а —100, —900 и у = 300, то полу­ М атрица 8 чим матрицу 8, которая не имеет седловой точки. 2 3 Легко убедиться, что оптимальная стратегия для природы будет теперь 100 — 900 — 900 — 900 I 4°о 1_ оптималь­ II - 2 0 0 — 900 — 600 — 300 ная стратегия для М — и цена игры І0 о III - 5 0 0 — 800 — 400 — 300 равна — 650. Итак, самая неприятная для М страте­ гия природы следующая: IV - 8 0 0 — 600 — 400 — 300 вероятность того, что колесо хорошее, равна,а вероятность того, что у него неисправна одна спица, равна. Для М самое лучшее — бросить игральную кость и затем поступить следующим образом: если кость показы­ вает 6, пропустить колесо без испытания; в остальных случаях испытывать все три спицы. Поскольку цена игры равна — 650, М вправе требовать первоначального платежа по меньшей мере в 650 единиц, помимо стоимо­ сти изготовления .

–  –  –

Нужно заметить, что при некоторых значениях р х и р 2 решение этой задачи не обеспечит Смиту получение точно Ьх и Ь2 единиц веществ В х и В 2. Так, предположим, что значения аІ а12, а21, а22, Ьх и Ь2 такие, как указано выше, но р х = 1 и р 2 — 20. В этом случае оказывается, что самая дешевая комбинация лекарств получается, если взять в качестве пар || х г х2 1 координаты точки В на рис. 50, то | есть если взять х х = 15 и х2 — 0. Тогда Смит получит самое дешевое требуемое лечение, покупая лишь С но совсем не покупая С2\ при этом он за 15 -f 20-0 = 15 центов получает единиц вещества В х 15 + 5 * 0 = 15 и единиц вёщества В 2 5-15 + 0 = 75 15 .

Заметим, что обычные способы отыскания максиму­ мов и минимумов с помощью дифференциального исчис­ ления мало помогают при решении задач, подобных опи­ санной выше. Это объясняется тем, что минимальные или максимальные значения функций достигаются в точках границы заштрихованной области, а не в тех точках, где производные равны нулю .

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

Так возник особый раздел математики, который назы­ вается линейным программированием. Под задачей линей­ ного программирования понимается задача отыскания минимального или максимального значения линейной функции, когда переменные подчиняются линейным не­ равенствам. Общую задачу линейного программирования можно сформулировать следующим образом: выбрать рреди гс-мерных векторов || у г... у п ||, удовлетворяющие неравенствам а пУі + • • • + а тУп ^т\Уі ~Ь • • • ^тпУп ^ n-мерный вектор | | ^ i... n ||, для которого достигается минимум или максимум линейной функции РіУ і + • • • + РпУпМы не дадим какой-либо общей теории линейного про­ граммирования, так как это находится вне рамок на­ стоящей книги, а ограничимся указанием некоторых связей между этим вопросом и. теорией игр. Мы увидим, что задачу решения произвольной прямоугольной игры можно рассматривать как особую задачу линейного программи­ рования, и обратно, многие задачи линейного програм­ мирования можно привести к задачам теории игр .

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

Преждё всего очевидно, что задача линейного про­ граммирования не обязательно должна иметь решение .

Может оказаться, например, что данные неравенства не­ совместимы. Так, не имеет решения, задача отыскания минимума функции, У\ + 2г/2

–  –  –

а по теореме 2.10 стратегия | | i 2|| оптимальна для 1 \ тогда и только тогда, когда у г и у 2 удовлетворяют неравенствам (1), с заменой z на Но, очевидно, три числа у г, у2 и z удовлетворяют неравенствам (1) тогда и только тогда, когда имеются такие неотрицательные числа z что а і і У і "Ь ^12^2 "Ь

–  –  –

ип^ 0 .

У к а з а н и е : обратите внимание на то, что матрица В косо­ симметрическая, и, следовательно, цена игры равна нулю .

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

К сожалению, для этого, более широкого класса игр нет теории, которая была бы интуитивно столь же прием­ лема, как теория игр двух лиц. Хотя большая часть книги фон Неймана и Моргенштерна [92] (примерно 400 страниц из 600) посвящена играм с числом игроков больше двух, математики в основном, по-видимому, не удовлетворены теорией, изложенной в этой книге. За последние несколько лет по этому "разделу теории игр было проведено сравнительно мало исследований .

Несмотря на то, что теория игр п лиц при 7г2 на­ ходится в не совсем удовлетворительном состоянии, уча­ щемуся необходимо ознакомиться с этой теорией в ее современном виде, ибо, бесспорно, в ней имеются неко­ торые разумные элементы, хотя и требующие дальней­ шего усовершенствования. Посему этот параграф будет посвящен изложению элементов теории игр п лиц в том виде, как ее разработали фон Нейман и Моргенштерн .

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

Прежде всего мы заметим, что когда конечная игра п лиц включает частичную информацию, наличие больше чем одного хода у какого-нибудь игрока, случайные ходы и тому подобное, то все же возможно, введя понятие стра­ тегии, описать эквивалентную «прямоугольную» игру, то есть игру, в которой каждый игрок делает один и только один выбор из конечного множества; причем не знает выбо­ ров других игроков. Это было пояснено в примере 5.10 .

Таким образом, мы можем ограничиться рассмотре­ нием прямоугольных игр п лиц с нулевой суммой. Такая игра имеет п ходов; на i-и ходу (і = 1, 2,..., п) игрок Р {, не зная исхода ни одного из предыдущих ходов, выбирает число из конечного множества С.. После того как сде­ ланы п ходов, игрок P t (= 1,..., п) получает сумму M t (xv х2,..., хп) .

Поскольку игра имеет нулевую сумму, функции М х, М 2,..., М п удовлетворяют (тождественно по х г,.. .

..., хп) равенству 2 М І (.Х1,. хп) = 0 .

і—1 Сделаем теперь несколько необходимых замечаний о значениях, принимаемых платежными функциями. Оче­ видно, для игроков эти значения должны быть хорошими или плохими, причем, например, они должны считать + 2 лучше, чем +1» 0 или —1. Но чтобы дать надлежа­ щий разбор игр с числом игроков больше двух, предста­ вляется необходимым принять дополнительное допуще­ ние о том, что значения платежных функций являются объективными и переносимыми. Так, + 2 нужно пони­ мать как нечто вроде «получения двух долларов» или «получения двух фунтов спагетти»*), а не что-нибудь типа «получения двух единиц вкусового удовольствия», ибо спагетти суть нечто внешнее по отношению к нам, и его можно передавать от одного человека к другому, а вкусовое удовольствие существует только для каждого индивидуума, и его нельзя переносить от одного к дру­ гому (в самом деле, далеко не очевидно, что можно при­ *) Тонкие макароны .

писать какой-нибудь практический смысл такому утвер­ ждению, как «Тони получает столько же вкусового удо­ вольствия от тарелки спагетти, как Чанг от чашки риса») .

Поскольку, таким образом, платеж считается объек­ тивным и переносимым, ничто не препятствует игрокам производить между собой такие платежи («побочные»), как возмещение за какие-нибудь виды сотрудничества .

Так, например, может случиться, что игрок Р г выиграет гораздо больше, если он убедит игрока Р 2 выбрать не­ которое число (например, М г (2, 2, z) может быть больше, чем М г (х, г/, z) при у ф 2), если даже этот выбор не даст Р 2 непосредственной выгоды (например, может быть, что М 2(х, у, z) не зависит от х, у и z и всегда имеет постоян­ ное значение г;). В таком случае, очевидно, игроку Р х следует уплатить игроку Р 2 дополнительную сумму, чтобы убедить его сделать выбор, выгодный для Р х .

Теория игр п лиц в основном рассматривает вопросы о том, какие сочетания («коалиции») игроков будут обра­ зованы и какие вознаграждения будут уплачивать игроки друг другу в виде приманок для вступления в коалиции .

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

Мы будем обозначать множество игроков через N, так что N = {1, 2, и}ч Допустим теперь,5 что игроки множества N группи­ руются в две коалиции: Т и N — Т = — Т, так что чле­ ны коалиции Т сотрудничают между собой в выборе стра­ тегий, и тоже сотрудничают между собой члены коали­ ции — Т. Тогда мы можем рассматривать Т и — Т как двух игроков в игре двух лиц. Итак, предположим, что в первоначальной игре игрок і (г = 1,..., п) выби­ рает число из конечного множества Ct и пусть Т = = {і’і» • • • » Іг) и Т = {/і • • • » /s)* Тогда в образованной нами искусственной игре двух лиц с игроками' Т и — Т коллективный игрок Т выбирает элемент из декартова произведения С множеств СІ1? С{, и аналогично коллективный игрок — Т выбирает элемент из декартова произведения С' множеств С^,.. Су .

Пусть С = { А А и ) и С' = {В и..., В]. Тогда, очевидно, имеются функции М ІУ М 2,..., М п такие, что М і (Аі9 В к) есть платеж игроку і, когда применяет стратегию А^ и — Т применяет стратегию Bk; действительно, если .

^• = 11^! ••• x ir I и B k = I т a^ J, кі.. .

ТО М Х(АІ B h) = * M i ( x !..........х„), где M t есть i-я платежная функция первоначальной игры .

Если Т применяет стратегию А^ а — Т применяет стра­ тегию В к, то общий платеж игроку Т будет 5 fc = i 2 T i ( ^ .

) ^ М т ( А }, Bk) а общий платеж игроку — Т будет М _Т(Л,., B h) = ^ i M i (Aj, B k) .

i е—т Поскольку первоначальная игра имела нулевую сумму, то М_т(Л, ~ Мт (Aj, В к) .

Поскольку множество С содержит и элементов, смешан­ ная стратегия игрока Т есть элемент множества Su. Ана­ логично, смешанная стратегия игрока — Т есть элемент множества S v .

Но если Т применяет смешанную стратегию || а х... аи || и — Т применяет смешанную стратегию || 2... j|, то общее математическое ожидание выигрыша для Т равно «Д, ' k— j= 1 i a общее математическое ожидание выигрыша для — Т равно ) М - Т (А1, B h) a $ k .

k=l j= i Положив = Ца!... а \\ и = || x ••• „||, мы можем представить эти математические ожидания соответственно как Е т(а, ) и _ т ( а, ) .

Поскольку M-.rr(Aj, Ак) = —М ^ ( А Ah) для всех / и к, то очевидно, что _ т (а, р) = — (а, ).

(1) Ha основании теории 'прямоугольных игр двух лиц мы заключаем:

max min (а, ) = min max Е т(а, ) .

а s u, € s v esu a 6su Полагаем (T) = max min E T (a, ) .

a Gsu esv Итак, мы имеем функцию, определенную для вся­ кого подмножества Т множества N и значение которой представляет для любого Т общую сумму, которую могут надеяться получить члены множества Т, если они соста­ вят коалицию; мы называем и характеристической функ­ цией игры. Ввиду того, что платеж переносим, мы впра­ ве предполагать, что все вопросы относительно коалиции и побочных платежей можно решить на основании одной лишь характеристической функции; например, если плата игроку за присоединение к некоторой коалиции в данной игре равна я, то она будет точно так же равна я в лю­ бой другой игре с такой же характеристической функцией .

Этот вопрос, очевидно, мог быть разрешен определенно, если бы мы могли дать надлежащую теорию игр п лиц только на основе характеристических функций. Фон Ней­ ман и Моргенштерн полагают, что им это удалось сделать .

Мы установим теперь некоторые математические свой­ ства характеристических функций .

Т е о р е м а 15.1. Пусть —характеристическая функ­ ция игры п лии с нулевой суммой, где N —множество игроков. Тогда V(N) (1) = 0;

(2) для любого подмножества Т множества N мы имеем { — Т) — — t(T);

(3) если R и Т — непересекающиеся подмножества мно­ жества N, то Р (R U Т) у (R) + V (Т) .

Д о к а з а т е л ь с т в о. Для доказательства (1) разде­ лим игроков множества N на две коалиции N и N — N *= Л, тогда не существует стратегий для второй коалиции (пустого множества игроков), а стратегия (чистая) первой коалиции есть упорядоченный n-мерный вектор || х х... х п |j, где xt С| (і = 1,..., ri). Следовательно, каждая из функ­ ций M t есть функция одного лишь элемента множе­ ства С. Итак, для любой стратегии А^ выбранной коа­ лицией N, общий платеж коалиции N (ввиду того, что первоначальная игра имела нулевую сумму) равен

–  –  –

Наконец, из (8), (9) и (11) мы видим, что і({1, 2}) V ({1}) + V ({2}), что и требовалось доказать .

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

Л е м м а 15.2 .

Пусть N — некоторое множество и — действительная функция, определенная для всякого подмножества Т множества N и удовлетворяющая условиям теоремы 15.1. Тогда (1) t» (Л) = 0;

(2) если Тх,..., Тг — непересекающиеся подмножества множества N, то

–  –  –

t» (Тх) +... + у (Tr) V (Тхи •. • и Т, ) = о (N) = 0 .

Теперь мы можем доказать упомянутую выше теорему, обратную теореме 15.1 .

Т е о р е м а 15.3. Пусть N — конечное множество, состоящее из п игроков и — действительная функция, определенная для всякого подмножества Т множества N и удовлетворяющая трем условиям теоремы 15.1. Тогда существует игра п лиц с нулевой суммой, для которой v является характеристической функцией .

Д о к а з а т е л ь с т в о.

Мы определяем игру, в которой игроки суть члены множества N, следующим образом:

каждый член х множества N делает один ход, состоящий в выборе подмножества Т х множества N такого, что x T при совершении каждого из этих ходов игроку ;

неизвестны ходы других игроков .

Чтобы определить платежные функции, мы введем сначала вспомогательное понятие характерного подмно­ жества множества N .

Подмножество Т множества N называется характерним (по отношению к данной партии игры), если либо (а) Т х = Т для всякого х в Т, либо (б) Т есть множество, содержащее только один эле­ мент x, который не принадлежит никакому множеству, удовлетворяющему условию (а) .

Легко видеть, что для данной партии игры характер­ ные подмножества множества N не пересекаются и их сумма есть N .

Предположим теперь, что для данной партии игры характерные подмножества множества N суть Т1..., Тр и что Ту (/ = 1,.. р) содержит иу элементов. Тогда, если игрок і ( і — 1,...

, п ) принадлежит множеству Tj, то выигрыш его определяется так:

V где и — данная функция .

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

Мы замечаем, что выигрыши любых двух членов одного и того же щюжества Ту одинаковы. Следовательно, сумма выигрышей членов множества Ту для любого / равна просто произведению rij на выигрыш каждого члена множества Т,, то есть

–  –  –

Для Т = А это вытекает из условия (1) леммы 15.2 .

В случае Т Ф А игроки множества Т могут образовать коалицию и условиться, что каждый член х множества Т будет выбирать Тх = Т. При этом Т станет характерным множеством относительно рассматриваемой партии. Пред­ положим, что характерные множества партии суть Т..., Тр, где Tj = Т. Тогда каждый игрок множества Т получает и, следовательно, общий выигрыш членов множества Т равен

–  –  –

2. Приведенная форма Основные вопросы, которые мы разбирали в теории игр п лиц,— это, как было сказано выше, вопросы о том, насколько сильны будут стремления игроков образовы­ вать коалиции и какие взносы игроки должны уплачи­ вать друг другу при вступлении в данную коалицию .

Если две игры не’различаются в этом отношении (хотя бы их платежные функции и характеристические функции и были различны), то с нашей точки зрения они будут по существу одинаковы. Уместно дать какое-нибудь назва­ ние такому соотношению между двумя играми; мы назо­ вем это соотношение стратегической эквивалентностью .

Конечно, понятие стратегической эквивалентности есть лишь интуитивное понятие без какого-либо математиче­ ского содержания, ибо оно основано на таких понятиях, как «стремление к образовании? коалиции», которые сами не были определены математически. Но, очевидно, это понятие чрезвычайно важно для нашей цели, и одна из основных задач теории игр — найти для него точное математическое определение. Можно привести приемле­ мые интуитивные доводы, которые покажут, что неко­ торые условия достаточны для стратегической эквива­ лентности; мы сделаем это в следующих абзацах .

Допустим, что йам даны две прямоугольные игры п лиц с нулевой суммой Г и Г', и в обеих играх игрок і ( і = 1, делает выбор из множества С{; пусть пла­ тежные функции в Г и Г' суть соответственном!,..., МП и. М[,..., М'п. Допустим, далее, что существует поло­ жительное число к, такое, что для і = 1, п и для любого элемента || х г... хп || из декартового произведения множеств С1..., Сп ?

Мі {х^ • • • » Хп) ^ кМі (x^j..., жп). (16) Тогда интуитивно очевидно, что игры Г и Г' стратеги­ чески эквивалентны, так как мы можем рассматривать к просто как константу, изменяющую денежную единицу (например, из центов или шиллингов в доллары), а пове­ дение разумного человека в игре не зависит от единиц, в которых выражается платеж. Итак, мы нашли доста­ точное условие для стратегической эквивалентности .

Другое достаточное условие мы получим, заменив условие (16) нижеследующим: существует п чисел а..., ап таких, что «1 + • • • + О = О, 'п и для г = 1,..., п и для любого элемента || х г... хп || из декартового произведения множеств С1..., Сп ?

(#і, • • • » х п) =: ( х • J хп) -f- (17) М% Чтобы в этом случае убедиться в стратегической экви­ валентности Г и Г', заметим, что платежи игроку і в Г' такие же, как в Г, с той разницей, что он получает дополнительную сумму а{ (которая, конечно, может быть отрицательной) и эту сумму игрок і получает неза­ висимо от течения игры. Таким образом, очевидно, что стратегии игры Г' не изменились бы, если бы платежи а..., ап производились в начале игры, а не в конце, и если бы их совсем не было, как это имеет место в игре Г .

Далее мы видим, что для того, чтобы Г и Г' были стратегически эквивалентны, в действительности не обя­ зательно предполагать, как мы делали раньше, что классы, из которых игроки делают выборы, действительно тождественны, достаточно просто предположить, что они могут быть поставлены соответствующим способом во взаимно однозначное соответствие .

Эти соображения подсказывают нам ввести следующее понятие S -эквивалентности, которое, как вытекает из наших интуитивных доводов, представляет собой доста­ точное услойй^для стратегической эквивалентности .

О п р е д е л е н и е 15.5. Пусть Г и Г' — две игры п лиц с нулевой суммой, в которых выборы производятся соот­ ветственно из множеств Сг..., С П и CJ.........Ci, и пла­ тежные функции суть соответственно М..., М п и.. .

..., М п. Игры Г и Г' называются S-эквивалентными, если существуют функции fv..., /п, действительные числа а..., ап и действительное положительное число /с, удовлетворяющие следующим условиям:

1) 2 а * = 0;

1= 1

2) fi ( і = 1) • • -, п) отображает C t взаимно однозначным образом на С[ .

3) Для і = 1,..., п и для любого элемента || x L... х п \\ декартова произведения множеств С..., Сп М і (хх,..., хп) = кМ і [/х (а^),..., /п (#л)] + Доказательства следующих двух теорем мы оставляем в качестве упражнений .

Т е о р е м а 15.6. Соотношение S-эквивалентности реф­ лексивно, симметрично и транзитивно .

Т е о р е м а 15.7. Если Г и Т ' —две игры п лиц с нуле­ вой суммой, которые S-эквивалентны относительно кон­ стант а..., ап и к и если и & — характеристиче­ ские функции игр Г и Г' соответственно, то для любого подмножества Т множества N t(T) = /« /( T ) + г iE T В силу теоремы 15.7 две характеристические функции V и ' называются S-эквивалентными, если они удовле­ творяют уравнению этой теоремы, то есть если имеется положительная константа к и константы а..., ап п (при 2 аі — 0) такие, что для всякого подмножества Т і= і множества N ( Т) = к' (Т) + 2 а * .

і Т Согласно теореме 15.6 соотношение S-эквивалентности разбивает класс всех игр п лиц с нулевой суммой на цепересекающиеся классы такие, что любые два элемента одного класса S -эквивалентны, а элементы разных клас­ сов не S-эквивалентны. Для некоторых целей желательно иметь возможность выбирать из этих классов особенно простой элемент; для этого мы сформулируем следующее определение .

О п р е д е л е н и е 15.8. Игра п лиц с характеристи­ ческой функцией V называется игрой в п ри веден н ой ф о рм е, если V ({1}) = V ({2}) =... = V ({n}) = Y .

где либо y —0, либо — 1- Когда эти уравнения спра­ ведливы, мы говорим также, что характеристическая функция есть характеристическая функция в приведенной форме с модулем у .

Т е о р е м а 15.9. Если —характеристическая функ­ ция в приведенной форме с модулем у и если Т — подмно­ жество множества N, содержащее р элементов, то ру^(Т)(р-п)у .

–  –  –

2 ИМ І—1 і= 1 Тот факт, что характеристическая функция не S-экви­ валентна двум различным характеристическим функциям в приведенной форме, вытекает из теоремы 15.11 и из того, что соотношение S-эквивалентности транзитивно .

З а м е ч а н и е 15.13. Из теорем 15.12 и 15.7 следует, что для того чтобы дать надлежащую теорию всех игр п лиц с нулевой суммой, достаточно рассмотреть лишь игры в приведенной форме .

Следствие 15.10 показывает, что игры в приведенной форме с модулем 0 резко отличаются от игр с модулем — 1. Действительно, из 15.10 мы видим, что когда модуль равен 0, любое множество игроков получает 0 ;

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

Поэтому мы можем впредь ограничиться играми в приве­ денной форме с модулем — 1. Мы будем называть такие игры существенными, в отличие от игр с модулем 0, которые будут называться несущественными .

Игры не в приведенной форме мы называем суще­ ственными или несущественными в зависимости от того, являются ли они S-эквивалентными существенным или несущественным играм в приведенной форме .

Следующие две теоремы дают условия того, чтобы игры (не обязательно в приведенной форме) были несу­ щественными; доказательства мы оставим в качестве упражнений .

Т е о р е м а 15.14. И гр а несущественна тогда и только тогда, когда ее характеристическая функция удовлетво­ ряет условию 2 »(Ш) = о .

і=1 Т е о р е м а 15.15. И гра несущественна тогда и толь­ ко тогда, когда ее характеристическая функция такая, что если Р f] Т = Л, мы имеем:

o ( R U T ) = o(R) + o(T) .

Итак, в существенной игре имеет место положитель­ ная тенденция к образованию коалиции .

Из следствия 15.10 мы видим, что для любого п в пределах S-эквивалентности имеется лишь одна несуще­ ственная игра п лиц. Интересно отметить, что для п = 3 имеется также лишь одна существенная игра п лиц в приведенной форме.

В самом деле, если — характери­ стическая функция такой игры, то мы имеем:

»({1}) = 0 ( { 2 } ) = о ( { 3 } ) = - 1, и, следовательно, на основании условия (2) теоремы 15.1 ({2, 3}) v ({1, 3}) = v ({1, 2j) = + 1;

поскольку мы имеем также о(Л) = о({1, 2, 3}) = 0, то мы заключаем отсюда, что значение функции (Т) определено для любого Т. Итак, можно говорить об опре­ деленной существенной игре трех лиц в приведенной форме .

Напротив, для п 3 имеется бесконечное число существенных игр п лиц в приведенной форме. Мы ис­ следуем этот вопрос несколько подробнее для п — 4 .

Если и — характеристическая функция существенной игры 4 лиц в приведенной форме, то мы сразу видим, что 0 (0

-1 1 I, когда Т состоит из f 2 элементов. (23) 0 (Т)Н ТГ Итак, значение функции (Т ) определено, за исключе­ нием случая, когда Т содержит два элемента. Но в силу того, что ([2, 3})= - и ( { 1, 4}), о ({1, 3 ) ) = - ( { 2, 4}), ( { і, 2}) = - ( { Ъ, 4}), значения будут полностью определены, если мы зада­ дим значения функций ( [ і, 4}), у ({2, 4}) и ({3, 4j) .

Далее, по теореме 15.9 мы видим, что если Т есть любое множество с двумя элементами, то — 2 (Т) 2 .

Итак, если мы положим У({1. 4}) = 2a:x, v({2, 4j) = 2х 2, (24) ({3, 4» = 2^з, то мы будем иметь у ({2, 3}) = - 2z lf (25) о({1, 3 } )= - 2 х „ о({1, 2)) = — 2х3 и — 1 ж { 1 для і = 1, 2, 3. (26) Далее, легко убедиться, что если х х 2 и х3 — любые числа, удовлетворяющие соотношению (26), и если мы определяем (Т) соотношениями (23), (24) и (25), то и есть характеристическая функция существенной игры четырех лиц в приведенной форме. Для этого необходимо лишь показать, что функция, определенная таким образом, удовлетворяет условиям теоремы 15.1 .

Итак, если числа х х2 и х3 мы рассматриваем как декартовы координаты точки в трехмерном евклидовом пространстве, то совокупность существенных игр четырех лиц в приведенной форме, очевидно, соответствует вза­ имно однозначно точкам \\хг х 2 х 2 \\, координаты которых удовлетворяют условию (26) (это точки некоторого куба) .

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

П р и м е р 15.16 .

Игра, называемая «один лишний», проводится следующим образом: каждый из игроков (их всего три) пишет на листке бумаги «герб» или «решка» .

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

Таким образом, если М М 2 и М 3—платежные функ­ ции для трех игроков и если обозначим «герб» как «1», а «решку» как «2», то М г ( 1, 1, 1 ) = Л М 2, 2, 2) = 0, М г ( 1, 1, 2 ) = М 1 (2, 2, 1) = Л/ 1 (1, 2, I H M, (2, 1, 2) = 1, М г ( 1, 2, 2 ) - - = ^ ( 2, 1, 1 ) = - 2 .

и аналогично для М 2 и М 3 .

Предположим теперь, что игроки 2 и 3 составляют коалицию против игрока 1. Игрок 1 имеет, очевидно, лишь две стратегии: он может выбрать 1 или 2. Коали­ ция {2, 3} имеет четыре стратегии: оба игрока могут выбрать 1; оба игрока могут выбрать 2; игрок 2 выби­ рает 1, а игрок 3 выбирает 2 ; игрок 2 выбирает 2, а игрок 3 выбирает 1. Из определения функции М х мы легко можем вычислить платежную матрицу игрока 1 для различных выбранных стратегий. Так, если, напри­ мер, игрок 1 выбирает 1, а коалиция {2, 3} выбирает II1 2 II, то поскольку М г ( 1, 1, 2) = 1, выигрыш игрока 1 будет равен 1. Полной матрицей будет матрица 1 .

–  –  –

3}) = ir({l, 2]) = 1 .

Далее (как и для любой игры трех лиц с нулевой суммой) о(Л) = о({1, 2, 3}) = 0 .

Итак, мы полностью определили характеристическую функцию этой игры. Платежная функция в этом случае оказывается такой, что характеристическая функция уже имеет приведенную форму .

Библиографические замечания Материал этой главы можно найти главным образом у фон Неймана и Моргенштерна [92]. Полный разбор S-эквивалентности еЪть у Мак-Кинси [74] .

–  –  –

1. Исход Как было указано, в играх п лиц мы интересуемся вопросами о том, какие коалиции могут быть образованы и что будет уплачено каждому игроку (после производ­ ства побочных платежей) в случае образования данной коалиции. Выигрыши нескольких игроков данной коали­ ции и побочные платежи можно представить как вектор x Y х 2....яп |і, где хі (і = 1,..., п) есть сумма,, которую получает і-й игрок .

Но поскольку игра имеет нулевую сумму, так что деньги не создаются и не уничтожаются, очевидно, вы­ игрыши игроков должны в сумме давать нуль, то есть

–  –  –

2. Определение решения Мы хотим теперь рассмотреть вопрос о том, какие исходы могут возникнуть в действительных партиях игры .

Сначала нам представляется следующий ответ: исход сх = Кet!... ап || может быть реализован в партии игры, если не существует исхода, который предпочтительней а, так как ни одно множество игроков не имело бы никакого повода к тому, чтобы сменить а на какойнибудь другой исход; поэтому, если при заключении сде­ лок был бы предложен исход а, то каждый понял бы, что он не может получить больше, чем ему обещает дать исход а; так было бы достигнуто соглашение .

Но, к сожалению, вообще не существует такого ис­ хода. Действительно, мы можем показать (за исключе­ нием случая несущественной игры, в которой имеется лишь один исход), что всякому исходу может быть пред­ почтен какой-нибудь другой исход. Пусть \\хг... х п \\ — какой-нибудь исход в существенной игре п лиц. Тогда существует целое число /с, такое, что Ч »({*}) .

ибо иначе мы имели бы по теореме 15.14

–  –  –

^3у • Допустим опять, что справедливо первое из этих не­ равенств. Для другого случая доказательство аналогично .

Тогда мы имеем *і4 и *2 у .

Поскольку ^1+ ^ 2= — Я3 1, мы заключаем, что так что \\хг хг x3||A, а это противоречит принятому условию. % Только что установленные свойства множества А на­ столько важны, что уместно дать наименование множе­ ствам исходов, обладающих этими свойствами .

О п р е д е л е н и е 16.6. Множество А исходов данной игры п лиц называется решением игры, если

1) ни одному элементу множества А нельзя отдать предпочтение но отношению к другому элементу множе­ ства А;

2) всякому элементу, не входящему в А, можно пред­ почесть некоторый элемент множества А .

З а м е ч а н и е 16.7. В развитой фон Нейманом теории игр п лиц понятие «решений» в только что определен­ ном смысле занимает центральное место. Теория состоит по существу в отыскании решений и рассмотрении их свойств .

Интуитивное обоснование употребления слова «реше­ ние», конечно, сильно отличается от того, которое было дано для игр двух лиц. % В первом случае под решением подразумевалось мно­ жество вероятностей, с которыми игроку нужно выбирать свои чистые стратегии, чтобы получить максимальный ожидаемый выигрыш. Но в случае игр п лиц (для п 2) решение имеет целью просто указать множество воз­ можных способов распределения выигрышей в конце партии .

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

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

–  –  –

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

Поскольку, как известно, точки евклидовой плоскости можно представить с помощью лишь двух координат (как, например, в обычной декартовой системе), мы должны ожидать, что эти три координаты не будут взаимно не­ зависимы. И действительно, можно легко показать (с по­ мощью некоторых тригонометрических соотношений), что для всякой точки I хг х 2 х 3 у мы имеем I Хі + х2 -f х 3 = 0 .

Далее, если х ІУ х2 и х3 — три числа, сумма которых равна нулю, то в плоскости существует точка, координаты которой суть I х х х 2 х3 у. Итак, мы имеем координатную I систему, которая автоматически удовлетворяет одному из условий, определяющих исход (для игры трех лиц) .



Pages:   || 2 |



Похожие работы:

«УДК 669.85/.86.018.543.06:00б.354 Груши BS9 ГОСУДАРСТВЕННЫЙ СТАНДАРТ СОЮЗА ССР СПЛАВЫ И ЛИГАТУРЫ РЕДКИХ МЕТАЛЛОВ Спектральный (с индукционной высокочастотной плазмой) ГОСТ метод определения компонентов и примесей в сплавах на осмосе ниобия 2 5 2 7 8.1 7 -8 7 Alloys and foundry alloys of таге metals. S...»

«опубликована 26 июня 2015 года, на сайте: www.tsvet-park.ru (с изменениями от 01.11.2016 года) Строительство Утверждаю: Директор ООО "Династия" Ведехин С.В. ПРОЕКТНАЯ ДЕКЛАРАЦИЯ Строительство объекта капитального строительства блокированного многоквартирного жилого дома (количество этажей – 3, количество секций – 7, количество ква...»

«ООО "Дивногорский завод рудничной автоматики" 663090, Россия, Красноярский край, г. Дивногорск, ул. Нижний проезд, д. 20/2 т. (39144) 3-00-45, (391) 282-78-18, (913) 834-12-86, (923) 354-53-85 opt@dzra.ru, office@dzra.ru, www.dzra.ru ОКП 3430 ШКАФ АВТОМАТИЧЕСКОГО ВВОДА РЕЗЕРВА ТИПА АВР-РН Паспорт Дата выпуска: 20 г. № Исполнитель: / /...»

«П равительство М осквы Комитет города М осквы по ценовой политике в строительстве и государственной экспертизе проектов СБОРНИК базовых цен на работы по обследованию и мониторингу технического состояния строительных конструкций и инженерного оборудования зданий и сооружений, в том числе соору...»

«Ковров: +7(999) 77-69-100 info@kovrovmodul.ru http://www.kovrovmodul.ru К-Модуль Презентация Ковров: +7(999) 77-69-100 info@kovrovmodul.ru http://www.kovrovmodul.ru Компания К-Модуль занимается проектированием, изготовлением быстровозводимых м о д ул ь н ы х зданий ГОСТ 22...»

«Перевод ООО "Планета Хобби" © http://www.planetahobby.ru Соосный вертолёт DRACO РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ Поздравляем вас! Вы стали пилотом вертолёта компании Nine Eagle! Для безопасного полёта, пожалуйста, прочтите данное руководство внимательно до конца....»

«2016 ПРОБЛЕМЫ АРКТИКИ И АНТАРКТИКИ № 3 (109) УДК 623.827 Поступила 3 июня 2016 г.ФИЗИЧЕСКОЕ МОДЕЛИРОВАНИЕ СТАТИЧЕСКОГО ВСПЛЫТИЯ ПОДВОДНОЙ ЛОДКИ ИЗ-ПОДО ЛЬДА В ЛЕДОВОМ БАССЕЙНЕ ААНИИ вед. инж. И.А. СВИСТУНОВ, ст. научн. сотр. А.В. ЧЕРНОВ, ст. научн. сотр. Н.А. КРУПИНА, ка...»

«УДК 334.021 ГАЗОПРОВОД "ЮЖНЫЙ ПОТОК": ЭКОНОМИЧЕСКАЯ НЕОБХОДИМОСТЬ И ПОЛИТИЧЕСКОЕ ПРОТИВОДЕЙСТВИЕ И.А. Агафонов4 ФГБОУ ВПО "Самарский государственный технический университет" 443100, г. Самара, ул. Молодогвардейская, 244 Е-mail: yuhan@mail.ru Экспорт энергоносителей, и особенно п...»

«ОКП 42 1392 ООО ТОПАЗ-СЕРВИС TОПАЗ-103М1 NUOVO PIGNONE ПУЛЬТ ДИСТАНЦИОННОГО УПРАВЛЕНИЯ ТОПЛИВОРАЗДАТОЧНЫМИ КОЛОНКАМИ И ГАЗОНАПОЛНИТЕЛЬНЫМИ КОЛОНКАМИ Руководство по эксплуатации ДСМК. 421252.001-14РЭ ДСМК. 421252.001-14РЭ Файл: D10969 Изменен: 21.08.08 Отпечатан: 21.08.08 ООО Топаз-сервис ул...»

«БЛОК БЕСПЕРЕБОЙНОГО ПИТАНИЯ ВОЛНА-ББП 3/20 РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ ФИАШ.436234.434 РЭ Настоящее руководство предназначено для ознакомления с основными техническими характеристиками, принципом работы, способом установки на объекте и правилами эксплуатации блока бесперебойного питания ВОЛНА...»

«Государственное учреждение высшего профессионального образования "АРХАНГЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ" ПОЛОЖЕНИЕ о проведении государственных экзаменов Принято на ученом совете университета 24 ноября 2005 г. Архангельск Настоящее Положение...»

«Договор подряда № г.Мирный "" _ 2014 г. Акционерный коммерческий банк " Алмазэргиэнбанк" Открытое акционерное общество в г.Мирный, именуемый в дальнейшем Заказчик в лице Руководителя дополнительного офиса, действующего на основании _, с одной стороны, и, именуемое в дальнейшем Подряд...»

«Влияние различных факторов на уровень соматических клеток в молоке коров Кадралиева Б. Т. Кадралиева Бакытканым Талаповна / Kadralieva Bakytkanym Talapovna – соискатель, кафедра эпизоотологии, паразитологии и ветеринарно-санитарной экспертизы, факультет ветеринарной медицины...»

«RU BTL 0 0H BTL 4 4H BTL 6 6H BTL 10 10H 2002/11 Перед пуском горелки или выполнением техобслуживания необходимо внимательно прочитать инструкции.Работы на горелке и в системе должны выполняться квалифицированными работниками.Перед осуществлением любых работ электрическое п...»

«План мероприятий ПКиО "Сокольники" по улучшению качества оказания услуг на 2018 год Улучшения в рамках проекта "Доступная среда" В 2018 году в парке появится тактильная плитка на перекрестках, которая поможет...»

«Лебо А.И. Анализ лазер-плазменных экспериментов с помощью методов математического моделирования 05.13.18 – математическое моделирование, численные методы и комплексы программ. ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Науч...»

«ЯЦЕНКО ВИКТОР МИХАЙЛОВИЧ ПРОБЛЕМЫ ЭФФЕКТИВНОГО УПРАВЛЕНИЯ ОСНОВНЫМИ СРЕДСТВАМИ В ГАЗОВОЙ ОТРАСЛИ И МЕХАНИЗМЫ ИХ РЕШЕНИЯ (НА ПРИМЕРЕ ОАО "ГАЗПРОМ") Специальность 08.00.05 "Экономика и управление народным хозяйством...»

«КИРИЛЛОВА ОКСАНА ЮРЬЕВНА РАЗВИТИЕ ИНСТИТУЦИОНАЛЬНЫХ МЕХАНИЗМОВ КОНТРОЛЯ В ТЕОРИИ И ПРАКТИКЕ КОРПОРАТИВНОГО УПРАВЛЕНИЯ Специальность: 08.00.05 – Экономика и управление народным хозяйством (менеджме...»

«Московский энергетический институт (технический университет) Институт Автоматики и вычислительной техники Кафедра Информационно-измерительной техники В.Ю. Кончаловский ЦИФРОВОЙ МУЛЬТИМЕТР Методическое руково...»

«РАССМОТРЕНО: УТВЕРЖДЕНО: Педагогическим советом Директор ГБПОУ НСО "БПК" ГБПОУ НСО "БПК" Т.В.Чуркина Протокол от _ № _ приказ от № ПОЛОЖЕНИЕ О ПОРЯДКЕ РАБОТЫ С ЖУРНАЛОМ УЧЕТА ТЕОРЕТИЧЕСКОГО ОБУЧЕНИЯ В ГОСУДАРСТВЕННОМ БЮДЖЕТНОМ ПРОФЕССИОНАЛЬНОМ ОБРАЗОВАТЕЛЬНОМ УЧРЕЖДЕНИИ НОВОСИБИР...»

«Интернет-журнал "Транспортные сооружения" 2017, Том 4, №1 ISSN 2413-9807 Russian journal of transport engineering 2017, Vol 4, No 1 http://t-s.today Интернет-журнал "Транспортные сооружения" / Russian journal o...»

«ИНСТРУКЦИЯ ПО ЭКСПЛУАТАЦИИ НА КРЫШНЫЙ ВЕНТИЛЯТОР BRF ОПИСАНИЕ ПРОДУКЦИИ Устанавливаемые на крыше вентиляторы BRF широко применяются по всему миру, с целью улучшения качества внутреннего воздуха при применении их в системах каналов. Крышные вентиляторы BRF идеальное решение для потребностей венти...»

«SUPERTRONIC 2000 Instrucciones de uso Instructions for use Instruction d’utilisation Bedienungsanleitung Instrues de servio Istruzioni d'uso Gebruiksaanwijzing Brugsanvisning Bruksanvisning ИНСТРУКЦИЯ Instrukcja obsugi A OPERATING INSTRUCTIONS Intro ESPAOL Pgina 5 Por favor, lea y cons...»

«Приложение УТВЕРЖДЕНЫ приказом СВФУ от 01.10.2018 г. № 1054-ОД Правила приема в федеральное государственное автономное образовательное учреждение высшего образования "Северо-Восточный федеральный университет имени М.К. Аммосова" на обучение по образовательным программам высшего образования программам ба...»

«XJ9900202 СООБЩЕНИЯ ОБЪЕДИНЕННОГО ж ИНСТИТУТА ЯДЕРНЫХ ИССЛЕДОВАНИЙ •• и M E : I Дубна Р18-98-366 В.Ф.Реутов, С.Н.Дмитриев ПРИМЕНЕНИЕ ТРЕКОВЫХ МЕМБРАН В НАНОТЕХНОЛОГИИ 30-29 Введение Производство субмикронных объектов является одной из...»







 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.