124

АНАЛІЗ КОНФЛІКТНИХ СИТУАЦІЙ. ЕЛЕМЕНТИ ТЕОРІЇ ІГОР

Практическая работа

Информатика, кибернетика и программирование

В теорії ігор супротивники – гравці. Кожен з гравців має деяку множину (скінченну або нескінченну) можливих дій (стратегій). Результати в грі задаються функціями, що залежать від стратегій кожного з гравців. Гра з двома гравцями, у якій виграш одного з гравців дорівнює програшу другого, називається грою з нульовою сумою. У такій грі достатньо задати результати у вигляді платежів одного з гравців.

Украинкский

2012-11-14

295.5 KB

22 чел.

Практична робота №7

АНАЛІЗ КОНФЛІКТНИХ СИТУАЦІЙ.
ЕЛЕМЕНТИ ТЕОРІЇ ІГОР

Мета роботи: засвоїти та навчитись використовувати методи теорії матричних ігор для аналізу конфліктних ситуацій.

7.1. Короткі теоретичні відомості

Розглянемо випадок, коли рішення приймаються супротивниками, що намагаються одержати прибутки (оптимізувати рішення) за рахунок суперника. Подібні ситуації називаються конфліктними. Вони є предметом вивчення теорії ігор.

В теорії ігор супротивники – гравці. Кожен з гравців має деяку множину (скінченну або нескінченну) можливих дій (стратегій). Результати в грі задаються функціями, що залежать від стратегій кожного з гравців. Гра з двома гравцями, у якій виграш одного з гравців дорівнює програшу другого, називається грою з нульовою сумою. У такій грі достатньо задати результати у вигляді платежів одного з гравців.

ПРИКЛАД 7.1.

Гра двох осіб з нульовою сумою. Гра на співпадіння сторін монети. Гравці А та В вибирають герб (Г) або решітку (Р). Якщо обидва гравці обрали одне й те саме (тобто Г та Г або Р та Р), то А одержує 1 грн. від В, в противному випадку А платить В. Отже, кожен з гравців має дві стратегії (Г або Р). Оскільки гра з нульовою сумою, то ми по виграшу гравця А завжди можна визначити програш гравця В і навпаки. Тому для задання всіх можливих ситуацій в цій грі досить задати матрицю 2х2, яка представляє, скажімо, виграш гравця А (див. табл. 7.1).

Таблиця 7.1

Матриця виграшів гравця А.

Гравець В

Гравець А

1

–1

–1

1

Оптимальний розв’язок у грі може вимагати від гравців чистих стратегій (тобто Г або Р), або комбінацій чистих стратегій (змішані стратегії).

7.1.1. Оптимальні розв’язки у іграх двох осіб з нульовою сумою

В практичні роботі № 6 був розглянутий випадок прийняття рішень в умовах невизначеності за допомогою максимінного (мінімаксного) критерію. Але особі, що приймає рішення, не протистояв “розумний” супротивник. Тому обрання мінімаксного критерія було досить песимістичним. Ми припускали, що на будь-яку нашу дію (стратегію) супротивник відповість найгіршим для нас способом. У випадку гри ситуація саме така. Тому ми повинні користуватися максимінним (мінімаксним) критерієм. Виходячи з цього критерію ми обираємо найкращій з найгірших для нас результатів. Так само діє наш супротивник. Кажуть, що оптимальне рішення гри досягнуто, якщо жодному з гравців невигідно змінити свою стратегію. Тоді гра стабільна або знаходиться у стані рівноваги.

ПРИКЛАД 7.2.

Таблиця 7.2

Розв’язок гри в чистих стратегіях

Гравець В

Гравець А

8

2

9

5

2

5

6

5

7

18

5

7

3

– 4

10

– 4

8

5

9

18

5

Стратегія, що обрана гравцем А, називається максимінною стратегією, а гравцем Вмінімаксною стратегією. Значення виграшу, який відповідає максимінній стратегії називається максимінним (нижнім) значенням гри. Аналогічно, значення програшу гравця В, який відповідає мінімаксній стратегії, називається мінімаксним (верхнім) значенням гри.

