Теория кооперативных игр

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

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

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

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

Кооперативная теория игр — это раздел теории игр, который занимается изучением игр, в которых игроки могут формировать коалиции, сотрудничать друг с другом и заключать обязывающие соглашения. Теория предлагает математические методы для анализа сценариев, в которых двум или более игрокам необходимо сделать выбор, который повлияет на благополучие других игроков. ^[5]

Общие интересы: В кооперативных играх игроки разделяют общий интерес в достижении определенной цели или результата. Игроки должны определить и договориться об общем интересе, чтобы установить основу и обоснование для сотрудничества. Как только игроки четко поймут свой общий интерес, они могут работать вместе, чтобы достичь его. ^{[ необходима цитата ]}

Необходимый обмен информацией: Сотрудничество требует общения и обмена информацией между игроками. Игроки должны делиться информацией о своих предпочтениях, ресурсах и ограничениях, чтобы определить возможности для взаимной выгоды. Обмениваясь информацией, игроки могут лучше понять цели друг друга и работать над их достижением вместе. ^{[ необходима цитата ]}

Добровольность, равенство и взаимная выгода: в кооперативных играх игроки добровольно объединяются, чтобы сформировать коалиции и заключить соглашения. Игроки должны быть равноправными партнерами в коалиции, и любые соглашения должны быть взаимовыгодными. Сотрудничество является устойчивым только в том случае, если все стороны чувствуют, что получают справедливую долю выгод. ^{[ необходима цитата ]}

Обязательный контракт: В кооперативных играх соглашения между игроками являются обязательными и обязательными. Как только игроки согласились на определенный курс действий, у них есть обязательство следовать ему. Игроки должны доверять друг другу, чтобы выполнять свои обязательства, и должны быть механизмы для обеспечения соблюдения соглашений. Делая соглашения обязательными и обязательными, игроки могут гарантировать, что они достигнут своей общей цели. ^{[ необходима цитата ]}

