Игра nx2. Бескоалиционные игры

Игра nx2

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

Игроки	B₁	B₂	a = min(A_i)
A₁	-1	-4	-4
A₂	-9	-8	-9
A₃		-6	-6
A₄	-8		-8
A₅	-10		-10
A₆	-5		-5
A₇	-5		-5
b = max(B_i)

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = -4, которая указывает на максимальную чистую стратегию A₁.
Верхняя цена игры b = min(b_j) = 4.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах -4 ≤ y ≤ 4. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Стратегия A₁ доминирует над стратегией A₂ (все элементы строки 1 больше или равны значениям 2-ой строки), следовательно, исключаем 2-ую строку матрицы. Вероятность p₂ = 0.
Стратегия A₄ доминирует над стратегией A₅ (все элементы строки 4 больше или равны значениям 5-ой строки), следовательно, исключаем 5-ую строку матрицы. Вероятность p₅ = 0.
Стратегия A₆ доминирует над стратегией A₄ (все элементы строки 6 больше или равны значениям 4-ой строки), следовательно, исключаем 4-ую строку матрицы. Вероятность p₄ = 0.
Стратегия A₆ доминирует над стратегией A₇ (все элементы строки 6 больше или равны значениям 7-ой строки), следовательно, исключаем 7-ую строку матрицы. Вероятность p₇ = 0.

-1	-4
	-6
-5

В платежной матрице отсутствуют доминирующие столбцы.
Мы свели игру 7 x 2 к игре 3 x 2.
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.
Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.
В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (6). Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).

3. Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях (для игрока II):
5x₁+10x₂+x₃ ≥ 1
2x₁+14x₃ ≥ 1
F(x) = x₁+x₂+x₃ → min
найти максимум функции Z(y) при ограничениях (для игрока I):
5y₁+2y₂ ≤ 1
10y₁ ≤ 1
y₁+14y₂ ≤ 1
Z(y) = y₁+y₂ → max
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции Z(Y) = y₁+y₂ при следующих условиях-ограничений.
5y₁+2y₂≤1
10y₁≤1
y₁+14y₂≤1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
5y₁+2y₂+y₃ = 1
10y₁+y₄ = 1
y₁+14y₂+y₅ = 1
Решим систему уравнений относительно базисных переменных: y₃, y₄, y₅
Полагая, что свободные переменные равны 0, получим первый опорный план:
Y0 = (0,0,1,1,1)

Базис	B	y₁	y₂	y₃	y₄	y₅
y₃
y₄
y₅
Z(Y0)		-1	-1

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y₂, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2
и из них выберем наименьшее:
min (1 : 2 , - , 1 : 14 ) = ¹/₁₄
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (14) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y₁	y₂	y₃	y₄	y₅	min
y₃							¹/₂
y₄							-
y₅							¹/₁₄
Z(Y1)		-1	-1

Формируем следующую часть симплексной таблицы. Вместо переменной y₅ в план 1 войдет переменная y₂.
Получаем новую симплекс-таблицу:

Базис	B	y₁	y₂	y₃	y₄	y₅
y₃	⁶/₇	³⁴/₇				^-1/₇
y₄
y₂	¹/₁₄	¹/₁₄				¹/₁₄
Z(Y1)	¹/₁₄	^-13/₁₄				¹/₁₄

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y₁, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1
и из них выберем наименьшее:
min (⁶/₇ : 4⁶/₇ , 1 : 10 , ¹/₁₄ : ¹/₁₄ ) = ¹/₁₀
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (10) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y₁	y₂	y₃	y₄	y₅	min
y₃	⁶/₇	³⁴/₇				^-1/₇	³/₁₇
y₄							¹/₁₀
y₂	¹/₁₄	¹/₁₄				¹/₁₄
Z(Y2)	¹/₁₄	^-13/₁₄				¹/₁₄

Формируем следующую часть симплексной таблицы. Вместо переменной y₄ в план 2 войдет переменная y₁.
Получаем новую симплекс-таблицу:

