МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Вятський державний гуманітарний університет
Математичний факультет
Кафедра алгебри і геометрії
Випускна кваліфікаційна робота
Методи наближеного рішення матричних ігор
Виконала студентка V курсу
математичного факультету
Вєтошкіна Є. Н.
______________ / Підпис /
Науковий керівник:
к. ф.-м. н., доцент, Ковязіна Є. М.
______________ / Підпис /
Рецензент:
к. ф.-м. н., доцент, Караулов В.М.
______________ / Підпис /
Допущена до захисту в ГАК
Зав. кафедрою __________________ Вечтомов Є. М.
«___» __________ 2003
Декан факультету _______________ Варанкіна В. І.
«___» __________ 2003

Кіров
2003
ЗМІСТ
Введення ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 3
§ 1. Основні поняття ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
§ 2. Ітеративний метод Брауна-Робінсона ... ... ... ... ... ... ... ... ... ... ... ... 10
§ 3. Монотонний ітеративний алгоритм розв'язання матричних ігор ... 16

Додаток ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .21

Список літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 24

Введення
«Теорія ігор - розділ математики, предметом якого є вивчення математичних моделей прийняття оптимальних рішень в умовах конфлікту ...». [17]
Математична теорія ігор здатна не тільки вказати оптимальний шлях до вирішення деяких проблем, а й прогнозувати їх результат. Матричні ігри серйозно вивчаються фахівцями, тому що вони досить прості і до них можуть бути зведені гри загального вигляду. Тому теорія матричних ігор добре розвинена, існують різні методи пошуку рішення ігор.
Але в більшості випадків рішення матричних ігор представляє собою складний і громіздкий процес. Є приклади, коли навіть для матриць розміру 3'3, процес пошуку рішення досить трудомісткий.
Крім того, виграші гравців у кожній ситуації не завжди визначаються точними вимірами. У процесі збору даних про досліджуваному явищі, аналізу цих даних і введення при побудові моделі різних припущень накопичуються помилки. Вони ж можуть виражатися числами в матриці виграшів. Тому точність у визначенні значення гри та оптимальних стратегій гравців виправдана не завжди.
А також, слід зауважити, що похибка в оцінці гравцем свого виграшу не може привести до практично серйозних наслідків і невелике відхилення гравця від оптимальної стратегії не тягне за собою істотної зміни в його виграші.
Тому виникає потреба в розробці чисельних методів розв'язання матричних ігор. В даний час в теорії ігор відомі декілька способів наближеного рішення матричних ігор.
Мета випускної кваліфікаційної роботи вивчити деякі методи наближеного рішення матричних ігор, обгрунтувати їх алгоритми, і, по можливості, реалізувати на мові програмування.
Робота складається з вступу, трьох параграфів і додатки, в якому наведена програма на мові Turbo Pascal, що дозволяє знаходити наближене рішення матричної гри.
У першому параграфі наведені основні поняття і затвердження теорії матричних ігор.
Параграф другий присвячений викладу наближеного розв'язання гри методом Брауна-Робінсона (метод фіктивного розігрування) і його обгрунтування. Наведено приклад застосування алгоритму для конкретної матричної гри.
У третьому параграфі розглянуто ще один метод - монотонний ітеративний алгоритм наближеного рішення матричних ігор.
§ 1. Основні поняття
Будемо розглядати тільки парні антагоністичні ігри, тобто ігри в яких беруть участь тільки два гравці - дві протиборчі сторони і виграш одного з гравців дорівнює програшу іншого. Крім того, будемо вважати, що кожен гравець має лише кінцеве число стратегій:
U ₁ = {a _1, a ₂ ,..., a _m} - безліч стратегій першого гравця;
U ₂ = {b _1, b _2, ... b _n} - безліч стратегій другого гравця.
Будемо називати ці стратегії чистими на відміну від змішаних, які будуть введені далі.
Безліч U ₁ ЧU ₂ - декартово твір множин стратегій гравців називається безліччю ситуацій у грі. Для кожної ситуації повинен бути визначений підсумок гри. Оскільки гра антагоністична досить визначити виграш а одного з гравців, скажімо першого. Тоді виграш другого гравця буде дорівнює (- а). Таким чином, маємо матрицю виграшів першого гравця (для другого гравця матриця виграшів-А):
A =
Визначення. Система Г = {U _1, U _2, A} називається матричною грою двох осіб.
Розігрування матричної гри зводиться до вибору гравцем 1 i-го рядка матриці виграшів, а гравцем 2 - j-го стовпця. Після цього гравець 1 отримує виграш рівний а _ij, а гравець 2 - (- а _ij).
При правильній грі гравець 1 може завжди гарантувати собі виграш, який назвемо нижнім значенням ціни гри. Позначимо його: .
У свою чергу, гравець 2 може гарантувати собі програш, який назвемо верхнім значенням ціни гри. Позначимо його:
.
Чисті стратегії i ^* і j ^*, відповідні називаються максимінної і мінімаксної стратегіями.
Лемма 1. У матричній грі . [17]
Визначення. Ситуація (i ^*, j ^*) називається ситуацією рівноваги, якщо для i Î 1,2, ..., m, j Î 1,2, ..., n виконується нерівність:
.
Ситуація рівноваги це така ситуація, від якої жодному з гравців не вигідно відхилятися. У цьому випадку стратегії i ^*, j ^* називають оптимальними стратегіями гравців.
Щоб така ситуація існувала необхідно і достатньо рівність верхньої та нижньої цін гри, тобто . [17]
Визначення. Нехай (i ^*, j ^*) - ситуацією рівноваги в матричній грі. Тоді число називається значенням або ціною гри.
Наприклад, в грі Г _А з матрицею А = існує не одна ситуація рівноваги. У даній грі їх дві: (1, 1) і (1, 3).
Безліч всіх ситуацій рівноваги в матричній грі позначимо через Z (Г).
Лемма про масштаб 1. Нехай Г і Г ^/ - дві матричні ігри з матрицею виграшів А = {a _ij} і A ^/ = {a ^/ _ij}, причому А ^/ = b А + a, b = const, a = const.
Тоді Z (Г) = Z (Г ^/) і n ^/ = b n + a (де n ^/ - значення ціни гри Г ^/, n - значення ціни гри Г). [17]
Ця лема має велике практичне значення, так як більшість алгоритмів для вирішення матричних ігор грунтується на припущенні, що матриця гри позитивна. У випадку, коли матриця має недодатні елементи, слід додати до всіх елементів матриці число найбільше за абсолютною величиною, з усіх негативних елементів.
Існують ігри, в яких ситуації рівноваги в чистих стратегіях не існує. Тоді гравцям буває не вигідно дотримуватися своїх мінімаксних і Максиміна стратегій, так як вони можуть отримати більший виграш, відхилившись від них. У цьому випадку гравцям розумно діяти випадково, тобто вибирати стратегії довільно і не повідомляти про вибір суперника. Такі стратегії гравців будемо називати змішаними.
Визначення. Змішаної стратегією гравця називається повний набір ймовірностей застосування його чистих стратегій.
Так якщо гравець 1 має m чистих стратегій, то його змішана стратегія x - це набір чисел x = (x _1, x _2, ..., x _m), які задовольняють співвідношенням , = 1. Аналогічним чином визначається змішана стратегія y гравця 2.
Визначення. Оптимальними стратегіями гравців називаються стратегії, які при багаторазовому повторенні забезпечують гравцям максимально можливий середній виграш (або мінімально можливий середній програш).
Таким чином, процес гри при використанні гравцями своїх змішаних стратегій перетворюється у випадкове випробування, яке назвемо ситуацією в змішаних стратегіях. Вона позначається так (x, y), де x і y - змішані стратегії гравців 1 і 2 відповідно.
Для ситуації в змішаних стратегіях кожен гравець визначає для себе середній виграш, який виражається у вигляді математичного очікування його виграшів: .
Від матричної гри прийшли до нової гри = {X, Y, K}, де X, Y - множини змішаних стратегій гравців, а K - функція виграшів у змішаних стратегіях. Таку гру називають змішаним розширенням матричної гри.
Цілі гравців залишаються незмінними: гравець 1 бажає отримати максимальний виграш, а гравець 2 прагне звести свій програш до мінімуму. Тому для змішаного розширення гри, аналогічним чином визначаються верхнє і нижнє значення ціни гри, тільки тепер гравці вибирають свої змішані стратегії. Позначимо їх:

