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


 

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

8797. Международные организации. Модель OSI 408.5 KB
  Международные организации. Модель OSI. Глобальность охвата и интернациональный характер развития компьютерных сетей делает роль международных организаций в вопросах стандартизации определяющей. При этом, в большинстве случаев, принимаемые стандарты ...
8798. История развития компьютерных сетей. Роль компьютерных сетей в современном мире 1.21 MB
  Эволюция компьютерных сетей началась в 50-х годах прошлого века. Развитие компьютерных сетей сопряжено с развитием вычислительной техники и телекоммуникаций. Компьютерные сети могут рассматриваться как средство передачи информации на большие расстоя...
8799. Назначение компьютерных сетей 18.79 KB
  Компьютерные сети - это системы компьютеров, объединенных каналами передачи данных, обеспечивающие эффективное предоставление различных информационно-вычислительных услуг пользователям посредством реализации удобного и надежного доступа к ресур...
8800. Классификация и принципы построения компьютерных сетей 23.35 KB
  По территориальной распространенности сети могут быть локальными, глобальными, и региональными: Локальная сеть (LAN - Local Area Network) (ЛКС) - сеть в пределах предприятия, учреждения, одной организации. К классу ЛКС относятся сети...
8801. Принципы построения компьютерных сетей 207.84 KB
  Топология сети - это классификационный признак сети, который определяет принцип соединения компьютеров (рабочих станций, машин) в единую сеть. Существует несколько топологий: линия, каждый с каждым (многосвязная), звезда, шина, кольцо (двойное...
8802. Основные компоненты компьютерной сети 16.62 KB
  Компьютерная сеть - это сложный комплекс взаимосвязанных и согласованно функционирующих программных и аппаратных компонентов. Изучение сети в целом предполагает знание принципов работы ее отдельных элементов: компьютеров коммуникационно...
8803. Модем. Типы модемов для ПК 176.5 KB
  Немного истории Вы, очевидно, знаете, что модем - это устройство, предназначенное для работы компьютера во Всемирной компьютерной сети Интернет. Появление модемов стало следствием появления глобальных компьютерных сетей. Когда были созданы перв...
8804. Валюта, валютні системи, валютні курси 148 KB
  Валюта, валютні системи, валютні курси 1.1. Поняття валюти, види валют, валютні системи Валюта (італ. valuta - ціна, вартість) - грошова одиниця країни. Валютна система - сукупність валютно-економічних відносин, що історично склались на засадах інте...
8805. Еволюція світової та вітчизняної валютних систем 70.5 KB
  Еволюція світової та вітчизняної валютних систем. Становлення світової валютної системи Першою формою організації міжнародних грошово-валютних відносин був золотий стандарт, що базувався на використанні золота як грошового товару. У більш...