Игровые модели принятия решения

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

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

Литература: [12-15]

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

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

(1)

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

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

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

aij*≤ai*j*≤ai*j (2)

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

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

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

(3)

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

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

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

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

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

x=(x1,…,xm): 0≤xi≤1, i=1,…,m; x1+…+xn=1 и

=(y1,…,yn): 0≤yj≤1, j=1,…,n; y1+…+yn=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=ξ 1+ξ 2+...+ξ m (1)

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

a11ξ 1+a21ξ 2+…+am1ξ m≥1,

a12ξ 1+a22ξ 2+…+am2ξ m≥1, (2)

………………………….

a1nξ 1+a2nξ 2+…+amnξ m≥1,

ξ 1≥0,…,ξ m≥0 (3)

где

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

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

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

max w=h1+h2+…+hn (5)

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

a11h1+a21h2+…+am1hm≥1,

a12h1+a22h2+…+am2hm≥1, (6)

………………………….

a1nh1+a2nh2+…+amnhm≥1,

h1≥0,…, hm≥0, (7)

где

hj=yj*/ν, j=1,…,n; w=1/ν, (8)

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

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

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

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

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

min z= ξ1+ ξ2+ ξ3

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

5ξ1+3ξ2+2ξ3≥1,

4ξ1+6ξ2+ ξ3≥1,

2ξ1+7ξ2+8ξ3≥1,

5ξ1+4ξ2+ ξ3≥1,

ξ1≥0, ξ2≥0, ξ3≥0;

max w=h1+h2+h3+h4

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

5h1+4h2+2h3+5h4≤1

3h1+6h2+7h3+4h4≤1

2h1+ h2+8h3+ h4≤1

h1≤0,…,h4≤0

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

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

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

Отсюда находим решение задачи ЛП: = (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 игрока, решая прямую задачу двухфазным симплекс-методом.