Матричные игры с нулевой суммой

Уважаемые студенты.

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

ЛЕКЦИИ ПО ТЕОРИИ ИГР

Теория игр в контексте теории принятия решений

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

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

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

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

Ситуации риска сопутствуют три условия:

· наличие неопределенности;

· необходимость выбора альтернативы;

· возможность оценить вероятность осуществления выбираемых альтернатив.

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

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

Существуют различные виды неопределенности, в частности:

· количественная, обусловленная значительным числом объектов или элементов в ситуации;

· информационная, вызванная недостатком информации или ее неточностью по техническим, социальным и другим причинам;

· стоимостная из-за слишком дорогой или недоступной платы за определенность;

· профессиональная как следствие недостаточного профессионализма ЛПР (не учитывается, например, требуемое количество влияющих факторов);

· ограничительная (вызванная ограничениями в ситуации принятия решений, например ограничения по времени и др.);

· внешней среды, связанная с поведением среды или реакцией конкурента на процесс принятия решения.

Природа риска в рыночной экономике обусловлена следующими факторами:

· ограниченной сферой государственного регулирования хозяйственной деятельности;

· усилением роли случайных факторов во взаимодействии предприятия с внешней средой;

· частной (и ее видами) собственностью предпринимателя, ее владением, пользованием, распоряжением;

· конкурентной борьбой товаропроизводителей и других хозяйствующих субъектов;

· всеобъемлющим характером риска, распространяющимся на сферы общественной жизни, как производственную, так и непроизводственную. Он имеет место на этапах производства, продажи, закупки и др.

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

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

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

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

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

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

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

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

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

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

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

· выбор образа действия игроков на каждом этапе игры;

· информацию, которой обладает каждый игрок при осуществлении таких выборов;

· плату для каждого игрока после завершения любого этапа игры.

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

К числу определяющих характеристик игр можно отнести следующие:

· имеется конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;

· сформулированы правила выбора допустимых стратегий, известные игрокам;

· определен набор возможных конечных состояний игры (например, выигрыш, проигрыш, ничья);

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

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

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

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

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

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

Д) По количеству ходов игры делятся на одноходовые (выигрыш распределяется после одного хода каждого игрока) и многоходовые (выигрыш распределяется после нескольких ходов).

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

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

Матричные игры с нулевой суммой

Рассмотрим парную игру с нулевой суммой. Пусть игрок I имеет стратегий (1, 2,…,m), а игрок II - стратегий 1, 2,…, n). Такая игра называется матричной игрой размерности .

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

Элементы для каждой пары стратегий считаются известными и записываются в платежную матрицу (табл. 4.1), строки которой соответствуют стратегиям игрока I, а столбцы - стратегиям игрока II. Каждый положительный элемент матрицы определяет величину выигрыша игрока I и, соответственно, проигрыша игрока II при применении ими соответствующих стратегий. Естественно, целью игрока I является максимизация своего выигрыша, тогда как игрока II - минимизация своего проигрыша.

Таблица 4.1Платежная матрица парной игры с нулевой суммой

II I			…	n
			…
			…
…	…	…	…	…
m			…

Решение парных матричных игр с нулевой суммой. Принцип минимакса

Используя платежную матрицу парной игры с нулевой суммой (табл. 4.1), определим наилучшую стратегию игрока I среди стратегий i ( i = ) и наилучшую стратегию игрока II среди стратегий j (j= ).

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

Проанализируем стратегии игрока I. Игрок I, выбирая стратегию , должен рассчитывать, что игрок II ответит на нее той из своих стратегий , для которой выигрыш игрока I будет минимальным. Найдем минимальное число в каждой строке матрицы и, обозначив его , запишем в добавочный столбец платежной матрицы (см. табл. 4.2):

. (4.1)

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

(т.е. и используя (4.1), получим

(4.2)

Таблица 4.2

II I			. . .	n
			. . .
			. . .
. . .	. . .	. . .	. . .	. . .	. . .
m			. . .
			. . .

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

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

. (4.3)

Стратегия игрока II, обеспечивающая «выигрыш» , является его минимаксной стратегией. Выбор минимаксной стратегии игроком II гарантирует ему проигрыш не больше .

В теории игр доказывается, что для нижней и верхней цены игры всегда справедливо неравенство

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

Общее значение нижней и верхней цены игры в играх с седловой точкой называется чистой ценой игры , а стратегии , позволяющие достичь этого значения, - оптимальными чистыми стратегиями; элемент = является одновременно минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии определяют в игре положение равновесия, поскольку каждому из игроков невыгодно отходить от своей оптимальной стратегии. Чистую цену игры в игре с седловой точкой игрок I не может увеличить, а игрок II ‑ уменьшить. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Игры без седловых точек

Итак, если матрица игры содержит седловую точку, то ее решение находится по принципу минимакса. Рассмотрим методику решения игры, в платежной матрице которой отсутствует седловая точка. Применение минимаксных стратегий каждым из игроков обеспечивает первому выигрыш не меньше , а второму проигрыш не больше . Учитывая, что < , естественно для игрока I желание увеличить выигрыш, а для игрока II - уменьшить проигрыш. Поиск такого решения приводит к применению сложной стратегии, состоящей в случайном применении двух и более чистых стратегий с определенными вероятностями. Такая сложная стратегия в теории игр называется смешанной. Смешанные стратегии игроков I и II будем обозначать, соответственно,

и

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

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

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

Использование линейной оптимизации при решении
матричных игр

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

Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - очевидно, при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что >0.

Будем искать решение игры в смешанных стратегиях

;

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

Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I - свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен

Учитывая, что не может быть меньше , запишем условия:

Разделив левую и правую части каждого из неравенств (4.4) на цену игры >0, получим

(4.5)

При использовании обозначений

(4.6)

неравенства (4.5) примут вид

где, очевидно, все , так как .

Из равенства

и в силу определения (4.6) следует, что переменные ( ) удовлетворяют условию

Учитывая, что игрок I стремится максимизировать , получаем линейную функцию

(4.8)

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

минимизирующие линейную функцию (4.8) и удовлетворяющие ограничениям (4.7).

Из решения задачи линейной оптимизации легко найти цену игры и оптимальную стратегию игрока I:

В свою очередь, оптимальная стратегия игрока II

может быть найдена из выражения

где - неотрицательные переменные задачи линейной оптимизации

которая является двойственной по отношению к задаче, представленной условиями (4.7) и (4.8).

В этой системе неравенств переменные

Таким образом, оптимальные стратегии

и

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

Исходная задача Двойственная задача

Цена игры и вероятности применения стратегий игроками I и II равны