теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
есть стационарное множество этой последовательности: IND W := N D ˆ t W = N D ˆ t−1 W (∃ˆt ≥ 1). Аналогично определена концепция итерационно сильно-недоминируемых исходов IN D S := N D ˆ t S = N D ˆ t−1 S (∃ˆt ≥ 1), отличаясь только сильным типом доминирова- ния. 7 Неформально, решение в итерационно- (слабо-)недоминируемых стратегиях (INDW) - это исход игры в случае одновременного итерационного отбрасывания (слабо-) до- минируемых стратегий каждым игроком и соответствующего редуцирования игры: исключения отброшенных стратегий из рассмотрения ВСЕМИ игроками. Требует знания или целей партнеров или факта отбрасывания стратегий. Аналогично INDS, только доминирование - сильное. Сложное равновесие SoE - это INDW, при экви- валентности, по доминированию, финальных стратегий. В терминах ожиданий, эту концепцию решения можно сформулировать так: я, зная цели партнеров, и зная, что они знают мои цели, ожидаю от партнеров неограниченно-глубокой (по глубине ин- дукции) рациональности, то есть расчета наших взаимных шагов по отбрасыванию “плохих” стратегий. Это хорошая концепция решения для гроссмейстеров, играющих в шахматы, но не для новичков. Заметим, что остаться в итоге могут только взаимно несравнимые или эквива- лентные стратегии. Эквивалентность моих стратегий в финальной игре не означает, что выигрыши не зависят от деятельности партнера, и сложные равновесия (как и доминирующие) могут включать исходы с различными выигрышами всех игроков: 6 Рассматривают также равновесия с неодновременным отбрасыванием худших стратегий, а с заданной последовательностью отбрасываний (Мулен, 1985, стр.40). Они подобны вводимым ниже равновесиям игр в развернутой форме и равновесиям Штакельберга. 7 Множество сложных равновесий SoE W или SoE (sophisticated equilibrium) есть такое IN DW , где каждый игрок имеет только эквивалентные стратегии в финальной игре G ˆ t , иначе считают, что SoE W = ∅ (Это не значит, что все исходы приносят одинаковые выигрыши, см. Табл. 2.6). Если SoE W 6= ∅, тогда говорят, что игра “разрешима по (слабому) доминированию”. Аналогично определяется разрешимость по сильному доминированию’, влекущая слабую. 29 − − x − − − − − − −y − − a | 2, 2 (SDE) | 0, 2 (SDE) b | 2, 0 (SDE) | 0, 0 (SDE) Таблица 2.6: (Пограничная ситуация между “no-conflict” и “prisoner’s dilemma”) Мно- жество неэквивалентных доминирующих решений, SDE=INDS= вся игра. В игре на Табл. 2.6 у обоих участников все стратегии эквивалентны, поэтому вся игра есть SDE = INDS = {(a, x), (b, x), (a, y), (b, y)}. Но выигрыши различны! Применение концепций сильного и слабого итерационного доминирования – рас- смотрите на примере “Экзамен” (Табл. 2.9). Заметим, что решение INDW может зависеть от порядка слабого доминирования (см. пример (Табл. 4.1)), в отличие от сильного, где порядок ходов безразличен (до- кажите). Какую из концепций – сильную или слабую – предпочесть, и какой порядок отбрасывания является реалистичным – тонкий вопрос. Ответ определяется допол- нительной информацией об игре (далее мы касаемся этого в динамических играх). 2.0.5 Игры в популяциях и равновесие Нэша Заметим, что разрешение игры по итеративному доминированию не обязательно от- ражает знание целей и соображений партнеров, а может быть применимо и к другим ситуациям. Эти “популяционные”, “эволюционные” ситуации играют в дальнейшем изложении большую роль. (ср. книгу Васин “Эволюционные игры”.) Подразумевается, что конкретная однократная игра между партнером типа А и партнером типа В – есть одна из типичных игр в достаточно большой популяции подобных игр. Тогда свои ожидания о поведении партнера (и, возможно, косвен- но о его целях) каждый игрок строит по прошлому опыту подобных игр. Скажем, конкретный пассажир, раздумывая, торговаться ли с таксистом или это бесполезно, учитывает свой опыт в этом деле с другими таксистами. В таких ситуациях устой- чивое в каком-то смысле решение игры естественно называть “равновесием” этой популяции. Интерпретация итеративного доминирования в такой трактовке иная, чем ра- нее: однажды некоторые игроки отбросили (перестали использовать) доминируемые стратегии – и игра уменьшилась (принимаемое во внимание множество возможных стратегий стало у 0 же). Их партнеры это наблюдали, и в следующих розыгрышах кто- то отбросил еще какие-то стратегии, это все наблюдали, игра опять уменьшилась и т.д. Очевидно, когда итеративно строго-недоминируемое решение единственно, то оно выглядит совершенно естественным “равновесием” такой популяционной игры, и не требует знания целей партнеров. Не-единственность же равновесия и/или толь- ко слабое доминирование могут вызывать вопросы к понятию решения. Какое из нескольких равновесий более правдоподобно? Какая концепция – сильная или сла- бая – лучше прогнозирует исход? Прежде чем сопоставить на примерах сильное и слабое доминирование, введем еще одну, конкурирующую с ними (особенно в попу- ляционных ситуациях), концепцию равновесий. Наиболее часто к ситуациям без знаний целей партнеров применяют концепцию равновесия Нэша — это “рациональное решение при таких ожиданиях ходов парт- 30 Глава 2. Статические или “одновременные” некооперативные игры неров, где все ожидания оправдались”. Выражая это формально, обозначим β j i ∈ X j ожидание (belief) игрока i о выбран- ной стратегии игрока j. Профиль (набор) стратегий и ожиданий (¯ x, ¯ β) = (¯ x i , ( ¯ β 1 i , ..., ¯ β n i )) i∈N ∈ X × (X × ... × X) можно назвать Нэшевским равновесием в терминах ожиданий, если: 1) решение ¯ x i ∈ X i каждого игрока является наилучшим для него ответом на ожи- даемые ходы ¯ β −i i ∈ X −i прочих игроков, в смысле: u i (¯ x i , ¯ β −i i ) = max x i ∈X i u i (x i , ¯ β −i i ); 2) все ожидания совпадают с истинными выбранными стратегиями: ¯ x i = ¯ β i j (∀i, j). Скажем, в примере “Семейный спор” (Футбол или кино) на Рис. 2.0.1 два таких равновесия ((футбол,футбол),(кино,кино)), причем одно из них выгоднее для Ан- ны, другое – для Виктора. Аналогично и в игре “Перекресток” два неравноценных равновесия Нэша. В некоторых играх равновесие Нэша может выражать идею наблюдаемости те- кущих ходов партнеров. Скажем, в игре “Перекресток”, если Анна видит, что Виктор не тормозит, а Виктор видит, что Анна тормозит, то этот исход и реализуется; никто не отступит от текущей стратегии. Впрочем, подобные динамические рассуждения (в том числе об игре “Перекресток”) не совсем корректны, возникают мотивы угроз. Точнее было бы обсуждать подробно последовательность моментов сохранения стра- тегии, то есть повторяющуюся динамическую игру (см. далее). Более адекватно кон- цепция Нэша применима к повторяющейся игре среди популяции игроков, а не пары игроков. Тогда мои ожидания некоторого поведения от моего сегодняшнего партне- ра могут быть основаны на прошлом опыте взаимодействия с другими подобными партнерами, но мотивы угроз не возникают, и не искажают решения. По сути, Нэшевское равновесие родственно равновесиям в доминирующих стра- тегиях в том смысле, что IDE, INDS, INDW “глобально стационарны” среди всех стратегий, а Нэшевское равновесие — по крайней мере “локально стационарно”. Сов- падение ожиданий с истинным выбором позволяет упростить его определение, не формулируя ожиданий явно, ограничиваясь стратегиями: Определение 2.0.5.1 Равновесие по Нэшу есть профиль стратегий, от которого никому нет выгоды отклоняться, если партнеры не отклоняются. Соответствен- но, множество нэшевских равновесий есть: NE := {¯ x ∈ X| y i ∈ X i ⇒ u i (¯ x i , ¯ x −i ) ≥ u i (y i , ¯ x −i ) ∀i ∈ I}, (2.3) если же все неравенства строгие, то говорят о строгих равновесиях по Нэшу (SNE). 8 Иными словами, Нэшевское равновесие – точка из которой ни одному игроку нет пользы уходить (он либо ничего от этого не приобретает, либо теряет) при текущих ходах партнеров, а строгое Нэшевское равновесие – точка, из которой вредно ухо- дить. 9 Иначе эту идею можно выразить через понятие “рационального отклика” или лучшего ответа на действия партнеров (“best response”). 8 Не путать с понятием сильного равновесия Нэша, подразумевающим коалиционную устойчи- вость. 9 Иногда еще вводят понятие сильных или коалиционных равновесий Нэша - когда ни одна коа- лиция не может улучшить своего положения. Такие равновесия редки. 31 Отображение (то есть многозначная функция) X ∗ i (.) : X −i 7→ X i рациональ- ного отклика i-го участника на ожидаемые действия x −i его партнеров состоит из аргументов, максимизирующих его целевую функцию: X ∗ i (x −i ) = arg max x i ∈X i u i (x i , x −i ) = {x i ∈ X i | u i (x i , x −i ) ≥ u i (y i , x −i ) ∀y i ∈ X i }. (2.4) В этих терминах, Нэшевское равновесие – это профиль рациональных откликов всех игроков на рациональные отклики партнеров: ¯ x ∈ NE ⇔ ¯ x ∈ Y i X ∗ i (¯ x −i ). Понятие NE может оказаться применимо в разных случаях. Наряду с популяци- онной ситуацией, и в однократной игре может случиться, что ожидания партнеров почему-либо “сфокусированы” на каком-либо профиле стратегий, считающемся веро- ятным. Например, в игре координации “семейный спор”, если оба почему-то ожидают от партнера выбор “кино”, или хотя бы я ожидаю, что партнер ожидает такой выбор от меня (например, известна уступчивость Виктора, или было сделано какое-то наме- кающее сообщение), то это и случится. Этот довольно распространенный эффект “са- моподдерживающихся ожиданий” называют еще “эффектом фокальной точки” (focal point, подробнее обсуждается ниже). В некоторых ситуациях эта фокальная точка возникает в результате предварительных переговоров. Тогда Нэшевское рав- новесие рассматривают как полу-кооперативную концепцию: если оно принадлежит ядру (определяемому ниже), то это “такое соглашение, от которого никто не склонен отступать”, по крайней мере, если ожидает не отступления партнеров. Напротив, в “Дилемме заключенных” хороший для обоих участников исход (мол- чать,молчать) таким естественно-устойчивым соглашением быть не может, а требует каких-то мер принуждения к выполнению такого соглашения. В этом смысле при- надлежность некоторого соглашения к NE – важное преимущество. 10 Оказывается, Нэшевское решение, может быть естественным исходом и в про- тивоположной – “совсем некооперабельной” ситуации, то есть в антагонистических играх. Определение 2.0.5.2 Антагонистической называют игру с одинаковой (напри- мер, нулевой) суммой выигрышей при любом исходе, т.е. такую, что P i∈I u i (x) = s ∃s ∈ IR, ∀x ∈ X. 11 В таких играх тоже применяют NE, точнее, его сужение, называемое “седлом” или седловой точкой. Определение 2.0.5.3 Множество седловых точек есть Sad := MM ∩ NE Это те Нэшевские равновесия, где худшие предположения о партнерах сбываются. 10 В качестве упражнения на эту тему, рассмотрите всевозможные варианты подобных игр 2х2 с точки зрения совместимости кооперативного и не-кооперативного поведения. 11 Синонимы – игра “с противоположными интересами”, “с нулевой суммой”. Как ни покажется странным, но в этой терминологии войну, в отличие от шахмат, нельзя назвать антагонистической игрой, поскольку обе стороны могут очень пострадать в одних вариантах действий и не очень – при других. 32 Глава 2. Статические или “одновременные” некооперативные игры Например, в играх типа chicken-game, например, “Семейный спор” и “Перекре- сток” седла нет: максимин и Нэшевское решение не пересекаются. Впрочем, суще- ствование и самого NE не всегда гарантировано, см. игру “Монетки” или прятки (Табл. 2.7). Victor: guessing guess Left guess Right An- hold Left -1, 1 1, -1 na hold Right 1, -1 -1, 1 Таблица 2.7: Игра “Монетки” (типа “hide-and-seek”, прятки): Нужно угадать, в какой руке у партнера монетка, тогда ее забираешь, иначе – отдаешь свою (Анна держит, Виктор угадывает). NE = ∅. В повторяющихся играх типа игры “Монетки” под NE может подразумеваться, что каждый игрок наблюдает определенный текущий выбор партнеров на преды- дущем шаге и ведет себя близоруко – не учитывает, что партнеры могут изменить свой выбор когда он изменит свой (неполная рациональность). Пустоту NE = ∅ то- гда надо рассматривать как несуществование стационарных точек такой игры: игра "болтается". Заметим, что применение концепций доминирования (INDW, INDS) в этой игре тоже никак не увеличивает определенность наших предсказаний о ее исхо- дах: вся исходная игра недоминируема. Смешанные стратегии и смешанное равновесие NE m Мы отмечали, что в повторяющихся играх типа игры “Орлянки или Чет-нечет (Мо- нетки)” несуществование решений NE = ∅ можно рассматривать как “раскачивание” игры. При отсутствии стационарного решения типа NE (а иногда и в других случа- ях, в популяциях игр) естественно пользоваться вероятностной концепцией решения (исхода) игры: как игроки будут ходить в среднем? Для этого используется понятие ожидаемой полезности. Лотереи, ожидаемая полезность. Пусть имеется множество Q = {1, 2, ..., q} возможных в мире событий, причем оно задано полным (все возможные события учтены), события взаимоисключающие, и субъективные вероятности событий (мнение рассматриваемого игрока i) есть σ i := (σ i1 , σ i2 , ..., σ iq ) ∈ IR q + , P k≤q σ ik = 1. Пусть полезность набора x ∈ X для рассматриваемого игрока выражена “эле- ментарной” целевой функцией u i (x). Вектор (x 1 , ..., x q ) ∈ (X × ... × X) вместе с ассоциированными вероятностями событий (σ i1 , σ i2 , ..., σ iq ) можно назвать ло- тереей: заданы уровни выигрыша в каждом событии и вероятности. Мы назы- ваем участника максимизирующим ожидаемую полезность (участником типа Неймана-Моргенштерна), если его выбор среди всех возможных лотерей опи- сывается функцией вида U i (¯ x) = P j∈Q σ j u i (x ij ), то есть функцией линейной по вероятности, или, иначе, матожиданием полезности. Именно такими мы и будем считать участников игр далее. Итак, пользуясь идеей "средней полезности”, в повторяющейся игре “Орлянка или Чет-нечет (Монетки)” мы можем искать вероятностное решение: насколько часто 33 каждый игрок в среднем будет делать тот или иной ход. Для этой игры естественная гипотеза - с равной вероятностью оба ходят левой и правой рукой: ((0.5,0.5),(0.5,0.5)). Victor: guessing guess Left =0.5 guess Right =0.5 An- hold Left =0.5 -1, 1 1, -1 na hold Right =0.5 1, -1 -1, 1 Таблица 2.8: Смешанное расширение игры “Монетки”: вероятности ходов есть NE m = ((0.5, 0.5), (0.5, 0.5)). Но как проверить эту догадку и обосновать ответ, если он верен? Идею равнове- сия, о котором мы догадываемся, можно сформулировать так. Нэшевское равновесие в смешанных стратегиях исходной игры - есть Нэшевское равновесие в ее смешанном расширении (то есть профиль веро- ятностей применения чистых стратегий, при котором ни один игрок не может меняя свою вероятностную стратегию улучшить матожидание своего выигрыша, при неиз- менных стратегиях партнеров). То же самое в более формальных терминах: Определение 2.0.5.4 Для игры G, где у каждого игрока i ∈ I есть конечное число (n i ≥ 1) стратегий X i = {x i1 , ..., x in i }, определим смешанную стратегию каждого игрока i как набор вероятностей 12 σ i = (σ k i ) n i k=1 = (σ k i (x k i )) n i |