Ігри Блотто
Ігри Блотто (Ігри Полковника Блотто) — клас ігор двох осіб з нульовою сумою, в яких завдання гравців полягає в розподілі обмежених ресурсів за кількома об'єктами (полями битв). У класичній версії гри гравець, який виставив більше ресурсів на полі, виграє битву на цьому полі, а сумарний виграш (ціна гри) дорівнює сумі виграних битв.
Хоча вперше гру полковника Блотто опублікував Борель[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.