МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Вятському ДЕРЖАВНИЙ ГУМАНІТАРНИЙ УНІВЕРСИТЕТ
Математичний факультет
Кафедра алгебри та геометрії
Випускна кваліфікаційна робота
Методи наближеного рішення матричних ігор
Виконала студентка V курсу
математичного факультету
Вєтошкіна Е. Н.
______________ / Підпис /
Науковий керівник:
к. ф.-м. н., доцент, Ковязіна Є. М.
______________ / Підпис /
Рецензент:
к. ф.-м. н., доцент, Караулов В.М.
______________ / Підпис /
Допущена до захисту в ГАК
Зав. кафедрою __________________ Вечтомов Є. М.
«___» __________ 2003
Декан факультету _______________ Варанкіна В. І.
«___» __________ 2003
Кіров
2003
ЗМІСТ
Введення ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 3
§ 1. Основні поняття ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
§ 2. Ітеративний метод Брауна-Робінсона ... ... ... ... ... ... ... ... ... ... ... ... 10
§ 3. Монотонний ітеративний алгоритм рішення матричних ігор ... 16
Додаток ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .21
Список літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 24
Введення
«Теорія ігор - розділ математики, предметом якого є вивчення математичних моделей прийняття оптимальних рішень в умовах конфлікту ...». [17]
Математична теорія ігор здатна не тільки вказати оптимальний шлях до вирішення деяких проблем, а й прогнозувати їх результат. Матричні ігри серйозно вивчаються фахівцями, так як вони досить прості і до них можуть бути зведені ігри загального вигляду. Тому теорія матричних ігор добре розвинена, існують різні методи пошуку рішення ігор.
Але в більшості випадків рішення матричних ігор являє собою складний і громіздкий процес. Є приклади, коли навіть для матриць розміру 3 '3, процес пошуку рішення досить трудомісткий.
Крім того, виграші гравців у кожній ситуації не завжди визначаються точними вимірами. В процесі збору даних про досліджуваному явищі, аналізу цих даних і введення при побудові моделі різних припущень накопичуються помилки. Вони ж можуть виражатися числами в матриці виграшів. Тому точність у визначенні значення гри та оптимальних стратегій гравців виправдана не завжди.
А також, слід зауважити, що похибка в оцінці гравцем свого виграшу не може привести до практично серйозних наслідків і невелике відхилення гравця від оптимальної стратегії не тягне за собою істотної зміни в його виграші.
Тому виникає потреба в розробці чисельних методів розв'язання матричних ігор. В даний час в теорії ігор відомі кілька способів наближеного рішення матричних ігор.
Мета випускної кваліфікаційної роботи вивчити деякі методи наближеного рішення матричних ігор, обгрунтувати їх алгоритми, і, по можливості, реалізувати на мові програмування.
Робота складається з вступу, трьох параграфів і програми, в якому приведена програма на мові Turbo Pascal, що дозволяє знаходити наближене рішення матричної гри.
У першому параграфі наведені основні поняття і твердження теорії матричних ігор.
Параграф другий присвячений викладу наближеного розв'язання гри методом Брауна-Робінсона (метод фіктивного розігрування) і його обгрунтування. Наведено приклад застосування алгоритму для конкретної матричної гри.
У третьому параграфі розглянуто ще один метод - монотонний ітеративний алгоритм наближеного рішення матричних ігор.
§ 1. Основні поняття
Будемо розглядати тільки парні антагоністичні ігри, тобто ігри в яких беруть участь тільки два гравці - дві протиборчі сторони і виграш одного з гравців дорівнює програшу іншого. Крім того, будемо вважати, що кожен гравець має лише кінцеве число стратегій:
U 1 = {a 1, a 2 ,..., a m} - безліч стратегій першого гравця;
U 2 = {b 1, b 2, ... b n} - безліч стратегій другого гравця.
Будемо називати ці стратегії чистими на відміну від змішаних, які будуть введені далі.
Безліч U 1 × U 2 - декартовій твір множин стратегій гравців називається безліччю ситуацій у грі. Для кожної ситуації повинен бути визначений підсумок гри. Оскільки гра антагоністична досить визначити виграш а одного з гравців, скажімо першого. Тоді виграш другого гравця буде дорівнювати (- а). Таким чином, маємо матрицю виграшів першого гравця (для другого гравця матриця виграшів-А):
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 / = bn + 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 А / = an А + 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-й стратегією. Занесемо дані в таблицю.
но-заходів пар тии |