У цьому випадку залишається справедливою лема 1, т. е. .
Визначення. Ситуація (x ^*, y ^*) у грі утворює ситуацію рівноваги, якщо для всіх x Î X, y Î Y виконується рівність:
K (x, y ^*) ≤ K (x ^*, y ^*) ≤ K (x ^*, y).
Щоб ситуація рівноваги в змішаному розширенні гри існувала необхідно і достатньо рівність верхньої та нижньої цін гри, тобто , Де n - ціна гри.
Для випадку змішаного розширення гри також справедлива лема про масштаб.
Лемма про масштаб 2.
Нехай Г _А і Г _А ^/ - дві матричні ігри А ^/ = a А + В,, a = const, В - матриця з однаковими елементами b, тобто b _ij = b для всіх i, j.
Тоді Z ( ) = Z (Г _А ^/) і n _А ^/ = a n _А + b (де n _А ^/ - значення ціни гри Г _А ^/, n _А - значення ціни гри Г _А). [17]
Теорема. У змішаному розширенні матричної гри завжди існує ситуація рівноваги. [17]

§ 2. Ітеративний метод Брауна-Робінсона (метод фіктивного розігрування)
Часто в практичних завданнях немає необхідності знаходити точне рішення матричної гри. Досить знайти наближене рішення, яке дає середній виграш, близький до ціни гри і наближені оптимальні стратегії гравців.
Орієнтовне значення ціни гри може дати вже простий аналіз матриці виграшів та визначення нижньої і верхньої цін гри. Якщо вони близькі, то пошуками точного рішення займатися не обов'язково, так як досить вибрати чисті мінімаксні стратегії. Якщо ж вони не близькі, можна отримати прийнятне для практики вирішення за допомогою чисельних методів розв'язання ігор, з яких розглянемо метод ітерацій.
Нехай розігрується матрична гра Г _А з матрицею А = {a _ij} розміру (m'n). Ідея методу - багаторазове фіктивне розігрування гри із заданою матрицею. Одне розігрування гри будемо називати партією, число яких необмежено.
У 1-ой партії обидва гравці вибирають абсолютно довільні чисті стратегії. Нехай гравець 1 вибрав i-ю стратегію, а гравець 2 - j-у стратегію. У другій партії гравець 1 відповідає на хід гравця 2 тієї своєю стратегією, яка дає йому максимальний виграш. У свою чергу, гравець 2, відповідає на цей хід гравця 1 своєю стратегією, яка звертає його програш у мінімум. Далі третя партія.
З ростом числа кроків процесу змішані стратегії, які приписуються гравцям, наближаються до їх оптимальним стратегіям. Цей процес наближеного знаходження оптимальних стратегій гравців називається ітеративним, а його кроки - итерациями.
Отже, припустимо, що за перші k розігрування гравець 1 використовував i-у чисту стратегію _i ^k   разів (i = 1, ..., m), а гравець 2 j-у чисту стратегію разів (j = 1, ..., n). Тоді їх змішаними стратегіями будуть вектори .
Гравець 1 стежить за діями гравця 2 і з кожним своїм ходом бажає отримати якомога більший виграш. Тому у відповідь на застосування гравцем 2 своєї змішаної стратегії y ^k, він буде використовувати чисту стратегію i _{k +1,} яка забезпечить йому найкращий результат при розігруванні (k +1)-ой партії. Гравець 2 вчинять аналогічно. У гіршому випадку кожен з них може отримати:

де - Найбільше значення програшу гравця 2 і - Найменше значення виграшу гравця 1.
Розглянемо відносини, які визначають середні значення програшу гравця 2 і виграшу гравця 1:

Нехай ν - ціна матричної гри Г _А. Її значення буде більше виграшу гравця 1, але менше програшу гравця 2, т. е.
. (1)
Таким чином, отриманий ітеративний процес, що дозволяє знаходити наближене рішення матричної гри, при цьому ступінь близькості наближення до істинного значення гри визначається довжиною інтервалу
.
Збіжність алгоритму гарантується наступної теоремою.
Теорема. .
Схема докази.
Лема. Для будь-якої матриці А і "e> 0 існує таке k _0, що
.
При граничному переході в нерівності (1) при k ® ¥ маємо:
. (2)
Звідси отримуємо оцінку різниці меж:
.
З леми випливає, що
.
На підставі нерівності (1) маємо: .
Отже, в силу обмеженості меж
.
Отримуємо оцінку для різниці меж:
для "e> 0.
Можемо зробити висновок, що . Залишилося показати рівність меж n. Це випливає з нерівності (2).
Отже, .
         Приклад. Знайти наближене рішення гри з матрицею
А = .
Нехай гру почне гравець 2. Він довільно вибирає одну зі своїх чистих стратегій. Припустимо, що він вибрав свою 1-у стратегію, а гравець 1 відповідає своїй 2-ій стратегією. Занесемо дані в таблицю.

но-заходів пар тії	стратегія друга гравця	виграш гравця 1 при його стратегіях			стратегія перший гравця	програш гравця 2 при його стратегіях			u	w	n
		1	2	3		1	2	3
1	1	0	4	2	2	4	1	2	4	1	5 / 2

У стовпці u знаходиться найбільший середній виграш 4 гравці 1, отриманий ним в першій партії; у стовпці w варто найменший середній програш 1, отриманий гравцем 2 в першій партії; у стовпці n знаходиться середнє арифметичне n = (u + w) / 2 = 5 / 2, тобто наближене значення ціни гри, отриманий в результаті програвання однієї партії.
Так як гравець 1 вибрав 2-у стратегію, то гравець 2 може програти:
4, якщо застосує свою 1-у стратегію;
1, якщо застосує свою 2-у стратегію;
2, якщо застосує свою 3-ю стратегію.
Оскільки він бажає програти якомога менше, то у відповідь застосує свою 2-у стратегію.
Тоді перший гравець отримає виграш рівний 3, 1, 0 відповідно при своїх 1-й, 2-й, 3-й стратегіях, а його сумарний виграш за дві партії складе:
0 +3 = 3 при його 1-й стратегії;
4 +1 = 5 при його 2-й стратегії;
2 +0 = 2 при його 3-й стратегії.
З усіх сумарних виграшів найбільшим є 5, який виходить при 2-й стратегії гравця 1. Значить, у цій партії він повинен вибрати саме цю стратегію.
При 1-й стратегії гравця 1 гравець 2 програє 4, 1, 2 відповідно 1-й, 2-й, 3-й його стратегіям, а сумарний програш за обидві партії складе:
4 +4 = 8 при його 1-й стратегії;
1 +1 = 2 при його 2-й стратегії;
2 +2 = 4 при його 3-й стратегії.
Всі отримані дані занесемо в таблицю. У стовпець u ставиться найбільший сумарний виграш гравця 1 за дві партії, поділений на кількість партій, тобто 5 / 2; в стовпець w ставиться найменший сумарний програш гравця 2, поділений на кількість партій, тобто 2 / 2; в стовпець n ставиться середнє арифметичне цих значень, тобто 7 / 2.

но-заходів пар тії	стратегія друга гравця	виграш гравця 1 при його стратегіях			стратегія перший гравця	програш гравця 2 при його стратегіях			u	w	n
		1	2	3		1	2	3
1 2	1 2	0 3	4 5	2 2	2 2	4 8	1 2	2 4	4 5 / 2	1 2 / 2	5 / 2 7 / 2

У третій партії гравець 2 вибирає свою 2-у стратегію, так як з усіх сумарних програшів найменшим є 2.
Таким чином, продовжуючи цей процес далі, складемо таблицю розігрування гри за 20 ітерацій (партій).

но-заходів пар тії	Страте- гія друга гравця	виграш гравця 1 при його стратегіях			Страте- гія перший гравця	програш гравця 2 при його стратегіях			u	w	n
		1	2	3		1	2	3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	1 2 2 2 3 3 1 3 3 3 3 3 2 2 2 2 2 2 2 3	0 3 6 9 10 11 11 12 13 14 15 16 19 22 25 28 31 34 37 38	4 5 6 7 9 11 15 17 19 21 23 25 26 27 27 29 30 31 32 34	2 2 2 2 5 8 10 13 16 19 22 25 25 25 25 25 25 25 25 28	2 2 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1	4 8 8 8 8 8 12 16 20 24 28 32 36 40 44 48 48 48 48 48	1 2 5 8 11 14 15 16 17 18 19 20 21 22 23 24 27 30 33 36	2 4 5 6 7 8 10 12 14 16 18 20 22 24 26 28 29 30 31 32	4 5 / 2 6 / 3 9 / 4 10 / 5 11 / 6 15 / 7 17 / 8 19 / 9 21/10 23/11 25/12 26/13 27/14 27/15 29/16 31/17 34/18 37/19 38/20	1 2 / 2 5 / 3 6 / 4 7 / 5 8 / 6 10 / 7 12 / 8 14 / 9 16/10 18/11 20/12 21/13 22/14 23/15 24/16 27/17 30/18 31/19 32/20	5 / 2 7 / 2 11 / 6 15 / 8 17/10 19/12 25/14 27/16 33/18 37/20 41/22 45/24 47/26 49/28 50/30 53/32 58/34 64/36 68/38 70/40

З таблиці видно, що в 20-ти програних партіях стратегії 1, 2, 3 для другого гравця зустрічаються відповідно 2, 10, 8 разів, отже, їх відносні частоти рівні 2 / 20, 10/20, 8 / 20. Стратегії 1, 2, 3 для гравця 1 зустрічаються відповідно 8, 12, 0 раз, отже, їх відносні частоти рівні 8 / 20, 12/20, 0, а наближене значення ціни гри одно 70/40.
Таким чином, отримали наближене рішення гри: x ²⁰ = (1 / 10, 1 / 2, 2 / 5), y ²⁰ = (2 / 5, 3 / 5, 0), n = 1,57.
Такий ітеративний процес веде гравців до мети повільно. Часто для отримання оптимальних стратегій, що дають гравцям виграш, доводиться проробляти сотні ітерацій. При цьому швидкість збіжності помітно погіршується із зростанням розмірності матриці і зростанням числа стратегій гравців. Це також є наслідком не монотонності послідовностей і . Тому, практична цінність цього методу має місце, коли обчислення проводяться на досить швидкодіючих обчислювальних машинах. Але поряд з таким недоліком можна виділити і достоїнства методу ітерацій:
1. Цей метод дає можливість знайти орієнтовне значення ціни гри і наближено обчислити оптимальні стратегії гравців.
2. Складність і обсяг обчислень порівняно слабко зростають у міру збільшення числа стратегій гравців (m і n).
Для розглянутого алгоритму наведена реалізація на мові Pascal (див. додаток).
§ 3. Монотонний ітеративний алгоритм розв'язання матричних ігор
Пропонований для розгляду алгоритм реалізується тільки для одного гравця на відміну від першого, який працює для двох гравців. Алгоритм дозволяє знаходити точно і наближено оптимальну стратегію гравця 1 і значення ціни гри n. За допомогою алгоритму можна отримати задану точність рішення, причому число кроків, необхідних для досягнення результатів, слабо залежить від розмірності матриці виграшів.
Особливість цього алгоритму у здатності генерувати строго монотонно зростаючу послідовність оцінок ціни гри, що не властиво раніше запропонованого алгоритму.
Розглянемо змішане розширення = (X, Y, K) матричної гри Г _А з матрицею А розміру (m'n). Процес розігрування гри складається з декількох кроків. Нехай кожен з гравців має кінцеве число стратегій.
Введемо наступні позначення:
а _i - i-й рядок матриці виграшів;
x ^N = (x ₁ ^N, x ₂ ^N, ..., x _m ^N) ÎX - m-мірний вектор, наближення оптимальної стратеги першого гравця на N-кроку (N-номер кроку);
c ^N = ( )-N-мірний вектор, який визначає середній накопичений виграш на N-кроку.
Задамо початкові умови. Нехай на 0-кроці з ⁰ = , X ⁰ = (0, ..., 1, ..., 0), де 1 займає i _0-у позицію.
Визначимо ітеративний процес наступним чином: за відомим векторах x ^{N -1,} c ^{N -1}   знаходимо вектори x ^N і c ^N, які обчислюються за такими формулами:

де параметр 0 £ e _N £ 1, а вектори вводяться далі.
Як зазначалося, вектор з ^N визначає середній накопичений виграш гравця 1 на N кроці. Компоненти цього вектора - це числа. У гіршому випадку гравець 1 може отримати мінімальне з цих чисел. Приймемо його за нижню оцінку ціну гри, яку позначимо:
. (4)
Запам'ятаємо безліч індексів J ^N-1 = ( ), (K <n), на яких буде досягається цей мінімум, тобто
.
Далі розглянемо подигру Г ^N ігри    Г _А з матрицею виграшів А ^N = { }, I = 1, ..., m, j ^{N -1} ÎJ ^{N -1.} Матриця виграшів складається із стовпців даної матриці, номери яких визначаються безліччю індексів J ^{N -1.} У цій подигре Г ^N знаходимо одну з оптимальних змішаних стратегій гравця 1: .
Після знаходження , Знаходимо вектор за правилом:
.
І розглянемо гру (2'n), в якій у гравця 1 дві чисті стратегії, а у гравця 2 - n чистих стратегій. Ця гра задається матрицею , Розв'язуючи яку, знаходимо ймовірність використання гравцем 1 своєї стратегії. Це дає нам коефіцієнт e _N.
Далі обчислюємо x ^N, з ^N і переходимо до наступного кроку. Процес продовжуємо до тих пір, поки не виконається рівність e _N = 0, тому що по теоремі про Мінімакс , А їх рівність (що й потрібно) досягається в цьому випадку, або поки не буде досягнута необхідна точність обчислень.
Збіжність алгоритму гарантується теоремою.
Теорема. Нехай {x ^N}, {n ^N} - послідовності, що визначаються рівностями (3), (4). Тоді справедливі наступні твердження:
1. тобто послідовність {n ^{N -1}} строго монотонно зростає.
2.
3. , Де x ^* Î X * - оптимальна стратегія гравця 1.
Докази цієї теореми досить рутинно. Його можна подивитися в [15].
Розглянемо застосування цього алгоритму до вирішення конкретного завдання.
Приклад. Вирішити гру з матрицею А = .
Ітерація 0. 1. Нехай гравець 1 вибрав свою 1-у стратегію, тобто А ⁰ = [0, 1, 2]. Тоді за початкові умови приймемо такі: x ⁰ = (1, 0, 0) - наближення оптимальної стратегії гравця 1; c ⁰ = a ₁ = (0, 1, 2) - можливий виграш гравця 1.
Знайдемо безліч індексів , На яких гравець 1 може отримати, в гіршому випадку, найменший виграш: , Значить безліч індексів J ⁰ = {1}. Для цього індексу виграш дорівнює 0. Це є значення нижньої оцінки ціни гри, тобто .
2. На цьому кроці визначимо, користуючись початковими значеннями, компоненти векторів . Для цього розглянемо подигру . Для цієї подигри оптимальною стратегією гравця 1 буде його друга стратегія, так як вона принесе йому найбільший виграш.
Позначимо її через : = (0, 1, 0). Знаючи , Можемо обчислити = 0а ₁ +1 а ₂ +0 а ₃ = а ₂ = (4, 2, 1).
3. Знайдемо e _1. Для цього розглянемо подигру (2'3) з матрицею . Вирішуючи матрицю графічним способом, отримуємо, що e ₁ = ₁ / 2.
4. Проведені обчислення дозволяють знайти значення векторів x ^1, c ^1:
  x ¹ = ¹ / 2 x ⁰ +1 / 2 = 1 / 2 (1, 0, 0) +1 / 2 (0, 1, 0) = (1 / 2, 1 / 2, 0);
  c ¹ = ¹ / 2 c ⁰ +1 / 2 = 1 / 2 (0, 1, 2) +1 / 2 (4, 2, 1) = (2, 3 / 2, 3 / 2).
Ітерація 1. Оскільки e ₁ не дорівнює 0, то процес продовжується далі. Тепер за початкові умови приймемо знайдені значення векторів x ^1, c ^1. З їх допомогою обчислюємо , Які з більшою точністю будуть близькі до дійсних оптимальним стратегіям гравця 1.
1. Отже, нехай x ¹ = (1 / 2, 1 / 2, 0), c ¹ = (2, 3 / 2, 3 / 2).
Знайдемо безліч індексів , На яких гравець 1 може одержати найменший виграш: , Значить, J ¹ = {2,3}. Для цих індексів виграш дорівнює 3 / 2. Це є значення нижньої оцінки ціни гри, тобто . Зауважимо, що .
2. Далі знайдемо компоненти векторів . Для цього розглянемо подигру . У силу симетричності матриці її рішенням буде вектор (1 / 2, 1 / 2), т. е. 1 / 2 a ₁ +1 / 2 a ₂ +0 a ₃ =
= (4 / 2, 3 / 2, 3 / 2).
3. Обчислимо коефіцієнт e _2. Для цього вирішимо подигру (2'3): . Стратегії гравців збігаються, тому e ₂ = 0. У цьому випадку ціна гри збігається зі своїм нижнім значенням, тобто . Повертаємося до попереднього кроку.
Отже, оптимальною стратегією гравця 1 є x ^* = x ¹ = (1 / 2, 1 / 2, 0) і . Задача розв'язана.
На перший погляд алгоритм практично важко реалізувати, тому що не відомо, якого розміру буде отримана матриця для подигри Г ^N. Але насправді з вірогідністю 1 на кожному кроці доведеться вирішувати подигру розміру не більше ніж m'2. [9]
Інженерами-програмістами алгоритм був реалізований на мові програмування Фортран-IV. Обчислювальні експерименти, проведені на ЕОМ ЄС-1030, показали, що для ігор розмірності від 25'25 до 100'100, елементи, матриці виграшів яких були заповнені випадковими числами, алгоритм дозволяє знайти шукане наближення за 100-1000 ітерацій, причому їх число слабо залежить від розміру матриці. Для вирішення однієї задачі машина витрачає не довше 8 хвилин. Ними ж були розроблені різні модифікації алгоритму. [9]

Додаток
У додатку наведена реалізація ітеративного методу Брауна-Робінсона рішення матричних ігор на мові програмування Turbo Pascal 7.0.
Користувач вводить матрицю виграшів розміру mЧn, де m ≥ 3, n ≥ 3.
Далі машина запитує інформацію про те, хто з гравців починає гру, яку стратегію він вибирає і кількість ітерацій.
На дисплеї виводиться таблиця розігрування гри за певне число ітерацій.
program br;
uses crt;
const matr1: array [1 .. 3,1 .. 3] of byte = ((0,4,2),
(3,1,0),
(1,2,3)); {Початкова матриця}
var
matr: array [1 .. 10,1 .. 10] of integer; {Матриця, введена користувачем}
win_one: array [0 .. 150,1 .. 10] of word; {Масив для виграшів ігор .1}
win_two: array [0 .. 150,1 .. 10] of word; {Масив для виграшів ігор .2}
max, min: integer;
a, i, j, m, n, pl, st, st1, st2, kl: byte;
nol, otr: boolean;
function igr _ one: byte; {Функція визначення наступного}
var a1, a2, max: integer; {ходу для гравця 1}
begin
max: = win_one [a, 1];
igr_one: = 1;
if pl = 1 then a2: = m else a2: = n;
for a1: = 1 to a2 do if win_one [a, a1]> max then begin
max: = win_one [a, a1];
igr_one: = a1;
end;
end;
function igr_two: byte; {Функція визначення наступного}
var a1, a2, min: integer; {ходу для гравця 2}
begin
min: = win_two [a, 1];
igr_two: = 1;
if pl = 1 then a2: = n else a2: = m;
for a1: = 1 to a2 do if win_two [a, a1] <min then begin
min: = win_two [a, a1];
igr_two: = a1;
end;
end;
begin
clrscr;
writeln ('Ітеративний метод Брауна-Робінсона.');
writeln ('Матриця користувача? (y / n)');
if (readkey = 'y') or (readkey = 'Y') then begin {Матриця з пам'яті або вводить користувач}
write ('Введіть розміри матриці:');
readln (n, m); {Введення кількості рядків і стовпців}
writeln ('Введіть', n, 'рядки по', m, 'елементів:');
nol: = true;
otr: = false;
min: = 0;
for j: = 1 to n do for i: = 1 to m do begin {Введення елементів матриці}
read (matr [i, j]);
if matr [i, j] <> 0 then nol: = false; {Установка прапора, що не всі елементи рівні 0}
if matr [i, j] <0 then otr: = true; {Установка прапора наявності негативних елементів}
if matr [i, j] <min then min: = matr [i, j]; {Визначення мінімального елемента}
end
end else begin {Інакше беремо матрицю з константи}
n: = 3; m: = 3;
for i: = 1 to m do for j: = 1 to n do matr [i, j]: = matr1 [i, j];
end;
clrscr;
writeln ('Ітеративний метод Брауна-Робінсона.');
if nol then writeln ('Всі елементи матриці дорівнюють 0!') else begin {якщо встановлений прапор нуля, то алгоритм не працює}
if otr then for j: = 1 to n do for i: = 1 to m do matr [i, j]: = matr [i, j]-min; {якщо є негативні елементи,}
writeln ('Початкова матриця:'); {Висновок остаточної матриці}
for j: = 1 to n do begin
for i: = 1 to m do write (matr [i, j]: 4);
writeln;
end;
write ('Який гравець почне гру?'); {Вод стартових значень}
readln (pl);
write ('Яку стратегію обере', pl, 'гравець?');
readln (st);
write ('Кількість ітерацій?');
readln (kl);
a: = 1; {заголовок таблиці}
writeln ('№ стор виграш 1-го ігор. стор виграш 2-го ігор. VW Y');
repeat
write (a: 2, st: 6, ''); {формування таблиці: номер ітерації, стратегія 1ігр.}
if pl = 2 then begin
for i: = 1 to n do begin
win_one [a, i]: = matr [st, i] + win_one [a-1, i]; {формування матриці виграшів 1 ігор.}
write (win_one [a, i]: 4); {висновок на екран}
end;
st1: = igr_one; {визначення відповідної стратегії 2 ігор.}
gotoxy (32, wherey);
write (st 1:10, ''); {висновок на екран}
for i: = 1 to m do begin
win_two [a, i]: = matr [i, st1] + win_two [a-1, i]; {формування матриці виграшів 2 ігор.}
write (win_two [a, i]: 4); {висновок на екран}
end;
gotoxy (64, wherey);
write (win _ one [a, st 1]: 4); {висновок найбільшого сумарного виграшу 1 ігор.}
st: = igr_two; {визначення відповідної стратегії 1 ігор.}
write (win_two [a, st]: 4); {висновок найбільшого сумарного виграшу 2 ігор.}
write ((win_one [a, st1] + win_two [a, st]) / (a * 2): 6:2); {наближене значення ціни ігри}
end
else
begin
for i: = 1 to m do begin
win_one [a, i]: = matr [i, st] + win_one [a-1, i]; {формування матриці виграшів 1 ігор.}
write (win_one [a, i]: 4);
end;
st1: = igr_one; {визначення відповідної стратегії 2 ігор.}
gotoxy (32, wherey);
write (st1: 10, '');
for i: = 1 to n do begin
win_two [a, i]: = matr [st1, i] + win_two [a-1, i]; {формування матриці виграшів 2 ігор.}
write (win_two [a, i]: 4);
end;
gotoxy (64, wherey);
write (win _ one [a, st 1]: 4); {висновок найбільшого сумарного виграшу 1 ігор.}
st: = igr_two; {визначення відповідної стратегії 1 ігор.}
write (win_two [a, st]: 4); {висновок найбільшого сумарного виграшу 2 ігор.}
write ((win_one [a, st1] + win_two [a, st]) / (a * 2): 6:2); {наближене значення ціни ігри}
end;
a: = a +1; {збільшення лічильника ітерацій}
writeln;
until a = kl +1;
end;
readln;
readln;
end.

Список літератури
1. Бєлєнький В.З. Ітеративні методи в теорії ігор і програмування. М.: «Наука», 1977
2. Блекуелл Д.А. Теорія ігор і статистичних рішень. М., Вид. іноземної літератури, 1958
3. Вентцель Є.С. Елементи теорії ігор. М., Фізматвид, 1961
4. Вілкас Е.І. Оптимальність в іграх і рішеннях. М.: «Наука», 1986
5. Воробйов І.М. Математична теорія ігор. М.: «Знання», 1976
6. Давидов Е.Г. Методи і моделі теорії антагоністичних ігор. М.: «Вища школа», 1990
7. Дрешер М. Стратегічні ігри. Теорія і додатки. М., 1964
8. Дослідження операцій в економіці / Н.Ш. Кремер, Б.А. Путко, І.М. Тришин, М.М. Фрідман. М.: «Банки і біржі», Юніті, 1997
9. Ітеративний алгоритм рішення матричних ігор / / Доповіді Академії наук СРСР, тому 238, № 3, 1978
10. Карлін С. Математичні методи в теорії ігор, програмуванні та економіці. М.: «Світ», 1964
11. Крапівін В.Ф. Теоретико-ігрові методи синтезу складних систем у конфліктних ситуаціях. М.: «Радянське радіо», 1972
12. Крушевський А.В. Теорія ігор: [Навчальний посібник для вузів]. Київ: «Вища школа», 1977
13. Льюїс Р., Райфа Х. Ігри та рішення. М., 1961
14. Морозов В.В., Старев А.Г., Федоров В.В. Дослідження операцій в задачах і вправах. М.: «Вища школа», 1996
15. Матричні ігри. [Збірник переказів]. Під ред. Воробйова І.М. М., Фізматвид, 1961
16. Оуен Г. Теорія ігор. [Навчальний посібник]. М.: «Світ», 1973
17. Петросян Л.А., Зенкевич Н.А., Семен Є.А. Теорія ігор. М., 1989
18. Шкільна енциклопедія математика. Ред. С. М. Нікольський, М.: 1996, с. 380