П 30 Теория игр: Учеб. Пособие для ун-тов:/Л. Шк., Книжный дом «Университет», 1998. ISBN 5-06-001005-8 ISBN 5-8013-0007-4 Книга представляет собой краткое и сравнительно элементарное учебное пособие, пригодное как для первоначального, так и для углубленного изучения теории игр; в ней проводится исследование математических моделей принятия решений в условиях конфликта. Впервые в отечественной научной литературе дано систематическое изложение единой теории статических и динамических игр. Учебник предназначен как для первоначального, так и для углубленного изучения теории игр. Проведено систематическое исследование математических моделей принятия решений несколькими сторонами в условиях конфликта. Представлено последовательное изложение единой теории статических и динамических игр. Рассмотрены все основные классы игр: конечные и бесконечные антагонистические игры, бескоалиционные и кооперативные игры, многошаговые и дифференциальные игры. Для закрепления материала в каждой главе содержатся задачи и упражнения разной степени сложности. Л.А.Петросян Н.А.Зенкевич Е.А.Семина ТЕОРИЯ ИГР Учебное пособие Рекомендовано Министерством общего и профессионального образования Российской Федерации в качестве учебного пособия для студентов университетов, обучающихся по специальности «Математика» Москва 1998 s31 Т ) V2. ТКт 1° §1 I V I и g ' Vi? УДК 51 ББК22.1 ПЗО Р е ц е н з е н т ы: кафедра исследования операций Московского государствен­ ного института электроники и математики (зав. Кафедрой д-р физ.-мат. Каштанов) и кафедра исследования операций факультета вычисли­ тельной математики и кибернетики Московского г. Петросян, Зенкевич, Шевкопляс: Теория игр. Автор: Петросян Леон Аганесович, Зенкевич Николай Анатольевич, Шевкопляс Екатерина Викторовна. Редактор: Кондукова Екатерина. Издательство: BHV, 2016 г. Учебник предназначен как для первоначального, так и для углубленного изучения теории игр. Проведено систематическое исследование математических моделей принятия решений несколькими сторонами в условиях конфликта. Представлено последовательное изложение единой теории статических и динамических игр.

1. Петросян Зенкевич Семина Теория Игр Скачать
2. Петросян Зенкевич Теория Игр
3. Петросян Зенкевич Шевкопляс Теория Игр

1 2 Л.А.Петросян Н.А.Зенкевич Е.А.Семина ТЕОРИЯ ИГР Учебное пособие Рекомендовано Министерством общего и профессионального образования Российской Федерации в качестве учебного пособия для студентов университетов, обучающихся по специальности «Математика» s31 Т) V2. Ткт 1 Москва 1 IVI и 1998 g ' Vi?

3 УДК 51 ББК22.1 ПЗО Рецензенты: кафедра исследования операций Московского государственного института электроники и математики (зав. Кафедрой д-р физ.-мат. Каштанов) и кафедра исследования операций факультета вычислительной математики и кибернетики Московского государственного университета им. Ломоносова (зав.

Кафедрой чл.-кор. П 30 Петросян Л. Теория игр: Учеб.

Пособие для ун-тов:/л. Шк., Книжный дом «Университет», с: ил. ISBN ISBN Книга представляет собой краткое и сравнительно элементарное учебное пособие, пригодное как для первоначального, так и для углубленного изучения теории игр; в ней проводится исследование математических моделей принятия решений в условиях конфликта. Впервые в отечественной научной литературе дано систематическое изложение единой теории статических и динамических игр.

Рассмотрены конечные и бесконечные антагонистические игры, многошаговые игры, бескоалиционные и кооперативные игры, дифференциальные игры. В каждой главе содержатся задачи разной сложности. Книга предназначена для студентов и аспирантов университетов, экономических и технических учебных заведений, представляет интерес как для математиков, работающих в области теории игр, так и для специалистов в области экономики, теории управления и исследования операций. Зенкевич, Е.А. Семина, 1998. 4 ОГЛАВЛЕНИЕ Предисловие 5 Введение 7 Глава I. Матричные игры 9 1.

Определение антагонистической игры в нормальной форме Максиминные и минимаксные стратегии Ситуации равновесия Смешанное расширение игры Некоторые сведения из теории вьшуклых множеств и систем линейных неравенств Существование решения матричной игры в классе смешанных стратегий Свойства оптимальных стратегий и значения игры Доминирование стратегии Вполне смешанные и симметричные игры Итеративные методы решения матричных игр 52 Упражнения и задачи 56 Глава II. Бесконечные антагошиiическне игры Бесконечные игры Ситуация е-равновесия, е-седловые точки и г-оптимальные стратегии Смешанные стратегии Игры с непрерывной функцией выигрыша Игры с выпуклой функцией выигрыша Одновременные игры преследования Один класс игр с разрывной функцией выигрыша Решение бесконечных одновременных игр поиска 104 Упражнения и задачи 109 Глава III. Неавтагонистнческне игры Определение бескоалиционной игры в нормальной форме Принципы оптимальности в бескоалиционных играх Смешанное расширение бескоалиционной игры Существование ситуации равновесия по Нашу Свойства оптимальных решений Равновесие в совместных смешанных стратегиях Задача о переговорах Игры в форме характеристической функции С-ядро и Н М-решение Вектор Шепли 163 Упражнения и задачи 170 Глава IV. Позиционные игры Многошаговые игры с полной информацией Ситуация абсолютного равновесия Основные функциональные уравнения Стратегии наказания 191 3. Иерархические игры Иерархические игры (кооперативный вариант) Многошаговые игры с неполной информацией Стратегии поведения Функциональные уравнения для одновременных многошаговых игр 218 Упражнения и задачи 224 Глава V. 6 ПРЕДИСЛОВИЕ Математическая теория игр является составной частью исследования операций.

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

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

Наиболее подробно изложена теория антагонистических игр (гл. I, II, IV, V).

В курсах «Системный анализ» и «Модели принятия решений» целесообразно использовать гл. Теория неантагонистических игр изложена в гл. III, IV, а теория динамических игр в гл. В пособии не отражены результаты теории дифференциальных игр многих лиц, поскольку этот класс игр еще недостаточно изучен. Однако имеющиеся в этом направлении работы широко представлены в списке литературы 38, 45, 51, 77, 87, 88. При построении курса лекций по приложениям теории игр полезно также воспользоваться специальной литературой 5, 10, 12, 20, 27, 34, 52, 53.

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

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

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

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

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

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

Зенкевичем студентам старших курсов и аспирантам на факультете прикладной математики процессов управления Санкт-Петербургского государственного университета. Параграфы 7, 9 гл. Ш, 4 6, 8 и 9 гл. IV, 2 6, 8 гл.

V написаны совместно с Е. 8 ВВЕДЕНИЕ 8.1. В настоящем учебном пособии изложены основные понятия и результаты теории игр. Теория игр это раздел математики, в котором исследуются математические модели принятия решений в условиях конфликта, т.

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

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

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

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

Петросян Зенкевич Семина Теория Игр Скачать

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

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

Начнем изучение теории с простейшей статической модели матричной игры, в которой участвуют два игрока, множество стратегий каждого из игроков конечно, а выигрыш одного игрока равен проигрышу другого. МАКСИМИННЫЕ И МИНИМАКСНЫЕ СТРАТЕГИИ 2.1. Рассмотрим антагонистическую игру Г=(Х, Y, К). Здесь каждый из игроков выбором стратегии стремится максимизировать свой выигрыш.

Но для игрока 1 он определяется функцией К(х, у), а для второго ( К(х, у)), т. Цели игроков прямо противоположны. При этом заметим, что выигрыш игрока 1(2) определен на ситуациях (х, y)exy, складывающихся в процессе игры. Но каждая ситуация, а следовательно, и выигрыш игрока зависят не только от его выбора, но и от того, какая стратегия будет выбрана противником. Поэтому, стремясь получить возможно больший выигрыш, каждый игрок должен учитывать поведение противника. Поясним сказанное на примере игры «оборона города».

Если игрок 1 хочет получить максимальный выигрыш, то он должен принять стратегию х 0 (или х 4 ). В этом случае, если игрок 2 применит стратегию у 0 (у 3 ), то первый получит выигрыш, равный 4 единицам. Но если игрок 2 применит стратегию у г (соответственно у 0 ), то игрок 1 получит выигрыш, равный 0, т. Зразок заяви на допомогу при народженні дитини. Потеряет 4 единицы.

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

Что может себе гарантировать игрок 7? Пусть игрок 1 выбрал стратегию х. Тогда в худшем случае он выиграет min K(x, у). Поэтому игрок 1 всегда может гарантировать себе выигрыш max min К(х, у).

Если отказаться от предположения достижимости. у экстремума, то игрок 1 может всегда получить выигрыш, сколь угодно близкий к величине r = supinf K(x, у), (2.1) - хех yey которую будем называть нижним значением игры. Если же внешний экстремум в (2.1) достигается, то величина v называется также максимином, принцип построения стратегии х, основанный на максимизации минимального выигрыша, принципом максимина, а выбираемая в соответствии с этим принципом стратегия х максиминной стратегией игрока 1. Для игрока 2 можно провести аналогичные рассуждения. Пусть он выбрал стратегию. Тогда в худшем случае он проиграет max K(x, у). Поэтому второй игрок всегда может себе гарантиро- X вать проигрыш min max K(x, у).

Число У х 14 v = inf sup K(x, у) (2.2) yey xex 16 называется верхним значением игры Г, а в случае достижения внешнего экстремума в (2.2) и минимаксом. При этом принцип построения стратегии у, основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принципом стратегия у минимаксной стратегией игрока 2.

Подчеркнем, что существование минимаксной (максиминной) стратегии определяется достижимостью внешнего экстремума в (2.2) ((2.1)). Пусть задана матричная (т х и)-игра Г^. Тогда экстремумы в (2.1) и (2.2) достигаются, а нижнее и верхнее значения игры соответственно равны» = max mm = 3, / 0 =2, а верхнее значение (минимакс) v и минимаксная стратегия у 0 второго игрока V = 3,j 0 = Для любой игры Г=(Х, Y, К) справедливо следующее утверждение. В антагонистической игре Г «кх.

У.) (3.2) для всех хех и ye Y. Множество всех ситуаций равновесия в игре Г обозначим через Z(r),Z(r)cXY. Для матричной игры Г^ речь идет о седловых точках матрицы выигрышей А, т. Таких точках (/., /.), что для всех iem ujen выполняются неравенства а,/. Внешние экстремумы у минимакса и максимина достигаются в точках у. и х.

соответственно. Пусть существуют минимакс и максимин max inf Кх, у)=inf K(x. У); (3.19) х у у min sup K(x. ^) = sup K(x, у.) (3.20) у х х и выполняется равенство (3.12).

Покажем, что ситуация (х., у.) является равновесной. Действительно, К(х. Y.)iof К(х. У)=max inf К(х, у); (3.21) у х у К(х.)к(х, у.) х для всех хех и je У, т. Заметим, что в ходе доказательства показано, что общее значение минимакса и максимина равно К(х.

Y.)=v значению игры, при этом любая минимаксная (максиминная) стратегия у.(х.) в условиях теоремы является оптимальной, т. Ситуация (х. У.) является равновесной. Из доказательства теоремы получаем следующее утверждение. Если минимакс и максимин в (3.11) существуют и достигаются нау и х соответственно, то max inf K(x, у)^к(х, у)^тт sup K(x, у).

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

Заметим, что в матричной игре Г А экстремумы в (3.11) всегда достигаются, поэтому теорема принимает следующий вид. 20 22 Следствие 2. Для того чтобы матричная (т х nj-игра Г^ была вполне определена, необходимо и достаточно выполнение равенства mm max а и = max mm a y.

J-l, 2., л i-1, 2., т i-l, 2., m J-l, 2. Я Например, в игре с матрицей равновесной. При этом max min a y =min max a y =2. ' J J С другой стороны, игра с матрицей весия, поскольку 3 1 О О (3.24) ситуация (2,1) является не имеет ситуации равноmin max а ц = 1 max min 0. (4.1) j ' ' J В этом случае максиминная и минимаксная стратегии не являются оптимальными. Более того, игрокам бывает невыгодно их придерживаться, так как они могут получить больший выигрыш.

Однако сообщение о выборе стратегии противнику может привести к еще большим потерям, чем в случае максиминной или минимаксной стратегии. Действительно, пусть матрица А имеет вид 7 3 А =. 53 сия (х., у.) единственная.

С точки зрения правил игры получаем, что дуэлянту не следует стрелять на 1-м шаге, он должен стрелять с равной вероятностью после 2-го и 3-го шагов, никогда после 4-го шага и лишь с малой вероятностью стрелять в упор. ИТЕРАТИВНЫЕ МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР Распространенный способ решения матричной игры путем сведения ее к задаче линейного программирования обладает тем недостатком, что процесс решения задачи линейного программирования существенно усложняется для матриц большой размерности. В таких случаях обычно используют методы декомпозиции задачи линейного программирования, когда вместо решения задачи с исходной матрицей строится координирующая задача с матрицей, у которой мало строк, но много столбцов. На каждой итерации координирующей задачи решается некоторая совокупность вспомогательных задач линейного программирования с матрицами меньших размерностей. К сожалению, декомпозиционные методы эффективны лишь для матриц специального вида (например, блочнодиагональных) Итеративный метод Брауна Робинсона (метод фиктивного разыгрывания). Идея метода многократное фиктивное разыгрывание игры с заданной матрицей выигрыша. Одно повторение игры будем называть партией.

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

Итак, предположим, что за первые к разыгрываний игрок / использовал i-ю стратегию

Рассмотрим отношения 52 l k /k=max 1 J ayrfilk^a^yrfilk, J. 61 ГЛАВА II БЕСКОНЕЧНЫЕ АНТАГОНИСТИЧЕСКИЕ ИГРЫ 1. БЕСКОНЕЧНЫЕ ИГРЫ 1.1. В этой главе рассматриваются антагонистические игры, которые отличаются от матричных тем, что в них один или оба игрока имеют бесконечное (счетное или континуум) множество стратегий. С теоретико-игровой точки зрения это отличие малосущественно, поскольку игра остается антагонистической и проблема состоит в использовании более сложного аналитического аппарата исследования. Таким образом, будем исследовать общие антагонистические игры, т. Системы вида Г=(Х, Y, Н), (1.1) где X и Y произвольные бесконечные множества, элементы которых являются стратегиями игроков 1 и 2 соответственно, а Н: Хх.

Y-.R l функция выигрыша игрока 1. Напомним, что правила антагонистической игры изложены в п. Выигрыш игрока 2 в ситуации (х, у) равен Щх, у), хех, yey (игра антагонистическая). В этой главе будем рассматривать такие игры, у которых функция Н ограничена Пример 1. (Одновременная игра преследования на плоскости.) Пусть Si и S 2 множества на плоскости.

Игра Г заключается в следующем. Пусть 1 выбирает некоторую точку xes u а игрок 2 точку yes 2. При совершении выбора игроки 1 и 2 не имеют информации о действиях противника, поэтому подобный выбор удобно интерпретировать как одновременный.

Точки xes v yes 2 являются в этом случае стратегиями игроков 1 и 2 соответственно. Таким образом, множества стратегий игроков совпадают с множествами S t и S 2 на плоскости. Целью игрока 2 является минимизация расстояния между ним и вторым игроком (игрок / преследует противоположную цель). Поэтому под выигрышем Щх, у) игрока 1 в этой игре будем понимать евклидово расстояние р(х, у) между точками xesi и у G S 2, т. Щх, у)=р(х, у), xes it yes 2. Выигрыш игрока 2 полагаем равным выигрышу игрока 1, взятому с обратным знаком (игра антагонистическая). (Поиск на отрезке.) Простейшей игрой поиска с бесконечным числом стратегий является следующая игра.

64 где 1(у) = Р(у-Уо), Р = (11-1о)1(У1-Уо), li=bi), 1 0 =Ъо)- Положительные числа х 0 У)= (Vi-^o) (.i-.o) В качестве функции выигрыша Щх, у) игрока 1 понимается производительность поиска, т. Просмотренная площадь в единицу времени Н(х, y)=2xl(x, у). Выигрыш игрока 2 полагаем равным Н(х, у).

Таким образом, получаем игру с функцией выигрыша Н(х, у)=2х l 0 bi-y)+li(y-yo) (.i-.) (У1-Уо) (Xi-x 0 ) тяе хех 0, Ху, уе у 0, уд. В заключение отметим специальный класс антагонистических игр, в которых Х= У=0, 1. В этих играх ситуации суть пары чисел (х, у), где х, уе0, 1. Эти пары задают точки единичного квадрата. Поэтому такие игры называются играми на единичном квадрате. Класс игр на единичном квадрате во многом характеризует бесконечные антагонистические игры и поэтому является базовым при исследовании бесконечных игр. В частности, примеры 2, 4, S примеры игр на единичном квадрате.

