Матричний метод розв’язання ігор

Нехай треба розв’язати гру з платіжною матрицею A = (a_ij) _m´n і нехай В – будь-яка квадратна підматриця матриці А, поря­док якої r ³ 2. Тоді алгоритм матричного методу полягає у ви­конанні таких операцій.

І. Вибираємо квадратну підматрицю В матриці А і обчислюємо

,

де J_r = /1, 1,..., 1/ – одиничний вектор-рядок; adjB – матриця, приєднана до В; (*)^T – індекс транспонування; – вектор, побудованний з Х викресленням елементів, які відпо­відають рядкам, викресленим з А під час побудови В; – вектор, побудований із Y викресленням елементів, які відпо­відають стовпцям, викресленим з А під час побудови В.

2. Якщо деякі x_i < 0, i =1, r або y_j <0 j =1, r, то відкидаємо підматрицю В та спробуємо аналізувати другу.

3. Якщо всі x_i ³ 0, i =1, r та y_j ³ 0, j =1, r, то обчислюємо

.

4. Будуємо X з та Y з , поширюючи ці вектори нулями на тих місцях, де ми викреслювали рядки чи стовпці під час по­будови підматриці В.

5. Перевіряємо виконанння співвідношень

Якщо хоча б однез них не виконується, відкидаємо підматриці і спробуємо аналізувати другу.

Приклад 8.8. Розв’яжемо гру з платіжною матрицею

Оскільки матриця А квадратна, то її можна розглядати як підматрицю В, порядок якої r = 3. Тоді

а розв’язок гри, обчислений за наведеними вище формулами, має вигляд

З дев’яти підматриць порядку r = 2лише одна має додатко­вий роз­в’я­зок, а саме для якої а звідки

Як бачимо, перший гравець має єдину оптимальну стратегію, тоді як другий – множину оптимальних стратегій:

, де

Виникає питання, чи можна зробити вибір між різними оптималь­ними стратегіями. Нехай перший гравець вибирав змішану стратегію Х, а дру­гий - чисту стратегію j. Тоді математичне сподівання виграшу першого гравця буде дорівнювати E (X, j).

Змішана стратегія Х домінує над змішаною стратегією , якщо для кожної чистої стратегії j другого гравця та існує хоча б одна така стратегія j, для якої Е (Х, j) > Е (Х’, j). У такому випадку стратегія Х називається найкращою, якщо вона оптимальна та жодна інша стратегія не домінує її. В розглянутому вище прикладі в другого гравця найкраща страте­гія – це Y= (0, 2/3, 1/3).