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

редактировать

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

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

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

Содержание

1 Математическое определение
2 Дивиденд Харшани
3 Двойственность
4 Подигры
5 Свойства для характеристики
- 5.1 Супераддитивность
- 5.2 Монотонность
- 5.3 Свойства для простых игры
6 Связь с некооперативной теорией
7 Концепции решения
- 7.1 Стабильный набор
  - 7.1.1 Свойства
- 7.2 Ядро
  - 7.2.1 Свойства
- 7.3 Ядро простой игры относительно предпочтений
- 7.4 Сильное эпсилон-ядро
- 7.5 Значение Шепли
- 7.6 Ядро
- 7.7 Ядрышко
  - 7.7.1 Свойства
8 Выпуклые кооперативные игры
- 8.1 Свойства
- 8.2 Сходства и различия с комбинаторной оптимизацией
9 См. Также
10 Ссылки
- 10.1 Дополнительная литература
11 Внешние ссылки

Математическое определение

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

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

Дивиденд Харсани

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

$dv ({i}) = v ({i}) dv ({i, j}) = v ({i, j}) - dv ({i}) - dv ({j}) dv ({i, j, k}) = v ({i, j, k}) - dv ({i, j}) - dv ({i, k}) - dx ({j, k}) - dv ({i}) - dv ({j}) - dv ({k}) ⋮ dv (S) = v (S) - ∑ T ⊊ S dv (T) {\ Displaystyle {\ begin {выровнено} 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 {align}}}$ ${\ displaystyle { \ begin {align} 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 {align}}}$

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

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

Двойственность

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

v ∗ (S) = v (N) - v (N ∖ S), ∀ S ⊆ N. {\ displaystyle v ^ {*} (S) = v (N) -v (N \ setminus S), \ forall ~ S \ substeq N.}

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

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

Подигры

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

v S (T) = v (T), ∀ T ⊆ S. {\ displaystyle v_ {S} (T) = v (T), \ forall ~ T \ substeq S.}

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

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

Свойства для характеризации

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

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

$v (S ∪ T) ≥ v (S) + v (T) { \ Displaystyle v (S \ чашка T) \ geq v (S) + v (T)}$ $v (S \ чашка T) \ geq v (S) + v (T)$ всякий раз, когда $S, T ⊆ N {\ displaystyle S, T \ substeq N}$ $S, T \ substeq N$ удовлетворить $S ∩ T = ∅ {\ displaystyle S \ cap T = \ emptyset}$ $S \ cap T = \ emptyset$ .

Монотонность

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

$S ⊆ T ⇒ v (S) ≤ v (T) {\ displaystyle S \ substeq T \ Rightarrow v (S) \ leq v (T)}$ $S \ substeq T \ Rightarrow v (S) \ leq v (T)$ .

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

Свойства простых игр

Коалиционная игра v считается простой, если выплаты равны 1 или 0, то есть коалиции либо «выигрывают», либо «проигрывают».

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

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

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

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

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

Существование простых игр
Тип	Конечное вычислимое	Конечное вычислимое	Бесконечное некомпьютерное	Бесконечное вычислимое
1111	Нет	Да	Да	Да
1110	Нет	Да	Нет	Нет
1101	Нет	Да	Да	Да
1100	Нет	Да	Да	Да
1011	Нет	Да	Да	Да
1010	Нет	Нет	Нет	Нет
1001	Нет	Да	Да	Да
1000	Нет	Нет	Нет	Нет
0111	Нет	Да	Да	Да
0110	Нет	Нет	Нет	Нет
0101	Нет	Да	Да	Да
0100	Нет	Да	Да	Да
0011	Нет	Да	Да	Да
0010	Нет	Нет	Нет	Нет
0001	Нет	Да	Да	Да
0000	Нет	Нет	Нет	Нет

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

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

Пусть G - стратегическая (некооперативная) игра. Затем, предполагая, что коалиции обладают способностью обеспечивать скоординированное поведение, существует несколько совместных игр, связанных с G. Эти игры часто называют представлениями G. Двумя стандартными представлениями являются:

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

