Ігри Блотто
Ігри Блотто (Ігри Полковника Блотто) — клас ігор двох осіб з нульовою сумою, в яких завдання гравців полягає в розподілі обмежених ресурсів за кількома об'єктами (полями битв). У класичній версії гри гравець, який виставив більше ресурсів на полі, виграє битву на цьому полі, а сумарний виграш (ціна гри) дорівнює сумі виграних битв.
Хоча вперше гру полковника Блотто опублікував Борель[1] 1921 року, більшість варіацій класичної гри не були вирішені до 1991 року. 2006 року Роберсон (Brian Roberson) описав рівноважну ціну класичної гри для будь-якого числа полів та будь-якого рівня ресурсів, а також характерні множини рівноваги для більшості варіацій класичної гри[2].
Гру названо на честь міфічного Полковника Блотта з роботи Гроса (Oliver Alfred Gross) і Вагнера (R. A. Wagner) 1950 року[3]. Полковник був зобов'язаний знайти оптимальний розподіл своїх солдатів за N полями битв, знаючи що:
- на кожному полі сторона, яка виставила більше солдатів, виграє, але
- жодна сторона не знає, скільки солдатів виставить протилежна сторона на кожному полі, і
- обидві сторони прагнуть максимізувати кількість полів, на яких битву буде виграно.
Приклад[ред. | ред. код]
Як приклад наведемо гру, в якій два гравці записують три додатних цілих числа в неспадному порядку, суму S яких заздалегідь задано. Потім обидва гравці порівнюють числа (за порядком). Гравець, у якого у двох позиціях числа більші, виграє́.
Для S = 6 можливі лише три варіанти: (2, 2, 2), (1, 2, 3) та (1, 1, 4). Легко бачити, що:
- Будь-який триплет проти такого ж спричиняє нічию;
- (1, 1, 4) проти (1, 2, 3) спричиняє нічию;
- (1, 2, 3) проти (2, 2, 2) спричиняє нічию;
- (2, 2, 2) б'є (1, 1, 4).
Отже, (2, 2, 2) — оптимальна стратегія, оскільки виграє в одному випадку, і не програє у всіх інших. Однак, якщо обидва гравці виберуть стратегію (2, 2, 2) або (1, 2, 3), то жоден із гравців не зможе виграти в іншого змінюючи стратегію, так що кожна така пара є рівновагою Неша.
При збільшенні числа S стає важче провести аналіз. Для S = 12 можна показати, що (2, 4, 6) є оптимальною стратегією, проте для S > 12 детерміновані стратегії не оптимальні. Для S = 13 оптимальною змішаною стратегією виявляється вибір (3, 5, 5), (3, 3, 7) та (1, 5, 7) зі ймовірністю 1/3 для кожної.
Метод знаходження розв'язків[ред. | ред. код]
Для знаходження змішаних розв'язків гри можна скористатися методом змінного базису, для чого матрична гра зводиться до задачі лінійного програмування. Отримувана матриця буде мати великі кількості рядків і стовпців (рівні числу стратегій), але зберігати її не потрібно — елементи матриці можна отримати в потрібний момент програмно. Розмір базисної матриці буде невеликим.
Застосування[ред. | ред. код]
Президентські вибори в США 2000 року, одні з найближчих за рейтингом претендентів, були змодельовані як Гра Блотто[4]. У роботі стверджується, що Гор мав стратегію, яка б привела його до виграшу, але він її не знайшов.
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ The Theory of Play and Integral Equations with Skew Symmetric Kernels
- ↑ The Colonel Blotto game[недоступне посилання з Март 2020]
- ↑ A Continuous Colonel Blotto Game
- ↑ Lotto, Blotto, or Frontrunner: An Analysis of Spending Patterns by the National Party Committees in the 2000 Presidential Election [Архівовано 2008-04-07 у Wayback Machine.]
Посилання[ред. | ред. код]
- Стаття Айала Арада (Ayala Arad) і Аріеля Рубінштейна Colonel Blotto's Top secret Files: Multi-Dimensional Iterative Reasoning in Action (англ.)
- Стаття Джонатана Партингтона[en] Colonel Blotto's game (англ.)
- Карлин С. Математические методы в теории игр, программировании и экономике / пер. с англ. — М., 1964.
- Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. — М. : Высшая школа, Книжный дом «Университет», 1998.
|
| |||||||||||||||||