Лекции по теории игр и политологии
 Скачать 1.03 Mb.
|
|
IN D W , IND S Рассмотрим концепции решений, в которых подразумевается, что игроки информиро- ваны о целях друг друга, причем, это является “общим знанием”: все знают, что все всё знают о целях (рекурсия “я знаю, что ты знаешь” любой глубины). Также подра- зумевается, что игроки неограниченно дальновидны и расчетливы, и это тоже являет- ся общим знанием. По сути, в “итерационно недоминируемом” равновесии считается, что игроки, зная цели друг друга, последовательно отбрасывают свои доминируемые стратегии и ожидают того же от других, взаимно просчитывая ходы (я отбросил свои доминируемые стратегии, знаю, как партнер отбросил свои, и он знает о моих от- брошенных, следовательно... ). Итерации этих расчетов взаимного предсказывания могут привести к решению, называемому “итерационно-недоминирующим решением”. Оно возможно и в сильном и в слабом варианте. Определение 1.3.1 Определим последовательность игр G 1 ⊆ G 2 ⊆ ..., G t , ..., зада- вая каждый раз множество всех стратегий новой игры как прошлое множество (слабо) недоминируемых стратегий: X t+1 := N D t W (t = 1, 2, ...) (предполагается что все игро- ки отбрасывают доминируемые стратегии одновременно). 5 Множество INDW итера- ционно недоминируемых (слабо) исходов игры G 1 есть стационарное множество этой последовательности: IN DW := N D ˆ t W = N D ˆ t−1 W (∃ˆt ≥ 1). Аналогично определена кон- цепция итерационно сильно-недоминируемых исходов INDS, отличаясь только типом доминирования. Множество сложных равновесий SoE W или SoE (sophisticated equilibrium) есть такое INDW , где каждый игрок имеет только эквивалентные стратегии 6 в финальной игре G ˆ t , иначе считают, что SoE W = ∅. Если SoE W 6= ∅, тогда говорят, что игра “разрешима по (слабому) доминированию”. Аналогично определяется разрешимость по сильному доминированию’, влекущая слабую. [Неформально, решение в итерационно- (слабо-)недоминируемых стратегиях (INDW) - это исход игры в случае одновременного итерационного отбрасывания (слабо-) до- минируемых стратегий каждым игроком и соответствующего редуцирования игры: исключения отброшенных стратегий из рассмотрения ВСЕМИ игроками. Требует знания или целей партнеров или факта отбрасывания стратегий. Аналогично INDS, только доминирование - сильное. Сложное равновесие SoE - это INDW, при экви- валентности, по доминированию, финальных стратегий. В терминах ожиданий, эту концепцию решения можно сформулировать так: я, зная цели партнеров, и зная, что они знают мои цели, ожидаю от партнеров неограниченно-глубокой (по глубине ин- дукции) рациональности, то есть расчета наших взаимных шагов по отбрасыванию “плохих” стратегий. Это хорошая концепция решения для гроссмейстеров, играющих в шахматы, но не для новичков.] 5 Рассматривают также сложные равновесия с неодновременным отбрасыванием худших страте- гий, а с заданной последовательностью отбрасываний (Мулен, 1985, стр.40). Они подобны вводимым ниже равновесиям игр в развернутой форме и равновесиям Штакельберга. 6 Это не значит, что все исходы приносят одинаковые выигрыши, см. Табл. 6. 13 Заметим, что эквивалентность моих стратегий в финальной игре не означает, что выигрыши не зависят от деятельности партнера, и сложные равновесия (как и доми- нирующие) могут включать исходы с различными выигрышами всех игроков: − − x − − − − − − −y − − a | 2, 2 (SDE) | 0, 2 (SDE) b | 2, 0 (SDE) | 0, 0 (SDE) Таблица 6: Множество неэквивалентных доминирующих решений, SDE=SoE. В игре на Табл. 6 у обоих участников все стратегии эквивалентны, поэтому вся игра есть SDE = SoE = {(a, x), (b, x), (a, y), (b, y)}. Но выигрыши различны! Применение концепций сильного и слабого итерационного доминирования – рас- смотрите на примере “Экзамен” (Табл. 9). Заметим, что решение INDW может зависеть от порядка слабого доминирования (см. пример (Табл. 16)), в отличие от сильного, где порядок ходов безразличен (до- кажите). Какую из концепций – сильную или слабую – предпочесть, и какой порядок отбрасывания является реалистичным – тонкий вопрос. Ответ определяется дополни- тельной информацией об игре (далее мы касаемся этого в динамических играх). 1.4 Игры в популяциях и равновесие Нэша Заметим, что разрешение игры по итеративному доминированию не обязательно от- ражает знание целей и соображений партнеров, а может быть применимо и к другим ситуациям. Эти “популяционные”, “эволюционные” ситуации играют в дальнейшем из- ложении большую роль. (ср. книгу Васин “Эволюционные игры”.) Подразумевается, что конкретная однократная игра между партнером типа А и партнером типа В – есть одна из типичных игр в достаточно большой популяции по- добных игр. Тогда свои ожидания о поведении партнера (и, возможно, косвенно о его целях) каждый игрок строит по прошлому опыту подобных игр. Скажем, конкрет- ный пассажир, раздумывая, торговаться ли с таксистом или это бесполезно, учиты- вает свой опыт в этом деле с другими таксистами. В таких ситуациях устойчивое в каком-то смысле решение игры естественно называть “равновесием” этой популяции. Интерпретация итеративного доминирования в такой трактовке иная, чем ранее: однажды некоторые игроки отбросили (перестали использовать) доминируемые стра- тегии – и игра уменьшилась (принимаемое во внимание множество возможных стра- тегий стало у 0 же). Их партнеры это наблюдали, и в следующих розыгрышах кто-то отбросил еще какие-то стратегии, это все наблюдали, игра опять уменьшилась и т.д. Очевидно, когда итеративно строго-недоминируемое решение единственно, то оно вы- глядит совершенно естественным “равновесием” такой популяционной игры, и не тре- бует знания целей партнеров. Не-единственность же равновесия и/или только слабое доминирование могут вызывать вопросы к понятию решения. Какое из нескольких равновесий более правдоподобно? Какая концепция – сильная или слабая – лучше прогнозирует исход? Прежде чем сопоставить на примерах сильное и слабое домини- рование, введем еще одну, конкурирующую с ними (особенно в популяционных ситу- ациях), концепцию равновесий. Наиболее часто к ситуациям без знаний целей партнеров применяют концепцию 14 равновесия Нэша — это “рациональное решение при таких ожиданиях ходов партне- ров, где все ожидания оправдались”. Выражая это формально, обозначим β 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). Скажем, в примере “Семейный спор” (Футбол или кино) на Рис. 1.1 два таких равновесия ((футбол,футбол),(кино,кино)), причем одно из них выгоднее для Анны, другое – для Виктора. Аналогично и в игре “Перекресток” два неравноценных равно- весия Нэша. В некоторых играх равновесие Нэша может выражать идею наблюдаемости теку- щих ходов партнеров. Скажем, в игре “Перекресток”, если Анна видит, что Виктор не тормозит, а Виктор видит, что Анна тормозит, то этот исход и реализуется; никто не отступит от текущей стратегии. Впрочем, подобные динамические рассуждения (в том числе об игре “Перекресток”) не совсем корректны, возникают мотивы угроз. Точнее было бы обсуждать подробно последовательность моментов сохранения стратегии, то есть повторяющуюся динамическую игру (см. далее). Более адекватно концепция Нэ- ша применима к повторяющейся игре среди популяции игроков, а не пары игроков. Тогда мои ожидания некоторого поведения от моего сегодняшнего партнера могут быть основаны на прошлом опыте взаимодействия с другими подобными партнерами, но мотивы угроз не возникают, и не искажают решения. По сути, Нэшевское равновесие родственно равновесиям в доминирующих страте- гиях в том смысле, что IDE, INDS, IN DW “глобально стационарны” среди всех стра- тегий, а Нэшевское равновесие — по крайней мере “локально стационарно”. Совпадение ожиданий с истинным выбором позволяет упростить его определение, не формулируя ожиданий явно, ограничиваясь стратегиями: Определение 1.4.1 Равновесие по Нэшу есть профиль стратегий, от которого нико- му нет выгоды отклоняться, если партнеры не отклоняются. Соответственно, множе- ство нэшевских равновесий есть: NE := {¯ x ∈ X| y i ∈ X i ⇒ u i (¯ x i , ¯ x −i ) ≥ u i (y i , ¯ x −i ) ∀i ∈ I}, (3) если же все неравенства строгие, то говорят о строгих равновесиях по Нэшу (SNE). 7 Иными словами, Нэшевское равновесие – точка из которой ни одному игроку нет пользы уходить (он либо ничего от этого не приобретает, либо теряет) при текущих ходах партнеров, а строгое Нэшевское равновесие – точка, из которой вредно уходить. 8 Иначе эту идею можно выразить через понятие “рационального отклика” или лучшего ответа на действия партнеров (“best response”). 7 Не путать с понятием сильного равновесия Нэша, подразумевающим коалиционную устойчи- вость. 8 Иногда еще вводят понятие сильных или коалиционных равновесий Нэша - когда ни одна коа- лиция не может улучшить своего положения. Такие равновесия редки. 15 Отображение (то есть многозначная функция) 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 }. (4) В этих терминах, Нэшевское равновесие – это профиль рациональных откликов всех игроков на рациональные отклики партнеров: ¯ x ∈ NE ⇔ ¯ x ∈ Y i X ∗ i (¯ x −i ). Понятие NE может оказаться применимо в разных случаях. Наряду с популяци- онной ситуацией, и в однократной игре может случиться, что ожидания партнеров почему-либо “сфокусированы” на каком-либо профиле стратегий, считающемся веро- ятным. Например, в игре координации “семейный спор”, если оба почему-то ожидают от партнера выбор “кино”, или хотя бы я ожидаю, что партнер ожидает такой выбор от меня (например, известна уступчивость Виктора, или было сделано какое-то на- мекающее сообщение), то это и случится. Этот довольно распространенный эффект “самоподдерживающихся ожиданий” называют еще “эффектом фокальной точки” (focal point, подробнее обсуждается ниже). В некоторых ситуациях эта фокальная точка возникает в результате предварительных переговоров. Тогда Нэшевское рав- новесие рассматривают как полу-кооперативную концепцию: если оно принадлежит ядру (определяемому ниже), то это “такое соглашение, от которого никто не склонен отступать”, по крайней мере, если ожидает не отступления партнеров. Напротив, в “Дилемме заключенных” хороший для обоих участников исход (мол- чать,молчать) таким естественно-устойчивым соглашением быть не может, а требует каких-то мер принуждения к выполнению такого соглашения. В этом смысле принад- лежность некоторого соглашения к NE – важное преимущество. 9 Оказывается, Нэшевское решение, может быть естественным исходом и в противо- положной – “совсем некооперабельной” ситуации, то есть в антагонистических играх. Определение 1.4.2 Антагонистической называют игру с одинаковой (например, нулевой) суммой выигрышей при любом исходе, т.е. такую, что P i∈I u i (x) = s ∃s ∈ IR, ∀x ∈ X. 10 В таких играх тоже применяют NE, точнее, его сужение, называемое “седлом” или седловой точкой. Определение 1.4.3 Множество седловых точек есть Sad := MM ∩ NE Это те Нэшевские равновесия, где худшие предположения о партнерах сбываются. Например, в играх “Семейный спор” и “Перекресток” седла нет: максимин и Нэ- шевское решение не пересекаются. Впрочем, существование и самого NE не всегда гарантировано, см. игру “Монетки” (Табл. 7). 9 В качестве упражнения на эту тему, рассмотрите всевозможные варианты подобных игр 2х2 с точки зрения совместимости кооперативного и не-кооперативного поведения. 10 Синонимы – игра “с противоположными интересами”, “с нулевой суммой”. Как ни покажется странным, но в этой терминологии войну, в отличие от шахмат, нельзя назвать антагонистической игрой, поскольку обе стороны могут очень пострадать в одних вариантах действий и не очень – при других. 16 Victor: guessing guess Left guess Right An- hold Left -1, 1 1, -1 na hold Right 1, -1 -1, 1 Таблица 7: Игра “Монетки”: Нужно угадать, в какой руке у партнера монетка, тогда ее забираешь, иначе – отдаешь свою (Анна держит, Виктор угадывает). NE = ∅. В повторяющихся играх типа игры “Монетки” под NE может подразумеваться, что каждый игрок наблюдает определенный текущий выбор партнеров на предыду- щем шаге и ведет себя близоруко – не учитывает, что партнеры могут изменить свой выбор когда он изменит свой (неполная рациональность). Пустоту NE = ∅ тогда надо рассматривать как несуществование стационарных точек такой игры: игра "болтает- ся". Заметим, что применение концепций доминирования (INDW, INDS) в этой игре тоже никак не увеличивает определенность наших предсказаний о ее исходах: вся исходная игра недоминируема. 1.4.1 Смешанные стратегии и смешанное равновесие 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 ), то есть функцией линейной по вероятности, или, иначе, матожиданием полезности. Именно такими мы и будем считать участников игр далее. Итак, пользуясь идеей "средней полезности”, в повторяющейся игре “Орлянка или Чет-нечет (Монетки)” мы можем искать вероятностное решение: насколько часто каж- дый игрок в среднем будет делать тот или иной ход. Для этой игры естественная гипотеза - с равной вероятностью оба ходят левой и правой рукой: ((0.5,0.5),(0.5,0.5)). Но как проверить эту догадку и обосновать ответ, если он верен? Идею равновесия, о котором мы догадываемся, можно сформулировать так. Нэшевское равновесие в смешанных стратегиях исходной игры - есть Нэшевское равновесие в ее смешанном расширении, то есть профиль (на- 17 |