83405

Теория игр. Расчётно-графическая работа

Контрольная

Информатика, кибернетика и программирование

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

Русский

2015-03-14

999.59 KB

15 чел.

Федеральное государственное образовательное учреждение высшего профессионального образования

НИУ ВПО

«Московский государственный строительный университет»

ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ИНФОРМАЦИОННЫХ СИСТЕМ В СТРОИТЕЛЬСТВЕ

(ИЭУИС)

Факультет экономики и управления в строительстве

Кафедра ЭУИС

Теория игр

Расчётно-графическая работа

Выполнила студент

2 курса 10 группы

Тищенко Е.И.

Преподаватель

Клашанов Ф.К.

Дата проверки:

Москва 2014

Содержание:

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

  1.  Терминология………………………………………………………………4
  2.  Классификация игр – дерево игр...............................................................8
  3.  Классификация игр – описание……………………………………….....10
  4.  Матричные игры…………………………………………………………..12

       4.1 Матричная игра с седловой точкой…………………………………...12

       4.2 Матричная игра со смешанными стратегиями………………………14

  1.  Аффинные преобразования………………………………………………15
  2.  Доминирующие строки и столбцы………………………………………16
  3.  Зеркальное преобразование………………………………………………17
  4.  Геометрическое и аналитическое решение матрицы 2х2………...……19
  5.  Решение матрицы 3х3 методом Крамера………………………………..20
  6.  Решение матрицы 3х3 методом Лагранжа………………………………22
  7.  Решение матрицы 3х3 методом обратной матрицы……………………24
  8.   Решение матрицы 2х6 графическим способом………………………...26
  9.   Решение матрицы 3х3 методом Брауна………………………………...28

Приложения……………………………………………………………….30

          Работа в Excel…………………………………………………………….34

Литература

Введение

  В данном отчете расчетно-графической работы по предмету «Теория игр» приведены примеры решения матричных игр, как в смешанных стратегиях, так и в чистых. Так же, в данной работе будет рассмотрена терминология дисциплины Теории игр по конкретным темам курса.

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

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

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

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

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

  В завершении работы будет сделан общий вывод о рассмотренных играх и об их экономическом смысле в целом.

  1.  Терминология

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

Антагонистическая игра –  (игра с нулевой суммой). Антагонистической игрой называется некооперативная игра, в которой участвуют два игрока, выигрыши которых противоположны. Формально антагонистическая игра может быть представлена тройкой <XYF>, где X и Y — множества стратегий первого и второго игроков, соответственно; F — функция выигрыша первого игрока, ставящая в соответствие каждой паре стратегий (ситуации) (x,y),  действительное число, соответствующее полезности первого игрока при реализации данной ситуации. Так как интересы игроков противоположны, функция F одновременно представляет и проигрыш второго игрока.

Аффинное преобразование - преобразование подобия и сдвига, т.е. преобразование всех элементов матрицы A вида: aij= k*aij+m, где k ≠ 0 и m – константа, которая не изменяет решение матрицы. Кроме того, цена преобразованной игры  может быть получена из цены первоначальной игры V по тому же правилу:

V’=k*V+m

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

Выигрыш – исход конфликта. Единственная цель каждого игрока – максимизация его выигрыша.

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

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

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

Зеркальное изоморфное преобразование – это означает перемену ролей игроков, т.е. если в антагонистической игре с игроками A и B матрица игры была A , выигрышей игрока A, то в результате изоморфизма матрица становится B выигрыша игрока B. Зеркальный тип представляет собой отображение строк матрицы A и столбцов.

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

Игра– математическая модель ситуаций, характеризующаяся признаками:

  1.  Наличие нескольких участников;
  2.  Неопределенность поведения участников, связанная с наличием у каждой из сторон нескольких вариантов действий;
  3.  Несовпадение интересов участников – конфликт;
  4.  Взаимосвязанность поведения участников;
  5.  Наличие правил поведения известных всем участникам.

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

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

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

Изоморфные преобразования игры – перенумерация чистых стратегий игрока A и/или игрока B.

Матрица А’ называется образом матрица А, а матрица А прообразом матрицы А’ или изоморфным преобразованием.

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

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

Maxmin(aij) – нижняя цена игры чистых стратегий – наибольший из показателей эффективности стратегий aij.

Стратегия, показатель эффективности которой совпадает с максимином, называется максиминной стратегией.

