Ядро (теория игр)

В теории кооперативных игр ядром , является набор распределений возможных или вменений при котором ни одна коалиция агентов не может получить выгоду от отделения от большой коалиции. Можно представить себе ядро, соответствующее ситуациям, в которых возможно поддерживать сотрудничество между всеми агентами. Говорят, что коалиция улучшает или блокирует возможное распределение, если члены этой коалиции могут генерировать между собой большую ценность, чем им было выделено при первоначальном распределении. Таким образом, у этой коалиции нет стимула оставаться в большой коалиции.

Говорят, что распределение лежит в основе игры, если нет коалиции, которая могла бы улучшить его. Тогда ядром является набор всех возможных распределений.

Происхождение

Идея ядра уже появилась в трудах Эджворта (1881) , в то время называемая контрактной кривой . Хотя фон Нейман и Моргенштерн считали эту концепцию интересной, они работали только с играми с нулевой суммой , где ядро ​​всегда пусто . Современное определение ядра принадлежит Гиллису .

Определение

Рассмотрим переносимую служебную кооперативную игру. $(N,v)$ где $N$ обозначает множество игроков и $v$ – характеристическая функция . Вменение ​ $x\in \mathbb {R} ^{N}$ преобладает обвинение другое $y$ если существует коалиция $C$, такой, что каждый игрок в $C$ слабо-предпочитает $y$ ( $x_{i}\leq y_{i}$ для всех $i\in C$) и существует $i\in C$ который строго предпочитает $y$ ( $x_{i}<y_{i}$), и $C$ может обеспечить соблюдение $y$ угрожая выйти из большой коалиции для формирования $C$ ( $\sum _{i\in C}y_{i}\leq v(C)$). Ядро – это набор вменений, над которыми не доминируют никакие другие вменения.

Слабое ядро

Вменение $x\in \mathbb {R} ^{N}$ другое сильно доминирует обвинение $y$ если существует коалиция $C$, такой, что каждый игрок в $C$ строго предпочитает $y$ ( $x_{i}<y_{i}$ для всех $i\in C$). Слабое ядро ​​— это набор вменений, над которыми не наблюдается сильного доминирования.

Свойства

• Другое определение, эквивалентное приведенному выше, гласит, что ядро ​​представляет собой набор распределений выигрышей. $x\in \mathbb {R} ^{N}$ удовлетворяющий

1. Эффективность: $\sum _{i\in N}x_{i}=v(N)$,
2. Коалиционная рациональность: $\sum _{i\in C}x_{i}\geq v(C)$ для всех подмножеств (коалиций) $C\subseteq N$.

• Ядро всегда четко определено, но может быть пустым .
• Ядро — это множество, удовлетворяющее системе слабых линейных неравенств. Следовательно, ядро ​​замкнуто и выпукло .
• Теорема Бондаревой – Шепли : ядро ​​игры непусто тогда и только тогда, когда игра «сбалансирована».
• Каждое вальрасовское равновесие обладает основным свойством, но не наоборот . Гипотеза Эджворта утверждает, что при дополнительных предположениях предел ядра, когда число потребителей стремится к бесконечности, представляет собой набор вальрасовских равновесий.
• Пусть есть n игроков, где n нечетно. Игра, в которой предлагается разделить одну единицу товара между коалицией, состоящей не менее ( n +1)/2 членов, имеет пустое ядро. То есть никакой устойчивой коалиции не существует.

Пример

Пример 1: Майнеры

Рассмотрим группу из n горняков, обнаруживших большие слитки золота. Если два старателя могут унести один кусок золота, то выигрыш коалиции S равен

$v(S)={\begin{cases}|S|/2,&{\text{if }}|S|{\text{ is even}};\\(|S|-1)/2,&{\text{if }}|S|{\text{ is odd}}.\end{cases}}$

Если майнеров больше двух и их четное количество, то ядро ​​состоит из одной выплаты, где каждый майнер получает 1/2. Если майнеров нечётное количество, то ядро ​​пустое.

Пример 2: Перчатки

