Лекция 7 (545630)
Текст из файла
Арбитражные схемыАрбитражной схемой называется пара (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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.