Практические применения паритетных игр

Существуют ли примеры практического применения паритетных игр, то есть систем, в реальном мире, которые можно представить как паритетные игры?

Обычно связанная документация по паритетным играм практически никогда не имеет практического примера этого приложения.

Это довольно отличное приложение от того, что вы могли иметь в виду. Линейное программирование имеет много практических применений. Существует много алгоритмов для линейного программирования, и те, которые основаны на симплекс-методе Джорджа Данцига, являются одними из наиболее часто используемых. Важный параметр симплекса называется правилом поворота. Виктор Клее и Джордж Минти предоставляют набор многогранников, для которых правило поворота, предложенное Данцигом, потребует экспоненциального числа поворотов. С тех пор примеры, демонстрирующие экспоненциальную нижнюю границу, были обнаружены почти для каждого детерминированного правила поворота.

Однако Simplex может использовать рандомизированные правила поворота. Гил Калай в 1992 году ввел рандомизированное правило поворота и доказал субэкспоненциальную верхнюю оценку симплекса с этим правилом. Также в 1992 году Миха Шарир и Эмо Вельцль определили задачи типа LP, которые включают стандартное линейное программирование, и вместе с Иржи Матушеком также предложили рандомизированные варианты симплекса и доказали субэкспоненциальные верхние оценки для этого варианта. Субэкспоненциальные нижние оценки были также обнаружены для задач типа LP, но до 2010 года не было конкретных примеров линейных программ, на которых эти нижние оценки могли бы быть продемонстрированы. Смотрите эти два поста в блоге Джила Калаи о другом рассказе этой истории, связи с гипотезой Хирша и ссылками на литературу.

Какое отношение это имеет к паритетным играм? Для настройки соединения требуется пара шагов. Открытой проблемой в исследованиях паритетных игр до 2009 года было определение, могут ли определенные алгоритмы итерации политики для решения паритетных игр иметь экспоненциальное поведение. См. Статьи Марцина Юрдзиньского, чтобы узнать больше об этом. Оливер Фридман, начиная с 2009 года , продемонстрировал примеры игр с четностью, в которых определенные алгоритмы итерации политики требовали экспоненциального времени. Используя связь между играми четности и некоторыми задачами типа LP, он вывел субэкспоненциальные нижние оценки для различных правил поворота для симплекса. (Заметим, однако, что один из результатов, который касался алгоритма Random Facet, был показан Оливером Фридманом, Томасом Хансеном и Ури Цвиком быть ошибочным.)

Я надеюсь, вы согласитесь, что это довольно увлекательный и убедительный пример применения паритетных игр.

На ваш вопрос также есть более прямой ответ. Предположим, что кто-то хочет спроектировать отдельный контроллер, который регулирует поведение некоторой физической системы (термостат, химический завод и т. Д.) На основе состояния системы и состояния окружающей среды. Вопрос о том, существует ли контроллер для предоставления гарантий, необходимых разработчику, может быть сведен к решению игр с четностью. Таким образом, вы можете думать о паритетной игре с точки зрения систем, сред и контроллеров.

Другой параметр - это анализ программы. Предположим, вы хотите автоматически определить, удовлетворяет ли программа некоторому свойству корректности в модальном -calculus. Проверка моделей является одним из подходов к решению этой проблемы, и проверка моделей calculus тесно связана с играми на четность. $\mu$$\mu$