теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
Заметим, что выбор индикатора неоднозначен: с точностью до строго монотонного преобразования. (?)Докажите это в общем виде? Примеры 7. Демонстрируя неоднозначность, постройте по два индикатора пред- почтения а)для гиперболы со степенью: y = 1/x 2 (?), б)для круговых линий уровня расхо- дящихся (возрастающих) наружу или возрастающих внутрь, в)для прямых уголков, у которых точка излома возрастает от начала координат по биссектрисе или не по биссектрисе, (см. также такие задачи ниже). Утверждение. Любое строго монотонное преобразование индикатора есть инди- катор того же предпочтения. Доказательство - элементарно. . . . . . Оказывается, подобрать индикатор не всегда возможно, даже если предпочтение полно, транзитивно (ниже пример — разрывное “Лексикографическое” предпочте- ние). Для непрерывных же рациональных предпочтений в лекциях приведена – Теорема Дебре (G.Debreu) о представимости непрерывных предпочтений целевыми функциями: Th.: Если предпочтение рационально (полно, транзи- тивно) и непрерывно, то найдется представляющая его функция – инди- катор, причем непрерывная (?) Док-во – частично было на лекции (а более общее - см. в кн. Алипрантис). Идея доказательства для монотонных предпочтений на R n + Непредставимость: Контрпример непредставимости предпочтений в отстут- ствии непрерывности – это предпочтение Lexgraph. Это такое предпочтение: Если у вектора x первая компонента больше, чем у y, то x лучше. Если они равны, то сравниваются вторые компоненты аналогично. Если и вторые равны, то третьи, и т.д. Утверждение: предпочтение Lexgraph не может быть представлено никакой функцией. Причина - то, что оно не непрерывно. Определение. Максимальный элемент в множестве – тот, для которого в этом множестве нельзя найти более хорошего элемента. А наилучший элемент - тот, что строго лучше всех других. Утверждение. Все максимальные элементы лежат в одном множестве безраз- личия. (Очевидно) 12 Глава 1. Предпочтения, кооперативные игры, общее равновесие Утверждение. Максимальные элементы непрерывного предпочтения на компак- те существуют. (Очевидно) (Выпуклость предпочтений в связи с вогнутостью и квазивогнутостью их инди- каторов) . . . . . Связь свойств предпочтений и функций в векторных пространствах Вогнутость функции и квазивогнутость. Свойство функции-индикатора свойство соответствующего предпочтения u(.) однозначно определена ⇒ º рационально u(.) монотонна (возрастает) ⇒ º монотонно u(.) строго монотонна (стр. возрастает) ⇒ º строго монотонно u(.) непрерывна ⇒ º непрерывно u(.) вогнута или квазивогнута ⇒ º выпукло (Лекция 2) 1.2 Многоцелевой оптимум: сильный и слабый оп- тимум Парето Когда целевых функций много, обычное понятие оптимальности приходится обоб- щить. Рассмотрим любую ситуацию, где есть множество участников N = {1, ..., n} и общее множество доступных им альтернатив X. Сильное и слабое доминирование среди векторов: знаки (2, 3) ≥ (2, 3), (2, 3) > (2, 2), (2, 3) À (1, 2). Сильное и слабое доминирование среди профиля предпочтений коллектива Ann, Bob: V ine º AB V ine ⇔ (u A (V ine), u B (V ine)) ≥ (u A (V ine), u B (V ine)); V ine  AB T ea ⇔ (u A (V ine), u B (V ine)) > (u A (T ea), u B (T ea)) ⇔ (u A (V ine), u B (V ine)) ≥6= (u A (T ea), u B (T ea)); V ine  AB W hisky ⇔ (u A (V ine), u B (V ine)) À (u A (W hisky), u B (W hisky)). Слабо Парето-оптимальные ( ˜ P или wP ) – это доступные альтернативы, для которых нет сильного Парето-улучшения среди доступных альтер- натив, то есть которые нельзя улучшить для всех участников сразу (нет доступного сильного Парето-доминирующего варианта) Сильно Парето-оптимальные ( ˜ P ) – это доступные альтернативы, для ко- торых нет слабого Парето-улучшения среди доступных альтернатив, то есть которые нельзя улучшить для кого-то не ухудшив для кого-то (нет доступного слабого Парето-доминирующего варианта) Пример “Круглый остров”. Есть в теплом море круглый остров радиуса 5 км, центр имеет координаты (0,0), то есть допустимое множество X = {(x 1 , x 2 )| x 2 1 + x 2 2 ≤ 5}. Для полноты рая, Анна и Боб собираются построить общий шалаш, но Анна хоте- ла бы по-восточнее, чтобы романтично встречать рассветы, а ленивый Боб поближе к любимой точке (-3,4) – банановой пальме. Эти предпочтения можно описать, на- пример, функциями u A (x 1 , x 2 ) = x 1 , u B (x 1 , x 2 ) = −(x 1 − 3) 2 − (x 2 − 4) 2 , (можно и другими, с точностью до строго монотонного преобразования). 1.3. Индивидуальные и коалиционные возможности: “переговорное множество”и ядро 13 Легко проверить, что сильный и слабый Парето-оптимумы этого сообщества в этой задаче поиска компромиссов совпадут: P = wP, и окажутся некой кривой со- единяющей наилучшую для Анны точку x ∗ A = (5, 0) с наилучшей для Боба точкой x ∗ B = (−3, 4). При этом, часть этого множества идет горизонтально по внутренности острова - от точки x ∗ B до береговой точки (3, 4), а остальная часть по восточному берегу до x ∗ A = (5, 0). Можно предложить два геометрических критерия проверки любой точки ˆ x на Парето-оптимальность. (1) Провести через нее все линии уровня. Если множество L ++ N (ˆ x) лучших для всего сообщества N = {A, B} точек (сильно-доминирующих) пусто, то она слабо-Паретовская. Если к тому же множество L + N (ˆ x) не-худших для всего сообщества точек состоит только из этой точки ˆ x, то она и Паретовская (а если не только из нее, то нужно исследовать подробнее). (2) Можно в проверяемой точке построить градиенты всех целевых функций, то есть нормали к линиям уровня. Если для внутренней точки не существует неотри- цательных весов с которыми эти градиенты суммировались бы к нулю, то точка никакая, ни слабо и ни сильно-Паретовская. Для краевой точки в качестве допол- нительного градиента можно брать "реакцию опоры", сдерживающую рост полез- ности, то есть нормаль к активному в точке ограничению. В другую сторону (что точка Паретовская) этот критерий в невыпуклой задаче может подвести, поскольку бывают и локальные оптимумы не являющиеся глобальными. 1.3 Индивидуальные и коалиционные возможности: “переговорное множество”и ядро Пусть, к уже рассмотренным задачам добавляется новое условие. Теперь, кроме сов- местных действий, каждый участник может что-то и в одиночку. Это накладывает дополнительное ограничение на множество возможных компромиссов, или ”исходов соглашения”, которое мы пытаемся предсказать. Участник отвергает соглашение, ес- ли оно хуже некоторого ”статус-кво”, случившегося точкой отсчета в переговорах. В играх обмена это точка начального запаса. В приведенной задаче об острове, пускай, точка отсчета – это условие, выдвинутое каждым, что он уступит не более 2/3 своей полезности, от наилучшей для него до наихудшей на острове точки. Где тогда могут лежать исходы переговоров? Есть соответствие между допустимым множеством в физическом пространстве выбора – например, точки на рассмотренном острове – и допустимым множеством результирующих полезностей. Пространство достижимых уровней полезности назы- вают критериальным пространством, оно имеет такую размерность как число участ- ников игры (в отличие от физического пространства выбора). Каждую точку физи- ческого пространства x ∈ X можно отобразить вектор-функцией u N = (u 1 , ..., u n ) в точку критериального пространства (u 1 (x), ..., u n (x)) ∈ R n . Но точке Парето здесь может соответствовать несколько прообразов в исходном физическом пространстве, доставляющих ту же полезность. Так или иначе, все допустимое множество x ∈ X имеет некоторый образ u N (X) в критериальном пространстве. Обычно считают, что вместе с любой полезностью участнику игры доступна и меньшая (вред себе все уме- ют приносить), поэтому допустимым множеством полезностей считают не сам образ u N (X) физического множества, а его расширение ˜ U вниз до бесконечности по всем 14 Глава 1. Предпочтения, кооперативные игры, общее равновесие направлениям: ˜ U = u N (X) + R n − . На этом множестве Парето-оптимум выглядит как его верхняя правая граница, поэтому его часто так и называют. Мы увидим, что когда ц. функции вогнуты, то множество . выпукло и его Парето-граница непрерывна в некотором смысле. Забегая вперед, в дополнение к Контрактному множеству введем понятие ядра, оно нам понадобится для анализа равновесий. Определение. Ядром игры называется множество альтернатив, не блокируемое никакой коалицией. Коалиция S блокирует (отверга- ет) какую-либо альтернативу x, если имеет в своем распоряжении (что бы ни делали остальные участники) другую альтернативу y, строго луч- шую, чем x для всех участников из S. Это определение имеет ясный смысл только в тех играх, где возможности ко- алиций ясно описаны. Например, они описаны в терминах пространства выигры- шей, которое мы здесь преимущественно и обсуждаем, то есть следует понимать, что x, y ∈ R n – это вектора выигрышей. Или, в экономике обмена, x, y ∈ R n – это распределения товаров. Из определения очевидно, что слабая Парето-граница есть просто множество альтернатив, не блокиру- емых большой (полной) коалицией 1.3.1 Теоремы, характеризующие сильный и слабый Парето- оптимумы (Характеризация Парето-оптимума варьированием ограничений.) Утверждение 1.3.1.1 Пусть предпочтения заданы функциями u i (.) на допу- стимом множестве X. Допустимая точка x ∈ X является Паретовской (x ∈ P ) тогда и только тогда, когда она есть решение n оптимизационных задач по макси- мизации полезности каждого при неубывании полезности остальных по сравнению с этой точкой: ¯ x ∈ P ⇔ [∀i ¯ x ∈ arg max x∈X u i (x) : u j (x) ≥ u 0j = u j (¯ x)∀j]. Доказательство очевидно, ведь это и есть определение Парето-оптимума: неулуч- шаемость предпочтений любого из участников при неубывании полезности осталь- ных. Соответственно, варьируя запрашиваемые уровни u 0j полезности каждого, можно получать разные точки Парето-оптимума, и перебрать их все. Варьирование весов целей для характеризации Парето-оптимума и его существование. Есть и другой способ вычислить все точки Парето-оптимума варьируя парамет- ры. Введем вектор весов α ∈ R n + , α 6= 0 и соответствующую Функцию Суммарного Благосостояния в виде U α (x) = X i α i u i (x). 1.4. Вальрасовское равновесие и ядро в игре обмена 15 Теорема. (1) При неотрицательных весах α ∈ R n + , любой аргмаксимум суммар- ного Благосостояния является слабым оптимумом Парето, при положительных весах являющийся и оптимумом Парето: ¯ x ∈ arg max X i α i u i (x) => ¯ x ∈ wP. (2) Если целевые функции вогнуты, а допустимое множество выпукло, то любой эле- мент оптимума Парето можно найти как аргмаксимум суммарного Благосостояния взятого с неотрицательными весами: ¯ x ∈ P => ∃α > 0 : ¯ x ∈ arg max X i α i u i (x). Следствие. Пусть допустимое множество – непустой компакт и целевые функции непрерывны. Тогда Парето-оптимум непуст, и более того, содержит точки не-худшие по сравнению с любой допустимой точкой. Доказательство теоремы в прямую сторону – несложно (от противного). Доказа- тельство теоремы в обратную сторону – по теореме отделимости выпуклых множеств, используя выясненную выпуклость множества достижимых полезностей. Доказательство Следствия – по теореме Вейерштрасса, применяя предыдущую теорему с любыми ненулевыми весами. Утверждения о форме Парето-оптимума . . . . . Утверждение 1.3.1.2 Если допустимое множество компактно, а предпочте- ния рациональны и непрерывны (например, заданы непрерывными функциями) то на каждой линии или поверхности безразличия каждого участника в допустимом множестве есть точка Парето. Если к тому же участников двое и их предпо- чтения выпуклы (на выпуклом д.м.), то подмножество Паретовских точек при- надлежащее любой поверхности безразличия любого из участников выпукло. Если предпочтения при этом строго выпуклы и строго монотонны (например, заданы строго вогнутыми строго монотонными функциями), то это единственная точка. Утверждение 1.3.1.3 Если допустимое множество выпукло и компактно, а предпочтения заданы непрерывными вогнутыми функциями, то Парето-оптимум – связное множество, включающее наилучшие точки каждого из участников. 1 1.4 Вальрасовское равновесие и ядро в игре обмена (Лекция 4) В этой лекции рассмотрим частный случай игр – игры обмена товарами. Будем интересоваться тоже Парето-оптимумом, ядром, и новым понятием – равновесием Вальраса. Вообще, это основная классическая модель совершенного (неискаженного) рынка. Она предложена в идее Адамом Смитом, развита в виде примеров Давидом 1 Связность множества означает существование пути (непрерывной кривой) из любой точки в любую. Вполне строго сформулировать и доказать это в рамках этого курса не получится, нужны понятия топологии. 16 Глава 1. Предпочтения, кооперативные игры, общее равновесие Рикардо, записана в уравнениях Вальрасом и Джевонсом в 19-м веке. В 1950-е годы Эрроу и Дебре теоретически “зачистили” эту модель, доказав существование равно- весий, их Парето-эффективность и другие свойства, и получили за это Нобелевскую премию. Модель стала "неоклассической”. Мы повторим вариант без производства, известный вам из курса микроэкономики, но с деталями и доказательствами (кото- рые понадобятся вам на 3-м курсе). Неоклассическая модель для рынка обмена l товарами включает исходные данные: 1)предпочтения или целевые функции u i (.) для n потребителей, 2)исходное рас- пределение собственности: для каждого i начальные запасы ω i и долю θ ij ≤ 1 в прибыли j предприятия. По этим исходным данным предсказывается “состояние” экономики (x, y, p), ко- торое включает: план общего потребления x ∈ R ml , цены p ∈ R l . В сущности, найти равновесие – значит решить задачу аукциониста: подобрать цены, при кото- рых спрос участников совпал бы с предложением по всем товарам. В аналитических задачах этот подбор сводится к системе уравнений, вытекающих из определения равновесия. В графических задачах это делается перебором наклонов ценовой линии. Определение. Состояние экономики обмена (¯ p, ¯ x) ∈ R l∗ml∗nl назовем равновесие Вальраса (W E), если: 1) (¯ x, ¯ y) – оптимальный выбор потребителей при ценах ¯ p, т.е., ¯ x ∈ X ∗ i (¯ p), ¯ y ∈ Y ∗ j (p), где спрос и предложение есть X ∗ i (p, y) = arg max x i ∈B i (p,y) u(x i ), ∀(p, y) ∈ R l+nl , Y ∗ j (p) = arg max y j ∈Y j (py j ), ∀p ∈ R l 2) выполнены материальные балансы спроса по всем товарам, то есть равенство нулю "избыточного спроса” ζ: ζ := P m i=1 (¯ x i − ω i ) − P n j=1 ¯ y j = 0 ∈ R l . Когда производства нет, равновесие Вальраса для двух участников и двух то- варов можно найти графически на "ящике Эджворта”. Как показано в лекциях (в конце этого текста), равновесие в ядре. Следовательно, задакча аукциониста сводит- ся к предложению ценовой линии, соединяющей точку начальных запасов с одной из точек ядра. Причем такой, чтобы спрос совпал с предложением, то есть выбор пер- вого участника x 1 и выбор второго |