Просмотр кода страницы N-ядро

{{нет ссылок|дата=21 февраля 2017}}
'''N-ядро''', '''пред-N-ядро''' ('''nucleolus''', '''prenucleolus''') — [[решения]] [[Кооперативная игра (математика)|кооперативных игр]],
основанные на минимизации степени неудовлетворённости выигрышем подмножеств участников игры (коалиций).

== Формальное определение ==

Обозначим через '''e(x)''' для каждого допустимого распределения выигрышей x в кооперативной игре (N,v)
вектор [[эксцесс коалиции|эксцессов]] всех коалиций, с элементами, упорядоченными по возрастанию.

Рассмотрим некоторое множество распределений выигрышей A. ''N-ядром''
''кооперативной игры относительно множества A'' называется точка x, соответствующая минимуму отношения [[Лексикографический порядок|лексикографического порядка]] на множестве всевозможных векторов '''e(x)''' для x принадлежащих A.

В случае когда множество A совпадает с множеством всех допустимых распределений выигрышей, соответствующее N-ядро называется пред-N-ядром игры (N,v). Если же A совпадает с множеством [[Дележ в кооперативной игре|дележей]], то соответствующее N-ядро называется N-ядром игры (N,v).

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

== История возникновения ==

Впервые N-ядро было введено Шмайдлером (Schmeidler) в 1969 году. Шмайдлер рассматривал именно N-ядро (то есть лексикографический минимум на множестве [[Дележ в кооперативной игре|дележей]], а не всех распределений выигрышей). Впоследствии большее распространение получило пред-N-ядро, ввиду большого количества интересных свойств, однако, так как термин «N-ядро» уже был занят, оно стало называться «пред-N-ядром».

Шмайдлер доказал существование и единственность N-ядра, также показал, что оно лежит в K-ядре и непрерывно зависит от значений характеристической функции игры v.

== Дальнейшие свойства ==

=== Характеризация посредством сбалансированности ===

В 1971 году Колберг доказал элегантную характеризацию пред-N-ядра в терминах [[сбалансированных наборов коалиций]].

Его теорема гласит, что данное распределение выигрышей является N-ядром тогда и только тогда, когда для любого вещественного числа <math>\alpha</math> верно, что набор коалиций с эксцессом больше <math>\alpha</math> является сбалансированным набором.

=== Связь с другими решениями ===

1. Пред-N-ядро всегда содержится в K-ядре. Обычно именно так показывают непустоту K-ядра для любой игры.

2. Если C-ядро непусто, то пред-N-ядро содержится в С-ядре.

=== Другие свойства ===

Пред-N-ядро обладает свойствами [[Анонимное решение кооперативной игры|анонимности]], [[Ковариантное решение кооперативной игры|ковариантности]], удовлетворяет [[Вектор Шепли|аксиоме болвана]] и является [[согласованным решением]] в смысле [[Девиса-Машлера]].

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

Пред-N-ядро отличается от других известных решений неконструктивностью своего определения. Нахождение N-ядра с помощью его определения является весьма трудоемким даже для игр с небольшим числом игроков (так как речь идет о поиске лексикографического минимума на множестве векторов в пространстве размерности <math>2^n</math>, где n равно количеству игроков в игре).

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

== См. также ==

* [[Кооперативная игра (математика)]]
* [[Эксцесс коалиции]]
* [[С-ядро]]
* [[K-ядро]]

{{math-stub}}

{{Теория игр}}

[[Категория:Теория игр]]