Игры Блотто

Игры Блотто (Игры Полковника Блотто) представляют собой класс игр двух лиц с нулевой суммой, в которой задача игроков состоит в распределении ограниченных ресурсов по нескольким объектам (полям битв). В классической версии игры игрок. выставивший больше ресурсов на поле выигрывает битву на этом поле, а суммарный выигрыш (цена игры) равен сумме выигранных битв.

Хотя игра полковника Блотто была впервые опубликована Борелем (Borel)^[1] в 1921-ом году, большинство вариаций классической игры не были решены до 91-го года. В 2006-ом году Роберсон (Roberson) описал равновесную цену классической игры для любого числа полей и любого уровня ресурсов, а также характеристические множества равновесия для большинства вариаций классической игры.^[2]

Игра названа в честь мифического Полковника Блотто из работы Гроса и Вагнера (Gross and Wagner) 1950-го года ^[3]. Полковник был обязан найти оптимальное распределение своих солдат по N полям сражений, зная что:

1. на каждом поле сторона, выставившая больше солдат, выигрывает, но
2. ни одна сторона не знает, какое число солдат выставит противоположная сторона на каждом поле, и
3. обе стороны стремятся максимизировать число полей, на которых битва будет выиграна.

Пример

В качестве примера представим игру, в которой два игрока записывают три положительных целых числа в неубывающем порядке, сумма которых заранее задана (=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] В работе утверждается, что Гор имел стратегию, которая привела бы его к выигрышу, но он ее не нашел.

Смотри также

• Goofspiel

Внешние ссылки

• Статья Айала Арада (Ayala Arad) и Ариеля Рубинштейна (Ariel Rubinstein) Colonel Blotto's Top secret Files: Multi-Dimensional Iterative Reasoning in Action

• Статья Джонатана Партингтона (Jonathan Partington) Colonel Blotto page

• Карлин С., Математические методы в теории игр, программировании и экономике, пер. с англ., М., 1964.

• Петросян Л.А., Зенкевич Н.А., Семина Е.А Теория игр М., Высшая школа, Книжный дом 'Университет', 1998

Ссылки

1. ↑ The Theory of Play and Integral Equations with Skew Symmetric Kernels
2. ↑ The Colonel Blotto game
3. ↑ A Continuous Colonel Blotto Game
4. ↑ Lotto, Blotto, or Frontrunner: An Analysis of Spending Patterns by the National Party Committees in the 2000 Presidential Election