Метод Лагранжа

Метод Лагранжа относится к точным методам решения матричных игр G(mm), т.е. имеющим квадратные матрицы (или приведенные к такому виду после упрощения).

Допустим, что игрок Aиспользует смешанную стратегиюS_A = (p₁, …,p_m), а игрокBотвечает своей чистой стратегиейB_i(i = 1, 2,…,m). Цена игры в таком случае равна. Если же игрокBтакже будет применять смешанную стратегиюS_B = (q₁, …,q_m), то итоговая цена игры будет равна

. (3.1)

Для нахождения оптимального решения необходимо максимизировать значение V при ограничениях.

Составим функцию Лагранжа L = V + ₁(p₁ + … + p_m – 1) +₂(q₁ + … + q_m – 1) и приравняем к нулю частные производные по всем аргументам:.

В результате получим следующую систему из (2m + 2) уравнений с (2m+ 2) неизвестными:

Решение этой системы и даёт смешанные стратегии для обоих игроков.

Нетрудно заметить, что исходная система уравнений включает две независимые подсистемы (для p_i, i = 1, …,m,₁иq_j, j = 1, …,m,₂ соответственно), состоящие из (m+ 1) уравнений с (m+ 1) неизвестными, решение которых и даст искомые вероятностиp_iиq_j, а также после подстановки этих вероятностей в формулу (3.1) цену игрыV.

В качестве примера рассмотрим игру G(22), представленную в общем виде табл. 3.9.

Таблица 3.10

Bj Ai	B1	B2
A1	a11	a12
A2	a21	a22

V₁ = a₁₁p₁ + a₂₁p₂, V₂ = a₁₂p₁ + a₂₂p₂,

V = V₁q₁ + V₂q₂ = (a₁₁p₁ + a₂₁p₂)q₁ + (a₁₂p₁ + a₂₂p₂)q₂.

L=V+₁(p₁+p₂– 1) +₂(q₁+q₂– 1).

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

Решив данную систему получим следующие значения вероятностей:

.

Подставив полученные значения в выражение для V, получим цену игры.

Например, для игры G(22), представленной табл. 3.8, получим:

p₁ = 0,6; p₂ = 0,4; q₁ = 0,8; q₃ = 0,2; V = 3,6.

Можно также найти решение в общем виде для игры G(33) и т.д.

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

Рассмотрим игру игры G(33) в общем виде, представленную табл. 3.10.

Таблица 3.11

Bj Ai	B1	B2	B3
A1	a11	a12	a13
A2	a21	a22	a23
A3	a31	a32	a33

Для нахождения решения в смешанных стратегиях необходимо решить следующую систему уравнений:

Эту систему можно представить следующим образом:

.

Решением в общем виде представляется системой

Более конкретно:

Обозначив

k = – a₁₁a₂₂ + a₁₁a₃₂ + a₁₁a₂₃ – a₁₁a₃₃ + a₂₁a₁₂ – a₂₁a₃₂ –

– a₂₁a₁₃ + a₂₁a₃₃ – a₃₁a₁₂ + a₃₁a₂₂ + a₃₁a₁₃ – a₃₁a₂₃ –

– a₁₂a₂₃ + a₁₂a₃₃ + a₂₂a₁₃ – a₂₂a₃₃ – a₃₂a₁₃ + a₃₂a₂₃,

получим итоговое решение:

p₁ = (– a₂₁a₃₂ + a₂₁a₃₃ + a₃₁a₂₂ – a₃₁a₂₃ – a₂₂a₃₃ + a₃₂a₂₃) / k

p₂ = ( a₁₁a₃₂ – a₁₁a₃₃ – a₃₁a₁₂ + a₃₁a₁₃ + a₁₂a₃₃ – a₃₂a₁₃) / k

p₃ = (– a₁₁a₂₂ + a₁₁a₂₃ + a₂₁a₁₂ – a₂₁a₁₃ – a₁₂a₂₃ + a₂₂a₁₃) / k

q₁ = (– a₁₂a₂₃ + a₁₂a₃₃ + a₂₂a₁₃ – a₂₂a₃₃ – a₃₂a₁₃ + a₃₂a₂₃) / k

q₂ = ( a₁₁a₂₃ – a₁₁a₃₃ – a₂₁a₁₃ + a₂₁a₃₃ + a₃₁a₁₃ – a₃₁a₂₃) / k

q₃ = (– a₁₁a₂₂ + a₁₁a₃₂ + a₂₁a₁₂ – a₂₁a₃₂ – a₃₁a₁₂ + a₃₁a₂₂) / k

V = – |A| / |A1|,

где А— исходная матрица игры.

Данный подход легко применим для произвольной игры G(mm): строится матрицаA1, далее, используя определители, записываются выражения дляp_iиq_j, множитель знака для них будет равен (–1)^{m + i + 1}.