Пример 6 также игра на единичном квадрате, если положить х 0 =у 0 =0, x l =y l = l. СИТУАЦИЯ 8-РАВНОВЕСИЯ, 6-СЕДЛОВЫЕ ТОЧКИ И 6-ОПТИМАЛЬНЫЕ СТРАТЕГИИ 2.1. Как и во всякой антагонистической игре Г=(Х, Y, Н), в бесконечной игре принципом оптимального поведения игроков является принцип равновесия. Оптимальной (равновесной) является такая ситуация (х., у.), для которой выполняются неравенства Щх, у.).

69 вариант случая 1, когда центр круга S. Принадлежит границе множества S 2.

Вычислим величину v (рис. Пусть y 0 es 2. Тогда точка х 0, доставляющая max p(x, у 0 ), содсе52 впадает с точкой пересечения л: 0 прямой, проходящей через у 0 и центр О круга S lt с границей круга S lf наиболее удаленной от точки у 0. Действительно, круг радиусом ХоУ 0 с центром в точке у 0 содержит 5 Х и его граница касается границы круга S^ в единственной точке х 0. Очевидно, что величина max р(х, у 0 )=р(х 0, у 0 ) дсея, достигает минимума в точке М х пересечения отрезка О^М с границей круга S 2. Таким образом, в рассматриваемом случае,;, v=minmax p(x, y) = 0 1 M R 2 =v.

Оптимальные стратегии заключаются в выборе точек MeSi и M 1 es z игроками 1 и 2 соответственно. Если в качестве множеств стратегий в примере 1 п. 1.2 рассматривать открытые круги 5 А и S 2, то в случае 2 значение игры существует и равно «= sup inf p(x, y) = iaf sup p(x, у) =v = O i M R 2 = v. ' xes t yesj yes, xes t Однако оптимальных стратегий не существует, поскольку МфБ 1, М 1 фб 2. Тем не менее для любого Б0 существуют е-оптимальные стратегии это точки из е-окрестности точек М и M t, принадлежащие соответственно можествам 5 Х и S В заключение отметим, что игра в примере 6 имеет ситуацию равновесия в чистых стратегиях (см. 7), а игры в примерах 1 5, вообще говоря, не имеют ситуации равновесия и значения игры. Так, в примере 2 лишь при /^ 1/ 2 у игрока 1 есть оптимальная стратегия х.

= 1 / 2, а значение игры равно единице (у игрока 2 оптимальной является любая стратегия). СМЕШАННЫЕ СТРАТЕГИИ 3.1. Рассмотрим антагонистическую игру Т=(Х, Y, Н).

Если она не имеет значения, то vv. Для увеличения своего.

70 гарантированного выигрыша в таких случаях каждому игроку, как уже отмечалось в 4 гл. I, важно знать намерение противника. И хотя правила игры не представляют такой возможности, при достаточно частом повторении игры с одним и тем же противником можно статистически оценить возможность выбора той или иной стратегии и поступить определенным образом. Как же должен поступить игрок, не желающий, чтобы его намерение было раскрыто? Единственным разумным способом в этом случае является выбор стратегии случайным образом, в соответствии с определенным случайным механизмом, т. Необходимо использовать смешанные стратегии. Дадим формальное определение смешанной стратегии для бесконечной игры Пусть х некоторая а-алгебра подмножеств множества X (включающая в себя одноточечные множества хех) и v о- алгебра подмножеств Y (yev, если yey).

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

С точки зрения проблемы нахождения решения желательно, чтобы смешанные стратегии имели наиболее простой вид и в то же время в этом расширении существовало, по крайней мере, значение игры. Строго говоря, интеграл в (3.1) должен браться по мере /JXV на декартовом произведении Хх Y. Однако согласно правилам антагонистической игры смешанные стратегии (меры) fiiv игроками выбираются одновременно и независимо друг от друга, т. Вероятностные меры ц. И v стохастически независимы.

Ситуацией (ц, v) в смешанных стратегиях называется пара вероятностных мер fiex.vet, которые стохастически независимы. Таким образом, в ситуации (ц, v) в смешанных стратегиях выигрыш К(ц, v) равен повторному интегралу (3.1).

Одноточечные множества принадлежат (Т-алгебре подмножеств множества стратегий, на которой определяются вероятностные меры, поэтому каждой чистой стратегии х(у) можно поставить в соответствие вероятностную меру p. X ex(v y ey), сосредоточенную в точке хех (yey).

Отождествляя стратегии х и ц х, у и v, видим, что чистые стратегии являются частным случаем смешанных, т. Справедливы включения X v) = H(x,y)dv(y); (3.2) ч К(ц, у) =К(ц, v,) = H(x, y)d i i(x), (3.3) где интегралы в (3.1), (3.2), (3.3) понимаются в смысле Лебега Стилтьеса. Если же распределения ц(х), v(y) имеют плотности f(x) и g(y), т.

Учебник английского 9 класс кузовлев. Dp.(x)=f(x)dx и dv(y)=g(y)dy, то интегралы в (3.1), (3.2), (3.3) понимаются в смысле Римана Стилтьеса. Таким образом, Г с Г подыгра своего смешанного расширения Г. Будем считать, что все интегралы в (3.1) (3.2), (3.3) существуют, каковы бы ни были вероятностные меры ц и v. Пусть Г= (X, Y, Н) антагонистическая игра, а Т=(Х, Т, К) ее смешанное расширение.

Тогда ситуация (ц., v.) exx Т называется ситуацией равновесия в игре Г в смешанных стратегиях, если для всех fiexuve выполняются неравенства К(ц, v.) ^К(ц., v.).$К(ц., v), (3.4) т. V.) ситуация равновесия в смешанном расширении игры 70.

