«Prenucleolus Илья Кацев1 1 Яндекс, НИУ ВШЭ И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 1 / 25 В предыдущих сериях С-ядро - многозначное решение Значение Шепли - одноточечное решение, ...»

Prenucleolus

Илья Кацев1

1 Яндекс, НИУ ВШЭ

И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 1 / 25

В предыдущих сериях

С-ядро - многозначное решение

Значение Шепли - одноточечное решение, обладает многочисленными

хорошими свойствами.

Однако, значение Шепли не всегда лежит в С-ядре

И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 2 / 25

Эксцесс и вектор эксцессов

X(N, v).

Рассматривается игра (N, v) и вектор выигрышей x

И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 3 / 25 Эксцесс и вектор эксцессов X(N, v).

Рассматривается игра (N, v) и вектор выигрышей x N называется величина Эксцессом коалиции S = v(S) x(S) = v(S) xi.

e(S, x, v) iS И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 3 / 25 Эксцесс и вектор эксцессов X(N, v).

Рассматривается игра (N, v) и вектор выигрышей x N называется величина Эксцессом коалиции S = v(S) x(S) = v(S) xi.

e(S, x, v) iS Эксцесс - мера неудовлетворенности коалиции.

И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 3 / 25 Эксцесс и вектор эксцессов X(N, v).

Рассматривается игра (N, v) и вектор выигрышей x N называется величина Эксцессом коалиции S = v(S) x(S) = v(S) xi.

e(S, x, v) iS Эксцесс - мера неудовлетворенности коалиции.

Вектор эксцессов x (N, v) состоит из эксцессов всех коалиций N, упорядоченных по убыванию.

И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 3 / 25 Пред-n-ядро (prenucleolus) Пусть (N, v) - кооперативная игра.

Тогда пред-n-ядром данной игры называется такое множество PN(N, v) X(N, v), что каждый его вектор лексикографически минимизирует вектор эксцессов:

PN(N, v) x lex y y

Пусть (N, v) - кооперативная игра.

Тогда n-ядром данной игры называется такое множество N(N, v) I(N, v), что каждый его вектор лексикографически минимизирует вектор эксцессов:

Теорема Для любой игры (N, v) выполнено |PN(N, v)| = 1.

И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 6 / 25 Существование и единственность Теорема Для любой игры (N, v) выполнено |PN(N, v)| = 1.

Теорема (Колберг, 1971) Рассмотрим игру (N, v) и вектор выигрышей x X(N, v). Тогда x = PN(N, v) в том и только в том случае, когда набор B является пустым или сбалансированным для каждого.

Согласованность решения означает, что если выигрыши игроков определены согласно, а зачем часть игроков покинула игру с этими выигрышами, то для оставшихся распределение согласно не изменится.

Теорема Для бесконечного универсального множества игроков пред-n-ядро является единственным одноточечным решением, которое удовлетворяет согласованности (по Девису-Машлеру), ковариантности и анонимности.

Теорема (Hart, Mas-Collel, 1989) Значение Шепли является единственным одноточечным значением, удовлетворяющим стандартности и согласованности (по Харту-Мас-Коллелу).

Определение Одноточечное решение коалиционно монотонно, если для любых двух игр (N, v), (N, w), для которых существует такая коалиция S N, что

w(S) v(S) и v(T) = w(T), для всех T = S выполнено:

Определение Одноточечное решение является агрегированно монотонным, если для любых таких двух игр (N, v), (N, w), что w(N) v(N) и v(T) = w(T) для всех

T = N, выполнено:

i (N, w) i (N, v), i N.

Пред-n-ядро не монотонно.

И.В.Кацев (Яндекс, НИУ ВШЭ) Prenucleolus 2017 15 / 25 Пред-n-ядро и монотонность Пред-n-ядро не монотонно.

Теорема (Megiddo, 1974) Пред-n-ядро не удовлетворяет агрегированной монотонности на классе игр GN, если |N| 9.

Пред-n-ядро не монотонно.

Теорема (Megiddo, 1974) Пред-n-ядро не удовлетворяет агрегированной монотонности на классе игр GN, если |N| 9.

Теорема (Hokari, 2000) Пред-n-ядро не удовлетворяет агрегированной монотонности на классе выпуклых игр.

Пред-n-ядро не монотонно.

Теорема (Megiddo, 1974) Пред-n-ядро не удовлетворяет агрегированной монотонности на классе игр GN, если |N| 9.

Теорема (Hokari, 2000) Пред-n-ядро не удовлетворяет агрегированной монотонности на классе выпуклых игр.

Теорема (Arin, Feltkamp, 2005) Пред-n-ядро не удовлетворяет агрегированной монотонности на классе вето-сбалансированных игр.

Теорема (Arin, Katsev, 2014-2016) Cуществует решениe (SD-prenucleolus), которое является стабильным на классе всех игр и коалиционно монотонным на классах выпуклых игр и вето-монотонных игр.

35. Докажите, что пред-n-ядро удовлетворяет свойству desirability, то есть:

Пусть (N, v) - кооперативная игра, i, j N, причем для любого S N : i, j S выполнено v(S {i}) v(S {j}). Тогда PNi (N, v) PNj (N, v).

28. Пусть N - множество из 5 элементов. Существует ли минимальный сбалансированный набор B 2N, в котором а. Больше 5 элементов б. Больше 6 элементов

29. Имеется комитет, состоящий из 4 человек: A,B,C,D, A является председателем. Комитет принимает решение по правилу большинства, но в случае ничьей 2–2 принимается решение, за которое голосует председатель.

Перечислить выигрывающие коалиции и найти значение Шепли в соответствующей простой игре.

32. Докажите теорему Янга:

Теорема (Янг, 1985) Существует только одно эффективное, симметричное и строго монотонное решение решение - это значение Шепли.