$\langle q_{F1},fval(fq_{X},\geq,1),*,stay,q_{F1}\rangle$ where $q_{A}$ is the
accepting state of $M$. The TM $M$ underlying the single FSR in $T$ is
deterministic in the classical automata-theoretic sense [52] and thus has at
most one transition enabled at any time; hence, the operation of that FSR in
$E$ is deterministic in the sense defined in this paper. Note that this
instance of TeamEnvVerSF can be constructed in time polynomial in the size of
the given instance of CDTMC.

Let us now prove that this reduction is correct, in that the answer for the
given instance of CDTMC is “Yes” if and only if the answer for the constructed
instance of TeamEnvVerSF is “Yes”. If $M$ accepts $x$ using at most $k$ tape
squares, the single FSR in $T$ starting from $p_{I}$ (as it is based on the
same transitions as $M$) will eventually enter state $q_{A}$ sitting on one of
the first $k$ squares of $E$. The extra transitions described above will then
ensure that the FSR proceeds to the eastmost square of $E$, i.e., $p_{X}$,
replaces $s_{F1}$ with $s_{X}$, i.e., $X$, and then stays there. Conversely,
if the single FSR in $T$ can proceed from $p_{I}$ to create $X$ at $p_{X}$
then at some point it must have entered $q_{A}$ (as only the extra transitions
added to $M$ originating from $q_{A}$ could have moved eastwards over the
second-last square in $E$ to reach $p_{X}$), which would imply that $M$
accepts $x$.

Given that CDTMC is $PSPACE$-complete [19, Problem Al3], the reduction above
establishes that TeamEnvVerSF is $PSPACE$-hard when $|T|=1$. The result then
follows from the fact that $NP\subseteq PSPACE$,

###  A.2 Proofs for Controller Design by Library Selection

Result B.ST.1 (Modified from [29, Result B]):

If ContDesLSSTfast is polynomial-time exact solvable then $P=NP$.

Proof: Consider the following reduction from Dominating set to
ContDesLSST${}^{fast}_{D}$, based on the reduction from Dominating set to
ContDes${}^{fast}_{D}$ given in Lemma 5 in the supplementary materials of [16]
as modified in the proof of Result B in the supplementary materials of [29].
Given an instance $\langle G=(V,E),k\rangle$ of Dominating Set, construct an
instance $\langle
E^{\prime},E^{\prime}_{T},|T|,p_{I},X,p_{X},|L|,r,|Q|,d\rangle$ of
ContDesLSST${}^{fast}_{D}$ as follows: Let $E^{\prime}$ be the environment
constructed in Lemma 5 in the supplementary materials of [16] with the
northwest $e_{N}$-based and SG1 subgrids removed, $E^{\prime}_{T}$ be the
version of $E_{T}$ in that same lemma with $e_{N}$ and $e_{E}$ replaced by
$e_{B}$ and $e_{F2}$ replaced by $e_{X}$, $p^{\prime}_{I}=E^{\prime}_{1,1}$,
$X$ be a single square of type $e_{X}$ at
$p_{X}=E^{\prime}_{|V|+1,|V|^{2}+1}$, $L=\\{\langle
q,enval(y,(0,0)),*,goEast,q^{\prime}\rangle~{}|~{}y\in\\{e_{1},\ldots,e_{|V|}\\}\\}\cup\\{\langle
q,enval(e_{F1},(0,0)),$ $enmod(e_{X},(0,0)),$ $stay,q^{\prime}\rangle,\langle
q,*,*,goNorth,q^{\prime}\rangle\\}$, $|T|=|Q|=1$, $r=0$, and $d=k+2$. This
instance of ContDesLSST${}^{fast}_{D}$ can be constructed in time polynomial
in the size of the given instance of Dominating Set.

Observe that the use of $L$ means that we no longer need subgrid SG1 and the
restrictions on $|f|$ posited in Lemma 5 above to force the created FSR to
have $k$ east-moving transitions corresponding to a candidate dominating set
of $k$ distinct vertices in $G$. Hence, by slight simplifications and
modifications of the proof of correctness of the reduction in Lemma 5 above,
it can be shown that there is a dominating set of size $k$ in graph $G$ in the
given instance of Dominating set if and only if there is an FSR with the
structure specified in the constructed instance of ContDesLSST${}^{fast}_{D}$
such that (1) $X$ can be constructed at $p_{X}$ if this FSR starts at $p_{I}$
and (2) the $k+2$ transitions in this FSR are $k$ east-moving transitions from
$L$ whose activation-formula predicates correspond to the vertices in a
dominating set of size $k$ in $G$, and the final two transitions in $L$. As
each transition in this FSR has an activation-formula consisting of either $*$
or a single predicate evaluating if that square has a particular square-type,
there can be at most one transition enabled at a time and the operation of
this FSR in $E^{\prime}$ is deterministic. As the single robot in $T$ can only
move north or east and does one of either in each move, the number of
transitions executed in this construction task is the Manhattan distance from
$p_{I}$ to $p_{X}$ in $E$. This distance is
$(|V|+1)+(|V|^{2}+1)<|E|=c_{1}|E|^{c_{2}}<c_{1}(|E|+|Q|)^{c_{2}}$ when
$c_{1}=c+2=1$ , which means that the construction task is
$(c_{1},c_{2})$-completable when $c_{1}=c_{2}=1$.

As Dominating set is $NP$-complete [19, Problem GT2], the reduction above
establishes that ContDesLSST${}^{fast}_{D}$ is $NP$-hard; our result then
follows from Lemma 3. To complete the proof, note that in the constructed
instance of ContDesLSST${}^{fast}_{D}$, $|T|=h=|Q|=|f|=|X|=1$, $r=0$, and
$d=k+2$.

Result B.SF.1:

If ContDesLSSFfast is polynomial-time exact solvable then $P=NP$.

Proof: As $|T|=1$ and $r=0$ in the instance of ContDesLSST${}^{fast}_{D}$
constructed by the reduction in the proof of Result B.ST.1, we can use the
techniques illustrated in the proof of Result A.SF.1 to simulate all square-
types in $E^{\prime}_{T}$ with point-fields that have source-value and delay 1
and replace the visual sensing robot in $T$ with an equivalent scalar-field
sensing robot. The result then follows by appropriate modifications to the
proof of Result B.ST.1. To complete the proof, note that in the constructed
instance of ContDesLSSF${}^{fast}_{D}$, $|T|=h=|Q|=|f|=|X|=1$ and $d=k+2$.

Result B.ST.2:

If $\langle|T|,h,|Q|,d,|f|,r,|X|\rangle$-ContDesLSSTfast is fp-tractable then
$FPT=W[1]$.

Proof: Follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating set
[20], the reduction from Dominating set to ContDesLSST${}^{fast}_{D}$ in the
proof of Result B.ST.1, the fact that $W[1]\subseteq W[2]$, and Lemma 4.

Result B.ST.3:

If $\langle|T|,h,|Q|,d,|f|,|E_{T}|,|X|\rangle$-ContDesLSSTfast is fp-tractable
then $FPT=W[1]$.

Proof: Consider the following reduction from Dominating set to
ContDesLSST${}^{fast}_{D}$, based on the reduction from Dominating set to
ContDesLSST${}^{fast}_{D}$ given in the proof of Result B.ST.1. Given an
instance $\langle G=(V,E),k\rangle$ of Dominating Set, construct an instance
$\langle E^{\prime},E^{\prime}_{T},|T|,p_{I},X,p_{X},|L|,r,$ $|Q|,d\rangle$ of
ContDesLSST${}^{fast}_{D}$ as follows: Let $E^{\prime}$ be the environment
constructed in the proof of Result B.ST.1 with each symbol-entry $x$ in each
vertex-neighbourhood column replaced by (1) a row of $|V|+1$ squares in which
the $((|V|-i)+1)$st square has type $e_{V}$, the $(|V|+1)$st square has type
$e_{M}$, and all other squares have type $e_{B}$ if $x=e_{Vi}$, and (2) a row
of $|V|+1$ squares of type $e_{B}$ if $x=e_{B}$ (see Figure 5(a) in the main
text), $E^{\prime}_{T}=\\{e_{B},e_{M},e_{F1},e_{robot},e_{X}\\}$,
$p^{\prime}_{I}=E^{\prime}_{1,1}$, $X$ be a single square of type $e_{X}$ at
$p_{X}=E^{\prime}_{2|V|+1,|V|^{2}+1}$, $L=\\{\langle
q,enval(e_{M},(0,0))~{}\rm{and}~{}enval(e_{V},(0,-i)),*,$
$goEast,q^{\prime}\rangle~{}|~{}1\leq i\leq|V|\\}~{}\cup~{}\\{\langle
q,enval(e_{F1},(0,0)),enmod(e_{X},(0,0)),stay,q^{\prime}\rangle,$ $\langle
q,*,*,goNorth,q^{\prime}\rangle\\}$, $|T|=|Q|=1$, $r=|V|$, and $d=k+2$. This
instance of ContDesLSST${}^{fast}_{D}$ can be constructed in time polynomial
in the size of the given instance of Dominating Set. By slight modifications
to the proof of correctness of the reduction in the proof of Result B.ST.1, it
can be shown that there is a dominating set of size $k$ in graph $G$ in the
given instance of Dominating set if and only if there is an FSR with the
structure specified in the constructed instance of ContDesLSST${}^{fast}_{D}$
such that (1) $X$ can be constructed at $p_{X}$ if this FSR starts at $p_{I}$
and (2) the $k+2$ transitions in this FSR are $k$ east-moving transitions from
$L$ whose activation-formula predicates correspond to the vertices in a
dominating set of size $k$ in $G$, and the final two transitions in $L$. By
the same arguments as those given in the proof of Result B.ST.1, the operation
of this FSR in $E^{\prime}$ is deterministic and the construction task is
$(c_{1},c_{2})$-completable when $c_{1}=c_{2}=1$.

The result follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating
set [20], the reduction above, the fact that $W[1]\subseteq W[2]$, and Lemma
4. To complete the proof, note that in the constructed instance of
ContDesLSST${}^{fast}_{D}$, $|T|=h=|Q|=|X|=1$, $|f|=3$, $|E_{T}|=5$, and
$d=k+2$.

Result B.SF.2:

If $\langle|T|,h,|Q|,d,|f|,|X|\rangle$-ContDesLSSFfast is fp-tractable then
$FPT=W[1]$.

Proof: Follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating set
[20], the reduction from Dominating set to ContDesLSST${}^{fast}_{D}$ in the
proof of Result B.SF.1, the fact that $W[1]\subseteq W[2]$, and Lemma 4.

Result B.SF.3:

If $\langle|T|,h,|Q|,|f|,|q_{E}|,|X|\rangle$-ContDesLSSFfast is fp-tractable
then $P=NP$.

Proof: If we replace Dominating set with Dominating setPD3 in the reduction in
the proof of Result B.SF.1, as each vertex in $G$ has degree 3, each vertex
point-field can occur at most four times (in the vertex-neighbourhood columns
of that vertex and its three adjacent vertices) and $|q_{E}|=4$. The result
then follows from the $NP$-hardness of Dominating setPD3 [19, Problem GT2] and
Lemma 5.

Result B.SF.4:

If $\langle|T|,h,|Q|,d,|f|,|S|,|X|\rangle$-ContDesLSSFfast is fp-tractable
then $FPT=W[1]$.

Proof: Consider the following reduction from Dominating set to
ContDesLSSF${}^{fast}_{D}$, based on the reduction from Dominating set to
ContDesLSST${}^{fast}_{D}$ given in the proof of Result B.ST.3. Given an
instance $\langle G=(V,E),k\rangle$ of Dominating Set, construct an instance
$\langle E^{\prime},S,|T|,p_{I},X,p_{X},|L|,r,|Q|,$ $d\rangle$ of
ContDesLSSF${}^{fast}_{D}$ as follows: Let $E^{\prime}$ be the environment
constructed in the proof of Result B.ST.3 with the following modifications:
(1) each row is now separated by $2|V|$ blank rows; (2) each marker-symbol
$e_{M}$ is replaced by a point-field $s_{M}$ with source-value 1 and decay 1;
(3) each vertex-symbol is replaced by a point-field $s_{V}$ with source-value
$|V|+1$ and decay 1; and (4) symbol $e_{F1}$ is replaced by a point-field
$s_{F1}$ with source-value and decay 1 (see Figure 5(c) in the main text). Let
$S=\\{s_{M},s_{V},s_{F1},s_{robot},s_{X}\\}$,
$p^{\prime}_{I}=E^{\prime}_{1,1}$, $X$ be a single point-field of type $s_{X}$
at $p_{X}=E^{\prime}_{2|V|+1,2|V|^{3}+1}$, $L=\\{\langle
q,fval(fq_{M},\geq,1.0)~{}\rm{and}~{}fval(fq_{V},=,(|V|+1)-i),*,goEast,q^{\prime}\rangle~{}|~{}1\leq
i\leq|V|\\}~{}\cup~{}\\{\langle
q,fval(e_{F1},\geq,1.0),fmod(s_{X},(0,0)),stay,q^{\prime}\rangle,\langle
q,*,*,goNorth,q^{\prime}\rangle\\}$, $|T|=|Q|=1$, and $d=k+2$. This instance
of ContDesLSSF${}^{fast}_{D}$ can be constructed in time polynomial in the
size of the given instance of Dominating Set. By slight modifications to the
proof of correctness of the reduction in the proof of Result B.ST.3, it can be
shown that there is a dominating set of size $k$ in graph $G$ in the given
instance of Dominating set if and only if there is an FSR with the structure
specified in the constructed instance of ContDesLSSF${}^{fast}_{D}$ such that
(1) $X$ can be constructed at $p_{X}$ if this FSR starts at $p_{I}$ and (2)
the $k$ east-moving transitions in this FSR correspond to the vertices in a
dominating set of size $k$ in $G$, and the final two transitions in $L$. By
the same arguments as those given in the proof of Result B.ST.1, the operation
of this FSR in $E^{\prime}$ is deterministic and the construction task is
$(c_{1},c_{2})$-completable when $c_{1}=c_{2}=1$.

