21813

ТЕОРИЯ МАТРИЧНЫХ ИГР. Примеры решения задач при парной игре с нулевой суммой

Лекция

Менеджмент, консалтинг и предпринимательство

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

Русский

2013-08-03

91 KB

96 чел.

ТЕМА 8. ТЕОРИЯ МАТРИЧНЫХ ИГР

Лекция 9

1. Постановка задачи выбора в условиях неопределенности

2.Основные определения и теоремы теории игр

3.Примеры решения задач при парной игре с нулевой суммой.

1. Постановка задачи выбора в условиях неопределенности

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

В реальных задачах часто приходится иметь дело с ситуацией, когда альтернатива неоднозначно определяет последствия сделанного выбора. Другими словами, имеется набор возможных исходов y  Y, из которых один окажется совмещенным с выбранной альтернативой, но с какой именно – в момент выбора неизвестно, но станет ясно только тогда, когда выбор уже сделан, и ничего изменить нельзя. Хотя с разной альтернативой x  X связано одно и то же множество исходов Y, для разных альтернатив разные исходы имеют неодинаковое значение.

1.1 Задание неопределенности с помощью матрицы

В случае дискретного набора альтернатив и исходов описанную выше стиуацию можно представить в виде матрицы

X,  Y

y1

y2

y3

yj

ym

x1

a11

a12

a13

a1i

a1m

x2

a21

a22

a23

a2i

a2m

xi

ai1

ai2

ai3

aii

aim

xn

an1

an2

an3

ani

anm

Вектор y = (y1,….ym) – это все возможные исходы. Числа aii выражают оценку ситуации, когда сделан выбор альтернативы хi и реализовался исход yi. В разных случаях числа aii могут иметь различный смысл (“выигрыш”, “потери”, “платеж”).

Возможны два варианта:

  1.  все строки ai = (ai1, …. aim) (т.е. мы видим, это тоже вектор) одинаковы и проблемы выбора между альтернативами нет;
  2.  строки различны, следовательно, возникает проблемв выбора альтернативы.

В случае непрерывных множеств X и Y ситуация описывается аналогично с помощью задаваемых на этих множествах функциях a (x,y), x  X, y  Y.

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

2.Основные определения и теоремы теории игр

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

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

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

 Конфликт - это противоречие, вызванное противоположными интересами сторон.

 Конфликтная ситуация - ситуация в которой участвуют стороны интересы которых полностью или частично противоположны.

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

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

 Платежом называется количественная оценка результатов игры.

 Парная игра - игра в которой участвуют только две стороны (два игрока).

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

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

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

Пусть мы имеем парную игру с нулевой суммой, один игрок может выбрать при данном ходе i -ю стратегию из m своих возможных (i=1..m), а второй, не зная выбора первого  j -ю стратегию из n своих возможных стратегий (j=1..n). В результате первый игрок выигрывает величину , а второй проигрывает эту величину. Из этих величин составим матрицу A.

                              A 

 Платежная матрица - так назовем матрицу A или еще по другому матрицей игры.

 Конечной игрой размерности (m  n) называется игра определенная матрицей А имеющей m строк и n столбцов.

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

а соответствующая ему стратегия (строка) максиминной.

 Минимаксом или верхней ценой игры назавем число

,

а соответствующая ему стратегия (столбец) минимаксной.

 Теорема 1.1. Нижняя цена игры всегда не превосходит верхнюю цену игры.

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

 Ценой игры называется величина , если .

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

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

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

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

 Теорема 1.2. Основная теорема теории матричных игр. Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

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

 2. Примеры решения задач при парной игре с нулевой суммой

   Задача 1.1.

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

                         А=.

   

   Решение. Прежде всего проверим наличие седловой точки в данной матрице.

Для этого найдем нижнюю и верхнюю цену игры.

Минимальные элементы по строкам равны (2 и 3) тогда нижняя цена игры   = max (2; 3) = 3. Максимальные элементы по столбцам равны (3 и 6) тогда верхняя цена игры = min (3; 6) = 3. Отсюда видно, что = =3 и мы имеем седловую точку .= 3, т.е. задача имеет решение в чистых стратегиях.

Оптимальные чистые стратегии для первого и второго игроков равны соответственно U* = (0; 1),  Z* = (1; 0), а цена игры = 3.

   Задача 1.2.

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

                         А=.

   Решение. Прежде всего проверим наличие седловой точки в данной матрице.

Для этого найдем нижнюю и верхнюю цену игры.

Минимальные элементы по строкам равны (2 и 3) тогда нижняя цена игры   = max (2; 3) = 3. Максимальные элементы по столбцам равны (4 и 6) тогда верхняя цена игры = min (4; 6) = 4. Отсюда видно, что    и мы имеем игру, которая имеет решение в смешанных стратегиях, а цена игры  .

Предположим, что для первого игрока смешанная стратегия задается вектором U = (u1; u2). Первый игрок, если придерживается своей оптимальной стратегии, независимо от стратегии второго игрока получает цену игры , т.е.

                       4u1* + 3u2* =                                     (1)

                       2u1* + 6u2* = .

 Кроме этого относительные частоты связаны условием:

                        u1* + u2* = 1.

Решаем полученную систему трех линейных уравнений с тремя неизвестными. Получим оптимальную стратегию первого игрока и цену игры:

U* = ( u1* ;  u2*) = (3/5; 2/5),   = 18/5.

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

                       4z1* + 2z2* = = 18/5                   (2)

                       3z1* + 6z2* = = 18/5.

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

Z* = ( z1* ;  z2*) = (4/5; 1/5).

Рассмотрим геометрическую интерпретацию этой задачи в смешанных стратегиях.  Для этого в плоскости  введем систему координат и на горизонтальной оси Ou отложим вероятность применения первым игроком его двух стратегий, сумма этих вероятностей равна 1, поэтому весь график расположится на отрезке единичной длины. В точках 0 стратегия (1; 0), а в 1 стратегия (0; 1).

                                          Рисунок 1.

По оси ординат в точке 0 отложим выигрыши первого игрока по первой его стратегии при обеих стратегиях второго, а в точке 1 при второй стратегии первого игрока.  Соединим эти платежи по столбцам, тогда пересечение прямых дадут решение системы уравнений (1), а ордината этой точки цену игры .

Анологично можно построить график для нахождения оптимальной стратегии второго игрока.

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


 

А также другие работы, которые могут Вас заинтересовать

83863. Резекция лёгкого. Хирургическая тактика при раке и доброкачественных опухолях лёгкого 50.4 KB
  Техника резекции лёгкого заднебоковой доступ; пневмолиз выделение из сращений; вскрытие медиастиналыюй плевры; обработка корня: последовательно вначале артерию затем вену и в конце бронх при раке вену артерию бронх; удаление легкого; проверка герметичности культи бронха физраствор в плевральную полость смотрят наличие пузырьков воздуха при раздувании; дренаж в плевральную полость; ушивание раны. Радикальные операции на легких выполняют при раке легкого туберкулезе легких бронхоэктатической болезни хронической пневмонии...
83864. Пункция перикарда и ушивание раны сердца. Техника выполнения 46.5 KB
  Пункция перикарда Показания: с диагностической или лечебной целями преимущественно при выпотных перикардитах. Ушивание раны сердца оперативный доступ обычно по ходу раневого канала; продольное вскрытие перикарда широким разрезом кпереди от диафрагмального нерва; наложение узловых или Побразных швов на рану; освобождение полости перикарда от сгустков крови; ушивание перикарда редкими швами.
83865. Коронарные артерии и проводящая система сердца. Принципы операций на коронарных артериях, шунтирование и стентирование 54.08 KB
  Коронарные артерии . interventriculris posterior – конечная ветвь правой коронарной артерии проходит в одноимённой борозде; r. interventriculris posterior конечная ветвь левой коронарной артерии проходит в одноимённой борозде.
