← rota-baxter-winning-games
CSCAT2024__main0.tex
\documentclass[12pt, portrait,aspectratio=169]{beamer}
% \documentclass[12pt]{beamer}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{array}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{pifont}
\graphicspath{ {images/} }
\newtheorem{proposition}{Proposition}
\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\X}{\mathbb{X}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\gS}{\mathbb{S}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\id}[1]{\mathrm{id}_{#1}}
\newcommand{\Pf}{\mathcal{P}_{\mathrm{fin}}}
\newcommand{\Set}{\mathrm{Set}}
\newcommand{\Gs}{\mathbf{Games}}
\newcommand{\nsum}{\oplus}
\newcommand{\Alg}[1]{\mathrm{Alg}_{#1}}
\newcommand{\Coalg}[1]{\mathrm{Coalg}_{#1}}
\newcommand{\PfAlg}{\Alg{\Pf}}
\newcommand{\PfCoalg}{\Coalg{\Pf}}
\newcommand{\mex}[1]{\mathrm{mex}(#1)}
\newcommand{\m}{\mathrm{mex}}
\newcommand{\G}[2]{\mathcal{G}_{#1}(#2)}
\newcommand{\rel}{\to}
\newcommand{\red}{\mathrm{red}}
\newcommand{\cp}{\ast}
\newcommand{\acc}{\rightsquigarrow}
\newcommand{\str}{\theta}
\newcommand{\Image}{\mathrm{Im}}
\newcommand{\HF}{\mathbb{HF}}
\newcommand{\Nim}[1]{\mathrm{Nim}_{#1}}
\newcommand{\Her}{\mathbb{H}}
\newcommand{\epi}{twoheadrightarrow}
\newcommand{\mono}{rightarrowtail}
\newcommand{\h}{\mathrm{h}}
\newcommand{\ADJ}[4]
{
\begin{tikzcd}[ampersand replacement = \&, column sep = small]
{#1}
\ar[rr, shift right=1.3ex, "{#2}"']
\&\perp\&
{#3}
\ar[ll, shift right=1.3ex,"{#4}"']
\end{tikzcd}
}
\newcommand{\cmark}{\ding{51}}%
\newcommand{\xmark}{\ding{55}}%
\DeclarePairedDelimiter{\gen}{\langle}{\rangle}
% 定理環境の色の設定
\setbeamercolor{block title theorem}{bg=red!30, fg=black} % 定理環境のタイトル部分の色を変更
\setbeamercolor{block body theorem}{bg=red!10, fg=black} % 定理環境の本文部分の色を変更
% 命題環境の色の設定
\setbeamercolor{block title proposition}{bg=red!30, fg=black} % 命題環境のタイトル部分の色を変更
\setbeamercolor{block body proposition}{bg=red!10, fg=black} % 命題環境の本文部分の色を変更
% 定義環境の色の設定
\setbeamercolor{block title definition}{bg=blue!30, fg=black} % 定義環境のタイトル部分の色を変更
\setbeamercolor{block body definition}{bg=blue!10, fg=black} % 定義環境の本文部分の色を変更
% 例環境の色の設定
\setbeamercolor{block title example}{bg=green!30, fg=black} % 例環境のタイトル部分の色を変更
\setbeamercolor{block body example}{bg=green!10, fg=black} % 例環境の本文部分の色を変更
\usetheme{Darmstadt}
\usecolortheme{seahorse}
\setbeamertemplate{items}[default]
\setbeamertemplate{navigation symbols}{}
\AtBeginSection[]
{
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}
}
\title{Combinatorial games as recursive coalgebras}
\author{Ryuya Hora}
% \institute{Graduate School of Mathematical Sciences, University of Tokyo/ National Institute of Informatics}
% \date{\today}
\date{March 15, 2024}
\begin{document}
\frame{\titlepage}
\begin{frame}\frametitle{Self Introduction}
{\Huge \textbf{Ryuya Hora}}
\begin{itemize}
\item M2 student at the University of Tokyo
\item RA at the National Institute of Informatics
\item (One of) the organizers of Japan Combinatorial Game Theory Workshop!
\end{itemize}
Recently I've been studying
\begin{itemize}
\item topos,
\item automata, and
\item $\infty$-categories.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{This talk in one slide}
\end{frame}
% \section{Front matter}
\section[Introduction]{Introduction: Bouton's theorem}
\begin{frame}{Nim}
\begin{itemize}
\item In the game \textbf{$n$-heap nim}, first, $n$ heaps of stones are given.
\item Two players take turns choosing one heap and removing at least one stone from that heap.
\item The player who is unable to take a stone loses.
\end{itemize}
\memo{write}
\end{frame}
\begin{frame}\frametitle{Bouton's theorem}
\begin{definition}
The \emph{Nim-sum} $\nsum$ is \dq{bit-wise xor}, i.e., an abelian group structure on $\N$, induced by the binary expansion $\N \overset{\simeq}{\to} \bigoplus_{k=0}^{\infty} \Z/2\Z$.
\end{definition}
\begin{example}
$5\nsum 7 = (101)_2 \nsum (111)_2 = (010)_2 = 2$
\end{example}
\begin{theorem}[{[Bouton, Ann. of Math., 1902]}]
A state of $n$-heap nim $(a_1, \dots ,a_n)$ is winning state if and only if $a_1 \nsum \dots \nsum a_n =0$.
\end{theorem}
\begin{example}
$(1,2,3),(0,1,1), (2,2,0)$ are winning states of the $3$-heap nim.
\end{example}
\end{frame}
\begin{frame}\frametitle{Definition of games}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}
A \emph{game} is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
\begin{enumerate}
\item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
\item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
\end{enumerate}
\end{definition}
\begin{example}
\begin{itemize}
\item \cmark 21-game $(\{0,1, \dots 21\}, x\to x' \colon \iff x'-x \in \{1,2,3\})$
\item \cmark $(\N,>)$ but \xmark $(\Z, >)$
\item \cmark Nim (Stone-taking game) $(\N^n,\to)$
\end{itemize}
\end{example}
\end{column}
\begin{column}{0.2 \textwidth}
\begin{figure}
\centering
\includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Conway addition of games}
\begin{definition}
The Conway addition $(X,\to_X) + (Y,\to_Y)$ of two games is the game $(X\times Y, \to_{+})$, where
\begin{itemize}
\item the underlying set is the cartesian product $X\times Y$, and
\item the relation $\to_{+}$ is defined by
\[
(x,y)\to_{+} (x', y') \iff (x\to_{X} x' \land y= y') \lor (x= x' \land y\to_{Y} y')
\]
\end{itemize}
\end{definition}
\end{frame}
\begin{frame}{Nim-sum theorem}
\begin{theorem}[Nim-sum theorem [see CGT, Siegel]]
\end{theorem}
\end{frame}
\begin{frame}\frametitle{Motivation}
Where does the nim-sum come from?
Why is the nim-sum useful?
\end{frame}
\section[Games $\to$ Recursion]{Games $\to$ Recursion: Recursion in game theory}
\begin{frame}\frametitle{Section 1 in one slide}
\begin{itemize}
\item \textbf{Combinatorial games} are games \dq{without factors of chance,} and are formalized using graph theory.
\item A fundamental technique in combinatorial game theory is to define a \textbf{recursive value} for each position of the game and to calculate it.
\item In this section, we define \textbf{the category of games}, which is the main subject of this talk, in the language of graph theory.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Recursion 1: Winning/Losing states}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}
A \emph{game} is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
\begin{enumerate}
\item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
\item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
\end{enumerate}
\end{definition}
\end{column}
\begin{column}{0.2 \textwidth}
\begin{figure}
\centering
\includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Recursion 2: Birthday}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}
A \emph{game} is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
\begin{enumerate}
\item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
\item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
\end{enumerate}
\end{definition}
\end{column}
\begin{column}{0.2 \textwidth}
\begin{figure}
\centering
\includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Recursion 3: Grundy number}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}
A \emph{game} is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
\begin{enumerate}
\item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
\item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
\end{enumerate}
\end{definition}
\end{column}
\begin{column}{0.2 \textwidth}
\begin{figure}
\centering
\includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Game morphisms}
\begin{definition}
A \emph{game morphism} $f\colon (X,\to_{X})\to(Y,\to_{Y})$ is a function $f\colon X \to Y$ that satisfies the following two conditions:
\begin{enumerate}
\item (Graph map) if $x\to_{X} x'$ then $f(x) \to_{Y} f(x')$.
\item (Lifting property) if $f(x) \to_{X} y$, then there exists $x\to_{X} x'$ such that $f(x') = y$.
\end{enumerate}
\end{definition}
\memo{Put an example.}
\end{frame}
\begin{frame}\frametitle{}
\begin{proposition}
Game morphisms preserve
\begin{itemize}
\item Winning/Losing states,
\item Birthday,
\item Grundy numbers,
\item (and any "recursive data.")
\end{itemize}
\end{proposition}
\begin{example}
The terminal game
\end{example}
\end{frame}
\section[Games $\leftarrow$ Recursion]{Games $\leftarrow$ Recursion: Defining games using recursion}
\begin{frame}\frametitle{Section 2 in one slide}
\begin{itemize}
\item Games = Recursive $\Pf$-coalgebras
\item Game morphisms = $\Pf$-coalgebra morphisms
\item Recursive data of games are $\Pf$-algebras (and associated morphisms)
\item
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Algebra/Coalgebra of an endofunctor}
\begin{definition}
For a category $\C$ and an endofunctor $T\colon \C \to \C$,
\begin{itemize}
\item A $T$-algebra is a pair $(A,\alpha)$ of an object $A$ of $\C$ and a morphism $\alpha\colon TA \to A$.
\item A $T$-coalgebra is a pair $(X,\theta)$ of an object $X$ of $\C$ and a morphism $\theta\colon X \to TX$.
\end{itemize}
\end{definition}
\begin{example}
We will consider the case where $\C=\Set$ and $T= \Pf\colon \Set \to \Set$. In this case,
\begin{itemize}
\item A $\Pf$-algebra is a function $\Pf(X) \to X$.
\item A $\Pf$-coalgebra is a function $X \to \Pf(X)$, i.e., a graph whose vertices have finite out-degree.
\pause \textbf{Games are $\Pf$-coalgebras.}
\end{itemize}
\end{example}
\end{frame}
\begin{frame}\frametitle{Coalgebra-Algebra morphism and Recursive coalgebra}
\begin{definition}[Coalgebra-algebra morphism]
% For a category $\C$ and an endofunctor $T$,
A \emph{coalgebra-algebra} morphism from a $T$-coalgebra $(X,\theta)$ to a $T$-algebra $(A, \alpha)$ is a morphism $f\colon X \to A$ such that the following diagram commutes.
\[
\begin{tikzcd}[ampersand replacement=\&]
X \ar[r,"f"]\ar[d,"\theta"]\&A\\
TX \ar[r,"Tf"]\&TA\ar[u,"\alpha"']
\end{tikzcd}
\]
\end{definition}
\begin{definition}[Recursive coalgebra]
A $T$-coalgebra $(X,\theta)$ is \emph{recursive} if for any $T$-algebra $(A,\alpha)$, there uniquely exists a coalgebra-algebra morphism $(X,\theta)\to (A, \alpha)$.
\end{definition}
\end{frame}
\begin{frame}\frametitle{Games = Recursive coalgebra}
\begin{theorem}
The category of games $\Gs$ is equivalent to the category of recursive $\Pf$-coalgebras.
\end{theorem}
\begin{proof}
We can check the following two claims by concrete calculations:
\begin{itemize}
\item A $\Pf$-coalgebra $(X, \theta)$ is recursive if and only if its corresponding graph
% $(X, \{(x,x')\mid x' \in \theta(x)\})$
$(X, x' \in \theta(x))$
\item For two $\Pf$-coalgebras $(X,\theta),(X',\theta)$, a function $f\colon X \to X'$ is a $\Pf$-coalgebra morphism if and only if $f$ is a game morphism.
\end{itemize}
\end{proof}
\end{frame}
\begin{frame}\frametitle{Recursive values = algebras}
% Any $\Pf$-algebra $(A,\alpha)$ defines \dq{recursive data} for games
% \[
% \{\h_{X,A}\colon X \to A\}_{(X,\to)\text{: game}}
% \]
\begin{corollary}
Let $(A, \alpha)$ be a $\Pf$-algebra.
For any game $(X, \to)$, there exists a unique function $\h_{X,A}\colon X\to A$ such that
\[
\h_{X,A}(x) = \alpha(\{\h_{X,A}(x')\mid x\to x'\})
\]
\end{corollary}
\begin{example}
W/L states
\[
\Pf(\{W,L\}) \ni
\]
\end{example}
\memo{Write}
\end{frame}
\section[Application]{Application: Theorem schema for Nim-sum theorem}
\begin{frame}\frametitle{Meta scheme for Grundy-type theorem}
% In this section, let $\otimes$ be a monoidal structure on $\Gs$
For a monoidal structure $\otimes$ on $\Gs$ and a $\Pf$-algebra $(A,\alpha)$,
\begin{theorem}
if the forgetful functor $U \colon \Gs \to \Set$ is lax monoidal, then
\end{theorem}
\end{frame}
\section{Applications and Future works}
\begin{frame}\frametitle{Categorical structure of games}
\begin{proposition}
The category of games $\Gs$
\begin{itemize}
\item is locally finitely presentable (and in particular, complete and cocomplete).
\item has a subobject classifier.
\item admits (Epi, Mono) factorization system.
\item is NOT cartesian closed.
\end{itemize}
\end{proposition}
\end{frame}
\begin{frame}\frametitle{Unifying other game theories}
\end{frame}
\begin{frame}\frametitle{Differential structure on Games}
\end{frame}
\end{document}
\begin{frame}\frametitle{}
\end{frame}