Мистер А и мистер Б вяжут перчатки. Перчатки имеют один размер, и две перчатки составляют пару, которую продают за 5 евро. Каждый из них сделал по три перчатки. Как поделить доходы от продажи? Задачу можно описать с помощью игры в форме характеристической функции со следующей характеристической функцией: У каждого человека есть три перчатки, то есть одна пара с рыночной стоимостью 5 евро. Вместе у них есть 6 перчаток или 3 пары, рыночная стоимость которых составляет 15 евро. Поскольку одноэлементные коалиции (состоящие из одного человека) являются единственными нетривиальными коалициями в игре, все возможные распределения этой суммы принадлежат ядру, при условии, что оба игрока получают как минимум 5 евро, сумму, которую они могут получить самостоятельно. Например, (7.5, 7.5) принадлежит ядру, но то же самое относится и к (5, 10) или (9, 6).

Пример 3: Обувь

На данный момент не обращайте внимания на размеры обуви: пара состоит из левой и правой обуви, которую затем можно продать за 10 евро. Рассмотрим игру с 2001 игроком: у 1000 из них 1 левый ботинок, у 1001 — 1 правый ботинок. Суть этой игры несколько удивительна: она состоит из одного вменения, которое дает 10 тем, у кого (недостаточный) левый ботинок, и 0 тем, у кого (избыточный) правый ботинок. Никакая коалиция не может блокировать этот результат, потому что ни один владелец левой обуви не примет меньше 10, и любое вменение, которое приносит положительную сумму любому владельцу правой обуви, должно в общей сложности выплатить менее 10 000 другим игрокам, которые могут получить 10 000 самостоятельно. . Итак, в ядре есть только одно вменение.

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

Ядро

Вальрасовское равновесие экономики обмена в модели общего равновесия будет лежать в основе игры сотрудничества между агентами. Графически в экономике с двумя агентами (см. Блок Эджворта) ядром является набор точек на кривой контракта (множество оптимальных по Парето распределений), лежащих между каждой из кривых безразличия агентов, определенных при начальных запасах.

Ядро

Когда альтернативами являются распределения (список потребительских наборов), естественно предположить, что любые непустые подмножества индивидов могут блокировать данное распределение.Однако, когда альтернативы являются общедоступными (например, объем определенного общественного блага), более уместно предположить, что только достаточно большие коалиции могут заблокировать данную альтернативу. Сбор таких больших («выигрышных») коалиций называется простой игрой .Суть простой игры в отношении профиля предпочтений основана на идее, что только победившие коалиции могут отвергнуть альтернативу. $x$ в пользу другой альтернативы $y$. Необходимое и достаточное условие непустоты ядра для всех профилей предпочтений дается через число Накамуры для простой игры.

См. также

• Кооперативные переговоры
• Экономика благосостояния
• Парето-эффективность
• Теорема Кнастера – Куратовского – Мазуркевича – Шепли - способствует доказательству непустоты ядра.

Ссылки

Цитируемые работы

• Эджворт, Фрэнсис Исидро (1881). Математическая экстрасенсорика: очерк применения математики к моральным наукам . Лондон: К. К. Пол.

Дальнейшее чтение

• Итииси, Тацуро (1983). «Кооперативное поведение и стабильность» . Теория игр для экономического анализа . Нью-Йорк: Академическая пресса. стр. 77–117. ISBN  0-12-370180-5 .
• Осборн, Мартин Дж.; Рубинштейн, Ариэль (1994). Курс теории игр . Массачусетский технологический институт Пресс.
• Пелег, Б (1992). «Аксиоматизации ядра». В Ауманне, Роберт Дж .; Харт, Серджиу (ред.). Справочник по теории игр с экономическими приложениями . Том. Я. Амстердам: Эльзевир. стр. 397–412. ISBN  978-0-444-88098-7 .
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Нью-Йорк: Издательство Кембриджского университета . ISBN  978-0-521-89943-7 .
• Тельсер, Лестер Г. (1994). «Полезность базовой теории в экономике» . Журнал экономических перспектив . 8 (2): 151–164. дои : 10.1257/jep.8.2.151 .