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

Термины и обозначенияКооперативная игра: пара (N, v), где N - конечное множество игроков иv : 2N → R - характеристическая функция, определенная для каждой коалицииS ⊂ N, причем величина v(S) показывает, какой выигрыш могут обеспечить себеигроки из S в результате кооперации.И.В.Кацев (СПб ЭМИ)Кооперативные игры20121 / 14Решения кооперативных игр и их свойстваКооперативная игра = проблема.Решением называется функция σ , сопоставляющая каждой игре (N, v)множество ”справедливых” распределений прибыли σ(N, v) ∈ RN .Решение σ называется одноточечным, если для любой игры (N, v) выполнено|σ(N, v)| = 1.И.В.Кацев (СПб ЭМИ)Кооперативные игры20122 / 14Решения кооперативных игр и их свойстваПусть G - класс игр.

Тогда решение σ удовлетворяет какому-либо свойству изсписка ниже на классе G , когда это свойство выполняется для всех игр(N, v) ∈ G . Решение σ на классе G является– непустым, если σ(N, v)И.В.Кацев (СПб ЭМИ)̸= ∅;Кооперативные игры20123 / 14Решения кооперативных игр и их свойстваПусть G - класс игр. Тогда решение σ удовлетворяет какому-либо свойству изсписка ниже на классе G , когда это свойство выполняется для всех игр(N, v) ∈ G . Решение σ на классе G является– непустым, если σ(N, v)– эффективным, еслиИ.В.Кацев (СПб ЭМИ)∑̸= ∅;i∈Nxi (N, v)= v(N) для каждого x ∈ σ(N, v);Кооперативные игры20123 / 14Решения кооперативных игр и их свойстваПусть G - класс игр. Тогда решение σ удовлетворяет какому-либо свойству изсписка ниже на классе G , когда это свойство выполняется для всех игр(N, v) ∈ G .

Решение σ на классе G является– непустым, если σ(N, v)– эффективным, если∑̸= ∅;i∈Nxi (N, v)– анонимным, если σπ(i) (π N, π v)инъекции π : N → N .И.В.Кацев (СПб ЭМИ)= v(N) для каждого x ∈ σ(N, v);= σi (N, v) для всех i ∈ N и произвольнойКооперативные игры20123 / 14Решения кооперативных игр и их свойстваПусть G - класс игр. Тогда решение σ удовлетворяет какому-либо свойству изсписка ниже на классе G , когда это свойство выполняется для всех игр(N, v) ∈ G . Решение σ на классе G является– непустым, если σ(N, v)– эффективным, если∑̸= ∅;i∈Nxi (N, v)– анонимным, если σπ(i) (π N, π v)инъекции π : N → N .= v(N) для каждого x ∈ σ(N, v);= σi (N, v) для всех i ∈ N и произвольной– симметричным, если xi (N, v) = xj (N, v) для любого xсимметричных в (N, v) игроков i и j;И.В.Кацев (СПб ЭМИ)Кооперативные игры∈ σ(N, v) и20123 / 14Решения кооперативных игр и их свойстваПусть G - класс игр.

