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

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

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

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

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

 

 

 

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

 

 

 

 

 

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

по теории игр

 

 

 

 

 

 

 

 

 

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

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

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

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

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

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

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

 

 

 

Хабаровск 2013

 

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

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

Решение:

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

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

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

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

Если игрок  П не поменяет свою стратегию, т.е. П₁ =9, П₂=8, П₃=7, П₄=6, П₅=5 ,а игрок М изменит, т.е М₁ =5, М₂=6, М₃=7, М₄=8, М₅=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) Найти оптимальную смешанную стратегию первого игрока.