Топологическая игра

В математике топологическая игра — это бесконечная игра с совершенной информацией , в которую играют два игрока в топологическом пространстве . Игроки выбирают объекты с топологическими свойствами, такими как точки, открытые множества , закрытые множества и открытые покрытия . Время, как правило, дискретно, но пьесы могут иметь трансфинитную продолжительность, и были предложены расширения непрерывного времени. Условия победы игрока могут включать такие понятия, как топологическое замыкание и сходимость .

Оказывается, некоторые фундаментальные топологические конструкции имеют естественный аналог в топологических играх; примерами этого являются свойство Бэра , пространства Бэра , свойства полноты и сходимости, свойства разделения, свойства покрытия и базисности, непрерывные изображения, множества Суслина и сингулярные пространства. В то же время некоторые топологические свойства, естественным образом возникающие в топологических играх, могут быть обобщены за пределы теоретико-игрового контекста: в силу этой двойственности топологические игры широко используются для описания новых свойств топологических пространств и для объяснения известных свойств. другой свет. Существуют также тесные связи с принципами отбора .

Термин «топологическая игра» впервые ввёл Клод Берже . определивший основные идеи и формализм по аналогии с топологическими группами . Другое значение топологической игры , концепция «топологических свойств, определяемых играми», было введено в статье Растислава Тельгарского: а позже «пространства, определяемые топологическими играми»; этот подход основан на аналогиях с матричными играми, дифференциальными играми и статистическими играми и определяет и изучает топологические игры в рамках топологии. Спустя более чем 35 лет термин «топологическая игра» получил широкое распространение и появился в нескольких сотнях публикаций. Обзорная статья Телгарского подчеркивает происхождение топологических игр от игры Банаха–Мазура .

Есть два других значения топологических игр, но они используются реже.

• Термин топологическая игра, введенный Леоном Петросяном. при изучении антагонистических игр преследования-уклонения . Траектории в этих топологических играх непрерывны во времени.
• Игры Нэша ( игры Hex ), игры Милнора (Y-игры), игры Шепли (игры на проективной плоскости) и игры Гейла ( игры Bridg-It назвал топологическими играми ) Дэвид Гейл в своем приглашенном обращении [1979/] . 80]. Число ходов в этих играх всегда конечно. Открытие или повторное открытие этих топологических игр относится к 1948–49 годам.

Базовая установка для топологической игры

Многие структуры могут быть определены для бесконечных позиционных игр с совершенной информацией.

Типичная установка — это игра между двумя игроками, I и II которые поочередно выбирают подмножества топологического пространства X. , В n -м раунде игрок I разыгрывает подмножество I _n из X , а игрок II отвечает подмножеством J _n . существует раунд Для каждого натурального числа n , и после того, как все раунды сыграны, игрок I побеждает, если последовательность

Я ₀ , Дж ₀ , Я ₁ , Дж ₁ ,...

удовлетворяет некоторому свойству, в противном случае выигрывает игрок II .

Игра определяется целевым свойством и разрешенными ходами на каждом этапе. Например, в игре Банаха-Мазура BM ( X ) разрешенные ходы представляют собой непустые открытые подмножества предыдущего хода, и игрок I выигрывает, если $\bigcap _{n}I_{n}\neq \emptyset$.

Эта типичная установка может быть изменена различными способами. Например, вместо того, чтобы быть подмножеством X , каждый ход может состоять из пары $(I,p)$ где $I\subseteq X$ и $p\in x$. Альтернативно, длина последовательности ходов может иметь некоторый порядковый номер, отличный от ω .

Определения и обозначения

• Ход игры представляет собой последовательность допустимых ходов.

Я ₀ , Дж ₀ , Я ₁ , Дж ₁ ,...

Результатом игры является либо победа, либо поражение каждого игрока.

• Стратегия — это игрока P функция, определенная для каждой допустимой конечной последовательности ходов P. противника Например, стратегия для игрока I — это функция s от последовательностей ( J ₀ , J ₁ , ..., J _n ) до подмножеств X . Говорят, что игра ведется в соответствии со стратегией s , если каждый ход игрока P имеет значение s в последовательности предыдущих ходов противника. Итак, если s — стратегия игрока I , то игра

$s(\lambda ),J_{0},s(J_{0}),J_{1},s(J_{0},J_{1}),J_{2},s(J_{0},J_{1},J_{2}),\ldots$

согласно стратегии s . (Здесь λ обозначает пустую последовательность ходов.)

• Стратегия игрока P называется выигрышной, если каждая игра в соответствии со стратегией s приводит к победе игрока P при любой последовательности допустимых ходов P. противника Если игрок P имеет выигрышную стратегию для игры G , это обозначается $P\uparrow G$. Если у любого из игроков есть выигрышная стратегия для G , то G называется определённым. следует Из аксиомы выбора , что существуют недетерминированные топологические игры.
• Стратегия P является стационарной , если она зависит только от последнего хода противника P ; стратегия - это Маркова , если оно зависит как от последнего хода противника , так и от порядкового номера хода.

Игра Банаха-Мазура

Основная статья: Игра Банаха – Мазура

Первой изученной топологической игрой была игра Банаха–Мазура, которая является мотивирующим примером связи между теоретико-игровыми понятиями и топологическими свойствами.

Пусть Y — топологическое пространство, а X — подмножество Y , называемое выигрышным множеством . Игрок I начинает игру, выбирая непустое открытое подмножество. $I_{0}\subseteq Y$, и игрок II отвечает непустым открытым подмножеством $J_{0}\subseteq I_{0}$. Игра продолжается таким же образом: игроки поочередно выбирают непустое открытое подмножество предыдущей игры. После бесконечной последовательности ходов, по одному на каждое натуральное число, игра окончена, и я выигрываю тогда и только тогда, когда

$X\cap \bigcap _{n\in \omega }I_{n}\neq \emptyset .$

Теоретико-игровые и топологические связи, демонстрируемые игрой, включают:

• II имеет выигрышную стратегию в игре тогда и только тогда, когда X принадлежит к первой категории в Y (множество относится к первой категории или скудно , если оно представляет собой счетное объединение нигде не плотных множеств ).
• Если Y — полное метрическое пространство , то у меня есть выигрышная стратегия тогда и только тогда, когда в некотором X сходится подмножестве Y. непустом открытом
• Если X обладает свойством Бэра в Y , то игра определена.

игры

Некоторые другие известные топологические игры:

• бинарная игра, предложенная Уламом — модификация игры Банаха–Мазура;
• игра Банаха — играется на подмножестве реальной линии;
• игра Шоке — связанная с просеиваемыми пространствами;
• игра с открытыми точками - в которой игрок I выбирает точки , а игрок II выбирает открытые их окрестности;
• игры с выбором — каждый игрок раунда I выбирает (топологическую) коллекцию, а II выбирает члена или конечное подмножество этой коллекции. См. Принцип выбора § Топологические игры .

За прошедшие годы было предложено множество других игр, в том числе для изучения: Куратовского принципа коредукции ; свойства разделения и редукции множеств в близких проективных классах; сита Лузина ; инвариантная дескриптивная теория множеств ; Наборы Суслина ; теорема о замкнутом графике ; перепончатые пространства ; MP-пространства; аксиома выбора ; вычислимые функции . Топологические игры также связаны с идеями математической логики , теории моделей , бесконечно длинных формул , бесконечных строк чередующихся кванторов, ультрафильтров , частично упорядоченных множеств и хроматического числа бесконечных графов.

Более длинный список и более подробный отчет см. в обзорной статье Телгарского 1987 года.

См. также

• Топологическая головоломка