МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Матричні ігри. Розв’язування матричних ігор в чистих стратегіяхНехай у кожного з двох гравців 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
Платіжна матриця – це табличний запис функції виграшу. Описані ігри називають матричними. Окрема партія в такій грі реалізується наступним чином. Гравець 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
, . Отже, максимінною стратегією для гравця 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
, , . В даному випадку маємо дві сідлові точки (A1, B2) і(A1, B4). Отже, розв’язками гри будуть: {A1; B2; 2}і {A1; B4; 2}.
Читайте також:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|