Ядрышко (теория игр)

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

Фон

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

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

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

Определения

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

Превышение выигрыша вектора $x$ за коалицию $S\subseteq N$ это количество $\mathrm {excess} (x,S):=\sum _{i\in S}x_{i}-v(S)$ . То есть прибыль, которую игроки в коалиции $S$ получить, если они останутся в большой коалиции $N$ и не отклоняться. ^{[примечание 1]}

Позволять $\theta (x)\in \mathbb {R} ^{2^{N}}$ быть вектором эксцессов $x$ , расположенные в неубывающем порядке: $\theta _{i}(x)\leq \theta _{j}(x),\forall ~i<j$ . Для двух векторов выигрышей $x,y$ , мы говорим $\theta (x)$ , лексикографически меньше чем $\theta (y)$ если для некоторого индекса $k$ , у нас есть $\theta _{i}(x)=\theta _{i}(y),\forall ~i<k$ и $\theta _{k}(x)<\theta _{k}(y)$ . Ядрышко $v$ является лексикографически самым большим вменением , основанным на этом порядке. Другими словами, ядрышко представляет собой дележ, вектор избытков которого является наибольшим в порядке лексиминов . Ее можно представить следующей оптимизационной задачей: ${\begin{aligned}\operatorname {lex} \max \min &&\mathrm {excess} (x,S_{1}),\mathrm {excess} (x,S_{2}),\ldots ,\mathrm {excess} (x,S_{k})\\{\text{subject to}}&&x~{\text{is an imputation}}\end{aligned}}$ где к = 2 ^Н = количество возможных коалиций.

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

Ядрышко всегда уникально. Видеть ^[1] и Раздел II.7 ^[2] для доказательства.

Связь с другими концепциями решения

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

Когда ядро пусто, естественно рассмотреть приближение: ε-ядро — это множество всех дележей, в которых избыток каждой коалиции равен не менее — ε . Для каждого ε, если ε-ядро непусто, то ядрышко находится в ε-ядре .
Наименьшее ядро — это наименьшее непустое ε-ядро (для наименьшего ε, для которого ε-ядро непусто). Ядрышко всегда находится в наименее ядровом состоянии. Фактически, ядрышко можно рассматривать как усовершенствованную версию наименьшего ядра. Начиная с наименьшего ядра, запишите коалиции, для которых избыток равен точно - ε . Найдите подмножество наименьшего ядра, в котором наименьший избыток других коалиций будет как можно большим. Повторите этот процесс столько раз, сколько необходимо, пока не будут записаны все коалиции. Результирующим вектором выигрыша является ядрышко.
Ядрышко всегда находится в ядре, а поскольку ядро содержится в переговорном множестве, то оно всегда находится в переговорном множестве (см. ^[2] подробности.)

Вычисление

Общие игры

Общая кооперативная игра n игроков характеризуется 2 ^н ценности - одно значение для каждой возможной коалиции. Ядро общей игры можно вычислить с помощью любого алгоритма лексикографической максиминной оптимизации . Эти алгоритмы обычно требуют решения линейных программ с одним ограничением для каждого целевого значения, а также с некоторыми дополнительными ограничениями. Следовательно, количество ограничений равно O(2 ^н). Число итераций, требуемых более эффективными алгоритмами, не превышает n , поэтому время выполнения равно O( n 2 ^н).

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

Игры с взвешенным голосованием

В с взвешенным голосованием игре каждый игрок имеет вес. Вес коалиции – это сумма весов ее членов. Коалиция может добиться принятия решения, если ее общий вес превышает определенный порог. Следовательно, ценность коалиции равна 1, если ее значение выше порога, и 0, если ее значение ниже порога. Игра с взвешенным голосованием может быть представлена только n +1 значениями: весом для каждого игрока и порогом.

В игре с взвешенным голосованием ядро можно вычислить за полиномиальное от n время . Напротив, алгоритм с наименьшим ядром является NP-сложным, но имеет псевдополиномиальный по времени алгоритм — алгоритм, полиномиальный по и максимальному весу W. n ^[3] Аналогично ядрышко NP-твердое, ^[3] но имеет алгоритм псевдополиномиального времени. ^[4] Доказательство основано на решении последовательных линейных программ экспоненциального размера путем построения динамического программирования на основе оракулов разделения .

Игры на связующем дереве с минимальной стоимостью

В игре связующего дерева с минимальной стоимостью каждый игрок является узлом полного графа . Граф содержит дополнительный узел s ( узел снабжения ). Каждое ребро в графе имеет стоимость. Стоимость каждой коалиции S — это минимальная стоимость связующего дерева, соединяющего все узлы в S с узлом предложения s . Стоимость S стоимость S. минус Таким образом, игру MCST можно представить в виде O(n ²) ценности. ^[5]

Вычисление ядрышка в обычных играх MCST является NP-сложным, ^[6] но его можно вычислить за полиномиальное время, если базовая сеть представляет собой дерево. ^[7]^[8]

Взвешенные кооперативные игры на совпадение

