Курсовая работа (т): Изучение игровых моделей и их применение в практике принятия решений

                                (2.1.2)

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

Если игрок B выберет стратегию B_j, то все возможные выигрыши игрока A будут элементами j - го столбца платежной матрицы С. В наихудшем для игрока B случае, когда игрок A применяет стратегию, соответствующую максимальному элементу этого столбца, выигрыш игрока B будет равен числу. Следовательно, игроку B нужно выбрать такую стратегию, для которой число минимально. Такая стратегия называется минимаксной. Если игрок В применяет минимаксную стратегию, то игрок А не может выиграть больше, чем число β, которое называется верхней ценой игры и рассчитывается по формуле:

                              (2.1.3)

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

         (2.1.4)

Такая игра называется игрой с седловой точкой. Для игры с седловой точкой общее значение нижней и верхней цены игры v называется ценой игры.

Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии А_i* и В_j*, образующие седловую точку, называются оптимальными. Элемент платежной матрицы c_i*j*, который соответствует минимаксным стратегиям A_i* и B_j, является одновременно минимальным в своей строке и максимальным в своем столбце и называется седловой точкой. Следовательно, выполняется равенство v= c_i*j*. Тройка (i*, j*, v) считается решением матричной игры с седловой точкой.

Если возникает ситуация, когда нижняя цена игры отличается от верхней цены игры, то игра является игрой без седловой точки. Для любой игры без седловой точки выполнено неравенство α < β.

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

Действительно, в игре без седловой точки элемент платежной матрицы c_i*j*, соответствующий минимаксной стратегии игрока A, не обязан быть минимальным в своей строке. Следовательно, игрок B, зная о том, что игрок A в следующей игре будет использовать минимаксную стратегию A_i*, может выбрать стратегию, отвечающую минимальному элементу строки i*. В результате выигрыш игрока A уменьшится от величины c_i*j* до величины α.

Аналогично может поступить и игрок A, неожиданно применив против игрока B стратегию, соответствующую максимальному элементу столбца j*.

Более того, доказано, что при многократно повторяемой игре без седловой точки игроку A, для обеспечения среднего выигрыша, большего, чем α, следует чередовать свои стратегии A₁, A₂, …, A_m. Игроку B для улучшения результата также целесообразно чередовать свои стратегии B₁, B₂, …, B_n.        В играх, которые повторяются многократно, каждая из стратегий A₁, A₂, …, A_m называется чистой стратегией. Стратегия игрока А, состоящая в том, чтобы применять чистые стратегии A₁, A₂, …, A_m, чередуя их по случайному закону с частотами p₁, …, p_m , называется смешанной стратегией p_I=(p₁,p₂,…p_m). Платежная функция при этом определяется как математическое ожидание выигрыша первого игрока при применении игроками смешанных стратегий p и q и равна:

 (2.1.5)

Сумма частот p₁, …, p_m должна быть равна единице. Чистые и смешанные стратегии игрока B определяются аналогично. Стратегии S_A и S_B называются оптимальными, если

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

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

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

.        Любая игра имеет цену.

. Цена игры удовлетворяет неравенству α ≤v ≤ β .

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

При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы:

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

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

.        Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение.

Рассмотрим аналитический метод решения игры типа 2 x 2. Необходимо найти решение для игры без седловой точки типа 2 x 2 с платежной матрицей , то есть найти оптимальную стратегию p_I=(p₁,p₂,…p_m) игрока А. Оптимальная стратегия обеспечивает игроку A выигрыш, равный цене игры v, даже если игрок B не выходит за пределы своих полезных стратегий. В данной игре обе чистые стратегии игрока B являются полезными, поскольку в противном случае игра имела бы решение в области чистых стратегий, то есть была бы игрой с седловой точкой.

Для нахождения оптимальной стратегии нужно найти неизвестные p₁, p₂, v, которые удовлетворяют следующей системе из трех линейных уравнений:

  (2.1.7)

Решение этой системы имеет вид:

 (2.1.8)

Аналогичным образом можно найти и оптимальную стратегию игрока В:

 (2.1.9)

Игры размером m×n решаются с помощью приведения к задачам линейного программирования.

2.2 Графический метод решения игровых задач с нулевой суммой

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии, то есть игры 2×2, 2×n, m×2.

Рассмотрим игру типа 2×n без седловой точки, платежная матрица которой имеет вид:

         (2.2.1)

Решение игры такого типа может быть найдено графическим методом. Для этого необходимо провести через точку (1; 0) координатной плоскости Oxy прямую l, перпендикулярную оси абсцисс. После этого для каждой из стратегий B_i (i=1,2,..., n) провести прямую, уравнение которой:

         (2.2.2)

Эта прямая соединяет точку (0, a_1i) на оси Оу с точкой (0, a_2i) на прямой l. Ось Оу отвечает за стратегию A₁, а прямая l − за стратегию A₂. Графически это изображено на рисунке 2.1 и 2.2:

Рисунок 2.1 - Изображение прямой b_i

Рисунок 2.2 - Решение игры графическим методом

Если игрок А применяет смешанную стратегию p_I=(p₁,p₂,…p_m), то его выигрыш в случае, если противник применяет чистую стратегию B_i, равен

                        (2.2.3)

Этому выигрышу соответствует точка М на прямой b_i с абсциссой p₂ (Рисунок 2.2). Ломаная b₁MNb₃, отмеченная на графике жирной линией, позволяет определить минимальный выигрыш игрока А при любом поведении игрока В. Точка N, в которой эта ломаная достигает максимума, определяет решение и цену игры. Ордината точки N равна цене игры v, а ее абсцисса p₂ - частоте применения стратегии A₁ в оптимальной смешанной стратегии игрока А.

Далее непосредственно по графику нужно найти пару "полезных" стратегий игрока В, пересекающихся в точке N (если в точке N пересекается более двух стратегий, то выбрать любые две из них). Пусть это будут стратегии B_i и B_j. Поскольку выигрыш игрока А, если он придерживается оптимальной стратегии, не зависит от того, в каких пропорциях игрок В применяет эти стратегии, то неизвестные p₁, p₂, v, определяются из системы уравнений:

                                                                           (2.2.4)

Оптимальная стратегия игрока B имеет вид:

Для нахождения частот q₁ и q₂ используется соотношение:

                                                                                     (2.2.5)

Следует отметить, что иногда точка N не является пересечением двух стратегий, а попадает на одну из прямых х = 0 или х = 1. В этом случае решением игры будут соответствующие чистые стратегии.

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

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

Верхняя и нижняя цены игры равны, то есть β=α=2. Значит эта игра имеет седловую точку. Оптимальными стратегиями игроков I и II будут P*=(1;0) и Q*=(1;0). В графическом виде решение игры представлено на рисунке 2.3.

Рисунок 2.3 - Решение игры с седловой точкой

Анализируя график, видно, что стратегия В₂ не выгодна, а стратегия А₁ лучше, чем стратегия А₂.

.3 Определение смешанных стратегий с помощью линейной оптимизации

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

Рассмотрим игру m×n , определяемую матрицей:

Пусть для данной матричной игры α≠β, определим такие значения вероятностей выбора стратегий для игрока 1 (p₁,p₂, …, p_m) и для игрока 2 (q₁,q₂, …, q_m) , при которых игроки достигали бы своего максимально гарантированного выигрыша. Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что v>0.

Применение игроком I оптимальной смешанной стратегии p_I*, гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры v. Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I - свою оптимальную стратегию p_I*. Тогда средний выигрыш игрока I будет равен:

v_i=a_1jp₁+a_1jp₂+…+a_ijp_i+…+a_mjp_m, j=           (2.3.2)

Учитывая, что vj не может быть меньше v, записываются следующие условия:

                           (2.3.3)

Чтобы определить значение v, разделим обе части каждого из уравнений на v. Величину p_i/v обозначим через x_i, а q_j/v - через u_j. Для игрока 1 получим новую систему неравенств:

                      (2.3.4)

Для игрока 1 необходимо найти максимальную цену игры v. Следовательно, значение 1/v должно стремиться к минимуму.

Целевая функция задачи будет иметь следующий вид:

(2.3.5)              (2.3.5)

Таким образом, задача определения оптимальной смешанной стратегии свелась к стандартной задаче линейной оптимизации: найти неотрицательные значения переменных x_i, i=1,2,…m, минимизирующие целевую функцию (2.3.5) и удовлетворяющие условиям (1.4.4).

Решение задачи линейной оптимизации позволяет найти цену игры v и оптимальную стратегию p_I*=(p₁,p₂, …, p_m ) первого игрока:

;  ; i=1, 2, …, m               (2.3.6)

Аналогично можно показать, что оптимальная стратегия второго игрока q_II*=(q₁,q₂, …, q_n ) определяется по формулам:

 , j=1, 2, …, n                       (2.3.7)