матричные игры

1

Введение

За окном XXI-ый век. Вода превращается в вино только в выступлениях фокусников; желание šда будет светŸ осуществляется вполне обыденно; человек, отрицающий шарообразность Земли через 500 лет после Колумба или печатающий сообщение в научном журнале о березовой ветке, выросшей на сосне, ассоциируется с клиентом психбольницы или проходимцем.

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

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

Однако, о природе многих явлений природы и человеческого мышления наши представления ничтожны. Какой-либо детерминизм представлений – база для принимаемых решений исчезает и подменяется неопределенностью. šАннушка уже разлила подсолнечное масло… и Берлиоза выкинуло на рельсыŸ (кто мог предугадать эту при- чинно-следственную связь, кроме Воланда). Гроссмейстер проигрывает партию из-за šзевкаŸ, о причине которого приходится только гадать. В каждой сотне операторов šотлаженнойŸ программы присутствует хотя бы одна ошибка. Запланированный отпуск на Мальдивских островах безнадежно испорчен из-за невесть откуда взявшегося цунами. Разражается финансовый кризис из-за того, что какие-то банки были непредусмотрительны в своей кредитной политике.

2

Если некоторые явления в природе еще можно познать хотя бы на уровне вероятностных оценок, то психология человека остается загадочной. Как часто рушатся надежды на массовый человеческий разум в общественной деятельности. Всякий экономист-академик (и не только) имеет свое, šединственно верноеŸ мнение о действиях по выходу из кризиса или об использовании профицита баланса. Мудрые философы никогда не придут к определенному выводу о первичности курицы или яйца. О каких разумных управленческих решениях в таких условиях можно говорить?!

šИскусство выработки наилучших (в смысле тех или иных критериев) суждений старо, как род человеческий; именно это искусство является сущностью любой сферы человеческой деятельности …Ÿ [2] При выработке суждений относительно последующих действий, приходится учитывать подчас случайный характер человеческих поступков, а также элемент случайности, присущий окружающей среде. Поэтому всякое научное предвидение тесно связано с использованием

аппарата теории вероятностей и математической статистики. Примечательно, что принимаемые рекомендации здесь не носят

категорического характера, а звучат как šвсё будет хорошо с вероятностью 0.95Ÿ, šвелика вероятность того, что ваши ожидаемые издержки не превысят …Ÿ, šвы достигнете максимума ожидаемого успеха, если два дня в неделю на вас будет коричневый костюмŸ (ответ на вопрос šв какие дни?Ÿ остается за кадром).

Наука о выработке таких суждений – математическая теория принятия решений - строилась оформилась как самостоятельная математическая дисциплина šТеория игр и статистических решенийŸ в 20-40-ые годы XX столетия в работах Джона фон-Неймана [1]. Большой вклад в ее развитие внесли А. Вальд (создатель теории последовательного анализа), Р. Беллман и Л.Понтрягин, блистательная группа американских математиков 50-ых годов, многие из которых удостоены Нобелевских премий по экономике.

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

3

Работа 1. Матричные игры

1.1. Постановка задачи и описание метода решения

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

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

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

Столь же важно различать понятия выбор и ход: игра состоит из последовательности ходов, тогда как партия – из последовательности выборов (в повседневности мы часто путаем эти понятия - когда Остап Бендер šсделал ход e2:e4Ÿ, фактически он сделал соответствующий выбор из 20 допустимых. Самыми примитивными являются одноходовые игры, где всякая партия состоит из одного хода (дети показывают друг другу пальцы: если общее число показанных пальцев четное, выигрывает первый, в противном случае – второй).

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

4

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

Простейшими среди игр являются одноходовые матричные иг-

ры с нулевой суммой.

В такой игре участвуют два игрока, первый из которых имеет m

выборов и второй – n своих выборов. Если игрок 1 делает выбор i, а игрок 2 – выбор j , то выигрыш игрока 1 (проигрыш игрока 2) равен

Rij. Матрицу R = [ Rij / i=1..m , j=1..n ] принято называть матрицей выигрышей, или платежной матрицей.

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

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

С этих позиций игроку 1 гарантирован выигрыш, не меньший

Если в матрице выигрышей существует элемент V1 = V2=Rk l , то говорят о наличии оптимальной политики в пространстве чистых стратегий и для игроков оптимальны соответственно выборы k и l.

Пару (k, l) называют седловой точкой.

Пример 1. Пусть игра определяется матрицей

7

Решение этих задач симплексным методом дает оптимальные значения X = {11/37, 4/37, 5/37}, Y = {8/37, 7/37, 5/37} и экстремумы целевых функций, равные 20/37.

Отсюда (с учетом замены переменных) V = 37/20 ,

P = {11/20, 4/20, 5/20} ,

Q = {8/20, 7/20, 5/20}.

Соответственно, первому игроку рекомендуется использовать свои выборы с вероятностями 0.55, 0.20, 0.25 (в 55 случаях из 100 использовать первый, в 20 – второй и в 25 – третий).

А как поступить в реальности с этими вероятностями?

Если бы вероятности былы равны 0.25, 0.5 и 0.25, то достаточно бросить монету: выпадет решка – делай выбор 2, в противном случае брось монету еще раз, при выпадении решки делай выбор 1 и при орле – выбор 3 (или наоборот), Здесь же можно включить компьютер, войти в любую знакомую программную среду и обратись к датчику случайных чисел равномерного распределения в (0,1). Если полученное число меньше 0.55 – делай выбор 1, при числе из интервала от 0.55 до 0.75 – выбор 2 и числе большем 0.75 – выбор 3.

1.2.Вопросы для самоконтроля

1.Что такое цена игры, и какая информация содержится в ее значении для каждого из игроков?

2.Что такое доминирование в играх и о чем свидетельствует обнаружение такового ? Присутствует ли доминирование в играх с матрицами

3.В каком случае игроки могут не тратить время на игру ввиду предопределенности ее исхода?

4.Вы решаете игру симплексным методом на основе постановки задачи в форме (2) и обнаруживаете признаки неограниченности целевой функции. Что можно сказать по поводу этого факта ?

8

5. Выясните оптимальную политику игроков в случае диаго-

нальной матрицы игры (все ai > 0)

6. Каждый игрок выбирает одно из целых чисел от 1 до 9. Если

число, выбранное одним из игроков, на единицу больше числа другого игрока, первый игрок проигрывает 2 руб. При большей разнице он выигрывает 1 рубль и при равенстве выборов результат ничейный. Постройте матрицу такой игры.

7. Покажите, что матрица игры aij=i-j / i, j=1 n имеет седловую точку. Опишите оптимальные стратегии игроков.

8. Цена игры с матрицей А равна V. Увеличив элементы матрицы А на константу С, получаем матрицу В. Покажите, что цена игры с матрицей В равна V +С и что оптимальные стратегии в обеих играх

совпадают.

9. Какова оптимальная политика игроков в случае кососиммет-

рической матрицы

1.3. Контрольные задания

1.3.1.Требования

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

2.Поставьте пару двойственных задач и выполните ее решение симплексным или каким-либо другим методом. Оцените полученное оптимальное решение с позиций здравого смысла.

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

9

дач (1) и (2). Зачем при переходе от постановки задачи (1) к (2) требу-

ется уверенность в положительности цены игры ?

1.3.2. Варианты заданий