prosdo.ru 1 2 ... 16 17
Часть 4. ВЗАИМОДЕЙСТВИЯ: КОНФЛИКТЫ И СОТРУДНИЧЕСТВО


В книге Г. Коэна «Обо всё можно договориться» утверждается: «Успешный подход к пе-реговорам заключается в выяснении того, что в действительности нужно противной стороне, и в доведении до её сознания того, каким образом она могла бы добиться желаемого, не мешая мне получить своё». Эта цитата определяет очень разумный подход к взаимодействию участни-ков с несовпадающими интересами, фокусирующийся на сотрудничестве, а не на соперничест-ве. Мы видим, что взаимодействия самого различного рода, в которых в той или иной степени присутствуют и конфликты, и сотрудничество, встречаются постоянно − и в нашей повседнев-ной жизни, и в профессиональной деятельности, и в окружающей нас действительности. Деле-ние наследства или имущества при разводе, согласование различных точек зрения при принятии решений, спортивные соревнования и творческие конкурсы, выделение квот партиям или терри-ториям в выборном органе, распределение различных видов работ между сотрудниками, доступ к компьютерным ресурсам при работе операционных систем и пользовательских программ, борьба за существование между хищниками и жертвами, переговоры о разоружении между су-пердержавами − всё это примеры взаимодействий, естественно сочетающих конфликты и со-трудничество.

Важность и распространённость таких взаимодействий уже с давних пор привлекали вни-мание представителей различных видов профессиональной деятельности − математиков, управ-ленцев, психологов, политологов, социологов, военных и других специалистов.

На многочисленные ситуации такого типа естественно смотреть с двух разных точек зре-ния, которые условно можно назвать внутренней и внешней. С внутренней точки зрения мы ассоциируем себя с одним из участников взаимодействия (или же на самом деле являемся им), пытаясь добиться наилучших для этого участника результатов, при том, что действия других участников (также преследующих свои цели) от нас не зависят. В силу такой точки зрения эта проблематика ориентирована больше на конфликты, чем на сотрудничество. Она относится к теории игр, является хорошо и подробно исследованной и имеет многочисленные приложения в самых разных реальных ситуациях. С внешней точки зрения мы ассоциируем себя не с одним из участников взаимодействия, а с теми людьми и или ведомствами, которые организуют это взаи-модействие и разрабатывают правила, в рамках которых оно и проистекает. При этом предпола-гается, что результат взаимодействия всех участников, которые преследуют свои индивидуаль-ные цели, будет достаточно разумным с более общей точки зрения, которая больше ориентиро-вана на сотрудничество, чем на конфликт. Люди и организации, заинтересованные в результатах подобных взаимодействия и разрабатывающих их правила, иногда называются метаигроками, что подчёркивает их особую – по сравнению с остальными участниками – роль.


В отличие от теории игр, общей теории взаимодействия с указанной точки зрения нет, од-нако есть важные результаты, полученные в рамках отдельных направлений. Достаточно извест-ным примером такого рода постановок является синтез механизмов в институциональной эко-номике, когда игроками являются экономические агенты, а в роли метаигрока, определяющего правила их взаимодействия, выступает государство (в лице соответствующих властных струк-тур). Однако с такой точки зрения можно рассмотреть и многие другие процессы и явления в са-мых различных сферах. Примером такой постановки является и выработка правил агрегации индивидуальных предпочтений, и разработка систем пропорционального представительства, и правила справедливого дележа, и алгоритмы предоставления вычислительных ресурсов процес-сам в современных ЭВМ, и многие другие ситуации, связанные с разработкой оптимальных или хотя бы разумных правил взаимодействия участников. Некоторые из этих вопросов, наряду с более традиционными постановками теории игр, и составляют материал данной части пособия.

В него входят три главы. Глава 4.1 «Матричные игры» посвящена самому базовому и простому классу игр – конечным играм двух участников с нулевой суммой. В главе 4.2 «Другие игровые модели» рассмотрены – на самом простом уровне – другие классы игр: биматричные и позици-онные. Наконец, в главе 4.3 «Организация взаимодействия» представлены результаты анализа взаимодействия с упомянутой внешней точки зрения в трёх достаточно известных и практичес-ки интересных ситуациях.
Глава 4.1. Матричные игры
1. Понятие матричной игры

2. Решение игры

3. Удаление стратегий

4. Смешанное расширение матричных игр

5. Решение игр размерности 22 и 2n в смешанных стратегиях

6. Предметный указатель
1. Понятие матричной игры

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


В игре участвуют два игрока (скажем, A и B). У каждого игрока имеется конечное число воз-можных действий, которые обычно называются стратегиями. Природа этих действий может быть самой разнообразной, но сама по себе она не имеет значения. Каждый игрок выбирает одну из сво-их стратегий независимо от другого игрока. Реально это значит, что игрок A не знает, какую стра-тегию выбирает игрок B, а игрок B не знает, какую стратегию выбирает игрок A. После того, как оба выбора сделаны, игрок A получает выигрыш, зависящий от обеих выбранных стратегий. Если выигрыш  положительное число, то игрок B платит игроку A соответствующую сумму (в заранее обговорённой валюте); в противном случае игрок A платит игроку B. Игрок A стремится максими-зировать свой выигрыш, а игрок B стремится минимизировать свой проигрыш.

При формальном описании игры в силу конечности множеств стратегий у обоих игроков без ограничения общности можно считать, что сами стратегии задаются натуральными числами от 1 до m у игрока A и от 1 до n у игрока B. Поэтому выигрыш игрока A можно задавать платёжной матрицей Q размера mn: если игроки выбрали стратегии i{1, ..., m} и j{1, ..., n}, то выигрыш игрока A равен числу qij  элементу матрицы Q, стоящему на пересечении i-ой строки и j-го столб-ца. Напомним, что проигрыш игрока B считается равным выигрышу игрока A. Можно считать, что выирыш игрока B при выборе стратегий i{1, ..., m} и j{1, ..., n} равен числу qij. Игры, в которых суммарный выигрыш всех игроков равен нулю, называются играми с нулевой суммой). Таким образом, матричная игра двух лиц является  по определению  игрой с нулевой суммой.
2. Решение игры

В матричной игре с платёжной матрицей Q игрок A стремится максимизировать свой выигрыш при любом выборе стратегии игроком B. Предположим, что он выбирает стратегию i{1, ..., m}. Поскольку игрок A не знает, какую именно стратегию (т.е. какой индекс j) выбрал игрок B, то всё, что он может себе гарантировать  это выгрыш в размере


gi = . (1)

Естественно, что игрок A выберет такую стратегию i{1, ..., m}, которая максимизирует его гарантированный выгрыш gi. Поэтому он выбирает стратегию i*, для которой

= . (2)

Заметим, что при любом i{1, ..., m} выражение , входящее в (2), не зависит от j. Поэтому значение зависит только от платёжной матрицы Q. Любая стратегия i*, удовлетво-ряющая условию (2), называется оптимальной стратегией игрока A (оптимальная стратегия i* может определяться неоднозначно, так как gi может быть максимальным при различных i{1, ..., m}).

Проведённые рассуждения показывают, что именно должен делать игрок А, чтобы до-биться максимально возможного гарантированного выигрыша. Величина , которая определя-ется только по платёжной матрице Q, называется нижней ценой игры и обозначается через V.

Игрок B стремится минимизировать свой проигрыш. Предположим, что он выбирает стра-

тегию j{1, ..., n}. Поскольку игрок B не знает, какую именно стратегию выбрал игрок А, то

всё, что он может себе гарантировать  это проигрыш в размере

fj = . (3)

Естественно, что игрок B выберет такую стратегию j{1, ..., n}, которая минимизирует его га-рантированный выгрыш fj. Поэтому он выбирает стратегию j*, для которой


= . (4)

Как и значение , значение зависит только от платёжной матрицы Q. Любая стратегия j*, удо-влетворяющая условию (4), называется оптимальной стратегией игрока B (оптимальная страте-гия j* может определяться неоднозначно, так как fj может быть минимальным при различных j{1, ..., n}).

Проведённые рассуждения показывают, что именно должен делать игрок B, чтобы до-биться минимально возможного гарантированного проигрыша. Величина , которая определя-ется только по платёжной матрице Q, называется верхней ценой игры и обозначается через V+.

В силу теоремы о минимаксе (см. главу 3.1) для любой матрицы Q имеет место неравенст-во

(5)

или, с учётом (2) и (4),

VV+.

