2 Спрощення мaтричних ігор icon

2 Спрощення мaтричних ігор




Скачати 449.53 Kb.
Назва2 Спрощення мaтричних ігор
Сторінка1/3
Дата20.09.2012
Розмір449.53 Kb.
ТипРішення
  1   2   3

2.6. Спрощення мaтричних ігор

Рішення матричних ігор тим складніше, чим більше розмірність платіжної матриці. Тому для ігор з платіжними матрицями великої розмірності відшукання оптимального рішення можна спростити, якщо зменшити їх розмірність шляхом виключення дублюючих і свідомо невигідних (домінуємих) стратегій.

Визначення 1. Якщо в платіжній матриці гри всі елементи рядка (стовпця) дорівнюють відповідним елементам іншого рядка (стовпця), то відповідні цим рядкам (стовпцям) стратегії називаються дублюючими.

Визначення 2. Якщо в платіжній матриці гри всі елементи деякого рядка, що визначає стратегію Аі гравця А, не більше (менше або деякі рівні) відповідних елементів іншого рядка, то стратегія Аі називається доминіємою (свідомо невигідною).

Визначення 3. Якщо в платіжній матриці гри всі елементи деякого стовпця, що визначає стратегію Ві гравця В не менше (більше або деякі рівні) відповідних елементів іншого стовпця, то стратегія Ві називається доминіємою(свідомо невигідної).

П


равило.
Рішення матричної гри не зміниться, якщо з платіжної матриці виключити рядки і стовпці, що відповідають дублюючим і домінуємим стратегіям.

Приклад. Спростити матричну гру, платіжна матриця якої має вид:


З платіжної матриці видно, що стратегія А2 дублює стратегію А5, тому кожну з них можна відкинути (відкинемо стратегію А5). Порівнюючи почленно стратегії А1 і А4, бачимо, що кожен елемент рядка А4 не більше відповідного елемента рядка А1. Тому застосування гравцем А домінуючої над А4 стратегії А1 завжди забезпечує виграш, не менший того, котрий був би отриманий при застосуванні стратегії А4. Отже, стратегію А4 можна відкинути. Таким чином, маємо спрощену матричну гру з платіжною матрицею виду:







З

цієї матриці видно, що в ній деякі стратегії гравця В домінують над іншими: В3 над В2, В4 і В5. Відкидаючи домінуємі стратегії В2, В4 і В5 одержуємо гру 3х2, що має платіжну матрицю виду:


У цій матриці стратегія A3 домінується як стратегією А1, так і стратегією А2. Відкидаючи стратегію А3, остаточно одержуємо гру 2х2 із платіжною матрицею




Цю гру вже спростити не можна, її треба вирішувати алгебраїчним або геометричним методом, що були розглянуті вище.

Необхідно відзначити, що відкидаючи дублюючі і домінуємі стратегії в грі з сідловою крапкою, ми все одно прийдемо до гри із сідловою крапкою, тобто до рішення в чистих стратегіях. Але краще відразу перевірити, чи не володіє гра сідловою крапкою - це простіше, ніж порівнювати почленно всі рядки і всі стовпці платіжної матриці.


Алгебраїчні методи рішення матричних ігор іноді робити простіше, якщо використовувати також наступні властивості матричних ігор.


Властивість 1. Якщо до всіх елементів платіжної матриці додати (відняти) одне і теж число С, то оптимальні змішані стратегії гравців не зміняться, а тільки ціна гри збільшиться (зменшиться) на це число С.

Властивість 2. Якщо кожен елемент платіжної матриці помножити на позитивне число k, то оптимальні змішані стратегії гравців не зміняться, а ціна гри збільшиться на k.

Відзначимо, що ці властивості вірні і для ігор, що мають сідлову крапку. Ці дві властивості матричних ігор застосовуються в наступних випадках:

1) якщо матриця гри поряд з позитивними має і негативні елементи, то до всіх її елементів додають таке число, щоб виключити негативні числа в матриці;

2) якщо матриця гри має дробові числа, то для зручності обчислень елементи цієї матриці варто помножити на таке число, щоб усі виграші були цілими числами.

Приклад. Вирішити матричну гру 2х2 з платіжною матрицею виду:




П

омноживши всі елементи платіжної матриці на 10, а потім додаючи до них число 2, одержуємо гру з платіжною матрицею


Вирішуючи цю гру алгебраїчним методом, одержуємо




У

відповідності з властивостями 1 і 2, вихідна матрична гра має ті ж оптимальні змішані стратегії:


А для одержання вихідної ціни гри необхідно з отриманої ціни гри відняти 2, а потім розділити на 10. Таким чином, одержуємо ціну вихідної гри:




2.7. Рішення ігор 2хп і тх2