83866. Хирургическая анатомия пищевода. Операции на пищеводе 66.98 KB
  Хирургическая анатомия пищевода Отделы: шейный грудной и брюшной. Синтопия: Спереди пищевода лежат перстневидный хрящ и трахея; сзади позвоночник и длинные мышцы шеи: по бокам нижние полюсы боковых долей щитовидной железы и общие сонные артерии. Правый возвратный нерв проходит позади трахеи по боковой поверхности пищевода.
83867. Строение брюшной стенки – классификация мышц живота, кровоснабжение, иннервация. Формирование влагалища прямой мышцы живота. Лапаротомия 53.51 KB
  Мышечные пучки идут в поперечном направлении. Линия перехода мышечной части поперечной мышцы живота в сухожильное растяжение называется полулунной линией (linea semilunaris) или спигелиевой линией. Самые нижние мышечные пучки внутренней косой мышцы живота и поперечной мышцы живота, сопровождая семенной канатик, образуют мышцу, поднимающую яичко...
83868. Грыжа: определение, составные части грыжи, классификация грыж. Принципы операций при грыжах передней брюшной стенки, основные этапы операции 45.85 KB
  Принципы операций при грыжах передней брюшной стенки основные этапы операции. Наружные грыжи: 1 паховая грыжа косая и прямая; 2 бедренная грыжа; 3 грыжа белой линии живота; 4 пупочная грыжа; 5 грыжа спигелиевой полулунной линии; 6 поясничная грыжа; 7 запирательная грыжа; 8 послеоперационная грыжа. Внутренние грыжи: 1 грыжа двенадцатиперстнотощего кармана; 2 грыжа сальниковой сумки; 3 ретроцекальная грыжа; 4 различные виды диафрагмальных грыж. По клиническим признакам: 1 вправимые; 2 невправимые; 3 ущемленные: ущемление...
83869. Строение пахового канала. Складки и ямки задней поверхности передней брюшной стенки. Треугольники паховой области. Косая и прямая паховая грыжа 98.4 KB
  Стенки: 1 верхняя нижние пучки внутренней косой мышцы живота и поперечной мышцы живота; 2 передняя апоневроз наружной косой мышцы живота; 3 нижняя паховая связка утолщенный и загнутый в виде желобка нижний край апоневроза наружной косой мышцы живота; 4 задняя поперечная фасция. Поверхностное паховое кольцо образовано расходящимися медиальными и латеральными ножками апоневроза наружной косой мышцы живота скрепленными межножковыми волокнами закругляющими щель между ножками в кольцо; Глубокое паховое кольцо образовано поперечной...
83870. Способы пластики пахового канала при прямых и косых паховых грыжах 50.78 KB
  Способы укрепления передней стенки пахового каналапри косых грыжах Способ Мартынова Впереди семенного канатика подшивается к паховой связке медиальный лоскут наружной косой мышцы живота а латеральный поверх медиального. Способ Жирара Впереди семенного канатика узловыми капроновыми швами подшивают свободные края внутренней косой и поперечной мышц живота к паховой связке. Затем к связке подшивают медиальный лоскут апоневроза наружной косой мышцы живота и латеральный лоскут укладывают поверх медиального и подшивают рядом узловых швов....
83871. Строение бедренного канала. Бедренная грыжа. Операции при бедренной грыже. «Corona mortis» - формирование, тактика при ранении аномального анастомоза 134.64 KB
  Отверстия бедренного канала: внутреннее отверстие соответствует бедренному кольцу. Стенки бедренного канала: передняя поверхностный листок собственной фасцнн бедра в этом месте он носит название верхнего рога серповидного края и паховая связка задняя глубокий листок собственной фасции бедра в этом месте он носит название гребенчатой фасции: латеральная бедренная вена. Операции при бедренной грыже Способы пластики бедренных грыж можно разделить на две группы: 1способы закрытия грыжевых ворот со стороны бедра; 2способы закрытия...