Теория игр

Размещено на http://www.allbest.ru/

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

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

Решение:

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

Игрок П (Петя) выбрал:

для стратегии П1: 5

для стратегии П2: 6

для стратегии П3: 7

для стратегии П4: 8

для стратегии П5: 9

Игрок М (Маша) выбрала:

для стратегии М1: 5

для стратегии М2: 6

для стратегии М3: 7

для стратегии М4: 8

для стратегии М5: 9

Платежная матрица будет 5-го порядка, так как у каждого из игроков по 5 стратегий.

Игрок П выбирает число х=5 и игрок М выбирает число у=5, то осуществляется упорядоченная пара стратегий (П1,М1). В такой ситуации 5+5=10<14, следовательно по правилам игры выиграла Маша, и Петя платит ей х=5 рублей. В платежной матрице, когда Петя является первым игроком, Маша - вторым, элемент а11=-5, этот элемент является выигрышем первого игрока П в ситуации (П1,М1). Знак «минус» появился от того, что Петя выплачивает деньги Маше, в то время как данная платежная матрица - это матрица выигрышей первого игрока, то есть Пети.

Рассуждая подобным образом, мы получим:

(П1,М2) 5+6=11<14, а12=-5

(П1,М3) 5+7=12<14, а13=-5

(П1,М4) 5+8=13<14, а14=-5

(П1,М5) 5+9=14, а15=0,

следовательно, противники ничего не выплачивают друг другу.

(П2,М1) 6+5=11<14, а21=-6

(П2,М2) 6+6=12<14, а22=-6

(П2,М3) 6+7=13<14, а23=-6

(П2,М4) 6+8=14, а24=0

(П2,М5) 6+9=15>14, а25=9,

то есть выигрывает Петя у=9 рублей, поэтому число положительное.

(П3,М1) 7+5=12<14, а31=-7

(П3,М2) 7+6=13<14, а32=-7

(П3,М3) 7+7=14, а33=0

(П3,М4) 7+8=15>14, а34=8

(П3,М5) 7+9=16>14, а35=9

(П4,М1) 8+5=13<14, а41=-8

(П4,М2) 8+6=14, а42=0

(П4,М3) 8+7=15>14, а43=7

(П4,М4) 8+8=16>14, а44=8



(П4,М5) 8+9=17>14, а45=9

(П5,М1) 9+5=14, а51=0

(П5,М2) 9+6=15>14, а52=6

(П5,М3) 9+7=16>14, а53=7

(П5,М4) 9+8=17>14, а54=8

(П5,М5) 9+9=18>14, а55=9

Таким образом, в игре, когда Петя является первым игроком, а Маша - вторым, мы получим платежную матрицу вида

-5 -5 -5 -5 0

-6 -6 -6 0 9

-7 -7 0 8 9

-8 0 7 8 9

0 6 7 8 9

Элемент этой матрицы аij есть выигрыш Пети в ситуации (Пi,Мj).

Если же первой стратегией Пети является выбор числа х=9, второй стратегией Пети - выбор числа 8, …, пятой стратегией - выбор числа 5. Стратегии Маши остаются прежними, тогда платежной матрицей будет

6 7 8 9

-8 0 7 8 9

-7 -7 0 8 9

-6 -6 -6 0 9

-5 -5 -5 -5 0

Ответ: Платежные матрицы игры - это



0 6 7 8 9 -5 -5 -5 -5 0

-8 0 7 8 9 -6 -6 -6 0 9

-7 -7 0 8 9 и -7 -7 0 8 9, при условии, что Петя

-6 -6 -6 0 9 -8 0 7 8 9

-5 -5 -5 -5 0 0 6 7 8 9

является первым игроком, Маша - вторым.

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

-5 -6 -7 -8 0

-5 -6 -7 0 9

Платежная матрица игры есть -5 -6 0 8 9 Найти нижнюю цену

-5 0 7 8 9

0 6 7 8 9

игры, верхнюю цену игры, чистую цену игры, все максиминные стратегии, все минимаксные стратегии, все седловые точки.

