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

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

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

K-ядро

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

K-ядро (от англ. kernel) — принцип оптимальности в кооперативных играх, впервые введен в работе М. Дэвиса и М. Машлера (1965).

Пусть задана кооперативная игра с характеристической функцией и — эффективный вектор выигрышей. Максимальный излишек игрока над игроком по отношению к определяется как

.

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

;

;

для всех пар игроков .

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