В кооперативных играх с взвешиванием ядрышко можно вычислить за полиномиальное время. ^[9]

Неявно заданная функция значения

В некоторых играх ценность каждой коалиции не указана явно, но ее можно вычислить путем решения набора задач математического программирования. Используя подход генерации ограничений , можно вычислить только те значения коалиций, которые необходимы для ядрышка. Это позволяет эффективно вычислять ядрышко на практике, когда имеется не более 20 игроков. ^[10]

Поттерс, Рейньерс и Ансинг ^[11] представить быстрый алгоритм вычисления ядрышка с использованием расширенного симплекс-алгоритма .

Использование преядра

Если предядро кооперативной игры содержит ровно один кор-вектор, то ядрышко можно вычислить эффективно. ^[12] Алгоритм основан на методе эллипсоидов и схеме Машлера аппроксимации предядра.

Ошибки при вычислении ядрышка

Гуахардо и Йорнстен ^[13] обнаружили ошибки в применении линейного программирования и двойственности к вычислению ядрышка.

Примечания

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

См. также

Спорное правило одежды
Ядрышко против наименьшего ядра ^[14]

Ссылки

^ Jump up to: ^а ^б Шмейдлер, Д. (1969), «Ядрышко характеристической функциональной игры», SIAM Journal on Applied Mathematics , 17 (6): 1163–1170, doi : 10.1137/0117107 .
^ Jump up to: ^а ^б Дриссен, Тео (1988), Совместные игры, решения и приложения , Kluwer Academic Publishers, ISBN 9789401577878
^ Jump up to: ^а ^б Элкинд, Эдит; Голдберг, Лесли Энн; Гольдберг, Пол; Вулдридж, Майкл (22 июля 2007 г.). «Вычислительная сложность игр с взвешенным порогом» . Материалы 22-й Национальной конференции по искусственному интеллекту. Том 1 . АААИ'07. Ванкувер, Британская Колумбия, Канада: AAAI Press: 718–723. ISBN 978-1-57735-323-2 .
^ Элкинд, Эдит; Пасечник, Дмитрий (4 января 2009 г.). Вычисление ядрышка игр с взвешенным голосованием . Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2009 г. Общество промышленной и прикладной математики. стр. 327–335. дои : 10.1137/1.9781611973068.37 . hdl : 10356/93815 . ISBN 978-0-89871-680-1 .
^ Берд, CG (1976). «О распределении затрат для связующего дерева: теоретико-игровой подход» . Сети . 6 (4): 335–350. дои : 10.1002/net.3230060404 .
^ Фэйгл, Ульрих; Керн, Уолтер; Койперс, Йерун (1 декабря 1998 г.). «Вычисление ядрышка в играх на связующем дереве с минимальной стоимостью NP-сложно» . Международный журнал теории игр . 27 (3): 443–450. дои : 10.1007/s001820050083 . ISSN 0020-7276 . S2CID 46730554 .
^ Мегиддо, Нимрод (август 1978 г.). «Вычислительная сложность подхода теории игр к распределению затрат для дерева» . Математика исследования операций . 3 (3): 189–196. дои : 10.1287/moor.3.3.189 . ISSN 0364-765X .
^ Галил, Цви (1 января 1980 г.). «Применение эффективных объединяемых куч для задач оптимизации на деревьях» . Акта Информатика . 13 (1): 53–58. дои : 10.1007/BF00288535 . ISSN 0001-5903 . S2CID 39221796 .
^ Кенеманн, Йохен; Пашкович, Константин; Тот, Джастин (01 сентября 2020 г.). «Вычисление ядрышка взвешенных кооперативных игр за полиномиальное время» . Математическое программирование . 183 (1): 555–581. arXiv : 1803.03249 . дои : 10.1007/s10107-020-01483-4 . ISSN 1436-4646 . S2CID 254135686 .
^ Халлефьорд, Оса; Хельминг, Рейдун; Йорнстен, Курт (1 декабря 1995 г.). «Вычисление ядрышка, когда характеристическая функция задана неявно: подход к созданию ограничений» . Международный журнал теории игр . 24 (4): 357–372. дои : 10.1007/BF01243038 . ISSN 1432-1270 . S2CID 122124918 .
^ Поттерс, Джос AM; Рейньерс, Йоханнес Х.; Ансинг, Мишель (август 1996 г.). «Вычисление ядрышка путем решения алгоритма длительного симплекса» . Математика исследования операций . 21 (3): 757–768. дои : 10.1287/moor.21.3.757 . hdl : 2066/27990 . ISSN 0364-765X .
^ Фэйгл, Ульрих; Керн, Уолтер; Кейперс, Йерун (1 сентября 2001 г.). «О вычислении ядрышка кооперативной игры» . Международный журнал теории игр . 30 (1): 79–98. дои : 10.1007/s001820100065 . ISSN 1432-1270 . S2CID 17702694 .
^ Гуахардо, Марио; Йорнстен, Курт (16 марта 2015 г.). «Распространенные ошибки при вычислении ядрышка» . Европейский журнал операционных исследований . 241 (3): 931–935. дои : 10.1016/j.ejor.2014.10.037 . hdl : 11250/194983 . ISSN 0377-2217 .
^ Ян, Том; Прокачча, Ариэль Д. (18 мая 2021 г.). «Если вам нравится Шепли, то вам понравится ядро» . Материалы конференции AAAI по искусственному интеллекту . 35 (6): 5751–5759. дои : 10.1609/aaai.v35i6.16721 . ISSN 2374-3468 .

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

