Развитие теории. 
Биматричные игры

В результате освоения данной главы студент должен:

знать

• • определения понятий «биматричная игра», «доминирование», «рационализация», «наилучший ответ», «никогда не лучший ответ» ;
• • конкретные примеры биматричных игр;
• • основные свойства процедур исключения доминируемых стратегий и рационализации игры;

уметь

• применять концепции доминирования и рационализации в процедурах анализа биматричных игр;

владеть

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

Биматричными играми будем называть игры двух лиц с конечными множествами стратегий.

В биматричной игре матрица, А =? ?m?n определяет полезности (платежи, выигрыши) игрока 1, а матрица В =? ?m?n — полезности игрока 2 для ситуации, в которой игрок 1 применяет свою i-ю стратегию (из множества допустимых стратегий {1,2,…, i,…, m}), а игрок 2 — j-ю стратегию (из множества допустимых стратегий {1,2,…, i,…, n}).

С одной стороны, биматричные игры являются «естественным» развитием матричных игр, с другой — они уже не относятся к классу игр с нулевой суммой, поскольку в них не требуется, чтобы выигрыш одного игрока компенсировался проигрышем другого.

Хрестоматийным примером биматричной игры является игра, известная как «дилемма заключенного». Ее фабула состоит в том, что имеются два преступника, связанные некоторым общим преступлением. Они задержаны властями и содержатся изолированно друг от друга. Каждый из них ставится перед выбором:

• • «С» — сознаться (пойти на сотрудничество с властями, предать подельника);
• • «М» — молчать (не сотрудничать с властями, не предавать).

Ситуации в игре определяют сроки наказания (тюремного заключения). Предполагается, что если оба преступника не сознаются, то каждый из них получает некоторое символическое наказание (допустим, один год тюремного заключения). Если сознается только один, то его отпускают, по его несознавшийся (и, в общем-то, преданный!) подельник получает максимальное наказание (например, десять лет заключения). Наконец, если сознаются оба одновременно, то им назначают среднее наказание (в предложенных масштабах — пять лет заключения). В табл. 2.1 сроки заключения обозначены соответствующими отрицательными числами.

Таблица 2.1

Игра «дилемма заключенного» .

Данная задача была впервые сформулирована в 1950 г. Мерилом Фладом (Merrill Flood) и Мелвином Дрешером (Melvin Dresher). Свое нынешнее название она получила благодаря канадскому математику Альберту Такеру (Albert W. Tucker), известному своими выдающимися результатами в области нелинейного программирования, теории игр и топологии [18].

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

Рассмотрим некоторую игру в нормальной форме Г = (I, { }_iII, { (s)}_iII). Договоримся о возможности представлення произвольной ситуации в данной игре в виде.

(2.1).

где — это некоторая стратегия, выбраиная (в рамках ситуации s) i-м игроком, а , означает выбор, сделанный всеми остальными участниками игры. Если число игроков конечно и равно m, то , представляет собой вектор размерности (m — 1). В общем случае.

Напомним, что под , мы подразумеваем множества чистых стратегий игроков в игре Г. Условимся через обозначать некоторую смешанную стратегию i-го игрока, задаваемую на множестве его чистых стратегий , а через - множество всех смешанных стратегий, доступных i-му игроку. Соответственно, ситуация в смешанных стратегиях представляет собой набор совместных выборов смешанных стратегий, осуществленных всеми игроками:

а множество всевозможных ситуаций в смешанных стратегиях (S) является декартовым произведением множеств :

Приведем пример. В частности, в игре «камень, ножницы, бумага» выбор игроком 1 смешанной стратегии = (0,5; 0,25; 0,25) означает, что он с вероятностью 0,5 (в половине случаев) собирается играть камень, с вероятностью 0,25 (в четверти случаев) — ножницы и с такой же вероятностью бумагу.

Примером ситуации в смешанных стратегиях в этой игре является набор

(2.2).

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

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

Игру, получаемую на основе исходной игры как Г = (I, { }_iII, { (s)}_iII) за счет определения смешанных стратегий, будем называть ее смешанным расширением и обозначать как Г = (I, { }_iII, { (s)}_iII).

Полезности игроков в смешанном расширении игры определяются как математические ожидания их полезностей в исходной игре, рассчитываемые по вероятностным распределениям s = ( ,…, …). В случае независимого применения смешанных стратегий они могут быть найдены по формуле.

Рис. 2.1. Графическая иллюстрация множества смешанных стратегий для одного из игроков в игре «камень, ножницы, бумага» .

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

Так же как и в представлении (2.1), ситуацию в смешанных стратегиях можно представить как.

где — это некоторая смешанная стратегия, выбранная i-м игроком, а  — стратегический выбор (нодситуация), сделанный всеми остальными участниками игры.

Будем говорить, что в игре как Г = (I, { }_iII, { (s)}_iII) чистая стратегия i-го игрока является строго доминируемой, если существует такая стратегия I , что для любых I

(2.3).

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

Будем говорить, что в игре Г = (I, { }_iII, { (s)}_iII) чистая стратегия i-го игрока является слабо доминируемой, если существует такая стратегия I что для любых I

(2.4).

и при этом существует по меньшей мере одна нодситуация , для которой неравенство (2.4) выполняется как строгое.

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

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

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