Равновесие в игре с остановками

10

Рассмотрим следующую игру для 2 игроков:

  • Природа случайно выбирает программу
  • Каждый игрок играет число в [0, бесконечность] включительно в ответ на движение природы
  • Возьмите минимум чисел игроков и запустите программу для (до) такого количества шагов (если оба игрока не выбрали бесконечность)
  • Если программа останавливается, игрок, сыгравший минимальное число, получает 1 очко. Если программа не останавливается, этот игрок теряет 1 очко. Любой игрок, сыгравший не минимальное число, получает 0 очков, а оба игрока получают 0, если они оба играют в бесконечность.

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

Вопрос: обладает ли эта игра вычислимым равновесием по Нэшу?

Без требования вычислимости каждый игрок просто воспроизводит точное количество шагов, на которых программа останавливается (или бесконечность, если она не останавливается).

Если вы попробуете обычный аргумент диагонализации для проблемы остановки, вы обнаружите, что в смешанных стратегиях существует равновесие, поэтому очевидный подход не сразу работает. Может быть, есть какой-нибудь способ настроить его?

С другой стороны, эквивалентность вещественных замкнутых полей означает, что конечные игры с вычислимыми выигрышами имеют вычислимые равновесия . Эта игра не конечна, но пространство стратегии закрыто, а выплаты вычислимы, так что, может быть, тот же трюк можно применить с теоремой Гликсберга или что-то в этом роде? Проблема в том, что без требования вычислимости равновесие заключается в чистых стратегиях, поэтому любая попытка доказать существование вычислимого равновесия с помощью существования возможно вычислимого равновесия должна объяснить, почему равновесие понижается с чистого до смешанного.

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

Мотивация: существует общая интуиция, согласно которой самоссылка является основным блоком вычислимости, т. Е. Что любая невычислимая проблема каким-то образом встраивает самоссылку. Если игра, примерно такая, как эта, имеет вычислимое равновесие по Нэшу, это послужит доказательством этой интуиции.

ОБНОВЛЕНИЕ: Чтобы уточнить, равновесие должно быть «вычислимым» в смысле вычислимых действительных чисел: вероятности, описывающие распределение смешанной стратегии, должны быть вычислимы с произвольной точностью. (Обратите внимание, что только конечное число вероятностей будет выше любого конкретного предела точности.) Это также означает, что мы можем выбирать из произвольно близкого приближения стратегии равновесия.

lo.logic computability gt.game-theory Джон Вентворт
источник
Ваше обновление также рассматривает игры как вычислимые реальные числа? (то есть, они могут играть ряд с вероятностью 1 , не зная, или, не то, что число бесконечности?)
Разрешено ли нам знать распределение противника?
Бирн Кджос-Хэнссен
Рики: пьесы можно рассматривать как вычислимые вещественные числа, но усечение до целого числа должно доминировать над любым нецелым конечным воспроизведением, поскольку программа будет выполняться только для целого числа шагов (или бесконечности). Я не уверен, что понимаю ваш пример в скобках, поэтому я могу неправильно понять ваш вопрос.
Джон Вентворт
Бьёрн: Да. Предположим, что распределение природы известно и имеет ненулевой вес во всех действующих программах. Также предположим, что каждый игрок знает стратегию другого игрока (то есть распределение).
Джон Вентворт
@johnwentworth, используйте @ или они не увидят ваш ответ.
rus9384

Ответы:

11

Даже если у вас игра с одним игроком, вычислимое равновесие отсутствует. Подумайте о том, чтобы в программе вероятность . Любая вычислимая стратегия достигнет некоторого значения, строго меньшего единицы, или вы можете использовать его для решения проблемы остановки. Но вы можете достичь любого значения, меньшего единицы, с помощью стратегии, которая для некоторого фиксированного достаточно большого моделирует естественную программу для шагов и выводит количество шагов, которое требуется программе для остановки, если останавливается в шагах, в противном случае - бесконечность.1/2iitjtjjt

Лэнс Фортноу
источник
Мне нравится эта конструкция - она ​​устанавливает, что любое равновесие по Нэшу должно играть правильно для всех программ. Существует дополнительный шаг, чтобы установить, что он решает проблему остановки, поскольку распределения должны сходиться только к идеальной производительности в пределе высокой точности (и, следовательно, бесконечные вычисления). Поскольку мы знаем, что результат должен помещать единичный вес в одно целое число, я думаю, что достаточно вычислить вероятности стратегии с точностью до 1/4, а затем взять любое целое число, имеющее вес больше 1/2.
Джон Вентворт