XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 48
Текст из файла (страница 48)
Как мы уже отмечали, смешанные стратегии представляют собой математическую модель гибкой тактики, при использовании которой противник не знает заранее, с какой обстановкой ему придется столкнуться в каждой следующей партии игры. При этом ожидаемые теоретические результаты игры, при неограниченном возрастании числа разыгрываемых партий, стремятся к их истинным значениям. 8.4. Игры двух участников с ненулевой суммой В играх двух участников с нулевой суммой интересы игроков являются диаметрально противоположными и им невыгодно информировать друг друга о своих предполагаемых дей- 349 В.4. Игры двух участников с ненулеаой суммой 348 В. ЭЛЕМЕНТЫ ТЕОРИИ ИГР ствиях.
Иная картина может наблюдаться в играх двух участников с ненулевой суммой. В частности, совершенно очевидна необходимость координированных действий игроков в игре с поспсоянной разностью (см. рис. 8.2): П1 — П~"— : С = сопвс 1 = 1, тп, т' = 1, и, р.р рр р когда они выигрывают и проигрывают одновременно. При этом (П"") — плателеная матрица й-го игрока, й = 1, 2. Рр Пример 8.11.
Два человека оказались в горящем доме. Они могут покинуть дом и спастись лишь через входную дверь, которую заклинило так сильно, что открыть ее можно только совместными усилиями. В данном случае каждый из игроков (й = 1, 2) располагает двумя стратегиями: Х~ — толкать дверь и пытаться ее открыть; 1 Х" — не толкать дверь.
Действуя вместе, игроки могут спастись — выигрыш каждого равен 1; в противном случае могут пострадать оба— выигрыш каждого равен О. Таким образом, платежная матрица имеет вид ( (1, 1) (О, 0) ( ((П,',, П,',) ) = ~ и мы имеем игру с постоянной (нулевой) разностью, в которой игрокам целесообразно координировать свои действия. -„(1 Выше было отмечено, что игры с ненулевой суммои могут быть кооперативными и ненооперативными. В некооперативных играх, которые рассматриваются в этом параграфе, игроки принимают решения независимо друг от друга либо потому что координация действий запрещена, либо потому, что р она невозможна.
Примером подобной ситуации могут служить антитрестовские законы, запрещающие некоторые виды соглашений между крупными фирмами. Один из подходов к решению некооперативных игр двух участников связан с понятием точки равновесия игры. Пусть Х,1, т =1, т, и Хз, у = 1, п, — чистые стратаегии первого и второго игроков соответственно, а П" = (П,"") Е М „(хь) — платежная матрица й-го игрока, /с = 1, 2, в которой П,"" — выигрыш й-го игрока при использовании первым игроком стратегии Х1, а вторым игроком — стратегии Хз.
Обозначим через 5~ и 5з множества смешанных стратегий первого и второго игроков, т.е. ро Р'=((р' ..р'1 ра:,'Гр,'.=1,р,'>р,;=1, ), 1=1 =(1Р— >1 ра: 1> =1 р >р р'=1, ). 1=1 Величина р„ — это вероятность выбора Й-м игроком своей чистой стратегии Х~. Под тпоипой равновесия некооперативной игры двух участников понимают пару оптимальныг смешанных стратегий в', Е Я и в*, Е Я, т.е.
вх>П вхт ((вх,) П вхт, вх Е з, (вх ) П вх ( (вх ) П вхт вхтс Е . Таким образом, как и в играх двух участников с нулевой суммой, в рассматриваемом подходе к решению некооперативных игр оптимальность решения связывают с состпо*нием равновесия игры, т.е. с ситуацией, в которой ни одному из игроков невыгодно изменять свою стратегию. Следует отметить, что в некооперативной игре может быть несколько точек равновесия и различным парам смешанных оптимальных стратегий игроков могут соответствовать различные значения ожидаемых выигрышей. 350 а эпементы теОРИИ ИГР Пример 8.12.
Двое подростков (нгрокн с номерами 1 н 2) едут на автомобилях навстречу друг другу, имея в своем распоряжении по две стратегии: Х1 — свернуть в сторону; /с Х" — не свернуть. Если один свернул в сторону, а другой г поехал прямо, то выигравший (поехавшнй прямо) получает одно очко, а проигравший (свернувшнй в сторону) теряет одно очко. Если сворачивают оба, то нх выигрыши равны нулю. Если же нн один нз ннх не свернул в сторону, то игра заканчнвается аварией н каждый игрок проигрывает 20 очков. Таким образом, платежная матрица игры имеет внд ( (О, 0) (-1, 1) ((По ~01)) = ~(1 ц ( 20, 20)(' а платежные матрицы игроков равны П 20 ' -1 — 20 Для определения точек равновесия рассматриваемой игры воспользуемся тем, что у каждого нз игроков две чистые стратегнн: 1~=1 — р", 5=1,2.
Таким образом, в соответствнн с определением оптимальной смешанной стратегии имеем — 20) (1-0;) 351 Вопросы и задачи где р11 р~~ с [О, 1], нлн что то же самое, (р,' — р1)(19 — 20р1") > О, р' Е (О 1) (р," — р,)(19 — 20р1') 3 О, р~ б (О, 1). Решив полученную систему неравенств, находим р1" = 1, рз~' — — 0 нлн р," = О, рз1' = 1. Значит, игра имеет две точки равновесия: которым соответствуют платежи ( — 1, 1) н (1, — 1). Вопросы и задачи 8.1. Какие способы описания вгр Вы знаете? В чем заключается нх принципиальное различие? 8.2. Дайте определение игры двух участников с нулевой суммой. Почему игры двух участников с нулевой суммой называют антагонистическими играми? 8.3. Почему в играх двух участников с нулевой суммой участникам целесообразно использовать макснмннные н минимаксные стратегии? Что представляет собой: а) нижняя цена игры; б) верхняя цена игры? 8.4.
Докажите, что игра двух участников с нулевой суммой обладает следующими свойствами: а) седловая точка может быть не единственной, но чистая цена игры определена однозначно; б) чистая цена игры является неубывающей непрерывной функцией элементов платежной матрицы. 8.5. Всегда лн оптимальное решение в играх двух участннков с нулевой суммой соответствует седловой точке? 353 Вопросы и задачи 352 8.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР 8.6. Докажите, что в любой игре двух участников с нулевой суммой выполняется неравенство шахш1п~ р;П;, < ш1пшаха р П; . бы1 8.7. Докажите, что в игре двух участников с нулевой суммой и без седловых точек верны следующие утверждения: а) если противник использует свою оптимальную смешанную стратегию, то никакая смешанная стратегия не может дать большего выигрыша, чем оптимальная стратегия; б) оптимальные смешанные стратегии не изменяются при монотонных линейных преобразованиях, а цена игры изменяется согласно использованному монотонному линейному преобразованию; в) если 81 и 82 — две оптимальные смешанные стратегии игрока то оптимальной является и смешанная стратегия 8 = ! = о 81 + (1 — а) 82, где 0 < ст < 1.
8.8. Докажите, что любая задача линейного программирования может быть представлена как игра двух участников с нулевой суммой. 8.9. В чем заключается принципиальное отличие игр двух участников с ненулевой суммой от игр двух участников с нулевой суммой? 8.10. Имеются два игрока: игрок А прячется, а игрок В его ищет. Игрок А по своему усмотрению может спрятаться в любом из убежищ с номерами 1 и 2 соответственно. Если игрок В найдет игрока А в том убежище, где тот спрятался, то игрок А платит игроку В штраф в одну денежную единицу.
Если игрок В будет искать игрока А не в том убежище, где тот спрятался, то игрок В платит игроку А такой же штраф. Для этой игры: а) постройте платежную матрицу игры; б) установите, имеются ли седловые точки; в) найдите оптимальное решение. / — 1 а) (ПН) = ( 1); б) седловых точек не /1 11' в)8Х =8' =(-, -,)'. .11. Найдите седловую точку и чистую цену в иг участников с нулевой суммой, в которой платежная матрица второго игрока имеет вид: 8 6 2 8 -0,5 -0,6 -0,8 а) 8 9 4 5 ; б) -0,9 -0,7 — 0,8 7 5 3 5 -0,7 -0,5 -0,6 — 2 — 2 — 1 — 1 -2 в) 0 — 1 — 1 — 1 — 1 — 1 — 1 — 1 — 1 — 2 — 1 — 2 — 1 — 1 -2 Ответ: а) Пз1 —— — 7; б) П22= 07; в) Пю=П14 — — Пзз = П84 = = П4з = П44 = 1.
8.12. Найдите оптимальное решение и цену игры в игре двух участников с нулевой суммой и платежной матрицей: )();б)(). 0,7 а) 8', = (О 1) рб(З,-) любое,л',=(О 1 0),ив 12 11 т (О 1 0) , и = 2; б) 8*,— т в) яхб = (р 1 — р), где 354 Е. ЭЛЕМЕНТЫ ТЕОРИИ ИГР 8.13., Найдите оптимальное решение и цену игры с платежной матрицей: 0,8 0,2 0,4 3 — 1 -3 а) 0,4 0,5 О,б ; б) -3 3 — 1 О, 1 0,7 0,3 — 4 -3 3 71 6 Ответ: а) вх, — — ~-— т )~ х' (77 )' 70' т 8.14. Ниже перечислен ряд принципов, лежащих в основе различных подходов к решению игр двух участников с ненулевой суммой: а) принцип максимина (максимизация своих минимальных выигрышей каждым игроком); б) принцип минимакса (каждый игрок минимизирует максимальный выигрыш своего противника); в) принцип максимальной суммы (максимизируется сумма выигрышей игроков); г) принцип максимальной разности (максимизируется разность выигрышей игроков).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
