Теория игр

игра, G¢ = (Х,Y y¢,А) – подыгра игры G, а y¢ – чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией Теория игр, спектр которой не содержит y¢.Тогда всякое решение игры G¢ является решением G.

Свойство 5. Если для чистой стратегии х¢ игрока 1 выполнены условия свойства 3, а для чистой стратегии y¢ игрока 2 выполнены условия свойства 4, то всякое решение игры G¢ = (Х х¢,Y y¢,А) является решением игры G = (Х,Y,А).

Свойство 6. Тройка (хо, yо, u) является решением игры G = (Х,Y,А) тогда и только тогда, когда (хо, yо, кu +а) является решением игры G(Х,Y,кА+а), где а – любое вещественное число, к > 0.

Свойство 7. Для того, чтобы хо = (Теория игр) была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры u, необходимо и достаточно выполнение следующих неравенств

Теория игр     (j = Теория игр)            Теория игр

Аналогично для игрока 2 : чтобы yо = (Теория игр, ...,Теория игр, ...,Теория игр) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:

Теория игр     (i = Теория игр)            Теория игр

Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (х, y) и u решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими уравнениями

Теория игр, Теория игр                 Теория игр

получим решение матричной игры.

Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений (***). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 3Теория игр3 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

Теория игрТеория игрТеория игр = Теория игрТеория игрТеория игр.

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

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

Пример 3. Пусть G = (Х,Y,А), где Х = {1, 2, 3, 4}; Y = {1, 2, 3, 4}, а функция выигрыша А задана следующим образом :

Теория игр

где С > 0.

Решение. Прежде всего заметим, что по свойству 6 достаточно решить игру G1 = (Х,Y,А), где А1 =Теория игрА . В матричной форме игра G1 определяется матрицей выигрышей

Теория игр

Элементы четвёртой строки этой матрицы “ £ ” соответствующих элементов третьей строки и поэтому третья стратегия игрока 1 доминирует над четвёртой. Кроме того, элементы первого столбца матрицы А1 “ ³ ” соответствующих элементов второго столбца, Следовательно, вторая стратегия игрока 2 доминирует над его первой стратегией.

Далее, из свойства 5 следует, что всякое решение игры G2 = (Х {4}, Y {1}, А1) является решением игры G1. В матричной форме игру G2 можно представить матрицей

Теория игр.

Очевидно, что элементы второй строки “ ³” полусуммы соответствующих элементов первой и третьей строк. Кроме того, элементы третьего столбца матрицы А2 “ ³“ соответствующих элементов второго столбца. Применяя свойство 5 получим, что всякое решение игры G3 = (Х {4,2}, Y {1,4}, А2) является решением игры G2, а следовательно и игры G1. Игра G3 определяется матрицей

Теория игр.

Матрица А3 не имеет седловой точки, т.к. не выполнено равенство

Теория игрТеория игрТеория игр = Теория игрТеория игрТеория игр,

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

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

Теория игр,

либо

Теория игр.

Аналогично, если игрок 2 использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно Теория игр. Следовательно, указанные стратегии являются оптимальными в игре G3, а величины Теория игр – значением игры G3. Из предыдущего следует, что эти стратегии оптимальны и в G1.

Таким образом, стратегия Х = (Теория игр, 0,Теория игр, 0) является оптимальной стратегией игрока 1, стратегия Y = (0,Теория игр,Теория игр, 0) – оптимальной стратегией игрока 2 в игре G1, а значение игры G1 равно Теория игр. В силу свойства 4 решением игры G будет тройка (Х,Y,Теория игр).

Игры порядка 2 х 2.

В общем случае игра 2Теория игр2 определяется матрицей

Теория игр

Прежде всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например 1) имеет чистую оптимальную стратегию, а другой – только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Далее, по свойству 1 следует, что а11 = а12 = u и матрица имеет вид

Теория игр.

Легко видеть, что для матриц такого вида одна из стратегий игрока 2 является доминируемой. Следовательно, по свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению.

Пусть Х = (x, 1 - x) – оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см. также свойство 7)

Теория игр

Отсюда следует, что при u ¹ 0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица А принимает вид

Теория игр

и игрок 1 имеет чистую оптимальную стратегию (он выбирает с вероятностью 1 ту из строк, элементы которой не меньше соответствующих элементов другой), что противоречит предположению. Следовательно, если u ¹ 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы А отличен от нуля. Из этого следует, что последняя система уравнений имеет единственное решение. Решая её, находим

Теория игр;

Теория игр.

Аналогичные рассуждения приводят нас к тому, что оптимальная стратегия игрока 2 Y = (h, 1 - h) удовлетворяет системе уравнений

Теория игр

откуда

Теория игр.

Графический метод решения игр 2 х n И m х 2.

Поясним метод на примерах.

Пример 1.

Рассмотрим игру, заданную платёжной матрицей.

Теория игр

На плоскости хОy введём систему координат и на оси Ох отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (х, 1 - х). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) – стратегия А2 и т.д.

      y

     11

                                                      7

                      М                  N            5

                    

      3

      2                                 u              2

Теория игр       Теория игр               x

В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0х соответствуют точки В1, В2 и В3.

Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки В¢1, В2¢, В3¢ на перпендикуляре, восстановленном в точке А2.Соединяя между собой точки В1 и В¢1, В2 и В¢2, В3 и В¢3 получим три прямые, расстояние до которых от оси 0х определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка В1В¢1 до оси 0х определяет средний выигрыш u1 при любом сочетании стратегий А1 А2 (с частотами х и 1–х) и стратегией В1 игрока 2. Это расстояние равно

2х1 + 6(1 - х2) = u1

(Вспомните планиметрию и рассмотрите трапецию А1 B1 B¢1 A2). Таким образом, ординаты точек, принадлежащих ломанной В1 M N В¢3 определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N; следовательно этой точке соответствует оптимальная стратегия Х* = (х, 1-х), а её ордината равна цене игры u. Координаты точки N находим как точку пересечения прямых В2 B¢2 и В3 B¢3.

Соответствующие два уравнения имеют вид

Теория игр.

Следовательно Х = (Теория игр; Теория игр), при цене игры u = Теория игр. Таким образом мы можем найти оптимальную стратегию при помощи матрицы

Теория игр

Оптимальные стратегии для игрока 2 можно найти из системы

Теория игр

и, следовательно, Y = (0; Теория игр; Теория игр). (Из рисунка видно, что стратегия B1 не войдёт в оптимальную стратегию.

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

Теория игрТеория игр

A¢4

        x                                                      8

A¢3

                                                              7

A1 A¢2

        6                                К                     6

 

A¢1
                                                              5

A2

        4

A3
                                        u

        2

A4
        1

B2
B1
          Теория игр          y

Решение. Матрица имеет размерность 2 х 4. Строим прямые, соответствующие стратегиям игрока 1. Ломанная А1 K А¢4 соответствует верхней границе выигрыша игрока 1, а отрезок N K –цене игры. Решение игры таково

U = (Теория игр; Теория игр);   Х = (Теория игр; 0; 0; Теория игр);   u = Теория игр.

Сведение матричной игры к задаче линейного программирования

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

Итак, пусть дана матричная игра с матрицей А порядка m х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1, ..., хm), y = (y1, ..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.

Теория игр                       Теория игр

Теория игр                       Теория игр

Разделим все уравнения и неравенства в (1) и (2) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения :

Теория игр   Теория игр,   Теория игр   Теория игр,

Тогда (1) и (2) перепишется в виде :

Теория игр,   Теория игр,  

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: