Лекция 7 (Лекции (4))

Арбитражные схемыАрбитражной схемой называется пара (X, d), где X ⊂ R2 - переговорноемножество, а d ∈ X - точка несогласия. IR(X) - множество индивидуальнорациональных векторов переговорного множества: IR(X) := {x ∈ X | x ≥ d}.Решением для класса арбитражных схем B называется отображениеφ : B → R2 .И.В.Кацев (СПб ЭМИ)Динамические игры20121 / 13Аксиомы1. Парето-оптимальность:φ(X, d) ∈ ∂ X.2.

Индивидуальная рациональность:φ(X, d) ≥ d.3. Независимость от аффинных преобразований: для a> 0, b ∈ R2φ(aX + b, ad + b) = aφ(X, d) + b.4. Анонимность: если π : R2то φ(π X, π d) = πφ(X, d).→ R2 - симметрия относительно прямой y = x,5. Независимость от несущественных альтернатив: если X′φ(X, d) ∈ X′ , то φ(X′ , d) = φ(X, d).⊂Xи6. Ограниченная монотонность. Пусть две АС B1 = (X1 , d), B2 = (X2 , d),таковы, что X1 ⊂ X2 и maxx∈IR(X1 ,d) xi = maxx∈IR(X2 ,d) xi для i = 1, 2.

Тогдаφ(X1 , d) ≤ φ(X2 , d)И.В.Кацев (СПб ЭМИ)Динамические игры20122 / 13Арбитражное решение Нэша.Теорема (Нэш, 1950).Существует только одно решение, удовлетворяющее аксиомам 1,3,4,5. Онозадается следующей формулой для B ∈ B :n∏φ(B) = arg max(xi − di ).x∈IR(X).И.В.Кацев (СПб ЭМИ)i=1Динамические игры20123 / 13Арбитражное решение Калаи-СмородинскогоИдеальной точкой арбитражной схемы B = ⟨X, d⟩ называется векторI(X, d) ∈ R2 :(I(X, d))i = max xi .x∈IR(X,d)6I(X, d)•xKC-dИ.В.Кацев (СПб ЭМИ)Динамические игры20124 / 13Арбитражное решение Калаи-Смородинского.Theorem.Существует единственное решение для класса B2 , удовлетворяюшееаксиомам1,3,4,6. Это решение Калаи–Смородинсткого..И.В.Кацев (СПб ЭМИ)Динамические игры20125 / 13Кооперативные игрыПереговорное множество = то, что все игроки могут получить вместеТочка несогласия = то, что игроки могут получить по отдельности.И.В.Кацев (СПб ЭМИ)Динамические игры20126 / 13Кооперативные игрыПереговорное множество = то, что все игроки могут получить вместеТочка несогласия = то, что игроки могут получить по отдельности.Надо учитывать и ”промежуточные” варианты - коалиции игроков.И.В.Кацев (СПб ЭМИ)Динамические игры20126 / 13Кооперативные игрыРассмотрим бескоалиционную игруΓ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩.И.В.Кацев (СПб ЭМИ)Динамические игры20127 / 13Кооперативные игрыРассмотрим бескоалиционную игруΓ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩.Игроки → коалиция → выигрыш коалиции.И.В.Кацев (СПб ЭМИ)Динамические игры20127 / 13Кооперативные игрыРассмотрим бескоалиционную игруΓ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩.Игроки → коалиция → выигрыш коалиции.Если игроки коалиции могут перераспределять выигрыш между собой, то этоигра с трансферабельными полезностями (TU game), иначе - снетрансферабельными (NTU game).И.В.Кацев (СПб ЭМИ)Динамические игры20127 / 13Кооперативные игрыРассмотрим игру Γ и коалицию S.

Множество ее стратегий является множество∏XS = i∈S Xi .И.В.Кацев (СПб ЭМИ)Динамические игры20128 / 13Кооперативные игрыРассмотрим игру Γ и коалицию S. Множество ее стратегий является множество∏XS = i∈S Xi .Рассмотрим антагонистическую игру ΓS :ΓS = ⟨XS , XN\S ,∑Ki (x)⟩.i∈ SВ игре ΓS имеются два игрока : коалиция S и ее дополнение N \ S. Функциявыигрыша игрока S определяется как сумма выигрышей всех ее членов.И.В.Кацев (СПб ЭМИ)Динамические игры20128 / 13Кооперативные игрыРассмотрим игру Γ и коалицию S. Множество ее стратегий является множество∏XS = i∈S Xi .Рассмотрим антагонистическую игру ΓS :ΓS = ⟨XS , XN\S ,∑Ki (x)⟩.i∈ SВ игре ΓS имеются два игрока : коалиция S и ее дополнение N \ S.

Функциявыигрыша игрока S определяется как сумма выигрышей всех ее членов.Рассмотрим осторожную стратегию игрока S:vΓ (S)И.В.Кацев (СПб ЭМИ)= maxminxS ∈XS xN\S ∈XN\S∑Ki (xS , xN\S ).i∈SДинамические игры20128 / 13Кооперативные игрыРассмотрим игру Γ и коалицию S. Множество ее стратегий является множество∏XS = i∈S Xi .Рассмотрим антагонистическую игру ΓS :ΓS = ⟨XS , XN\S ,∑Ki (x)⟩.i∈ SВ игре ΓS имеются два игрока : коалиция S и ее дополнение N \ S.

Функциявыигрыша игрока S определяется как сумма выигрышей всех ее членов.Рассмотрим осторожную стратегию игрока S:vΓ (S)= maxminxS ∈XS xN\S ∈XN\S∑Ki (xS , xN\S ).i∈SВектор значений {vΓ (S)}S⊂N называется характеристической функцией игры Γ.И.В.Кацев (СПб ЭМИ)Динамические игры20128 / 13Свойства характеристической функции1. vΓ (∅)= 0 по определению;2. Супераддитивность: vΓ (K ∪ L)≧ vΓ (K) + vΓ (L);∑3. Для игр с постоянной суммой ( i∈N Ki (x) = c ∀x ∈ X)vΓ (S) + vΓ (N \ S) = vΓ (N) = c для всех S ⊂ N;4. Инвариантность относительно аффинных преобразований: если игры Γ иΓ′ отличаются друг от друга только функциями выигрышей:K′i (x)= a · Ki (x) + bi , a > 0,∑то для любой коалиции S v′Γ (S) = avΓ (S) +i∈S bi ;5.

Для любого изоморфизма π: Γ → Γ′vΓ′ (π S)И.В.Кацев (СПб ЭМИ)= vΓ (S).Динамические игры20129 / 13Кооперативные игрыКооперативной игрой с трансферабельными полезностями или игрой в формехарактеристической функции называется пара (N, v), где N− множество игроков,v : 2N → R− характеристическая функция.Мы не рассматриваем бескоалиционную игру, на основе которой построенаданная кооперативная игра!И.В.Кацев (СПб ЭМИ)Динамические игры201210 / 13Пример: голосованияЕсть n игроков с весами (количества голосов) a1 , a2 , ..., an > 0.

Законпринимается, если за него отдано как минимум A > 0 голосов.Определяем кооперативную игру (N, v) следующим образом:= {1, 2, ..., n},{∑1 еслиai ≥ ANv(S)=i∈ S0 иначеЭто взвешенная мажоритарная игра.И.В.Кацев (СПб ЭМИ)Динамические игры201211 / 13Пример: простая играИгра (N, v) называется простой, если1. Для любого S ⊂ N v(S) ∈ {0, 1}.2. v(N) = 1.3. Если v(S) = 1 и S ⊂ T, то v(T) = 1.Верно ли, что любая простая игра является взвешенно мажоритарной?И.В.Кацев (СПб ЭМИ)Динамические игры201212 / 13Пример: игра с вето-игрокомЕсть n игроков с весами a1 , a2 , ..., an> 0.

Рассмотрим игру (N, v), где= {1, 2, ..., n},{ ∑Nv(S)=i∈ S0И.В.Кацев (СПб ЭМИ)aiесли1∈AиначеДинамические игры201213 / 13Пример: игра с иерархической структуройЕсть n игроков с весами a1 , a2 , ..., an > 0. Игроки являются вершинамиориентированного дерева с одной вершиной без предшественников.Рассмотрим игру (N, v), гдеN = {1, 2, ..., n},v(S)=∑aii∈σ(S)где σ(S) - максимальное допустимое подмножество S.И.В.Кацев (СПб ЭМИ)Динамические игры201214 / 13.