Примеры задач, сводимых к матричным играм

Все на свете начинается грошовым делом, а смотришь,

маленькая игра как раз кончилась большой.
Н. В. Гоголь «Игроки»

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

Рассмотрим несколько конкретных ситуаций.

Пример 10. «Планирование посева». Сельскохозяйственное предприятие имеет возможность выращивать две культуры - А и А . Необходимо определить, как сеять эти культуры, если при прочих равных условиях их урожаи зависят от погоды, а план посева должен обеспечить наибольший доход (прибыль от реализации определяется полученным объемом выращенной культуры). В зоне рискованного земледелия (а таковой является большая часть России) планирование посева должно осуществляться с учетом наименее благоприятного состояния погоды.

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

Налицо антагонистический конфликт, в котором у игрока Адве стратегии - А и А ,а у игрока В три — В (засушливое лето), В (нормальное лето) и В (дождливое лето).

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

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

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

75 105 65 45
70 60 55 40
80 90 35 50
95 100 50 55

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

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

Нетрудно заметить, что седловой точки у платежной матрицы нет. Кроме того, для дальнейшего анализа существенными являются лишь стратегии А и А игрока А и стратегии В и В игрока В (в этом легко убедиться, воспользовавшись правилом доминирования стратегий). В результате соответствующего усечения получим матрицу .
Элементы матрицы , связаны с элементами предыдущей матрицы соотношениями
65=5•4+45, 45=5•0+45,
50=5•1+45, 55=5•2+45.
Воспользовавшись графическим методом, в итоге получим
Р = , Q = , v = 53. Тем самым, профсоюзу следует выбирать стратегию А в 20% случаев и стратегию А в 80%. Что касается администрации, то ей следует выбирать стратегию В с вероятностью 0,4 и стратегию В с вероятностью 0,6. При этом ожидаемая цена игры равна 53.

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

Пример 12. «Локальный конфликт». Рассмотрим войну между двумя небольшими государствами А и В, которая ведется в течение 30 дней.

Для бомбардировки небольшого моста — важного военного объекта страны В - страна А использует оба имеющихся у нее самолета. Разрушенный мост восстанавливается в течение суток, а каждый самолет совершает один полет в день по одному из двух воздушных маршрутов, соединяющих эти страны. У страны В есть два зенитных орудия, при помощи которых можно сбивать самолеты страны А. Если самолет собьют, то некая третья страна в течение суток поставит стране А новый самолет.
Страна А может послать самолеты либо по одному маршрут, либо по разным. Страна Вможет поместить либо обе зенитки на одном маршруте, либо по одной зенитке на каждый маршрут.

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

У страны А есть две стратегии:
«послать самолеты по разным маршрутам» - А ,
«послать самолеты по одному маршруту» - А .
У страны В - также две стратегии:
«поместить зенитки на разных маршрутах» - В ,
«поместить зенитки на одном маршруте» - В .

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

Если страна А выберет стратегию А , а страна В — стратегию В , то хотя бы один самолет достигнет цели и вероятность разрушения моста будет равна 1.

Если страна А выберет стратегию А , а страна В стратегию В , то вновь хотя бы один самолет достигнет цели и вероятность разрушения моста будет равна 1.

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

Оформим результаты проведенного анализа в стандартной игровой форме: . При помощи графического метода получаем оптимальные смешанные стратегии игроков и цену игры Р = , , .

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

Заключение.

Давеча я кушал в ресторане и после того заглянул в

бильярдную.Хотелось посмотреть, как там, как говорится,

шарики катают.
М. М. Зощенко «Веселая игра»

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

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

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

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

Литература

1. Вентцель Е.С. Элементы теории игр. М.: Физматгиз,1961

2. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985

3. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические

методы в экономике / Под ред. А.В. Сидоровича. – М.: Издательство «Дело

и Сервис», 2004. – с. 368

4. Кузнецов Ю.Н., Кузубов В.П., Волощенко А.Б. Математическое

программирование. – М.: Высшая школа, 1980. – с. 300

5. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. – М.: Книжный

дом «Университет», 1998. – с. 304

6. Шикин Е.В. От игр к играм: Математическое введение. Изд.4-е. - М.:

Издательство ЛКИ, 2008.-112с.

7. http://www.reshmat.ru/example_The_theory_of_games_1.html

8. http://www.reshmat.ru/example_The_theory_of_games_2.html

9. http://www.math-pr.com/game_theory_1.php