• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Принцип мінімаксу.

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

Серед чисел виберемо найбільше: . Назвемо нижньою ціною гри, або максиміним виграшем (максиміном). Це гарантований виграш гравця при будь-якій стратегії гравця . Отже

Стратегія, що відповідає максиміну, називається максиміною стратегією.

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

Серед чисел виберемо найменше і назвемо верхньою ціною гри або мінімаксним виграшем (мінімаксом). Це гарантований програш гравця . Отже

Стратегія, що відповідає мінімаксу, називається мінімаксною стратегією. Принцип, що диктує гравцям вибір найбільш «обережних» мінімаксних і максиміних стратегій, називається принципом мінімаксу.

Визначимо верхню і нижню ціни гри і відповідні стратегії в прикладі 12.1, доповнивши таблицю рядком і стовпцем :

стратегії
	-1		-1
		-1	-1

При виборі гравцем стратегії мінімальний виграш і відповідає стратегії гравця . При виборі стратегії мінімальний виграш досягається при стратегії . Гарантуючи собі максимальний виграш при будь-якій стратегії гравця , тобто нижню ціну гри , гравець може вибрати будь-яку стратегію: або , тобто будь-яка стратегія є максиміною.

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

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

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

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

,

яка справедлива для всіх .

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

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

Чи має гра сідлову точку?

Розв’язок. Всі розрахунки проведемо в таблиці, до якої крім матриці , введемо стовбець і рядок . Аналізуючи рядки матриці ( стратегії гравця ), заповнимо стовбець . Аналогічно по стовпцях : .

стратегії
	0,5	0,6	0,8	0,5
	0,9	0,7	0,8	0,7
	0,7	0,6	0,6	0,6
	0,9	0,7	0,8

Нижня ціна гри , а верхня ціна гри . Ці значення рівні: і досягаються на одній і тій же парі стратегій . Отже, гра має сідлову точку і ціна гри .

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