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

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

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

Происхождение [ править ]

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

Определение [ править ]

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

Ядро есть множество дележей, которые не доминировали. ^[3]

Свойства [ править ]

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

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

Ядро всегда четко определено, но может быть пустым .
Ядро - это множество, удовлетворяющее системе слабых линейных неравенств. Следовательно, ядро замкнутое и выпуклое .
Теорема Бондаревой – Шепли : ядро игры непусто тогда и только тогда, когда игра «сбалансирована». ^[4]^[5]
Каждое вальрасовское равновесие обладает основным свойством, но не наоборот . Гипотеза Эджворта утверждает, что с учетом дополнительных предположений предел ядра, когда число потребителей стремится к бесконечности, является набором вальрасовских равновесий.
Пусть есть 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, и любое вменение, которое выплачивает положительную сумму любому правому владельцу обуви, должно заплатить меньше 10000 в общей сложности другим игрокам, которые могут получить 10000 самостоятельно. . Итак, в ядре всего одно вменение.

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

Ядро теории общего равновесия [ править ]

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

Суть теории голосования [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

^ Каннай, Y. (1992). «Ядро и уравновешенность». In Aumann, Роберт Дж .; Харт, Серджиу (ред.). Справочник по теории игр с экономическими приложениями . Я . Амстердам: Эльзевир. С. 355–395. ISBN 978-0-444-88098-7.
Перейти ↑ Gillies, DB (1959). «Решения общих игр с ненулевой суммой». В Tucker, AW ; Люс, Р. Д. (ред.). Вклад в теорию игр IV . Анналы математических исследований. 40 . Принстон: Издательство Принстонского университета . С. 47–85.
^ Как отмечает Шепли, LS; Шубик, М. (1969). «На рынке игр». Журнал экономической теории . 1 (1): 9–25. DOI : 10.1016 / 0022-0531 (69) 90008-8 . благодаря вкладу г-на Э. Кольберга
↑ Бондарева, Ольга Н. (1963). «Некоторые приложения методов линейного программирования к теории кооперативных игр». Проблемы Кибернетики . 10 : 119–139.
^ Шепли, Ллойд С. (1967). «О балансных наборах и сердечниках». Ежеквартально по логистике военно-морских исследований . 14 (4): 453–460. DOI : 10.1002 / nav.3800140404 . hdl : 10338.dmlcz / 135729 .

Дальнейшее чтение [ править ]

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

[Kannai_1992-1] Каннай, Y. (1992). «Ядро и уравновешенность». In Aumann, Роберт Дж .; Харт, Серджиу (ред.). Справочник по теории игр с экономическими приложениями . Я . Амстердам: Эльзевир. С. 355–395. ISBN 978-0-444-88098-7.

[2] Перейти ↑ Gillies, DB (1959). «Решения общих игр с ненулевой суммой». В Tucker, AW ; Люс, Р. Д. (ред.). Вклад в теорию игр IV . Анналы математических исследований. 40 . Принстон: Издательство Принстонского университета . С. 47–85.

[3] Как отмечает Шепли, LS; Шубик, М. (1969). «На рынке игр». Журнал экономической теории . 1 (1): 9–25. DOI : 10.1016 / 0022-0531 (69) 90008-8 . благодаря вкладу г-на Э. Кольберга

[4] Бондарева, Ольга Н. (1963). «Некоторые приложения методов линейного программирования к теории кооперативных игр». Проблемы Кибернетики . 10 : 119–139.

[5] Шепли, Ллойд С. (1967). «О балансных наборах и сердечниках». Ежеквартально по логистике военно-морских исследований . 14 (4): 453–460. DOI : 10.1002 / nav.3800140404 . hdl : 10338.dmlcz / 135729 .

[1]

vтеТемы по теории игр
Определения	Игра с перегрузкой Кооперативная игра Решительность Эскалация обязательств Игра в расширенной форме Победа первого и второго игрока Сложность игры Язык описания игры Графическая игра Иерархия убеждений Информационный набор Игра в нормальной форме Предпочтение Последовательная игра Одновременная игра Выбор одновременного действия Решенная игра Лаконичная игра
Концепции равновесия	равновесие по Нэшу Совершенство подигры Устойчивое равновесие по Мертенсу Байесовское равновесие по Нэшу Идеальное байесовское равновесие Дрожащая рука Правильное равновесие Эпсилон-равновесие Коррелированное равновесие Последовательное равновесие Квази-совершенное равновесие Эволюционно устойчивая стратегия Доминирование риска Основной Значение Шепли Парето эффективность Равновесие Гиббса Квантовое равновесие отклика Самоподтверждающееся равновесие Сильное равновесие по Нэшу Марковское идеальное равновесие
Стратегии	Доминирующие стратегии Чистая стратегия Смешанная стратегия Аргумент кражи стратегии Око за око Мрачный спусковой крючок Сговор Обратная индукция Прямая индукция Марковская стратегия Затенение ставки
Классы игр	Симметричная игра Идеальная информация Повторная игра Сигнальная игра Скрининговая игра Дешевый разговор Игра с нулевой суммой Конструкция механизма Проблема торга Стохастическая игра Средняя игра n -пользовательская игра Большая игра Пуассона Нетранзитивная игра Глобальная игра Строго определенная игра Возможная игра
Игры	Идти Шахматы Бесконечные шахматы Шашки Крестики-нолики Дилемма заключенного Игра по обмену подарками Необязательная дилемма заключенного Дилемма путешественника Координационная игра Курица Сороконожка игра Сигнальная игра Льюиса Дилемма волонтера Долларовый аукцион Битва полов Охота на оленя Соответствующие пенни Ультиматум игра Камень ножницы Бумага Пиратская игра Диктаторская игра Игра в общественные блага Блотто игра Война на истощение Проблема с баром Эль Фарол Справедливое деление Ярмарка нарезки торта Игра Курно Тупик Дилемма закусочной Угадайте 2/3 среднего Покер куна Игра Нэша в торг Индукционные пазлы Доверительная игра Игра принцесс и монстров Проблема рандеву
Теоремы	Теорема невозможности Эрроу Теорема согласия Ауманна Народная теорема Теорема о минимаксе Теорема Нэша Теорема очищения Принцип откровения Теорема Цермело
Ключевые цифры	Альберт В. Такер Амос Тверски Антуан Огюстен Курно Ариэль Рубинштейн Клод Шеннон Даниэль Канеман Дэвид К. Левин Дэвид М. Крепс Дональд Б. Гиллис Дрю Фуденберг Эрик Маскин Гарольд В. Кун Герберт Саймон Эрве Мулен Жан Тироль Жан-Франсуа Мертенс Дженнифер Тур Чейес Джон Харсаньи Джон Мейнард Смит Джон Нэш Джон фон Нейман Кеннет Эрроу Кеннет Бинмор Леонид Гурвич Ллойд Шепли Мелвин Дрешер Меррилл М. Флуд Ольга Бондарева Оскар Моргенштерн Пол Милгром Пейтон Янг Райнхард Зельтен Роберт Аксельрод Роберт Ауманн Роберт Б. Уилсон Роджер Майерсон Сэмюэл Боулз Сюзанна Скотчмер Томас Шеллинг Уильям Викри
Разное	All-pay аукцион Альфа – бета обрезка Парадокс бертрана Ограниченная рациональность Комбинаторная теория игр Анализ конфронтации Совместное соревнование Эволюционная теория игр Преимущество первого хода в шахматах Игровая механика Глоссарий теории игр Список теоретиков игр Список игр по теории игр Безвыигрышная ситуация Решение шахмат Топологическая игра Трагедия общественного достояния Тирания маленьких решений