The result follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating
set [20], the reduction above, the fact that $W[1]\subseteq W[2]$, and Lemma
4. To complete the proof, note that in the constructed instance of
ContDesLSSF${}^{fast}_{D}$, $|T|=h=|Q|=|X|=1$, $|f|=3$, $|S|=5$, and $d=k+2$.

Result B.ST.4:

$\langle|Q|,|L|\rangle$-ContDesLSSTfast is fp-tractable.

Proof: Consider the algorithm that generates all possible controllers and then
for each controller $c$ checks in polynomial time if a team $T$ composed of
$c$ started at $p_{I}$ will create $X$ at $p_{X}$. The number of controllers
is upper-bounded by $|L|^{d|Q|}|Q|^{d|Q|}$, which, as $c$ is deterministic and
hence $d\leq|L|$, is in turn upper-bounded by a function of $|Q|$ and $|L|$.
As the construction task is assumed to be $(c_{1},c_{2})$-completable, the
checking of the team with any such controller can be done in
$c_{1}(|E|+|Q|)^{c_{2}}$ multiplied by some polynomial of the input size
(i.e., the time required to simulate $T$ in $E$ for one timestep), completing
the proof.

Result B.SF.5:

$\langle|Q|,|L|\rangle$-ContDesLSSFfast is fp-tractable.

Proof: Follows from the algorithm in the proof of Result B.ST.4.

###  A.3 Proofs for Team Design by Library Selection

Result C.ST.4:

If $\langle|T|,h,|Q|,d,r,|X|\rangle$-TeamDesLSSTfast is fp-tractable then
$FPT=W[1]$.

Proof: Modify the reduction in the proof of Lemma A.2 in the appendix of [14]
such that in transition-groups (5), (6), and (7) for vertex neighborhood
robots, instead of having potentially $|V|$ transitions in each group, have a
single transition whose transition formula ORs together all of the predicates
of the form $enval(e_{vj},(0,-1))$ to create a parenthesis-enclosed subformula
that is then ANDed with the other predicates in each existing transition
trigger formula. Note that this modified reduction still runs in time
polynomial in the size of the given instance of Dominating set; moreover, this
reduction is correct by slight modifications of the arguments given for the
proof of correctness of the reduction in the proof of Lemma A.2. The result
then follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating set
[20], the modified reduction above, the fact that $W[1]\subseteq W[2]$, and
Lemma 4. To complete the proof, note that in the constructed instance of
TeamDesLSST${}^{fast}_{D}$, $r=|X|=1$, $|Q|=3$, $d=7$, and $|T|=h=k+1$.

Result C.ST.5:

If $\langle|T|,h,|Q|,d,|E_{T}|,|X|\rangle$-TeamDesLSSTfast is fp-tractable
then $FPT=W[1]$.

Proof: Modify the reduction in the proof of Lemma A.3 in the appendix of [14]
such that in transition-groups (5), (6), and (7) for vertex neighborhood
robots, instead of having potentially $|V|$ transitions in each group, have a
single transition whose transition formula ORs together all of the subformulas
used to recognize $v_{i}$, $1\leq i\leq|V|$, to create a parenthesis-enclosed
subformula that is then ANDed with the other predicates in each existing
transition trigger formula. Note that this modified reduction still runs in
time polynomial in the size of the given instance of Dominating set; moreover,
this reduction is correct by slight modifications of the arguments given for
the proof of correctness of the reduction in the proof of Lemma A.3. The
result then follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating
set [20], the modified reduction above, the fact that $W[1]\subseteq W[2]$,
and Lemma 4. To complete the proof, note that in the constructed instance of
TeamDesLSST${}^{fast}_{D}$, $|X|=1$, $|Q|=3$, $d=7$, $|E_{T}|=13$, and
$|T|=h=k+1$.

Result C.SF.1

[18, Result A.1]: TeamDesLSSFfast is exact polynomial-time solvable when
$h=1$.

Proof: Follows from the algorithm in the proof of Result A in [14].

Result C.SF.2

[18, Result A.2]: If TeamDesLSSFfast is exact polynomial-time solvable when
$h>1$ then $P=NP$.

Proof: Consider the following reduction from Dominating set to
TeamDesLSSF${}^{fast}_{D}$, based on the reduction from Dominating set to
DesCon${}^{D}_{syn}$ given in the proof of Lemma A.2 in [14]. Given an
instance $\langle G=(V,E),k\rangle$ of Dominating set, construct an instance
$\langle E^{\prime},S,|T|,L,E_{I},X,p_{X}\rangle$ of
TeamDesLSSF${}^{fast}_{D}$ as follows: Let $E^{\prime}$ be a $(|V|+8)\times 5$
grid containing point-fields from the set
$S=\\{s_{N},s_{S},s_{E},s_{W},s_{v1},s_{v2},\ldots
s_{v|V|},s_{T},s_{M1},s_{M2},s_{M3},s_{robot},s_{X}\\}$, each with source-
value 1 and decay 0.5, as follows:

  * •

$E^{\prime}_{1,2}=s_{E}$.

  * •

$E^{\prime}_{|V|+8,2}=E^{\prime}_{|V|+8,3}=s_{N}$.

  * •

For $3\leq i\leq(|V|+7)$, $E^{\prime}_{i,5}=s_{W}$.

  * •

$E^{\prime}_{1,3}=E^{\prime}_{1,4}=s_{S}$.

  * •

$E^{\prime}_{3,3}=s_{M1}$.

  * •

$E^{\prime}_{|V|+4,3}=s_{M2}$.

  * •

$E^{\prime}_{|V|+5,3}=s_{T}$.

  * •

$E^{\prime}_{|V|+6,3}=s_{M3}$.

  * •

For $1\leq i\leq|V|$, $E^{\prime}_{i+3,1}=s_{vi}$.

An example environment $E^{\prime}$ when $|V|=5$ and $k=2$ is shown in Figure
1(a) in the main text. Let $|T|=k+1$, $E_{I}=\\{E^{\prime}_{j,4}~{}|~{}3\leq
j\leq k+3\\}$, and FSR library $L=\\{r_{v1},r_{v2},\ldots,r_{v|V|},r_{chk}\\}$
consist of $|V|$ vertex neighbourhood robots $r_{vi}$, $1\leq i\leq|V|$, and a
checker robot $r_{chk}$ that are specified as follows:

  * •

Vertex neighbourhood robot: Each vertex neighbourhood robot $r_{vi}$ is based
on a single state $q_{0}$ and has the following transitions:

    1. 1.

$\langle q_{0},(fval(fq_{E},=,0.5)$ or $fval(fq_{M1},=,0.5)$ or
$fval(fq_{M2},=,0.5)$ or $fval(fq_{T},=,0.5)$ or $fval(fq_{M3},=,0.5)$ or
$fval(fq_{X},=,0.5))$ and $(fval(fq_{N},=,0.0)$ and $fval(fq_{S},=,0.0)$ and
$fval(fq_{W},=,0.0))$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),*,goEast,q_{0}\rangle$.

    2. 2.

$\langle q_{0},fval(fq_{N},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,North)),$ $*,goNorth,q_{0}\rangle$.

    3. 3.

$\langle q_{0},fval(fq_{W},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,West)),$ $*,goWest,q_{0}\rangle$.

    4. 4.

$\langle q_{0},fval(fq_{S},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,South)),$ $*,goSouth,q_{0}\rangle$.

    5. 5.

For $v_{j}\in N_{C}(v_{i})$, $\langle q_{0},fval(fq_{vj},=,0.5)$ and
$fval(s_{X},=,0.0)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),fmod(s_{X},(0,1)),goEast,q_{0}\rangle$.

    6. 6.

For $v_{j}\in N_{C}(v_{i})$, $\langle q_{0},fval(fq_{vj},=,0.5)$ and
$fval(s_{X},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),*,goEast,q_{0}\rangle$.

    7. 7.

For $v_{j}\not\in N_{C}(v_{i})$, $\langle q_{0},(fval(fq_{vj},=,0.5)$ and
$(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),*,goEast,q_{0}\rangle$.

The transitions in (2), (3), and (4) allow $r_{vi}$ to progress northwards
along the west, westwards along the north, and southwards along the east sides
of the movement-track, respectively. All remaining transitions cover movement
on the south side of the movement-track. The transitions in (5) allow $r_{vi}$
to put a point-field of type $s_{X}$ in the scaffolding to its immediate north
and progress eastwards if there is a point-field to its immediate south whose
type corresponds to a vertex in the complete neighbourhood of $v_{i}$ in $G$,
while the transitions in (6) and (7) allow eastward progression if either such
an $s_{X}$ is already in place or the type of the point-field to the immediate
south corresponds to a vertex that is not in the complete neighbourhood of
$v_{i}$ in $G$. Finally, transition (1) allows $r_{vi}$ to progress eastwards
over all remaining positions on the south side of the movement-track.

  * •

Checker robot: The checker robot $r_{chk}$ is based on three states $q_{0}$,
$q_{1}$, and $q_{2}$ and has the following transitions:

    1. 1.

$\langle q_{0},fval(fq_{E},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),$ $*,goEast,q_{0}\rangle$.

    2. 2.

$\langle q_{0},fval(fq_{N},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,North)),$ $*,$ $goNorth,q_{0}\rangle$.

    3. 3.

$\langle q_{0},fval(fq_{W},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,West)),$ $*,$ $goWest,q_{0}\rangle$.

    4. 4.

$\langle q_{0},fval(fq_{S},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,South)),$ $*,$ $goSouth,q_{0}\rangle$.

    5. 5.

$\langle q_{0},fval(fq_{M1},=,0.5)$ and $(fval(fq_{S},=,0.0)$ and
$fval(fq_{W},=,0.0))$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),*,goEast,q_{1}\rangle$.

    6. 6.

$\langle q_{1},fval(fq_{X},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),$ $*,goEast,q_{1}\rangle$.

    7. 7.

$\langle q_{1},fval(fq_{M2},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),$ $*,goEast,q_{1}\rangle$.

    8. 8.

$\langle q_{1},fval(fq_{T},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),$ $fmod(s_{X},(0,1)),goEast,q_{1}\rangle$.

    9. 9.

$\langle q_{1},fval(fq_{M3},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),$ $*,goEast,q_{0}\rangle$.

    10. 10.

$\langle q_{1},fval(fq_{X},=,0.0)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),$ $*,goEast,q_{2}\rangle$.

    11. 11.

$\langle q_{2},(fval(fq_{X},=,0.5)$ or $fval(fq_{X},=,0.0)$ or
$fval(fq_{M2},=,0.5)$ or $fval(fq_{T},=,0.5))$ and
$(fval(fq_{robot},\leq,1.5)$ and $fgrd(fq_{robot},>,East)),$
$*,goEast,q_{2}\rangle$.

    12. 12.

$\langle q_{2},fval(fq_{M3},=,0.5)$ and $(fval(fq_{robot},\leq,1.5)$ and
$fgrd(fq_{robot},>,East)),$ $*,goEast,q_{0}\rangle$.

The transitions in (2), (3), and (4) allow $r_{chk}$ to progress northwards
along the west, westwards along the north, and southwards along the east sides
of the movement-track, respectively. All of this movement is done when
$r_{chk}$ is in state $q_{0}$. All remaining transitions cover movement on the
south side of the movement-track. On entering the south side, $r_{chk}$ enters
state $q_{1}$ (transition (5)) and remains there if the scaffolding has been
completely filled in by the vertex neighbourhood robots (transitions in
(6–7)). This then allows $r_{chk}$ to create $X$ at $p_{X}$ (transition (8))
and then return to state $q_{0}$ (transition (9)). If at any point $r_{chk}$
finds that part of the scaffolding has not been filled in (transition (10)),
it enters state $q_{2}$, skips over the remainder of the scaffolding
(transition (11)) and then returns to state $q_{0}$ (transition (12)).
Finally, transition (1) allows $r_{chk}$ to progress eastwards from the
westmost square on the south side of the movement track.

Note the use in all of the transitions described above of the robot collision-
avoidance formula $(fval(fq_{robot},\leq,1,5)$ and $fgrd(fq_{robot},>,dir))$
derived in Section 3.4 that allows moves in direction $dir$ along the
movement-track. Finally, let $X$ be a single point-field of type $s_{X}$ at
position $p_{X}=E^{\prime}_{|V|+5,3}$. Note that this instance of
TeamDesLSSF${}^{fast}_{D}$ can be constructed in time polynomial in the size
of the given instance of Dominating set.

