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

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

Формализованная модель конфликта в теории игр называется игрой. Игра ведётся по определённым правилам, которые чётко определяют права и обязанности сторон, участвующих в игре, а также исход игры – выигрыш или проигрыш. Конфликтующие стороны называются игроками. Одна реализация игры называется партией. Выбор игроком того или иного действия называется ходом. Ходы бывают личные (игрок сознательно принимает то или иное решение) и случайные (исход игры не зависит от воли игрока). Набор правил, которые определяют, какой ход игроку необходимо сделать, называется стратегией. Стратегии бывают чистыми (неслучайные решения игроков) и смешанными (стратегию можно рассматривать как случайную величину).

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

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

 

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

1.      В зависимости от количества игроков выделяют парные и множественные игры.

2.      В зависимости от количества стратегий выделяют конечные и бесконечные игры.

3.      В зависимости от вида ходов выделяют стратегические игры (все ходы личные) и азартные (все ходы случайные).

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

Для примера рассмотрим конечную игру двух игроков А и В, в которой игрок А может применить одну из стратегий

а игрок В – одну из  стратегий

---

Будем предполагать везде далее, что игрок А выигрывает, а игрок B проигрывает

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

Эту матрицу будем называть платёжной матрицей. Величина

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

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

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

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

---

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

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

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

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

 

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

 

При этом, по свойствам вероятности случайного события, необходимо учитывать, что

и

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

---

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

Эта функция называется платёжной функцией игры с платёжной матрицей 

Пусть   − оптимальные смешанные стратегии игроков А и В соответственно. Справедливы неравенства:

 

 

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

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

Точное задание элементов платежной матрицы матричной игры, как правило, затруднено из-за недостаточности, неточности исходной информации или неточности модели исследуемой системы, что особенно характерно для экономических систем. В этом случае, предлагается задавать элементы платежной матрицы в виде нечётких чисел a_ij , i=1…n, j=1…m, где n – число чистых стратегий игрока 1; m- число чистых стратегий игрока 2. Нечёткие числа полностью описываются своими функциями принадлежности _ij (x), которые определяются или экспертным опросом или на основе нечёткой модели исследуемой системы. Таким образом, возникает нечёткая матричная игра. В данной статье предлагается методика решения таких игр и анализа чувствительности и стабильности полученного решения.

---

Решение любой матричной игры (n  m) может быть сведено к решению пары двойственных задач линейного программирования. Однако в случае нечёткой матричной игры возникает проблема в использовании для решения этих задач симплекс-метода, связанная с делением на нечёткие числа, носитель которых содержит нуль. Эта операция над нечёткими числами неопределена 1. Для избежания этой проблемы предлагается решать нечёткие матричные игры итерационным методом Брауна-Робинсона, для которого не требуется деления на нечёткие числа , а осуществляются лишь операции сложения и сравнения нечётких чисел.

Все арифметические операции осуществляются просто, если нечёткие числа задавать трапецеидальными функциями принадлежности (боковые ветви (х) описываются линейной функцией). Как показано в работах Василевича, задание боковых ветвей (х) другим образом практически не изменяет решения, но усложняет выполнение арифметических операций. При использовании трапецеидальных функций любое нормальное нечёткое число задаётся четырьмя параметрами (а₁,в₁,в₂,а₂) , где а₁ и а₂ – определяют нижнюю и верхнюю границы носителя n нечёткого числа, а в₁ и в₂ - соответственно границы ядра r.

В этом случае нормальное нечёткое число А , равное сумме двух нормальных чисел с параметрами (а₁,в₁,в₂,а₂) и (с₁,б₁,б₂,с₂) будет определяться в соответствии с принципом обобщения Заде параметрами (а1+с1,в1+б1,в2+б2,а2+с2).

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

H_A =  A_{ +} + (1-) А_{ ,} (1)

где A_{ +} - max A_ ; A_ - min A_ ; A_ - срез нечёткого числа А на уровне  ;   0 , 1 и отражает степень рискованности лица принимающего решение (обычно берут = 0,5). Аналогично вычисляется H_В. Далее процедура сравнения сводится к определению отношения H_A\ H_В. Если H_A  H_В, то в соответствии с данным индексом ранжирования считается, что А В, а величина отношения определяет степень их отличия. Можно использовать и другие индексы ранжирования.

В результате решения конечной матричной игры методом Брауна- Робинсон будут получены чёткие квазиоптимальные , в общем случае, смешанные стратегии игроков S_A = \p₁,p₂,…,p_n\ и S_B = \g₁,g₂,…,g_n\ и нечёткая цена игры

---

Смотрите также файлы

• Нечеткая байесова сеть.doc

• Н.Бердяев. Воля к жизни и воля к культуре.doc

• МЭИ(ТУ) Физика.pdf

• МПЭис.doc

• МП.Введение в курс ОИ.Last.doc