Контрольная работа по "Теории игр"

Министерство  образования и науки российской федерации

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

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

«Тихоокеанский  государственный университет»

 

 

 

Кафедра прикладная математика

 

 

 

 

 

Контрольная работа

по теории игр

 

 

 

 

 

 

 

 

 

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

Группа (поток)                     ФКзу - 21

Курс (год обучения)            1

Номер зачетной книжки

Фамилия                               Кульбеда

Имя                                       Маргарита

Отчество                               Игоревна

 

 

 

Хабаровск 2013

 

Задача 1.  (Платежная матрица)

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

Решение:

Для составления  платежной матрицы следует проанализировать поведение каждого из игроков. Игрок  П (Петя) может выбрать натуральное  число 5 – обозначим эту стратегию  П1 , может выбрать натуральное  число 6 – обозначим эту стратегию П2, …, может выбрать натуральное число 9 – обозначим эту стратегию П5 . Игрок М (Маша) может выбрать натуральное число 5 – обозначим эту стратегию М1,  может выбрать натуральное число 6 – обозначим эту стратеги М2,…, может выбрать натуральное число 9 – обозначим эту стратегию М5. Платежная матрица будет 5-го порядка, так как у каждого из игроков по 5 стратегий.

Если игрок  П выбирает число х=5 и игрок  М выбирает число у=5, то осуществляется упорядоченная пара стратегий (П1,М1). В такой ситуации 5+5=8<14, следовательно по правилам игры выиграла Маша, и Петя платит ей x=5 рубля. В платежной матрице, когда Петя является первым игроком, Маша – вторым, элемент a11=-5, этот элемент является выигрышем первого игрока П в ситуации (П1,М1). Знак «минус» появился от того, что Петя выплачивает деньги Маше, в то время как данная платежная матрица – это матрица выигрышей первого игрока, то есть Пети. Аналогично, в ситуации (П1,М2)  имеем, что 5+6=11<14, следовательно a= -5 – это выигрыш первого игрока в ситуации (П1,М2).   Рассуждая подобным образом, мы получим, что a13=-5 и a14=-5. В ситуации (П5,М5). получим, что 5+9=14 следовательно противники ничего не выплачивают друг другу, то есть a15=0. В ситуации (П3,М5) 7+9=16>14, выигрывает Петя y=9 рублей, поэтому число a35=9 положительное. Таким образом, в игре, когда Петя является первым игроком, а Маша – вторым, мы получим платежную матрицу вида:

Если игрок  П не поменяет свою стратегию, т.е. П1 =5, П2=6, П3=7, П4=8, П5=9,а игрок М изменит, т.е М1 =9, М2=8, М3=7, М4=6, М5=5, то когда Петя является первым игроком, а Маша – вторым, мы получим платежную матрицу вида:

Если игрок  П поменяет свою стратегию, т.е. П1 =9, П2=8, П3=7, П4=6, П5=5, а игрок М не изменит, т.е М1 =9, М2=8, М3=7, М4=6, М5=5, , то когда Петя является первым игроком, а Маша – вторым, мы получим платежную матрицу вида:

Если игрок  П не поменяет свою стратегию, т.е. П1 =9, П2=8, П3=7, П4=6, П5=5 ,а игрок М изменит, т.е М1 =5, М2=6, М3=7, М4=8, М5=9, то когда Петя является первым игроком, а Маша – вторым, мы получим платежную матрицу вида:

 

 

 

 

Задача 2.  (Матричная игра в чистых стратегиях)

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

Решение:

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

В первой строке минимальное число равно -8, во второй строке – это -7, в третьей –  это -6, в четверной –это -5, в пятой  – это 0 Выпишем эти числа в  отдельный столбец справа от платежной матрицы.

Таблица 1

 

В1

В2

В3

В4

В5

аi

А1

-5

-6

-7

-8

0

-8

А2

-5

-6

-7

0

9

-7

А3

-5

-6

0

8

9

-6

А4

-5

0

7

8

9

-5

А5

0

6

7

8

9

0


 

Среди всех найденных чисел  (i = -8,…, 0) выберем наибольшее: ( –это наибольшее число в последнем столбце таблицы 1,a=max ).

Назовем нижней ценой игры, или максимином.

Ответ: нижняя цена игры равна 0.

2. Обозначим  через  наибольший выигрыш игрока A при выборе игроком В стратегии для всех возможных стратегий игрока А ( – это наибольшее число в j – ом столбце платежной матрицы), т.е. .

В первом столбце  максимальное число равно 0, во втором столбце – это 6, в третьем –  это 7, в четвертом – это 8, в  пятом – это . Выпишем эти числа  в отдельную строку снизу под  платежной матрицей.

Таблица 2

 

В1

В2

В3

В4

В5

А1

-5

-6

-7

-8

0

А2

-5

-6

-7

0

9

А3

-5

-6

0

8

9

А4

-5

0

7

8

9

А5

0

6

7

8

9

0

6

7

8

9


 

Среди всех чисел  , записанных в последней строке таблицы 2, выберем наименьшее, ( min= ).

Назовем верхней ценой игры, или минимаксом.

Ответ: верхняя цена игры равна 0.

3. Если нижняя  и верхняя цена игры совпадают  , то общее значение верхней и нижней цены называется чистой ценой игры, или ценой игры. Но если нижняя цена игры не равна верхней, то чистая цена игры не определена.

В нашей задаче а=0 и в=0 (см. решение задач 2. и 3), следовательно, чистая цена равна 0.

4. Стратегия  первого игрока А, соответствующая максимину, называется максиминной стратегией. Найдем нижнюю цену игры платежной матрицы: а=0. (см. решение задачи 2).

 

В1

В2

В3

В4

В5

аi

А1

-5

-6

-7

-8

0

-8

А2

-5

-6

-7

0

9

-7

А3

-5

-6

0

8

9

-6

А4

-5

0

7

8

9

-5

А5

0

6

7

8

9

0


 

Число 0 находится  в пятой строке, соответствующей  стратегии  , следовательно, номер 5 определяет максиминную стратегию.

5. Стратегия второго игрока В, соответствующая минимаксу, называется минимаксной стратегией. Найдем верхнюю цену игры платежной матрицы: В=0. (см. решение задачи 3).

 

В1

В2

В3

В4

В5

А1

-5

-6

-7

-8

0

А2

-5

-6

-7

0

9

А3

-5

-6

0

8

9

А4

-5

0

7

8

9

А5

0

6

7

8

9

0

6

7

8

9


 

Число 0 находится  в первом столбце платежной матрицы, и соответствует стратегии второго игрока В, следовательно, номер 1 определяет минимаксную стратегию.

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

Т.к.  а=0 (см. 2 задачу) и в=0 (см. 3 задачу), т.е. а=в, то в данной матрице седловая точка равна 5,1.

Ответ: Седлова точка =5,1

 

Задача 3.  (Доминируемые стратегии)

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

Решение:

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

Т.к. все элементы пятой строки не больше (т.е. меньше или равны) соответствующих элементов  четвертой строки, то пятая строка является доминируемой.

Т.к. все элементы второй строки не больше (т.е. меньше или  равны) соответствующих элементов  четвертой строки, то вторая строка является доминируемой.

Т.к. все элементы третей строки не больше (т.е. меньше или равны) соответствующих элементов четвертой,пятой строки, то третья строка является доминируемой.

Ответ: доминируемой стратегией первого игрока является 2,3 и 5 строки.

 

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

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

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

Ответ: доминируемыми стратегиями второго игрока являются 1 и 3

 

Задача 4.  Смешанное расширение матричной игры

Платежная матрица  игры есть .

1) Какие из данных векторов , , , являются смешанными стратегиями первого игрока?

2) Если смешанная стратегия первого игрока , а второго игрока – , то чему равен выигрыш второго игрока в данной ситуации ?

3) Найти оптимальную смешанную стратегию первого игрока.

4) Указать цену игры.

Решение:

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

Платежная матрица  игры есть . Тогда смешанными стратегиями первого игрока являются…

-: -: -: -:

Решение:

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

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

Вектор  является смешанной стратегией первого игрока, так как это трехмерный вектор с неотрицательными компонентами, сумма которых равна 1.

Вектор  не является смешанной стратегией первого игрока, так как это трехмерный вектор сумма которых больше 1.

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

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

Ответ: Вектор  являются смешанной стратегией первого игрока.

2)Выигрыши игроков

Платежная матрица игры есть . Cмешанная стратегия первого игрока , а второго игрока – . Тогда выигрыш второго игрока в данной ситуации

Решение:

Выигрыш второго игрока A в игровой ситуации определяется по формуле:

,

при мы получим,

что

, т.е.

H(x;y)= x1 * (a11y1+a12y2+a13y3+a14y4) + x2 * (a21y1+a22y2 +a23y3+a24y4) +

+ x3 * (a31y1+a32y2+a33y3+a34y4).

После подстановки  чисел мы будем иметь

Ответ: выигрыш первого игрока в данной ситуации равен .

  1. Оптимальные смешанные стратегии

Платежная матрица  игры есть . Тогда оптимальная смешанная стратегия первого игрока равна …

-: -: -: -:

Решение:

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

Будем искать оптимальные  решения в смешанных стратегиях.

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

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

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

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

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

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

Решив эту систему, получим , , .

Подставляя  в эти формулы числа матрицы  , будем иметь , .

 – это вероятность,  с которой второй игрок может  выбирать 1-ую чистую стратегию,  а  – это вероятность, с которой он может выбирать 4-ую чистую стратегию, вспомним, что 2-ую и 3-ую стратегии игрок выбирает с нулевой вероятностью. Таким образом, оптимальная смешанная стратегия второго игрока равна .

Ответ: Оптимальная смешанная стратегия первого игрока равна .

4)  Цена игры

Вычислим цену игры подставив р1, р2 в уравнение:

.

Ответ: цена игры:

 

Задача 5.  (Матричные игры с природой)

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

 

 

 

 

         

   

40

40

30

70

20

70

80

30

40


 

Указать все  номера оптимальных стратегий фермера Иванова по критерию Гурвица с параметром .

Решение:

Критерий Сэвиджа  – принцип минимаксного риска (пессимистичный принцип) при выборе стратегии советует опираться не на «выигрыш», а на риск.

Риск определяется как разность между максимальным выигрышем (при условии полной информации о состоянии природы) и реальным выигрышем (при незнании состояния  природы):    .

Найдем  – максимальное число в j-ом столбце.

 

40

40

30

70

20

70

80

30

40

80

40

70


 

Составим матрицу  рисков фермера Петрова:

 

40

0

40

10

20

0

0

10

30


 

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

 

40

0

40

40

10

20

0

20

0

10

30

30


Таблица 3

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

.                                       (1)

В нашей задаче в последнем столбце найдем минимальное  число 

Выберем в соответствии с формулой (1) ту стратегию, где достигается  минимальный из максимальных по всем состояниям природы риск. Число 15 находится  во второй строке и соответствует второй стратегии .

Ответ: номер оптимальной стратегии фермера по критерию Сэвиджа равен 2.

Решение игры по критерию Гурвица

Тогда номер  оптимальной стратегии фермера  Иванова по критерию Гурвица с  параметром равен …

Решение:

Этот критерий рекомендует при выборе решения  не руководствоваться ни крайним  пессимизмом, ни крайним оптимизмом. Согласно критерию Гурвица максимизируется  взвешенное среднее между выигрышами крайнего пессимизма и крайнего оптимизма, причем «вес» – коэффициент пессимизма , заключенный между 0 и 1.

В соответствии с критерием Гурвица оптимальная  стратегия выбирается из условия  .

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

Состояния природы

Стратегии фермера Иванова

40

40

30

30

40

34

70

20

70

20

70

40

80

30

40

30

80

50


 

Максимальное  значение достигается при выборе первой стратегии А3.

Ответ: номер оптимальной стратегии фермера Иванова по критерию Гурвица равен 3.

Задача 6.  (Биматричные игры)

Платежная матрица  первого игрока есть .  Платежная матрица второго игрока равна . Найти все ситуации равновесия по Нэшу.

 Тогда ситуацией равновесия по Нэшу является …

-: не существует 

-:

-:

-:

Решение:

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

Затем в каждой строке матрицы B второго игрока выберем  наибольший элемент. Эти элементы подчеркнуты  в матрице B. Их положение будет определять приемлемые ситуации 2-го игрока, когда первый игрок выбрал i-ую стратегию соответственно.

Платежная матрица  игрока А:

4

8

2

6


Платежная матрица  игрока B:

2

4

8

6


 

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

В нашей задаче число 8 первой матрицы А и число 4 второй матрицы В находятся на одном и том же месте: во второй строке и втором столбце. Таким образом ситуация (1;2) и является равновесной по Нэшу.

В равновесной  ситуации (1;2) первый игрок выигрывает 8 единиц, а второй игрок – 4 единиц.

Ответ: ситуацией равновесия по Нэшу является (1;2).

 

Задача 7.  (Кооперативные игры)

Указать, какие  из векторов ; ; ; являются дележами в кооперативной игре трех лиц в (0-1) редуцированной форме, и почему Вы выбрали эти вектора?

В кооперативной  игре трех лиц в (0-1) редуцированной форме дележами являются …

-:

-:

-:

-:

Решение:

Дележом в игре n лиц в (0-1) редуцированной форме называется любой вектор компоненты которого удовлетворяют условиям:

Контрольная работа по Теории игр 📙 Контрольная → 🆔 70774

Контрольная работа по Теории игр 📙 Контрольная → 🆔 70774

Контрольная работа по "Теории игр"