Решение матричных игр со смешанным расширением методами линейного программирования

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

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

 

	B 1	B 2	…	Bn
A 1	a11	a12	...	a1n
A 2	a21	a22	...	a2n
…	...	...	...	...
A m	am1	am2	...	amn

Рис. 1

 

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

 

Для первого игрока:

 

Для второго игрока

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

Из первой системы найдем отношение 1/ v, в котором величина v должна равняться максимальной цене игры для игрока 1. Сформируем целевую функцию для первого игрока

.

Для игрока 2 необходимо найти минимальную цену игры (v), следовательно величина 1/ v должна стремиться к максимуму, т.е.

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

Для решения задач линейного программирования используется симплекс-метод. [1, 5].

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

Величина v * определяется по формуле: v * = 1/ z

Значения вероятностей выбора стратегий определяются: для игрока 1: : для игрока 2: .

Для определения цены игры v из величины v * необходимо вычесть число K.

 

Биматричные игры. Основные понятия и ситуация равновесия

 

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

Рассмотрим конфликтную ситуацию, в которой два игрока имеют следующие возможности для выбора своей линии поведения:

- игрок 1 может выбрать любую из стратегий ;

- игрок 2 - любую из стратегий .

При этом в ситуации выигрыш первого игрока будет , а второго - , т.е. игра задается в форме двух платежных матриц :

 

. (1)

В этом случае говорят о биматричной бескоалиционной игре двух игроков с платежными матрицами (1). При получаем обычную матричную игру.

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

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

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

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

Пример. Фирмы 1 и 2 продают конкурирующие товары и решают проводить ли им рекламные компании. Возможные исходы отражены платежными матрицами

 

Фирма B

Фирма B

Реклама Нет

Реклама Нет

 

Матрица выигрышей фирмы А Матрица выигрышей фирмы B

 

Фирма B: доминирующая стратегия – В₁

Фирма А: доминирующая стратегия – А₁