Пусть будет непустой коалицией игроков. Подыгра на естественно определяется как${\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, стр. 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, то есть коалиции либо «выигрывают», либо «проигрывают». ^[6]

Эквивалентно, простая игра может быть определена как набор 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 имеем тогда и только тогда, когда . Когда простая игра имеет носитель, любой игрок, не принадлежащий ему, игнорируется. Простая игра иногда называется конечной , если она имеет конечный носитель (даже если N бесконечно).${\displaystyle T\subseteq N}$${\displaystyle S\in W}$${\displaystyle S\cap T\in W}$
• Число Накамуры простой игры — это минимальное число выигрышных коалиций с пустым пересечением. Согласно теореме Накамуры, число измеряет степень рациональности; это показатель того, в какой степени правило агрегации может давать четко определенные выборы.

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

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

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

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

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

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

Основное предположение в теории кооперативных игр заключается в том, что сформируется большая коалиция. ^[13] Затем задача состоит в том, чтобы распределить выигрыш между игроками каким-либо образом. (Это предположение не является ограничительным, поскольку даже если игроки разделяются и формируют меньшие коалиции, мы можем применять концепции решения к подиграм, определяемым фактически сформированными коалициями.) Концепция решения — это вектор (или набор векторов), который представляет распределение для каждого игрока. Исследователи предложили различные концепции решения, основанные на различных представлениях о справедливости. Вот некоторые свойства, на которые следует обратить внимание в концепции решения:${\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}$
• Монотонность: Выигрыш игрока увеличивается, если предельный вклад этого игрока увеличивается: подразумевает, что слабо больше в , чем в .${\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 я}$${\displaystyle j}$${\displaystyle я}$${\displaystyle j}$${\displaystyle v(S\cup \{i\})=v(S\cup \{j\}),\forall ~S\subseteq N\setminus \{i,j\}}$
• Аддитивность: распределение игрока в сумме двух игр является суммой распределений игрока в каждой отдельной игре. Математически, если и являются играми, игра просто назначает любой коалиции сумму выплат, которые коалиция получила бы в двух отдельных играх. Концепция аддитивного решения назначает каждому игроку сумму того, что он получил бы в и .${\displaystyle v}$${\displaystyle \омега}$${\displaystyle (v+\омега)}$${\displaystyle (v+\омега)}$${\displaystyle v}$${\displaystyle \омега}$
• Нулевое распределение для нулевых игроков: распределение для нулевого игрока равно нулю. Нулевой игрок удовлетворяет . С экономической точки зрения предельная ценность нулевого игрока для любой коалиции, которая его не содержит, равна нулю.${\displaystyle я}$${\displaystyle v(S\cup \{i\})=v(S),\forall ~S\subseteq N\setminus \{i\}}$

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

Стабильный набор игры (также известный как решение фон Неймана-Моргенштерна (von Neumann & Morgenstern 1944)) был первым решением, предложенным для игр с более чем 2 игроками. Пусть будет игрой и пусть , будет двумя подстановками . Тогда доминирует , если некоторая коалиция удовлетворяет и . Другими словами, игроки в предпочитают выигрыши от тем из , и они могут угрожать покинуть большую коалицию, если используется , потому что выигрыш, который они получают самостоятельно, по крайней мере так же велик, как распределение, которое они получают при .${\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}$

Стабильный набор — это набор импутаций , удовлетворяющий двум свойствам:

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

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

• Стабильный набор может существовать, а может и не существовать (Lucas 1969), а если он существует, то он, как правило, не является уникальным (Lucas 1992). Стабильные наборы обычно трудно найти. Эта и другие трудности привели к разработке многих других концепций решений.
• Положительная доля кооперативных игр имеет уникальные стабильные наборы, состоящие из ядра (Оуэн, 1995, стр. 240).
• Положительная доля кооперативных игр имеет стабильные наборы, которые дискриминируют игроков. В таких наборах по крайней мере дискриминируемые игроки исключаются (Owen 1995, стр. 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) было введено обобщение. Сильное ядро${\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), является пересечением всех непустых сильных -ядер. Его также можно рассматривать как сильное -ядро для наименьшего значения , которое делает множество непустым (Bilbao 2000).${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$

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

Пусть будет игрой, и пусть будет эффективным вектором выигрыша. Максимальный излишек игрока i над игроком j относительно x равен${\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 . Максимальный излишек — это способ измерить переговорную силу одного игрока над другим. Ядро — это набор подстановок 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 , если , но игрок j невосприимчив к угрозам игрока i , если , потому что он может получить этот выигрыш самостоятельно. Ядро содержит все вменения , где ни один игрок не имеет этой переговорной силы над другим. Эта концепция решения была впервые введена в (Davis & Maschler 1965).${\displaystyle s_{ij}^{v}(x)>s_{ji}^{v}(x)}$${\displaystyle x_{j}=v(j)}$

Дивиденд Харсани (названный в честь Джона Харсани , который использовал его для обобщения значения Шепли в 1963 году ^[15] ) определяет излишек, который создается коалицией игроков в кооперативной игре. Чтобы определить этот излишек, ценность этой коалиции корректируется излишком, который уже создан подкоалициями. С этой целью дивиденд коалиции в игре рекурсивно определяется${\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_{v}(\{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}}}$

Явная формула для дивиденда задается как . Функция также известна как обратная функция Мёбиуса . ^[16] Действительно, мы можем восстановить из с помощью формулы .${\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|}}$

Пусть будет игрой, и пусть будет вектором выигрыша. Избыток для коалиции — это величина ; то есть выигрыш, который игроки в коалиции могут получить, если они выйдут из большой коалиции при выигрыше и вместо этого возьмут выигрыш . Ядрышко — это подстановка , для которой вектор избытков всех коалиций (вектор в ) является наименьшим в лексиминном порядке . Ядрышко было введено в (Schmeidler 1969).${\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 v}$${\displaystyle \mathbb {R} ^{2^{N}}}$

(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;}$

то есть, «стимулы для присоединения к коалиции увеличиваются по мере роста коалиции» (Шепли, 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), поскольку минимизация обоих типов функций вычислительно поддается обработке. К сожалению, это напрямую противоречит первоначальному определению Шепли супермодулярных функций как «выпуклых».

Корпоративные стратегические решения могут развиваться и создавать ценность посредством кооперативной теории игр. ^[17] Это означает, что кооперативная теория игр может стать стратегической теорией фирмы, а различные решения CGT могут моделировать различные институты.

• Принятие решений на основе консенсуса
• Игра на координацию
• Внутрисемейные торги
• Гедонистическая игра
• Линейная производственная игра
• Игра «Охватывающее дерево с минимальной стоимостью» — класс кооперативных игр.

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

• Дэвис, М.; Машлер, М. (1965), «Ядро кооперативной игры», Naval Research Logistics Quarterly , 12 (3): 223–259, doi :10.1002/nav.3800120303

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

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

• Ловас, Ласло (1983), «Субмодулярные функции и выпуклость», в Bachem, A.; Grötschel, M .; Korte, B. (ред.), Mathematical Programming—The State of the Art , Berlin: Springer, стр. 235–257

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

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

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

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

• Осборн, М.Дж. и Рубинштейн, А. (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

• Шмейдлер, Д. (1969), «Ядро характеристической функциональной игры», Журнал SIAM по прикладной математике , 17 (6): 1163–1170, doi :10.1137/0117107.

• Шепли, Ллойд С. (1953), «Значение для игр с двумя лицами», в книге Кун, Х.; Такер, А. В. (ред.), Вклад в теорию игр II , Принстон, Нью-Джерси: Princeton University Press, стр. 307–317${\displaystyle n}$

• Шепли, Ллойд С. (18 марта 1952 г.), «Ценность игр N-человек», Санта-Моника, Калифорния: Корпорация RAND

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

• Шепли, Ллойд С.; Шубик, М. (1966), «Квазиядра в денежной экономике с невыпуклыми предпочтениями», Econometrica , 34 (4): 805–827, doi :10.2307/1910101, JSTOR  1910101

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

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

• Yeung, David WK и Leon A. Petrosyan. Кооперативные стохастические дифференциальные игры (серия Springer по исследованию операций и финансовому инжинирингу), Springer, 2006. Мягкая обложка - ISBN 978-1441920942 . 
• Yeung, David WK и Leon A. Petrosyan. Subgame Consistent Economic Optimization: An Advanced Cooperative Dynamic Game Analysis (Static & Dynamic Game Theory: Foundations & Applications), Birkhäuser Boston; 2012. ISBN 978-0817682613 

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