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

Д/з28. Докажите теорему Бондаревой-Шепли:Для того, чтобы С-ядро в игре (N, v) было непусто, необходимо и достаточно,чтобы для любого минимального сбалансированного набора B выполнялосьнеравенство:∑λS v(S) ≤ v(N).S∈BИ.В.Кацев (СПб ЭМИ)Кооперативные игры20121 / 16Д/з29. Пусть N - множество из 5 элементов. Существует ли минимальныйсбалансированный набор B ⊂ 2N , в которома.

Больше 5 элементовб. Больше 6 элементовИ.В.Кацев (СПб ЭМИ)Кооперативные игры20122 / 16В предыдущих серияхС-ядро - многозначное решениеЗначение Шепли - одноточечное решение, обладает многочисленнымихорошими свойствами.Однако, значение Шепли не всегда лежит в С-ядреИ.В.Кацев (СПб ЭМИ)Кооперативные игры20123 / 16Эксцесс и вектор эксцессовРассматривается игра (N, v) и вектор выигрышей xИ.В.Кацев (СПб ЭМИ)Кооперативные игры∈ X(N, v).20124 / 16Эксцесс и вектор эксцессовРассматривается игра (N, v) и вектор выигрышей xЭксцессом коалиции S∈ X(N, v).⊂ N называется величинаe(S, x, v)= v(S) − x(S) = v(S) −∑xi .i∈SИ.В.Кацев (СПб ЭМИ)Кооперативные игры20124 / 16Эксцесс и вектор эксцессовРассматривается игра (N, v) и вектор выигрышей xЭксцессом коалиции S∈ X(N, v).⊂ N называется величинаe(S, x, v)= v(S) − x(S) = v(S) −∑xi .i∈SЭксцесс - мера неудовлетворенности коалиции.И.В.Кацев (СПб ЭМИ)Кооперативные игры20124 / 16Эксцесс и вектор эксцессовРассматривается игра (N, v) и вектор выигрышей xЭксцессом коалиции S∈ X(N, v).⊂ N называется величинаe(S, x, v)= v(S) − x(S) = v(S) −∑xi .i∈SЭксцесс - мера неудовлетворенности коалиции.Вектор эксцессов θx (N, v) состоит из эксцессов всех коалиций N, упорядоченныхпо убыванию.И.В.Кацев (СПб ЭМИ)Кооперативные игры20124 / 16Пред-n-ядро (prenucleolus)Пусть (N, v) - кооперативная игра.

Тогда пред-n-ядром данной игры называетсятакое множество PN(N, v) ⊂ X(N, v), что каждый его вектор лексикографическиминимизирует вектор эксцессов:xИ.В.Кацев (СПб ЭМИ)∈ PN(N, v) ⇔ θx ≤lex θy ∀y ∈ X(N, v).Кооперативные игры20125 / 16n-ядро (nucleolus)Множество индивидуально рациональных векторов:I(N, v)= {x ∈ X(N, v) : xi ≥ v({i}) ∀i ∈ N}.Пусть (N, v) - кооперативная игра. Тогда n-ядром данной игры называется такоемножество N(N, v) ⊂ I(N, v), что каждый его вектор лексикографическиминимизирует вектор эксцессов:xИ.В.Кацев (СПб ЭМИ)∈ N(N, v) ⇔ θx ≤lex θy ∀y ∈ I(N, v).Кооперативные игры20126 / 16Существование и единственность.Теорема.Длялюбой игры (N, v) выполнено |PN(N, v)|.И.В.Кацев (СПб ЭМИ)= 1.Кооперативные игры20127 / 16Существование и единственность.Теорема.Длялюбой игры (N, v) выполнено |PN(N, v)|.= 1..Теорема (Шмайдлер, 1967)..Для любой такой игры (N, v), что I(N, v)И.В.Кацев (СПб ЭМИ)̸= ∅ выполнено |N(N, v)| = 1.Кооперативные игры20127 / 16Теорема КолбергаДля игры (N, v) и вектора x обозначимBα = {S ⊊ N : e(S, x) ≥ α}.Теорема (Колберг, 1971).Рассмотрим игру (N, v) и вектор выигрышей x ∈ X(N, v).

