WWW.BOOK.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные ресурсы
 
s

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


Похожие работы:

«Утверждаю ООО НПФ "Сиббиотест" Директор ООО НПФ НСО, наукоград Кольцово, ул.Технопарковая 1, оф.225. "Сиббиотест" Тел. 8(383)336-50-91, E-mail: sibbiotest@ngs.ru _ Шведкин Е.И. "_16_"мая_2013 г. Набор диагно...»

«КАТАЛОГ прОдуКции для автоматизированных систем опробования пульповых продуктов • пробоотборники • пробосократители • Оборудование пробоподготовки КАТАЛОГ продукции для автоматизированных систем опробования пульповых продуктов (пробоотборники, пробосократители, оборудование пробоподготовки)...»

«Приложение к Решению Совета депутатов Муниципального образования Переволоцкий район Оренбургской области от 17.06.2015г. № 387 ВНЕСЕНИЕ ИЗМЕНЕНИЙ В ГЕНЕРАЛЬНЫЙ ПЛАН МУНИЦИПАЛЬНОГО ОБРАЗОВАНИЯ "АБРАМОВСКИЙ СЕЛЬСОВЕТ" ПЕРЕВОЛОЦКОГО РАЙОНА ОРЕНБУРГСКОЙ ОБЛАСТИ ТОМ 2 МА...»

«2 Приложение 1 УТВЕРЖДАЮ Заместитель Министра образования Омской области _И.Б. Елецкая " " 20г. Оргкомитет областной олимпиады профессионального мастерства обучающихся профессиональных образовательных организаций по профессии "Повар" № Ф.И.О. Должность 1. Елецкая Заместитель министра образования Омской области Инна Борисовна 2. Гордиенк...»

«Выпуск 1 Список основных источников 1. Алчинов, В.М. СНГ Россия Евросоюз. Проблемы и перспективы инте­ грации / В.М. Алчинов. М. : Восток-Запад, 2008.2. Бжезинский, З. Великая шахматная доска / З. Бжезинский. М., 1998.3. Буторина, О.В. Региональная и...»

«АРХИТЕК ТУРА А Р М Я Н С К О Й Ц Е РК В И А Р Х А Н Г Е Л О В Г А В Р И И Л А И М И Х А И Л А В Ф Е О Д О С И И И ЕЕ Р Е С Т А В Р А Ц И Я ЕВГЕНИЯ ЛАПУШИНСКАЯ Д ата сооруж ения церкви Гавриила и М ихаила в Ф еодосии— 1408 г.— значится в надписи на камне, который был вмонтирован над е порталом или над калиткой в ограде:...»

«ФЕДЕРАЛЬНАЯ АНТИМОНОПОЛЬНАЯ СЛУЖБА Проблемы регулирования цен на лекарственные препараты в Российской Федерации и возможные пути их решения Н.А. Шаравская Москва, 2012 г. ПРОБЛЕМЫ РЕГУЛИРОВАНИЯ ЦЕН В период с 23.08.2010 по 28.09.2010 ФАС России приняла участие в проводимой Генеральной прокуратурой Ро...»

«Сергей Иванников Интеллигенция и русофобия Конец июня 1941 года. Некто Владимир Соколов, 1913 г.р., на тот момент — житель Орла, услышав песню призывников, уходящих на фронт: "В бой за Родину, в бой за Сталина", записывает в дневнике: "Нет, в бой за Сталина я не пойду. За Р...»

«Константин Сергеевич Бадигин На морских дорогах Андрей Мятишкин (amyatishkin@mail.ru) http://www.litres.ru/pages/biblio_book/?art=128010 Содержание Моим читателям 4 Тетрадь первая. Ледовитый океан...»










 
2017 www.book.lib-i.ru - «Бесплатная электронная библиотека - электронные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.