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

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

Игра названа в честь мифического Полковника Блотто из работы Гроса и Вагнера (Gross and Wagner) 1950 года . Полковник был обязан найти оптимальное распределение своих солдат по 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 году, одни из самых близких по рейтингу претендентов, были смоделированы как Игра Блотто. В работе утверждается, что Гор имел стратегию, которая привела бы его к выигрышу, но он её не нашёл.

См. также

Примечания

Ссылки

• Статья Айала Арада (Ayala Arad) и Ариеля Рубинштейна (Ariel Rubinstein) .
• Статья Джонатана Партингтона (Jonathan Partington) .
• Карлин С., Математические методы в теории игр , программировании и экономике, пер. с англ., М., 1964.
• Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр М., Высшая школа, Книжный дом «Университет», 1998.