Русская Википедия:K-ядро

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

<math> ( s_{ij}^\nu(x) - s_{ji}^\nu(x) ) ( x_j - \nu(j) ) \leq 0 </math>;

<math> ( s_{ji}^\nu(x) - s_{ij}^\nu(x) ) ( x_i - \nu(i) ) \leq 0 </math>;

для всех пар игроков <math> i, j </math>.

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

Ссылки

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

См.также

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