Доминируемые стратегии. 
Задача № 3

Платежная матрица игры есть.

• 7 0 6 0
• 4 3 6 2
• 3 2 3 3
• 6 6 7 7
• 5 3 4 3

Найти все доминируемые (заведомо невыгодные) стратегии первого игрока, все доминируемые стратегии второго игрока.

Решение:

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

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

Столбец платежной матрицы называется доминируемым столбцом, если все его элементы больше или равны соответствующих элементов какого-либо другого столбца. Т.к. все элементы первого столбца больше или равны соответствующих элементов второго столбца, то первый столбец является доминируемым. То же самое можно утверждать относительно третьего столбца. Ответ: доминируемыми стратегиями первого игрока являются 2,3,5; доминируемыми стратегиями второго игрока являются 1,3.

Смешанное расширение матричной игры. Задача № 4

Платежная матрица игры есть.

• 2 4 1 1
• 3 6 2 1
• 1 5 3 2

Какие из данных векторов ;0;, ;;, ;0;;0, ;0;;0.

являются смешанными стратегиями первого игрока?

Если смешанная стратегия первого игрока х =; ;, а второго игрока — у =; 0; 0;, то чему равен выигрыш второго игрока в данной ситуации (х;у)?

Найти оптимальную смешанную стратегию первого игрока.

Указать цену игры.

Решение:

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

Каждая смешанная стратегия игрока, А полностью определяется вероятностями р1, р2, р3, с которыми игрок, А выбирает соответствующие чистые стратегии А1, А2, А3. Поэтому смешанную стратегию Р игрока, А можно отождествлять с трехмерным вектором.

Р = (р1, р2, р3), рi 0, i = 1, 2, 3,.

Вектор ;0; является смешанной стратегией первого игрока, т.к. это трехмерный вектор с неотрицательными компонентами, сумма которых равна 1.

Вектор ;; не является смешанной стратегией первого игрока, т.к. сумма компонентов не равна 1.

Вектор ;0;;0 не является смешанной стратегией первого игрока, т.к. он содержит четыре компоненты, а чистых стратегий у первого игрока только 3.

Вектор ;0;;0 не является смешанной стратегией первого игрока, т.к. он содержит четыре компоненты, а чистых стратегий у первого игрока только 3.

Ответ: вектор ;0; является смешанной стратегией первого игрока.

Выигрыш второго игрока В в игровой ситуации (х; у) определяется по формуле:

при = 3, = 4, =, =, =, =, = 0, = 0, = мы получим, что.

=(+++)+(+++)++ (+++).

После подстановки чисел мы будем иметь.

= (2· + 4· 0 + 1· 0 + 1·) + (3· + 6· 0 + 2· 0 + 1·) + (1· + +5· 0+ 3· 0 + 2·)= + + = .

Ответ: Выигрыш второго игрока в данной ситуации равен .

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

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

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

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

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

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

Пусть () — оптимальная смешанная стратегия первого игрока, а (- оптимальная смешанная стратегия второго игрока, — цена игры.

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

Учитывая, что вероятности должны удовлетворять условию.

+=1,.

мы получим систему трех уравнений с тремя неизвестными Решив эту систему, получим.

, .

Аналогично, применяя теорему об активных стратегиях, ко второму игроку, получим систему и, решая ее, найдем, что.

.

Подставляя в эти формулы числа матрицы, будем иметь.

=, =, = =.

— это вероятность, с которой первый игрок может выбирать 2-ую чистую стратегию, а — это вероятность, с которой он может выбирать 3-ю чистую стратегию, вспомним, что 1-ую стратегию игрок выбирает с нулевой вероятностью. Таким образом, оптимальная смешанная стратегия первого игрока равна .

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

Цена игры равна = =.

Ответ: цена игры: =.