%% bare_conf.tex
%% V1.3
%% 2007/01/11
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.7 or later) with an IEEE conference paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE! 
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex
%%*************************************************************************

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/



% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
\documentclass[conference]{IEEEtran}
% Add the compsoc option for Computer Society conferences.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
    \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at: 
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
%\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/





% *** SUBFIGURE PACKAGES ***
%\usepackage[tight,footnotesize]{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.



%\usepackage[caption=false]{caption}
%\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.





% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

\newtheorem{result}{Result}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}

\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{Exploring Options for Efficiently Evaluating \\ the Playability of Computer Game Agents}

% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{\IEEEauthorblockN{Todd Wareham and Scott Watson}
\IEEEauthorblockA{Department of Computer Science\\
Memorial University of Newfoundland\\
St.\ John's, NL Canada A1B 3X5\\
Email: harold@mun.ca, saw104@mun.ca}}

% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass

% for over three affiliations, or if they all won't fit within the width
% of the page, use this alternative format:
% 
%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
%Homer Simpson\IEEEauthorrefmark{2},
%James Kirk\IEEEauthorrefmark{3}, 
%Montgomery Scott\IEEEauthorrefmark{3} and
%Eldon Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
%Georgia Institute of Technology,
%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}

%\author{\IEEEauthorblockN{Todd Wareham\IEEEauthorrefmark{1},
%Pim Haselager\IEEEauthorrefmark{2}, 
%Johan Kwisthout\IEEEauthorrefmark{3}, and
%Iris van Rooij\IEEEauthorrefmark{2}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}Department of Computer Science\\
%Memorial University of Newfoundland\\
%St.\ John's, NL Canada A1B 3X5\\
%Email: harold@mun.ca}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Donders Institute for Brain, Cognition, and Behavior\\
%Radboud University Nijmegen\\
%Nijmegen, the Netherlands\\
%Email: W.Haselager@donders.ru.nl, I.vanRooij@donders.ru.nl}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Department of Computer Science\\
%Radboud University Nijmegen\\
%Nijmegen, the Netherlands\\
%Email: J.Kwisthout@science.ru.nl}}

% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}

% make the title area
\maketitle


\begin{abstract}
%\boldmath
Automatic generation of game content is an important challenge in computer 
game design. Such generation requires methods that are both efficient
and guaranteed to produce playable content. While existing methods are
adequate for currently available types of games, games based on more 
complex entities and structures may require new methods. In this paper,
we use computational complexity analysis to explore algorithmic options
for efficiently evaluating the playability of and generating playable
groups of enhanced agents that are capable of exchanging items and 
facts with each other and human players. Our results show that neither
of these problems can be solved both efficiently and correctly either in 
general or
relative to a surprisingly large number of restrictions 
on enhanced agent structure and gameplay. We also
give the first restrictions under which the playability evaluation problem
is solvable both efficiently and correctly.
\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the conference you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals/conferences frown on
% math in the abstract anyway.

% no keywords




% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Introduction}

\label{SectIntro}

Given the time and cost involved with the human design of computer games,
the ability to automatically generate game content is an important problem 
in computer game design \cite{TY+11,YT11}. It is
critical that such automatic methods generate playable content
because ``[g]iven the way most commercial games are designed, any risk
of the player being presented with unplayable content is unacceptable''
\cite[p.\ 183]{TY+11}. They should also operate quickly, particularly if 
content is being 
generated in real time to accommodate unanticipated player actions or choices
(a situation in which human-based methods such as testing or 
manually adjusting game parameters to ensure playability
are not applicable).

Though existing automatic methods appear to be adequate for currently available 
types of games, {\em e.g.}, \cite{WD+12}, this may not be so for more
complex games. 
A case in point is games incorporating enhanced 
agents that maintain collections of items and facts which can be both 
exchanged 
with and used in defining behavior with respect to other agents and human 
players. Such agents nicely model socially realistic agent-player interactions
that take place over long (possibly disjoint) periods of time, {\em cf.},
the short-term action-based interactions modelled by finite-state
agents \cite{DG+14,Nar07,Yan12}.
Initial work on generating groups of enhanced
agents \cite{WBV14} has demonstrated that genetic
algorithms and backtracking-based agent-group playability evaluation suffice
for the off-line and real-time generation of moderate- ($\sim$ 50) and small-
($\sim$ 5) size groups of playable agents, respectively. However, in the 
interests of improved scalability, it would be most useful to know if 
more efficient methods are available for generating larger and more complex 
groups of agents, and, if so, in what circumstances.

In this paper, we present initial results addressing both of these questions.
First, using techniques from computational complexity theory \cite{GJ79}, we 
show that evaluating the playability of a given group of enhanced agents
(in particular, determining if a human player can interact with the group
to obtain a specified goal-set of items and facts) is $NP$-hard
and thus intractable in  general. This holds even in the case where there is 
only one given agent and no time limit on achieving the goal, as 
well as whether or not the agents operate autonomously or under the control of 
a game narrative manager. Second, using techniques from parameterized
complexity theory \cite{DF13}, we establish that 
surprisingly few restrictions on enhanced agents and
human-agent interactions render playability evaluation tractable. Though these 
results are derived for the model of game agents and playability 
given in \cite{WBV14}, we show that these results apply not only to 
evaluating the playability of a much broader class of models but also to the 
playable agent-group generation process itself.

The remainder of this paper is organized as follows. In Section \ref{SectForm},
we present an augmented finite-state machine model of game agents that can
exchange items and facts with other agents and human players and formalize 
playability evaluation for such agents. Section \ref{SectCIRes} demonstrates 
the intractability of this problem. Section \ref{SectTCM} describes a 
methodology for identifying conditions for tractability, which is then applied 
in Section \ref{SectTCRes} to identify such conditions for agent playability
evaluation. In order to focus in the main text on the 
implications of our results for computer game design, all proofs of 
results are given in Appendix \ref{AppProof}. Finally, our conclusions and directions for 
future work are given in Section \ref{SectConc}.

\subsection{Related Work}

Determining whether given game levels can be completed and are thus playable
is known to be $NP$-hard (and not efficiently solvable  in general) 
for many types of games \cite{ADG+14,For10,GLN14,Lyn12,Vig12}. However this work
has not been extended to address the problem of designing playable levels,
let alone evaluating the playability or designing playable groups of agents.

There is existing work on the computational complexity of verifying if
given multi-agent systems can perform a specified task (and hence are
in  a sense ``playable'') as well as designing multi-agent systems to 
correctly perform specified tasks \cite{WD02,DLW03,Ste03,VD11}. 
The formalizations of agent control and interaction mechanisms and 
the environments analyzed in this work are very general and powerful 
({\em e.g.}, arbitrary Turing machines or Boolean propositional formulae), 
rendering the intractability of these problems unsurprising. Moreover, as 
these formalizations obscure almost all details of the agent mechanisms and 
environment, the derived results are also unenlightening with respect to 
possible restrictions that could yield tractability. Similar reasoning
applies with respect to existing complexity analyses of verification
problems relative to single robots and swarms of robots (see 
\cite[Section 4.2.1]{vRW08} and references).

\section{Formalizing Agent Playability Evaluation}

\label{SectForm}

In this section, we extend the popular finite-state model  of game
agents \cite{DG+14} to accommodate
item- and fact-enhanced agents and use this extended model to 
state the agent-group playability evaluation problem. 
To aid readability, the technical details of this extended
model and its operation in gameplay are given in Appendix
\ref{AppAFSM}.

At a minimum, an agent capable of exchanging items and 
facts with another agent (which could be a human player) should be 
able to do the following:

\begin{itemize}
\item Maintain an internal state as well as collections of
       personal items and facts;
\item Perform actions (and possibly change internal
       state) in response to another agent's
       actions and offered items and facts; and
\item As part of a performed action, give in return
       some of its own personal items and facts to that
       other agent.
\end{itemize}

\noindent
Following \cite{WBV14}, there can be at 
most one copy of an item in a game at any time ({\em i.e.}, an 
item can be possessed by at most one agent or human player) but
there can be any number of copies of a fact ({\em i.e.}, 
any number of agents or human players can possess the same 
fact). 

\begin{figure}
\begin{center}
\begin{minipage}[t]{2.8in}
\begin{center}
\includegraphics[width=2.8in]{fig1.pdf}
\end{center}
\end{minipage}
\end{center}
\caption{Three Example Augmented Finite-State Machine (AFSM) agents}
\label{FigAFSMExample}
\end{figure}

Agents with the requisite 
abilities described above can be modeled using
{\bf augmented finite-state machines (AFSM)} (see Figure \ref{FigAFSMExample}).
An AFSM is a straightforward extension of the commonly-used finite-state 
model of game agents.  Each transition between two states in an AFSM
$M$ corresponds to an interaction between $M$ and another agent in which
that other agent performs action $a$ with item- and 
fact-sets $I$ and $F$ offered to $M$ and $M$ responds in turn via action $a'$ 
with (1) a change from state $q$ to state $q'$ and (2) item- and fact-sets 
$I'$ and $F'$ being given to the other agent. 
Any unspecified proposed action and offered item- and fact-sets 
relative to a state $q$ whose result is not explicitly stated as a
transition 
is assumed to loop back on $q$ with no effect, {\em e.g.}, $M$ ignores
the offered amulet and mumbles under its breath. For simplicity,
we focus on deterministic AFSM
in which for any given $q$, $a$, $I$, and $F$, there
is at most one transition.

