Игры Блотто

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

Хотя игра полковника Блотто была впервые опубликована Борелем (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 (неопр.). Дата обращения: 2 октября 2017. Архивировано 10 апреля 2016 года.
↑ The Colonel Blotto game (недоступная ссылка)
↑ A Continuous Colonel Blotto Game (неопр.). Дата обращения: 19 декабря 2012. Архивировано 2 октября 2012 года.
↑ 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.

[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 года.

[1]

[2]

[3]

[4]