теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
x 2 оказались совместимы, графически совмеще- ны. Выбор потребителя с выпуклым предпочтением есть точка (или точки) касания бюджетного треугольнике наивысшей из его линий уровня, задевающих бюджетное множество. Если это точка не угловая, то это касание означает пропорциональность градиентов полезности и цен: ∇u i = α p, то есть, MRS i (k/ˆk) := ˙u ik (x i ) ˙u iˆ k (x i ) = p k p ˆ k ∀k, ˆk. Тем самым, внутренние равновесия будут характеризоваться такими же диффе- ренциальными условиями, что и Парето-граница, плюс бюджетные ограничения в форме равенгств: px i = pω i . Это и означает, что ценовая линия, выходя из точки на- чальных запасов, должна отделить в точке равновесия более желательное множество одного от более желательного множества другого участника. 1.4. Вальрасовское равновесие и ядро в игре обмена 17 6 - 0 ¾ ? x 2 x 1 z 1 z 2 ω ¯ x 6 - 0 ¾ ? x 2 x 1 z 1 z 2 ω ¯ x 0 0 µ µ ª ® µ µ ª ª * * ¾ ® 6 Рис. 1.1: Графическое нахождение равновесий Вальраса. По сути, диаграмма Эджворта – это и есть два бюджетных треугольника (один из которых перевернут), совмещенные ценовой линией и начальными запасами. Если выборы участников на бюджетных множествах (у каждого на своем) совме- стились, то это равновесие. Та же идея для краевых равновесий. Рассмотрим Пример. Два участника, целевые функции линейны: u x = x 1 + x 2 , u z = z 1 + 2z 2 , ω x = (1, 1), ω z = (3, 2). Найдем последовательно сужая: Парето, ядро и равнове- сие. Легко видеть по критерию "зоны улучшения для двоих"(см. выше), что Парето пойдет по правой и нижней грани ящика. Далее,как мы выясняли, ядро окажется от- резком из Парето, лежащим между двух линий уровня, проходящих через начальный запас, см. Рис. Остается выбрать равновесие. 1) Предположим, равновесие где-то посредине отрезка ядра. Тогда, легко понять, второй участник выбрал бы свое потребление z на верхнем для него (нижнем на рисунке) углу своего бюджетного множества. Потому, что он ценит 2-й товар вдвое выше первого, а любая ценовая линия идущая из начального запаса во внутренность ядра, ценит 2-й менее чем вдвое против 1-го товара. Этот угол выходит за край бюджетного множества, но потребителя это не должно волновать. Аукционист его спросил: сколько бы ты хотел потреблять при таких ценах, он и ответил. Не его дело учитывать обще системные ограничения наличия товаров, а дело аукциониста. Итак, во внутренности ядра равновесий нет. В левом углу ядра равновесия нет по тем же причинам: 2-й потребитель предъявляет слишком большой спрос на 2-й товар, это не равновесие. Но где-то же оно должно быть, по теореме существования: целевые функции непрерывны, возрастают и вогнуты, запасы внутренние. Проверяя правый угол ядра, увидим, что это равновесие. Для второго участника ценовая линия параллельна линиям уровня, и он согласен на любой выбор из нее. А первый выбирает свой правый угол. Они договорятся в отмеченной точке ¯ x. Общее правило таких краевых равновесий: условие касательности линии уровня 18 Глава 1. Предпочтения, кооперативные игры, общее равновесие и ценовой линии обязательно для того участника, для кого равновесие внутреннее а не краевое в его бюджетной линии. Для участника же, для которого равновесие в углу, условие аргмаксимума выра- зится в "касательности” в форме неравенства: ¯ x 2 = 0 => ˙u x2 (¯ x) ˙u x1 (¯ x) ≤ p 2 p 1 . 1.5 Ядро в играх с трансферабельной полезностью и дележи (Лекция 5) Напомним: Определение. Ядром игры называется множество альтернатив, не блокируемое никакой коалицией. Калиция S блокирует (отвергает) какую-либо альтернативу x, если имеет в своем распоряжении (что бы ни делали остальные участники) другую альтернативу y, строго лучшую, чем x для всех участников из S. В том числе, слабая Парето-граница есть просто множество альтернатив, не блокиру- емых большой (полной) коалицией Определение блокирования имеет ясный смысл только в тех играх, где возможно- сти коалиций ясно описаны. Например, они бывают описаны в терминах простран- ства выигрышей, которое мы здесь преимущественно и обсуждаем. Тогда понимаем, что x, y ∈ R n – это вектора выигрышей. Или, в экономике обмена, x, y ∈ R nl – это распределения товаров. Рассмотрим пример: Аня и Боб решили ловить рыбу. Аня может грести, а Боб бросать спиннинг или наоборот. Пусть, их полезности в этих двух вариантах такие... Пусть, индивидуальные возможности – если отказаться ловить вместе рыбу и остать- ся дома – приносят каждому по 0.5 полезности. Где ядро? Теперь допустим, что они измеряют полезность в одинаковых единицах – напри- мер в пирожках, и способны передавать друг другу пирожки за уступку в вопросе кто гребет, а кто ловит. Тогда допустимое множество заметно расширилось и стало плоским, т.е., полупространством. Теперь ясно, кто станет грести, неясно только как поделят выигрыши. Это получилась "игра с трансферабельной полезностью". Глава 2 Статические или “одновременные” некооперативные игры 2.0.1 Обозначения и термины “Нормальную” форму игры часто соотносят со случаем “статической” или одновре- менной игры (однократные одновременные ходы участников), а развернутую форму — с “динамическими” играми (последовательные ходы), хотя мы увидим, что воз- можны и другие трактовки. Нормальная форма описывает физическую и целевую структуру игры как объект 1 G := hI, X, u(.)i = hI, {X i } i∈I , {u i (.)} i∈I i , где I := {1, ..., m} — множество участников i, X := (X i ) i∈I := Q i X i = (X 1 ×X 2 ×...×X m ) — набор (профиль) допустимых множеств стратегий (x i ) i∈I участников, u := (u i ) I = (u i ) i∈I — набор (профиль) целевых функций участников, причем, каж- дая целевая функция u i : X i 7→ IR зависит, вообще говоря, от всех выбранных стратегий (x j ) j∈I ), а не только от своей. Состоянием игры в нормальной форме будем называть или профиль x = (x i ) i∈I выбранных стратегий, или, более полно, пару (x, β) выбранных стратегий и ожида- ний всех участников. Ожидание β i ∈ X каждого участника о ходах всех партнеров может совпадать с настоящими, намеченными к исполнению, стратегиями, или не совпадать. Проиллюстрируем используемые далее принципы обозначений и простейшее понятие решения на примере. Пример 2.0.1 “Игра координации” (известная в учебниках игр как “семейный спор” = “Battle of Sexes”: Luce and Raiffa, 1953). Далее, как и здесь, мы будем большими буквами обозначать участников или мно- жества, а малыми латинскими буквами – переменные, то есть стратегии. Греческие 1 Возможно также более общее представление игр (оно соответствует, в частности, Вальрасовско- му равновесию игр обмена): не только выигрыши, но и текущее допустимое множество стратегий каждого участника может зависеть от текущих действий других участников. 19 20 Глава 2. Статические или “одновременные” некооперативные игры буквы используются для ожиданий или вероятностей, в данном случае β V – это ожи- дание (belief) Виктора о ходе Анны. Играют Анна (персонаж, который далее во всех обсуждаемых динамических иг- рах ходит первым и обозначается А) и Виктор (персонаж, который в других играх, не как здесь, ходит позже Анны и, соответственно, обозначается буквой V стоя- щей позже в латинском алфавите). Здесь Анна и Виктор ходят одновременно, после хода “Природы”, сформировавшей у них какие-то “ожидания” (beliefs) о поведении партнера. Они почему-либо не имеют возможности переговариваться. Возможно, это период симпатии еще до того как они “познакомились”, или это супруги, уже устав- шие спорить и каждый молча гнет свою линию :-). Каждый выбирает, пойти ли вечером на футбол или в кино. Оба предпочли бы оказаться где-нибудь вместе, что отражено в таблице выигрышей на Рис. 2.0.1. А именно, совместное попада- ние в кино ( x = (x A , x V ) := (c A , c V ) ) дало бы вектор полезностей (выигрышей) (u A (c A , c V ), u V (c A , c V )) := (3, 2), а совместное попадание на футбол дает выигрыши (u A (f A , f V ), u V (f A , f V )) := (1, 4). U q Nature Victor Anna * j j N 3, 2 0, 0 0, 0 1, 4 cinema (c A ) cinema (c V ) football (f V ) footb. (f A ) Ann’s belief (β A ) Vic.’s belief (β V ) Payoff matrix Рис. 2.1: Игра координации типа “Семейный спор” или “Chicken game”. 2 В каждой клетке, соответствующей одному из 4-х возможных исходов, помещен сначала субъективный выигрыш строчного игрока – Анны (измеренный в некоторых единицах полезности), затем - выигрыш Виктора. Стрелки отражают последователь- ность ходов, в данном случае - то, что игроки вынуждены принять решения одно- временно, не зная выбора другого, а только имея какие-то “ожидания” (expectations, beliefs) об этом выборе, предопределенные природой (случаем). Что может произойти? Очевидно, если оба ожидают от партнера выбор “футбол”, то есть β A = f ootb V , β V = f ootb A , тогда рациональный выбор каждого — присо- единиться к выбору партнера, и исходом будет счастливая (более счастливая для Виктора) встреча на футболе: x A = f ootb A , x V = f ootb V . Аналогично, совпадающие ожидания о кино привели бы к счастливой, особенно для Анны, встрече в кино, а несовпадающие гипотезы – к развлечениям порознь. 3 3 Заметим, что здесь независимое принятие решений игроками может приводить к Парето- неэффективному исходу, что вообще типично в не-кооперативных играх. Эффективных же вари- антов координации оказалось 2, причем один выгоднее для одного игрока, а другой для другого, поэтому если кто-то имеет возможность пойти первым и этим вынудить партнера подстроиться, то 21 Итак, мы описали простейший вариант решения игры – “решение с заданными извне (не согласованными с реальностью) ожиданиями”. Далее будем в основном рассматривать другие, согласованные, типы решений, в том числе, для этой же игры. О понятиях решения. Вообще говоря, найти решение игры означает, предска- зать множество ее возможных состояний, соответствующих нашим (наблюдателя) гипотезам о принципах поведения и информации участников. Совокупность наших гипотез задает некоторое “согласование” стратегий и ожиданий. Обычно оно фор- мализуется в “концепции решения” или “равновесия”, то есть состояния, от которых участники не станут переходить к другим состояниям, если игра повторится. В приведенном примере для предсказания исхода мы использовали простейшую концепцию – решение с заданными заранее ожиданиями ходов, ожиданиями, из- вестными откуда-то нам, предсказывающему исход игры наблюдателю. Ожидания не предполагались “согласованными”, или “обоснованными” истинными намерения- ми партнера, поэтому такая концепция мало применима. Перечислим более сложные концепции решения игр, изучаемые в этом разделе. (Табл.1): Информация, на которую Тип возникающих решений ориентируется участник j ∈ I : (равновесий), т.е., поведения: - только на знание множеств (X i ) I ⇒ MM — “осторожное” (максимин), IDE, SIDE — “доминирующее”, - еще и на чужие цели (u i ) I\{j} ⇒ IND S , IND W — “итерац.домин.”, - на текущий чужой ход (x i ) I\{j} ⇒ NE — “Нэшевское” - на текущую вероятность ходов ⇒ NEm — “Нэшевское в смешанных стратегиях” - лидер знает цели, ведомые - теку- ⇒ StE — щий ход “Штакельберговское” - на соглашение с партнерами ⇒ C — ядро — “кооперативное” Таблица 2.1: Разные типы решений игр в нормальной форме, в зависимости от ин- формации о партнерах (это не значит, что решение Нэша нельзя применять в си- туации знания чужих целей или в ситуации переговоров, таблица говорит только о типичности применения понятий). Всюду в таблице подразумевается знание соб- ственных целей, и “общее знание” множества возможных стратегий всех участников. Обсудим последовательно каждую из концепций решения, начав с простых. 2.0.2 Максимин и доминирование Будем обозначать через x −i := (x j ) j∈I\{i} профиль (набор) стратегий всех игроков кроме i, и аналогично индексировать множества и функции. Сначала рассмотрим случай, когда игроки не обладают информацией ни о це- лях, ни о намеченных стратегиях партнеров. Если они к тому же ведут себя “очень осторожно”, то подходит следующая концепция решения. лидер в выигрыше. Такую ситуацию часто называют “chicken game”: кто из двух цыплят первым клюнул червяка, тому больше досталось. 22 Глава 2. Статические или “одновременные” некооперативные игры Определение 2.0.2.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 ) ) }, (2.1) при этом MM := Q i∈I X M M i – множество максиминных решений игры. Поясним: выбирая осторожно-оптимальную стратегию игрок ожидает от партне- ров самого худшего для себя, то есть ожидания игрока есть β i = (inf z −i ∈X −i u i (y i , z −i ) ) (равновесием решение ММ обычно называть нельзя, поскольку ожидание всего худ- шего может не оправдаться и при новом розыгрыше подобной игры они переходят по-другому). Каждый максимизирует выигрыш при этих мрачных ожиданиях, то есть в целом – максимизирует гарантированный выигрыш. Такое поведение кажется правдоподобным при неизвестности целей партнеров, крайней осторожности игроков и однократном розыгрыше (см. пример “Перекресток” - Табл. 2.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.2: Игра координации “Нерегулируемый перекресток” (тоже “chicken game”). Нет правил, и каждый может продолжать быстро ехать или затормозить. Худший исход – столкновение – игроки оценивают для себя в -1000$, а возможность опередить соперника – в 1$. Осторожное решение – MM: (Stop A , Stop V ). Рядом, для сравнения - “антагонистический” вариант этой игры при невозможности разбить ма- шины: нулевая сумма выигрышей всюду. В антагонистической игре (т.е. “игре с нулевой суммой” или, вообще, с постоян- ной суммой выигрышей) концепция максимина очень естественна (см. ниже понятие “седла”). В других ситуациях, как видно из примера “Перекресток”, максиминные решения могут не вызывать доверия как прогнозируемый результат повторяющейся игры. Игра типа “Перекресток”, разыгрываемая многократно, вряд ли будет приво- дить к взаимно-осторожному решению (Stop,Stop), означающему по сути несогласо- ванные с истинными намерениями партнера ожидания. Скорее всего, ожидания тем или иным путем скорректируются и согласуются (см. “повторяющиеся игры”). Концепция максимина при осторожности имеет альтернативы: если игроки осто- рожны, то почему не внести степень их неприятия риска в явном виде в значения выигрышей, приписывая одновременно некоторые вероятности ожидаемым ходам партнеров? Впрочем, бывают случаи, когда ожидания о партнерах не играют роли; это ситу- ации, где имеет место “доминирование”. 4 Как обычно, sup = max, inf = min, если max |