75 нимаксная стратегия у игрока 2 с точностью до а описывают оптимальное поведение игроков и могут быть взяты в качестве приближенного решения игры Г. Таким образом, в этом случае задача сводится к нахождению максиминных и минимаксных стратегий игроков 1 и 2 соответственно, а точность приближенного решения определяется величиной a=v + v, при этом значение игры v согласно (3.14) лежит в интервале vev, v +. Способам нахождения решения задач (3.15), (3.16) посвящена теория минимакса 31, 30 Как и в случае матричных игр, для бесконечных игр важную роль играет понятие спектра смешанной стратегии.

Пусть Г= (X, Y, Н) антагонистическая игра. Тогда чистую стратегию х 0 ех (y 0 ey) игрока 1 (2) называют точкой концентрации его смешанной стратегии ц (х), если р. (х 0 ) 0 (У(УО)0). Чистая стратегия х 0 ех (y 0 ey), где X (соответственно Y) топологическое пространство, называется точкой спектра смешанной стратегии ц (v), заданной на борелевской о-алгебре подмножеств множества X (Y), если для любой измеримой окрестности ш точки х 0 (у 0 ) имеет место неравенство /z(o))= ф(.)0(у(а)= dv(y)0). Т Спектром смешанной стратегии ц (v) назовем наименьшее замкнутое множество, ц-мера (v-мера) которого равна единице. Точки концентрации смешанной стратегии являются точками спектра; обратное, вообще говоря, неверно.

Так, чистые стратегии, в которых смешанная стратегия имеет положительную плотность, являются точками спектра, но они не являются точками концентрации. Спектр смешанной стратегии ц (соответственно v) будем обозначать Хр (Г,). Докажем аналог теоремы п. I о дополняющей нежесткости для бесконечных игр. Пусть Г=(Х, Y, Н) антагонистическая игра, имеющая значение v. Тогда, если х 0 ех, a v.

оптимальная смешанная стратегия игрока 2 и K(x 0,v.). ИГРЫ С НЕПРЕРЫВНОЙ ФУНКЦИЕЙ ВЫИГРЫША 4.1. В данном параграфе рассмотрим антагонистические игры Г=(Х, Y,H)B предположении, что пространства стратегий XuY метрические компакты (чаще всего они будут подмножествами евклидовых пространств), а функция Н непрерывна по обеим переменным.

Под множествами X, Y смешанных стратегий игроков 1 и 2 будем понимать множества вероятностных мер, заданных на о-алгебрах% и v борелевских множеств пространств X и Y соответственно. Тогда выигрыш K(ji, v) игрока 1 в ситуации (p., v)exxy в смешанных стратегиях измеримая функция относительно борелевской v (4.3) выполняется для всех точек yey. Если (4.1) не выполнено, то существует такая точка y 0 ey y., что К(р., y Q )v.

В силу непрерывности функции К(р., у) неравенство (4.3) в некоторой окрестности ю точки у 0 строгое. Из того, что у 0 е У. Точка спектра смешанной стратегии v., следует v.(to)0. Отсюда и из неравенства (4.3) получаем v=kqi., v.)=j К(ц., y)dv.(y)v. Y Противоречие доказывает справедливость (4.1).

Равенство (4.2) доказывается аналогично. Данный результат является аналогом теоремы о дополняющей нежесткости п. Напомним, что чистая стратегия х, входящая в спектр оптимальной стратегии, называется существенной. Таким образом, теорема утверждает, что для существенных стратегий должны быть выполнены равенства (4.1), (4.2). Пусть Г=(Х, Y, Н), X a jf, Yс Л' выпуклая игра. Тогда значение v игры Г определяется по формуле w=min тах#(л:, у).

У. Игрок 1 обладает оптимальной смешанной стратегией /х 0 с конечным спектром, состоящим не более чем из (и+ 1)-й точки множества X. В то же время все чистые стратегии у 0, на которых достигается min max Hx, у), являются оптимальными для игрока 2. Если, У х кроме того, функция Н(х, у) при каждом фиксированном хех строго выпукла по у, то оптимальная стратегия игрока 2 единст венна- Проиллюстрируем эти результаты на примере. Рассмотрим частный случай примера 1 (см. Пусть 5' 1 = 5' 2 =5 и множество S представляет собой замкнутый круг на плоскости с центром в точке О и радиусом R. Функция выигрыша Н(х, у)=р(х, y),xes,yes, где р функция расстояния в R 2, является строго вьшуклой по у при любом фиксированном х, a S выпуклое множество.

Поэтому согласно теореме п. 5.5 значение игры v равно «=min maxp(x, у).

(5.15) yes xes Вычисляя min max в (5.15), получаем, что v=r (см. При этом точка y Q es, на которой достигается минимум выражения тах/(х, у), единственная и совпадает с центром круга S (т. Xes точкой О). Эта точка и является оптимальной стратегией игрока 2 (минимизирующего). Теорема утверждает, что у игрока 1 (максимизирующего) существует оптимальная смешанная стратегия, предписывающая положительную вероятность не более чем трем точкам множества S. Однако вследствие симметрии множества S в действительности оптимальная смешанная стратегия ц 0 игрока 1 предписывает с вероятностью 1 / 2 выбирать любые две диаметрально противоположные точки на границе множества S.

Для доказательства оптимальности стратегий /х 0, у 0 достаточно установить, что К(х, y 0 )^K(pi 0, y 0 )^K(jx 0, у) для всех х, yes, где К математическое ожидание выигрыша, К(р 0, y 0 )=RI2 + R/2 = R. Действительно, К(х, y o )=p(0, x)^r и К(ц 0, y)=p(x v y)/2 + p(x 2, y)/2^r, где х 1 ах 2 произвольные диаметрально противоположные точки на границе круга S.

Оптимальность стратегий /х 0 и у 0 доказана Рассмотрим частный случай выпуклой игры Г=(Х, Y, Н), 90. 93 Множество уравновешивающих стратегий компактно, поэтому его можно покрыть конечным числом таких д (х)-окрестностей. Пусть Е наименьшее из всех соответствующих чисел е (х). Тогда имеем неравенство, справедливое для всех уравновешивающих стратегий х (в том числе и для всех существенных стратегий) Н(х, у)4:н(х, у 0 )-е/2, где у 0 -тшв(х)-e/2, что противоречит оптимальности стратегии ц 0. Пусть Г выпуклая игра на единичном квадрате с функцией выигрыша Н, дифференцируемой по у при любом х, Уо чистая оптимальная стратегия игрока 2,av значение игры.

Тогда: 1) если уо=1, то среди оптимальных стратегий игрока 1 имеется чистая стратегия х', для которой выполняется (5.18); 2) если уо=0, то среди оптимальных стратегий игрока 1 имеется чистая стратегия х', для которой выполняется (5.19); 3) если 0 0 (fi)= 'yv, y 0 )Hl-P)H;(x', у 0 ). Из (5.18), (5.19) следует, что 0, (fj) непрерывна, поэтому найдется. 94 Рассмотрим смешанную стратегию ц 0 игрока 1, заключающуюся в выборе стратегии х' с вероятностью а и стратегии х' с вероятностью 1. Функция К(ц 0, у)=анх!, у)+(1-«)н(х', у) выпукла. Ее производная по у в точке у=у 0 равна K' y (ji 0, Уо)=хн;(х', у 0 )+у -«)#;(.' , Уо)=о. Следовательно, в точке у 0 функция К(ц 0, у) достигает минимума.

Отсюда, учитывая (5.17), имеем К(Ио yo)0, так что игра Г строго выпуклая, поэтому игрок 2 имеет единственную оптимальную стратегию, которая является чистой (теорема п. Пусть у фиксированная стратегия игрока 2. Тогда тах(х X Таким образом, из (5.16) -.-'-. если у1/2.»=min. Оба внутренних минимума достигаются на у 0 =1/2 и принимают значение 1/4. Поэтому ю= 1/4, а у 0 = 1/2 единственная оптимальная стратегия игрока 2. Найдем оптимальную стратегию игрока 1.

Для этого заметим, что 0. 105 Игра является симметричной, поэтому v = 0, а оптимальные стратегии игроков совпадают. Здесь оба игрока имеют чистую оптимальную стратегию;с.=. = 1/2. Действительно, #(1/2, у)=6 (1/2, у) = 1-2у О, если у 1/2. С точки зрения интерпретации игры решение предписывает дуэлянтам стрелять одновременно, когда каждый пройдет половину дистанции до барьера. В заключение следует отметить, что класс игр с выбором момента времени хорошо изучен (см.

РЕШЕНИЕ БЕСКОНЕЧНЫХ ОДНОВРЕМЕННЫХ ИГР ПОИСКА В этом параграфе будет приведено решение игр поиска с бесконечным числом стратегий, сформулированных в п Первая из рассматриваемых игр интересна тем, что в ней оба игрока имеют оптимальные смешанные стратегии с конечным спектром Пример 18. (Поиск на отрезке). Рассмотрим задачу поиска на отрезке (см. 1.1), которая моделируется игрой на единичном квадрате с функцией выигрыша Н(х, у) вида я ( jl, если.-, 1/2 у игрока 1 имеется чистая оптимальная: стратегия х. = 1/2 и значение игры равно единице, поскольку в этом случае Н(х., у)=н(1/2, у)=1, так как у-1/2 ^ 1/2^/для всех уе0, 1. Предположим, что / 1 1. Действительно, Щх,у)=Н(1,у)= 1 п ПрЯуе Ц (О в противном случае, и если х 1+Х ' (О в противном случае.

Таким образом, при хе0, 1. Рассмотрим следующую смешанную стратегию ц.

игрока ). Пусть l=x l 11т. (8.2) Пусть теперь v. стратегия игрока 2, которая состоит в равновероятном выборе точек 0=у 1. 110 к^' ч 1 -$) значение рассмотренной игры поиска Рассмотрим вариант предыдущей игры, полагая, что игрок 2 выбирает некоторое односвязное множество Ус С и целью игрока 1 является максимизация площади пересечения МГО^^^П U S( X/,r) j-i Цель игрока 2 противоположна. В остальном игра совпадает с игрой, рассмотренной в начале параграфа. Стратегия ц.

Майкл уилкокс синий и желтый не дают зеленый читать. игрока 1 совпадает с таковой в предыдущей игре. Смешанная стратегия v.

игрока 2 строится аналогично стратегии р. и заключается в случайном бросании множества У на сферу (в предыдущем случае игрок 2 случайно выбирал точки yeq. Таким образом, v.

строится как инвариантная мера, которая состоит из случайного (в соответствии с равномерным распределением на С) выбора одной из фиксированных точек множества У на С и далее поворота У вокруг этой точки на случайный угол (в соответствии с равномерным распределением на 0, 2л). Пусть К(х, v), К(ц,у) соответствуют математическим ожиданиям площади пересечения L(Y )M X ). Тогда КОЛ у)=кх, v.)=k0i», v.) Если У г-окрестность точки у, то значение игры равно K(fl., V.) =.5 (R-y/tf-t 3 ). Упражнения задачи LY)LMJ г. Игра нападения защиты. Игрок 1 силами А единиц намерен атаковать один из объектов C i С, ценность которых определяется числами t x О, х 2 О. Т 0, причем т 1 т 2.т я.

