«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) Существует только одно эффективное, симметричное и строго монотонное решение решение - это значение Шепли.