Матричные игры (игровые методы)
занимательные факты по информатике и икт (11 класс) по теме

Игровые методы

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

Подобные явления и ситуации называются конфликтными или просто конфликтами.

Типичный конфликт характеризуется тремя основными составляющими:

1. Заинтересованными сторонами;
2. Возможными действиями этих сторон;
3. Интересами сторон.

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

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

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

• Игроки – заинтересованные стороны;
• Стратегия – любое возможное для игрока действие;
• Ситуация – набор стратегий;
• Выигрыш – число, выражающее степень удовлетворения интересов игрока в определенной ситуации;

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

• К выработке принципов оптимальности, т.е. того критерия, по которому поведение игроков следует считать оптимальным (разумным, целесообразным);
• К выяснению реализуемости этих принципов, т.е. установлению существования оптимальных в выработанном смысле ситуаций, и отысканию этих реализаций.

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

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

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

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

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

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

Для того чтобы отличать прежние стратегии от новых, первые называют чистыми, а вторые – смешанными стратегиями.

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

Таким образом, преобразованная игра обычно называется смешанным расширением исходной игры.

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

Исследование матричных игр интересно еще и потому, что к ним могут быть приближенно сведены многие игры наиболее общего вида.

Матричные игры

МАТРИЧНЫЕ ИГРЫ - игры, в которых  участвуют два игрока (I и II) с противоположными интересами, причём каждый игрок имеет конечное число чистых стратегий. Если игрок I имеет т стратегий, а игрок II -п стратегий, то игра может быть задана (m x n)-матрицей А = || aij ||, где aij есть выигрыш игрока I, если он выберет стратегию i (z = 1, ...,т), а игрок II -стратегию j (j = 1, ..., га). Следуя общим принципам поведения в антагонистических играх,

игрок I стремится выбрать такую стратегию i0, на которой  достигается

игрок II стремится выбрать стратегию j0, на которой достигается 

Если Vi = V2, то пара (i0, j0) составляет седловую точку игры, Т: е. выполняется двойное неравенство aij0< ai0j0<ai0j i=1,...,m; j=1,...,n Число ai0j0 наз. значением игры; стратегии i0, j0 наз. оптимальными чистыми стратегиями игроков I и II соответственно. Если v1 не равно v2, то всегда v1 2 в этом случае в игре седловой точки нет, а оптимальные стратегии игроков следует искать среди их смешанных стратегий (т. е. вероятностных распределений на множестве чистых стратегий). В этом случае игроки оперируют уже с математическими  ожиданиями выигрышей.

Основная теорема теории матричных игр  утверждает, что в любой М. и. существуют оптимальные смешанные стратегии х*, у*, на которых достигаемые «минимаксы» равны (общее их значение есть значение игры). Напр., игра с матрицей  имеет седловую точку при i0 =2 2, j0 = 1, а значение игры равно 2: игра с матрицей  не имеет седловой точки. Для нее оптимальные смешанные стратегии суть х*= (3/4, 1/4), у* = (1/2, 1/2); значение игры равно 1/2.

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

Методы решения матричных игр

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

Для построения решений 2 х n- и m х 2 игр существует эффективный метод, основанный на простых геометрических соображениях.

Этот метод называют графическим.

1. 2 х n-игры

Пусть дана матрица  - платежная матрица 2 х n-игры

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

v = ( p+ (1 - p)) = ( p + (1 - p))

опишем общую схему, приводящую к искомому результату.

Максимум функции

        ( p + (1 - p))        (1)

проще всего найти, построив график.

Предположим, что игрок А выбрал смешанную стратегию Р = , а игрок В – k –ую чистую стратегию, k = 1,2,….., n. Тогда средний выигрыш игрока А в ситуации  оказывается равным

(k) : w = p +

На плоскости (p,w) уравнение (k) описывает прямую. Тем самым каждой чистой стратегии игрока В на этой плоскости соответствует своя прямая.

Для того, чтобы выяснить расположение этой прямой, на плоскости (p,w) последовательно и аккуратно прорисуем все прямые

(k) : w =  p + ,                 k = 1,2,…n.   (рис.1)

Затем, для каждого значения  p, 0p1, путем визуального сравнения соответствующих ему значений w на каждой из построенных прямых определяется и отмечается наименьшее из них. (рис.2)

В результате описанной процедуры получается ломаная, которая и является графиком функции (1) (жирная линия на рис.3)

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

Верхняя точка построенной нижней огибающей

определяет и цену игры – v,

 и оптимальную стратегию игрока А -  1 -  

(рис.4)

Для того, чтобы понять и отработать описанную схему решения 2 х n-игры, рассмотрим пример задачи.

Задача: пусть игра задана 2 х 6 - матрицей

Решение

Будем решать по алгоритму (каждый шаг прописывается отдельно)

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

Нижняя цена игры равна -1, верхняя равна 1. Седловой точки нет. Значит, решение игры следует искать в смешанных стратегиях

2. Вычисление средних выигрышей игрока А

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

Рассмотрим таблицу

Из данной таблицы получаем следующие соотношения

(1): w = 6p – 2 (1 - p)

                                                 (2): w = 4p –    (1 – p)

(3): w = 3p +   (1 - p)

                                                 (4): w = p

  (5): w = – p + 5 (1 - p)

   (6): w =           4 (1 - p)

3. Построение нижней огибающей

Выберем в качестве координатной плоскости

Плоскость  (p,w).

Построим на ней все шесть прямых,

уравнения которых получены на 2-ом шаге алгоритма  

и находим нижнюю огибающую. (рис.5)

4. Отыскание цены игры и оптимальной смешанной стратегии игрока А

Для начала необходимо определить, где будет лежать наивысшая точка нижней огибающей. Она будет находиться на пересечении двух из шести прямых. В данном случае это прямые (4) и (5), заданные соответственно уравнениями w = p и w = – p + 5 (1 - p).

Решая систему уравнений

        w = p

        w = – p + 5 (1 - p),

получаем следующие значения    (рис.6)    

Тем самым,  цена игры  v и оптимальная стратегия P игрока А соответственно равны:

v =   ,

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

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

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

Попробуем рассмотреть, как отыскать оптимальную смешанную стратегию игрока В.

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

А. Нижняя огибающая имеет ровно одну наивысшую точку

1. Если  (оптимальная стратегия игрока А – чистая стратегия ), то игроку В выгодно применить чистую стратегию, соответствующую прямой, проходящей через точку (0, ) и имеющей наибольший отрицательный наклон (рис.7)

2. Если  (оптимальная стратегия игрока А – чистая стратегия ), то оптимальной для игрока В является чистая стратегия, соответствующая прямой, проходящей через точку (1, )  и имеющей наименьший положительный наклон (рис.8)
3. Если 0 <  < 1, то в наивысшей точке

    нижней огибающей пересекаются по

    меньшей мере

         две прямые, одна из которых

         (k-я) имеет  положительный наклон,

         а другая (l-я) – отрицательный

    (рис.9)

Оптимальная смешанная стратегия игрока В получается, если положить

,   ,   , jk,l,    

где q – решение уравнения

Б. Нижняя огибающая содержит горизонтальный участок, соответствующий чистой стратегии  игрока В, которая является оптимальной для него. (рис.10)

Найдем  полное решение игры , то есть еще и оптимальную смешанную стратегию игрока В.

Алгоритм решения:

1. Предполагается, что

, , , , ,

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

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

к цене игры:

q – (1 – q ) =      ,        5 (1 – q ) =

3. Получается (в обоих случаях), что .

Полное решение задачи имеет вид

     ,    v =

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

2 х  n.

2. m x 2-игры

Предположим, что в матричной игре две чистые стратегии имеет игрок , а число чистых стратегий игрока А произвольно (равно m).

Тогда платежная матрица будет иметь следующий вид  .

Пусть Q = {q, 1-q} – произвольная смешанная стратегия игрока В. Если игрок А выбирает i-ю чистую стратегию, i = 1,2,….,m, то средний выигрыш игрока В в ситуации {i, Q} будет равным

(i) : w = , i = 1,2,…m.                                     (2)

Зависимость этого выигрыша от переменной q описывается прямой.

Графиком функции

является верхняя  огибающая семейства прямых (2),

соответствующих стратегиям игрока А . (рис.11)

Абсциссой  нижней точки полученной ломаной

будет значение q, определяющее

оптимальную смешанную стратегию игрока В,

а ординатой w  - цена игры.

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

Задача: 3 х 2-игра задана матрицей  .

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

Решение

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

нижняя цена игры равна 0, верхняя – равна 3. Седловой точки нет. Решение игры нужно искать в смешанных стратегиях.

2. Вычисление средних выигрышей игрока В (проводится при условии, что игрок А выбирает только чистые стратегии)

Рассмотрим таблицу

Получаем уравнения

(1): w = 3q – (1 – q )

(2): w = -q+3(1 – q )

                                               (3): w = q

3. Построение верхней огибающей

Построим на координатной плоскости (q,w) все три прямые, а затем их верхнюю огибающую. (рис.12)

4. Отыскание цены игры и оптимальной смешанной стратегии игрока В

Нижняя точка верхней огибающей является точкой пересечения прямых (1) и (2). Решая систему уравнений

w = 3q – (1 – q )

w = - q +3(1 – q )

получаем q = , w = 1

5. Отыскание оптимальной смешанной стратегии игрока А

Полагая

    ,

приравниваем средние выигрыши игрока А, соответствующие чистым стратегиям игрока В:

3p – (1 – p ) = - p +3(1 – p ),

находим = .

Таким образом, цена игры и оптимальные смешанные стратегии игроков А и В соответственно равны:

v = 1, P, Q

3. m x n-игры.

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

Правило доминирования.

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

Сравнение строк и столбцов матрицы

Пусть i-я строка матрицы А  

a a …a

не больше j-й строки матрицы

a a… a,

если одновременно выполнены следующие n неравенств:

a a, a a, …, a a

При  этом  j-я строка доминирует i-ю строку или что стратегия А игрока А доминирует стратегию А.

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

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

Тогда k-ый столбец матрицы А

a

a

.

.

a

не меньше l-го столбца этой матрицы

a

a

.

.

a

если одновременно выполнены следующие из m-неравенств

a a, a a, …, a a.

При этом l-й столбец доминирует k-й столбец или что стратегия В игрока В доминирует стратегию В.

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

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

Задача:

Игра задана платежной матрицей

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

           y

         11

                                                                                                            7

                                           М                                   N                        5 x

           3

           2                                                                                            2

В точках А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х определяет средний выигрыш  1  при любом сочетании стратегий А1 А2 (с частотами  х и  1–х) и стратегией  В1 игрока 2. Это расстояние равно

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

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

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

.

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

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

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