Minmax(aij) – верхняя цена игры в чистых стратегиях – наименьший из показателей неэффективности стратегий bj.

Стратегия, показатель неэффективности которой совпадает с минимаксом, называется минимаксной стратегией.

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

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

Основная теорема матричных игр.

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

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

Показатель эффективности стратегий ai– это минимальный выигрыш игрока А при этой стратегии, т.е. минимальный элемент i-строки. α=min(aij).

Показатель неэффективности стратегий bj – максимальный проигрыш игрока B при этой стратегии, т.е. максимальный элемент j-столбца. β=max(aij)

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

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

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

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

Ситуация – набор стратегий.

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

Стратегии i* и j*  образуют седловую точку и называются оптимальными, а значение υ = aij называют ценой игры. Тройка υ, i*,j* - решение матричной игры с седловой точкой.

Элемент ai*ji*, являющийся седловой точкой матрицы, является минимальным в i* cтроке и максимальным в j* столбце.

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

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

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

Необходимым условием равновесия является наличие седловой точки.

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

Теория игр -  математическая теория конфликтных ситуаций.

Точка Нэша –точка, равная множеству { } такая, что для всех

i=  достигается оптимум функции ni(mн) =

                                                                             i

Ход – регулярные действия, выполняемые игроком.

Ходы бывают:

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

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

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

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

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

Элементы матрицы – результаты первого игрока (выигрыш игрока A).

  1.  Классификация игр - Дерево игр

Игры

Статические

Динамические

По кол-ву ходов

По кол-ву игроков

По характеру выигрыша

Азартные

Стратег.

Множеств.

Парные

C нулевой суммой

С ненулевой суммой

По характеру взаимод.

По кол-ву стратегий

Бескоалиц.

Бесконеч.

Антагонистические

Кооперат.

Конечные

Коалиц.

Позицион.

По кол-ву информации

По виду описания

Нормальная форма

Дифференц.

Полная

Неполная

Кооперат.

Симметрич.

Рефлекс.

Некооперат.

Несимметрич.

Матричные игры

Изученные в ходе решения игры задач                    Вид игр

Признак сравнения

  1.  Классификация игр - описание

Классификация игр осуществляется по целому ряду признаков:

  1.  По количеству игроков:
  2.  парные игры и игры nигроков. Трудность решений задач при увеличении игроков возрастает.

2. по количеству стратегий:

  1.  конечные
  2.  бесконечные

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

3. по характеру взаимоотношений:

  1.  бескоалиционные
  2.  коалиционные
  3.  кооперативные

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

4. по характеру выигрышей:

  1.  игры с нулевой суммой (антагонистические)
  2.  игры с ненулевой суммой (неантагонистические)

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

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

5.по количеству ходов:

  1.  одношаговые
  2.  многошаговые

В одношаговых играх каждый игрок делает только один ход, а далее идет распределение выигрышей.

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

  1.  В зависимости от состояния информации:
  2.  игры с полной информацией
  3.  игры с неполной информацией

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

  1.  По виду функций выигрыша:
  2.  матричная
  3.  биматричная
  4.  непрерывная

Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой выигрыши первого игрока равны проигрышам второго; задается в виде матрицы.

Биматричная игра – это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока сосредоточены в матрице игры данного игрока; данный вид игры задается двумя матрицами.

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

  1.  Матричные игры

4.1 Матричные игры с седловой точкой

Дана матрица 4х6. Это значит, что у игрока А – 4 стратегии, а у игрока В – 6.

В1

В2

В3

В4

В5

В6

А1

110

150

115

130

140

145

А2

120

135

105

255

810

805

А3

250

500

130

100

235

190

А4

540

700

505

420

815

705

Для нахождения нижней и верхней цен игры чистых стратегий удобно дополнить матрицу игры А столбцом показателей эффективности αi стратегией Ai, и строкой показателей неэффективности βj и стратегией Bj. В результате получим матрицу:

В1

В2

В3

В4

В5

В6

αi

min

А1

110

150

115

130

140

145

110

А2

120

135

105

255

810

805

105

А3

250

500

130

100

235

190

100

А4

540

700

505

420

815

705

420

βj

max

540

700

505

420

815

805

   420

420

α=420 – это минимальный выигрыш первого игрока.

β=420 – это максимальный проигрыш второго игрока.

Определим верхнюю и нижнюю цену игры

Находим нижнюю цену игры:

