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


 

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

41708. ИССЛЕДОВАНИЕ ТИПОВЫХ ЗВЕНЬЕВ ЛИНЕЙНЫХ АСР 165.27 KB
  Переходная характеристика Время сек Импульсная характеристика Время сек Рисунок 1 Переходная и импульсная характеристика звена W1 Переходная характеристика Время сек Импульсная характеристика Время сек Рисунок 2 Переходная и импульсная характеристика звена W2 Переходная характеристика Время сек Импульсная характеристика Время сек Рисунок 3 Переходная и импульсная характеристика звена W3 Переходная характеристика Время сек Импульсная характеристика Время сек Рисунок 4 Переходная и импульсная характеристика звена W4...
41709. Расчет поперечной рамы стального каркаса одноэтажного здания на действие постоянной нагрузки 702.68 KB
  Поперечное сечение в виде 2х уголков с параметрами уголка 160×100×10 Высота низа колонн 8 м Поперечное сечение в виде трубы с параметрами 720×12 Высота верха колонн 6 м Поперечное сечение в виде трубы с параметрами 720×8 q = 24 кН м P = 32 кН ℓ = 32 м Цели лабораторной работы: Произвести расчет поперечной рамы стального каркаса одноэтажного здания с помощью ПК ЛИРА Определить для основных сечений колонн и ригеля максимальные значения нормальных и касательных напряжений Сделать вывод о работе конструкции Ход работы: Создание расчетной...
41710. Команды MSDOS 251.68 KB
  Название команды Синтаксис команды Создание файла с консоли copycon имя файла Удаление файла del имя файла Переименование файла ren имя файла 1 имя файла 2 Редактирование файла edit имя файла Переход на диск имя диска Переход в каталог cd путь Создание каталога md имя каталога Удаление каталога rd имя каталога Очистка экрана Cls Вывод содержимого файла на экран type имя файла Копирование файла copy путь 1 что копируется путь 2 куда копируется Поиск файла filefind имя файла Работа с командной строкой Prompt Информация о команде команда ...
41711. Индекс FTSE 100 109.84 KB
  Индекс начал рассчитываться с 3 января 1984 года с уровня 1000 пунктов. Компании чьи акции учитываются в расчете индекса FTSE 100 должны удовлетворять условиям выставляемым FTSE Group: а должны входить в список Лондонской фондовой биржи; б стоимость акций индекса FTSE 100 выражается в фунтах или евро;в пройти тест на принадлежность к определенному государству;г акции FTSE 100 должны быть в свободном обращении и быть легко ликвидными. Индекс FTSE 100 включает 100 компаний британской экономики хотя на самом деле список состоит из...
41712. Основы работы в ГИС ArcView 1.75 MB
  Интерфейс пользователя rcView Окно программ Окно приветствия Строка меню Строка кнопок Строка инструментов Окно вида Меню работы с файлами Меню редактирования Меню вид Меню тема Меню графика Меню окно Строка кнопок:
41713. Классы. Основные понятия 260.14 KB
  Основные понятия Цель работы: Познакомиться с понятием класса. Продемонстрировать работу с классом создание экземпляра класса изменение значений полей вызов перегруженных методов Выполнить требования к лабораторным работам см. Контрольные вопросы: Что такое метод Что такое возвращаемый тип каким он может быть Что значит void Что такое параметры метода какие параметры бывают Что такое перегрузка методов и для чего она нужна Что такое класс Какие члены класс может содержать Что такое конструктор для чего служит...
41714. Таблицы, сортировка таблиц, вычисление в таблицах в редакторе Word 54.82 KB
  С помощью Microsoft Grph можно создавать высококачественные информативные диаграммы и включать их в документы Word. Создание диаграммы Диаграммы строятся на основе данных содержащихся в таблице данных также внедряемой в документ Word. Можно создавать диаграммы четырнадцати основных и двадцати дополнительных типов. Тип диаграмм Правильный выбор типа диаграммы позволяет представить данные самым выигрышным образом.
41715. Ввод-вывод. Ветвления 168.52 KB
  Цель работы: Разработать алгоритм и написать программу на языке С++ для выполнения задания согласно номера бригады. Программа должна обеспечивать обмен с оператором, выдавая необходимые сообщения и позволяя вводить исходные данные и просмотреть результат выполнения программы.