теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
, min существуют. 23 Для описания этого понятия введем понятия сравнимости стратегий. Естественно считать, что одна моя стратегия “слабо доминирует” вторую (то есть первая моя стратегия “заведомо не хуже” для меня чем вторая) – когда первая стра- тегия при любых действиях партнеров не хуже второй стратегии и по крайней мере для одного варианта действий партнеров строго лучше (приносит мне больший вы- игрыш). Формально: Определение 2.0.2.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 лучше при любых действиях партнеров). Если две стратегии x i , y i доставляют одинаковые выигрыши при любых дей- ствиях партнеров (то есть u i (x i , x −i ) = u i (y i , x −i ) ∀x −i ), то они эквивалентны для игрока i. Если же из пары стратегий ни одна не слабо-доминирует другую и они не эквивалентны, то они несравнимы. Понятие доминирования позволяет разбить множество стратегий X i на классы: Определение 2.0.2.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 . По сути, доминирующей или независимо-оптимальной называют стратегию, при- носящую выигрыш не менее любой другой независимо от действий партнеров. По- нятно, что это не часто встречается. Но уж если встретилось - это позволяет сделать довольно надежное предсказание о ходе рассматриваемого игрока независимо от ин- формационной структуры! Сопоставьте доминирование с максиминной стратегией игрока на примере. 24 Глава 2. Статические или “одновременные” некооперативные игры Пример доминирования. Пусть множество стратегий Анны есть 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= ∅. 2.0.3 Доминирующее и сильно-доминирующее равновесия Понятия доминирования, примененные ко всем игрокам сразу, позволяют сформу- лировать четыре типа решений, по два для сильной и для слабой концепции. Определение 2.0.3.1 Множество равновесий в (слабо) доминирующих стратеги- ях есть множество профилей (наборов) слабо-доминирующих стратегий игроков: W IDE ≡ 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 ). Пример 2.0.2 ( “Симбиоз, или бесконфликтная ситуация”) Крупный гры- зун “медоед” типа россомахи, живущий в Африке, питается преимущественно медом диких пчел, а птичка “медовед” питается преимущественно воском от разоренных им диких “ульев”. При этом птичка разведывает дупла - ульи, и ведет туда медоеда, криком призывая его за собой. Каждый из них может выбрать, объединиться ли с партнером. Решение этой игры (и всех подобных “симбиозов” в быту или экономике) очевидно и легко объяснимо по доминированию: Сопоставим четыре концепции связанные с доминированием. Очевидно, всегда N D W i ⊂ N D Si , поэтому W N D ⊂ SN D. Кроме того, оче- видно, когда SIDE 6= ∅, то W IDE = SIDE. При этом W IDE имеет больше шан- сов существовать: если есть слабо-доминирующие стратегии, это еще не значит, что есть сильно-доминирующие. Недоминируемые же решения существуют всегда (при 25 alone together alone together (0, 0) (0, 0) (0, 0) (1, 1) ← W DE (2.2) Таблица 2.3: Пример игры координации “симбиоз” (no-conflict). компактности множеств стратегий и достижимых выигрышей), но часто оставляют слишком большую неопределенность решения. Сопоставляя слабо-доминирующие и слабо-недоминируемые стратегии некоторого игрока i, легко доказать (см. Мулен, 1985): Утверждение 2.0.3.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= ∅. Выбор между введенными концепциями доминирования — сильной и слабой — неочевиден, с точки зрения правдоподобия их применимости. Иногда гипотеза пове- дения со слабым доминированием оправдана смыслом игры: почему бы не подстра- ховать себя. А иногда – нет, как видно из игры на Таб. 2.4: Victor b b 0 An- a $ 100, $ 100 $ 0, $ 100 na a 0 $ 100, $ 0 $ 3, $ 2 (WDE) Таблица 2.4: Пример “weak prisoner’s dilemma” с большими проигрышами. Приме- нимость слабого доминирования – неочевидна. Если популяция игроков находится в хорошей точке (a, b) =>(100,100), то возможно, реальные игроки не станут отступать от нее на доминирующие стратегии (a’, b’), то есть поведут себя по какой-то другой модели рационального поведения, чем идея DE. Здесь по слабому доминированию игра приходит к мало выгодному решению b, y. Оно вполне возможно в однократной игре без всякой информации, а другое, более выгодное, решение a, x кажется менее разумным прогнозом их поведения. Однако, ес- ли a, x – состояние не в однократной игре, а в некоторой популяции, то игроки могут не захотеть переходить от “равновесия” на (a, x) на индивидуально- нестрого-более выгодные позиции b и y, основательно опасаясь сползания популяции к выигрышам (3, 2) при (b, y) (в сущности, здесь мы неявно подразумеваем не совсем корректное использование этой статической модели для описания динамической ситуации). Тем более подобные динамические соображения могут удержать от слабого доминиро- вания, если это модель повторяющейся игры двух лиц. Даже и при однократном розыгрыше втемную, исход (a, x) не кажется слишком глупым: достаточно ли ве- лика разница между 0 и 2, чтобы мотивировать отбрасывание слабо доминируемой стратегии x? Не повлияет ли на выбор Виктора его “порог чувствительности” или (не учтенное пока в таблице выигрышей) нежелание причинить вред своему партне- ру? Впрочем, это бы означало, что игра неточно формализована в данной таблице: в ней учтены лишь денежные выигрыши, а должны быть учтены “полезности”. Так или 26 Глава 2. Статические или “одновременные” некооперативные игры иначе, прежде чем применять ту или иную концепцию решения, желательно сопоста- вить ее с нашими представлениями о поведении и предпочтениях партнеров, возмож- но недоучтенных в целевых функциях. Скажем, если из равно-выгодных вариантов для себя участник выбирает благоприятное для партнера, это можно отразить как лексико-графической целевой функцией, так и концепцией решения. Та же проблема и в популярном в учебниках примере координации “Дилемма заключенных”, где доминирующее решение существует (SDE = W IDE 6= ∅), и ярко показывает возможный вред некооперативного поведения. Пример 2.0.3 “Дилемма заключенных” (R.Luce, H.Raiffa,1957). Двух человек арестовали по подозрению в совершении двух разных преступлений, при- чем у каждого есть улики на партнера. Известно, что если один “стучит” на другого, а другой нет, то информатор получает 1 год наказания, а “молчун” – 10 лет. Если информи- руют оба, то каждый получит по 7 лет. Заключенным известно, что если никто из них не информирует, то оба получат по 3 года. Игру можно представить с помощью следующей матрицы (Табл.2.5), в клетках которой слева внизу стоит выигрыш первого заключенного, а справа вверху – второго. Таким обра- зом, две матрицы выигрышей совмещены в одной диаграмме, каждая клетка отражает один из исходов. Это типичный способ представления игр с конечным множеством стратегий — “матричных” (“биматричных”, по другой терминологии, не поддерживаемой нами). Victor Victor USA USA стучать молчать вооруж. разоруж. Аnna -7 -10 USSR -1 -2 стуч. -7 DE 0 вооруж-ся -1 SDE 2 Аnna 0 0 USSR 2 1 молч. -10 0 разоруж-ся -2 1 Таблица 2.5: Слабая и строгая ситуации типа “дилеммы заключенных”. Поступая враждебно к партнеру локально не проигрываешь или даже выигрываешь. Здесь у каждого игрока имеется стратегия слабо доминирующая среди возможных стра- тегий – стучать. Ведь соответствующий вектор возможных выигрышей (-7,0) доминирует над вектором (-10,0), то есть (−7, 0) > (−10, 0) поэтому DE ={(стучать, стучать) }. В аналогичной игре двух сверхдержав ущерб от некооператив- ного поведения даже сильнее: существует SDE ={(вооружаться, вооружаться) }, потому что при фиксированной позиции партнера ты всегда строго увеличиваешь свою безопас- ность вооружаясь. 5 Забегая вперед, заметим, что все рассмотренные ниже виды некооперативных решений (равновесий) в этой игре совпадают (ниже формулируются их опре- деления и соответствующее общее утверждение о совпадении разных решений 5 Несколько подобное, но не строго доминируемое “глупое” NE в примере "дырявая лодка” типа prisoners dilemma. Пусть лодка, где плывут Анна и Боб получила течь, и откачать воду можно только вдвоем, усилий одного недостаточно. Анна и Боб в ссоре и не разговаривают друг с другом. Одно из равновесий NE – когда оба черпают. Но есть и другое NE – когда оба не черпают, ведь нет смысла черпать, если не черпает другой. 27 в случае SIDE = W IDE 6= ∅). Действительно, худшее, что может получить заключенный, если стучит это 7 лет, если же не стучит, то 10 лет. Поэтому “осторожным” поведением для них будет сознаться. С другой стороны, каж- дому из них не выгодно изменять этот выбор при текущем выборе партнера, поскольку при этом он ухудшил бы свое положение. Поэтому это будет и рав- новесием по Нэшу. Далее, если первому из заключенных предложили сделать свой выбор первым (он находится в положении лидера), то он, зная, что ре- акцией второго на любой его выбор будет информировать, выберет наилучшее для себя – стучит. То есть равновесие Штакельберга будет там же. Сложное равновесие тоже совпадает с равновесием в доминирующих стратегиях. Любой некооперативный исход выглядит парадоксально- неудачным: ведь если бы оба не выбирали лучшее для себя по отдельности, и не стучали, то оба получили бы меньшее наказание, достигнув Парето-оптимума (u 1 = −3, u 2 = −3). Такая неоптимальность довольно типична для некооперативных решений в раз- ных играх. Если же участники способны скооперироваться и верят в выполнение соглашения партнером, то достигают ядра (−3, −3), и одновременно Парето- оптимума. Структуру игры аналогичную дилемме заключенных мы видим во многих иг- рах, в частности, при рассмотрении гонки вооружений двух сверхдержав (СССР и США): при невысокой вооруженности обоих их безопасность выше, чем при высокой вооруженности обоих. Но при любой фиксированной вооруженности партнера безопаснее поднимать свою. Поэтому, при отсутствии сдерживающих договоров (кооперативного поведения) страны скатываются к не-Парето опти- мальному, то есть невыгодному обоим состоянию: чрезмерной вооруженности. Такая же структура игры у дуополии (где непрерывные стратегии, а не дискрет- ные как выше). Например, в дуополии Бертрана каждому конкуренту выгодно отклониться от монопольно- высокой цены, но после таких шагов обоих, оба продавца прогадают (и выгадают покупатели). Еще пример игры с непрерывными стратегиями, где есть доминирующее равно- весие – это аукцион Викри или аукцион второй цены (см. задачник). Во многих ситуациях, в отличие от специальных случаев (повторяющиеся игры, очень большие проигрыши, альтруизм к партнеру и др.), концепция доминирующих равновесий DE, весьма убедительна, а SDE - тем более. То есть, когда доминирую- щее равновесие существует, то оно кажется вполне естественным (особенно – строго доминирующее) исходом некооперативной игры, причем не требующим от игрока ни- каких знаний о партнерах. Однако существование проблематично, игры чаще всего не имеют равновесия в доминирующих стратегиях. В этом случае возникает пробле- ма выбора другой концепции равновесия (решения), которая бы наилучшим образом подходила к моделируемой ситуации. Как и во всяком моделировании, этот выбор подчинен интуиции исследователя, в нем трудно дать точные общие рекомендации. Мы рассмотрим здесь некоторый арсенал концепций, различающихся, в сущности, ожиданиями игроков: INDS, INDW, NE, MM, StE, а позже коснемся попыток уни- версализации концепции решения. 28 Глава 2. Статические или “одновременные” некооперативные игры 2.0.4 Итерационно-недоминируемые решения IN D W , IND S Рассмотрим концепции решений, в которых подразумевается, что игроки информи- рованы о целях друг друга, причем, это является “общим знанием”: все знают, что все всё знают о целях (рекурсия “я знаю, что ты знаешь” любой глубины). Также подразумевается, что игроки неограниченно дальновидны и расчетливы, и это то- же является общим знанием. По сути, в “итерационно недоминируемом” равновесии считается, что игроки, зная цели друг друга, последовательно отбрасывают свои до- минируемые стратегии и ожидают того же от других, взаимно просчитывая ходы (я отбросил свои доминируемые стратегии, знаю, как партнер отбросил свои, и он знает о моих отброшенных, следовательно... ). Итерации этих расчетов взаимного предска- зывания могут привести к решению, называемому “итерационно-недоминирующим решением”. Оно возможно и в сильном и в слабом варианте. Определение 2.0.4.1 Определим вложенную последовательность игр G 1 ⊆ G 2 ⊆ ..., G t , ..., задавая каждый раз множество всех стратегий новой игры как прошлое множество (слабо) недоминируемых стратегий: X t+1 := N D t W (t = 1, 2, ...) (предпо- лагается что все игроки отбрасывают доминируемые стратегии одновременно). 6 Множество IND W итерационно недоминируемых (слабо) исходов игры G 1 |