\input amstex
\loadbold
\documentstyle{gsm}

\Monograph
\NoBlackBoxes
\input epsf

\define\({[}
\define\){]}
\font\bmi=cmmib10
\font\msbm=msbm10
\font\cmmi=cmmi10
\font\sf=cmss10
\font\sc=cmcsc10
\font\tit=cmr10 scaled\magstep2
\font\sfa=cmss10 scaled\magstep1
\font\msbm=msbm10
\define\IZ{\hbox{\msbm\char'132}}
\define\NP{N\hskip -2pt P}
\UseAMSsymbols
\catcode`\@=11
\def\bqed{\ifhmode\unskip\nobreak\fi\quad
  \ifmmode\blacksquare\else$\m@th\blacksquare$\fi}
\def\mex{\qopname@{mex}}
\let\oldbigcup=\bigcup
\def\bigcup{\DOTSB\mathop{\textstyle\oldbigcup}\slimits@}
\let\oldbigcap=\bigcap
\def\bigcap{\DOTSB\mathop{\textstyle\oldbigcap}\slimits@}
\catcode`\@=13
\vglue1.5cm
\centerline{\tit Combinatorial Game Theory Foundations}\vskip0.2cm 
\centerline{\tit Applied to Digraph Kernels}
\vskip1.5cm
\centerline{{\sfa Aviezri S.\ Fraenkel}}
\vskip0.5cm
\centerline{{\it Department of Applied Mathematics and Computer Science}}
\centerline{{\it Weizmann Institute of Science}}
\centerline{{\it Rehovot 76100, Israel}}
\vskip 0.5cm
\centerline{{\tt fraenkel\@wisdom.weizmann.ac.il}}
\centerline{{\tt http://www.wisdom.weizmann.ac.il/\~{}fraenkel/fraenkel.html}}
\vskip 1.0cm
\centerline{Submitted: August 29, 1996;\quad Accepted: November 21, 1996}
\vskip 2.1cm
\centerline{{\sf To Herb Wilf at the end of the first $5$ {\sl Bar Mitzvahs}:}}
\centerline{{\sf At least $5$ more in ever increasing joy and creativity}}
%\vskip0.8cm
{\bf Abstract} 
Known complexity facts: the decision problem of the existence of a kernel 
in a digraph $G=(V,E)$ is NP-complete; if all of the cycles of $G$ have 
even length, then $G$ has a kernel; and the question of the number of kernels
is $\#$P-complete even for this restricted class of digraphs. In the 
opposite direction, we construct game theory tools, of independent 
interest, concerning strategies in the presence of draw positions, to show 
how to partition $V$, in $O(|E|)$ time, into $3$ 
subsets $S_1,S_2,S_3$, such that $S_1$ lies in all the kernels; $S_2$ lies 
in the complements of all the kernels; and on $S_3$ the kernels may be 
nonunique. Thus, in particular, digraphs with a ``large'' number 
of kernels are those in which $S_3$ is ``large''; possibly $S_1=S_2=\emptyset$.
We also show that $G$ can be decomposed, in  $O(|E|)$ time, 
into two induced subgraphs $G_1$, with vertex-set $S_1\cup S_2$,
which has a unique kernel;  
and $G_2$, with vertex-set $S_3$, such that any kernel $K$ of $G$ is the 
union of the kernel of $G_1$ and a kernel of $G_2$. In 
particular, $G$ has no kernel if and only if $G_2$ has none. Our results 
hold even for some classes of infinite digraphs.
\font\smcp=cmcsc8 
          \headline={\ifnum\pageno>1 {\smcp the electronic journal of
combinatorics 4 (no. 2) (1997), \#R10\hfill\folio} \fi}
\vskip3.0cm
\document 
%\head 1. Introduction\endhead
\centerline{{\bf 1. Introduction}}
\vskip0.2cm
Modern combinatorial game theory has largely been a parasite: it drew 
tools and results from fields such as logic, computational complexity, graph 
and matroid theory, combinatorics,
algebra and number theory to generate results for itself. More recently, it 
has also begun to contribute back to some of its benefactors, such as to
surreal numbers, a subject created by John Conway \cite{Con1976}, and to 
linear error-correcting codes (which is linear algebra) \cite{CoS1986}, 
\cite{Con1990}, \cite{BrP1993}, \cite{Fra1996}. 
%We may also include 
%in this list areas in combinatorial game-theory itself, which have
%benefited from other areas of combinatorial game theory.

In this paper we develop some basic concepts of 2-player game theory, 
and use them to shed new light on the structure of digraph kernels.
Connections between kernels and game-theory have been explored in the past,
see e.g. Berge \cite{Ber1992}; the new element here seems to be the use 
of draw positions for investigating digraph kernels. In fact, the set of
draw positions appears to be the ``kernel of the kernels'', i.e., the part
where many of the interesting properties of the kernels are concentrated.
 
Throughout a digraph is a finite or infinite directed graph, which may 
contain cycles or loops, unless otherwise specified.
A {\it kernel} of a digraph $G=(V,E)$ is a subset $K\subseteq V$ which
is both independent and dominating. ``Independent'' means that the 
subgraph induced by $K$ has no edges (so in particular: no loops); and 
``dominating'' --- that every vertex of $V-K$ has a follower (successor) 
in $K$, i.e., an edge leading into $K$. If $G$ is finite, 
the decision problem of the existence of a kernel is NP-complete, see
Chv\'atal \cite{Chv1973} and van Leeuwen  \cite{VLe1976} for a general digraph,
and Fraenkel \cite{Fra1981} for a planar digraph with indegrees $\leq 2$,
outdegrees $\leq 2$ and degrees $\leq 3$. For any tighter constraints the 
problem is clearly solvable in linear time. 
It is further known that a finite digraph all of whose cycles have even length
has a kernel \cite{Ric1953}, and that the question of the number of 
kernels is $\#$P-complete even for this restricted class of digraphs 
\cite{SzC1994}. 
%Some such digraphs can indeed have an exponential number 
%of kernels---see Fig.~1.

As an example, consider a digraph with $2k+1$ vertices and $k$ 
``blades'', as depicted in Fig.~1 for $k=4$. It clearly has 
$2^k$ kernels. The center vertex is in the kernel if and only if 
all its $k$ followers are not. Note that there is no vertex which 
is in all the kernels or in the complement of all the kernels for 
this example.

\midinsert\vskip 1.0truecm
\centerline{\epsfysize 5.0cm \epsffile{cgt_1.eps}}
\botcaption{Figure 1. {\rm The case $k=4$ of a digraph with $2k+1$ vertices
and $2^k$ kernels.}}\endcaption
\endinsert 
%%\midinsert\vskip 12truecm
%%\botcaption{Figure 9. {\rm A {\it menorah\/} waiting to be labeled.}}
%%\endcaption
%%\endinsert\par

Despite all the inefficiency and chaos exuded by these results, we exhibit 
in this paper a nice structure of digraph kernels; and we show that 
the inefficiency part can be localized and contained within a well-defined 
induced subgraph of $G$. 
Moreover, if $G$ is finite, all of this can be done in $O(|E|)$ steps.

Specifically, we show that for a class of infinite digraphs $G=(V,E)$, 
there exists a partition of $V$ into $3$ subsets $S_1,S_2,S_3$, 
such that $S_1$ lies 
in all the kernels; $S_2$ lies in the complements of all the kernels; and on
$S_3$ the kernels may be nonunique. For $G$ finite, the partition can 
be found in $O(|E|)$ steps. In general we cannot be more 
precise about what happens in $S_3$, a region where the NP-completeness 
reigns, but in special cases one may be able to say something; see e.g., 
the paragraph after Corollary~5. Note that if a 
digraph has a ``large'' number of kernels, then $S_3$ must be 
``large''; possibly $S_1=S_2=\emptyset$. But $S_3$ may be large 
when there are only few 
kernels: if $G$ is an $n$-gon, then $S_3=V$ and there are $\leq 2$
kernels. Of course $S_1=S_2=\emptyset$ and $S_3=V$ is always a trivial
solution, but for many digraphs, especially those with a small number of 
edges, as found, e.g., in many game-graphs, $S_3$ is small.
Furthermore, we show that there exists a decomposition of $G$ into 
two induced subgraphs $G_1$, with vertex-set $S_1\cup S_2$, which has a 
unique kernel; and $G_2$, with vertex-set $S_3$, such that any kernel $K$ 
of $G$ is the union of the kernel of $G_1$ and a kernel of $G_2$. In 
particular, $G$ has no kernel (a unique kernel) if and only if $G_2$ has no 
kernel (a unique kernel). 

%Moreover, for $G$ finite, e.g., an all-even-cycle digraph, we show how 
%to accomplish the partition and decomposition in $O(|E|)$ steps. 
It will also become clear 
that these results are proved most naturally in a game-theoretic setting; in 
fact, they can be understood best in terms of the strategy of the following 
simple coin-pushing game played on $G$. Initially a coin is placed on some 
vertex of $G$. Two players alternate moves. A move consists of sliding the 
coin to a follower vertex $v$, which could be $v$ itself, if the move 
is along a loop (``passing''). The player first unable to move loses, 
and the other player wins. In the case of an infinite or cyclic digraph, 
there may be no last move: none of the players can force a win, but each 
has always a nonlosing move. In this case the outcome is a draw.

The tools from combinatorial game theory, which are of independent interest,
concern basic strategies in the presence of possible draw positions, and
efficient computational algorithms for implementing them. They appear to be
the most natural tools for revealing the structure of digraph kernels. 
Specifically, we present two equivalent definitions for the 
losing/winning/drawing-positions in possibly infinite games, and some of their 
ramifications, including the {\sl Fundamental Theorem of Game Theory}.

%\head 2. Some Foundational Combinatorial Game Theory\endhead
\centerline{{\bf 2. Some Foundational Combinatorial Game Theory}}
\vskip0.2cm
{\it Combinatorial games}, or simply {\it games} in the sequel, consist of 
2-person games with perfect information (unlike some card games where
information is hidden), without chance moves (no dice), and {\it outcome\/}
restricted to lose/win, tie/tie and draw/draw for the two
players who {\it move\/} alternately. A tie is an end position 
with no winner and no loser, as may occur in tic-tac-toe for example. A 
draw is a ``dynamic tie", i.e., a non-end position such that neither player 
can force a win, but each can always find a non-losing move. A 
{\it position\/} of a game is any state which is reachable in any play 
of the game, including play with collusion. The play's 
outcome function is defined on a subset of game positions, called
the {\it termination set\/} $\tau$. The player, if any, who first reaches 
a position in $\tau$ won.  
The most common convention is {\it normal} play,
where the player first unable to play loses and the opponent wins, i.e., 
$\tau$ is the set of end positions; the 
outcome is reversed in the mis\`ere convention. If there is no last move, 
the outcome is a draw. We restrict our attention to games without ties, because
ties behave much like the other outcomes we consider.

With any game $\Gamma$ we 
associate a digraph $G=(V,E)$, where $V$ is the set of positions of 
$\Gamma$ and $(u,v)\in E$ if and only if there is a move from position 
$u$ to position $v$. It is called the {\it game-graph\/} of $\Gamma$.

Thus any game corresponds to a digraph, namely its game-graph.
Conversely, given any digraph $G$, we can define a game whose game-graph
is $G$: initially place a token on any vertex. The 2 players alternate
in pushing the token to a follower. Because of this correspondence between 
digraphs and games, we shall identify games with their corresponding 
game-graphs, game positions with digraph vertices and game moves with 
digraph edges, using them interchangeably.

For $u\in V$, the sets
$$F(u)=\{v\in V:(u,v)\in E\},\qquad F^{-1}(u)=\{w\in V:(w,u)\in E\}$$
are called the set of {\it followers\/} and the set of {\it predecessors\/}
respectively. If $F(u)=\emptyset$, then $u$ is a {\it leaf} of $G$.

Informally, given any finite or infinite game $\Gamma$, a $P$-{\it position\/}
is any position $u$ from which ``the {\it P}revious player can force a win'', 
that is, the opponent of the player moving from $u$ can reach a position 
in $\tau$ in a {\sl finite} --- though perhaps {\sl unbounded} --- 
number of moves, independently of the moves of the opponent. 
An $N$-{\it position\/}
is any position $v$ from which ``the {\it N}ext player can force a win'',
that is, the player who moves from $v$. A  $D$-{\it position\/} is any 
position from which ``a player cannot force a win but has a next nonlosing 
move''. The outcome is then a {\it D}raw. The set of all $P,N,D$-positions 
of a game is denoted by $\Cal P,\Cal N,\Cal D$ respectively.

The game-graph may be infinite, so $|V|$ is a finite or transfinite 
ordinal. The reader who so prefers can always think of the ordinals in the 
sequel as being nonnegative integers. 
 
The following is a formal definition of these notions.

\definition{\bf Definition 1} Given a game $\Gamma$ without ties 
which may contain cycles or loops, or may be infinite, with arbitrary 
termination set $\tau$. Let $G=(V,U)$ be the game-graph of $\Gamma$.  
Here and in the sequel we denote by $\Cal O$ the set of all ordinals 
not exceeding $|V|$. By recursion on $n\in\Cal O$ define,
$$\multline 
P_n=\{u\in V: n=\min m, F(u)\subseteq\bigcup_{i<m} N_i\}, \\
N_n=\{u\in V: n=\min m, F(u)\cap\bigcup_{i<m} P_i\ne\emptyset\}.
\endmultline$$ 
Finally, we let $\Cal P=\bigcup_{n\in\Cal O} P_n$, 
$\Cal N=\bigcup_{n\in\Cal O} N_n$, $\Cal D=V\setminus(\Cal P\cup\Cal N)$.  
\enddefinition\indent

Definition~1 doesn't contain any claim about the computational 
complexity of finding a strategy. We now illustrate Definition~1 
on hand of a few examples.\medskip

{\sc Example 1.} Rabin's game \cite{Rab1957} has fixed length 3. It has the
form I picks $x_1$, II picks $x_2$, I picks $x_3$. Player~I wins if and only
if $G(x_1, x_2, x_3)=0$. The function $G$ is chosen so that player~II has 
a winning strategy, which, however, is not decidable. Other pathological
games appear in \cite{Jon1982} and in \cite{JFr1995}.

{\sc Example 2.} For the two vertices of Fig.~2(a), the only labels 
consistent with Definition~1 are $D$; in particular, the labels $P_0$ 
for one and 
$N_1$ for the other are inconsistent with Definition~1. In Fig.~2(b), 
the subscripts $0$ and $2$ of the $P$-positions cannot be interchanged.
\midinsert\vskip 1.0truecm
\centerline{\epsfysize 4.0cm \epsffile{cgt_2.eps}}
\botcaption{Figure 2. {\rm Games on simple cyclic digraphs.}}
\endcaption\endinsert
{\sc Example 3.} Consider the game $G=(V,E)$ where $V=\IZ^0\cup\{-1\}$. 
Every positive integer $m$ 
has a unique follower $m-1$, and $0$ has no follower, so is a leaf;
and the followers of $-1$ are all the positive odd integers. 
It is easy to see that then $P_{2i}=\{2i\}$, $N_{2i+1}=\{2i+1\}$ 
for all $i\in\IZ^0$, and $P_{\omega}=\{-1\}$.  

{\sc Example 4.} The game is a digraph $G=(V,E)$, where the vertex set 
consists of {\sl pairs} of nonnegative integers, namely, 
$V=\{(i,j):j\geq 2i+1, i\in\{0,\dots ,t\}\}\cup \{(0,0)\}$, where $t$ 
is some fixed positive integer. See Fig.~3 for the case $t=2$. The unique
follower of $(i,2j)$ is $(i,2j-1)$ for $j\geq i+1$. The followers of $(i,2j+1)$
for $j\geq i+1$ are $(i,2j)$, $i\in\{0,\dots ,t\}$, and 
$\{(i+1,2k): k\geq j+1\}$, $i\in\{0,\dots ,t-1\}$. The followers of
$(0,0)$ are $\{(0,2j):j\geq 1\}$. Thus the set of all leaves is 
$\{(i,2i+1): i\in\{0,\dots ,t\}\}$.
\midinsert\vskip 1.0truecm
\centerline{\epsfysize 10.0cm \epsffile{cgt_3.eps}}
\botcaption{Figure 3. {\rm The case $t=2$ of Example~4.}}
\endcaption\endinsert
Definition~1 implies that
$$\align
P_0&=\{(i,2i+1):i\in\{0,\dots ,t\}\},\ N_1=\{(i,2i+2):i\in\{0,\dots ,t\}\},\\
P_{2+2i}&=\{(t,2t+2i+3):i\in\IZ^0\},\ N_{3+2i}=\{(t,2t+2i+4):i\in\IZ^0\},\\
P_{\omega+2i}&=\{(t-1, 2(t-1)+2i+3):i\in\IZ^0\},\\ 
N_{\omega+2i+1}&=\{(t-1, 2(t-1)+2i+4):i\in\IZ^0\},\\
P_{\omega 2+2i}&=\{(t-2, 2(t-2)+2i+3):i\in\IZ^0\},\\ 
N_{\omega 2+2i+1}&=\{(t-2, 2(t-2)+2i+4):i\in\IZ^0\},\\
&\qquad\qquad\dots\dots \\
P_{\omega t+2i}&=\{(0,2i+3):i\in\IZ^0\},\ 
N_{\omega t+2i+1}=\{(0,2i+4):i\in\IZ^0\}.
\endalign$$

{\sc Example 5.} The game is as in Example~4, except that there is no 
bound $t$. Specifically, $V=\{(i,j):j\geq 2i+1, i\in\IZ^0\}$, and the
same follower function is defined, except that $i\in\IZ^0$ instead of the
dependence on $t$. The set of leaves is then $P_0=\{(i,2i+1):i\in\IZ^0\}$, 
and all their predecessors satisfy $N_1=\{(i,2(i+1)):i\in\IZ^0\}$. 
But all the other positions are $D$-positions.\medskip 

\proclaim{\bf Lemma 1} Let\/ $G=(V,E)$ be a cyclic, possibly infinite,
game-graph. Then for every\/ $u\in V$ we have,\par
$u\in\Cal P$ if and only if\/ $F(u)\subseteq\Cal N$,\par
$u\in\Cal N$ if and only if\/ $F(u)\cap\Cal P\ne\emptyset$,\par
$u\in\Cal D$ if and only if\/ $F(u)\cap\Cal P=\emptyset$ and\/ 
$F(u)\cap\Cal D\ne\emptyset$.
\endproclaim

\demo{\bf Proof} Let $u\in\Cal P$. Then $u\in P_n$ for some $n\in\Cal O$,
so $F(u)\subseteq\bigcup_{i<n} N_i$, hence $F(u)\subseteq\Cal N$. 
The middle part is proved similarly. Now by definition, $u\in\Cal D$ 
if and only if $u\notin(\Cal P\cup\Cal N)$, if and only if 
$F(u)\cap\Cal P=\emptyset$ (otherwise $u\in\Cal N$ by the second 
part), {\sl and\/} $F(u)\cap\Cal D\ne\emptyset$ (because otherwise 
$F(u)\subseteq\Cal N$, and so $u\in\Cal P$ by the first part). 
\bqed\enddemo 
\proclaim{\bf Corollary 1} Under the assumptions of Lemma~\rom{1}, 
$u\in\Cal D$ if and only if\/ $F(u)\subseteq\Cal N\cup\Cal D$ and 
$F(u)\cap\Cal D\ne\emptyset$.
\endproclaim 
\demo{\bf Proof} Follows from $F(u)\cap\Cal P=\emptyset$ of Lemma~1
and Definition~1. 
\bqed\enddemo


Is it clear that precisely one of the players can always win, or else both can
draw, as in the above examples? The answer is given by what we shall call 
the {\sl Fundamental Theorem of Combinatorial Game Theory}, analogously to 
the Fundamental Theorem of Algebra or Arithmetic.

\proclaim{\bf Theorem 1} Let\/ $\Gamma$ be a two-person game with 
perfect information, no chance moves and no ties ending in 
lose/win or draw/draw, 
whose game-graph may be infinite. For any termination 
set and every position of\/ $\Gamma$ there exists a winning move for 
precisely one of the two players, or else, both players can maintain 
an infinite sequence of drawing moves, but neither can force a win\/.
\endproclaim

\demo{\bf Proof} The last part of Lemma~1 implies that both players 
can maintain a draw from a $D$-position, but neither can force a win. 
By Definition~1, each vertex has at least one label in 
$\Cal P\cup\Cal N\cup\Cal D$.  
It thus suffices to show that the set $S$ of positions of
$\Gamma$ has a {\sl unique\/} partition into three subsets $\Cal P$, 
$\Cal N$ and $\Cal D$.

Suppose $w\in\Cal P\cap\Cal N$. Then let the players play to $w$,
possibly using collusion. Starting from $w$, both the Next and the
Previous player can win --- a contradiction to the only possible outcomes 
lose/win and draw/draw. We get similar contradictions when assuming
$\Cal P\cap\Cal D\neq\emptyset$ or $\Cal N\cap\Cal D\neq\emptyset$.\bqed
\enddemo
We point out that Definition~1, Lemma~1 and Theorem~1 are generalizations of
previous results by various authors who considered only the outcome 
(win, lose). Classical theorems of Zermelo \cite{Zer1912}, von Neumann 
\cite{VNe1928} and von Neumann and Morgenstern \cite{VNM1953} state that 
every finite length 2-person game ends in (lose, win). If, in addition, 
we restrict attention to games whose length of play is bounded, the proof 
becomes simpler. See Mark Kac \cite{Kac1974} who attributes the result to 
Hugo Steinhaus. The result is stated as follows.

\proclaim{\bf Theorem *} Let\/ $G$ be a\/ $2$-person game with perfect 
information, terminating in a {\sl bounded} number of moves in a win
by one of the players. Then there must exist a winning move for either
one or the other adversary.\endproclaim

\demo{\bf Proof} Denote the moves of players~1 and 2 by $x_1,x_2,\ldots ,x_n$
and $y_1,y_2,\ldots ,y_n$ respectively. Assuming that player~I begins to
play, we can express the fact that player~1 has a winning move by,
$$(\exists x_1)(\forall y_1)\ldots (\exists x_n)(\forall y_n)\qquad 
\text{player~I won}.$$

The negation of this statement is obtained by De Morgan's rule:

$$(\forall x_1)(\exists x_2)\ldots (\forall x_n)(\exists y_n)\qquad
\text{player~I did not win}.$$
This, however, is clearly the statement that player~II won.\bqed\enddemo 

The same proof appears in Jones \cite{Jon1982}. The proof is valid 
only for games whose number of moves is bounded by a constant, otherwise 
the negation doesn't necessarily proclaim that player~II won. A finite 
number of moves isn't good enough. Steinhaus proposed to make 
Theorem~* an axiom for the case of infinite play, so there wouldn't be any 
draws: play would always terminate in a finite, if unbounded, number of 
moves, with precisely one of the two players winning. Infinite play was 
also treated by Gale and Stewart \cite{GaS1953}, where it was shown that 
{\sl both} players may have a winning strategy if the axiom of choice, 
rather than Steinhaus' axiom, is adopted.  
Their games are somewhat different; the outcome is determined by the 
concatenation of the (infinite number of) moves, rather than by reaching 
a set of terminals. No draws are considered there. 
\medskip
Theorem~1 implies that every position in a game without ties has a unique 
$P$-, $N$- or $D$\/-label. If the game-graph of $\Gamma$ is finite and acyclic,
then Theorem~1 reduces to the classical result that every position has a 
unique $P$- or $N$\/-label. The finiteness and acyclicity requirements 
are sufficient but not necessary; the 
dichotomy result holds also for certain families of infinite or cyclic 
games, e.g., for the game of Example~3; even if there are loops on any 
subsets of the odd-indexed vertices. 

How can we compute the $P$-, $N$-, $D$\/-labels? Can
Lemma~1 help? Lemma~1 is unsatisfactory in at least two respects.

(a) It does not {\sl characterize} the $P$-, $N$- and $D$\/-labels. 
%This does {\sl not} mean that for any partition 
%$V=\Cal P'\cup\Cal N'\cup\Cal D'$ satisfying the conditions of Lemma~I we
%have $\Cal P'=\Cal P,\ \Cal N'=\Cal N,\ \Cal D'=\Cal D$. 
See Fig.~2(a), where
labels $P$ and $N$ on the two vertices satisfy the conditions of Lemma~1;
but so does the labeling of both of them by $D$, and only the latter
is the unique labeling satisfying Theorem~1.

(b) The player moving from an $N$-position may find it difficult to
consummate a win.
A token on the vertex labeled $N$ in Fig~2(b)can indeed be pushed to the 
leaf, thus realizing a win. However, there is another 
follower labeled $P$, and going to it is only a nonlosing move. The digraph 
may be embedded within a large digraph, or the player may have only local 
information about the label of a vertex and the labels of its immediate 
followers. In both of these cases it may be nonobvious which $P$-follower 
of an $N$-position leads to a win. 

These two difficulties are connected, and both can be remedied 
by a single medicine, namely by introducing an associated counter function
$c\colon V\cap \Cal P\rightarrow\IZ^0$ as done in the following algorithm for 
computing the $P,N,D$-labels. (For {\sl classical} games, which are finite
and acyclic, these two difficulties do not exist. This is clear for the 
second (going to {\sl any} $P$-follower from an $N$-position leads to a
win), and can be proved for the first.) We state the algorithm for the 
case of normal play, which is all that's needed in the sequel.
In a way, the counter function fills the function of the subscripts 
of $P$ in Definition~1.\medskip
%\midinsert\vskip 1.0truecm
%\centerline{\epsfysize 4.0cm \epsffile{cgt_3.eps}}
%\botcaption{Figure 3. {\rm Lemma~1 and Theorem~1 don't tell the full story.}}
%\endcaption\endinsert
{\it Algorithm\/} PND {\it for computing the\/ $P$-, $N$- and\/
$D$-positions of a finite cyclic digraph\/}.\par
1. (Initialize counter.) Put $m\leftarrow 0$.\par
2. ($P$-label and counter.) As long as there is an unlabeled vertex $u$
all of whose followers are labeled $N^{\prime}$, label $u$ by $
P^{\prime}$ and put $c(u)\leftarrow m$, $m\leftarrow m+1$.\par
3. ($N$-label.) Label by $N^{\prime}$ every unlabeled vertex which has a
follower labeled $P^{\prime}$ and return to 2.\par
4. ($D$-label.) Label all unlabeled vertices by $D^{\prime}$. End.
\medskip

The complexity of this algorithm, which requires examining each edge once,
is $O(|E|)$. We have:

\proclaim{\bf Theorem 2} For every finite cyclic digraph, the labels\/
$P^{\prime}$, $N^{\prime}$ and\/ $D^{\prime}$ assigned by Algorithm\/
\rom{PND} are\/ $P$-, $N$- and\/ $D$-labels respectively, and the first
property of Lemma~\rom{1} can be strengthened to\/\rom{:}
$$\eqalign{&u\in P\ \hbox{\it if and only if\/}\colon\ F(u)
\subseteq\Cal N,\ \hbox{\it and for every}\ v\in F(u)\cr
&\quad\hbox{\it there is}\ w\in F(v)\cap\Cal P\ \hbox{\it with}\
c(w)<c(u).\cr}\tag 1$$\endproclaim

\demo{\bf Proof} Labels $P,N,D$ exist uniquely by Theorem~1. A vertex $u$ is
labeled $P^{\prime}$ in step~2 if and only if $F(u)\subseteq\Cal N^{\prime}$\/
if and only if each $v\in F(u)$ has a follower which had been labeled 
$P^{\prime}$ at an earlier stage if and only if $P^{\prime}$ has property~(1).
Also $u$ is labeled $N'$ in step~3 if and only if $F(u)\cap P'\ne\emptyset$. 

Let $u\in\Cal D^{\prime}$. Then $F(u)\cap\Cal P^{\prime}=\emptyset$,
since otherwise $u$ would have been labeled $N^{\prime}$ in step~3. Also
$F(u)\not\subseteq\Cal N^{\prime}$, otherwise $u$ would have been labeled
$P^{\prime}$ in step~2. Thus there is $v\in F(u)\cap\Cal D^{\prime}$,
leading to an infinite sequence of $D^{\prime}$-followers. So $u$
satisfies the condition of a $D$-position by Lemma~1. Therefore
$\Cal P^{\prime}\subseteq\Cal P$, $\Cal N^{\prime}\subseteq\Cal N$ and
$\Cal D^{\prime}\subseteq\Cal D$. Since step~4 of the algorithm
guarantees that every vertex gets precisely one label, it follows that
$V=\Cal P^{\prime}\cup\Cal N^{\prime}\cup\Cal D^{\prime}$; and $V=\Cal P
\cup\Cal N\cup\Cal D$ follows from Theorem~1. Hence $\Cal P^{\prime}=\Cal
P$, $\Cal N^{\prime}=\Cal N$ and $\Cal D^{\prime}=\Cal D$.\bqed\enddemo

We now collect together those properties of the $P$-, $N$- and $D$-labels
whose acquaintance we have already made, and reintroduce infinite digraphs.

\proclaim{\bf Corollary 2} Let\/ $G=(V,E)$ be a any cyclic game-graph, 
not necessarily finite, which has a 
counter function\/ $c:V\cap\Cal P\rightarrow\Cal O$ satisfying \rom{(1)}, 
without ties. Then there is a unique partition\/\rom{:} 
$V=\Cal P\cup\Cal N\cup\Cal D$ 
%and a counter function\/ $c\colon V\cap\Cal P\rightarrow\IZ^0$ 
such that\/\rom{:}\par
\roster
\item"{(i)}" $u\in\Cal P$ if and only if\/
%\rom{:} 
$F(u)\subseteq\Cal N$,
%and for every\/ $v\in F(u)$ there is\/ $w\in F(v)\cap\Cal P$ 
%with\/ $c(w)<c(u)$
\par
\item"{(ii)}" $u\in\Cal N$ if and only if\/ $F(u)\cap\Cal P\ne\emptyset$,
\par
\item"{(iii)}" $u\in\Cal D$ if and only if\/ $F(u)\cap\Cal P=\emptyset$ 
and\/ $F(u)\cap\Cal D\ne\emptyset$.
\endroster
\endproclaim

\demo{\bf Proof} A unique partition $V=\Cal P\cup\Cal N\cup\Cal D$ exists by
Theorem~1, independently of Algorithm~PND, which applies only to finite 
$G$; property (i) is included in (1), and 
%and a counter function with property (i) exists by Theorem~2.
properties (ii) and (iii) are the last two assertions of Lemma~1.\bqed
\enddemo

Infinite digraphs with a counter function $c$ satisfying (1) do exist.
Thus in Example~3, $c(2i)=i$ for all $i\geq 0$ satisfies (1). Also 
for Example~4 an appropriate counter function satisfying (1) can be 
defined. 

\proclaim{\bf Corollary 3} Let\/ $G$ be as in Corollary~2. 
%a finite cyclic game-graph. 
A player
moving from an\/ $N$-position can consummate a win by always moving to
a\/ $P$-follower of minimum counter function value\/.
\endproclaim\par
\demo{\bf Proof} Follows from property (1): the winner can arrange
that any two consecutive $P$-positions $u$, $w$ will satisfy $c(w)<c(u)$.
Since every set of ordinals is well-ordered and so in particular 
totally-ordered (see e.g., Halmos \cite{Hal1960} \S20), the winner 
will reach a leaf in a finite number of moves.  
\bqed\enddemo\medskip
We have thus remedied shortcoming (b) mentioned above. For example, in 
Fig.~2(b), the leaf will get a lower counter function value than the other
vertex labeled $P$, if the labeling is done by Algorithm~PND. Moreover, also 
shortcoming (a) has disappeared as will be shown now. Obviously the counter 
function $c$ is not unique, but properties (i), (ii), (iii) of the 
$P$-, $N$- and $D$-labels of Corollary~2 provide a characterization for 
these labels. Note that the $P$- and $N$-labels in Fig.~2(a) are 
inconsistent with property~(1).

\proclaim{\bf Theorem 3} Let\/ $G=(V,E)$ be a cyclic digraph, not 
necessarily finite, which has a 
counter function\/ $c:V\cap\Cal P\rightarrow \Cal O$ satisfying \rom{(1)}. 
Suppose
there is a partition\/ $V=\Cal P^{\prime}\cup\Cal N^{\prime}\cup\Cal D^{
\prime}$ where\/ $\Cal P^{\prime}$, $\Cal N^{\prime}$, $\Cal D^{\prime}$
satisfy the three conditions of Corollary\/~\rom{2}. Then\/ $\Cal P^{
\prime}=\Cal P$, $\Cal N^{\prime}=\Cal N$, $\Cal D^{\prime}=\Cal D$.
\endproclaim

\demo{\bf Proof} By Theorem~1 there is a unique partition $V=\Cal P\cup\Cal N
\cup\Cal D$. Let
$$T=\{u\in V\colon\ u\in\Cal P^{\prime},\ u\notin\Cal P\}.$$
Pick $u\in T$ with $c^{\prime}(u)$ minimum, where $c^{\prime}$ is a
counter function: $V\cap\Cal P^{\prime}\rightarrow \Cal O$. By Theorem~1,
$u\in\Cal N\cup\Cal D$.

Assume first $u\in\Cal N$. Then property (ii) of Corollary~2 implies
that there is $v\in F(u)\cap\Cal P$. By property (i), $v\in\Cal N^{
\prime}$, and there is $w\in F(v)\cap\Cal P^{\prime}$ with $c^{\prime}(w)
<c^{\prime}(u)$ (see Fig.~4). Furthermore, $w\in N$ by property (i). Thus
also $w\in T$, contradicting the minimality of $c^{\prime}(u)$.
\midinsert\vskip 1.0truecm
\centerline{\epsfxsize 6.8cm \epsffile{cgt_4.eps}}
$$\vcenter{\halign{\hfill $#$\hfill\hskip 2truecm&\hfill $#$\hfill\hskip
2truecm&\hfill $#$\hfill\cr
u&v&w\cr
%\bigcirc&\bigcirc&\bigcirc\cr
\noalign{\vskip 5pt}
\Cal P^{\prime}\cap\Cal N&\Cal N^{\prime}\cap\Cal P&\Cal P^{\prime}\cap
\Cal N\cr}}$$
\botcaption{Figure 4. {\rm An impossible situation.}}\endcaption\endinsert

Secondly, assume that $u\in\Cal D$. By property (iii), there is $v\in F(u
)\cap\Cal D$. By property (i), $v\in\Cal N^{\prime}$, and there is $w\in
F(v)\cap\Cal P^{\prime}$ with $c^{\prime}(w)<c^{\prime}(u)$. Since $v\in
\Cal D$, property (iii) implies $w\notin\Cal P$. Thus also $w\in T$,
which is the same contradiction as in the previous case. Therefore
$T=\emptyset$.\par
If $u\in\Cal N\cap\Cal D^{\prime}$, then $u$ has a $P=P^{
\prime}$-follower, contradicting property (iii) for $\Cal D^{\prime}$.
Similarly for $u\in\Cal N^{\prime}\cap\Cal D$. Thus also $\Cal N^{\prime}
=\Cal N$ and $\Cal D^{\prime}=\Cal D$.\bqed
\enddemo\medskip

Since Lemma~1 is so fundamental for game theory, we exhibit below, very 
briefly, another approach for establishing it, that of fixpoint logic, 
also known as $\mu$-Calculus. See e.g., Kozen \cite{Koz1983}. Let $f$ be a  
logical relation. We are looking for a solution in a predicate 
or set $S$ of $S=f(S)$. If it exists, it is called a {\it fixed point} 
of $f$. We write $\mu S.f(S)$ for the minimal solution of $S=f(S)$, and
$\nu S.f(S)$ for its maximal solution; minimal and maximal in the sense 
of set inclusion. 
 
\definition{\bf Definition 2} Given a game $\Gamma$ without ties 
which may contain cycles or loops, or may be infinite, 
with arbitrary termination set $\tau$. Player~I begins to play 
from position $u_0$ in $\Gamma$. Then $u_0$ is a $P$-position if
$$\mu P(u_0).\forall u_1\in F(u_0)\exists u_2\in F(u_1)P(u_2).\tag 2$$ 
The position $u_0$ is an $N$-position if   
$$\mu N(u_0).\exists u_1\in F(u_0)\forall u_2\in F(u_1)N(u_2).\tag 3$$ 
The position $u_0$ is a $D$-position if 
$$\nu D(u_0).\exists u_1\in F(u_0)D(u_1) \land \forall u_1\in F(u_0)
(D(u_1) \lor N(u_1)).\tag 4$$\enddefinition

The relations (2)--(4) are clearly {\it monotonic}, i.e., viewing them,
say (2), as a function $f$ of the predicate 
$P: f(P)=\forall u_1\in F(u_0)\exists u_2\in F(u_1)P(u_2)$, we have,
$\forall P_1\forall P_2\forall u\in V:P_1(u)\rightarrow P_2(u)\Rightarrow
f(P_1)\rightarrow f(P_2)$. Hence by the Tarski-Knaster fixpoint 
Theorem \cite{Tar1955}, there is a solution to (2)--(4). 

Analogously to Lemma~1 we prove, 

\proclaim{\bf Lemma 2} Let\/ $G=(V,E)$ be a cyclic, possibly infinite,
game-graph without ties. Then for every\/ $u=u_0\in V$ we have,\par
relation \rom{(2)} holds if and only if 
$$\mu P(u_0).\forall u_1\in F(u_0)N(u_1),\tag 5$$\par
relation \rom{(3)} holds if and only if
$$\mu N(u_0).\exists u_1\in F(u_0)P(u_1).\tag 6$$ 
\endproclaim 
\demo{\bf Proof} Let $u_0\in\tau$. Then $u_0\in \Cal P$ by (2), which is
satisfied vacuously in this case, and by the fact that the first part of 
(4) doesn't hold. Moreover, (5) is clearly satisfied vacuously for $u_0$. 
Now let $u_0$ be any predecessor of some $u_1\in\tau$. By (3), 
$u_0\in\Cal N$, since $\forall u_2\in F(u_1)N(u_2)$ holds vacuously 
if $u_1\in\tau$, and since the second part of (4) doesn't hold. 
Thus (6) holds for $u_0$. 

Suppose, inductively, that the lemma holds for all $u\in\Cal N\cup\Cal P$
which lie on any directed path from some $u_0=u$. 

(i) Let $u_0\in\Cal P$. By (2) and the induction hypothesis (5) applied 
to $P(u_2)$, 
$$\mu P(u_0).\forall u_1\in F(u_0)
[\exists u_2\in F(u_1)\forall u_3\in F(u_2)N(u_3)].$$
The part in brackets is (3) for $u_1$, establishing (5). 

(ii) Let $u_0\in\Cal N$. By (3) and the induction hypothesis (6) applied 
to $N(u_2)$, 
$$\mu N(u_0).\exists u_1\in F(u_0)
[\forall u_2\in F(u_1)\exists u_3\in F(u_2)P(u_3)].$$
The part in brackets is (2) for $u_1$, establishing (6).

Conversely, suppose that (5) and (6) hold. Substituting (6) into (5)
gives (2); and (5) into (6) gives (3).\bqed\enddemo

Finally, we show that the $P$-, $N$-, $D$-labels of Definitions~1 and 2 are 
the same. Denote those of Definition~1 by $P', N', D'$, and their sets 
by $\Cal P', \Cal N', \Cal D'$. 

\proclaim{\bf Theorem 4} Let\/ $G=(V,E)$ be a cyclic digraph, not 
necessarily finite, which has a 
counter function\/ $c:V\cap\Cal P\rightarrow \Cal O$ satisfying \rom{(1)}.
Then\/ $\Cal P=\Cal P'$, $\Cal N=\Cal N'$, $\Cal D=\Cal D'$.\endproclaim 

\demo{\bf Proof} Using the method of Theorem~3 one can show easily that 
$\Cal P'\subseteq \Cal P$ and $\Cal N'\subseteq \Cal N$. If any of 
these inclusions would be strict, then we would have $\Cal D'\supset\Cal D$ 
strictly, contradicting the maximality of the set $\Cal D$ as expressed 
in (4).\bqed\enddemo 

The theory of (impartial) {\sl cyclic} games is due to Smith \cite{Smi1966}; 
see also \cite{Con1976} ch.~11, pp.~133-135, \cite{BCG1982} ch.~12. 
An algorithm similar to Algorithm PND appears in the proof
of Theorem~2 in \cite{Cnd1992}, but no counter function is mentioned there.
Algorithm~PND is a specialization of Algorithm~G in \cite{FrY1986} p.~168, 
for computing the generalized Sprague-Grundy function $\gamma$ of a digraph, 
which has complexity $O(|V||E|)$. The higher complexity is due to the fact 
that in the latter algorithm we seek out and label grandparents of previously 
labeled grandchildren, rather than parents of previously labeled children, 
as in the former algorithm. In fact, $\gamma$ is a generalization of 
the $P$-, $N$-, $D$-labeling. One can trade a counter function, which 
appears in Definitions~1 and 2 there, by the requirement of the 
maximality of the set of infinities of $\gamma$ in Definition~3 
there. This is analogous to the present case where a counter function $c$, 
as used in Algorithm~PND, can be traded for a maximality operator $\nu$ 
in Definition~2, though  $\nu$ seems to cure only shortcoming (a) above, 
not (b). For related treatments of games using fixpoint logic see e.g., 
Banaschewski and Pultr \cite{BaP1991} and Stirling \cite{Sti$\geq$1996}. No 
draw positions were considered by them.  


%\head 3. The Structure of Digraph Kernels\endhead
\centerline{{\bf 3. The Structure of Digraph Kernels}}
\vskip0.2cm
We are now ready to state our results on digraphs precisely, and to prove 
them by using the game-theoretic results obtained in the previous section.

\proclaim{\bf Theorem 5} Let\/ $G=(V,E)$ be any cyclic digraph, not necessarily
finite, which has a counter function\/ 
$c:V\cap \Cal P\rightarrow \Cal O$ satisfying property~\rom{(1)}.
Then\/ $\Cal P$ is a subset of every kernel and\/ $\Cal N$ is 
a subset of the complement of every kernel; the kernels \rom{(}and their 
complements\rom{)} are possibly nonunique only on\/ $\Cal D$.
\endproclaim\medskip
\demo{\bf Proof} By Theorem~1, the vertex set $V$ of $G$ can be partitioned 
{\sl uniquely} into $\Cal P$, $\Cal N$ and $\Cal D$. Denote by $\Cal K$ the
set of all kernels of $G$. Then the first part of the claim is equivalent
to: $\Cal P\subseteq K\ \forall K\in\Cal K$ and 
$\Cal N\subseteq V-K\ \forall K\in\Cal K$. We see that this is satisfied 
vacuously if $G$ has no kernel ($\Cal K=\emptyset$). If $\Cal P=\emptyset$,
then $\Cal N=\emptyset$, and then the first part holds trivially. The last
part of the claim clearly holds for these two special cases. If the claim 
is false, we may thus suppose that there exists 
$u\in\Cal P$, $u$ not in some kernel $K$. Let $T=\{u\in\Cal P: u\not\in K\}$. 
If $T$ is nonempty, there exists $u\in T$ with $c(u)$ minimum; it exists by 
the well-ordering principle. Since $u\not\in K$, 
there exists $v\in F(u)\cap K$. By Lemma~1, $v\in\Cal N$ and there 
exists $w\in F(v)\cap\Cal P$ with $c(w)<c(u)$. We have $w\not\in K$, and so 
$w\in T$, contradicting the minimality of $c$. Thus $\Cal P$ is in
every kernel. It follows that $\Cal N$ is in the complement of every kernel.
Hence the only subset on which the kernel is possibly nonunique, is $\Cal D$.
\bqed\enddemo\medskip
Note the simplicity of the proof, once we set up the appropriate tools.
Theorem~5 says that $\Cal P$ is a set of {\it fixed points} for all the 
kernels and $\Cal N$ is a set of fixed points for the complement of every 
kernel. But it doesn't yet tell the full story. We now show that every 
kernel of $G$ can be written as a union of 2 kernels, one of them 
fixed. 

\proclaim{\bf Theorem 6} \rom{(}{\sc Decomposition Theorem.}\rom{)} Let\/ 
$G=(V,E)$ be any cyclic digraph, not necessarily finite, which has a 
counter function\/ $c:V\cap\Cal P\rightarrow \Cal O$ satisfying \rom{(1)}.
Let\/ $G_1=(V_1,E_1)$ be the 
subgraph induced by the vertex subset\/ $\Cal P\cup\Cal N$, and\/ 
$G_2=(V_2,E_2)=G-G_1$ the subgraph induced by the vertex subset\/ $\Cal D$.
Then\/ $G_1$ has a unique kernel\/ $K(G_1)=V_1\cap\Cal P$; it is the empty 
set if and only if\/ $\Cal P=\emptyset$. Let\/ $\Cal K,\Cal K_2$
denote the set of kernels of\/ $G,G_2$ respectively. Then\/ 
$\Cal K=K(G_1)\cup\Cal K_2=\{K(G_1)\cup K(G_2):K(G_2)\in\Cal K_2\}$. In
particular,\/ $\Cal K=\emptyset$ if and only if\/ $\Cal K_2=\emptyset$.
\endproclaim\medskip

\demo{\bf Proof} The partition $V=\Cal P\cup\Cal N\cup\Cal D$ exists and is 
unique by
Theorem~1. The set $S:=V_1\cap\Cal P$ is clearly a kernel of $G_1$. Thus by
Theorem~5, $S$ is in every kernel of $G_1$. Since all the remaining vertices 
of $G_1$ are in in $V_1\cap\Cal N$ and $S$ is dominating, $S$ is the unique
kernel of $G_1$. The digraph $G_1$ and its kernel $K(G_1)$ are empty if and 
only if $\Cal P=\emptyset$.

Let $u$ be any vertex of $V_2$. If it has a follower $v\in V_1$, then 
$v\in\Cal N$ by Lemma~1. If $u\in V_2$ has a predecessor $w\in V_1$, then
again $w\in\Cal N$, since $w\in\Cal P$ implies $F(w)\subseteq\Cal N$ by 
Lemma~1, but $u\in F(w)\cap\Cal D$. Thus the ``boundary'' of $G_1$ has no
influence on the structure of any kernel of $G_2$. Conversely, if $(u,v)\in E$,
$u\in V_1$, $v\in V_2$ and $v$ is in a kernel of $G_2$, the edge $(u,v)$
cannot affect the kernel $K(G_1)$, since it is unique. We conclude that 
the kernel $K(G_1)$ is {\sl isolated}
from any kernel $K(G_2)$: they cannot influence each other adversely when 
embedded together in $G$, as would be the case in the presence of an edge
of $G$ joining a vertex of $G_2$ and a vertex of $G_1$ labeled $P$. 
Therefore any kernel $K(G_2)\in\Cal K_2$ can be 
adjoined to $K(G_1)$ to form a kernel $K=K(G_1)\cup K(G_2)$ of $G$; and 
conversely, every kernel $K$ of $G$ can be decomposed into the kernel 
$K(G_1)$ and a kernel $K(G_2)\in\Cal K_2$.\bqed\enddemo\medskip

Note that normally a union of $2$ kernels of $2$ induced subgraphs of a 
connected digraph is not a kernel of the entire digraph, because edges 
connecting the $2$ induced subgraphs influence these kernels adversely. 
Informally, if we consider a digraph with a multiplicity of kernels to
be ``malignant'', then Theorem~6 indicates a healing process: the cancer is 
completely contained in $\Cal D$; removing it preserves the healthy part
$\Cal P\cup\Cal N$, though the healthy part may be empty, as is the case 
for the digraph of Fig.~1. But for other digraphs, the malignant part may 
be empty! On the other hand, if we {\sl do} have to compute or estimate 
the number of kernels, then Theorem~6 shows that it suffices to count or 
estimate this number on the subgraph $G_2$, which is computationally more 
efficient, in general, than doing it on $G$ itself.

If $G$ is finite, then $\Cal P, \Cal N, \Cal D$ can be computed in polynomial
time by Algorithm~PND. We combine Theorems~5 and 6 for this case.

\proclaim{\bf Corollary 4} Let\/ $G=(V,E)$ be a connected finite cyclic 
digraph. Let\/ $G_1=(V_1,E_1)$ be the 
subgraph induced by the vertex subset\/ $\Cal P\cup\Cal N$, and\/ 
$G_2=(V_2,E_2)=G-G_1$ the subgraph induced by the vertex subset\/ $\Cal D$.
Then\/ $G_1$ has a unique kernel\/ $K(G_1)=V_1\cap\Cal P$; it is the empty 
set if and only if\/ $\Cal P=\emptyset$. Let\/ $\Cal K,\Cal K_2$
denote the set of kernels of\/ $G,G_2$ respectively. Then\/ 
$\Cal K=K(G_1)\cup\Cal K_2=\{K(G_1)\cup K(G_2):K(G_2)\in\Cal K_2\}$. In
particular,\/ $\Cal K=\emptyset$ if and only if\/ $\Cal K_2=\emptyset$.
Moreover, the decomposition of\/ $G$ into\/ $G_1$ and\/ $G_2$ and the kernel\/
$K(G_1)$ can be computed in \/ $O(|E|)$ steps.
\endproclaim

\demo{\bf Proof} Since for a connected digraph, $\Cal P, \Cal N, \Cal D$ can
be computed in $O(|E|)$ steps, the result follows from Theorem~2.
\bqed\enddemo\medskip
Corollary~4 implies, informally, that the source of the NP-completeness
of the existence of a digraph-kernel and the $\#$P-completeness
result of their number, are both contained in $\Cal D$.

There may be a unique kernel even when there are $D$-positions. A simple 
example is depicted in Fig.~5; the $2$ vertices of degree $2$ constitute
a unique kernel.
\midinsert\vskip 1.0truecm
\centerline{\epsfysize 4.0cm \epsffile{cgt_5.eps}}
\botcaption{Figure 5. {\rm Unique kernel for the case $\Cal D=V$.}}
\endcaption\endinsert
As an example of Corollary~4, we may ask about the existence of kernels in
the digraph depicted in Fig.~6. To answer that, we first apply Algorithm~PND,
which then enables us to decompose $G$ into the induced digraphs $G_1$, $G_2$ 
(Fig.~7). It is easily seen that $G_2$ has no kernel, so $G$ has none. (It 
suffices to reverse the direction of a single edge of $G_2$ (which?), and 
correspondingly of $G$, to get a unique kernel.) 
\midinsert\vskip 1.0truecm
\centerline{\epsfysize 7.0cm \epsffile{cgt_6.eps}}
\botcaption{Figure 6. {\rm How many kernels does this digraph have?}}
\endcaption\endinsert
\midinsert\vskip 1.0truecm
\centerline{\epsfysize 7.0cm \epsffile{cgt_7.eps}}
\botcaption{Figure 7. {\rm Answer: it suffices to analyse $G_2$.}}
\endcaption\endinsert
We don't know a priori whether $K$ is unique on $D$ or not, and we
can't find out for a general digraph in polynomial 
time, unless $\NP=P$. But we can give a game-theoretic interpretation to 
digraphs whose kernels intersect the ``uncertainty region'' $\Cal D$: a 
token-pushing game on them, in normal play, has $D$-positions, all of them 
lying in $\Cal D$. In fact, 
in the example of Fig.~5, the kernel is not a set of $P$-positions.
Define a {\it strategy kernel} to be a kernel in a digraph $G$ all of 
whose elements are $P$-positions in normal play of a game with game-graph $G$.

\proclaim{\bf Theorem 7} Let\/ $G=(V,E)$ be a finite cyclic digraph. Then\/
$G$ has a strategy kernel\/ $K=\{u\in V: u\in\Cal P \}$ if and only if\/ 
$\Cal D=\emptyset$.\endproclaim

\demo{\bf Proof} If $G$ has a strategy kernel $K$, then $\Cal D=\emptyset$, 
since any element of  $\Cal D$ is neither in $K$ nor in its complement. If 
$\Cal D=\emptyset$, then $V$ is partitioned uniquely into $\Cal P$ and 
$\Cal N$, so the result follows from Theorem~5. 
\bqed\enddemo\medskip
\proclaim{\bf Corollary 5} If a finite cyclic digraph $G$ has a strategy 
kernel, it is a unique kernel of $G$.\endproclaim
\demo{\bf Proof} A digraph cannot have $2$ distinct strategy
kernels by Theorem~1.\bqed\enddemo\medskip

Can one produce a decomposition similar to that of Theorem~6 also when 
$\Cal P=\emptyset$, i.e., all vetices are in $\Cal D$? We mention briefly 
that for a special 
family of digraphs the answer is positive. A slight generalization of the 
problem of {\it stable marriages}, see Gale and Shapley \cite{GaS1962},  
can be cast as a digraph $G$ on a grid with horizontal and vertical edges 
only, and every row and every column is acyclic. This generalization 
is used e.g., in Galvin's proof \cite{Gal1995} of the Dinitz 
conjecture, mentioned in a paper by Erd\"os, Rubin and Taylor \cite{ERT1980}.
Stable marriages correspond to kernels in $G$, which has no leaf unless 
there is a pair $(m,w)$ such that the woman $w$ is the first choice of 
the man $m$ and $m$ is the first choice of $w$. The algorithm in which 
the men propose first results in marriages in which the men get their  
best choices, and the women their worst. Conversely if the women 
propose first. Knowing these two extreme cases, one can partition the 
vertex set into the subsets belonging to no kernel, every kernel, 
and the rest.\medskip   

{\bf Conclusion}. We have constructed game-theoretic tools, of independent
interest, and applied them to study the structure of digraph kernels. There
exist more sophisticated tools, to provide polynomial strategies for the more
complicated class of {\it annihilation games}: a finite number of tokens is 
placed initially on a subset of the vertices, at most $1$ token per vertex. A
move consists of selecting a token and sliding it to a follower. If that
follower was occupied, then both tokens are phased out of the game 
(annihilation). These tools enable to shed more light on digraph kernels 
and their relationship to certain homomorphism kernels. This in turn can 
be applied to obtain further results in the theory of linear 
error-correcting codes. Some of this is planned to appear in 
\cite{Fra$\geq$1997}.\medskip

{\bf Acknowledgment.} Herb Wilf pointed out the desirability of a formal 
definition of the $P$-, $N$- and $D$-positions. Ron Holzman and Donald A.\
Martin made useful comments on a previous version of Definition~1. 
The present Definition~1 is a slight variation of a suggestion made 
to me by Azriel Levy. Amir Pnueli introduced me to 
fixpoint logic, which led to Definition~2 and Lemma~2. Gil 
Kalai told me about partitioning the stable marriage digraph into subsets 
of kernels and Uri Zwick pointed out the relationship with reference 
\cite{Cnd1992}. Many thanks to all of them!
\vskip 25pt\par
%\Refs
%\refstyle{A}
%\widestnumber\key{ONAG}
%\head References\endhead
\centerline{{\bf References}}
\vskip0.2cm
1. \cite{BaP1991} B.\ Banaschewski and A.\ Pultr \(1991\), Tarski's 
fixpoint lemma and combinatorial games, {\it Order} {\bf 7}, 375--386.\par
2. \cite{Ber1992} C. Berge \(1992\), {\it Graphs\/} (Chapter 4), 
Second Edition, Elsevier (French: Gauthier Villars 1988).\par
3. \cite{BCG1982} E. R. Berlekamp, J. H. Conway and R. K. Guy \(1982\), 
{\it Winning Ways\/} (two volumes), Academic Press, London.\par
4. \cite{BrP1993} R. A. Brualdi and V. S. Pless \(1993\), Greedy codes, 
{\it J.\ Combin.\ Theory\/} (Ser.~A) {\bf 64}, 10--30.\par
5. \cite{Chv1973} V. Chv\'atal \(1973\), On the computational complexity 
of finding a kernel, Report No.~CRM-300, Centre de Recherches Math\'ematiques,
Universit\'e de Montr\'eal.\par
6. \cite{Cnd1992} A. Condon \(1992\), The complexity of Stochastic games, 
{\it Information and Computation\/} {\bf 96}, 203--224.\par
7. \cite{Con1976} J. H. Conway \(1976\), {\it On Numbers and Games\/}, 
Academic Press, London.\par
8. \cite{Con1990} J. H. Conway \(1990\), Integral lexicographic codes, 
{\it Discrete Math.}, {\bf 83}, 219--235.\par
9. \cite{CoS1986} J. H. Conway and N. J. A. Sloane \(1986\), Lexicographic 
codes: error-cor\-rec\-ting codes from game theory, {\it IEEE Trans.\ Inform.\
Theory\/} {\bf IT-32}, 337--348.\par
10. \cite{ERT1980} P.\ Erd\"os, A.\ L.\ Rubin and H.\ Taylor \(1980\), 
Choosability in graphs, {\it Congr.\ Numer.\/} {\bf 26}, 122--157.\par
11. \cite{Fra1981} A. S. Fraenkel \(1981\), Planar kernel and Grundy with 
$d\leq 3$, $d_{out}\leq 2$, $d_{in}\leq 2$ are NP-complete, {\it Discrete 
Appl.\ Math.} {\bf 3}, 257--262.\par
12. \cite{Fra1996} A. S. Fraenkel \(1996\), Error-correcting codes derived 
from combinatorial games, 
in: {\it Games of No Chance}, Proc.\ MSRI Workshop on Combinatorial 
Games, July, 1994, Berkeley, CA (R. J. Nowakowski, ed.), MSRI Publ. Vol.~29, 
Cambridge University Press, Cambridge, pp.~417--431.\par
13. \cite{Fra$\geq$1997} A. S. Fraenkel \($\geq 1997$\) {\it Adventures in 
Games and Computational Complexity\/}, Graduate Studies in Math., Amer.\
Math.\ Soc., to appear.\par
14. \cite{FrY1986} A. S. Fraenkel and Y. Yesha \(1986\), The generalized 
Sprague-Grundy function and its invariance under certain mappings, 
{\it J.\ Combin.\ Theory\/} (Ser.~A) {\bf 43}, 165--177.\par
15. \cite{GaS1962} D.\ Gale and L.\ S.\ Shapley \(1962\), College 
admissions and the stability of marriages, {\it Amer.\ Math.\ Monthly\/} 
{\bf 69}, 9--15.\par 
16. \cite{GaS1953} D.\ Gale and F.\ M.\ Stewart \(1953\), Infinite games 
with perfect information, Contributions to the Theory of Games, 
{\it Ann.\ of Math.\ Stud.\/} {\bf 2}(28), 245--266, Princeton.\par
17. \cite{Gal1995} F.\ Galvin \(1995\), The list chromatic index of a 
bipartite multigraph, {\it J.\ Combin.\ Theory\/} (Ser.~B) {\bf 63}, 
153--158.\par 
18. \cite{Hal1960} P.\ R.\ Halmos \(1960\), {\it Naive Set Theory}, 
Van Nostrand, Princeton, NJ.\par 
19. \cite{Jon1982} J. P. Jones \(1982\), Some undecidable determined games, 
{\it Internat.\ J.\ Game Theory\/} {\bf 11}, 63--70.\par
20. \cite{JFr1995} J. P. Jones and A. S. Fraenkel \(1995\), Complexities 
of winning
strategies in diophantine games, {\it J. Complexity\/} {\bf 11}, 435-455.\par
21. \cite{Kac1974} M. Kac \(1974\), Hugo Steinhaus, a reminiscence and a 
tribute, {\it Amer.\ Math.\ Monthly\/} {\bf 81}, 572--581 (p.~577).\par
22. \cite{Koz1983} D.\ Kozen \(1983\), Results on the propositional 
$\mu$-calculus, {\it Theoret.\ Comput.\ Sci.\/} {\bf 27}, 333--354.\par
23. \cite{Rab1957} M. O. Rabin \(1957\), Effective computability of winning 
strategies, Contributions to the Theory of Games vol.~3, {\it Ann.\ of 
Math.\ Stud.} {\bf 39}, 147--157, Princeton.\par
24. \cite{Ric1953} M. Richardson \(1953\), Solutions of irreflexive 
relations, {\it Ann.\ of Math.} {\bf 58}, 573--590.\par
25. \cite{Smi1966} C. A. B. Smith \(1966\), Graphs and composite games, 
{\it J.\ Combin.\ Theory\/} {\bf 1}, 51--81. Reprinted in slightly modified 
form in: {\it A Seminar on Graph Theory\/} (F.\ Harary, ed.), Holt, Rinehart 
and Winston, New York, NY, 1967.\par
26. \cite{Sti$\geq$1996} C.\ Stirling \(1996\), Model checking and other games,
presented at Computer Science Logic, September, 1996.\par
27. \cite{SzC1994} J. L. Szwarcfiter and G. Chaty \(1994\), Enumerating the 
kernels of a directed graph with no odd circuits, {\it Inform.\ Process.\ 
Lett.} {\bf 51}, 149--153.\par
28. \cite{Tar1955} A.\ Tarski \(1955\), A lattice theoretical fixpoint 
theorem and its applications, {\it Pacific J.\ Math.\/} {\bf 5}, 285--309.\par 
29. \cite{VLe1976} J. van Leeuwen \(1976\), Having a Grundy-numbering is 
NP-complete, Report No.~207, Computer Science Dept., Pennsylvania State 
University, University Park, PA.\par
30. \cite{VNe1928} J. von Neumann \(1928\), Zur Theorie der 
Gesellschaftsspiele, {\it Math.\ Ann.} {\bf 100}, 295--320.\par
31. \cite{VNM1953} J. von Neumann and O. Morgenstern \(1953\), {\it Theory 
of Games and Economic Behaviour\/}, 3rd ed., Princeton University Press, 
Princeton, NJ.\par
32. \cite {Zer1912} E. Zermelo \(1912\), \"Uber eine Anwendung der 
Mengenlehre auf die Theorie des Schachspiels, Proc.\ 5th Int.\ Cong.\ Math., 
Cambridge, Cambridge University Press, 1913, Vol.~II, pp. 501--504.

\enddocument