Матричные игры, их виды и разработка моделей

Размещено на http://www.allbest.ru/

Оглавление

Введение

Матричная игра

Метод решения матричных игр

Решение 2 x 2 игры

Решение m x n игры

Решение игр 2 x n m x 2

Приближенный метод решения матричных игр

Смешанная стратегия

Заключение

Список литературы

Введение

Теория игр впервые была систематически изложена Дж. фон Нейманом и О. Моргенштерном в 1994 г., хотя отдельные исследования в этой области публиковались ещё в 1920 годах. Нейман и Моргенштерн написали книгу, которая содержала в основном экономические примеры, т.к. описать конфликт легче в числовой форме. После второй мировой войны всерьез теорией игр заинтересовались военные, т.к. увидели в ней аппарат для исследования стратегических решений. Затем внимание снова переключилось на экономические проблемы. Сейчас ведется большая работа, направленная на расширение сферы применения теории игр.

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

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

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

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

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

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

Матричная игра

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

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

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

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

Пусть игроки A и B располагают конечным числом возможных действий -- чистых стратегий. Обозначим из соответственно A₁,...,A_n и B₁,...,B_n. Игрок A может выбирать любую чистую стратегию , в ответ на которую игрок может выбрать любую свою чистую стратегию . Если игра состоит только из личных хо бор пары стратегий однозначно определяет результат -- выигрыш игрока A.

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

Таблица 1.

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

Число называют нижней чистой игры (максимином), а соответствующую ему чистую стратегию ---- максиминной. Число л показывает, какой минимальный гарантированный выигрыш может получить игрок A, правильно применяя свои чистые стратегии при любых действиях игрока B.

Число называют верхней чистой ценной игры (минимаксом), а соответствующую чистую стратегию -- минимаксной. Число в показывает, какой минимальный гарантированный проигрыш может быть у игрока B при правильном выборе им своих чистых стратегий независимо от действий игрока A.

Таким образом, правильно используя свои чистые стратегии, игрок A обеспечит себе выигрыш не меньше л, а игрок B в результате правильного применения своих чистых стратегий не позволит игроку A выиграть больше, чем в. Ясно, что .Если , то говорят, что игра имеет седловую точку в чистых стратегиях и чистую цену игры . Пару чистых стратегий и , соответствующих л и в, называют седловой точкой матричной игры, а элемент платежной матрицы, стоящий на пересечении -й строки и -гo столбца, -- седловым элементом платежной матрицы. Он одновременно является минимальным в своей строке и максимальным в своем столбце, т. е. . Стратегии и , образующие седловую точку, являются оптимальными. Тройку называют решением игры

Методы решения матричных игр

Сравнительно просто решаются игры, в которых хотя бы один игрок имеет всего две чистых стратегии: игры 22, 2n, mn. Когда m, n>2 теория игр не имеет собственного точного метода. Такие игры сводятся к задачам линейного программирования и решаются методом симплекс-таблиц. Нужно заметить, что применение симплекс метода приводит к громоздким вычислениям уже для игры 3x3. Для игр больших размеров применяются приближенные методы.

Решение 22-игры

В общем случае игра 22 определяется матрицей

.

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

Пусть U = (, 1  ) оптимальная стратегия игрока A. Тогда

; .

Аналогично, если W = (, 1 - ) - оптимальная стратегия игрока B, то

m x n - игры

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

Пусть дана m n - игра А. Говорят, что i-я стратегия игрока A доминирует его k-ю стратегия, если для всех j = 1,2,…,n. Говорят, что j-я стратегия игрока B доминирует его l-и стратегию, если для всех i = 1,2,…,m. .

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

Теорема 2. Пусть (x,y) - седловая точка m n - игры А, а () - седловая точка - игры A' (), полученной из А в результате исключения доминируемых стратегий. Тогда , для всех недоминируемых i, j: =0, для всех доминируемых i:

Пример 1. Рассмотрим игру

Стрелками показаны доминируемые стратегии. Получили 2х2-игру, в которой все стратегии недоминируемы. Игра эквивалентна первоначальной игре А, т.е. оптимальные стратегии в игре А имеют вид x=(0,),

В результате вместо игры А мы можем решить более простую 2х2-игру .

Теперь мы можем указать общий порядок решения матричной игры:

1. проверить, существует ли решение в чистых стратегиях; если есть, то игра решена;

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

3. найти решение в смешанных стратегиях.

Решение игр 2 x n , m x 2

Для построения решений 2 x n и m x 2- игр существует эффективный метод, основанный на простых геометрических соображениях. Этот метод называют графическим.

Рассмотрим игру 2n: .

Задача игрока A состоит в максимизации функции .Так как , мы имеем .

Таким образом, v является минимумом n линейных функций одной переменной ; можно вычертить графики этих функций и затем максимизировать их минимум g() графическими методами. Покажем на примере игры 23.

Поясним на примере 1.

На плоскости хОу введём систему координат и на оси Ох отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (х, 1-х). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) - стратегии А2 и т. д.

матричный игра выигрыш стратегия

На перпендикуляре А1 будем откладывать выигрыш игрока 1 при стратегии 1, на втором - при стратегии А2.

Таким образом, ординаты точек, принадлежащих ломаной оMNс определяют минимальный выигрыш игрока 1 при применении им любой смешанной стратегии. Эта минимальная величина является максимальной в точке N; следовательно, этой точке соответствует оптимальная стратегия Х* = (х, 1-х), а её ордината равна цене игры. Координаты точки N находим как пересечение прямых.

Соответствующие два уравнения имеют вид

Размещено на http://www.allbest.ru/

следовательно, х = (3/11,9/11), при цене игры v = 49/11. таким образом мы можем найти оптимальную стратегию при помощи матрицы

Оптимальные стратегии для игрока 2 можно найти из системы

Укажем основные этапы нахождения решения игры 2n (m2):

1) Строим прямые, соответствующие стратегиям второго (первого) игрока.

2) Определяем нижнюю (верхнюю) огибающую графиков, соответствующих столбцам (строкам).

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

4) Определяем цену игры и оптимальные стратегии игроков.

Приближенный метод решения матричных игр

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

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

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

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

Таблица 2

В первой партии допускаем, что игрок выбрал некоторую чистую стратегию (например, максиминную). Запишем в первую строку табл. 3 все возможные значения выигрыша, которые игрок A может получить при применении игроком любой из его чистых стратегий B_j. Игрок B ответит той стратегией, при которой его проигрыш будет наименьшим.

Эта стратегия соответствует наименьшему из элементов . Пусть им будет элемент . Тогда наилучшей для игрока B будет стратегия B_s.

Таблица 3

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

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

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

раз. Тогда за вероятности применения чистых стратегий принимаются значения частостей:

; .

Приближенное значение цены игры .

Смешанные стратегии

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

Приведем простой пример смешивания стратегий.

Арбитр футбольного матча, чтобы определить первую атакующую команду, бросает монету, т.е. вместо того, чтобы принять определенное решение, выбирает пару чисел (1/2, 1/2), где первое число - есть вероятность того, что атакующей будет первая команда, второе - вероятность для второй команды.

Четыре студентки, проживающие в одной комнате, тянут четыре спички, одна из которых короче остальных. Та "неудачница", которой достанется короткая спичка, должна вымыть пол. Поступая так, студентки добавляют к своим четырем стратегиям: "моет пол Галя", "поет пол Вера", "моет пол Наташа", "моет пол Лена" еще одну, а именно, вектор х=(1/4, 1/4, 1/4, 1/4). Дополнительная стратегия х состоит в смешивании четырех стратегий, каждой с вероятностью 1/4.

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

Пусть дана игра A= ,

в которой у игрока A - m, а у игрока B - n чистых стратегий.

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

Смешанная стратегия игрока A в игре есть вектор , где (i=1,...,m) - вероятность выбора i-й чистой стратегии. Так как - вероятность, то 0 и, поскольку одна из m чистых стратегий обязательно будет выбрана, то представляет собой вероятность полной группы событий. Значит,=1.

Аналогично, смешанная стратегия игрока B есть вероятностный вектор Y, где (j=1,...,n) выбора j-й чистой стратегии, 0 и =1.

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

Это число принимается за средний выигрыш игрока A в ситуации в смешанных стратегиях .

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

Последнее равносильно тому, что

.

Величина V=, определяемая последней формулой называется ценой игры.

Набор , состоящий из оптимальных смешанных стратегий игроков A и B и цены игры, называется решением матричной игры.

Не всякая матричная игра имеет решение в чистых стратегиях. Благодаря введению смешанных стратегий становится возможным следующее важнейшее в теории игр утверждение.

Теорема 1 (о минимаксе). Любая матричная игра имеет решение в смешанных стратегиях.

Теорема о минимаксе, или основная теорема для матричных игр, впервые была доказана Дж. фон Нейманом.

существуют и равны между собой:

.

Более того, существует хотя бы одна ситуация в смешанных стратегиях , для которой выполняется соотношение

Заключение

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

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

Список литературы

1.Шишкин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. Пособие. - М.: Дело, 2000.

2.Лапшин К.А. Методические указания для студентов экономического факультета «Игровые модели и принятие решений». - М. 2001.

3.Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике / Под ред. А.В. Сидоровича. - М.: Издательство «Дело и Сервис», 2004. - с. 368

4. Струченков, В.И. Методы оптимизации. Основы теории, задачи, обучающие компьютерные программы: учеб. пособие / В.И. Струченков. - М.: Экзамен, 2005. - 256с.

5. Костевич, Л.С. Математическое программирование: информ. технологии оптимальных решений: учеб. пособие / Л.С. Костевич. - Мн.: Новое знание, 2003. - 424 с.

Размещено на Allbest.ru