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

Игра, в которой группы игроков могут обеспечивать совместное поведение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подигры

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

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

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

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

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

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

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

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

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

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

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

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

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

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}Стабильный набор

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

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

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

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

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

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

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

Значение Шепли — это уникальный вектор выигрыша, который эффективен, симметричен и удовлетворяет монотонности. ^[16] Он был введен Ллойдом Шепли (Shapley 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)}$

Ядрышко

Пусть это игра, и пусть это вектор выигрыша. Избытком для коалиции является количество ; то есть выигрыш, который игроки в коалиции могут получить, если они выйдут из большой коалиции при выплате и вместо этого получат выигрыш . Ядрышко - это дележ , для которого вектор эксцессов всех коалиций (вектор в ) наименьший в порядке лексиминов . Ядрышко было введено (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;}$

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

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

дальнейшее чтение

• Бильбао, Хесус Марио (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), «Ценность игр для людей», Кун, Х.; Такер, А.В. (ред.), «Вклад в теорию игр II» , Принстон, Нью-Джерси: Princeton University Press, стр. 307–317. ${\displaystyle n}$

• Шепли, Ллойд С. (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 , Princeton: Princeton University Press , 157 (3981): 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]