Кооперативная теория игр

В теории игр , кооперативная игра (или коалиционная игра ) является игра с конкуренцией между группами игроков ( «коалициями») в связи с возможностью внешнего исполнения кооперативного поведения (например , с помощью договорного права ). Они выступают против некооперативных игр, в которых либо нет возможности заключать союзы, либо все соглашения должны быть самодостаточными (например, посредством реальных угроз ). ^[1]

Кооперативные игры часто анализируются в рамках теории кооперативных игр, которая фокусируется на предсказании того, какие коалиции сформируются, совместные действия, которые предпринимают группы, и итоговые коллективные выгоды. Она противоположна традиционной теории некооперативных игр, которая фокусируется на прогнозировании действий и выигрышей отдельных игроков и анализе равновесий по Нэшу . ^{[2] [3]}

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

Математическое определение [ править ]

Кооперативная игра задается указанием значения для каждой коалиции. Формально коалиционная игра состоит из конечного набора игроков , называемого большой коалицией , и характеристической функции ^[4] от множества всех возможных коалиций игроков до множества выплат, которые удовлетворяют . Функция описывает, какой коллективный выигрыш группа игроков может получить, сформировав коалицию, и игру иногда называют игрой ценности или игрой прибыли .${\ displaystyle N}$ ${\ Displaystyle v: 2 ^ {N} \ to \ mathbb {R}}$ ${\ Displaystyle v (\ emptyset) = 0}$

И наоборот, кооперативная игра также может быть определена с удовлетворяющей характеристической функцией стоимости . В этом случае игроки должны выполнить некоторую задачу, а характеристическая функция представляет собой стоимость группы игроков, выполняющих задачу вместе. Игра такого рода известна как игра с затратами . Хотя большая часть теории кооперативных игр имеет дело с играми на прибыль, все концепции могут быть легко переведены на определение стоимости.${\ displaystyle c: 2 ^ {N} \ to \ mathbb {R}}$${\ Displaystyle с (\ emptyset) = 0}$${\ displaystyle c}$

Дивиденды Харшаньи [ править ]

Дивиденд Harsanyi (названный в честь Джона Harsanyi , который использовал его для обобщения Шепли значение в 1963 году ^[5] ) определяет излишек , который создается коалицией игроков в кооперативной игре. Чтобы определить этот излишек, ценность этой коалиции корректируется на излишек, который уже создан субкоалициями. С этой целью дивиденд коалиции в игре рекурсивно определяется как${\ displaystyle d_ {v} (S)}$${\ displaystyle S}$${\ displaystyle v}$

${\displaystyle {\begin{aligned}d_{v}(\{i\})&=v(\{i\})\\d_{v}(\{i,j\})&=v(\{i,j\})-d_{v}(\{i\})-d_{v}(\{j\})\\d_{v}(\{i,j,k\})&=v(\{i,j,k\})-d_{v}(\{i,j\})-d_{v}(\{i,k\})-d_{x}(\{j,k\})-d_{v}(\{i\})-d_{v}(\{j\})-d_{v}(\{k\})\\&\vdots \\d_{v}(S)&=v(S)-\sum _{T\subsetneq S}d_{v}(T)\end{aligned}}}$

Явная формула для дивиденда дается . Эта функция также известна как функция Мёбиуса, обратная к . ^[6] Действительно, мы можем вылечиться с помощью формулы .${\textstyle d_{v}(S)=\sum _{T\subseteq S}(-1)^{|S\setminus T|}v(T)}$${\displaystyle d_{v}:2^{N}\to \mathbb {R} }$${\displaystyle v:2^{N}\to \mathbb {R} }$${\displaystyle v}$${\displaystyle d_{v}}$${\textstyle v(S)=d_{v}(S)+\sum _{T\subsetneq S}d_{v}(T)}$

Дивиденды Харшани полезны для анализа как игр, так и концепций решений, например, значение Шепли получается путем распределения дивидендов каждой коалиции между ее членами, т. Е. Значение Шепли игрока в игре дается путем суммирования доли игрока в дивидендах все коалиции , что она принадлежит, .${\displaystyle \phi _{i}(v)}$${\displaystyle i}$${\displaystyle v}$${\textstyle \phi _{i}(v)=\sum _{S\subset N:i\in S}{d_{v}(S)}/{|S|}}$

Двойственность [ править ]

Пусть будет игра с прибылью. Двойная игра в это стоимость игры определяется как${\displaystyle v}$${\displaystyle v}$${\displaystyle v^{*}}$

