Игры Блотто
Игры Блотто (Игры Полковника Блотто) представляют собой класс игр двух лиц с нулевой суммой, в которой задача игроков состоит в распределении ограниченных ресурсов по нескольким объектам (полям битв). В классической версии игры игрок, выставивший больше ресурсов на поле, выигрывает битву на этом поле, а суммарный выигрыш (цена игры) равен сумме выигранных битв.
Хотя игра полковника Блотто была впервые опубликована Борелем (Borel)[1] в 1921-м году, большинство вариаций классической игры не были решены до 91-го года. В 2006-м году Роберсон (Roberson) описал равновесную цену классической игры для любого числа полей и любого уровня ресурсов, а также характеристические множества равновесия для большинства вариаций классической игры.[2]
Игра названа в честь мифического Полковника Блотто из работы Гроса и Вагнера (Gross and 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] В работе утверждается, что Гор имел стратегию, которая привела бы его к выигрышу, но он её не нашёл.
См. также
- Goofspiel
Примечания
- The Theory of Play and Integral Equations with Skew Symmetric Kernels
- The Colonel Blotto game (недоступная ссылка)
- A Continuous Colonel Blotto Game
- Lotto, Blotto, or Frontrunner: An Analysis of Spending Patterns by the National Party Committees in the 2000 Presidential Election Архивировано 7 апреля 2008 года.
Ссылки
- Статья Айала Арада (Ayala Arad) и Ариеля Рубинштейна (Ariel Rubinstein) Colonel Blotto’s Top secret Files: Multi-Dimensional Iterative Reasoning in Action.
- Статья Джонатана Партингтона (Jonathan Partington) Colonel Blotto page.
- Карлин С., Математические методы в теории игр, программировании и экономике, пер. с англ., М., 1964.
- Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр М., Высшая школа, Книжный дом «Университет», 1998.