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

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное образовательное  учреждение

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

«Чувашский  государственный университет имени  И.Н.Ульянова» 
 
 

Факультет дизайна и компьютерных технологий

Кафедра компьютерных технологий 
 
 
 
 

КУРСОВАЯ  РАБОТА

 Дисциплина: «Теория принятия решений» 

Тема: «Решение игр в смешанных стратегиях» 
 
 
 
 
 
 

                                                                     Выполнил: студент гр. ЗДиКТ 25-08 

                                                                                         Иванова А.В. 

                                                                    Проверил: Андреева Л.Н. 
 
 
 
 
 
 
 

Чебоксары

2011

Введение

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

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

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

1. КЛАССИФИКАЦИЯ  ИГР

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

     В зависимости от количества игроков  различают игры двух и  n  игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Чем больше игроков - тем больше проблем.

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

     По  характеру взаимодействия игры делятся  на:

1)  бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;

2)   коалиционные (кооперативные) – могут вступать в коалиции.

     В кооперативных играх коалиции наперёд  определены.

     По  характеру выигрышей игры делятся  на: игры с нулевой суммой (общий  капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.

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

     

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

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

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

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

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

     Если  функция выигрышей  является выпуклой, то такая игра называется выпуклой. Для них  разработаны приемлемые методы решения, состоящие в отыскании чистой оптимальной стратегии (определённого числа) для одного игрока и вероятностей применения чистых оптимальных стратегий другого игрока. Такая задача решается сравнительно легко.

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

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

     Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm причем сумма вероятностей равна 1: Смешанные стратегии игрока А записываются в виде матрицы

или в  виде строки SA = (p1, p2, ..., pi, ..., pm) Аналогично смешанные стратегии игрока В обозначаются:

, или,  SB = (q1, q2, ..., qi, ..., qn),

где сумма  вероятностей появления стратегий равна 1:

     Чистые  стратегии можно считать частным  случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A , S*B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству:

α ≤ v ≤ β  

где α и β — нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*A = (p*1, p*2, ..., p*i, ..., p*m) и S*B = (q*1, q*2, ..., q*i, ..., q*n) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.

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

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

     Рассмотрим  игру размера 2×2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение — это пара чистых стратегий, соответствующих этой точке.  
Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S*A = (p*1, p*2) и S*B = (q*1, q*2).

     Для того чтобы их найти, воспользуемся  теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S'A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) — случайная величина, математическое

     

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

Пусть игра задана платежной матрицей

     Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию , а игрок В — чистую стратегию B1 (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v: a11 p*1+ a21 p*2= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B2, т.е. a12 p*1+ a22 p*2= v. Учитывая, что p*1+ p*2= 1, получаем систему уравнений для определения оптимальной стратегии S'A и цены игры v:

 

Решая эту систему, получим оптимальную  стратегию

 

и цену игры

 

     Применяя  теорему об активных стратегиях при  отыскании SВ*- оптимальной стратегии  игрока В, получаем, что при любой  чистой стратегии игрока А (А1 или  А2) средний проигрыш игрока В равен  цене игры v, т.е.

(3.9)

Тогда оптимальная  стратегия определяется формулами:

(3.10)

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

Пример 1

     Решение. Игра "поиск" задана платежной матрицей без седловой точки:

     Поэтому ищем решение в смешанных стратегиях; для игрока А средний выигрыш равен цене игры v (при B1 и B2); для игрока В средний проигрыш равен цене игры v (при A1 и B2). Системы уравнений в данном случае имеют вид:

         

     Решая эти системы, получаем

     Это означает, что оптимальная стратегия  каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью 1/2, при этом средний выигрыш равен 0.

     

Пример 2.

     Игра  «поиск» 

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

     Решение. Для составления платежной матрицы следует проанализировать поведение каждого из игроков. Игрок А может спрятаться в убежище I – обозначим эту стратегию через A1 или в убежище II — стратегия A2 .

     Игрок В может искать первого игрока в убежище I — стратегия B1 , либо в убежище II — стратегия B2. Если игрок А находится в убежище I и там его обнаруживает игрок В, т.е. осуществляется пара стратегий (A1, B1), то игрок А платит штраф, т.е. a11 = - 1. Аналогично получаем a22 = - 1 (A2, B2). Очевидно, что стратегии (A1, B2) и (A2, B1) дают игроку А выигрыш 1, поэтому a12 = a21 = 1. Таким образом, для игры "поиск" размера 2×2 получаем платежную матрицу

3. Смешанная стратегия игроков

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

 
Игроки 		  
B1 		 
B2 		 
a = min(Ai)
 
A1 		 
4 		 
5 		 
4
 
A2 		 
7 		 
3 		 
3
 
b = max(Bi ) 		 
7 		 
5 		 
0

 
       Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 4, которая указывает на максимальную чистую стратегию A1.  
 Верхняя цена игры b = min(bj) = 5.  
       Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 4 ≤ y ≤ 5. Находим решение игры в смешанных стратегиях.  
        Запишем систему уравнений.  
 Для игрока I  
 4p1+7p2 = y  
 5p1+3p2 = y  
 p1+p2 = 1  
 Для игрока II  
 4q1+5q2 = y  
 7q1+3q2 = y  
 q1+q2 = 1

 

   Решая эти системы методом Гаусса, находим:  
 y = 43/5  
 p1 = 4/5 (вероятность применения 1-ой стратегии).  
 p2 = 1/5 (вероятность применения 2-ой стратегии).  

Оптимальная смешанная  стратегия игрока I: P = (4/5; 1/5)  

q1 = 2/5 (вероятность применения 1-ой стратегии).  
 q2 = 3/5 (вероятность применения 2-ой стратегии).  

Оптимальная смешанная  стратегия игрока II: Q = (2/5; 3/5)  

Цена игры  
 y = 43/5  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4. РЕШЕНИЕ МАТРИЧНЫХ ИГР 2Х2 В СМЕШАННЫХ СТРАТЕГИЯХ И МОДЕЛИРОВАНИЕ РЕЗУЛЬТАТОВ

  Матричную игру 2х2 решим в смешанных стратегиях:

  1) аналитически (для игрока А); геометрически (для игрока В)

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

  Игра  задана платежной матрицей: .

  Решение:

  1. Найдем аналитически оптимальную  стратегию игрока А и соответствующую цену игры Х*(р1, р2), n.

  Так как Х* – оптимальная, то она должна гарантировать средний выигрыш  игроку А, равный цене игры при любом  поведении игрока В:

  для стратегии В1: ;

  для стратегии В2: .

  С учетом того, что сумма компонентов  смешанной стратегии равна 1, получаем систему уравнений:

    

  Вычтем  из первого уравнения второе: или .Значит:

    

  

    

  Итак: , n = 9. 

  Найдем геометрически оптимальную смешанную стратегию игрока В: Y*(q1, q2).

  Стратегию А1 изобразим точками с ординатами 10 и 7 на прямых В1 и В2 соответственно. Стратегию А2 – точками с ординатами 8 и 11 (см. рис. 1).

  

  Рис. 1. Геометрическая интерпретация матричной  игры для игрока В 
 

  Каждой  точке на отрезке [0; 1] соответствует смешанная стратегия игрока В. Среди них оптимальной будет та, которая определяется самой низкой точкой ломанной А1МА2, т.е. точкой М. Для нахождения компонентов оптимальной стратегии игрока В надо найти координаты точки М, причем если М (х, у), то q1 = 1 – х, q2 = х, n = y. Для этого найдем уравнения прямых А1А1 и А2А2, воспользовавшись уравнением прямой, проходящей через две точки:

.

  Так как А1(0; 10) и А1(1; 7), то

, , , .

  Т.е. уравнение прямой А1А1 имеет вид: .

  Так как А2(0; 8) и А2(1; 11), то

   , , , .

  Т.е. уравнение прямой А2А2 имеет вид: .

  Найдем  координаты точки М, решив систему  уравнений прямых А1А1 и А2А2:

    

  Итак, , значит n = 9, или .

  Ответ: , , n = 9.

  

                                         Заключение

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

 
     

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

  1. Шишкин Е.В., Чхартишвили А.Г.  Математические методы и модели в управлении: Учеб. Пособие. – М.: Дело, 2000.
  2. Лапшин К.А. Методические указания для студентов экономического факультета «Игровые модели и принятие решений». – М. 2001.
  3. Мулен Г. Н. Теория игр с примерами из математической экономики. – М.: Мир, 1985.
  4. Черноморов Г.А. Теория принятия решений. Учебное пособие.- Новочеркасск: Электромеханика, 2002, 276 с.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Содержание 

Введение  ……………………………………………………………………….....3

1. Классификация игр………………………………………………………….... 4

2. Решение игр в смешанных стратегиях ……………………………………....6

3. Смешанная стратегия игроков …………………………………………..…. 11

4. Решение матричных игр 2х2 в смешанных стратегиях и моделирование результатов ………………………………………………………………………13

Заключение……………………………………………………………………… 16

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