Тема 9. Теоретико-игровые модели принятия решений

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

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

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

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

- возможные варианты поведения сторон;

- объем информации о поведении противоборствующих сторон;

- результат конфликта (игры) в зависимости от действий (ходов) сторон.

При этом полагается, что интересы участников конфликта могут быть оценены количественно.

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

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

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

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

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

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

Наиболее простой является парная игра с нулевой суммой. Но с ее помощью хорошо описывается большинство конфликтных ситуаций.

Рассмотрим парную игру. Сторона А может выбрать m стратегий (i=1,2,...,m), а сторона В - n стратегией (j=1, 2,...,n ). Если сторона А выбрала определенную i - ю стратегию, а сторона В -j-ю стратегию, то выбор стратегий однозначно определяет исход игры - a, выигрыш (положительный или отрицательный) стороны А. Известные значения для любой пары стратегий составляют платежную матрицу игры или просто матрицу игры.

Строки матрицы соответствуют стратегиям игрока А, а столбцы - стратегиям игрока В. Элемент матрицы a_ij показывает выигрыш игрока А, если он избрал стратегию i, а игрок В- стратегию j.

Исходя из предположения о разумности противников, определим стратегии игроков.

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

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

a = max a_i,

ⁱ

или a=max min a_ij,

^{i j}

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

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

b=max a_ij .

ⁱ

Значения b пишутся внизу матрицы в виде дополнительной строки.

Игрок В выбирает такую стратегию В_j, при которой минимизируется значение b=min max a_ij.

^{j i}

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

Задача 8. Найти верхнюю и нижнюю цены игр, платежные матрицы которых приведены в таблицах.

Методические указания к решению

Определим минимумы строк a_i, и максимумы столбцов b_j (т.е. соответственно минимальные выигрыши игрока А и максимальные проигрыши игрока В). Для игры, матрица которой задана таблицей I, результаты приведены в таблице:

Максимальное значение a_i,.равное 4, дает нижнюю цену игры.

Верхняя цена игры (равная минимуму b_j) составляет 11.

Для второй игры получим таблицу:

В данном случае нижняя и верхняя цены игры равны 8, т.е. max a_i, = min b_j или max min a_ij = min max a_ij= g.

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

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

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

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

Однако на практике часто встречаются игры, у которых верхняя и нижняя цены не равны. Если в этом случае применять только одну чистую стратегию по принципу минимакса, то выигрыш игрока А не будет превышать a, а выигрыш игрока В - b.

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

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

Смешанная стратегия S_A игрока А определяется набором вероятностей р₁,р₂,…,р_m использования чистых стратегий А_i (i=1,2,…,m), причем =1.

Аналогично, для игрока В смешанная стратегия игрока S_В определяется набором вероятностей q₁,q₂,…,q_n использования чистых стратегий B_j (j=1,2,…n), и =1.

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

Пара оптимальных стратегий S^*_А и S^*_В обладает следующим свойством: если один игрок придерживается своей оптимальной стратегии, то другому не выгодно отклоняться от своей оптимальной.

Цена игры g при применении смешанных стратегий находится в пределах между верхней и нижней ценами игры: a£ g £ b

Применение игроком А своей оптимальной стратегии S^*_А при любой стратегии противника В_j обеспечивает ему выигрыш не менее g, т.е.

g (j=1,2,…,n). (9.1)

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

g (i=1,2,…,m). (9.2)

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

При определении оптимальной стратегии игрока А должны выполняться условия:

р₁а₁₁+р₂а₂₁+ …+р_iа_i1+….+р_mа_m1³g

р₁а₁₂+р₂а₂₂+ …+р_iа_i2+….+р_mа_m2³g

…………………………………….

р₁а_1j+р₂а_2j+ …+р_iа_ij+….+р_mа_mj³g

……………………………………

р₁а_1n+р₂а_2n+ …+р_iа_in+….+р_mа_mn³g

Цена игры g, если элементы платежной матрицы неотрицательны - всегда положительное число. Если в матрице есть отрицательные элементы, ее можно преобразовать, прибавляя ко всем элементам определенное положительное число.

Систему ограничений (3) можно преобразовать, разделив на g все члены неравенства и обозначив р_i/g=x_i.

В результате получим

а₁₁x₁+а₂₁x₂+ …+а_i1x_i+….+а_m1x_m³1

а₁₂x₁+а₂₂x₂+ …+а_i2x_i+….+а_m2x_m³1

…………………………………….

а_1jx₁+а_2jx₂+ …+а_ijx_i+….+а_mjx_m³1

……………………………………

а_1nx₁+а_2nx₂+ …+а_inx_i+….+а_mnx_m³1

Из условия =1 получим:

x₁+x₂+…+x_i+…+x_m=1/g (9.5)

Оптимальная стратегия S^*_А должна максимизировать значение g, а следовательно, минимизировать 1/g.

Таким образом, задача определения выбора вероятностей p_i составляющих оптимальную стратегию S^*_А, сводится к минимизации линейной формы (5) при ограничениях (4).

Решив полученную задачу линейного программирования и найдя величины x_i и 1/g, определим значения р_i=gx_i.

Оптимальная стратегия игрока В -S^*_В находится аналогичным образом, исходя из условия минимизации проигрыша (g), при соблюдении условий (9.2).

Разделив систему неравенств (2) на g и заменив q_i на y_i =q_i /g, получим следующую задачу линейного программирования:

а₁₁y₁+а₁₂y₂+ …+а_1jy_j+….+а_1ny_n£1

а₂₁y₁+а₂₂y₂+ …+а_2jy_j+….+а_2ny_n£1

…………………………………….

а_i1y₁+а_i2y₂+ …+а_ijy_j+….+а_jny_n £1

……………………………………

а_m1y₁+а_m2y₂+ …+а_mjy_j+….+а_mny_n£1

y₁+y₂+…+y_j+…+y_n®max

Задача максимизации линейной формы при ограничениях (9.6) является двойственной по отношению к задаче, определяемой условиями (9.4) и (9.5).

Таким образом, задача отыскания решения матричной игры сводится к решению пары симметричных двойственных задач линейного программирования. Решение прямой задачи дает оптимальную стратегию игрока A (S^*_А), а двойственной - оптимальную стратегию игрока В (S^*_В).

Задача 9.1. Найти оптимальные стратегии игроков А и В, т.е. решение игры, платежная матрица которой представлена первой таблицей задачи 8.

Методические указания к решению

Найдем смешанную стратегию игрока А.

Обозначив x₁= p₁/g, x₂= p₂/g, x₃= p₃/g, получим следующую модель задачи:

L=x₁+x₂+x₃ ® min,

9x₁+4x₂+11x₃£1

4x₁+11x₂+2x₃£1

11x₁+2x₂+13x₃£1

x_i ³ 0

Решая эту задачу симплекс-методом, получим:

x₁= 1/28, x₂=1/14, x₃ = 1/28.

Цена игры g=1/L_min , g= 1/(1/28+1/14+1/28)=7.

Соответственно, вероятности использования игроком А первой, второй и третьей стратегий составят:

р₁=gx₁= 7*1/28=1/4

р₂=gx₂= 7*1/14=1/2

р₃=gx₃= 7*1/28=1/4,

т.е.

S^*_А =(1/4,1/2,1/4).

Оптимальная стратегия игрока В (S^*_В) находится аналогичным образом, только ограничения типа (£) составляются по строкам, а критерий оптимальности следует не минимизировать, а максимизировать. Составив модель и решив ее, получим, что оптимальная стратегия игрока В состоит в следующем:

q₁=1/4

q₂=1/2

q₃=1/4,

т.е.

S^*_B =(1/4,1/2,1/4).

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

Задание. Найти оптимальные стратегии игроков А и В, т.е. решение игры, платежная матрица которой представлена таблицей: