\documentclass[12pt,a4paper]{article}
\usepackage{cdmtcs}

\addtolength{\topmargin}{-.75in}
\addtolength{\oddsidemargin}{-.5in}
\setlength{\textwidth}{6.25in}
\setlength{\textheight}{9in}

\begin{document}

\cdmtcstitle{On Game-Theoretic Models of Networks}
\cdmtcsauthor{Hans L. Bodlaender}
\cdmtcsaffiliation{Institute of Information and Computing Sciences,
Utrecht University,\\ Utrecht, the Netherlands}
\cdmtcsauthor{Michael J. Dinneen\\ Bakhadyr Khoussainov}
\cdmtcsaffiliation{Department of Computer Science,
\\ University of Auckland,\\ Auckland, New Zealand}
\cdmtcstrnumber{151}
\cdmtcsdate{April 2001}
\colourcoverpage
%\coverpage

\title{\textbf{On Game-Theoretic Models of Networks}}

\author{\textsc{Hans L. Bodlaender}\\
	Institute of Information and Computing Sciences\\
	Utrecht University, P.O. Box 80.089, 3508 TB\\ 
        Utrecht, the Netherlands\\ \texttt{hansb@cs.uu.nl} 
\and    \textsc{Michael J. Dinneen} and \textsc{Bakhadyr Khoussainov}\\
	Department of Computer Science\\
	The University of Auckland, Private Bag 92019\\ 
        Auckland, New Zealand\\ \texttt{\{mjd,bmk\}@cs.auckland.ac.nz} 
}

\date{}
\maketitle

\begin{abstract} 
In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

\smallskip

{\bf Keywords:} graph and network algorithms, complexity,
infinite graph games, McNaughton games.
\end{abstract}

In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

In this paper, we study the complexity of deciding which player has
a winning strategy in certain types of McNaughton games. These graph
games can be used as models for computational problems and processes
of infinite duration.  We consider the cases (1) where the first
player wins when vertices in a specified set are visited infinitely
often and vertices in another specified set are visited finitely
often, (2) where the first player wins when exactly those vertices
in one of a number of specified disjoint sets are visited infinitely
often, and (3) a generalization of these first two cases.  We give
polynomial time algorithms to determine which player has a winning
strategy in each of the games considered.

\end{document}
