Гедонистическая игра

В теории кооперативных игр гедонистическая игра ^[1]^[2] гедонистической (также известная как игра формирования коалиции ) — игра, которая моделирует формирование коалиций (групп) игроков, когда у игроков есть предпочтения относительно того, к какой группе они принадлежат. Гедонистическая игра определяется путем предоставления конечного набора игроков и для каждого игрока ранга предпочтений среди всех коалиций (подмножеств) игроков, к которым принадлежит игрок. Результатом гедонистической игры является разделение игроков на непересекающиеся коалиции, то есть каждому игроку назначается уникальная группа. Такие разделы часто называют коалиционными структурами.

Гедонистические игры — это разновидность непередаваемых полезных игр . Их отличительная черта («гедонистический аспект»). ^[3]) заключается в том, что игроков заботит только идентичность игроков в их коалиции, но их не волнует, как разделены остальные игроки, и их не волнует ничего, кроме того, какие игроки находятся в их коалиции. Таким образом, в отличие от других кооперативных игр , коалиция не выбирает, как распределять прибыль между своими членами, и не выбирает конкретное действие для игры. Некоторые известные подклассы гедонистических игр представляют собой задачи сопоставления, такие как стабильный брак , стабильные соседи по комнате и проблемы больницы/ординаторов .

Игроки в гедонистических играх обычно понимаются как корыстные, и поэтому гедонистические игры обычно анализируются с точки зрения стабильности коалиционных структур, где используются несколько понятий стабильности, включая стабильность ядра и стабильность по Нэшу . Гедонические игры изучаются как в экономике , где основное внимание уделяется выявлению достаточных условий существования стабильных результатов, так и в многоагентных системах , где основное внимание уделяется выявлению кратких представлений гедонических игр и вычислительной сложности поиска стабильных результатов. . ^[2]

Определение

Формально гедоническая игра – это парная игра. $(N,(\succcurlyeq _{i})_{i\in N})$ конечного множества $N$ игроков (или агентов), и для каждого игрока $i\in N$ отношение полное и транзитивное предпочтения $\succcurlyeq _{i}$ над съемочной площадкой $\{S\subseteq N:i\in S\}$ коалиций этот игрок $i$ принадлежит. Коалиция – это подмножество $S\subseteq N$ из набора игроков. Коалиция $N$ обычно называют большой коалицией .

Коалиционная структура $\pi$ является разделом $N$ . Таким образом, каждый игрок $i\in N$ принадлежит к уникальной коалиции $\pi (i)$ в $\pi$ .

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

Как и в других областях теории игр, результаты гедонистических игр оцениваются с использованием концепций решений. Многие из этих концепций относятся к понятию теоретико-игровой стабильности: результат стабилен, если ни один игрок (или, возможно, ни одна коалиция игроков) не может отклониться от результата, чтобы достичь субъективно лучшего результата. Здесь мы даем определения нескольких концепций решения из литературы. ^[1]^[2]

Коалиционная структура $\pi$ находится в ядре (или ядро стабильно), если нет коалиции $S$ чьи участники все предпочитают $S$ к $\pi$ . Формально непустая коалиция $S$ говорят, что блокирует $\pi$ если $S\succ _{i}\pi (i)$ для всех $i\in S$ . Затем $\pi$ находится в ядре, если нет блокирующих коалиций.
Коалиционная структура $\pi$ находится в строгом ядре (или строго ядро стабильен), если нет слабо блокирующей коалиции $S$ где все участники слабо предпочитают $S$ к $\pi$ и некоторые участники строго предпочитают $S$ к $\pi$ . Другими словами, $\pi$ находится в строгом ядре, если $\not \exists :S\subseteq N:(\forall i\in N:S\succeq \pi )\land (\exists i\in N:S\succ \pi )$ .
Коалиционная структура $\pi$ является стабильным по Нэшу, если ни один игрок не желает менять коалицию внутри $\pi$ . Формально, $\pi$ устойчив по Нэшу, если нет $i\in N$ такой, что $S\cup \{i\}\succ _{i}\pi (i)$ для некоторых $S\in \pi \cup \{\emptyset \}$ . Заметим, что согласно Нэш-стабильности отклонение игрока допускается, даже если члены группы $S$ к которым присоединились $i$ усугубляются отклонениями.
Коалиционная структура $\pi$ индивидуально стабильна, если ни один игрок не желает присоединиться к другой коалиции, все члены которой приветствуют игрока. Формально, $\pi$ индивидуально стабильна, если нет $i\in N$ такой, что $S\cup \{i\}\succ _{i}\pi (i)$ для некоторых $S\in \pi \cup \{\emptyset \}$ где $S\cup \{i\}\succeq _{j}S$ для всех $j\in S$ .
Коалиционная структура $\pi$ является индивидуально стабильным по контракту, если нет игрока, который принадлежит к коалиции, желающей позволить ему уйти, и который хочет присоединиться к коалиции, желающей его получить. Другими словами, $\pi$ является контрактно индивидуально стабильным, если $\not \exists i\in N:(\forall j\in \pi (i):\pi (i)\setminus \{i\}\succeq _{j}\pi (i))~\land ~(\exists C\in \pi :(C\cup \{i\}\succ _{i}\pi (i))~\land ~(\forall j\in C:C\cup \{i\}\succeq _{j}C))$ .

Можно также определить Парето-оптимальность коалиционной структуры. ^[4] В случае, когда отношения предпочтений представлены функциями полезности , можно также рассматривать коалиционные структуры, максимизирующие общественное благосостояние.

Примеры

Следующая игра для трёх игроков была названа « нежеланным гостем ». ^[1] ${\begin{aligned}&\{1,2\}\succ _{1}\{1\}\succ _{1}\{1,2,3\}\succ _{1}\{1,3\},\\&\{1,2\}\succ _{2}\{2\}\succ _{2}\{1,2,3\}\succ _{2}\{2,3\},\\&\{1,2,3\}\succ _{3}\{2,3\}\succ _{3}\{1,3\}\succ _{3}\{3\}.\end{aligned}}$ Из этих предпочтений мы видим, что $1$ и $2$ нравятся друг другу, но не нравится присутствие игрока $3$ .

Рассмотрим раздел $\pi =\{\{1,2\},\{3\}\}$ . Обратите внимание, что в $\pi$ , игрок 3 предпочел бы присоединиться к коалиции $\{1,2\}$ , потому что $\{1,2,3\}\succ _{3}\{3\}$ , и, следовательно, $\pi$ не является устойчивым по Нэшу. Однако, если игрок $3$ должны были присоединиться $\{1,2\}$ , игрок $1$ (а также игрок $2$ ) это отклонение ухудшит ситуацию, и поэтому игрок $3$ Отклонение России не противоречит индивидуальной стабильности. Действительно, это можно проверить $\pi$ является индивидуально стабильным. Мы также видим, что нет никакой группы $S\subseteq N$ игроков так, что каждый член $S$ предпочитает $S$ в свою коалицию в $\pi$ а так раздел тоже есть в ядре.

Другой пример с тремя игроками известен как « двое — компания, трое — толпа ». ^[1] ${\begin{aligned}&\{1,2\}\succ _{1}\{1,3\}\succ _{1}\{1,2,3\}\succ _{1}\{1\},\\&\{2,3\}\succ _{2}\{2,1\}\succ _{2}\{1,2,3\}\succ _{2}\{2\},\\&\{3,1\}\succ _{3}\{3,2\}\succ _{3}\{1,2,3\}\succ _{3}\{3\}.\end{aligned}}$ В этой игре ни один раздел не является стабильным для ядра: раздел $\{\{1\},\{2\},\{3\}\}$ (где все одни) заблокировано $\{1,2,3\}$ ; раздел $\{\{1,2,3\}\}$ (где все вместе) заблокировано $\{1,2\}$ ; а разделы, состоящие из одной пары и синглтона, блокируются другой парой, поскольку предпочтения содержат цикл.

Краткие представления и ограниченные предпочтения

Поскольку отношения предпочтения в гедонической игре определяются над совокупностью всех $2^{|N|-1}$ подмножеств набора игроков, хранение гедонистической игры занимает экспоненциальное пространство. Это вдохновило на создание различных представлений о гедонистических играх, которые являются краткими в том смысле, что они (часто) требуют только полиномиального пространства.

Индивидуально рациональные коалиционные списки ^[5] представляют собой гедонистическую игру, явно перечисляя рейтинги предпочтений всех агентов, но перечисляя только индивидуально рациональные коалиции, то есть коалиции $S$ с $S\succcurlyeq _{i}\{i\}$ . Для многих концепций решения не имеет значения, насколько точно игрок ранжирует неприемлемые коалиции, поскольку ни одна стабильная коалиционная структура не может содержать коалицию, которая не является индивидуально рациональной для одного из игроков. Обратите внимание: если индивидуально рациональных коалиций полиномиально много, то это представление занимает только полиномиальное пространство.
Гедонистические коалиционные сети ^[6] представляют гедонистические игры посредством взвешенных логических формул . Например, взвешенная формула $j\land \lnot k\mapsto _{i}5$ означает, что игрок $i$ получает 5 очков полезности в коалициях, включающих $j$ но не включать $k$ . Этот формализм представления универсально выразителен и часто краток. ^[6] (хотя по необходимости существуют некоторые гедонистические игры, чье сетевое представление гедонистической коалиции требует экспоненциального пространства).
Аддитивно отделимые гедонические игры ^[1] основаны на том, что каждый игрок присваивает числовые значения другим игрокам; коалиция так же хороша для игрока, как и сумма ценностей игроков. Формально аддитивно отделимые гедонические игры — это игры, для которых существуют оценки. $v_{i}(j)\in \mathbb {R}$ для каждого $i,j\in N$ так, что для всех игроков $i$ и все коалиции $S,T\ni i$ , у нас есть $S\succcurlyeq _{i}T$ тогда и только тогда, когда $\textstyle \sum _{j\in S}v_{i}(j)\geq \textstyle \sum _{j\in T}v_{i}(j)$ . Аналогичное определение, использующее среднее, а не сумму значений, приводит к классу дробных гедонических игр. ^[7]
В анонимных гедонистических играх , ^[8] игроков волнует только размер их коалиции, а агентам безразличны любые две коалиции одинаковой мощности: если $|S|=|T|$ затем $S\sim _{i}T$ . Эти игры анонимны в том смысле, что личности участников не влияют на рейтинг предпочтений.
В булевых гедонических играх ^[9] у каждого игрока есть булева формула, переменными которой являются другие игроки. Каждый игрок предпочитает коалиции, удовлетворяющие его формуле, коалициям, которые этого не делают, но в остальном он безразличен.
В гедонистических играх с предпочтениями, зависящими от худшего игрока (или W-предпочтений ^[10]), игроки имеют рейтинг предпочтений перед игроками и распространяют этот рейтинг на коалиции, оценивая коалицию по (субъективно) худшему игроку в ней. несколько подобных понятий (таких как B-предпочтения ). Было определено ^[11]^[12]^[13]

Гарантии существования

Не каждая гедонистическая игра допускает стабильную коалиционную структуру. Например, можно рассмотреть игру «Сталкер» , состоящую всего из двух игроков. $N=\{1,2\}$ с $\{1\}\succ _{1}\{1,2\}$ и $\{1,2\}\succ _{2}\{2\}$ . Здесь мы называем игрока 2 сталкером . Обратите внимание, что ни одна коалиционная структура в этой игре не является устойчивой по Нэшу: в коалиционной структуре $\pi _{1}=\{\{1\},\{2\}\}$ , где оба игрока одни, сталкер 2 отклоняется и присоединяется к 1; в коалиционной структуре $\pi _{2}=\{\{1,2\}\}$ , где игроки вместе, игрок 1 отклоняется в пустую коалицию, чтобы не быть вместе со сталкером. Существует хорошо известный пример проблемы стабильных соседей по комнате с четырьмя игроками и пустым ядром. ^[14] а также существует аддитивно отделимая гедоническая игра с пятью игроками, имеющая пустое ядро и не имеющая индивидуально устойчивых коалиционных структур. ^[15]

Для симметричных аддитивно разделимых гедонических игр (тех, которые удовлетворяют условию $v_{i}(j)=v_{j}(i)$ для всех $i,j\in N$ ), всегда существует устойчивая по Нэшу коалиционная структура по потенциальному функциональному аргументу . В частности, коалиционные структуры, которые максимизируют социальное благосостояние, устойчивы по Нэшу. ^[1] Аналогичный аргумент показывает, что устойчивая по Нэшу коалиционная структура всегда существует в более общем классе гедонических игр, нейтральных по подмножеству . ^[16] Однако существуют примеры симметричных аддитивно разделимых гедонических игр с пустым ядром. ^[8]

Было выявлено несколько условий, гарантирующих существование основной коалиционной структуры. В частности, это относится к гедонистическим играм с общим свойством ранжирования: ^[17]^[18] с высшей коалиционной собственностью, ^[8] с верхней или нижней отзывчивостью, ^[19] с нисходящими отделимыми предпочтениями, ^[20]^[21] и с дихотомическими предпочтениями . ^[9] Более того, было показано, что общее свойство ранжирования гарантирует существование коалиционной структуры, которая одновременно стабильна по ядру, индивидуально стабильна и оптимальна по Парето. ^[22]

Вычислительная сложность

При рассмотрении гедонических игр специалисты в области алгоритмической теории игр обычно интересуются сложностью проблемы поиска коалиционной структуры, удовлетворяющей определенной концепции решения, когда в качестве входных данных задана гедоническая игра (в некотором кратком представлении). ^[2] Поскольку обычно не гарантируется, что данная гедонистическая игра допускает стабильный результат, такие проблемы часто можно сформулировать как проблему принятия решения, предполагающую, допускает ли данная гедонистическая игра какой-либо стабильный результат. Во многих случаях эта проблема оказывается вычислительно неразрешимой. ^[18]^[23] Единственным исключением являются гедонистические игры с общим свойством ранжирования, в которых всегда существует основная коалиционная структура, и ее можно найти за полиномиальное время. ^[17] Однако по-прежнему NP-трудно найти оптимальный по Парето или социально оптимальный результат. ^[22]

