K-ядро

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

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

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

[math]\displaystyle{ ( s_{ij}^\nu(x) - s_{ji}^\nu(x) ) ( x_j - \nu(j) ) \leq 0 }[/math];

[math]\displaystyle{ ( s_{ji}^\nu(x) - s_{ij}^\nu(x) ) ( x_i - \nu(i) ) \leq 0 }[/math];

для всех пар игроков [math]\displaystyle{ i, j }[/math].

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