Блото игра
Игра «Полковник Блотто» — это разновидность игры с постоянной суммой для двух человек , в которой игрокам (офицерам) поручено одновременно распределять ограниченные ресурсы по нескольким объектам (полям боя). В классической версии игры игрок, вложивший наибольшее количество ресурсов на поле битвы, побеждает в этом поле битвы, а выигрыш (или выигрыш) равен общему количеству выигранных полей битвы.
Впервые игру предложил Эмиль Борель. [1] в 1921 г. В 1938 г. Борель и Вилле опубликовали особую оптимальную стратегию («дисковое» решение). [2] Игра была изучена после Второй мировой войны учеными из отдела исследования операций и стала классикой теории игр . [3] Гросс и Вагнер, 1950 год. [4] В исследовательском меморандуме изложена оптимальная стратегия Бореля, а также вымышлены имена полковника Блотто и врага. Для трех и более полей сражений пространство чистых стратегий является многомерным (два измерения для трех полей сражений), и, таким образом, смешанная стратегия представляет собой распределение вероятностей по непрерывному множеству. Игра представляет собой редкий пример нетривиальной игры такого типа, в которой можно явно найти оптимальные стратегии.
Помимо приложений военной стратегии, игра «Полковник Блотто» имеет приложения к политической стратегии (распределение ресурсов на полях политических сражений), сетевой защите, гонкам за патентами на исследования и разработки и стратегическим решениям о найме. Предположим, что две спортивные команды с ограниченным бюджетом (или два факультета экономики с грантами «используй или проиграешь») преследуют один и тот же набор кандидатов и должны выбирать между множеством скромных предложений или агрессивным преследованием подмножества кандидатов.
Пример [ править ]
В качестве примера игры «Блотто» рассмотрим игру, в которой каждый из двух игроков записывает по три положительных целых числа в неубывающем порядке так, чтобы их сумма составляла заранее заданное число 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 каждый является оптимальной вероятностной стратегией.
Игра Бореля аналогична приведенному выше примеру для очень большого S, но игроки не ограничены круглыми целыми числами. Таким образом, у них есть бесконечное количество доступных чистых стратегий, фактически континуум.
Эта концепция также реализована в истории Сунь Бина ( 田忌赛马 ), когда он наблюдает за гонками на колесницах, в которых одновременно проводятся три разные гонки. В гонках у каждой стороны была возможность иметь одну команду колесниц в каждой гонке, и каждый предпочитал использовать стратегию 1, 2, 3 (где 3 — самая быстрая колесница, а 1 — самая медленная) для размещения своих колесниц между тремя. гонки, приносящие близкие победы в каждой гонке и мало надежных результатов для победителей. Когда его спросили, как победить, Сунь Бин посоветовал владельцу колесницы изменить расстановку на 2, 3, 1. Хотя он наверняка проиграет гонку против самых быстрых колесниц (3 колесницы); он выигрывал каждую из остальных гонок: его 3 колесницы легко побеждали 2 колесницы, а его 2 колесница побеждала 1 колесницу.
Случай двух полей битвы [ править ]
В более простом случае двух полей битвы Макдонелл и Мастронарди (2015) впервые дали полную характеристику всех равновесий Нэша для канонической простейшей версии игры полковника Блотто. Это решение, которое включает в себя графический алгоритм для характеристики всех стратегий равновесия Нэша, включает ранее не идентифицированные стратегии равновесия Нэша, а также помогает определить, какого поведения никогда не следует ожидать рациональным игрокам. Стратегии равновесия Нэша в этой версии игры представляют собой набор двумерных вероятностных распределений: распределения по набору возможных распределений ресурсов для каждого игрока, часто называемые смешанными равновесиями Нэша (например, можно найти в играх «Бумага-камень-ножницы» или «Сопоставление»). Копейки как гораздо более простые примеры).
Решение, доказательство и графический алгоритм Макдонелла и Мастронарди, 2015 г. для определения стратегий равновесия Нэша также относятся к обобщенным версиям игры, например, когда полковник Блотто имеет разные оценки полей сражений, когда их ресурсы имеют разную эффективность на двух полях сражений (например, на одном поле битвы). включает высадку на воду, а ресурсы полковника Блотто — морские пехотинцы, а не солдаты) и дает представление о версиях игры с тремя или более полями боя.
Рассмотрим двух игроков (полковника Блотто и Врага), два поля боя, оба имеют равную ценность, оба игрока знают общий уровень ресурсов друг друга до распределения, а затем они должны одновременно принять решение о распределении. Часто предполагается, что полковник Блотто является более обеспеченным ресурсами офицером (его уровень ресурсов можно определить равным 1), а у врага доля ресурсов меньше 1. Стратегии распределения и выигрыши в равновесии Нэша зависят от этого соотношения уровней ресурсов.
Приложение [ править ]
Эта игра обычно используется как метафора предвыборной борьбы, когда две политические партии выделяют деньги или ресурсы для привлечения поддержки фиксированного числа избирателей. [5] [6] Каждый избиратель – это «поле боя», на котором может победить та или иная партия. Эта же игра также находит применение в теории аукционов, где участники торгов должны делать одновременные ставки. [7]
Несколько вариантов оригинальной игры были решены Жаном-Франсуа Ласлиером . [8] Брайан Роберсон, [9] and Dmitriy Kvasov. [10]
См. также [ править ]
Ссылки [ править ]
- ^ Теория игры и интегральные уравнения с кососимметричными ядрами (перевод французской статьи 1953 года « Теория игры и интегральные уравнения с левосимметричным ядром »)
- ^ Эмиль Борель и Жан Виль. Применение теории вероятностей к азартным играм . Готье-Виллар, Париж, 1938 г. Перепечатано в: Э. Борелем и А. Шероном «Математическая теория моста, доступная каждому» , Editions Jacques Gabay, Париж, 1991 г.
- ^ Гильермо Оуэн, Теория игр, Academic Press (1968)
- ^ Непрерывная игра полковника Блотто
- ^ Р. Майерсон «Стимулы для развития привилегированных меньшинств в условияхальтернативные избирательные системы» American Political Science Review 87(4):856–869, 1993 г.
- ^ Ласлье, Ж.-Ф.; Пикард, Н. (2002). «Распределительная политика и электоральная конкуренция». Журнал экономической теории . 103 : 106–130. дои : 10.1006/jeth.2000.2775 .
- ^ Сентеш, Б.; Розенталь, Р. (2003). «Одновременные аукционы с тремя объектами и двумя участниками: палочки для еды и тетраэдры». Игры и экономическое поведение . 44 : 114–133. дои : 10.1016/s0899-8256(02)00530-4 .
- ^ Ж.-Ф. Ласлиер, «Цели партии в предвыборной борьбе по принципу «раздели доллар»» в: Социальный выбор и стратегические решения, Очерки в честь Джеффа Бэнкса, под редакцией Д. Остина-Смита и Дж. Даггана, Спрингер, стр. 113–130 ( 2005)
- ^ Б. Роберсон, Игра «Полковник Блотто» [ мертвая ссылка ]
- ^ Квасов, Д. (2007). «Конкурсы с ограниченными ресурсами». Журнал экономической теории . 136 : 738–748. дои : 10.1016/j.jet.2006.06.007 .
Внешние ссылки [ править ]
- Совершенно секретные файлы полковника Блотто: многомерные итеративные рассуждения в действии, Аяла Арад и Ариэль Рубинштейн
- Джонатана Партингтона Страница полковника Блотто