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

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

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

Термин топологическая игра была впервые введена Клод Berge , ^[1]^[2]^[3] , который определил основные идеи и формализм по аналогии с топологическими группами. Другое значение топологической игры , понятие «топологические свойства, определяемые играми», было введено в статье Растислава Телгарского ^[4], а затем в статье «Пространства, определяемые топологическими играми»; ^[5] этот подход основан на аналогиях с матричными играми, дифференциальными играми.и статистические игры, а также определяет и изучает топологические игры в топологии. Спустя более 35 лет термин «топологическая игра» получил широкое распространение и появился в нескольких сотнях публикаций. Обзорная статья Телгарского ^[6] подчеркивает происхождение топологических игр от игры Банаха – Мазура .

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

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

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

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

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

I ₀ , J ₀ , I ₁ , J ₁ , ...

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

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

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

Определения и обозначения [ править ]

Игра игры последовательность ходов

I ₀ , J ₀ , I ₁ , J ₁ , ...

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

Стратегия для игрока Р есть функция , определенная над любой правовой конечной последовательностью ходов P» противника s. Например, стратегия для игрока I является функцией s из последовательностей ( J ₀ , J ₁ , ..., J _п ) для подмножеств 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

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

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

Игра Банаха – Мазура [ править ]

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

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

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

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

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

Другие топологические игры [ править ]

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

двоичная игра введен Улам - модификация игры Банах-Мазур;
игра Банаха - играл на подмножестве вещественной прямой;
игра Шок - связанная с siftable пространств;
игра с открытием точек - в которой игрок I выбирает точки, а игрок II выбирает их открытые окрестности .

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

Более длинный список и более подробное описание см. В обзорном докладе Телгарски за 1987 год. ^[6]

См. Также [ править ]

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

Ссылки [ править ]

^ C. Berge, Топологические игры с точной информацией. К теории игр, т. 3, 165–178. Анналы математических исследований, вып. 39. Princeton University Press, Princeton, NJ, 1957.
↑ C. Berge, Теория женского образа жизни, Mém. des Sc. Матем., Готье-Виллар, Париж, 1957.
^ AR Pears, О топологических играх, Proc. Cambridge Philos. Soc. 61 (1965), 165–171.
^ Р. Telgársky, О топологических свойствах, определяемых играми, Темы в топологии (Proc. Colloq. Keszthely 1972), Colloq. Математика. Soc. Янош Бойяи, Vol. 8, North-Holland, Amsterdam 1974, 617–624.
^ Р. Telgársky, Пространства, определенные топологическими играми, Фонд. Математика. 88 (1975), 193–223.
^ a b Р. Телгарски, "Топологические игры: к 50-летию игры Банах-Мазур" , Rocky Mountain J. Math. 17 (1987), 227–276.
^ Л. А. Петросян, Топологические игры и их приложения для решения задач. I. SIAM J. Control 10 (1972), 194–202.

[1] C. Berge, Топологические игры с точной информацией. К теории игр, т. 3, 165–178. Анналы математических исследований, вып. 39. Princeton University Press, Princeton, NJ, 1957.

[2] C. Berge, Теория женского образа жизни, Mém. des Sc. Матем., Готье-Виллар, Париж, 1957.

[3] AR Pears, О топологических играх, Proc. Cambridge Philos. Soc. 61 (1965), 165–171.

[4] Р. Telgársky, О топологических свойствах, определяемых играми, Темы в топологии (Proc. Colloq. Keszthely 1972), Colloq. Математика. Soc. Янош Бойяи, Vol. 8, North-Holland, Amsterdam 1974, 617–624.

[5] Р. Telgársky, Пространства, определенные топологическими играми, Фонд. Математика. 88 (1975), 193–223.

[Telgarsky-1987-6] Р. Телгарски, "Топологические игры: к 50-летию игры Банах-Мазур" , Rocky Mountain J. Math. 17 (1987), 227–276.

[7] Л. А. Петросян, Топологические игры и их приложения для решения задач. I. SIAM J. Control 10 (1972), 194–202.

[1]