Базис	B	y₁	y₂	y₃	y₄	y₅
y₃	¹³/₃₅				^-17/₃₅	^-1/₇
y₁	¹/₁₀				¹/₁₀
y₂	⁹/₁₄₀				^-1/₁₄₀	¹/₁₄
Z(Y2)	²³/₁₄₀				¹³/₁₄₀	¹/₁₄

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис	B	y₁	y₂	y₃	y₄	y₅
y₃	¹³/₃₅				^-17/₃₅	^-1/₇
y₁	¹/₁₀				¹/₁₀
y₂	⁹/₁₄₀				^-1/₁₄₀	¹/₁₄
Z(Y3)	²³/₁₄₀				¹³/₁₄₀	¹/₁₄

Оптимальный план можно записать так:
y₁ = ¹/₁₀, y₂ = ⁹/₁₄₀
Z(Y) = 1•¹/₁₀ + 1•⁹/₁₄₀ = ²³/₁₄₀
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
x₁=0, x₂=¹³/₁₄₀, x₃=¹/₁₄
Это же решение можно получить, применив теоремы двойственности.
Из теоремы двойственности следует, что X = C*A^-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

A = (A₃, A₁, A₂) =

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

D = A^-1 =

	^-17/₃₅	^-1/₇
	¹/₁₀
	^-1/₁₄₀	¹/₁₄

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1расположена в столбцах дополнительных переменных.
Тогда X = C*A^-1 =

(0, 1, 1) x

	^-17/₃₅	^-1/₇
	¹/₁₀
	^-1/₁₄₀	¹/₁₄

= (0;¹³/₁₄₀;¹/₁₄)

Оптимальный план двойственной задачи равен:
x₁ = 0, x₂ = ¹³/₁₄₀, x₃ = ¹/₁₄
F(X) = 1*0+1*¹³/₁₄₀+1*¹/₁₄ = ²³/₁₄₀
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
q_i = g*y_i; p_i = g*x_i.
Цена игры: g = 1 : ²³/₁₄₀ = ¹⁴⁰/₂₃
p₁ = ¹⁴⁰/₂₃*0 = 0
p₂ = ¹⁴⁰/₂₃*¹³/₁₄₀ = ¹³/₂₃
p₃ = ¹⁴⁰/₂₃*¹/₁₄ = ¹⁰/₂₃
Оптимальная смешанная стратегия игрока I:
P = (0; ¹³/₂₃; ¹⁰/₂₃)
q₁ = ¹⁴⁰/₂₃*¹/₁₀ = ¹⁴/₂₃
q₂ = ¹⁴⁰/₂₃*⁹/₁₄₀ = ⁹/₂₃
Оптимальная смешанная стратегия игрока II:
Q = (¹⁴/₂₃; ⁹/₂₃)
Поскольку ранее к элементам матрицы было прибавлено число (6), то вычтем это число из цены игры.
6²/₂₃ - 6 = ²/₂₃
Цена игры: v=²/₂₃
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑a_ijq_j ≤ v
∑a_ijp_i ≥ v
M(P₁;Q) = (-1*¹⁴/₂₃) + (-4*⁹/₂₃) = -2.174 ≤ v
M(P₂;Q) = (4*¹⁴/₂₃) + (-6*⁹/₂₃) = 0.087 = v
M(P₃;Q) = (-5*¹⁴/₂₃) + (8*⁹/₂₃) = 0.087 = v
M(P;Q₁) = (-1*0) + (4*¹³/₂₃) + (-5*¹⁰/₂₃) = 0.087 = v
M(P;Q₂) = (-4*0) + (-6*¹³/₂₃) + (8*¹⁰/₂₃) = 0.087 = v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Поскольку из исходной матрицы были удалены строки, то найденные векторы вероятности можно записать в виде:
P(0,0,¹³/₂₃,0,0,¹⁰/₂₃,0)
Q(¹⁴/₂₃,⁹/₂₃)

б)

Рассматриваем игру, после сведения ее к игре 3x2