α = max αi = maxmin аij = 420

             1≤ i ≤4           1≤ i ≤4   1≤  j ≤6
i*( оптимальная стратегия) = 4

Находим верхнюю цену игры:

β = min βj = minmax aij = 420

          1≤  j ≤6            1≤  j ≤6  1≤ i ≤4           

j* (оптимальная стратегия) =4

maxmin aij = minmax aij

      i        j                      j          i

α = 420 = β = 420  из данного равенства следует, что существует седловая точка, образованная оптимальными стратегиями  i*  j*

Cедловая точка - 420

Находим цену игры:

Цена игры имеет формулу ( αi *j* )

Тройка (i* j* ) считается решением игры, следовательно для данной матрицы решением матричной игры является (4;4;420) 

(П4.1)

4.2 Матричная игра со смешанными стратегиями

Составим и рассмотрим матрицу 4х6.

 

 В1

В2 

 В3

В4

В5

В6 

αi  (min)

 А1

180

130

610

740

530

700

130

 А2

320

640

820

920

620

850

320

 А3

310

170

780

850

610

790

170

 А4

980

520

550

810

540

830

520

βj (max)

980

640

820

920

610

850

520

 

 

 

 

 

 

 

610

Находим нижнюю цену игры:

α = max αi = maxmin аij = 520

             1≤ i ≤ 4          1≤ i ≤ 4  1≤  j ≤ 6

В данной матрице, минимальный гарантированный выигрыш 1 игрока по строкам равен: 130; 320; 170; 520, следовательно maxmin = 520, что является 4 стратегией 1 игрока.      

i*( оптимальная стратегия) = 4

Находим верхнюю цену игры:

β = min βj = minmax aij = 610

          1≤  j ≤  6           1≤  j ≤ 6   1≤ i ≤ 4           

Для 2 игрока максимальный проигрыш по столбцам матрицы составит: 980; 540; 820; 920; 610; 850, где minmax = 610, что является 5 стратегией 2 игрока.   

j* (оптимальная стратегия) =5

maxmin aij  minmax aij

      i        j                      j          i

Данная матричная игра не имеет седловой точки.

Цена игры находится в пределах 520

  1.  Аффинные преобразования

Рассмотрим матрицу 4х6 со смешанными стратегиями

 

 В1

В2 

 В3

В4

В5

В6 

αi  (min)

 А1

180

130

610

740

530

700

130

 А2

320

540

820

920

620

850

320

 А3

310

170

780

850

610

790

170

 А4

980

520

550

810

540

830

520

βj (max)

980

540

820

920

610

850

520

 

 

 

 

 

 

 

610

Проведем аффинные преобразования

  1.  m= -200, k = 1, уменьшает значения матрицы на 200.

 

 

 В1

В2 

 В3

В4 

 В5

В6 

 А1

-20

-70

410

540

230

500

 А2

120

340

620

720

420

650

 А3

110

-30

580

650

410

590

 А4

780

320

350

610

340

630

2. m = -200, а k= 0,1

 

 В1

В2

 В3

В4 

В5 

В6 

 А1

-2

-7

41

54

23

50

 А2

12

34

62

72

42

65

 А3

11

-3

58

65

41

59

 А4

78

32

35

61

34

63

(П5)

  1.  Определение доминирующих строк и столбцов

Рассмотрим матрицу 4х6

Сопоставляем стратегии A-игрока.

Стратегия A3 доминирует над стратегией A1 (все элементы строки 3 больше или равны значениям 1-ой строки), следовательно, исключаем 1-ую строку матрицы. Получилась матрица 3x6

 

 

 В1

В2 

В3 

В4 

В5 

В6 

 А1

-2

-7

41

54

23

50

 А2

12

34

62

72

42

65

 А3

11

-3

58

65

41

59

 А4

78

32

35

61

34

63

Стратегия A1 доминирует над стратегией A2 (все элементы строки 1 больше или равны значениям 2-ой строки), следовательно, исключаем 2-ую строку матрицы. Получилась матрица 2x6

 

 В1

В2 

В3 

В4 

В5 

В6 

 А1

12

34

62

72

42

65

 А2

11

-3

58

65

41

59

 А3

78

32

35

61

34

63

Преобразованная матрица имеет вид:

 

 В1

В2 

В3 

В4 

В5 

В6 

 А1

12

34

62

72

42

65

 А3

78

32

35

61

34

63

