Кооперативные игры. Смагин Б.И. - 3 стр.

UptoLike

Составители: 

Рубрика: 

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