Тема: Теория игр и принятия решений.

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

Игра – это совокупность правил, определяющих сущность конфликтной ситуации, которые устанавливают:

· Выбор способа действия игроками на каждом этапе игры

· Информацию, которой обладает каждый игрок при выполнении таких выборов

· Плату для каждого игрока после завершения любого этапа игры

Основными понятиями теории игр являются:

· Конфликтующие стороны, называемые игроками

· Одна реализация игры партией и набор её возможных конечных состояний

· Исход игры – выигрыш, ничья или проигрыш

Игрокам известны платежи в виде матрицы . Развитие игры во времени происходит последовательно по этапам (ходам).

Ходом в теории игр называется выбор одного из правил, предусмотренных игрой и его реализации.

Ходы бывают личными и случайными.

Личный ход – сознательный выбор игроком одного из вариантов действия и его осуществление.

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

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

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

В зависимости от причин, вызывающих неопределённость исходов игры их делят на основные группы:

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

2) Азартные игры – это игры, источником неопределённости которых является случайные факторы. При их анализе применяется теория вероятностей.

3) Стратегические игры – это игры, в которых неопределённость исхода вызвана тем, что каждый из игроков, принимая решение о выборе предстоящего хода, не знает какой стратегии будут придерживаться другие участники игры. Такие игры и изучает теория игр.

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

Также игры различают по сумме выигрыша:

1. С нулевой суммой (один игрок выигрывает за счёт другого, а сумма выигрыша одного равна сумме проигрыша другого)

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

В зависимости от количества возможных стратегий:

· Конечные – если у каждого игрока имеется только конечное число стратегий.

· Бесконечные – если хотя бы у одного игрока имеется бесконечное число стратегий.

Постановка игровых задач.

Основными вопросами теории игр являются:

1. Какие свойства стратегий следует считать признаками оптимальности.

2. Существуют ли стратегии игроков, которые обладали бы свойствами оптимальности.

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

Пример

Рассмотрим игру двух лиц с нулевой суммой. Пусть игра состоит из двух ходов. Игрок 1 выбирает стратегию , игрок 2 – стратегию ; выигрыш соответственно  и .

Игра каждого из игроков удовлетворяет условиям:

=0. Если

Пусть функция .

Составим матрицу А:

 

Строки матрицы А соответствуют стратегии , столбцы- стратегии . Матрица А называется платёжной или матрицей игры.

Элемент платёжной матрицы А является выигрышем игрока 1, если он выбрал стратегию , а второй игрок выбрал стратегию . Эти стратегии называются чистыми стратегиями игроков.

Пусть игрок 1 выбирает некую стратегию (игроку 2 известен выбор), тогда в худшем случае он получит выигрыш, равный минимуму , то есть минимальному элементу в i-ой строке платежной матрицы А.

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

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

Величина β называется верхней ценой игры, а стратегия  – минимаксной.

Пусть выигрыш игрока 1 будет V, тогда его значение ограничено верхней и нижней ценами игры:

 

Если же совпадают, то выигрыш игрока 1 составляет определённую величину, игра называется вполне определённой.

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

Элемент в платёжной матрице А является одновременно минимальным в строке и максимальным в столбце и называется седловой точкой.

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

Игра в смешанных стратегиях

Если платежная матрица не имеет седловой точки, то цена игры V определяется условием (1) §2, т.е. первый игрок обеспечит выигрыш не меньше α, а второй игрок обеспечит проигрыш не больше β. Так как α<β, то первый игрок стремится увеличить выигрыш, а второй – уменьшить проигрыш.

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

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

Теорема 2. (Дж. фон Неймана. Основная теорема теории игр) Каждая конечная матричная игра имеет, по крайней мере, оптимальное решение в смешанных стратегиях.

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

Смешанные стратегии для соответствующих игроков 1 и 2 будут  и :

                                       (3)

 

                                         (4)

где  и  – чистые стратегии игроков

                   (5)

 

Вероятности применения соответствующих стратегий игроками 1 и 2

                     (6)

 

Зная платежную матрицу A можно определить средний выигрыш (математическое ожидание):

M(A,X,Y)=                                         (7)

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

Рассмотрим конечную игру, матрица которой имеет размер 2х2

                                             (8)

Определить оптимальные стратегии первого и второго игроков и соответствующие им вероятности для матрицы (8), т.е.

                                    (9)

Для игрока 1 получаем систему уравнений:

                                               (10)

 

Для игрока 2 система имеет вид:

                                                (11)

Если V≠0 и игроки имеют только оптимальные смешанные стратегии, то определитель матрицы A не равен нулю. Следовательно системы (10) и (11) имеют единственные решения.

Решая системы уравнений (10) и (11) находим вероятности X и Y в следующем виде:

                           (12)

 

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

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

Первому игроку не выгодно применять стратегии, которым соответствуют доминируемые строки, а игроку 2 не выгодно применять стратегии, которым соответствуют доминирующие столбцы.

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

Теорема 3. Если x ’, y ’, v ’ являются решением платежной матрицы A, то решением игры с платежной матрицей  является тройка чисел x ’; y ’; kv ’+ b; k ≥0, где b – любое действительное число.

Элементы теории графов

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

Задача Эйлера заключается в том, чтобы пройти по семи мостам только один раз и вернуться в исходную часть города. Само название граф предполагает графическую интерпретацию изучаемого явления. Графом G=(X;U) называется совокупность двух множеств непустого множества X вершин и множеств U ребер, т.е.:

G=(X;U)= ,X≠0         U= , k=

Обычно граф изображают диаграммой, вершины – точками либо кружочками, а ребра – линиями. Если ребра графа ориентированы, т.е. показаны стрелкой от вершины к вершине, то они называются дугами, а такой граф называется ориентированным или орграфом (рис1). Если ребра не имеют ориентации, то граф называется неориентированным или неографом (рис.2).

                   

Рис.1                                                             Рис.2

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

Другим обозначением орграфа является задание множества вершин Х и соответствия Г(. Соответствие Г показывает, как между собой связаны вершины и называются отображением множества ХвХ, а граф обозначается G=(ХГ).

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

Г =

Г() = (

Г(  = ø

Г() =

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

Например:

Г()=()

Так как Г() представляет множество вершин , для которых G существует дуга (), то через () обозначает множество вершин , для которых в графе существует дуга () и её называют обратным соответствием.

Например: для орграфа G(рисунок 3)

Если отображение Г() распространяется не на одну вершину, а множество вершин , а под множеством Г() понимают объединение Г()U Г()U… U Г() для орграфа (рисунок 3) оно будет выглядеть так:

Г({ })= { }, Г({ })={ }

Отображение Г(Г())→ (), а тройное отображение Г(Г(Г()))→ () и так далее.

Для нашего орграфа (рисунок 3)

()= Г(Г())= Г({ }={ }

() Г( ())=Г({ })={ }

С каждой вершиной графа связано два множества:

()- это множество тех, смежных  – вершин, в которых заходят в дуги из .

()- это множество таких вершин смежных , из которых выходят дуги, заканчивающиеся .

Вершины и называются смежными если существует дуга(ребро) U(), соединяющая их.

Например (), (), (), вершины () нашего (рисунок 1)орграфа, не являются смежными.

Если вершины  и  являются концами дуги, то говорят, что эти вершины инцидентны дуге U или дуга U инцидентна вершинам и .

Степенью или валентностью вершины графа называется количество инцидентных ей дуг и обозначается d()= Г().

В нашем примере орграфа (рисунок 1) d()= 4, d()=2.

Вершина, степень которой равна нулю называется изолированной.

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

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

Например, для нашего рисунка 1

()=3, ()=1, ()=1, ()=2

Теорема Эйлера

Сумма степеней вершин графа ровна удвоенному количеству дуг или рёбер

Где n- число вершин графа,

 m –число дуг.

Следствие №1

Число вершин нечётной степени всегда чётное.

Следствие №2

Сумма полу степеней вершин орграфа равна удвоенному числу дуг

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

=

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

Маршрут – это неориентированный «двойник» пути. Это понятие рассматривается в тех случаях, когда можно пренебречь направленностью в орграфе.

Маршрут – это последовательность рёбер  , , …,  , в котором каждое ребро , за исключением первого и последнего ребра связано с ребрами   и  своими двумя концевыми вершинами.

Последовательность дуг в орграфе (рисунок 1)

Являются маршрутными.

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

Маршруты бывают:

· простые и цепи (ребро в таком маршруте используется только один раз)

· элементарный (простые цепи)- в котором вершины встречаются только один раз.

Маршрут -простой, -цепь, - ни цепь и ни простой

Петлёй называется дуга графа, у которой начальной и конечной точки вершины совпадают (рисунок 1,  ).

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

Замкнутые пути орграфа называются контурами.

Замкнутые маршруты (цепи) в неографах называются циклами.