4551
правка
Сложность ядра: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Кооперативная игра с побочными платежами задается парой (N, v), где N = {1, 2, ..., n} – множество игроков, а <math>v: 2^N \to R</math> – характеристическая функция. Для каждой коалиции <math>S \subseteq N</math> значение v(S) интерпретируется как прибыль или затраты, достигнутые коллективными действиями игроков из S без какой-либо помощи игроков из | Кооперативная игра с побочными платежами задается парой (N, v), где N = {1, 2, ..., n} – множество игроков, а <math>v: 2^N \to R</math> – характеристическая функция. Для каждой коалиции <math>S \subseteq N</math> значение v(S) интерпретируется как прибыль или затраты, достигнутые коллективными действиями игроков из S без какой-либо помощи игроков из N \ S. Игра называется ''прибыльной (затратной)'', если v(S) измеряет прибыль (затраты), достигнутые коалицией S. Далее определения даются только для прибыльных игр, для затратных игр справедливы симметричные утверждения. Вектор <math>x = \{ x_1, x_2, ..., x_n \}</math> называется ''дележом'', если он удовлетворяет условиям <math>\sum_{i \in N} x_i = v(N)</math> и <math>\forall i \in N : x_i \ge v( \{ i\} )</math>. Ядро игры (N, v) определяется следующим образом: | ||
C(v) = | |||
<math>C(v) =\{ x \in R^n : x(N) = v(N)</math> и <math>x(S) \ge v(S), \forall S \subseteq N \},</math> | |||
где <math>x(S) = \sum_{i \in S} x_i</math> для <math>S \subseteq N</math>. Игра называется ''сбалансированной'', если ее ядро непусто, и ''полностью сбалансированной'', если каждая подигра (т. е. игра, полученная путем ограничения множества игроков коалицией, а характеристической функции – степенным множеством этой коалиции) сбалансирована. | |||