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

[Arks]

xagiwo в сообщении #1557212 писал(а):

А? Нет, в исходной стратегии первый ход всегда пропускался, а значит, в построенной по нашей "наивной" тактике стратегии пропускаются вообще все ходы (потому что мы ходим так, как будто сейчас первый ход)

А все, понял

[novichok2018]

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

[xagiwo]

novichok2018
Пусть у нас есть цифры 0,110101, тогда мы знаем, что первый ход был 1, второй — 1, третий — 0 и т. д. Изначальный вопрос о сильных стратегиях тривиален, потому что любая стратегия сильная. Для игры с выбором отрезков это не так.
Хотя да, по сути игры одни и те же.

[mihaild]

Для множества первой категории и отрезка вроде бы можно построить стационарную стратегию для второго игрока и без аксиомы выбора. Раз множество первой категории, рассмотрим его как объединение последовательности нигде не плотных множеств $X_n$. Пронумеруем рациональные отрезки, и каждым ходом возьмем отрезок с минимальным номером, который 1) можно брать; 2) если $n$ такое, что $X_n$ пересекается с нашим множеством, а предыдущие - нет, то отрезок не пересекается с $X_n$.
Без аксиомы выбора я не уверен, что вообще верно, что наличие выигрышной стратегии у второго эквивалентно тому, что множество первой категории.
В "The Banach-Mazur game and Banach category theorem" Oxtoby доказывает эту эквивалентность с использованием аксиомы выбора, и она там нужна в обе стороны. В сторону "если первой категории, то есть стратегия" срабатывает и без аксиомы выбора если есть счетная база (второму игроку нужно выбирать ход с нужным свойством), в другую сторону вроде бы срабатывает без аксиомы выбора только если множество допустимых ходов счетно.

Но это всё для второго игрока (который хочет пустое пересечение), для первого всё сложнее.

[xagiwo]

mihaild в сообщении #1557285 писал(а):

Но это всё для второго игрока (который хочет пустое пересечение), для первого всё сложнее.

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

-- 13.06.2022, 22:02 --

mihaild в сообщении #1557285 писал(а):

в другую сторону вроде бы срабатывает без аксиомы выбора только если множество допустимых ходов счетно.

Я подозреваю, что исходная игра с точки зрения выигрышных стратегий эквивалентна такой, в которой выбираются только рациональные отрезки (если стратегия $f(\text{предыстория})$ выигрышная, то выигрышная будет и $g(\text{предыстория})$, где $g(\text{предыстория})$ — рациональный подотрезок в $f(\text{предыстория})$;; любую "нерациональную" предысторию можно легко заменить на рациональную).

[novichok2018]

В книге Кановея говорится, что для всех разумных множеств в каком то смысле больших или маленьких утверждение АД можно доказать и без неё. В том числе для множеств первой категории. Значит в этом случае можно доказать существование выигрышной стратегии у одного из игроков, без АД. Наверное, выше говорится примерно об этом.

[mihaild]

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

xagiwo в сообщении #1557293 писал(а):

если стратегия $f(\text{предыстория})$ выигрышная, то выигрышная будет и $g(\text{предыстория})$, где $g(\text{предыстория})$ — рациональный подотрезок в $f(\text{предыстория})$;; любую "нерациональную" предысторию можно легко заменить на рациональную

Нельзя, у новой стратегии может получиться предыстория, невозможная для старой, и про неё нет никаких гарантий.

novichok2018 в сообщении #1557315 писал(а):

Значит в этом случае можно доказать существование выигрышной стратегии у одного из игроков, без АД. Наверное, выше говорится примерно об этом.

Нет, вопрос в том, как из стратегии (функции из предыстории в ход) сделать тактику (функцию из текущего состояния в ход). Ну точнее, когда из существования стратегии следует существование тактики.

[xagiwo]

mihaild в сообщении #1557317 писал(а):

Нельзя, у новой стратегии может получиться предыстория, невозможная для старой, и про неё нет никаких гарантий.

Ой, да, я это упустил. Но можно считать стратегию второго игрока зависящей только от совершённых ранее ходов первого — ходы второго по стратегии восстанавливаются, так что это одно и то же. И тогда этой проблемы не возникает.

-- 13.06.2022, 23:34 --

Если внятнее описать, что я имею в виду (предполагая стратегии зависящими от ходов 1-го игрока):
1) если есть выигрышная стратегия в обычной игре, то есть выигрышная в рациональной. Пусть $f(k,B_1,...,B_k) = f(B_1,...,B_k)$ — стратегия второго игрока, где $B_i$ — все ходы первого игрока с начала игры. Пусть $g(B_1,...,B_k)$ — первый (в смысле некоторой нумерации) рациональный подотрезок в $f(B_1,...,B_k)$. Тогда $g$ — выигрышная в рациональной игре.
Действительно, пусть $B_1, C_1, B_2, C_2, ...$ — рациональная игра согласно стратегии $g$. Тогда возможна обычная игра вида $B_1, C_1', B_2, C_2',...$ согласно стратегии $f$ (или, что то же самое, для $C_i' = f(B_1, ..., B_i)$ верно $B_i \supset C_i' \supset B_{i+1}$. Но $B_i \supset C_i'$, потому что $C_i'$ это ход, совершённый после $B_i$ и $C_i' \supset B_{i+1}$, потому что $C_i' \supset C_i \supset B_{i+1}$). Тогда второй побеждает в исходной игре $\Leftrightarrow$ $B_1 \cap B_2 \cap ...$ не содержит точек из $A$ $\Leftrightarrow$ второй побеждает в модифицированной игре.

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

[mihaild]

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

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

[xagiwo]

Только сегодня прочитал статью.

mihaild в сообщении #1557430 писал(а):

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

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