-1	-4
	-6
-5

Находим решение игры в смешанных стратегиях.
Решим задачу геометрическим методом, который включает в себя следующие этапы:
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии B₁, правый - стратегии B₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).
2. На левой оси ординат откладываются выигрыши стратегии B₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии B₂.
Решение игры (m x 2) проводим с позиции игрока B, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.
Выделяем верхнюю границу выигрыша A₂NA₃. Максиминной оптимальной стратегии игрока B соответствует точка N, лежащая на пересечении прямых A₂A₂ и A₃A₃, для которых можно записать следующую систему уравнений:
y = 4 + (-6 - 4)q₂
y = -5 + (8 - (-5))q₂
Откуда
q₁ = ¹⁴/₂₃
q₂ = ⁹/₂₃
Цена игры, y = ²/₂₃
Теперь можно найти минимаксную стратегию игрока A, записав соответствующую систему уравнений, исключив стратегию A₁, которая дает явно больший проигрыш игроку A, и, следовательно, p₁ = 0.
4p₂-5p₃ = y
-6p₂+8p₃ = y
p₂+p₃ = 1
или
4p₂-5p₃ = ²/₂₃
-6p₂+8p₃ = ²/₂₃
p₂+p₃ = 1
Решая эту систему, находим:
p₂ = ¹³/₂₃.
p₃ = ¹⁰/₂₃.

Ответ:
Цена игры: y = ²/₂₃, векторы стратегии игроков:
P(0, ¹³/₂₃, ¹⁰/₂₃), Q(¹⁴/₂₃, ⁹/₂₃)
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑a_ijq_j ≤ v
∑a_ijp_i ≥ v
M(P₁;Q) = (-1*¹⁴/₂₃) + (-4*⁹/₂₃) = -2.174 ≤ v
M(P₂;Q) = (4*¹⁴/₂₃) + (-6*⁹/₂₃) = 0.087 = v
M(P₃;Q) = (-5*¹⁴/₂₃) + (8*⁹/₂₃) = 0.087 = v
M(P;Q₁) = (-1*0) + (4*¹³/₂₃) + (-5*¹⁰/₂₃) = 0.087 = v
M(P;Q₂) = (-4*0) + (-6*¹³/₂₃) + (8*¹⁰/₂₃) = 0.087 = v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Поскольку из исходной матрицы были удалены строки, то найденные векторы вероятности можно записать в виде:
P(0,0,¹³/₂₃,0,0,¹⁰/₂₃,0)
Q(¹⁴/₂₃,⁹/₂₃)

2.2)

Прибавим ко всем элементам матрицы 48, получим матрицу:

F₁

F₂

F₃

F₄

F₅

F₆

F₇

F₈

F₉

F₁₀

F₁₁

F₁₂

E₁

E₂

E₃

E₄

E₅

E₆

E₇

Составим пару взаимно-двойственных задач:

Решим вторую задачу симплекс методом

Для построения первого опорного плана, систему неравенств, приведем к системе уравнений путем введения дополнительных переменных

Матрица коэффициентов А системы уравнений будет иметь вид:

А=

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений с коэффициентом 1.

Решим систему уравнений относительно базисных переменных q₁₃, q₁₄, q₁₅, q₁₆, q₁₇, q₁₈, q₁₉

Пологая, что свободные переменные равны 0, получим первый опорный план

Q₁=(0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1)

3. Бескоалиционные игры

А
	-2	-8
	-13	-2

В
		-8

3.1) В каждом столбце матрицы А выберем максимальный элемент. Их положение соответствует приемлемым ситуациям первого игрока, когда второй игрок выбрал стратегию j соответственно. Затем в каждой строке матрицы В выберем наибольший элемент. Их положение будет определять приемлемые ситуации второго игрока, когда первый выбрал стратегию j соответственно.

Позиции максимумов в столбцах матрицы А: (1,1), (2,2)

а₁₁=-2; а₂₂=2

Позиции максимумов в строках матрицы В: (1,1), (2,2)

