Введение в теорию игр. Антагонистические игры. Чистые стратегии

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

Лабораторная работа

по дисциплине «ТСиСА»

Введение в теорию игр. Антагонистические игры. Чистые стратегии

1. Краткие теоретические сведения

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

теория игра стратегия

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

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

Математическая модель конфликтной ситуации называется игрой. Раздел теории исследования операций (теории оптимальных решений), занимающийся математическими моделями принятия оптимальных решений в условиях конфликта, называется теорией игр.

Заинтересованные стороны (в частности лица) в игре называются игроками.

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

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

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

В общем случае парную игру с нулевой суммой можно записать платежной матрицей:

.

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

Найдем наилучшую стратегию первого игрока: минимальное число в каждой строке, обозначимее через

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

.

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

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

,

где - верхняя цена игры (минимакс).

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

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

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

Индивидуальное задание

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

Варианты индивидуального задания



1.2 Выбор стратегии при помощи статистических критериев

Возможно строительство четырех типов электростанций: А₁ (тепловых), А₂ (приплотинных), А₃ (бесшлюзовых), А₄(шлюзовых). Эффективность каждого из типов зависит от различных факторов: режима рек, стоимости топлива и его перевозки т.п. Было выделено четыре различных состояния, каждое из которых означает определенное сочетание факторов, влияющих на эффективность энергетических объектов. Данные состояния природы обозначаются как Р₁, Р₂, Р₃, Р₄ (вероятности состояний соответственно равны 0,1; 0,2; 0,4; 0,3). Экономическая эффективность строительства отдельных типов электростанций изменяется в зависимости от состояний природы и задана платежной матрицей. Необходимо выбрать наиболее подходящую стратегию при помощи статистических критериев (с помощью программы MS Excel).

1. Вводятся элементы платежной матрицы и вероятности:

2. Для определения оптимальной стратегии по критерию Байеса элементы платежной матрицы копируются в ячейки А8:D11.

3. В ячейку Е8 вводится формула $F$1*A1+$F$2*B1+$F$3*C1+$F$4*D1 и копируется в ячейки Е9:Е11. Далее в ячейку Е12 вводится формула =МАКС(E8:E11), исходя из полученного результата выделяются строки, соответствующие оптимальным стратегиям, в данном случае это стратегии А₂ и А₃.

4. Для определения оптимальной стратегии по критерию Лапласа элементы платежной матрицы копируются в ячейки А16:D19.

5. В ячейку Е16 вводится формула =1/4*СУММ(A16:D16) и копируется в ячейки Е17:Е19. Далее в ячейку Е20 вводится формула =МАКС(E16:E19), исходя из полученного результата выделяются строки, соответствующие оптимальным стратегиям, в данном случае это стратегия А₃.

6. Для определения оптимальной стратегии по критерию Вальда элементы платежной матрицы копируются в ячейки А25:D28.



7. В ячейку Е25 вводится формула =МИН(A25:D25) и копируется в ячейки E26:Е28. Далее в ячейку Е29 вводится формула =МАКС(E25:E28), исходя из полученного результата выделяются строки, соответствующие оптимальным стратегиям, в данном случае это стратегия А₃.

8. Для определения оптимальной стратегии по критерию Сэвиджа , элементы платежной матрицы копируются в ячейки А33:D36.

9. В ячейках А37:D37 вычисляются максимальные элементы столбцов по формулам =МАКС(А33:А36), =МАКС(В33:В36), =МАКС(С33:С36), =МАКС(D33:D36).

10. В ячейках А40:D43 вычисляются элементы матрицы рисков. В ячейку А40 вводится формула =$A$37-A33 и копируется в ячейки А41:А43. В ячейку В40 вводится формула =$В$37-В33 и копируется в ячейки В41:В43. В ячейку С40 вводится формула =$С$37-С33 и копируется в ячейки С41:С43. В ячейку D40 вводится формула =$D$37-D33 и копируется в ячейки D41:D43. В ячейку Е40 вводится формула =МАКС(A40:D40) и копируется в ячейки Е41:Е43. Далее в ячейку Е44 вводится формула =МИН(E40:E43), исходя из полученного результата выделяются строки, соответствующие оптимальным стратегиям, в данном случае это стратегия А_3.

11. Для определения оптимальной стратегии по критерию Гурвица элементы платежной матрицы копируются в ячейки А47:D50.

12. В ячейку Е47 вводится формула

=0,5*(МИН(A47:D47)+МАКС(A47:D47)) и копируется в ячейки Е48:Е50, в ячейку Е51 вводится формула =МАКС(Е47:Е50), исходя из полученного результата выделяются строки, соответствующие оптимальным стратегиям, в данном случае это стратегия А₂.

13. Выписываются наименования стратегий, частоты стратегий (2 и 4), общее число стратегий (6) в ячейки А53:В57, в ячейках С53:С57вычисляются вероятности по формулам =B53/$B$57, =B54/$B$57, =B55/$B$57, =B56/$B$57, =B57/$B$57.

14. В данном случае рекомендованной стратегий является стратегия А₃ (бесшлюзовые электростанции).

Решить самостоятельно: магазин может завезти в различных пропорциях товары трех типов (А₁, А₂, А₃), их реализация и прибыль магазина зависят от вида товара и состояния спроса. Предполагается, что спрос может находиться в одном из трех состояний - В₁, В₂, В₃ (вероятности 0,6; 0,2; 0,2). Прибыли в зависимости от состояний спроса заданы платежной матрицей.

Определить оптимальные пропорции в закупке товаров при помощи статистических критериев.

Варианты индивидуального задания:



1.3 «Смешанные стратегии. Решения игр 2х2, 2хn и mx2»

1.3.1 Решение игры 2х2

Пусть игра задана платежной матрицей

А=	Ai Вj	B1	B2
	A1
	A2

По оси абсцисс отложим единичный отрезок А₁ А₂, где точка А₁(0, 0) изображает стратегию А₁, А₂ (1, 0) - стратегию А₂, а каждая промежуточная точка S_Aэтого отрезка изображает смешанную стратегию первого игрока A P= (p₁, p₂), где p₁- расстояние от точки S_A до A₂, p₂-расстояние от точки S_A до A₁,т.е. р₂=1-р₁.

Выигрыш игрока A будем откладывать на вертикальных отрезках.



Случай 1. Если игрок B применит стратегию В₁, то выигрыш игрока A пристратегии А₁равен а₁₁, поэтому на оси ординат отложим отрезок А₁В₁=а₁₁.

Приприменении игроком A стратегии А₂выигрыш равен а₂₁, отложим этот отрезок наперпендикуляре из точки А₂, обозначим полученную точку В₁'. Ордината любойточки М₁отрезка В₁В₁? равна среднему выигрышу игрока A при применении смешаннойстратегии S_A(действительно, этот выигрыш равен математическому ожиданию случайнойвеличины, т.е. a₁₁p₁ + a₂₁p₂).

Запишем уравнение прямой В₁В₁?:

. (1)

Тогда при x = p₂ получим y = a₁₁ + p₂a₂₁ - p₂a₁₁ = a₁₁(1-p₂) + p₂a₂₁ = a₁₁p₁ + a₂₁p₂.

Случай 2. Если игрок B применяет стратегию В₂, то аналогично откладываем отрезки а₁₂и а₂₂и получаем отрезок В₂В₂?:

. (2)

Ордината любой точки М₂ отрезка В₂В₂? -выигрыш игрока A, если A применяет смешанную стратегию S_A, а B - стратегию В₂.

Построим нижнюю границу выигрыша игрока А - ломаную В₁NВ₂?. Ординаты точек этой ломаной показывают минимальные выигрыши игрока А при использовании им любой смешанной стратегии. Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение. Ордината точки N равна цене игры.

Проекция этой точки на ось ОХ показывает оптимальную стратегию игрока А: .

Оптимальную стратегию и цену игры находим, решая (1) и (2) совместно как систему из двух уравнений с двумя неизвестными: х и у, где - оптимальная стратегия игрока А, V=у - цена игры.

Аналогично находится оптимальная стратегия игрока B, только в соответствии с принципом минимакса надо находить верхнюю границу выигрыша, т. е. строить ломаную А₂NА₁? и брать точку N с наименьшей ординатой.

Абсцисса точки N определяет оптимальную стратегию игрока B, т. е. .

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

Пример 3. Найти решение игры, заданной матрицей



Решение.

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

По формулам

Находим оптимальные стратегии и цену игры

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

Данный ответ означает следующее:

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

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

У таких игр всегда имеется решение, содержащее не более двух активных стратегий для каждого из игроков. Если найти эти активные стратегии, то игра 2 х n или m х 2 сводится к игре 2 х 2, которую мы уже умеем решать. Поэтому игры 2 х n и m х 2 решают обычно графоаналитическим методом.

1.3.2 Решение игры 2хn

Рассмотрим решение матричной игры на примере.

Пример.

Решение.

	1	4	7	1
	6	3	2	2
	6	4	7	2 4

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

1. Строим графическое изображение игры.

Если игрок B применяет стратегию В₁, то выигрыш игрока A при применении стратегии А₁ равен а₁₁ = 1, а при использовании А₂ выигрыш равен а₂₁ = 6, поэтому откладываем отрезки А₁В₁ = 1, А₂В₁^? = 6 на перпендикулярах в А₁ и А₂ и соединяем их отрезком. Аналогично для стратегий В₂ и В₃ строим отрезки В₂ В₂^?и В₃ В₃^?.

2. Выделяем нижнюю границу выигрыша В₁М N В₃^? и находим наибольшую ординату этой нижней границы, ординату точки М, которая равна цене игры г.

3. Определяем пару стратегий, пересекающихся в точке оптимума М.

В этой точке пересекаются отрезки В₂В₂^? и В₁В₁^?, соответствующие стратегиям В₁ и В₂ игрока B. Следовательно, стратегию В₃ ему применять невыгодно. Исключаем из матрицы третий столбец и решаем игру 2 x 2 аналитически:

 ; ; .

Ответ: г = 7/2; P_A= (1/2; 1/2); Q_B= (1/6; 5/6; 0).

Окончательно правила решения игр 2xn и mx2 следующие:

¦ строится графическое изображение игры;

¦ выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы, которая равна цене игры V;

¦ определяется пара стратегий, пересекающихся в точке оптимума M. Эти стратегии являются активными стратегиями игрока B. Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них;

¦ решается полученная игра 2x2.

Решение игры mx2 осуществляется аналогично.

Вместо пункта 2:

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

Пример 4. Найти решение игры, заданной матрицей

Решение.

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

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

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

Решение игры сводится к решению игры с матрицей 2х2

По формулам находим оптимальные стратегии и цену игры:

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

Данный ответ означает следующее:

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

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

Индивидуальные задания:

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

1. 2. 3.

4. 5. 6.

7. 8. 9.

10.

1.3.3 Решение игры mх2

Пример 5. Найти решение игры, заданной матрицей

Решение:

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



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

Решение игры сводится к решению игры с матрицей 2х2:

Индивидуальные задания:

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

1. 2. 3. 4. 5.

6. 7. 8. 9. 10.

Список источников информации по дисциплине «Теория игр»

1. Косоруков О.А., Мищенко А.В. Исследование операций: Учебник/ Косоруков О.А., Мищенко А.В.//Под общ. Ред. Д.э.н., проф. Н.П. Тихомирова. - М.: Издательство «Экзамен», 2003. - 448 с.

2. Абланская Л.В., Бабешко Л.О. и др. Экономико-математическое моделирование: Учебник для студентов вузов/Под общ. Ред. Дрогобыцкого.- М.: Издательство «Экзамен», 2004.- 800 с.

3. Розен В.В. математические модели принятия решений в экономике: Учебное пособие.- М.: Издательство «Высшая школа», 2002.- 288 с.

4. Пинегина М.В. Математические методы и модели в экономике: учеб. пособие для студентов вузов.- М.: «Экзамен», 2005.- 267 с.

5. Попов А.М., Сотников В.Н. Экономико-математические методы и модели: Высшая математика для экономистов: Учебник для бакалавров / А. М. Попов, В. Н. Сотников. -- М.: Юрайт, 2011. -- 479 с.

6. Красс М.С. Математика для экономистов: учеб. Пособие: рек. УМО вузов/ М.С. Красс, Б.П. Чупрынов. - СПб.: Питер, 2010. - 464 с.

6. http://window.edu.ru - единое окно доступа к образовательным ресурсам.

7. http://www.intuit.ru - интернет-университет.

Структура отчета по лабораторной работе

Титульный лист (см. Приложение);

Название лабораторной работы;

Цель лабораторной работы;

Краткие теоретические сведения, необходимые для выполнения лабораторной работы;

Индивидуальное задание;

Описание хода выполнения лабораторной работы;

Выводы, обобщения, критический анализ и комментарии к результатам, полученным в процессе выполнения лабораторной работы;

Список литературы, использованной для выполнения лабораторной работы.

Оформление отчета по лабораторной работе

Текст отчета пишется с одной стороны стандартного машинописного листа формата А4. Межстрочное расстояние 1 интервал, размер шрифта - 12, шрифт - Times new Roman. Слева и справа на полях оставляются поля: слева 3 см., справа 1 - 1.5 см., сверху и снизу 2.0-2.5 см. Абзацный отступ -1.25 см.

Список литературы должен оформляться согласно существующим правилам.

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

...