Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Реферат - Матричные игры - файл 1.docx


Реферат - Матричные игры
скачать (102.5 kb.)

Доступные файлы (1):

1.docx103kb.29.11.2011 18:47скачать

содержание
Загрузка...

1.docx

Реклама MarketGid:
Загрузка...


Содержание

Введение2

  1. Матричная игра 2

  2. Равновесная ситуация5

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

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

    1. Решение 22-игры 10

    2. m × n – игры 11

    3. Решение игр 2 ×n и m×2 13

Решение игр симплекс-методом16

Заключение18

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




Введение

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

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

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

ной деятельности.

Игра (в математике) - это идеализированная математическая модель коллективного поведения: несколько игроков влияют на исход игры, причем их интересы различны

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

  1. ^

    

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


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

Предположим, что игрок А имеет m стратегий: A1, A2, …, Am, а игрок В – n стратегий: B1, B2, …, Bn.

Пусть игрок А выбрал стратегию Ai, а игрок В – стратегию Bj. Будем считать, что выбор игроками стратегий Ai и Bj однозначно определяет исход игры – выигрыш aij игрока А и выигрыш bij игрока В, причем эти выигрыши связаны равенством bij = -aij.

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

Если нам известны значения aij выигрыша при каждой паре стратегий Ai,Bj, i = 1,2,…,m, j = 1,2,…,n, то их удобно записывать или в виде матрицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В (рис. 1.1.),




B1

B2



Bn

A1

a11

a12

...

a1n

A2

a21

a22

...

a2n



...

...

...

...

Am


am1

am2

...

amn


Рис. 1.1. Общий вид платёжной матрицы матричной игры

Полученная матрица имеет размер m × n и называется матрицей игры или платежной матрицей.



Матричной игрой (при двух участниках) называется игра, в которой выигрыши первого игрока (проигрыши второго игрока) задаются матрицей. Матричные игры относятся к разряду так называемых антагонистических игр, т. е. игр, в которых интересы игроков прямо противоположны.
  1. ^

    

  2. Равновесная ситуация


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

Величина выигрыша игрока ^ A равна, по определению матричной игры, величине проигрыша игрока B. Поэтому для игрока B необходимо определить значение Vв=minjmaxiaij.

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

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

Цена игры совпадает с элементом ai0j0 матрицы игры ^ A, расположенным на пересечении i0-й строки (стратегия Ai0 игрока A) и j0-го столбца (стратегия Bj0 игрока B), - минимальным в своей строке и максимальным в своем столбце.

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



Стратегии Ai0 и Bj0, соответствующие седловой точке, называют оптимальными, а совокупность оптимальных ситуаций и цена игры – решением матричной игры с седловой точкой.

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

Матричные игры с седловой точкой важны и интересны, однако более типичным является случай, когда применение описанного алгоритма приводит к неравенству Vн < Vв.
  1. ^

    

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


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

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

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

Дополнительная стратегия х состоит в смешивании четырех стратегий, каждой с вероятностью 1/4.

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

Пусть дана игра A= a11a12…a1na21a22…a2n…………am1am2…amn,

в которой у игрока A - m, а у игрока B - n чистых стратегий.
        Смешанной стратегией игрока называется вероятностное распределение на множестве его чистых стратегий.

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

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

В этих условиях каждая обычная ситуация Ai,Bj по определению является случайным событием и ввиду независимости X и Y реализуется с вероятностью xi,yj. Поскольку в этой ситуации игрок A получает выигрыш aij, то математическое ожидание выигрыша в условиях ситуации в смешанных стратегиях X,Y равно EA,X,Y = i=1mj=1naijxiyj.

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

Стратегии X0=x01,x02,…,x0m и Y0=y01,y20,…,yn0 называются оптимальными смешанными стратегиями игроков A и B соответственно, если выполнено следующее соотношение: E(A,X,Y0)≤E(A,X0,Y0)≤E(A,X0,Q).



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

maxXminYEA,X,Y=EA,X0,Y0=minYmaxXE(A,P,Q).

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

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

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

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

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

maxXminYEA,X,Y, minYmaxXE(A,P,Q)

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

maxXminYEA,X,Y=minYmaxXE(A,P,Q).

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

EA,X0,Y0=maxXminYEA,X,Y=minYmaxXE(A,P,Q)



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

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

^ Решение 22-игры
В общем случае игра 22 определяется матрицей

.

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

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

; .

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

.



m × n – игры

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

Пусть дана m × n - игра А. Говорят, что i-я стратегия игрока A доминирует его k-ю стратегия, если aij≥akj для всех j = 1,2,…,n. Говорят, что j-я стратегия игрока B доминирует его l-и стратегию, если aij≤akl для всех i = 1,2,…,m. .
        Из определения видно, что доминирующая стратегия дает игроку выигрыш не хуже, чем доминируемая. Отсюда следует, что игрок всегда может обойтись без доминируемых стратегий, в частности, если есть одинаковые стратегии, то он может применять только одну из них. Поэтому в матрице А доминируемые стратегии (строки или столбцы) могут быть отброшены, а это приводит к матрице малых размеров. В результате выполнения доминирования получается игра, эквивалентная первоначальной, в смысле следующего утверждения.

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

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

Стрелками показаны доминируемые стратегии. Получили 2х2-игру, в которой все стратегии недоминируемы. Игра A' эквивалентна первоначальной 

игре А, т.е. оптимальные стратегии в игре А имеют вид x=(0,x2,x3), y=(y1,y2,0,0)

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

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

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

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

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


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

Для построения решений 2×n и m×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 находим как пересечение прямых.

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

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

31142

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

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



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

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

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

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

      

    2. Решение игр симплекс-методом


  Симплекс-метод является самым распространенным и наиболее универсальным методом решения задач линейного программирования (ЗЛП). Любую матричную игру можно свести к ЗЛП, точнее, задачам нахождения оптимальных стратегий первого и второго игроков в каждой матричной игре соответствует пара двойственных ЗЛП. Благодаря этому становится возможным применение симплекс-метода для решения матричной игры.
        Пусть игрок ^ A играет оптимально, а игрок B вместо y* выбирает чистую стратегию j. По определению седловой точки, каждому такому отклонению соответствует неравенство:

При j=1 a11x1*+…+am1xm*≥V

При j=2 a12x1*+…+am2xm*≥V

При j=n a1nx1*+…+amnxm*≥V

    Предположим, что V>0. Разделим обе части каждого неравенства на V и введем новую переменную εi=xi*/V. Тогда мы имеем:

a11εi+…+am1εm≥1

a12εi+…+am2εm≥1

a1nεi+…+amnεm≥1

Рассмотрим сумму

Z=ε1+…+εm=x1*V+...+xm*/V=1/^ V.

 Целью игрока A является получение максимального выигрыша. Легко видеть, что это равносильно уменьшению функции Z. Пользуясь новыми переменными εi, задачу вычисления оптимальной стратегии x* игрока A можем теперь сформулировать так:

Найти ε1,…,εm такие что Z=iεi→min, при ограничениях iaijεi≥1, i = 1,2,…,m, j = 1,2,…,n, εi≥0. Здесь ε=xi*/V, Z=1/V.



Рассуждая аналогично, задачу нахождения оптимальной стратегии игрока B можно написать следующим образом:

Найти 1,…,m такие что W=Jjmax, при ограничениях jaijj≤1, i = 1,2,…,m, j = 1,2,…,n, j0. Здесь =yj*/V, W=1/V.

 Задачи представляют собой пару двойственных задач линейного программирования. Суть применения симплекс-метода такова: решая задачу, находим ее оптимальный план и значение Z*, W*, V, x*,y*.



Заключение

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



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

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

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

http://www.math.kemsu.ru

http://www.sosh.ru


Скачать файл (102.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации