Лекции по теории игр и политологии
 Скачать 1.03 Mb.
|
|
x j ) j∈I\{i} профиль (набор) стратегий всех игроков кроме i, и аналогично индексировать множества и функции. Сначала рассмотрим случай, когда игроки не обладают информацией ни о целях, ни о намеченных стратегиях партнеров. Если они к тому же ведут себя “очень осто- рожно”, то подходит следующая концепция решения. Определение 1.1.1 Множество X M M i осторожных или максиминных стратегий игрока i задается как аргументы, максимизирующие гарантированный выигрыш: 4 X M M i := {x i ∈ X i | ∀x −i ⇒ u i (x i , x −i ) ≥ sup y i ∈X i ( inf z −i ∈X −i u i (y i , z −i ) ) }, (1) при этом MM := Q i∈I X M M i – множество максиминных решений игры. Поясним: в осторожном решении игроки ожидают от партнеров самого худше- го для себя, то есть ожидания игрока есть β i = (inf z −i ∈X −i u i (y i , z −i ) ) (равновесием это решение называть не совсем точно, поскольку ожидание всего худшего может не оправдываться). Каждый максимизирует выигрыш при этих мрачных ожиданиях, то 4 Как обычно, sup = max, inf = min, если max, min существуют. 7 есть в целом – максимизирует гарантированный выигрыш. Такое поведение кажется правдоподобным при неизвестности целей партнеров, при крайней осторожности, и однократном розыгрыше (см. пример “Перекресток” - Табл. 2); либо в ситуации ан- тагонистической игры, то есть игры с противоположными интересами (определяемой ниже). Victor Go V Stop V An- Go A -1000, -1000 1, -1 (NE) na Stop A -1, 1 (NE) 0, 0 (MM) Victor Go V Stop V A Go A 0, 0 1, -1 Stop A -1, 1 0, 0 Таблица 2: Игра координации “Нерегулируемый перекресток”. Нет правил, и каждый может продолжать быстро ехать или затормозить. Худший исход – столкновение – игроки оценивают для себя в -1000$, а возможность опередить соперника – в 1$. Осто- рожное решение – MM: (Stop A , Stop V ). Рядом, для сравнения - “антагонистический” вариант этой игры при невозможности разбить машины: нулевая сумма выигрышей всюду. В антагонистической игре (т.е. игре “с нулевой суммой” или, что эквивалентно, с постоянной суммой выигрышей) концепция максимина очень естественна. Но, как видно из приведенного примера, не все максиминные решения вызывают доверие как возможный результат повторяющейся игры. Это обсуждается далее и в понятии “сед- ла”. Во многих случаях применимость концепции максимина вызывает и другие со- мнения: если игроки осторожны, то почему не внести степень их неприятия риска в явном виде в значения выигрышей, приписывая одновременно некоторые вероятно- сти ожидаемым ходам партнеров? К тому же, такая же игра типа “Перекресток”, но разыгрываемая многократно, вряд ли будет приводить к такому как мы рассмотре- ли взаимно-осторожному решению, означающему несогласованные ожидания. Скорее всего, ожидания тем или иным путем скорректируются и согласуются (см. “повторя- ющиеся игры”). Впрочем, бывают случаи, когда ожидания не играют роли; это ситуации, где имеет место “доминирование”. Для описания их введем понятия сравнимости стратегий. Естественно считать, что одна моя стратегия “слабо доминирует” вторую (то есть первая моя стратегия “заведомо не хуже” для меня чем вторая) – когда первая страте- гия при любых действиях партнеров не хуже второй стратегии и по крайней мере для одного варианта действий партнеров строго лучше (приносит мне больший выигрыш). Формально: Определение 1.1.2 Стратегия x i ∈ X i игрока i (слабо) доминирует стратегию y i ∈ X i , если ∀x −i ∈ X −i ⇒ u i (x i , x −i ) ≥ u i (y i , x −i ), ∃x −i ∈ X −i : u i (x i , x −i ) > u i (y i , x −i ), где −i := I \ {i}, X −i := (X j ) j6=i . Если же оба приведенные неравенства строгие, то x i сильно доминирует над y i (то есть x i лучше при любых действиях партнеров). 8 Если две стратегии x i , y i доставляют одинаковые выигрыши при любых действиях партнеров (то есть u i (x i , x −i ) = u i (y i , x −i ) ∀x −i ), то они эквивалентны для игрока i. Ес- ли же из пары стратегий ни одна не слабо-доминирует другую и они не эквивалентны, то они несравнимы. Понятие доминирования позволяет разбить множество стратегий X i на классы: Определение 1.1.3 Стратегия x i ∈ X i игрока i называется (слабо) доминирующей стратегией (среди его стратегий) или (слабо) заведомо-оптимальной — если она до- минирует любую другую его стратегию либо эквивалентна ей: ∀y i ∈ X i , ∀x −i ∈ X −i ⇒ u i (x i , x −i ) ≥ u i (y i , x −i ), и сильно доминирующей если все такие неравенства строгие. Множество всех (слабо) доминирующих стратегий игрока i далее обозначается ID W i , а сильно доминирующих стратегий – ID Si (оно, по определению, состоит не более чем из одной стратегии). Мно- жество всех недоминируемых слабо (ни одной другой стратегией) стратегий игрока i обозначается далее N D W i , множество всех недоминируемых сильно – N D Si . Очевид- но, сильное и слабое доминирование отличаются широтой образуемых ими классов стратегий: ID Si = ID W i , если оба непусты, но N D W i ⊆ N D Si . По сути, доминирующей или независимо-оптимальной называют стратегию, при- носящую выигрыш не менее любой другой независимо от действий партнеров. По- нятно, что это не часто встречается. Но уж если встретилось - это позволяет сделать довольно надежное предсказание о ходе рассматриваемого игрока независимо от ин- формационной структуры! Сопоставьте доминирование с максиминной стратегией игрока на примере. Пример доминирования. Пусть множество стратегий Анны есть X A = (a, b, c, d, e), и выигрыши ее заданы таблицей (выигрыши Виктора не приведены): Ann\ V ictor x y z − − −− − − −− − − −− − − −− a | 2, ∗ | 3, ∗ | 5, ∗ b | 3, ∗ | 3, ∗ | 4, ∗ c | 2, ∗ | 4, ∗ | 5, ∗ d | 3, ∗ | 3, ∗ | 3, ∗ e | 1, ∗ | 3, ∗ | 4, ∗ В этом примере {b, d} = X M M,A ⊂ N D S,A = {a, b, c} ⊃ N D W,A = {b, c}. Сопоставляя далее доминирование с максимином, проверьте Утверждение. Осторожная стратегия игрока не может быть сильно- доми- нируемой, и среди осторожных есть слабо- недоминируемые: X M M i ⊂ N D Si [X M M i 6= ∅, N D W i 6= ∅] ⇒ X M M i ∩ N D W i 6= ∅. 9 1.2 Доминирующее равновесие Понятия доминирования, примененные ко всем игрокам сразу, позволяют сформули- ровать четыре типа решений, по два для сильной и для слабой концепции. Определение 1.2.1 Множество равновесий в (слабо) доминирующих стратегиях есть множество профилей (наборов) слабо-доминирующих стратегий игроков: W IDE := Q i∈I ID W i = (ID W 1 × ID W 2 × ... × ID W m ). Аналогично, множество равновесий в сильно-доминирующих стратегиях есть: SIDE := Q i∈I ID Si = (ID S1 × ID S2 × ... × ID Sm ). Множество профилей (наборов) слабо-недоминируемых стратегий игроков обозна- чим: W N D := Q i∈I N D W i = (N D W 1 × N D W 2 × ... × N D W m ). Аналогично, множество профилей сильно-недоминируемых стратегий обозначим: SN D := Q i∈I N D Si = (N D S1 × N D S2 × ... × N D Sm ). Пример 1.2 ( “Симбиоз, или однозначная координация”) Крупный грызун “медоед” типа россомахи, живущий в Африке, питается преимущественно медом ди- ких пчел, а птичка “медовед” питается преимущественно воском от разоренных им диких “ульев”. При этом птичка разведывает дупла - ульи, и ведет туда медоеда, криком призывая его за собой. Каждый из них может выбрать, объединиться ли с партнером. Решение этой игры (и всех подобных “симбиозов” в быту или экономике) очевидно и легко объяснимо по доминированию: alone together alone together (0, 0) (0, 0) (0, 0) (1, 1) ← W DE (2) Таблица 3: Пример игры координации “симбиоз”. Сопоставим четыре концепции связанные с доминированием. Очевидно, всегда N D W i ⊂ N D Si , поэтому W N D ⊂ SN D. Кроме того, очевид- но, когда SIDE 6= ∅, то W IDE = SIDE. При этом W IDE имеет больше шансов су- ществовать: если есть слабо-доминирующие стратегии, это еще не значит, что есть сильно-доминирующие. Недоминируемые же решения существуют всегда (при ком- пактности множеств стратегий и достижимых выигрышей), но часто оставляют слиш- ком большую неопределенность решения. Сопоставляя слабо-доминирующие и слабо- недоминируемые стратегии некоторого игрока i, легко доказать (см. Мулен, 1985): Утверждение 1.2.1 Попарно эквивалентны три утверждения: 1) ID W i 6= ∅ ⇔ 2) N D W i = ID W i ⇔ 3) все стратегии в N D W i эквивалентны. Отсюда, W N D = W ID когда W ID 6= ∅. Выбор между введенными концепциями доминирования — сильной и слабой — неочевиден, с точки зрения правдоподобия их применимости. Иногда гипотеза пове- дения со слабым доминированием оправдана смыслом игры. А иногда – нет, как видно из игры на Таб. 4: 10 Victor x y An- a $ 101, $ 100 $ 1, $ 100 na b $ 101, $ 0 $ 3, $ 2 (WDE) Таблица 4: Применимость слабого доминирования - неочевидна. Здесь по слабому доминированию игра приходит к мало выгодному решению b, y. Оно вполне возможно в однократной игре без всякой информации, а другое, более вы- годное, решение a, x кажется менее разумным прогнозом их поведения. Однако, если a, x – состояние не в однократной игре, а в некоторой популяции, то игроки могут не захотеть переходить от “равновесия” на (a, x) на индивидуально- нестрого-более вы- годные позиции b и y, основательно опасаясь сползания популяции к выигрышам (3, 2) при (b, y) (в сущности, здесь мы неявно подразумеваем не совсем корректное исполь- зование этой статической модели для описания динамической ситуации). Тем более подобные динамические соображения могут удержать от слабого доминирования, ес- ли это модель повторяющейся игры двух лиц. Даже и при однократном розыгрыше втемную, исход (a, x) не кажется слишком глупым: достаточно ли велика разница между 0 и 2, чтобы мотивировать отбрасывание слабо доминируемой стратегии x? Не повлияет ли на выбор Виктора его “порог чувствительности” или (не учтенное пока в таблице выигрышей) нежелание причинить вред своему партнеру? Впрочем, это бы означало, что игра неточно формализована в данной таблице: в ней учтены лишь де- нежные выигрыши, а должны быть учтены “полезности”. Так или иначе, прежде чем применять ту или иную концепцию решения, желательно сопоставить ее с нашими представлениями о поведении и психологии партнеров. Та же проблема и в популярном примере координации “Дилемма заключенных”, где оба доминирующих решения существуют (SDE = W IDE 6= ∅), и ярко показывают возможный вред некооперативного поведения. Пример 1.3 “Дилемма заключенных” (R.Luce, H.Raiffa,1957). Двух человек арестовали по подозрению в совершении двух разных преступлений, при- чем у каждого есть улики на партнера. Известно, что если один “стучит” на другого, а другой нет, то информатор получает 1 год наказания, а “молчун” – 10 лет. Если информируют оба, то каждый получит по 7 лет. Заключенным известно, что если никто из них не информирует, то оба получат по 3 года. Игру можно представить с помощью следующей матрицы (Табл.5), в клетках которой слева внизу стоит выигрыш первого заключенного, а справа вверху – второго. Victor стучать молчать стучать молчать -7 -10 Аn- стучать -7 SDE -1 na -1 -3 молчать -10 -3 Таблица 5: “Дилемма заключенных”. 11 Здесь у каждого игрока имеется стратегия сильно доминирующая среди возможных стра- тегий – стучать. Ведь соответствующий вектор возможных выигрышей (-7,-1) строго доми- нирует над вектором (-10,-3), то есть (−7, −1) À (−10, −3) поэтому SDE ={(стучать, стучать) }. Забегая вперед, заметим, что все рассмотренные ниже виды некооперативных решений (равновесий) в этой игре совпадают (ниже формулируются их опреде- ления и соответствующее общее утверждение о совпадении разных решений в случае SIDE = W IDE 6= ∅). Действительно, худшее, что может получить заклю- ченный, если стучит это 7 лет, если же не стучит, то 10 лет. Поэтому “осторож- ным” поведением для них будет сознаться. С другой стороны, каждому из них не выгодно изменять этот выбор при текущем выборе партнера, поскольку при этом он ухудшил бы свое положение. Поэтому это будет и равновесием по Нэшу. Далее, если первому из заключенных предложили сделать свой выбор первым (он находится в положении лидера), то он, зная, что реакцией второго на любой его выбор будет информировать, выберет наилучшее для себя – стучит. То есть равновесие Штакельберга будет там же. Сложное равновесие тоже совпадает с равновесием в доминирующих стратегиях. Любой некооперативный исход выгля- дит парадоксально- неудачным: ведь если бы оба не выбирали лучшее для себя по отдельности, и не стучали, то оба получили бы меньшее наказание, достигнув Парето-оптимума (u 1 = −3, u 2 = −3). Такая неоптимальность довольно типична для некооперативных решений в раз- ных играх. Если же участники способны скооперироваться и верят в выполне- ние соглашения партнером, то достигают ядра (−3, −3), и одновременно Парето- оптимума. Структуру игры аналогичную дилемме заключенных мы видим во многих иг- рах, в частности, при рассмотрении гонки вооружений двух сверхдержав (СССР и США): при невысокой вооруженности обоих их безопасность выше, чем при высокой вооруженности обоих. Но при любой фиксированной вооруженности партнера безопаснее поднимать свою. Поэтому, при отсутствии сдерживающих договоров (кооперативного поведения) страны скатываются к не-Парето опти- мальному, то есть невыгодному обоим состоянию: чрезмерной вооруженности. Такая же структура игры у дуополии. Например, в дуополии Бертрана каждому конкуренту выгодно отклониться от монопольно- высокой цены, но после таких шагов обоих, оба продавца прогадают (и выгадают покупатели). Пример игры с непрерывными стратегиями, где есть доминирующее равновесие – аукцион Викри (аукцион второй цены – см. задачник). Во многих ситуациях, в отличие от оговоренных выше случаев (повторяющиеся ситуации и др.), концепция доминирующих равновесий WDE, весьма убедительна, а SDE - тем более. Но к сожалению, оба редко существуют, из-за частого отсутствия доминирующих стратегий. Итак, когда доминирующее равновесие существует, то оно кажется вполне есте- ственным (особенно – строго доминирующее) исходом некооперативной игры, причем не требующим от игрока никаких знаний о партнерах. Однако, игры чаще всего не имеют равновесия в доминирующих стратегиях. В этом случае возникает проблема выбора концепции равновесия (решения), которая бы наилучшим образом подходила к моделируемой ситуации. Как и во всяком моделировании, этот выбор подчинен инту- иции исследователя, в нем трудно дать точные общие рекомендации. Мы рассмотрим 12 |