K-ядро

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

Пусть задана кооперативная игра с характеристической функцией $\nu : 2^N \to \mathbb{R}$ и $x \in \mathbb{R}^N$ — эффективный вектор выигрышей. Максимальный излишек игрока $i$ над игроком $j$ по отношению к $x$ определяется как

$s_{ij}^\nu(x) = \max \left\{ \nu(S) - \sum_{ k \in S } x_k : S \subseteq N \setminus \{ j \}, S \ni i \right\}$.

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

$( s_{ij}^\nu(x) - s_{ji}^\nu(x) ) ( x_j - \nu(j) ) \leq 0$;

$( s_{ji}^\nu(x) - s_{ij}^\nu(x) ) ( x_i - \nu(i) ) \leq 0$;

для всех пар игроков $i, j$.

Интуитивно, игрок $i$ имеет большую переговорную силу, чем игрок $j$ при дележе $x$, если $s_{ij}^\nu(x) > s_{ji}^\nu(x)$, но игрок $j$ защищен от угроз игрока $i$, если $x_j = \nu(j)$, так как в этом случае он может получить выигрыш $x_j$ без кооперации. K-ядро содержит все дележи, при которых ни один игрок не имеет такой переговорной силы ни над каким другим игроком.

Ссылки

• Davis, M., Maschler, M. The kernel of a cooperative game // Naval Research Logistics Quarterly. — 1965. — Vol.12. — P. 223–259.

См.также

• Кооперативная игра (математика)
• С-ядро
• N-ядро