By slight modifications to the proof of correctness of the reduction in the
proof of Lemma A.2 in [14], it can be shown that there is a dominating set of
size at most $k$ in $G$ in the given instance of Dominating set if and only if
there is robot team $T$ consisting of $k+1$ robots from $L$ in the constructed
instance of TeamDesLSSF${}^{fast}_{D}$ such that, when started at any
positioning of the team members in $E_{I}$, $T$ constructs $X$ at $p_{X}$. By
the same arguments as those given in the proof of Lemma A.2 in [14], the
operation of $T$ in $E^{\prime}$ is deterministic. With respect to
$(c_{1},c_{2})$-completability, observe that in the worst case, all vertex
neighbourhood robots have to pass below $s_{M1}$ and $s_{M2}$ on the south
side of the movement-track (in order to fill in all point-fields of type
$s_{X}$ in the scaffolding) and then the checker robot must similarly pass
below $s_{M1}$ and $s_{M2}$ on the south side of the movement-track (to ensure
that all positions in the scaffolding have been filled in). As the positions
of the members of $T$ in $E_{I}$ are not guaranteed, this means that all
robots need to progress around the movement-track at most twice relative to
their starting positions. As the movement-track is of length $2|V|+14$ and at
least one robot moves forward in each timestep (as there will always be at
least one robot with a free square in front of it on the movement track that
is not situation (h) in Figure 6 in the main text), this means that in the
worst case at most $2(2|V|+14)(k+1)\leq(4|V|+28)(|V|+1)$ timesteps are
required for $T$ to construct $X$ at $p_{X}$. However, as $|E|=5|V|+40$, when
$c_{1}=1$ and $c_{2}=2$, which means that this construction task is
$(c_{1},c_{2})$-completable wrt $T$ when $c_{1}=1$ and $c_{2}=2$.

The result follows from the $NP$-hardness of Dominating set [19, Problem GT2],
the reduction above, and Lemma 3. To complete the proof, note that in the
constructed instance of TeamDesLSSF${}^{fast}_{D}$, $|X|=1$, $|Q|=3$,
$|f|=27$, and $|T|=h=k+1$.

Result C.SF.3

[18, Result A.3]: If $\langle|T|,h,|Q|,|f|,|X|\rangle$-TeamDesLSSTfast is fp-
tractable then $FPT=W[1]$.

Proof: Follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating set
[20], the reduction from Dominating set to TeamDesLSSF${}^{fast}_{D}$ in the
proof of Result C.SF.2, the fact that $W[1]\subseteq W[2]$, and Lemma 4.

Result C.SF.4

[18, Result A.4]: If $\langle|T|,h,|Q|,d,|X|\rangle$-TeamDesLSSTfast is fp-
tractable then $FPT=W[1]$.

Proof: Modify the reduction in the proof of Result C.SF.2 such that in
transition-groups (5), (6), and (7) for vertex neighborhood robots, instead of
having potentially $|V|$ transitions in each group, have a single transition
whose transition formula ORs together all of the predicates of the form
$fval(fq_{vj},=,0.5)$ to create a parenthesis-enclosed subformula that is then
ANDed with the other three predicates in each existing transition trigger
formula. Note that this modified reduction still runs in time polynomial in
the size of the given instance of Dominating set; moreover, this reduction is
correct by slight modifications of the arguments given for the proof of
correctness of the reduction in the proof of Result C.SF.2. The result then
follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating set [20],
the modified reduction above, the fact that $W[1]\subseteq W[2]$, and Lemma 4.
To complete the proof, note that in the constructed instance of
TeamDesLSSF${}^{fast}_{D}$, $|X|=1$, $|Q|=3$, $d=7$, and $|T|=h=k+1$.

Result C.SF.5

[18, Result A.5]: If $\langle|T|,h,|Q|,|f|,|S|,|X|\rangle$-TeamDesLSSTfast is
fp-tractable then $FPT=W[1]$.

Proof: Consider the reduction in the proof of Result C.SF.2 relative to the
following modifications:

  1. 1.

Delete all point-fields in the set $\\{s_{vi}~{}|~{}1\leq i\leq|V|\\}$ from
$S$ and add to $S$ point-fields $s_{M}$ and $s_{B}$ with source-value 1 and
decay 0.5 and a point-field $s_{V}$ with source-value $|V|+1$ and decay 1.

  2. 2.

Expand the environment in the north-south direction by $|V|$ squares to
replace each square with point-field $s_{vi}$, $1\leq i\leq|V|$ with a vertex
column consisting of $|V|+1$ squares with a point-field of type $s_{M}$ in the
northmost square of that column and a point-field of type $s_{V}$ $i$ squares
below $s_{M}$ to the south.

  3. 3.

Expand the environment created in (2) above in the east-west direction by
$2|V|$ $(|V|-1)$ squares to place between each pair of adjacent vertex-columns
an additional $2|V|$ blank columns, each consisting of $|V|+1$ squares, in
which the northmost square in the column has a point-field of type $s_{B}$.
The northmost square in the environment above each such column will have a
point-field $s_{W}$.

  4. 4.

Alter the positions of all other point-fields in $E^{\prime}$ and the
positions in $E_{I}$, and $p_{X}$ accordingly given the environment-expansions
in (2) and (3) above.

  5. 5.

In the transition-set of each vertex neighborhood robot, replace the term
$fval(fq_{vi},=0.5)$, $1\leq i\leq|V|$, with the formula $(fval(fq_{M},=,0.5)$
and $fval(fq_{V},$ $=,(|V|+1)-i))$.

  6. 6.

Add the transition $\langle
q_{0},fval(fq_{B},=,0.5),fmod(s_{X},(0,1)),goEast\rangle$ to the transition-
set of each neighbourhood robot.

Modifications (1), (2), and (3) above are analogous to those developed in the
proof of Result B.SF.4 to reduce the size of $S$. Modifications (5) and (6)
are required to make the vertex neighborhood robots fill in the portions of
the central scaffolding above the new blank columns and thus allow the checker
robot to function as in the proof of Result C.SF.2. Note that this instance of
TeamDesLSSF${}^{fast}_{D}$ can be constructed in time polynomial in the size
of the given instance of Dominating set.

By slight modifications to the proof of correctness of the reduction in the
proof of Lemma A.2 in [14], it can be shown that there is a dominating set of
size at most $k$ in $G$ in the given instance of Dominating set if and only if
there is robot team $T$ consisting of $k+1$ robots from $L$ in the constructed
instance of TeamDesLSSF${}^{fast}_{D}$ such that, when started at any
positioning of the team members in $E_{I}$, $T$ constructs $X$ at $p_{X}$. By
the same arguments as those given in the proof of Lemma A.2 in [14], the
operation of $T$ in $E^{\prime}$ is deterministic. With respect to
$(c_{1},c_{2})$-completability, as all robots need to progress around the
movement-track twice relative to their starting positions, the movement-track
is now of length
$2(|V|+2|V|(|V|-1))+14=2(|V|+2|V|^{2}-2|V|)+14=2|V|+4|V|^{2}-2|V|+14=4|V|^{2}+14$,
and at least one robot moves forward in each timestep, this means that in the
worst case at most
$2(4|V|^{2}+14)(k+1)\leq(8|V|^{2}+28)(|V|+1)=8|V|^{3}+8|V|^{2}+28|V|+28$
timesteps are required for $T$ to construct $X$ at $p_{X}$. However, as

$\displaystyle|E|$ $\displaystyle=$ $\displaystyle(|V|+5)(|V|+2|V|(|V|-1)+8)$
$\displaystyle=$ $\displaystyle(|V|+5)(2|V|^{2}-2|V|+8)$ $\displaystyle=$
$\displaystyle(2|V|^{3}-2|V|^{2}+8|V|+10|V|^{2}-10|V|+40)$ $\displaystyle=$
$\displaystyle 2|V|^{3}+8|V|^{2}-2|V|+40$

then

$\displaystyle 8|V|^{3}+8|V|^{2}+28|V|+28$ $\displaystyle<$ $\displaystyle
8|V|^{3}+36|V|^{2}+28$ $\displaystyle<$ $\displaystyle
6(2|V|^{3}+8|V|^{2}-2|V|^{2}+40)$ $\displaystyle=$ $\displaystyle
6(2|V|^{3}+6|V|^{2}+40)$ $\displaystyle=$ $\displaystyle
12|V|^{3}+36|V|^{2}+240$ $\displaystyle<$ $\displaystyle c_{1}|E|^{c_{2}}$
$\displaystyle<$ $\displaystyle c_{1}(|E|+|Q|)^{c_{2}}$

when $c_{1}=6$ and $c_{2}=1$, which means that this construction task is
$(c_{1},c_{2})$-completable wrt $T$ when $c_{1}=6$ and $c_{2}=1$.

The result follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating
set [20], the reduction above, the fact that $W[1]\subseteq W[2]$, and Lemma
4. To complete the proof, note that in the constructed instance of
TeamDesLSSF${}^{fast}_{D}$, $|X|=1$, $|Q|=3$, $|S|=13$, $|f|=31$, and
$|T|=h=k+1$.

Result C.SF.6

[18, Result A.6]: If $\langle|T|,h,|Q|,d,|S|,|X|\rangle$-TeamDesLSSTfast is
fp-tractable then $FPT=W[1]$.

Proof: Modify the reduction in the proof of Result C.SF.5 such that in the
modified transition-groups (5), (6), and (7) for vertex neighborhood robots,
instead of having potentially $|V|$ transitions in each group, have a single
transition whose transition formula ORs together all of the subformulas of the
form $(fval(fq_{M},=,0.5)~{}\rm{and}~{}fval(fq_{V},=(|V|+1)-i))$ to create a
parenthesis-enclosed subformula that is then ANDed with the other three
predicates in each existing transition trigger formula. Note that this
modified reduction still runs in time polynomial in the size of the given
instance of Dominating set; moreover, this reduction is correct by slight
modifications of the arguments given for the proof of correctness of the
reduction in the proof of Result C.SF.5. The result then follows from the
$W[2]$-hardness of $\langle k\rangle$-Dominating set [20], the modified
reduction above, the fact that $W[1]\subseteq W[2]$, and Lemma 4. To complete
the proof, note that in the constructed instance of
TeamDesLSSF${}^{fast}_{D}$, $|X|=1$, $|Q|=3$, $d=7$, $|S|=13$, and
$|T|=h=k+1$.

Result C.SF.7

[18, Result A.7]: $\langle|T|,|L|\rangle$-TeamDesLSSTfast is fp-tractable.

Proof: Follows from the algorithm in the proof of Result G in [14].

###  A.4 Proofs for Environment Design

Result D.SF.1

[18, Result B.1] If EnvDesSFfast is polynomial-time exact solvable then
$P=NP$.

Proof: Consider the following reduction from Dominating set to
EnvDesSF${}^{fast}_{D}$. Given an instance $\langle G=(V,E),k\rangle$ of
Dominating set, construct instance $\langle G^{\prime},S,T,$
$p_{I},X,p_{X}\rangle$ of EnvDesSF${}^{fast}_{D}$ as follows: Let $G^{\prime}$
be a $1\times(|V|+1)$ grid, $S=\\{s_{S},s_{v1},s_{v2},$
$\ldots,s_{v|V|},s_{robot},s_{X}\\}$ be a set of point-fields such that
$s_{S}$ has source-value and decay 1 and $s_{vi}$, $1\leq i\leq|V|$, has
source-value $|V|+1$ and decay 1, and $T$ consist of a single robot $r$ based
on set $Q=\\{q_{0},q_{v0},q_{v1},q_{v2},\ldots,q_{v|V|}\\}$ with the following
transitions:

  1. 1.

$\langle q_{0},fval(fq_{S},=,1.0)),*,stay,q_{v0}\rangle$

  2. 2.

$\\{\langle q_{v(i-1)},fval(fq_{vj},\geq,1.0),*,stay,q_{vi}\rangle~{}|~{}1\leq
i\leq|V|~{}\rm{and}~{}v_{j}\in N_{C}(v_{i})\\}$

  3. 3.

$\langle q_{v|V|},fval(fq_{S},=,1.0),fmod(s_{X},(0,0)),q_{v|V|}\rangle$

Finally, let $p_{I}=E^{\prime}_{1,1}$ and $X$ be a single point-field of type
$s_{X}$ at $p_{X}=E^{\prime}_{1,1}$. Note that this instance of
EnvDesSF${}^{fast}_{D}$ can be constructed in time polynomial in the size of
the given instance of Dominating set.

Let us now prove that this reduction is correct, in that the answer to the
given instance of Dominating set is “Yes” if and only if the answer for the
constructed instance of EnvDesSF${}^{fast}_{D}$ is “Yes”.

  * •

Suppose there is dominating set of size at most $k$ in the given graph $G$.
Let the set $V^{\prime}\subseteq V$ be the vertices in this dominating set; if
$|V^{\prime}|<k$, add an arbitrary set of $k-|V^{\prime}|$ vertices in $G$ to
$V^{\prime}$. Construct an environment $E^{\prime}$ such that square
$E^{\prime}_{1,1}$ contains point-field $s_{S}$ and square
$E^{\prime}_{1,i+1}$, $1\leq i\leq k$, contains the point-field $s_{j}$, where
$v_{j}$ is the $i$th vertex in $V^{\prime}$. In such an environment, observe
that $r$ started at $p_{I}$ will progress from $q_{0}$ to $q_{v|V|}$ and
construct $X$ at $p_{X}$. At any point in the operation of $r$, all enabled
transitions relative to current state $q$ do the same thing, which means that
the operation of $r$ in $E^{\prime}$ is deterministic in the sense described
in Section 2. With respect to $(c_{1},c_{2})$-completability, observe that $r$
needs $|Q|+1$ timesteps to progress from $q_{0}$ to $q_{v|V|}$ and then
construct $X$ at $p_{X}$. As $|Q|+1<c_{1}(|E|+|Q|)^{c_{2}}$ when
$c_{1}=c_{2}=1$, this means that the task of constructing $X$ at $p_{X}$ is
$(c_{1},c_{2})$-completable when $c_{1}=c_{2}=1$.

  * •

Conversely, suppose there is an environment $E^{\prime}$ based on $G^{\prime}$
and $S$ such that robot $r$ started at $p_{I}$ constructs $X$ at $p_{X}$. In
order to progress from $q_{0}$ to $q_{v0}$, $E^{\prime}_{1,1}$ must contain
the point-field $s_{S}$; moreover, for $1\leq i\leq|V|$, by the structure of
the transition-set of $r$, $r$ can only progress from $q_{v(i-1)}$ to $q_{i}$
(and hence eventually trigger the transition from $q_{v|V|}$ that constructs
$X$ at $p_{X}$) if there is a vertex $v$ in the dominating set encoded in
$E^{\prime}$ such that $v\in N_{C}(v_{i})$ in $G$.444 Note that in this case,
a vertex $v$ may appear multiple times in the dominating set encoded in
$E^{\prime}$. This is not a problem here, as (1) the $fval()$ predicates in
the transition trigger formulas in $r$ will still register the presence of $v$
in the encoded candidate solution even if the associated point-fields
interfere to boost the value of $fq_{v}$ at $E^{\prime}_{1,1}$ and (2) the
vertices in the encoded dominating set need not be distinct as we are are only
interested in the presence of a dominating set of size at most $k$ in $G$.
Thus, $r$ started at $p_{I}$ can construct $X$ at $p_{X}$ in $E^{\prime}$ only
if a dominating set of size at most $k$ in $G$ is encoded in the northmost $k$
squares of the first column in $E^{\prime}$.

This proves the correctness of the reduction. The result then follows from the
$NP$-hardness of Dominating set [19, Problem GT2], the reduction above, and
Lemma 3. To complete the proof, note that in the constructed instance of
EnvDesSF${}^{fast}_{D}$, $|T|=h=|f|=|X|=1$ and $|E|=|S_{E}|=|q_{E}|=2(k+1)$.

Result D.SF.2

[18, Result B.2] If
$\langle|T|,h,|f|,|E|,|S_{E}|,|q_{E}|,|X|\rangle$-EnvDesSFfast is fp-tractable
then $FPT=W[1]$.

Proof: Follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating set
[20], the reduction in the proof of Result D.SF.1, the fact that
$W[1]\subseteq W[2]$, and Lemma 4.

Result D.SF.3

[18, Result B.3]: If
$\langle|T|,h,|Q|,d,|E|,|S_{E}|,|q_{E}|,|X|\rangle$-EnvDesSFfast is fp-
tractable then $FPT=W[1]$.

Proof: Modify the reduction in the proof of Result D.SF.1 such that for $1\leq
i\leq|V|$, the set of transitions $\\{\langle
q_{v(i-1)},fval(fq_{vj},\geq,1.0),*,stay,q_{vi}\rangle~{}|~{}v_{j}\in
N_{C}(v_{i})\\}$ in transition-set (2) and the single transitions in sets (1)
and (3) is replaced by a single transition $\langle
q_{0},f,fmod(s_{X},(0,0)),stay,q_{0}\rangle$, where $f$ is the formula AND-ing
the subformulas OR-ing all $fval()$ predicates in the trigger formulas of the
transitions in the sets for the various $v_{i}$ in transition-set (2) and then
AND-ing this with the predicate $fval(fq_{S},=,1.0)$. Note that this modified
reduction still runs in time polynomial in the size of the given instance of
Dominating set; moreover, this reduction is correct by slight modifications of
the arguments given for the proof of correctness of the reduction in the proof
of Result D.SF.1. The result then follows from the $W[2]$-hardness of $\langle
k\rangle$-Dominating set [20], the modified reduction above, the fact that
$W[1]\subseteq W[2]$, and Lemma 4. To complete the proof, note that in the
constructed instance of EnvDesSF${}^{fast}_{D}$, $|T|=h=|Q|=d=|X|=1$ and
$|E|=|S_{E}|=|q_{E}|=2(k+1)$.

Result D.SF.4

[18, Result B.4]: If
$\langle|T|,h,|f|,|S|,|S_{E}|,|q_{E}|,|X|\rangle$-EnvDesSFfast is fp-tractable
then $FPT=W[1]$.

Proof: Consider the following reduction from Dominating set to
EnvDesSF${}^{fast}_{D}$. Given an instance $\langle G=(V,E),k\rangle$ of
Dominating set, construct instance $\langle G^{\prime},S,T,$
$p_{I},X,p_{X}\rangle$ of EnvDesSF${}^{fast}_{D}$ as follows: Let $G^{\prime}$
be a $3\times(|V|+2)$ grid, $S=\\{s_{P},s_{S},s_{N},$
$s_{E},s_{W},s_{L},s_{robot},s_{X}\\}$ be a set of fields such that $s_{P}$,
$s_{S}$, $s_{N}$, $s_{E}$, and $s_{W}$ are all point-fields with source-value
and decay 1 and $s_{L}$ is an edge-field with source-value $|V|+2$ and decay
1, and $T$ consist of a single robot $r$ based on set
$Q=\\{q_{c0},q_{c10},q_{c11}\ldots,q_{c1k},$
$q_{c2},q_{c3},q_{c4}\\}~{}\cup~{}\\{q_{vi0},q_{vi1},\ldots,q_{vi4}~{}|~{}0\leq
i\leq|V|\\}$ with the following transitions:

  1. 1.

$\langle
q_{c0},fval(fq_{N},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0),*,goNorth,q_{c10}\rangle$

  2. 2.

$\\{\langle q_{c1(i-1)},fval(fq_{P},=,1.0),*,goNorth,q_{c1i}\rangle,\langle
q_{c1(i-1)},fval(fq_{P},=,0.0)$
and $fval(fq_{E},=,0.0),*,goNorth,q_{c1(i-1)}\rangle~{}|~{}1\leq i\leq k\\}$

  3. 3.

$\langle
q_{c1k},fval(fq_{E},=,1.0))~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0),*,goEast,q_{c2}\rangle$

  4. 4.

$\langle
q_{c2},fval(fq_{E},=,1.0))~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0),*,goEast,q_{c2}\rangle$

  5. 5.

$\langle
q_{c2},fval(fq_{S},=,1.0))~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0),*,goSouth,q_{c3}\rangle$

  6. 6.

$\langle
q_{c3},fval(fq_{L},<,|V|+2,0)~{}\rm{and}~{}fval(fq_{L},>,1.0),*,goSouth,q_{c3}\rangle$

  7. 7.

$\langle
q_{c3},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0),*,goWest,q_{c4}\rangle$

  8. 8.

$\langle
q_{c4},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0),*,goWest,q_{c4}\rangle$

  9. 9.

$\langle
q_{c4},fval(fq_{N},=,1.0))~{}\rm{and}~{}fval(fq_{L},=,1,0),*,goNorth,q_{v10}\rangle$

  10. 10.

$\\{\langle
q_{v(i-1)0},fval(fq_{P},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,j+1.0),*,goNorth,q_{v(i-1)1}\rangle,$
$\langle
q_{v(i-1)0},fval(fq_{P},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,k+1.0),*,goNorth,q_{v(i-1)0}\rangle,$
$\langle q_{v(i-1)1},fval(fq_{E},=,0.0),*,goNorth,q_{v(i-1)1}\rangle,$
$\langle
q_{v(i-1)0},fval(fq_{P},=,0.0)~{}\rm{and}~{}fval(fq_{E},=,0.0),*,goNorth,q_{v(i-1)0}\rangle$
$~{}|~{}1\leq i\leq|V|,v_{j}\in N_{C}(v_{1}),~{}\rm{and}~{}v_{k}\not\in
N_{C}(v_{i})\\}$

  11. 11.

$\\{\langle
q_{v(i-1)1},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0),*,goEast,$
$q_{v(i-1)2}\rangle,$ $\langle q_{v(i-1)2},$
$fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0),*,goEast,q_{v(i-1)2}\rangle$
$~{}|~{}1\leq i\leq|V|\\}$

  12. 12.

$\\{\langle
q_{v(i-1)2},fval(fq_{S},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0),*,goSouth,q_{v(i-1)3}\rangle$
$~{}|~{}1\leq i\leq|V|\\}$

  13. 13.

$\\{\langle
q_{v(i-1)3},fval(fq_{L},<,|V|+2,0)~{}\rm{and}~{}fval(fq_{L},>,1.0),*,goSouth,q_{v(i-1)3}\rangle$
$~{}|~{}1\leq i\leq|V|\\}$

  14. 14.

$\\{\langle
q_{v(i-1)3},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0),*,goWest,q_{v(i-1)4}\rangle,$
$\langle
q_{v(i-1)4},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0),*,goWest,q_{v(i-1)4}\rangle$
$~{}|~{}1\leq i\leq|V|\\}$

  15. 15.

$\\{\langle
q_{v(i-1)4},fval(fq_{N},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0),*,goNorth,q_{vi0}\rangle$
$~{}|~{}1\leq i<|V|\\}$

  16. 16.

$\langle
q_{v|V|4},fval(fq_{N},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0),fmod(s_{X},(0,0)),stay,q_{v|V|}\rangle$

The transitions in (1)–(9) ensure that the environment $E^{\prime}$ initially
has the proper form, i.e.,

  * •

Square $E^{\prime}_{1,1}$ contains a point-field of type $s_{N}$;

  * •

Squares $E^{\prime}_{1,i}$, $2\leq i\leq|V|+1$, encode a candidate dominating
set consisting of $k$ distinct vertices in $G$ (indicated by point-fields of
type $s_{P}$ at the appropriate positions);

  * •

Squares $E^{\prime}_{1,|V|+2}$ and $E^{\prime}_{2,|V|+2}$ contain point-fields
of type $s_{W}$;

  * •

Square $E^{\prime}_{3,|V|+2}$ contains a point-fields of type $s_{S}$; and

  * •

Squares $E^{\prime}_{2,1}$ and $E^{\prime}_{3,1}$ contain point-fields of type
$s_{W}$.

  * •

The north edge of $E^{\prime}$ has an edge-field $s_{L}$.

Point-fields in other squares can be eliminated by setting $|S_{E}|=k+7$ and
$|q_{E}|=\max(2,k)$. The transitions in (10)–(15) check if the encoded
dominating set contains at least one vertex in each complete vertex-
neighbourhood in $G$, i.e., the encoded dominating set is an actual dominating
set of size $k$ in $G$; if this is so, transition (16) constructs $X$ at
$p_{X}$. Finally, let $p_{I}=E^{\prime}_{1,1}$ and $X$ be a single point-field
of type $s_{X}$ at $p_{X}=E^{\prime}_{1,1}$. Note that this instance of
EnvDesSF${}^{fast}_{D}$ can be constructed in time polynomial in the size of
the given instance of Dominating set.

Let us now prove that this reduction is correct, in that the answer to the
given instance of Dominating set is “Yes” if and only if the answer for the
constructed instance of EnvDesSF${}^{fast}_{D}$ is “Yes”.

  * •

Suppose there is dominating set of size at most $k$ in the given graph $G$.
Let the set $V^{\prime}\subseteq V$ be the vertices in this dominating set; if
$|V^{\prime}|<k$, add an arbitrary set of $k-|V^{\prime}|$ vertices in $G$ to
$V^{\prime}$. Construct an environment $E^{\prime}$ as described above. In
such an environment, observe that $r$ started at $p_{I}$ will progress from
$q_{0}$ to $q_{v|V|4}$ and construct $X$ at $p_{X}$; at any point in the
operation of $r$, the current state of $r$ indicates how many vertex-
neighborhoods in $G$ have been evaluated against the dominating set encoded in
$E^{\prime}$. Also at any point in the operation of $r$, at most one
transition is enabled, which means that the operation of $r$ in $E^{\prime}$
is deterministic in the sense described in Section 2. With respect to
$(c_{1},c_{2})$-completability, observe that in the worst case, $r$ needs to
do at most $|V|+1$ complete passes around the movement-track (the first to
ensure that $E^{\prime}$ is in the proper initial form and then $|V|$ passes
to ensure that each of the complete vertex-neighborhoods in $G$ has at least
one vertex in the dominating set encoded in $E^{\prime}$). As there are
$2|V|+6$ squares in the movement track, this means that $r$ requires at most
$(|V|+1)(2|V|+6)$ timesteps to construct $X$ at $p_{X}$. As in turn
$(|V|+1)(2|V|+6)<(3|V|+9)^{2}=|E|^{2}<c_{1}(|E|+|Q|)^{c_{2}}$ when $c_{1}=1$
and $c_{2}=2$, this means that the task of constructing $X$ at $p_{X}$ is
$(c_{1},c_{2})$-completable when $c_{1}=1$ and $c_{2}=2$.

  * •

Conversely, suppose there is an environment $E^{\prime}$ based on $G^{\prime}$
and $S$ such that robot $r$ started at $p_{I}$ constructs $X$ at $p_{X}$. In
order to progress from $q_{0}$ to $q_{v00}$, $E^{\prime}$ must be in the
initial form described above; moreover, for $1\leq i\leq|V|$, by the structure
of the transition-set of $r$, $r$ can only progress from $q_{v(i-1)0}$ to
$q_{v(i-1)4}$ (and hence eventually trigger the transition from $q_{v|V|}$
that constructs $X$ at $p_{X}$) if there is a vertex $v$ in the dominating set
encoded in $E^{\prime}$ such that $v\in N_{C}(v_{i})$ in $G$.555 Note that
here, as in the reduction in the proof of Result D.SF.1, a vertex $v$ may
appear multiple times in the dominating set encoded in $E^{\prime}$. Once
again, this is not a problem — the vertices in the encoded dominating set need
not be distinct as we are are only interested in the presence of a dominating
set of size at most $k$ in $G$.  Thus, $r$ started at $p_{I}$ can construct
$X$ at $p_{X}$ in $E^{\prime}$ only if a dominating set of size at most $k$ in
$G$ is encoded in the middle $|V|$ squares of the first column in
$E^{\prime}$.

This proves the correctness of the reduction. The result then follows from the
$W[2]$-hardness of Dominating set [20], the reduction above, the fact that
$W[1]\subseteq W[2]$, and Lemma 4. To complete the proof, note that in the
constructed instance of EnvDesSF${}^{fast}_{D}$, $|T|=h=|X|=1$, $|f|=3$,
$|S|=8$, $|S_{E}|=k+7$, and $|q_{E}|=\max(2,k)$.

Result D.SF.5

[18, Result B.5]: If
$\langle|T|,h,d,|S|,|S_{E}|,|q_{E}|,|X|\rangle$-EnvDesSFfast is fp-tractable
then $FPT=W[1]$.

Proof: Modify the reduction in the proof of Result D.SF.4 such that for $1\leq
i\leq|V|$, the sets of transitions $\\{\langle
q_{v(i-1)0},fval(fq_{P},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,j+1.0),*,goNorth$
$q_{v(i-1)1}\rangle~{}|~{}v_{j}\in N_{C}(v_{i})\\}$ and $\\{\langle
q_{v(i-1)0},fval(fq_{P},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,k+1.0),*,$
$goNorth,q_{v(i-1)0}\rangle~{}|~{}v_{k}\not\in N_{C}(v_{i})\\}$ in transition-
set (10) are replaced by the pair of transitions $\langle
q_{v(i-1)0},fval(fq_{P},=,1.0)~{}\rm{and}~{}f,*,goNorth,$ $q_{v(i-1)1}\rangle$
and $\langle
q_{v(i-1)0},fval(fq_{P},=,1.0)~{}\rm{and}~{}f^{\prime},*,goNorth,q_{v(i-1)0}\rangle$,
respectively, where $f$ and $f^{\prime}$ are the formulas OR-ing all formulas
of the form $fval(fq_{L},=,j+1.0)$ and $fval(fq_{L},=,k+1.0)$ (each such Or-ed
group now enclosed by parentheses) in the trigger formulas of the transitions
in their respective sets. Note that this modified reduction still runs in time
polynomial in the size of the given instance of Dominating set; moreover, this
reduction is correct by slight modifications of the arguments given for the
proof of correctness of the reduction in the proof of Result D.SF.1. The
result then follows from the $W[2]$-hardness of $\langle k\rangle$-Dominating
set [20], the modified reduction above, the fact that $W[1]\subseteq W[2]$,
and Lemma 4. To complete the proof, note that in the constructed instance of
EnvDesSF${}^{fast}_{D}$, $|T|=h=|X|=1$, $d=3$, $|S|=8$, $|S_{E}|=k+7$, and
$|q_{E}|=\max(2,k)$.

Result D.SF.6

[18, Result B.6]: If $\langle|Q|,|f|,d,|S|,|X|\rangle$-EnvDesSFfast is fp-
tractable then $FPT=W[1]$.

Proof: Consider the following reduction from Dominating set to
EnvDesSF${}^{fast}_{D}$, based on the reduction from Dominating set to
EnvDesSF${}^{fast}_{D}$ given in the proof of Result D.SF.4. Given an instance
$\langle G=(V,E),k\rangle$ of Dominating set, construct instance $\langle
G^{\prime},S,T,p_{I},X,p_{X}\rangle$ of EnvDesSF${}^{fast}_{D}$ as follows:
Let $G^{\prime}$ be a $3\times(|V|+2)$ grid,
$S=\\{s_{P},s_{S},s_{N},s_{E},s_{W},s_{L},s_{robot},s_{X}\\}$ be a set of
fields such that $s_{P}$, $s_{S}$, $s_{N}$, $s_{E}$, and $s_{W}$ are all
point-fields with source-value and decay 1 and $s_{L}$ is an edge-field with
source-value $|V|+2$ and decay 1. The environment $E^{\prime}$ based on
$G^{\prime}$ and $S$ can be split into two regions: a movement track
consisting of the outer squares on all edges of $E^{\prime}$ and a central
scaffolding composed of squares
$E^{\prime}_{2,2},E^{\prime}_{2,3},\ldots,E^{\prime}_{2,|V|+1}$ in the second
column of $E^{\prime}$. Let
$p_{I}=E^{\prime}_{1,1}~{}\cup~{}\\{E^{\prime}_{3,i}~{}|~{}2\leq
i\leq|V|+1\\}$, $X$ be a single point-field of type $s_{X}$ at
$p_{X}=E^{\prime}_{3,2}$, and $T$ consist of $|V|+1$ robots of two basic
types:

1)

Vertex neighborhood robots: Each vertex neighborhood robot $r_{vi}$, $1\leq
i\leq|V|$, moves clockwise around the movement-track to check if the candidate
dominating set encoded in $E^{\prime}$ contains at least one vertex in the
complete neighborhood in $G$ of the vertex associated with that robot; if so,
$r_{vi}$ places a point-field of type $e_{X}$ at position $i$ in the central
scaffolding. For $1\leq i\leq|V|$, robot $r_{vi}$ is initially positioned at
$E^{\prime}_{3,i+1}$, is based on state-set
$Q=\\{q_{0},q_{v1},q_{v1f},q_{v2},q_{v2f},q_{v3},v_{q3f},$ $q_{v4}\\}$, and
has the following transitions:

  1. 1.

$\langle q_{0},*,*,stay,q_{v3}\rangle$

  2. 2.

$\\{\langle
q_{v1},fval(fq_{P},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,j+1.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,North)),*,goNorth,q_{v1f}\rangle,\\\ \langle
q_{v1},fval(fq_{P},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,k+1.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,North)),*,goNorth,q_{v1}\rangle,\\\ \langle
q_{v1f},fval(fq_{L},<|V|+2.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$ and
$fgrd(q_{robot},>,$ $North)),$ $*,goNorth,q_{v1f}\rangle,\\\ \langle
q_{v1},fval(fq_{P},=,0.0)~{}\rm{and}~{}fval(fq_{L},<|V|+2.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,North)),*,goNorth,q_{v1}\rangle\\\ ~{}|~{}v_{j}\in
N_{C}(v_{i})~{}\rm{and}~{}v_{k}\not\in N_{C}(v_{i})\\}$

  3. 3.

$\\{\langle
q_{v1f},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,East)),*,goEast,q_{v2f}\rangle,\\\ \langle
q_{v2f},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,East)),*,goEast,q_{v2f}\rangle,\\\ \langle
q_{v1},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,East)),*,goEast,q_{v2}\rangle,\\\ \langle
q_{v2},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,East)),*,goEast,q_{v2}\rangle\\}$

  4. 4.

$\\{\langle
q_{v2f},fval(fq_{S},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,South)),*,goSouth,q_{v3f}\rangle,\\\ \langle
q_{v2},fval(fq_{S},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,South)),*,goSouth,q_{v3}\rangle\\}$

  5. 5.

$\\{\langle
q_{v3f},fval(fq_{L},<,|V|+2,0)~{}\rm{and}~{}fval(fq_{L},>,1.0)~{}\rm{and~{}not}~{}fval(fq_{L},=,i+1.0)~{}\rm{and}~{}(fval(e_{robot},$
$\leq,1,5)$ and $fgrd(q_{robot},>,South)),*,goSouth,q_{v3f}\rangle,\\\ \langle
q_{v3f},fval(fq_{L},<,|V|+2,0)~{}\rm{and}~{}fval(fq_{L},>,1.0)~{}\rm{and}~{}fval(fq_{L},=,i+1.0)~{}\rm{and}~{}\linebreak(fval(e_{robot},$
$\leq,1,5)$ and $fgrd(q_{robot},>,South)),fmod(s_{X},(-1,0)),\linebreak
goSouth,q_{v3f}\rangle,\\\ \langle
q_{v3},fval(fq_{L},<,|V|+2,0)~{}\rm{and}~{}fval(fq_{L},>,1.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,South)),*,goSouth,q_{v3f}\rangle\\}$

  6. 6.

$\\{\langle
q_{v3f},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goWest,q_{v4}\rangle,\\\ \langle
q_{v3},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goWest,q_{v4}\rangle,\\\ \langle
q_{v4},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goWest,q_{v4}\rangle\\}$

  7. 7.

$\langle
q_{v4},fval(fq_{N},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goNorth,q_{v1}\rangle$

The transitions in (2) move $r_{vi}$ north along the first column and, on
detecting a vertex $v$ encoded in the candidate dominating set in $E^{\prime}$
such that $v\in N_{C}(v_{i})$, set the state of $r_{vi}$ to $q_{v1f}$. The
transitions in (3) and (4) ensure that this state-distinction is preserved
until $r_{vi}$ is at position $E^{\prime}_{3,i+1}$ in the third column of
$E^{\prime}$, at which point the transitions in (5) places the point-field
$s_{X}$ one square to the west in the central scaffolding. All other
transitions ensure repeated motion around the outer movement track in a
clockwise fashion, provided the correct motion-marker point-fields have been
placed on this track (see the description of the checker robot below).

2)

Checker robot: The checker robot $r_{chk}$ moves clockwise around the
movement-track to ensure on its first pass around that $E^{\prime}$ has the
proper initial form. On its second pass around, it checks if all vertex
neighborhood robots have fully filled in the central scaffolding; if so, it
creates the requested structure $X$ at $p_{X}$. Robot $r_{chk}$ is initially
positioned at $E^{\prime}_{1,1}$, is based on state-set
$Q=\\{q_{0},q_{ce10},q_{ce11}\ldots,1_{ce1k},q_{ce2},q_{ce3},q_{ce4},q_{cv1},q_{cv2},q_{cv3f},q_{cv3nf},q_{c4}\\}$,
and has the following transitions:

  1. 1.

$\langle
q_{0},fval(fq_{N},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},>,$ $North)),*,goNorth,q_{ce10}\rangle$

  2. 2.

$\\{\langle
q_{ce1(i-1)},fval(fq_{P},=,1.0)~{}\rm{and}~{}fval(fq_{X},=,0.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,North)),*,goNorth,q_{ce1i}\rangle,$
$\langle
q_{ce1(i-1)},fval(fq_{P},=,0.0)\rm{and}~{}fval(fq_{E},=,0.0)~{}\rm{and}~{}fval(fq_{X},=,0.0)~{}\rm{and}~{}\linebreak(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},>,North)),*,goNorth,q_{ce1(i-1)}\rangle$ $~{}|~{}1\leq
i\leq k\\}$

  3. 3.

$\langle
q_{ce1k},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,East)),*,goEast,q_{ce2}\rangle$

  4. 4.

$\langle
q_{ce2},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,East)),*,goEast,q_{ce2}\rangle$

  5. 5.

$\langle
q_{ce2},fval(fq_{S},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,South)),*,goSouth,q_{ce3}\rangle$

  6. 6.

$\langle
q_{ce3},fval(fq_{L},<,|V|+2,0)~{}\rm{and}~{}fval(fq_{L},>,1.0)~{}\rm{and}~{}fval(fq_{X},=,0.0)$
$~{}\rm{and}~{}\linebreak(fval(e_{robot},\leq,1,5)$ and
$fgrd(q_{robot},>,South)),*,goSouth,q_{ce3}\rangle$

  7. 7.

$\langle
q_{ce3},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goWest,q_{ce4}\rangle$

  8. 8.

$\langle
q_{ce4},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goWest,q_{ce4}\rangle$

  9. 9.

$\langle
q_{ce4},fval(fq_{N},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,North)),*,goNorth,q_{cv1}\rangle$

  10. 10.

$\\{\langle q_{cv1},fval(fq_{P},=,1.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},>,North)),\linebreak*,goNorth,q_{cv1}\rangle,\\\ \langle
q_{cv1},fval(fq_{P},=,0.0)~{}\rm{and}~{}fval(fq_{E},=,0.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},>,$ $North)),*,goNorth,q_{cv1}\rangle\\}$

  11. 11.

$\langle
q_{cv1},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,East)),*,goEast,q_{cv2}\rangle$

  12. 12.

$\langle
q_{cv2},fval(fq_{E},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,East)),*,goEast,q_{cv2}\rangle$

  13. 13.

$\langle
q_{cv2},fval(fq_{S},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,|V|+2,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,South)),*,goSouth,q_{cv3f}\rangle$

  14. 14.

$\langle
q_{cv3f},fval(fq_{L},<,|V|+2,0)~{}\rm{and}~{}fval(fq_{L},>,2.0)~{}\rm{and}~{}fval(fq_{X},=,0.5)~{}\rm{and}~{}\\\
(fval(e_{robot},\leq,1,5)$ and
$fgrd(q_{robot},>,South)),*,goSouth,q_{cv3f}\rangle$

  15. 15.

$\langle
q_{cv3f},fval(fq_{L},=,2.0)~{}\rm{and}~{}fval(fq_{X},=,0.5)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,South)),fmod(s_{X},(0.0)),goSouth,q_{cv3f}\rangle$

  16. 16.

$\langle
q_{cv3f},fval(fq_{L},<,|V|+2,0)~{}\rm{and}~{}fval(fq_{L},>,2.0)~{}\rm{and}~{}fval(fq_{X},=,0.0)~{}\rm{and}~{}$
$(fval(e_{robot},\leq,1,5)$ and
$fgrd(q_{robot},>,South)),*,goSouth,q_{cv3nf}\rangle$

  17. 17.

$\langle q_{cv3nf},fval(fq_{L},>,1.0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},>,South)),\linebreak*,goSouth,$ $q_{cv3nf}\rangle$

  18. 18.

$\langle
q_{cv3f},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goWest,q_{cv4}\rangle$

  19. 19.

$\langle
q_{cv3nf},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goWest,q_{cv4}\rangle$

  20. 20.

$\langle
q_{cv4},fval(fq_{W},=,1.0)~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,West)),*,goWest,q_{cv4}\rangle$

  21. 21.

$\langle
q_{cv4},fval(fq_{N},=,1.0))~{}\rm{and}~{}fval(fq_{L},=,1,0)~{}\rm{and}~{}(fval(e_{robot},\leq,1,5)$
and $fgrd(q_{robot},$ $>,North)),*,goNorth,q_{cv1}\rangle$

The transitions in (1)–(9) ensure that the environment $E$ initially has the
proper form, i.e.,

  * •

Square $E^{\prime}_{1,1}$ contains a point-field of type $s_{N}$;

  * •

Squares $E^{\prime}_{1,i}$, $2\leq i\leq|V|+1$, encode a candidate dominating
set consisting of $k$ distinct vertices in $G$ (indicated by point-fields of
type $s_{P}$ at the appropriate positions);

  * •

Squares $E^{\prime}_{1,|V|+2}$ and $E^{\prime}_{2,|V|+2}$ contain point-fields
of type $s_{W}$;

  * •

Square $E^{\prime}_{3,|V|+2}$ contains a point-fields of type $s_{S}$;

  * •

Squares $E^{\prime}_{2,1}$ and $E^{\prime}_{3,1}$ contain point-fields of type
$s_{W}$;

  * •

The north edge of $E^{\prime}$ has an edge-field $s_{L}$; and

  * •

There are no point-fields of type $e_{X}$ in the middle $|V|$ squares of the
second or third column of $E^{\prime}$.

With respect to the final point, there may be other types of point-fields in
these squares, but they are ignored by the vertex neighborhood and checker
robots. The transitions in (14) check if the central scaffolding has been
fully filled in with point-fields of type $e_{X}$ by the vertex neighbourhood
robots, i.e., the encoded dominating set is an actual dominating set of size
$k$ in $G$; if this is so, the transition (15) constructs $X$ at $p_{X}$. All
other transitions ensure repeated motion around the outer movement track in a
clockwise fashion, provided the correct motion-marker point-fields have been
placed on this track.

Note that all of the transitions described above use the robot collision-
avoidance formula
$(fval(e_{robot},\leq,1,5)~{}\rm{and}~{}fgrd(q_{robot},>,dir))$ derived in
Section 3.4 that allows moves in direction $dir$ along the movement-track.
This instance of EnvDesSF${}^{fast}_{D}$ can be constructed in time polynomial
in the size of the given instance of Dominating set.

Let us now prove that this reduction is correct, in that the answer to the
given instance of Dominating set is “Yes” if and only if the answer for the
constructed instance of EnvDesSF${}^{fast}_{D}$ is “Yes”.

  * •

Suppose there is dominating set of size at most $k$ in the given graph $G$.
Let the set $V^{\prime}\subseteq V$ be the vertices in this dominating set; if
$|V^{\prime}|<k$, add an arbitrary set of $k-|V^{\prime}|$ vertices in $G$ to
$V^{\prime}$. Construct an environment $E^{\prime}$ as described above. In
such an environment, observe that (1) the vertex neighbourhood robots in $T$
started at the specified positions in $p_{I}$ will, on their first pass around
the movement-track, fully fill in the squares in the central scaffolding with
point-fields of type $s_{X}$ and (2) the checker robot, on its second pass
around the movement-track, will construct $X$ at $p_{X}$. At any point in the
operation of $T$, at most one transition is enabled in any robot, which means
that the operation of $T$ in $E^{\prime}$ is deterministic in the sense
described in Section 2. With respect to $(c_{1},c_{2})$-completability,
observe that in the worst case, each of robots in $T$ needs to do at most two
passes around the movement-track. As there are $2|V|+6$ squares in the
movement track and at least one robot in $T$ moves forward in every timestep,
this means that $T$ requires at most $(|V|+1)(2|V|+6)$ timesteps to construct
$X$ at $p_{X}$. As in turn
$(|V|+1)(2|V|+6)<(3|V|+6)^{2}=|E|^{2}<c_{1}(|E|+|Q|)^{c_{2}}$ when $c_{1}=1$
and $c_{2}=2$, this means that the task of constructing $X$ at $p_{X}$ is
$(c_{1},c_{2})$-completable when $c_{1}=1$ and $c_{2}=2$.

  * •

Conversely, suppose there is an environment $E^{\prime}$ based on $G^{\prime}$
and $S$ such that robot team $T$ started at $p_{I}$ constructs $X$ at $p_{X}$.
In order for $X$ to be constructed at $p_{X}$, the checker robot the checker
robot must have been able to complete its second pass of $E^{\prime}$ and all
of the vertex neighborhood robots in $T$ must have fully filled in the squares
in the central scaffolding in $E^{\prime}$ with point-fields of type $s_{X}$.
However, by the structures of the transition-sets of the vertex neighborhood
robots, the latter can only happen if, for each vertex robot $e_{v}$ in $T$,
there is a vertex $v^{\prime}$ in the dominating set encoded in $E^{\prime}$
such that $v^{\prime}\in N_{C}(v)$ in $G$.666 Note that here, as in the
reduction in the proof of Result D.SF.1, a vertex $v$ may appear multiple
times in the dominating set encoded in $E^{\prime}$. Once again, this is not a
problem — the vertices in the encoded dominating set need not be distinct as
we are are only interested in the presence of a dominating set of size at most
$k$ in $G$.  Thus, $T$ started at $p_{I}$ can construct $X$ at $p_{X}$ in
$E^{\prime}$ only if a dominating set of size at most $k$ in $G$ is encoded in
the middle $|V|$ squares of the first column in $E^{\prime}$.

This proves the correctness of the reduction. The result then follows from the
$W[2]$-hardness of Dominating set [20], the reduction above, the fact that
$W[1]\subseteq W[2]$, and Lemma 4. To complete the proof, note that in the
constructed instance of EnvDesSF${}^{fast}_{D}$, $|X|=1$, $d=4$, $|S|=8$,
$|f|=12$, and $|Q|=k+10$.

Result D.SF.7

[18, Result B.7]: $\langle|E|,|S|\rangle$-EnvDesSFfast is fp-tractable.

Proof: Follows from the algorithm in the proof of Result N in [16].

###  A.5 Proofs for Team / Environment Co-design by Library Selection

Result E.SF.1:

If TeamEnvDesSFfast is polynomial-time exact solvable then $P=NP$.

Proof: Follows from the reduction in the proof of Result D.SF.1, modified such
that $L$ consists of the single robot in $T$.

Result E.SF.2:

If $\langle|T|,h,|f|,|L|,|E|,|S_{E}|,|q_{E}|,|X|\rangle$-TeamEnvDesSFfast is
fp-tractable then $FPT=W[1]$.

Proof: Follows from the reduction in the proof of Result D.SF.2, modified such
that $L$ consists of the single robot in $T$.

Result E.SF.3:

If $\langle|T|,h,|Q|,d,|L|,|E|,|S_{E}|,|q_{E}|,|X|\rangle$-TeamEnvDesSFfast is
fp-tractable then $FPT=W[1]$.

Proof: Follows from the reduction in the proof of Result D.SF.3, modified such
that $L$ consists of the single robot in $T$.

Result E.SF.4:

If $\langle|T|,h,|f|,|L|,|S|,|S_{E}|,|q_{E}|,|X|\rangle$-TeamEnvDesSFfast is
fp-tractable then $FPT=W[1]$.

Proof: Follows from the reduction in the proof of Result D.SF.4, modified such
that $L$ consists of the single robot in $T$.

Result E.SF.5:

If $\langle|T|,h,d,|L|,|S|,|S_{E}|,|q_{E}|,|X|\rangle$-TeamEnvDesSFfast is fp-
tractable then $FPT=W[1]$.

Proof: Follows from the reduction in the proof of Result D.SF.5, modified such
that $L$ consists of the single robot in $T$.

Result E.SF.6:

If $\langle|Q|,|f|,d,|S|,|X|\rangle$-TeamEnvDesSFfast is fp-tractable then
$FPT=W[1]$.

Proof: Follows from the reduction in the proof of Result D.SF.6, modified such
that $L$ consists of the $|V|+1$ robots in $T$. Observe that given its
transition structure, the checker robot must be selected from $L$ and
initially positioned in $E^{\prime}_{1,1}$ in order to both progress around
the movement-track and (if the central scaffolding is filled in with point-
fields of $s_{X}$) create $X$ at $p_{X}$. Moreover, in order for all squares
in the central scaffolding to be filled in, all $|V|$ vertex neighbourhood
robots from $L$ must be selected from $L$ and initially positioned in the
middle $|V|$ squares of the eastmost column in $E^{\prime}$. The order of the
vertex neighborhood robots in this initial region is immaterial, as all of
these roots will have a chance to fill in their respective squares in the
central scaffolding before the second pass of the checker robot around the
movement-track. The proof of correctness of the reduction follows modulo these
observations, as does the result.

Result E.SF.7:

$\langle|L|,|E|,|S|\rangle$-TeamEnvDesSFfast is fp-tractable.

Proof: Follows from the algorithm in the proof of Theorem 7 in [12].


# A Constrained Conditional Likelihood Approach for Estimating the Means of
Selected Populations

Claudio Fuentes  Department of Statistics, Oregon State University  Vik Gopal
Department of Statistics and Applied Probability, National University of
Singapore

###### Abstract

Given $p$ independent normal populations, we consider the problem of
estimating the mean of those populations, that based on the observed data,
give the strongest signals. We explicitly condition on the ranking of the
sample means, and consider a constrained conditional maximum likelihood
(CCMLE) approach, avoiding the use of any priors and of any sparsity
requirement between the population means. Our results show that if the
observed means are too close together, we should in fact use the grand mean to
estimate the mean of the population with the larger sample mean. If they are
separated by more than a certain threshold, we should shrink the observed
means towards each other. As intuition suggests, it is only if the observed
means are far apart that we should conclude that the magnitude of separation
and consequent ranking are not due to chance. Unlike other methods, our
approach does not need to pre-specify the number of selected populations and
the proposed CCMLE is able to perform simultaneous inference. Our method,
which is conceptually straightforward, can be easily adapted to incorporate
other selection criteria.

##  1 Introduction

Consider a scenario where $p\geq 2$ independent normal populations are
available, and from each one of them, we obtain a sample of size $n$. In this
context, practitioners are sometimes interested in estimating the true means
of those populations that yielded the $k$ largest sample means in the
experiment.

A naive solution to the problem is to estimate the selected population means
with the corresponding sample means. Such an approach, however, is known to be
problematic. [11] showed that the resulting estimator is biased for the case
$k=1$. This bias is particularly evident when all $p$ populations are
identically distributed. In terms of optimality, [16, 13] both showed that the
estimator is minimax only when $p=2$.

