В этой статье я подробно рассматриваю проблему поиска равновесных смешанных стратегий на примере игр с нулевой суммой.
Пусть есть два игрока, A и B, которые неоднократно играют в определенную игру.
Каждый игрок в каждом розыгрыше придерживается одной из нескольких стратегий – для простоты будем считать, что количество стратегий у обоих игроков совпадает и равно 
.
При выборе 
-стратегия первого игрока и 
-стратегия второго игрока, выигрыш получит первый игрок 
, и второй игрок получит такой же проигрыш — так устроены антагонистические игры.
Эти выигрыши можно записать в виде квадратной матрицы.
: 
Игроки играют в игру несколько раз и могут использовать разные стратегии в разных играх.
Смешанный Стратегия – это вектор вероятностей, связанных с каждым чистый стратегии игроков.
Каждый игрок выбирает одну из стратегий в следующем розыгрыше в соответствии с вероятностью, определенной для него его смешанной стратегией.
Если мы обозначим через 
И 
смешанные стратегии игроков, то математическое ожидание победы первого игрока будет равно 
Пара смешанных стратегий называется баланс , если ни один игрок не может увеличить свой выигрыш, изменив свою стратегию.
Другими словами, для любой другой пары стратегий 
, 
сделанный: 
Именно сейчас мы и займемся поиском таких равновесий.
1. Равновесие
Итак, пара смешанных стратегий образует равновесие, если изменение смешанной стратегии первого игрока не может увеличить его выигрыш, а изменение смешанной стратегии второго игрока не может уменьшить его проигрыш.
Например, рассмотрим следующую матрицу выигрышей: 
В этом случае ни одна из пар чистых стратегий не является равновесной.
Допустим, первый игрок выбирает первую стратегию.
Тогда второй игрок хочет всегда выбирать первую стратегию: это приведет к меньшему проигрышу (2 против 3).
Но если второй игрок выберет первую стратегию, первый игрок предпочтет ответить стратегией номер два: так его выигрыш будет больше (4 против 1).
Однако если первый игрок выберет вторую стратегию, второй игрок также отреагирует вторым: его потери, таким образом, уменьшатся (1 против 4).
Но если второй игрок выберет вторую стратегию, первый игрок выберет первую стратегию и так далее.
Итого, при любом выборе чистых стратегий хотя бы один из игроков может изменить свой выбор таким образом, чтобы увеличить собственную выгоду.
Однако в пространстве смешанных стратегий равновесие будет найдено.
Легко проверить, что равновесием в этом случае будет пара смешанных стратегий.
,
.
В этом случае математическое ожидание выигрыша первого игрока будет равно 2,5. Нетривиально, что обязательно существует пара стратегий, образующих равновесие.
Об этом заявил известный Теорема Нэша , применяемый к антагонистическим играм.
Если смешанные стратегии
И
образуют равновесие, они оказываются решениями оптимизационных задач: 
Однако сами стратегии имеют очевидные ограничения: 
Если бы в задаче были только ограничения в виде равенств, можно было бы использовать Метод множителей Лагранжа .
Но ее применение невозможно из-за наличия ограничений в виде неравенств: каждая составляющая смешанной стратегии должна допускать вероятностную интерпретацию, а значит, не может быть отрицательной.
Рассмотрим, например, следующую матрицу выигрышей: 
Не вдаваясь в технические подробности, скажу, что использование метода множителей Лагранжа с учетом только ограничений в виде равенств
в этом случае приведет к решению 
Это связано с тем, что метод множителей Лагранжа не может учитывать ограничения в виде неравенств.
Здесь нам помогут условия Каруша-Куна-Такера.
2. Условия Каруша-Куна-Такера
Эти условия известны также как условия Куна-Таккера, а все потому, что они были впервые опубликованы в 1951 году в работе Куна и Такера, и только позже выяснилось, что Каруш сформулировал их уже в 1939 году в неопубликованной работе.
Давайте на минутку отвлечемся от теории игр и сформулируем более общую задачу оптимизации следующим образом: нам нужно найти минимум некоторой функции 
с учетом ограничений как в виде равенств, так и в виде неравенств: 
Доказано, что тогда каждая точка, являющаяся решением задачи оптимизации, удовлетворяет условиям Каруша-Куна-Таккера: 
Здесь первое условие очень похоже на соответствующие условия в методе множителей Лагранжа; последние два условия фактически дублируют ограничения исходной задачи оптимизации.
Второе и третье условия сложны.
Вместе с условием четвертым они означают следующее:
- или
, - или в конце концов
, но тогда это необходимо
.
Обычно вы можете сделать следующее:
- из условия 2 означают некоторые из
нули; - из остальных уравнений условия 2, уравнения 1 и условия 5 получить систему уравнений и найти все ее решения;
- из этих решений выбрать те, которые удовлетворяют условиям 3 и 4;
- повторить описанный алгоритм для всех возможных способов обозначения переменных из условия 2 нулями;
- из всего множества полученных решений простым перебором выбрать те, которые являются решениями исходной задачи оптимизации.
Попробуем теперь применить этот алгоритм к задаче поиска равновесных стратегий в играх с нулевой суммой.
3. Условия КПК для антагонистических игр
Выше я записал условия ККТ для задачи минимизации.Поэтому нужно сформулировать все условия в терминах задачи минимизации, плюс нужно соблюсти формальность и переписать условия в виде неравенств так, чтобы они были записаны в виде «меньше или равно нулю».
Условия для
:
:
Возьмем производные:
Теперь запишем оставшиеся условия Каруша-Куна-Такера, приведя их в некоторых местах к более удобному виду.
Для
:
:
Здесь
переменные и
уравнения.
Теперь используем условия:
, или
, а также либо
, или
.
Итак, есть 
способы означать 
переменные с нулями.
Поэтому придется решить
системы линейных уравнений, каждая из которых будет иметь
уравнения и
неизвестные (остальные обозначены нулями).
Из всех решений необходимо будет выбрать только те, которые удовлетворяют остальным ограничениям Каруша-Куна-Таккера: 
Полученный набор решений обязательно будет содержать искомое равновесие.
Рассмотрим теперь более подробно уравнения, которые получаются после приравнивания некоторых неизвестных к нулю.
В качестве примера рассмотрим следующее уравнение для некоторого
: 
Мы знаем это
может быть равно нулю, и в этом случае уравнение принимает вид 
Если
в соответствии с выбором не равно нулю, это неизвестное просто выражается через значения вектора
и смысл 
: 
В этом случае можно достаточно простым способом гарантировать, что сумма справа всегда будет положительной: для этого достаточно увеличить все значения матрицы
на какую-то очень большую сумму.
Итак, неизвестные
и по аналогии
при решении систем их можно просто исключить из рассмотрения: они всегда либо равны нулю, либо тривиально выражаются через другие неизвестные и в дальнейшем не используются; ограничения на неотрицательность этих неизвестных также выполняются автоматически.
Поэтому систему решения можно упростить: 
И ограничения становятся тривиальными: 
Итак, мы получили две независимые друг от друга системы линейных алгебраических уравнений, в каждой из которых 
неизвестный и
неизвестный.
Матрицы двух систем отличаются друг от друга транспонированием.
5. Поиск баланса
Не все полученные решения будут равновесными: условия ККТ достаточны, но не обязательны.Нам нужно явно проверить свойство равновесия.
Напомню, что парочка смешанных стратегий
,
является равновесием, если для любых других смешанных стратегий
,
сделанный:
Но проверьте это свойство на каждый возможные альтернативные смешанные стратегии, конечно, не сработают. Нам помогает то, что среди множества найденных решений всегда есть равновесие.
Это значит, что равновесие можно проверить только путем сравнения с другими полученными решениями.
Подробнее: пусть 
- все решения найдены.
Пара 
является равновесием тогда и только тогда, когда 
6. Реализация
Я разместил весь код реализации на GitHub: https://github.com/ashagraev/zero_sum_game В матрица.h
лежит простой утилитарный код: прочитать матрицу, транспонировать матрицу, решить СЛАУ.Для решения СЛАУ я использую простейший метод Гаусса с выбором ведущего элемента И тривиальный тест на вырождение .
Можно было бы реализовать лучше, но дело не в этом.
Реализация описанного алгоритма решения набора СЛАУ находится в файле kkt.cpp .
Для генерации подмножеств мы используем Коды Грея .
Чтобы совместить рекурсивный метод генерации кодов Грея с их последовательной обработкой, потребовалось немного хвастайтесь обратными вызовами .
В игре может быть более одного равновесия; причём их может быть бесконечное количество.
В любом случае нужно быть готовым к тому, что алгоритм выведет более одного решения (и все множество решений будет представлять собой некую линейную оболочку над выходными решениями).
Следовательно, сигнатура функции предполагает, что результатом будет вектор стратегий, а не одна стратегия.
И в основном, соответственно, все эти векторы выводятся .
Примеры входных матриц для программы находятся в input.txt , а результаты запуска программы на этих примерах находятся в файле вывод.txt .
Теги: #математика #Алгоритмы #теория игр #игры с нулевой суммой #Теорема Каруша-Куна-Такера
-
Понимание Hdmi
19 Oct, 24 -
Что Удобнее – Мышь Или Тачпад?
19 Oct, 24 -
Airfordable – Авиабилеты В Рассрочку
19 Oct, 24 -
Philips Imageo - Светодиодные Свечи
19 Oct, 24
