варинат. Алгоритм решения

Гарантированные рез-ты в матричной игре

Гарантированные результаты: n ₁= n – нижняя цена игры, n₂= – верхняя цена игры.

Можно показать, что всегда n £ , или

£ .

Действительно, £ - по свойству с.р. Но если f(x)<g(x), minf(x)<ming(x), т.е. £ , справа стоит константа. Если функция ограничена сверху константой, то и максимум этой функции ограничен ею же. Т.е. £ , ч.т.д.

Это неравенство носит название неравенство минимаксов и успешно используется для решения игр.

Если n = , то это ситуация равновесия, или седловая точка. Соответствующая пара стратегий является решением игры.

Пример. Пусть задана матрица игры:

Найдем гарантированные результаты каждого игрока:

= max_xmin_yf_ij=2; = min_ymax_xf_ij=2 – в игре есть седловая точка. Тогда цена игры равна 2, а решение игры – (х₂, y₂).

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

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

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

Теорема Неймана гарантирует, что каждая антагонистическая игра имеет оптимальные стратегии.

Пример 2. Задана матрица игры: = 4; = 6.

Если первый игрок будет придерживаться своей оптимальной стратегии (х₂), то его выигрыш будет не меньше, чем 4. Второй игрок, придерживаясь своей гарантирующей стратегии y₁, проиграет не больше, чем 6. Анализируя поведение игроков при выборе хода, можно сообразить, что пока твои ходы знает противник, ситуации равновесия не будет. В играх без седловой точки свои ходы надо тщательно скрывать. Это игры с закрытой информацией. Однако интервал [4;6] каждый из игроков хочет перераспределить в свою пользу, и это выгодно им обоим. Значит, надо придумать такую процедуру поведения, чтобы nÎ[4;6]. Правильное поведение состоит в том, чтобы стратегию выбирать случайно – не на основании каких-то разумных соображений, - но сама схема рандомизации должна выбираться разумно. В этом состоит идея использования смешанных стратегий.

3 варинта+15 вариант: Биматричная игра

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

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

Биматричные игры

Если выполнено хотя бы одно из следующих условий:

- не всегда выигрыши игроков противоположны, т.е. f₁=-f₂;

- интересы сторон даже с двумя участниками не обязательно противоположны,

существует хотя бы одна ситуация, когда интересы игроков близки;

- различие в оценках ситуации оставляет место для соглашений, договоров и кооперации;

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

следует перейти к другой форме игры – биматричной.

Биматричная игра – это конечная игра двух лиц с ненулевой суммой

Выигрыши игроков определяются следующими матрицами:

А = - матрица выигрышей первого игрока, или ||а_ij||,

В =||b_ij|| - матрица выигрышей второго игрока.

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

Средний выигрыш первого игрока: Мn₁= ,

Средний выигрыш второго игрока: Мn₂= ,

å b_ij p_i £ å b_ij p_i q_j, å p_i=1

å a_ij q_j £ å a_ij p_i q_j, å q_j=1, для любых i, j.

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

Пример. Заданы две матрицы игры: А = , В =

p₁ = = = ; p₂ = = = Þ Þ n=

р₁= ; р₂=

Матрица В решается с точки зрения первого игрока, т.к. целью второго является также выиграть как можно больше:

q₁ = = ; q₂ = = Þ Þ n= ; q₁= ; q₂=

Ответ: Р= (; ); n₁= ; Q= (; ); n₂= .

Это решение выгодно обоим игрокам, т.к. их гарантированные результаты: (-1) – для первого и (-1) – для второго.

5 вариант

Ситуация равновесия в игре:

В игре может существовать ситуация равновесия – (x^*, y ^*).

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

Пусть f₁(x,y) – выигрыш первого игрока в ситуации (x,y); f₂(x,y) – выигрыш второго игрока. Тогда принцип равновесия запишется в виде

f₁(x,y^*)£ f₁(x^*,y^*)

f₂(x^*,y)£f₂(x^*,y^*).

Умножим второе неравенство на (-1):

-f₂(x^*,y ³-f₂(x^*,y^*),

или, учитывая, что f₁(x,y)=-f₂(x,y),

f₁(x^*,y)³ f₁(x^*,y^*), откуда

f₁(x,y^*)£ f₁ (x^*,y^*) £f₁(x^*,y)

Таким образом, ситуация равновесия – точка, выигрыш в которой первого игрока минимален по y и максимален по x:

.

y1 y2 y3

Пример 1. Пусть платежная матрица задана в виде

 

 

 

,

тогда первый игрок выбирает 1-ую стратегию, ориентируясь на максимальный выигрыш 5. Второй игрок выбирает свою вторую стратегию, чтобы проиграть 1, а не 5. На следующем шаге 1-ый игрок ходит своей второй стратегией, чтобы максимизировать свой выигрыш при 2-ой стратегии 2-го игрока, на что тот отвечает опять же своей второй стратегией, чтобы минимизировать свой проигрыш. Далее игра становится устойчивой, т.к. ситуация (x₂,y₂) выгодна обоим игрокам.

Когда в игре есть ситуация равновесия, то через какое-то число ходов игра сойдется и станет устойчивой – игрокам нет смысла скрывать свои стратегии. Если игра не имеет ситуации равновесия, то игроки сохраняют свои стратегии в тайне.

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

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

.

Здесь n₁ – гарантированный результат для I игрока: он не получит меньше, чем n₁, при любой стратегии II игрока. Следует заметить, что аналогичного принципа придерживается ЛПР в нестратегической игре с природой, когда, не желая рисковать, он выбирает минимаксный критерий.

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

.

Здесь n₂ – гарантированный результат для II игрока:

он не проиграет больше, чем n₂, при любой стратегии первого игрока.

Соответствующие стратегии носят названия: максиминная - для I игрока, - и минимаксная – для второго.

 

9 вариант + 18 вариант(антогонистическая игра)

Антагонистическая игра – игра двух лиц с нулевой суммой.

В антагонистической игре цели игроков противоположны:

Цель первого игрока –

выиграть как можно больше,

 

цель второго -

проиграть как можно меньше

 

 

16 вариант

Смешанная стратегия

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

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

Тогда смешанная стратегия первого игрока – это случайная величина

x = , или просто вероятностное распределение

на множестве чистых стратегий Р = (р₁, р₂, ¼, р_m), причем .

Смешанная стратегия второго игрока – это случайная величина

h = , Q = (q₁, q₂, ¼, q_n), .

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

Очевидно, что любая чистая стратегия является частным случаем смешанной: например, х₁=Р(1,0,…,0). Таким образом, для любой игры существует пара (P,Q) смешанных стратегий. Платеж, соответствующий паре (P,Q), называется ценой игры n. Поскольку первый игрок гарантирует себе при этом выигрыш n³ , а второй игрок гарантирует себе проигрыш n£ , то применение смешанных стратегий выгодно обоим игрокам.

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

Решить игру – значит найти цену игры и оптимальные стратегии каждого игрока.

 

варинат. Алгоритм решения

 

1. Упростить игру.
2. Найти гарантированные результаты для каждого игрока.
3. Если существует седловая точка, то найти решение игры в чистых стратегиях.
4. Если седловой точки нет, то найти решение игры в смешанных стратегиях.

 

Рассмотрим по очереди каждый из этапов.

Упрощение игры

Решение игры m х n – довольно трудоемкая задача, особенно если у нее нет седловой точки. Дальше мы увидим, что матричную игру произвольной размерности можно свести к задаче линейного программирования. Однако игры небольшой размерности можно решить аналитически. Это относится к играм, где хотя бы у одного игрока имеется только две стратегии. Поэтому упрощение игр – необходимая составляющая процесса решения.

Игру иногда удается упростить, если уменьшить в ней число стратегий путем вычеркивания некоторых лишних стратегий. Лишние стратегии – это

1) дублирующие

2) заведомо невыгодные.