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


 

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

44899. Принципы и технологии оценки недвижимости 13.6 KB
  Оценка недвижимости это прежде всего оценка прав собственности на данную недвижимость. Отсюда следует что оценка недвижимости должна включать оценку самой недвижимости оценку права собственности или права пользования землей или зданиями. Основные принципы оценки недвижимости: Принцип спроса и предложения: заключается в учете действия закона спроса и предложения на стоимость объекта недвижимости.
44900. Представления. Отличие представления от базовых переменных отношения 28.5 KB
  Представления. Отличие представления от базовых переменных отношения. CRETE TBLE ЕМР Однако реляционные системы обычно поддерживают еще один вид именованных переменных отношений называемых представлениями В любой конкретный момент их значение является производным отношением и поэтому упрощенно можно считать что представление это производная переменнаяотношение. Значение данного представления в данное время является результатом вычисления определенного реляционного выражения в данный момент а упомянутое реляционное выражение...
44903. The USA. Соединенные Штаты Америки 16.29 KB
  The United States of America is the fourth largest country in the world (after Russia, Canada, and China). It occupies the southern part of North America and stretches from the Pacific to the Atlantic Ocean. It also includes Alaska in the north and Hawaii in the Pacific Ocean.
44905. Основные принципы обучения РЯ в школе 16.17 KB
  Специальные: общеметодические и частнометодические: экстра-лингвистический сопоставление языка и реалий функциональный коммуникативный показ функций языковых единиц речи структурно-семантический изучение языковых явлений с точки зрения строения и значения функциональносемантический межуровневых и внутриуровневых связях нормативностилистический обучение учащихся правильной и выразительной речи исторический учет исторических изменений языка. Эстетический – отбор понятий направленных на раскрытие прекрасного в...
44906. Ударение и его типы. Интонация и её конструкции. Паузация и темп русской речи 27.5 KB
  Словесное ударение это более сильное произношение одного слога в слове служащее для фонетического объединения этого слова. В русском языке ударение зависит от силы выдоха поэтому оно силовое и динамическое. В русском языке нет определенного зафиксированного места ударения оно может падать на любой слог разноместное ударение: мама собака. Русское словесное ударение также является подвижным 2 так как при переходе слова из одной формы в другую может меняться и место ударения в слове: стена' сте'ны.
44907. Орфоэпические нормы 16.48 KB
  Иное произношение звуков воспринимается как неправильное приводит к нарушению законов фонетического языка. Современное русское произношение сложилось в ревой половине 18 века. К началу 19 века староманерное произношение как общественное стало национальной нормой. Произношение согласных.