13.1. Розв'язання матричної гри в змішаних стратегіях

Гра розміром m X n в загальному випадку не має геометричної інтерпретації. Її розв'язування трудомістке, але принципових труднощів не має, оскільки може бути зведене до розв'язування пари двоїстих задач лінійного програмування.

розв'язання матричних

Нехай задано матричну гру m X n платіжною матрицею (13.1).a

a

av(13.1)\ami am2оптимальна змішана стратегія

Нехай SA =

An

P0

A1 A2 po Po

гравця А, p > 0, i = 1, m , p - ймовірність використання чистоїi=1

- оптимальна

стратегії A , ^ P = 1; SB =

Bn

qO

B1 B2

WO q0

змішана стратегія гравця В, qj > 0, j = 1, n , ^qj = 1, qj - ймовірність

j=i

використання чистої стратегії Bj, v - невідома ціна гри. Без обмеження узагальненості будемо вважати, що v > 0 . Цього можна добитися, якщо всі будуть a j > 0 .

Якщо гравець А застосовує свою оптимальну стратегію SA , а гравець В - деяку чисту стратегію Bj, тоді середній виграш складає a1Jpl + a2jP2 +... + amjPm, j = 1, n . Для оптимальної стратегії S"A всі середні виграші не можуть бути меншими, ніж ціна гри v (стратегія SA гравця А гарантує йому виграш не менш, ніж v , незалежно від вибору стратегії Bj гравцем В). В результаті таких міркувань одержимо систему нерівностей:

a11 P1 + a21 P2 + .

. + am1 Pm

> v,

a12 P1 + a22 P2 + .

. + am 2 Pm

> v,

a1nP1 + a2nP2 + .

.. + amn Pm

> v.

Перетворимо систему (13.2), поділивши всі члени на v , v > 0 і ввівши позначення

Xt = —, i = 1, m

(13.4)

v

a11x1

+ a21x2

+.

. + am1xm

> 1,