Случайная стабильность и доминирование рисков в игре 2х2

Напомним, что конвенция – это структура формы (х, х,…, х), где х =(х₁,х₂,…, х_n), являющаяся строгим равновесием G по Нэшу. В таком состоянии каждый будет продолжать играть свою роль в х (без учета ошибок), поскольку х_i является уникальным лучшим ответом, дающим i – ожидания, что все остальные будут играть свою роль в х.

Теорема 4.1. Пусть G есть координационная игра 2 X 2 и пусть P^m,s, ᵋ – адаптивное обучение с памятью M, выборка размера S и ошибка величины ε.

(I) Если информация достаточно неполная (S / M ≤1/2), то из любого исходного состояния спокойный процесс P^{m,s, 0} сходится с вероятностью один к конвенции и блокируется.

(II) Если информация достаточно неполная (S / M ≤1/2) и s и m достаточно велики, случайно устойчивые структуры беспокойного процесса соответствуют один на один рискодоминирующим конвенциям.

Доказательство. Пусть G координационная игра 2 х 2 с платежной матрицей (4,1), удовлетворяющая неравенствам (4,2) так, что и (1, 1), и (2, 2) строгие равновесия по Нэшу. Пусть h₁ и h₂ обозначим как соответствующие соглашения для некоторого фиксированного значения m. Притяжения h₁ определяется как множество состояний h таких, что есть положительная вероятность движения к конечному числу периодов от h до h₁ в спокойном процессе p⁰. Пусть β_i обозначает притяжение h_i, i=1, 2. Чтобы доказать I теорему, мы должны показать, что β₁ и β₂ охватывает пространство состояний.

Пусть h = (x^t-m+1 ,….x’) – произвольное состояние. Существует положительная вероятность того, что оба игрока попробовать определенный набор прецедентов x^t-m+1 в каждый период с t + 1 до t + s включительно. Т.к. ε=0, каждый из них играет лучший ответ. Предположим на минуту, что лучший из ответов является уникальным, скажем, (x*₁, x*₂)=x*. Тогда мы получим перспективу (х*, х*….x*) от периода t + 1 к периоду t + s (если есть связи в лучшем ответе для некоторых игроков, то по-прежнему существует положительная вероятность, что та же пара лучших ответов (x*₁, x*₂)=x* будет выбрана для периодов s, потому что все лучшие ответы имеют положительную вероятность быть выбраными). Заметим, что этот аргумент использует предположение, что s ≤ m/2. Если s слишком велико по отношению к m, некоторые из прецедентов x^t-m+1 ,….x’ "вымрут" к периоду t + s, что противоречит нашему предположению о фиксированном наборе прецедентов для периодов s.

Предположим, что с одной стороны х* является координацией равновесия, то есть х * = (1,1) или х * = (2,2). Существует положительная вероятность того, что, с периодом t + s + 1 через период t +m оба игрока будут совершать действия сразу же. Уникальный лучший ответ на i с любого такого образца х_i* (i = 1,2). Таким образом, к концу периода t +m существует положительная вероятность того, что процесс достигнет соглашение (x*, x*,….x*).

Предположим, с другой стороны, что х * не является координацией равновесия. Тогда х * = (1,2) или х * = (2,1) Без ограничения общности считаем, что х * = (1,2) Существует положительная вероятность того, что от периода t + s + 1 через период t + 2s, строка игроков в дальнейшем будет придерживаться последовательности (x^t-s+1 ,….x’) и играть 1 как лучший ответ. Существует также положительная вероятность того, что одновременно колонка игроков будут попробовать сразу и, следовательно, будут играть 1 как лучший ответ. Таким образом, с периодом t + s + 1 через период t + 2s, мы получим формы (1,1), (1,1),.... (1,1). С этого момента становится ясно, что с положительной вероятностью процесс сходится к конвенции h₁.

Таким образом, мы показали, что из любого исходного состояния существует положительная вероятность достижения h₁ и/или h₂ в конечном числе периодов.

Чтобы установить утверждение (II), применяем теорему 3.1. Пусть г^s₁₂ – наименьшее сопротивление среди всех путей с h₁ и до h₂ функции с размером выборки. Очевидно, что это так же, как наименьшее сопротивление среди всех путей, которые начинаются в h₁ и заканчиваются в ϐ₂, потому что после ввода ϐ₂ не нужно никаких дальнейших ошибок, необходимых для достижения г^s₁₂.

Пусть α и β определены, как в (4,7). Кроме того, пусть [у] обозначим как наименьшее целое число, большее или равное у для любого вещественного числа у. Предположим, что процесс находится в состоянии поглощать h₁, где оба игрока строки и столбца выбрали действие 1 на m периодов подряд. Для игрока столбца чтобы предпочесть действие 2 действию 1, должна быть по крайней мере [αs] случаев действия 2 в образце игрока строки. Это произойдет с положительной вероятностью, если последовательность [αs] игроков колонки выберут действие 2 по ошибке. (Заметим, что при этом используется предположение, что все образцы взяты с положительной вероятностью.) Вероятность этих событий ε^[αs]-порядка. Аналогично, игрок колонки предпочитает действие 2 действию 1 только, если существует по крайней мере [αs] случаев действия 2 в образце игрока колонки. Это произойдет с положительной вероятностью, если последовательность [βs] игроков колонки выберите действие 2 по ошибке, которая имеет вероятность порядка ε^[βs].

Отсюда следует, что переход от h₁ к h₂ есть r^s₁₂ = [αs] ˄ [βs] Простые вычисления показывают, что r^s₂₁ = [(1-α)s] ˄ [(1-β)s]. По теореме 3.1 h₁ случайно устойчив тогда и только тогда, когда r^s₁₂≥ r^s₂₁; аналогично h2 случайно устойчиво тогда и только тогда, когда r^s₁₂ ≤ r^s_21. Если одно равновесие строго рискодоминирующее, скажем, равновесие (1, 1.), то r^s₁₂ ˃ r^s₂₁ для всех достаточно больших s, поэтому соответствующие конвенции является случайно устойчивый. Предположим, с другой стороны, что два равновесия делят риск доминирования. Тогда α = 1 - β и r^s₁₂ = r^s₂₁ для всех s, так как h₁ к h₂ случайно стабильны. Это завершает доказательство теоремы 4.1.

Мы не утверждаем, что незавершенность, связанная с s/m ≤ 1/2 является наилучшим, но некоторая степень неполноты, необходимой для части (I) теоремы 4.1, выполняется. Чтобы понять почему, рассмотрим этикет игры, описанной в главе 2. Пусть s = m и предположим, что процесс начинается в рассогласованном состоянии, в котором либо оба игрока всегда имеют пользу в периоде s, либо они всегда неуспешны. Из-за реакции игроков на полную историю и нулевого уровня, они уверены, что рассогласуются снова. Этот рассогласованность продолжается вечно, и этот процесс никогда не достигает поглощающего состояния. Заявление (i) теоремы утверждает, что такое циклическое поведение не может произойти, когда информация является достаточно полной, потому что неполная выборка обеспечивает достаточно случайные изменения (даже без ошибок), чтобы вытряхнуть процесс из цикла.

4.3 КТО ХОДИТ ПЕРВЫМ?

Чтобы проиллюстрировать этот результат, рассмотрим общую игру, кто ходит первым. Этикет игры является одним из примеров; другой с большим следствием этого является игровым предложением. Предложит ли этот человек даме, как ожидается, или же наоборот? Этот вопрос, очевидно, возникает под влиянием социальных обычаев: у обеих сторон есть ожидания, кто должен взять на себя инициативу, и эти ожидания формируются из того, что другие люди сделали бы в подобных обстоятельствах. Если человек, который должен сделать первый шаг, не делает его, то другие могут принять его как знак безразличие. Если человек, который не должен сделать первый шаг, делает так или иначе, другой может рассматривать это как самонадеянность. Если быть кратким, то неверное движение может иметь серьезные последствия.

Неявные игры здесь – для координации по правилам другой игры (кто идет первым, кто идет второй). Мы можем видеть эту мета игру как одну из чистой координации: если стороны не согласовали между собой, их выплаты равны нулю, если они согласуют, то они получают более высокие выплаты, чем если бы они не сделали этого. Чтобы сделать пример более интересным, мы можем предположить, что выплаты для обеих сторон являются асимметричными. Ради конкретности, пусть выигрыши быть следующим:

(где men-мужчины, women-женщины, propose-предлагать, respond – отвечать)

Случайно устойчивым равновесием является тот, кто максимизирует произведение выплат сторон. В данном примере, это равновесие (9,10), в котором мужчины предлагают, а женщины отвечают. Другими словами, при отмене взаимодействия многих близоруких агентов, "мужчины предлагают" равновесие будет выступать как стандартный, или "обычный" большую часть времени.

Хотя этот пример является сильным упрощением и выплаты изобретены лишь в целях иллюстрации, общий смысл состоит в том, что стабильность конвенции зависит от последствий ее благосостояния индивидов. Более того, выбор конвенции не происходит на индивидуальном уровне; он возникает как непреднамеренное следствие многих людей, удовлетворяющих их ближайшее окружение. Этот пример также иллюстрирует, что игры не всегда даны априори, как игровые теоретики хотели бы предположить; скорее, правила игры сами являются социальными конструкциями (допущениями), которые регулируются эволюционными силами. Чтобы начать игру, нужно иметь общие ожидания относительно того, каковы ее правила, и, кажется разумным предположить, что эти ожидания формируются (в некоторой степени) прецедентом. Поэтому теория предполагает, что правила обычной игры зависит от их ожидаемых выигрышей, и что когда имеет место конкуренция между двумя альтернативными формами игры, тот, кто максимизирует произведение ожидаемых платежей сторон, более вероятно будет наблюдаться в долгосрочной перспективе.

4,4 Игры на поле

Естественный вариант модели обучения возникает, когда отдельные лица образуют единую популяцию и играют в симметричные игры. Это, по сути дела рассматриваются Кандори, Майлат и Роб (1993). Рассмотрим, например, валютные игры, описанные в главе 1. В начале каждого периода, человек обращается наугад и он или она решает, использовать золото или серебро для всех операциях, которые происходят в этот период. Ожидаемый выигрыш зависит от относительных пропорций людей, владеющих золотом и владеющих серебром в общей популяции. Ради определенности будем считать следующие выплаты:

(где gold-золото, а silver-серебро)

Таким образом, если р доля холдинга золота в общей популяции, человек, владеющий золотом, имеет ожидаемый выигрыш за период 3p, в то время как лицо, владеющий серебром, имеет ожидаемый выигрыш 2 (1 - р).

В общем, пусть G – симметричная игра двух лиц с пространством стратегии Х₀, в которую играет одна популяция, состоящая из m лиц. Функции выигрыша заданы как u₁(x,x’) = u₂(x,x’) для игрока строки и игрока столбца, соответственно. В начале каждого периода, каждый человек решает играть по данной чистой стратегии в отношении всех желающих в этом периоде. Для каждого из них x ∈ X₀, пусть k^t_x обозначает число лиц, стремящихся играть стратегию х в период t. Состояние в момент времени t, следовательно, есть вектор целых чисел k^t= (k^t_x), таких, что

В этом контексте, адаптивное обучение работает следующим образом. Пусть s – размер выборки (число между 1 и m), и пусть ε ∈ [0,1] – уровень ошибок. Предположим, что состояние в конце периода t k^t. В начале периода t + 1:

(I) Один агент обращается с населением в случайном порядке.

(II) C вероятностью (1 - ε) агент проводит случайную выборку размером s, без замены, с k^t распределением частот, и играет лучший ответ на полученные образцы пропорций p^{^t}. Если есть связи в лучшем ответе, каждый играет с равной вероятностью.

(III) С вероятностью ε, агент выбирает действие в X₀ наугад, каждый с равной вероятностью.

Это однопопулятивная версия адаптивного обучения структурно схожа с (хотя и не идентична) с двупопулятивным процессом, описанным ранее. В частности, если G является симметричной координационной игрой 2x2, то при 1 ≤ s ≤ m, невозмущенный процесс сходится с вероятностью 1 конвенции, и рискодоминирующая конвенция является случайно стабильной всякий раз, когда s и m достаточно велики.

4.5 ВЫЧИСЛЕНИЯ СТАЦИОНАРНОГО РАСПРЕДЕЛЕНИЯ

Случайная устойчивость говорит нам, что состояния выживают с положительной вероятностью, когда фоновый шум исчезающе мал, но она не говорит, как вероятны эти состояния, когда шум всего лишь "небольшой". Априори мы не можем сказать, сколько "обоснованного' шума, так как это зависит от приложения под рукой. Отсутствие такой оценки представляет интерес спросить, как тесно стационарные распределения ɱ приближается к его асимптотическому пределу, когда уровень шума положителен. В этом разделе мы покажем, как получить точную оценку распределения ɱ для игры 2x2, что дает ощущение, как сильно случайно устойчивое равновесия выбрано в случае, когда шум небольшой, но не исчезающе мал. Удивителен ответ тем, что выбор может быть резким даже для значительных значений ε (например,. е =.05, или.10) так долго, пока численность населения также велика. Причина этого вскоре станет очевидным.

Рассмотрим однопопуляционную обучающую модель для симметричной координационной игры 2х2 в (4,4). Мы должны определить состояние k^t в момент времени t с числом агентов, играющих действие 1; таким образом, пространство состояний является одно-

Рисунок 4.1. Уникальное k-дерево с ненулевой вероятностью для данного состояния k.

мерным. Пусть (ɣ, 1 - ɣ) – смешанное стратегическое равновесие для каждого игрока, то есть, у = (b-c) / (a - d + b - c). Предположим, что ɣ <1/2, то есть равновесие (1, 1) строго рискодоминирующее. Будет удобно считать, что выборка является полной (s = m), то есть каждый игрок реагирует на все распределение, включая его самого. Пусть 0 < k^t < m – состояние в период t (число агентов, играющих действие 1). Предположим, что с вероятностью 1 - ε, игрок, выбранный в период t +1 выбирает лучший ответ на распределение вероятностей (k^t / m, 1 - k^t / m) и что, с вероятностью ε, он случайно выбирает стратегию 1 или 2, каждая с вероятностью ε / 2. Фиксируем ε ∈ (0,1). Пусть P^m "обозначает матрицу перехода этого процесса, то есть, p^m_kk есть вероятность перехода из состояния k к состоянию k' в одном периоде. Обратите внимание, что процесс либо остается в том же состоянии, либо перемещается в соседнее состояние: P^m_kk˃ 0 только если k' = k – 1 или k + 1. Вероятности перехода являются:

Так как единственно возможный однопериодный переход в соседние состояния (или в то же состояние) каждое состояние k связано только с одним k-деревом с ненулевой вероятностью, а именно дерево T_k, в котором все ребра лежат на линии и направлены к k (см. рис 4,1).

Зафиксируем ε ∈ (0,1). Для каждого натурального m, пусть ɱ^m (к) обозначим как единственное стационарное распределение процесса P^m на пространстве состояний 0 ≤ k ≤ m. По лемме 3.1, ɱ^m(к) пропорциональна произведению вероятностей на краях уникального k – дерева T_k. Мы утверждаем, что, когда m достаточно велико, ɱ^m(к) ставит почти все вероятности состояния k таким, что k / m близко к 1 - ε / 2. Чтобы установить это, давайте расширим (4,10) путем определения вероятности правого и левого переходов для каждого действительного числа ɯ ∈ [0,1] следующим образом:

Для каждого ɯ ∈ [0,1], определим

где i пробегает целые 0,1,2… m. Отметим, что для целого k, v^m (k / m) равна произведению вероятностей перехода краев в уникальном k – дереве T_k, следовательно, v^m (k / m) пропорционально ɱ^m(к). Мы будем изучать форму v^m (.), когда m становится большим. Из (4.12) имеем

Для каждого ɯ ∈ [0,1] определим функцию V (ɯ) следующим образом:

Затем

и сходимость равномерна на [0, 1]. В сущности, - V (ɯ) является случайным потенциалом состояния ɯ когда m – численность населения стремится к бесконечности и ставка ошибки ε является фиксированной. (Эта конструкция является достаточно общей и работает для широкого спектра одномерных процессов).

Пусть ɯ* - точка, в которой V(ɯ) достигает своего максимума. Условие первого порядка V'(ɯ*) = 0, которое имеет место тогда и только тогда, когда R (ɯ *) = L (ɯ *). Существуют два решения: ɯ* = 1 - ε / 2 и ɯ* = ε / 2. Прямая оценка (4,14) показывает, что ɯ*= 1-е / 2 является единственным глобальным максимумом. Для каждого маленького δ > 0 пусть F_δ = { ɯ: | ɯ - ɯ* |> δ} и N_δ/2 = { ɯ: | ɯ - ɯ* |≤ δ/2}. Тогда sup{ V(ɯ): ɯ ∈ F_δ } < inf{V(ɯ): ɯ ∈ N_δ/2 } и

Отсюда и из (4,15) мы заключаем, что v^m(.), а также ɱ^m(.) концентрируются в δ-окрестности ɯ* = 1 -ε / 2 для всех достаточно больших m, то есть

Нт цт ({к: | к / ​​т - (1 - 6/2) | <6)) = 1. (4.17)

Резюмируем это в следующий результат.

Теорема 4.1 Пусть G – симметричная координационная игра 2 х 2 со строгим рискодоминирующим равновесием и пусть Q^m – адаптивное изучение в модели полевой игры размера m, полной выборкой и ставкой ошибки размера ε, 0 < ε <1. Для каждого ε' > ε вероятность сколь угодно высока, что не менее 1 - ε'/2 населения играет рискодоминирующее равновесие, когда m достаточно велико.

Этот результат показывает, что, даже когда люди делают независимые ошибки в существенных темпах, агрегация этих ошибок может привести к довольно мощной силе выбора на популяционном уровне.