Лекція № 15


Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации:

Лекція № 15 Проблематика теорії ігор та прийняття рішень “Гра – не філософія і не релігія, це особлива дисципліна, за своїм характером вона найближча до мистецтва... ”Г.Гессе “Гра у бісер” Питання, що розглядаються у лекції: Коротка історична довідкаТермінологія та класифікація ігорМатематичний формалізм теорії ігор Матричні ігри двох осібГра зі змішаними стратегіямиМатричні та біматричні ігри двох осіб (приклади) Історична довідка Перші роботи по теорії ігор – Цермело, Борель(початок ХХст.) Доведена основна теорема теорії ігор – Д. фон Нейман(1928р.) Математик Джон фон Нейман був переконаний, що економіку краще всього вивчати через аналогії з салонними (стратегічними) іграми, а не через просту аналогію з аналітичною задачею знаходження максимумів та мінімумів. Вперше теорія ігор систематично викладена у монографії : “Теорія ігор і економічної поведінки” Д.Нейман, О. Моргенштерн(1944р.) Теорія ігор – це теорія математичних моделей та методів прийняття раціональних рішень за умов конфлікту та невизначеності Умови прийняття рішень:прийняття рішень в умовах визначеності, коли дані відомі точно;прийняття рішень в умовах ризику, коли дані можна описати за допомогою розподілу імовірностей;прийняття рішень в умовах невизначеності (ситуація Робінзона Крузо); Сфери застосування теорії ігор Питання бізнесу в умовах конкуренціїПланування воєнних дій та управління воєнною технікоюПланування народного господарстваУправління виробництвомАналіз торгівельних угод та переговорівВивчення принципів формування коаліційкомп’ютерні мережіБезпровідні теле- та інтернет комунікації Математичне моделювання конфліктної ситуації Основні компоненти:учасники конфліктних ситуаційможливі дії кожної із сторінінтереси гравців ситуації в яких беруть участь люди(групи, коаліції) з протилежними цілями, причому результат будь-якого рішення кожного з них залежить від рішень прийнятих іншими учасникамиматематична модель конфліктних ситуаційучасники конфліктних ситуацій можливі дії кожної із сторінрезультат дії гравців ! Кількість учасників гри не може бути меншою двох !гра однієї особи зводиться до екстремальної задачі математичного програмування Формалізація конфліктної ситуації Конфліктні ситуаціїГраГравціСтратегіяВиграш(програш) Формалізація конфліктної ситуації I – множина всіх гравцівXi – множина всіх стратегій i-го гравця, i є Ix=(x1 , x2 , …, xn ) - ситуація, тобто набір стратегій, де x1 є X1 – деяка стратегія 1-го гравця, x2 є X2 – деяка стратегія 2-го гравця і т. д. Hi(x) – виграш гравця i у ситуації x Реалізація конфлікту полягає у виборі кожним гравцем i є Iйого стратегії xi є Xi та одержанні ним в утвореній ситуаціїx=(x1 , x2 , …, xn ) деякого виграшу Hi(x) Класифікація ігор (по кількості гравців):парна (два гравці) та множинна (більше двох гравців)(по кількості стратегій):скінченна та нескінченна (за властивостями фунцій виграшу):гра з нульовою сумою (виграш та програш розподіляються між всіма гравцями), гра з ненульовою сумою (по взаємодії між гравцями): кооперативна гра (поєднання інтересів гравців та домовленість між ними про вибір стратегій) та некооперативна гра (дії гравців не координуються)(за кількістю ходів): однокрокові, багатокрокові(за станом інформації): ігри з повною інформацією (шахи, шашки); ігри з неповною інформацією Класифікація ігор Парна гра з нульовою сумою або антагоністична гра має властивість: У грі з нульовою сумою один гравець виграє те, що програє інший;У грі з нульовою сумою інтереси гравців прямо протилежні; Гравець А Гравець В - рядки відповідають стратегіям гравця А - стовпчики відповідають стратегіям гравця В - значення елементів матриці А відповідає виграшам гравця А - значення елементів матриці B відповідає виграшам гравця B Стратегії гравця В:В1,В2,.........Вn Платіжна матриця Aa11 а12 ... a1na21 a22 … a2n ……am1 am2 … amn Стратегії гравця А:А1,А2,......Аm Платіжна матриця Bb11 b12 ... b1nb21 b22 … b2n ……bm1 bm2 … bmn Безкоаліційна гра двох осіб з ненульовою сумою(неантагоністична гра або біматрична гра) Ситуації:Мета: Гравець А Гравець В Стратегії гравця А:А1,А2,......Аm Стратегії гравця В:В1,В2,.........Вn Платіжна матрицяa11 а12 ... a1na21 a22 … a2n ……am1 am2 … amn Якщо гравець А використовує стратегію А2, а гравець В – стратегію В2, топлатіж гравцю Аскладає а22 Рядки відповідають стратегіямгравця Астовпчики відповідаютьстратегіям гравця В! Якщо аij > 0(виграш гравця А)якщо аij < 0(програш гравця А) Гра двох осіб з нульовою сумою(антагоністична гра) Практична діяльність менеджерів, маркетологів, рекламних агентів, які приймають рішення в умовах гострої конкуренції вибір оптимальних стратегій кожним з гравців для одержання найкращого результату серед найгірших α=max min aij i j β=min max aij j i Песимістичний критерій мінімаксу – максиміну Гравець А вибирає стратегію (максимінна стратегія) , яка максимізує його мінімальний виграш:α – нижня ціна гриГравець В вибирає стратегію (мінімаксна стратегія), яка мінімізує його максимальний програш: β – верхня ціна гриЯкщо α = β = γ, γ – чиста ціна грито гру називають грою з сідловою точкою Властивості ігор з сідловими точками: сідловій точці відповідає пара оптимальних стратегій виграш (програш) гравця А (В) дорівнює чистій ціні гри. оптимальні стратегії є стійкими: жодному з гравців невигідно відхилятися від своїх оптимальних стратегій Чисті стратегії Задача знаходження сідлової точки в платіжній матриці називається задачею розв’язання гри у чистих стратегіях 5 -9 4 -2 8 6 5 6 -3 9 -2 8 В1 В2 В3 В4 мінімуми рядків А1А2А3 Максимуми стовпчиків 8 5 9 8 -3 5 -9 максимін мінімакс α = β = 5 Чиста ціна гри дорівнює: γ=5оптимальні стратегії: А2 і В2Висновок: компаніям потрібно проводити рекламу на телебаченні, тоді риноккомпанії А збільшиться на 5%. Приклад Дві компанії А та В продають два види препаратів проти грипу. Компанія А рекламує продукцію на радіо (А1), телебаченні (А2) та у газетах (А3). Компанія В крім використання радіо (В1), телебачення (В2) та газет (В3) розсилає також по пошті рекламні буклети (В4). В залежності від умов проведення рекламної кампанії, кожна із фірм може залучити на свій бік частину клієнтів конкуруючої компанії. Платіжна матриця характеризує відсоток клієнтів залучених або втрачених компанією А Змішані стратегії B A В1 В2 Герб Цифра А1 Герб 1 -1 А2 цифра -1 1 основна теорема теорії ігор(Д. фон Нейман, 1928) Кожна скінченна гра має, принаймні, один розв’язок (можливо в області змішаних стратегій)Виграш або ціна гри задовольняє умові: α = β = (для чистих стратегій) α ≤ ≤ β (для змішаних стратегій) 1 2 4 3 0 2 3 2 1 2 4 3 4 3 5 4 А1А2А3А4 В1 В2 В3 В4 невигідна стратегія невигідна Дублюючі стратегії 1 2 3 4 3 4 А1А4 В1 В2 В4 Гра зі змішаними стратегіями Розглянемо гру з платіжною матрицею: Гра зі змішаними стратегіями Якщо гра не має сідлової точки, то максимінні та мінімаксні стратегії не є оптимальними, тому потрібно застосовувати змішані стратегії (повторюваність гри з різною частотою використання чистих стратегій).Означення Випадкова величина, значеннями якої є імовірності вибору гравцем своїх чистих стратегій, називається змішаною стратегією.Зауваження Змішані стратегії доцільно застосовувати, коли гра повторюється. m i=1 n j=1 Гра зі змішаними стратегіями Означення 2.15Змішаною стратегією першого гравця називається вектор : Х = (x1, x2,… xm) для якого ∑ xi = 1, xi ≥ 0Змішаною стратегією другого гравця називається вектор : Y = (y1, y2,… yn) для якого ∑ yj = 1, yj ≥ 0 xi, yj - ймовірності використання чистих стратегій Гра зі змішаними стратегіями Розв’язок гри має наступну властивість:Якщо один з гравців притримується своєї оптимальної змішаної стратегії, то виграш залишається незмінним і дорівнює ціні гри νA. незалежно від дій другого гравця (він може використовувати будь-яку зі своїх стратегій, що входять у оптимальну змішану стратегію , в чистому вигляді, або змішувати їх довільним чином) 3 6 7 5 Гра зі змішаними стратегіями Дві конкуруючі фірми (гравці) реалізують на ринок продукцію, що швидко псується. Кожен з гравців прагне зайняти по два сегменти ринку (стратегії). Відомі прибуток (виграш) або збиток (програш гравця) для кожного сегменту ринку (аij), які наведені у платіжній матриці (в умовних грош. од.) 3 6 7 5 В1 В2 А1А2 min 3 5 α=5 max 7 6 β=6 α ≠ β !платіжна матриця не маєсідлової точки! Розв”язок гри будемо шукати у змішаних стратегіях. Позначимо шукані оптимальні змішані стратегії гравців: гравець А: SA = (x1,x2) гравець В: SB = (у1, у2) Якщо гравець В застосовує чисту стратегію В1, то виграш гравця А дорівнює: 3х1+7х2=γ Якщо гравець В застосовує чисту стратегію В2, то виграш гравця А дорівнює: 6х1+5х2=γ Аналогічно знаходиться оптимальний виграш гравця В * * Розв”язання: знайдемо оптимальні стратегії та ціну гри кожного гравця 3х1 + 7х2=γ6х1 + 5х2= γх1 + х2 = 1 3у1 + 6у2= γ7у1 + 5у2= γу1 + у2= 1 Розв”язавши системи, одержимо: х1 = 2/5х2 = 3/5γ = 27/5 у1 = 1/5у2 = 4/5γ = 27/5 Враховуючи додаткові умови:х1 + х2= 1 у1 + у2= 1одержимо системи рівнянь для знаходження SA та SB:оптимальна стратегія гравця А: оптимальна стратегія гравця В: Висновок: рекомендується першій фірмі працювати на першому сегменті ринку з відносною частотою 2/5, на другому сегменті ринку-з відносною частотою 3/5; другій фірмі працювати на першому сегменті ринку з відносною частотою 1/5; на другому сегменті – з відносною частотою 4/5. При цьому середній гарантований прибуток 1-ої фірми від реалізації продукції(середній збиток другої фірми від нереалізації продукції) на обраних сегментах ринку становитиме 27/5 умовних грошових одиниць. y x 6 3 7 5 x1 x2 А В 1 у т. С знаходитьсячиста стратегія А1(х=1) С О У т. О знаходиться чиста стратегія А2(х=0) ! довжина відрізка АВдорівнює ціні гри. γ SA = (x,1-x)для стратегії В1:3х+7(1-х)=7-4хдля стратегії В2:6х+5(1-х)=х+5 * Графічний метод роз”язку (можна застосовувати для ігор, платіжні матриці, яких мають розмірність 2Хn або mX2 ) Приклади безкоаліційних ігор 1. Гра “Викладач-студент”2. Гра “ Камінь, ножиці, бумага”3. Гра “Дилема засудженого”4. Гра “Сімейна суперечка”5. Гра “Мора n осіб” Приклади безкоаліційних ігор 1. Гра «викладач – студент» (біматрична, з ненульовою сумою)Стратегії студента: вивчити предмет (В); не вивчити предмет (НВ);Стратегії викладача: поставити залік (+); не поставити залік (-);Платіжна матриця студента Платіжна матриця викладача (виграші студента) (виграші викладача)Аналіз: найбільший виграш студента 2 у ситуації (В, +);найбільший виграш викладача 0 у ситуації (В, +);ситуація (В; +) – рівноважна і вигідна для обох гравцівОтже, ідеальний результат гри: для студента вивчити предмет; для викладача – поставити залік! + - В 2 -1 НВ 1 0 + - В 0 -2 НВ -3 -1 Приклади безкоаліційних ігор 2. Гра «Камінь, ножиці, папір» (Матрична, з нульовою сумою)х1 = х2 = {Камінь, Ножиці, папір} Н(Камінь, Камінь)=0(«нічия»);Н(Камінь, Ножиці)=1 (камінь «б’є» ножиці – гравець 1 виграє у гравця 2) і т.д.Платіжна матриця Аналіз: будь-яка ситуація нерівноважна (для чистих стратегій);можливо знайти рівноважну ситуацію у змішаних стратегіях . Камінь Ножиці папір Камінь 0 1 -1 Ножиці -1 0 1 папір 1 -1 0 Приклади безкоаліційних ігор 3. Гра «Дилема засудженого»х1 = х2 = {«мовчати», «зрадити»} – множина стратегій гравців Платіжна матриця гравця 1 Платіжна матриця гравця 2 М ЗРАДА М ЗРАДАМ -0,5 -10 М -0,5 0ЗРАДА 0 -2ЗРАДА -10 -2  Аналіз: ситуація {З; З} для обох гравців є рівноважною, але невигідною;ситуація {М; М} для обох гравців є нерівноважною, але вигідною;ЯКЩО КОЖЕН ВИБИРАЄ, ЩО КРАЩЕ ДЛЯ НЬОГО, ОБИДВА ЗРАДЯТЬ І ОДЕРЖАТЬ 2 РОКИЯКЩО КОЖЕН БУДЕ ДУМАТИ ПРО СПІЛЬНЕ БЛАГО, ТО ОБИДВА БУДУТЬ МОВЧАТИ І ОДЕРЖАТЬ 0,5 РОКІВ Приклади безкоаліційних ігор 4. Гра «Сімейна суперечка» (біматрична гра з ненульовою сумою)Оптимальний вибір подружжям спільної розваги Платіжна матриця Платіжна матриця дружини чоловіка Театр Футбол Театр ФутболТеатр 2 0 Театр 1 0Футбол 0 1 Футбол 0 2Аналіз:ситуації (театр, театр) та (футбол, футбол) рівноважні;Чи вигідні ці ситуації для обох гравців? прийняття рішень в умовах ризику:Критерій Байєса-Лапласа: (рішення та стани природи повторюються)SБ.-Л = max∑ aij xij прийняття рішень в умовах невизначеності:Максимінний критерій Вальда (критерій обережного спостерігача)SВ = max min aijМаксимаксний критерій (критерій крайнього оптимізму):Sm = max max aijКритерій песимізму оптимізму Гурвіца:Sr = max [α max aij + (1- α) min aij] α – ступінь оптимізму 0≤ α ≤1Критерій Севіджа (критерій мінімального ризику)Ризик : Rij = max aij – aij Виграш: Sc = min max Rij n i j=1 i j i j j i i j Ігри з природою Роберт Оманн получает свой приз от его величества шведского Короля Карла Густава XVI в Стокгольмском концертном зале, 10 Декабря 2005 года Томас Шеллинг получает свой приз от его величества шведского Короля Карла Густава XVI в Стокгольмском концертном зале, 10 Декабря 2005 года

Приложенные файлы

  • ppt 22444322
    Размер файла: 2 MB Загрузок: 1

Добавить комментарий