Дисципліни:
Лабораторна робота №4
На тему:

Матричні ігри.

Дисципліна: Теорія прийняття рішень
ВНЗ:НУ «ЛП»
Формат: Word Doc

Переглядів: 1731 Додано: 2014-06-04




Частина тексту

Мета: Розв’язати матричну ігру методом послідовного наближення ціни гри.

Теоретичні відомості

Розв’язування матричних ігор при розмірах матриць n х m більших або рівних 3 х 3 і відсутності сiдлових точок в чистих стратегіях або можливості зменшити розміри матриці за допомогою видалення домінованих стратегій загальному випадку можливо лише за допомогою чисельних методів. Розглянемо один з таких методів - метод послідовного наближення ціни гри. В цьому методі послідовно розігрує багато партій. У кожній партії оба гравця вибирають ті стратегії, які дають їм найбільшу суму виграшів у всіх партіях, включаючи поточну. Після кожної партії матричної гри обчислюється середнє значення виграшу v1 в одній партії першого гравця, середнє значення програшу v2 в одній партії другого гравця і півсума v1 і v2, яка береться за наближене значення ціни матричної гри v:

де N - номер розігруваної партії; S11, S21,….. Sn1- виграші першого гравця в N партіях відповідно при вживанні своїх першої, другої ..., n -ї чистої стратегії; n - число чистих стратегій першого гравця; S12, S22….. Sm2 -програші другого гравця в N партіях відповідно при застосуванні своїх першої, другої ..., m-ї чистої стратегії; m - число чистих стратегій другого гравця.

Для визначення оптимальних змішаних стратегій обох гравців підраховуються частоти fi1 (i=1,n), fi2 (i=1,n), застосування кожної чистої стратегії відповідно першого і другого гравців. Ці частоти приймають за наближені значення вірогідності застосування відповідних чистих стратегій в оптимальних змішаних стратегіях обох гравців.

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

Об'єм обчислень в цьому методі пропорційний сумі числа рядків і стовпців вихідної матриці гри.