Основные понятия теории игр

§1. Основные понятия теории игр При решении ряда практических экономических задач приходится анализировать ситуации, где несколько сторон преследуют противоположные цели, причем результат действия одной из сторон зависит от того, какой образ действий выберет противник. Такие ситуации называются конфликтными. В роли конфликтующих сторон могут выступать торговые фирмы, промышленные предприятия, отдельные потребители, пр. Считается, что математическая теория игр зародилась в 1929 г., когда была опубликована статья Дж. Фон Неймана1 «К теории стратегических игр». Теория игр обрела свой первоначальный вид как новая математическая дисциплина с выходом в свет в 1944 г. основополагающей монографии Дж. Фон Неймана и О. Моргенштерна2 «Теория игр и экономическое поведение». Игра – это упрощенная формализованная модель реальной конфликтной ситуации. Формализация означает выработку определенных правил действия сторон в процессе игры: 1) варианты действия сторон; 2) исход игры при данном варианте; 3) степень информированности каждой стороны о поведении всех других сторон. Заинтересованные играющие стороны называются игроками. Причем одного игрока может представлять как одно лицо, так и несколько человек. Ход – выбор одного из предусмотренных правилами игры действий и его осуществление. 1 Джон фон Нейман (1903-1957) – венгеро-американский математик, сделавший важный вклад в квантовую физику, квантовую логику, функциональный анализ, теорию множеств, информатику, экономику и другие отрасли науки. Наиболее известен как праотец современной архитектуры компьютеров, применением теории операторов к квантовой механике, а также как участник Манхэттенского проекта и как создатель теории игр и концепции клеточных автоматов. 2 Оскар Моргенштерн (1902-1977) — американский экономист немецкого происхождения, один из авторов теории игр. Автор ряда работ, посвященных экономическим циклам, международной торговле, методологии экономического и статистического анализа. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор игроком одного из возможных вариантов действий и его осуществление. Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либо механизмом случайного выбора (бросание монеты, выбор карты из перетасованной колоды и т.п.). Стратегия – это априори принятая игроком система решений (вида «если – то»), которых он придерживается во время ведения игры, стратегия может быть представлена в виде алгоритма и выполняться автоматически. Каждый игрок выбирает свою стратегию, в результате чего складывается набор стратегий, называемых ситуацией. Заинтересованность игроков проявляется в том, что каждому игроку в каждой ситуации приписывается число, выражающее степень удовлетворения его интересов в этой ситуации и называемое его выигрышем в ней. Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтной ситуации, т.е. определение оптимальной стратегии для каждого из них. Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш (или, что тоже, минимально возможный средний проигрыш). При выборе этой стратегии основой рассуждений является предположение, что противник (противники) является, по меньшей мере, таким же разумным, как и мы сами, и делает все для того, чтобы помешать нам добиться своей цели. Теория игр, как и всякая математическая модель, имеет свои ограничения. Одним из них является предположение о полной («идеальной») разумности противников. В реальном конфликте зачастую оптимальная стратегия состоит в том, чтобы угадать, в чем противник «глуп», и воспользоваться этой глупостью в свою пользу. Еще одним недостатком теории игр является то, что каждому из игроков должны быть известны все возможные действия (стратегии) противника, неизвестно лишь то, каким именно из них он воспользуется в данной партии. В реальном конфликте это обычно не так: перечень всех возможных стратегий противника как раз и неизвестен, а наилучшим решением в конфликтной ситуации нередко будет именно выход за пределы известных противнику стратегий, «ошарашивание» его чем-то совершенно новым, непредвиденным. Теория игр не включает элементов риска, неизбежно сопровождающего разумные решения в реальных конфликтах. Она определяет наиболее осторожное, «перестраховочное» поведение участников конфликта. Кроме того, в теории игр находятся оптимальные стратегии по одному показателю (критерию). В практических ситуациях часто приходится принимать во внимание не один, а несколько числовых критериев. Стратегия, оптимальная по одному показателю, может быть неоптимальной по другим. Сознавая эти ограничения и потому не придерживаясь слепо рекомендаций, даваемых теорий игр, можно все же выработать вполне приемлемую стратегию для многих реальных конфликтных ситуаций. В настоящее время ведутся научные исследования, направленные на расширение областей применения теории игр. §2. Классификация игр В зависимости от количества игроков различают игры: - парные (в игре два игрока); - множественные (n игроков, n≥3). Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. По количеству стратегий игры делятся: - конечные (в игре все игроки имеют конечное число возможных стратегий); - бесконечные (если хотя бы один из игроков имеет бесконечное количество возможных стратегий). По характеру взаимодействия игры делятся: - бескоалиционные (игроки не имеют права вступать в соглашения, образовывать коалиции); - коалиционные (игроки могут вступать в коалиции). Частным случаем коалиционных игр являются кооперативные игры, коалиции в которых определены заранее. По характеру выигрышей игры делятся: - антагонистические игры, или игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю). В частности, если игроков двое, то выигрыш одного игрока равен проигрышу другого; - неантагонистические, или игры с ненулевой суммой. По виду функций выигрыша игры делятся: - матричные; - биматричные; - непрерывные; - выпуклые; - сепарабельные; - типа дуэлей и др. Матричная игра – это конечная парная антагонистическая игра. Биматричная игра – это конечная парная неантагонистическая игра. Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной. Доказано, что игры этого класса имеют решения, однако не разработано практически приемлемых методов их нахождения. Если функция выигрышей является выпуклой, то такая игра называется выпуклой. Для них разработаны приемлемые методы решения, состоящие в отыскании чистой оптимальной стратегии (определённого числа) для одного игрока и вероятностей применения чистых оптимальных стратегий другого игрока. Если функция выигрышей может быть представлена в виде суммы произведений функций от одного аргумента, то такая игра называется сепарабельной (разделимой). С помощью определенных преобразований ее решение сводится к решению игры с билинейной функцией выигрышей и к определению неподвижной точки при специальном отображении множеств элементов, соответствующих стратегиям. Игры типа дуэлей характеризуются моментом выбора хода и вероятностями получения выигрышей в зависимости от времени, прошедшего от начала игры до момента выбора. По количеству шагов игры делятся: - одношаговые (заканчиваются после одного хода каждого игрока); - многошаговые (не заканчиваются после одного хода каждого игрока), делящиеся на позиционные, стохастические, дифференциальные, пр. В позиционных играх может быть несколько игроков, каждый из которых может последовательно во времени делать несколько ходов. Такие игры сводятся к матричным играм и могут решаться присущими им методами. Если в игре производятся ходы, приводящие к выбору определенных позиций, причем имеется определенная вероятность возврата на предыдущую позицию, то такая игра называется стохастической. Если в многошаговой игре допускается делать ходы непрерывно и подчинять поведение дифференциальными игроков некоторым уравнениями, то условиям, такие игры описываемым называются дифференциальными. В зависимости от состояния информации различают игры: - с полной информацией (на каждом ходе игры каждому игроку известно, какие выборы сделаны игроками раньше); - с неполной информацией (в игре не все известно о предыдущих выборах). В зависимости от степени неполноты информации игры делятся: - стратегические (проходят в условиях полной неопределенности); - статистические (проводятся в условиях частичной неопределенности). С теорией статистических игр тесно связана теория принятия экономических решений. §3. Максиминные и минимаксные стратегии. Седловая точка Рассмотрим матричную игру, в которой первый игрок А имеет m стратегий: A1, А2, ..., Аm, а второй игрок B – n стратегий: В1, В2, ..., Вn. Такая игра называется игрой размера m×n. Предположим, что каждая сторона выбрала определенную стратегию: Ai или Bj (i=1, 2, …, m; j=1, 2, …, n). Если игра состоит только из личных ходов, то выбор стратегий однозначно определяет исход игры – выигрыш одной из сторон (например, игрока А) aij. Если игра содержит кроме личных еще и случайные ходы, то выигрыш при паре стратегий Ai и Bj является случайной величиной, зависящей от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша, которое также обозначается за aij. Предположим, что нам известны значения aij (i=1, 2, …, m; j=1, 2, …, n) при каждой паре стратегий. Эти значения можно записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют стратегиям Ai, а столбцы – стратегиям Bj. Тогда в общем виде матричная игра может быть записана следующей платежной матрицей Р: Ai Вj B1 B2 … Bn A1 а11 а12 … а1n A2 а21 а22 … а2n … … … … … Am аm1 аm2 … аmn где Ai – названия стратегий игрока А; Bj – названия стратегий игрока В; aij – значения выигрышей игрока A при выборе им i-й стратегии, а игроком B – j-й стратегии (i=1, 2, …, m; j=1, 2, …, n). Поскольку данная игра является антагонистической, то значение выигрыша для игрока В является величиной, противоположной по знаку значению выигрыша игрока А. Величина aij>0 указывает на выигрыш игрока А и проигрыш игрока В, aij<0 – на проигрыш игрока А и выигрыш игрока В. Обычно (из соображений осторожности) применяется принцип гарантированного результата. Он заключается в том, чтобы выбрать стратегию, при которой минимальный выигрыш максимален (т.е. выбирать лучшее из худшего). Выбирая стратегию Ai (i=1, 2, …, m), игрок А должен рассчитывать на то, что его противник может ответить на нее той из стратегий B j (j=1, 2, …, n), для которой выигрыш aij минимален:  i  min aij . Действуя наиболее j осторожно и рассчитывая на наиболее разумного противника, игрок А должен остановиться на той стратегии Ai , для которой величина  i является максимальной: min aij .   max  i , или   max j i i Число  называется нижней ценой игры (максимином) и показывает, какой минимальный выигрыш может гарантировать себе первый игрок, применяя свои чистые стратегии при всевозможных действиях второго игрока. Второй игрок при оптимальном своем поведении должен стремиться по возможности за счет своих стратегий максимально уменьшить выигрыш первого игрока. Поэтому для второго игрока определяется  j  max aij . Затем i игрок В отыскивает такую свою стратегию, при которой игрок А получит минимальный выигрыш, т.е. определяется   min  j , или   min max aij . j j i Число  называется верхней ценой игры (минимаксом) и показывает, какой максимальный выигрыш за счет своих стратегий может себе гарантировать первый игрок. Если в игре нижняя и верхняя цены игры совпадают     , то говорят, что эта игра имеет седловую точку. Седловая точка – это пара чистых   * * стратегий i ; j (i=1, 2, …, m; j=1, 2, …, n) соответственно первого и второго игроков, при которых достигается равенство    . Если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не может поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Чистые стратегии i ; j , * * образующие седловую точку, являются оптимальными стратегиями игроков (i=1, 2, …, m; j=1, 2, …, n). Пример. Продавец руководствуется одной из трех стратегий: назначить твердую цену 100 рублей за некоторый товар; установить первоначальную цену 100 рублей и затем сбавлять (в процессе торговли с покупателем) по 10 рублей вплоть до 60 рублей; назначить твердую цену 70 рублей. Покупатель выбирает одну из трех стратегий: купить товар за 100, 80, 60 рублей соответственно. Требуется: а) составить платежную матрицу игры (элементами платежной матрицы является выручка продавца от продажи единицы товара); б) найти решение игры в чистых стратегиях. Решение. Составим платежную матрицу игры Р  аij 33 . Для этого необходимо определить выручку продавца от продажи единицы товара. Вычислим элементы первой строки платёжной матрицы: продавец устанавливает твердую цену 100 рублей. Покупатель принимает решение о приобретении товара: при использовании своей первой стратегии (элемент платежной матрицы а11 ) он соглашается с ценой продавца ( а11 =100), при использовании второй и третьей стратегий покупатель не согласен с ценой продавца, поэтому сделка не состоится ( а12 = а13 =0). Аналогично найдем все остальные элементы платёжной матрицы: а21 =100 (цена 100 рублей устраивает обоих игроков); а22 =80 (продавец сбавляет цену товара от 100 до 80 рублей); а23 =60 (продавец сбавляет цену от 100 до 60 рублей); а31 =70 (продавец устанавливает цену 70 рублей, и эта цена устраивает покупателя); а32 =70 (цена 70 рублей выгодна и продавцу, и покупателю); а33 =60 (выставленная продавцом цена 70 рублей не устраивает покупателя, сделка не состоится). В итоге платежная матрица примет вид: Цена покупателя 100 80 60 100 100 от 100 до 60 100 80 60 70 70 70 Цена продавца Определим нижнюю и верхнюю цены игры. Для этого найдем: 1) минимальное из чисел аij в i-ой строке (i,j=1,2,3) платежной матрицы:  i  min аij ; числа  i выпишем рядом с платежной матрицей в виде j добавочного столбца; 2) максимальное из чисел аij в j-ом столбце (i,j=1,2,3) платежной матрицы: β j  max аij ; числа  j выпишем под платежной матрицей в виде i добавочной строки. Цена покупателя Цена продавца 100 80 60 i 100 100 от 100 до 60 100 80 60 60 70 70 70 j 100 80 60 Находим минимальное из чисел  i :   max  i =60 (нижняя цена игры) и i минимальное из чисел  j :   min  j =60 (верхняя цена игры). j 100 80 60 i 100 100 от 100 до 60 100 80 60 60 70 70 70 j 100 80 60 α=60, β=60 Цена покупателя Цена продавца Поскольку α=β=60, игра имеет седловую точку, определяющую решение игры. Оптимальной стратегией для продавца является стратегия А2 продажи товара по цене 60 рублей, оптимальной стратегией для покупателя является стратегия В3 покупки товара по цене 60 рублей. Пример. На каждой из двух баз ассортиментный минимум составляет один и тот же набор из n видов товаров. Каждая база должна поставить в свой магазин только один из этих видов товара. Магазины (А и В) конкурируют между собой. Один и тот же вид товара в обоих магазинах продается по одной и той же цене. Однако товар, поставляемый в магазин В, более высокого качества. Если магазин А завезет с базы товар i-го вида (i=1,2,…,n), а магазин В – товар j-го вида (j=1,2,…,n), отличного от товара i-го вида (i≠j), то товар iго вида будет пользоваться спросом, и магазин А получит прибыль ci у.е. Если же в магазины А и В завезены товары одинакового вида (i=j), то товар i-го вида в магазине А не будет пользоваться спросом, так как такой же товар, но более высокого качества продается в магазине В, по такой же цене. Поэтому магазин В понесет убытки по транспортировке, хранению и, возможно, порче товара i- го вида в размере di у.е. Требуется составить платежную матрицу игры при n=3. Решение. Пусть в качестве первого игрока выступает магазин А, а в качестве второго – магазин В. У игрока А имеется n стратегий: Аi – завезти со своей базы товар i-го вида (i=1, 2,..., n). У игрока В имеется также n стратегий: Вj – завезти со своей базы j-ый товар (j=1, 2,..., n). Функция выигрышей имеет вид: d j . если i  j , f (i, j )   c , если i  j  i а платежная матрица (при n=3) примет вид: c c d 1  1 1  Pc  d c 2 2 2 . c  d 3 3  3 c §4. Смешанные стратегии Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит в чистых стратегиях, а используемые игроком А и игроком В пара стратегий называются чистыми стратегиями. Однако наличие седловой точки в игре – это далеко не правило, скорее – исключение. Большинство матричных игр не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Как найти решение игры, платежная матрица которой не имеет седловой точки? Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее , игроку В – проигрыш не больше . Учитывая, что , естественным для игрока А является желание увеличить выигрыш, а для игрока В – уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии с какими-то частотами. стратегии: чередовать чистые Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией. Смешанные стратегии игроков А и В обозначаются соответственно: А А   1А 2... m     S   р ; р ;...; р , А 1 2 m  р р ... р  1 2 m  В В   1В 2... n     S   q ; q ;...; q , В 1 2 n  q q  1q 2 ... n  где pi – вероятность применения игроком А чистой стратегии Аі (i=1, 2, …, m); m  pi  1; qj – вероятность применения игроком В чистой стратегии Bj (j=1, 2, i 1 n …, n); qj 1. j1 В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна – единице, смешанная стратегия превращается в чистую. Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными pi и qj (i=1,2,..., m; j=1,2,...,n). Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, какую чистую стратегию выберет противник в данной партии. р  а ;р ;...; р Если игрок А применяет смешанную стратегию S А 1 2 m, q  то средний выигрыш ;q ;...; q игрок В смешанную стратегию S В 1 2 n, (математическое ожидание) игрока А, как и средний проигрыш игрока В определяется соотношением m n     H A , p , q  H B , p , q  a p q   . ij ij i  1 j  1 Итак, если матричная игра не имеет седловой точки, то игрок должен использовать оптимальную смешанную стратегию, которая обеспечит максимальный выигрыш минимальный проигрыш. §5. Основные теоремы матричных игр р  ;р ;...; р Если игрок А выбирает смешанную стратегию S А 1 2 m, т о в соответствии с принципом максимина должен выбрать такую стратегию, при которой минимально возможный выигрыш был бы максимален, т.е. такую стратегию, которая обеспечивает m n max min   aij pi q j  v A . j i Аналогичные i 1 j 1 рассуждения, связанные с поиском оптимальной смешанной стратегии игрока В, приводят к рекомендации выбрать такую стратегию SB, которая обеспечивает m n min max   aij pi q j  v B . j i i 1 j 1 Теорема о максимине. В матричной игре при    имеет место равенство  A  B . Теорема о максимине указывает на существование равновесия для случая v А = v B при    и, следовательно, существования оптимальных смешанных стратегий. Приведем другую формулировку теоремы о максимине, называемую основной теоремой матричных игр. Основная теорема матричных игр (теорема Дж. Фон Неймана). Любая матричная игра имеет, по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену v . Из теорем следует, что любая матричная игра имеет цену v . Цена игры v – средний выигрыш, приходящийся на одну партию, всегда удовлетворяет условию: , т.е. лежит между нижней  и верхней  ценами игры. Оптимальное решение игры в смешанных стратегиях, так же как и решение в чистых стратегиях, обладает тем свойством, что каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет свою оптимальную смешанную стратегию, так как это ему невыгодно. Эта пара стратегий образует в игре положение равновесия: один игрок хочет обратить выигрыш в максимум, другой – в минимум, каждый «тянет» в свою сторону и, при оптимальном поведении обоих, устанавливается равновесие и устойчивый выигрыш . Чистые стратегии игроков, входящие в их оптимальные смешанные стратегии с вероятностями, не равными нулю, называются активными стратегиями. Применение следующей теоремы позволяет упрощать решение некоторых матричных игр. Теорема об активных стратегиях. Если один из участников матричной игры размера mn придерживается своей оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий (т.е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях), причем число активных стратегий каждого игрока, входящих в их оптимальные смешанные стратегии, не превосходит min(m,n). §6. Аналитический способ решения матричных игр Пусть матричная игра имеет платежную матрицу Bj B1 B2 A1 a11 a12 A2 a21 a22 Ai Предположим, что игра не имеет седловой точки, т.е. . В соответствии с основной теоремой игра имеет оптимальное решение в смешанных стратегиях: SA p1;p2 и применения (относительные частоты SB q1;q2, применения) где вероятности чистых стратегий удовлетворяют соотношениям: p1 p2 1, (1) q1 q2 1. (2) В соответствии с теоремой об активных стратегиях оптимальная смешанная стратегия обладает тем свойством, что обеспечивает игроку максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если тот не выходит за пределы своих активных стратегий. В частности, если игрок А использует свою оптимальную смешанную стратегию, а игрок В – свою чистую активную стратегию В1, то цена игры  равна a p a p , 11 1 21 2 (3) а при использовании игроком В чистой активной стратегии В2 выигрыш будет равен a p a p . 12 1 22 2 (4) Уравнения (1), (3) и (4) образуют систему трех линейных алгебраических уравнений с тремя неизвестными: a11p1 a21p2   a12p1 a22p2 . р р 1 1 2 Решая ее, находим значения р1, р2 , . Если игрок В использует свою оптимальную смешанную стратегию, а игрок А – свою чистую активную стратегию А1, то цена игры  равна: a q a q , 11 1 12 2 (5) а при использовании игроком А чистой активной стратегии А2 выигрыш будет равен: a q a q . 21 1 22 2 (6) Уравнения (2), (5) и (6) образуют систему трех линейных алгебраических уравнений с тремя неизвестными: a11q1 a12q2   a21q1 a22q2 . q q 1 1 2 Решая ее, находим q 1 , q 2 и  . Естественно, что в обоих случаях цена игры должна получиться одна и та же. Пример. Имеются две карты: туз и двойка. Игрок А наугад вынимает одну из карт; В не видит, какую карту он вынул. Если А вынул туза, он заявляет: «у меня туз», и требует от противника 1 у.е. Если А вынул двойку, то он может либо сказать «у меня туз» и потребовать у противника 1 у.е., либо признаться, что у него двойка, и уплатить противнику 1 у.е. Противник, если ему добровольно платят 1 у.е., может только принять сумму. Если же у него потребуют 1 у.е., то может либо поверить игроку А, что у него туз и отдать ему 1 у.е., либо потребовать проверки с тем, чтобы убедиться, верно ли утверждение игрока А. Если в результате проверки окажется, что у А действительно туз, В должен уплатить 2 у.е. Если же окажется, что А обманывает и у него двойка, то игрок А уплачивает игроку В 2 у.е. Проанализировать игру и найти оптимальную стратегию каждого игрока. Решение. У каждого из игроков по две стратегии: А1 – обманывать; А2 – не обманывать; В1 – верить; В2 – не верить. Для построения платежной матрицы игры вычислим средний выигрыш при каждой комбинации стратегий. 1 случай (А1,В1). Если А получил туз (вероятность этого 0,5), он требует 1 у.е., игрок В верит ему; выигрыш А равен 1. Если А получил двойку (с вероятностью тоже 0,5), он, согласно своей стратегии, обманывает и требует 1 у.е. Игрок В верит ему и уплачивает 1 у.е. Выигрыш А равен вновь 1 у.е. В итоге средний выигрыш игрока А составит: а  , 5 1  , 5 1  1 . 11 2 случай (А1,В2). Если А получил туза, у него нет личного хода, он требует 1 у.е.; В, согласно своей стратегии, не верит и в результате проверки уплачивает 2 у.е. (выигрыш А равен 2 у.е.). Если А получил двойку, он требует 1 у.е. В не верит ему, в результате чего игрок А уплачивает 2 у.е. (выигрыш А равен -2 у.е.). Средний выигрыш игрока А составит: а  , 5  2  , 5  (  2 )  . 12 3 случай (А2,В1). Если А вынул туза, он требует 1 у.е. В уплачивает эту сумму, выигрыш А составит 1 у.е. Если А вынул двойку, он платит 1 у.е.; В остается только принять сумму (выигрыш А равен -1). Средний выигрыш А составит: а  , 5  1  , 5  (  1 )  . 21 4 случай (А2,В2). Если А вынул туза, он требует 1 у.е. В проверяет и в результате проверки уплачивает 2 у.е. (выигрыш А равен 2 у.е.). Если А вынул двойку, он уплачивает 1 у.е.; В остается только принять эту сумму (выигрыш А равен -1). Средний выигрыш А составит: а  , 5  2  , 5  (  1 )  , 5 . 22 Составим платежную матрицу игры и определим нижнюю и верхнюю цены игры. B1 B2 i A1 1 A2 0,5 j 1 0,5 0;0,5 Bj Ai Поскольку игра не имеет седловой точки, ищем решение в смешанных стратегиях. Составим системы уравнений для нахождения S A   p1 ; p2  и S B  q1 ;q2 . 1   p1  3 1p1 0p2   p1    2    Для игрока А: 0p1 0,5p2  , откуда  p2  2 , и  p 2  . 3 р  р 1   2  1  1 2   1     3 Т.е. игрок А в трети своих случаев должен пользоваться своей первой стратегией (обманывать), а в двух третях – второй (не обманывать). При этом он будет выигрывать в среднем 1 3 у.е. Положительное значение  свидетельствует о том, что в данных условиях игра выгодна для А и невыгодна для В. Пользуясь своей оптимальной стратегией, А всегда может обеспечить себе положительный средний выигрыш. Заметим, что если бы А пользовался своей наиболее осторожной максиминной стратегией (в данном случае обе стратегии А1 и А2 являются таковыми), он имел бы средний выигрыш, равный нулю. 1  q  1  3 1q1 0q2  q1    2    Для игрока В: 0q1 0,5q2  , откуда q2  2 , и  q 2  . 3 q q 1   2  1  1 2  1     3 Т.е. игрок В в одной трети всех случаев должен верить А и уплачивать ему 1 у.е. без проверки, а в двух третях случаев – проверять. Тогда в среднем на каждую игру он будет проигрывать 1 у.е. Если бы он пользовался своей 3 минимаксной чистой стратегией В2 (не верить), он каждую игру проигрывал бы в среднем 1 . 2 §7. Упрощение матричных игр Решение матричных игр тем сложнее, чем больше размерность платежной матрицы. Поэтому для игр с платежными матрицами большой размерности отыскание оптимального решения можно упростить, если уменьшить их размерность путем исключения дублирующих и заведомо невыгодных (доминируемых, мажорируемых) стратегий. Процесс сведения игры к игре с матрицей меньшего размера называется редуцированием игры. Если в платежной матрице игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующие этим строкам (столбцам) стратегии называются дублирующими. Если в платежной матрице игры все элементы некоторой строки, определяющей стратегию Аi (i=1, 2, …, m) игрока А, не больше (меньше или некоторые равны) соответствующих элементов другой строки, то стратегия Аi называется доминируемой (заведомо невыгодной). Если в платежной матрице игры все элементы некоторого столбца, определяющего стратегию Вj (j=1, 2, …, n) игрока В не меньше (больше или некоторые равны) соответствующих элементов другого столбца, то стратегия Вj называется доминируемой (заведомо невыгодной). Решение матричной игры не изменится, если из платежной матрицы исключить строки и столбцы, соответствующие дублирующим и доминируемым стратегиям. Множество недоминируемых стратегий, полученных после уменьшения размерности платёжной матрицы, называется ещё множеством Парето3. Пример. Упростить матричную игру, платежная матрица которой имеет вид: Bj B1 B2 B3 B4 B5 Ai A1 A2 5 4 9 7 3 7 4 9 5 10 Вильфредо, Парето (1848-1923) – итальянский инженер, экономист и социолог. Один из основоположников теории элит. 3 A3 A4 A5 4 4 4 6 8 7 3 3 7 3 4 9 9 5 10 Из платежной матрицы видно, что стратегия А2 дублирует стратегию А5, потому любую из них можно отбросить (отбросим, например, стратегию А5). Сравнивая почленно стратегии А1 и А4, видим, что каждый элемент строки А4 не больше соответствующего элемента строки А1. Поэтому применение игроком А доминирующей над А4 стратегии А1 всегда обеспечивает выигрыш, не меньший того, который был бы получен при применении стратегии А4. Следовательно, стратегию А4 можно отбросить. Таким образом, имеем упрощенную матричную игру с платежной матрицей вида: Bj B1 B2 B3 B4 B5 A1 5 9 3 4 5 A2 4 7 7 9 10 A3 4 6 3 3 9 Ai Из последней матрицы видно, что в ней некоторые стратегии игрока В доминируют над другими: В3 над В2 (элементы столбца В3 не больше соответствующих элементов столбца В2), В4 над В5 (элементы столбца В5 больше соответствующих элементов столбца В4), В3 над В4. Отбрасывая доминируемые стратегии В2, В4 и В5, получаем игру 32, имеющую платежную матрицу вида: Bj B1 B3 5 4 4 3 7 3 Ai A1 A2 A3 В этой матрице стратегия А3 доминируется как стратегией А1, так и стратегией А2. Отбрасывая стратегию А3, окончательно получаем игру 22 с платежной матрицей Bj B1 B3 5 4 3 7 Ai A1 A2 Эту игру уже упростить нельзя, ее можно решить, например, рассмотренным выше алгебраическим методом. Необходимо отметить, что отбрасывая дублируемые и доминируемые стратегии в игре с седловой точкой, мы все равно придем к решению, содержащему седловую точку, т.е. к решению в чистых стратегиях. Но лучше сразу проверить, не обладает ли игра седловой точкой – это проще, чем сравнивать почленно все строки и все столбцы платежной матрицы. Алгебраические методы решения матричных игр иногда производить проще, если использовать также следующие свойства матричных игр (см. также аффинные преобразования матричных игр §11). Свойство 1. Если ко всем элементам платежной матрицы прибавить (вычесть) одно и то же число С (СR), то оптимальные смешанные стратегии игроков не изменятся, а цена игры увеличится (уменьшится) на это число С. Свойство 2. Если каждый элемент платежной матрицы умножить на положительное число k (kR+), то оптимальные смешанные стратегии игроков не изменятся, а цена игры умножится на k. Отметим, что эти свойства верны и для игр, имеющих седловую точку. Указанные выше свойства матричных игр удобно применять в следующих случаях: 1) если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем ее элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице; 2) если матрица игры содержит большие числа, то из всех элементов матрицы можно вычесть некоторое число, уменьшающее порядок входящих в матрицу элементов; 3) если матрица игры содержит дробные числа, то для удобства вычислений элементы этой матрицы следует умножить на такое число, чтобы все выигрыши были целыми числами. Пример. Решить матричную игру 22 с платежной матрицей вида: Bj B1 B2 0,5 0,1 -0,2 0,3 Ai A1 A2 Решение. Умножая все элементы платежной матрицы на 10, а затем прибавляя к ним число 2, получаем игру с платежной матрицей Bj B1 B2 A1 7 A2 3 5 Ai Решая эту игру алгебраическим методом, получаем: 2 7 SA   ;  , 9 9 35 5 4 SB  ; ,   . 2 9 9 В соответствии со свойствами 1 и 3, исходная матричная игра имеет те же оптимальные смешанные стратегии: 2 7 SA   ;  , 9 9 5 4 S B   ;  . А для 9 9 получения цены исходной игры необходимо из полученной цены игры вычесть 2, а затем разделить на 10. Таким образом, получаем цену исходной 17 35 2  . :10 игры:   90 9  §8. Графический способ решения матричных игр Как уже отмечалось в теореме об активных стратегиях, любая конечная игра mn имеет решение, в котором число активных стратегий каждого игрока не превосходит min( m, n) . Следовательно, у игры 2n или m2 всегда имеется решение, содержащее не более двух активных стратегий у каждого из игроков (min( 2, n)  min( m,2)  2) . Если эти активные стратегии игроков будут найдены, то игры 2n и m2 превращаются в игру 22, методы решения которой рассмотрены выше. Практически решение игры 2n осуществляется следующим образом: 1) строится графическое изображение игры для игрока А; 2) выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы (максимин), которая равна цене игры v; 3) определяется пара стратегий игрока В, пересекающихся в точке оптимума. Эти стратегии и являются активными стратегиями игрока В. Таким образом, игра 2n сведена к игре 22, которую более точно можно решить алгебраическим методом. Если в точке оптимума пересекается более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них. Решение игры m2 осуществляется аналогично. Но в этом случае строится графическое изображение игры для игрока В и выделяется не нижняя, а верхняя граница выигрыша (так как находится оптимальная смешанная стратегия игрока В), и на ней находится точка оптимума с наименьшей ординатой (минимакс). Пример. Сельскохозяйственное предприятие имеет возможность выращивать две культуры. Прибыль предприятия от реализации выращенной культуры зависит от объема полученной. Урожай первой культуры выше при сухой погоде, а второй – при более влажной. Состояние погоды в летний период можно рассматривать как следующие стратегии природы: 1. Лето жаркое сухое. 2. Лето жаркое влажное. 3. Лето теплое влажное. 4. Лето теплое сухое. 5. Лето прохладное сухое. 6. Лето прохладное влажное. Стратегии предприятия: 1. Выращивать первую культуру. 2. Выращивать вторую культуру. Предприятие считается игроком А, природа – игроком В. Расчеты прибыли предприятия в зависимости от состояния погоды сведены в следующую матрицу: определить 10 86423       (в млн руб.). Требуется 124312 6   оптимальные стратегии поведения сельскохозяйственного предприятия. Решение. Рассматривая полученную ситуацию как матричную игру порядка 26, определим оптимальные стратегии предприятия – игрока А. Для определения нижней и верхней цены игры составим вспомогательную таблицу: Bj B1 B2 B3 В4 В5 В6 10 1 10 8 2 8 6 4 6 Ai A1 A2 j 4 3 4 2 12 12 3 6 6 i 2 1 α=2, β=4 Поскольку α≠β, игра не имеет седловой точки, и решение следует искать в смешанных стратегиях. Для их нахождения воспользуемся графическим методом. Требуется найти S A   p;1  р  . Определим средние выигрыши игрока А:   w  10 p  1 1  p  9 p  1 ; 1   w  8 p  2 1  p  6 p  2 ; 2   w  6 p  4 1  p  2 p  4 ; 3   w  4 p  3 1  p  p  3 ; 4   w  2 p  12 1  p   10 p  12 ; 5   w  3 p  6 1  p   3 p  6 . 6 Построим полученные прямые в системе координат pw (рисунок 1). w w1 12 w2 w3 w4 w6 1 1 w5 р Рисунок 1 Далее строим нижнюю огибающую построенных прямых и отмечаем верхнюю точку М этой огибающей. w w1 12 w2 w3 M w4 w6 1 1 w5 р1 Рисунок 2 Точка М – точка пересечения прямых w4 и w6. Для определения координат точки М решим систему, составленную из уравнений указанных прямых: wp3 .  3p6 w Получим: p  3 3 1 3 p 1 . , w= 3 , 1 4 4 4 4 3 Тем самым, цена игры  и оптимальная стратегия игрока А равны: = 3 , 4 3 1 * SA  ; . 4 4 Использовать это решение сельскохозяйственное предприятие может следующим образом: на 75% имеющейся площади выращивать первую культуру, а на остальной выращивать вторую культуру, в этом случае прибыль предприятия составит 3,75 млн рублей. Пример. Найти решение игры, платежная матрица которой имеет вид: Bj B1 B2 4 -1 1 6 1,5 1 2 4 -3 -2 3 Ai A1 A2 A3 A4 A5 A6 Решение. Платежная матрица не имеет седловой точки. Для сведения данной игры к игре 22 строим ее графическое изображение для игрока В. Требуется найти SВ q;1q. Определим средние выигрыши игрока В:   w  q  1 1  q   q  1 ; 1   w  4 q  2 1  q  2 q  2 ; 2   w   1 q  4 1  q   5 q  4 ; 3   w  1 q  3 1  q  4 q  3 ; 4   w  6 q  2 1  q  8 q  2 ; 5   w  1 , 5 q  3 1  q   1 , 5 q  3 . 6 Построим полученные прямые в системе координат qw , изобразим верхнюю огибающую построенных прямых (рисунок 3). w 12 w5 6 w2 М w4 1 1 q w6 w1 w3 Рисунок 3 Точка М – нижняя точка построенной огибающей, является точкой оптимума. В этой точке пересекаются отрезки, соответствующие активным стратегиям В2, В3 и В6 игрока В. Таким образом, исключая стратегии В1, В4 и В5, выберем из трех активных стратегий любые две (например, В2 и В3). Найдем координаты точки М из решения системы: w2q2  . w5q4 4 2 4 2 5 Получим: M  ;2  , откуда S B*   ;  , = 2 . 7 7 7 7 7 Далее найдем решение игры для игрока А: S A   р1 ; р2 ; р3 ; р4; ; р5 ; р6  . Так как точка М является пересечением прямых w2 и w3 , то активными стратегиями игрока А будут стратегии А2 и А3. Найдем частоты их применения р2 и р3  р2  р3  1 , зная, что выигрыш игрока А равен цене игры = 2 4 , если 7 игрок А применяет оптимальную стратегию, а игрок В – любую из своих активных, например стратегию В1: 4  2 4 р 1 1  р . 2 2 7 Откуда р2  2  5 *  5  ;;; ; ;   иS . А 7 7 7   2  * 2 5 4 *  5  ;;; ; ;   Ответ: S , SB  ; , = 2 . А 7  77  7 7 Замечание. В зависимости от формы огибающей может представиться несколько случаев. 1 случай. Нижняя огибающая имеет единственную точку максимума М р;w : * * * а) если p =0, то S *А  0;1 , и оптимальной стратегией игрока А является стратегия А2, игроку В выгодно применять соответствующую прямой, проходящей через точку чистую 0;  стратегию, и имеющей наибольший отрицательный наклон (рисунок 4); w М  1 р Рисунок 4 * б) если p =1, то S *А  1;0  , и оптимальной стратегией игрока А является стратегия А1, игроку В выгодно применять соответствующую прямой, проходящей через точку наименьший положительный наклон (рисунок 5); чистую 0;  стратегию, и имеющей w М  1 р Рисунок 5 в) если p*  0;1 , то в оптимальной точке пересекаются, как минимум, две прямые, одна из которых имеет положительный, другая – отрицательный наклон (рисунок 6): w  М р* 1 р Рисунок 6 Координаты оптимальной точки М находятся с помощью решения системы уравнений прямых, пересекающихся в указанной точке. 2 случай. Нижняя огибающая имеет горизонтальный участок (рисунок 7): w  М1 М2 р1 * р2* wk 1 р Рисунок 7 Тогда оптимальной для игрока В является чистая стратегия Вk .