b₁₁=5; b₂₂=4;

Пересечение множеств этих максимумов: (1,1), (2,2)

Таким образом, найдены две равновесные ситуации по Нешу (1,1), (2,2). Эти равновесные ситуации оптимальны по Парето. В равновесной ситуации (1,1) первый игрок выигрывает -2, а второй 5. В равновесной ситуации (2,2) первый игрок выигрывает 2, а второй игрок 4.

Если биматричная игра не имеет равновесных ситуаций в чистых стратегиях, то она неразрешима в чистых стратегиях. И тогда можно искать решение в смешанных стратегиях. Чтобы в биматричной игре пара (p, q) определяла равновесную ситуацию, необходимо и достаточно одновременное выполнение неравенств:

(p-1)(cq-2)≥0, p(cq-2)≥0, 0≤p≤1

(q-1)(Дp-β)≥0, p(Дp-β)≥0, 0≤q≤1, где

С=a₁₁-a₁₂-a₂₁+a₂₂

α=a₂₂-a₁₂

Д=b₁₂-b₁₂-b₂₁+b₂₂

β=b₂₂-b₂₁

C=-2-(-8)-(-13)+2=21

α=2-(-8)=10

Д=5-(-8)-1+4=16

β=4-1=3

(p-1)(21q-10)≥0 1) p=1, q≥

p(21q-10)≥0 p=0, q≤

=> 0≤p≤1, q=

(q-1)(16p-3)≥0 2) q=1, p≥

q(16p-3)≥0 q=0, p≤

0≤q≤1, p=

Рассматриваемая игра имеет единственную ситуацию равновесия (p*, q*), где оптимальными стратегиями по Нему являются: p*=( ); q*=(

Таким образом, она может быть реализована при многократном повторении следующим образом: первый игрок должен использовать чистые стратегии 1 и 2 с частотами и , а игрок два – чистые стратегии 1 и 2 с частотами . Любой игрок, отклонившись от указанной смешанной стратегии, уменьшает свой ожидаемый выигрыш.

Цена игры:

H= + +

H_a= + + + =-5

H_b= + + + =1

Цена игры для первого игрока: H_a=( )= -5

Цена игры для второго игрока: H_b=( )= 1

Смешанная стратегия для первого игрока p*=( ), для второго игрока q*=( ),

Выигрыш игроков в равновесной ситуации: f(p*, q*)=(-5 1

Множество всех реализуемых векторов выигрышей для игры имеет вид, изображенный на рисунке:

3.2)

	В₁	В₂	a=min(A_i)
А₁	-2	-8	-8
А₂	-13		-13
b=max(B_i)	-2

Считаем, что игрок 1 выбирает свою стратегию так, чтобы получить максимальный выигрыш, а второй чтобы минимизировать выигрыш первого игрока. Находим гарантированный выигрыш, определяемый нижней ценой игры a=max(A_i)=-8, которая указывает на максимальную чистую стратегию А₁

Верхняя цена игры b=min(B_i)=2.

В данном случае отсутствует седловая точка, так как a≠b, тогда цена игры находится в пределах -8≤y≤-2.

Находим решение игры в смешанных стратегиях.

Запишем систему уравнений

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

=> => => => = =>

10y+130=22-11y

21y=-108

y= => p₁= , p₂=

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

=> => =>

15y+120=12-6y

21y=-108

y= => q₁= q₂=

В итоге, цена игры y= , оптимальная смешанная стратегия игрока 1: p=( ), для второго игрока: q=( )

	B₁	B₂	a=min(A_i)
A₁		-8	-8
A₂
b=max(B_i)

Находим гарантированный выигрыш, определяемый нижней ценой игры a=max(A_i)=1, которая указывает на максимальную чистую стратегию A₂. Верхняя цена игры b=min(B_j) =4

Седловая точка отсутствует, так как a≠b, тогда цена игры находится в пределах 1≤y≤4. Находим решение в смешанных стратегиях.

Запишем систему уравнений:

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

=> => =>