Игры Блотто

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

Хотя игра полковника Блотто была впервые опубликована Борелем (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] В работе утверждается, что Гор имел стратегию, которая привела бы его к выигрышу, но он её не нашёл.

См. также

Примечания

  1. ↑ The Theory of Play and Integral Equations with Skew Symmetric Kernels. Дата обращения: 2 октября 2017. Архивировано 10 апреля 2016 года.
  2. ↑ The Colonel Blotto game (недоступная ссылка)
  3. ↑ A Continuous Colonel Blotto Game. Дата обращения: 19 декабря 2012. Архивировано 2 октября 2012 года.
  4. ↑ 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.