Концепции решения

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

Эффективность: вектор выигрыша точно разделяет общее значение: $∑ i ∈ N xi = v (N) {\ displaystyle \ sum _ {i \ in N} x_ {i} = v (N)}$ $\ sum _ {{я \ in N}} x_ {i} = v (N)$ .
Индивидуальная рациональность: ни один игрок не получает меньше, чем он мог бы получить самостоятельно: $xi ≥ v ({i}), ∀ i ∈ N {\ displaystyle x_ { i} \ geq v (\ {i \}), \ forall ~ i \ in N}$ $x_ {i} \ geq v (\ {i \}), \ forall ~ i \ in N$ .
Существование: концепция решения существует для любой игры $v {\ displaystyle v}$ $v$ .
Уникальность: концепция решения является уникальным для любой игры $v {\ displaystyle v}$ $v$ .
Маржа: выигрыш игрока зависит только от предельного вклада этого игрока, т. е. если эти предельные взносы одинаковы в двух разных играх, то выплата такая же: $v (S ∪ {i}) = w (S ∪ {i}), ∀ S ⊆ N ∖ {i} {\ displaystyle v (S \ cup \ {i \}) = w (S \ cup \ {i \}), \ forall ~ S \ substeq N \ setminus \ {i \}}$ ${\ displaystyle v (S \ cup \ {i \}) = w (S \ cup \ {i \}), \ forall ~ S \ substeq N \ setminus \ {i \}}$ подразумевает, что $xi {\ displaystyle x_ {i}}$ $x_{i}$ то же самое в $v {\ displaystyle v}$ $v$ и в $w {\ displaystyle w}$ $w$ .
Монотонность: выигрыш игрока увеличивается, если предельный вклад этого игрока увеличивается: $v (S ∪ {i}) ≤ w (S ∪ {i}), ∀ S ⊆ N ∖ {я} {\ Displaystyle v (S \ чашка \ {я \}) \ leq w (S \ cup \ {я \}), \ forall ~ S \ substeq N \ setminus \ {i \}}$ ${\ displaystyle v (S \ cup \ {i \}) \ leq w (S \ cup \ {i \}), \ forall ~ S \ substeq N \ setminus \ {i \}}$ подразумевает, что $xi {\ displaystyle x_ {i}}$ $x_{i}$ слабо больше в $w {\ displaystyle w}$ $w$ , чем в $v {\ displaystyle v}$ $v$ .
Вычислительная простота: концепция решения может быть эффективно вычислена (т. е. за полиномиальное время по количеству игроков $| N | {\ displaystyle | N |}$ $| N |$ .)
Симметрия: концепция решения $x {\ displaystyle x}$ $x$ распределяет равные платежи $xi = xj {\ displaystyle x_ {i} = x_ {j }}$ $x_i = x_j$ для симметричных игроков $i {\ displaystyle i}$ $i$ , $j {\ displaystyle j}$ $j$ . Два игрока $i {\ displaystyle i}$ $i$ , $j {\ displaystyle j}$ $j$ симметричны, если $v (S ∪ {i}) = v (S ∪ {j}), ∀ S ⊆ N ∖ {я, J} {\ Displaystyle v (S \ чашка \ {я \}) = v (S \ cup \ {j \}), \ forall ~ S \ substeq N \ setminus \ {i, j \}}$ $v (S \ cup \ {i \}) = v (S \ cup \ {j \}), \ forall ~ S \ substeq N \ setminus \ {i, j \}$ ; то есть мы можем обменять одного игрока на другого в любой коалиции, которая содержит только одного из игроков, и не изменить выигрыш.
Аддитивность: распределение игроку в сумме двух игр представляет собой сумму отчисления игроку в каждой отдельной игре. Математически, если $v {\ displaystyle v}$ $v$ и $ω {\ displaystyle \ omega}$ $\ omega$ являются играми, игра $(v + ω) {\ displaystyle (v + \ omega)}$ $(v + \ omega)$ просто назначает любой коалиции сумму выигрышей, которую коалиция получит в двух отдельных играх. Концепция аддитивного решения назначает каждому игроку в $(v + ω) {\ displaystyle (v + \ omega)}$ $(v + \ omega)$ сумму того, что он получит в $v {\ displaystyle v}$ $v$ и $ω {\ displaystyle \ omega}$ $\ omega$ .
Нулевое распределение для нулевых игроков: распределение нулевым игрокам равно нулю. Нулевой игрок $i {\ displaystyle i}$ $i$ удовлетворяет $v (S ∪ {i}) = v (S), ∀ S ⊆ N ∖ {i} {\ displaystyle v (S \ cup \ {i \}) = v (S), \ forall ~ S \ substeq N \ setminus \ {i \}}$ $v (S \ cup \ {i \}) = v (S), \ forall ~ S \ подэтап N \ setminus \ {i \}$ . С экономической точки зрения предельная ценность нулевого игрока для любой коалиции, в которую он не входит, равна нулю.

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

