17. Решение матричной игры (2х2). Приведите алгоритм решения матричной игры 2х2

Аналитический метод решения игры 2х2 11 12 21 22 a a A a a

1) оптимальное решение в смешанных стратегиях: SA=|p1 , p2 | и SB=|q1 , q2 |

2)вероятности применения (относительные частоты применения) чистых стратегий удовлетворяют соотношениям p1 + p2 = 1 q1 +q2 = 1 2.4. Решение матричных игр в смешенных стратегиях 2х2Е.В. Яроцкая, к.э.н., доцент кафедры экономики ТПУ

3) В соответствии с теоремой об активных стратегиях, оптимальная смешанная стратегия обладает тем свойством, что обеспечивает игроку максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если тот не выходит за пределы своих активных стратегий. 2.4. Решение матричных игр в смешенных стратегиях 2х2Е.В. Яроцкая, к.э.н., доцент кафедры экономики ТПУ 4

1) Eсли игрок А использует свою оптимальную смешанную стратегию, а игрок В - свою чистую активную стратегию В1 , то цена игры равна a11p1 + a21p2 = v

2) Eсли игрок А использует свою оптимальную смешанную стратегию, а игрок В - свою чистую активную стратегию В2 , то цена игры равна a12p1 + a22p2 = v

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

1. Найдем оптимальную стратегию для первого игрока (А):

а) Построим систему координат v а22 а21 а11 а12 0 р 1 р опт v

б) По оси абсцисс откладывается вероятность р1 [0,1], равная 1.

в) По оси ординат – выигрыши игрока А при стратегии А2 , а на прямой р = 1 – выигрыши при стратегии А1

г) Находим точку пересечения прямых, которая и дает оптимальное решение матричной игры для игрока А (ропт, v)Е.В. Яроцкая, к.э.н., доцент кафедры экономики ТПУ

2.4. Решение матричных игр в смешенных стратегиях 2х2 13

2. Найдем оптимальную стратегию для второго игрока (В):

а) По оси абсцисс откладывается вероятность q1 [0,1], равный 1.

б) По оси ординат – выигрыши игрока B при стратегии B2 , а на прямой q = 1 – выигрыши при стратегии B1

в) Находим точку пересечения прямых, которая и дает оптимальное решение матричной игры для игрока B (qопт, v

18. Упрощение матричных игр.

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

Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B.

Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры.

Частный случай доминирования является дублированиестратегий.

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

Упрощение (уменьшение размерности) платёжных матриц за счёт исключения заведомо невыгодных чистых стратегий возможно в силу справедливости следующей Теоремы о доминирующих стратегиях:

Пусть I - игра, в матрице которой i -я стратегия первого игрока доминирует над i +1, а G - игра, матрица которой получена из матрицы I исключением i + 1 стратегии (строки). Тогда:

1. цена игры I равна цене игры G;

2. оптимальная смешенная стратегия Q^*= (q₁^*,q₂^*,…,q_n^*) второго игрока в игре G является также его оптимальной смешанной стратегией в игре I;

3. если P^*= (p₁^*,p₂^*,…,p_i^*, p*_i+2,…, p_m^*) оптимальная смешенная стратегия первого игрока в игре G, то его смешенная стратегия P^*= (p₁^*,p₂^*,…,p_i^*, p*_i+2,…, p_m^*) является оптимальной в игре I.

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