Размещено на http://www.allbest.ru/

удк 519.83 + 519.86

Василевич Л.Ф. Теория игр. КИИМ, 2000

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

игра программирование матричный



1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР И ИХ КЛАССИФИКАЦИЯ

1.1 Предмет и задачи теории игр

Первую попытку создать математическую теорию игр предпринял в 1921 г. Э.Борель. Как самостоятельная область науки впервые теория игр была систематизировано изложена в монографии Дж.фон Неймана и О.Моргенштерна “Теория игр и экономическое поведение” в 1944 г. С тех пор многие разделы экономической теории (например, теория несовершенной конкуренции, теория экономического стимулирования и др.) развивались в тесном контакте с теорией игр [2]. Теория игр с успехом применяется и в социальных науках (например, анализ процедур голосования, поиск равновесных концепций, определяющих кооперативные и некооперативные поведения лиц). Как правило, избиратели отводят кандидатов, представляющих крайние точки зрения, но при избрании одного из двух кандидатов, предлагающих различные компромиссные решения, возникает борьба. Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке зрения на кооперацию.

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

Примерами конфликтной ситуации являются ситуации, складывающиеся во взаимоотношениях покупателя и продавца; в условиях конкуренции различных фирм; в ходе боевых действий и др. Примерами игр являются и обычные игры: шахматы, шашки, карточные, салонные и др. (отсюда и название “теория игр” и ее терминология).

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

Теория игр - это математическая теория конфликтных ситуаций.

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

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

Теория игр, как и всякая математическая модель, имеет свои ограничения. Одним из них является предположение о полной (“идеальной”) разумности противников. В реальном конфликте зачастую оптимальная стратегия состоит в том, чтобы угадать, в чем противник “глуп” и воспользоваться этой глупостью в свою пользу [1].

Еще одним недостатком теории игр является то, что каждому из игроков должны быть известны все возможные действия (стратегии) противника, неизвестно лишь то, каким именно из них он воспользуется в данной партии. В реальном конфликте это обычно не так: перечень всех возможных стратегий противника как раз и неизвестен, а наилучшим решением в конфликтной ситуации нередко будет именно выход за пределы известных противнику стратегий, “ошарашивание” его чем-то совершенно новым, непредвиденным [1].

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

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

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

В настоящее время ведутся научные исследования, направленные на расширение областей применения теории игр.

1.2 Терминология и классификация игр

В теории игр предполагается, что игра состоит из ходов, выполняемых игроками одновременно или последовательно.

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

Совокупность ходов, предпринятых игроками от начала до окончания игры, называется партией.

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

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

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

Повторим, что задача теории игр - нахождение оптимальных стратегий.

Классификация игр представлена на рис. 1.1.

1. В зависимости от видов ходов игры подразделяются на стратегические и азартные. Азартные игры состоят только из случайных ходов - ими теория игр не занимается. Если наряду со случайными ходами есть личные ходы, или все ходы личные, то такие игры называются стратегическими.

2. В зависимости от числа участников игры подразделяются на парные и множественные. В парной игре число участников равно двум, в множественной - более двух.

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

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

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

Рис. 1.1. Классификация игр

Исходом кооперативной игры является дележ выигрыша коалиции, который возникает не как следствие тех или иных действий игроков, а как результат их наперед определенных соглашений.

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

4. По количеству стратегий каждого игрока игры подразделяются на конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).

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

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

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

7. Если любая возможная партия некоторой игры имеет нулевую сумму выигрышей f_i, всех N игроков (), то говорят об игре с нулевой суммой. В противном случае игры называются играми с ненулевой суммой.

Очевидно, что парная игра с нулевой суммой является антагонистической, так как выигрыш одного игрока равен проигрышу второго, а следовательно цели этих игроков прямо противоположны.

Конечная парная игра с нулевой суммой называется матричной игрой. Такая игра описывается платежной матрицей, в которой задаются выигрыши первого игрока. Номер строки матрицы соответствует номеру применяемой стратегии первого игрока, столбец - номеру применяемой стратегии второго игрока; на пересечении строки и столбца находится соответствующий выигрыш первого игрока (проигрыш второго игрока).

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

1.3 Примеры игр

Игра 1. Зачет

Пусть игрок 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-Н.)



2. МАТРИЧНЫЕ ИГРЫ

2.1 Описание матричной игры

Наиболее разработанной в теории игр является конечная парная игра с нулевой суммой (антагонистическая игра двух лиц или двух коалиций), называемая матричной игрой.

