Глава 3. Кооперативные решения

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

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

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

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

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

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

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

С математической точки зрения, коалиция представляет собой некоторое подмножество участников игры. Обозначим 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

1-е и 2-е | 3-е	оборона	наступление
оборона	90; 10	50; 50
наступление	50; 50	90; 10

 

 

Таблица 2

1-е и 3-е | 2-е	оборона	наступление
оборона	80; 20	50; 50
наступление	50; 50	80; 20

 

Таблица 3

2-е и 3-е | 1-е	оборона	наступление
оборона	60; 40	50; 50
наступление	50; 50	60; 40

Решение.

Рассмотрим игру, заданную таблицей 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 может служить предметом торга.

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

Определение решения игры

Исход можно считать оптимальным только в том случае, если он может быть реализуем в условиях, когда каждая коалиция выбирает стратегии, направленные на наиболее предпочитаемые ею исходы игры. Будем обозначать S={s} множество всех исходов коалиционной игры, X_K={x_K} множество стратегий коалиции K, S(x_K) подмножество исходов, которые могут реализоваться при использовании коалицией K стратегии x_K.

Введем следующие определения.

Определение 1. Пару (K, x_K), где X_K={x_K} непустое множество, будем называть угрозой против исхода s, если все исходы из подмножества S(x_K) более предпочтительны для коалиции K, чем исход s. Будем в этом случае говорить, что коалиция K имеет угрозу x_K против исхода s.

Определение 2. Пару (Q, x_Q), где X_Q={x_Q} непустое множество, будем называть контругрозой против угрозы (K, x_K), если Q∩K непустое множество и существует по крайней мере один исход s’ из подмножества S(x_K), который менее предпочтителен, чем все исходы из подмножества S(x_Q). Будем в этом случае говорить, что коалиция Q имеет контругрозу x_Q на угрозу x_K коалиции K.

Определение 3. Угроза называется эффективной, если на нее нет контругрозы.

Определение 4. Оптимальными называются те исходы игры, против которых нет эффективных угроз. Множество всех оптимальным решением будем называть V-решением коалиционной игры, или просто решением игры.

Выясним содержательный смысл введенных определений. Пусть s некоторый исход. Если есть коалиция K, которая с помощью стратегии x_K может добиться исходов S(x_K), более благоприятных для нее, чем s, то она заинтересована в в том, чтобы исключить исход s из числа возможных и может это сделать с помощью стратегии x_K. Поэтому x_K является угрозой против исхода s. Но, с другой стороны, само существование коалиции K тоже может находиться под угрозой. Если существует коалиция Q, имеющая общих игроков с коалицией K, и применение коалицией Q некоторой стратегии x_Q приводит к исходам, более благоприятным для Q, чем один из исходов, к которым приводит стратегия x_K, то часть игроков из K может предпочесть участие в коалиции Q. Тогда образование коалиции Q может помешать образованию коалиции K, а значит помешать реализации угрозы x_K против исхода s. Угроза x_K в этом случае не является эффективной, и реализации исхода s ничто не мешает.

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

Пример. Парламент, состоящий из депутатов I={ a,b,c,d,e,f,g } выбирает решения из множества S ={1,2,3,4,5,6,7}. Депутат a предпочитает все исходы 1,2,3 исходу 4, и все исходы 4,5,6 исходу 1. Депутат a может войти в коалицию K={ a,b,c }, которая также предпочитает исходы 1,2,3 исходу 4, и может применить стратегию x_K, в результате которой может реализоваться один из исходов 1,2,3. Но a может войти в коалицию Q={ a, d,e,f,g }, которая предпочитает исходу 1 любой исход из множества исходов {5,6,7}, к которым приводит стратегия x_Q. Другие коалиции кроме K и Q не могут организоваться в силу личных пристрастий депутатов. Является ли исход 4 оптимальным?

Решение.

Депутат a может предпочесть войти в коалицию Q, т.к. у нее есть стратегия x_Q, исключающая неблагоприятный для a исход 1. Следовательно, коалиция K может распасться, и стратегия x_K, угрожающая решению 4 может не осуществиться. Следовательно, исход 4 нельзя исключить из числа потенциально реализуемых, т.е. оптимальных исходов.

⇐ Предыдущая234567891011Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: