Игры с седловой точкой и без неё

 

 

Вх. №____от _______  Ростовский-на-Дону филиал       Негосударственного образовательного учреждения

высшего профессионального образования

МОСКОВСКОЙ АКАДЕМИИ ПРЕДПРИНИМАТЕЛЬСТВА

при Правительстве Москвы

 

 

 

 

кафедра: математики и информационных технологий

 

 

 

 

 

 

 

Реферат

по дисциплине: Методы принятия управленческих решений

 на тему: «Игры с седловой точкой и без неё»

 

 

 

 

 

Студента 2 курса заочного отделения        Группы ЗМ-2, зачетная книжка №072

Манекина Дмитрия Павловича

Моб.тел.89054538096

Научный руководитель:

К.э.н., доц. Рудский А. А.

 

 

 

 

 

 

г. Ростов-на-Дону

2014

РЕШЕНИЕ МАТРИЧНЫХ ИГР В ЧИСТЫХ СТРАТЕГИЯХ

 

Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков. Первый игрок имеет  m  стратегий        i = 1,2,...,m, второй имеет n  стратегий  j = 1,2,...,n. Каждой паре стратегий  (i,j)  поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i= ), 2 – свою j-ю стратегию (j= ), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму |аij|). На этом игра заканчивается.

Каждая стратегия игрока  i= ;  j = часто называется чистой стратегией.

Если рассмотреть матрицу

 

A =

,

 

то проведение каждой партии матричной игры с матрицей  A сводится к выбору игроком 1  i-й строки, а игроком 2  j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша  аij.

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

аij          (i = )

т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия  i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится

аij = =                            (1).

Определение. Число , определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается аij, т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

aij = =                               (2).

Определение. Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.

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

Определение. Если в игре с матрицей А  = , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры n = = .

Седловая точка – это пара чистых стратегий  (iо,jо)  соответственно игроков 1 и 2, при которых достигается равенство  = . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:                                                            

где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент    является минимальным в   iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элемент  , называется решением игры. При этом  iо и jо  называются оптимальными чистыми стратегиями соответственно игроков 1 и 2.

Пример 1

Седловой точкой является пара  (iо = 3; jо = 1), при которой  n = = = 2.

Заметим, что хотя выигрыш в ситуации (3;3) также равен  2 = = , она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2

 

 

Из анализа матрицы выигрышей видно, что , т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию  i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию  i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию  j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

СМЕШАННОЕ РАСШИРЕНИЕ МАТРИЧНОЙ ИГРЫ

 

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

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

Таким образом, если игрок 1 имеет  m  чистых стратегий  1,2,...,m, то его смешанная стратегия  X – это набор чисел  p = (p1, ..., pm) удовлетворяющих соотношениям

pi ³ 0     (i = 1,m),    

= 1.

Аналогично для игрока 2, который имеет  n  чистых стратегий, смешанная стратегия  Y – это набор чисел

q = (q1, ..., qn),     qj ³ 0,   (j = 1,n),    

= 1.

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

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я  чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я  чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

Определение. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей

E (A, p, q) =

= =p A qT

                              Первый игрок имеет целью за  счёт изменения своих смешанных  стратегий  X  максимально увеличить свой средний выигрыш Е (А, p, q), а второй – за счёт своих смешанных стратегий Y стремится сделать Е (А, p, q) минимальным. Таким образом для решения игры необходимо найти такие  p  и  q, при которых достигается верхняя цена игры Е (А, p, q).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть Е (А, p,q).

Подобно  играм, имеющим седловые точки  в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями  игроков 1 и 2 называются такие наборы pо, qо  соответственно, которые удовлетворяют равенству

 Е (А, p, q) = Е (А, p, q) = Е (А, pо, qо).

Величина Е (А, pо ,qо) называется при этом ценой игры и обозначается через  n

Имеется и другое определение оптимальных смешанных стратегий:  pо, qо называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:

Е (А, p, qо) £ Е (А, pо, qо) £ Е (А, pо, q)

Оптимальные смешанные стратегии и цена игры называются решением матричной игры.

 

Теорема Неймана:

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

 

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

 

Теорема об активных стратегиях:

Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры n, если второй игрок не выходит за пределы своих активных стратегий.

 

ИГРЫ ПОРЯДКА 2×2

 

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

Прежде всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если седловая точка отсутствует, то в соответствии с  теоремой Неймана оптимальное решение определяется парой смешанных стратегий: Для того, чтобы их найти воспользуемся теоремой об активных стратегиях. Если 1-й игрок придерживается своей оптимальной стратегии X*, то его средний выигрыш будет равен цене игры n, какой бы активной стратегией не пользовался 2-ой игрок. Для игры размера 2´2

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

Средний выигрыш 1-го игрока, если он использует оптимальную смешанную стратегию   X*, а 2-ой игрок – свою первую чистую стратегию, равен цене игры n:

Тот же средний выигрыш получит 1-ый игрок, если 2-ой игрок применяет свою вторую чистую

Учитывая, что сумма вероятностей применения чистых стратегий равна единице, получаем систему уравнений для определения оптимальной стратегии X* и цены игры n:

 

Решая её, находим

.

 

Аналогичные рассуждения приводят нас  к  тому,  что  оптимальная  стратегия  2-го игрока  Y *  удовлетворяет системе уравнений:

Решая её, находим

 

 

.

 

 

ГРАФИЧЕСКИЙ МЕТОД  РЕШЕНИЯ ИГР  2 х n  и m х 2.

 

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

Пример 1.

Рассмотрим игру, заданную платёжной матрицей.   

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

 

         y  

 

  

 

         11

        

                                     y=11-9x

 

                                                                                                               7

            

                                                                                                            

                                                                                       N                     5

                        y=2x+3      М