Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Матричні ігри. Розв’язування матричних ігор в чистих стратегіях

Нехай у кожного з двох гравців A і B скінченне число можливих дій – чистих стратегій: гравець A володіє m чистими стратегіями A1, A2, …, Am, а гравець B – n чистими стратегіями B1, B2, …., Bn. Щоб гра була повністю визначена, необхідно вказати правило, яке кожній парі чистих стратегій (Aі;Bj )ставить у відповідність число aij виграш гравця A за рахунок гравця B або програш гравця B. При aij<0 гравець A платить гравцю B суму . В грі, яка складається тільки з особистих ходів, вибір пари чистих стратегій (Aі;Bj) єдиним чином визначає її результат. Якщо ж в грі використовуються і випадкові ходи, то її результат обумовлюється середнім значенням виграшу (математичним сподіванням).

Якщо відомі значення aij виграшу для кожної пари (Aі; Bj)стратегій, то можна записати матрицю гри (платіжну матрицю)

Таблиця 3.1

Ai Bj
B1 ………. Bn
A1 …….
….. …… …….. …… …….
Am ……..
βj β1 …….. βn  

Платіжна матриця – це табличний запис функції виграшу. Описані ігри називають матричними. Окрема партія в такій грі реалізується наступним чином. Гравець A вибирає один із рядків платіжної матриці (одну з своїх чистих стратегій). Елемент матриці, який стоїть на перетині вибраного рядка і стовпця, визначає виграш гравця A (програш гравця B ).

Метою гравців є вибір найбільш вигідних стратегій, при яких гравець A вибирає максимальний виграш, а B – мінімальний програш. В теорії ігор виходять з припущення, що кожен гравець вважає свого супротивника розумним і намагається не дати йому досягти найкращого результату.

Визначення 3.1. Стратегія гравця A називається оптимальною, якщо при її застосуванні виграш гравця A не зменшиться, якими б стратегіями не користувався гравець B.

Визначення 3.2. Стратегія гравця B називається оптимальною, якщо при її застосуванні програш гравця B не збільшується, які б стратегії не застосовував гравець A.

Враховуючи наведені визначення, гравець A аналізує матрицю виграшів наступним чином: для кожної своєї чистої стратегії Aі він визначає мінімальне значення , виграшу в залежності від застосованих гравцем B чистих стратегій Bj. Потім серед усіх мінімальних виграшів він шукає таку чисту стратегію Ai0, при якій цей виграш буде максимальний, тобто знаходить

. (3.1)

Визначення 3.3. Число , яке визначається рівністю (3.1), називається нижньою чистою ціною гри (максиміном).

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

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

. (3.2)

Визначення 3.4. Число , яке визначається за формулою (3.2), називається верхньою чистою ціною гри (мінімаксом).

Воно показує, який максимальний програш може бути в гравця B внаслідок використання чистих стратегій. Відповідна чиста стратегія Bj гравця B називається мінімаксною.

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

Визначення 3.5. Принцип обережності, який диктує гравцям вибір максимінної і мінімаксної стратегій, називають принципом мінімакса.

Приклад 3.1. Знайти максимінну і мінімаксну стратегії в грі з матрицею

.

Розв’язок.Заповнимо для даної матриці таблицю 3.2

Таблиця 3.2

Ai Bj
B1 B2 B3 B4
A1 -1 -1
A2
A3 -2 -1 -2
βj  

 

, .

Отже, максимінною стратегією для гравця A є стратегія A2, а мінімаксною стратегією гравця B – стратегія B3.

Зв’язок між нижньою чистою ціною гри і верхньою чистою ціною гри встановлює наступна теорема, яку ми сформулюємо без доведення.

Теорема 3.1. В матричній грі її нижня чиста ціна гри не перевищує верхньої чистої ціни , тобто .

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

Визначення 3.6. Позначимо через i* і j* номери чистих стратегій, при яких має місце рівність . Пару чистих стратегій гравців A і B, при яких досягається ця рівність, називають сідловою точкою матричної гри, а елемент платіжної матриці, який стоїть на перетині i*-го рядка, j*- го стовпчика, – сідловим елементом.

Сідловий елемент є найменшим в i*-му рядку і найбільшим в j*-му стовпчику, тобто . Тому, якщо гравець B відхилиться від своєї мінімаксної стратегії, його програш може збільшитися. Аналогічно відхилення гравця A від своєї максимінної стратегії веде до зменшення його виграшу. Таким чином, мінімаксні стратегії в грі з сідловою точкою мають властивість стійкості. Звідси випливає, що якщо в матриці гри існує сідловий елемент, то найкращими для гравців є їх мінімаксні стратегії.

Визначення 3.7. Чисті стратегії Aі* і Bj*, які утворюють сідлову точку і виділяють в матриці гри сідловий елемент, називаються оптимальними чистими стратегіями відповідно гравців A і B.

Визначення 3.8. Набір називається розв’язком гри.

Приклад 3.2. Знайти розв’язок гри, заданої матрицею

.

Розв’язок. Заповнимо для даної матриці таблицю 3.3.

 

Таблиця 3.3

  Ai Bj  
  B1 B2 B3 B4  
A1  
A2 -1 -3 -3  
A3 -2 -5 -5  
βj    
               

, ,

. В даному випадку маємо дві сідлові точки (A1, B2) і(A1, B4). Отже, розв’язками гри будуть: {A1; B2; 2}і {A1; B4; 2}.

 


Читайте також:

  1. Алгоритм розв’язування задачі
  2. Алгоритм розв’язування задачі
  3. Алгоритм розв’язування задачі
  4. Алгоритм розв’язування задачі
  5. Алгоритм розв’язування задачі
  6. Алгоритм розв’язування задачі
  7. Алгоритм розв’язування задачі оптимізації в Excel
  8. Аналіз перед розв’язуванням задачі
  9. Аналіз перед розв’язуванням задачі
  10. Вартість чистих активів і визначення фактичної доходності інвестиційного портфелю
  11. Використання пакету Maple для розв’язування задач лінійного програмування
  12. Геометрична інтерпретація ЗЛП. Графічний метод розв’язування




Переглядів: 5461

<== попередня сторінка | наступна сторінка ==>
Предмет і деякі основні поняття теорії ігор | Розв’язування матричних ігор в змішаних стратегіях

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.005 сек.