Таким образом, гарантированный выигрыш игрока А не может быть больше гарантированного проигрыша игрока B.

В теории игр особенно важны те случаи, когда нижняя и верхняя цены игры совпадают. Общее значение V = V= V+. называется ценой игры. При этом имеет место следующее

Утверждение 1. 1) V=V+ тогда и только тогда, когда некоторый элемент платёжной матрицы Q является одновременно максимальным в её i*-ой строке и минимальным в её j*-ом столбце, т.е. для любых i{1, ..., m} и j{1, ..., n}


. (6)

2) цена игры V совпадает с ; 3) стратегии i* и j* являются оптимальными ■

Пара стратегий i*, j*, удовлетворяющих требованиям утверждения 1, может определять-ся неоднозначно. Однако для всех таких пар i*, j* элементы платёжной матрицы Q равны одному и тому же числу  цене игры V. Всякий элемент платёжной матрицы Q, который является одновременно максимальным в i*-ой строке и минимальным в j*-ом столбце, называ-ется седловой точкой матрицы Q.

Заметим, что в силу неравенств (6) любому игроку оказывается невыгодным менять опти-мальную стратегию, если другой игрок будет придерживаться своей оптимальной стратегии. Для игрока А это следует из 1-го неравенства, для игрока В  из 2-го неравенства. Именно в силу разумности одновременного выбора игроками в данной ситуации своих оптимальных стратегий, любая пара стратегий i*, j*, удовлетворяющих требованиям утверждения 1, называ-ется решением игры.

Решения существуют далеко не у всех игр рассматриваемого типа. Как выбирать страте-гии в случае отсутствия седловых точек у платёжной матрицы, будет показано в разделе 4 дан-ной главы.

Пример 1. Рассмотрим матричную игру двух лиц со следующей платёжной матрицей:

Q = . (7)

Найдём, в соответствии с формулами (1) и (2), оптимальные стратегии игрока А. По фор-муле (1)


g1 = = min{7, 6, 5, 4} = 4;

g2 = = min{1, 8, 2, 3} = 1;

g3 = = min{8, 1, 3, 2} = 1.

По формуле (2) = max{4, 1, 1}, откуда следует, что оптимальная стратегия i* = 1 и нижняя цена игры V= 4.

Найдём, в соответствии с формулами (3) и (4), оптимальные стратегии игрока В. По фор-муле (3)

f1 = = max{7, 1, 8} = 8;

f2 = = max{6, 8, 1} = 8;

f3 = = max{5, 2, 3} = 5;

f4 = = max{4, 3, 2} = 4.

По формуле (4) = min{8, 8, 5, 4} = 4, откуда следует, что оптимальная стратегия j* = 4 и верхняя цена игры V+= 4.

Таким образом, нижняя цена игры совпадает с верхней ценой. Как и должно быть по ут-верждению 1, цена игры 4 равна = q14. Пара стратегий 1, 4 является решением игры и седловой точкой матрицы Q

Пример 2. Рассмотрим матричную игру двух лиц со следующей платёжной матрицей:

Q = , (8)

все элементы которой, кроме q24, совпадают с соответствующими элементами платёжной матрицы из примера 1.


Найдём, в соответствии с формулами (1) и (2), оптимальные стратегии игрока А. По фор-муле (1)

g1 = = min{7, 6, 5, 4} = 4;

g2 = = min{1, 8, 2, 5} = 1;

g3 = = min{8, 1, 3, 2} = 1.

По формуле (2) = max{4, 1, 1}, откуда следует, что оптимальная стратегия i* = 1 и нижняя цена игры V= 4.

Найдём, в соответствии с формулами (3) и (4), оптимальные стратегии игрока В. По фор-муле (3)

f1 = = max{7, 1, 8} = 8;

f2 = = max{6, 8, 1} = 8;

f3 = = max{5, 2, 3} = 5;

f4 = = max{4, 5, 2} = 5.

По формуле (4) = min{8, 8, 5, 5} = 5, откуда следует, что множеством оптимальных страте-гий j* является множество {3, 4} и верхняя цена игры V+ = 5.

Таким образом, в данном случае, в отличие от примера 1, нижняя цена игры не равна верхней цене. Поэтому для данной платёжной матрицы Q решений игры, как и седловых точек, нет ■

Для любой матричной игры верно следующее



следующая страница >>