In order to improve on the naive estimator, several alternatives have been
proposed in the literature, including [5], [2], and [3]. These papers propose
estimators that perform better in terms of the Mean Squared Error (MSE). [18]
considered a bias correction approach for the problem, obtaining estimators
that perform well in terms of frequentist risk. Following up on his own idea,
[19] introduced $\omega$-estimators which are essentially a weighted average
of the order statistics. [4] considered a two-stage procedure, assuming we can
obtain a second sample from the selected population, to produce unbiased
estimators of the selected means. Despite these results, performance theorems
are scarce, with the exception of [1] and [9]. The latter proposes an
empirical Bayes estimator and shows that it performs better in terms of the
Bayes risk with respect to any normal prior. The former paper focuses on
admissibility and obtains a generalized Bayes estimator under a harmonic
prior.

More recently, [12] make an implicit assumption of sparsity, that many effect
sizes (absolute population means) $\theta_{i}=0$. By adapting the theory
developed in [10], the authors in [12] perform post-selection inference with
the Lasso. [15] approached the problem by estimating the first and second
order bias of the naive estimator. Their results, which are similar in
performance to the empirical Bayes approach in [6], extend to the non-Gaussian
setting.

In this paper we propose a new estimator, that is based entirely on the
likelihood function after incorporating the selection process. We motivate and
define this new estimator in section 2, where we also provide a neat result
for $p=2$ that yields some insight into how the estimator works. In section 3,
we discuss the main computational hurdle in computing this estimator, and
provide some direction on overcoming it. Following that section, we summarize
the results of a simulation study that highlights the benefits and flaws of
this new estimator. We conclude the paper with a brief discussion of our main
results.

##  2 Conditional Likelihood Estimation

###  2.1 Defining the Conditional Likelihood

For simplicity, suppose that we obtain a single observation $X_{i}\sim
N(\mu_{i},\sigma^{2})$ from each population, and that the common variance
$\sigma^{2}=1$. Then, for $\bm{\mu}=(\mu_{1},\ldots,\mu_{p})^{T}$, the
unconditional likelihood is given by
$L_{0}(\bm{\mu})=\prod_{i=i}^{p}\phi(x_{i}-\mu_{i})$, where $\phi$ denotes the
density function of the standard normal distribution. However, once we observe
$X_{1}=x_{1},\;X_{2}=x_{2},\;\ldots,\;X_{p}=x_{p}$, we rank the observations
in order to identify the populations corresponding to the largest $x_{i}$’s
and estimate the respective means $\mu_{i}$. Hence, the conditional likelihood
of interest is

$L(\bm{\mu})=\frac{\prod_{i=i}^{p}\phi(x_{i}-\mu_{i})}{P_{\bm{\mu}}(X_{1}>X_{2}\ldots>X_{p})},$
(1)

where the notation $P_{\bm{\mu}}(\cdot)$ explicitly states that the
probability under consideration depends on $\bm{\mu}$. Note that, for equation
(1), we do not have to worry about the labels attached to the groups. In other
words, there is no loss of generality in assuming that the ordering of the
means is $X_{1}>X_{2}>\ldots>X_{p}$. It follows from equation (1) that the log
of the conditional likelihood is

$l(\bm{\mu})=C-\frac{1}{2}\sum_{i=1}^{p}(x_{i}-\mu_{i})^{2}-\log{P_{\bm{\mu}}(X_{1}>X_{2}\ldots>X_{p})}$
(2)

###  2.2 Constrained Conditional MLE

For the case $p=2$, note that $\bm{\mu}=(\mu_{1},\mu_{2})$ and

$P_{\bm{\mu}}(X_{1}>X_{2})=P_{\bm{\mu}}(X_{1}-X_{2}>0)=1-\Phi\left(\frac{\mu_{2}-\mu_{1}}{\sqrt{2}}\right)$
(3)

For a fixed $\mu_{2}$, $P_{\bm{\mu}}(X_{1}>X_{2})$ approaches 0 as
$\mu_{1}\downarrow-\infty$. This means that the $-\log
P_{\bm{\mu}}(X_{1}>X_{2})$ term in equation (2) increases to $\infty$, causing
the conditional likelihood to be unbounded. In other words, there is no global
maximum for the expression in (2) for $-\infty<\mu_{1},\mu_{2}<\infty$. This
phenomenon is of course, not specific to $p=2$.

The occurrence of an unbounded likelihood is not without precedent in the
statistics literature. Possibly the most widely studied models in which this
occurs is a normal mixture model with unequal variances [7]. One of the
solutions in that model was to constrain the parameter space to where there
are local modes, and that is what we shall attempt to do here as well.

Since we expect that the populations with the largest sample means would be
the ones with the largest population means, we now aim to maximise the
conditional likelihood in equation (2) subject to $\bm{\mu}\in\Theta$, where
$\Theta=\\{\bm{\mu}:\mu_{1}\geq\mu_{2}\geq\mu_{3}\ldots\geq\mu_{p}\\}$. We
thus define the Constrained Conditional Maximum Likelihood Estimator (CCMLE)
to be

$\hat{\bm{\mu}}=\underset{\bm{\mu}\in\Theta}{\mbox{arg max}}\;l(\bm{\mu})$ (4)

This is clearly a case of constrained statistical inference. Much of the
theory regarding this approach can be found in [14].

###  2.3 A Closed Form Result

######  Proposition 1.

Consider the CCMLE when $p=2$ and the variance is known. Thus, we have
realisations $x_{1}$ and $x_{2}$ from $N(\mu_{i},\;\sigma^{2})$ for $i=1,2$,
and have observed that $x_{1}>x_{2}$. If
$x_{1}-x_{2}>\frac{2\sigma}{\sqrt{\pi}}$, then the unique CCMLE is an interior
point of $\Theta=\\{(\mu_{1},\mu_{2}):\mu_{1}\geq\mu_{2}\\}$. If
$x_{1}-x_{2}\leq\frac{2\sigma}{\sqrt{\pi}}$, the CCMLE is
$\hat{\bm{\mu}}=(\bar{x},\bar{x})$, where $\bar{x}=(x_{1}+x_{2})/2$.

###### Proof.

Let us first define $g(\cdot)$ to denote the inverse Mills ratio:

$g(x)=\frac{\phi(x)}{1-\Phi(x)}$ (5)

We shall use certain properties of $g$ in this proof – in particular, note
that $g$ is convex and monotone increasing [[, see]]baricz2008mills.

Recall that the log-likelihood function is given by

$l(\bm{\mu})=-\log
2\pi-\log\sigma^{2}-\frac{1}{2\sigma^{2}}\sum_{i=1}^{2}(x_{i}-\mu_{i})^{2}-\log{\left(1-\Phi\left(\frac{\mu_{2}-\mu_{1}}{\sqrt{2\sigma^{2}}}\right)\right)}$

Setting the partial derivatives to zero, we find that, if a solution exists,
it must satisfy

$g\left(\sqrt{\frac{2}{\sigma^{2}}}(\bar{x}-\mu_{1})\right)=\sqrt{\frac{2}{\sigma^{2}}}(x_{1}-\mu_{1})$
(6)

Observe that equation (6) depends only on $\mu_{1}$. Let us define the
function on the left to be $h_{1}(\cdot)$ and the function on the right to be
$h_{2}(\cdot)$. Thus, a stationary point exists if $h_{1}$ and $h_{2}$
intersect. Note that we are finding the root of a transcendental equation; no
closed form solution exists. A plot of these two functions can be seen in
Figure 1. Several quantities on the plot can be derived. For instance, from
equation (5), we can compute that $h_{1}(\bar{x})=g(0)=\sqrt{\frac{2}{\pi}}$
and
$h^{\prime}_{1}(\bar{x})=-g^{\prime}(0)\sqrt{2/\sigma^{2}}\approx-0.900/\sqrt{\sigma^{2}}$.
Moreover, the height $H$ is $(x_{1}-x_{2})/\sqrt{2\sigma^{2}}$.

Figure 1: Conditions for existence/absence of a stationary point.

The figure shows that an intersection exists in
$\\{\mu_{1}:\mu_{1}\geq\bar{x}\\}$ if and only if $H>\sqrt{2/\pi}$. In other
words, if and only if $x_{1}-x_{2}>2\sigma/\sqrt{\pi}$.

Suppose that there is more than 1 root in $\\{\mu_{1}:\mu_{1}\geq\bar{x}\\}$.
Then, at some point, it must be that
$h^{\prime}_{1}(\mu_{1})<-\sqrt{2/\sigma^{2}}$. However
$h^{\prime}_{1}(0)\approx-0.900/\sqrt{\sigma^{2}}$, and $h_{1}$ is convex.
Hence $h^{\prime}_{1}(\mu_{1})>-0.900/\sqrt{\sigma^{2}}$ for all
$\mu_{1}\geq\bar{x}$. It follows from this contradiction that the stationary
point (if it exists) is unique.

Our final task is to show that, when $x_{1}-x_{2}\leq 2\sigma/\sqrt{\pi}$, the
CCMLE is on the boundary of $\Theta$ at $(\bar{x},\bar{x})$. Within the
constrained parameter space $\Theta$, we have $\mu_{2}\leq\mu_{1}$ and
therefore

$1-\Phi\left(\frac{\mu_{2}-\mu_{1}}{\sqrt{2\sigma^{2}}}\right)\geq 0.5$

Hence, for all $\bm{\mu}\in\Theta$,

$l(\bm{\mu})\leq C-\frac{1}{2\sigma^{2}}\sum_{i=1}^{2}(x_{i}-\mu_{i})^{2}+\log
2$

It is then easy to see that as $\mu_{1}$ and/or $\mu_{2}$ go to $+\infty$
and/or $-\infty$, it holds that $l(\bm{\mu})\rightarrow-\infty$.

When $x_{1}-x_{2}<2\sigma/\sqrt{\pi}$, we already know that there are no
stationary points in $\Theta$. This information, coupled with the
understanding that $l(\bm{\mu})$ decreases without bound as $\bm{\mu}$ moves
away from the boundary, leads to the conclusion that the CCMLE must be on the
boundary $\\{\bm{\mu}:\mu_{1}=\mu_{2}\\}$.

Now consider any point $\bm{\mu}$ such that $\mu_{1}=\mu_{2}$. If we can show
that the directional derivative in the direction of $(\bar{x},\bar{x})$ is
always positive, we are done, because it implies that we can always increase
the log-likelihood by taking a suitable step in the direction of
$(\bar{x},\bar{x})$. To simplify notation, let

$\gamma=\frac{1}{\sqrt{2\sigma^{2}}}g\left(\frac{\mu_{2}-\mu_{1}}{\sqrt{2\sigma^{2}}}\right)$

Thus we can write the gradient of $l$ as $\nabla
l=\left(\frac{1}{\sigma^{2}}(x_{1}-\mu_{1})-\gamma,\;\frac{1}{\sigma^{2}}(x_{2}-\mu_{2})+\gamma\right)^{T}$.
The direction we need to consider is
$\bm{u}=K(\bar{x}-\mu_{1},\;\bar{x}-\mu_{2})^{T}$, where $K$ is a positive
normalising constant, that makes $|\bm{u}|=1$.

For any point in $\Theta$, the directional derivative is

$\nabla
l^{T}\bm{u}\propto((1/\sigma^{2})(x_{1}-\mu_{1})-\gamma)(\bar{x}-\mu_{1})+((1/\sigma^{2})(x_{2}-\mu_{2})+\gamma)(\bar{x}-\mu_{2})$
(7)

Now for any point on the edge of $\Theta$, we let $\mu=\mu_{1}=\mu_{2}$ and
simplify expression (7) to show that

$\nabla l^{T}\bm{u}\propto\frac{2}{\sigma^{2}}(\bar{x}-\mu)^{2}\geq 0$

∎

###  2.4 Sample Computations

It is not straightforward to generalize the proof in Proposition 1 to higher
dimensions. However, the same intuitive results and numerical approaches
apply.

In Table 1 below, we present some sample CCMLE computations for various
combinations of observed values when $p=4$. In performing the computations, we
assume that $\sigma^{2}$ is known, and is equal to 1. The purpose is to
underline how, whenever a subset of observed sample means are close together,
the CCMLE procedure will shrink them towards each other. This is apparent in
row 1 of the table. Unlike the $p=2$ case, however, the critical distance at
which they are collapsed onto one another is no longer $2/\sqrt{\pi}$. This
latter phenomenon can be observed in row 2, where the separation is less than
$2/\sqrt{\pi}$, but the estimated values are not exactly equal.

| Observed Values | Estimates
---|---|---
| $\bm{x_{1}}$ | $\bm{x_{2}}$ | $\bm{x_{3}}$ | $\bm{x_{4}}$ | $\bm{\hat{\mu}_{1}}$ | $\bm{\hat{\mu}_{2}}$ | $\bm{\hat{\mu}_{3}}$ | $\bm{\hat{\mu}_{4}}$
Config 1 | 10.0 | 9.5 | 9.0 | 0.0 | 9.50 | 9.50 | 9.50 | 0.00
Config 2 | 10.0 | 9.0 | 8.0 | 0.0 | 9.35 | 9.00 | 8.65 | 0.00
Config 3 | 10.0 | 9.0 | 1.0 | 0.0 | 9.50 | 9.50 | 0.50 | 0.50
Config 4 | 10.0 | 2.0 | 1.0 | 0.0 | 10.00 | 1.35 | 1.00 | 0.65
Table 1: Sample CCMLE computations for $p=4$