Сопоставляем стратегии B-игрока.

С позиции проигрышей игрока В стратегия B4 доминирует над стратегией B3 (все элементы столбца 4 больше элементов столбца 3),

следовательно, исключаем 4-й столбец матрицы.

 

 В1

В2 

В3 

В4 

В5 

В6 

 А1

12

34

62

72

42

65

 А3

78

32

35

61

34

63

С позиции проигрышей игрока В стратегия B5 доминирует над стратегией B2 (все элементы столбца 5 больше элементов столбца 2),

следовательно, исключаем 4-й столбец матрицы.

 

 В1

В2 

В3 

В5 

В6 

 А1

12

34

62

42

65

 А3

78

32

35

34

63

С позиции проигрышей игрока В стратегия B6 доминирует над стратегией B3 (все элементы столбца 4 больше элементов столбца 3),

следовательно, исключаем 4-й столбец матрицы.

 

 В1

В2 

В3 

В6 

 А1

12

34

62

65

 А3

78

32

35

63

С позиции проигрышей игрока В стратегия B3 доминирует над стратегией B2 (все элементы столбца 3 больше элементов столбца 2), следовательно, исключаем 3-й столбец матрицы.

 

 В1

В2 

В3 

 А1

12

34

62

 А3

78

32

35

Преобразованная матрица примет вид 2х2:

 

 В1

В2 

 А1

12

34

 А3

78

32

(П6)

  1.  Зеркальное преобразование

 

 В1

В2 

 А1

-12

-78

 А3

-34

-32

(П7)

  1.    Геометрическое и аналитическое решение матрицы 2х2.(с равновесием по Нэшу.)

Рассмотрим матрицу 2х2:

 

 В1

В2 

 А1

10

9

 А3

3

7

Решение матричной игры 2х2:

= 10xy+ 3(1-x)y + 9(1-y)x + 7(1-x)(1-y) = 5xy - 4y + 2x+7

Определим точку Нэша:

 5y+2=0

 5x - 4=0

= 0.4 ; 1-y = 0.6

= 0,8 ; 1-x = 0,2

Таким образом получаем оптимальные стратегии в данной игре:

= (0,8; 0,2) – вероятность выбора стратегии первым игроком

= (0,4;0,6) – вероятность выбора стратегии вторым игроком

v=. Подставляем значения х и у в уравнение функции выигрыша и получим: 3*0,8*0,4 - 4*0,4+2*0,8+7=7,96

Решение игры в смешанных стратегиях: <{0,8;0,2}; {0,4;0,6};7,96 >

Графическое решение

Рассмотрим матрицу 2х2

 

 В1

В2 

 А1

10

9

 А3

3

7

В1=10

M

В1=9

L

K

В2=7

 

V = 7,96

В1=3

A2

A1

0

1

x1 = 0.8

x2 = 0.2

Решение игры в смешанных стратегиях: <{0,8;0,2}; {0,4;0,6};7,96 >

(П8)

  1.  Решение игры 3×3 методом Крамера

Дана матрица 3х3:

А =

Определим цену игры и оптимальную стратегию игрока А.

Для начала рассчитаем определители:

= = -21;

= -5;

= -8;

= -2.

С помощью определителей рассчитываем вероятность применения стратегии игрока А:

V= ;

x1=  =  ;

x2= =  ;

x3= =  .

Определим цену игры и оптимальную стратегию игрока А.

Для начала рассчитаем определители:

= = -5;

= = -3;

= = 1.

С помощью определителей рассчитываем вероятность применения стратегии игрока В:

у1=  =  ;

у2= =  ;

у3= =  .

Ответ: х, у. V=

(П9)

  1.  Решение матрицы 3х3 методом Лагранжа

Дана матрица 3х3:

А =

Найдем математическое ожидание выигрыша игрока А:

V = (x1 x2 x3) = y1 (x1+2x2+2x3)+y2(3x1+2x2+x3)+y3(5x1+x2+4x3)

Составим вспомогательные функции  ha*, у*) и hb*, у*):

ha*, у*)  =  v + λa (x1 + x2 + x3 -1);

hb*, у*)  =  -v + λb (y1 + y2 + y3 -1) .

Запишем системы уравнений для определения точки Нэша:

                                       

Решаем первую систему методом алгебраического сложения.

Вычитаем из 2-го уравнения 1-е и из 2-го вычитаем 3- е, получаем:

Решив мы получаем вероятности применения стратегий игрока В:

Аналогично определяется оптимальная стратегия игрока А из второй системы. Вычитаем из 1-го уравнения 2-е, а из 2-го вычитаем 3-е, получаем:

Решив мы получаем вероятности применения стратегий игрока A:

Подставив данные стратегии в выражение для цены игры, получим ее значение:

V= хАу* = ( =
,, v=.

  1.  Решение матрицы 3х3 методом обратной матрицы

Дана матрица 3х3:

А =

Определим матрицу А-1. Для этого рассчитываем определитель матрицы А:

det(A) =1*  = 1*7-3*6+5*(-2) = - 21

и матрицу алгебраических дополнений:

adj (AT) =  =

Тогда

А-1 =  = -   =  

Определим вектор:

=  =

Получили распределение вероятности применения стратегий стороны А, составляющую её оптимальную смешанную стратегию:

Рассчитаем значение цены игры v:

v =

Определим оптимальную смешанную стратегию стороны В, вектора :

=  =

Получили распределение вероятности применения стратегий стороны B, составляющую её оптимальную смешанную стратегию:

Ответ: ,

, v = .

  1.  Решение матричной игры 2×6 графическим способом

Рассмотрим матричную игру 2×6, решим ее аналитическим способом.

А =           2×6

Составим упрощенную матрицу данной игры

Рассмотрим матрицу 2х2:

 

 В1

В2 

 А1

8

3

 А3

6

4

Решение матричной игры 2х2:

= 8xy+ 6(1-x)y + 3(1-y)x + 4(1-x)(1-y) = 3xy +2y - x+4

Определим точку Нэша:

 3y-1=0

 3x +2=0

= 0.3 ; 1-y = 0.7

= 0,7 ; 1-x = 0,3

Таким образом получаем оптимальные стратегии в данной игре:

= (0,7; 0,3) – вероятность выбора стратегии первым игроком

= (0,3;0,7) – вероятность выбора стратегии вторым игроком

v=. Подставляем значения х и у в уравнение функции выигрыша и получим: 3*0,7*0,3 + 2*0,3-0,7+4=4,53

Решение игры в смешанных стратегиях: <{0,7;0,3}; {0,3;0,7};4,53 >

а25=10

а24 = 9

a11=8

а26=7

а21 = 6

a12=6

M

a16= 5

a23 = 4

a14=4

a13= 3

V

1

0

х1

х2

a15 = -2

a22= -5

Р = {x1; 1 - x1}

Q = {y1; y2; у3; у4; у5; у6}; = 1

Цена игры V = 4,53

х1 = 0,7

х2= 0,3

Р = {0.7;0.3}

M (0.7;4.53)

Q = {0;0;0;у4;0;у6}

у4=0,7

у6=0,3

Q = {0;0;0;0.7;0;0.3}

Ответ: <{0.7;0.3};{0;0;0;0.7;0;0.3};4,53>

(П12)

  1.  Решение матричной игры 3×3 методом Брауна

Пусть дана матрица 3×3:

С =         

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

Получим преобразованную матрицу А:

А =  

Теперь можем применить метод Брауна.

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

                      Таблица 1

Таблица накопления выигрышей

1

2

3

4

5

6

7

8

9

10

11

12

K

Ai

B1

B2

B3

Bj

A1

A2

A3

V

V*

1

A3

17

8

13

B2

6

21

8

8

21

14,5

2

A2

17+2=19

8+21=29

13+0=13

B3

6+19=25

21+0=21

8+13=21

6,5

12,5

12,7

3

A1

34

34

32

B3

44

21

34

10,6

14,7

20

4

A1

49

40

51

B2

50

42

42

10

12,5

11,2

5

A1

64

46

70

B2

56

63

50

9,2

12,6

17,2

6

A2

66

67

70

B1

71

65

67

11

11,8

11,4

7

A1

81

73

89

B2

77

86

75

10,4

12,3

16,5

8

A2

83

94

89

B1

92

88

92

10,4

11,5

16,2

9

A3

100

102

102

B1

107

90

109

11,1

12,1

17,2

10

A3

117

110

115

B3

126

90

122

11,5

12,6

17,8

11

A1

132

116

134

B2

132

111

130

10,5

12,0

16,5

12

A1

147

122

153

B2

138

132

138

10,2

11,5

15,9

NA1 = 6;         Р(А1) =  = 0,5

NA2 = 3;         Р(А2) =  = 0,25

NA3 = 3;         Р(А3) =  = 0,25

NВ1 = 3;         Р(В1) =  = 0,25

NВ2 = 6;         Р(В2) =  = 0,5

NВ3 = 3;         Р(В3) =  = 0,25

Цена игры V = 15,9

Р = {0,5; 0,25; 0,25}

Q = {0,25; 0,5; 0,25}

Общее решение игры:   <{0,5; 0,25; 0,25}; {0,25; 0,5; 0,25}; 15,9>

(П13)

Приложения

Приложение 4.1

4.1 Матричная игра с седловой точкой

В данной задаче максимин равен минимаксу, а это значит, что присутствует седловая точка.

Максимином или нижней ценой игры в чистых стратегиях называется наибольший из показателей эффективности стратегий αi

В данной матрице, минимальный гарантированный выигрыш 1 игрока по строкам равен: 110;105;100;420, следовательно maxmin = 420, что является 4 стратегией 1 игрока.     

Минимаксом или верхней ценой игры в чистых стратегиях называется наименьший показатель неэффективности статегий βj

Для 2 игрока максимальный проигрыш по столбцам матрицы составит:540;700;505;420;815;805, где minmax = 420, что является 4 стратегией 2 игрока.  

Приложение 5

5. Аффинные преобразования

Проведем аффинное преобразование.

, где  – элемент старой матрицы, k ≠ 0, m – константа, которая не изменяет решение матрицы.

Приложение 6

  1.  Доминирующие строки и столбцы

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

Приложение 7

  1.  Зеркальное преобразование

Зеркальное преобразование получится в результате транспонирования матрицы и изменения знака, т.е. столбцы матрицы станут строками, а строки-столбцами, числовые значения поменяют знак.

Приложение 8

  1.  Геометрическое и аналитическое решение матрицы 2х2

Пусть игрок А использует стратегию А1 с вероятностью Х, а стратегию А2 с вероятностью 1-Х

Игрок B использует стратегию В1 с вероятностью Y, а стратегию В2 с вероятностью 1-Y

Тогда математическое ожидание М(Х) выигрыша игрока А будет определяться по формуле:

Заметим, что

Точка Нэша ( ) определяется из уравнения:

=0

=0

Зная точку Нэша (), можно легко определить оптимальные

стратегии и цену игры v.

Построение графика

В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1=(х12). На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.

Из графического решения видно, что точка М – максимум нижней границы, решение и цена игры, т.е. средний выигрыш игрока А.

х1 и х2 – оптимальные смешанные стратегии игрока А: 0,8 и 0,2 соответственно.

Решение игры определяется точкой пересечения стратегий В1 и В2. Решение определяется именно верхней точкой нижней границы, но эта точка не всегда совпадает с точкой пересечения стратегий. Ордината  точки М–значение цены игры = 7,96. Чтобы найти цену игры, надо найти нижнюю границу пересекающихся прямых. На данной границе найти максимальную точку, ордината которой будет равна значению цены игры.  

Приложение 9

  1.  Решение матрицы 3х3 методом Крамера

Цену игры V и оптимальную стратегию х = (х1, х2, х3) игрока А  определяем с помощью  

Оптимальную стратегию у = (у1, у2, у3) игрока В определяем с помощью выражений

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

Приложение 12

12. Решение матрицы 2х6 графическим способом

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

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

В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый – стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (P1,P2).

На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.

Решение игры (2 x 6) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующих и дублирующих стратегий ни у одного из игроков нет. Максиминной оптимальной стратегии игрока A соответствует точка M, лежащая на пересечении прямых a12;a22 и a14;a24. Точка M лежит на нижней огибающей, которая является нижней ценой игры. Ордината точки – цена игры, равная 4.53, а перпендикуляр от точки M на ось А1А2 с абсциссой характеризует оптимальную стратегию игрока А – x2, равную 0.3. Следовательно, x1=0,7.

Проведем из точки M прямую, параллельную оси А1А2. Получим точки K и L и получим оптимальные стратегии игрока В.

Приложение 13

  1.  Решение матрицы 3х3 методом Брауна

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

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

Столбец 1 – номер интерации k;

2 – выбранная в данной партии стратегия Аi игрока А;

3-5 – накопленный выигрыш игрока А за первые k партий соответственно при стратегиях В123 игрока В. Из этих накопленных выигрышей выделяется минимальный, он определяет самую выгодную стратегию Вj в данной партии, номер которой проставляется в 6-ом столбце таблицы;

Столбец 6  – выбранная в данной партии стратегия Вj игрока В;

7-9 – приводится накопленный проигрыш игрока В за первые k партий соответственно при стратегиях А123 игрока А. Из этих значений подчеркивается минимальное  - оно и определяет выбор стратегий игрока А в следующей партии;

10 – нижняя оценка игры, она равна минимальному накопленному выигрышу, деленная на k;

11 - верхняя оценка игры, она равна максимальному накопленному проигрышу, деленная на k;

12 – среднее арифметическое нижней и верхней оценкой цен игры.

Работа в Excel

Нахождение седловой точки

Для нахождения минимальных значений по строкам и максимальных значений по столбцам нужно:

  1.  Вбить все данные в Excel, т.е. матрицу 5*6
  2.   В ячейку около первой строки нужно напечатать формулу =МИН (диапазон первой строки) и нажать Enter. Таким образом, мы найдем минимальное значение в первой строке. И так все эти действия нужно проделать для остальных четырех строк.

  1.  В ячейку около первого столбца нужно напечатать формулу = МАКС (диапазон первого столбца) и нажать  Enter. Таким образом, мы найдем максимальное значение первого столбца. И так все эти действия нужно проделать для остальных 5 столбцов.

Таблица накопленных выигрышей

  1. Для нахождения чисел в таблице накопленных выигрышей, для удобства подсчета, в последнем столбце выделим ячейку А3 и введем туда формулу, нажав enter протягиваем значения вниз. Таким образом мы узнаем V*

Литература

  1.  Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.
  2.  Колобашкина Л.В, Алюшин М.В.Теория игр. – М., 1998.

  1.  Теория игр – Википедия ru.wikipedia.org


 

А также другие работы, которые могут Вас заинтересовать

58438. Религия древних греков 67 KB
  Прочитайте или расскажите миф о Геракле стр. Сам же Зевс по греческой мифологии стал править небом и владеть Олимпом горой обиталищем богов гора Олимп находится в Северной Греции; расположенным под землей царством мертвых стал править Аид а Посейдону досталась власть над морями. Задание: прочитайте в учебнике миф о Деметре и ее дочери Персефоне. Какое природное явление отражено в этом мифе стр.
58439. Добрый Пастырь 225 KB
  Пояснить им что как пастух любит и заботится о своих овцах так Иисус любит нас даже знает каждого из нас по имени. Словарная работа: Пастырь – пастух овец Ход урока: 1. Мотивация Необходимые материалы: картинка с изображением пастуха и овечки иллюстрации снаряжения пастуха. Вниманию детей предлагаем картинку с изображением пастуха.
58440. Все починається з мами 45.5 KB
  Мета. Удосконалювати навички виразного читання, збагачувати активний словниковий запас; виховувати любов і повагу до матері красою художнього слова.
58441. Повторення теми «Одяг» 32 KB
  Мета. Повторити ЛО теми. Навчати діалогічного мовлення за темою. Практикувати у відповіді на запитання Whose is this? Увести та активізувати присвійні займенники в абсолютному відмінку
58443. Ляльки. Одяг 68 KB
  Take the short dress and colour it blue. Take the big boots and colour them black. Take the small shoes and colour them red. Take the new trousers and colour them grey.
58444. Герої мультфільмів 36 KB
  Jane came to visit Vicky. Look at picture b. What are they doing? Do you know this cartoon? Do you like it? Who are the characters in this cartoon? Do Jane and Vicky like it?icture. This is Sue again. Whats she wearing?
58445. Той ще не музика, хто в дудку дме. А. Григорук Той ще не музика, хто в дудку дме 35 KB
  У яку групу обєднаємо слова останньої групи Музичні інструменти. Як ви їх розумієте Прочитайте слова і вирази правильно наголошуючи один одному напівголосно. Поясніть її слова. Чому він винувато посміхнувся Чи підтримали їхню думку інші члени сімї
58446. Посилення колоніальної політики Російської імперії. Спроби ліквідації гетьманства 75.5 KB
  Спроби ліквідації гетьманства Становище в Україні після Полтавської битви. Заходи щодо економіки Гетьманщини. Україна від гетьманування Івана Скоропадського до Правління гетьманського уряду. Гетьман Іван Скоропадський.