K-ядро

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

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

$s_{ij}^{\nu }(x)=\max \{\nu (S)-\sum _{k\in S}{x}_k:S\subseteq N\setminus \{j\},S\ni i\}$.

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

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

$(s_{ji}^{\nu }(x)-s_{ij}^{\nu }(x))(x_i-\nu (i))\le 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-ядро