${\displaystyle v^{*}(S)=v(N)-v(N\setminus S),\forall ~S\subseteq N.}$

Интуитивно двойная игра представляет собой альтернативную стоимость отказа коалиции от присоединения к большой коалиции . Игра с двойной прибылью может быть определена идентично игре с затратами . Кооперативная игра и ее дуал в некотором смысле эквивалентны и имеют много общих свойств. Например, ядро игры и ее дуал равны. Подробнее о двойственности кооперативных игр см., Например, ( Bilbao 2000 ).${\displaystyle S}$${\displaystyle N}$${\displaystyle c^{*}}$${\displaystyle c}$

Подигры [ править ]

Позвольте быть непустой коалиции игроков. Подыгры на естественно определяются как${\displaystyle S\subsetneq N}$ ${\displaystyle v_{S}:2^{S}\to \mathbb {R} }$${\displaystyle S}$

${\displaystyle v_{S}(T)=v(T),\forall ~T\subseteq S.}$

Другими словами, мы просто ограничиваем наше внимание коалициями, содержащимися в . Подигры полезны, потому что они позволяют нам применять концепции решения, определенные для большой коалиции, к меньшим коалициям.${\displaystyle S}$

Свойства для характеристики [ править ]

Супераддитивность [ править ]

Характеристические функции часто считаются супераддитивными ( Owen 1995 , p. 213). Это означает, что ценность объединения непересекающихся коалиций не меньше суммы отдельных значений коалиций:

${\displaystyle v(S\cup T)\geq v(S)+v(T)}$всякий раз, когда удовлетворяю .${\displaystyle S,T\subseteq N}$${\displaystyle S\cap T=\emptyset }$

Монотонность [ править ]

Более крупные коалиции получают больше:

${\displaystyle S\subseteq T\Rightarrow v(S)\leq v(T)}$.

Это следует из супераддитивности . т.е. если выплаты нормализованы, то одноэлементные коалиции имеют нулевое значение.

Свойства для простых игр [ править ]

Коалиционная игра v считается простой, если выигрыши равны 1 или 0, т. Е. Коалиции либо «выигрывают», либо «проигрывают». ^[7]

Точно так же простую игру можно определить как набор W коалиций, где члены W называются выигрышными коалициями, а остальные - проигрышными коалициями. Иногда предполагается, что простая игра непуста или не содержит пустого множества. Однако в других областях математики простые игры также называют гиперграфами или булевыми функциями (логическими функциями).

• Простая игра W является монотонной, если любая коалиция, содержащая выигрышную коалицию, также выигрывает, то есть если и подразумевают .${\displaystyle S\in W}$${\displaystyle S\subseteq T}$${\displaystyle T\in W}$
• Простая игра W является правильной, если дополнение (оппозиция) любой выигрышной коалиции проигрывает, то есть если подразумевается .${\displaystyle S\in W}$${\displaystyle N\setminus S\notin W}$
• Простая игра W является сильным , если дополнение к любой проигравшей коалиции побеждает, то есть, если подразумевает .${\displaystyle S\notin W}$${\displaystyle N\setminus S\in W}$
  • Если простая игра W правильная и сильная, то коалиция выигрывает тогда и только тогда, когда ее дополнение проигрывает, то есть тогда и только тогда . (Если v - коалиционная простая игра, правильная и сильная для любого S. )${\displaystyle S\in W}$${\displaystyle N\setminus S\notin W}$${\displaystyle v(S)=1-v(N\setminus S)}$
• Игрок с правом вето (вето) в простой игре - это игрок, который принадлежит ко всем выигрышным коалициям. Предположим, что есть игрок с правом вето, любая коалиция, не содержащая игрока с правом вето, проигрывает. Простая игра W является слабой ( коллегиальной ), если в ней есть игрок с правом вето, то есть если пересечение всех выигрышных коалиций непусто.${\displaystyle \bigcap W:=\bigcap _{S\in W}S}$
  • Диктатор в простой игре вето игрок такой , что любая коалиция , содержащая этот игрок выигрывает. Диктатор не принадлежит ни к одной проигравшей коалиции. ( Игры с диктаторами в экспериментальной экономике не имеют к этому отношения.)
