Введение
Тип игры, в которой игроки распределяют ограниченные ресурсы по нескольким объектам на полях сражений Игра с полковником Блотто - это тип игры с постоянной суммой для двух человек, в которой игрокам (офицерам) поручено одновременно распределять ограниченные ресурсы по нескольким объектам (поля сражений). В классической версии игры, игрок, посвятивший больше всего ресурсов на поле боя, выигрывает это поле боя, а выигрыш (или выгода) равен общему количеству выигранных полей боя. Игра была впервые предложена Эмилем Борелем в 1921 году. В 1938 году Борель и Вилле опубликовали конкретную оптимальную стратегию ("дисковое" решение). Игра была изучена после Второй мировой войны учеными в исследовании операций и стала классикой в теории игр. В исследовательском меморандуме Гросса и Вагнера 1950 года указывается оптимальная стратегия Бореля и придумываются вымышленные имена полковника Блотто и Врага. Для трех и более полей сражения пространство чистых стратегий является многомерным (двухмерным для трех полей сражения), а смешанная стратегия, таким образом, является распределением вероятности по непрерывному множеству. Игра является редким примером нетривиальной игры такого рода, где оптимальные стратегии могут быть явно найдены. В дополнение к военным стратегическим приложениям, игра "Полковник Блотто" имеет применение к политической стратегии (распределение ресурсов по политическим полям сражений), сетевой обороне, патентным гонкам в области НИОКР и стратегическим решениям о найме. Представьте себе две спортивные команды с ограниченным бюджетом (или два отделения экономики с использованием или потерей грантов) ищут одного и того же набора кандидатов и должны решить между многими скромными предложениями или агрессивным преследованием подмножества кандидатов.
A Colonel Blotto game is a type of two person constant sum game in which the players (officers) are tasked to simultaneously distribute limited resources over several objects (battlefields). In the classic version of the game, the player devoting the most resources to a battlefield wins that battlefield, and the gain (or payoff) is equal to the total number of battlefields won. The game was first proposed by Émile Borel in 1921. In 1938 Borel and Ville published a particular optimal strategy (the "disk" solution). The game was studied after the Second World War by scholars in Operation Research, and became a classic in game theory. Gross and Wagner's 1950 research memorandum states Borel's optimal strategy, and coined the fictitious Colonel Blotto and Enemy names. For three battlefields or more, the space of pure strategies is multi dimensional (two dimensions for three battlefields) and a mixed strategy is thus a probability distribution over a continuous set. The game is a rare example of a non trivial game of that kind where optimal strategies can be explicitly found. In addition to military strategy applications, the Colonel Blotto game has applications to political strategy (resource allocations across political battlefields), network defense, R&D patent races, and strategic hiring decisions. Consider two sports teams with must spend budget caps (or two Economics departments with use or lose grants) are pursuing the same set of candidates, and must decide between many modest offers or aggressive pursuit of a subset of candidates.
Случай двух полей сражений
В более простом случае двух полей сражения Макдонелл и Мастронарди 2015 года предоставляют первую полную характеристику всех равновесий Нэша в канонической простой версии игры полковника Блотто. Это решение, которое включает графический алгоритм для характеристики всех стратегий равновесия Нэша, включает ранее неидентифицированные стратегии равновесия Нэша, а также помогает определить, какое поведение никогда не должно ожидаться рациональными игроками. Стратегии равновесия Нэша в этой версии игры представляют собой набор бивариативных распределений вероятности: распределения по набору возможных распределений ресурсов для каждого игрока, часто называемые смешанными равновесиями Нэша (такие, как можно найти в Paper Rock Scissors или Matching Pennies как гораздо более простые примеры). Решение, доказательство и графический алгоритм Макдональ и Мастронарди 2015 для определения стратегий равновесия Нэша также относится к обобщенным версиям игры, например, когда у полковника Блотто разные оценки полей сражения, когда их ресурсы имеют разную эффективность на двух полях сражения (например, одно поле сражения включает в себя водяную посадку, а ресурсы полковника Блотто - морские пехотинцы вместо солдат), и дает представление о версиях игры с тремя или более полях сражения. Рассмотрим двух игроков (полковника Блотто и врага), два поля боя, оба равных по стоимости, оба игрока знают общий уровень ресурсов друг друга до распределения, и они должны принять решение о одновременном распределении. Часто предполагается, что полковник Блотто является офицером с большим количеством ресурсов (его уровень ресурсов может быть определен как 1), а у Врага есть часть ресурсов меньше, чем 1. Стратегии распределения и выигрыш в равновесии Нэша зависят от этой связи уровня ресурсов.
Применение
Эта игра обычно используется в качестве метафоры для избирательной конкуренции, когда две политические партии выделяют деньги или ресурсы, чтобы привлечь поддержку определенного числа избирателей. Каждый избиратель - это "поле битвы", которое может выиграть одна или другая партия. Эта же игра также применяется в теории аукциона, где участники торгов должны делать одновременные ставки. Несколько вариаций оригинальной игры были решены Жаном Франсуа Ласлье, Брайаном Роберсоном и Дмитрием Квасовым.