Решение:

Нижняя цена игры.

Обозначим через аi наименьший выигрыш игрока А при выборе им стратегии Аi для всех возможных стратегий Вj игрока В (аi - это наименьшее число в 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
(-это наибольшее число в последнем столбце таблицы 1,

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

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

Верхняя цена игры.

Обозначим через вj наибольший выигрыш игрока А при выборе игроком В стратегии Вj для всех возможных стратегий Аi игрока А (вj - это наибольшее число

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

Таблица 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
вj	0	6	7	8	9



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

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

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

Чистая цена игры.

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

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

Максиминная стратегия.

Стратегия первого игрока А, соответствующая максимину, называется максиминной стратегией. Нижняя цена игры платежной матрицы: б = 0. Число 0 находится в пятой строке, соответствующей стратегии А5 (табл.1), следовательно, номер 5 определяет максиминную стратегию.

Ответ: максиминная стратегия равна 5.

Минимаксная стратегия.

Стратегия второго игрока В, соответствующая минимаксу, называется минимаксной стратегией. Верхняя цена игры платежной матрицы: в = 0. Число 0 находится в первом столбце платежной матрицы, и соответствует стратегии В1 второго игрока В (табл.2), следовательно, номер 1 определяет минимаксную стратегию.

Ответ: минимаксная стратегия равна 1.

Седловая точка.

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

Т.к. б = 0 и в = 0, т.е. б = в, то в данной матрице есть седловая точка.

Ответ: в игре существует седловая точка со значением 0.

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

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

7 0 6 0

4 3 6 2

3 2 3 3

6 6 7 7

5 3 4 3

Найти все доминируемые (заведомо невыгодные) стратегии первого игрока, все доминируемые стратегии второго игрока.

Решение:

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

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

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



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

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

2 4 1 1

3 6 2 1

1 5 3 2

Какие из данных векторов ;0;, ;;, ;0;;0, ;0;;0

являются смешанными стратегиями первого игрока?

Если смешанная стратегия первого игрока х = ; ;, а второго игрока - у = ; 0; 0;, то чему равен выигрыш второго игрока в данной ситуации (х;у)?

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

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

Решение:

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

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

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

Вектор ;; не является смешанной стратегией первого игрока, т.к. сумма компонентов не равна 1.

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

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

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

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

при ?? = 3, ?? = 4, = , = , = , = , = 0, = 0, = мы получим, что

??(??;??)=(+++)+(+++)+

+ (+++)

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

??(??;??)= (2· + 4·0 + 1·0 + 1· ) + (3· + 6·0 + 2·0 + 1· ) + (1· + +5·0+ 3·0 + 2· )= + + = .

Ответ: Выигрыш второго игрока в данной ситуации (??;??) равен .



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

и верхнюю цену игры

Так как 12, то седловая точка отсутствует.

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

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

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

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

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

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

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

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

, , .

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

, .



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

= , = , = =

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

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

Цена игры равна = =

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

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

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

	В1	В2	В3
А1	40	40	30
А2	70	20	70
А3	80	30	40



Указать все номера оптимальных стратегий фермера Петрова по критерии Гурвица с параметром = 0,6.

Решение:

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

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

.

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

Применим этот критерий к нашей задаче, полагая = 0,6 (небольшая склонность к пессимизму).

Состояния природы	В1	В2	В3
Стратегии фермера Петрова	А1	40	40	30	30	40	34
	А2	70	20	70	20	70	40
	А3	80	30	40	30	80	50

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

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

вектор платежный матрица игра

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

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

Решение:

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

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

4	8
2	6

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

2	4
8	6

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

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

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

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

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

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

Решение:

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

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

?0, 0 ? 0, ? 0, + 0 + = 1.

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

?0, 0 ? 0, ? 0, + 0 + = 1.



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

+ = > 1.

Вектор ; не является дележом в игре трех лиц, т.к. он содержит всего две компоненты, а игроков трое.

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

Размещено на Allbest.ru