Можна показати, що нижнє значення гри не перевищує верхнього значення гри.

Якщо має місце рівність

,

то відповідні чисті стратегії називають оптимальними. А про гру кажуть, що вона має сідлову точку. ”Оптимальність” стратегії означає, що жодному з гравців не вигідно міняти свою стратегію, оскільки інший гравець може відповісти вибором іншої стратегії, яка погіршить результат гри для першого гравця.

7.1.2. Змішані стратегії

Із існування сідлової точки безпосередньо витікає існування оптимальних чистих стратегій. Розглянемо гру, яка не має сідлової точки.

Таблиця 7.3

Гра, яка не має сідлової точки

В

А

5

–10

9

0

–10

2

6

7

8

1

1

8

7

15

2

2

3

4

–1

4

–1

8

7

15

4

4

Тобто

= 2,

а

= 4.

У цій грі не існує стратегій, від яких не вигідно відхилятись, кожен гравців може покращити своє становище. Наприклад, А вибрав стратегію 3 (виграш 2), тоді В вибрав стратегію 4. Тоді для А краще обрати також стратегію 4 (виграш 4). В цьому випадку кажуть, що гра нестабільна. Користуючись чистими стратегіями ми не можемо одержати оптимальний розв’язок гри. Тому виникає ідея використання змішаних стратегій. Кожен гравець обирає не одну чисту стратегію, а будь-яку з можливих чистих стратегій з різними ймовірностями.

Нехай  та  набори ймовірностей, з якими відповідно А і В можуть обирати свої чисті стратегії. Події обрання стратегій утворюють повні групи подій:

Запишемо тепер матрицю виграшів у вигляді табл. 7.4. Підхід до розв’язання такої гри ґрунтується також на критерії мінімаксу. Єдина різниця у тім, що А обирає стратегію так, щоб максимізувати найменший виграш, який очікується, тоді як В обирає найменший програш, який очікується.

Таблиця 7.4

Матриця гри mn

А

В

Математичний запис критерію мінімаксу у випадку змішаних стратегій. 

Гравець А обирає стратегію , виходячи з умови:

– максимінного платежу.

Гравець В обирає стратегію , виходячи з умови:

– мінімаксного платежу.

Якщо  та  оптимальні змішані стратегії для кожного з гравців, то оптимальне значення гри визначається за формулою

.

Знайти оптимальні стратегії та значення гри можна в результаті розв’язування відповідної задачі лінійного програмування.

Будемо шукати оптимальну змішану стратегію для гравця А. Нехай матриця доходів для гравця А задана в табл. 7.4.

Гравець А може обирати свої стратегії з ймовірностями:  відповідно. При виборі гравцем В своєї стратегії, виграш, який очікується, гравцем А визначається за формулою:. Згідно з максимінним критерієм змішану стратегію треба знайти за умови:

.

Поставимо цю задачу, як задачу лінійного програмування. Нехай

.

Нам треба обрати такий х*, щоб величина  набула б максимального значення. Отже,

,

при умові

;

Для зручності спростимо цю задачу. Розділимо ліву і праву частину обмежень на . Для того щоб знаки не змінилися треба забезпечити умову > 0. Це не завжди так, але легко забезпечити цю умову штучним способом. Відомо, що значення гри не може бути меншим, ніж нижнє значення гри, тобто . Якщо нижнє значення гри додатне, то  гарантовано більше нуля. Якщо не додатне, то додавши до елементів матриці необхідне число К (більше модуля нижнього значення гри), зробимо його додатнім. Очевидно, що ми одержимо при цьому нову задачу. Розв’язавши її, розв’язок вихідної одержимо, віднявши від розв’язку модифікованої задачі число К.

Отже, ділимо ліву і праву частину обмежень на . Тоді обмеження задачі приймуть вид:

;

;

.

Введемо нові позначення  і наша задача лінійного програмування остаточно прийме вигляд:

;

;

.

Аналогічно для відшукання стратегії гравця В може бути розглянута відповідна задача лінійного програмування.

Для цього запишемо умову оптимальності:

.

Нехай

.

Тоді задача лінійного програмування приймає вигляд

  min,

;

.

Після аналогічного введення нових позначень одержимо:

;

.

Ця пара задач лінійного програмування  утворює двоїсту пару. Розв’язок однієї задачі дорівнює розв’язку іншої у тому сенсі, що  значення оптимуму функції мети в обох задачах є рівними.

7.1.3. Графічний розв’язок ігор (m 2) або (2 n)

Графічний метод можна застосовувати, якщо один з гравців має лише дві стратегії (табл.7.5).

Таблиця 7.5

Матриця гри виду (2 n)

А

В

Припустимо, що ця гра не має сідлової точки. Запишемо у табл. 7.5 виграші, які очікуються, гравця А для кожної з чистих стратегій гравця В, враховуючи умову .

Таблиця 7.6

Виграші, які очікуються, гравця А в залежності від стратегій гравця В

Чисті стратегії гравця В

Виграші, які очікуються, гравця А

1

2

3

4

n

З табл. 7.6 видно, що виграш, який очікується, лінійно залежить від . У відповідності з критерієм максиміну гравець А повинен обрати  (тобто обрати ймовірність вибору першої стратегії) так, щоб максимізувати свій мінімальний виграш, який очікується. Цього можна досягти побудовою прямих ліній, які відповідають лінійним функціям від .

ПРИКЛАД 7.4.

Таблиця 7.7

Матриця гри 24

В

min

Max

А

2

2

3

–1

–1

4

3

2

6

2

2

max

4

3

3

6

min

3

Гра не має сідлової точки. Виграші, які очікуються, гравця А відповідно до чистих стратегій гравця В у табл. 7.8:

Таблиця 7.8

Виграші гравця А в залежності від стратегій В

Стратегії гравця В

Виграші, які очікуються, гравця А

1

2

3

4

Будуємо прямі, відповідно до табл. 7.8. (рис. 7.1).

Рис. 7.1. Виграші, які очікуються, гравця А в залежності від

Максимін досягається при . В цій точці перетинаються три прямі – 2, 3, 4. З цього випливає, що у гравця В оптимальна стратегія  і являє собою сукупність трьох стратегій – 2, 3, 4. Першу стратегію ми зовсім не використовуємо (). Однак точка максиміну цілком визначається перетином двох прямих. Тобто з боку гравця В ми можемо забезпечити  оптимальну стратегію, як сукупність лише двох чистих стратегій. З наших трьох стратегій можна одержати три пари стратегій (2, 3), (3, 4), (2, 4). Оптимальним стратегіям гравця В відповідають лише пари стратегій, яким відповідають прямі з протилежними нахилами. Тоді з наведених пар пару (2, 4) треба виключити. Дійсно, якщо ми розглянемо лише стратегії 2 і 4, то точкою максиміну буде зовсім не точка А, а точка Т. Залишились пари (2, 3) та (3, 4). Будь-яка з них визначає точку максиміну.

Розглянемо пару (2, 3), тобто = 0, = 0. Залишається визначити  та . Очевидно, що = 1 – .  Результати розгляду в табл.7.9.

Таблиця 7.9

Програші, які очікуються, гравця В в залежності від стратегій гравця А за умови = 0, = 0

Стратегії гравця А

Програші, які очікуються, гравцем В

1

2+2+3–=2+3= –+3

2

4+3+2+6=+2

– визначається з рівності

+ 3 =  + 2  = 1/2  = 1/2.

Аналогічно, розглянемо пару (3, 4). Тоді  = 0, = 0. Визначимо , . Очевидно, що = 1 – . Результати розгляду в табл.7.10.

Таблиця 7.10

Програші, які очікуються, гравця В в залежності від стратегій гравця А за умови  = 0, = 0

Стратегії гравця А

Програші, які очікуються, гравцем В

1

4 – 1

2

–4 + 6

Отже, маємо 4 – 1 = –4 + 6. Звідки  = 7/8;    = 1/8.

Значення гри  для пари стратегій (2, 3) і пари (3, 4), очевидно, однакове, визначається точкою максиміну і дорівнює 5/2.

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

ПРИКЛАД 7.5.

Розглянемо наступну гру виду (4х2), табл. 7.11.

Таблиця 7.11

Матриця гри (4х2)

В

А

2

4

2

3

3

2

–2

6

Гра не має сідлової точки.

Нехай і =1– – змішані стратегії гравця В. Тоді:

Чисті стратегії гравця А

Програші, які очікуються, гравця В

1

–2+4

2

–+3

3

+2

4

–8+6

Точка мінімаксу визначаєтьсяі як найнижча точка огинаючої зверху (див. рис.7.2).

Значення отримуємо як точку перетину прямих 1 і 3 (рис.7.2). Це дає  = 2/3 і = 8/3. Оскільки  є точка перетину прямих 1 і 3, то =  = 0  .

Чисті стратегії гравця А

Програші, які очікуються, гравця В

1

–+3

2

2+2

Рис. 7.2. Програші, які очікуються, гравця В в залежності від

– + 3 = 2 + 2;

= 1/3  = 2/3.

Оптимальна стратегія гравця А буде:

=1/3;  =0; =2/3; =0.

Значення гри: 8/3.

7.2. Порядок виконання роботи

  1.  Ознайомитись з теоретичними відомостями.
    1.  Для заданих у варіанті індивідуального завдання даних виграшу гравця А розв’язати гру графічним методом.
      1.  Для заданих у варіанті індивідуального завдання даних про виграші гравця А розв’язати гру симплекс методом.
      2.  Оформити звіт з практичної роботи.


7.3. Варіанти індивідуальних завдань

  1.  Вихідні дані для задачі п. 7.2.2

Варіант №1

В

А

–3

4

2

–1

5

–6

–1

3

Варіант №2

В

А

3

–1

–3

4

–5

2

2

–3

Варіант №3

В

А

–3

5

10

–1

2

–2

–1

3

Варіант №4

В

А

–1

4

2

–3

4

–3

–1

2

Варіант №5

В

А

–1

4

2

–3

4

–6

–1

3

Варіант №6

В

А

3

–2

–1

1

4

–4

–1

3

Варіант №7

В

А

–2

7

4

–1

–2

3

–1

3

Варіант №8

В

А

1

–2

2

–1

–2

4

–1

3

Варіант №9

В

А

3

–2

–4

1

5

–2

–1

3

Варіант №10

В

А

–3

4

2

–1

3

–3

–1

3

  1.  Вихідні дані для задачі п.7.2.3

Варіант №1

В

А

–3

2

–1

3

–1

4

–4

2

3

Варіант №2

В

А

3

–2

1

–3

1

4

4

2

–3

Варіант №3

В

А

–1

3

–2

2

–4

3

–1

2

3

Варіант №4

В

А

4

–2

–3

–1

–3

4

–4

2

3

Варіант №5

В

А

–3

2

1

1

–1

4

2

3

–3

Варіант №6

В

А

1

2

–1

3

–1

2

–4

2

3

Варіант №7

В

А

–3

2

1

4

–1

–3

–2

2

2

Варіант №8

В

А

–3

3

–1

4

–1

4

–4

2

-3

Варіант №9

В

А

–3

2

2

3

–1

3

2

2

–3

Варіант №10

В

А

–3

4

–1

5

–1

4

–4

2

–3


7
.4. Зміст звіту

  1.  Назва та мета роботи.
    1.  Короткі теоретичні відомості.
      1.  Умови задачі та її розв’язок.
      2.  Короткі висновки.

7.5. Контрольні запитання

7.5.1. Що є предметом вивчення теорії ігор?

7.5.2. Що таке розв’язок гри в чистих стратегіях?

7.5.3. Чи завжди існує розв’язок гри в змішаних стратегіях?

7.5.4. Які ігри можна розв’язати графічним методом?

PAGE 85


 

А также другие работы, которые могут Вас заинтересовать

21113. Література і літописання XIV – першої половини XVII ст. 25.69 KB
  Література і літописання XIV першої половини XVII ст. зявляються також нові розширені версії перекладних повістей про Олександра Македонського Олександрія оповідання про Трою Бовукоролевича у XVI ст. До найзначніших літописів тієї доби слід віднести Короткий Київський літопис XIV XVI ст. Виробництво власного паперу в Україні почалося в Галичині тільки в першій половині XVI ст.
21114. Релігійна полеміка другої половини XVI – першої половини XVII ст 23.14 KB
  У творчості цього полеміста чи не найповніше виражено віру у швидке відродження національної культури та її майбутній розквіт. Він виступав проти вищої ієрархії що призвела до унії а також проти католицької та західної культури. Якщо в часи ренесансних віянь в Україні та за її межами під враженням від давніх київських руїн часто висловлювалася думка що Київ це ніщо інше як гомерівська Троя то з початком поширення барокової культури в Україні виникає концепція Києва як Другого Єрусалима Й. який має стати надійним оплотом не тільки...
21115. Архітектура доби пізнього Середньовіччя (XIV – перша половина XVII ст.) 22.82 KB
  Найбільшими будівлями цього стилю були католицькі костели у Львові кінець XIV ст. Найстарішою памяткою готичної доби де готичні елементи співіснують з візантійськомало азійським стилем є Вірменська церква у Львові закладена у 1363 р. особливо у Львові панував стиль пізнього Ренесансу. У цьому стилі у Львові збудовані Високий замок будинок Гепнера Чорна камяниця 1570 будинок грецького купця й уславленого мецената Корнякта 1580 каплиця Трьох святителів 1578 вежа Вірменської церкви 1576 а також вежа Корнякта дзвіниця...
21116. Образотворче мистецтво у XIV – першій половині XVII ст 28.59 KB
  Образотворче мистецтво у XIV першій половині XVII ст. У фресковий розпис проникають народні й світські мотиви повязані з раннім Ренесансом хоча в цілому памятки монументального фрескового живопису XIV середини XVI ст. У цілому ж до середини XVI ст. З XVI ст.
21117. Театральне мистецтво і музична культура доби пізнього Середньовіччя (XIV - перша половина XVII ст.) 15.84 KB
  Театральне мистецтво і музична культура доби пізнього Середньовіччя XIV перша половина XVII ст. Театральне мистецтво. Зароджується також театральне мистецтво. Розвиваються народні ігри та мистецтво скоморохів виконавців і творців розважальної усної поезії музичного фольклору.
21118. Освіта у другій половині XVII – XVIII ст. 21.54 KB
  періодично то набував то втрачав статус академії доки цей статус не було остаточно затверджено 1701 р. Студенти Київської академії здебільшого йшли до війська пожежі та військова руїна нищили шкільні будинки та надані маєтності. починається новий розквіт діяльності академії який свого апогею досягає на межі століть. У стінах Академії відбуваються численні публічні диспути з різних наук затверджується звичай рекреацій культурномистецьких свят з виставами та іграми приуроченими до завершення навчального року.
21119. Література у другій половині XVII – XVIII ст. 26.69 KB
  Література у другій половині XVII XVIII ст. Розвиток літератури протягом другої половини XVII першої половини XVIII ст. Так званий леонінський вірш що поширився у XVIII ст. В кінці XVIII ст.
21120. Козацькі літописи (друга половина XVII - XVIII ст.) 17.41 KB
  Літописом Самовидця назвав цей твір Пантелеймон Куліш бо неназваний автор вважається що ним був представник козацької старшини Роман Ракушка став очевидцем подій від початку Визвольної війни і до 1702 р. Цей твір має не лише історіографічну а й значну літературну вартість. Але й недописаний твір складається з чотирьох томів які систематично охоплюють події 16481700 рр. Твір написано емоційно образною книжною українською мовою з використанням народної фразеології поетичних творів українських авторів.
21121. Філософія у другій половині XVII - XVIII ст. Творчість Г. С. Сковороди 17.36 KB
  Сковороди Певний внесок зробив Ф. Феноменальним явищем в історії української культури була творчість Григорія Савича Сковороди 17221794. Характерним для філософської позиції Сковороди є широке використання мови образів символів а не чітких раціоналістичних понять які не в змозі відповідно розкрити сутність філософської та життєвої істини. Тому заклик Сковороди пізнай себе означає в нього пізнати Бога в собі у глибині свого єства.