• Носитель из простой игры W представляет собой набор , что для любой коалиции S , мы имеем IFF . Когда в простой игре есть оператор, любой игрок, не принадлежащий к нему, игнорируется. Простую игру иногда называют конечной, если у нее есть конечный носитель (даже если N бесконечно).${\displaystyle T\subseteq N}$${\displaystyle S\in W}$${\displaystyle S\cap T\in W}$
• Число Накамуры простой игры - это минимальное количество выигрышных коалиций с пустым пересечением. Согласно теореме Накамуры, число измеряет степень рациональности; это индикатор того, в какой степени правило агрегирования может давать четко определенный выбор.

Несколько соотношений между вышеуказанными аксиомами получили широкое признание, например следующие (например, Peleg, 2002, раздел 2.1 ^[8] ):

• Если простая игра слабая, то это правильно.
• Простая игра диктаторская тогда и только тогда, когда она сильна и слаба.

В более общем плане было проведено полное исследование связи между четырьмя общепринятыми аксиомами (монотонность, правильность, сила и неслабость), конечностью и алгоритмической вычислимостью ^[9] (Kumabe and Mihara, 2011 ^[10] ), чьи результаты приведены в таблице «Существование простых игр» ниже.

Также были тщательно изучены ограничения, которые различные аксиомы для простых игр накладывают на их число Накамуры . ^[12] В частности, вычислимая простая игра без вето игрока имеет число Накамуры больше 3, только если это правильная и несильная игра.

Связь с некооперативной теорией [ править ]

Пусть G - стратегическая (не кооперативная) игра. Тогда, при условии , что блоки имеют возможность применять согласованное поведение, есть несколько совместных игр , связанные с G . Эти игры часто называют представлениями G . Двумя стандартными представлениями являются: ^[13]

• Α-эффективная игра связывает с каждой коалицией сумму выигрышей, которую ее участники могут «гарантировать» объединением усилий. Под «гарантией» подразумевается, что значение является максимальным-минимальным, например, максимальное значение минимума, взятое на стратегии противника.
• Β-эффективная игра связывает с каждой коалицией сумму выигрышей, которую ее участники могут «стратегически гарантировать» объединением усилий. Под «стратегической гарантией» подразумевается, что значение - это min-max, например, минимальное значение из максимума, используемое для стратегий противника.

Концепции решения [ править ]

Основное предположение в теории кооперативных игр состоит в том, что большая коалиция сформируется. ^[14] Задача состоит в том, чтобы справедливо распределить выигрыш между игроками. (Это предположение не является ограничивающим, потому что даже если игроки отделяются и образуют меньшие коалиции, мы можем применять концепции решения к подиграм, определяемым какими бы то ни было коалициями на самом деле.) Концепция решения - это вектор, который представляет распределение каждому игроку. Исследователи предложили разные концепции решения, основанные на разных представлениях о справедливости. Некоторые свойства, которые следует искать в концепции решения, включают:${\displaystyle N}$${\displaystyle v(N)}$${\displaystyle x\in \mathbb {R} ^{N}}$

• Эффективность: вектор выигрышей точно разделяет общую стоимость: .${\displaystyle \sum _{i\in N}x_{i}=v(N)}$
• Индивидуальная рациональность: Ни один игрок не получает меньше , чем он мог бы получить в одиночку: .${\displaystyle x_{i}\geq v(\{i\}),\forall ~i\in N}$
• Существование: Концепция решения существует для любой игры .${\displaystyle v}$
• Уникальность: Концепция решения уникальна для любой игры .${\displaystyle v}$
• Маржинальность: выигрыш игрока зависит только от предельного вклада этого игрока, т. Е. Если эти предельные взносы одинаковы в двух разных играх, то выплата одинакова: подразумевается, что это одинаково и внутри, и внутри .${\displaystyle v(S\cup \{i\})=w(S\cup \{i\}),\forall ~S\subseteq N\setminus \{i\}}$${\displaystyle x_{i}}$${\displaystyle v}$${\displaystyle w}$
• Монотонность: выигрыш игрока увеличивается, если предельный вклад этого игрока увеличивается: подразумевается, что он немного больше in, чем in .${\displaystyle v(S\cup \{i\})\leq w(S\cup \{i\}),\forall ~S\subseteq N\setminus \{i\}}$${\displaystyle x_{i}}$${\displaystyle w}$${\displaystyle v}$
• Простота вычислений: концепция решения может быть вычислена эффективно (т. Е. За полиномиальное время по отношению к количеству игроков ).${\displaystyle |N|}$
• Симметрия: Решение Концепция выделяет равные платежи в симметричные игрок , . Два игрока , является симметричным , если ; то есть мы можем обменять одного игрока на другого в любой коалиции, в которую входит только один из игроков, и не изменять выигрыш.${\displaystyle x}$${\displaystyle x_{i}=x_{j}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle v(S\cup \{i\})=v(S\cup \{j\}),\forall ~S\subseteq N\setminus \{i,j\}}$
• Аддитивность: распределение игроку в сумме двух игр - это сумма распределения игроку в каждой отдельной игре. Математически, если и являются играми, игра просто назначает любой коалиции сумму выигрышей, которую коалиция получит в двух отдельных играх. Концепция аддитивного решения назначает каждому игроку сумму того, что он получил бы и .${\displaystyle v}$${\displaystyle \omega }$${\displaystyle (v+\omega )}$${\displaystyle (v+\omega )}$${\displaystyle v}$${\displaystyle \omega }$
• Нулевое распределение нулевым игрокам: Нулевым игрокам выделяется ноль. А нулевой игрок удовлетворяет . С экономической точки зрения предельная ценность нулевого игрока для любой коалиции, в которую он не входит, равна нулю.${\displaystyle i}$${\displaystyle v(S\cup \{i\})=v(S),\forall ~S\subseteq N\setminus \{i\}}$

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