Тогда x = PN(N, v) втом и только в том случае, когда набор Bα является пустым или.сбалансированным для каждого α.И.В.Кацев (СПб ЭМИ)Кооперативные игры20128 / 16Простые свойстваn-ядро - анонимно, симметрично, ковариантно, обладает свойствомболвана, непрерывно и стандартно для двух лицЕсли С-ядро непусто, то PN(N, v)∈ C(N, v)Если С-ядро непусто, то PN(N, v)= N(N, v)И.В.Кацев (СПб ЭМИ)Кооперативные игры20129 / 16Свойства согласованностиСогласованность решения σ означает, что если выигрыши игроков определенысогласно σ , а зачем часть игроков покинула игру с этими выигрышами, то дляоставшихся распределение согласно σ не изменится.И.В.Кацев (СПб ЭМИ)Кооперативные игры201210 / 16Согласованность по Девису-МашлеруСчитаем, что уходящие игроки оставляют свои стратегические возможностидругим.

Пусть (N, v) - произвольная игра, S ⊂ N – коалиция, x ∈ X(N, v).Редуцированной игрой в определении Дэвиса–Машлера игры (N, v) намножество игроков относительно вектора выигрышей называется игра (S, vxS ) гдеvxS (T)=v(N) − x(N \ S), max v(T ∪ Q) − x(Q),Q⊂N\SИ.В.Кацев (СПб ЭМИ)Кооперативные игры= S,если T ⫋ S.если T201211 / 16Согласованность по Девису-МашлеруСчитаем, что уходящие игроки оставляют свои стратегические возможностидругим.

Пусть (N, v) - произвольная игра, S ⊂ N – коалиция, x ∈ X(N, v).Редуцированной игрой в определении Дэвиса–Машлера игры (N, v) намножество игроков относительно вектора выигрышей называется игра (S, vxS ) гдеvxS (T)=v(N) − x(N \ S), max v(T ∪ Q) − x(Q),Q⊂N\S= S,если T ⫋ S.если TРешение σ согласовано в определении Дэвиса–Машлера, если для любой игры(N, v) и коалиции S ⊂ N из x ∈ σ(N, v) следует, что xS ∈ σ(S, vxS ).И.В.Кацев (СПб ЭМИ)Кооперативные игры201211 / 16Теорема Соболева.Теорема.Для бесконечного универсального множества игроков пред-n-ядро являетсяединственным одноточечным решением, которое удовлетворяетсогласованности(по Девису-Машлеру), ковариантности и анонимности..И.В.Кацев (СПб ЭМИ)Кооперативные игры201212 / 16Коалиционная монотонность.Определение.Одноточечное решение Φ коалиционно монотонно, если для любых двух игр(N, v), (N, w), для которых существует такая коалиция S ⊂ N, чтоw(S) > v(S) и v(T) = w(T), для всех T ̸= S выполнено:Φi (N, w) ≥ Φi (N, v), i ∈ S..И.В.Кацев (СПб ЭМИ)Кооперативные игры201213 / 16Aggregate monotonicity.Определение.Одноточечное решение Φ является агрегированно монотонным, если длялюбых таких двух игр (N, v), (N, w), что w(N) > v(N) и v(T) = w(T) для всехT ̸= N, выполнено:Φi (N, w) ≥ Φi (N, v), i ∈ N..И.В.Кацев (СПб ЭМИ)Кооперативные игры201214 / 16Пред-n-ядро и монотонностьПред-n-ядро не монотонно.И.В.Кацев (СПб ЭМИ)Кооперативные игры201215 / 16Пред-n-ядро и монотонностьПред-n-ядро не монотонно..Теорема (Megiddo, 1974).Пред-n-ядро не удовлетворяет агрегированной монотонности на классе игрG.

N , если |N| ≥ 9.И.В.Кацев (СПб ЭМИ)Кооперативные игры201215 / 16Пред-n-ядро и монотонностьПред-n-ядро не монотонно..Теорема (Megiddo, 1974).Пред-n-ядро не удовлетворяет агрегированной монотонности на классе игрG. N , если |N| ≥ 9..Теорема (Hokari, 2000).Пред-n-ядро не удовлетворяет агрегированной монотонности на классевыпуклыхигр..И.В.Кацев (СПб ЭМИ)Кооперативные игры201215 / 16Пред-n-ядро и монотонностьПред-n-ядро не монотонно..Теорема (Megiddo, 1974).Пред-n-ядро не удовлетворяет агрегированной монотонности на классе игрG. N , если |N| ≥ 9..Теорема (Hokari, 2000).Пред-n-ядро не удовлетворяет агрегированной монотонности на классевыпуклыхигр...Теорема (Arin, Feltkamp, 2005).Пред-n-ядро не удовлетворяет агрегированной монотонности на классевето-сбалансированныхигр..И.В.Кацев (СПб ЭМИ)Кооперативные игры201215 / 16Теорема Янга.Теорема (Young, 1985).Не существует решения, которое является и стабильным и коалиционномонотоннымна классе игр GN , где |N| ≥ 5..И.В.Кацев (СПб ЭМИ)Кооперативные игры201216 / 16.