Петросян Зенкевич Теория Игр

Чистой стратегией х игрока 1 является вектор Jc=(f t ( п ), л ii=a, где i часть сил, выделенных для атаки объекта Q. Суммарные силы обороняющейся стороны (игрок 2) равны В. Чистой стратегией у игрока 2 является выбор набора неотрицательных чисел y=(viы) удовлетворяющих условию л t i=b, где щ часть сил, предназначенных для защиты объекта Cj. Результат таки на объект С, пропорционален разности / щ, если силы атакующих превосходят силы защищающихся, а в остальных случаях он равен нулю. Построить функцию выигрыша. Игра на единичном квадрате имеет функцию выигрыша Н(х,у)=ху-1/Зх- 12у.

Показать, что (1/2, 1/3) ситуация равновесия в этой игре. Показать, что игра на единичном квадрате с функцией выигрыша H(x,y)=siga(x-y) имеет седловую точку. 4 Показать, что игра на единичном квадрате типа дуэли с функцией выигрыша 109.

111 Г-1/х 2, xy, H(x, y)- = Х?И, уфо, хш1 '. 0-1/2+х, хф, =0, 2, х=1, у=0 пара (х ,), где х, = 1 e,y t =e, является ситуацией е-равновесия. Имеет ли эта игра значение? Решить игру «поиска шумного объекта», сформулированную в примере 6 п Вычислить выигрыш игрока 1 в игре на единичном квадрате с функцией выигрыша Н(х, у) в ситуации (F(x), G(y)) (FuG функции распределения), если: а) Н(х, y)=(x+y)/(4xy), F(x)=x., G(y)= 2; б) H(x,y) = x-y (l- x-y ), F(x) = x, G(y)=y; в) H(x, y)=x-y) 2, F(x) = l/2/ 0 (x)+l/2/ 1 (x), G(y)=I m x), где /jt(x) ступенчатая функция. Игра дискретного поиска.

Рассматривается следующая бесконечная игра. Стратегия игрока 2 заключается в выборе точки, равномерно распределенной на окружности радиуса у, где у может принимать значения из интервала 0, 1. Игрок 1 может просмотреть в единичном круге односвязную область Q, площадь которой e(0 = e=const, где ае0, 1. Найти решение игры. Доказать теорему Хелли п Рассмотрим непрерывный аналог игры «обороны города» (п.

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

Построить функцию выигрыша Н(х, у) игры на единичном квадрате. Показать, что данная игра не имеет решения в смешанных стратегиях. Воспользоваться результатом примера 10 п Показать, что в непрерывной игре с функцией выигрыша стратегии F.(x)=Ii/ 2 (x), G.(y)=l/2I 0 (y) + l/2i 2 (y) оптимальны для игроков 1 и 2 соответственно. 119 ним из них является равновесие по Нэшу и его различные обобщения. В случае, когда игра Г является антагонистической, равновесие по Нэшу совпадает с понятием равновесия, которое представляет собой основной принцип оптимальности в антагонистической игре. Пусть х х х.,.;!, х, x i+i., х ) произвольная ситуация в игре Г, а х,- некоторая стратегия игрока i.

Построим ситуацию, которая отлична от х только тем, что стратегия х,- игрока i заменена на стратегию х. В результате мы получаем ситуацию (х 1., х, xj, Xi+u х ), которую будем обозначать через (x xj)- Очевидно, что если х, и xj совпадают, то (x xj)=x.

Ситуация x.=(xf., xf., х.) называется ситуацией равновесия по Нэшу, если для всех x^xju i=l. П имеет место неравенство Я,(х.)^Я,(х. х; ). (2.1) Пример 6. Рассмотрим игру примера 3 п Равновесными по Нэшу здесь являются ситуации, для которых выполняется условие t 0^t.-l/n, t. + l/n^t u (2.2) л где f.=(l/n) Y, Х Т- Из условия (2.2) следует, что переключение 7-1 каждого отдельного игрока с одной чистой стратегии на другую при условии, что другие игроки своих стратегий не изменяют, не влияет на его выигрыш.

Пусть в игре реализовалась ситуация х, которой соответствует t=(l/ri) Xj, tet 0, tj, и пусть величина «5 доля игроков, решивших переключиться со стратегии 0 на стратегию 1. Заметим, что если 8 таково, что b(t) = a(t).

120 но на стратегию 1. При осуществлении этого желания доля л 1/и Y, X J увеличится и вновь вернется на отрезок / 0, /J Из определения ситуации равновесия по Нэшу следует, что ни один из игроков i не заинтересован в отклонении от стратегии х., входящей в эту ситуацию (согласно (2.1) его выигрыш при использовании стратегии x t вместо xf разве лишь уменьшится при условии, что остальные игроки придерживаются стратегий, образующих ситуацию равновесия х.). Таким образом, если игроки договорились предварительно об использовании стратегий, входящих в ситуацию равновесия JC., TO индивидуальное отклонение от договора невыгодно отклонившемуся игроку. Стратегия xfexj называется равновесной, если она входит хотя бы в одну ситуацию равновесия по Нэшу. Для бескоалиционной игры двух лиц r = (Z l5 Х 2, Н и Н?) ситуация (х., у.) является ситуацией равновесия, если неравенства Н, (х, y.hh, (х., у.), Н 2 (х., унн 2 (х., у.) (2.3) выполняются для всех xex t uyey 2.

В частности, для биматричной (т хи)-игры Г (Л, В) пара (г., /.) будет ситуацией равновесия по Нэшу, если неравенства «. Если в игре Г существует ситуация равновесия, ах максиминная и у минимаксная стратегии соответственно 1 и 2 игроков, то (х, y)ez (Г) ситуация равновесия, и наоборот. Выясним, выполняются ли эти свойства для биматричных игр. Рассмотрим игру «семейный спор» (см. Пример 1 и п. Как уже отмечалось, в ней есть две равновесные ситуации (а 1; /? 122 смысле, что различные ситуации равновесия могут быть в разной степени предпочтительными для различных игроков.

Таким образом, остается не решенным вопрос: какую из ситуаций равновесия можно принять как устраивающий всех игроков принцип оптимальности? В дальнейшем будет показано, что множественность принципа оптимальности является существенной характерной чертой оптимального поведения в конфликтных управляемых процессах со многими участниками. Заметим также, что в отличие от антагонистического случая равновесная стратегия i-го игрока JC. далеко не всегда обеспечивает получение, по крайней мере, выигрыша Я;(х.) в ситуации равновесия по Нэшу, поскольку это существенно зависит от того, выберут ли остальные игроки стратегии, входящие в данную ситуацию равновесия по Нэшу.

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

Пусть S с N некоторое подмножество множества игроков (коалиция) и пусть x=(x t., х ) ситуация в игре Г. Обозначим через (х х' л ) ситуацию, которая получается из ситуации х при замене в ней стратегий x h ies, на стратегии x' i ex i, ies. Иными словами, в ситуации (x x' s ) игроки, входящие в коалицию S, заменяют свои стратегии x t на стратегии JCJ. Если х. ситуация равновесия по Нэшу, то из (2.1) вовсе не следует, что Я, (х.) Я, (xf x s ) для всех ie S. (2.7) Это будет показано далее на простейших примерах. Можно усилить понятие равновесия по Нэшу, потребовав выполнения условия (2.7) или ослабленного условия (2.7) хотя бы для одного из игроков ies.

Тогда мы приходим к следующему определению. Ситуация х. называется сильно равновесной, если для любых коалиций S а N и x s e J X, выполняется неравенство ies #,(.

) Ел,.!!.). (2.8) /65 ies Условие (2.8) гарантирует нецелесообразность соглашения между игроками с целью вступления в некоторую коалицию S, так как в любой коалиции находится игрок /, которого это соглашение не 121. 137 или Ау^(хАу)и, хв ^(хву)и. Проверим справедливость этих соотношений для х= и у= А ' 1и иа' 1 и тя. Имеем Л У=7^Т =, -1»,-i М ха У) и иа 1 и (ив 1 и)(иа '«) ub l u (ив- х и)(иа- х и) v ив- у ив 1 и что и требовалось доказать. Проиллюстрируем применение теоремы на примере игры «семейный спор» п Рассмотрим смешанное расширение игры. Множество точек, соответствующих векторам выигрышей в смешанных стратегиях, можно изобразить графически (рис.

Нетрудно заметить, что игра удовлетворяет условиям теоремы, поэтому здесь имеется единственная вполне смешанная ситуация равновесия (х, у), вычисляемая по формулам (5.11) (5.13): х=(4/5, 1/5),у=(1/5,4/5),(«1.«2 ) = (4/5,4/5) Рассмотрим свойства различных принципов оптимальности. Заметим, что определения оптимальности ситуации по Парето и Нэшу, приведенные в 2, касаются произвольной бескоалиционной игры (в частности, двух лиц), поэтому они справедливы и для смешанного расширения Г.

Следовательно, для игры двух лиц г(г)=^пг 2 (где Z(T) множество ситуаций равновесия по Нэшу, Z 1 и Z 2.множества наилучших ответов игроков 1 и 2 соответственно в игре Г) и справедлива теорема о борьбе за лидерство (см. В более сложном отношении находятся ситуации, равновесные по Нэшу и оптимальные по Парето. Из примеров 2 следует, что возможны случаи, когда ситуация равновесна по Нэшу, но не оптимальна по Парето, и наоборот. Вместе с тем возможно, что одна и та же ситуация оптимальна и в том и в другом смысле (п. В примере 11 п.

3.3 было показано, что дополнительная ситуация равновесия, возникающая в смешанном расширении игры Г, не является оптимальной по Парето в смешанном расширении Г. Оказывается, что это довольно распространенное свойство биматричных игр. Пусть Г (А, В) биматричная (т х п)-игра. Тогда почти для всех (тхп)-игр (за исключением не более чем счетного множества игр) справедливо следующее утверждение. 139 венства aiia 21, a 12 a 22 приводят к тому, что в игре Г чистая стратегия д^ строго доминирует все остальные смешанные стратегии первого игрока. Поэтому ситуацией равновесия является пара (pi2i т гх если Pu Pi2 Ргх^гг.

причем det АФО, йеьвфоя поэтому выполняются условия теоремы п Поэтому в игре существует ситуация равновесия (х., у.), где,j bz. Pii+Pii- -Ри Р11+Р22-Р21-Р12, д.1 РП-РИ.

(514) у. J.HZ^ 1 «AiZ^ (5.15).ll + a 22 -.ai '12 Я 11+ а 22 а 21 а 12/ а соответствующие равновесные выигрыши v i и v 2 определяются по формулам а 11 Я 22 -Я 12 а 21. PllPl a 22 a 12 «21 Pll+P22-Pl2-P21 Случай 3. Игра Г имеет две ситуации равновесия по Нэшу.

Петросян Зенкевич Шевкопляс Теория Игр

Этот случай получается, когда выполнено одно из условий: а) a 21 б) a u «X 21, «22 Pl2.