В частности, для гедонических игр, заданных индивидуально рациональными коалиционными списками, NP-полно решить, допускает ли игра базовый стабильный, Нэш-стабильный или индивидуально стабильный результат. ^[5] То же самое справедливо и для анонимных игр. ^[5] Для аддитивно разделимых гедонических игр NP-полно определить существование стабильного по Нэшу или индивидуально стабильного результата. ^[15] и завершается для второго уровня полиномиальной иерархии, чтобы решить, существует ли устойчивый по ядру результат, ^[24] даже для симметричных аддитивных предпочтений. ^[25] Эти результаты по твердости распространяются на игры, заданные гедонистическими коалиционными сетями. Хотя стабильные по Нэшу и индивидуально стабильные результаты гарантированно существуют для симметричных аддитивно разделимых гедонических игр, найти их все равно может быть сложно, если оценки $v_{i}(j)$ даны в двоичном формате; проблема PLS-полная . ^[26] Для проблемы стабильного брака стабильный результат может быть найден за полиномиальное время с использованием алгоритма отложенного принятия ; для проблемы стабильных соседей по комнате существование стабильного результата может быть решено за полиномиальное время, если предпочтения строгие, ^[27] но проблема является NP-полной, если разрешены связи предпочтений. ^[28] Гедонистические игры с предпочтениями, основанными на худшем игроке, ведут себя очень похоже на проблемы со стабильными соседями по комнате в отношении ядра, ^[10] но есть результаты по твердости для других концепций решения. ^[13] Многие из предыдущих результатов жесткости можно объяснить с помощью метатеорем о распространении предпочтений в отношении отдельных игроков на коалиции. ^[23]

Приложения

Робототехника

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

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

Используя анонимные гедонистические игры с предпочтением SPAO (Single-Peaked-At-One) , в пределах гарантированно можно найти устойчивый по Нэшу раздел децентрализованных роботов, где каждая коалиция посвящена каждой задаче. $O(n_{a}^{2}d_{G})$ итераций, ^[29] где $n_{a}$ количество роботов и $d_{G}$ их сети связи это диаметр . Здесь следствием SPAO является социальное торможение роботов (т. е. нежелание быть вместе), которое обычно возникает, когда их сотрудничество субаддитивно .

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Богомольная, Анна ; Джексон, Мэтью О. (февраль 2002 г.). «Стабильность гедонистических коалиционных структур». Игры и экономическое поведение . 38 (2): 201–230. CiteSeerX 10.1.1.42.8306 . дои : 10.1006/game.2001.0877 .
^ Перейти обратно: ^а ^б ^с ^д Харис Азиз и Рахул Савани, «Гедонические игры». Глава 15 в: Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )
^ Дрез, Дж. Х.; Гринберг, Дж. (1980). «Гедонические коалиции: оптимальность и стабильность». Эконометрика . 48 (4): 987–1003. дои : 10.2307/1912943 . JSTOR 1912943 .
^ Азиз, Харрис; Брандт, Феликс; Харренштейн, Пол (ноябрь 2013 г.). «Оптимальность по Парето при формировании коалиций». Игры и экономическое поведение . 82 : 562–581. CiteSeerX 10.1.1.228.6696 . дои : 10.1016/j.geb.2013.08.006 . S2CID 6441501 .
^ Перейти обратно: ^а ^б ^с Баллестер, Коралио (октябрь 2004 г.). «NP-полнота в гедонических играх». Игры и экономическое поведение . 49 (1): 1–30. дои : 10.1016/j.geb.2003.10.003 .
^ Перейти обратно: ^а ^б Элкинд, Эдит ; Вулдридж, Майкл (2009). Гедонистические коалиционные сети . ААМАС '09. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем. стр. 417–424. ISBN 978-0-981-73816-1 . {{cite book}}: |journal= игнорируется ( помогите )
^ Азиз, Харис; Брандт, Феликс; Харренштейн, Пол (2014). Дробные гедонические игры . ААМАС '14. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем. стр. 5–12. ISBN 978-1-450-32738-1 . {{cite book}}: |journal= игнорируется ( помогите )
^ Перейти обратно: ^а ^б ^с Банерджи, Сурьяпратим; Кониси, Хидео; Сёнмез, Тайфун (2001). «Ядро в простой игре по формированию коалиции». Социальный выбор и благосостояние . 18 (1): 135–153. CiteSeerX 10.1.1.18.7132 . дои : 10.1007/s003550000067 . ISSN 0176-1714 . S2CID 2822109 .
^ Перейти обратно: ^а ^б Азиз, Харис; Харренштейн, Пол; Ланг, Жером; Вулдридж, Майкл (25 апреля 2016 г.). «Бульевы гедонические игры» . КР'16 Материалы пятнадцатой Международной конференции по принципам представления и рассуждения знаний . Международная конференция по принципам представления и рассуждения знаний . АААИ Пресс. стр. 166–175. arXiv : 1509.07062 .
^ Перейти обратно: ^а ^б Чефларова, Катарина; Хайдукова, Яна (15 апреля 2004 г.). «Стабильные разделы с W-предпочтениями». Дискретная прикладная математика . 138 (3): 333–347. дои : 10.1016/S0166-218X(03)00464-5 .
^ Хайдукова, Яна (1 декабря 2006 г.). «Игры по формированию коалиций: обзор». Международный обзор теории игр . 08 (4): 613–641. дои : 10.1142/S0219198906001144 . ISSN 0219-1989 .
^ Чехларова, Катарина; Хайдукова, Яна (1 июня 2003 г.). «Вычислительная сложность стабильных разделов с B-предпочтениями». Международный журнал теории игр . 31 (3): 353–364. дои : 10.1007/s001820200124 . ISSN 0020-7276 . S2CID 206890693 .
^ Перейти обратно: ^а ^б Азиз, Харис; Харренштейн, Пол; Пырга, Евангелия (2012). Индивидуальная стабильность в гедонических играх в зависимости от лучших или худших игроков . ААМАС '12. Том. 1105. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем. стр. 1311–1312. arXiv : 1105.1824 . Бибкод : 2011arXiv1105.1824A . ISBN 978-0981738130 . {{cite book}}: |journal= игнорируется ( помогите )
^ Гейл, Д.; Шепли, Л.С. (1962). «Прием в колледж и стабильность брака». Американский математический ежемесячник . 69 (1): 9–15. дои : 10.2307/2312726 . JSTOR 2312726 .
^ Перейти обратно: ^а ^б Сун, Шао-Чин; Димитров, Динко (июнь 2010 г.). «Вычислительная сложность в аддитивных гедонических играх». Европейский журнал операционных исследований . 203 (3): 635–639. CiteSeerX 10.1.1.318.6242 . дои : 10.1016/j.ejor.2009.09.004 .
^ Суксомпонг, Варут (ноябрь 2015 г.). «Индивидуальная и групповая стабильность в нейтральных ограничениях гедонистических игр». Математические социальные науки . 78 : 1–5. arXiv : 1804.03315 . doi : 10.1016/j.mathsocsci.2015.07.004 . S2CID 4749111 .
^ Перейти обратно: ^а ^б Фаррелл, Джозеф; Скотчмер, Сюзанна (1988). «Партнерство». Ежеквартальный экономический журнал . 103 (2): 279–297. дои : 10.2307/1885113 . JSTOR 1885113 .
^ Перейти обратно: ^а ^б Вегингер, Герхард Дж. (2013). «Базовая стабильность в формировании гедонистической коалиции». В Боасе, Питер ван Эмде; Гроен, Франс Калифорния; Итальяно, Джузеппе Ф.; Навроцкий, Ежи; Сак, Харальд (ред.). СОФСЭМ 2013: Теория и практика информатики . Конспекты лекций по информатике. Том. 7741. Шпрингер Берлин Гейдельберг. стр. 33–50. arXiv : 1212.2236 . дои : 10.1007/978-3-642-35843-2_4 . ISBN 978-3-642-35842-5 . S2CID 13229559 .
^ Азиз, Харис; Брандл, Флориан (2012). Существование стабильности в играх с образованием гедонических коалиций . ААМАС '12. Том. 1201. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем. стр. 763–770. arXiv : 1201.4754 . Бибкод : 2012arXiv1201.4754A . ISBN 978-0981738123 . {{cite book}}: |journal= игнорируется ( помогите )
^ Бурани, Надя; Цвикер, Уильям С. (февраль 2003 г.). «Игры по формированию коалиций с разделяемыми предпочтениями». Математические социальные науки . 45 (1): 27–52. CiteSeerX 10.1.1.329.7239 . дои : 10.1016/S0165-4896(02)00082-3 .
^ Каракая, Мехмет (май 2011 г.). «Игры с формированием гедонистических коалиций: новое понятие стабильности». Математические социальные науки . 61 (3): 157–165. doi : 10.1016/j.mathsocsci.2011.03.004 . hdl : 11693/21939 .
^ Перейти обратно: ^а ^б Каскурлу, Бугра; Кизилкая, Фатих Эрдем (2019). «О гедонистических играх с общим ранговым свойством» . Алгоритмы и сложность . CIAC 2019. Том. 11485. Рим, Италия: Springer, Cham. стр. 137–148. arXiv : 2205.11939 . дои : 10.1007/978-3-030-17402-6_12 . ISBN 978-3-030-17402-6 . S2CID 159041690 .
^ Перейти обратно: ^а ^б Петерс, Доминик; Элкинд, Эдит (2015). Простые причины сложности гедонических игр . IJCAI'15. Том. 1507. Буэнос-Айрес, Аргентина: AAAI Press. стр. 617–623. arXiv : 1507.03474 . Бибкод : 2015arXiv150703474P . ISBN 978-1-577-35738-4 . {{cite book}}: |journal= игнорируется ( помогите )
^ Вегингер, Герхард Дж. (март 2013 г.). «Результат твердости ядра стабильности в аддитивных гедонистических играх». Математические социальные науки . 65 (2): 101–104. doi : 10.1016/j.mathsocsci.2012.10.001 .
^ Петерс, Доминик (08 сентября 2015 г.). " $\Sigma _{2}^{p}$ -полные задачи по гедоническим играм». arXiv : 1509.02333 [ cs.GT ].
^ Гейринг, Мартин; Савани, Рахул (2010). «Вычисление стабильных результатов в гедонических играх». В Контояннисе, Спирос; Куцупиас, Элиас; Спиракис, Пол Г. (ред.). Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 6386. Шпрингер Берлин Гейдельберг. стр. 174–185. Бибкод : 2010LNCS.6386..174G . дои : 10.1007/978-3-642-16170-4_16 . ISBN 978-3-642-16169-8 .
^ Ирвинг, Роберт В. (декабрь 1985 г.). «Эффективный алгоритм решения проблемы «стабильных соседей по комнате»». Журнал алгоритмов . 6 (4): 577–595. дои : 10.1016/0196-6774(85)90033-1 .
^ Ронн, Эйтан (июнь 1990 г.). «NP-полные задачи устойчивого сопоставления». Журнал алгоритмов . 11 (2): 285–304. дои : 10.1016/0196-6774(90)90007-2 .
^ Перейти обратно: ^а ^б Джанг, И.; Шин, Х.; Цурдос, А. (декабрь 2018 г.). «Анонимная гедоническая игра для распределения задач в крупномасштабной системе с несколькими агентами». Транзакции IEEE в робототехнике . 34 (6): 1534–1548. arXiv : 1711.06871 . дои : 10.1109/TRO.2018.2858292 . ISSN 1552-3098 . S2CID 124328 .

[:0-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж Богомольная, Анна ; Джексон, Мэтью О. (февраль 2002 г.). «Стабильность гедонистических коалиционных структур». Игры и экономическое поведение . 38 (2): 201–230. CiteSeerX 10.1.1.42.8306 . дои : 10.1006/game.2001.0877 .

[:3-2] Перейти обратно: ^а ^б ^с ^д Харис Азиз и Рахул Савани, «Гедонические игры». Глава 15 в: Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432 . ( бесплатная онлайн-версия )

[3] Дрез, Дж. Х.; Гринберг, Дж. (1980). «Гедонические коалиции: оптимальность и стабильность». Эконометрика . 48 (4): 987–1003. дои : 10.2307/1912943 . JSTOR 1912943 .

[4] Азиз, Харрис; Брандт, Феликс; Харренштейн, Пол (ноябрь 2013 г.). «Оптимальность по Парето при формировании коалиций». Игры и экономическое поведение . 82 : 562–581. CiteSeerX 10.1.1.228.6696 . дои : 10.1016/j.geb.2013.08.006 . S2CID 6441501 .

[:2-5] Перейти обратно: ^а ^б ^с Баллестер, Коралио (октябрь 2004 г.). «NP-полнота в гедонических играх». Игры и экономическое поведение . 49 (1): 1–30. дои : 10.1016/j.geb.2003.10.003 .

[:1-6] Перейти обратно: ^а ^б Элкинд, Эдит ; Вулдридж, Майкл (2009). Гедонистические коалиционные сети . ААМАС '09. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем. стр. 417–424. ISBN 978-0-981-73816-1 . {{cite book}}: |journal= игнорируется ( помогите )

[7] Азиз, Харис; Брандт, Феликс; Харренштейн, Пол (2014). Дробные гедонические игры . ААМАС '14. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем. стр. 5–12. ISBN 978-1-450-32738-1 . {{cite book}}: |journal= игнорируется ( помогите )

[:6-8] Перейти обратно: ^а ^б ^с Банерджи, Сурьяпратим; Кониси, Хидео; Сёнмез, Тайфун (2001). «Ядро в простой игре по формированию коалиции». Социальный выбор и благосостояние . 18 (1): 135–153. CiteSeerX 10.1.1.18.7132 . дои : 10.1007/s003550000067 . ISSN 0176-1714 . S2CID 2822109 .

[BHG-9] Перейти обратно: ^а ^б Азиз, Харис; Харренштейн, Пол; Ланг, Жером; Вулдридж, Майкл (25 апреля 2016 г.). «Бульевы гедонические игры» . КР'16 Материалы пятнадцатой Международной конференции по принципам представления и рассуждения знаний . Международная конференция по принципам представления и рассуждения знаний . АААИ Пресс. стр. 166–175. arXiv : 1509.07062 .

[:4-10] Перейти обратно: ^а ^б Чефларова, Катарина; Хайдукова, Яна (15 апреля 2004 г.). «Стабильные разделы с W-предпочтениями». Дискретная прикладная математика . 138 (3): 333–347. дои : 10.1016/S0166-218X(03)00464-5 .

[11] Хайдукова, Яна (1 декабря 2006 г.). «Игры по формированию коалиций: обзор». Международный обзор теории игр . 08 (4): 613–641. дои : 10.1142/S0219198906001144 . ISSN 0219-1989 .

[12] Чехларова, Катарина; Хайдукова, Яна (1 июня 2003 г.). «Вычислительная сложность стабильных разделов с B-предпочтениями». Международный журнал теории игр . 31 (3): 353–364. дои : 10.1007/s001820200124 . ISSN 0020-7276 . S2CID 206890693 .

[:5-13] Перейти обратно: ^а ^б Азиз, Харис; Харренштейн, Пол; Пырга, Евангелия (2012). Индивидуальная стабильность в гедонических играх в зависимости от лучших или худших игроков . ААМАС '12. Том. 1105. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем. стр. 1311–1312. arXiv : 1105.1824 . Бибкод : 2011arXiv1105.1824A . ISBN 978-0981738130 . {{cite book}}: |journal= игнорируется ( помогите )

[14] Гейл, Д.; Шепли, Л.С. (1962). «Прием в колледж и стабильность брака». Американский математический ежемесячник . 69 (1): 9–15. дои : 10.2307/2312726 . JSTOR 2312726 .

[:8-15] Перейти обратно: ^а ^б Сун, Шао-Чин; Димитров, Динко (июнь 2010 г.). «Вычислительная сложность в аддитивных гедонических играх». Европейский журнал операционных исследований . 203 (3): 635–639. CiteSeerX 10.1.1.318.6242 . дои : 10.1016/j.ejor.2009.09.004 .

[16] Суксомпонг, Варут (ноябрь 2015 г.). «Индивидуальная и групповая стабильность в нейтральных ограничениях гедонистических игр». Математические социальные науки . 78 : 1–5. arXiv : 1804.03315 . doi : 10.1016/j.mathsocsci.2015.07.004 . S2CID 4749111 .

[Partnerships-17] Перейти обратно: ^а ^б Фаррелл, Джозеф; Скотчмер, Сюзанна (1988). «Партнерство». Ежеквартальный экономический журнал . 103 (2): 279–297. дои : 10.2307/1885113 . JSTOR 1885113 .

[:9-18] Перейти обратно: ^а ^б Вегингер, Герхард Дж. (2013). «Базовая стабильность в формировании гедонистической коалиции». В Боасе, Питер ван Эмде; Гроен, Франс Калифорния; Итальяно, Джузеппе Ф.; Навроцкий, Ежи; Сак, Харальд (ред.). СОФСЭМ 2013: Теория и практика информатики . Конспекты лекций по информатике. Том. 7741. Шпрингер Берлин Гейдельберг. стр. 33–50. arXiv : 1212.2236 . дои : 10.1007/978-3-642-35843-2_4 . ISBN 978-3-642-35842-5 . S2CID 13229559 .

[19] Азиз, Харис; Брандл, Флориан (2012). Существование стабильности в играх с образованием гедонических коалиций . ААМАС '12. Том. 1201. Ричленд, Южная Каролина: Международный фонд автономных агентов и мультиагентных систем. стр. 763–770. arXiv : 1201.4754 . Бибкод : 2012arXiv1201.4754A . ISBN 978-0981738123 . {{cite book}}: |journal= игнорируется ( помогите )

[20] Бурани, Надя; Цвикер, Уильям С. (февраль 2003 г.). «Игры по формированию коалиций с разделяемыми предпочтениями». Математические социальные науки . 45 (1): 27–52. CiteSeerX 10.1.1.329.7239 . дои : 10.1016/S0165-4896(02)00082-3 .

[21] Каракая, Мехмет (май 2011 г.). «Игры с формированием гедонистических коалиций: новое понятие стабильности». Математические социальные науки . 61 (3): 157–165. doi : 10.1016/j.mathsocsci.2011.03.004 . hdl : 11693/21939 .

[HGCRP-22] Перейти обратно: ^а ^б Каскурлу, Бугра; Кизилкая, Фатих Эрдем (2019). «О гедонистических играх с общим ранговым свойством» . Алгоритмы и сложность . CIAC 2019. Том. 11485. Рим, Италия: Springer, Cham. стр. 137–148. arXiv : 2205.11939 . дои : 10.1007/978-3-030-17402-6_12 . ISBN 978-3-030-17402-6 . S2CID 159041690 .

[:7-23] Перейти обратно: ^а ^б Петерс, Доминик; Элкинд, Эдит (2015). Простые причины сложности гедонических игр . IJCAI'15. Том. 1507. Буэнос-Айрес, Аргентина: AAAI Press. стр. 617–623. arXiv : 1507.03474 . Бибкод : 2015arXiv150703474P . ISBN 978-1-577-35738-4 . {{cite book}}: |journal= игнорируется ( помогите )

[24] Вегингер, Герхард Дж. (март 2013 г.). «Результат твердости ядра стабильности в аддитивных гедонистических играх». Математические социальные науки . 65 (2): 101–104. doi : 10.1016/j.mathsocsci.2012.10.001 .

[25] Петерс, Доминик (08 сентября 2015 г.). " $\Sigma _{2}^{p}$ -полные задачи по гедоническим играм». arXiv : 1509.02333 [ cs.GT ].

[26] Гейринг, Мартин; Савани, Рахул (2010). «Вычисление стабильных результатов в гедонических играх». В Контояннисе, Спирос; Куцупиас, Элиас; Спиракис, Пол Г. (ред.). Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 6386. Шпрингер Берлин Гейдельберг. стр. 174–185. Бибкод : 2010LNCS.6386..174G . дои : 10.1007/978-3-642-16170-4_16 . ISBN 978-3-642-16169-8 .

[27] Ирвинг, Роберт В. (декабрь 1985 г.). «Эффективный алгоритм решения проблемы «стабильных соседей по комнате»». Журнал алгоритмов . 6 (4): 577–595. дои : 10.1016/0196-6774(85)90033-1 .

[28] Ронн, Эйтан (июнь 1990 г.). «NP-полные задачи устойчивого сопоставления». Журнал алгоритмов . 11 (2): 285–304. дои : 10.1016/0196-6774(90)90007-2 .

[Jang_1534–1548-29] Перейти обратно: ^а ^б Джанг, И.; Шин, Х.; Цурдос, А. (декабрь 2018 г.). «Анонимная гедоническая игра для распределения задач в крупномасштабной системе с несколькими агентами». Транзакции IEEE в робототехнике . 34 (6): 1534–1548. arXiv : 1711.06871 . дои : 10.1109/TRO.2018.2858292 . ISSN 1552-3098 . S2CID 124328 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

v т и Темы теории игр
Определения	Игра с пробками Кооперативная игра Определенность Эскалация обязательств Игра развернутой формы Победа первого и второго игрока Сложность игры Графическая игра Иерархия убеждений Информационный набор Игра в нормальной форме Предпочтение Последовательная игра Одновременная игра Выбор одновременного действия Решенная игра Краткая игра Конструкция механизма
Равновесие концепции	Байесовское коррелированное равновесие Байесовское равновесие Нэша Равновесие Бержа Основной Коррелированное равновесие Коалиционно-устойчивое равновесие Нэша Эпсилон-равновесие Эволюционно стабильная стратегия Равновесие Гиббса Устойчивое равновесие Мертенса Марковское совершенное равновесие Равновесие Нэша Парето-эффективность Идеальное байесовское равновесие Правильное равновесие Равновесие квантового ответа Практически идеальный баланс Доминирование риска Равновесие удовлетворенности Самоподтверждающееся равновесие Последовательное равновесие Значение Шепли Сильное равновесие Нэша Совершенство подигры Дрожащая рука, равновесие
Стратегии	Умиротворение Обратная индукция Затенение ставок Сговор Дешевый разговор Деэскалация Сдерживание Эскалация Прямая индукция Мрачный триггер Марковская стратегия Доминирующие стратегии Чистая стратегия Смешанная стратегия Аргумент о краже стратегии Око за око
Классы игр	Аукцион Проблема с переговорами Глобальная игра Непереходная игра Среднее поле игры n игроков игра для Идеальная информация Большая игра Пуассона Потенциальная игра Повторная игра Скрининговая игра Сигнальная игра Строго определенная игра Стохастическая игра Симметричная игра Игра с нулевой суммой
Игры	Идти шахматы Бесконечные шахматы Шашки Аукцион с полной оплатой Дилемма заключенного Игра-обмен подарками Необязательная дилемма заключенного Дилемма путешественника Координационная игра Курица игра многоножка Сигнальная игра Льюиса Дилемма волонтера Долларовый аукцион Битва полов Охота на оленя Соответствующие пенни Ультиматум игра Электронная почтовая игра Камень-ножницы-бумага Пиратская игра Диктатор игра Игра «Общественные блага» Блото игра Война на истощение Проблема с баром Эль-Фарол Ярмарочный отдел Ярмарка разрезания торта Бертран конкурс Конкурс Курно конкурс Штакельберга Тупик Дилемма закусочной Угадайте 2/3 от среднего Кун покер Торговая игра Нэша Индукционные головоломки Доверительная игра Игра Принцесса и монстр Проблема встречи
Теоремы	Теорема согласия Ауманна Народная теория Теорема о минимаксе Nash's theorem Теорема Негамакса Теорема очистки Принцип откровения Теорема Спрэга – Гранди Теорема Цермело
Ключ цифры	Альберт В. Такер Амос Тверски Антуан Огюстен Курно Ариэль Рубинштейн Клод Шеннон Дэниел Канеман Дэвид К. Левин Дэвид М. Крепс Дональд Б. Гиллис Дрю Фуденберг Эрик Маскин Гарольд В. Кун Герберт Саймон Эрве Мулен Джон Конвей Жан Тироль Жан-Франсуа Мертенс Дженнифер Тур Чейес Джон Харсаньи Джон Мейнард Смит Джон Нэш Джон фон Нейман Кеннет Эрроу Кеннет Бинмор Леонид Гурвич Ллойд Шепли Мелвин Дрешер Меррилл М. Флуд Ольга Бондарева Оскар Моргенштерн Пол Милгром Пейтон Янг Райнхард Зельтен Роберт Аксельрод Роберт Ауманн Роберт Б. Уилсон Роджер Майерсон Сэмюэл Боулз Сюзанна Скотчмер Томас Шеллинг Уильям Викри
Разнообразный	Альфа-бета-обрезка Ограниченная рациональность Комбинаторная теория игр Анализ конфронтации сотрудничество Эволюционная теория игр Глоссарий теории игр Список теоретиков игр Список игр по теории игр Безвыходная ситуация Топологическая игра Трагедия общего пользования