Теория игр

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

Российская Федерация

Министерство образования и науки

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

«Тюменский государственный университет» в г. Новый Уренгой

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

По дисциплине: «Методы оптимизации решений»

На тему: Теория игр

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

Направление «Экономика»

А.В. Чернодед

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

В.Г. Сергеев

Новый Уренгой 2014



Оглавление

Введение

1. Основные понятия теории игр

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

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

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

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

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

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

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

Заключение

Список использованной литературы



Введение

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

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

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

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



1. Основные понятия теории игр

матричная игра математический стратегия

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

Теория игр была разработана Дж. фон Нейманном и О. Моргенштерном в 1944г., ее дальнейшую разработку продолжил Дж. Нэш.

Ознакомимся с основными понятиями теории игр. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, - игроками, а исход конфликта - выигрышем. Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая: 1) варианты действий игроков; 2) объём информации каждого игрока о поведении партнёров; 3) выигрыш, к которому приводит каждая совокупность действий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулём, выигрыш - единицей, а ничью - ?.

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

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

Выдающийся французский математик Луи Борель еще в начале XX века предпринял издание большого, многотомного «Курса теории вероятностей и ее приложений». Предпоследний том был посвящен «Приложениям к азартным играм». Ученый подвел в нем итог своим длительным исследованиям азартных игр, которыми он интересовался как математик. В теорию игр Борель внес смелые и оригинальные идеи. Он попытался найти математическую формулировку игр, когда течение игры зависело от умения игроков. Со временем многие ученые развили теорию. Она стала гораздо шире теории азартных игр.

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

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

Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход - это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Случайный ход - это случайно выбранное действие (например, выбор карты из перетасованной колоды).

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

2. Платежная матрица. Задача № 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

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



3. Матричная игра в чистых стратегиях. Задача № 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.

4. Доминируемые стратегии. Задача № 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.

5. Смешанное расширение матричной игры. Задача № 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-ую стратегию игрок выбирает с нулевой вероятностью. Таким образом, оптимальная смешанная стратегия первого игрока равна .

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

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

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

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

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

Таблица 4

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

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

Решение:

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

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

.

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

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

Таблица 5

Состояния природы	В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.

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



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

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

Решение:

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

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

Таблица 6

4	8
2	6

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

Таблица 7

2	4
8	6

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

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

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

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

8. Кооперативные игры. Задача № 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; и .



Заключение

«Есть в современной математике одна область, она носит безобидное название теории игр, но ей, несомненно, суждено сыграть очень важную роль в человековедении самого ближайшего будущего, - говорил Джон фон Нейман, один из основоположников кибернетики.

Кибернетика - занимается вопросами оптимального поведения людей при наличии противодействующего противника. Для ученого противник - это природа со всеми ее явлениями; экспериментатор борется со средой; математик - с загадками математического мира; инженер - с сопротивлением материалов».



Список использованной литературы

1. « Математические методы в программировании » : / Агальцов В.П., Волдайская И.В. Учебник : - М . : ИД «ФОРУМ» : ИНФРА-М, 2006. - 224с. : ил. -(Профессиональное образование). - (Учимся программировать).

2. Лекции по дисциплине « Математические методы ».

3. «Математические методы: Учебник» / Партика Т.Л., Попов И.И. - М: ФОРУМ: ИНФРА, 2005.

4.«Математическое программирование» / Костевич Л., издательство «Новое знание», 2003.

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

...