##  3 Computation of the CCMLE

###  3.1 Calculation of Probabilities

As part of numerically maximising the conditional likelihood in equation (2),
we need to repeatedly compute $P_{\bm{\mu}}(X_{1}>X_{2}\ldots>X_{p})$ for
different $\bm{\mu}$ vectors. In this section, we outline how it is possible
to compute this integral for small values of $p$ using a trick of
conditioning, followed by a nested application of the integrate function in R.

For the case $p=2$, it is clear from equation (3) that the probability of
interest can be computed using the usual approximations to the standard normal
distribution function.

For the case $p=3$, we can condition on the random variable in the middle to
yield a univariate integral.

$\displaystyle P_{\bm{\mu}}(X_{1}>X_{2}>X_{3})$ $\displaystyle=$
$\displaystyle\int
P_{\bm{\mu}}(X_{1}>X_{2}>X_{3}|X_{2}=x_{2})f(x_{2})\,\mathrm{d}x_{2}$
$\displaystyle=$ $\displaystyle\int
P_{\bm{\mu}}(X_{1}>x_{2})P(x_{2}>X_{3})f(x_{2})\,\mathrm{d}x_{2}$

The same approach enabled us to compute the probabilities up to $p=7$ without
any further optimisation in R. For higher dimensions, we advocate computing
the integral using a lower level language such as C, and switching to a sparse
grid method [8] instead of persisting with cubature techniques.

###  3.2 Obtaining A Good Starting Point

We now focus on obtaining a good starting point for the numerical optimisation
in the case that $p>2$. A good starting point ensures that we can reduce the
number of times that we evaluate the high-dimensional probability and its
derivatives. Let us first denote
$f(\bm{\mu})=\log{P_{\bm{\mu}}(X_{1}>X_{2}\ldots>X_{p})}$. Taking a first
order Taylor approximation of $f$ about the observed $\bm{x}$, we can
approximate the conditional likelihood in (2) with

$l(\bm{\mu})\approx
C-\frac{1}{2}(\bm{x}-\bm{\mu})^{T}(\bm{x}-\bm{\mu})-f(\bm{x})-(\bm{\mu}-\bm{x})^{T}\nabla
f(\bm{x})$ (8)

Taking derivative with respect to $\bm{\mu}$ and setting the above equation to
0, we can get an approximation to the CCMLE. It works out to be

$\hat{\bm{\mu}}_{0}\approx\bm{x}-\nabla f(\bm{x})$ (9)

The solution does not mean that a stationary point always exists - remember
that we are solving an approximation to the conditional log-likelihood. For
the same reason, it is also possible that the solution in equation (9) does
not fall within the constrained space $\Theta$. In such cases, we shall use
the orthogonal projection onto $\Theta$ as the starting point. Note that the
projection has to be performed numerically - fortunately however, $\Theta$ is
convex, and hence we can rely on prior methods from convex optimization theory
in order to perform this step. The R package [17] provides a good
implementation for solving this projection problem, using a quadratic
programming technique.

##  4 A Comparison By Simulation

In this section, we shall assess the performance of the CCMLE via its Mean
Squared Error, and the bootstrap confidence intervals constructed using it. We
take the opportunity to highlight that the errors and intervals have to
respect the selection procedure.

For instance, suppose that populations A, B and C have true means 3, 2 and 1
respectively. If the corresponding sample means are 2.1, 2.2 and 1.8, then the
population selected as the maximum would be population B. The error in
estimating the mean of the selected population using the sample mean would be

$2-2.2=-0.2$

This is the methodology employed in Section 4.1. The error should not be
computed as $3-2.2=+0.8$, since the true mean of the selected population is in
fact 2.

Similarly, when bootstrapping the strata in Section 4.2, the population
selected to have the maximum will not always be population B. It could be
population A or even population C depending on the bootstrap sample drawn.
Thus it is not accurate to describe it as a confidence interval for population
A (which has the largest mean). It is a confidence interval for the population
_selected_ to have the maximum mean.

###  4.1 Mean Squared Error Comparison

In this subsection, we conduct a simulation study to understand the MSE of the
CCMLE, as compared to the MSE of the ordinary MLE. We consider only the cases
when $p=2$ and $p=3$ as they are sufficiently informative.

For the $p=2$ case, we fix $\mu_{2}=0$, and vary $\mu_{1}$ from 0 to 5. For
each configuration, we generate 1000 bivariate $N(\bm{\mu},\bm{I})$ random
vectors, and then estimate the mean of the population with the larger sample
mean.

The MSE estimate for each configuration has been plotted and smoothed in
Figure 2. Notice that the CCMLE performs very well when $\mu_{1}-\mu_{2}\leq
1.5$. Beyond that, it performs approximately 10% worse than the unconditional
MLE until the difference in means becomes quite large. From such a point
onwards, it will be the case that the sample means will be far enough apart to
warrant no shrinkage at all. It seems reasonable to guess that when
populations are close together, the CCMLE will be very beneficial; however,
when the population means are in fact far apart, it is not the right estimator
to use. We shall witness this in the $p=3$ case as well.

Figure 2: Estimated MSE for $p=2$ simulation experiment.

Now let us turn to the situation when $p=3$. In our experiment, we considered
3 possible values for $\mu_{3}:0,2$ and 4. For each $\mu_{3}$, we varied
$\mu_{2}$ and $\mu_{1}$ between $\mu_{3}$ and 5. The ouput for these
experiments is shown in Figure 3.

Figure 3: Estimated MSE for $p=3$ simulation experiment

Consider the three separate 2-by-3 lattice plots in Figure 3. In each, the
level plots in the top row correspond to the ordinary MLE, and the plots in
the second row correspond to the CCMLE. The plots in the left-most column
correspond to the errors when estimating the mean of the population with the
_maximum_ sample mean, and the plots in the right-most column correspond to
the errors for the population with the _minimum_ sample mean. Note that colors
closer to black indicate a good estimator (low MSE) while colors closer to
white indicate a poorer performance (high MSE).

Let us focus first on the case $\mu_{3}=0$. Observe that there is a diagonal
dark line for the CCMLE in the left-most column. In the configurations on the
diagonal, the means of population 1 and 2 are close to each other, and hence
the CCMLE does well. In the off-diagonals, the populations are better
separated and hence performance goes down. Overall though, it does appear that
the MLE and CCMLE have a similar performance for this setting.

In the second configuration for $p=3$, we had fixed $\mu_{3}$ to be 2, while
$\mu_{1}$ and $\mu_{2}$ varied from 2 to 5. The level plots for this
configuration dark regions for the CCMLE than the MLE, when compared to the
case when $\mu_{3}=0$. The reason is that the number of configurations where
at least two of the populations are close together has increased, resulting in
overall better performance from the CCMLE.

Now focus on the displayed plots for $\mu_{3}=4$, in Figure 3. The difference
between the CCMLE and the MLE is more pronounced when we consider this final
configuration, where $\mu_{1}$ and $\mu_{2}$ vary between 4 and 5. The regions
in the level plot for the CCMLE are consistently darker than those for the
MLE, due to the close proximity of sample means generated.

###  4.2 Confidence Intervals based on the CCMLE

In this subsection, we use the stratified bootstrap to assess the confidence
intervals from the CCMLE procedure. Consider $p=3$, and the true means to be
$\mu_{1}$, $\mu_{2}$, $\mu_{3}$. We simulate a single sample of size 50 from
each population. We draw from $N(\mu_{i},\sqrt{50})$ so that the sample mean
still has variance 1. Then we draw 9999 bootstrap samples from within each
sample and repeatedly compute the CCMLE. Each time, we are returned with an
estimate of the mean of the populations selected to be the maximum, middle and
minimum. The bias corrected intervals are then plotted for comparison with the
traditional intervals that do not incorporate the selection process. This
procedure is carried out for 4 different configurations of true means. The
output can be seen in Figure 4.

The output is most informative for the configuration where $\mu_{1}=10$,
$\mu_{2}=9.5$ and $\mu_{3}=9$. In this case, the CCMLE point estimates are all
equal, since there is insufficient power to discriminate between them. The
CCMLE intervals are roughly the same, though it is worth pointing out the
slight shrinkage, in opposite directions, of the intervals for the maximum and
the minimum. In the situations where the mean of a group is far from the rest
(for instance, in the bars for “Max” in the plots on the right, and the bars
for “Min” in the bottom left), the CCMLE and the traditional approach provide
comparable intervals. In cases where means are not distinguishable, (for
instance, in the bars for “Mid” and “Min” in the top right), the CCMLE
suggests it can provide shorter intervals.

Figure 4: Bootstrap confidence intervals using CCMLE procedure. See Section
4.2 for a detailed explanation.

##  5 Discussion

In this paper, we introduced a new estimator for the means of selected
populations and have started to unveil some of its properties. Although
simulations experiments suggest the estimator is not admissible (see Figures 2
and 3), it performs well, particularly when the population means are close
together. Furthermore, the proposed CCMLE provides simultaneous inference on
selected populations, without a need to pre-specify the number of populations
selected. Another advantage of the procedure is that because it is frequentist
in paradigm, there is no need for prior specification.

Although the focus in this paper has been on selection via ranking of sample
means, conceptually, this approach allows for any other selection criterion to
be used. For instance, if populations were to be selected based on the
absolute values of the sample means, the primary modification would be to the
probability in the denominator of equation (1). Finally, as presented, it is
straightforward to obtain bootstrap confidence intervals for this estimator,
as demonstrated in Section 4.2.

Future work include the study of the asymptotic properties of this estimator,
and computationally efficient methods to approximate the probability
$P_{\bm{\mu}}(X_{1}>\ldots>X_{p})$ in a general framework.

## References

  * [1] Alexandra Bolotskikh.  Post-Selection Inference.  PhD thesis, Cornell University, 2015.
  * [2] A. Cohen and H.B. Sackrowitz.  Estimating the Mean of the Selected Population.  In Third Purdue Symposium on Statistical Decision Theory and Related Topics. New York: Academic Press, 1982.
  * [3] A. Cohen and H.B. Sackrowitz.  A Decision Theoretic Formulation for Population Selection Followed by Estimating the Mean of the Selected Population.  In Fourth Purdue Symposium on Statistical Decision Theory and Related Topics. New York: Academic Press, 1986.
  * [4] Arthur Cohen and Harold B Sackrowitz.  Two stage conditionally unbiased estimators of the selected mean.  Statistics & Probability Letters, 8(3):273–278, 1989.
  * [5] R.C. Dahiya.  Estimation of the Mean of the Selected Population.  Journal of the American Statistical Association, 69(345):226–230, 1974.
  * [6] Bradley Efron.  Tweedie’s formula and selection bias.  Journal of the American Statistical Association, 106(496):1602–1614, 2011.
  * [7] Richard J Hathaway.  A constrained formulation of maximum-likelihood estimation for normal mixture distributions.  The Annals of Statistics, pages 795–800, 1985.
  * [8] Florian Heiss and Viktor Winschel.  Likelihood approximation by numerical integration on sparse grids.  Journal of Econometrics, 144(1):62–80, 2008.
  * [9] J.T. Hwang.  Empirical Bayes Estimation for the Means of the Selected Populations.  Sankhyā: The Indian Journal of Statistics, Series A, 55(2):285–304, 1993.
  * [10] Jason D Lee, Dennis L Sun, Yuekai Sun, and Jonathan E Taylor.  Exact post-selection inference with applications to the lasso.  arXiv preprint arXiv:1311.6238, 2014.
  * [11] J. Putter and D. Rubinstein.  On Estimating the Mean of a Selected Population.  Technical Report 165, Department of Statistics, University of Wisconsin., 1968.
  * [12] Stephen Reid, Jonathan Taylor, and Robert Tibshirani.  Post-selection point and interval estimation of signal sizes in gaussian samples.  arXiv preprint arXiv:1405.3340, 2014.
  * [13] H. Sackrowitz and E. Samuel-Cahn.  Evaluating the Chosen Population: A Bayes and Minimax Approach.  Lecture Notes-Monograph Series, pages 386–399, 1986.
  * [14] Mervyn J Silvapulle and Pranab Kumar Sen.  Constrained Statistical Inference: Order, Inequality, and Shape Constraints, volume 912.  John Wiley & Sons, 2011.
  * [15] Noah Simon and Richard Simon.  On estimating many means, selection bias, and the bootstrap.  arXiv preprint arXiv:1311.3709, 2013.
  * [16] C. Stein.  Contribution to the Discussion of Bayesian and Non-Bayesian Decision Theory.  Handout from the Institute of Mathematical Statistics Meeting, 1964\.
  * [17] Ravi Varadhan and Paul Gilbert.  BB: An R package for solving a large system of nonlinear equations and for optimizing a high-dimensional nonlinear objective function.  Journal of Statistical Software, 32(4):1–26, 2009.
  * [18] JH Venter.  Estimation of the Mean of the Selected Population.  Communications in Statistics-Theory and Methods, 17(3):791–805, 1988.
  * [19] JH Venter and SJ Steel.  Estimation of the Mean of the Population Selected from k Populations.  Journal of Statistical Computation and Simulation, 38(1-4):1–14, 1991.