Examples of three 
possible AFSM representing two shopkeepers $S1$ and $S2$ and a wizard $W$ are 
shown in Figure \ref{FigAFSMExample}. These AFSM are defined relative
to the action-, item-, and fact-sets $\{${\em chat, consult, 
intimidate, offer}$\}$, 
$\{${\em false amulet (Af), true amulet (At), gold piece (G), sword (Sw)}$\}$, and
$\{${\em know shopkeeper \#1 (kS1), know shopkeeper \#2 (kS2), know wizard (kW)}$\}$, 
respectively. Each transition in which item- and fact-sets $I$ and
$F$ are offered as a result of action $a$ and $I'$ and $F'$ are given in response as part of action $a'$ is
written as an arrow between $q$ and $q'$ with the label ``$a \{I\} \{F\} /
\{I'\} \{F'\}$'', {\em i.e.}, $a'$ is ignored. For example, 
$S1$ has a transition between $q0$ and $q2$ such that $S1$ hands over the fake 
amulet when intimidated by another agent with a sword.

% For simplicity, we focus on the case in which
% agent actions can only be triggered by human players. In any sequence
% of interactions between a player and an agent $M$, 
% the player and $M$ start with specified item- and fact-sets, $M$ starts
%  in a designated state $q0$, and if a player temporarily stops 
% interacting with $M$ left in state $q$,
% the next interaction of the player with $M$ resumes with $M$
% in $q$.

Playability of a group of AFSMs can be formalized in 
terms of hard (inviolable) and soft (violable) constraints \cite{WBV14}. Example
hard and soft constraints are, respectively, that a specified goal must be 
achieved and that the interactions in any goal-achieving interaction-sequence 
should incorporate as many of the actions allowable to agents as possible.
Evaluations of playability are based on the degree to which these constraints
can be satisfied by a human player interacting with the given agents. For 
simplicity, we focus on minimum playability,
{\em i.e.}, whether or not a human player can
interact with a given set of agents to obtain specified goal-sets
of facts and items.

The above yields the following formalization:

\vspace*{0.1in}

\noindent
{\sc AFSM Agent Playability Evaluation} (APE) \\ 
{\em Input}: A set $A = \{a_1, \ldots, a_n\}$ of AFSM with associated initial 
              item- and fact-sets $\{I^0_{a_1}, \ldots, I^0_{a_n}\}$ and 
              $\{F^0_{a_1}, \ldots F^0_{a_n}\}$, initial player item- and 
              fact-sets $I^0_P$ and $F^0_P$, goal item- and fact-sets $I_G$ 
              and $F_G$, and a positive integer $t$. \\
{\em Question}: Can the player obtain $I_G$ and $F_G$ by engaging in at 
              most $t$ interactions with the agents in $A$?

\vspace*{0.1in}

\noindent
Note that this formalization applies regardless of whether the agents in $A$
operate autonomously or under the direction of a game narrative manager;
hence, results derived relative to this formalization will apply in both
of these cases.

\section{Agent Playability Evaluation is Intractable}

\label{SectCIRes}

In this section, we address whether or not agent playability evaluation
can be done efficiently relative to the model described in Section 
\ref{SectForm}. 
Following general practice in Computer Science \cite{GJ79},
we define efficient solvability
as being solvable in the worst case in time polynomially bounded in the input
size. We show that a problem is not polynomial-time solvable, {\em i.e.},
not in the class $P$ of polynomial-time solvable problems,  by proving it to be
at least as difficult as the hardest problems in problem-class $NP$
(see \cite{GJ79} and Appendix \ref{AppIntract} for details). 

\vspace*{0.1in}

\noindent
\begin{quotation}
{\em Result A}: APE is $NP$-hard.
\end{quotation}

\vspace*{0.1in}

\noindent
Modulo the conjecture $P \neq NP$ which is widely believed to be true 
\cite{For09}, the above shows that APE is not polynomial-time solvable.
Note that this result holds even in the very restricted case in which the player 
only interacts with a single agent, {\em i.e.}, $|A| = 1$, and an unlimited 
number of interactions between the player and that agent is allowed, 
{\em i.e.}, $t = \infty$.

\section{A Method for Identifying Tractability Conditions}

\label{SectTCM}

A computational problem that is intractable for unrestricted inputs may yet be tractable 
for non-trivial restrictions on the input. This insight is based on the observation that 
some $NP$-hard problems can be solved by algorithms whose running time is polynomial
in the overall input size and non-polynomial only in some aspects of the input 
called \textit{parameters}. In other words, the main part of the input contributes 
to the overall complexity in a ``good'' way, whereas only the parameters contribute
 to the overall complexity in a ``bad'' way. In such cases, the problem $\Pi$ is said to 
be \textbf{fixed-parameter tractable} for that respective set of parameters. The 
following definition states this idea more formally. 
	
\vspace*{0.1in}

\begin{definition}
Let $\Pi$ be a problem with parameters $k_1, k_2,$ $\ldots$. Then $\Pi$ is 
said to be {\bf fixed-parameter (fp-) tractable} for parameter-set $K = 
\{k_1, k_2, ...\}$ if there exists at least one algorithm that solves $\Pi$ 
for any input of size $n$ in time $f(k_1, k_2, ...)n^c$, where $f(\cdot)$ is an 
arbitrary function and $c$ is a constant. If no such algorithm exists then 
$\Pi$ is said to be {\bf fixed-parameter (fp-) intractable} for parameter-set $K$.
%
\label{DefFPT}
\end{definition}
	
\vspace*{0.1in}

\noindent
In other words, a problem $\Pi$ is fp-tractable for a parameter-set $K$ if all 
superpolynomial-time complexity inherent in solving $\Pi$ can be confined to the
 parameters in $K$. In this sense the ``unbounded" nature of the parameters in $K$ can be 
seen as a reason for the intractability of the unconstrained version of $\Pi$. 

There are many techniques for designing
fp-tractable algorithms \cite{Nie06,DF13}, and fp-intractability is established in a
manner analogous to classical polynomial-time intractability 
by proving a parameterized problem is at least as difficult as the hardest problems in one
of the problem-classes in the $W$-hierarchy $\{W[1], W[2], ...\}$ (see
\cite{DF13} and Appendix \ref{AppIntract} for details). 
Additional results are typically implied by any given result
courtesy of the following lemmas:

\vspace*{0.1in}

\begin{lemma}
\cite[Lemma 2.1.30]{War99}
If problem $\Pi$ is fp-tractable relative to parameter-set $K$ then $\Pi$ is
       fp-tractable for any parameter-set $K'$ such that $K \subset K'$.
%
\label{LemProp1}
\end{lemma}

\vspace*{0.1in}

\begin{lemma}
\cite[Lemma 2.1.31]{War99}
If problem $\Pi$ is fp-intractable relative to parameter-set $K$ then $\Pi$ is
       fp-intractable for any parameter-set $K'$ such that $K' \subset K$.
%
\label{LemProp2}
\end{lemma}

\vspace*{0.1in}

Observe that it follows from the definition of fp-tractability that if an intractable 
problem $\Pi$ is fp-tractable for parameter-set $K$, then $\Pi$ can be efficiently 
solved even for large inputs, provided only that the values of all parameters in $K$ are 
relatively small. 
% This implies that an intractable problem $\Pi$ can be rendered 
% tractable under those conditions in which inputs have small values on exactly those 
% parameters for which $\Pi$ is fp-tractable. 
This strategy has been successfully applied to a wide variety of
intractable problems
(see \cite{DF13,Ste12} and references). In the 
next section we investigate how the same strategy may be 
used to render the problem APE tractable. 

\section{What Makes Agent Playability Evaluation Tractable?}

\label{SectTCRes}

\begin{table*}
\caption{Fixed-parameter Intractability Results for the Agent
          Playability Evaluation Problem}
\label{TabRes}
%
{
\begin{center}
\begin{tabular}{| l c || c | c | c | c | c |}
\hline
        & & \multicolumn{5}{c|}{\hspace*{0.3in}} \\
 \multicolumn{2}{|c||}{Parameter} & \multicolumn{5}{c|}{Result} \\
        & & \multicolumn{5}{c|}{\hspace*{0.3in}} \\
\cline{3-7}
Description & Name & B & C & D & E & F \\
\hline\hline
        & \hspace*{0.7in} & \hspace*{0.5in} & \hspace*{0.5in} & \hspace*{0.5in} & \hspace*{0.5in} & \hspace*{0.5in} \\
AGENTS: & & & & & & \\
        & & & & & & \\
\# agents                  &$|A|$&  --&   $P$&   $P$&   $P$&     1 \\
\hline
max \# items per agent       &$i_A$&   0&     1&     1&     1&    -- \\
\hline
max \# facts per agent       &$f_A$&   3&    --&    --&    --&    -- \\
\hline
max \# items per interaction &$i_I$&   0&     1&     1&     2&     1 \\
\hline
max \# facts per interaction &$f_I$& $P$&    --&     2&     2&     2 \\
\hline
max \# states per agent      &$|Q|$&   2&    --&    --&    --&   $P$   \\
\hline
max \# interactions per state&$|I|$&   1&    --&     2&    --&    -- \\
\hline\hline
        & & & & & & \\
PLAYER: & & & & & & \\
        & & & & & & \\
max \# items per player      &$i_P$&    0&    --&    --&    --&     -- \\
\hline
max \# facts per player      &$f_P$&  $P$&    --&    --&   $P$&    $P$ \\
\hline\hline
        & & & & & & \\
GAME: & & & & & & \\
        & & & & & & \\
max \# interactions in game       &  $t$&  $P$&   $P$&    --&   $P$&    $P$   \\
\hline
max \# items in goal       &$i_G$&    0&     0 &    0&     0&     0 \\
\hline
max \# facts in goal       &$f_G$&    1&      1&    1&     1&     1 \\
\hline
\end{tabular}
\end{center}
}
\end{table*}

The AFSM agent playability evaluation problem has a number of parameters whose 
restriction could render agent playability evaluation tractable. An 
overview of the parameters that we considered in our fp-tractability analysis 
is given in Table \ref{TabRes}. These parameters  can be divided into three 
groups:

\begin{enumerate}
\item Restrictions on the game agents;
\item Restrictions on the human player; and
\item Restrictions on the game itself.
\end{enumerate}

\noindent
In the remainder of this section, we will assess the fp-tractability of
APE relative to all parameters in Table \ref{TabRes} (Section
\ref{SectAPERes}), show how these results apply in more general 
settings (Section \ref{SectGenRes}) as well as to playable AFSM agent
generation (Section \ref{SectDesRes}), and discuss the implications of
these results for computer game design (Section \ref{SectDisc}).


\subsection{Results}

\label{SectAPERes}

Our parameterized intractability results are summarized in Table \ref{TabRes}. 
Each column describes an intractability result that holds 
relative to the set of all parameters whose entries in 
that column are not dashes (``--''); if the result holds when a
non-dashed parameter has constant value $c$, this indicated by an entry
for that parameter with the value $c$.
Result B is notable because it, when combined with results implied by
Lemma \ref{LemProp2}, establishes the intractability of APE
relative to all subsets of the considered parameters that do not include
$|A|$; the intractability of many (but not all) of those remaining subsets 
including $|A|$ is then established by Results C--F.

At present, we have a lone tractability result:

\vspace*{0.1in}

\begin{quotation}
{\em Result G}: APE is fp-tractable for $\{|A|, |I|, t\}$.
\end{quotation}

\vspace*{0.1in}

\noindent
Results B, D, F, and G, combined with those implied by Lemmas 
\ref{LemProp1} and \ref{LemProp2}, establish the intractability of APE 
relative to all subsets of $\{|A|, i_I, f_I, |I|, t, i_G, f_G\}$. This in 
turn establishes that the parameter-set in Result G is minimal in the sense 
that no parameter in that set can be deleted to yield fp-tractability.

\subsection{Generality of Agent Playability Evaluation Results}

\label{SectGenRes}

Our intractability results, though defined relative to 
an admittedly simple model of game agents and human-agent
interaction, have a remarkable generality. 
Observe that this model is a special case of many more
realistic models, {\em e.g.},

\begin{itemize}
\item deterministic AFSM are special cases of both nondeterministic
       and probabilistic AFSM (AFSM without non-determinism or in
       which all all actions have probability of execution 1.0 if
       their triggering conditions are satisfied are deterministic);
\item player-activated AFSM are special cases of autonomous AFSM
       (restrict non-player-triggered interaction); and 
\item basic AFSM ares special cases of AFSM with extra abilities 
       (restrict use of these extra abilities).
\end{itemize}

\noindent
Intractability results for these more realistic models then follow 
from the well-known observation in computational complexity theory that
intractability results for a problem $\Pi$ also hold for any problem $\Pi'$
that has $\Pi$ as a special case (suppose $\Pi$
is intractable; if $\Pi'$ is tractable, then any algorithm for $\Pi'$
 can be used to solve $\Pi$
efficiently, which contradicts the intractability of $\Pi$ -- hence, $\Pi'$
must also be intractable). 

Our fp-tractability result is more fragile, as innocuous changes to
agent or game models may in fact violate assumptions critical to
the operation of the algorithm underlying this result. For now, we
can say that as our fp-tractability results depend on the combinatorics of 
possible player-agent interactions and require only that
any such interaction can be checked for validity and performed in
time polynomial in the sizes of the entities involved in that
interaction, our tractability result
holds for {\em all} choices of agent
and game model whose player-agent interactions are
polynomial-time verifiable.

\subsection{Applicability to Playable Agent Generation}

\label{SectDesRes}

The results given so far for APE are useful in suggesting
improvements to the playability-evaluation module in systems like that
described in Watson et al \cite{WBV14}. However, our ultimate goal is still the
efficient generation of playable agents, regardless of whether or not an explicit
playability-evaluation module is used. In this section, we will sketch how our
results for APE apply to this larger problem.

\newpage

Though a full formalization of the AFSM agent-group generation problem is beyond
the scope of this paper, we can informally sketch what such a
problem might look like. It is trivial to construct an agent-group $A$
that will allow a player to obtain specified goal item- and fact-sets
within $t$ steps (let $A$ consist of a single AFSM whose lone transition
gives the player all required items and facts in response to an arbitrary
action on the part of the player). Hence, a specification of the characteristics
of the desired agent-group must be given; let us call such a specification
$S_A$. As a minimum, $S_A$ should specify two types of characteristics:

\begin{enumerate}
\item Overall characteristics of agent-group and individual-agent
       structure; and
\item Required internal structures of individual agents.
\end{enumerate}

\noindent
The first type of characteristics correspond to the AGENTS parameters in
Table \ref{TabRes} while the second could consist of specifications of
required states and transitions along the lines of the system described
in Watson et al \cite{WBV14}. 

The above yields the following: 

\vspace*{0.1in}

\noindent
{\sc AFSM Playable Agent Generation} (PAG) \\ 
{\em Input}: Item- and fact-sets $I$ and $F$, an AFSM-group specification 
              $S_A$, initial player item- and 
              fact-sets $I^0_P$ and $F^0_P$, goal item- and fact-sets $I_G$ 
              and $F_G$, and a positive integer $t$. \\
{\em Output}: An AFSM-group $A$ consistent with $S_A$ such that the player 
               can obtain $I_G$ and $F_G$ by engaging in at most $t$ 
               interactions with the agents in $A$, if such an $A$ exists,
               and special symbol $\bot$ otherwise.

\vspace*{0.1in}

\noindent 
This informal version can be fully formalized relative to a particular format in
which specifications are written.
Consider the set of specification-formats in which one can create
in time polynomial in $|A|$ a specification that can only be satisfied by a 
given AFSM-set $A$; let us call this set $\cal{S}$. 

To see how the intractability results given in Sections \ref{SectCIRes}, 
\ref{SectAPERes}, and \ref{SectGenRes} 
apply to PAG, note the following -- namely,
any algorithm $a$ for a version of PAG formalized relative to any member of 
$\cal{S}$ can be used to answer any instance of APE (given an instance $I$ of 
APE with agent-set $A$, construct an instance $I'$ of PAG such that $S_A$ 
generates $A$; return ``No'' for $I$ if $a$ run on $I'$ returns $\bot$
and ``Yes'' otherwise). Hence, {\em any} intractability result (including {\em all}
intractability results in Sections \ref{SectCIRes}, \ref{SectAPERes}, and 
\ref{SectGenRes}) that forbids the existence of a
certain type of algorithm for APE also then forbids that type of
algorithm for any version of PAG formalized relative to any member of
$\cal{S}$. Our lone tractability result for APE does not appear to apply in such
a general manner to PAG; however it may hold relative to specific members of 
$\cal{S}$.

\subsection{Discussion}

\label{SectDisc}

We have found that evaluating agent playability is $NP$-hard (Result A).
This $NP$-hardness holds for a basic agent model and a minimal 
playability condition that a human player can attain a specified goal by
interacting with the given group of agents, even when that group consists 
of a single agent; moreover, as pointed out in Section \ref{SectDesRes},
this also applies to plausible schemes for generating playable agents. 

Our results immediately imply that it is unlikely that deterministic
polynomial-time methods exist for these problems. The scope of these results
is actually broader still. It is widely believed that $P = BPP$ 
\cite[Section 5.2]{Wig07} where 
$BPP$ is considered the most inclusive class of problems that can efficiently 
solved using probabilistic methods (in particular, methods whose probability of
correctness can be efficiently boosted to be arbitrarily close to
probability one). Hence, our results also imply that unless $P = NP$, 
there are no probabilistic polynomial-time methods which correctly evaluate or 
generate playable agent-groups with high probability for all inputs. This then 
constitutes the first proof that 
{\em no} currently-used method (including the automated search and
simulated-play-based processes described in \cite{TY+11,YT11} 
or evolutionary algorithms such as that employed in \cite{WBV14}) 
can guarantee both efficient and correct operation for all inputs
for these problems.

As described in Section \ref{SectTCM}, efficient correctness-guaranteed methods
may yet exist relative to plausible restrictions on the input and output.
To our knowledge, no such restrictions have been proposed in the literature
for either  agent playability evaluation or playable agent generation.
It seems reasonable to conjecture that some restrictions 
relative to the parameters listed in Table \ref{TabRes} should render 
these problems tractable. However, no single one or
indeed many possible combinations of these restrictions can yield
tractability, even when the parameters involved are restricted to very
small constants (Results B--F and Section \ref{SectDesRes}). 

The one exception that we have found to date (and only for agent
playability evaluation) is that of simultaneously 
restricting $|A|$, $|I|$, and $t$ (Result G). Though
this may initially seem of limited interest in that it overly restricts
the form of games whose playability can be checked efficiently, it 
actually suggests several reasonable ways in which games can be 
decomposed into sub-games whose playability can be checked efficiently.
For example, a long game could be decomposed into several shorter ones 
(restrict $t$). Alternatively, the game could be structured such that
only a very small number of agents or player-agent interactions are 
necessary and/or relevant to achieving the goal (restrict $|A|$ and/or 
$|I|$); this could be done while preserving a larger game environment 
by embedding the goal-relevant set of agents and interactions within a 
goal-irrelevant set of agents and interactions, {\em e.g.}, only 
a few shopkeepers, wizards, or travellers are worth talking to and only
about specific matters.

A valid objection to this lone tractability result is that the running time 
of the underlying algorithm is impractical. This is often true of the initial
algorithms derived relative to a parameter-set. However, our result
is important nonetheless because it establishes fixed-parameter tractability 
relative to a set of parameters which (by reasoning like that above) can be of 
small value in practice. Once this has been done, surprisingly effective 
parameterized algorithms can frequently be developed with both 
greatly diminished non-polynomial terms and polynomial terms that are quadratic
and even linear in the input size (see \cite{DF13,Nie06} and references). 

\newpage

A final very important proviso is in order -- namely, as illuminating as
the results given here are in demonstrating basic forms of (in)tractability
for the agent playability evaluation and playable agent generation problems,
these results do not necessarily imply that methods
currently being applied to evaluate or generate agents are impractical.
Differing agent models, the particular situations in which these methods are 
being applied, and accepted standards by which method practicality is assessed 
may render the results given here irrelevant. For example, current methods may 
already be implicitly exploiting restrictions on the input and output such that
both efficient and correct operation (or operation that is correct with
probability very close to one) are guaranteed.
That being said, not knowing the precise conditions under which
such practicality holds could have very damaging consequences, {\em e.g.},
drastically slowed gameplay and/or unplayable game content, for systems 
(in particular, real-time-adaptable systems) using such methods that stray
outside these conditions.  Given that (as noted earlier in Section \ref{SectIntro})
playability and its efficient evaluation and 
enforcement are very important properties of game systems, the acquisition of 
such knowledge via a combination of rigorous empirical and theoretical
analyses should be a priority. With respect to theoretical analyses,
it is our hope that the techniques and results in this paper comprise
a useful first step.

\section{Conclusions}\label{SectConc}

We have presented a formal characterization of the problem of game agent 
playability evaluation relative to an
augmented finite-state machine model of game agents.
Our complexity analyses reveal that, while this problem is computationally 
intractable in general, there are conditions that render it tractable. 
Knowledge of this and other such conditions can be exploited in 
computer game design to create efficient playability-guaranteed content 
generation methods with respect to more complex and interesting gameplay 
involving player interactions with more socially realistic game agents.

In future research, we plan to explore the computational consequences
of additional types of restrictions on agent playability evaluation 
and playable agent design relative to both the agent-model described in this 
paper and more complex agent-models ({\em e.g.},
agents that are truly autonomous rather than player-activated)
as well as minimal and broader conceptions of playability. We will also
build on previous work establishing the $NP$-hardness of evaluating 
the playability of and generating playable game levels by applying 
parameterized analysis to establish under which restrictions these
problems can and cannot be solved efficiently. Finally, given
work positing connections between human cognition and
fixed-parameter tractability \cite{vRW08,vR08}, we will
investigate the extent to which results such as those we have derived
here can help in creating games whose
level of difficulty not only is more appropriate to human players but
can also be efficiently customized to the abilities
of those players \cite{YT11}.

\section*{Acknowledgments}

The authors would like to thank Rod Byrne, Andrew Vardy, and Wolfgang Banzhaf
for encouraging them to embark on this research and two anonymous reviewers
for comments that improved the presentation of this paper. TW was supported by 
NSERC Discovery Grant RGPIN 228104-2010 and SW was supported by 
NSERC Discovery Grant RGPIN 283304-2012  to Wolfgang Banzhaf and a doctoral 
award from the Dean of the School of Graduate Studies at MUN.



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,paper}
\bibliography{paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
%\begin{thebibliography}{1}
%
%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
%
%\end{thebibliography}

\appendices

\section{Augmented Finite-State Machines}

\label{AppAFSM}

Recall that for any set $S$, 
$2^S$ denotes the set of all possible subsets of $S$ (including the empty set 
$\emptyset$). Define an {\bf augmented
finite-state machine (AFSM)} (see Figure \ref{FigAFSMExample}) relative to game-overall action-, 
item-, and fact-sets
$A^G$, $I^G$, and $F^G$ as a 2-tuple $\langle Q, \delta \rangle$ where
$Q$ is a set of states and $\delta \subseteq Q \times A^G \times 2^{I^G} \times 2^{F^G} \times
A^G \times 2^{I^G} \times 2^{F^G} \times Q$ is a state-transition relation. A transition
$(q, a, I, F, a', I', F', q') \in \delta$ of an AFSM $M$ can be interpreted 
as an interaction between $M$ and another agent in which
that other agent performs action $a$ with item- and 
fact-sets $I$ and $F$ offered to $M$ and $M$ responds in turn via action $a'$ 
with (1) a change from state $q$ to state $q'$ and (2) item- and fact-sets 
$I'$ and $F'$ being given to the other agent. 
Any unspecified proposed action and offered item- and fact-sets 
relative to a state $q$ whose result is not explicitly stated in $\delta$
is assumed to loop back on $q$ with no effect.
There are many
possible ways of specifying determinism and non-determinism relative 
to AFSM; we will focus on AFSM that are {\bf offered (o-)
deterministic}, {\em i.e.}, for any given $q$, $a$, $I$, and $F$, there
is at most one $(q, a, I, F, a', I', F', q') \in \delta$.

\begin{figure*}[t!]
\begin{center}
Interaction-sequence \#1 \\
\vspace*{0.1in}
\begin{tabular}{| l || c | c | c | c |}
\hline
Interaction & $P$ & $S1$ & $S2$ & $W$ \\
\hline\hline
-- & $\{2G\}, \{\}$
   & $q0: \{Af, At\}, \{kS1\}$
   & $q0: \{Sw\}, \{kS2\}$
   & $q0: \{\}, \{kW\}$\\
\hline
$S1$: {\em offer} $\{1G\}, \{\}$ 
   & $\{1G, Af\}, \{kS1\}$
   & $q1: \{1G, At\}, \{kS1\}$
   &  "
   & " \\
\hline
$S2$: {\em chat} $\{\}, \{kS1\}$ 
   & $\{1G, Af\}, \{kS1, kS2\}$
   &  "
   &  "
   & " \\
\hline
$W$: {\em offer} $\{1G\}, \{\}$ 
   & $\{Af\}, \{kS1, kS2\}$
   &  "
   &  "
   & $q1: \{1G\}, \{kW\}$\\
\hline
$W$: {\em cnslt} $\{Af\}, \{kS2\}$ 
   & $\{Af\}, \{kS1, kS2, kW\}$
   &  "
   &  "
   & $q3: \{1G\}, \{kW\}$\\
\hline
$S1$: {\em offer} $\{Af\}, \{kW\}$ 
   & $\{At\}, \{kS1, kS2, kW\}$
   & $q3: \{1G, Af\}, \{kS1\}$
   &  "
   &  " \\
\hline
\end{tabular} 

\vspace*{0.1in}
Interaction-sequence \#2 \\
\vspace*{0.1in}
\begin{tabular}{| l || c | c | c | c |}
\hline
Interaction & $P$ & $S1$ & $S2$ & $W$ \\
\hline\hline
-- & $\{20G\}, \{\}$
   & $q0: \{Af, At\}, \{kS1\}$
   & $q0: \{Sw\}, \{kS2\}$
   & $q0: \{\}, \{kW\}$\\
\hline
$S2$: {\em offer} $\{2G\}, \{\}$ 
   & $\{18G, Sw\}, \{\}$
   &  "
   &  $q0: \{2G\}, \{kS2\}$
   & " \\
\hline
$S1$: {\em intim} $\{Sw\}, \{\}$ 
   & $\{18G, Sw, Af\}, \{\}$
   &  $q2: \{At\}, \{kS1\}$
   &  "
   & " \\
\hline
$W$: {\em offer} $\{1G\}, \{\}$ 
   & $\{17G, Sw, Af\}, \{\}$
   &  "
   &  "
   &  $q1: \{1G\}, \{kW\}$ \\
\hline
$W$: {\em cnslt} $\{Af\}, \{\}$ 
   &  "
   &  "
   &  "
   &  " \\
\hline
$S1$: {\em offer} $\{10G\}, \{\}$ 
   & $\{7G, Sw, Af\}, \{kS1\}$
   &  $q1: \{10G, At\}, \{kS1\}$
   &  "
   &  " \\
\hline
$S2$: {\em chat} $\{\}, \{kS1\}$ 
   & $\{7G, Sw, Af\},$
   &  "
   &  "
   &  " \\
   & $\{kS1, kS2\}$
   &  
   &  
   &   \\
\hline
$W$: {\em cnslt} $\{Af\}, \{kS2\}$ 
   & $\{7G, Sw, Af\},$
   &  "
   &  "
   &  $q3: \{1G\}, \{kW\}$ \\
   & $\{kS1, kS2, kW\}$
   &  
   &  
   &  \\
\hline
$S1$: {\em offer} $\{Af\}, \{kW\}$ 
   &  $\{7G, Sw, At\},$
   &  $q3: \{10G, Af\}, \{kS1\}$
   &  "
   &  " \\
   & $\{kS1, kS2, kW\}$
   &  
   &  
   &   \\
\hline
\end{tabular}

\vspace*{0.1in}
Interaction-sequence \#3 \\
\vspace*{0.1in}
\begin{tabular}{| l || c | c | c | c |}
\hline
Interaction & $P$ & $S1$ & $S2$ & $W$ \\
\hline\hline
-- & $\{2G\}, \{\}$
   & $q0: \{Af, At\}, \{kS1\}$
   & $q0: \{Sw\}, \{kS2\}$
   & $q0: \{\}, \{kW\}$ \\
\hline
$S2$: {\em offer} $\{2G\}, \{\}$ 
   & $\{Sw\}, \{\}$
   &  "
   &  $q0: \{2G\}, \{kS2\}$
   & " \\
\hline
$S1$: {\em intim} $\{Sw\}, \{\}$ 
   & $\{Sw, Af\}, \{\}$
   & $q2: \{At\}, \{kS1\}$
   & "
   & " \\
\hline
$W$: {\em intim} $\{\}, \{\}$ 
   & "
   & "
   & "
   & $q2: \{\}, \{kW\}$ \\
\hline
$S2$: {\em intim} $\{\}, \{\}$ 
   & "
   & "
   & "
   & " \\
\hline
\end{tabular}
\end{center}
\caption{Three Example AFSM Agent -- Human Player Interaction-sequences}
\label{FigAFSMInteractionExample}
\end{figure*}

Define the execution of interactions of an AFSM $M = \langle Q, \delta 
\rangle$ with another agent $X$ as follows. A transition 
$(q, a, I, F, a', I', F', q')$ is {\bf enabled} relative to $M = \langle Q, \delta \rangle$
and $X$,
where $M$ and $X$ currently possess the items and facts in sets $I_M$,
$F_M$, $I_X$, and $F_X$, respectively, if:

\begin{enumerate}
\item $(q, a, F, I, a', F', I', q') \in \delta$;
\item $M$ is currently in  state $q$;
\item $I \subseteq I_X$ and $F \subseteq F_X$; and
\item $I' \subseteq I_M \cup I$ and $F' \subseteq F_M$.
\end{enumerate}

\noindent
The {\bf execution} of a transition $(q, a, I, F, a', I', F', q')$ that is 
enabled relative $M$ and $X$ has the following effects:

\begin{enumerate}
\item The state of $M$ is set to $q'$;
\item $I_X$ is set to $(I_X - I) \cup I'$;
\item $F_X$ is set to $F_X \cup F'$; and
\item $I_M$ is set to $(I_M \cup I') - I'$.
\end{enumerate}

\noindent
For simplicity, we only consider the case in which
the other agent $X$ is a human player, {\em i.e.}, agent actions can
only be triggered by human players. Three possible sequences of interactions
of the AFSM in Figure \ref{FigAFSMExample} with a human player are
shown in Figure \ref{FigAFSMInteractionExample}. 
% Note that in each
% such interaction-sequence, the players and agents start with specified
% item- and fact-sets, each agent starts in a designated state $q0$,
% and if a player temporarily stops interacting an agent $M$ left in state $q$
% with current item- and fact-sets $I$ and $F$,
% the next interaction of the player with $M$ resumes with $M$
% in state $q$ with current item- and fact-sets $I$ and $F$.
% 
% For simplicity, we focus on minimum playability,
% {\em i.e.}, whether or not a human player can
% interact with a given set of agents to obtain specified goal-sets
% of facts and items within a given time limit. 
With respect to the goal consisting of having the true amulet and 
knowing the wizard, the first and second interaction-sequences 
%in Figure \ref{FigAFSMInteractionExample} 
achieve this goal within 5 and 8 interactions, respectively, while the 
third
interaction-sequence does not achieve the goal and moreover cannot be
extended by any sequence of interactions to achieve the goal.


\section{Proving Intractability}

\label{AppIntract}

Given some criterion of tractability like polynomial-time or fixed-parameter solvability,
we can define the class $T$ of all computational problems that are tractable relative to that criterion.
For example, $T$ could be the class
$P$ of decision problems (see below) solvable in polynomial-time, or $FPT$, the class of
parameterized problems that are fp-tractable. We can show that a particular
problem is not in $T$ (and thus that this problem is intractable) by showing that
this problem is at least as hard as the hardest problem in some class
$C$ that properly includes (or is strongly conjectured to properly include) $T$.
For example, $C$ could be $NP$, the class of decision problems whose candidate
solutions can be verified in polynomial time, or a class of parameterized problems
in the $W$-hierarchy $= \{W[1], W[2], \ldots, W[P], \ldots, XP\}$ (see \cite{GJ79} and
\cite{DF13}, respectively, for details).

We will focus here on reducibilities between pairs of {\bf decision
problems}, {\em i.e.}, problems whose outputs are either ``Yes'' or ``No''.
The two types of reductions used in this paper are as follows.

\vspace*{0.1in}

\begin{definition}
Given a pair $\Pi$, $\Pi'$ of decision problems, {\bf $\Pi$ polynomial-time many-one
reduces to $\Pi$} if there is a polynomial-time computable
function $f$ mapping instances $I$ of $\Pi$ to instances $f(I)$ of $\Pi'$ such that
the answer to $I$ is ``Yes'' if and only if the answer to $f(I)$ is ``Yes''.
%
\label{DefRedmo}
\end{definition}

\vspace*{0.1in}

\begin{definition}
Given a pair $\Pi$, $\Pi'$ of parameterized decision problems with parameters $p$ and $p$,
respectively, , {\bf $\Pi$ fp-reduces
to $\Pi$} if there is a function $f$ mapping instances $I = (x, p)$ of
$\Pi$ to instances $I' = (x', p')$ of $\Pi'$ such that (i) $f$ is computable in $g(p)|x|^\alpha$
time for some function $g()$ and constant $\alpha$, (ii) $p' = h(p)$ for some function
$h()$, and (iii) the answer to $I$ is ``Yes'' if and only if the answer to $I' = f(I)$ is ``Yes''.
%
\label{DefRedfp}
\end{definition}

\vspace*{0.1in}

\noindent
A reducibility is appropriate for a tractability class $T$ if whenever $\Pi$ reduces to $\Pi'$
and $\Pi' \in T$ then $\Pi \in T$. We say that a problem $\Pi$ is {\bf $C$-hard} for a class $C$ if
every problem in $C$ reduces to $\Pi$. A $C$-hard problem is essentially as hard as the
hardest problem in $C$.

Reducibilities become particularly useful given the following
easily-provable properties:

\begin{enumerate}
\item If $\Pi$ reduces to $\Pi'$ and $\Pi$ is $C$-hard then $\Pi'$ is $C$-hard.
\item If $\Pi$ is $C$-hard and $T \subset C$ then $\Pi \not\in T$, {\em i.e.},
       $\Pi$ is not tractable.
\item If $\Pi$ is $C$-hard and $T \subseteq C$ then $\Pi \not\in T$ unless $T = C$, {\em i.e.},
       $\Pi$ is not tractable unless $T = C$.
\end{enumerate}

\noindent
%These properties are easily provable for many commonly-used 
%reducibilities.
% , including those given in Definitions \ref{DefRedmo} and 
% \ref{DefRedfp} above.
The first and third properties are used below to show 
intractability relative to $T$-classes $P$ and $FPT$ 
and $C$-classes $NP$, $W[1]$, and $XP$. Note that these intractability
results hold relative to the conjectures $P \neq NP$ and $FPT \neq W[1]$ which, though
not proved, are commonly accepted as true within the
Computer Science community (see \cite{GJ79,DF13,For09} for details).

\section{Proofs of Results}

\label{AppProof}

All of our intractability results will be derived using reductions from the
following $NP$-hard decision problems:

\vspace*{0.1in}

\noindent
{\sc Nondeterministic Turing machine computation} \\
{\em Input}: A single-tape, single-head nondeterministic Turing machine $M = \langle \Sigma, Q,
              \Delta, s, F\rangle$ (where $\Sigma$ is an alphabet, $Q$ is a set of internal states,
	      $\Delta \subseteq  Q \times \Sigma \times Q$ is a set of transitions, $s \in Q$
	      is the start state, and $f \in Q$ is the final state), a word $x \in \Sigma^*$, and 
	      a positive integer $k$. \\
{\em Question}: Is there a computation of $M$ on $x$ starting in $s$ that reaches some final state $f \in F$ in at
              most $k$ steps?

%\vspace*{0.1in}
\newpage

\noindent
{\sc Dominating set} \cite[Problem GT2]{GJ79} \\
{\em Input}: An undirected graph $G = (V, E)$ and an integer $k$. \\
{\em Question}: Does $G$ contain a dominating set of size $\leq k$, {\em i.e.}, is
              there a subset $V' \subseteq V$, $|V'| \geq k$, such that for
	      all $v \in V'$, either $v \in V'$ or there is a $v' \in V'$ such
	      that $(v, v') \in E$?

\vspace*{0.06in}

\noindent
{\sc Clique} \cite[Problem GT19]{GJ79} \\
{\em Input}: An undirected graph $G = (V, E)$ and an integer $k$. \\
{\em Question}: Does $G$ contain a clique of size $\geq k$, {\em i.e.}, is
              there a subset $V' \subseteq V$, $|V'| \geq k$, such that for
	      all $v, v' \in V'$, $(v, v') \in E$?

\vspace*{0.06in}

\begin{lemma}
$\{k\}$-{\sc NTMC} fp-reduces to $\{i_A, f_A, i_I, f_I,$ $ |Q|, |I|, i_G, f_G,
t, i_P, f_P\}$-APE such that in the constructed instance of APE, 
$i_A = 0$, $f_A = 3$, $i_I = 0$, $|Q| = 2$, $|I| = 1$, $i_P = 0$,
$i_G = 0$, and $f_G = 1$, and the values of $f_I$, $f_P$, and $t$ are 
all functions of $k$ in the given instance of {\sc NTMC}.
%
\label{LemRedAPENTMC}
\end{lemma}

\begin{IEEEproof}
Given an instance $\langle M = \langle \Sigma, Q, \Delta, s, F\rangle,
x, k\rangle$ of NTMC, construct an instance of APE in which the state of
the NTM at time $t$, $0 \leq t \leq k$, is encoded by a time-fact $t$,
a time/head-position fact $t/i$, $1 \leq i \leq k$, a time/state fact
$t/q$, $q \in Q$, and $k$ time/tape square position/tape square contents
(TTT) facts $t/i/s$, $1 \leq i \leq k$ and $s \in \Sigma$. Each write transition
$(q,x,q')$ in $M$ is encoded by $k \times k \times \Sigma$ agents each 
consisting of states $q_0$ and $q_1$ with a single transition that 
is enabled by the time-fact $t$, time/head position fact $t/i$, time/state 
fact $t/q$, and TTT fact $t/i/s$ and returns the corresponding facts $(t+1)$, 
$(t+1)/i$, $(t+1)/q'$, and $(t+1)/i/s$ for $0 \leq t < k$, $1 \leq i \leq k$, 
and $s' \in \Sigma$. Analogous sets of agents are constructed for all 
left-move and right-move transitions in $M$. The following four sets of 
two-state single-transition agents are also required:

\begin{enumerate}
\item A set of agents that individually enable on time-fact $t$ and TTT
       fact $(t-1)/i/s$ and return the 
       TTT fact $t/i/s$ for $1\leq t, i \leq k$ and $s \in \Sigma$ ({\em i.e.}, 
       bring forward in time all tape-square contents not updated by a 
       write-transition at time $(t-1)$);
\item A set of agents that individually enable on time/state fact $t/f$ and
       return time/state fact $(t+1)/f$ for $1 \leq t < k$ and $f \in F$
       ({\em i.e.}, bring forward in time any final state reached at or before
       time $(t - 1)$); 
\item A set of agents that individually enable on time-fact $k$ and TTT
       fact $k/i/s$ and return
       TTT fact $k/i/s''$ for some $s'' \not\in \Sigma$ ({\em i.e.}, erase the
       contents of the tape at time $k$); and
\item A set of agents that enable on time-fact $k$, time/state fact $t/f$, and 
       TTT facts $k/1/s'', k/2/s'', \ldots k/k/s''$ and return 
       completion-fact $c$ for $f \in F$.
\end{enumerate}

\noindent
Each agent starts with no items and the facts it returns and the player
starts with no items and the facts corresponding to an initial
state $q_0$, head position 1, and $x$ on the first $|x|$ squares
of the tape and $s''$ in the remaining $k - |x|$ squares. Finally, set the
goal to $c$ and $t = (k + 1)k + 1$. Note that the instance of APE described
above can be constructed in time that is fp-tractable with respect to $k$ and
the size of the given instance of {\sc Dominating set} (this is necessary
as $k$ is stored in binary in the given instance and the value of
$k$ is exponential in $\log_2 k$).

If there is a transition-sequence of length at most $k$ for $M$ computing
on $x$ from $s$ that reaches a final state, there is a sequence of exactly $t$ 
agent-player interactions that will achieve the goal (as all tape-squares must 
be updated to time $k$ and be available for subsequent erasure in order
to obtain goal-fact $c$). Conversely, if there is an interaction-sequence
of length $t$ that achieves the goal, there must be embedded in this 
sequence a subsequence of interactions of length $\leq k$ that allowed 
time/state fact $k/f$ to be derived from time/state fact $0/q_0$,
time/head position fact $0/1$, and the TTT facts encoding of $x$ on the tape,
which corresponds to a sequence $k$ transitions that allow $M$ computing
on $x$ from $s$ to reach a final state.

To complete the proof, note that in the constructed instance of APE,
$i_A = 0$, $f_A = 3$, $i_I = 0$, $|Q| = 2$, $|I| = 1$, $i_P = 0$,
$i_G = 0$, $f_G = 1$, $f_I = k + 2$, $f_P = k(k + 3) + k + 1$, 
and $t = (k + 1)k + 1$.
\end{IEEEproof}

\vspace*{0.06in}

\begin{lemma}
{\sc Dominating Set} polynomial-time many-one reduces to APE such that in the constructed instance
of APE, $i_A = i_I = 1$, $i_G = 0$, $f_G = 1$, and $|A|$ and $t$ are both a function of $k$ in the given 
instance of {\sc Dominating Set}.
%
\label{LemRedAPEDS1}
\end{lemma}

\begin{IEEEproof}
Given an instance $\langle G = (V, E), k\rangle$ of {\sc Dominating 
set}, the constructed instance of APE consists of $k$ identical agents plus
an additional final agent. Each of the identical agents consists of an initial 
state $q_0$ and a transition from
$q_0$ to each of the $|V|$ states $q_i$, $1 \leq i \leq |V|$, in which 
the offered item $v_i$ is exchanged for the set of facts corresponding
to all vertices in the neighbourhood of of $v_i$ (including $v_i$ itself)
in $G$. The final agent consists of two states $q_0$ and $q_1$ and a
transition from $q_0$ to $q_1$ that exchanges the complete set of
vertex-facts for $G$ for a completion-fact. Each identical agent starts with 
no items and the complete set of vertex-facts for $G$, the final agent starts
with no items and the completion-fact, and the player starts with the complete 
set of vertex-items for $G$ and no facts. Finally, the goal is the 
completion-fact and $t = k + 1$. Note that the instance of APE described
above can be constructed in time polynomial in the size of the given instance
of {\sc Dominating set}. 

If there is a dominating set of size at most $k$ in the given instance of
{\sc Dominating set}, the player 
can exchange the vertices in that dominating set with at most $k$ of the
identical agents to obtain the complete set of vertex-facts for $G$ and hence
achieve the goal. Conversely, as the player can interact with each of the
identical agents at most once to trade a vertex-item for its associated
neighbourhood-set of vertex-facts in $G$, any set of at most $k + 1$ 
interactions between the player and the agents that achieves the goal in
the constructed instance of APE must
correspond to a set of at most $k$ vertices that form a dominating set in $G$.

To complete the proof, note that in the constructed instance of APE,
$i_A = i_I = f_G =  1$, $i_G = 0$, and $|A| = t = k + 1$.
\end{IEEEproof}

\vspace*{0.06in}

\begin{lemma}
{\sc Dominating Set} polynomial-time many-one reduces to APE such that in 
the constructed instance of APE, $i_A = i_I = 1$, $f_I = |I| = 2$, $i_G = 0$, 
and $f_G = 1$, and $|A|$ is a function of $k$ in 
the given instance of {\sc Dominating Set}.
%
\label{LemRedAPEDS2}
\end{lemma}

\begin{IEEEproof}[Proof (sketch)]
Modify the instance of APE constructed in Lemma \ref{LemRedAPEDS1}
as follows: (1) Replace all
$|V|$ transitions in each identical agent with a transition-tree rooted
at $q_0$ consisting of a $|V|$-;length ``spine'' of transitions, each of
which is enabled by a move-fact, with $|V|$ branches off this spine, where
each branch is a $|V|$-length chain of transitions which are initially enabled by item $v_i$ and deliver (one at a time) the vertex-facts corresponding to the
neighbourhood vertex-facts for $v_i$ before terminating at $q_i$; (2) Replace
the single transition in the final agent with a $|V|$-length chain of
transitions that are enabled by the individual vertex-facts in $G$ before
terminating in $q_1$ and the final exchange of the completion-fact; (3)
make the move fact the initial fact-set for the player; and (4) set
$t = (k \times 2|V|) + |V| = (2k + 1)|V|$. The proof of correctness is
a modification of that given in Lemma \ref{LemRedAPEDS1}. Note that in the
instance of APE described above, $i_A = i_I = f_G =  1$, $f_I = |I| = 2$, $i_G = 0$, 
and $|A| = k + 1$.
\end{IEEEproof}

\vspace*{0.06in}

\begin{lemma}
{\sc Clique} polynomial-time many-one reduces to APE such that in the constructed instance
of APE, $i_A = i_I = 1$, $i_I = f_I = 2$, $u_G = 1$, and $f_G = 0$, and $|A|$, $f_P$, and $t$ 
are all functions of $k$ in the given instance of {\sc Clique}.
%
\label{LemRedAPECli1}
\end{lemma}

\begin{IEEEproof}
Given an instance $\langle G = (V,E), k\rangle$ of {\sc Clique},
construct an instance of APE consisting of two groups of $k$ and
$k(k - 1)/2$ agents, respectively. The agents in the first group are
the vertex-selection agents from Lemma \ref{LemRedAPEDS1} modified so
that agent $i$ exchanges vertex-item $v$ for vertex/position-fact
$v/i$. Each of the agents in the second group corresponds to a 
distinct pair $i, j$, $1 \leq i < j \leq k$ which checks if the 
vertices selected in positions $i$ and $j$ have an edge between them in
$G$. For the $l$th pair, $ 1 \leq l \leq k(k - 1)/2$, this is done using
two states $q_0$ and $q_1$ and $2|E|$ transition between $q_0$
and $q_1$ which, for each edge $(u,v) \in E$, trade items $u/i, v/j$
($v/i, u/j$) and fact $echk_{(l - 1)}$ for  
items $u/i, v/j$ ($v/i, u/j$) and fact $echk_l$, respectively. Each
vertex-selection agent $i$ starts with no items and the entire
vertex/position $i$-fact-set, each edge-check agent $l$ starts with no
items and edge-check fact $echk_l$, and the player starts with the
entire vertex-item-set for $G$ and edge-check fact $echk_0$. Finally,
the goal is $c_{k(k-1)/2}$ and $t = k + k(k-1)/2$.
Note that the instance of APE described
above can be constructed in time polynomial in the size of the given instance
of {\sc Clique}. 

If there is a clique of size at $k$ in the given instance of
{\sc Clique}, the player 
can exchange the vertices in that clique with the
vertex/position agents in any order to obtain a ``sequence'' of
vertex/position facts that will satisfy the edge-check agents and hence
achieve the goal. Conversely, as the player can interact with each of the
vertex-selection agents at most once to trade a vertex-item for its associated
vertex/position fact, any set of at most $k + k(k-1)/2$ 
interactions between the player and the agents that achieves the goal in
the constructed instance of APE must
correspond to a set of $k$ vertices that form a clique in $G$.
 
To complete the proof, note that in the constructed instance of APE,
$i_A = 1$, $i_I = f_I = 2$, $i_G = 0$, $f_G = 1$, and $|A| = k + k(k-1)/2$, 
$f_P = k(k-1)/2 + 1$, and $t = k + k(k-1)/2$.
\end{IEEEproof}

\vspace*{0.06in}

\begin{lemma}
{\sc Clique} polynomial-time many-one reduces to APE such that in the constructed instance
of APE, $|A| = 1$, $i_I = 1$, $f_I = 2$, $i_0 = 1$, $f_G = 1$, and 
$|Q|$, $f_P$, and $t$ are
all functions of $k$ in the given instance of {\sc Clique}.
%
\label{LemRedAPECli2}
\end{lemma}

\begin{IEEEproof} [Proof (sketch)]
Note that all of the agents in the reduction in Lemma
\ref{LemRedAPECli1} can be chained together in a single agent
consisting of a chain of $1 + k + k(k-1)/2$ states, and that all
edge-check facts except the last can be eliminated as they are no 
longer necessary, {\em e.g.}, the state $q_1$ for what was originally 
the $k(k-1)/2$st edge-check agent can only be reached if all other 
edge-checks are satisfied. The goal and value of $t$ are unchanged. 
The proof of correctness of this reduction is a
modification of that given in Lemma \ref{LemRedAPECli1}. Note
that in the instance of APE described above, $|A| = 1$, $i_I = 1$,
$f_I = 2$, $i_G = 0$, $f_G = 1$ $|Q| = 1 + k + k(k-1)/2$, $f_P = k$, and
$t = k + k(k-1)/2$.
\end{IEEEproof}

\vspace*{0.06in}

\noindent
Observe that setting $t$ to any specified value is actually unnecessary for 
the reductions in Lemmas \ref{LemRedAPENTMC} --
\ref{LemRedAPECli2} to work.

%\vspace*{0.1in}
\newpage

\noindent
{\bf Result A} {\em APE is $NP$-hard when $|A| = 1$.}

\vspace*{0.08in}

\begin{IEEEproof}
Follows from the $NP$-hardness of {\sc Clique} and the reduction in
Lemma \ref{LemRedAPECli2}.
\end{IEEEproof}

\vspace*{0.1in}

\noindent
{\bf Result B} 
{\em APE is fp-intractable for the parameter-set $\{i_A, f_A, i_I, f_I, |A|, |A|, i_P, f_P, t, i_G, f_G\}$.}

\vspace*{0.08in}

\begin{IEEEproof}
Follows from the $W[1]$-hardness of NTMC for parameter-set $\{k\}$
\cite{CCDF97} and the reductions from NTMC to APE given in Lemma \ref{LemRedAPENTMC}.
\end{IEEEproof}

\vspace*{0.1in}

\noindent
{\bf Result C} 
{\em APE is fp-intractable for the parameter-set $\{|A|, i_A, i_I, t, i_G, f_G\}$.}

\vspace*{0.08in}

\begin{IEEEproof}
Follows from the $W[1]$-hardness of {\sc Dominating Set} for parameter-set $\{k\}$
\cite{DF13} and the reductions from {\sc Dominating Set} to APE given in Lemma \ref{LemRedAPEDS1}.
\end{IEEEproof}

\vspace*{0.1in}

\noindent
{\bf Result D} 
{\em APE is fp-intractable for the parameter-set $\{|A|, i_A, i_I, f_I, |I|, i_G, f_G\}$.}

\vspace*{0.08in}

\begin{IEEEproof}
Follows from the $W[1]$-hardness of {\sc Dominating Set} for parameter-set $\{k\}$
\cite{DF13} and the reductions from {\sc Dominating Set} to APE given in Lemma \ref{LemRedAPEDS2}.
\end{IEEEproof}

\vspace*{0.1in}

\noindent
{\bf Result E} 
{\em APE is fp-intractable for the parameter-set $\{|A|, i_A, i_I, f_I, f_P, t, i_G. f_G\}$.}

\vspace*{0.08in}

\begin{IEEEproof}
Follows from the $W[1]$-hardness of {\sc Clique} for parameter-set $\{k\}$
\cite{DF13} and the reductions from {\sc Clique} to APE given in Lemma \ref{LemRedAPECli1}.
\end{IEEEproof}

\vspace*{0.1in}

\noindent
{\bf Result F} 
{\em APE is fp-intractable for the parameter-set $\{|A|, i_I, f_I, |Q|, f_P, t, i_G, f_G\}$.}

\vspace*{0.08in}

\begin{IEEEproof}
Follows from the $W[1]$-hardness of {\sc Clique} for parameter-set $\{k\}$
\cite{DF13} and the reductions from {\sc Clique} to APE given in Lemma \ref{LemRedAPECli2}.
\end{IEEEproof}

\vspace*{0.1in}

\noindent
{\bf Result G} 
{\em APE is fp-tractable for the parameter-set $\|A|, |I|, t\}$.}

\vspace*{0.08in}

\begin{IEEEproof}
Consider the gamespace search tree whose nodes encode the current item- and
fact-sets of each agent and the player as well as the current state of each
agent. Observe that there are at most $|A| \times |I|$ possibilities for
interactions relative to each node (as each agent's current state has
at most $|I|$ enabled transitions outwards from that state). As we
require that the goal be reachable within $t$ agent-player interactions, the 
tree has at most $(|A||I|)^t$ nodes that must be considered. As each node
can be generated and evaluated in time polynomial in the size of the
given instance of APE, the above is an algorithm for APE whose
runtime is fp-tractable for parameter-set $\{|A|, |I|, t\}$. 
\end{IEEEproof}

% that's all folks
\end{document}