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

Эта статья о теории игр. Информацию о видеоиграх см. в разделе «Кооперативная видеоигра» . Информацию о подобной функции в некоторых настольных играх см. в разделе «Кооперативная настольная игра» .

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

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

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

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

Определение теории кооперативных игр

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

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

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

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

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

Подигры

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

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

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

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

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

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

$v(S\cup T)\geq v(S)+v(T)$ в любое время $S,T\subseteq N$ удовлетворить $S\cap T=\emptyset$.

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

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

$S\subseteq T\Rightarrow v(S)\leq v(T)$.

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

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

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

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

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

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

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

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

Существование простых игр

Тип	Конечный некомп.	Конечная вычислимая	Бесконечный без компа	Бесконечная вычислимость
1111	Нет	Да	Да	Да
1110	Нет	Да	Нет	Нет
1101	Нет	Да	Да	Да
1100	Нет	Да	Да	Да
1011	Нет	Да	Да	Да
1010	Нет	Нет	Нет	Нет
1001	Нет	Да	Да	Да
1000	Нет	Нет	Нет	Нет
0111	Нет	Да	Да	Да
0110	Нет	Нет	Нет	Нет
0101	Нет	Да	Да	Да
0100	Нет	Да	Да	Да
0011	Нет	Да	Да	Да
0010	Нет	Нет	Нет	Нет
0001	Нет	Да	Да	Да
0000	Нет	Нет	Нет	Нет

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

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

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

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

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

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

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

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

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

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

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

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

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

Характеристики

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

Ядро

Основная статья: Core (теория игр)

Позволять $v$ быть игрой. Ядро ​ ​ $v$ — набор векторов выигрышей

$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 ). см . доказательство

Суть простой игры с учетом предпочтений

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

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

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

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

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

$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\}.$

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

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

Основная статья: Значение Шепли

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

Ядро

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

$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 . Максимальный излишек — это способ измерить переговорную власть одного игрока над другим. Ядро ​ ​ $v$ - это набор делений x , которые удовлетворяют

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

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

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

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

${\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}}$

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

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

Ядрышко

Основная статья: Ядрышко (теория игр)

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

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

Характеристики

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

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

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

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

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

$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 ), что приводит к вышеупомянутому эффекту снежного кома. Для игр со стоимостью неравенства меняются местами, так что мы говорим, что игра со стоимостью является выпуклой , если характеристическая функция субмодулярна .

Характеристики

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

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

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

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

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

Связь между теорией кооперативных игр и фирмой

Корпоративные стратегические решения могут способствовать развитию и созданию ценности посредством теории кооперативных игр. Это означает, что теория кооперативных игр может стать стратегической теорией фирмы, а различные решения 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), «Субмодулярные функции и выпуклость», в Бахеме, А.; Гретшель, М .; Корте, Б. (ред.), Математическое программирование – современное состояние , Берлин: Springer, стр. 235–257.

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

• Лукас, Уильям Ф. (1969), «Доказательство того, что игра может не иметь решения», Transactions of the American Mathematical Society , 136 : 219–229, doi : 10.2307/1994798 , JSTOR   1994798 .

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

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

• Осборн, М.Дж. и Рубинштейн, А. (1994) Курс теории игр , MIT Press (см. главы 13,14,15).
• Мулен, Эрве (1988), Аксиомы совместного принятия решений (1-е изд.), Кембридж: Издательство Кембриджского университета , 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$-личные игры», в Кун, Х.; Такер, А.В. (ред.), «Вклад в теорию игр II» , Принстон, Нью-Джерси: Princeton University Press, стр. 307–317.

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

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

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

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

• фон Нейман, Джон ; Моргенштерн, Оскар (1944), «Теория игр и экономического поведения» , Nature , 157 (3981), Princeton: Princeton University Press : 172, Бибкод : 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]