\documentclass{fit-teorsem}

%-------------------------------------------------------------------------------
%                 Fill in seminar information
%-------------------------------------------------------------------------------
\lecturername{Radovan Červený}
\lectureremail{cervera3@fit.cvut.cz}
\papertitle{On the Shortest Path Game}
\paperauthors{Andreas Darmann, Ulrich Pferschy, Joachim Schauer}
\paperlink{http://www.sciencedirect.com/science/article/pii/S0166218X15003959}

%-------------------------------------------------------------------------------
%                 Use custom packages
%-------------------------------------------------------------------------------
\usepackage{enumitem}
\usepackage{amsmath}


\begin{document}
%-------------------------------------------------------------------------------
%                 Print seminar header
%-------------------------------------------------------------------------------
\maketsheader
%-------------------------------------------------------------------------------
%                 Create your content!
%-------------------------------------------------------------------------------
\thispagestyle{empty}

\section*{Definitions}

\subsection*{Shortest Path Game}
\begin{itemize}
    \setlength\itemsep{-1mm}

    \item game setting: (un)directed graph $G = (V,E)$; edges have non-negative cost $c(e):E\rightarrow R^+_0$; two designated vertices $s,t \in V(G)$
    \item two players $A,B$ start in $s$; players move together along the edges and take turns in selecting the next vertex to be visited; the deciding player pays the cost of the edge; total costs payed by players are given by $C(A)$, $C(B)$
    \item $A$ starts i.e. A has first decision in $s$, game ends the first time $A$ and $B$ step on $t$
    \item[$\Rightarrow$] each player selfishly minimizes his total cost payed

    \item[] \textbf{Additional rules}

    \item[\textbf{(R1)}] no player can select an edge which does not permit a path to vertex $t$
    \item[\textbf{(R2)}] the players cannot select an edge which implies necessarily a cycle of even length
    \item[$\Rightarrow$] gives us \textit{perfect information finite game in extensive form}
    \item \textit{subgame perfect equilibrium (spe)} is a strategy that is a Nash equilibrium for every subgame of the original game
    \item \textit{spe-path} is a unique path from $s$ to $t$ in $G$ corresponding to the unique subgame perfect equilibrium
\end{itemize}


\subsection*{Problems}

\begin{figure}[!h]
\vspace{-2mm}
\hspace{1mm}
\begin{tabular}{ l  l }
\multicolumn{2}{l}{\textsc{Shortest Path Game}} \\
  Input: & edge-weighted graph $G=(V,E)$, vertices $s,t$, values $C_A, C_B \in R^+_0$  \\
  Decide: & does spe-path yield costs $c(A) \leq C_A$ and $c(B) \leq C_B$? \\
\end{tabular}
\vspace{-5mm}
\end{figure}

% \begin{figure}[!h]
% \hspace{1mm}
% \begin{tabular}{ l  l }
% \multicolumn{2}{l}{\textsc{Vertex Geography}} \\
%     Description: & on oriented graph $G=(V,E)$, two players start from vertex $s$, \\
%             & players move together and take turns in selecting the next vertex, \\
%             &the player who can not select a next vertex loses  \\
%
%   Input: & oriented graph $G=(V,E)$, vertex $s$  \\
%   Decide: & does first player have a winning strategy? \\
% \end{tabular}
% \vspace{-5mm}
% \end{figure}

\begin{figure}[!h]
\hspace{1mm}
\begin{tabular}{ l  l }
\multicolumn{2}{l}{\textsc{Quantified 3-SAT}} \\
  Input: & set $X = {x_1,\ldots,x_n}$ of variables, quantified formula $F = (\exists x_1)(\forall x_2)(\exists x_3)\ldots(\forall x_n) \phi(x_1,\ldots,x_n)$\\
        & where $\phi$ is a 3-CNF formula over $X$ \\
  Decide: & is $F$ true? \\
\end{tabular}
\vspace{-7mm}
\end{figure}

\section*{Theorems}

\begin{itemize}[leftmargin=*]
\setlength\itemsep{-1mm}

\item[]\textbf{Theorem 1.} \textsc{Shortest Path Game} is \textit{PSPACE-complete} even for bipartite directed graphs.

\item[]\textbf{Theorem 2.} The spe-path of \textsc{Shortest Path Game} on DAGs can be computed in $O(|E|)$ time.

\item[]\textbf{Theorem 3.} \textsc{Shortest Path Game} on undirected graphs is \textit{PSPACE-complete} even for bipartite graphs.

\item[]\textbf{Theorem 4.} The spe-path of \textsc{Shortest Path Game} on undirected cactus graphs can be computed in $O(|V|^2)$ time.
\end{itemize}

\subsection*{Cactus algorithm}
Let $G = (V,E)$ is a undirected \textit{cactus graph} -- each edge is part of at most one simple cycle.
\begin{enumerate}
\setlength\itemsep{-1mm}

\item Recognize \textit{connection strip} $G'$ in $G$
\item Recognize cycles in $G \setminus G'$ and determine order in which we need to preprocess them.
\item Preprocess $G \setminus G'$ in a bottom-up fashion computing \textit{swap options} to be used in $G'$
\item Compute spe-path in $G'$ taking swap options into account.
\end{enumerate}

\noindent
Let $d_{p}^{\pm}(i)$ be general distance $d$ from vertex $i$ to a fixed vertex, where $p \in \{d,f\}$ denotes \textit{decider}, \textit{follower} role and $\pm \in \{+,-\}$. If $\pm = +$ player deciding in $i$ is the same as player deciding in $v_0 = 0$, otherwise $\pm = -$.

\paragraph{\textbf{Step 3 dynamic programming arrays}}
\begin{itemize}[leftmargin=*]
\setlength\itemsep{-1mm}
\item $tc_{p}^{\pm}(i)$ $:=$ min. cost to move from $i$ back to $0$ if a turn around is possible.
\item $rc_{p}^{\pm}(i)$ $:=$ min. cost to move from $i$ back to $0$ with no turn possible and the path goes around the cycle.
\end{itemize}

\end{document}