Лекция 8 (545633)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Термины и обозначенияКооперативная игра: пара (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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций