K-ядро

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

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

$s_{ij}^{\mathrm{\nu <!--\; \nu \; -->}}(x)=max\left\{\mathrm{\nu <!--\; \nu \; -->}(S)-<!--\; -\; -->\underset{k\in <!--\; \in \; -->S}{\sum <!--\; \sum \; -->}{x}_k:S\subseteq <!--\; \subseteq \; -->N\setminus <!--\; \setminus \; -->\{j\},S\ni <!--\; \ni \; -->i\right\}$$s_{ij}^{\nu }(x)=\max \left\{\nu (S)-\sum _{k\in S}x_{k}:S\subseteq N\setminus \{j\},S\ni i\right\}$.

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

$(s_{ij}^{\mathrm{\nu <!--\; \nu \; -->}}(x)-<!--\; -\; -->s_{ji}^{\mathrm{\nu <!--\; \nu \; -->}}(x))(x_j-<!--\; -\; -->\mathrm{\nu <!--\; \nu \; -->}(j))\le <!--\; \le \; -->0$$(s_{ij}^{\nu }(x)-s_{ji}^{\nu }(x))(x_{j}-\nu (j))\leq 0$;

$(s_{ji}^{\mathrm{\nu <!--\; \nu \; -->}}(x)-<!--\; -\; -->s_{ij}^{\mathrm{\nu <!--\; \nu \; -->}}(x))(x_i-<!--\; -\; -->\mathrm{\nu <!--\; \nu \; -->}(i))\le <!--\; \le \; -->0$$(s_{ji}^{\nu }(x)-s_{ij}^{\nu }(x))(x_{i}-\nu (i))\leq 0$;

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

Интуитивно, игрок $i$$i$ имеет большую переговорную силу, чем игрок $j$$j$ при дележе $x$$x$, если $s_{ij}^{\mathrm{\nu <!--\; \nu \; -->}}(x)>s_{ji}^{\mathrm{\nu <!--\; \nu \; -->}}(x)$$s_{ij}^{\nu }(x)>s_{ji}^{\nu }(x)$, но игрок $j$$j$ защищен от угроз игрока $i$$i$, если $x_j=\mathrm{\nu <!--\; \nu \; -->}(j)$$x_{j}=\nu (j)$, так как в этом случае он может получить выигрыш $x_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-ядро