ВУЗ:
Составители:
Рубрика:
3
1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ
КООПЕРАТИВНЫХ ИГР
Игра называется кооперативной, если в ней игрокам разрешается об-
суждать перед игрой свои стратегии и договариваться о совместных дейст-
виях (добровольный обмен между игроками информацией, совместный
выбор стратегий, передача игроками части выигрыша друг другу и т.п.);
иначе говоря, игроки могут образовывать коалиции. Теория кооператив-
ных игр исследует типы коалиций, образующихся в процессе игры и усло-
вия, необходимые для их устойчивого существования.
Обозначим через N множество всех игроков, причем игроков приня-
то различать по их номерам, т.е. N={1,2,...,n}, а через S – любое его под-
множество, которое является коалицией. Очевидно, что число коалиций,
состоящих из k игроков, равно числу сочетаний из n по k, то есть
k
n
C
, а
число всевозможных коалиций равно
n
k
2C
n
0
k
n
=
∑
=
Из этой формулы видно, что число всевозможных коалиций значи-
тельно растёт в зависимости от количества n всех игроков в данной игре.
Образовав коалицию, множество игроков S действует как один игрок про-
тив остальных игроков, и выигрыш этой коалиции зависит от применяе-
мых стратегий каждым из n игроков. Общность интересов игроков из S оз-
начает, что выигрыш объединенного игрока есть сумма выигрышей со-
ставляющих его игроков из S.
Пусть игроки из N, образуя различные коалиции, могут получать не-
которые сравнимые между собой выигрыши. Обозначим выигрыш, кото-
рый может уверенно обеспечить себе коалиция S ⊂ N, через V(S). Функция
V, ставящая в соответствие каждой коалиции S наибольший уверенно по-
лучаемый ею выигрыш V(S), называется характеристической функцией.
Если для всех непересекающихся подмножеств А и В выполняется
неравенство
V(A ∪ B) ≥ V(A) + V(B) (1),
то характеристическая функция является супераддитивной. Свойство су-
пераддитивности означает, что если нет ни одного игрока, который входил
бы одновременно в обе коалиции А и В, то коалиция, составленная как
объединение этих двух подмножеств, будет иметь выигрыш не меньший,
чем сумма выигрышей А и В. Предположение о супераддитивности явля-
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ
КООПЕРАТИВНЫХ ИГР
Игра называется кооперативной, если в ней игрокам разрешается об-
суждать перед игрой свои стратегии и договариваться о совместных дейст-
виях (добровольный обмен между игроками информацией, совместный
выбор стратегий, передача игроками части выигрыша друг другу и т.п.);
иначе говоря, игроки могут образовывать коалиции. Теория кооператив-
ных игр исследует типы коалиций, образующихся в процессе игры и усло-
вия, необходимые для их устойчивого существования.
Обозначим через N множество всех игроков, причем игроков приня-
то различать по их номерам, т.е. N={1,2,...,n}, а через S – любое его под-
множество, которое является коалицией. Очевидно, что число коалиций,
k
состоящих из k игроков, равно числу сочетаний из n по k, то есть Cn , а
число всевозможных коалиций равно
n
∑C
k =0
k
n = 2n
Из этой формулы видно, что число всевозможных коалиций значи-
тельно растёт в зависимости от количества n всех игроков в данной игре.
Образовав коалицию, множество игроков S действует как один игрок про-
тив остальных игроков, и выигрыш этой коалиции зависит от применяе-
мых стратегий каждым из n игроков. Общность интересов игроков из S оз-
начает, что выигрыш объединенного игрока есть сумма выигрышей со-
ставляющих его игроков из S.
Пусть игроки из N, образуя различные коалиции, могут получать не-
которые сравнимые между собой выигрыши. Обозначим выигрыш, кото-
рый может уверенно обеспечить себе коалиция S ⊂ N, через V(S). Функция
V, ставящая в соответствие каждой коалиции S наибольший уверенно по-
лучаемый ею выигрыш V(S), называется характеристической функцией.
Если для всех непересекающихся подмножеств А и В выполняется
неравенство
V(A ∪ B) ≥ V(A) + V(B) (1),
то характеристическая функция является супераддитивной. Свойство су-
пераддитивности означает, что если нет ни одного игрока, который входил
бы одновременно в обе коалиции А и В, то коалиция, составленная как
объединение этих двух подмножеств, будет иметь выигрыш не меньший,
чем сумма выигрышей А и В. Предположение о супераддитивности явля-
3
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
