4551
правка
Сложность ядра: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Сбалансированность; наименьшее ядро == Постановка задачи ==…») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Кооперативная игра с побочными платежами задается парой (N, v), где N = {1, 2, ..., n} – множество игроков, а v: | Кооперативная игра с побочными платежами задается парой (N, v), где N = {1, 2, ..., n} – множество игроков, а <math>v: 2^N \to R</math> – характеристическая функция. Для каждой коалиции <math>S \subseteq N</math> значение v(S) интерпретируется как прибыль или затраты, достигнутые коллективными действиями игроков из S без какой-либо помощи игроков из NnS. Игра называется прибыльной (затратной), если v(S) измеряет прибыль (затраты), достигнутые коалицией S. Далее определения даются только для прибыльных игр, для затратных игр справедливы симметричные утверждения. Вектор x = fx1; x2; - - - ; xng называется дележом, если он удовлетворяет условиям Pi2Nxi = v(N) и 8i 2 N : xi > v(fig): xi > v(fig). Ядро игры (N, v) определяется следующим образом: | ||
C(v) =fx 2 Rn : x(N) = v(N) и x(S) > v(S); 8S С Ng; где x(S) = Pi2S xi для S С N. Игра называется сбалансированной, если ее ядро непусто; и полностью сбалансированной, если каждая подигра (т. е. игра, полученная путем ограничения множества игроков коалицией, а характеристической функции – степенным множеством этой коалиции) сбалансирована. | C(v) =fx 2 Rn : x(N) = v(N) и x(S) > v(S); 8S С Ng; где x(S) = Pi2S xi для S С N. Игра называется сбалансированной, если ее ядро непусто; и полностью сбалансированной, если каждая подигра (т. е. игра, полученная путем ограничения множества игроков коалицией, а характеристической функции – степенным множеством этой коалиции) сбалансирована. | ||