Стабильный набор

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

Стабильно ый набор - это набор вменений, который удовлетворяет характеристикам:

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

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

Свойства

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

Ядро

Пусть $v {\ displaystyle v}$ $v$ будет игрой. ядро в $v {\ displaystyle v}$ $v$ - это набор векторов выигрыша

C (v) = {x ∈ RN: ∑ i ∈ N xi = v (N); ∑ i ∈ S x i ≥ v (S), ∀ S ⊆ N}. {\ 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 \ substeq N \ right \}.}

{\ 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 \ substeq N \ right \}.}

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

Свойства

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

Ядро простые игры по отношению к предпочтениям

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

x ∈ C (v, p) {\ displaystyle x \ in C (v, p)}

x \ in C (v, p)

тогда и только тогда, когда нет

y ∈ X {\ displaystyle y \ в X}

y \ в X

так, что

y ≻ vpx {\ displaystyle y \ succ _ {v} ^ {p} x}

y \ succ _ {v} ^ {p} x

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

Сильное эпсилон-ядро

Времен ядро может быть пустым, в (Шепли и Шубик 1966). Сильное ядро $ε {\ displaystyle \ varepsilon}$ $\ varepsilon$ для некоторого числа $ε ∈ R {\ displaystyle \ varepsilon \ in \ mathbb {R}}$ $\ varepsilon \ в {\ mathbb {R}}$ множество векторов выигрыша

C ε (v) = {x ∈ RN: ∑ i ∈ N xi = v (N); I ∈ S x i ≥ v (S) - ε, ∀ S ⊆ N}. {\ 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 \ substeq N \ right \}.}

C _ {\ varepsilon} (v) = \ left \ {x \ in {\ math bb {R}} ^ {N}: \ sum _ {{i \ in N}} x_ {i} = v (N); \ quad \ sum _ {{i \ in S}} x_ {i} \ geq v (S) - \ varepsilon, \ forall ~ S \ substeq N \ right \}.

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

Значение Шепли

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

Ядро

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

sijv (х) = макс {v (S) - ∑ К ∈ S xk: S ⊆ N ∖ {j}, я ∈ S}, {\ displaystyle s_ {ij} ^ {v} (x) = \ max \ left \ {v (S) - \ sum _ {k \ in S} x_ {k}: S \ substeq N \ setminus \ {j \}, i \ in S \ right \},}

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

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

$(sijv (x) - sjiv (x)) × (xj - v (j)) ≤ 0 {\ Displaystyle (s_ {ij} ^ {v} (х) - s_ {ji} ^ {v} (x)) \ times (x_ {j} -v (j)) \ leq 0}$ $(s _ {{ij}} ^ {v} (x) -s _ {{ji}} ^ {v} (x)) \ times ( x_ {j} -v (j)) \ leq 0$ и
$(sjiv (x) - sijv (x)) × (xi - v (i)) ≤ 0 {\ displaystyle (s_ {ji} ^ {v} (x) -s_ {ij} ^ {v} (x)) \ times (x_ {i} -v (i)) \ leq 0}$ $(s _ {{ji}} ^ {v} (x) -s _ {{ij}} ^ {v} (x)) \ раз (x_ {i} -v (i)) \ leq 0$

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

Ядрышко

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

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

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

Свойства

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

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

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

v (S ∪ T) + v (S ∩ T) ≥ v (S) + v (T), ∀ S, T ⊆ N. {\ displaystyle v (S \ cup T) + v (S \ cap T) \ geq v (S) + v (T), \ forall ~ S, T \ substeq N.}

{\ displaystyle v (S \ чашка T) + v (S \ cap T) \ geq v (S) + v (T), \ forall ~ S, T \ substeq N.}

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

v (S ∪ {i}) - v (S) ≤ v (T ∪ {i}) - v (T), ∀ S ⊆ T ⊆ N ∖ {i}, ∀ i ∈ N; {\ Displaystyle v (S \ чашка \ {я \}) - v (S) \ Leq v (T \ cup \ {я \}) - v (T), \ forall ~ S \ substeq T \ substeq N \ setminus \ {i \}, \ forall ~ i \ in N;}

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

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

Свойства

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

Супермодульность тривиально подразумевает супераддитивность.
Выпуклые игры полностью сбалансированы: ядро выпуклой игры непусто, и поскольку любая под-игра выпуклой игры является выпуклой, ядро любой подигры также не является пустым.
Выпуклая игра имеет уникальный стабильный набор, который совпадает с ее ядром.
значение Шепли выпуклой игры - центр тяжести его ядра.
. Крайняя точка (вершина) ядра может быть найдена за полиномиальное время с помощью жадного алгоритма : Пусть $π: N → N {\ displaystyle \ pi: N \ to N}$ $\ pi: N \ to N$ будет перестановкой игроков, и пусть $S i = { j ∈ N: π (j) ≤ i} {\ displaystyle S_ {i} = \ {j \ in N: \ pi (j) \ leq i \}}$ $S_ {i} = \ {j \ in N: \ pi (j) \ leq i \}$ - упорядоченный набор игроков <35 год 0>1 {\ displaystyle 1} $1$ до $i {\ displaystyle i}$ $i$ в $π {\ displaystyle \ pi}$ $\ pi$ , для любого $i = 0,…, n {\ displaystyle i = 0, \ ldots, n}$ $я = 0, \ ldots, n$ , при $S 0 = ∅ {\ displaystyle S_ {0} = \ emptyset}$ $S_ {0} = \ emptyset$ . Тогда выигрыш $x ∈ RN {\ displaystyle x \ in \ mathbb {R} ^ {N}}$ $x \ in {\ mathbb {R}} ^ {N}$ определяется как $xi = v (S π (i)) - v (S π (я) - 1), ∀ я ∈ N {\ Displaystyle x_ {я} = v (S _ {\ pi (i)}) - v (S _ {\ pi (i) -1}), \ forall ~ я \ in N}$ $x_ {i} = v (S _ {{\ pi (i)}}) - v (S _ {{\ pi (i) -1}}), \ forall ~ i \ in N$ - это вершина ядра в $v {\ displaystyle v}$ $v$ . Любая вершина ядра может быть построена таким образом, выбрав соответствующую перестановку $π {\ displaystyle \ pi}$ $\ pi$ .

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

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

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

См. Также

Ссылки

^Шор, Майк. «Не-совместная игра - теория игр.net». www.gametheory.net. Проверено 15 сентября 2016 г.
^Чандрасекаран, Р. «Теория совместных игр» (PDF).
^Бранденбургер, Адам. «Теория совместных игр: характерные функции, распределение, маржинальный вклад» (PDF). Архивировано из исходного (PDF) 27 мая 2016 года.
^ $2 N {\ displaystyle 2 ^ {N}}$ $2^N$ обозначает набор мощности из $N {\ displaystyle N}$ $N$ .
^Харсани, Джон К. (1982). "Упрощенная модель переговоров для совместной игры n человек". Статьи по теории игр. Библиотека теории и решений. Спрингер, Дордрехт. С. 44–70. DOI : 10.1007 / 978-94-017-2527-9_3. ISBN 9789048183692.
^Задайте функции, игры и возможности при принятии решений | Мишель Грабиш | Спрингер. Библиотека теории и К. решений. Спрингер. 2016. ISBN 9783319306889.
^Георгиос Халкиадакис; Эдит Элкинд; Майкл Дж. Вулдридж (25 октября 2011 г.). Вычислительные аспекты теории кооперативных игр. Издательство Morgan Claypool. ISBN 978-1-60845-652-9.
^Пелег, Б. (2002). «Глава 8 Теоретико-игровой анализ голосование в комитетах». Справочник по социальному выбору и благосостоянию Том 1. Справочник по социальному выбору и благосостоянию. 1 . С. 395–423. DOI : 10.1016 / S1574-0110 (02) 80012-1. ISBN 9780444829146.
^См. раздел теоремы Райса для вычисления вычислимой простые игры. В частности, все конечные игры вычислимы.
^Кумабе, М.; Михара, Х. Р. (2011). «Вычислимость простых игр: полное исследование шестидесяти четырех возможностей» (PDF). Журнал математической экономики. 47 (2): 150–158. arXiv : 1102.4037. Bibcode : 2011arXiv1102.4037K. doi : 10.1016 / j.jmateco.2010.12.003. S2CID 775278.
^Изменено из таблицы 1 в Kumabe and Mihara (2011). Шестнадцать типов четырьмя четырьмя общепринятыми аксиомами (монотонность, правильность, сила и неслабость). Например, тип 1110 указывает на монотонные (1), правильные (1), сильные (1), слабые (0, потому что не неслабые) игры. Среди игр типа 1110 нет конечных невычислимых, есть конечные вычислимые, нет бесконечных невычислимых и нет бесконечных вычислимых. Обратите внимание на то, что, за исключением типа 1110, последние три столбца идентичны.
^Кумабе, М.; Михара, Х. Р. (2008). «Числа Накамуры для вычислимых простых игр». Социальный выбор и благосостояние. 31 (4): 621. arXiv : 1107.0439. DOI : 10.1007 / s00355-008-0300-5. S2CID 8106333.
^Ауман, Роберт Дж. «Ядро совместной игры без побочных выплат.» Труды Американского математического общества (1961): 539-552.
^Питерс, Ханс (2008). Теория игр: многоуровневый подход. Springer. Стр. 123. DOI : 10.1007 / 978-3-540-69291-1_17. ISBN 978-3-540-69290-4.
^Янг, Х. П. (1985-06-01). «Монотонные решения кооперативных игр». Международный журнал теории игр. 14 (2): 65–72. DOI : 10.1007 / BF01769885. ISSN 0020-7276. S2CID 122758426.

Дополнительная литература

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

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

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

Эдмондс, Джек (1970), «Субмодульные функции, матроиды и некоторые многогранники», в Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J. (ред.), Комбинаторные структуры и их приложения, New York: Gordon and Breach, стр. 69–87

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

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

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

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

Люс, RD и Райффа, Х. (1957) Игры и решения: Введение и критический обзор, Wiley Sons. (см. главу 8).
Maschler, M. ; Пелег, Б.; Шепли, Ллойд С. (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

Шмейдлер Д. (1969), "Ядрышко характеристической функциональной игры", SIAM Journal on Applied Mathematics, 17 (6): 1163–1170, doi : 10.1137 / 0117107.

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

Шепли, Ллойд С. (1971), «Ядра выпуклых игр», International Журнал теории игр, 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, 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]