Игры Блотто

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Смотри также[править | править исходный текст]

Внешние ссылки[править | править исходный текст]

  • Статья Джонатана Партингтона (Jonathan Partington) Colonel Blotto page
  • Карлин С., Математические методы в теории игр, программировании и экономике, пер. с англ., М., 1964.
  • Петросян Л.А., Зенкевич Н.А., Семина Е.А Теория игр М., Высшая школа, Книжный дом 'Университет', 1998

Ссылки[править | править исходный текст]