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


 

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

34720. Основные особенности развития системы мер в средневековой Западной Европе 19.29 KB
  Характерной чертой ее было понятие целого s базовой единицы измерения. Такой принцип унифицировал способы измерения облегчал установление соответствий между линейными квадратными и кубическими мерами. Для измерения больших земельных массивов применялись такие меры как центурии 200 югеров 50377 га и сальтус 4 центурии или 2015 га. Меры измерения объема жидких и сыпучих тел исчислялись несколько поиному.
34721. Меры веса и объема Древнерусского государства 15.12 KB
  Меры веса были очень разнообразны т. Равнялся 10 пудам1638 кг Пуд был наиболее ходовой мерой и равнялся 1638 кг Гривна употреблялась и как мера веса и как денежная единицаслиток серебра весом 400г Гривна весоваяпримерно 40 г серебра Меры объёма: основная мера объёма жидкостей была ведро= 1 40 бочки=10 кружек. Бочка как мера жидкостей применялась в основном в процессе торговли с иностранцами которым запрещалось вести розничную торговлю вином на малые меры.
34722. Измерение длины, расстояния и площади Древнерусского государства 15.32 KB
  существовало 3 вида сажени: Простаярасстояние по прямой между большими пальцами вытянутых в стороны рук=152см Маховаярасстояние по прямой между средними пальцами вытянутых в стороны рук=176см Косаярасстояние от ступни до конца пальцев противоположной руки вытянутой по диагонали. Следующей мерой длины был локотьрасстояние по прямой от локтевого сгиба до конца вытянутого среднего пальца4751см или одна треть сажени.это расстояние между концами вытянутых пальцев по прямой 1 8 сажени. Пядь малая 1819смрасстояние между большим пальцем и...
34723. Денежная система Древнерусского государства 15.01 KB
  происходит дальнейшее усложнение денежной системы. общерусская денежновесовая система как бы разделилась на две местные системы северную и южную. В основу северной системы была положена норма веса принятая в торговле с Западной Европой. Гривна этой системы равнялась 5119 г серебра и являлась древнейшим элементом возникше.
34724. Мера веса и объема в удельных княжествах 12.94 KB
  Основными мерами веса являлись большая96 золотников и малая48 золотников гривенка. В новгородских летописях появляется новая единица весапочка служившая при взвешивании благородных металлов и драгоценных камней. Продолжают употребляться крупные единицы весаберковец равный 10 пудам; пуд; а так же новая мера капь=4 пудам= 65.
34725. Изменение единиц площади, длины и расстояния в удельных княжествах 15.91 KB
  Сохраняется старое деление крупных единиц на мелкие: локоть или стопа = 2 пядям или ногам; сажень = 4 локтям = 8 пядям.и сажень в 174 см. Малой пяди в 19 см соответствовал локоть в 38 см й сажень в 152 см. Помимо указанных размеров саженей локтей и пядей в употреблении была и сажень в 216 см образовавшаяся на основании пяди с кувырком в 27 см1.
34726. Дифференциация денежной системы Руси периода феодальной раздробленности 18.37 KB
  Таким образом гривна из счетной денежной единицы гривны кун превратилась в гривну серебра. По источникам можно проследить что стоимость гривны серебра была в четыре раза больше стоимости гривны кун. Вес этой гривны 195 2045 г. Основные единицы гривны сеЬёрорусской и южнорусской денежных систем существовали в виде слитков.
34727. Метрологическая деятельность Московского государства по унификации системы измерений 16.43 KB
  Если в период феодальной раздробленности можо было наблюдать различие в местных мерах то в Русском централизованном государстве правительство стремится создать единые общегосударственные меры обязательные к употреблению по всей стране. Это мероприятие диктовалось централизаторской политикой правительства. Необходимость введения единых мер и веса диктовалась и экономическими соображениями.
34728. Меры длины и расстояния централизованного государства 15.5 KB
  начинает употребляться новая единица длины аршин. Аршин мера восточного происхождения но точного прототипа аршина среди восточных мер нет. Распространение аршина проходит от центра к окраинам. господствовал аршин.