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

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

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

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

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

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

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

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

Пред-N-ядро обладает свойствами анонимности,ковариантности, удовлетворяетаксиоме болванаи являетсясогласованным решениемв смыслеДевиса-Машлера.

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

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

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

K-ядро

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

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

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

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

.

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

;

;

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

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