Лекция 6. Биматричные игры
Не все конфликтные ситуации можно представить как игры с нулевой суммой, потому что интересы участников таких конфликтов не всегда противоположны. Обобщением игр с нулевой суммой на случай не противоположных интересов участников являются игры с ненулевой суммой.
Рассмотрим конечную игру с ненулевой суммой, т. е. такую, в которой множества стратегий игроков конечны: будем считать, что первый игрок может выбрать одну из m своих стратегий, обозначенных номерами 
, а второй игрок – одну из n своих стратегий, обозначенных номерами 
. Если первый игрок выбрал свою i-ю стратегию, а второй игрок – свою 
-ю стратегию, то в результате такого совместного выбора первый игрок получает выигрыш 
, а второй игрок – выигрыш 
. При этом не обязательно, чтобы 
, как в матричных играх.
Таким образом, конечная игра с ненулевой суммой полностью определяется двумя матрицами
и 
,
поэтому называется биматричной.
Допустим, матрицы игры выглядят следующим образом:
и 
.
Припишем стратегиям 
, 
( 
) вероятности 
, 
( 
) соответственно.
и 
.
Тогда средний выигрыш игрока 
(первого игрока) равен:
.
Средний выигрыш игрока 
(второго игрока) равен:
.
Биматричная игра, как и матричная, происходит партиями.
Цель каждого игрока – выиграть как можно большую сумму в результате большого числа партий. Понятия чистых и смешанных стратегий игроков в биматричных играх вводятся аналогично тому, как это было сделано в матричных играх.
Если матричные игры являются играми со строгим соперничеством, поскольку выигрыш одного игрока в точности равен проигрышу другого, то в биматричных играх интересы игроков могут быть в большей или меньшей степени близки.
В зависимости от того, запрещено или разрешено сотрудничество игроков, различают некооперативныеи кооперативныеигры.
Анализ биматричной игры в некооперативном варианте сводится к поиску максиминных стратегий игроков, т. е. стратегий, которые обеспечивают игрокам получение максимально возможного гарантированного выигрыша вне зависимости от действий противника.
Множество всевозможных пар смешанных стратегий игроков обозначим
, где
.
Если два игрока выбрали смешанные стратегии 
и 
соответственно, то математические ожидания выигрышей игроков равны
и
.
Важным в теории игр является понятие равновесия.
Говорят, что стратегии игроков 
и 
образуют равновесие Нэша, если никому из игроков не выгодно от них отклоняться при условии, что другой игрок не следует своей равновесной стратегии, т. е. если для любых стратегий 
и 
.
,
.
Теорема существования равновесий. В любой биматричной игре существует хотя бы одно равновесие Нэша.
Найти равновесные ситуации можно следующим образом.
По матрице находим числа 
, 
и решаем систему:
.
По матрице находим числа 
, 
и решаем систему:
.
Изобразив обе полученные кривые в координатах 
, найдем точки пересечения этих кривых, лежащие в квадрате 
, 
, которые определяют равновесные ситуации. Для каждой равновесной ситуации находят средние выигрыши 
и 
.
Критерий равновесия. Стратегии игроков и образуют равновесие Нэша тогда и только тогда, когда при условии использования первым игроком стратегии любая чистая стратегия второго игрока, соответствующая 
, приносит второму игроку один и тот же выигрыш 
, а любая чистая стратегия второго игрока, соответствующая 
, приносит второму игроку выигрыш, не больший , а при условии использования вторым игроком стратегии любая чистая стратегия первого игрока, соответствующая 
, приносит первому игроку один и тот же выигрыш 
, а любая чистая стратегия первого игрока, соответствующая 
, приносит первому игроку выигрыш, не больший .
Доказательство. Пусть пара стратегий первого и второго игрока 
), 
образуют равновесие Нэша, и пусть первый игрок действует в соответствии со стратегией , не отклоняясь от нее.
Предположим, что у второго игрока существуют такие чистые стратегии с номерами 
и 
, что
и
,
где
.
В этом случае второй игрок может отклониться от стратегии и выбрать стратегию 
, которая обеспечит ему больший выигрыш, чем стратегия при условии, что первый игрок не будет отклоняться от стратегии .
Действительно,
Получили противоречие с предположением, что стратегии и образуют равновесие Нэша, которое доказывает теорему.
Максиминные смешанные стратегии первого и второго игроков обеспечивают им гарантированные выигрыши
и 
соответственно вне зависимости от поведения противника.
По-другому максиминные стратегии называются осторожными – смысл этого названия очевиден, и в некооперативном случае игрокам имеет смысл придерживаться своих осторожных стратегий.
Пример 3.1. (Игра «Дилемма заключенных»). Двое преступников (первый и второй игроки), подозреваемые в совместном совершении тяжкого преступления, находятся изолированно друг от друга в предварительном заключении. Прямые улики у следствия отсутствуют, поэтому успех обвинения зависит от того, признаются ли заключенные. У каждого из заключенных есть две стратегии: признаться (первая стратегия) или не признаваться (вторая стратегия). Если оба преступника признаются, то они будут признаны виновными и приговорены к восьми годам заключения. Если ни один из них не признается, то по обвинению в основном преступлении они будут оправданы, но суд все-таки признает их вину в менее значительном преступлении (например, в ношении оружия), в результате чего оба будут приговорены к одному году заключения. Если же признается только один и них, то признавшийся будет освобожден (за помощь следствию), а другой преступник будет приговорен к максимальному сроку заключения – к десяти годам. Требуется определить максиминные стратегии игроков и равновесия Нэша, если такие есть.
Решение 1. Матрицы выигрышей игроков таковы:
и 
Смешанные стратегии игроков представим в виде 
и 
, где 
, 
.
При этом математическое ожидание выигрыша первого игрока равно
.
Аналогично определяется математическое ожидание выигрыша второго игрока:
.
Наилучший гарантированный выигрыш первого игрока равен
Учли, что 
, так как , поэтому вне зависимости от 
будет достигаться при 
, а максиминная стратегия первого игрока, соответствующая этому наилучшему гарантированному выигрышу, 
, т. е. максиминная стратегия первого игрока – признаться и получить восемь лет заключения.
Аналогично находим наилучший гарантированный выигрыш второго игрока
и его максиминную стратегию 
– признаться.
Очевидно, максиминные стратегии образуют равновесие Нэша.
Решение 2.По матрице находим числа 
, 
и решаем систему:
.
где получим 
.
По матрице находим числа 
, 
и решаем систему:
.
где получим .
Тогда средний выигрыш игрока (первого игрока) равен:
.
Средний выигрыш игрока (второго игрока) равен:
.
Очевидно, максиминные стратегии образуют равновесие Нэша.
Пример 3.2 (Игра «семейный спор»). Два игрока (муж и жена) выбирают, где провести вечер. У каждого из них есть две стратегии: выбрать посещение футбольного матча (первая стратегия) или оперного спектакля (вторая стратегия). Полезность совместного похода в театр муж оценивает в одну единицу, а жена в две, полезность совместного похода на футбол, наоборот, жена оценивает в одну единицу, а муж в две. Если же супруги идут в разные места, вечер оказывается испорченным, что соответствует нулевым полезностям для обоих игроков. Требуется определить макси-минные стратегии игроков и равновесия Нэша, если такие есть.
Решение. Составим матрицы выигрышей игроков:
и 
Смешанные стратегии игроков представим в виде и , где , .
При этом математические ожидания выигрышей игроков равны
.
.
Наилучшие гарантированные выигрыши игроков
;
,
а соответствующие максиминные стратегии таковы: 
и 
.
Иным способом:
По матрице находим числа 
, 
и решаем систему:
.
где получим ; 
.
По матрице находим числа 
, 
и решаем систему:
.
где получим ; 
Тогда средний выигрыш игрока (первого игрока) равен:
.
Средний выигрыш игрока (второго игрока) равен:
.
Это означает, что муж должен в 
вечеров выбирать футбол и в 
вечеров театр, а жена должна в вечеров выбирать футбол и в вечеров театр, тогда в среднем и муж, и жена будут выигрывать по за одну партию.
Равновесий Нэша в данной игре целых три:
;
;
.
В отличие от матричных игр, в биматричных играх может оказаться так, что совместное отклонение двумя игроками от равновесий Нэша (или от максиминных стратегий) приводит к увеличению выигрыша обоих игроков. Это иллюстрируется следующими примерами.
Если в примере 3.1 один из игроков будет придерживаться максиминной стратегии и признается, а другой игрок отклонится от своей максиминной стратегии и признаваться не будет, то тот, кто не признается, получит десять лет заключения вместо восьми (в результате его положение ухудшится, а положение его соучастника улучшится).
Существенным отличием биматричных игр от матричных являются то, что возможны ситуации, когда отклонение обоих игроков от максиминных стратегий приводит к увеличению их выигрышей: если в примере 3.1 оба преступника не признаются, то оба получат всего по одному году. Это и является основой дилеммы, которая стоит перед каждым из заключенных: поскольку переговоры друг с другом невозможны, каждый из двух заключенных делает выбор, признаваться или нет, не зная, сознался ли его соучастник.
В примере 3.2 ситуация еще сложнее: участники могут увеличить свои выигрыши, совместно отклонившись от максиминных стратегий, в нескольких ситуациях. Например, если вместо максиминных стратегий и игроки выберут соответственно стратегии и 
, то их выигрыши составят 2 для мужа и 1 для жены (оба эти выигрыша больше ). Но есть и другая ситуация: если вместо максиминных стратегий игроки выберут стратегии 
и 
, то их выигрыши составят 1 для мужа и 2 для жены (что опять превышает максиминные выигрыши). Если переговоры между участниками невозможны, отклоняться от максиминных стратегий опасно, так как даже если есть возможность выиграть больше, эта возможность сопряжена с риском уменьшения выигрыша. Например, если муж выберет театр – , а жена футбол – , или наоборот, то выигрыши обоих игроков будут равны нулю.
Выходом в таких ситуациях является кооперация игроков, т. е. сотрудничество, состоящее в том, что игроки могут договориться о совместном выборе стратегий.
Перейдем к обсуждению возможностей кооперативного поведения игроков.
Ранее предполагалось, что в процессе игры отсутствует явный обмен информацией между участниками. Каждый игрок определял свою линию поведения, исходя из своей функции выигрыша, и, безусловно, основываясь на том, что другие игроки действуют аналогично. При этом считалось, что игроки знают функции выигрыша друг друга, но в непосредственный контакт не вступают.
Между тем в реальных экономических ситуациях участники конфликтов активно взаимодействуют друг с другом: вступают в переговоры, заключают соглашения, создают коалиции, применяют угрозы и подкупы и т. д. Все эти процессы могут в различной степени получать отражения в игровых моделях.
Игры, в которых возможны непосредственные контакты между участниками, называются кооперативными. Если игроки могут вступать в переговоры и образовывать коалиции, то какие исходы могут стать результатом переговоров.
Рассмотрим биматричную игру, в которой выигрыши первого и второго игроков заданы матрицами 
и 
.
Пусть 
и 
– смешанные стратегии игроков. Так как 
, 
, 
, 
, множество всех возможных вариантов пар выигрышей
( 
представляет собой выпуклую оболочку точек плоскости с координатами ( 
), 
и ; эти точки ( ) соответствуют парам выигрышей игроков в случае выбора ими своих чистых стратегий.
При этом точка ( 
) доминирует точку ( 
), если
или 
это означает, что при переходе от первой точки ко второй выигрыш каждого из игроков не уменьшится, и при этом хотя бы у одного из игроков выигрыш увеличится.
Множество точек, оптимальных по Парето (т. е. не доминируемых другими), описывается так:
.
Если выбрать из множества точек, оптимальных по Парето, те точки, в которых выигрыши первого и второго игроков окажутся не меньше их максиминных выигрышей α и β, то получится переговорное множество
.
Игрокам, естественно, имеет смысл выбирать свои оптимальные стратегии, соответствующие точкам из переговорного множества.
Существуют различные способы достижения игроками договоренности о совместном выборе точки из переговорного множества. Самый простой из них заключается в выборе таких чистых стратегий, которые приносят игрокам наибольший суммарный доход, из которого один из игроков платит другому оговоренную сумму. Этот способ, конечно же, предполагает полностью доверительные отношения между игроками.
Если же договориться о выборе точки из переговорного множества игрокам не удается, то можно предложить им применить одну из так называемых арбитражных схем. Например, арбитражная схема Нэша предлагает игрокам выбрать из переговорного множества решение Нэша — такую пару смешанных стратегий, которая доставляет максимум функции Нэша, которая равна произведению превышений выигрышей игроков над гарантированными (минимаксными) выигрышами.
Реализация алгоритма Нэша предполагает решение задачи математического программирования
Целевая функция этой задачи называется функцией Нэша, а оптимальное решение данной — решением Нэша.
Решение этой задачи всегда существует, и если в переговорном множестве V есть хотя бы одна точка 
, такая что 
, то решение задачи единственно.
Пример 3.3 (Игра «Дилемма заключенных» в кооперативном варианте). Требуется найти переговорное множество и решение Нэша в игре, описанной в примере 3.1 (Двое преступников (первый и второй игроки), подозреваемые в совместном совершении тяжкого преступления, находятся изолированно друг от друга в предварительном заключении. Прямые улики у следствия отсутствуют, поэтому успех обвинения зависит от того, признаются ли заключенные. У каждого из заключенных есть две стратегии: признаться (первая стратегия) или не признаваться (вторая стратегия). Если оба преступника признаются, то они будут признаны виновными и приговорены к восьми годам заключения. Если ни один из них не признается, то по обвинению в основном преступлении они будут оправданы, но суд все-таки признает их вину в менее значительном преступлении (например, в ношении оружия), в результате чего оба будут приговорены к одному году заключения. Если же признается только один и них, то признавшийся будет освобожден (за помощь следствию), а другой преступник будет приговорен к максимальному сроку заключения – к десяти годам. Требуется определить максиминные стратегии игроков и равновесия Нэша, если такие есть) при условии, что заключенные могут обмениваться информацией.
Решение. Множество всех возможных пар выигрышей игроков представлено четырехугольником ABCD на рис. 3.1.
| С |
| F |
| D |
| В |
| Е |
| β=-8 |
| α=-8 |
Рис. 3.1 - Множество ожидаемых выигрышей, множество Парето и переговорное множество в кооперативном варианте игры «Дилемма заключенных»
Очевидно, множество Парето соответствует ломаной BCD, а переговорное множество — ломаной ECF.
Прямая, проходящая через точки B(-10, 0) и C(-1, -1), задается уравнением M2 = (‑M1‑10)/9, а прямая, проходящая через точки C(-1, -1) и D(0, -10), — уравнением M2 = ‑9M1 - 10 , поэтому функция Нэша
Функцию Нэша мы рассматриваем на переговорном множестве, т. е. на ломаной ECF, при этом отрезок EC задается уравнением M2 = (-M1 -10)/9 при M1 
[-8, -1], а отрезок CF задается уравнением M2 = -9M1 -10 при M2 = -9M1 -10 [-8, -1] (или, что эквивалентно, при M1 [-1, -2/9]).
Максимум функции Нэша на переговорном множестве достигается в точке 
= -1 (график функции Нэша представлен на рис. 3.2).
При этом 
= -9 -10 = -1.
На рис. 3.1 решение Нэша соответствует точке C, поэтому если заключенные имеют возможность переговариваться, то они могут договориться не признаваться вдвоем, и тогда получат всего по одному году заключения.
| M1 |
Рис. 3.2 – График функции Нэша в кооперативном варианте игры «Дилемма заключенных»
Пример 3.4 (Игра «Семейный спор» в кооперативном варианте). Требуется найти переговорное множество и решение Нэша в игре, описанной в примере 3.2 (Два игрока (муж и жена) выбирают, где провести вечер. У каждого из них есть две стратегии: выбрать посещение футбольного матча (первая стратегия) или оперного спектакля (вторая стратегия). Полезность совместного похода в театр муж оценивает в одну единицу, а жена в две, полезность совместного похода на футбол, наоборот, жена оценивает в одну единицу, а муж в две. Если же супруги идут в разные места, вечер оказывается испорченным, что соответствует нулевым полезностям для обоих игроков. Требуется определить макси-минные стратегии игроков и равновесия Нэша, если такие есть) при условии, что игроки могут обмениваться информацией.
Решение. Множество всех возможных пар выигрышей игроков представлено треугольником OAB на рис. 3.3. Очевидно, и множество Парето, и переговорное множество соответствуют отрезку AB.
Прямая, проходящая через точки A(1, 2) и B(2, 1), задается уравнением M2 = 3 - M1, поэтому функция Нэша
Эта функция достигает максимума при = (-3)/[2×(-1)]=1,5. При этом = 3 ‑ = 1,5.
Точка ( , ) на рис. 3.3 обозначена D. Она находится ровно посередине отрезка AB, поэтому решение Нэша таково: = (1/2,1/2) и 
= (1/2,1/2).
Это означает, что игроки могут договориться выбирать (случайным образом и независимо друг от друга) в половине случаев театр, и в другой половине — футбол, тогда выигрыш каждого составит в среднем 1,5 единицы за один вечер.
| M2 |
| α=2/3 |
| β=2/3 |
| D |
| B |
| A |
Рис 3.3 – Множество ожидаемых выигрышей, множество Парето и переговорное множество в кооперативном варианте игры «Семейный спор»
Пример 3.5. Требуется провести анализ биматричной игры, заданной матрицами
Решение. Пусть р = (р,1 - р) и q= (q,1 - q), где р [0,1], q [0,1], - смешанные стратегии игроков. Тогда математические ожидания выигрышей игроков равны соответственно
(р,q) = 6pq + 9р(1 - q) + 8(1 - p)q + 2(1 - р)(1 - q) = (6-9p)q + 7р + 2,
(р,q) = 9pq + 7р(1 - q) + 4(1 - p)q +10(1 - р)(1 - q) = (8q - 3)р - 6q +10.
Максиминные стратегии игроков определяются из условий
(где максимум достигается при = 2/3),
(где максимум достигается при = 3/8).
Таким образом, максиминные стратегии первого и второго игрока равны р = (2/3,1/3) и q = (3/8,5/8), а их гарантированные выигрыши составляют 20/3 и 31/4 соответственно.
Множество всех возможных пар выигрышей игроков представлено четырехугольником ABCD на рис. 3.4. Очевидно, множество Парето соответствует отрезку BC, а переговорное множество — отрезку EF.
Прямая, проходящая через точки B(6, 9) и C(9, 7), задается уравнением M2 = 13 ‑ 2M1/3, поэтому функция Нэша
N( , 
на отрезке M1 [20/3,63/8] (т. е. на отрезке EF; при M2 = 31/4 значение M1 = 3(13 ‑ 31 / 4) / 2 = 63/8) достигает максимума в точке 
. При этом
. Эта точка на рис. 3.4 обозначена G.
Точка G( 
, 
) является выпуклой комбинацией точек B(6, 9) и C(9, 7), т. е.
откуда λ = 
.
Точка В соответствует выбору обоими игроками своих первых чистых стратегий, точка C соответствует выбору первым игроком своей первой чистой стратегии, а вторым игроком — своей второй чистой стратегии, поэтому точка G соответствует тому, что первый игрок выбирает свою первую чистую стратегию, а второй игрок с вероятностью
выбирает первую чистую стратегию, и с вероятностью
1 - = 
— вторую чистую стратегию.
Таким образом, решение Нэша таково: 
=(1,0), =(83/144,61/144). При этом средний выигрыш первого игрока равен = 349/48, а средний выигрыш второго игрока — = 587/72.
| α=20/3 |
| β=31/4 |
| M1 |
| M2 |
| F |
| G |
| E |
| C |
| D |
| В |
Рис. 3.4 – Множество ожидаемых выигрышей, множество Парето и переговорное множество в примере 3.5
Непрерывные игры
Игра с нулевой или ненулевой суммой называется непрерывной, если множества стратегий участников игры целиком заполняют некоторые отрезки.
Смешанные стратегии в непрерывных играх задаются уже не наборами вероятностей, а функциями (или плотностями) распределения непрерывных случайных величин на соответствующих отрезках. При этом математические ожидания выигрышей из сумм превращаются в интегралы.
Можно доказать, что если в непрерывной игре с нулевой суммой функция выигрыша первого игрока непрерывна по всем переменным, то у игроков есть оптимальные смешанные стратегии.
Рассмотрим пример непрерывной игры с нулевой суммой.
Пример 4.1 (Игра «Шумная дуэль»). В дуэли принимают участие двое. В начальный момент дуэлянты находятся на расстоянии d0 и по команде начинают сближаться. В распоряжении каждого дуэлянта имеется один выстрел, который он может произвести в противника с любого расстояния (конечно при условии, что дуэлянт жив), он может даже подойти к противнику вплотную. Пусть функции pk(d) задают вероятности поражения противника k-м игроком (k = 1, 2) с расстояния d. Предположим, что эти функции непрерывны и убывают на отрезке [0, d0]. Рассматривается шумная дуэль, когда противники слышат выстрелы друг друга. Требуется формализовать поведение игроков в виде непрерывной игры с нулевой суммой и определить оптимальные чистые стратегии игроков (если такие стратегии существуют).
Решение. Стратегии первого и второго игроков определяются выбором чисел
, 
— расстояний, с которых дуэлянты намечают произвести свои выстрелы.
Выигрышем F(x, y) первого дуэлянта, если он стреляет с расстояния x, а его противник — с расстояния y, удобно считать вероятность того, что первый дуэлянт поразит второго. Очевидно,
(Здесь мы учли, что если x < у, и второй игрок промахнется, то первый, услышав выстрел противника, стреляет в него с расстояния 0 вместо x.)
Покажем, что шумная дуэль имеет решение в чистых стратегиях: эти стратегии таковы: 
для первого дуэлянта, для второго, при этом цена игры равна 
[здесь — единственный корень уравнения 
]. Действительно,
Таким образом, 
для любых , , откуда и следует, что ( 
— седловая точка данной игры.
В частности, если меткость игроков одинакова [т. е. 
], то цена игры, очевидно, равна 1/2, а является корнем уравнения 
.
В бесшумной дуэли игроки не слышат выстрелов друг друга, поэтому
Читателю предлагается доказать, что бесшумная дуэль не имеет решений в чистых стратегиях.
Переходя к рассмотрению непрерывных игр с непротивоположными интересами, отметим, что решение Нэша (и в конечных играх, и в непрерывных) имеет серьезный недостаток, который заключается в том, что оно не принимает в расчет угрозы. Это иллюстрирует пример игры «Работодатель — работник», в которой работник имеет возможность установить интенсивность своей работы от 100% (полезность этой ситуации для работника оценивается нулем, а для работодателя прибылью 1 млн. руб.) до 0% (в этом случае работник будет голодать, и полезность этой ситуации для работника оценивается в ‑500 000 руб., а работодатель получит нулевую прибыль). Работодатель может поделиться с работником частью прибыли (если захочет). Минимаксные выигрыши игроков равны нулю, а решение Нэша (в чем мы предлагаем убедиться читателю) состоит в том, что работодатель и работник делят прибыль поровну — по 500 тыс. руб. Однако при этом игнорируется тот факт, что работодатель находится в гораздо более выгодном положении, чем работник. Действительно, работник может воспрепятствовать работодателю, только решившись на очень трудный шаг; угроза прекратить работу с его стороны не очень правдоподобна, и в результате работник, скорее всего, будет продолжать работать за зарплату даже в том случае, если работодатель не будет делиться с ним прибылью. Угроза же работодателя уменьшить сумму, которой он делится с работником, вполне реальна.
Позиционные игры
Все игры, которые рассматривались до сих пор, были заданы в так называемой нормальной форме, которая предполагает, что:
1) задано множество игроков I (не ограничивая общности, можно считать, что k игроков заданы своими номерами, т. е. I = {1, 2, …, k};
2) для каждого игрока 
задано множество возможных стратегий 
;
3) для каждой ситуации (т. е. совместного выбора игроками своих стратегий: 
— первым игроком, 
— вторым, …, 
— k-м игроком) заданы выигрыши игроков: 
— первого, 
— второго, …, 
— k-го, т. е. заданы функции выигрышей.