Стабильный набор [ править ]

Стабильный набор игры (также известный как решение фон Неймана-Моргенштерна ( von Neumann & Morgenstern, 1944 )) был первым решением, предложенным для игр с более чем двумя игроками. Пусть будет игра , и пусть , два инсинуации о . Тогда доминирует, если некоторая коалиция удовлетворяет и . Другими словами, игроки предпочитают отдачу от тех , с , и они могут угрожать покинуть большую коалицию , если используется , потому что выигрыш они получают сами по себе, по крайней мере столь же большой как выделение они получают под .${\displaystyle v}$${\displaystyle x}$${\displaystyle y}$${\displaystyle v}$${\displaystyle x}$ ${\displaystyle y}$${\displaystyle S\neq \emptyset }$${\displaystyle x_{i}>y_{i},\forall ~i\in S}$${\displaystyle \sum _{i\in S}x_{i}\leq v(S)}$${\displaystyle S}$${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle x}$

Множество устойчиво представляет собой набор расчетных данных , который удовлетворяет двум свойствам:

• Внутренняя стабильность: ни один вектор выигрыша в стабильном наборе не подчиняется другому вектору в наборе.
• Внешняя стабильность: все векторы выигрыша вне набора определяются по крайней мере одним вектором в наборе.

Фон Нейман и Моргенштерн рассматривали стабильный набор как совокупность приемлемых моделей поведения в обществе: одно явно не предпочтительнее любого другого, но для каждого неприемлемого поведения есть предпочтительная альтернатива. Это очень общее определение, позволяющее использовать концепцию в самых разных игровых форматах.

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

• Стабильный набор может существовать, а может и не существовать ( Лукас, 1969 ), и если он существует, то обычно не является уникальным ( Лукас, 1992 ). Стабильные наборы обычно трудно найти. Эта и другие трудности привели к разработке многих других концепций решения.
• Положительная часть кооперативных игр имеет уникальные стабильные наборы, состоящие из ядра ( Owen 1995 , p. 240).
• Положительная часть кооперативных игр имеет стабильные наборы, которые различают игроков. В таких наборах исключаются, по крайней мере, дискриминированные игроки ( Owen 1995 , p. 240).${\displaystyle n-2}$${\displaystyle n-3}$

Ядро [ править ]

Пусть будет игра. Ядро из есть множество векторов выигрышей${\displaystyle v}$${\displaystyle v}$

${\displaystyle C(v)=\left\{x\in \mathbb {R} ^{N}:\sum _{i\in N}x_{i}=v(N);\quad \sum _{i\in S}x_{i}\geq v(S),\forall ~S\subseteq N\right\}.}$

Другими словами, ядро ​​- это набор условных обозначений, при которых ни одна коалиция не имеет ценности, превышающей сумму выплат ее членов. Следовательно, ни у какой коалиции нет стимула выйти из большой коалиции и получить больший выигрыш.

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

• Ядро из игры может быть пустым (см теоремы Бондарева-Шепли ). Игры с непустыми ядрами называются сбалансированными .
• Если он не пустой, ядро ​​не обязательно содержит уникальный вектор.
• Ядро содержится в любом стабильном наборе, и если ядро является стабильным он является единственным устойчивым множеством; см. ( Driessen 1988 ) для доказательства.

Ядро простой игры относительно предпочтений [ править ]

Для простых игр существует другое понятие ядра, когда предполагается, что каждый игрок имеет предпочтения по набору альтернатив. Профиль представляет собой список индивидуальных предпочтений на . Здесь означает , что индивидуум предпочитает альтернативу к в профиле . Учитывая простую игру и профиль , отношение доминирования определяется тем и только тогда, когда существует выигрышная коалиция (т. Е.), Удовлетворяющая всех . Ядро от простой игры по профилю${\displaystyle X}$${\displaystyle p=(\succ _{i}^{p})_{i\in N}}$${\displaystyle \succ _{i}^{p}}$${\displaystyle X}$${\displaystyle x\succ _{i}^{p}y}$${\displaystyle i}$${\displaystyle x}$${\displaystyle y}$${\displaystyle p}$${\displaystyle v}$${\displaystyle p}$${\displaystyle \succ _{v}^{p}}$${\displaystyle X}$${\displaystyle x\succ _{v}^{p}y}$${\displaystyle S}$${\displaystyle v(S)=1}$${\displaystyle x\succ _{i}^{p}y}$${\displaystyle i\in S}$ ${\displaystyle C(v,p)}$${\displaystyle v}$${\displaystyle p}$предпочтений - это набор альтернатив, не доминирующий (набор максимальных элементов по ):${\displaystyle \succ _{v}^{p}}$${\displaystyle X}$${\displaystyle \succ _{v}^{p}}$

${\displaystyle x\in C(v,p)}$тогда и только тогда, когда такого нет .${\displaystyle y\in X}$${\displaystyle y\succ _{v}^{p}x}$

Число Накамуры простой игры - это минимальное количество выигрышных коалиций с пустым пересечением. Теорема Накамуры утверждает , что ядро не пусто для всех профилей из ациклических (альтернативно, переходного ) предпочтений тогда и только тогда , конечно , и кардинальное число (число элементов) из меньше , чем число Накамур . Вариант Кумабе и Михара утверждает, что ядро непусто для всех профилей предпочтений, имеющих максимальный элемент, тогда и только тогда, когда кардинальное число меньше числа Накамуры . (Видеть${\displaystyle C(v,p)}$${\displaystyle p}$${\displaystyle X}$${\displaystyle X}$${\displaystyle v}$${\displaystyle C(v,p)}$${\displaystyle p}$${\displaystyle X}$${\displaystyle v}$Номер Накамуры для подробностей.)

Сильное эпсилон-ядро [ править ]

Поскольку ядро может быть пустым, в ( Shapley & Shubik 1966 ) было введено обобщение . Сильный -core${\displaystyle \varepsilon }$ для некоторого числа есть множество векторов выигрышей${\displaystyle \varepsilon \in \mathbb {R} }$

${\displaystyle C_{\varepsilon }(v)=\left\{x\in \mathbb {R} ^{N}:\sum _{i\in N}x_{i}=v(N);\quad \sum _{i\in S}x_{i}\geq v(S)-\varepsilon ,\forall ~S\subseteq N\right\}.}$