Як уже відзначалося в теоремі про активні стратегії, будь-яка кінцева гра mxn має рішення, у якому число активних стратегій кожного гравця не перевершуєL, де L = тin(т,п). Отже, у гри 2хn або mх2 завжди мається рішення, яке містить не більше двох активних стратегій у кожного з гравців (min (2, п) = min (m,2) = 2) . Якщо ці активні стратегії гравців будуть знайдені, то ігри 2хn і mх2 перетворюються в ігри 2х2, методи рішення яких розглянуті вище.

Практично рішення гри 2хn здійснюється в такий спосіб:

1) будується графічне зображення гри для гравця А;

2) виділяється нижня границя виграшу і знаходиться найбільша ордината нижньої границі (максимін), що дорівнює ціні гри v,

3) визначається пара стратегій гравця В, що перетинаються в крапці оптимуму. Ці стратегії і є активними стратегіями гравця В.

Таким чином, гра 2хn зведена до гри 2х2, яку більш точно можна вирішити алгебраїчним методом.

Якщо в крапці оптимуму перетинається більш двох стратегій, то в якості активної стратегії може бути обрана будь-яка пара з них.

Рішення гри mх2 здійснюється аналогічно. Але в цьому випадку будується графічне зображення гри для гравця В и виділяється не нижня, а верхня границя виграшу (тому що знаходиться оптимальна змішана стратегія гравця В), і на ній знаходиться крапка оптимуму з найменшою ординатою (мінімакс).


Приклад. Знайти рішення гри, платіжна матриця якої має вид:



Платіжна матриця не має сідлової крапки, тому оптимальне рішення повинне бути в змішаних стратегіях. Будуємо графічне зображення гри для гравця А (мал.2.10)



Крапка N (максимін) є крапкою оптимуму. У цій крапці перетинаються лінії, що відповідають активним стратегіям B1 і В2 гравця В. Таким чином, крім стратегії В3, одержуємо матричну гру 2х2 з платіжною матрицею виду






Використовуючи алгебраїчний метод рішення цієї гри, одержуємо точне рішення


Відповідь:




Приклад. Знайти рішення гри, платіжна матриця якої має вид

  1   2   3

Схожі:

2 Спрощення мaтричних ігор iconО. С. Фонова санкційне спрощення господарського процесу
Запропоновано підвиди ситуативного спрощення, а саме: форсований господарський процес та санкційне спрощення господарського процесу....
2 Спрощення мaтричних ігор iconРішення нечітких матричних ігор
Таким чином, виникає нечітка матрична гра. У даній статті пропонується методика розв'язання таких ігор І аналізу чутливості І стабільності...
2 Спрощення мaтричних ігор iconОсика Ігор Миколайович
Осика Ігор Миколайович, викладач кафедри криміналістики Національного університету внутрішніх справ
2 Спрощення мaтричних ігор iconАнкети з пропозиціями претендентів на Літературну премію Валерія Шевчука, які надійшли до 14. 02. 2012 року Котик Ігор
Котик Ігор, літературознавець, к ф н., науковий співробітник Львівського відділення Інституту літератури ім. Тараса Шевченка нан...
2 Спрощення мaтричних ігор iconЗахара ігор Степанович
Захара ігор Степанович (27. ХІІ. 1943, Львів) – філолог, історик філософії, канд філос наук (Філософські погляди Стефана Яворського,...
2 Спрощення мaтричних ігор iconПрокопенко Ігор Григорович Завідувач кафедри авіаційних радіоелектронних комплексів Доктор технічних наук, професор
Прокопенко Ігор Григорович д-р техн наук, проф. Фахівець в області теорії обробки сигналів І даних
2 Спрощення мaтричних ігор iconІгор В. Загороднюк наукові результати за 2002-2007 рр
Загороднюк Ігор Володимирович — кандидат біологічних наук, старший науковий співробітник, доцент кафедри екології Луганського нпу,...
2 Спрощення мaтричних ігор iconІгор В. Загороднюк наукові результати за 2002-2007 рр
Загороднюк Ігор Володимирович — кандидат біологічних наук, старший науковий співробітник, доцент кафедри екології Луганського нпу,...
2 Спрощення мaтричних ігор iconЗадачі теорії гри
Потім головна увага знову була звернута до економічних проблем. Нині сфера застосування теорії ігор значно розширилась. Так, у соціальних...
2 Спрощення мaтричних ігор iconО. М. Шлапак, асистент, Вінницький державний педагогічний університет взаємодія викладача та студентів у процесі застосування дидактичних ігор
У статті висвітлено особливості взаємодії викладача та студентів у процесі застосування дидактичних ігор майбутніми вчителями у внз....
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи