Понятие коалиционной игры

В экономике отдельные субъекты редко действуют поодиночке. Чаще всего они объединяются в союзы, коллективы, кооперации для достижения своих целей. Интуиция и практика показывают, что коллективные действия могут существенно увеличивать эффективность их участников. Коллективные действия можно разделить на три ступени взаимодействия:

а) обмен информацией;

б) совместный выбор стратегий участников (договор о совместных действиях);

в) объединение ресурсов и последующий выбор совместных действий на основе объединенных ресурсов.

Математические модели конфликтов, участники которых могут предпринимать коллективные действия, изучаются в теории коалиционных игр. Коалиционной игрой называется игра с непротивоположными интересами, в которой игроки могут обсуждать перед игрой свои стратегии, договариваться о совместных действиях, заключать союзы (коалиции) для объединения ресурсов.

Коалиция представляет собой добровольное объединение участников игры, согласившихся осуществлять совместные действия (совместные стратегии). Объединение игроков в коалицию означает их сотрудничество, согласие по поводу выбора общего, т.е. кооперативного решения. Общее решение всех участников коалиции определяет стратегию коалиции. Возможны случаи, когда участники игры объединяются в коалицию только для осуществления коалиционной стратегии, а после этого коалиция распадается.

С математической точки зрения, коалиция представляет собой некоторое подмножество участников игры. Обозначим I={i} (i=1, 2, …n) множество игроков, произвольную коалицию будем обозначать K. Общее число всех возможных коалиций, т.е. всех подмножеств множества I, включая пустое подмножество, равно , где – число сочетаний m по n. Число сочетаний является количеством всех всевозможных коалиций на множестве из n игроков, в каждую из которых входят m участников.

Формальное описание полностью определенной коалиционной игры можно задать с помощью следующих параметров:

1. Множество участников .

2. Множество всех коалиций K где отдельная коалиция K является подмножеством множества т.е. , включая пустое множество игроков.

K – коалиционное разбиение множества игроков.

3. Для каждой коалиции K должно быть определено множество (набор) стратегий X_K={x_K}

4. Множество исходов игры S=∏ X_K, где исход s€S определяется выбором коалициями своих стратегий x_K.

5. Для каждого исхода игры s€S и каждой коалиции K определён общий выигрыш коалиции H_K(s).

6. K определена схема дележа выигрыша коалиции H_K(s) между участниками коалиции при каждом исходе x

H_K(s)=∑ h_i(s)

где h_i(s) – выигрыш игрока i из коалиции K.

Исход коалиционной игры при заданных стратегических возможностях всех игроков определяется, во-первых, разбиением множества игроков на коалиции, (т.е. коалиционным разбиением K множества I), во-вторых, множествами возможных стратегий каждой из коалиций, в-третьих, стратегиями, которые коалиции выбирают из своих наборов стратегий.

Игровые возможности каждой отдельной коалиции K могут быть определены с помощью ее характеристической функции v_K, равной гарантированному математическому ожиданию выигрыша данной коалиции при применении смешанной стратегии, составленной из стратегий X_K={x_K}.

Смысл характеристической функции поясним на следующем примере.

Пример «Война за ресурс»

Три королевства борются за владение нефтяным месторождением. Если они договорятся о долевой эксплуатации, то их суммарный доход составит 111 единиц. Если два королевства объединятся для войны против третьего, то с учетом издержек на ведение войны суммарный доход уменьшится. Пусть каждая из двух образовавшихся коалиций имеет две стратегии – оборонительную и наступательную. Для коалиционного разбиения {1-е и 2-е} против {3-го} доходы сторон в зависимости от исходов игры приведены в таблице 1. Для коалиционного разбиения {1-е и 3-е} против {2-го} доходы сторон в зависимости от исходов игры приведены в таблице 2. Для коалиционного разбиения {2-е и 3-е} против {1-го} доходы сторон в зависимости от исходов игры приведены в таблице 3. Если каждое королевство будет воевать против двух других, то в результате 1-е получит доход 30 единиц, 2-е и 3-е получат по 15 единиц. Найдем характеристические функции каждой из коалиций.

Таблица 1

Таблица 2

Таблица 3

Решение.

Рассмотрим игру, заданную таблицей 1. Легко обнаружить, что в игре нет равновесий по Нэшу в чистых стратегиях и найти равновесные смешанные стратегии каждого их игроков x^*= {1/2; 1/2}, y^*= {1/2; 1/2}. При этих стратегиях все исходы равновозможны, следовательно, гарантированное ожидание выигрыша коалиции {1-е и 2-е}, т.е. характеристическая функция v{1-е и 2-е} =(90+50+50+90)/4=70. Характеристическая функция коалиции, состоящей из одного игрока (3-е королевство) v{3-е} =(10+50+50+10)/4=30.

Аналогично, из таблицы 2 находим характеристические функции

v{1-е и 3-е} =(80+50+50+80)/4=65, v{2-е} =(20+50+50+20)/4=35.

Из таблицы 3 находим характеристические функции

v{2-е и 3-е} =(60+50+50+60)/4=55, v{1-е} =(40+50+50+40)/4=45.

Война всех против всех будет невыгодна каждой из рассмотренных коалиций, т.к. в ней соответствующие характеристические функции принимают меньшие значения. Наконец, при договоре о долевой эксплуатации месторождения, коалиционное разбиение имеет вид

K= {1-е и 2-е и 3-е }UΩ, характеристическая функция коалиции {1-е и 2-е и 3-е} равна 111.

По отношению к коалиционной игре большое значение имеют следующие вопросы:

1) При каких условиях данный игрок вступает в ту или иную коалицию?

2) Как следует производить делёж общего выигрыша между членами одной коалиции?

3) Насколько устойчивы различные коалиции, и что влияет на их устойчивость?

4) Каким условиям должен соответствовать механизм принятия решений в отдельной коалиции?

В рассмотренном выше примере легко найти ответы на первые два вопроса. 1-е королевство, действуя в одиночку против двух других, получает гарантированное математическое ожидание дохода, равное 45, 2-е – 35, 3-е – 30. Если королевства являются рациональными игроками, то они будут вступать в коалиции только в тех случаях, когда их доли в дележе будут не меньше значений 45, 35 и 30 соответственно. Коалиции из двух игроков не могут обеспечить такие значения: v{1-е и 2-е} =70< 45+35 и т.д. Единственным разумным коалиционным решением будет объединение всех трех в одну коалицию. Дележ 111 единиц между членами коалиции должен обеспечивать участникам доли, не меньшие тех, которые они получили бы, действуя в одиночку, т.е. v{1-е и 2-е и 3-е} =111=45+35+30+1, оставшаяся 1 может служить предметом торга.

Для общего случаякоалиционнойигрыответы на эти вопросы не так очевидны и требуют введения дополнительных понятий.