С экономической точки зрения сильное ядро - это набор предварительных условных обозначений, при которых ни одна коалиция не может улучшить свой выигрыш, покинув большую коалицию, если она должна заплатить штраф в размере за выход. Обратите внимание, что он может быть отрицательным, и в этом случае он представляет собой бонус за выход из большой коалиции. Очевидно, что независимо от того , пусто ли ядро , сильное ядро будет непустым при достаточно большом значении и пустым при достаточно малом (возможно отрицательном) значении . Следуя этой линии рассуждений, наименьшее ядро , введенное в ( Maschler, Peleg & Shapley, 1979 ), является пересечением всех непустых сильных- ядер. Его также можно рассматривать как сильное${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$-core для наименьшего значения, которое делает набор непустым ( Bilbao 2000 ).${\displaystyle \varepsilon }$

Значение Шепли [ править ]

Значение Шепли - это уникальный вектор выигрыша, который является эффективным, симметричным и удовлетворяет монотонности. ^[15] Он был введен Ллойдом Шепли ( Shapley 1953 ), который показал, что это уникальный вектор выигрыша, который является эффективным, симметричным, аддитивным и присваивает нулевые выплаты фиктивным игрокам. Ценность Шепли супераддитивной игры индивидуально рациональна, но в целом это неверно. ( Дриссен, 1988 )

Ядро [ править ]

Позвольте быть игрой, и пусть будет эффективным вектором выигрыша. Максимальный излишек игрока я над игроком J относительно х является${\displaystyle v:2^{N}\to \mathbb {R} }$${\displaystyle x\in \mathbb {R} ^{N}}$

${\displaystyle s_{ij}^{v}(x)=\max \left\{v(S)-\sum _{k\in S}x_{k}:S\subseteq N\setminus \{j\},i\in S\right\},}$

максимальную сумму, которую игрок i может получить без сотрудничества с игроком j , выйдя из большой коалиции N согласно вектору выигрыша x , предполагая, что другие игроки в коалиции вывода i удовлетворены своими выигрышами при x . Максимальный профицит - это способ измерить переговорную силу одного игрока над другим. Ядро из есть множество дележей х , которые удовлетворяют условию${\displaystyle v}$

• ${\displaystyle (s_{ij}^{v}(x)-s_{ji}^{v}(x))\times (x_{j}-v(j))\leq 0}$, и
• ${\displaystyle (s_{ji}^{v}(x)-s_{ij}^{v}(x))\times (x_{i}-v(i))\leq 0}$

для каждой пары игроков i и j . Интуитивно, игрок i имеет большую переговорную силу, чем игрок j, в отношении вменения x if , но игрок j невосприимчив к угрозам игрока i if , потому что он может получить эту выплату самостоятельно. Ядро содержит все вменения, при которых ни один игрок не имеет такой переговорной силы над другим. Эта концепция решения была впервые представлена ​​в ( Davis & Maschler 1965 ).${\displaystyle s_{ij}^{v}(x)>s_{ji}^{v}(x)}$${\displaystyle x_{j}=v(j)}$

Ядрышко [ править ]

Пусть будет игра, и пусть будет вектор выигрыша. Избытком из для коалиции является величиной ; то есть выигрыш, который игроки в коалиции могут получить, если они выйдут из большой коалиции при выплате и вместо этого получат выплату .${\displaystyle v:2^{N}\to \mathbb {R} }$${\displaystyle x\in \mathbb {R} ^{N}}$${\displaystyle x}$${\displaystyle S\subseteq N}$${\displaystyle v(S)-\sum _{i\in S}x_{i}}$${\displaystyle S}$${\displaystyle N}$${\displaystyle x}$${\displaystyle v(S)}$

Пусть теперь будет вектор излишков , упорядоченный в порядке невозрастания. Другими словами, . Обратите внимание , что находится в ядре в том и только если это предварительно вменение и . Чтобы определить ядрышко, мы рассматриваем лексикографическое упорядочение векторов в : Для двух векторов выигрыша мы говорим, что он лексикографически меньше, чем если бы для некоторого индекса у нас есть и . (Упорядочение называется лексикографическим потому что оно подражает алфавитный порядок используется для организации слов в словаре) . В ядрышке из является лексикографический минимальным вменением${\displaystyle \theta (x)\in \mathbb {R} ^{2^{N}}}$${\displaystyle x}$${\displaystyle \theta _{i}(x)\geq \theta _{j}(x),\forall ~i<j}$${\displaystyle x}$${\displaystyle v}$${\displaystyle \theta _{1}(x)\leq 0}$${\displaystyle \mathbb {R} ^{2^{N}}}$${\displaystyle x,y}$${\displaystyle \theta (x)}$${\displaystyle \theta (y)}$${\displaystyle k}$${\displaystyle \theta _{i}(x)=\theta _{i}(y),\forall ~i<k}$${\displaystyle \theta _{k}(x)<\theta _{k}(y)}$${\displaystyle v}$, исходя из этого порядка. Эта концепция решения была впервые представлена ​​в ( Schmeidler 1969 ).

Хотя определение ядрышка кажется абстрактным, ( Maschler, Peleg & Shapley, 1979 ) было дано более интуитивное описание: начиная с наименьшего ядра, запишите коалиции, для которых правая часть неравенства в определении не может быть дальше уменьшается без опустошения набора. Продолжайте уменьшать правую часть для оставшихся коалиций, пока ее нельзя будет уменьшить, не опустошая набор. Запишите новый набор коалиций, для которых неравенства выполняются при равенстве; продолжайте уменьшать правую часть оставшихся коалиций и повторяйте этот процесс столько раз, сколько необходимо, пока все коалиции не будут записаны. Полученный вектор выигрыша - ядрышко.${\displaystyle C_{\varepsilon }(v)}$

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

• Хотя в определении это прямо не говорится, ядрышко всегда уникально. (См. Доказательство в Разделе II.7 ( Driessen 1988 ).)
• Если ядро ​​не пусто, ядрышко находится в ядре.
• Ядрышко всегда находится в ядре, и поскольку ядро ​​содержится в наборе переговоров, оно всегда находится в наборе переговоров (подробности см. ( Driessen 1988 )).

Выпуклые кооперативные игры [ править ]

Представленные Шепли в ( Shapley, 1971 ) выпуклые кооперативные игры захватывают интуитивное свойство некоторых игр «снежного кома». В частности, игра является выпуклой, если ее характеристическая функция является супермодульной :${\displaystyle v}$

${\displaystyle v(S\cup T)+v(S\cap T)\geq v(S)+v(T),\forall ~S,T\subseteq N.}$

Можно показать (см, например, раздел V.1 из ( Дриссен 1988 )) , что супермодулярности из эквивалентно${\displaystyle v}$

${\displaystyle v(S\cup \{i\})-v(S)\leq v(T\cup \{i\})-v(T),\forall ~S\subseteq T\subseteq N\setminus \{i\},\forall ~i\in N;}$

то есть «стимулы для присоединения к коалиции возрастают по мере роста коалиции» ( Shapley, 1971 ), что приводит к вышеупомянутому эффекту снежного кома. Для стоимостных игр неравенства меняются местами, поэтому мы говорим, что стоимостная игра является выпуклой, если характеристическая функция субмодулярна .

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

У выпуклых кооперативных игр есть много хороших свойств:

• Сверхмодулярность тривиально влечет супераддитивность .
• Выпуклые игры полностью сбалансированы : ядро выпуклой игры непусто, а поскольку любая под-игра выпуклой игры выпуклая, ядро любой под-игры также непусто.
• У выпуклой игры есть единственное стабильное множество, совпадающее с ее ядром .
• Шепли выпуклой игры является центром тяжести его ядра .
• Точку крайности (вершина) из ядра можно найти в полиномиальное время с помощью жадного алгоритма : Пусть будет перестановкой игроков, и пусть множество игроков заказало через в , для любого , с . Тогда выигрыш определяется является вершиной сердечника из . Таким образом можно построить любую вершину ядра , выбрав соответствующую перестановку .${\displaystyle \pi :N\to N}$${\displaystyle S_{i}=\{j\in N:\pi (j)\leq i\}}$${\displaystyle 1}$${\displaystyle i}$${\displaystyle \pi }$${\displaystyle i=0,\ldots ,n}$${\displaystyle S_{0}=\emptyset }$${\displaystyle x\in \mathbb {R} ^{N}}$${\displaystyle x_{i}=v(S_{\pi (i)})-v(S_{\pi (i)-1}),\forall ~i\in N}$${\displaystyle v}$ ${\displaystyle \pi }$

Сходства и различия с комбинаторной оптимизацией [ править ]

Субмодульные и супермодульные функции множества также изучаются в комбинаторной оптимизации . Многие из результатов ( Shapley, 1971 ) имеют аналоги в ( Edmonds 1970 ), где субмодулярные функции были впервые представлены как обобщения матроидов . В этом контексте ядро игры с выпуклой стоимостью называется базовым многогранником , поскольку его элементы обобщают базовые свойства матроидов .

Однако сообщество оптимизаторов обычно считает субмодулярные функции дискретными аналогами выпуклых функций ( Lovász, 1983 ), поскольку минимизация обоих типов функций является вычислительно управляемой. К сожалению, это прямо противоречит первоначальному определению Шепли супермодулярных функций как «выпуклых».

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

• Принятие консенсусных решений
• Координационная игра
• Внутрихозяйственный торг
• Гедоническая игра
• Линейная производственная игра

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

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

• Бильбао, Хесус Марио (2000), Совместные игры на комбинаторных структурах , Kluwer Academic Publishers, ISBN 9781461543930

• Дэвис, М .; Maschler, М. (1965), "Ядро кооперативной игры", военно - морских исследований логистики Ежеквартально , 12 (3): 223-259, DOI : 10.1002 / nav.3800120303

• Дриссен, Тео (1988), Совместные игры, решения и приложения , Kluwer Academic Publishers, ISBN 9789401577878

• Эдмондс, Джек (1970), «Субмодульные функции, матроиды и некоторые многогранники», в Guy, R .; Hanani, H .; Sauer, N .; Шёнхейм, Дж. (Ред.), Комбинаторные структуры и их приложения , Нью-Йорк: Гордон и Бреч, стр. 69–87.

• Ловас, Ласло (1983), «Субмодулярные функции и выпуклость», в Bachem, A .; Grötschel, M .; Корте, Б. (ред.), « Математическое программирование - современное состояние» , Берлин: Springer, стр. 235–257.

• Лейтон-Браун, Кевин; Шохам, Йоав (2008), Основы теории игр: краткое, многопрофильное введение , Сан-Рафаэль, Калифорния: Издательство Morgan & Claypool, ISBN 978-1-59829-593-1. 88-страничное математическое введение; см. главу 8. Бесплатное онлайн- обучение (требуется подписка) во многих университетах.

• Лукас, Уильям Ф. (1969), «Доказательство того, что игра может не иметь решения», Труды Американского математического общества , 136 : 219-229, DOI : 10,2307 / 1994798 , JSTOR  1994798 .

• Лукас, Уильям Ф. (1992), «Стабильные множества фон Неймана-Моргенштерна», в Aumann, Robert J .; Харт, Серджиу (ред.), Справочник по теории игр, том I , Амстердам: Elsevier , стр. 543–590.

• Люс, Р. Д. и Райффа, Х. (1957) Игры и решения: Введение и критический обзор , Wiley & Sons. (см. главу 8).
• Машлер, М .; Пелег, Б .; Шепли, Ллойд С. (1979), "Геометрические свойства ядра, ядрышка и связанные концепции решения", Математика исследования операций , 4 (4): 303–338, doi : 10.1287 / moor.4.4.303

• Осборн, MJ, и Рубинштейн, A. (1994) Курс теории игр , MIT Press (см. Главы 13,14,15)
• Мулен, Эрве (1988), Аксиомы совместного принятия решений (1-е изд.), Кембридж: Cambridge University Press , ISBN 978-0-521-42458-5

• Оуэн, Гильермо (1995), Теория игр (3-е изд.), Сан-Диего: Academic Press , ISBN 978-0-12-531151-9

• Schmeidler, D. (1969), "Ядрышко характеристической функции игры", SIAM журнал по прикладной математике , 17 (6): 1163-1170, DOI : 10,1137 / 0117107 .

• Шепли, Ллойд С. (1953), «Ценность для -личностных игр», в Kuhn, H .; Tucker, AW (eds.), Contributions to Theory of Games II , Princeton, New Jersey: Princeton University Press, pp. 307–317.${\displaystyle n}$

• Шепли, Ллойд С. (1971), "Ядра выпуклых игр", Международный журнал теории игр , 1 (1): 11-26, DOI : 10.1007 / BF01753431 , S2CID  123385556

• Шепли, Ллойд С .; Шубик, М. (1966), "квази-ядра в денежной экономике с невыпуклыми предпочтениями", Эконометрика , 34 (4): 805-827, DOI : 10,2307 / 1910101 , JSTOR  1910101

• Шохам, Йоав; Лейтон-Браун, Кевин (2009), Многоагентные системы: алгоритмические, теоретико-игровые и логические основы , Нью-Йорк: Cambridge University Press , ISBN 978-0-521-89943-7. Исчерпывающий справочник с вычислительной точки зрения; см. главу 12. Загружается бесплатно в Интернете .

• фон Нейман, Джон ; Моргенштерн, Оскар (1944), «Теория игр и экономического поведения» , Nature , Princeton: Princeton University Press , 157 (3981): 172, Bibcode : 1946Natur.157..172R , doi : 10.1038 / 157172a0 , S2CID  29754824

• Юнг, Давид В.К. и Леон А. Петросян. Кооперативные стохастические дифференциальные игры (серия Springer по исследованию операций и финансовому инжинирингу), Springer, 2006. Мягкая обложка - ISBN 978-1441920942 . 
• Юнг, Давид В.К. и Леон А. Петросян. Последовательная экономическая оптимизация подигр: расширенный совместный динамический анализ игры (Статическая и динамическая теория игр: основы и приложения), Birkhäuser Boston; 2012. ISBN 978-0817682613. 

Внешние ссылки [ править ]

• "Кооперативная игра" , Энциклопедия математики , EMS Press , 2001 [1994]