Тогда решение σ удовлетворяет какому-либо свойству изсписка ниже на классе G , когда это свойство выполняется для всех игр(N, v) ∈ G . Решение σ на классе G является– непустым, если σ(N, v)– эффективным, если∑̸= ∅;i∈Nxi (N, v)– анонимным, если σπ(i) (π N, π v)инъекции π : N → N .= v(N) для каждого x ∈ σ(N, v);= σi (N, v) для всех i ∈ N и произвольной– симметричным, если xi (N, v) = xj (N, v) для любого xсимметричных в (N, v) игроков i и j;∈ σ(N, v) и– стандартным, если для игры любой игры двух лиц ({i, j}, v)σi = v({i}) +σj = v({j}) +И.В.Кацев (СПб ЭМИ)v({i, j}) − v({i}) − v({j})2v({i, j}) − v({i}) − v({j})Кооперативные игры2,.20123 / 14Решения кооперативных игр и их свойстваРешение σ на классе G является– ковариантным, если оно ковариантно относительно стратегическихпреобразований:σ(N, αv + β) = ασ(N, v) + βдля всех α> 0 и β ∈ RN ;– непрерывным, если из того, что xn ∈ σ(N, vn ) и xn → x при n → ∞ следует,что x ∈ σ(N, v), где (N, vn )∞n=1 - последовательность игр в G , vn → v и(N, v) ∈ G ;– обладает свойством нулевого игрока, если xi- нулевой игрок в (N, v).= 0 для всех x ∈ σ(N, v), где iОдноточечное решение σ на G называется– аддитивным, если σi (N, v + w) = σi (N, v) + σi (N, w) для любых двух такихигр (N, v), (N, w) ∈ G , что (N, v + w) ∈ G .И.В.Кацев (СПб ЭМИ)Кооперативные игры20124 / 14Свойства согласованностиСогласованность решения σ означает, что если выигрыши игроков определенысогласно σ , а зачем часть игроков покинула игру с этими выигрышами, то дляоставшихся распределение согласно σ не изменится.И.В.Кацев (СПб ЭМИ)Кооперативные игры20125 / 14C-ядроМножество эффективных векторов выигрышей:X(N, v)= { x ∈ RN :∑xi= v(N)}.i∈N.Определение.С-ядро C сопоставляет каждой игре (N, v) следующее множество вектороввыигрышей (N, v):C(N, v)= {x ∈ X(N, v) : ∀S ⊂ N∑xi≥ v(S)}.i∈ S.С-ядро может быть пустым.И.В.Кацев (СПб ЭМИ)Кооперативные игры20126 / 14Выпуклые игрыИгра (N, v) является выпуклой, если для любых коалиций S, Tv(S ∩ T) + v(S ∪ T)⊂N≥ v(S) + v(T).В выпуклой игре C-ядро непусто.И.В.Кацев (СПб ЭМИ)Кооперативные игры20127 / 14Выпуклые игры.Теорема (Shapley, 1971).Если игра (N, v) выпуклая, то все векторы маргинальных вкладов лежат вС-ядре..И.В.Кацев (СПб ЭМИ)Кооперативные игры20128 / 14Выпуклые игры.Теорема (Shapley, 1971).Если игра (N, v) выпуклая, то все векторы маргинальных вкладов лежат вС-ядре...Теорема (Ichiishi, 1981).Если в игре (N, v) все векторы маргинальных вкладов лежат в С-ядре, то игравыпукла..И.В.Кацев (СПб ЭМИ)Кооперативные игры20128 / 14СбалансированностьНабор коалиций B ⊂ 2N называется сбалансированным, если существуют такиеположительные числа {λS }S∈B , что для любого элемента i ∈ N выполнено∑λS = 1.i∈S∈BИ.В.Кацев (СПб ЭМИ)Кооперативные игры20129 / 14СбалансированностьНабор коалиций B ⊂ 2N называется сбалансированным, если существуют такиеположительные числа {λS }S∈B , что для любого элемента i ∈ N выполнено∑λS = 1.i∈S∈B.Теорема (Бондарева, 1963, Шепли, 1967).Для того, чтобы С-ядро в игре (N, v) было непусто, необходимо идостаточно, чтобы для любого минимального сбалансированного набора Bвыполнялось неравенство:∑λS v(S) ≤ v(N).S∈B.И.В.Кацев (СПб ЭМИ)Кооперативные игры20129 / 14Значение Шепли.Определение.Значение Шепли Sh сопоставляет каждой игре (N, v) следующий векторвыигрышей Sh(N, v):Shi (N, v).∑={S⊆N,i∈S}И.В.Кацев (СПб ЭМИ)(|N| − |S|)!(|S| − 1)!(v(S) − v(S \ {i})) , i ∈ N.|N|!Кооперативные игры201210 / 14Значение Шепли: аксиоматизации.Теорема (Shapley, 1953).Значение Шепли является единственным одноточечным решением,обладающим свойствами аддитивности, симметричности, эффективности и.свойством ”болвана”.И.В.Кацев (СПб ЭМИ)Кооперативные игры201211 / 14Значение Шепли: аксиоматизации.Теорема (Shapley, 1953).Значение Шепли является единственным одноточечным решением,обладающим свойствами аддитивности, симметричности, эффективности и.свойством ”болвана”..Теорема (Keane, 1969).Для любой игры (N, v),Sh(N, v)= arg min.И.В.Кацев (СПб ЭМИ)x∈X(N,v)∑(|S| − 1)!(|N| − |S| − 1)! (v(S) − x(S))2 .S⊂NКооперативные игры201211 / 14Значение Шепли: аксиоматизации.Теорема (Hart, Mas-Collel, 1989).Существует единственное такое эффективное одноточечное решение σ ,что найдется такая функция P : G → R, что для любой игры (N, v) ∈ Gσi (N, v) = P(N, v) − P(N \ {i}, v) для всех i ∈ N.Этозначение Шепли.И.В.Кацев (СПб ЭМИ)Кооперативные игры201212 / 14Значение Шепли: аксиоматизацииХарт и Мас-Коллел описали значение Шепли через согласованность:Для игры (N, v) и коалиции S ⊂ N редуцированная игра (S, vSσ ) (дляодноточечного решения σ задается следующим образом):vSσ (T)= v(T ∪ N \ S) −∑σi (T ∪ N \ S, v).i∈N\S.Теорема (Hart, Mas-Collel, 1989).Значение Шепли является единственным одноточечным значением,удовлетворяющимстандартности и согласованности..И.В.Кацев (СПб ЭМИ)Кооперативные игры201213 / 14Свойство сбалансированных вкладовБудем говорить, что решение σ обладает свойством сбалансированных вкладов,если для любой игры (N, v) и для любой пары игроков i, j ∈ N выполнено:σi (N, v) − σi (N \ {j}) = σj (N, v) − σj (N \ {i}).Теорема (Майерсон,1977).Существует только одно эффективное решение, обладающее свойством.сбалансированных вкладов - это значение Шепли.И.В.Кацев (СПб ЭМИ)Кооперативные игры201214 / 14.