ТЕОРИЯ ИГР. Учебник и практикум Шагин В.Л. ПрактикУм для академического бакалавриата Рекомендовано Учебно методическим отделом высшего образования в качестве учебника для студентов высших учебных заведений
 Скачать 367.99 Kb.
|
|
В. Л. Шагин Москва Юрайт 2015 ТЕОРИЯ ИГР Учебник и практикУм для академического бакалавриата Рекомендовано Учебно-методическим отделом высшего образования в качестве учебника для студентов высших учебных заведений, обучающихся по экономическим направлениям и специальностям Êнига äостóïна в ýëåктронной áиáëиотå÷ной систåìå biblio-online.ru ВЫСШАЯ ШКОЛА ЭКОНОМИКИ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ УДК 519.83(075.8) ББК 22.18я73 Ш15 Автор: Шагин Вадим Львович — доцент кафедры математической экономики и экономет рики Департамента прикладной экономики факультета экономики Национального исследовательского университета «Высшая школа экономики». Рецензенты: Молоствов В. С. — кандидат физикоматематических наук, доцент кафедры выс шей математики факультета экономики Национального исследовательского универ ситета «Высшая школа экономики»; Соловьев Ю. П. — доктор экономических наук, профессор кафедры математических методов в экономике Российского экономического университета им. Г. В. Плеханова. Ш15 Шагин, В. Л. Теория игр : учебник и практикум для академического бакалавриата / В. Л. Шагин. — М. : Издательство Юрайт, 2015. — 223 с. — Серия : Авторский учебник. ISBN 9785991646963 Книга написана на основе многолетнего опыта чтения курса «Теория игр» студен там НИУ ВШЭ (факультеты экономики, мировой экономики и мировой политики, МИЭФ). В главах последовательно описаны основные понятия теории некооперативных игр. Рассмотрены статические и динамические игры с полной и неполной, с совер шенной и несовершенной информацией. Изложение теоретического материала тесно переплетается с множеством практических примеров, что дает возможность глубже осмыслить основные понятия теории игр. Для студентов и преподавателей экономических вузов (на факультетах эконо- мики, менеджмента, политологии ). УДК 519.83(075.8) ББК 22.18я73 ISBN 9785991646963 © Шагин В. Л., 2014 © ООО «Издательство Юрайт», 2015 3 Огëавëåниå Предисловие ..................................................................................... 5 Глава 1. Основные понятия теории игр. Классификация и описание игр ...........................................................7 1.1. Основные понятия теории игр .......................................................................................7 1.2. Классификация игр ..........................................................................................................10 1.3. Формы описания игры ....................................................................................................12 1.3.1. Развернутая (экстенсивная) форма описания игры .................................12 1.3.2. Нормальная форма описания игры ................................................................13 Контрольные вопросы и задания .........................................................................................15 Глава 2. Статические игры .................................................................16 2.1. Доминирующие и недоминируемые стратегии ......................................................16 2.2. Игры двух участников с противоположными интересами. Осто рожные (минимаксные и максиминные) стратегии. Нижняя и верхняя цена игры. Седловая точка ......................................................19 2.3. Смешанные стратегии и теорема о минимаксе для матричных антагонистических игр ...................................................................................................26 2.4. Решение игр 2 × n и m × 2 ................................................................................................31 2.5. Сведение конечной матричной игры к задаче линейного программирования ...........................................................................................................34 2.6. Решение антагонистической игры в программе MS Excel .................................44 2.7. Игры с непротивоположными интересами. Равновесие Нэша. Паретооптимальность ..............................................................48 2.8. Равновесие дрожащей руки...........................................................................................69 2.9. Бесконечные игры ............................................................................................................72 2.10. Экономические приложения ......................................................................................76 Задания для самостоятельной работы ............................................................................78 Глава 3. Динамические игры с полной информацией ...........................82 3.1. Динамические игры с полной и совершенной информацией ...........................82 3.2. Модель дуополии Штакельберга ................................................................................90 3.3. Последовательная торговая сделка (модель Рубинштейна) .............................91 3.3.1. Трехэтапная торговля .........................................................................................91 3.3.2. Многоэтапная торговля ......................................................................................93 3.4. Последовательные игры с полной, но несовершенной информацией ...........93 3.5. Модифицированная модель Штакельберга ............................................................94 3.6. Развернутая форма представления игр .....................................................................97 3.7. Совершенное подыгровое равновесие Нэша ........................................................ 101 3.8. Последовательные игры с участием Природы .................................................... 116 Задания для самостоятельной работы ......................................................................... 119 Глава 4. Повторяемые игры ............................................................. 124 4.1. Двукратно повторяемая игра ..................................................................................... 124 4.2. Бесконечно повторяемые игры ................................................................................. 126 4.3. Стратегии переключения ............................................................................................ 129 4.4. Достижимые платежи и теорема Фридмана ........................................................ 134 4.5. Модель дуополии Курно (бесконечное число раз повторяемая игра) ....... 138 4.6. Предельные Паретооптимальные профили стратегий ................................... 143 Задания для самостоятельной работы ......................................................................... 147 Глава 5. Игры с неполной информацией ........................................... 149 5.1. Введение в байесовские игры .................................................................................... 149 5.2. Нормальная форма представления статических байесовских игр ............... 151 5.3. Разделяющее равновесие Байеса — Нэша............................................................. 156 5.4. Модель Штакельберга при асимметричной информации .............................. 162 5.5. Аукционы .......................................................................................................................... 165 5.5.1. Закрытый аукцион первой цены ................................................................... 165 5.5.2. Симметрические стратегии ............................................................................. 167 5.5.3. Форматы аукционов .......................................................................................... 168 Задания для самостоятельной работы ......................................................................... 169 Глава 6. Динамические игры с несовершенной информацией ............. 174 6.1. Введение в слабое секвенциальное равновесие .................................................. 175 6.2. Сигнализирующие игры .............................................................................................. 179 6.3. Примеры игр с неполной и несовершенной информацией ............................. 184 Задания для самостоятельной работы ......................................................................... 212 Список литературы ......................................................................... 217 Ответы ........................................................................................... 218 Предметный указатель.................................................................... 222 5 Прåäисëовиå Данный курс читается автором студентам бакалавриата экономических специальностей Национального исследовательского университета Высшей шко лы экономики в течение последних четырнадцати лет, а также в Высшей школе финансов и менеджмента РАНХиГС при Президенте РФ. Теория игр настоль ко тесно переплетается с жизнью, что это не про сто математиче ская дисциплина. Можно сказать, что это в какойто сте пени ми ровоззрение. Везде, где сталкиваются интересы двух или более ин дивидуумов, складывается игровая ситуация. Это в первую оче редь эко номика, где есть игроки — продавцы и покупатели, нани маемые работники и работодатели, государство и фирмы и т.д. Это и менеджмент, и страховое дело, и юриспруденция, и полити ка. В любой из перечисленных отраслей знаний возможны столкно вения интересов различных групп людей. Методика преподавания курса теории игр в российских университетах ориентирована скорее на слушателей математических факультетов и часто неприемлема для экономистов и менеджеров с меньшим уровнем математи ческой подготовки. В книге предпринята попытка приблизить уровень изло жения к экономистам не только за счет примеров из экономики, но и за счет более подробного и неформального изложения материала. Этим объясня ется и стиль изложения материала, при котором смешиваются вопросы тео рии и примеры. Книга состоит из шести глав и включает в себя все разделы теории неко оперативных игр. В конце каждой главы приводятся упражнения для само стоятельной работы, а в конце книги даны ответы к ним. По окончании изу чения данного курса студент должен: знать • основные понятия теории игр; • формы представления игр; • игровые методы, стратегии и модели; • равновесия в играх; уметь • классифицировать игровые ситуации; • формулировать цели и стратегии игроков; • находить равновесные профили стратегий; • анализировать информацию, которой обладают игроки; • строить модель игры, соответствующую рассматриваемой задаче; • рассчитывать игровые модели (как аналитически, так и с помощью компьютера); • анализировать результаты моделирования; владеть • навыками определения равновесий в играх; • навыками подготовки обоснованных решений игровых задач; Хочется сказать слова благодарности студентам НИУ ВШЭ, прослушав шим данный курс и высказавшим свои замеча ния. Искренняя благодарность Борису Борисовичу Демешеву за ценные реко мендации и советы при подготовке курса. Многие его замечания, а также разнообразные примеры очень помогли автору при написании книги. Автор также благодарит редактора Павла Александровича Макарова за внимательное прочтение рукописи и устранение недочетов. Все замечания и рекомендации прошу высылать по адресу: vadimshagin07@yandex.ru. 7 Гëава 1 . ОснОВныЕ ПОнЯТИЯ ТЕОРИИ ИГР. ÊЛассИфИÊацИЯ И ОПИсанИЕ ИГР Изучив материал данной главы, студенты должны: знать • предмет изучения теории игр; • понятия стратегии и профиля стратегий; • нормальную и развернутую формы представления игры; уметь • описывать игровые ситуации в виде игры в нормальной или развернутой форме; владеть • базовыми понятиями теории игр. 1.1. Основныå ïонятия тåории игр В данной главе рассмотрены основные понятия теории игр. Для лучшего понимания рассмотрим две жизненные ситуации. Ситуация 1. Покупатель пришел на рынок и собирается купить поми доры. Подходит к первому продавцу и начинает с ним торговаться. Задача покупателя — купить подешевле и хорошего качества, задача продавца — продать подороже. Ситуация 2. Два (или более) ценителя живописи пришли на аукцион для приобретения картин. Каждый из них готов уплатить некоторую сумму за пред лагаемый товар, но картина будет продана тому, кто предложит бóльшую цену. По условиям аукциона они предлагают цену одновременно, не зная, какую цену предложит конкурент. Задача каждого — купить подешевле, но чтобы при этом предложенная им цена превышала предлагаемую цену соперника. Что общего в этих ситуациях? Есть несколько человек, принимающих решение, причем выигрыш каждого из них зависит не только от его соб ственных действий, но и от действий другой стороны. Теория игр рассматривает ситуации, при которых сталкиваются инте ресы двух или более сторон, преследующих различные цели. Такие ситуа ции называют конфликтными. Стороны, участвующие в конфликте, назы ваются игроками. Игроками могут быть как отдельные лица, так и группы лиц (партнеры в бизнесе, фирмы и т.д.). Последовательные действия каж дого из игроков зависят от действий, предпринятых ранее другими игро ками. Таким образом, теория игр изучает конфликтные ситуации. 8 Следует отметить, что под конфликтом будем понимать не только анта гонистическое взаимодействие сторон. Игроки могут и помогать друг другу, при условии совпадения (возможно, частичного) их целей. Главное — это то, что действия каждого игрока влияют на интересы других игроков и, наобо рот, интересы каждого игрока зависят от действий остальных. Игра всегда ведется по определенным правилам, известным каждому из игроков. Интересы игроков определяются функциями выигрыша, или платежными функциями (payoff function). Игроки в ходе игры последова тельно осуществляют некоторые действия, выбирают один из вариантов — делают ходы. Однако выигрыш игрока определяется не только его ходами, но и ходами других игроков, а также, возможно, и случайными ходами, пред усмотренными правилами игры (например, расклад после сдачи в карточ ной игре либо бросание игральной кости). Последовательность ходов состав ляет партию. Рассмотрим для примера следующую игру, условие которой можно представить, либо сформулировав правила, либо изобразив ее в виде так называемого дерева (рис. 1.1). Саша Маша Маша A C D E F B (2; 1) (1; 2) (–1; 3) (2; 2) Рис. 1.1 Пусть играют два игрока — Саша и Маша. Сначала Саша выбирает ход (A или B). Если он выбирает A, то далее Маша выбирает C или D, и игра заканчивается. При ходе C выигрыши Саши и Маши равны соответственно 2 и 1, а при ходе D — 1 и 2. Если же Саша выберет ход B, то далее ходит Маша (E или F), и игра заканчивается При выборе хода E Сашин выигрыш равен –1 (это означает проигрыш 1), а Маша выигрывает 3. При ходе F выигрыши обоих игроков равны 2. Эту же игру удобно представить в виде дерева (см. рис. 1.1), на котором есть начальный узел (начало игры), решающие узлы (в которых один из игро ков должен сделать ход) и терминальные узлы (конечные точки, в которых отображены выигрыши игроков при соответствующих ходах). Два числа в терминальных узлах, разделенные точкой с запятой, означают выигрыши соответственно Саши и Маши. Начальный узел также является решающим. При выборе ходов игрок руководствуется стратегией — набором правил (инструкций), формулируемых до игры и однозначно определяющих выбор 9 действий при каждом ходе в зависимости от сложившейся ситуации («Если ситуация сложится такаято, то я поступлю такто…»). Иначе говоря, стра тегия — это полный набор указаний, как нужно поступать во всех ситуа циях в данной партии. При выборе стратегии предполагается, что противник в игре не глупее нас . Чтобы понимать, как будет действовать противник, надо иметь воз можность поставить себя на его место и, следовательно, знать возможные варианты выбора его стратегий. Поэтому теория игр занимается вопросами выбора стратегий игроками в предположении, что множества возможных стратегий каждого игрока известны всем игрокам. Рассмотрим представленную выше игру (см. рис. 1.1). У Саши две стратегии: A и B. У него один решающий узел (начальный), и его стратегия определяется ходом (A или B). Иногда возникает путаница между понятиями «стратегия» и «ход» в игре. Если действия игрока соответствуют только одному решающему узлу, как, например, действия Саши, то выбор стратегии определяет выбор хода. В этом случае ход игрока совпадает с его стратегией. В противном слу чае, когда игроку соответствуют два решающих узла или более, возникает альтернатива для действий игрока и его инструкции носят более сложный характер. У Маши два решающих узла, и задание ее возможных стратегий предполагает следующую инструкцию: 1. Как поступать после хода Саши A? 2. Как поступать после хода Саши B? Удобно стратегию Маши описать двумя буквами. Первая буква отвечает на первый вопрос, вторая — на второй. У Маши тогда будет четыре страте гии: CE, CF, DE и DF. Каждая из четырех стратегий является инструкцией для Маши: как сделать выбор после хода Саши A и после его хода B. Стратегия Маши CE, например, означает: «Если Саша сделает ход A, то я (Маша) пойду C, а если Саша сделает ход B, то я пойду E» (здесь и в дальнейшем мы будем формулировать стратегию от первого лица). В теории игр имеется некоторое ограничение: не предполагается наличие множества целей — целевая функция только одна. Цель каждого игрока — максимизация своей функции выигрыша, но не минимизация выигрыша остальных игроков. Математическая модель игры предполагает, что каждый игрок до игры выбирает свою стратегию (сознательно или случайным образом, но в послед нем случае с известным распределением вероятностей) и строго придержи вается выбранной стратегии на протяжении всей игры. Это означает, что после осуществления выбора стратегий всеми игроками игра может осу ществляться без участия самих игроков. При этом результат игры будет либо полностью предопределен (если не используются случайные ходы), либо зависит от разыгрывания «случайностей», распределение вероятно стей которых считается известным и поэтому может также осуществляться без участия самих игроков. И наконец, введем еще одно важное понятие — «профиль стратегий» (outcome, синонимы: исход, ситуация). 10 Профиль стратегий — это набор стратегий по одной для каждого игрока. Для n игроков профиль стратегий можно сравнить с n-мерным вектором s s s s s n = ( , , , , ) 1 2 3 … , в котором каждый игрок выбирает значение только одной из координат: первый игрок выбирает s 1 , второй — s 2 и т.д. Но в курсе тео рии игр принята несколько иная терминология. Координатам соответствуют стратегии, а вектору — профиль стратегий. Точное формализованное опре деление профиля стратегий дано ниже, в параграфе 1.3. Применительно к рассмотренной выше игре профилями стратегий явля ются, например, ( ; ) A CE или ( ; ) A DE . Всего в данной игре две стратегии у первого игрока, четыре стратегии у второго и 2 4 8 × = профилей. Иногда в игре принимает участие особый игрок, имя которому «Природа» или «Случай». Особенность этого игрока заключается в том, что он, вопервых, выбирает ходы в соответствии с некоторыми вероятностями и, вовторых, не имеет функции выигрыша. Обычно на дереве игры этот игрок обозначается буквой N (от Nature). 1.2. Êëассификация игр В предыдущем параграфе мы знакомились с языком теории игр, ввели понятия стратегии игрока, профиля стратегий. В данном параграфе рассмот рим классификацию игр по различным признакам. По возможности предварительных (до игры) договоренностей. Игроки могут вступать в коалиции — группы игроков, объединенных одной общей целью и координирующих свои действия. Игры с принимаемыми до игры соглашениями между игроками о своих стратегиях называются коопера- тивными. В противном случае игра некооперативная. В данном учебнике рассматриваются только некооперативные игры. По количеству стратегий. Различают конечные и бесконечные игры. В конечных играх и количество стратегий каждого игрока конечно. По наличию элементов случайности при выборе стратегий. Различают чистые и смешанные стратегии. Чистые стратегии построены на инструк циях, не использующих случайные числа. Применительно к рассмотрен ному выше примеру у Саши две чистые стратегии (A и B), у Маши четыре чистые стратегии (CE, CF, DE, DF). Смешанные стратегии предполагают использование датчика случайных чисел непосредственно перед выбором чистой стратегии. Так, например, Саша может подбросить монету и при выборе хода (A или B) положиться «на случай»: «орел» — выбор хода A, «решка» — выбор B. Маша также может использовать датчик случайных чисел и выбрать стратегии CE и CF,к примеру, с вероятностями 0,7 и 0,3 соответственно. Запишем эту смешанную стратегию следующим образом: 0 0 , , 7 3 CE CF + . Это будет означать, что перед выбором между CE и CF Маша реализует случайное число x U ∼ [ ; ] 0 1 , равномерно распределенное на еди ничном отрезке. Если окажется, что x ≤ 0,7, то Маша выбирает CE, в про тивном случае — CF. Выбор игроком смешанной стратегии заключается в выборе вектора вероятности на множестве чистых стратегий. 11 По свойствам функции выигрыша. В общем случае платежная функция может быть любой. Простейшими случаями для игры двух игроков явля ются следующие два: а) игры с нулевой суммой — игры, в которых сумма выигрышей игроков равна нулю. В случае двух игроков (антагонистиче ские игры) это означает: выигрыш одного из игроков равен проигрышу дру гого; б) альтернативой играм с нулевой суммой являются игры с ненуле- вой суммой. Игроки могут выигрывать (или проигрывать) одновременно. По правилам осуществления ходов. Игроки могут делать ходы одно- временно . Такие игры называются статическими. Примером статиче ской игры является игра в «орлянку» при одновременном выбрасывании монеты или игра в «четнечет» при одновременном выбрасывании пальцев. Альтернативой являются динамические игры, в которых игроки выполняют ходы последовательно. Например, сначала первый игрок делает ход, затем второй игрок, проанализировав ход первого игрока, делает свой ход и т.д. Примером последовательной игры являются шахматы. По информации, которой располагают игроки. а) В играх с полной информацией каждый из игроков имеет полную информацию о платежных функциях каждого игрока. В этом случае они могут исключить из рассмотрения заведомо проигрышные стратегии дру гих игроков, а это, в свою очередь, может повлиять и на выбор собствен ной стратегии. б) В играх с неполной информацией некоторые из игроков (по крайней мере один) не располагают полной информацией о платежных функциях всех других игроков. Тогда они ориентируются на свою функцию вы игрыша и на вероятностное распределение на множестве возможных функций вы игрыша других игроков. Полезность информации приводит к вопросу о возможности ее приобретения, например покупки. в) В играх с совершенной информацией каждый игрок при осуществле нии своего хода знает всю предысторию развития игры, т.е. всю последо вательность осуществляемых игроками ходов от начала игры до текущего момента. г) В играх с несовершенной информацией хотя бы один из игроков при осуществлении какогото своего хода не располагает полным знанием всей предыстории развития игры. Например, игрок на четвертом ходе не знает, каков выбор сделал его противник на предыдущем ходе. Следует отметить, что данная классификация игр не является единой и общепринятой и носит, в общем, индивидуальный характер: в других книгах можно встретить иной подход к классификации игр. Более того, одну и ту же игру иногда можно представить либо как статическую игру с совершенной информацией, либо как динамическую игру с несовершен ной информацией. Так что данное разбиение по типам игр не является жест ким и однозначным. Поясним сказанное на примере. Пример 1.1. Игра в «четнечет». Саша и Маша одновременно загадывают числа: Саша выбирает x ∈{ ; } 1 2 , Маша — y ∈{ ; } 1 2 . Если сумма s x y = + чет ная, то выигрыши равны ( ; ) 1 1 − , т.е. выигрыш Саши равен 1, Маши — −1. Если сумма нечетная, то выигрыши равны ( ; ) − 1 1 . 12 Очевидно, игра статическая (игроки делают выбор одновременно), с пол ной совершенной информацией (игра одноходовая, в ней не существует предыстории). Но можно игру представить и в несколько ином в виде. Саша ходит пер вым. Он выбирает число x ∈{ ; } 1 2 и записывает его в конверт. На следу ющем шаге Маша, не зная x, выбирает y ∈{ ; } 1 2 , после чего игра заканчива ется и игроки получают свои выигрыши. Изобразим дерево игры (рис. 1.2). Саша Маша Маша x = 1 у = 1 у = 1 у = 2 у = 2 x = 2 (1; –1) (–1; 1) (–1; 1) (1; –1) Рис. 1.2 На дереве игры появилась пунктирная линия, связывающая два реша ющих узла, которые относятся к Маше. Эта линия означает, что Маша к моменту выбора не знает, в каком из узлов она находится, т.е. у нее нет информации о том, какой выбор сделал Саша на первом ходу. Множество узлов, объединенных такой линией, называется информационным множе- ством. Иначе говоря, Маша не располагает полным знанием всей предысто рии развития игры (она не знает хода Саши на предыдущем шаге). Значит, эту игру можно рассматривать как динамическую игру с несовершенной информацией. 1.3. форìы оïисания игры В теории игр различают две формы описания игры: — развернутую (или экстенсивную); — нормальную. 1.3.1. Развернутая (экстенсивная) форма описания игры Развернутая форма описания игры указывает, какие ходы могут делать игроки, какой информацией они располагают, каковы размеры платежей в конце игры. Игра обычно описывается деревом игры; ветви дерева — ходы, которые могут делать игроки в сложившейся обстановке. Пример 1.2. На рис. 1.3 представлена игра в развернутой форме. Первым в игре ходит игрок 1. Он выбирает один из ходов A, B или C. 13 Далее ходит второй игрок. Он перед своим ходом знает, был ли сделан первым игроком ход C или нет. Если да, то он выбирает ход f или g. В про тивном случае (если игрок 1 выбрал не C) второй игрок, не зная, был ли выбран первым игроком ход A или B, выбирает ход d или e. Игра заканчи вается выигрышами (пары чисел), зависящими от ходов обоих игроков. Так, например, если первый игрок сделал ход B, а второй — ход d, то выигрыш первого игрока равен 1, а второго — 7. A d d f e e g C B (2; 1) (6; 2) (1; 7) (5; –2) (1; 5) (3; 6) 2 2 1 Рис. 1.3 На этом рисунке точки хода второго игрока (после ходов первого A и B) соединены пунктиром. Это значит, что эти точки составляют одно инфор- мационное множество и игрок, осуществляющий выбор хода в этом мно жестве, не знает, какого именно из узлов данного информационного мно жества достигла игра. Также представленный выше рис. 1.1 задает игру в развернутой форме. Как видим, словесное описание игры значительно сложнее для пони мания, чем развернутая форма игры, представленная на рисунке. Поэтому последовательные игры мы будем представлять, как правило, в разверну той форме. 1.3.2. Нормальная форма описания игры Проще всего объяснить, что такое нормальная форма игры, на примере биматричной игры: s s s s s u u u u u u u j n j j n 1 2 2 2 2 2 1 1 11 1 11 2 12 1 12 2 1 1 1 2 1 1 … … … … ( ; ) ( ; ) ( ; ) ( ; uu s u u u u u u u u n j j n n 1 2 2 1 21 1 21 2 22 1 22 2 2 1 2 2 2 1 2 2 ) ( ; ) ( ; ) ( ; ) ( ; ) … … … … … … … … … … … … … … … … … … … … … … … s u u s u u u u i ij ij m m m m m 1 1 2 1 1 1 1 2 2 1 2 2 ( ; ) ( ; ) ( ; ) (uu u u u mj mj mn mn 1 2 1 2 ; ) ( ; ) … Играют два игрока. У первого m различных стратегий (он выбирает строки), у второго — n (он выбирает столбцы). Игроки осуществляют свой выбор одновременно (игра статическая). Рассматриваются все возможные 14 профили стратегий игроков и определяются платежи, соответствующие любой возможной комбинации стратегий игроков. Такую игру проще всего представить в виде двух платежных матриц, показывающих, какую сумму получит каждый из игроков при всех возможных стратегиях. Можно пред ставить эти две матрицы в виде одной матрицы с элементами в виде пары чисел — выигрышей первого и второго игроков. В указанной игре u ij 1 и u ij 2 — элементы платежных матриц первого и вто рого игроков; s i 1 и s j 2 — их стратегии. Такие игры называются биматрич- ными играми. В общем случае имеется N игроков. Игрой внормальной форме ( , , , , , ) N S u i N i i = 1 … назовем совокупность, содержащую для каждого игрока с номером i, 1 ≤ i ≤ N: • множество стратегий S i с элементами s i /S s i i = { } (это может быть как конечное, так и бесконечное множество стратегий); • функцию выигрыша (полезности) u i , являющуюся отображением декартова произведения S S S S S N i i = ⋅ ⋅ ⋅ = ∏ 1 2 … в R. Элемент из множества S назовем профилем стратегий (или исходом игры, или ситуацией). После того как каждый игрок выбрал свою стратегию s S i i ∈ , определены профиль стратегий s s s s N = ( ; ; ; ) 1 2 … и выигрыш каждого игрока u s i ( ). Пример 1.3. В рассмотренной ниже биматричной игре первый игрок выбирает одну из трех стратегий (строк) a, b или c, второй, одновременно с ним, — одну из двух стратегий (столбцов) d или e: d e a b c ( ; ) ( ; ) ( ; ) ( ; ) ( ; ) ( ; ) − − 2 2 1 1 3 0 1 1 2 2 2 3 Всего, таким образом, существует 6 комбинаций, т.е. 6 профилей стратегий (исходов). При всех исходах известны выигрыши игроков. Так, например, при исходе ( ; ) c e выигрыш первого игрока равен 2, второго — 3. В данной игре присутствуют все признаки нормальной формы: N S a b c S d e = = = 2 1 2 ; { ; ; }; { ; }, а множество платежей задается указанной таблицей пар чисел (выигрыши игроков при всех возможных комбинациях стратегий). Рассмотрим пример бесконечной игры, заданной в нормальной форме. Пример 1.4. На рынке имеется N различных фирм, желающих продать некий товар. Каждая из фирм предлагает свою продажную цену p i на этот товар. Игра статическая (цены объявляются фирмами одновременно). Здесь S i = (0; + ∞) 1 . Обозначим p 0 = min j p j . Пусть I i p p i = = { | } 0 — множество индексов тех игроков, которые «угадали» минимальную цену. И пусть k — количество элементов множества I, т. е. количество фирм, предложивших минимальную цену. Будем полагать, что в этом случае спрос на товар d p ( ) 0 распределится между этими фирмами в равных долях. Тогда функция выи грыша для каждой фирмы определится как 1 Для упрощения будем считать деньги бесконечно делимыми. |