Рассмотрим такую игру G, в которой участвуют два игрока А и В, имеющие антагонистические интересы: выигрыш одного игрока равен проигрышу второго. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, можем интересоваться только выигрышем а игрока А. Естественно, игрок А хочет максимизировать а, а игрок В - минимизировать а. Для простаты отождествим себя мысленно с одним из игроков (пусть это будет игрок А), тогда будем называть игрока В - “противник” (разумеется, каких-то реальных преимуществ для А из этого не вытекает).

Пусть у игрока А имеется m возможных стратегий А₁, А₂, ..., А_m, а у противника - n возможных стратегий В₁, В₂, ..., B_n (такая игра называется игрой m х n). Обозначим через a_ij выигрыш игрока А, в случае, если он воспользуется стратегией А_i, а игрок В - стратегией В_j. Предполагается, что выигрыш a_ij известен. Тогда мы можем составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (рис.2.1).

Bj Ai	B1	B2	...	Bn
A1	a11	a12	...	a1n
A2	a21	a22	...	a2n
...	...	...	...	...
Am	am1	am2	...	amn

Рис. 2.1.



Если такая таблица составлена, то говорят, что игра G приведено к матричной форме. Отсюда рассматриваемая игра и получила название матричная. Само по себе приведение игры к такой форме уже может составить трудную задачу, а иногда и невыполнимую, из-за необозримого множества возможных стратегий игроков и трудности определения выигрышей a_ij.

Рассмотрим некоторые задачи, решение которых сводится к решению матричных игр.

Игра 1. Вариант игры «Морра»

Игра состоит в том, что каждый из двух игроков независимо друг от друга выбирает определенную сторону монеты (“герб” или “решка”), затем одновременно называют свой выбор. Если игроки выбрали одну и ту же сторону монеты, то второй игрок платит первому одну гривну, если разные, то первый платит второму такую же сумму. Легко видеть, что матрица выигрышей (платежная матрица) этой игры имеет вид

Bj Ai	B1	B2
A1	1	-1
A2	-1	1

Здесь стратегии А₁ и В₁ - игроки А и В выбирают “герб”, а А₂ и В₂ - игроки А и В выбирают “решку”.

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

Игра 2. Борьба за рынки

Фирмы А и В производят одинаковый товар и в настоящее время каждая «контролирует» 50% рынка. Улучшив качество товара, обе фирмы собираются развернуть рекламные кампании. При этом, приобретение новых покупателей одной фирмой сопровождается потерей этих покупателей другой фирмой. Исследование показало, что 60% потенциальных покупателей получают информацию через телевидение, 30% - через газеты и 10% - через радиовещание.

Задача каждой фирмы - выбрать стратегию рекламной кампании.

В данной игре у каждого из игроков по три стратегии:

А₁, В₁ - рекламировать товар через телевидение;

А₂, В₂ - через газеты;

А₃, В₃ - через радиовещание.

Поскольку это игра с нулевой суммой, то матрицу выигрышей фирмы А можно представить в следующем виде:

	B1	B2	B3
A1	0	30	50
A2	-30	0	20
A3	-50	-20	0

где a_ij - количество покупателей товара фирмы А в процентах, на которое оно увеличивается, если фирма А применяет стратегию А_i , а фирма В - стратегию В_j.

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

Как видно, принцип максимина - это принцип крайне осторожного игрока, но именно он является основным принципом теории матричных игр.

Для пояснения принципа максимина рассмотрим пример 1 матричной игры G (4х5) с платежной матрицей, приведенной на рис. 2.2.

Какой стратегией игроку А воспользоваться? Есть соблазнительный выигрыш 12, при применении стратегии А₃. Но при этом противник может выбрать стратегию В₃, и игрок А получит выигрыш, равный всего трем.

Для определения оптимальной стратегии в соответствии с принципом максимина, запишем в правом добавочном столбце платежной матрицы минимальное значение _i в каждой строке (минимум строки). Из всех значений _i (правый столбец) выделим наибольшее. Ему соответствует стратегия А₄. Выбрав эту стратегию, мы во всяком случае можем быть уверены, что при любом поведении противника выигрыш будет не менее пяти.

Эта величина - наш гарантированный выигрыш. Он называется нижней ценой игры (или «максимином» - максимальный из минимальных выигрышей). Будем обозначать его . В нашем примере = a_ij =5.

Теперь станем на точку зрения игрока В и порассуждаем за него. Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наихудшее для него поведение игрока А.

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

Очевидно, осторожный противник должен выбрать стратегию, при которой величина _j минимальна. Эта величина называется верхней ценой игры (или “минимаксом” - минимальный из максимальных проигрышей). Будем обозначать ее . В нашем примере = a_ij = 7.

Итак, исходя из принципа осторожности, игрок А должен выбрать стратегию А₄, а его противник - В₃. Такие стратегии называются максиминными или минимаксными стратегиями (вытекающие из принципа максимина).

До тех пор, пока обе стороны в нашем примере будут придерживаться своих максиминных стратегий, выигрыш игрока А и проигрыш игрока В будет равен а₄₃=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*) называется седловой точкой платежной матрицы ||a_ij||, если для всех остальных i и j этой матрицы выполняется условие

a_i*j a_i*j* a_ij*,

т.е. а_ij является одновременно минимумом своей строки и максимумом своего столбца.

Приведем без доказательства следующую теорему.

Теорема 1. Для того чтобы

необходимо и достаточно, чтобы матрица ||a_ij|| имела седловую точку. Кроме того, если (i^*, j^*) - седловая точка матрицы ||a_ij||, то

Говорят, что матричная игра имеет седловую точку, если соответствующая ей матрица выигрышей (платежная матрица) имеет седловую точку.

Пример. Найти решение игры 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. Найти решение игры 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 и запишем их в таблицу.

Находим нижнюю и верхнюю цену игры:

; . Видно, что игра имеет четыре седловые точки с соответствующими парами оптимальных стратегий: А₁В₂; А₁В₄; А₃В₂ и А₃В₄. Цена игры равна 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



2.3 Чистые и смешанные стратегии

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

