N-ядро

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-ядро

Отрывок, характеризующий N-ядро

«Sur ce je prie Dieu, mon ami, de vous avoir sous sa sainte et puissante garde. Votre amie Helene».
[«Затем молю бога, да будете вы, мой друг, под святым сильным его покровом. Друг ваш Елена»]
Это письмо было привезено в дом Пьера в то время, как он находился на Бородинском поле.


Во второй раз, уже в конце Бородинского сражения, сбежав с батареи Раевского, Пьер с толпами солдат направился по оврагу к Князькову, дошел до перевязочного пункта и, увидав кровь и услыхав крики и стоны, поспешно пошел дальше, замешавшись в толпы солдат.
Одно, чего желал теперь Пьер всеми силами своей души, было то, чтобы выйти поскорее из тех страшных впечатлений, в которых он жил этот день, вернуться к обычным условиям жизни и заснуть спокойно в комнате на своей постели. Только в обычных условиях жизни он чувствовал, что будет в состоянии понять самого себя и все то, что он видел и испытал. Но этих обычных условий жизни нигде не было.
Хотя ядра и пули не свистали здесь по дороге, по которой он шел, но со всех сторон было то же, что было там, на поле сражения. Те же были страдающие, измученные и иногда странно равнодушные лица, та же кровь, те же солдатские шинели, те же звуки стрельбы, хотя и отдаленной, но все еще наводящей ужас; кроме того, была духота и пыль.
Пройдя версты три по большой Можайской дороге, Пьер сел на краю ее.
Сумерки спустились на землю, и гул орудий затих. Пьер, облокотившись на руку, лег и лежал так долго, глядя на продвигавшиеся мимо него в темноте тени. Беспрестанно ему казалось, что с страшным свистом налетало на него ядро; он вздрагивал и приподнимался. Он не помнил, сколько времени он пробыл тут. В середине ночи трое солдат, притащив сучьев, поместились подле него и стали разводить огонь.
Солдаты, покосившись на Пьера, развели огонь, поставили на него котелок, накрошили в него сухарей и положили сала. Приятный запах съестного и жирного яства слился с запахом дыма. Пьер приподнялся и вздохнул. Солдаты (их было трое) ели, не обращая внимания на Пьера, и разговаривали между собой.
– Да ты из каких будешь? – вдруг обратился к Пьеру один из солдат, очевидно, под этим вопросом подразумевая то, что и думал Пьер, именно: ежели ты есть хочешь, мы дадим, только скажи, честный ли ты человек?
– Я? я?.. – сказал Пьер, чувствуя необходимость умалить как возможно свое общественное положение, чтобы быть ближе и понятнее для солдат. – Я по настоящему ополченный офицер, только моей дружины тут нет; я приезжал на сраженье и потерял своих.
– Вишь ты! – сказал один из солдат.
Другой солдат покачал головой.
– Что ж, поешь, коли хочешь, кавардачку! – сказал первый и подал Пьеру, облизав ее, деревянную ложку.
Пьер подсел к огню и стал есть кавардачок, то кушанье, которое было в котелке и которое ему казалось самым вкусным из всех кушаний, которые он когда либо ел. В то время как он жадно, нагнувшись над котелком, забирая большие ложки, пережевывал одну за другой и лицо его было видно в свете огня, солдаты молча смотрели на него.
– Тебе куды надо то? Ты скажи! – спросил опять один из них.
– Мне в Можайск.
– Ты, стало, барин?
– Да.
– А как звать?
– Петр Кириллович.
– Ну, Петр Кириллович, пойдем, мы тебя отведем. В совершенной темноте солдаты вместе с Пьером пошли к Можайску.