[schmeidler-1] Jump up to: ^а ^б Шмейдлер, Д. (1969), «Ядрышко характеристической функциональной игры», SIAM Journal on Applied Mathematics , 17 (6): 1163–1170, doi : 10.1137/0117107 .

[driessen-3] Jump up to: ^а ^б Дриссен, Тео (1988), Совместные игры, решения и приложения , Kluwer Academic Publishers, ISBN 9789401577878

[:0-4] Jump up to: ^а ^б Элкинд, Эдит; Голдберг, Лесли Энн; Гольдберг, Пол; Вулдридж, Майкл (22 июля 2007 г.). «Вычислительная сложность игр с взвешенным порогом» . Материалы 22-й Национальной конференции по искусственному интеллекту. Том 1 . АААИ'07. Ванкувер, Британская Колумбия, Канада: AAAI Press: 718–723. ISBN 978-1-57735-323-2 .

[5] Элкинд, Эдит; Пасечник, Дмитрий (4 января 2009 г.). Вычисление ядрышка игр с взвешенным голосованием . Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2009 г. Общество промышленной и прикладной математики. стр. 327–335. дои : 10.1137/1.9781611973068.37 . hdl : 10356/93815 . ISBN 978-0-89871-680-1 .

[:1-6] Берд, CG (1976). «О распределении затрат для связующего дерева: теоретико-игровой подход» . Сети . 6 (4): 335–350. дои : 10.1002/net.3230060404 .

[7] Фэйгл, Ульрих; Керн, Уолтер; Койперс, Йерун (1 декабря 1998 г.). «Вычисление ядрышка в играх на связующем дереве с минимальной стоимостью NP-сложно» . Международный журнал теории игр . 27 (3): 443–450. дои : 10.1007/s001820050083 . ISSN 0020-7276 . S2CID 46730554 .

[8] Мегиддо, Нимрод (август 1978 г.). «Вычислительная сложность подхода теории игр к распределению затрат для дерева» . Математика исследования операций . 3 (3): 189–196. дои : 10.1287/moor.3.3.189 . ISSN 0364-765X .

[9] Галил, Цви (1 января 1980 г.). «Применение эффективных объединяемых куч для задач оптимизации на деревьях» . Акта Информатика . 13 (1): 53–58. дои : 10.1007/BF00288535 . ISSN 0001-5903 . S2CID 39221796 .

[10] Кенеманн, Йохен; Пашкович, Константин; Тот, Джастин (01 сентября 2020 г.). «Вычисление ядрышка взвешенных кооперативных игр за полиномиальное время» . Математическое программирование . 183 (1): 555–581. arXiv : 1803.03249 . дои : 10.1007/s10107-020-01483-4 . ISSN 1436-4646 . S2CID 254135686 .

[11] Халлефьорд, Оса; Хельминг, Рейдун; Йорнстен, Курт (1 декабря 1995 г.). «Вычисление ядрышка, когда характеристическая функция задана неявно: подход к созданию ограничений» . Международный журнал теории игр . 24 (4): 357–372. дои : 10.1007/BF01243038 . ISSN 1432-1270 . S2CID 122124918 .

[12] Поттерс, Джос AM; Рейньерс, Йоханнес Х.; Ансинг, Мишель (август 1996 г.). «Вычисление ядрышка путем решения алгоритма длительного симплекса» . Математика исследования операций . 21 (3): 757–768. дои : 10.1287/moor.21.3.757 . hdl : 2066/27990 . ISSN 0364-765X .

[13] Фэйгл, Ульрих; Керн, Уолтер; Кейперс, Йерун (1 сентября 2001 г.). «О вычислении ядрышка кооперативной игры» . Международный журнал теории игр . 30 (1): 79–98. дои : 10.1007/s001820100065 . ISSN 1432-1270 . S2CID 17702694 .

[14] Гуахардо, Марио; Йорнстен, Курт (16 марта 2015 г.). «Распространенные ошибки при вычислении ядрышка» . Европейский журнал операционных исследований . 241 (3): 931–935. дои : 10.1016/j.ejor.2014.10.037 . hdl : 11250/194983 . ISSN 0377-2217 .

[15] Ян, Том; Прокачча, Ариэль Д. (18 мая 2021 г.). «Если вам нравится Шепли, то вам понравится ядро» . Материалы конференции AAAI по искусственному интеллекту . 35 (6): 5751–5759. дои : 10.1609/aaai.v35i6.16721 . ISSN 2374-3468 .

[1]

[примечание 1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]