Свойства матричных игр.

Раздел III. ИГРОВЫЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЯ

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

Литература: [11-13]

§1. Основные сведения из теории матричных игр.

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

(1)

В этой модели выбор I игрока сводится к выбору строки (m чистых стратегий), выбор II игрока - к выбору столбца (n чистых стратегий); а_ij - выигрыш I игрока при стратегиях (i,j); выигрыш II игрока при тех же стратегиях есть число а_ij с противоположным знаком (игра антагонистическая). Каждый игрок выбирает свою стратегию так, чтобы получить как можно больший выигрыш.

В отличие от ранее рассмотренных задач оптимизации в модели (1) участвуют два ЛПР. Наша задача заключается в вычислении "оптимальных" стратегий и соответствующих им выигрышей обоих ЛПР (игроков).

Стратегия i* (j*) называется оптимальной чистой стратегией первого (второго) игрока, если для любых i = 1,2,...,m и j = 1,2...n выполнено неравенство

a_ij*≤a_i*j*≤a_i*j (2)

Пара оптимальных стратегий (i*j*) называется седловой точкой, а число a_i*j* -значением (или ценой) игры (1).

Свойства матричных игр.

1. Седловая точка в матричных играх существует не всегда (примеры см. в [14]). Она существует тогда и только тогда, когда

(3)

Поэтому принципы оптимальности в матричных играх называются принципом минимакса (или максимина).

2. Значение игры, если оно существует, является наименьшим числом в своей строчке и наибольшим в своем столбике.

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

4. Игра (1) может иметь несколько седловых точек. Если (i*,j*), () - седловые точки, то (i*, ) и (,j*) - тоже седловые точки (взаимозаменяемость) и a_i*j*= = = (эквивалентность).

5. Если игра (1) не имеет оптимальных чистых стратегий, то вводят смешанные стратегии:

x=(x₁,…,x_m): 0≤x_i≤1, i=1,…,m; x₁+…+x_n=1 и

=(y₁,…,y_n): 0≤y_j≤1, j=1,…,n; y₁+…+y_n=1;

х - смешанная стратегия 1 игрока; у - смешанная стратегия II игрока. Таких стратегий у игроков бесконечное множество.

6. В любой матричной игре существуют оптимальные смешанные стратегии x*,y*:

(4)

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

Решить игру (1) это значит найти пару оптимальных стратегий (чистых или смешанных) и значение игры.

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

Пример 1. Найти оптимальные чистые стратегии и значения следующей матричной игры:

Чтобы упростить эту игру, умножим каждый элемент матрицы А на 12, а затем каждому элементу прибавим 6 (чтобы избавиться от отрицательных чисел) - см. свойство 3:

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

В этом случае говорят, что первая стратегия доминирует четвертую стратегию.

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

Игра А' эквивалентна исходной игре в том смысле, что в них оптимальные стратегии одинаковы (свойство 3), a ν(A') = 12ν(A)+6

В игре А' применяем принцип минимакса (3). Вычислим левую часть равенства (З):

max{6,1,3}=6.

Вычислим правую часть равенства (З):

min{l0,7} =7.

Так как равенство (3) не выполнено, то в игре А' и, значит, в игре А, оптимальных чистых стратегий нет.

Пример 2. Решить игру

Решение: max{-2, 1,3,-6)=3,

min {3,6,5)=3.

Оптимальные стратегии: i*=3 (третья строка), j* = 1 (первый столбик); значение игры ν(А)=3.

Пример 3. Решить игру

В этой игре четыре седловые точки: (1,2), (1,4), (2,1), (2,4); значение игры ν(А)=3. Алгоритм решения матричной игры в чистых стратегиях следующий;

1) выполнить доминирование стратегий для обоих игроков;

2) вычислить обе части равенства (3); если равенство выполнено, то игра имеет решение в чистых стратегиях; если не выполнено - то оптимальных чистых стратегий нет.

§ 3. Общий метод решения матричных игр.

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

Для решения игры (1) в смешанных стратегиях сводят ее к паре двойственных задач линейного программирования, применяя неравенство (4). Прямая задача ЛП:

min z=ξ ₁+ξ ₂+...+ξ _m (1)

при ограничениях

a₁₁ξ ₁+a₂₁ξ ₂+…+a_m1ξ _m≥1,

a₁₂ξ ₁+a₂₂ξ ₂+…+a_m2ξ _m≥1, (2)

………………………….

a_1nξ ₁+a_2nξ ₂+…+a_mnξ _m≥1,

ξ ₁≥0,…,ξ _m≥0 (3)

где

ξ ₁=x_i*/ν, i=1,…,m; z=1/ν, (4)

a (x₁*,…,x_n*)=x* - оптимальная смешанная стратегия первого игрока. Задача (1)-(3) соответствует первому игроку, т.е. решая ее симплекс-методом находят оптимальную смешанную стратегию I игрока и значение игры по формулам (4).

Двойственная задача ЛП:

max w =h₁+h₂+…+h_n (5)

при ограничениях

a₁₁h₁+a₂₁h₂+…+a_m1h_m≤1,

a₁₂h₁+a₂₂h₂+…+a_m2h_m≤1, (6)

………………………….

a_1nh₁+a_2nh₂+…+a_mnh_m≤1,

h₁≥0,…, h_m≥0, (7)

где

h_j=y_j*/ν, j=1,…,n; w =1/ν, (8)

a (у₁*,...,у_n*)=у* - оптимальная смешанная стратегия II игрока. Задача (5)-(7) соответствует второму игроку, т.е. решая ее симплекс-методом, находят оптимальную смешанную стратегию II игрока и значение игры по формулам (8).

Пример 4. Решить следующую игру

Решение: Доминируемых стратегий нет, т.е. упростить игру невозможно. Оптимальных чистых стратегий нет, т.к. равенство (3) не выполнено. Поэтому надо решить игру в смешанных стратегиях.

Чтобы исключить случай v ≤0 (см. (4),(8)) избавимся от отрицательных элементов матрицы, прибавив ко всем элементам 4. Тогда получим эквивалентную игру

Задача (1)-(3) и (5)-(7) запишутся:

min z= ξ₁+ ξ₂+ ξ₃

при ограничениях

5ξ₁+3ξ₂+2ξ₃≥1,

4ξ₁+6ξ₂+ ξ₃≥1,

2ξ₁+7ξ₂+8ξ₃≥1,

5ξ₁+4ξ₂+ ξ₃≥1,

ξ₁≥0, ξ₂≥0, ξ₃≥0;

max w=h₁+h₂+h₃₊h₄

при ограничениях

5h₁+4h₂+2h₃+5h₄≤1

3h₁+6h₂+7h₃+4h₄≤1

2h₁+ h₂+8h₃+ h₄≤1

h₁≥0,…,h₄≥0

Примеры решения таких задач ЛП приведены в разделе II в достаточном количестве. Поэтому подробное решение здесь приводить не будем.

Последняя (оптимальная) симплекс-таблица для двойственной задачи (задачи второго игрока) имеет вид:

		h1	h2	h3	h4	h5	h6	h7
w	7/29		5/29		3/29	4/29	3/29
h1	5/29		16/29		27/29	7/29	-2/29
h3	2/29		18/29		5/29	-3/29	5/29
h7	3/29		144/29		65/29	10/29	36/29

Отсюда находим решение задачи ЛП: = (5/29,0, 2/29, 0) - точка максимума, w* =7/29 - максимальное значение целевой функции.

Оптимальную смешанную стратегию игрока П и значение игры А' находим по формулам (8):

v (A') =1/ w* = 29/7; у* = (5/7, 0, 2/7, 0).

В исходной игре А: v (А)= v (A')-4=1/7.

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

Дата добавления: 2015-09-05