Определение. В антагонистической игре пара стратегий (А_i, В_j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

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

В рассмотренном в 2.2 примере 1 максиминные чистые стратегии А₄ и В₅ неустойчивы по отношению к информации о поведении противника; они не обладают свойством равновесия.

Действительно, предположим, что мы узнали, что противник придерживается стратегии В₃. Используя эту информацию, выберем стратегию А₁ и получим больший выигрыш, равный 7. Но если противник узнал, что наша стратегия А₁, он выберет стратегию В₄, сведя наш выигрыш к 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, т.е. игра имеет седловую точку.

Оказывается, что в этом случае максиминные стратегии А₂ и В₂ будут устойчивыми по отношению к информации о поведении противника.

Действительно, пусть игрок А узнал, что противник применяет стратегию В₂. Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А₂, потому что любое отступление от стратегии А₂ только уменьшит выигрыш. Равным образом, информация, полученная игроком В, не заставит его отступить от своей стратегии В₂.

Пара стратегий А₂ и В₂ обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.

Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.

Стратегии А_i и В_j (в рассматриваемом примере А₂, В₂), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.

Величина называется ценой игры.

Если 0, то игра выгодна для игрока А, если 0 - для игрока В; при =0 игра справедлива, т.е. является одинаково выгодной для обоих участников.

Однако наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.

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

Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной чистой стратегии она должна кончаться выигрышем, равным цене игры. Скажем, шахматная игра, как игра с полной информацией, либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей (только чем именно - мы пока не знаем, так как число возможных стратегий в шахматной игре огромно).

Если матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.

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

Определение. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией.

Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии.

Будем обозначать смешанные стратегии игроков А и В соответственно

S_A=||p₁, p₂, ..., p_m||,

S_B=||q₁, q₂, ..., q_n||,



где p_i - вероятность применения игроком А чистой стратегии А_і; ;

q_j - вероятность применения игроком В чистой стратегии B_j; .

В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.

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

Если игрок А применяет смешанную стратегию S_A=||p₁, p₂, ..., p_m||, а игрок В смешанную стратегию S_B=||q₁, q₂, ..., q_n||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением

.

Естественно, что ожидаемый проигрыш игрока В равен такой же величине.

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

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



2.4 Основные теоремы матричных игр

Если игрок А выбирает смешанную стратегию S_A=||p₁, p₂, ..., p_m||, а игрок В смешанную стратегию S_B=||q₁, q₂, ..., q_n||,то средний выигрыш математическое ожидание выигрыша игрока А (проигрыша игрока В) определится суммой

,

которая может рассматриваться в качестве характеристики выбранных S_А и S_B.

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

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

.

Весьма важным для теории и практики является вопрос о том, связаны ли между собой v_А и v_B. Ответ на него дает теорема о максимине.

Теорема о максимине. В конечной игре двух игроков (коалиций) с нулевой суммой (матричной игре) при имеет место равенство

.

Теорема о максимине указывает на существование равновесия для случая v_А=v_B, при и, следовательно, существования оптимальных смешанных стратегий.

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

Основная теорема матричных игр. Любая матричная игра имеет, по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену v.

Обе эти теоремы эквивалентны. Из этих теорем следует, что любая матричная игра имеет цену v. Цена игры v - средний выигрыш, приходящийся на одну партию, - всегда удовлетворяет условию

,

т.е. лежит между нижней и верхней ценами игры.

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

Эта пара стратегий образует в игре положение равновесия: один игрок хочет обратить выигрыш в максимум, другой - в минимум, каждый “тянет” в свою сторону и, при оптимальном поведение обоих, устанавливается равновесие и устойчивый выигрыш .

Определение. Те из чистых стратегий игроков А и В, которые входят в их оптимальные смешанные стратегии с вероятностями, не равными нулю, называются активными стратегиями.

Существует теорема об активных стратегиях, применение которой позволяет упрощать решение некоторых матричных игр.

Теорема об активных стратегиях. Если один из участников матричной игры G (mxn), придерживается своей оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий (т.е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях), причем число активных стратегий каждого игрока, входящих в их оптимальные смешанные стратегии, не превосходит L, где L = min(m, n).

Использование данной теоремы позволяет в частности, упрощать решение матричных игр 2xn и mx2.

ТЕСТЫ

(В - Верно, Н - Неверно)

1. В антагонистической игре пара стратегий (A_i, B_j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

2. Стратегии, соответствующие седловой точке платежной матрицы, не обладают свойством равновесия (устойчивости).

3. Игра решается в чистых стратегиях если платежная матрица имеет седловую точку.

4. Игра решается в чистых стратегиях, если нижняя цена платежной матрицы равна верхней.

5. Игры с полной информацией всегда имеют седловую точку.

6. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией.

7. Если игрок А применяет смешанную стратегию S_A=||p₁, p₂, ..., p_m||, а игрок В смешанную стратегию S_B=||q₁, q₂, ..., q_n||, то средний выигрыш игрока А определяется соотношением

8. Если матричная игра не имеет седловой точки, то игроки должны использовать оптимальные смешанные стратегии.

9. Оптимальные смешанные стратегии в отличие от оптимальных чистых стратегий не обладают свойством равновесия (устойчивости).

10. Те из чистых стратегий игроков, которые входят в их оптимальные смешанные стратегии с вероятностями, не равными нулю, называются активными стратегиями.

11. Любая, матричная игра имеет по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену .

12. Теорема о максимине утверждает, что

.

13. При оптимальных смешанных стратегиях цена игры удовлетворяет условию .

14. Теорема об активных стратегиях утверждает, что если игрок придерживается свой оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, независимо от того, какие действия предпринимает другой игрок, если только тот не выходит за пределы своих активных стратегий.

(Ответы: 1-В; 2-Н; 3-В; 4-В; 5-В; 6-В; 7-Н; 8-В; 9-Н; 10-В; 11-В; 12-В; 13-В; 14-В.)



2.5 Решение матричной игры (2х2)

Пусть матричная игра G (2x2) имеет платежную матрицу

Bj Ai	B1	B2
A1	a11	a12
A2	a21	a22

Предположим, что игра не имеет седловой точки, т.е. . При наличии седловой точки решение очевидно.

В соответствии с основной теоремой игра имеет оптимальное решение в смешанных стратегиях: S_A=||p₁, p₂|| и S_B=||q₁, q₂||, где вероятности применения (относительные частоты применения) чистых стратегий удовлетворяют соотношениям

; (1)

. (2)

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

, (3)



а при использовании игроком В чистой активной стратегии В₂, выигрыш будет равен

. (4)

Уравнения (1), (3) и (4) образуют систему трех линейных алгебраических уравнений с тремя неизвестным:

р₁, р₂ и .

Решая ее, легко находим, что

. (5)

. (6)

. (7)

Если игрок В использует свою оптимальную смешанную стартегию, а игрок А - свою чистую активную стратегию А₁, то цена игры равна

, (8)

а при использовании игроком А чистой активной стратегии А₂, выигрыш будет равен

. (9)



Уравнения (2), (8) и (9) образует систему трех линейных алгебраических уравнений с тремя неизвестными: q₁; q₂ и .

Решая ее, легко находим, что

. (10)

. (11)

. (12)

Естественно, что в обоих случаях цена игры (выражения (7) и (12)) получилась одна и та же.

Чтобы соотношения (5), (6), (7), (10), (11), (12) имели смысл, необходимо потребовать, чтобы

или

Тогда 0<p₁<1; 0<p₂<1; 0<q₁<1; 0<q₂<1.

Нетрудно заметить, что в этих неравенствах отражено предположение об отсутствии в рассматриваемой игре седловой точки. Действительно, ни один из четырех выигрышей а₁₁, а₁₂, а₂₁, а₂₂ не может удовлетворить этим неравенствам, будучи минимальным в своей строке и максимальным в своем столбце.

Решения системы уравнений (5), (6), (7) и (10), (11), (12), полученные алгебраическим методом, удобно получать и графическим методом. Для нахождения вероятностей р₁, р₂ и цены игры v в прямоугольной системе координат по оси абсцисс откладывается вероятность р₁[0,1], а по оси ординат - соответствующие этой вероятности - выигрыши игрока А.

При р₁=0, игрок А применяет чистую стратегию А₂. Если при этом игрок В применяет чистую стратегию В₁, то выигрыш игрока А равен а₂₁ (уравнение (3)), а если игрок В применяет чистую стратегию В₂, то выигрыш игрока А равен а₂₂ (уравнение (4)). При р₁=1, игрок А применяет чистую стратегию А₁.

Рис. 2.4

Если при этом игрок В применяет чистую стратегию В₁, то выигрыш игрока А равен а₁₁, а при применении чистой стратегии В₂ - а₁₂. Так как значения р₁ лежат в пределах [0,1], то соединяя крайние точки для стратегий В₁ и В₂ (строя графики функций v_А=(a₁₁-a₂₁)p₁+a₂₂ и v_А=(a₁₂-a₂₂)p₁+a₂₂), получаем значения выигрышей игрока А для всех промежуточных значений р₁.

В соответствии с принципом максимина, игрок А должен выбрать такую смешанную стратегию, при которой его минимальный выигрыш максимален. Точка N пересечения отрезков прямых и определяет как оптимальную цену игры v_opt, так и оптимальные вероятности p_1opt и p_2opt=1-p_1opt, соответствующие оптимальной смешанной стратегии игрока А, т.е. дает решения системы уравнений (5), (6), (7).

Для графического решения системы уравнений (2), (11), (12) отложим по оси абсцисс вероятность q₁[0,1], а по оси ординат соответствующие этой вероятности выигрыши игрока В:

v_В=(a₁₁-a₁₂)q₁+a₁₂; (13)

v_В=(a₂₁-a₂₂)q₁+a₂₂. (14)

Рис. 2.5

Решением являются координат точки М пересечения прямых, описываемых уравнений (13) и (14):

q_1opt;q_2opt=1-q_1opt и v_opt.



Это же следует и из принципа максимина, в соответствии с которым игрок В должен выбрать такую смешанную стратегию, при которой его максимальный проигрыш будет минимальным.

Для игры G(2х2) с седловой точкой геометрическая интерпретация решения быть представлена, например, следующим образом

Стратегия В₂ игрока В является для него явно невыгодной, так как, применяя ее, он в любой случае проигрывает больше, чем при применении стратегии В₁. В данной игре р_1opt=1;р_2opt=0; v_opt=а₁₁, т.е. игра имеет седловую точку N и решается в чистых стратегиях. Игрок А должен применять стратегию А₁, а игрок В - стратегию В₁.

На показан случай, в котором решением игры для игрока А является чистая стратегия А₂, а для игрока В - стратегия В₁.

Игра имеет седловую точку N.

Пример: Найти алгебраическим и геометрическим методами решение игры, платежная матрица которой имеет вид

Bj Ai	B1	B2	i
A1	4	-2	-2
A2	1	3	1
j	4	3



Рис. 2.7

В данной игре нижняя цена игры =1 не равна верхней цены игры =3, поэтому игра не имеет седловой точки и, в соответствии с основной теоремой матричных игр, имеет оптимальное решение в смешанных стратегиях.

Для игрока А, в соответствии с формулами (5) и (6), оптимальные вероятности применения стратегий А₁ и А₂ равны:

;

.

Для игрока В, в соответствии с формулами (10) и (11), оптимальные вероятности применения стратегий В₁ и В₂ равны:

;

.



Таким образом, оптимальные смешанные стратегии игроков ; , а цена игры в соответствии с формулой (2.22) равна:

.

Так как , то игра выгодна для игрока А.

Нижняя граница выигрыша игрока А определяется ломаной 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

2.6 Упрощение матричных игр

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

Определение 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

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



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

Из этой матрицы видно, что в ней некоторые стратегии игрока В доминируют над другими: В₃ над В₂, В₄ и В₅. Отбрасывая доминируемые стратегии В₂, В₄ и В₅, получаем игру 3x2, имеющей платежную матрицу вида: