Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 5
p
ведущая строка
ведущая строка
ведущая строка
1
R2
,
R1
q
R3
-1
р
1
2/9
0
3/14
1
q
-1
-1
1
-1
р
1
q
Н1
Н2
–10
–10
1
p
1
R
1
q
СОДЕРЖАНИЕ
|
[0.1] П.И.Чайковский [1] 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР И ИХ КЛАССИФИКАЦИЯ [1.1] 1.1. Предмет и задачи теории игр [1.2] 1.2. Терминология и классификация игр [1.3] 1.3. Примеры игр [1.4] ТЕСТЫ [2] 2. МАТРИЧНЫЕ ИГРЫ [2.1] 2.1. Описание матричной игры [2.2] 2.2. Принцип максимина в антагонистических играх. Седловая точка [2.3] ТЕСТЫ [2.4] ЗАДАЧИ [2.5] 2.3. Чистые и смешанные стратегии [2.6] 2.4. Основные теоремы матричных игр [2.7] ТЕСТЫ [2.8] 2.5. Решение матричной игры (2х2) [2.9] ЗАДАЧИ [2.10] 2.6. Упрощение матричных игр [2.11] 2.7.Решение игр 2xn и mx2 [2.12] ТЕСТЫ [2.13] ЗАДАЧИ [2.14] 2.8. Решение игр mхn. Эквивалентные задачи линейного программирования [2.15] ТЕСТЫ [2.16] ЗАДАЧИ [2.17] 2.9. Приближенный метод решения матричных игр mxn [2.18] 2.10. Качественная оценка элементов платежной матрицы [2.19] 2.11. Способы реализации случайного механизма выбора стратегий [2.20] ТЕСТЫ [2.21] ЗАДАЧИ [3] 3. ПОЗИЦИОННЫЕ ИГРЫ [3.1] 3.1. Общие сведения [3.2] 3.2. Задание позиционной игры в виде дерева [3.3] 3.3. Решение позиционной игры с полной информацией [3.4] 3.4. Нормализация позиционной игры [3.5] ТЕСТЫ [3.6] ЗАДАЧИ [4] 4. БЕСКОНЕЧНЫЕ АНТАГОНИСТИЧЕСКИЕ ИГРЫ [4.1] 4.1.Общие сведения [4.2] 4.2. Решение выпуклых игр на единичном квадрате [4.3] 4.3. Примеры решения бесконечных антагонистических игр [4.3.0.1] Игра «Борьба за рынки» [4.4] ТЕСТЫ [4.5] ЗАДАЧИ [5] 5. БЕСКОАЛИЦИОННЫЕ ИГРЫ [5.1] 5.1. Общие сведения [5.2] 5.2. Ситуации, оптимальные по Парето [5.3] 5.3. Состояние равновесия по Нэшу [5.4] 5.4. Описание биматричных игр [5.5] 5.5. Решение биматричных игр [5.6] 5.5. Пример решения биматричной игры [5.7] 5.6. Метастратегии и метарасширения [5.8] ТЕСТЫ [5.9] ЗАДАЧИ [6] СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ |
удк 519.83 + 519.86
Василевич Л.Ф. Теория игр. КИИМ, 2000
В учебном пособии рассмотрены на элементарном математическом уровне, без доказательств теорем основные вопросы теории игр в объеме программы для студентов экономических специальностей. Вместе с тем, пособие может представлять интерес для работников различных специальностей, занимающихся применением математики к задачам принятия оптимальных решений. Пособие можно использовать как конспект лекций. В книге рассмотрены антагонистические, биматричные, бесконечные, позиционные игры в том объеме, который позволяет решать конкретные задачи. Книга содержит большое количество тестов и задач, которые можно использовать для проведения практических занятий, а также для самостоятельного изучения. Автор выражает глубокую благодарность Б.А.Иванниковой за подготовку рукописи к изданию.
«Что наша жизнь? – Игра.»
«Пиковая дама».
Первую попытку создать математическую теорию игр предпринял в 1921 г. Э.Борель. Как самостоятельная область науки впервые теория игр была систематизировано изложена в монографии Дж.фон Неймана и О.Моргенштерна “Теория игр и экономическое поведение” в 1944 г. С тех пор многие разделы экономической теории (например, теория несовершенной конкуренции, теория экономического стимулирования и др.) развивались в тесном контакте с теорией игр [2]. Теория игр с успехом применяется и в социальных науках (например, анализ процедур голосования, поиск равновесных концепций, определяющих кооперативные и некооперативные поведения лиц). Как правило, избиратели отводят кандидатов, представляющих крайние точки зрения, но при избрании одного из двух кандидатов, предлагающих различные компромиссные решения, возникает борьба. Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке зрения на кооперацию.
Игра - это идеализированная математическая модель коллективного поведения нескольких лиц (игроков), интересы которых различны, что и порождает конфликт. Конфликт не обязательно предполагает наличие антагонистических противоречий сторон, но всегда связан с определенного рода разногласиями. Конфликтная ситуация будет антагонистической, если увеличение выигрыша одной из сторон на некоторую величину приводит к уменьшению выигрыша другой стороны на такую же величину и наоборот. Антагонизм интересов порождает конфликт, а совпадение интересов сводит игру к координации действий (кооперации).
Примерами конфликтной ситуации являются ситуации, складывающиеся во взаимоотношениях покупателя и продавца; в условиях конкуренции различных фирм; в ходе боевых действий и др. Примерами игр являются и обычные игры: шахматы, шашки, карточные, салонные и др. (отсюда и название “теория игр” и ее терминология).
В большинстве игр, возникающих из анализа финансово-экономических, управленческих ситуаций, интересы игроков (сторон) не являются строго антагонистическими ни абсолютно совпадающими. Покупатель и продавец согласны, что в их общих интересах договориться о купле-продаже, однако они энергично торгуются при выборе конкретной цены в пределах взаимной выгодности.
Теория игр - это математическая теория конфликтных ситуаций.
Цель теории игр - выработка рекомендаций по разумному поведению участников конфликта (определение оптимальных стратегий поведения игроков).
От реального конфликта игра отличается тем, что ведется по определенным правилам. Эти правила устанавливают последовательность ходов, объем информации каждой стороны о поведении другой и результат игры в зависимости от сложившейся ситуации. Правилами устанавливаются также конец игры, когда некоторая последовательность ходов уже сделана, и больше ходов делать не разрешается.
Теория игр, как и всякая математическая модель, имеет свои ограничения. Одним из них является предположение о полной (“идеальной”) разумности противников. В реальном конфликте зачастую оптимальная стратегия состоит в том, чтобы угадать, в чем противник “глуп” и воспользоваться этой глупостью в свою пользу [1].
Еще одним недостатком теории игр является то, что каждому из игроков должны быть известны все возможные действия (стратегии) противника, неизвестно лишь то, каким именно из них он воспользуется в данной партии. В реальном конфликте это обычно не так: перечень всех возможных стратегий противника как раз и неизвестен, а наилучшим решением в конфликтной ситуации нередко будет именно выход за пределы известных противнику стратегий, “ошарашивание” его чем-то совершенно новым, непредвиденным [1].
Теория игр не включает элементов риска, неизбежно сопровождающего разумные решения в реальных конфликтах. Она определяет наиболее осторожное, “перестраховочное” поведение участников конфликта.
Кроме того, в теории игр находятся оптимальные стратегии по одному показателю (критерию). В практических ситуациях часто приходится принимать во внимание не один, а несколько числовых критериев. Стратегия, оптимальная по одному показателю, может быть неоптимальной по другим.
Сознавая эти ограничения и потому, не придерживаясь слепо рекомендаций, даваемых теорий игр, можно все же выработать вполне приемлемую стратегию для многих реальных конфликтных ситуаций.
В настоящее время ведутся научные исследования, направленные на расширение областей применения теории игр.
В теории игр предполагается, что игра состоит из ходов, выполняемых игроками одновременно или последовательно.
Ходы бывают личными и случайными. Ход называется личным, если игрок сознательно выбирает его из совокупности возможных вариантов действий и осуществляет его (например, любой ход в шахматной игре). Ход называется случайным, если его выбор производится не игроком, а каким-либо механизмом случайного выбора (например, по результатам бросания монеты).
Совокупность ходов, предпринятых игроками от начала до окончания игры, называется партией.
Одним из основных понятий теории игр является понятие стратегии. Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от ситуации, сложившейся в процессе игры. В простых (одноходовых) играх, когда в каждой партии игрок может сделать лишь по одному ходу, понятие стратегии и возможного варианта действий совпадают. В этом случае совокупность стратегий игрока охватывает все возможные его действия, а любое возможное для игрока i действие является его стратегией. В сложных (многоходовых играх) понятие «варианта возможных действий» и «стратегии» может отличаться друг от друга.
Стратегия игрока называется оптимальной, если она обеспечивает данному игроку при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш, независимо от того, какие стратегии применяет противник. Могут быть использованы и другие критерии оптимальности.
Возможно, что стратегия, обеспечивающая максимальный выигрыш, не обладает другим важным представлением оптимальности, как устойчивостью (равновесностью) решения. Решение игры является устойчивым (равновесным), если соответствующие этому решению стратегии образуют ситуацию, которую ни один из игроков не заинтересован изменить.
Повторим, что задача теории игр - нахождение оптимальных стратегий.
Классификация игр представлена на рис. 1.1.
1. В зависимости от видов ходов игры подразделяются на стратегические и азартные. Азартные игры состоят только из случайных ходов - ими теория игр не занимается. Если наряду со случайными ходами есть личные ходы, или все ходы личные, то такие игры называются стратегическими.
2. В зависимости от числа участников игры подразделяются на парные и множественные. В парной игре число участников равно двум, в множественной - более двух.
3. Участники множественной игры могут образовывать коалиции, как постоянные, так и временные. По характеру взаимоотношений игроков игры делятся на бескоалиционные, коалиционные и кооперативные.
Бескоалиционными называются игры, в которых игроки не имеют право вступать в соглашения, образовывать коалиции, и целью каждого игрока является получение по возможности наибольшего индивидуального выигрыша.
Игры, в которых действия игроков направлены на максимизацию выигрышей коллективов (коалиций) без последующего их разделения между игроками, называются коалиционными.
Рис. 1.1. Классификация игр
Исходом кооперативной игры является дележ выигрыша коалиции, который возникает не как следствие тех или иных действий игроков, а как результат их наперед определенных соглашений.
В соответствии с этим в кооперативных играх сравниваются по предпочтительности не ситуации, как это имеет место в бескоалиционных играх, а дележи; и сравнение это не ограничивается рассмотрением индивидуальных выигрышей, а носит более сложный характер.
4. По количеству стратегий каждого игрока игры подразделяются на конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).
5. По количеству информации, имеющейся у игроков относительно прошлых ходов, игры подразделяются на игры с полной информацией (имеется вся информация о предыдущих ходах) и неполной информацией. Примерами игр с полной информацией могут быть шахматы, шашки и т.п.
6. По виду описания игры подразделяются на позиционные игры (или игры в развернутой форме) и игры в нормальной форме. Позиционные игры задаются в виде дерева игры. Но любая позиционная игра может быть сведена к нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. В позиционных играх ходы делаются в дискретные моменты времени. Существуют дифференциальные игры, в которых ходы делаются непрерывно. Эти игры изучают задачи преследования управляемого объекта другим управляемым объектом с учетом динамики их поведения, которая описывается дифференциальными уравнениями.
Существуют также рефлексивные игры, которые рассматривают ситуации с учетом мысленного воспроизведения возможного образа действий и поведения противника.
7. Если любая возможная партия некоторой игры имеет нулевую сумму выигрышей fi, всех N игроков (), то говорят об игре с нулевой суммой. В противном случае игры называются играми с ненулевой суммой.
Очевидно, что парная игра с нулевой суммой является антагонистической, так как выигрыш одного игрока равен проигрышу второго, а следовательно цели этих игроков прямо противоположны.
Конечная парная игра с нулевой суммой называется матричной игрой. Такая игра описывается платежной матрицей, в которой задаются выигрыши первого игрока. Номер строки матрицы соответвует номеру применяемой стратегии первого игрока, столбец - номеру применяемой стратегии второго игрока; на пересечении строки и столбца находится соответствующий выигрыш первого игрока (проигрыш второго игрока).
Конечная парная игра с ненулевой суммой называется биматричной игрой. Такая игра описывается двумя платежными матрицами, каждая для соответствующего игрока.
Игра 1. Зачет
Пусть игрок 1 - студент, готовящийся к зачету, а игрок 2 - преподаватель, принимающий зачет. Будем считать, что у студента две стратегии: А1- хорошо подготовиться к зачету; А2 - не подготовиться. У преподавателя имеется тоже две стратегии: В1 - поставить зачет; В2 - не поставить зачет. В основу оценки значений выигрышей игроков можно положить, например, следующие соображения, отраженные в матрицах выигрышей
|
В1 |
В2 |
В1 |
В2 |
|||
|
А1 |
+ (5) (оценили по заслугам) |
- (-6) (обидно) |
А1 |
+ (0) (все нормально) |
- (-3) (проявил несправедли вость) |
|
|
А2 |
(1) (удалось словчить) |
(0) (получил по заслугам) |
А2 |
-2 (дал себя обмануть) |
- 1 (студент придет еще раз) |
|
|
Выигрыши студента |
Выигрыши преподавателя |
Данная игра в соответствии с приведенной выше классификацией является стратегической, парной, бескоалиционной, конечной, описана в нормальной форме, с ненулевой суммой. Более кратко данную игру можно назвать биматричной.
Задача состоит в определении оптимальных стратегий для студента и для преподавателя.
Игра 2. Морра
Игрой “морра” называется игра любого числа лиц, в которой все игроки одновременно показывают (“выбрасывают”) некоторое число пальцев. Каждой ситуации приписываются выигрыши, которые игроки в условиях этой ситуации получают из “банка”. Например, каждый игрок выигрывает показанное им число пальцев, если все остальные игроки показали другое число; он ничего не выигрывает во все остальных случаях. В соответствии с приведенной классификацией данная игра является стратегической; в общем случае, множественной (в этом случае игра может быть бескоалиционной, коалиционной, и кооперативной) конечной.
В частном случае, когда игра парная - это будет матричная игра (матричная игра всегда является антагонистической).
Пусть два игрока «выбрасывают» одновременно один, два или три пальца. При четной сумме выигрывает первый игрок, при нечетной – второй. Выигрыш равен сумме «выброшенных пальцев». Таким образом, в данном случае каждый из игроков имеет по три стратегии, а матрица выигрышей первого игрока (проигрышей второго) имеет вид:
|
В1 |
В2 |
В3 |
|
|
А1 |
2 |
-3 |
4 |
|
А2 |
-3 |
4 |
-5 |
|
А3 |
4 |
-5 |
6 |
где Аi – стратегия первого игрока, заключающаяся в «выбрасывании» i пальцев;
Вj – стратегия второго игрока, заключающаяся в «выбрасывании» j пальцев.
Что должен делать каждый из игроков, чтобы обеспечить себе максимальный выигрыш?
Игра 3. Борьба за рынки
Некая фирма А, имея в своем распоряжении 5 условных денежных единиц, пытается удержать два равноценных рынка сбыта. Ее конкурент (фирма В), имея сумму равную 4 условным денежным единицам, пытается вытеснить фирму А с одного из рынков. Каждый из конкурентов для защиты и завоевания соответствующего рынка может выделить целое число единиц своих средств. Считается, что если для защиты хотя бы одного из рынков фирма А выделит меньше средств, чем фирма В, то она проигрывает, а во всех остальных случаях – выигрывает. Пусть выигрыш фирмы А равен 1, а проигрыш равен (-1), тогда игра сводится к матричной игре, для которой матрица выигрышей фирмы А (проигрышей фирмы В) имеет вид:
|
В0 |
В1 |
В2 |
В3 |
В4 |
|
|
А0 |
1 |
-1 |
-1 |
-1 |
-1 |
|
А1 |
1 |
1 |
-1 |
-1 |
-1 |
|
А2 |
-1 |
1 |
1 |
-1 |
-1 |
|
А3 |
-1 |
-1 |
1 |
1 |
-1 |
|
А4 |
-1 |
-1 |
-1 |
1 |
1 |
|
А5 |
-1 |
-1 |
-1 |
-1 |
1 |
Здесь Аi – стратегия фирмы А, заключающаяся в выделении i условных денежных единиц на защиту первого рынка; Вj – стратегия фирмы В, заключающаяся в выделении j условных денежных единиц на завоевание первого рынка.
Если бы на защиту или завоевание рынков фирмы могли выделить любое количество средств из имеющихся, то игра стала бы бесконечной.
(В – Верно, Н – Неверно)
1. Всякая конфликтная ситуация является антагонистической.
2. Всякая антагонистическая ситуация является конфликтной.
3. Цель теории игр - выработка рекомендаций по разумному поведению участников конфликта.
4. Недостатком теории игр является предположение о полной разумности противников.
5. В теории игр предполагается, что не все возможные стратегии противника известны.
6. Теория игр включает элементы риска, неизбежно сопровождающие разумные решения в реальных конфликтах.
7. В теории игр нахождение оптимальной стратегии осуществляется по многим критериям.
8. Стратегические игры состоят только из личных ходов.
9. В парной игре число стратегий каждого участника равно двум.
10. Игры, в которых действия игроков направлены на максимизацию выигрышей коалиций без последующего их разделения между игроками, называются коалиционными.
11. Исходом кооперативной игры является дележ выигрыша коалиции, который возникает не как следствие тех или иных действий игроков, а как результат их наперед определенных соглашений.
12. По виду описания игры делятся на игры с полной информацией или игры с неполной информацией.
13. Конечная множественная игра с нулевой суммой называется матричной.
14. Конечная парная игра с нулевой суммой называется биматричной игрой.
(Ответы: 1-Н; 2-В; 3-В; 4-В; 5-Н; 6-Н; 7-Н; 8-Н; 9-Н; 10-В; 11-В; 12-Н; 13-Н; 14-Н.)
Наиболее разработанной в теории игр является конечная парная игра с нулевой суммой (антагонистическая игра двух лиц или двух коалиций), называемая матричной игрой.
Рассмотрим такую игру G, в которой участвуют два игрока А и В, имеющие антагонистические интересы: выигрыш одного игрока равен проигрышу второго. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, можем интересоваться только выигрышем а игрока А. Естественно, игрок А хочет максимизировать а, а игрок В - минимизировать а. Для простаты отождествим себя мысленно с одним из игроков (пусть это будет игрок А), тогда будем называть игрока В - “противник” (разумеется, каких-то реальных преимуществ для А из этого не вытекает).
Пусть у игрока А имеется m возможных стратегий А1, А2, ..., Аm, а у противника - n возможных стратегий В1, В2, ..., Bn (такая игра называется игрой m х n).
Обозначим через aij выигрыш игрока А, в случае, если он воспользуется стратегией Аi, а игрок В - стратегией Вj. Предполагается, что выигрыш aij известен. Тогда мы можем составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (рис.2.1).
|
Bj Ai |
B1 |
B2 |
... |
Bn |
|
A1 |
a11 |
a12 |
... |
a1n |
|
A2 |
a21 |
a22 |
... |
a2n |
|
... |
... |
... |
... |
... |
|
Am |
am1 |
am2 |
... |
amn |
Рис. 2.1.
Если такая таблица составлена, то говорят, что игра G приведено к матричной форме. Отсюда рассматриваемая игра и получила название матричная. Само по себе приведение игры к такой форме уже может составить трудную задачу, а иногда и невыполнимую, из-за необозримого множества возможных стратегий игроков и трудности определения выигрышей aij.
Рассмотрим некоторые задачи, решение которых сводится к решению матричных игр.
Игра 1. Вариант игры «Морра»
Игра состоит в том, что каждый из двух игроков независимо друг от друга выбирает определенную сторону монеты (“герб” или “решка”), затем одновременно называют свой выбор. Если игроки выбрали одну и ту же сторону монеты, то второй игрок платит первому одну гривну, если разные, то первый платит второму такую же сумму. Легко видеть, что матрица выигрышей (платежная матрица) этой игры имеет вид
|
Bj Ai |
B1 |
B2 |
|
A1 |
1 |
-1 |
|
A2 |
-1 |
1 |
Здесь стратегии А1 и В1 - игроки А и В выбирают “герб”, а А2 и В2 - игроки А и В выбирают “решку”.
Нетривиальность сформулированной задачи, как и любой матричной игры, состоит в том, что каждый из игроков делает свой выбор независимо друг от друга.
Игра 2. Борьба за рынки
Фирмы А и В производят одинаковый товар и в настоящее время каждая «контролирует» 50% рынка. Улучшив качество товара, обе фирмы собираются развернуть рекламные кампании. При этом, приобретение новых покупателей одной фирмой сопровождается потерей этих покупателей другой фирмой. Исследование показало, что 60% потенциальных покупателей получают информацию через телевидение, 30% - через газеты и 10% - через радиовещание.
Задача каждой фирмы – выбрать стратегию рекламной кампании.
В данной игре у каждого из игроков по три стратегии:
А1, В1 – рекламировать товар через телевидение;
А2, В2 – через газеты;
А3, В3 – через радиовещание.
Поскольку это игра с нулевой суммой, то матрицу выигрышей фирмы А можно представить в следующем виде:
|
B1 |
B2 |
B3 |
|
|
A1 |
0 |
30 |
50 |
|
A2 |
-30 |
0 |
20 |
|
A3 |
-50 |
-20 |
0 |
где aij – количество покупателей товара фирмы А в процентах, на которое оно увеличивается, если фирма А применяет стратегию Аi , а фирма В – стратегию Вj.
Как отмечалось, важнейшим вопросом в теории игр (в том числе и матричных) является вопрос о выборе оптимальных стратегий для каждого из игроков.
Оптимальной стратегией игрока в матричной игре называется такая, которая обеспечивает ему максимальный выигрыш. Если игра повторяется неоднократно, то оптимальная стратегия должна обеспечивать максимальный средний выигрыш.
При выборе этой стратегии основой рассуждений является предположение, что противник является, по меньшей мере, так же разумен, как и мы сами, и делает все, чтобы добиться такой же цели.
Расчет на разумного противника - лишь одна из возможных позиций в конфликте, но в теории игр именно она кладется в основу.
При этом для выбора оптимальной стратегии используют принцип максимина: выбирай ту стратегию, чтобы при наихудшем для нас поведении противника получить максимальный выигрыш. Другими словами, принцип максимина предполагает выбор той стратегии, при которой наш минимальный выигрыш для различных стратегий максимален. Отсюда и название «принцип максимина».
Как видно, принцип максимина - это принцип крайне осторожного игрока, но именно он является основным принципом теории матричных игр.
Для пояснения принципа максимина рассмотрим пример 1 матричной игры G (4х5) с платежной матрицей, приведенной на рис. 2.2.
Пример 1.
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
B5 |
i |
|
|
A1 |
5 |
6 |
7 |
4 |
5 |
4 |
|
|
A2 |
3 |
10 |
6 |
5 |
6 |
3 |
|
|
A3 |
12 |
5 |
3 |
9 |
8 |
3 |
|
|
A4 |
6 |
7 |
5 |
6 |
10 |
5 |
максимин aij |
|
j |
12 |
10 |
7 |
9 |
10 |
||
|
минимакс aij |
Рис. 2.2
Какой стратегией игроку А воспользоваться? Есть соблазнительный выигрыш 12, при применении стратегии А3. Но при этом противник может выбрать стратегию В3, и игрок А получит выигрыш, равный всего трем.
Для определения оптимальной стратегии в соответствии с принципом максимина, запишем в правом добавочном столбце платежной матрицы минимальное значение i в каждой строке (минимум строки). Из всех значений i (правый столбец) выделим наибольшее. Ему соответствует стратегия А4. Выбрав эту стратегию, мы во всяком случае можем быть уверены, что при любом поведении противника выигрыш будет не менее пяти.
Эта величина - наш гарантированный выигрыш. Он называется нижней ценой игры (или «максимином» - максимальный из минимальных выигрышей). Будем обозначать его . В нашем примере = aij =5.
Теперь станем на точку зрения игрока В и порассуждаем за него. Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наихудшее для него поведение игрока А.
Припишем к платежной матрице (рис.2.2) нижнюю строку и в ней запишем наихудшее для игрока В возможные результаты (максимумы столбцов j.
Очевидно, осторожный противник должен выбрать стратегию, при которой величина j минимальна. Эта величина называется верхней ценой игры (или “минимаксом” - минимальный из максимальных проигрышей). Будем обозначать ее . В нашем примере = aij = 7.
Итак, исходя из принципа осторожности, игрок А должен выбрать стратегию А4, а его противник - В3. Такие стратегии называются максиминными или минимаксными стратегиями (вытекающие из принципа максимина).
До тех пор, пока обе стороны в нашем примере будут придерживаться своих максиминных стратегий, выигрыш игрока А и проигрыш игрока В будет равен а43=5.
Легко показать, что нижняя цена игры никогда не превосходит верхней цены игры.
Лемма 1. Пусть задана матрица выигрышей
А = ijи определены = и = .
Тогда .
Доказательство. По определению максимума и минимума для любых фиксированных значений i и j имеем
(2.1)
Поскольку левая часть неравенства (2.1) не зависит от i, то можем записать
(2.2)
Так как правая часть неравенства (2.1) не зависит от j, то
(2.3)
Объединяя неравенства (2.2) и (2.3), получаем неравенство (2.1), что и требовалось доказать. Итак, всегда .
Случай =, соответствует наличию у платежной матрицы так называемой седловой точки.
Определение. Точка (i*, j*) называется седловой точкой платежной матрицы ||aij||, если для всех остальных i и j этой матрицы выполняется условие
ai*j ai*j* aij*,
т.е. аij является одновременно минимумом своей строки и максимумом своего столбца.
Приведем без доказательства следующую теорему.
Теорема 1. Для того чтобы
необходимо и достаточно, чтобы матрица ||aij|| имела седловую точку. Кроме того, если (i*, j*) - седловая точка матрицы ||aij||, то
(2.4)
Говорят, что матричная игра имеет седловую точку, если соответствующая ей матрица выигрышей (платежная матрица) имеет седловую точку.
Пример 2. Найти решение игры G (3х3), платежная матрица которой имеет следующий вид:
|
Bj Ai |
B1 |
B2 |
B3 |
i |
|
A1 |
0 |
-1 |
-2 |
-2 |
|
A2 |
3 |
2 |
-1 |
-1 |
|
A3 |
6 |
3 |
0 |
0 |
|
j |
6 |
3 |
0 |
Определим и и запишем их в таблицу.
Нижняя цена игры
Верхняя цена игры
Так как ==0, то платежная матрица и матричная игра имеют седловую точку. Оптимальными стратегиями для игрока А является стратегия А3, а для игрока В - В3.
Легко заметить, что отклонение игрока А от оптимальной стратегии приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В - к увеличению его проигрыша.
Могут встречаться случаи, когда платежная матрица имеет несколько седловых точек, однако это не изменит характера рекомендуемых решений, поскольку все ситуации равновесия имеют одну и ту же цену, а следовательно, эквиваленты.
Пример 3. Найти решение игры G (3х4), платежная матрица которой имеет вид:
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
i |
|
A1 |
7 |
6 |
9 |
6 |
6 |
|
A2 |
8 |
4 |
3 |
4 |
3 |
|
A3 |
7 |
6 |
8 |
6 |
6 |
|
j |
8 |
6 |
9 |
6 |
Определим i и j и запишем их в таблицу.
Находим нижнюю и верхнюю цену игры:
; . Видно, что игра имеет четыре седловые точки с соответствующими парами оптимальных стратегий: А1В2; А1В4; А3В2 и А3В4. Цена игры равна 6.
В заключение отметим, что с позиций игрока 1 второй игрок руководствуется принципом минимакса, обеспечивающим минимизацию максимальных потерь. Но с собственной точки зрения игрока 2, оценивающего свой выигрыш, он также руководствуется принципом максимина. Поэтому, как правило, говорят лишь об использовании в антагонистической игре принципа максимина обоими игроками.
(В – Верно, Н – Неверно)
1. Матричная игра является антагонистической, поскольку выигрыш одного игрока равен проигрышу второго (выигрышу второго с обратным знаком).
2. Название “матричная игра” произошло из-за того, что такая игра описывает платежной функцией в виде матрицы.
3. В матричной игре каждый из игроков делает свой ход независимо от хода противника, предполагая лишь, что противник разумен, как и он сам.
4. Оптимальной стратегией игрока в матричной игре называется такая, которая обеспечивает ему максимальный средний выигрыш.
5. Принципом максимина руководствуются очень азартные и рискованные люди (оптимисты).
6. Принцип максимина предполагает выбор той стратегии, при которой минимальный выигрыш для различных стратегий максимален.
7. Стратегии, выбираемые из принципа максимина, называются максиминными.
8. Нижняя цена матричной игры всегда равна верхней цене.
9. Случай, когда нижняя цена матричной игры равна верхней цене, соответствует наличию у платежной матрицы седловой точки.
10. Платежная матрица игры не может иметь несколько седловых точек.
11. Если платежная матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.
(Ответы: 1-В; 2-В; 3-В; 4-В; 5-Н; 6-В; 7-В; 8-Н; 9-В; 10-Н; 11-В.)
1. Составьте платежную матрицу игры Морра, если в ней участвуют два игрока, а максимально возможное количество «выбрасываемых» пальцев равно i (i=2,3,4,5,6,7,8,9,10). Выигрыш равен сумме пальцев выброшенных игроками. При четной сумме выигрывает первый игрок, при нечетной – второй.
2. Составьте платежную матрицу игры борьба за рынки, если фирма А имеет в своем распоряжение а условных денежных единиц, а противник - в. а=3,4,5,6,7,8,9,10; а соответствующие в=2,3,4,5,6,7,8,9.
3. Найдите седловую точку и максиминные стратегии игроков для следующих матричных игр:
|
3.1. |
3 |
7 |
5 |
3.2. |
3 |
6 |
1 |
8 |
|
|
3 |
8 |
4 |
3 |
4 |
4 |
9 |
|||
|
1 |
8 |
3 |
6 |
8 |
5 |
9 |
|||
|
2 |
1 |
9 |
7 |
2 |
3 |
5 |
|||
|
3.3. |
4 |
7 |
4 |
8 |
3 |
3.4. |
5 |
9 |
7 |
|
7 |
6 |
5 |
6 |
9 |
5 |
10 |
6 |
||
|
9 |
9 |
6 |
8 |
8 |
3 |
10 |
5 |
||
|
5 |
7 |
3 |
4 |
3 |
4 |
3 |
11 |
||
|
4 |
8 |
2 |
3 |
7 |
|||||
|
3.5. |
6 |
12 |
2 |
16 |
3.6. |
7 |
13 |
3 |
17 |
|
6 |
8 |
8 |
18 |
7 |
9 |
9 |
19 |
||
|
12 |
16 |
10 |
18 |
15 |
17 |
11 |
19 |
||
|
14 |
4 |
6 |
10 |
15 |
5 |
7 |
11 |
||
|
3.7. |
3 |
5 |
9 |
3.8. |
3 |
5 |
6 |
4 |
|
|
4 |
7 |
8 |
4 |
8 |
4 |
3 |
|||
|
2 |
1 |
5 |
6 |
8 |
5 |
5 |
|||
|
2 |
7 |
4 |
2 |
|
3.9. |
4 |
6 |
3.10. |
1 |
3 |
8 |
4 |
2 |
|
|
5 |
2 |
8 |
5 |
5 |
9 |
11 |
|||
|
8 |
7 |
8 |
3 |
6 |
7 |
2 |
|||
|
3 |
1 |
||||||||
|
3.11 |
3 |
6 |
2 |
3 |
5 |
||||
|
5 |
7 |
3 |
2 |
4 |
|||||
Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит в чистых стратегиях, а используемые игроком А и игроком В пара стратегий называются чистыми стратегиями.
Определение. В антагонистической игре пара стратегий (Аi, Вj) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.
Применять чистые стратегии имеет смысл тогда, когда игроки А и В располагают сведениями о действиях друг друга и достигнутых результатах. Если допустим, что хотя бы одна из сторон не знает о поведении противника, то идея равновесия нарушается, и игра ведется бессистемно.
В рассмотренном в §2.2 примере 1 максиминные чистые стратегии А4 и В5 неустойчивы по отношению к информации о поведении противника; они не обладают свойством равновесия.
Действительно, предположим, что мы узнали, что противник придерживается стратегии В3. Используя эту информацию, выберем стратегию А1 и получим больший выигрыш, равный 7. Но если противник узнал, что наша стратегия А1, он выберет стратегию В4, сведя наш выигрыш к 4.
Таким образом, в рассмотренном примере максиминные чистые стратегии оказались неустойчивы по отношению к информации о поведении другой стороны. Но это не всегда так.
Рассмотрим матричную игру G (3х4), платежная матрица которой приведена на рис 2.3.
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
i |
|
A1 |
5 |
7 |
10 |
8 |
5 |
|
A2 |
10 |
9 |
11 |
10 |
9 |
|
A3 |
8 |
6 |
7 |
4 |
4 |
|
j |
10 |
9 |
11 |
10 |
Рис. 2.3
В этом примере нижняя цена игры равна верхней: ==9, т.е. игра имеет седловую точку.
Оказывается, что в этом случае максиминные стратегии А2 и В2 будут устойчивыми по отношению к информации о поведении противника.
Действительно, пусть игрок А узнал, что противник применяет стратегию В2. Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А2, потому что любое отступление от стратегии А2 только уменьшит выигрыш. Равным образом, информация, полученная игроком В, не заставит его отступить от своей стратегии В2.
Пара стратегий А2 и В2 обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.
Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.
Стратегии Аi и Вj (в рассматриваемом примере А2, В2), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.
Величина (2.5)
называется ценой игры.
Если 0, то игра выгодна для игрока А, если 0 - для игрока В; при =0 игра справедлива, т.е. является одинаково выгодной для обоих участников.
Однако наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.
Теорема 2. Каждая игра с полной информацией имеет седловую точку, а следовательно, решается в чистых стратегиях, т.е. имеется пара оптимальных чистых стратегий, дающая устойчивый выигрыш, равный .
Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной чистой стратегии она должна кончаться выигрышем, равным цене игры. Скажем, шахматная игра, как игра с полной информацией, либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей (только чем именно - мы пока не знаем, так как число возможных стратегий в шахматной игре огромно).
Если матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.
Возникает вопрос: как найти решение игры, платежная матрица которой не имеет седловой точки? Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее , игроку - проигрыш не больше . Учитывая что , естественно для игрока А желание увеличить выигрыш, а для игрока В - уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии: чередовать чистые стратегии с какими-то частотами.
Определение. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией.
Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии.
Будем обозначать смешанные стратегии игроков А и В соответственно
SA=||p1, p2, ..., pm||,
SB=||q1, q2, ..., qn||,
где pi - вероятность применения игроком А чистой стратегии Аі; ;
qj - вероятность применения игроком В чистой стратегии Bj; .
В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.
Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными pi и qj.
Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, какую чистую стратегию выберет противник в данной партии.
Если игрок А применяет смешанную стратегию SA=||p1, p2, ..., pm||, а игрок В смешанную стратегию SB=||q1, q2, ..., qn||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением
. (2.6)
Естественно, что ожидаемый проигрыш игрока В равен такой же величине.
Итак, если матричная игра не имеет седловой точки, то игрок должен использовать оптимальную смешанную стратегию, которая обеспечит максимальный выигрыш .
Естественно возникает вопрос: какими соображениями нужно руководствоваться при выборе смешанных стратегий? Оказывается принцип максимина сохраняет свое значение и в этом случае. Кроме того, важное значение для понимания решения игр, играют основные теоремы теории игр.
Если игрок А выбирает смешанную стратегию SA=||p1, p2, ..., pm||, а игрок В смешанную стратегию SB=||q1, q2, ..., qn||,то средний выигрыш математическое ожидание выигрыша игрока А (проигрыша игрока В) определится суммой
,
которая может рассматриваться в качестве характеристики выбранных SА и SB.
Формируя свою стратегию SА в антагонистической игре, игрок А в соответствии с принципом максимина должен выбрать такую стратегию, при которой минимально возможный выигрыш был бы максимален, т.е. такую стратегию, которая обеспечивает
(2.7)
Аналогичные рассуждения, связанные с поиском оптимальной смешанной стратегии игрока В, приводят к рекомендации выбрать такую стратегию SB, которая обеспечивает
. (2.8)
Весьма важным для теории и практики является вопрос о том, связаны ли между собой vА и vB. Ответ на него дает теорема о максимине.
Теорема о максимине. В конечной игре двух игроков (коалиций) с нулевой суммой (матричной игре) при имеет место равенство
. (2.9)
Теорема о максимине указывает на существование равновесия для случая vА=vB, при и, следовательно, существования оптимальных смешанных стратегий.
Поэтому другая формулировка теоремы о максимине, называемая основной теоремой матричных игр определяется следующим образом.
Основная теорема матричных игр. Любая матричная игра имеет, по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену v.
Обе эти теоремы эквивалентны. Из этих теорем следует, что любая матричная игра имеет цену v. Цена игры v - средний выигрыш, приходящийся на одну партию, - всегда удовлетворяет условию
, (2.10)
т.е. лежит между нижней и верхней ценами игры.
Оптимальное решение игры в смешанных стратегиях, также как и решение в чистых стратегиях, обладает тем свойством, что каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет свою оптимальную смешанную стратегию, так как это ему невыгодно.
Эта пара стратегий образует в игре положение равновесия: один игрок хочет обратить выигрыш в максимум, другой - в минимум, каждый “тянет” в свою сторону и, при оптимальном поведение обоих, устанавливается равновесие и устойчивый выигрыш .
Определение. Те из чистых стратегий игроков А и В, которые входят в их оптимальные смешанные стратегии с вероятностями, не равными нулю, называются активными стратегиями.
Существует теорема об активных стратегиях, применение которой позволяет упрощать решение некоторых матричных игр.
Теорема об активных стратегиях. Если один из участников матричной игры G (mxn), придерживается своей оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий (т.е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях), причем число активных стратегий каждого игрока, входящих в их оптимальные смешанные стратегии, не превосходит L, где L = min(m, n).
Использование данной теоремы позволяет в частности, упрощать решение матричных игр 2xn и mx2.
(В – Верно, Н – Неверно)
1. В антагонистической игре пара стратегий (Ai, Bj) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.
2. Стратегии, соответствующие седловой точке платежной матрицы, не обладают свойством равновесия (устойчивости).
3. Игра решается в чистых стратегиях если платежная матрица имеет седловую точку.
4. Игра решается в чистых стратегиях, если нижняя цена платежной матрицы равна верхней.
5. Игры с полной информацией всегда имеют седловую точку.
6. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией.
7. Если игрок А применяет смешанную стратегию SA=||p1, p2, ..., pm||, а игрок В смешанную стратегию SB=||q1, q2, ..., qn||, то средний выигрыш игрока А определяется соотношением
8. Если матричная игра не имеет седловой точки, то игроки должны использовать оптимальные смешанные стратегии.
9. Оптимальные смешанные стратегии в отличие от оптимальных чистых стратегий не обладают свойством равновесия (устойчивости).
10. Те из чистых стратегий игроков, которые входят в их оптимальные смешанные стратегии с вероятностями, не равными нулю, называются активными стратегиями.
11. Любая, матричная игра имеет по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену .
12. Теорема о максимине утверждает, что
.
13. При оптимальных смешанных стратегиях цена игры удовлетворяет условию .
14. Теорема об активных стратегиях утверждает, что если игрок придерживается свой оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, независимо от того, какие действия предпринимает другой игрок, если только тот не выходит за пределы своих активных стратегий.
(Ответы: 1-В; 2-Н; 3-В; 4-В; 5-В; 6-В; 7-Н; 8-В; 9-Н; 10-В; 11-В; 12-В; 13-В; 14-В.)
Пусть матричная игра G (2x2) имеет платежную матрицу
|
Bj Ai |
B1 |
B2 |
|
A1 |
a11 |
a12 |
|
A2 |
a21 |
a22 |
Предположим, что игра не имеет седловой точки, т.е. . При наличии седловой точки решение очевидно.
В соответствии с основной теоремой игра имеет оптимальное решение в смешанных стратегиях: SA=||p1, p2|| и SB=||q1, q2||, где вероятности применения (относительные частоты применения) чистых стратегий удовлетворяют соотношениям
; (2.11)
. (2.12)
В соответствии с теоремой об активных стратегиях, оптимальная смешанная стратегия обладает тем свойством, что обеспечивает игроку максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если тот не выходит за пределы своих активных стратегий. В частности, если игрок А использует свою оптимальную смешанную стратегию, а игрок В - свою чистую активную стратегию В1, то цена игры равна
, (2.13)
а при использовании игроком В чистой активной стратегии В2, выигрыш будет равен
. (2.14)
Уравнения (2.11), (2.13) и (2.14) образуют систему трех линейных алгебраических уравнений с тремя неизвестным:
р1, р2 и .
Решая ее, легко находим, что
. (2.15)
. (2.16)
. (2.17)
Если игрок В использует свою оптимальную смешанную стартегию, а игрок А - свою чистую активную стратегию А1, то цена игры равна
, (2.18)
а при использовании игроком А чистой активной стратегии А2, выигрыш будет равен
. (2.19)
Уравнения (2.12), (2.18) и (2.19) образует систему трех линейных алгебраических уравнений с тремя неизвестными: q1; q2 и .
Решая ее, легко находим, что
. (2.20)
. (2.21)
. (2.22)
Естественно, что в обоих случаях цена игры (выражения (2.17) и (2.22)) получилась одна и та же.
Чтобы соотношения (2.15), (2.16), (2.17), (2.20), (2.21), (2.22) имели смысл, необходимо потребовать, чтобы
или
Тогда 0<p1<1; 0<p2<1; 0<q1<1; 0<q2<1.
Нетрудно заметить, что в этих неравенствах отражено предположение об отсутствии в рассматриваемой игре седловой точки. Действительно, ни один из четырех выигрышей а11, а12, а21, а22 не может удовлетворить этим неравенствам, будучи минимальным в своей строке и максимальным в своем столбце.
Решения системы уравнений (2.15), (2.16), (2.17) и (2.20), (2.21), (2.22), полученные алгебраическим методом, удобно получать и графическим методом (рис. 2.4). Для нахождения вероятностей р1, р2 и цены игры v в прямоугольной системе координат по оси абсцисс откладывается вероятность р1[0,1], а по оси ординат - соответствующие этой вероятности - выигрыши игрока А.
При р1=0, игрок А применяет чистую стратегию А2. Если при этом игрок В применяет чистую стратегию В1, то выигрыш игрока А равен а21 (уравнение (2.13)), а если игрок В применяет чистую стратегию В2, то выигрыш игрока А равен а22 (уравнение (2.14)). При р1=1, игрок А применяет чистую стратегию А1.
Рис. 2.4
Если при этом игрок В применяет чистую стратегию В1, то выигрыш игрока А равен а11, а при применении чистой стратегии В2 - а12. Так как значения р1 лежат в пределах [0,1], то соединяя крайние точки для стратегий В1 и В2 (строя графики функций vА=(a11-a21)p1+a22 и vА=(a12-a22)p1+a22), получаем значения выигрышей игрока А для всех промежуточных значений р1.
В соответствии с принципом максимина, игрок А должен выбрать такую смешанную стратегию, при которой его минимальный выигрыш максимален. Точка N пересечения отрезков прямых (рис. 2.4) и определяет как оптимальную цену игры vopt, так и оптимальные вероятности p1opt и p2opt=1-p1opt, соответствующие оптимальной смешанной стратегии игрока А, т.е. дает решения системы уравнений (2.11), (2.13), (2.14).
Для графического решения системы уравнений (2.12), (2.18), (2.19) отложим по оси абсцисс вероятность q1[0,1], а по оси ординат соответствующие этой вероятности выигрыши игрока В:
vВ=(a11-a12)q1+a12; (2.23)
vВ=(a21-a22)q1+a22. (2.24)
Рис. 2.5
Решением являются координат точки М пересечения прямых, описываемых уравнений (2.23) и (2.24):
q1opt;q2opt=1-q1opt и vopt.
Это же следует и из принципа максимина, в соответствии с которым игрок В должен выбрать такую смешанную стратегию, при которой его максимальный проигрыш будет минимальным.
Для игры G(2х2) с седловой точкой геометрическая интерпретация решения быть представлена, например, следующим образом (рис.2.6).
Рис. 2.6
Стратегия В2 игрока В является для него явно невыгодной, так как, применяя ее, он в любой случае проигрывает больше, чем при применении стратегии В1. В данной игре р1opt=1;р2opt=0; vopt=а11, т.е. игра имеет седловую точку N и решается в чистых стратегиях. Игрок А должен применять стратегию А1, а игрок В - стратегию В1.
На рис. 2.7 показан случай, в котором решением игры для игрока А является чистая стратегия А2, а для игрока В - стратегия В1.
Игра имеет седловую точку N.
Пример: Найти алгебраическим и геометрическим методами решение игры, платежная матрица которой имеет вид
|
Bj Ai |
B1 |
B2 |
i |
|
A1 |
4 |
-2 |
-2 |
|
A2 |
1 |
3 |
1 |
|
j |
4 |
3 |
Рис. 2.7
В данной игре нижняя цена игры =1 не равна верхней цены игры =3, поэтому игра не имеет седловой точки и, в соответствии с основной теоремой матричных игр, имеет оптимальное решение в смешанных стратегиях.
Для игрока А, в соответствии с формулами (2.15) и (2.16), оптимальные вероятности применения стратегий А1 и А2 равны:
;
.
Для игрока В, в соответствии с формулами (2.20) и (2.21), оптимальные вероятности применения стратегий В1 и В2 равны:
;
.
Таким образом, оптимальные смешанные стратегии игроков ; , а цена игры в соответствии с формулой (2.22) равна:
.
Так как , то игра выгодна для игрока А.
Графическое изображение игры для игрока А показана на рис. 2.8.
Рис. 2.8
Нижняя граница выигрыша игрока А определяется ломаной CND. Оптимальное решение, определяется точкой N, естественно, дает тоже решение, что и алгебраический метод: .
Геометрическое изображение игры для игрока В показано на рис.2.9.
Рис. 2.9
Оптимальное решение, определяемое точкой М, дает решение .
Определите алгебраическим и геометрическим методами оптимальные решения следующих игр 2х2:
|
1. |
B1 |
B2 |
2. |
B1 |
B2 |
3. |
B1 |
B2 |
|||||
|
A1 |
5 |
2 |
A1 |
-3 |
-6 |
A1 |
6 |
9 |
|||||
|
A2 |
-1 |
0 |
A2 |
-4 |
-5 |
A2 |
7 |
8 |
|||||
|
4. |
B1 |
B2 |
5. |
B1 |
B2 |
6. |
B1 |
B2 |
|||||
|
A1 |
0 |
7 |
A1 |
8 |
6 |
A1 |
0 |
-1 |
|||||
|
A2 |
10 |
4 |
A2 |
4 |
7 |
A2 |
-3 |
0 |
|||||
|
7. |
B1 |
B2 |
8. |
B1 |
B2 |
9. |
B1 |
B2 |
|||||
|
A1 |
-10 |
-16 |
A1 |
7 |
9 |
A1 |
1 |
2 |
|||||
|
A2 |
-12 |
-14 |
A2 |
13 |
11 |
A2 |
4 |
3 |
|||||
|
10. |
B1 |
B2 |
11. |
B1 |
B2 |
12. |
B1 |
B2 |
|||||
|
A1 |
-3 |
-2 |
A1 |
0 |
2 |
A1 |
-1 |
1 |
|||||
|
A2 |
0 |
-2 |
A2 |
3 |
1 |
A2 |
2 |
0 |
|||||
|
13. |
B1 |
B2 |
14. |
B1 |
B2 |
15. |
B1 |
B2 |
|||||
|
A1 |
6 |
-2 |
A1 |
4 |
-5 |
A1 |
5 |
6 |
|||||
|
A2 |
-2 |
6 |
A2 |
-5 |
4 |
A2 |
6 |
5 |
|||||
|
16. |
B1 |
B2 |
17. |
B1 |
B2 |
18. |
B1 |
B2 |
|||||
|
A1 |
4 |
7 |
A1 |
4 |
-5 |
A1 |
8 |
-1 |
|||||
|
A2 |
5 |
4 |
A2 |
-4 |
5 |
A2 |
1 |
9 |
|||||
|
19. |
B1 |
B2 |
20. |
B1 |
B2 |
21. |
B1 |
B2 |
|||||
|
A1 |
6 |
9 |
A1 |
1 |
-3 |
A1 |
4 |
-2 |
|||||
|
A2 |
13 |
11 |
A2 |
-8 |
5 |
A2 |
-3 |
5 |
|||||
|
22. |
B1 |
B2 |
23. |
B1 |
B2 |
24. |
B1 |
B2 |
|||||
|
A1 |
5 |
8 |
A1 |
6 |
9 |
A1 |
2 |
5 |
|||||
|
A2 |
7 |
6 |
A2 |
8 |
7 |
A2 |
3 |
4 |
|||||
|
25. |
B1 |
B2 |
26. |
B1 |
B2 |
27. |
B1 |
B2 |
|||||
|
A1 |
0 |
-3 |
A1 |
12 |
3 |
A1 |
4 |
-5 |
|||||
|
A2 |
-1 |
0 |
A2 |
9 |
7 |
A2 |
1 |
-1 |
Решение матричных игр тем сложнее, чем больше размерность платежной матрицы. Поэтому для игр с платежными матрицами большой размерности отыскание оптимального решения можно упростить, если уменьшить их размерность путем исключения дублирующих и заведомо невыгодных (доминируемых) стратегий.
Определение 1. Если в платежной матрице игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующее этим строкам (столбцам) стратегии называются дублирующими.
Определение 2. Если в платежной матрице игры все элементы некоторой строки, определяющей стратегию Аi игрока А, не больше (меньше или некоторые равны) соответствующих элементов другой строки, то стратегия Аi называется доминируемой (заведомо невыгодной).
Определение 3. Если в платежной матрице игры все элементы некоторого столбца, определяющего стратегию Вi игрока В не меньше (больше или некоторые равны) соответствующих элементов другого столбца, то стратегия Вi называется доминируемой (заведомо невыгодной).
Правило. Решение матричной игры не изменится, если из платежной матрицы исключить строки и столбцы, соответствующие дублирующим и доминируемым стратегиям.
Пример. Упростить матричную игру, платежная матрица которой имеет вид:
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
B5 |
|
A1 |
5 |
9 |
3 |
4 |
5 |
|
A2 |
4 |
7 |
7 |
9 |
10 |
|
A3 |
4 |
6 |
3 |
3 |
9 |
|
A4 |
4 |
8 |
3 |
4 |
5 |
|
A5 |
4 |
7 |
7 |
9 |
10 |
Из платежной матрицы видно, что стратегия А2 дублирует стратегию А5, потому любую из них можно отбросить (отбросим стратегию А5). Сравнивая почленно стратегии А1 и А4, видим, что каждый элемент строки А4 не больше соответствующего элемента строки А1. Поэтому применение игроком А доминирующей над А4 стратегии А1 всегда обеспечивает выигрыш, не меньший того, который был бы получен при применении стратегии А4. Следовательно, стратегию А4 можно отбросить. Таким образом, имеем упрощенную матричную игру с платежной матрицей вида:
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
B5 |
|
A1 |
5 |
9 |
3 |
4 |
5 |
|
A2 |
4 |
7 |
7 |
9 |
10 |
|
A3 |
4 |
6 |
3 |
3 |
9 |
Из этой матрицы видно, что в ней некоторые стратегии игрока В доминируют над другими: В3 над В2, В4 и В5. Отбрасывая доминируемые стратегии В2, В4 и В5, получаем игру 3x2, имеющей платежную матрицу вида:
|
Bj Ai |
B1 |
B3 |
|
A1 |
5 |
3 |
|
A2 |
4 |
7 |
|
A3 |
4 |
3 |
В этой матрице стратегия А3 доминируется как стратегией А1, так и стратегией А2. Отбрасывая стратегию А3, окончательно получаем игру 2x2 с платежной матрицей
|
Bj Ai |
B1 |
B3 |
|
A1 |
5 |
3 |
|
A2 |
4 |
7 |
Эту игру уже упростить нельзя, ее надо решать рассмотренным выше алгебраическим или геометрическим методом.
Необходимо отметить, что отбрасывая дублируемые и доминируемые стратегии в игре с седловой точкой, мы все равно придем к игре с седловой точкой, т.е. к решению в чистых стратегиях. Но лучше сразу проверить, не обладает ли игра седловой точкой - это проще, чем сравнивать почленно все строки и все столбцы платежной матрицы.
Алгебраические методы решения матричных игр иногда производить проще, если использовать также следующие свойства матричных игр.
Свойство 1. Если ко всем элементам платежной матрицы прибавить (вычесть) одно и тоже число С, то оптимальные смешанные стратегии игроков не изменятся, а только цена игры увеличится (уменьшится) на это число С.
Свойство 2. Если каждый элемент платежной матрицы умножить на положительное число k, то оптимальные смешанные стратегии игроков не изменятся, а цена игры умножится на k.
Отметим, что эти свойства верны и для игр, имеющих седловую точку. Эти два свойства матричных игр применяются в следующих случаях:
1) если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем ее элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице;
2) если матрица игры имеет дробные числа, то для удобства вычислений элементы этой матрицы следует умножить на такое число, чтобы все выигрыши были целыми числами.
Пример. Решить матричную игру 2х2 с платежной матрицей вида:
|
Bj Ai |
B1 |
B2 |
|
A1 |
0.5 |
-0.2 |
|
A2 |
0.1 |
0.3 |
Умножая все элементы платежной матрицы на 10, а затем прибавляя к ним число 2, получаем игру с платежной матрицей
|
Bj Ai |
B1 |
B2 |
|
A1 |
7 |
0 |
|
A2 |
3 |
5 |
Решая эту игру алгебраическим методом, получаем
; ;
; ;
.
В соответствии со свойствами 1 и 2, исходная матричная игра имеет те же оптимальные смешанные стратегии: и . А для получения исходной цены игры необходимо из полученной цены игры вычесть 2, а затем разделить на 10. Таким образом, получаем цену исходной игры: .
Как уже отмечалось в теореме об активных стратегиях, любая конечная игра mxn имеет решение, в котором число активных стратегий каждого игрока не превосходит, где . Следовательно, у игры 2xn или mx2 всегда имеется решение содержащее не более двух активных стратегий у каждого из игроков . Если эти активные стратегии игроков будут найдены, то игры 2xn и mx2 превращаются в игры 2x2, методы решения которых рассмотрены выше.
Практически решение игры 2xn осуществляется следующим образом:
1) строится графическое изображение игры для игрока А;
2) выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы (максимин), которая равна цене игры v;
3) определяется пара стратегий игрока В, пересекающихся в точке оптимума. Эти стратегии и являются активными стратегиями игрока В.
Таким образом, игра 2xn сведена к игре 2x2, которую более точно можно решить алгебраическим методом.
Если в точке оптимума пересекается более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них.
Решение игры mx2 осуществляется аналогично. Но в этом случае строится графическое изображение игры для игрока В и выделяется не нижняя, а верхняя граница выигрыша (так как находится оптимальная смешанная стратегия игрока В), и на ней находится точка оптимума с наименьшей ординатой (минимакс).
Пример. Найти решение игры, платежная матрица которой имеет вид:
|
Bj Ai |
B1 |
B2 |
B3 |
|
A1 |
2 |
5 |
8 |
|
A2 |
7 |
4 |
3 |
Платежная матрица не имеет седловой точки, поэтому оптимальное решение должно быть в смешанных стратегиях. Строим графическое изображение игры для игрока А (рис.2.10)
Рис. 2.10
Точка N (максимин) является точкой оптимума. В этой точке пересекаются линии, соответствующие активным стратегиям В1 и В2 игрока В. Таким образом, исключая стратегию В3, получаем матричную игру 2x2 с платежной матрицей вида
|
Bj Ai |
B1 |
B2 |
|
A1 |
2 |
5 |
|
A2 |
7 |
4 |
Используя алгебраический метод решения этой игры, получаем точное решение
; ;
; ;
.
Ответ: ; ; .
Пример. Найти решение игры, платежная матрица которой имеет вид
|
Bj Ai |
B1 |
B2 |
|
A1 |
0 |
1 |
|
A2 |
4 |
2 |
|
A3 |
-1 |
4 |
|
A4 |
1 |
-3 |
|
A5 |
6 |
-2 |
|
A6 |
1,5 |
3 |
Платежная матрица не имеет седловой точки. Для сведения данной игры к игре 2x2 строим ее графическое изображение для игрока В (рис. 2.11).
Точка М (минимакс) является точкой оптимума. В этой точке пересекаются отрезки, соответствующие активным стратегиям А2, А6 и А3 игрока А. Таким образом, исключая стратегии А1, А4 и А5 и выбирая из трех активных стратегий две (например, А2 и А3 или А2 и А6), приходим к матричной игре 2x2. Выбор стратегий А3 и А6 исключен, так как в этом случае точка М перестанет быть точкой минимакса.
Рис.2.11
Пусть выбираются стратегии А2 и А3. Тогда игра 2x2 приобретает вид
|
Bj Ai |
B1 |
B2 |
|
A2 |
4 |
2 |
|
A3 |
-1 |
4 |
Оптимальные смешанные стратегии данной игры, а, следовательно, и исходной игры определяются следующими вероятностями:
; ;
; ;
.
Ответ: ; ; .
Другой вариант игры 2x2 получается, если использовать стратегии А2 и А6. В этом случае платежная матрица имеет вид
|
Bj Ai |
B1 |
B2 |
|
A2 |
4 |
2 |
|
A6 |
1,5 |
3 |
Тогда
; ;
; ;
.
Ответ: ; ; .
Естественно, что цена игры для обоих вариантов одинакова.
В заключение наметим общую схему решения матричных игр 2xn и mx2:
1. Определяется наличие седловой точки, т.е. возможность решения игры в чистых стратегиях. Если нижняя цена игры не равна верхней цене игры , то осуществляется поиск решения в смешанных стратегиях.
2. Производится упрощение матричной игры путем исключения дублирующих и доминируемых стратегий. Если упрощенная игра имеет размерность не 2x2, то переходим к этапу 3.
3. Строится графическое изображение игры и определяется две активные стратегии игрока, имевшего в исходной задаче число стратегий больше двух.
4. Решается матричная игра 2x2.
(В – Верно, Н – Неверно)
1. Если в игре 2xn нет оптимального решения в чистых стратегиях, то оптимальное решение в смешанных стратегиях содержит две активные стратегии у каждого из игроков.
2. В игре mx2 число активных стратегий в оптимальной стратегии каждого из игроков может быть равно или единице, или двум.
3. Оптимальное решение в игре двух лиц с нулевой суммой всегда является устойчивым независимо от того, смешанные или чистые стратегии используют игроки.
4. Если оптимальная цена матричной игры отрицательна, то конечный результат игры будет убыточным для игрока А.
5. Прибавление одного и того же числа ко всем элементам платежной матрицы не влияет на цену игры.
6. Умножение всех элементов платежной матрицы на одно и тоже положительное число не изменяет оптимальных стратегий игроков.
7. Цена матричной игры изменится, если из платежной матрицы исключить строки и столбцы, соответствующие дублирующим и доминируемым стратегиям.
8. Любая матричная игра 2xn или mx2 может быть сведена к игре 2х2.
Ответы: (1 - В; 2 - В; 3 - В; 4 - В; 5 - Н; 6 - В; 7 - Н; 8 - В).
Решить следующие матричные игры:
|
1. |
8 |
1 |
7 |
2. |
-4 |
-8 |
-7 |
-3 |
3. |
5 |
1 |
3 |
|
|
3 |
0 |
7 |
-5 |
-9 |
-8 |
-4 |
7 |
8 |
2 |
||||
|
4. |
6 |
13 |
19 |
25 |
19 |
15 |
16 |
18 |
5. |
3 |
3 |
4 |
5 |
|
19 |
25 |
19 |
18 |
16 |
12 |
13 |
15 |
5 |
4 |
3 |
3 |
||
|
6. |
0,4 |
0,5 |
1 |
7. |
1 |
2 |
3 |
8. |
11 |
8 |
12 |
1 |
|
|
1 |
0,5 |
0,3 |
4 |
3 |
0 |
-7 |
-1 |
-8 |
2 |
||||
|
9. |
10 |
-4 |
6 |
14 |
0 |
10. |
2 |
-6 |
10 |
-14 |
18 |
||
|
0 |
10 |
4 |
4 |
12 |
-4 |
8 |
-12 |
16 |
-20 |
||||
|
11. |
3 |
7 |
-1 |
11 |
-5 |
12. |
9 |
-5 |
7 |
1 |
-3 |
||
|
6 |
2 |
10 |
-4 |
14 |
-10 |
4 |
-8 |
-6 |
2 |
||||
|
13. |
24 |
0 |
18 |
21 |
14. |
7 |
9 |
0 |
|||||
|
9 |
18 |
9 |
3 |
6 |
0 |
10 |
|||||||
|
15. |
-1 |
8 |
7 |
6 |
3 |
1 |
|||||||
|
9 |
0 |
1 |
2 |
5 |
7 |
||||||||
|
16. |
1 |
3 |
17. |
2 |
10 |
18. |
-3 |
-9 |
19. |
1 |
3 |
||
|
5 |
7 |
4 |
8 |
-15 |
-21 |
5 |
7 |
||||||
|
9 |
11 |
6 |
6 |
-27 |
-33 |
9 |
11 |
||||||
|
8 |
4 |
||||||||||||
|
10 |
2 |
||||||||||||
|
20. |
-1 |
5 |
21. |
11 |
3 |
22. |
2 |
2 |
3 |
-1 |
23. |
4 |
8 |
|
-3 |
1 |
9 |
7 |
4 |
3 |
2 |
6 |
4 |
6 |
||||
|
0 |
-3 |
10 |
5 |
6 |
4 |
||||||||
|
-3 |
0 |
7 |
11 |
-2 |
12 |
||||||||
|
1 |
-3 |
8 |
9 |
||||||||||
|
5 |
-1 |
||||||||||||
|
24. |
1 |
3 |
25. |
2 |
4 |
-2 |
8 |
26. |
1 |
2 |
27. |
5 |
9 |
|
1 |
4 |
3 |
6 |
5 |
-5 |
5 |
6 |
5 |
7 |
||||
|
2 |
1 |
-7 |
9 |
7 |
5 |
||||||||
|
-1 |
5 |
-4 |
-3 |
-1 |
13 |
||||||||
|
2 |
1 |
||||||||||||
|
28. |
3 |
8 |
12 |
29. |
0 |
8 |
30. |
-2 |
10 |
||||
|
6 |
10 |
14 |
2 |
6 |
-6 |
2 |
|||||||
|
4 |
4 |
0 |
-6 |
||||||||||
|
6 |
2 |
-6 |
0 |
||||||||||
|
8 |
0 |
1 |
1 |
||||||||||
|
2 |
-6 |
||||||||||||
|
10 |
-2 |
Пусть имеется матричная игра mxn без седловой точки с матрицей выигрышей ||aij||. Допустим, что все выигрыши aij положительны (этого всегда можно добиться, прибавляя ко всем элементам матрицы достаточно большое число С; от этого, как уже отмечалось, цена игры увеличится на C, а оптимальные решения SA и SB не изменятся).
Если все aij положительны, то и цена игры при оптимальной стратегии тоже положительна, т.к. .
В соответствии с основной теоремой матричных игр, если платежная матрица не имеет седловой точки, то имеется пара оптимальных смешанных стратегий SA=||p1, p2, ..., pm|| и SB=||q1, q2, ..., qn||, применение которой обеспечивает игрокам получение цены игры .
Найдем вначале SA. Для этого предположим, что игрок В отказался от своей оптимальной смешанной стратегии SB и применяет только чистые стратегии. В каждом из этих случаев выигрыш игрока А будет не меньше, чем :
(2.25)
Разделив левую и правую часть каждого из неравенств (2.25) на положительную величину v и введя обозначения:
(2.26)
запишем неравенства (2.25) в следующем виде:
, (2.27)
где x1, x2, ... xm - неотрицательные переменные.
В силу того, что
p1+p2+...+pm=1,
переменные x1, x2, ... xm удовлетворяют условию
. (2.28)
Учитывая, что игрок А стремится максимизировать , получаем следующую задачу линейного программирования: найти неотрицательные значения переменных x1, x2, ... xm такие, чтобы они удовлетворяли линейным ограничениям - неравенствам (2.27) и обращали в минимум линейную функцию этих переменных:
min L(x)=x1+x2+ ... +xm. (2.29)
Из решения задачи линейного программирования находим цену игры и оптимальную стратегию Sa по формулам:
, (2.30)
, . (2.31)
Аналогично находим оптимальную стратегию SВ игрока В. Предположим, что игрок А отказался от своей оптимальной стратегии SA и применяет только чистые стратегии. Тогда проигрыш игрока В в каждом из этих случаев будет не больше, чем :
. (2.32)
Разделив левую и правую части каждого их неравенств (2.32) на положительную величину и введя обозначения:
, (2.33)
запишем неравенство (2.32) в следующем виде:
, (2.34)
где y1, y2, ..., yn - неотрицательные переменные.
В силу того, что q1+q2+...+qn=1, переменные y1, y2, ..., yn удовлетворяют условию
. (2.35)
Учитывая, что игрок В стремится минимизировать положительную цену v (свой проигрыш), получаем задачу линейного программирования: найти неотрицательные значения переменных y1, y2, ..., yn такие, чтобы они удовлетворяли линейным ограничениям (2.34) и обращали в максимум линейную функцию этих переменных:
max L(y)=y1+y2+ ... +ym. (2.36)
Эта задача является двойственной по отношению к задаче, представленной условиями (2.27) и (2.29).
Оптимальная стратегия SB=||q1, q2, ..., qn|| игрока В определяется из решения двойственной задачи линейного программирования по формулам:
, . (2.37)
Таким образом, оптимальные стратегии SA=||p1, p2, ..., pm|| и SB=||q1, q2, ..., qn|| матричной игры mxn с платежной матрицей ||aij|| могут быть найдены путем решения пары двойственных задач линейного программирования:
|
Прямая (исходная) задача |
Двойственная задача |
|
, , ; , . |
, , ; , . |
При этом
, (2.38)
.
Пример. Найти решение и цену матричной игры, платежная матрица которой имеет вид
|
Bj Ai |
B1 |
B2 |
B3 |
|
A1 |
1 |
2 |
3 |
|
A2 |
3 |
1 |
1 |
|
A3 |
1 |
3 |
1 |
Решение
1. Так как =1 не равно =3, то игра не имеет седловой точки.
2. В данной игре нет дублирующих и доминируемых стратегий.
3. Решаем игру путем решения пары двойственных задач линейного программирования.
Математические модели пары двойственных задач линейного программирования будут выглядеть следующим образом:
|
Прямая (исходная) задача: Найти неотрицательные переменные х1,х2,х3, минимизирующие функцию min L (x)=х1+х2+х3, при ограничениях: х1+3х2+х31; 2х1+х2+3х31; 3х1+х2+х31; xi0, . |
Двойственная задача: Найти неотрицательные переменные у1,у2,у3, максимизирующие функцию max L (x)=y1+y2+y3, при ограничениях: y1+2y2+3y31; 3y1+y2+y31; y1+3y2+y31; yj0, . |
Данные задачи решаются, например, симплекс - методом. Поскольку в двойственной задаче ограничения имеют вид ““, то эту задачу решать проще (не нужно вводить искусственные переменные). Оптимальное решение исходной задачи можно будет непосредственно получить из данных симплекс - таблицы для оптимального решения двойственной задачи.
Начальная симплекс - таблица двойственной задачи имеет вид
|
БП |
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Решение |
|
у4 |
1 |
2 |
3 |
1 |
0 |
0 |
1 |
|
у5 |
3 |
1 |
1 |
0 |
1 |
0 |
1 |
|
у6 |
1 |
3 |
1 |
0 |
0 |
1 |
1 |
|
L |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
ведущий столбец
Последующие симплекс-таблицы приведены ниже:
|
БП |
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Решение |
|
у4 |
0 |
1 |
0 |
||||
|
у1 |
1 |
0 |
0 |
||||
|
у6 |
0 |
0 |
1 |
||||
|
L |
0 |
0 |
0 |
ведущий столбец
|
БП |
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Решение |
|
у4 |
0 |
0 |
1 |
||||
|
у1 |
1 |
0 |
0 |
||||
|
у2 |
0 |
1 |
0 |
||||
|
L |
0 |
0 |
0 |
ведущий столбец
И, наконец, получаем симплекс-таблицу, которая соответствует оптимальному решению двойственной задачи:
|
БП |
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Решение |
|
у3 |
0 |
0 |
1 |
||||
|
у1 |
1 |
0 |
0 |
||||
|
у2 |
0 |
1 |
0 |
||||
|
L |
0 |
0 |
0 |
Оптимальное решение двойственной задачи линейного программирования следующее:
у1=; у2=; у3=; max L (y)= .
Находим оптимальную смешанную стратегию игрока В в соответствии с формулами (2.37) и (2.38):
;
.
Следовательно, .
Оптимальное решение исходной задачи находим, используя двойственные оценки, из симплекс - таблицы для оптимального решения двойственной задачи: коэффициент при начальной базисной переменной в оптимальном уравнении прямой задачи равен разности между правой и левой частями ограничения двойственной задачи, ассоциированного с данной начальной переменной.
Получаем x1=; x2=; x3=; max L (x)= .
Отсюда определим вероятности применения своих активных стратегий игроком А:
.
Следовательно: .
Таким образом, решение игры mxn сводится к решению задачи линейного программирования. Нужно заметить, что и наоборот, - для любой задачи линейного программирования может быть построена эквивалентная ей задача теории матричных игр. Эта связь задач теории матричных игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения матричных игр, которые при большой размерности задачи могут оказаться проще, чем симплекс - метод.
(В – Верно, Н – Неверно)
Ответы: (1 - В; 2 - В; 3 - Н; 4 - В; 5 - Н).
Решить следующие матричные игры:
|
1. |
2 |
4 |
6 |
2. |
-7 |
4 |
2 |
3. |
-5 |
6 |
4 |
|
|
6 |
2 |
2 |
0 |
2 |
1 |
2 |
4 |
3 |
||||
|
2 |
6 |
2 |
6 |
-5 |
-1 |
8 |
-3 |
1 |
||||
|
4. |
1 |
3 |
2 |
5. |
2 |
1 |
0 |
6. |
4 |
6 |
1 |
|
|
3 |
1 |
3 |
1 |
2 |
1 |
4 |
4 |
1 |
||||
|
2 |
3 |
1 |
0 |
1 |
2 |
1 |
1 |
6 |
||||
|
7. |
-4 |
-6 |
-1 |
8. |
-2 |
-5 |
2 |
9. |
5 |
7 |
1 |
|
|
-4 |
-4 |
-1 |
-1 |
1 |
-5 |
5 |
5 |
1 |
||||
|
-1 |
-1 |
-6 |
-2 |
-1 |
-2 |
2 |
2 |
6 |
||||
|
10. |
2 |
6 |
4 |
11. |
3 |
6 |
9 |
12. |
0 |
1 |
2 |
|
|
6 |
2 |
6 |
9 |
3 |
3 |
2 |
0 |
0 |
||||
|
4 |
6 |
2 |
3 |
9 |
3 |
0 |
2 |
1 |
Рассмотрим приближенный метод решения матричных игр - метод Брауна-Робинсон (метод итераций). Идея его заключается в следующем. Разыгрывается эксперимент, в котором игроки А и В поочередно применяют друг против друга свои чистые стратегии. Каждый из игроков стремится увеличить свой выигрыш, предполагая, что будущее будет походить на прошлое; при этом считается, что ни один из них не знает своей оптимальной стратегии.
Такой принцип приводит к некоторой последовательности партий игры, для каждой из которых можно подсчитать приближенные оптимальные стратегии каждого из игроков, а также верхнюю и нижнюю цены игры.
Вместо того, чтобы вычислять каждый раз средний выигрыш, можно пользоваться суммарным за все предыдущие ходы выигрышем и выбирать ту свою стратегию, при которой этот накопленный выигрыш максимален.
Доказано, что такой метод сходится: при увеличении числа партий средний выигрыш на одну партию будет стремиться к цене игры, а частоты применения стратегий - к их вероятностям в оптимальных смешанных стратегиях игроков.
Объясним этот метод на примере игры 3x3, платежная матрица которой приведена ниже. Игра начинается с произвольно выбранной стратегии игрока А, - например стратегии А1 (выбранные стратегии обозначаются звездочкой). Платежные элементы этой строки переписываются под платежной матрицей. Игрок В, предполагая, что будущее будет походить на прошлое, выберет стратегию В1, при которой его проигрыш минимален. Соответствующий этой стратегии проигрыш обозначен звездочкой. Платежные элементы стратегии В1 переписываются справа от платежной матрицы. Игрок А, также предполагая, что будущее будет походить на прошлое, выбирает стратегию А2 (наибольшее число обозначено звездочкой). Платежные элементы, соответствующие стратегии А2, прибавляются поочередно к элементам предыдущей строки, записанной под матрицей. Далее выбирается наименьший элемент суммарной строки. Ему соответствует стратегия В2. Тогда к столбцу, записанному справа от платежной матрицы, поочередно прибавляются платежные элементы стратегии В2. Этот процесс продолжается до тех пор, пока разрыв между нижней и верхней оценками игры станет небольшим. Если при выборе стратегий на некотором шаге есть несколько альтернатив, то выбирается любая из равноценных стратегий.
В рассматриваемом примере сделано 20 шагов. За эти двадцать шагов игрок А применил свою первую стратегию (количество звездочек в суммарных выигрышах, соответствующей первой стратегии) 7 раз; вторую - 8 раз; третью - 5 раз. Игрок В применил стратегию В1 восемь раз; вторую - 8 раз; третью - 4 раза. Следовательно, приближенные оценки оптимальных стратегий, полученные за 20 итераций, равны:
.
Эти оценки не так уж сильно отличаются от точного решения данной матричной игры, которое равно .
|
Bi Ai |
B1 |
B2 |
B3 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
A1 |
1 |
2 |
3 |
* |
1 |
3 |
5 |
8* |
9* |
10 |
12 |
14 |
17* |
20* |
|
A2 |
3 |
1 |
1 |
3* |
4* |
5 |
6 |
9 |
12* |
13* |
14 |
15 |
16 |
|
|
A3 |
1 |
3 |
1 |
1 |
4 |
7* |
8 |
9 |
10 |
13 |
16* |
17 |
18 |
|
|
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|||||
|
1 |
1* |
2 |
3 |
21* |
22 |
24* |
25 |
27 |
29 |
31 |
32 |
33 |
36* |
|
|
2 |
4 |
3* |
4 |
19 |
22* |
23 |
26* |
27* |
28 |
29 |
32 |
35* |
36 |
|
|
3 |
7 |
4* |
5 |
19 |
20 |
23 |
24 |
27 |
30* |
33* |
34* |
35 |
36 |
|
|
4 |
8 |
7 |
6* |
|||||||||||
|
5 |
9* |
9 |
9 |
|||||||||||
|
6 |
10* |
11 |
12 |
|||||||||||
|
7 |
13 |
12* |
13 |
|||||||||||
|
8 |
16 |
13* |
14 |
|||||||||||
|
9 |
17 |
16 |
15* |
|||||||||||
|
10 |
18 |
13 |
18* |
|||||||||||
|
11 |
19* |
20 |
21 |
|||||||||||
|
12 |
20* |
22 |
24 |
|||||||||||
|
13 |
23 |
23* |
25 |
|||||||||||
|
14 |
24* |
25 |
28 |
|||||||||||
|
15 |
27 |
26* |
29 |
|||||||||||
|
16 |
30 |
27* |
30 |
|||||||||||
|
17 |
31 |
30* |
31 |
|||||||||||
|
18 |
32* |
33 |
32 |
|||||||||||
|
19 |
33* |
36 |
33 |
|||||||||||
|
20 |
36 |
37 |
34* |
Приближенную цену игры определяют как среднеарифметическое между нижней оценкой игры , равной минимально накопленному выигрышу игрока А, деленному на число шагов k, и верхней оценкой игры , равной максимальному суммарному проигрышу игрока В, деленному на k:
.
В рассматриваемом примере
.
Точная цена игры v = 1,8.
Разрыв между и отражает неточность оценок относительно оптимальных смешанных стратегий. В примере составляет 2,8% от цены игры v=1,8.
Увеличивая число итераций k, можно найти еще более точные оценки оптимальных смешанных стратегий.
Преимуществом итерационного метода решения матричных игр является то, что объем вычислений с увеличением размерности игры mxn растет существенно медленнее, чем в методах линейного программирования (в частности, в симплекс - методе).
Очевидной трудностью при использовании теории игр является задание элементов платежной матрицы с требуемой точностью. Вместе с тем эту задачу не нужно и переоценивать. Использование, например, свойств 1 и 2 из параграфа 2.6, позволяет находить оптимальные стратегии задавая лишь относительные значения элементов платежной матрицы. Например, если в платежной матрице имеется всего три различных значения элементов платежной матрицы, то в этом случае совершенно не важно, какое значение имеют наименьший и наибольший платежи. Единственно, что имеет значение - это относительное положение третьего платежа.
Таким образом, теория игр может дать важные результаты даже в тех случаях, в которых точные оценки платежей затруднены. В частности, имеется слабая форма оценки платежей, называемая упорядочением. Она заключается в расположении платежей по порядку их относительной величины. Существуют игровые ситуации, для которых не требуется ничего большего, чем определение порядка расположения платежей по величине. В других игровых ситуациях знание порядка платежей позволяет сделать частичные выводы относительно оптимальных стратегий и цены игры.
Пусть, например, платежи оцениваются как плохие (п); удовлетворительные (у), хорошие (х) или отличные (о), а матрица игры имеет вид
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
B5 |
i |
|
A1 |
п |
о |
х |
о |
х |
п |
|
A2 |
у |
у |
х |
о |
х |
у* |
|
A3 |
п |
х |
о |
о |
х |
п |
|
A4 |
у |
о |
о |
п |
о |
п |
|
j |
у* |
о |
о |
о |
о |
В этой игре ==y, т.е. игра решается в чистых стратегиях. Игрок А должен придерживаться своей второй стратегии, а игрок В - стратегии В1. Цена игры – «удовлетворительно».
Пусть игра имеет седловую точку в клетке, отмеченной звездочкой.
|
B1 |
B2 |
B3 |
B4 |
B5 |
B6 |
|
|
A1 |
||||||
|
A2 |
||||||
|
A3 |
||||||
|
A4 |
* |
|||||
|
A5 |
||||||
|
A6 |
||||||
|
A7 |
Так как седловая точка отмечает наименьшее число в этой строке и наибольшее число в столбце, то все остальные числа в данной строке (столбце) могут быть какими угодно, лишь бы число, отмеченное звездочкой, оставалось наименьшим в строке (наибольшим в столбце). Наконец, все остальные числа в матрице, которые не попали в строку и столбец, соответствующих оптимальным стратегиям, могут быть вообще какими угодно. Их значения не влияют ни на оптимальный способ ведения игры, ни на ее цену.
Пример. Решить игру, платежная матрица которой имеет вид
|
Bj Ai |
B1 |
B2 |
B3 |
|
A1 |
п |
о |
у |
|
A2 |
х |
у |
х |
|
A3 |
п |
у |
о |
Как видно стратегия В1 доминирует стратегию В3, далее стратегия А1 будет доминировать стратегию А3, а, следовательно, исходную игру можно свести к игре 2*2:
|
Bj Ai |
B1 |
B2 |
i |
|
A1 |
п |
о |
п |
|
A2 |
х |
у |
у* |
|
j |
х* |
о |
Таким образом, игрокам не следует использовать стратегии А3 и В3. Так как =у не равняется =х, то игра не имеет седловой точки и должна решаться в смешанных стратегиях.
Частоты применения своих стратегий игроком А равны:
;
.
Частоты применения своих стратегий игроком В равны:
;
,
таким образом, частота применения стратегии А1 пропорциональна разности между “хорошо” и “удовлетворительно”, а стратегии А2 пропорциональна разности между “отлично” и “плохо”. Ясно, что стратегия А1 должна применяться реже, чем стратегия А2 независимо от того, какие упорядоченные числа будут приписаны этим понятиям.
Положение игрока В несколько более неопределенно. Он должен применять стратегию В1 с частотой пропорциональной разности между “отлично” и “удовлетворительно”, а стратегию В2 - с частотой, пропорциональной разности между “хорошо” и “плохо”. Здесь неясно, какая разность больше.
Хотя в данном примере мы не получили строгого решения, но полученное решение дает ориентацию, как следует себя вести в исходной слабо определенной ситуации.
Для реализации применения игроком его активных стратегий с оптимальными вероятностями (относительными частотами), необходимо иметь случайный механизм выбора стратегий.
Например, если оптимальная смешанная стратегия (относительные частоты 1:1), то для ее реализации можно использовать подбрасывание монеты: если выдает “герб”, то применяется первая стратегия, а если “решка”, - то вторая.
Игральную кость можно использовать при относительных частотах 1:5; 2:4; 1:1; 4:2; и так далее до 5:1.
Секундная стрелка часов может служить для выбора случайных чисел от 0 до 59, если только игрок не смотрел на часы недавно и не знает наперед, даже приблизительно, ответ.
Но на практике могут потребоваться любые сочетания чисел в качестве относительных частот. Механизмом, удовлетворяющим вышеуказанному требованию, является датчик случайных чисел R от 0 до 1 с равномерной плотностью вероятности.
Так как стратегии А1, А2, ..., Аm несовместны (в каждый момент, применяется лишь одна из этих стратегий) и образуют полную группу событий , то для реализации случайного механизма выбора стратегий поступают следующим образом. Делят интервал (0, 1) на m участков длиной p1, p2, ..., pm (рис. 2.12). На какой из участков попало число R - ту стратегию и следует в данной партии использовать.
Рис. 2.12
Возникает вопрос: а как же реализуется сам датчик случайных чисел R? Самый простой из датчиков случайных чисел (ДСЧ) - это вращающийся барабан, в котором перемешивается перенумерованные шары. Пусть, например, нам надо разыграть случайное число R от 0 до 1 с точностью 0.001. Заложим в барабан 1000 перенумерованных шаров и после, случайным образом выбранного одного из шаров, разделим его номер на 1000.
Можно поступить и иначе: вместо1000 шаров заложить только 10, с цифрами 0, 1, 2, .... , 9. Вынув случайным образом первый шар, получаем первый десятичный знак дроби. Вернув шар в барабан и прокрутив его, выберем случайным образом второй шар - его номер даст второй десятичный знак и т.д.
Можно доказать, что получаемые таким образом десятичные дроби будет иметь равномерное распределение от 0 до 1. Достоинством этого способа в том, что он может обеспечить любую точность задания числа R.
На практике широко применяются таблицы случайных чисел. Ниже приведен пример такой таблицы (рис.2.13). Числа сгруппированы лишь для удобства пользования таблицей. Можно начинать с любой точки таблицы, отсчитывать числа вверх или вниз, группировать числа.
Как использовать таблицу случайных чисел, чтобы получить желаемые относительные частоты? Возьмем в качестве примера оптимальную стратегию . Далее выбираем из таблицы любое однозначное случайное число. Если это число равно 0, 1, 2, 3 или 4, то используем в данной партии первую стратегию. Если число равно 5 и 6, то применяем вторую стратегию. Если это число равно 7, 8 и 9, то отбрасываем его и берем число под ним. Для следующей партии используется число ниже предыдущего.
|
11 |
16 |
43 |
63 |
18 |
75 |
6 |
13 |
76 |
74 |
40 |
60 |
31 |
61 |
52 |
||
|
21 |
21 |
59 |
17 |
91 |
76 |
83 |
15 |
86 |
78 |
40 |
94 |
15 |
35 |
85 |
||
|
10 |
43 |
84 |
44 |
82 |
66 |
55 |
83 |
76 |
49 |
73 |
50 |
58 |
34 |
72 |
||
|
36 |
79 |
22 |
62 |
36 |
33 |
26 |
66 |
65 |
83 |
39 |
41 |
21 |
60 |
13 |
||
|
73 |
94 |
40 |
47 |
73 |
12 |
3 |
25 |
14 |
14 |
57 |
99 |
47 |
67 |
48 |
||
|
49 |
56 |
31 |
28 |
72 |
14 |
6 |
39 |
31 |
17 |
61 |
83 |
45 |
91 |
99 |
||
|
64 |
20 |
84 |
82 |
37 |
38 |
60 |
52 |
93 |
41 |
91 |
40 |
27 |
72 |
27 |
||
|
51 |
48 |
67 |
28 |
75 |
64 |
51 |
61 |
79 |
71 |
58 |
99 |
98 |
38 |
80 |
||
|
99 |
75 |
62 |
63 |
60 |
41 |
70 |
17 |
31 |
17 |
40 |
68 |
49 |
99 |
48 |
||
|
71 |
32 |
55 |
52 |
17 |
13 |
1 |
57 |
29 |
7 |
75 |
97 |
86 |
42 |
98 |
||
|
65 |
28 |
59 |
71 |
98 |
12 |
13 |
85 |
30 |
10 |
34 |
55 |
63 |
98 |
61 |
||
|
17 |
26 |
45 |
73 |
27 |
38 |
22 |
42 |
93 |
1 |
65 |
99 |
5 |
70 |
48 |
||
|
95 |
63 |
99 |
97 |
54 |
31 |
19 |
99 |
25 |
58 |
16 |
38 |
11 |
50 |
69 |
||
|
61 |
55 |
57 |
64 |
4 |
86 |
21 |
1 |
18 |
8 |
52 |
45 |
88 |
88 |
80 |
||
|
78 |
13 |
79 |
87 |
68 |
4 |
68 |
98 |
71 |
30 |
33 |
0 |
78 |
56 |
7 |
||
|
62 |
49 |
9 |
92 |
15 |
84 |
98 |
72 |
87 |
59 |
38 |
71 |
23 |
15 |
12 |
||
|
24 |
21 |
66 |
34 |
44 |
21 |
28 |
30 |
70 |
44 |
58 |
72 |
20 |
36 |
78 |
||
|
16 |
97 |
59 |
54 |
28 |
33 |
22 |
65 |
59 |
3 |
26 |
18 |
86 |
94 |
97 |
||
|
59 |
13 |
83 |
95 |
42 |
71 |
16 |
85 |
76 |
9 |
12 |
89 |
35 |
40 |
48 |
||
|
29 |
47 |
85 |
96 |
52 |
50 |
41 |
43 |
19 |
61 |
33 |
18 |
68 |
13 |
46 |
Рис.2.13
Часто желательно модифицировать этот способ. Например, в случае относительных частот 8:3 сумма чисел равна 8+3=11. Приходится применять двухзначные числа от 00 до 99. Но чтобы не отбрасывать числа от 11 до 99, разделим 99 на 11, получаем 9 (в общем случае это будет смешанная дробь). Далее умножаем 89=72 и 39=27. Теперь, если выбранное двухзначное число лежит в пределах от 00 до 71, используем первую стратегию, а если от 72 до 99, - то вторую. Число 99 будем отбрасывать.
Для получения R на ЭВМ применяются специальные датчики случайных чисел. Это могут быть как “физические датчики”, принцип действия которых основан на преобразовании случайных шумов, так и вычислительные алгоритмы, по которым сама машина вычисляет так называемые “псевдослучайные” числа. Один из самых простых алгоритмов вычисления псевдослучайных чисел состоит в следующем. Берут два произвольных n-значных числа a1 и a2 и перемножают их, и в полученном результате берут n средних знаков. Так получают число а3. Затем перемножают а2 и а3 и в полученном результате берут n средних чисел, получая число а4,и т.д. Полученные таким образом числа рассматриваются как последовательность двоичных дробей с n знаками после запятой. Такая последовательность дробей практически ведет себя как ряд случайных чисел R от 0 до 1.
В заключение изложения матричных игр отметим, что хотя само понятие смешанной стратегии требует многократного повторения партий игры, полученные результаты справедливы и к играм, которые играются только один раз, поскольку все изложения теории были выведены применительно к одной партии игры.
Качественно аргументировать этот тезис можно следующим образом: очевидно, что если противник узнает, какую мы выбрали стратегию, то предпримет ход, который будет иметь для нас наихудшие последствия. Поэтому единственным выходом является использование для выбора стратегии случайного механизма (жребия), результат которого противник не может предвидеть (хотя, конечно, ему может и повезти). Теория игр указывает характеристики (частоты применения стратегий), которыми должен обладать используемый случайный механизм.
(В – Верно, Н – Неверно)
Ответы: (1 - В; 2 - В; 3 - Н; 4 – В, 5- В).
Решить матричные игры, имеющие платежные матрицы вида:
|
1. |
8 |
4 |
2 |
2. |
-1 |
1 |
1 |
3. |
1 |
2 |
-5 |
3 |
2 |
|
2 |
8 |
4 |
2 |
-2 |
2 |
-1 |
4 |
7 |
2 |
-4 |
|||
|
1 |
2 |
8 |
3 |
3 |
-3 |
5 |
-1 |
1 |
1 |
3 |
|||
|
4. |
0 |
-13 |
-1 |
5. |
1 |
0 |
-1 |
6. |
3 |
2 |
4 |
||
|
13 |
0 |
-13 |
0 |
2 |
1 |
4 |
3 |
2 |
|||||
|
1 |
13 |
0 |
1 |
-1 |
3 |
2 |
4 |
3 |
|||||
|
7. |
3 |
6 |
0 |
8. |
3 |
0 |
7 |
9. |
203 |
403 |
103 |
||
|
5 |
3 |
2 |
4 |
6 |
0 |
303 |
3 |
103 |
|||||
|
2 |
1 |
6 |
3 |
4 |
3 |
3 |
103 |
303 |
|||||
|
10. |
2 |
-11 |
1 |
11. |
7 |
5 |
4 |
12. |
16 |
0 |
14 |
||
|
15 |
2 |
-11 |
1 |
3 |
7 |
6 |
6 |
16 |
|||||
|
3 |
15 |
2 |
2 |
7 |
4 |
6 |
12 |
2 |
|||||
|
13. |
0 |
1 |
1 |
14. |
-1 |
1 |
0 |
15. |
0 |
2 |
1 |
||
|
1 |
0 |
1 |
0 |
-1 |
1 |
2 |
0 |
2 |
|||||
|
1 |
1 |
0 |
1 |
0 |
-1 |
1 |
2 |
0 |
|
18. |
1 |
6 |
2 |
5 |
19. |
6 |
0 |
1 |
2 |
20. |
4 |
3 |
3 |
2 |
2 |
6 |
|
5 |
1 |
6 |
2 |
0 |
3 |
1 |
0 |
6 |
0 |
4 |
2 |
6 |
2 |
|||
|
2 |
5 |
1 |
6 |
2 |
0 |
3 |
1 |
0 |
7 |
3 |
6 |
2 |
2 |
|||
|
21. |
0 |
-13 |
-3 |
22. |
9 |
6 |
12 |
23. |
2 |
7 |
3 |
6 |
||||
|
13 |
0 |
-13 |
12 |
9 |
6 |
6 |
2 |
7 |
3 |
|||||||
|
1 |
13 |
0 |
6 |
12 |
9 |
3 |
6 |
2 |
7 |
|||||||
|
24. |
12 |
0 |
2 |
4 |
25. |
6 |
-10 |
4 |
26. |
104 |
304 |
4 |
||||
|
0 |
6 |
2 |
0 |
-4 |
-4 |
6 |
204 |
-96 |
4 |
|||||||
|
4 |
0 |
6 |
2 |
-4 |
2 |
-8 |
-96 |
4 |
204 |
|||||||
|
27. |
3 |
1 |
4 |
1 |
6 |
28. |
2 |
3 |
1 |
4 |
29. |
-1 |
-2 |
-3 |
||
|
6 |
3 |
1 |
4 |
1 |
1 |
2 |
5 |
4 |
-3 |
-1 |
-1 |
|||||
|
1 |
6 |
3 |
1 |
4 |
2 |
3 |
4 |
1 |
-1 |
-3 |
1 |
|||||
|
4 |
1 |
6 |
3 |
1 |
4 |
2 |
2 |
2 |
||||||||
|
1 |
4 |
1 |
6 |
3 |
||||||||||||
|
30. |
1/7 |
2/7 |
3/7 |
|||||||||||||
|
3/7 |
1/7 |
1/7 |
||||||||||||||
|
1/7 |
3/7 |
1/7 |
В общих играх число игроков может быть больше двух, некоторые ходы возможно являются случайными, игроки могут иметь по несколько ходов, причем информация о прошедшем может меняться от хода к ходу. Такие игры называются позиционными или играми в развернутой форме.
Пример. Выборы с правом вето.
Пусть три игрока (N=3) выбирают одного из четырех (G=4) кандидатов в президенты. Правило выбора таково: начиная с первого игрока, каждый игрок налагает вето на выбор одного из неотведенных кандидатов. Единственный оставшийся кандидат считается избранным. Функции выигрышей Ui для каждого из игроков в зависимости от выбранного в президенты кандидата имеют вид:
В развернутой форме данная игра может быть представлена в виде следующего дерева игры (рис. 3.1.), где около ветвей поставлены номера отводимых кандидатов, а у конечных вершин – номера победивших кандидатов. Если победил, например, кандидат под номером 4, то выигрыш первого игрока будет равен 7, а для второго и третьего игроков – 4.
Позиционные игры должны включать следующие элементы описания:
Рис.3.1
Число ходов в данной игре не фиксируется. В общем случае, оно зависит от последовательности выборов, исходов. Однако, правила должны гарантировать, что игра в конце концов закончится.
Относительно ходов правила игры имеют следующую структуру. Для первого хода правила указывают его вид. Если это личный ход, то правила перечисляют возможные варианты и указывают игрока, который делает выбор. Если это случайный ход, то перечисляются возможные варианты и обуславливаются вероятности их выбора. Для последующих ходов правила определяют в зависимости от выбора и исходов предыдущих (-1) ходов, будет ли -й ход личным или случайным. Если ход личный, то перечисляются возможные варианты игрока, который будет делать выбор, и определяется информация о выборах и исходах при первых (-1) ходах, которой располагает игрок к моменту своего выбора. Если ход случайный, то перечисляются возможные варианты и вероятности их выбора. Правила, наконец, определяют в зависимости от выборов и исходов в последовательности ходов, когда игра должна закончиться и выигрыш каждого из игроков.
Позиционные игры удобно задавать графически в виде дерева игры (рис.3.2.). Дерево состоит из вершин, соединенных между собой ветвями. Вершины дерева называют еще позициями игры, а его ветви - ходами игрока.
Рис.3.2
Основными свойствами дерева игры являются:
Вершина соответствует определенному состоянию игры перед очередным ходом. Каждую вершину занимает только один игрок, и ей присваивается номер, равный номеру игрока, который делает выбор.
Вершины, соответствующие случайным ходам, обозначают номером 0. Ветви, выходящие из вершины, изображают выборы, которые могут быть сделаны игроком при данном ходе. Вероятности выполнения случайного хода записывают у соответствующих ветвей. Возле конечных вершин дерева указываются исходы игры - значения выигрыша игроков (а в антагонистических играх – выигрыш первого игрока).
Партия начинается с корня (нижней вершины). Каждый ход есть изменение позиции, соответствующее перемещению из одной вершины на какую-нибудь из примыкающих верхних вершин. Число ветвей у вершины равно числу вариантов хода. Партия заканчивается при достижении одной из конечных вершин. Величина называется длиной дерева.
В зависимости от выбора игроков возможно столько различных партий игры, сколько конечных вершин у дерева.
Очевидно, если в игре нет случайных ходов, и каждый из игроков выбрал свою стратегию, то исход игры однозначно определен. Для игры со случайными ходами, результат партии становится случайной величиной, поэтому необходимо случайные выигрыши заменить их математическими ожиданиями. Как совокупность всех решений, которые должен принять игрок, можно описать как одно решение - выбор стратегии, так и совокупность случайных ходов, может быть заменена одним случайным испытанием Н.
В рассматриваемом примере (рис.3.2) случайное испытание Н может иметь следующие исходы:
Н=|(Г,3),(Г,2),(Р,3),(Р,2)|, с вероятностями , где Г - означает выпадение “герба”, Р - “решки”, а цифры 2, 3 соответствуют случайному выбору на четвертом ходу.
Игра, полученная путем усреднения случайных исходов, не полностью эквивалентна исходной игре, так как она характеризует не частный результат отдельной партии, а средние исходы большого числа партий.
Информация, доступная игрокам задается информационным разбиением вершин на множества Vi, называемые классами информации или информационными множествами. Если достигнута вершина vVi, то игроку, который должен ходить, указывается только класс информации, а не точное положение вершины v. Таким образом, в классы информации могут входить несколько вершин, неразличимых игроком, делающим выбор на данном ходе, т.е. игрок не в состоянии различить, какой из нескольких вершин соответствует состояние игры в данный момент времени.
В рассматриваемом примере класс информации V1 состоит из двух вершин. В том случае, когда всякий класс информации содержит только одну вершину, имеем игру с полной информацией (например, игра в шахматы). В играх с неполной информацией содержится хотя бы один класс информации с числом вершин не менее двух.
При вычерчивании дерева игры классы информации обводят замкнутой линией.
Игрок всегда знает, какому классу информации соответствует состояние игры в данный момент, но не знает конкретной вершины этого класса.
Классы информации (информационные множества) должны удовлетворять следующим условиям:
Дерево, изображенное на рис.3.2., соответствует следующей игре:
Первый игрок выбирает одно из двух направлений (“налево” или “направо”). Ход “налево” оценивается тремя баллами, а “направо” - четырьмя. Затем бросается жребий (монета) и, если выпадает герб, второму игроку сообщается предыдущий выбор первого игрока. Если выпадает решка, то второй игрок знает лишь, что он находится в классе информации V1, но не знает, в какой из двух вершин этого класса он находится.
Второй игрок выбирает одно из двух направлений (“налево” или “направо”). Ход “налево” оценивается пятью баллами, а “направо” - двумя. Четвертый ход является опять случайным и состоит в выборе с равными вероятностями одного из направлений: “налево”, “направо”, которые оцениваются тремя и двумя баллами соответственно. Поскольку вероятности выбора направления при случайном ходе одинаковы (равны ), то их можно на графическом изображении дерева игры и не указывать.
Числа, выбранные в первом, третьем и четвертом ходах, складываются, и полученная сумма уплачивается вторым игроком первому, если она четная, в противном случае первый игрок платит второму.
Пространства Ф1 и Ф2 всех возможных стратегий игроков 1 и 2 в рассматриваемом примере следующие:
Ф1=|(3), (4)|;
Ф2=|(3,Г,5),(3,Г,2),(3,Р,5),(3,Р,2),(4,Г,5),(4,Г,2),(4,Р,5),(4,Р,2)|,
где первое число каждой стратегии в пространстве Ф2 соответствует выбору первого игрока, второе число - выпаданию герба или решки (“Г” - выпал “герб”; “Р” - выпала “решка”). Третья - выбору второго игрока пятерки или двойки.
Очевидно, что если в игре нет случайных ходов и каждый из игроков выбрал свою стратегию, то исход игры однозначно определен.
Описание позиционной игры в виде дерева позволяет глубже проанализировать ход игры. Вместе с тем, оптимальное поведение игроков легче определить для игры, заданной в нормальной форме (для двух игроков - в матричной форме), особенно в том случае, если игра содержит информационные множества и случайные ходы.
Решение позиционной игры с полной информацией легко решается в соответствии с теоремой Куна, утверждающей, что данная игра разрешима по доминированию, т.е. для каждого из игроков имеются доминирующие стратегии, которые и необходимо применять.
Для того, чтобы это продемонстрировать, рассмотрим описанную выше игру «Выборы с правом вето». Поскольку из всех вершин, предшествующих конечным, ходит игрок 3, то остальные игроки, зная его функцию выигрыша U3, могут легко предвидеть его решения. Это позволяет привести игру, изображенную на рис.3.1 к следующей:
Рис.3.3
Поскольку в новом дереве игрок 3 уже по существу не принимает решения, то финальная вершина определяется ходами игрока 2. Игрок 1, зная функцию выигрышей U2, может предвидеть поведение игрока 2. В итоге получается игра с одним участником – первым игроком и следующим деревом игры:
Рис.3.4
Поскольку для первого игрока желательна победа четвертого претендента, то он отклонит третьего претендента. Далее второй игрок вынужден будет отклонить второго претендента, а третий игрок – первого. Выигрыши игроков в данной игре равны 7, 4 и 4 соответственно.
Таким образом алгоритм решения позиционных игр с полной информацией, в соответствии с теоремой Куна, состоит в том, что начиная с последнего хода последовательно отбрасываются заведомо худшие для игрока, делающего этот ход, решения. После всех таких редукций получаем решение в чистых стратегиях.
Процесс сведения позиционной игры к игре в нормальной форме называют нормализацией игры. Любая позиционная игра может быть сведена к игре в нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. Для нормализации игры нужно перечислить все возможные стратегии игроков и для каждой совокупности стратегий определить выигрыш игроков. Рассмотрим процесс нормализации позиционной игры на конкретном примере. Пусть игра задана деревом, показанном на рис.3.5.
Рис. 3.5
Первый игрок делает свой первый ход, выбирая правую или левую ветвь. Затем ход делает второй игрок, у которого в каждой вершине также имеется два выбора, после чего игра заканчивается.
В данной игре у первого игрока (игрока А) имеется две чистых стратегии: Ф1=/А1, А2/, где стратегия А1 - всегда выбирать левую ветвь; стратегия А2 - всегда выбирать правую ветвь. Второй игрок (игрок В) имеет больше стратегий:
Ф2=/В1,В2,В3,В4/,
где стратегия В1 - всегда выбирать левую ветвь;
стратегия В2 - всегда выбирать правую ветвь;
стратегия В3 - выбирать ветвь, которую выбрал игрок А;
стратегия В4 - выбирать ветвь, противоположную той, которую выбрал игрок А.
Матрица игры в этом случае имеет вид:
|
Bj |
||||
|
Ai |
B1 |
B2 |
B3 |
B4 |
|
A1 |
4 |
-2 |
4 |
-2 |
|
A2 |
-2 |
3 |
3 |
-2 |
Очевидно, что исходная позиционная игра является игрой с полной информацией. Следовательно, она должна иметь седловую точку, а, следовательно, решение в чистых стратегиях.
Действительно, так как
;
.
и, следовательно, .
Поэтому SA=||1,0|| или SA=||0,1||, а SB=||0,0,0,1||. Цена игры v=-2.
Допустим, что в рассматриваемом примере второму игроку не сообщается выбор, сделанный первым игроком. Тогда в дереве игры на втором ходе появляется класс информации V1, содержащей две вершины второго игрока (рис.3.6)
Рис. 3.6
Количество чистых стратегий второго игрока по сравнению с первым случаем сократится до двух: Ф2=/В1,В2/,
где В1 - всегда выбирать левую ветвь;
В2 - всегда выбирать правую ветвь.
Процесс нормализации приводит к следующей платежной матрице:
|
Bj |
||
|
Ai |
B1 |
B2 |
|
A1 |
4 |
-2 |
|
A2 |
-2 |
3 |
В новой игре ¹, т.е. седловая точка отсутствует. Решение игры в смешанных стратегиях имеет вид:
.
Уменьшение информации, имеющейся у второго игрока на момент принятия решения, привело к уменьшению его выигрыша с 2 до .
Итак для нормализации позиционной игры необходимо:
В зависимости от количества игроков, а также значений их выигрышей путем нормализации позиционные игры можно свести к матричной или бескоалиционной, в частности, биматричной игре, каждые из которых решаются по-своему.
(В – Верно, Н – Неверно)
(Ответы: 1-В; 2-Н; 3-В; 4-Н; 5-Н; 6-В; 7-Н; 8-В; 9-В; 10-В; 11-В; 12-В.)
І. Произвести нормализацию позиционных игр, у которых дерево игры имеет вид, приведенный ниже. У конечных вершин поставлен выигрыш первого игрока, а выигрыш второго игрока противоположен по знаку.
Варианты:
1.
2.
3.
4.
2. Нарисовать дерево следующей позиционной игры «Выбор с правом вето», у которой N игроков выбирают одного кандидата из множества , i N. Правило голосования таково: начиная с игрока 1, каждый игрок последовательно налагает вето на выбор кандидатуры одного из не отведенных кандидатов. Единственный оставшийся кандидат считается избранным. Заданы также функции выигрыша u1, u2, …, uN на множестве С, т.е. выигрыш каждого игрока в зависимости от того, какой кандидат победил. Найти решение, используя теорему Куна.
Варианты:
1. N =2;
u1={2,-5,4}; u2={-2,5,-4}
2. N =2;
u1={2,5,-4,-3,1}; u2={-2-3,4,3,-1}
3. N =3;
u1={1,2,-3,4}; u2={3,2,1,-5}; u3={-2,-3,-1,8}.
4. N =4;
u1={1,2,-2,-3,4}; u2={3,5,1,-7,6}; u3={2,4,-5,-1,1}; u4={2,3,4,1,6}.
Если множество чистых стратегий хотя бы одного из игроков бесконечно, то игры называются бесконечными. Различие между конечными и бесконечными антагонистическими играми приводит к необходимости применять для исследования бесконечных игр более сложный математический аппарат, заменять линейно - алгебраические уравнения функционально - аналитическими, интегральными уравнениями, которые в благоприятных случаях сводятся к системам дифференциальных уравнений. Но, как и во всякой антагонистической игре, в бесконечной антагонистической игре принципом оптимального поведения игроков остается принцип «максимина».
Обозначим через Х и У - произвольные множества, элементы которых являются соответственно стратегиями игроков 1 и 2, а через Н(х, у) - функцию выигрыша игрока 1 в ситуации (х, у). Далее будем считать, что функция Н(х, у) непрерывна на пространстве ситуаций Х*Y и ограничена.
Принцип “максимина” может быть реализован тогда и только тогда, когда существуют и равны смешанные экстремумы:
max inf H(x,y) и min sup H(x,y).
xX; yY yY; xX
Для бесконечных антагонистических игр, в отличие от конечных, существование оптимальных смешанных стратегий не обязательно имеет место.
Пусть, например, X и Y принадлежат (0, 1), а функция выигрыша Н(х,у) = х + у. Очевидно, что если бы 1 и 0 входили в число возможных стратегий игроков, то ситуация (1, 0) соответствовала бы седловой точке. Поскольку эту ситуацию реализовать нельзя, то в описываемой игре можно говорить об оптимальности стратегии игроков «с точностью до произвольного ».
Определение 1. Ситуация в бесконечной антагонистической игре называется ситуацией - равновесия, если для любых стратегий х, у соответственно игроков 1 и 2 имеет место неравенство:
.
Точка , для которой выполняется это соотношение, называется - седловой точкой функции Н.
Определение 2. Стратегии и , составляющие ситуацию - равновесия в бесконечной антагонистической игре, называются - оптимальными стратегиями.
Этот термин отражает тот факт, что такие стратегии являются оптимальными “с точностью до ”. Именно, если отклонение от оптимальной стратегии никакой пользы игроку принести не может, то его отклонение от - оптимальной стратегии может увеличить его выигрыш, но не более чем на .
Теорема 1. Если при всяком , функция Н(х, у) имеет - седловые точки, то
.
Экстремумы и называются соответственно нижним и верхним значениями бесконечной антагонистической игры.
Как и в случае конечных игр, при отсутствии решения в чистых стратегиях, необходимо расширение стратегических возможностей игроков - введение смешанных стратегий.
Смешанными стратегиями в бесконечной антагонистической игре являются вероятностные распределения S(x) и S(y) на множествах их чистых стратегий Х и У. Пара таких вероятностных распределений является статистически независимыми.
Если и - смешанные стратегии игроков 1 и 2, то выигрыши Н(Х,у), Н(х,Y) и H(X,Y) являются по определению математическими ожиданиями:
Для смешанных стратегий в бесконечных антагонистических играх можно доказать теоремы, аналогичные тем, которые справедливы для смешанных стратегий в матричных играх. Покажем методику решения бесконечных антагонистических игр на отдельных примерах для наиболее простого случая – игр на единичном квадрате.
Определение 3. Класс антагонистических игр, в которых х,у Î [0,1] называются играми на единичном квадрате.
В играх на единичном квадрате любая ситуация (х,у) понимается как точка единичного квадрата.
Определение 4. Бесконечная антагонистическая игра на единичном квадрате называется строго выпуклой, если ее функция выигрыша Н(х,у) строго выпукла по у при любом х.
Решение выпуклых игр на единичном квадрате базируется на следующих основных теоремах [2].
Теорема 2. В строго выпуклой игре игрок 2 имеет единственную оптимальную стратегию у*, которая является чистой и является решением уравнения
, где - цена игры.
Теорема 3. Пусть в выпуклой бесконечной антагонистической игре на единичном квадрате с функцией Н(х,у) дифференцируемой по у при любом х, у* - оптимальная чистая стратегия игрока 2, а - цена игры. Тогда:
При этом стратегии и употребляются с вероятностями р и 1-р, где р находится из уравнения
р y(,у*) + (1-р) y(,у*)=0.
Игра «Борьба за рынки»
Пусть одна из фирм (игрок 1) пытается вытеснить другую фирму (игрок 2), имеющую два рынка сбыта, с одного из этих рынков. Общая сумма средств, выделяемых игроком 1 на эту цель, равна единице (Х ). Стратегии игрока 1 состоят в распределении этих средств между двумя рынками. Если на первый рынок направляется сумма х, то на второй - (1-х). Пусть игрок 2 для удержания рынков также располагает единичной суммой средств, и его стратегия будет состоять в выделении суммы у на первый рынок и (1-у) - на второй.
Считается, что игрок 1, добившись превосходства средств на одном из рынков, вытесняет своего противника с этого рынка и получает выигрыш, равный избытку своих средств, который берется с коэффициентом, характеризующим важность рынка (пусть этот коэффициент равен k1 для первого рынка и k2 для второго).
Рассматриваемая игра является игрой на единичном квадрате. В этой игре пара чисел (х, у), где х, у 0,1 являются точками единичного квадрата.
Функция выигрыша в рассматриваемом примере
где h1 h.
Решение.
График зависимости H(х0,y) от у для некоторого х=х0 представлен на рис.4.1.
Рис.4.1
Очевидно, что при любых х0 функция Н (х0, у) является выпуклой функцией от у. Имеем
.
Поэтому цена игры
.
График функции выделен на рис.4.2. жирной ломаной.
Рис.4.2
Первый член под знаком максимума с ростом у убывает, а второй - возрастает. Поэтому при малых значениях у максимум достигается на отрезке k1(1-у), а при больших - на отрезке прямой k2у. Следовательно, минимальное значение этот максимум принимает при таком у*, для которого
, т.е. при
. (4.1)
Таким образом, найденное у* является единственной оптимальной чистой стратегией игрока 2. Она состоит в распределении имеющихся средств между рынками пропорционально важности рынков.
Значение цены игры
. (4.2)
Далее надо найти оптимальную стратегию игрока 1. Случаи ху* и ху* будем рассматривать порознь.
Теорема 3 утверждает, что если Н(х,у) - выпукла и 0у*1, то среди оптимальных стратегий игрока 1 найдется такая, которая является смесью двух активных стратегий и . Для этих стратегий
и . (4.3)
При этом стратегии и употребляются с вероятностями р и (1-р), где р находится из уравнения
(4.4)
Для случая ху* уравнение (4.2) принимает вид
.
откуда =1.
Для случая ху* уравнение (4.2) имеет уже другой вид:
.
откуда =0.
Таким образом, активными стратегиями игрока 1 оказываются: =0; и =1.Поэтому игрок 1 должен применять смешанную стратегию, являющуюся смесью этих двух активных стратегий. Для нахождения вероятности р, используем уравнение (4.4).
Частные производные
.
.
Тогда уравнение (4.4) для данной игры приобретает вид
, откуда
. (4.5)
Таким образом оптимальная стратегия игрока 1 состоит в концентрации всех его средств на одном из рынков, причем вероятность выбора рынка обратно пропорциональна его важности. Этот результат объясняется просто: чем важнее рынок, тем больше средств вложит противник в его сохранение и тем меньше свободных средств останется на нем после вытеснения противника, и тем менее значимой будет победа над ним.
Игра с выбором момента времени (игра типа дуэли)
Формулировка. Пусть каждый из двух игроков намерен выполнить некоторое действие (выбросить на рынок партию товара, внести на совещание предложение, произвести выстрел и т.д.). При этом обстоятельства часто складываются так, что, во-первых, целесообразно выполнить это действие как можно позже, а во-вторых, желательно своим действием упредить сходное действие противника. Такой конфликт в условиях противоположных интересов его участников естественно моделировать бесконечной антагонистической игрой на единичном квадрате, в которой функция выигрыша Н в общем случае имеет вид
(4.6)
где каждая из функций и
а) непрерывна по обеим переменным;
б) монотонно возрастает по х при любых значениях y;
в) монотонно убывает по y при любом значении х;
г) удовлетворяет условию
.
Игра с функцией выигрыша Н(х,у), удовлетворяющая перечисленным условиям называется игрой с выбором момента времени, или игрой типа дуэли.
Мы ограничимся рассмотрением одного примера данной игры, теория которой, хотя и разработана, но достаточно сложна 2.
Пусть игроки 1 и 2 выбирают соответственно числа х и у из интервала . Эти числа будем понимать как моменты времени выполнения ими требуемых действий. Пусть t - время появления некоторого объекта, который достается игроку, который первый после t совершил требуемое действие. Игрок, обладающий объектом, получает выигрыш, равный 1, а его противник эту единицу теряет. Если ни один из игроков не получит объект, то выигрыш каждого из игроков принимается равным нулю.
Предполагается, что время появления объекта является случайной величиной, распределенной на интервале по равномерному закону. Эту игру называют также борьбой за встречу случайно появляющегося объекта.
Запишем математическое выражение функции выигрыша. Рассмотрим ситуацию (х,у), в которой ху. В этом случае игрок 1 выигрывает единицу, если
tх; (4.7)
проигрывает единицу, если
хty; (4.8)
и не получает ничего, если
yt. (4.9)
Вероятность событий (4.7), (4.8) и (4.9) равны соответственно х, (у-х) и (1-у). Таким образом, при ху имеем
. (4.10)
Аналогичным способом находим, что при ху
. (4.11)
Естественно, что при х=у, Н(х,у)=0.
Схематическое описание Н(х,у) приведено на рис.4.3.
Решение. Заметим, что игра является симметричной. Действительно, при ху
.
Аналогично, при ху
.
Наконец, при х=у
.
Рис.4.3
Для антагонистических симметричных игр существует теорема, утверждающая для этих игр цена игры = 0, а оптимальные стратегии игроков 1 и 2 совпадают.
Поэтому для решения данной задачи достаточно найти оптимальную стратегию игрока 1.
Пусть оптимальная стратегия игроков имеет плотность распределения f:
;
.
Если игрок 2 применяет эту стратегию, то
.
С учетом формул (4.10) и (4.11.). перепишем последний интеграл
. (4.12)
Так как и постоянна, то все производные по х функции Н(x,f) также должны обращаться в нуль.
Дифференцируя тождество (4.12) по х, имеем
(4.13)
Вторая частная производная имеет вид
т.е. .
Интегрируя это дифференциальное уравнение, получаем
,
откуда
. (4.14)
Полученная плотность распределения f(x) положительна и дифференцируема. Однако интеграл расходится. Следовательно, плотность f не может быть дифференцируемой и больше нуля на всем сегменте .
Можно доказать, что плотность распределения может обращаться в нуль лишь между нулем и некоторым . Таким образом, имеем:
Для определения неизвестных параметров и с воспользуемся следующими соображениями. Во-первых, f(x) должна удовлетворять условию нормировки:
. (4.15)
Во-вторых, . (4.16)
Из уравнений (4.15) и (4.16) можно определить значения и с. С этой целью перепишем эти уравнения в явном виде.
, т.е.
. (4.17)
Далее на основании симметричности игры
.
Поскольку с0, это нам дает
.
Откуда получаем . Это квадратное уравнение имеет два корня: 1 и . Корень =1 противоречит равенству (4.17), а подстановка в это равенство дает .
Таким образом, искомая оптимальная стратегия игрока 1 определяется плотностью распределения
График f(x) изображен на рис.4.4.
Рис.4.4.
Остается проверить, что найденные стратегии игроков действительно являются оптимальными. Для этого достаточно убедиться в том, что для любого х .
При , ,
поскольку в рассматриваемом случае . При , формула (4.13) дает
.
Тем самым оптимальность стратегии с плотностью f установлена.
(В – Верно, Н – Неверно)
(Ответы: 1-Н; 2-В; 3-В; 4-Н; 5-В; 6-В; 7-Н; 8-В).
Найти хотя бы одно решение бесконечной антагонистической игры на единичном квадрате со следующей функцией выигрыша:
Антагонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны разным ситуациям или вообще не могут считаться приемлемыми.
В частности, антагонистические игры не затрагивают конфликты с числом игроков больше двух. Более того, даже в конфликтах с двумя игроками интересы сторон не всегда противоположны. Во многих конфликтах одна из ситуаций может оказаться предпочтительнее другой для обоих игроков.
Бескоалиционные игры являются играми более общей природы. Бескоалиционность понимается в том смысле, что группам игроков (“коалициям”) не приписывается ни каких-либо интересов, за исключением тех, которые вытекают из интересов отдельных игроков. Целью каждого игрока в такой игре является только получение по возможности наибольшего индивидуального выигрыша.
Определение 1. Бескоалиционной игрой называется игра N игроков (N2), каждый из которых имеет множество стратегий , с функцией выигрыша Нi(x), , где x – ситуация, задаваемая на множество декартового произведения стратегий і.
Определение 2. Бескоалиционная игра называется игрой с постоянной суммой, если существует такое постоянное С, что , для всех ситуаций x.
Класс антагонистических игр является классом игр двух лиц с нулевой суммой.
Определение 3. Конечная бескоалиционная игра двух игроков с ненулевой суммой называется биматричной игрой.
Как и в случае антагонистических игр необходимо выработать принципы оптимального поведения игроков в бескоалиционных играх и найти решения (оптимальные стратегии каждого из игроков).
Для класса антагонистических игр принципом оптимальности является принцип максимина. В общих бескоалиционных играх возможны ситуации одновременного увеличения выигрышей всех игроков или хотя бы их одновременного выигрыша, поэтому в этих играх необходимо ввести формализованное описание таких понятий, как выгодность, устойчивость и справедливость того или иного решения игры.
Определение 4. Ситуация х в игре называется приемлемой для игрока і, если для любой его стратегии
, (5.1)
т.е. при применении і-м игроком в данной ситуации всех других стратегий, его выигрыш не может увеличиться.
Определение 5. Ситуация в игре, приемлемая для всех игроков, называется ситуацией равновесия по Нэшу (равновесной ситуацией).
Иными словами, ситуация х называется равновесной, если для любого игрока іN выполняется условие (5.1).
Из определения видно, что ни один из игроков не заинтересован в отклонении от своей стратегии, образующих в совокупности ситуацию равновесия.
В случае антагонистической игры приемлемые стратегии игроков совпадают с их оптимальными стратегиями. Для неантагонистических игр понятие оптимальной стратегии может вообще не иметь смысла: в таких играх оптимальными оказываются не стратегии отдельных игроков, а их сочетания для всех игроков сразу. В бескоалиционных играх как оптимальные следует квалифицировать не действия того или иного игрока, а совокупность действий всех игроков.
Поэтому в бескоалиционной игре решение игры – это чаще, нахождение ситуаций равновесия.
Пример 1. Игра “Семейный спор”
Одна из наиболее распространенных интерпретаций игры следующая. Муж (первый игрок) и жена (второй игрок) могут выбрать одно из двух вечерних развлечений: футбольный матч или балет. Естественно предположить, что муж предпочтет футбол, а жена – балет. Однако для обоих гораздо важнее идти вместе, чем смотреть предпочитаемое зрелище в одиночестве. В данной 2х2 биматричной игре функции выигрышей Н1 и Н2 соответственного первого и второго игроков можно представить в виде
и ,
где стратегии игрока 1: А1 – выбираю футбол; А2 – иду на балет; игрока 2: В1 – иду на футбол, В2 – на балет.
Очевидно, что для первого игрока предпочтительнее ситуация (А1, В1), а для второго (А2, В2), и эти ситуации являются равновесными. Однако в данном примере как будет показано ниже, есть еще и третья ситуация равновесия, состоящая в выборе игроками смешанных стратегий: ; с ценой игры для обоих игроков .
Однако выигрыши каждого из игроков в этой ситуации равновесия меньше, чем в двух первых ситуациях равновесия, где они равны 2 или 1, в зависимости от ситуации и игрока.
Хотя стратегии (А1,В1) и (А2,В2) являются оптимальными, поскольку дают максимальные выигрыши, однако приносят игрокам не одинаковые выигрыши, поэтому не являются справедливыми.
Отметим также, что если в матричной игре ни одному из игроков не выгодно информировать противника о своей стратегии, то в данной биматричной игре это свойство не выполняется.
Действительно, если игроки не общаются до игры и оба обладают твердыми характерами, т.е. первый игрок выбирает стратегию А1, а второй – В2, то в результате они оба проигрывают. Аналогичная ситуация получиться и в том случае, когда каждый из игроков имеет мягкий характер и решает уступить. Так сочетание устойчивости со справедливостью вступает в противоречие с сочетанием устойчивости и выгодности.
Лучшим для игроков в рассматриваемой игре является договорный вариант (А1,В1) или (А2,В2), причем справедливым решением будет их выбор одного из этих вариантов путем бросания монеты. Выпадение герба будет означать, например, что семейство идет на матч по футболу, а решки – на балет. Заметим, что в антагонистической игре в отличие от биматричной нет смысла вести переговоры до игры и уславливаться о совместном плане действий. В рассматриваемой игре, ясно, что если игроки договорились бы играть оба, скажем первую чистую стратегию, причем игрок 1 за получение большего выигрыша, чем игрок 2, заплатил бы ему 1/2, то решение было бы выгодным и справедливым для обоих игроков. Однако в рамках бескоалиционных игр такого рода дележи не предусматриваются.
Как уже отмечалось, формальное понятие оптимальности призвано отражать различные варианты содержательных представлений об устойчивости, выгодности и справедливости. Можно считать, что устойчивость ситуации проявляется в ее равновесности.
Другой вариант устойчивости ситуации в большей степени, чем равновесность, отражающей черты ее выгодности, состоит в ее оптимальности по Парето1.
Определение 6. Ситуация х0 в бескоалиционной игре называется оптимальной по Парето, если не существует ситуации х, для которой имеет место векторное неравенство
, для всех іІ. (5.2)
Иными словами, в оптимальной по Парето ситуации игроки не могут совместными усилиями увеличить выигрыш кого-либо из них, не уменьшив при этом выигрыш кого-либо другого.
Подчеркнем различие ситуации равновесия от ситуации, оптимальной по Парето: в первой ни один игрок, действуя в одиночку, не может увеличить свой собственный выигрыш; во второй, – все игроки, действуя совместно, не могут (даже нестрого) увеличить выигрыш каждого.
Вопросы об оптимальных по Парето ситуациях решаются в принципе проще, чем аналогичные вопросы о ситуациях равновесия (оптимальных по Нэшу).
Проиллюстрируем графический метод определения ситуаций оптимальных по Парето. На рис. 5.1 изображено множество возможных стратегий х1,х2 двух игроков. Каждой точке х соответствует точка на множестве Н значений функций выигрышей Н1(х) и Н2(х) (рис. 5.2).
Рис. 5.1 Рис. 5.2
На рис. 5.2 дуга АСВ соответствует множеству ситуаций оптимальных по Парето, так как никакими совместными усилиями игроков, нельзя увеличить выигрыш одного из них, не уменьшив при этом выигрыш другого.
Определение 7. Игра называется аффинно эквивалентной игре G, если число игроков , стратегии одной игры , (отсюда следует, что игры и имеют одно и то же множество ситуаций), а функции выигрыша
,
где , .
Различие между двумя аффинно эквивалентными играми по существу состоит в различии начальных капиталов игроков и в соотношениях единиц измерения выигрышей, определяемых соответственно величинами Ci и ki.
Для однородно аффинно эквивалентных игр ki=k, iN.
Очевидно, что для антагонистических игр понятия аффинной эквивалентности и однородной аффинной эквивалентности совпадают.
Теорема 1. Всякая бескоалиционная игра с постоянной суммой аффинно эквивалентна некоторой игре с нулевой суммой.
Теорема 2. Аффинно эквивалентные игры имеют одни и те же оптимальные по Парето ситуации.
Рассмотрим пример для нахождения ситуации оптимальной по Парето.
Пример 2. Игра “Дилемма заключенного”
Каждый из двух игроков располагает двумя стратегиями: А2 и В2 – стратегии агрессивного поведения, а А1 и В1 – миролюбивое поведение. Предположим, что “мир” (оба игрока миролюбивы) лучше для обоих игроков, чем “война”. Случай, когда один игрок агрессивный, а другой миролюбивый, выгоднее агрессору. Пусть матрицы выигрышей игроков 1 и 2 в данной биматричной игре имеют вид
, .
Для обоих игроков агрессивные стратегии А2 и В2 доминируют мирные стратегии А1 и В1. Таким образом, единственное равновесие в доминирующих стратегиях имеет вид (А2,В2), т.е. постулируется, что результатом некооперативного поведения является война. В то же время исход (А1,В1) (мир) дает больший выигрыш для обоих игроков. Таким образом, некооперативное эгоистическое поведение вступает в противоречие с коллективными интересами. Коллективные интересы диктуют выбор мирных стратегий. В то же время, если игроки не обмениваются информацией, война является наиболее вероятным исходом.
В данном случае ситуация (А1, В1) является оптимальной по Парето. Однако эта ситуация неустойчива, что ведет к возможности нарушения игроками установленного соглашения. Действительно, если первый игрок нарушит соглашение, а второй не нарушит, то выигрыш первого игрока увеличится до трех, а второго упадет до нуля и, наоборот. Причем, каждый игрок, не нарушающий соглашение, теряет больше при нарушении соглашения вторым игроком, нежели в том случае, когда они оба нарушают соглашение.
Как видим, в отличие от примера 1 (игра “семейный спор”), где кооперация игроков была им выгодна, в этом примере кооперация не выгодна для игроков.
Определение 8. Стратегии , в игре N лиц с ненулевой суммой называются оптимальными по Нэшу (решением по Нэшу или точкой равновесия по Нэшу), если для каждого
, (5.3)
x
т.е. каждый игрок в ситуации х* получает свой наибольший выигрыш (в той мере, в какой это от него самого зависит).
В рассмотренной игре “семейный спор” ситуации (А1,В1) и (А2,В2) являются решением по Нэшу, а в игре “дилемма заключенного” таковой является ситуация (А2,В2).
В случае антагонистической игры равновесные стратегии игроков совпадают с их оптимальными стратегиями. Для неантагонистических игр понятие оптимальной стратегии игрока нередко вообще не имеет смысла: в таких играх оптимальными оказываются не стратегии отдельных игроков, а их сочетания (ситуации) и притом для всех игроков сразу. Поэтому в общих бескоалиционных играх оптимальными следует понимать совокупность действия всех игроков (ситуацию в игре), которая и является решением игры.
Как и в играх двух лиц с нулевой суммой, игра N лиц с ненулевой суммой может не иметь решение по Нэшу в чистых стратегиях. Приведенное выше определение 7 решения по Нэшу в чистых стратегиях легко обобщается на случай смешанных стратегий путем подстановки смешанных стратегий , представляющих собой вероятностное распределение на множестве чистых стратегий.
Таким образом мы приходим к вероятностному распределению Х на множестве всех ситуаций. Другими словами, ситуация игры в смешанных стратегиях реализует различные ситуации в чистых стратегиях с некоторыми вероятностями. Значение функции выигрыша каждого из игроков оказывается случайной величиной. В качестве значения функции выигрыша принимается математическое ожидание этой случайной величины.
Дж. Нэшем было доказано существование ситуации равновесия для любой конечной бескоалиционной игры.
Теорема Нэша. В каждой бескоалиционной игре существует хотя бы одна ситуация равновесия в классе смешанных стратегий.
Если, кроме того, функции Нi(х) выпуклые вверх, то решение по Нэшу достигается в классе чистых стратегий.
Заметим, что принципиальная важность теоремы Нэша ограничивается существованием ситуации равновесия. Непосредственно применять ее для нахождения таких ситуаций не удается.
Дж. Нэшем была доказана также следующая теорема.
Теорема 2. Конечная бескоалиционная игра имеет симметричные ситуации равновесия, в которых игроки, равноправно входящие в игру согласно ее условиям, фактически оказываются в одинаковом положении.
Ее применение позволяет избежать отдельных ошибок при решении конечных бескоалиционных игр.
Одним из простых классов бескоалиционных игр ход решения которых поддается элементарному описанию являются биматричные игры, представляющие собой бескоалиционную игру двух игроков с ненулевой суммой.
Пусть в биматричной игре игрок 1 имеет m чистых Аі, , а игрок 2 имеет n чистых стратегий Вj, и в каждой ситуации (Ai, Bj) игрок 1 получает выигрыш aij, а игрок 2 – выигрыш bij. Значение обеих функций выигрыша игроков естественно представить в виде пары матриц
Поэтому такие игры и называются биматричными. Используют также запись платежных матриц А и В в следующем виде:
|
а11 b11 |
......... |
a1n b1n |
|
........ |
......... |
........ |
|
am1 bm1 |
......... |
amn bmn |
где “северо-западное” число в каждой клетке обозначает выигрыш первого игрока, а “юго-восточное” – выигрыш второго игрока.
Смешанные стратегии X и Y, естественно, понимаются как векторы, причем
и .
Выигрыш игроков 1 и 2 при применении смешанных стратегий равны:
где Т – означает транспонирование, т.е. вектор строка записывается как вектор столбец; - смешанные стратегии игроков 1 и 2 соответственно.
Определение ситуации равновесия для случая биматричной игры приобретает следующую формулировку. Ситуация (X,Y) в биматричной игре с матрицами выигрышей А и В является равновесной, если
. (5.4)
. (5.5)
Очевидно, что при В = -А биматричная игра превращается в матричную.
В качестве примера рассмотрим биматричную игру «Торг».
Пример. Игра «Торг»
Игрок 1 продает неделимый товар игроку 2. Игрок 1 должен решить, какую назначить цену: высокую или низкую. Для покупателя в принципе приемлемы обе цены. Покупатель не может спорить о цене, он может либо сделать покупку, либо отказаться от нее.
Платежные матрицы игроков имеют вид:
|
Игрок 2 |
|||
|
В1 - покупка |
В2 - отказ |
||
|
Игрок 1 |
А1 – Высокая цена |
10 5 |
0 0 |
|
А2 – Низкая цена |
5 10 |
0 0 |
Описание всех возможных ситуаций в этой игре позволяет определить, что ситуация (А1, В1) является оптимальной по Парето и по Нэшу. Ситуация (А2, В2) также является оптимальной по Парето, но не является устойчивой, т.е. оптимальной по Нэшу.
Рассмотрим способ нахождения устойчивых ситуаций для биматричных игр с произвольным количеством чистых стратегий игроков.
Рассмотрим вначале биматричную игру 2х2 с матрицами выигрышей
,
соответственно игроков 1 и 2. Как и в случае матричных игр, смешанные стратегии полностью описываются вероятностями p и q выбора игроками своих первых чистых стратегий (вторые чистые стратегии выбираются, очевидно, с вероятностями 1-p и 1-q.
Опишем порознь множество приемлемых ситуаций, для каждого из игроков и изобразим эти множества на единичном квадрате p, q, где p[0,1] и q[0,1].
Начнем с описания ситуаций, приемлемых в игре для игрока 1.
Приемлемость ситуации (X,Y) для игрока 1 в биматричной игре означает, что
; (5.6)
, (5.7)
где А1 и А2 – вектор строки, соответствующие первой и второй строке матрицы А, соответственно.
Подчеркнем, что эти условия приемлемости никак не связаны с матрицей В выигрышей игрока 2. Поэтому они будут совпадать с аналогичными условиями матричной игры с платежной матрицей А.
Приемлемость ситуации (X,Y) для игрока 2 означает, что
(5.8)
(5.9)
где В1 и В2 – вектор-столбцы, соответствующие первому и второму столбцу матрицы В, соответственно.
В общем случае, Х=Ip, 1 – pI. Рассмотрим три случая:
а) р = 1, (Х=|1,0|). Тогда выражение (5.6) превращается в тождественное равенство, а условием приемлемости данной ситуации для игрока 1 оказывается неравенство (5.7). Для рассматриваемого случая его можно записать как
; (5.10)
б) р = 0 (Х=|1,0|). В этом случае выражение (5.7) превращается в тождественное равенство, а условием приемлемости данной ситуации для игрока 2 оказывается неравенство (5.6). Для рассматриваемого случая оно имеет вид
; (5.11)
в) 0 р 1 (Х=Ip, 1 - pI). В этом случае оба неравенства (5.6) и (5.7) превращаются в равенство, и условием приемлемости становится
. (5.12)
Опишем ситуации приемлемости (5.10), (5.11) и (5.12) в развернутом виде. Так как
то соотношения (5.10), (5.11) и (5.12) можно соответственно записать как
(5.14)
(5.15)
(5.16)
Таким образом, приемлемые для игрока 1 ситуации (X,Y) могут быть одного из трех типов:
(5.17)
(5.18)
(5.19)
Неравенства (5.17) и (5.18) верны в случае, если а11 + а22 – а12 – а21 > 0. Если а11 + а22 – а12 – а21 < 0, то знак неравенства в соотношениях (5.17) и (5.18) необходимо поменять на противоположный.
Если величина а11 + а22 – а12 – а21 = 0, а а22 – а12 0, то (5.19) не имеет место, поэтому будет выполняться или (5.17) и (5.18), и притом со знаком строгого неравенства.
Если же а11 + а22 – а12 – а21 = 0 и а22 – а12 = 0, то все условия (5.17), (5.18) и (5.19) выполняются тождественно, и приемлемыми для игрока 1 будут вообще все ситуации.
Описание ситуаций приемлемости в развернутом виде для игрока 2 получаем аналогично из неравенств (5.8) и (5.9).
В общем случае Y=|q, 1-q|. Для трех случая получаем:
а) q=1 (Y=|1,0|). В этом случае приемлемость ситуации (X,Y) равносильна неравенству
(5.20)
или в развернутом виде
|p, 1-p|
. (5.21)
б) q=0 (Y=|0,1|). В этом случае приемлемость ситуации (X,Y) определяется неравенством
(5.22)
или в развернутом виде
. (5.23)
в) 0q1 (Y = |q,1–q|). Условие приемлемости
(5.24)
в развернутом виде
. (5.25)
Таким образом, приемлемые для игрока 2 ситуации (X,Y) могут быть одного из трех типов:
(5.26)
(5.27)
(5.28)
Вновь подчеркнем, что неравенства (5.26) и (5.27) справедливы, если их знаменатель больше нуля. Если в11 + в22 – в12 – в21 < 0, то знак неравенства в выражениях (5.26) и (5.27) необходимо поменять на противоположный.
Для определения ситуаций, приемлемых одновременно как для первого, так и для второго игроков, удобно все найденные приемлемые ситуации представить на единичном квадрате (рис. 5.3).
Рис. 5.3
Для случаев, когда а11 + а22 – а12 – а21 0 и b11 + b22 – b12 – b21 0 приемлемые ситуации игроков 1 и 2 составляют трехзвенные зигзаги. Причем, ситуации равновесия во вполне смешанных стратегиях игрока 2 совпадают с поведением игрока 2 в матричной игре с матрицей выигрыша А, а поведение игрока 1 – с поведением игрока 1 в матричной игре с матрицей выигрышей В.
Таким образом, описанное равновесное поведение игроков оказывается ориентированным не столько на максимализацию собственного выигрыша, сколько на минимизацию выигрыша противника. Так, “антагонизм поведения” может возникнуть и при отсутствии “антагонизма интересов”.
В приведенном на рис. 5.3 решении игры три ситуации равновесия, соответствуют точкам R1, R2, R3.
Если бы зигзаги приемлемых ситуаций были одинаковой ориентации, как показано на рис. 5.4, то пересечение приемлемых ситуаций игрока 1 и игрока 2 состояло бы из одной точки R.
Рис. 5.4
При решении биматричных игр большей размерности необходимо решать большую систему линейных неравенств, определяемых выражениями (5.6), (5.7) и (5.8), (5.9), а затем таким же конечно-рациональным путем находить точки пересечения приемлемых ситуаций игрока 1 и игрока 2. Причем, любая конечная бескоалиционная игра имеет конечное и нечетное чисто ситуаций равновесия (решений игры). Поиск ситуаций равновесия в этом случае следует осуществлять с применением ПЭВМ.
Формулировка игры “Борьба за рынки”
Небольшая фирма (игрок 1) намерена сбыть крупную партию товара на одном из двух рынков, контролируемых другой, более крупной фирмой (игрок 2). Для этого оно может предпринять на одном из рынков соответствующие действия (например, развернуть рекламную кампанию). Господствующий на рынках игрок 2 может попытаться воспрепятствовать этому, предприняв на одном из двух рынков предупредительные меры. Игрок 1, не встретивший на рынке препятствий, захватывает его; встретившись с сопротивлением – терпит поражение. Выборы фирмами рынков являются их чистыми стратегиями.
Пусть проникновение игрока 1 на первый рынок более выгодно для него, чем проникновение на второй, но борьба за первый рынок требует больших средств. Например, победа игрока 1 на первом рынке принесет ему вдвое больший выигрыш, чем на втором, но зато поражение на первом рынке полностью его разоряет (проигрыш равен 10), а игрока 2 избавляет от конкурента (выигрыш равен 5).
Описанная биматричная игра может быть задана матрицами выигрышей
Решение игры. В соответствии с выражениями (5.6) и (5.7) приемлемыми ситуациями для игрока 1 будут те, которые удовлетворяют условиям
Рассмотрим три случая:
а) р=1 (X=|1, 0|). В соответствии с выражением (5.10) имеем
Откуда .
б) р = 0 (X=|0, 1|). В соответствии с выражением (5.11) имеем
или .
в) 0 р1 (X=|р, 1 – р|). В соответствии с выражением (5.12) или в развернутом виде (5.19) получаем
Приемлемые ситуации для игрока 2 в соответствии с выражениями (5.26), (5.27) и (5.27) следующие:
а)
б)
в)
Множества всех приемлемых ситуаций игрока 1 и игрока 2 изображены на рис. 5.5 (для игрока 2 соответствующее множество показано пунктиром).
Рис. 5.5
Зигзаги приемлемых ситуаций пересекаются в единственной точке , которая и оказывается единственной ситуацией равновесия. Эта ситуация равновесия является ситуацией равновесия в смешанных стратегиях. Таким образом, оптимальными стратегиями по Нэшу являются и . При этом цена игры для игрока 1
.
Цена игры для игрока 2
.
Смешанные стратегии определяются как случайные величины, реализующиеся в виде чистых стратегий. Дальнейшее расширение понятия стратегии сводится к пониманию новых, обобщенных стратегий, как функции, в которой исходные стратегии принимаются константами. В качестве аргументов, от которых целесообразно рассматривать функции – стратегии, можно брать стратегии других игроков.
Далее мы ограничимся случаем, когда каждый раз рассматривается функция от стратегии только одного игрока.
Определение 9. В бескоалиционной игре всякая функция Fkij : Xk Xj (которая исходя из стратегии Xk игрока k определяет стратегию Xj игрока j называется метастратегией игрока j (в ответ на стратегию игрока k).
Содержательно всякую метастратегию Fkij можно понимать как способ выбора игроком j некоторой своей стратегии в зависимости от получаемой им информации о стратегии, выбираемой игроком k. Если рассматривать ситуацию в бескоалиционной игре как некоторое соглашение, некоторый договор между игроками, а общую стратегию – как принимаемое на себя в договоре обязательство, то метастратегию можно понимать как своего рода условное обязательство: “в случае если игрок k поступит так-то, я, игрок і, выбираю такую-то свою стратегию, а если этак-то, то такую-то”.
Очевидно, множество всех метастратегий і в ответ на стратегию k можно изобразить в степени множеств .
Определение 10. Бескоалиционные игры G, с тем же множеством игроков N, что и игра называется метаигрой над игрой (метарасширением игры Г), если для некоторых j, kN
и для любой метастратегии yiYi и любого игрока іI
,
где xk – стратегия игрока k, входящая в ситуацию , Н – функция выигрышей в игре Г.
Очевидно, процесс образования метаигр (метарасширений игр) поддается неограниченному интегрированию: от метаигры можно переходить к ее метаигре (называемой второй метаигрой), от нее к третьей метаигре и т.д. В этом отношении метарасширения игр отличаются большим разнообразием, чем смешанные расширения.
Для метастратегических расширений доказаны следующие важные теоремы.
Теорема 3. Каждая конечная бескоалиционная игра двух лиц имеет в своем первом метарасширении ситуации равновесия.
Доказанная теорема не противоречит той возможности, что ситуацией равновесия может обладать уже сама исходная игра Г.
Теорема 4. Каждая конечная бескоалиционная игра двух лиц имеет в своем третьем метарасширении ситуацию, которая является одновременно ситуацией равновесия и оптимальной по Парето.
Пример. Биматричная игра 2х2 имеет следующие матрицы выигрышей игроков А и В:
В соответствии с выражениями (5.17), (5.18) и (5.19) находим приемлемые ситуации (X,Y) игрока 1:
а) (q может быть в любом интервале [0, 1];
б) (ситуация невозможна);
в) (ситуация невозможна).
В соответствии с выражениями (5.25), (5.27) и (5.28) находим приемлемые ситуации (X,Y) игрока 2:
а) (р может быть любым в интервале [0, 1];
б) (ситуация невозможна);
в) (ситуация невозможна);
Для наглядности на рис. 5.6 изображены зигзаги, описывающие и невозможные ситуации за пределами допустимых изменений вероятностей p,q).
Рис. 5.6
Единственной ситуацией равновесия в рассматриваемой игре оказывается ситуация (1,1). В этой ситуации каждый из участников теряет 8. Вместе с тем очевидно, что в ситуации (0,0) каждый игрок теряет лишь по единице. Однако эта ситуация неустойчива, каждый игрок, изменяя в ней произвольным образом свою стратегию, увеличивает свой выигрыш.
Множество всех реализуемых векторов выигрышей для рассматриваемой игры имеет вид, изображенный на рис. 5.7.
Рис. 5.7
Очевидно, что ситуации с выигрышами (–1, –1), (–10,0), (0,–10) являются оптимальными по Парето. При этом первая из них, в которой получаются наибольшие выигрыши (–1,–1) для каждого из игроков лучше, чем равновесная.
Противоречие между осуществимостью ситуации, выражаемой в виде равновесности и ее выгодности, которой соответствует оптимальность по Парето, имеет по существу ту же природу, что и противоречие между максиминным и минамаксным выигрышами. Поэтому оно должно разрешаться при помощи аналогичных приемов, состоящих в расширении уже имеющихся стратегий, т.е. переходу к метарасширениям.
Первая метастратегия игрока 2 состоит в выборе им своей второй стратегии в ответ на вторую стратегию игрока 1 и первой стратегии в ответ на первую.
Вторая метастратегия игрока 1 состоит в выборе им второй своей стратегии, если игрок 2 выберет ту же стратегию, что и 1 и в выборе им своей первой стратегии во всех остальных случаях.
Содержательно это можно представить себе так, что игрок 2 исходит из тезиса “око за око”, а игрок 1 – из более изощренных соображений, которые можно расценить как эгоцентризм (“поддерживать тех, кто действует так же, как я) и ксенофобию (“выступаю против всех тех, кто действует иначе, чем я”).
(В – Верно, Н – Неверно)
(Ответы: 1 – В; 2 – Н; 3 – В; 4 – В; 5 – В; 6 – В; 7 – В; 8 – В; 9 – Н; 10 – Н; 11 – Н; 12 – В; 13 – В; 14 – Н; 15 – В; 16 – В; 17 – В.)
І. Найти ситуации оптимальные по Парето и ситуации устойчивые по Нэшу для следующих биматричных игр:
1.
2.
3.
4.
5.
6.
7.
8.
ІІ. Решить бескоалиционную игру “Экологический конфликт”.
Формулировка игры. Два промышленных предприятия (А и В), расположенные вблизи обширного водоема, берут из него воду для технических нужд и после использования сбрасывают ее обратно в водоем. Если суммарный объем сбрасываемой (загрязненной) воды не превышает некоторого предела , то происходит ее естественное очищение, и общий водный ресурс сохраняется. Если же указанный предел нарушен, то загрязненность водоема интенсивно растет. Возникает проблема его восстановления за счет предприятий и уплаты штрафов, общая стоимость чего составляет .
Чтобы избежать неприятных последствий, приходится строить очистные сооружения, состоящие из отдельных стандартных блоков, рассчитанных на определенные объемы пропускаемой через них воды (пусть каждый блок восстанавливает 25% используемой воды). Затраты на приобретение, монтаж и эксплуатацию одного блока равны С.
Суть конфликта, возникающего между предприятиями, сводится к их стремлению обеспечить себе благоприятные условия деятельности путем более свободного расходования природной воды. Это отрицательно влияем на состояние источника и через него – на ход производства, качество продукции обоих предприятий. Все оказывается взаимосвязанным, и появляется заинтересованность в поиске решений, приемлемых для конфликтующих сторон, хотя никакой договоренности между ними не предусматривается.
Математическая модель. Данный конфликт можно представить как бескоалиционную игру двух лиц следующим образом.
Пусть количество воды, потребляемой каждым предприятием в его технологическом цикле равно единице (100 т, 10 цистерн, и т.д.). Количество очищаемой воды составляет 1 – х на предприятии А; 1 – y на предприятии В, где чистые стратегии игрока А = |0; 0,25; 0,5; 0,75; 1|, в зависимости от числа применяемых очистных блоков. Чистые стратегии игрока В = |0; 0,25; 0,5; 0,75; 1|.
Расходы предприятия А составляют:
4С(1 – х), если х + у ;
4С(1 – х) + , если х + у ,
а расходы предприятия В –
4С(1 – у), если х + у ;
4С(1 – у) + , если х + у .
Данные формулы позволяют составить платежные матрицы игроков А и В. Для случая имеем
|
В А |
В4 |
В3 |
В2 |
В1 |
В0 |
|
А4 |
4С 4С |
4С 3С |
4С+ 2С+ |
4С+ С+ |
4С+ |
|
А3 |
3С 4С |
3С+ 3С+ |
3С+ 2С+ |
3С+ С+ |
3С+ |
|
А2 |
2С+ 4С+ |
2С+ 3С+ |
2С+ 2С+ |
2С+ С+ |
2С+ |
|
А1 |
С+ 4С+ |
С+ 3С+ |
С+ 2С+ |
С+ С+ |
С+ |
|
А0 |
4С+ |
3С+ |
2С+ |
С+ |
|
Индекс при чистых стратегиях игроков указывает на количество используемых очистных блоков (например А3 – предприятие А использует 3 очистных блока; В0 – предприятие В не использует ни одного очистного блока).
Найти ситуации оптимальные по Парето и ситуации равновесия по Нэшу при следующих исходных данных:
9. С ; 10. С ;
11. 5С = ; 12. 5С = ; ;
13. 4С = ; ; 14. 2С = ; ;
15. 2С = ;; 16. С = 3; ;
17. С = 2; ; 18. С = ; ;
19. С = ; ; 20. С = 4; .
ІІІ. Найти множества всех ситуаций оптимальных по Парето в следующих биматричных играх:
21.
22.
23.
24.
25.
26.
27.
28.
1 В.Парето – итальянский экономист.
PAGE 4