Deception, Delay, and Detection of Strategies
Michael Erdmann


roman

Scalability Model for the LOFAR Direction Independent Pipeline
    H.J.A Rottgering ^a
    December 30, 2023
==============================================================


empty




Homology generators in a relation offer individuals the ability to
delay identification, by guiding the order via which the individuals
reveal their attributes <cit.>.  This perspective
applies as well to the identification of goal-attaining strategies in
systems with errorful control, since the strategy complex of a fully
controllable nondeterministic or stochastic graph is homotopic to a
sphere.  Specifically, such a graph contains for
each state v a maximal strategy σ_v that converges to state
v from all other states in the graph and whose identity may be
shrouded in the following sense: One may reveal certain actions of
σ_v in a particular order so that the full strategy becomes
known only after at least n-1 of these actions have been revealed,
with none of the actions revealed definitively inferable from those
previously revealed.  Here n is the number of states in the graph.
Moreover, the strategy contains at least (n-1)! such informative action release sequences, each of length at least n-1.

The earlier work described above sketched a proof that every 
maximal strategy in a pure nondeterministic  or pure
stochastic  graph contains at least one  informative action
release sequence of length at least n-1.  The primary purpose of the
current report is to fill in the details of that sketch.  To build
intuition, the report first discusses several simpler examples.  These
examples suggest an underlying structure for hiding capabilities or
bluffing capabilities, as well as for detecting such deceit.








Contents





arabic







§ INTRODUCTORY EXAMPLES







 §.§ Paths and Constituent Transitions

Paths and Constituent Transitions



LakeFig shows four islands connected by bridges, as might be
found in one of the great oceanic cities of the world.  One of the
bridges allows traffic in two directions, the others are one-way
bridges.  Of interest are the possible paths a bus of tourists or the
motorcade of a prominent dignitary might take from the Hotel
Island to the Palace Island, via one or two intermediary
islands (the Left Island and/or the Right Island).




Since the bridge between Left Island and Right Island is
bidirectional, there are infinitely many such paths, parameterized by
the number of times the bus or motorcade cycles over the two-way
bridge.  For the purposes of this report, we will disallow such
infinite cycling.  One can imagine different restrictions.

In this first example, we impose the restriction that a vehicle may
traverse the two-way bridge at most once in each of its possible
directions (perhaps for legal or monetary reasons).  In a more general
setting, we would disallow traversing any bridge in the same direction
more than once.  Later, in Section <ref>, we will discuss a
different example with a different restriction that prevents infinite
cycling.

We define a permissible path to be any path that a
vehicle might take from Hotel Island to Palace Island,
subject to the “no directional transition twice” restriction.  The
next page enumerates all permissible paths; there are six.
For clarity, we abbreviate each island name to its first letter and
give paths the names π_1, …, π_6.  Throughout this
subsection, we consider only these six paths, each of which starts at
Hotel Island and ends at Palace Island.


    π_1:       →      →               
    π_2:       →      →               
    π_3:       →      →      →         
    π_4:       →      →      →         
    π_5:       →      →      →      →   
    π_6:       →      →      →      →





LakeGraph describes the islands and bridges of LakeFig as
a directed graph, and the six permissible paths as a relation.  The
relation has a row for each permissible path and a column for each
directed edge in the graph, that is, for each directional transition
across a bridge.  Since a permissible path may traverse any bridge
direction at most once, each permissible path defines a set of directed edges, modeling all directional bridge
transitions in the path.  The relation therefore contains a nonblank
entry  for a given path π_i and a given directed edge
 if and only if path π_i includes transition .






  §.§.§ Identifying Paths from Transitions at Execution Time


Suppose an observer is watching a bus drive from the Hotel
Island to the Palace Island.  At what point during the trip can
the observer identify uniquely the specific path followed by the bus,
assuming the bus is traversing one of the permissible paths π_1,
π_2, π_3, π_4, π_5, or π_6?




  * Certainly, once the bus arrives at its destination, Palace
  Island, the observer can identify the path uniquely, since at that
  point the observer knows that he/she has seen the entire path.


  * The observer cannot identify any path uniquely after observing
  only the first bridge transition.  For instance, after observing
  transition , the possible paths consistent with this
  observation are π_1, π_3, and π_5.  Similarly, after
  observing transition , the possible paths consistent with the
  observation are π_2, π_4, and π_6.


  * Consider paths π_1 and path π_2, each of which consists
  of two transitions.  By the previous point, the observer must see
  the entire path in order to identify either of these paths uniquely.


  * The first two transitions of paths π_3 and π_5 are the
  same, namely  and .  Consequently, upon observing these
  transitions, the observer cannot identify a path uniquely; the path
  could be either π_3 or π_5.  Path π_3 consists of three
  transitions.  Thus, if the actual path is π_3, the observer must
  see the entire path before identifying the path as π_3.  A similar
  argument holds for path π_4.


  * Paths π_5 and π_6 contain four transitions.  For each of
  these two paths, the observer only needs to see the first three
  transitions in order to identify the path; no other permissible path
  shares those same three transitions with the path being observed.



In summary: Paths π_1, π_2, π_3, and π_4 can only be
identified uniquely after seeing all their transitions, assuming one
observes transitions in consecutive order.  Paths π_5 and π_6
can be identified uniquely after seeing the first three of their four
transitions, again assuming one observes transitions in consecutive
order.




  §.§.§ Identifying Paths from Transitions in Arbitrary Order


Previously we assumed that the observer was observing consecutive
motions of a bus.  Suppose now that the observer merely learns of
particular transitions made by the bus, without any explicit
ordering in time.  For instance, perhaps the observer is listening to
stories told by tourists on the bus after their trip, from which the
observer attempts to reconstruct the path taken.  Or perhaps the
observations are coming from many trips taken over the course of
several days by a bus following a particular fixed bus route each day.
Or perhaps the observer overhears the bus driver commenting on
particular bridges he will encounter on his next trip, from which the
observer is trying to predict the path yet to be taken.




We now ask:  What set  of transitions allows an observer to
identify a path uniquely?




  * Recall that path π_1 consists of the set of transitions
  {, }.  Previously, when observing transitions in
  consecutive order, seeing both these transitions identified path
  π_1 uniquely.  That is no longer true when transitions may be
  observed nonconsecutively.  The reason is that path π_5 contains
  these same transitions, plus others.  In fact, it is no longer
  possible to identify path π_1 uniquely.  Similarly, it is no
  longer possible to identify path π_2 uniquely.


  * If the observer learns that a path contains the transitions
   and , then the observer can infer that the path must
  also contain the transition  and must in fact be path
  π_3.  Whereas previously an observer needed to see the entire
  path π_3 in order to identify it uniquely, now a pair of
  nonconsecutive transitions identifies the path.  In effect,
  continuity of paths allows the observer to infer an unobserved
  transition.  A similar argument holds for path π_4.  Of course,
  if a story teller wishes to draw out identification of the path,
  he/she might simply talk about the sights seen during the bus ride
  in consecutive order, thus preventing such a leap of inference.


  * If the observer learns that a path contains the transitions
   and , then the observer can actually infer two
  unobserved transitions, namely  and , thereby
  concluding that the path is π_5.  A similar inference is
  possible for path π_6.  The observer is in effect taking
  advantage both of path continuity and knowledge of the path's
  destination.  Again, a story teller could draw out identification of
  path π_5 slightly by reporting transitions in consecutive order.



LakeComplexes encodes these conclusions geometrically, using
simplicial complexes <cit.>.  As in the relation of LakeGraph, we now view
each path as a set of directed edges.  These sets
constitute the generating simplices of the left simplicial complex
shown in LakeComplexes.  The vertices in this complex are the
directed edges of the graph of LakeGraph.  Path π_1
generates a one-dimensional simplex (edge) in the complex.  This
simplex is a subset of the three-dimensional simplex (tetrahedron)
generated by path π_5, modeling the earlier conclusion that one
cannot identify path π_1 uniquely when observing transitions in
arbitrary order.  Observe that the set {, } is a free
face[Simplicial complexes in this report are abstract,
i.e., collections of sets and all their subsets.  A simplex is a free face of an abstract simplicial complex if it is
a proper subset of exactly one maximal simplex in the complex.] in the
complex and is not itself a path.  This geometry models the inference
and identification of path π_3 discussed previously.  Similarly,
the set {, } forms a free face in the complex, modeling
the inferences and identification of path π_5 discussed above.
(The set {, } is an undrawn “diagonal” of the
tetrahedron labeled π_5.)



The right simplicial complex of LakeComplexes contains the same
information as the left complex, but in dual form.  The duality is
with respect to the relation of LakeGraph.  (Details of such
“Dowker duality” are discussed further in <cit.>.)

The vertices in the right complex are the permissible paths of the
graph of LakeGraph.  The generating simplices of the complex are
given by the columns of the relation of LakeGraph.  In other
words, each generating simplex consists of all the paths that share a
given directed edge.  Thus the right complex tells us how to interpret
observations of transitions as intersections of generating simplices.
For instance, if we know that a path contains the transitions 
and , then we can intersect the triangle labeled with  and
the triangle labeled with  to see that the possible paths are
π_1 and π_5.  (This geometric intersection is exactly the
intersection of the two columns indexed by  and  in the
relation of LakeGraph.)




Considering such intersections, our earlier observations
plus some others are immediate:





-4pt


  * π_1 and π_2 are not uniquely identifiable.

  * Observing  and  identifies path π_3.

  * Observing  and  identifies path π_4.

  * Observing  and  identifies path π_5 (as does observing  and ).

  * Observing  and  identifies path π_6 (as does observing  and ).





(These are the smallest sets of identifying observations for each
path; there exist larger sets of observations as well.)







 §.§ Strategies and Underlying Capabilities

Strategies and Underlying Capabilities



Stream shows a river with two islands, a fishing area upstream
of the islands, and a marina downstream from the islands.  The two
islands create three passages within the river that boats may
traverse, either upstream or downstream, as they move between the
fishing area and the marina.  The three passages produce currents of
different strengths.  One of these currents is so strong that only
boats with powerful motors are able to traverse the current going
upstream.  Fish in the fishing area like to gather near the start of
that strong current.  Consequently, boats with powerful motors have an
advantage reaching nice fish over boats with weaker motors.  On the
other hand, revealing that one has a powerful motor leads to envy and
other competitions.  As a result, skippers tend to underplay the power
of their motors.



We will examine the possible strategies for reaching the fishing area
(along with strategies for reaching the marina).  We will further
examine the extent to which someone can reveal portions of a strategy
without revealing the entire strategy.  Conversely, we will examine
the extent to which an observer can infer that a boat has a powerful
motor even when the observer never sees the boat traversing upstream
over the strong current.







StreamGraphs describes the river setting of Stream using a
directed graph, much as we did in the earlier example of
Section <ref>.  We will be interested primarily in the
transitions upstream and downstream through the passages beside the
islands, so we give those directed edges explicit names: _1,
_1, _2, _2, _3, _3, as shown in the right
panel of the figure.



In the example of Section <ref>, we focused on paths.  In the
current example, we adopt a slightly different perspective.  We are
interested in a generalization of what is frequently called a control law, namely a mapping from states to commanded motions.  The
generalization is that of a strategy, to be reviewed in
Section <ref>.  A strategy is a mapping from states to sets of possible motions, in this case sets of directed edges.
The semantics are as follows: When a boat is at a particular location,
a strategy specifies a set of directed edges leading from that
location to some neighboring locations.  The boat must move along some
one of those directions, with the particular direction determined
possibly by circumstance rather than chosen by the skipper.  (The
strategy specifies a set since sometimes the precise direction is not
so important as is a general direction. For instance, a boat with a
powerful motor that is currently at the marina might be instructed to
move toward any of the three passages in the river.  A corresponding
strategy would therefore include the set of transitions
{0→ 1,  0→ 2,  0→ 3}.)  If the set
specified for a particular location is empty, then the boat must stop
if it is at that location.



In the example of Section <ref>, we prevented infinite cycling by
disallowing any path that traversed any directed edge more than once.
With strategies, it is more natural to disallow any strategy whose
motion sets might cause the system to revisit a state.



There is a well-developed theory for strategies in graphs with
directed edges <cit.> as well as in graphs with nondeterministic and/or
stochastic transitions <cit.>.  One can
model the collection of all strategies as a simplicial complex,
similar to the constructions of Section <ref>.  In a directed
graph, a strategy is a set of directed edges that produces no cycle(s)
in the graph.  A graph's strategies constitute the simplices of a
simplicial complex whose underlying vertex set consists of the graph's
directed edges.  For a strongly connected directed graph, this
simplicial complex has the homotopy type of a sphere, namely ,
with n the number of states in the graph <cit.>.  For
the graph of StreamGraphs, the simplicial complex is therefore
homotopic to .

Since a sphere has homology, our prior work on privacy
<cit.> offers some lower bounds on how long a skipper
may delay identification of a strategy or a boat's final destination,
relative to all possible strategies in the graph of
StreamGraphs.  However, rather than explore the entire space of
strategies, we will focus in this example on some simpler scenarios.




  §.§.§ Strategies for Attaining the Fishing Area


For the moment, let us consider only all maximal strategies that
ultimately attain the fishing area from anywhere in the graph.  (By a
maximal strategy we mean here a cycle-free set
of directed edges in the graph of StreamGraphs that is maximal
among all such sets.)







  * Here is one such strategy, consisting of all possible upstream
  motions in the graph of StreamGraphs:





    σ_123 = {0→ 1,  0→ 2,  0→ 3,  
        1→ 4,  2→ 5,  3→ 6,  
        4→ 7,  5→ 7,  6→ 7}.


(This strategy contains the three upstream transitions _1,
    _2, and _3, with _i = i → i+3.)



  * The strategy σ_123 only makes sense for a boat with a
powerful enough motor to traverse the strong current of Stream.  A
boat without such a powerful motor might instead use the following
strategy:





    σ_23 = {1→ 0,  0→ 2,  0→ 3,  
        4→ 1,  2→ 5,  3→ 6,  
        4→ 7,  5→ 7,  6→ 7}.


(This strategy contains downstream transition _1 and 
    upstream transitions _2 and _3.)


Strategy σ_23 is very similar to strategy σ_123, but
in place of the upstream transitions 0→ 1 and
1→ 4, the strategy contains the downstream transitions
1→ 0 and 4→ 1.  As a result, if necessary, the
boat will first return to the marina via the leftmost passage of
Stream, then move up to the fishing area via either of the other
two passages.






  
Permissible Strategies: Strategy σ_23 specifies
two transitions at state #4, namely 4→ 7 and
4→ 1.  A boat moving under strategy σ_23 may
therefore reach the fishing area from state #4 either by moving
directly to the fishing area or by moving first downstream to the
marina then upstream via one of the other passages.  Intuitively, this
bifurcation arises because there are two arcs between any two points
on a circle.  Some maximal strategy must contain both.





While generally useful, motion multiplicity may merely add bookkeeping
clutter, so we restrict it: To start, we define a permissible
strategy to be a maximal strategy that (i) attains the fishing
area from anywhere in the graph and (ii) specifies a unique motion at
each state in the set {1, 2, 3}.  We also stipulate that whenever
a strategy specifies a passage transition and some other motion at a
boat's current location, then the boat will move through the passage.




We may now model permissible strategies via the relation of
StreamFishingStrategyRelation.  The relation contains a row for
each permissible strategy and a column for each passage transition.
An entry in the relation is nonblank if and only if the given strategy
contains the given transition.  Every maximal strategy in the graph of
StreamGraphs must contain exactly one transition from each of
the three sets {_i, _i}, i = 1, 2, 3.  Furthermore, among
the permissible2mu strategies, each strategy is
uniquely characterized by the three passage transitions it contains.
(Of course, it is impossible for a permissible strategy to contain all
three downstream transitions _1, _2, _3, since then the
strategy would not be guaranteed to attain the fishing area from the
marina.)

StreamFishingStrategyRelation further depicts a simplicial
complex generated by the strategies of the relation.  The underlying
vertex set of this complex is {_1, _1, _2, _2, _3,
_3}, comprising the six passage transitions in the river.




Each of the free faces in the complex of
StreamFishingStrategyRelation consists of a pair of downstream
transitions, e.g., {_1, _2}, suggesting inference of an
upstream transition, e.g., _3.  Indeed, if an observer learns
that a permissible strategy specifies downstream motion through two
passages, then the observer can infer that the strategy must specify
an upstream motion through the remaining passage (since the fishing
area is given as destination).  Consequently, observing two downstream
transitions in a permissible strategy identifies the strategy
uniquely.

There are no other free faces in the complex.  Consequently, observing
any other proper subset of a permissible strategy's passage
transitions does not identify that strategy uniquely.






  
Comment: On a given fishing expedition, an observer may
only see a boat move through a single passage, but over the course of
several days the observer may see the boat take different routes.  Or
perhaps a crewmember speaks of the transitions specified by a
strategy.  Assuming the skipper's strategy is constant, the observer
may be able to eventually infer the overall permissible strategy, much
like an observer could infer a bus route in Section <ref>, after
observing different bridge crossings on different days or by listening
to tourist stories.



  
Inferring Motor Strength:  How might an observer of a
boat's transitions infer that the boat has a strong motor?  Directly
observing the upstream transition u_1 is one way, of course.
Additionally, if the observer learns that a strategy specifies
downstream transitions _2 and _3 and  if the observer
knows that these are part of a strategy to reach the fishing area,
then the observer can infer that the strategy must contain the
upstream transition _1, implying that the boat has a powerful
motor.   (We assume that each boat only follows strategies it can execute.)

Four of the permissible strategies in
StreamFishingStrategyRelation, namely σ_123,
σ_12, σ_13, and σ_1, presuppose a powerful
motor.  If a skipper is following one of the strategies
σ_123, σ_12, or σ_13, then the skipper can
carefully reveal up to two different passage transitions while still
hiding the motor's power.  In contrast, for strategy σ_1, the
skipper can reveal at most one passage transition; revealing a second
transition necessarily exposes or implies the motor's power.







  §.§.§ Strategies for Attaining the Fishing Area and Strategies
  for Attaining the Marina


Let us augment our collection of permissible strategies, in
order to model boat excursions that are either outbound to the fishing area
or returning to the marina.  We
now permit any maximal strategy for attaining the fishing area that
specifies a unique motion at each state in the set {1, 2, 3}, plus any maximal strategy for attaining the marina
that specifies a unique motion at each state in the set {4, 5, 6}.
 (We retain the stipulation regarding passage transitions.)

Focusing on the subcollection of strategies for attaining the marina,
we may again construct a simplicial complex whose underlying vertex
set is {_1, _1, _2, _2, _3, _3}, much as in
StreamFishingStrategyRelation, now with the upstream and
downstream transitions interchanged.  We thus have two simplicial
complexes, one for the fishing-attaining strategies, the other for the
marina-attaining strategies.  We wish to combine these complexes.  In
order to not confuse simplices, we conify each complex with a vertex
identifying the complex.  We then glue the resulting two complexes
together at common boundary locations.  The final simplicial complex
thus obtained is homotopic to .

In order to visualize this construction more easily, let us simplify
the problem, by removing one of the islands, as in StreamNarrow.
Now there are only two passages, one with a strong current requiring a
powerful motor for the upstream direction, the other with a mild
current, traversable by all boats in both directions.  (The new
graph's state and transition names are consistent with those of
StreamGraphs.  State #0 is the marina and state #7 is the
fishing area.)

There are now three permissible strategies that attain the fishing
area from anywhere in the graph.  We name them σ_12,
σ_1, and σ_2.  Similarly, there are three permissible
strategies that attain the marina from anywhere in the graph.  We name
them τ_12, τ_1, and τ_2.  NarrowRelation
describes these six strategies via a relation.  Strategy names index
the rows of the relation.  The upstream and downstream transitions,
_1, _1, _2, and _2, plus two additional
attributes,  and , index the columns of the relation.
Previously, when we were considering only permissible strategies for
attaining the fishing area, the component upstream and downstream
transitions of that strategy fully determined the strategy (given that
the strategy was permissible).  Now, knowing a strategy's upstream and
downstream transitions may -0.5munot1.5mu fully
determine the strategy.  However, each permissible strategy in the set
{σ_12, σ_1, σ_2, τ_12, τ_1, τ_2} is
fully determined by its upstream and downstream transitions and by its destination.  The attributes  and  model
this destination.  Attribute  means a strategy's destination is
the fishing area and attribute  means the strategy's destination
is the marina.  For each permissible strategy, the relation lists the
strategy's upstream and downstream transitions along with its
destination.













  
Comment: One may readily observe a boat traversing a
passage, but what does it mean to observe attribute  or
?   One possibility is that a skipper announces a boat's
destination.   Another possibility is that the “observation” of
 or  is actually an inference made from other observations.
For instance, if an observer learns that the skipper has made
preparations for both transitions 4→ 7 and 5→
7, then the observer may conclude that the boat's destination is the
fishing area.  Or perhaps someone observes a boat departing the
marina, for instance by making the transition 0→ 2.  Then
the observer knows that the boat's destination cannot be the marina,
and so has “observed ” (assuming the strategy being observed is
permissible).





We will now construct a simplicial complex to represent the relation
of NarrowRelation, much as we constructed the complex in
StreamFishingStrategyRelation.  Let us proceed in steps.  First,
we construct a simplicial complex representing the permissible
strategies for attaining the fishing area and a separate simplicial
complex representing the permissible strategies for attaining the
marina.  In both cases, we let the underlying vertex set be {_1,
_1, _2, _2, , }.  See
StreamNarrowComplexHemispheres.  Observe that attribute  is
a cone apex for the complex generated by the fishing-attaining
strategies, while attribute  is a cone apex for the complex
generated by the marina-attaining strategies.[A cone
apex for a finite simplicial complex is a vertex contained in
every maximal simplex of the complex.]  Finally, we glue these two
simplicial complexes together along shared simplices, obtaining the
complex of StreamNarrowComplex.  The homotopy type of this
complex is , suggesting some ability to delay identification of
strategies <cit.>.  Observe in particular that every
upstream or downstream transition appears in three permissible
strategies.






Considering the free and nonfree faces of the simplicial complex in
StreamNarrowComplex, or directly from the relation of
NarrowRelation, we may make the following inferences:




  * Observing upstream transitions _1 and _2 in a boat's
  strategy implies attribute .  In other words, one may infer
  that the boat's destination is the fishing area and that the
  encompassing permissible strategy is σ_12.  This inference
  reflects the physical reality that a boat cannot have the marina as
  destination if its strategy always entails moving upstream, via the
  two passages on both sides of the island.


  * Similarly, observation of _1 and _2 implies 
  and identifies strategy τ_12.


  * Observing an upstream transition in one passage and a downstream
  transition in the other passage (without knowing which occurred
  first) leaves the boat's destination ambiguous.  This ambiguity
  reflects the physical reality that the boat could have rounded
  either the upstream end or the downstream end of the island.


  * Knowing the boat's destination and observing a passage
  transition away  from that destination implies the other
  passage transition and thus the overall permissible strategy.  For
  instance, knowing that the boat is heading to the fishing area
  () and observing the boat move downstream along the strong
  current (_1) means the boat's strategy must also specify a
  motion upstream over the mild current (_2).  The geometry of
  the river forces this implication and thus identifies the strategy
  σ_2  (assuming strategies are permissible).


  * Knowing the boat's destination and observing a passage
  transition toward  that destination leaves open the
  directionality of the transition through the other passage.  For
  instance, knowing that the boat is heading to the marina () and
  observing the boat move downstream along the mild current (_2)
  does not nail down whether the strategy specifies an upstream or a
  downstream transition through the passage with the strong current.
  There remains an ambiguity as to whether the encompassing
  permissible strategy is τ_12 or τ_2.






  §.§.§ Deception and Detection


Skippers of boats with motors capable of moving upstream over the
strong current tend to hide their strength for when it is really
needed, such as a competition to snag nice fish at the head of the
strong current.  They may hide their strength either by never
exercising it or by moving upstream over the strong current only under
cover of fog or darkness.

Let us suppose that this deception is so pervasive that, for all
intents and purposes, the upstream transition _1 is never  observable.  Two questions emerge:






  * How does the unobservability of _1 change the relation of
  NarrowRelation and the complex of StreamNarrowComplex?





  * How can one distinguish between a boat that is truly incapable
  of moving upstream over the strong current and a boat whose skipper
  is merely hiding that capability?





An initial answer to question #2 is that one cannot distinguish the
two types of boats if  the powerful boat always  acts
like the weaker boat.  However, if the powerful boat does sometimes
exercise its capabilities, then other observations may  imply
the boat's power.








StreamNarrowHiddenRelationComplex answers question #1.  The
relation one obtains when _1 is unobservable is the same as the
original relation of NarrowRelation, except that the column
indexed by the upstream transition _1 disappears.  The resulting
simplicial complex is now the deletion (Γ, _1), with
Γ the complex of StreamNarrowComplex.  (Formally,
(Γ,_1) = γ∈Γ_1∉γ.
In other words, the resulting complex contains all simplices of the
original complex except those that included _1.)



In the new complex, some strategies that appeared as triangles
originally now appear as edges.  These are the strategies
σ_12, σ_1, and τ_2, namely all strategies that
include the now unobservable upstream transition _1.



The observable portions of two of those strategies, namely
σ_12 and τ_2, are subsets of other strategies.  For
instance, the observable portion of σ_12 is a subset of
strategy σ_2.  This means: If one observes the upstream
transition _2 and if one knows that the boat's destination is the
fishing area (attribute ), then there remains an ambiguity
regarding the strategy's specified transition over the strong current;
it could be either upstream (as in σ_12) or downstream (as in
σ_2).  Consequently, if a skipper with a powerful motor always
follows strategy σ_12, but traverses the strong current only
during fog and the mild current during clear weather, then no one will
know of the boat's power.  (This assumes that the traversal times are
unmeasured or constant, e.g., the skipper avoids traversing the mild
current excessively quickly with the strong motor.)



In contrast, strategy σ_1 generates a maximal simplex even in
the new complex and is thus uniquely identifiable from its observable
attributes.  This means: If one observes the downstream transition
_2 but knows that the overall destination of the boat is the
fishing area (attribute ), then one can conclude that the
strategy must be σ_1 and that the boat will traverse the strong
current upstream.  In other words, even though _1 is
unobservable, one can infer its existence and conclude that the boat
has a powerful motor.





It is instructive to construct the strategy relation and attendant
simplicial complex for a boat that truly is incapable of traversing
the strong current upstream.  These appear in
StreamNarrowLimitedRelationComplex.  Not only does the
transition _1 now disappear, but so do all strategies that relied
on that transition.  (Again, we assume that the boat only follows
strategies which it is capable of executing.)

The space of strategies is much smaller now.  The resulting simplicial
complex looks similar to that in which _1 was merely
unobservable, but there is a key difference: The simplex {,
_2} is gone.  (In fact, all three strategies that once contained
_1 are now gone, but only one of those, namely σ_1, formed
a maximal simplex previously in the complex of
StreamNarrowHiddenRelationComplex.)  The new complex tells us
that it is inconsistent  for a boat with a weak motor to
announce its destination as the fishing area (attribute ) but to
traverse the mild current downstream (attribute _2).




Report <cit.> described how inconsistent observations
sometimes suggest or identify unmodeled properties.  Here, observing
the inconsistency {, _2} might suggest that the actual
strategies for the boat being observed are not those of
StreamNarrowLimitedRelationComplex but those of
StreamNarrowHiddenRelationComplex.




We may therefore interpret the difference between the two relations
and complexes of Figures <ref> and
<ref> as follows:






  * The relations and complexes tell an actor  what behavior
  to avoid, in order to be successful  at deception.

  * The relations and complexes tell an observer  how to
  look for  inconsistencies in behavior, in order to detect  deception.







  §.§.§ Inferences, Free Faces, Geometry


The simplicial complex of StreamNarrowLimitedRelationComplex is
a cone with apex _1.  This geometry arises because every 
permissible strategy in the relation of that figure contains the
downstream transition _1.  Said differently, if a boat is
incapable of moving upstream through the passage with the strong
current, then there is no choice but to include the downstream
transition in every permissible strategy for that boat.  (Recall that
a permissible strategy consists of a maximal  set of motions
that a boat might  make to attain its destination without
cycling.)  One can thus infer the transition _1 “for free”,
i.e., without observing or learning of the motion directly, assuming
one knows that the boat has a weak motor.




Let us therefore remove vertex _1 from the complex of
StreamNarrowLimitedRelationComplex to obtain the following:






This simplified complex highlights some inferences that are possible
when observing boats known to have weak motors (as usual, we also
assume that the strategies under consideration are permissible
strategies and that each boat only follows strategies it can execute):







  * _2:  If one knows that a boat is heading to
  the fishing area, then one can infer that the boat must move
  upstream when traversing the mild current.


  * _2:  If one observes a boat moving
  downstream over the mild current, then the boat must be heading to
  the marina.






These conclusions reflect the geometry of the fishing area and marina
relative to the passages.  Said differently, the geometry of the
simplicial complex models the geometry of the river in such a way that
one can draw conclusions about boat motions from the free faces in the
complex.  We saw this property as well when modeling paths in the
example of Section <ref>.







 §.§ Hidden State

Hidden State

The examples and discussion of this introduction have assumed that the
underlying state is known to the observer.  For example, the analysis
of Section <ref> assumed a state space defined by the river
geometry, along with strategies whose motions were not allowed to
revisit states.



In reality, a skipper might have additional hidden state.  The
restriction on revisiting states would then apply to the composite of
observable and hidden states but not necessarily to the observable
states alone.  For instance, a skipper might be willing to revisit
some parts of the river once or twice, relative to some hidden
internal counter (perhaps fuel consumption).  A skipper could then
selectively hide some motions and reveal other motions, in order to
bluff the capability of a strong motor.  (An observer unaware of the
skipper's hidden state might infer _1 from observations {,
_2} even though the boat only has a weak motor and has made
surreptitious cyclic motions not involving _1 in order to give
the appearance of a strong motor.)



One possible approach for dealing with such hidden state is to
construct many possible models of that state, then hope to observe
inconsistencies in behavior to rule out or imply some of these models.
We leave such higher-order deception and detection for future work.







§ REVIEW OF PRIOR WORK AND NOTATION

Review

This section briefly reviews key concepts and notation regarding
strategy complexes and relations.  Detailed discussions of strategies
and strategy complexes appear in <cit.>.
The connection of strategies to relations appears in
<cit.>.  Background material on topology may be found in
<cit.>, on posets in <cit.>,
and on privacy in <cit.>.




Assumption:  All graphs, relations, and simplicial
complexes in this report are finite.





 §.§ Graphs and Strategies

Graphs and Strategies


This subsection reviews material on strategies, taken fairly directly
from <cit.>, with some descriptions verbatim.






  
Nondeterministic and Stochastic Graphs: We are interested
in finite graphs, viewed as state spaces with errorful transitions.
We model any such graph G as a pair (V, ), consisting of a
finite set of states 1muV-2mu and a finite
collection of actions  .  Each action a∈
consists of a source  state v and a nonempty set
T-2mu of targets, with v ∈ V and ∅≠ T
⊆ V.

If T consists of a single state t, we say that the action
is deterministic.  We may write a deterministic action a as
vt, just like a directed edge in a directed graph.
If T contains more than one state, there are two
possibilities: The action is either nondeterministic  or stochastic.  We discuss each of these possibilities next.  We may
also regard a deterministic action as a special instance of a
nondeterministic action and/or as a special instance of a stochastic
action.

We write a nondeterministic action a as vT.  The
semantics of such an action are as follows: Action a may be executed
whenever the system is at state v.  When action a is executed, the
system moves from state v to one of the target states in T.   If
T > 1, then the precise target attained is not predictable in
advance, but is known after execution completes.  Different execution
instances of action a could attain different target states within
T.  An adversary might be choosing the target attained.

We write a stochastic action a as vp T, with
p a strictly positive probability distribution p : T
→ (0, 1], such that ∑_t∈Tp(t) = 1.

The semantics of a stochastic action are very similar to those of a
nondeterministic action, except that the target state attained at
execution time is now determined stochastically, according to the
probability distribution p, rather than nondeterministically.
Different execution instances of action a are assumed to be
independent of each other.

We say that a graph (V, ) is a pure nondeterministic
graph if all the actions in  are either deterministic or
nondeterministic.  We say that a graph (V, ) is a pure
stochastic1.5mu graph if all the actions in  are
either deterministic or stochastic.  This report is primarily
interested in such pure graphs.  However, see <cit.> for a
discussion of graphs with a mix of deterministic, nondeterministic,
and stochastic actions.  See also Section <ref>.

Suppose action a has source v and targets T.  We refer to each
possible transition v → t, with t∈ T, as
an action edge (of action a).




Comment:  We permit multiple actions to be distinct yet have
the same source v and the same target set T (and the same
probability distribution p if the actions are stochastic).  Such
duplication flexibility is useful, for instance when forming quotient
graphs (see page quotient).



  
Strategies and Strategy Complexes: We next define strategies and strategy complexes via a series of intermediate
concepts.  Intuitively, a strategy is a generalization of a control
law, now viewed as a mapping from states to sets of actions.

Let G=(V, ) be a graph as on
page strategies, and suppose ⊆.   We
view  as a generalized control law as follows: Suppose the
system is currently at state v.  The set  may contain zero,
one, or several actions with source v.  The system stops
moving precisely when  contains no action with source v.
Otherwise, the system must execute some action a∈
with source v.  If there are several such actions, any one of the
actions might execute, determined nondeterministically.  (Worst-case,
an adversary might make the choice.  In Section <ref>, perhaps
sometimes a boat's skipper could.)  Upon execution of action a, the
system finds itself at one of the targets t of action a.  The
process then repeats, with t the system's new current state.

We are interested in only those control laws that eventually stop at
some state or states.  Intuitively, for pure nondeterministic graphs,
this means that executing any of the actions contained in  will
never cause the system to cycle (i.e., revisit a previously
encountered state).   For pure stochastic graphs, it means that no
subset of the actions contained in  forms a recurrent Markov
chain.  We model these requirements with the following definitions,
again taken fairly directly from <cit.>:




Let G=(V, ) be a graph as on page strategies.







  * With a∈, let (a) denote the source of action
  a.  When ⊆, define 's source set 
  () as the set of all the individual
  actions' sources:  ()=1mu(a)a∈.


  * With a∈, let (a) denote the set of targets of
  action a.


  * Let W ⊆ V and a ∈.  We say
  that action a moves off  W (in G) if
  (a) ∈ W and one (or both) of the following is true: (i)
  action a is nondeterministic with all of its targets in V
  ∖ W, or (ii) action a is stochastic with at least one of
  its targets in V ∖ W.  (The two requirements are identical
  when a is deterministic.)


  * Let ⊆.  We say  contains a
  circuit  if, for some nonempty subset  of , no
  action of  moves off ().  We say  converges  or is convergent  if  does not contain a
  circuit.   Comment:  If  is convergent
  and V≠∅, then necessarily () ≠ V.


  * If V≠∅, then the strategy complex   of  G is the simplicial complex whose
  underlying vertex set is  and whose simplices are all the
  convergent subsets  of .  Every simplex of  is
  called a strategy.  The empty simplex ∅ is one such
  strategy, modeling no motion.  It appears in  whenever
  V-2.5mu≠∅.   If V-2.5mu=∅,
  then one would let  be the void complex, containing no
  simplices.   (This report will always require V≠∅.)


  * If σ is a strategy in , then
  V(σ) is called the goal  or goal
  set  of σ.  The goal set consists of all states in the
  graph at which σ does not specify a motion.  We may say that
  σ converges to  V(σ).   If
  the goal set is a singleton {v}, we may refer directly to state
  v as 1muσ's goal.


  * Suppose V≠∅.  We say that G is fully
  controllable if every nonempty subset of V-2mu is the
  goal set of some strategy in .  Observe that G is fully
  controllable if and only if every singleton state is the goal set of
  at least one maximal  strategy (simplex) in .


  * Topologically, G is fully controllable if and only if  is
  homotopic to the sphere , with n=V.   See
  <cit.>.



We will soon model strategy complexes via relations.  The maximal
simplices of a strategy complex will index the rows of the relation
and the graph's actions will index the columns.  Of interest will be
how to reveal the constituent actions of a maximal strategy in such a
way as to delay identification of the strategy for as long as
possible.




We end this subsection with two definitions that will be useful later
in the report:






  
Subgraphs: Suppose G=(V,) is a graph as on page strategies.

 By a subgraph 1muH-1.5mu of
4muG2mu we mean a graph H=(W, ) in its
own right such that W ⊆ V and ⊆.



  
Quotient graphs: Suppose G=(V,) is a graph as on
page strategies and suppose ∅≠ W ⊆ V.



We define the quotient graph  G/W =(V^',^')
as follows:






  * The state space is V^' =  (VW)  {}.

      Here  is a new state.  It represents the set of states
      W all identified to one state.[In this report,
      identify typically means
      determine identity of, but sometimes, as
      here, it means treat as same.]


  * The actions ^' are in one-to-one correspondence
  with the actions , but source and target states of actions
  in ^' are relabeled to match the new state space.
  Specifically, any source or target in VW remains
  unchanged, while any source or target in W-0.5mu becomes .
  
  The relabeling of targets may identify some or all of the targets of
  an action a∈.  For a stochastic action of the form
  vp T, with T  W -2mu ≠∅, one therefore sums the transition probabilities of the
  targets in T  W in order to determine the transition
  probability to state  of the relabeled action
  a^'∈^'.



  Comment: “one-to-one correspondence” means that distinct
  actions of  remain distinct in ^' even if their
  sources become the same and their target sets become the same (and
  even if their probability distributions become the same, in the
  stochastic case).





The following facts are easy to establish:





  * A convergent set of actions in G may contain a circuit once
one views the actions in G/W.   (In particular, individual actions
may become nonconvergent.)  However, the set of actions remains
convergent if its source set does not overlap W.


  * Any convergent set of actions in G/W-1.5mu will remain
convergent if one views the actions back in their original form in
G.


  * If G is fully controllable, then so is G/W.





  
Generalization: Suppose W_1, …, W_k are
nonempty pairwise disjoint subsets of V, with k ≥ 1.
 Let _1, …, _k be new and distinct states.  The
definition of quotient graph given above generalizes to this setting:
For each i=1, …, k, we identify all states of G that lie in
W_i to the single state _i.   We denote the resulting
quotient graph by G/{W_1, …, W_k}.







 §.§ Relations and Dowker Complexes

Relations and Dowker Complexes


This subsection reviews material on relations, taken fairly directly
from <cit.>, with some descriptions verbatim.



Let X and Y be nonempty finite discrete spaces.  A relation
R on  is a set of ordered pairs constituting a subset of the
cross product .  We frequently view R as a matrix of blank and
nonblank entries, with X indexing rows and Y indexing
columns.  We often refer to elements of X-0.5mu as
individuals and to elements of Y-2.3mu
as attributes.

For each x∈X, we let Y_x be the set of attributes that
individual x has.  Formally, Y_x = 2muy∈
Y(x,y)∈ R.  We may view Y_x as the row of R0.75mu
indexed by x (or more precisely, as all the attributes with nonblank
entries in the row indexed by x).

Similarly, for each y∈Y, we let X_y be the set of individuals
who have attribute y, that is, X_y = 1mux∈
X(x,y)∈ R.  We may view X_y as the column of R0.5mu
indexed by y (or more precisely, as all the individuals with
nonblank entries in the column indexed by y).




Given a relation R, we define two simplicial complexes,  and
, as follows:



 is called the Dowker attribute complex.  It has
  underlying vertex set Y and is generated by the rows of R.

  is called the Dowker association complex.  It has
  underlying vertex set X and is generated by the columns of R.

 Thus:

    =_x∈ X<Y_x>    and    =_y∈ Y<X_y>.


(The symbol <σ> means the simplicial complex
generated by σ, that is, the collection of all subsets of
σ, including the empty simplex 2mu∅ and
σ itself.)





We define two interpretation maps, ϕ_R and ψ_R, as
follows:





    ϕ_R(σ)    =   _x∈σY_x,     for any σ⊆X,
    ψ_R(γ)    =   _y∈γX_y,     for any γ⊆Y.





Thus ϕ_R(σ) consists of all attributes shared by at least
all the individuals in σ, while ψ_R(γ) consists of
all individuals who each have at least all the attributes in γ.



Observe that ϕ_R(∅) = Y and ψ_R(∅) = X.



One may regard ϕ_R both as an interpretation map as well as a
test for membership in the Dowker complex .  Specifically, for
all σ⊆X, σ∈ if and only if
ϕ_R(σ)≠∅.  Moreover, if
∅≠σ∈, then
∅≠ϕ_R(σ)∈.



Similarly, for all γ⊆Y, γ∈ if
and only if ψ_R(γ)≠∅.  And
∅≠ψ_R(γ)∈ whenever
∅≠γ∈.




We say that individual x ∈ X is identifiable
via 0.5muR1.5mu whenever ψ_R(Y_x) = {x}.  In
other words, an individual x is identifiable when no other
individual's attributes include all of x's attributes.



The following facts are useful to remember <cit.>:




5.7in



  * Each of ϕ_R and ψ_R is inclusion-reversing.

  * For all γ⊆Y,   γ⊆()(γ).   Similarly for .

  * If γ is a maximal simplex of , then
  ()(γ)=γ.   Similarly for .

  * Each of the compositions  and  is idempotent.

  * ϕ_R ∘ψ_R ∘ϕ_R = ϕ_R.   Similarly with
  the roles of ϕ_R and ψ_R interchanged.






The maps ϕ_R and ψ_R define homotopy equivalences between
the two Dowker complexes <cit.>.  In particular, the
compositions  and  are homotopy equivalent to the
identity maps on their respective simplicial complexes.  These
equivalences allow one to construct a poset whose elements may be
viewed as pairs of sets (σ, γ) satisfying ∅≠σ = ψ_R(γ) ∈ and ∅≠γ =
ϕ_R(σ) ∈.  This poset has an encompassing lattice
structure and is amenable to topological analysis: When the poset has
high-dimensional homology, one can be assured that it contains long
chains.  We will not need the details of that poset construction in
this report.  Instead, we jump directly to one additional definition
that we will need:



  
Informative Attribute Release Sequences:

 An informative attribute release sequence (for relation R),
abbreviated as iars, is a nonempty set of attributes in
Y released in a particular sequential order





    y_1, y_2, …, y_k,   with k ≥ 1,

satisfying





    y_i ∉()({y_1, …, y_i-1}),   for all 1 ≤ i ≤ k.





In order to understand this last condition, recall from
<cit.> that ()(γ)γ, with
γ∈, is the set of all attributes inferable from
γ.  For instance, one may have directly observed attributes
γ for some unknown individual known to be modeled by relation
R.  Then the set of attributes ()(γ)γ is
inferable without direct observation.  Thus the condition above
requires that no attribute y_i in the sequence be inferable from the
attributes y_1, …, y_i-1 released before y_i.  In
particular, y_1 must not be inferable “for free”, i.e., without
observation.  (The cone apex _1 of the complex in
StreamNarrowLimitedRelationComplex on
page StreamNarrowLimitedRelationComplex was inferable for
free and thus would never appear in an informative attribute release
sequence for the relation in that figure.)



Comment:  An informative attribute release sequence y_1, y_2,
…, y_k might not form a simplex in , but any proper prefix
of the sequence will.  It may at first seem counterintuitive to have
a nonsimplex be informative, but the inconsistency one obtains with
the last attribute released may provide information in some relation
containing R, as discussed in <cit.>.



Of interest in some privacy settings is how long one can delay
identifying an individual while revealing information: Given an
individual x, how large can one make k in defining an informative
attribute release sequence y_1, y_2, …, y_k for which
ψ_R({y_1, …, y_k}) = {x}?  Topology offers lower bounds
<cit.>.  In this report, we will consider that question
with strategies in place of individuals and actions in place of
attributes.  We will argue from first principles.






  
Relations from Complexes: Suppose
Γ is a nonvoid simplicial complex with underlying vertex set
Y≠∅.  We can define a relation R on
×Y, with  the maximal simplices of
Γ:

    R = (γ, y)y ∈γ∈.

One readily sees that = Γ.

  (See footnote
[Void vs. Empty: The void complex  is the simplicial
  complex Γ=∅, containing no simplices.  In contrast,
  the empty complex  is the simplicial complex
  Γ={∅}, containing a single simplex, namely the empty simplex  ∅.  One may construct R1mu from
  the empty complex, assuming 1muY-4mu≠∅.  In
  that case, ={∅}, R=∅, and =
  {∅} = Γ.]

for a side comment.)




Observe that every maximal simplex of Γ, i.e., every
γ∈, is identifiable via relation R.






  
Action Relations: Suppose G=(V, ) is a graph as
on page strategies, now with both V-3.65mu ≠∅ and 1mu≠∅.   We may substitute
 for Γ in the previous construction to obtain a relation
on ×, with  the maximal simplices of
.  We refer to such a relation as an action relation, or
more specifically, as graph G's -1muaction relation.
In an action relation, maximal strategies[The term maximal strategy (in 2muG-1mu or
1mu) is synonymous with maximal simplex (in
).]  play the role of individuals while actions play the
role of attributes.  The strategy relations of Section <ref>
were of this form, though there we were only considering subcomplexes
of the full strategy complex.




In this context, informative attribute release sequences
become informative action release sequences.

 We may thus ask the question:






4in
How many actions can one reveal informatively before one has
identified a maximal strategy?







  
Caution: The order via which actions are revealed in an
informative action release sequence need not correspond to the order
in which actions might be executed at runtime.






  
Terminology: Let G be a graph as on
page strategies.   We will make statements of the form
“maximal strategy σ in G1.5mu contains informative
action release sequence a_1, a_2, …, a_k”.  This statement
means that the following three conditions hold:






5.65in

-4pt

  (a) σ is a maximal simplex in .

  (b) {a_1, a_2, …, a_k}⊆σ.

  (c) a_1, a_2, …, a_k2mu is an informative
  attribute release sequence for G's action relation.





In particular, the order of the actions 1mua_1, a_2, …,
a_k1mu is significant.  If we view the same set of actions in a
different order we obtain a different sequence.  Consequently, a
statement of the form “σ contains k! different informative
action release sequences” has meaning even when σ=k.  (Caution: A permutation of an informative attribute release sequence
need not itself be an informative attribute release sequence.  See
page permsnotiars.)



 §.§ Minimal Nonfaces

Minimal Nonfaces


Suppose Γ is a simplicial complex with underlying vertex set
Y.  A minimal nonface of (or in) Γ is a subset of
Y that is not itself a simplex in Γ but all of
whose proper subsets are simplices in Γ.



If we arrange the vertices of a minimal nonface in any order, we
obtain an informative attribute release sequence.  That fact is the
content of our first lemma:


 Let R be a relation on , with both X and
Y nonempty.

Suppose κ is a minimal nonface of .  Then any
ordering of the attributes in κ is an informative attribute
release sequence for R.



Suppose the lemma fails for some minimal nonface κ of .
Necessarily, κ≠∅.  Let k = κ.  Then,
for some ordering y_1, y_2, …, y_k of the attributes in
κ, y_k must be implied by y_1, …, y_k-1 (if k=1,
this means y_1 is inferable “for free”).  Since κ is a
minimal nonface of , {y_1, …, y_k-1} is a simplex in
.  Thus {y_1, …, y_k-1}⊆()({y_1,
…, y_k-1})∈.  By supposition, y_k∈()({y_1,
…, y_k-1}).  Consequently, κ⊆ ()({y_1,
…, y_k-1}) ∈, contradicting the assumption that
κ is a nonface of .





Suppose all individuals in a relation R are identifiable.  Then all
rows of R are distinct and each row forms a maximal simplex in the
attribute complex .  Suppose an observer has observed
attributes η for some unknown individual x known to be modeled
by relation R.  Even if η is a proper subset of Y_x, it is
possible that η identifies x, meaning ψ_R(η)={x}.  In
that case, Y_x is the only maximal simplex containing η.
Conversely, if the observed attributes η do not identify
individual x, then η must be contained in some maximal simplex
besides Y_x.  Thus there exists an attribute y that is not one of
x's attributes but that is consistent with all the observed
attributes η of x, meaning η{y}∈.  The
following lemma characterizes this situation more generally for a
simplicial complex, in terms of minimal nonfaces.



Suppose Γ is a simplicial complex with underlying vertex set
Y.

 Let γ be a maximal simplex of Γ and let
y∈ Y such that y∉γ.  Define





    = κ⊆γ{y}κ is a minimal nonface of Γ.





Suppose η⊆γ.

Let η^' = η{y}.




Then η^'∈Γ  if and only if  
κη^'≠∅ for every
κ∈.



Comments:  (i) -2mu≠∅, since γ is a
maximal simplex in Γ and y∉γ. 
(ii) If {y}∉Γ, then  consists solely of {y}
and {y}η^'=∅, no matter what η is.
Indeed, no η^' can be in Γ.

(iii) If {y}∈Γ, then γ cannot be the empty simplex.
Every κ∈ now contains at least two vertices, namely y
and some element of γ.  Therefore the lemma's assertion for
η=∅ is clear.

(iv) More generally, the lemma says: Even though vertex y cannot
enlarge simplex γ, it may be able to enlarge a face η of
γ.  Such enlargement is possible precisely when the enlarged
set contains no minimal nonfaces of the type described by .


Suppose η^'∈Γ.  If for some κ∈,
κη^'=∅, then η^' would
contain κ as a minimal nonface, a contradiction.  Now suppose
η^'∉Γ.  Then η^' must contain some
minimal nonface, necessarily a set κ in  since
η^'⊆γ{y}.  Thus
κη^'=∅.





  
Minimal Nonfaces in a Strategy Complex: 
Specializing to minimal nonfaces of a strategy complex yields
additional results, as discussed below.


 Let G=(V,) be a graph as on page strategies, with
1muV≠∅.

Suppose κ is a minimal nonface of .  Then the actions
in κ all have distinct sources and no action in κ moves
off (κ) in 1.5muG.



Let k = κ.   Since V≠∅, k>0.

Write κ = {a_1, …, a_k}.  For each i=1,…,k,
define κ_i = κ{a_i}, that is, remove one
action from κ.  Then κ_i∈, for i=1,…,k.
Thus, for every ∅≠τ⊆κ_i, some action in
τ must move off (τ).  On the other hand,
κ∉, so for some ∅≠ξ⊆κ, no
action in ξ moves off (ξ).  Consequently ξ=κ,
establishing the second assertion of the lemma.

The first assertion is trivial if k=1, so assume k>1 and suppose
(a_1)=(a_2).  Then
(κ)=(κ_1)=(κ_2).  Some action in
κ_1 moves off (κ_1)=(κ).  That contradicts
the previous paragraph, thereby establishing the first assertion of
the lemma.





  
Interpreting Minimal Nonfaces in Strategy Complexes: 
Let us examine the meaning of minimal nonfaces for the two types of
pure graphs discussed in this report.  Assume the notation of
Lemma <ref> and its proof.







  * Suppose G is a pure nondeterministic graph.  Inductively,
  Lemma <ref> produces a cycle of actions a_1,
  …, a_k, such that (a_i+1) ∈(a_i), for i=1,
  …, k (here indices wrap around, so that a_k+1 again means
  a_1).  Moreover, for each action a_i, exactly
  one of the action's targets lies in (κ);
  any additional targets lie outside (κ).  (Otherwise, one
  could create a shorter cycle and thus a proper subset of κ
  would be a nonface of .)


  * Suppose G is a pure stochastic graph.  In the definition of
  “moves off” from page movesoff, the quantification over
  targets is different for stochastic actions than for
  nondeterministic actions.  Consequently, Lemma <ref>
  now implies that all  targets of every action in
  κ must lie within (κ).  One may therefore create a
  subgraph H of G defined by H=((κ), κ).  One sees
  that κ is also a minimal nonface in , that  is
  the boundary complex[The boundary complex on the set
  Z (with Z finite) is the simplicial complex whose underlying
  vertex set is Z and whose simplices are all the proper subsets of
  Z.] on the set κ, and that H is a fully controllable pure
  stochastic graph.  In fact, H defines an irreducible Markov chain
  <cit.>.







 §.§ Sample Graphs, Relations, and Informative Action Release Sequences


This subsection provides examples of graphs, action relations, and
strategy complexes, along with discussion of the extent to which
strategy or goal identification may be delayed.  (Actions here are
deterministic or nondeterministic.  Stochastic actions appear in
Sections <ref> and <ref>.)



  §.§.§ A Directed Cycle Graph

A Directed Cycle Graph




As a first example, consider the directed graph G in the left panel
of CycleGraph4.  The graph contains four states and four
directed edges.  (The directed edges represent deterministic actions.)
These edges form a directed cycle.  Any proper subset of the four
directed edges does not form a cycle.  Consequently, any set of three
directed edges forms a strategy, in fact a maximal strategy, that
converges to one of the states in the graph, from any other state in
the graph.  For instance, the strategy σ_4, consisting of the
set {e_1, e_2, e_3} of directed edges, converges to state #4, for
any initial starting state of the system.




Comment: Any subset of a maximal strategy is also a strategy,
since it too will be acyclic.  For instance, the set of directed edges
{e_1, e_4} is a strategy that stops at either state #2 or state
#3.  (The precise stopping point depends on the starting point during
a particular execution of the strategy.)  The set {e_1, e_4} is a
strategy but it it is not  a maximal  strategy.




The middle panel of CycleGraph4 shows graph G's action
relation, describing each maximal strategy by its constituent actions.
For each state v, there is a maximal strategy σ_v converging
to that state from anywhere else in the graph.  Therefore, G is
fully controllable.  The strategy complex  is in fact generated
by four such maximal strategies, each consisting of three directed
edges.  Consequently, the strategy complex is a hollow tetrahedron, as
shown in the right panel of the figure.  In particular, the strategy
complex contains a single minimal nonface, namely the set {e_1, e_2,
e_3, e_4}, consisting of all four directed edges (actions) in the
graph.




There are no free faces in the strategy complex, so it is impossible to
infer any actions of a strategy from any actions revealed —
“attribute privacy is preserved” <cit.>.  Thus
it is impossible to identify a maximal strategy uniquely if one knows
only a proper subset of its actions.

Each maximal strategy consists of three actions and has no free faces.
Consequently, each maximal strategy contains 3! different
informative action release sequences that identify the strategy, and
each such sequence has length 3.  For instance, the six sequences for
strategy σ_4 are:





    e_1, e_2, e_3       e_2, e_3, e_1       e_3, e_1, e_2 
    
    e_3, e_2, e_1       e_2, e_1, e_3       e_1, e_3, e_2.







  
Ability to Delay Strategy Identification: 

Let G=(V,) be a fully controllable graph with n=V > 1.
The following property holds <cit.>: For every state
v∈V, there is some maximal strategy σ_v∈ such that
σ_v has goal v and contains at least (n-1)! different
informative action release sequences of length at least n-1 each.

 For each such sequence a_1, …, a_ℓ, this means the
following: An observer cannot infer (via G's action relation) that
σ_v contains action a_i merely from knowing that σ_v
contains the set {a_1, …, a_i-1} of actions appearing
earlier in the sequence.  In particular, an observer cannot identify
σ_v uniquely before seeing all actions in the sequence a_1,
…, a_ℓ.   Moreover, ℓ≥ n-1.




Comment:  In the example of CycleGraph4, the six
informative action release sequences of length 3 within each maximal
strategy were permutations of the strategy's three constituent
actions.  In general, the 0.75mu(n-1)!1mu different
sequences need not be permutations of each other.







  §.§.§ A Graph with a Subspace Cycle

A Graph with a Subspace Cycle



As a second example, let us consider a graph with a directed cycle
merely on a proper subset of the state space, as shown in
Ex202b_Graph.  The graph again consists of four states.  The set
of deterministic actions {e_1, e_2, e_3} forms a directed cycle on
the set of states {1, 2, 3}.  In addition, there is a
deterministic action a_2 that moves off this cycle space,
specifically from state #2 to state #4.  Finally, there is a
nondeterministic action b_4 that moves from state #4 back to the
set of target states {1, 2, 3}.  (To say that the action is
nondeterministic means that the precise target state attained cannot
be predicted in advance, not even stochastically.)



The actions e_1, e_2, and e_3 form a directed cycle.  Any two of
these actions form a convergent strategy.  The remaining two actions,
a_2 and b_4, taken together, could cause the system to cycle
between states #2 and #4.  Any one of these actions is convergent by
itself.  Therefore, the two sets of actions {e_1, e_2, e_3} and
{a_2, b_4} each form a minimal nonface in the strategy complex
.  In fact, these are the only minimal nonfaces in the strategy
complex.  They are independent of each other.  Consequently, G's
strategy complex is the simplicial join of the boundary of the
triangle {e_1, e_2, e_3} and the boundary of the edge {a_2,
b_4}.  In other words,  is a suspension
<cit.> of a triangle boundary.
Ex202b depicts this complex along with G's action relation.
Observe that the complex is homotopic to , consistent with G
being fully controllable.






As in the example of Section <ref>,  contains no
free faces.  So, again, it is impossible to identify a maximal
strategy uniquely from a proper subset of its constituent actions.



One salient difference between this example and the previous one is
that some maximal strategies now have goal sets with more than one
state in them.  For instance, strategy σ_34, consisting of
actions {e_1, e_2, a_2} has goal set {3, 4}.  This multi-state
goal arises because the actions e_1 and e_2, taken together,
converge to state #3 assuming the system state lies within
the subset of states {1, 2, 3}.  However, if the starting state
happens to be state #4, then the system will simply remain at that
state.  Consequently, the strategy {e_1, e_2} has goal set {3,
4}.  That strategy is not itself maximal.  One can augment it either
with action b_4, in which case the resulting maximal strategy would
be σ_3, converging to state #3.  Or one can augment {e_1,
e_2} with action a_2 to produce σ_34.  Adding action
a_2 introduces some nondeterminism at state #2, but nothing that
changes the overall goal set; it remains {3, 4}.





  
Informative Action Release Sequences: 
As in the example of Section <ref>, the longest
informative action release sequences within each maximal strategy in
 are simply permutations of the strategy's constituent actions.
Whenever a maximal strategy has no free faces, one can release its
actions in any order without definitively identifying the strategy
before all actions have been released.

In order to understand the more general picture, suppose we simply
interchange the roles of strategies and actions in this example.  The
“individuals” are now e_1, e_2, e_3, a_2, b_4 and the
“attributes” are σ_1, σ_2, σ_3, σ_4,
σ_14, σ_34.  We are thus interested in the Dowker
association complex  of the original action relation.  That
complex appears in Ex202b_dowAx.
 (Comment: We are not asserting that this complex
is the strategy complex of a fully controllable graph, merely using
the complex to illustrate a point. One can however construct fully
controllable graphs with strategy complexes that make the same
underlying point: permutations of informative attribute release
sequences need not themselves be informative attribute release
sequences.)



Each maximal simplex of  continues to offer (at least) 3!
different informative release sequences of length 3 each, with
elements in each sequence drawn from the simplex's vertices.  Two of
the maximal simplices (namely, the “endcaps” in the figure) are
solid triangles with no free faces, so their sequences are again
simply permutations of each other.  Three of the maximal simplices are
solid tetrahedra.  The undrawn “diagonals” of these tetrahedra are
free faces, so releasing their endpoints would completely identify the
tetrahedron.  For instance, releasing vertices σ_1 and
σ_4 identifies the tetrahedron labeled e_3.  Consequently,
one cannot simply choose arbitrary sequences of length 3 and expect
them to be informative.  Nonetheless, each tetrahedron does contain 16
informative release sequences of length 3.  Here are the sequences for
the tetrahedron labeled e_3:


    [  σ_1, σ_2, σ_4  σ_2, σ_1, σ_4 σ_1, σ_2, σ_14 σ_2, σ_1, σ_14; σ_4, σ_14, σ_1 σ_14, σ_4, σ_1 σ_4, σ_14, σ_2 σ_14, σ_4, σ_2; σ_1, σ_14, σ_4 σ_14, σ_1, σ_4 σ_1, σ_14, σ_2 σ_14, σ_1, σ_2; σ_2, σ_4, σ_14 σ_4, σ_2, σ_14  σ_2, σ_4, σ_1 σ_4, σ_2, σ_1. ]








  
Incorporating Additional Constraints: 

Suppose, in some context, the system only executes strategies that
converge to singleton goals.  From an inference perspective, the
action relation A and strategy complex  of Ex202b would
be misleading.  To understand the possible inferences, one should
consider a relation  that models all the maximal strategies
with singleton goal sets, and only those, as shown in
Ex202btruncated.




With this added information, it is no longer true that one can find
6 different informative action release sequences of length 3
within every maximal strategy.  For instance, action a_2 identifies
strategy σ_4.  Consequently, as soon as one releases that
action, the other two actions in σ_4, if not previously
released, would be implied.  As a result, there are only two
informative action release sequences of length 3 for identifying
strategy σ_4, namely e_1, e_3, a_21mu and e_3, e_1,
a_2.

Similarly, action e_2 implies action b_4, again limiting the
ordering of any sequences containing both those actions.  Strategy
σ_1 now contains only three, rather than six, informative
action release sequences of length 3, namely:





    e_3, b_4, e_2      b_4, e_3, e_2      b_4, e_2, e_3.







  
Ability to Delay Goal Identification:
Suppose G=(V,) is a fully controllable graph with n=V>1.
The following property holds <cit.>: 
For every state v∈V, there is some maximal strategy
τ_v∈ such that τ_v has goal v and contains an
informative action release sequence whose sequential release leaves
the goal ambiguous at least until all actions in the sequence have
been revealed.   Moreover, the sequence reduces the goal ambiguity by
at most one state with each action revealed, so the sequence has
length at least n-1.

One sees this property in the complex of Ex202btruncated since:
(i) every maximal simplex contains a vertex shared by three strategies
with different goals and (ii) the vertex lies within one of the
simplex's edges that is shared by two strategies with different goals.




  §.§.§ An Augmented Cycle Graph

An Augmented Cycle Graph

Let us augment the graph of CycleGraph4 with two nondeterministic
actions, as shown in Ex200_Graph.  The actions are a_1 =
1→{2, 3} and a_2 = 2→{3,
4}.




The new graph  has a strategy complex  described by the
action relation  shown in Ex200_Graph.  The complex is a
partially puffed up version of the hollow tetrahedron from
CycleGraph4, now consisting of three solid tetrahedra and two
solid triangles glued together to enclose an  hole.
Ex200_1skel shows the 1-skeleton of this complex.

The maximal strategies from the original strategy complex  are
still present in .  Two of these strategies now lie within
larger maximal simplices.  For instance, strategy σ_2 for
attaining goal state #2 in the original graph G consisted of the
actions {e_1, e_3, e_4}, whereas now the corresponding maximal
simplex _2 consists of the actions {e_1, e_3, e_4, a_1}.
The original strategy σ_2 always executed action e_1 when the
system was at state #1, thus transitioning to state #3.  In the new
graph , the new _2 might execute either action e_1 or
action a_1 at state #1, selected nondeterministically (possibly by
an adversary).  Action a_1 will transition either to state #2 (the
goal) or to state #3.  (If an adversary controls the outcome of
action a_1, then the adversary might choose to make action a_1
mimic action e_1, in which case the old σ_2 and the new
_2 would behave equivalently.)

Actions e_2 and e_4 both appear in both the original strategies
σ_1 and σ_3 of .  In the new graph , the set
{e_2, a_1} contains a circuit, as does the set {e_4, a_2}.
Consequently, one cannot augment the strategies σ_1 and
σ_3 with either of the actions a_1 or a_2.  These
strategies remain unchanged as one passes from G to , that is,
_1 = σ_1 and _3 = σ_3.

There are five maximal strategies in the new graph, whereas there were
four previously.  New strategy _5 has the same goal state,
namely state #4, as does strategy _4, but arrives there with
different actions, trading off action e_2 for action a_1.  The
minimal nonface {e_2, a_1} of  hints at this
possible tradeoff.



The ability to delay strategy identification mentioned on
page stratdefer, as well as our analysis of the original
graph G, ensures that each of _1, _2, _3, _4
contains (at least) 6 informative action release sequences of length
(at least) 3 each.  What can we say about strategy _5?

Releasing both of the two nondeterministic actions a_1 and a_2
identifies _5.  Releasing either one of these actions implies
both deterministic actions in _5.  Consequently, one obtains
the longest possible informative action release sequences within
_5 by first revealing the two deterministic actions (in either
order) and then the two nondeterministic actions (in either order).
Here are the four possible longest informative action release
sequences within _5:





    e_1, e_3, a_1, a_2      e_1, e_3, a_2, a_1 
               e_3, e_1, a_1, a_2      e_3, e_1, a_2, a_1.


(The previous reasoning can be generalized and formalized using
lattice representations of links, as discussed in
<cit.>, but we will not develop or use that machinery in
this report.)







  
Informative Action Release Sequences for Maximal Strategies in Pure Graphs:

Suppose G is a fully controllable graph containing n states, with
n > 1.  Suppose further that G is either pure nondeterministic or
pure stochastic.  The remainder of this report will provide proofs
that every  maximal strategy in G contains at least one
informative action release sequence of length at least n-1.  The
proofs will be different for the two types of graphs.  This property
need not hold for graphs containing a mix of nondeterministic and
stochastic actions.  See <cit.> and Section <ref>
for counterexamples.







§ BASIC TOOLS

Basic Tools


Graphs and strategies were defined in Section <ref>.

 We wish to prove the following theorem:


0


Let G=(V,) be a fully controllable graph with n = V >
1.  Suppose that G is either pure nondeterministic or pure
stochastic.

 Then every maximal strategy in  contains an informative action
release sequence of length at least n-1.


Section <ref> will prove Theorem <ref> for the pure
nondeterministic case, while Section <ref> will prove
Theorem <ref> for the pure stochastic case.

This section builds some tools that are useful for both settings.
Throughout this section the graph G may in fact contain a mix of
deterministic, nondeterministic, and stochastic actions.




  
Terminology and Notation:



  * We frequently abbreviate informative action release
  sequence as iars, for both the singular and plural cases.


  * If G is a graph, the phrase a_1, …, a_k is an iars
  for G means that a_1, …, a_k is an informative action
  release sequence for G's action relation as defined on
  page actionrelation.


  * Suppose G=(V,) is a graph and
  G^'=(V^',^') is some quotient graph of G.
  Recall from page quotient that the sets of actions
   and ^' are in one-to-one correspondence.
  Corresponding actions a∈ and a^'∈^'
  differ only in that the source and/or target states of action
  a^' may have changed from those of action a in order to
  reflect the quotient graph's state identifications.  One may
  therefore view any action of G^' in the form a^', with
  a being the unique action of G corresponding to a^'.    We will use this prime notation from now on.






Our first tool allows us to combine two strategies when one of the
strategies comes from a subgraph and the other comes from a quotient
graph formed by collapsing that subgraph to a single state.


  Let G=(V,) be a graph and let H=(W,) be a subgraph of G.

 (As always, both V-4mu and W-4mu are assumed to be nonempty.)      



If σ^'∈ and γ∈,
      then σγ∈.



(Prime notation indicates corresponding actions in a graph and a
quotient, as discussed.)


Comment: Since all sources and targets of actions in γ lie
within W, no such action is convergent in the quotient graph
G/W. Therefore σγ=∅.


Suppose ∅≠τ⊆σγ.  We need to
show that some action of τ moves off (τ) in G.



If 1mu(τγ)W=∅, then
this assertion follows from Lemma 7.3(b)(i) in <cit.>.



Otherwise, let κ = τγ.  Then
∅≠κ^'⊆σ^'∈, so some
action b^' in κ^' moves off (κ^')
in G/W.  If b^' is nondeterministic, then all its targets lie
in the set

((VW){})(κ^').

If b^' is stochastic, then at least one of its targets lies in
that set.  (As usual, 0.5mu represents
.75muW-1.5mu identified to a single state in
1muG/W.)   Since 0.1muκ0.4mu contains an
action with source in W-1.5mu, 1muκ^'
contains an action with source .   Thus

((VW){})(κ^')
 = 
V(W0.5mu(κ^'))
 = 
V(W1mu(κ))
 ⊆ 
V(τ).
That means action b lies in τ and moves off (τ) in G.


The next lemma ensures that unquotienting a simplicial informative
action release sequence (iars) again produces an informative action
release sequence, when the quotienting is over a proper subspace that
is fully controllable.


  Let G=(V,) be a graph

      and let H=(W,) be a fully controllable subgraph of G,
      with ∅≠ W ⊊ V.



Suppose a^'_1, …, a^'_k is an iars for G/W, with
{a^'_1, …, a^'_k}∈ and k ≥ 1.



Then a_1, …, a_k is an iars for G.



Let A be G's action relation.  We need to show that





    a_i ∉()({a_1, …, a_i-1}),   for i=1, …, k.


Suppose this assertion is false for some i.  Then a_i is contained in every
maximal simplex of  that contains {a_1, …, a_i-1}.




Let ^' be the actions of the quotient graph G/W.  Since
a^'_1, …, a^'_k is an iars for
.5muG/W-.5mu and {a^'_1, …, a^'_k}∈, there exist actions τ^', with
∅≠τ^'⊆^'{a^'_1,
…, a^'_i}, such that





    {a^'_1, …, a^'_i-1}τ^'∈    but    {a^'_1, …, a^'_i}τ^'∉.


Let η^' be a minimal nonface of  contained in
{a^'_1, …, a^'_i}τ^'.

(Since {a^'_i}∈, η^' contains at least two
actions, one of them being a^'_i.)

 By Lemma <ref> on page minnonfacestrat, no
action of η^' moves off (η^') in G/W.




We consider two cases below, deriving a contradiction for each.

By Lemma <ref>, there are no further cases.




State  represents W-1.5mu identified to a single state
in the quotient graph G/W, as per page quotient.






  I: No action in η^' has source : 

Then (η) = (η^'), so no action of η moves
  off (η) in G.

On the other hand, {a_1, …, a_i-1}τ∈, by
  Fact 2 on page quotientfacts.
  So {a_1, …, a_i}τ∈, by the falsity assumption above.  Since
  η⊆{a_1, …, a_i}τ, that means
  ∅≠η∈ and some action of η must move off
  (η) in G, a contradiction.



  II: Exactly one action in η^' has source
  : 

Suppose the source of the corresponding action in G is w.  Then
  w∈ W.  Let κ = ηγ, with γ∈ a
  strategy that attains w from anywhere in W-2mu using
  actions of H.  Then (κ) =
  ((η^'){})  W.  Since
  no action of η^' moves off (η^') in
  0.5muG/W-1.5mu and since γ has all its sources
  and targets in W, no action of κ moves off (κ)
  in G.

Since {a^'_1, …, a^'_i-1}τ^'∈ and γ∈, Lemma <ref> on
page unquotienting implies that {a_1, …, a_i-1}τγ∈.  By the falsity assumption,
{a_1, …, a_i}τγ∈.  Now
κ⊆{a_1, …, a_i}τγ, so
∅≠κ∈, and some action of κ must move off
(κ) in G, again a contradiction.










  
Combining Informative Action Release Sequences: 
The next lemma shows how one may combine an iars in a graph with an
iars from a subgraph.  The subsequent corollary leverages this result
with those discussed earlier, showing how one may combine an iars from
a quotient graph with an iars from a fully controllable subgraph.
That combinability forms a stepping stone in several proofs during the
rest of the report.





  Let G=(V,) be a graph and let H=(W,) be a
subgraph of G (with both 1muV-4.5mu and
1.2muW-4mu nonempty).




Suppose a_1, …, a_k, with k ≥ 1, is an iars for
G, such that:




4in

   -3pt

   
  (i) a_i ∈, for i=1, …, k, and

   
  (ii) {a_1, …, a_k}τ∈, for every τ∈.







Suppose b_1, …, b_ℓ is an iars for H, with
{b_1, …, b_ℓ}∈ and ℓ≥ 1.




Then 1mua_1, …, a_k, , …, b_ℓ
is an iars for G,

with {a_1, …, a_k, , …, b_ℓ}∈.


Comment: The lemma also holds when k=0, meaning every
iars for H is also an iars for G.


Suppose the iars part of the assertion is false.  Let A be G's
action relation.



Then, for some i∈{0, 1, …, ℓ - 1},
 b_i+1∈()({a_1, …, a_k, , …, b_i}).

(When i=0, this notation means b_1∈()({a_1, …,
a_k}).)

Consequently, every maximal simplex of  containing {a_1,
…, a_k, , …, b_i} also contains b_i+1.



Since b_1, …, b_ℓ is an iars for H's
action relation, there exists a maximal simplex τ∈ such
that {b_1, …, b_i}⊆τ but {b_1, …,
b_i+1}⊈τ.



By assumption, {a_1, …, a_k}τ∈.
Consequently, {a_1, …, a_k, b_i+1}τ∈.
Thus τ{b_i+1} = ({a_1, …, a_k,
b_i+1}τ) ∈, contradicting the maximality
of 1muτ in .







 Let G=(V,) be a graph and let H=(W,) be a fully
controllable subgraph of G with ∅≠ W ⊊ V.



Suppose a^'_1, …, a^'_k is an iars for G/W, with
{a^'_1, …, a^'_k}∈ and k ≥ 1.



Suppose further that b_1, …, b_ℓ is an iars for H, with
{b_1, …, b_ℓ}∈ and ℓ≥ 1.



Then 1mua_1, …, a_k, , …, b_ℓ is an iars
for G,

with {a_1, …, a_k, , …, b_ℓ}∈.



By Lemma <ref>, a_1, …, a_k is an iars for
G.  By Lemma <ref>, {a_1, …, a_k}τ∈, for every τ∈.  Since actions of H become
self-loops in G/W, a_i∉, for i=1, …, k.  The
desired result therefore follows from Lemma <ref>.


Comment:  The corollary also holds if one of k or ℓ is 0.







§ THE NONDETERMINISTIC SETTING

The Nondeterministic Setting


The aim of this section is to prove Theorem <ref> from
page longiars for the case in which the graph G is pure
nondeterministic.  Throughout, this section assumes that all graphs
are pure nondeterministic, meaning each action is either deterministic
or nondeterministic (but not stochastic).

 First, we need some additional definitions and results.





 §.§ Hierarchical Cyclic Graphs

Hierarchical Cyclic Graphs

We start with a recursive definition:


 A pure nondeterministic graph 3muG=(V,) is a
hierarchical cyclic graph if one of conditions
(i) or (ii) holds:



  (i) V=1 and 4.5mu=∅.


  (ii) There exist V_1, …, V_k, _1, …,
            _k, a_1, …, a_k, with k > 1, such that:

  


   
   2pt

    
  * V_1, …, V_k are nonempty pairwise disjoint subsets of
    4muV and V=⋃_i=1^kV_i.

    
  * _i consists of all actions in  whose sources
    and targets lie in V_i, for i=1, …, k.

    
  * (V_i,  _i) is a hierarchical cyclic graph, for i=1, …, k.

    
  * = {a_1, …, a_k} 4.5mu ⋃_i=1^k_i.

    
  * For i=1, …, k, (a_i) ∈ V_i and 4mu(a_i) ⊆ V_i+1
          
 (here indices wrap around, so V_k+1 again means V_1).
   



The decomposition above need not be unique.  We implicitly assume a
specific decomposition when stating that a graph is hierarchical
cyclic.  We refer to it as the tree decomposition of
G.




A graph of type (i) is a leaf and a graph of type (ii)
is a node.




When G is a node, we refer to the subgraphs (V_1, _1),
…, (V_k, _k) in .09emG's tree decomposition as
the .06emchildren of G.  Each subgraph
1mu(V_i, _i) is itself either a leaf or a node, with
.07emparent (V, ).  When (V_i, _i)
is a node, we may then speak of its children, and so forth.
Transitively, we may therefore speak of all the nodes
and leaves within G (that includes (V, )).  Finally,
we may speak of the root of the tree decomposition of
1.75muG, meaning the node or leaf (V, ), i.e., G
itself.




For a graph of type (ii), the actions a_1, …, a_k are the
(top-level) cycle actions of G.  Similarly, if N is
any node within G, the cycle actions of N are the
top-level cycle actions of N when N is viewed as a hierarchical
cyclic graph in its own right.





  
Comments and Observations:



  * Given a hierarchical cyclic graph G of type (ii) as above, we can
  form the quotient graph G/{V_1, …, V_k} (see again
  page quotient).   This quotient graph has state space
  {_1, …, _k}, where _i represents all of
  V_i identified to a single state, for i=1, …, k.

  All actions in each _i become nonconvergent in G/{V_1,
  …, V_k} (actions in _i become self-loops on state
  _i), so we may ignore them.  In contrast, each action a_i
  turns into a deterministic transition a^'_i from
  state _i to state _i+1.

  We may therefore view the quotient graph G/{V_1, …, V_k} as
  the cycle graph

  


  
    _1   _2
             ⋯  _k
               _1

  (the first and last states in the diagram above are the same state,
   namely _1).



  * More generally, suppose G is a hierarchical
  cyclic graph and (W, ) is some node that appears within the
  tree decomposition of G.  We can form the quotient graph
  1.25muG/W.  The quotienting identifies all of
  0.5muW-2mu to a single state .  The actions
   become self-loops on state .  Technically,
  0.5muG/W-1.5mu includes these self-loops, but there is
  no harm ignoring them, thereby allowing us to view G/W-2mu
  as a hierarchical cyclic graph.  If (W, ) is G itself,
  then we may view 0.5muG/W-1.75mu as the leaf
  ({}, ∅).  Otherwise, the tree decomposition of
  1muG/W-1.5mu is largely unchanged from that of G,
  except that one node, along with the subtree rooted at that node,
  has now become a leaf, and any actions of G with source or target
  states in W-1mu have had those states relabeled as
  .  The only actions that become nonconvergent (by creating
  self-loops) are those in , which we now ignore and discard.


  * Conversely, suppose ({s}, ∅) is a leaf that
  appears in the tree decomposition of a hierarchical cyclic graph
  G=(V, ).  Suppose H=(W, ) is another hierarchical
  cyclic graph, with states and actions distinct from those of G.

  We can replace the leaf ({s}, ∅) with node H, to form
  a new hierarchical cyclic graph G = (V,
   ).

  Here V =  (V{s})  W.
 
   In forming  from , we have some choices:

  Suppose a=v→T is an action in .  We create a
  corresponding action a∈ as follows:

  


  

   
  * If v=s,  we let v be any  state
   in 0.5muW-2mu and define a=v→T.

   
  * If s∈ T,  we let S be any  nonempty subset of
   1muW-1.5mu and then define
   a=v→T, with T = 
   (T{s})  S.

   
  * In all other cases, a = a.

  


  * A special case of the previous construction
  is to replace a single state s in a hierarchical cyclic graph with
  a deterministic cycle on some new set of states, while adjusting all
  other actions of the encompassing graph accordingly.  Actions of the
  encompassing graph that used to start at s now start at an
  arbitrary state of the cycle.  Actions that used to have a
  transition to s now might transition to one or more states
  comprising the cycle.


  * Every hierarchical cyclic graph is fully controllable and each
  of its actions is convergent.


  * Conversely, the lemma below shows that every fully controllable
  pure nondeterministic graph contains a hierarchical cyclic subgraph
  with the same state space.   (There may be more than one such
  subgraph.)







Let G=(V,), with V-4mu≠∅, be a fully
controllable pure nondeterministic graph.  Then G contains a
hierarchical cyclic subgraph H=(V, ).



By strong induction on V.  The base case V=1 is clear,
so suppose V > 1.   

For every state v in V-2mu one can find a nonlooping deterministic action with target v (since G is fully
controllable and pure nondeterministic).  Backchaining such actions
produces a deterministic cycle  on some subspace W of V
(possibly all of V), containing at least two states.

Consider G/W = (V^', ^').  Here V^' = 
(VW)  {}, with  representing W.
 G/W is fully controllable (by Fact 3 on
page quotientfacts) and pure nondeterministic, with 0 <
V^' < V, so the induction hypothesis applies.  We
therefore obtain a hierarchical cyclic subgraph H^'=(V^',
^') of G/W.

We may now replace leaf ({}, ∅) in H^' with
cycle  on state space W.  When adjusting the encompassing
actions ^', we choose sources and targets so as to undo
any relabeling of states that occurred in forming G/W.  These
adjustments produce a hierarchical cyclic subgraph H=(V, ) of
G.






 §.§ Core Cycle Actions, Leaf Covers, Disruptive Sets of Actions

Core Cycle Actions, Leaf Covers, Disruptive Sets of Actions

Suppose H=(W,) is a hierarchical cyclic graph with W >
1.  Each state 1.5mut of W appears as a leaf
({t}, ∅) in the tree decomposition of 1.5muH and
has some parent node N=(U, ).  Some action c_t∈,
necessarily a cycle action of N, must be deterministic with target 1.5mut.  We refer to c_t as t's core cycle
action.  This action is determined uniquely by t and the tree
decomposition of H.  (H may contain multiple deterministic actions
with target t, but one and only one of those actions will be a cycle
action in the parent node of ({t}, ∅).)

With that construct in mind, we now make a series of definitions and observations.


Let H=(W,) be a hierarchical cyclic graph.  The set
 of  core cycle actions of H is


    = {  c_tt∈ W,       if W > 1      (with c_t-1mu  as defined above);
    ∅,       otherwise.       
    .







Let N be a node in a  hierarchical cyclic graph H.  We say that N
covers only leaves in H whenever each of N's children is a
leaf in H's tree decomposition.






Let H=(W,) be a hierarchical cyclic graph and suppose ⊆.  We say that  is disruptive (in H)
whenever the following condition is satisfied:




4.7in
For every node that covers only leaves in H,

at least two of the node's cycle actions are missing from .





  
Observations:

-2pt

  * When a hierarchical cyclic graph H=(W,) contains at least
  two states, = W.

  * A node covers only leaves in H if and only if all the node's
  cycle actions lie in .

  * The empty set of actions is always disruptive, even when H is a leaf.






 §.§ Cycle-Breaking Strategies

Cycle-Breaking Strategies

Sets of actions that do not contain any node's full set of cycle
actions are convergent and may be arranged informatively, as the
following definition and lemmas make precise.


 Suppose H=(W,) is a hierarchical cyclic graph.  A set of
actions τ⊆ is cycle-breaking (in
H) if, for each node N in the tree decomposition of H,
τ-1mu does not contain all of N's cycle actions.






Suppose τ is a cycle-breaking set of actions in a hierarchical
cyclic graph H.   Then τ∈.






By structural induction on the tree decomposition of H.  The lemma
holds if 0.5muH-0.5mu is a leaf, since only
τ=∅ is possible.   Otherwise, suppose the children of
1muH-1mu are (W_1, _1), …, (W_k,
_k).  Inductively, the lemma holds for the set of actions τ_i in the hierarchical cyclic graph (W_i, _i),
for i=1, …, k.   Let σ consist of the top-level cycle
actions of 1.2muH-0.2mu that are in τ.   Since
H/{W_1, …, W_k} is a directed cycle graph (see top of
page cyclequotient) and since τ is cycle-breaking,
σ^'∈Δ_H/{W_1, …, W_k}.   Thus, by
repeated application of Lemma <ref> on
page unquotienting, τ∈.







  
Caution: Not all strategies in a
hierarchical cyclic graph need be cycle-breaking (see
page Ex241_H1).





Suppose τ is a nonempty cycle-breaking set of actions in a
hierarchical cyclic graph H.   Then some ordering of all the
actions in 1muτ is an informative action release sequence
for H.




The proof will associate to each leaf and node of H an informative
action release sequence, with the sequence associated to the root of
H comprising all of τ.

For the purposes of this proof, it will be convenient to consider the
empty sequence of actions as an informative action release sequence.
Since τ is nonempty, the final sequence produced below will be
nonempty, satisfying the standard requirement of
page iarsdef that informative attribute release sequences be
nonempty.



Base Case:  Associate to each leaf of H the empty sequence.



Inductive Step:  Consider a node N of H and assume each child C
of N has an associated informative action release sequence
consisting of all the actions of τ that appear in the graph C.
View N as a hierarchical cyclic subgraph in its own right, and form
the quotient graph N^' obtained by identifying each child to a
singleton state.  The cycle actions of N create a deterministic
directed cycle in N^'.  This cycle forms a minimal nonface in
Δ_N^'.  By Lemma <ref> on
page minnonfaceiars, any sequential ordering of the directed
edges comprising this cycle forms an iars for N^', any proper
subset of which is convergent.  Let {a_1, …, a_ℓ} be the
set of N's cycle actions in τ, this being ∅ with
ℓ=0 when none of N's cycle actions lie in τ.  Since τ
is cycle-breaking, the reasoning just given implies {a^'_1,
…, a^'_ℓ}∈Δ_N^' and a^'_1, …,
a^'_ℓ is an iars for N^'.



Since the children of N are fully controllable subgraphs of N,
repeated application of Corollary <ref> on
page combinequotientgraphiars shows that a_1, …,
a_ℓ, c_1, …, c_m is an iars for N, with c_1,
…, c_m being some concatenation of all the informative action
release sequences associated to N's children.  Associate a_1,
…, a_ℓ, c_1, …, c_m to N.  Observe that this
iars consists of all actions of τ that appear in the graph N.

 Associated to H itself therefore is an iars consisting of all of
τ.






 §.§ Markings

Markings


Let H=(W,) be a hierarchical cyclic graph.  We will view each
node of H as being either marked  or unmarked.   Each
node is unmarked initially.  Later, we will define an algorithm that
marks nodes according to some criteria.   Once marked, a
node remains marked.



In order to consider marking a node N, we first require that each
child of N be either a leaf or an already marked node.  The
collection of marked nodes at any instant therefore defines a set
 of maximal marked nodes, consisting of those nodes
that are marked but have no marked parent.

 After some nodes have been marked, = {(W_1, _1),
…, (W_ℓ, _ℓ)}, for some ℓ≥ 1, with the
sets W_1, …, W_ℓ nonempty and pairwise disjoint.  We may
therefore form the quotient graph H/{W_1, …, W_ℓ}, which
we abbreviate as H/.  We view H/ as a
hierarchical cyclic graph, much as on page ignoreloops, by
discarding any actions that have become self-loops.



The process will be iterative, adding an additional node to the
collection of marked nodes with each step.  We abbreviate the notation
by writing ^(j) to mean the maximal marked nodes at the
j^th step, with j ≥ 1, and by writing H^(j)
to mean H/^(j).  We also define
^(0)=∅ and H^(0)=H.






  
Observation: Any node covering only leaves in H^(j)
corresponds to a node in H that is not yet marked but that could be
marked at the (j+1)^st step, and vice-versa.





 §.§ Forward Projections

Forward Projections

Strategies in a pure nondeterministic graph define partial orders.
One may view those partial orders as forward projections of possible
system states.


Let G=(V,) be a pure nondeterministic graph.  If
1muσ∈, then σ induces a partial
order ≥_σ on V as follows:



For each w,v ∈ V, w ≥_σ v if and only if either
w=v or there exist actions a_1, …, a_k ∈σ, with k
≥ 1, such that:




3.5in

-3pt

  (i) (a_1) = w,

  (ii) (a_i+1) ∈(a_i),  for i=1,…,k-1,  and

  (iii) v ∈(a_k).



Thus, w ≥_σ-0.75muv if and only if w is v or the
system might move from w to v while executing strategy σ

 (in the diagram below, a_i∈σ, v_i=(a_i), and
v_i+1∈(a_i), for i=1,…,k):





    w=v_1  
        v_2  ⋯ 
        v_k   v_k+1=v.

The partial order ≥_σ is well-defined since σ cannot
create any cycles.



Suppose G=(V,) is a pure nondeterministic graph.
Let σ∈ and ∅≠W⊆V.

  The  forward projection of W under σ is the set

    _σ(W)  = v ∈ Vw ≥_σ v,  for
        some w∈W.



In other words, _σ(W) consists of all states that the
system might pass through or stop at, assuming the system starts at
some state in W and moves according to strategy σ.  (In
some papers, forward projection refers only to the states the
system might stop at.  Here, forward projection includes
all states through which the system might move, including starting
states.)



0



Let H=(W,) be a hierarchical cyclic graph and suppose
τ∈.



Define = τ  and  = τ.




For each c∈, let J_c = _({t}), with t being
the unique target of action c.  Then:




(a) The sets in the family
    1mu{J_c}_c1mu∈1mu are pairwise
    disjoint.



(b) Suppose further that 2muτ is disruptive.  Let
c∈.  Write c = w → t.  Then  w∉J_c.


In words: We split the core cycle actions  of H into two sets,
those that lie in the strategy τ and those that do not.  The
first set is itself a strategy, so we can consider forward projections
under that strategy.  For each core cycle action that is not in
τ, we consider the forward projection of that action's target
state.  The lemma asserts that the resulting forward projections are
pairwise disjoint.  Moreover, if 2muτ is disruptive, then
each such forward projection does not loop back far enough to include
the source state of its generating core cycle action.

These properties will help us later to construct minimal nonfaces from
which we can then extract an informative action release sequence that
is sufficiently long to establish Theorem <ref>.


(a) Let ≥ be the partial order induced by  on W.
  Suppose v∈ J_c  J_d, with c,d ∈.  Write c = w
  → t and d = u → s.  Then t ≥ v and s
  ≥ v.  Since ⊆, backchaining from v
  produces a unique backwards path of action edges in , with
  each edge actually being a deterministic action.  (The path could be
  degenerate, consisting of no edges, just the state v.)  That
  backwards path eventually encounters both t and s, establishing
  that t and s are comparable.  For example, 
 s →⋯→ t →⋯→ v

  would establish s ≥ t.  Since core cycle actions w
  → t and u → s are missing from , this
  is only possible if s=t, meaning c=d.




(b) Suppose w∈ J_c, with c∈ and c = w → t.
Arguing as in (a), we now obtain a cycle:




 
    w → t → w_1 →⋯→ w_k = w,   with k ≥ 1.


All but one of the actions comprising this cycle lie in .



The exception is w → t, which lies in .



All the actions comprising the cycle lie in . Consider any action
u → s of .  The depth[Here, the depth of a
node or leaf in a tree is defined recursively as follows: 

 The depth of the tree's root is 0.   The depth of a
child is one more than the depth of its parent.] of the leaf
({u}, ∅) in the tree decomposition of H must be greater
than or equal to the depth of the leaf ({s}, ∅).
Consequently, all the states in the cycle appear in H as leaves at
the same depth and with the same parent node.  The cycle must
therefore consist of that parent node's cycle actions and the parent
node cannot contain any other children.  So, the parent node covers
only leaves.  Since τ is disruptive, at least two of the node's
cycle actions lie in , not just one, establishing a
contradiction.






 §.§ Quotienting until Disruption

Quotienting until Disruption


The proof path now is to iteratively mark and quotient by nodes that
prevent a strategy from being disruptive.  Concurrently, one assembles
several sets of actions that satisfy a property similar to the
disjointness of forward projections described in
Lemma <ref>.

[Acyclic Dissection]
Let H=(W,) be a hierarchical cyclic graph.  Suppose
τ⊆.  An acyclic dissection
(,,,ξ) of τ
in H is defined iteratively as follows:




1pt


  * Initialize τ^(0)=τ  and κ^(0) = ∅.
      Assume all nodes in the tree decomposition of H are unmarked
      and initialize H^(0)=H, as per Section <ref>.

      Set Done to true if 1muτ is disruptive in
      H and to false otherwise.


  * While not Done, run the following loop, starting from j=0:
      
  


  

  2pt

  
  * At this stage, τ^(j) consists of actions in H^(j)
        and is not disruptive in H^(j).   Let N be some
        unmarked node in H such that the corresponding quotient node
        N^' in H^(j) covers only leaves and at most one of
        the cycle actions in N^' is absent from τ^(j).


  
  * Suppose N^' has k cycle actions {c^'_1,
        …, c^'_k}.  Discard one of these, so that the rest
        all lie in τ^(j).  Without loss of generality, assume
        one may discard c^'_k.  Now let

        


        
    κ^(j+1) = κ^(j){c_1, …, c_k-1}.


        Inductively: κ^(j+1) consists of (unquotiented)
        actions in H.   In fact, κ^(j+1)⊆τ.


  
  * Mark node N, then let H^(j+1) be the quotient graph
        formed from the resulting maximal marked nodes, as per
        page markings, again viewed as a hierarchical cyclic
        graph.

  
  * Suppose H^(j+1) = (W^',  ^').   Let
        τ^(j+1) = a'∈^'a∈τ.  So
        τ^(j+1) is nearly the same as τ^', except
        that τ^(j+1) ignores any action of
        1.75muτ-0.1mu whose source and targets all
        lie within any one maximal marked node of H.  (Prime
        notation indicates the correspondence between an action in
        1muH and its relabeled form in a quotient graph.)

  
  * If τ^(j+1) is disruptive in H^(j+1), set Done
        to true.  The loop ends.  Otherwise, the loop continues,
        with j+1 in place of j.

  


  * If τ was already disruptive in H, let H^*=H,
      τ^*=τ, and =∅.  Otherwise, let
      H^*=H^(j+1), τ^*=τ^(j+1), and
      =κ^(j+1), with j+1 as above when the loop
      ends.  In either case, τ^* is disruptive in H^*.

       Finally, let = c∈c'∈.  In
      other words,  is the set of actions in H that become
      core cycle actions in the quotient graph H^*.


  * Define ξ as follows (H contains a marked node if and only if
      the loop of step 2 was run):

      Start with ξ=∅.  Then, for each unmarked 
      node N in H, let  be N's cycle actions.  If
      τ is a proper subset of , add all of
      τ to ξ.  Otherwise, select an action c in
      .  Add the actions {c} to
      ξ.   (Why does c exist?  If not, let N^' be the
      node in H^* corresponding to N.  It is well-defined since
      N is unmarked.  Then N^' would cover only leaves in
      H^* and thus τ^* would not be disruptive in H^*, a
      contradiction.)  

  * Step 3 defined .  Now define
            = ξ,  and
            = ξ.




Construction <ref> produces an acyclic dissection
(, , , ξ) of τ such that:




5in

-3pt

  (i) ⊆ξ and ⊆,

  (ii) ξ⊆τ and ξ=∅,

  (iii) ξ is cycle-breaking in H, and

  (iv) τ=∅.







The loop in step 2 of Construction <ref> runs at most
a finite number of times, since the graph H is finite.  As a result,
an acyclic dissection (, , , ξ) of τ is
well-defined by step 5.



Assertions (i), (ii), and (iii) are clear from the construction.



To establish assertion (iv), suppose a∈τ.  Let prime
notation denote quotienting from H to 1muH^*, with
1muH^* as defined in step 3 of the construction, and assume
the rest of the notation from the construction.

Then a∈, a∈τ, and a∉ξ.

So a^'∈, implying a∈, with  the cycle
actions of some unmarked node N in H.



If τ is proper subset of , then a∈ξ, by
step 4 of the construction, producing a contradiction.

So τ=.  Let c be the action removed in step 4 of
the construction.  So c∉.  Since a∉ξ, a∈,
and {c}⊆ξ, it must be that a=c, but
that contradicts a∈.



And here is a generalization of Lemma <ref>:


 Suppose H=(W,) is a hierarchical cyclic graph and
τ⊆.   Construct (, , , ξ)
from 3muτ-0.5mu as per Construction <ref>.  Let η =.




Given c∈, write c = w → T and define





    J_c = _η(T).


(The definition is sensible since η is
cycle-breaking in H and so η∈.)




Then:

5in

-3pt

  (a) The sets in the family
  1mu{J_c}_c1mu∈1mu are pairwise
  disjoint.

  (b) For each c∈,  (c)∉J_c.





Let prime notation denote quotienting from H to H^*, where
sensible, with H^* as in step 3 of the construction.  Write
H^*=(W^', ^'), viewed with a tree decomposition
derived from that of H.



Since ξ arises only from cycle actions of unmarked nodes, each
action in ξ^' is a well-defined convergent action in
^'.  By construction, ξ^' is cycle-breaking in
H^*, so ξ^'∈.  Since ξ^'⊆τ^*,
ξ^' is disruptive in H^*.  Consequently,
Lemma <ref> applies to the graph H^* and the
disruptive strategy ξ^'.



In H, we have =ξ and =ξ.
Therefore, each action c∈ corresponds to an action c^'∈ = ξ^' in H^*, and each action
c∈ corresponds to an action c^'∈ =
ξ^'.   (Recall the comment about “one-to-one
correspondence” on page quotient.)



Let ≥ be the partial order induced by η on W and let
≥^* be the partial order induced by  on W^'.

Suppose v ≥ w, with v,w ∈ W.  Then v^'≥^*
w^', with v^', w^'∈ W^' being the state
relabelings of v and w, respectively.  (Why?  If there is a path
of action edges from v to w with the actions drawn from η,
then there is a path of action edges from v^' to w^'
with the actions drawn from η^'.  Some of the action edges
between states in W-2.3mu may become self-loops when sources
and targets are relabeled as states in W^'.  Indeed,
v^'=w^' is possible even if v≠ w.  Any such
self-loops could only come from actions in .  Conversely, all
actions in  are self-loops.  One discards those actions in
forming H^*, leaving only  from η^'.  Thus there
is a path of action edges from v^' to w^' with the
actions drawn from .)



It follows that v∈ J_c implies v^'∈ J_c^', with
J_c^' defined for H^* and ξ^' as in
Lemma <ref>, now using c^' in place of c,
 in place of , and  in place of .
 (To see this, write c = w → T.  The set of targets T
becomes a single state t^'∈ W^', since
c^'∈.  Write c^' = w^'→ t^'.
If v∈ J_c, then t ≥ v for some t∈ T, so t^'≥^*
v^', and thus v^'∈ J_c^'.)



Consequently, Lemma <ref> establishes the claims of
the current lemma.








 §.§ Alternate Development: Quotienting until Disruption

Alternate Development: Quotienting until Disruption

This subsection restates Construction <ref>
recursively without mentioning markings, then provides induction
proofs of the corresponding lemmas.  The key steps are the same as
before.  The rest of Section <ref> will prove
Theorem <ref> for pure nondeterministic graphs using the
earlier iterative construction, side-stepping any issue of strategy
maximality in quotient graphs.   Section <ref> will engage
that issue when proving Theorem <ref> for pure stochastic
graphs.



[Alternate Construction: Acyclic Dissection]
 Let H=(W,) be a hierarchical cyclic graph.  Suppose
τ⊆.  An acyclic dissection
(,,,ξ) of τ
in H is defined recursively as follows:








  I.  Suppose τ is disruptive in H:






  
  * Define ξ as follows, starting from ξ=∅:

        For each node N in H, let  be N's cycle actions.
        If τ is a proper subset of , add all of
        τ to ξ.  Otherwise, there is at least one
        action c in .  (If not, then N would
        cover only leaves in H and thus τ would not be
        disruptive.)   Pick one such action c and add the remaining
        actions {c} to ξ.

  
  * Let =∅,
            = ξ,  and
            = ξ.




  II. Suppose τ is not disruptive in H:






  
  * Let N=(U, ) be a node in H that covers only leaves
        and at most one of whose cycle actions is absent from τ.
        The actions  are necessarily N's cycle actions.
        Discard one of those actions, so the rest all lie in τ.
        Denote that resulting set by .

  
  * Let H^*=(W^',^') be the hierarchical cyclic
        graph formed from the quotient graph H/U by discarding
        self-loops.  Let (, , , ξ^') be a recursively constructed acyclic dissection
        of τ^'^' in H^*.  (As usual,
        prime notation describes the correspondence between actions of
        2.5muH and actions of 2.5muH/U.)

  
  * Now define the sets of actions , , and
        ξ by unquotienting, that is, by direct correspondence
        from the sets of actions , , and
        ξ^', respectively.

          Finally, let =, with 
        formed from  by unquotienting.







  
Proof of Lemma <ref>, assuming alternate acyclic
  dissection given by Construction <ref>:


The construction terminates because H is finite and each recursive
invocation of the construction replaces a node with a leaf.

The proof of the specific assertions is by induction, with Case I of
the construction defining the base case and Case II defining the
inductive step:







  I: In the base case, assertions (i), (ii), and (iii) are
          immediate from the construction.  Assertion (iv) follows as
          it did in the earlier proof of Lemma <ref>, but
          now working directly with H rather than needing to form a
          quotient.


  II: Inductively, we assume assertions (i)–(iv) hold for an
           acyclic dissection (, , , ξ^') of
           1muτ^'^'1mu in
           H^*, using the notation from the construction.  Then:

  


   
   2pt

   
  (i) ⊆ξ^', so ⊆ξ
               and  
              ⊆^', so
              ⊆⊆.

   
  (ii) ξ^'⊆τ^'^',
              so
              ξ=ξ⊆τ,
              since ⊆τ.

              ξ^'=∅, so
              ξ=∅.   Since all actions in
               become self-loops and are discarded when
              forming H^* from H, ξ=∅,
              and so ξ=∅.
              

   
  (iii) ξ^' is cycle-breaking in H^*,
              so ξ=ξ is cycle-breaking
              in H, since  consists of a proper subset of one
              node's cycle actions and since ξ does not
              include any of that node's actions.

   
  (iv) τ^'^'=∅,
                so τ=∅.  Since
                ⊆, it follows that
                τ=∅.
   











  
Proof of Lemma <ref>, assuming alternate acyclic
  dissection given by Construction <ref>:


Again by induction:







  I: The base case follows from Lemma <ref>,
          with ξ in place of τ, since ξ is a disruptive
          strategy by Lemmas <ref> and <ref>.



  II: Inductively, the argument is much the same as in the
           earlier proof of this lemma.  One assumes the assertions
           hold for the hierarchical cyclic quotient graph H^*.  In
           moving back to H, one state of H^* turns back into a
           cycle of states, with all but one of the cycle actions
           added to  to form .  The other sets of
           actions in the dissection do not change as one moves back
           from H^* to H, except for relabelings of sources and
           targets. Consequently, execution paths of
            (within H) imply execution paths of
            (within H^*), thereby establishing
           the lemma's assertions for H.











 §.§ Acyclic Dissection Sizes

Acyclic Dissection Sizes

This subsection measures the size of the set
 in an acyclic dissection.


When reading the lemma below, recall that
Construction <ref> marks nodes in H.


 Suppose H=(W,) is a hierarchical cyclic graph and
τ⊆.   Let H^*=(W^',^') and
2mu be derived from 2muτ as per step 3 in
Construction <ref> on
page acyclicdissection.



For each u∈ W^', define (W_u, _u) as follows: If 2muu∈ W, let (W_u, _u) be the leaf ({u},
∅) of H.  If u∉W, let (W_u,
_u) be the maximal marked node of H for which u
represents W_u.



Then _u = W_u - 1,  for each
u∈ W^'.



The proof is by induction on the iteration count j in the loop
of Construction <ref>, now using H^(j) in place
of H^*, κ^(j) in place of , and with the collection
of marked nodes dependent on j.  The base case, j=0, corresponds
to all u being in W, for which the lemma's assertion is clear.
Inductively, suppose the lemma's assertion is true for H^(j).

In forming H^(j+1) from H^(j), one marks an unmarked node
N=(V, ) of H whose corresponding node N^' in
H^(j) covers only leaves.  So N is now a maximal marked node.
 Let W^(j) be the states of H^(j), W^(j+1) the states of
H^(j+1), and V^' the states of N^'.  Then
W^(j+1)=(W^(j)V^')  {},
with  representing the states V^' identified to a
singleton.



Let {c_1, …, c_k} and {(V_1, _1), …, (V_k,
_k)} be the cycle actions and children of N in H, respectively.

 Without loss of generality, κ^(j+1) = κ^(j){c_1, …, c_k-1}.  One has k=V^'>1.




Case I:  Suppose u∈ W^(j+1) W^(j).   Then the
definition of (W_u, _u) is the same via H^(j+1) as via
H^(j).  So κ^(j)_u = W_u - 1.
Since (W_u, _u) is either a leaf or a marked node of H at
the j^th iteration of the loop in
Construction <ref>, _u contains none of node
N's cycle actions.  Thus κ^(j+1)_u =
κ^(j)_u and so κ^(j+1)_u = W_u - 1, inductively.




Case II:  Suppose u=.   Then the definition of (W_,
_) via H^(j+1) is N, so W_ = V and
_ =.  The states V^' of N^' in
H^(j) are in one-to-one correspondence with the children {(V_i,
_i)} of N.  Inductively, κ^(j)_i
= V_i - 1.  Again, κ^(j+1)_i =
κ^(j)_i.   Moreover,





    W_ =  V_1 ⋯ V_k
          and    
      B_ = {c_1, …, c_k}_1 ⋯_k.





By reasoning about markings, one further knows that
κ^(j){c_1, …, c_k}=∅.   Therefore





    κ^(j+1) B_  =  {c_1, …, c_k-1}    _i=1^k(κ^(j)_i)


and





    κ^(j+1) B_    =    
      (k-1)  + ∑_i=1^k κ^(j)_i
        =    
      (k-1)  + ∑_i=1^k (V_i - 1) 
        =    
      - 1  + ∑_i=1^k V_i
        =    W_ - 1.








 Suppose H=(W,) is a hierarchical cyclic graph and
τ⊆.   Let , , , and H^* be
derived from τ as per Construction <ref> on
page acyclicdissection.



Let n=W and m=.



If H^*-1.5mu is a leaf, then m=n-1.   
If H^*-1.5mu is a node, then m=n.



Suppose H^* is a leaf.  Then H^*=({u}, ∅), for some u,
and ==∅.  Using the notation of
Lemma <ref>, (W_u, _u) must be all of H.

 The lemma then implies that m= = 
= _u = W_u-1 = W-1=n-1, as
claimed.




Suppose H^* is a node.  Let W^' be the states of H^*.  For each
u∈W^', let (W_u, _u) be defined as in
Lemma <ref>.  Since  is formed from cycle actions
in marked nodes of H, =
_u∈W^'(_u).  We also know that
W=_u∈W^'W_u.  Thus, by the lemma,





    =    ∑_u∈W^'_u
        =    ∑_u∈W^'(W_u - 1) 
        =    W - W^'
        =     n - W^'.


Let  and  be as in Construction <ref>.
Then =, so
== = W^'.
Consequently, m=+=n, as claimed.








 §.§ Informative Action Release Sequences for Maximal Strategies

Informative Action Release Sequences for Maximal Strategies

This subsection assembles the previous results to prove
Theorem <ref> for pure nondeterministic graphs.




 Let G=(V,) be a fully controllable pure nondeterministic graph
with V-4mu≠∅ and suppose H=(V, ) is a
hierarchical cyclic subgraph of G.  (Recall that H exists, by
Lemma <ref> on page hierarch.)



Let σ be a maximal strategy in , define
τ=σ, let (, , , ξ) be
an acyclic dissection of 3muτ-0.25mu obtained from
Construction <ref>, and set η =.



Suppose c∈.   Write c = w → T and define





    _c     =   κ⊆σ{c}κ is a minimal nonface of ,
    
    J_c         =   _η(T),
    σ_c    =   a∈σ(a)∈J_c and (a)⊈J_c.


Then _c≠∅ and κσ_c≠∅
for every κ∈_c.




  
Comment:  The lemma tells us that every action
c∈ is part of a minimal nonface of  whose remaining
actions lie in σ, and that at least one of those actions has
its source, but not all its targets, in the forward projection of
c's targets.  Here the forward projection is based on those actions
of 2muσ that lie in the acyclic dissection sets
1mu and .  Intuitively, it is useful to think of
0.5muH-1.5mu as a single node defining a directed cycle,
with the projection of 1.5muσ0.5mu onto that cycle
being disruptive.  Disruption means that the cycle splits into at
least two pairwise disjoint directed arcs, as follows: The cycle edges
present in σ constitute , the cycle edges missing from
σ constitute , and  is empty in this simple
scenario.  There is one directed arc for each action c∈,
starting at c's target.  Each arc is formed from contiguous action
edges of .  Each arc has a forward projection flow defined on
it by the directionality of those action edges.  A directed arc ends
when it encounters the source of another action in .  An arc may
be degenerate, consisting of a single state.  The lemma says that, for
each missing cycle edge c, there is some action a∈σ whose
source lies in an arc that starts at c's target, such that at least
one of a's targets lies outside this arc and such that a and c
appear together in a minimal nonface of .   As we will see
shortly, the “a or c?” choice is therefore informative.


By Lemma <ref>(iv) on page acyclicprop,
c∉σ.  So, since σ is maximal in ,
_c≠∅.

Let κ∈_c be given.

Define γ=a∈κ(a)∈J_c.

Since κ is a minimal nonface of , no action of κ
moves off (κ), by Lemma <ref> on
page minnonfacestrat.  Since c∈κ and {c}∈,
γ≠∅.   By Lemma <ref>(b) on
page disjointforward, (c)∉J_c, so
c∈κγ.   Thus
∅≠γ⊊κ and γ⊆σ.

Now suppose the lemma's second assertion is false for this κ.
Then every action in γ has all its targets in J_c.  Pick some
a∈γ.  Since a∈κ, there exists b∈κ such that
(b)∈(a)⊆J_c.  We see therefore that b∈γ
and that no action of γ moves off (γ).
Consequently, γ∉, which contradicts κ being a
minimal nonface of .



Imagine revealing actions of some secret maximal strategy
0.25muσ-3mu∈-3mu0.5mu to an
observer who knows G0.85mu but initially merely that σ
is maximal in .  Suppose c1mu is an action in , as
previously defined.  So c∉σ and
σ{c}∉.  Let σ_c be as before.  The next
corollary says that so long as one has not explicitly revealed any
actions of σ_c, the observer cannot exclude the possibility
that one is revealing actions of some maximal strategy other than
σ, some strategy that does include action c.  Moreover, there
exists some unrevealed and unimplied action in σ_c that one may
yet release informatively.  (The explicitly revealed actions may imply
some actions in σ_c, but so long as none of the explicitly
revealed actions themselves lie in σ_c, these assertions hold.)





Let the hypotheses and notation be as in Lemma <ref>.

 In particular, σ is maximal in  and c∈.



Suppose γ⊆σ such that γσ_c=∅.



Let A be G's action relation and define = ()(γ).

 Then:




5in

-3pt

  (i) {c}∈.

  (ii) _c≠∅ and
  (κσ_c) ≠ ∅
  for every κ∈_c.





We may prove (i) by establishing that
ψ_A({c})≠∅.  By reasoning
similar to that on page 122 in <cit.>,
ψ_A({c})=ψ_A(γ{c}),
so it is enough to show that γ{c}∈.  Suppose this
is false.  Then there exists a minimal nonface κ of  such
that κ⊆γ{c}⊆σ{c}, so
κ∈_c.  By Lemma <ref>,
κσ_c≠∅.  That establishes a contradiction
to γσ_c=∅ and c∉σ_c.



Turning to (ii), _c≠∅ by Lemma <ref>.

 Suppose now that γ=σσ_c.  Establishing
the second part of (ii) for this particular γ will establish it
for all hypothesized γ, by monotonicity of closure operators.
By (i), {c}∈.  Since σ is maximal in
, ⊆σ.   Since c∉σ and by
Lemma <ref> on page minnonfacesmaxsimplex,
κ({c})≠∅1.5mu for
every κ∈_c.

 Since σσ_c = γ ⊆  ⊆ σ and κ ⊆ σ{c}, κ({c}) =
(κσ_c),  completing the
proof.


The following theorem has as corollary
Theorem <ref> of page longiars for pure
nondeterministic graphs:

0

Let G=(V,) be a fully controllable pure nondeterministic graph
with n = V > 1 and suppose H=(V, ) is a hierarchical
cyclic subgraph of G.

Suppose σ is a maximal strategy in .  Set
τ=σ, then define H^* by step 3 of
Construction <ref> on
page acyclicdissection.



5in

-3pt

  I. If H^*-0.5mu is a leaf, then σ
contains an informative action release sequence for G of
length at least n-1.

  II. If H^*-0.5mu is a node, then σ
contains an informative action release sequence for G of
length at least n.





Throughout the proof we assume notation as given in
Construction <ref> and Lemma <ref>.  Observe
that σ≠∅, since G is fully controllable with n > 1.




I. Suppose H^* is a leaf.  Then ==∅.   By
Lemma <ref> on page acyclicprop,
⊆σ and  is cycle-breaking in H; by
Corollary <ref> on page dissize, =n-1;
and by Lemma <ref> on page nocycleiars, one may
find an ordering of the actions in  such that they form an
informative action release sequence for H.  This sequence is also
informative for G by the comment after
Lemma <ref> on page combinesubgraphiars.




II. Suppose H^* is a node.  As in part I, one may find an ordering
of the actions in  such that they form an
informative action release sequence for G
(≠∅, by maximality of σ and full
controllability of G).  Write this sequence as a_1, …,
a_ℓ.  It is contained in σ.



By Corollary <ref>, =n.
Since τ^* is disruptive in H^*, ≠∅.  Of
course, one cannot release the actions in , since they are not
in σ.  Instead, as we will see shortly, for each c∈
one may release some action of σ_c informatively, thereby
completing the proof.



First, observe that
()σ_c=∅, for every
c∈.  To see this, write η= and suppose
a∈η and (a)∈ J_c for some c∈.  Write c = w
→ T.  Let ≥ be the partial order induced on
1muV by η.  Then t ≥(a) for some t∈ T.
Since a∈η, (a) ≥ s for every s∈(a).  So t
≥ s for every s∈(a), meaning (a)⊆ J_c.
Consequently, a∉σ_c.



Inductively, suppose we have released, for some sequence of distinct
actions c_1, ..., c_k in , with k≥ 0, a corresponding
sequence of distinct actions b_1, ..., b_k in σ, such that
b_i∈σ_c_i, for i=1, …, k, and such
that the overall sequence a_1, …, a_ℓ, , …, b_k
is an iars for G.  If k=, we are done.  Otherwise, we
need to show how to extend this sequence.



Let γ={a_1, …, a_ℓ, , …, b_k} and
= ()(γ), with A being G's action relation.
Pick some c∈{c_1, …, c_k}.  We already
observed that ()σ_c=∅.
By construction, (b_i)∈ J_-0.5muc_i,
for i=1, …, k.  By part (a) of Lemma <ref> on
page disjointforward,
J_-0.5muc_i J_c = ∅, for i=1,
…, k.  Consequently, γσ_c = ∅.  By
Corollary <ref>, there exist κ∈_c and b∈(κσ_c), so b may be
released informatively.   Let c_k+1=c and b_k+1=b.







 §.§ Examples for Pure Nondeterministic Graphs

Examples for Pure Nondeterministic Graphs

This subsection shows how the proof of Theorem <ref>
produces informative action release sequences for various pure
nondeterministic graphs and strategies.




  §.§.§ A Hierarchical Pure Nondeterministic Graph


The first example considers the pure nondeterministic graph of
Ex202b_Graph on page Ex202b_Graph.  The graph
may be viewed directly as a hierarchical cyclic graph, as indicated by
Ex202b_HTree.



Let us consider two maximal strategies and see how our constructions
generate informative action release sequences using the hierarchical
cyclic graph H.  Since H and G have the same actions, τ in
Construction <ref> on
page acyclicdissection is the maximal strategy under
consideration.








  
τ = {e_2, e_3, b_4}  (This strategy
converges to state #1.)


-3pt


  * Not used by the construction, but just for reference: τ is
  cycle-breaking in H.


  * τ is not disruptive in H, so we run the loop of step 2 in
  Construction <ref>:




  
  -3pt
    
  * First we mark node N, defining κ^(1)={e_2, e_3}.
    
  * Then we mark node H, defining κ^(2)={e_2, e_3, b_4}.
  


  * At step 3, H^* is a leaf.  So =κ^(2)=τ and
  ==∅.


  * The proof of Lemma <ref> on
  page nocycleiars now produces either the sequence b_4,
  e_2, e_3 or the sequence b_4, e_3, e_2 as an informative
  action release sequence.






  
τ = {e_1, e_2, a_2}  (This strategy
converges to the set of states {3, 4}.)


-3pt


  * τ is cycle-breaking in H.


  * τ is not disruptive in H, so we run the loop of step 2 in
  the construction:




  
  -3pt
    
  * First we mark node N, defining κ^(1)={e_1, e_2}.
    
  * Then we mark node H, defining κ^(2)={e_1, e_2, a_2}.
  


  * At step 3, H^* is a leaf.  So  is again all of τ
  and ==∅.


  * Again, one may release the actions of  informatively, as
  per the proof of Lemma <ref>, for instance as the sequence
  a_2, e_1, e_2.



Comments: (i) G's action relation in Ex202b on
page Ex202b shows that no maximal strategy is disruptive in
H, so Construction <ref> will always run the loop
of step 2.

(ii) The construction will always assemble the entire strategy as an
iars.  In fact, as Ex202b shows, the strategy complex 
is a triangulation of , and in particular has no free faces.
Consequently, any ordering of the actions in a maximal strategy will be
an informative action release sequence for G.







  §.§.§ A Pure Nondeterministic Graph with Several Nondeterministic Actions


Let us add some nondeterministic actions to the previous graph, as shown
in Ex202_Graph.





The earlier hierarchical cyclic graph H of Ex202b_HTree
is a subgraph of the new G, on the same state space (but with fewer
actions), so we can use the same H as before to construct
informative action release sequences for maximal strategies, now in
the new G.  Almost every maximal strategy in the new  is either
identical to or a proper superset of a maximal strategy in the old
.  Intersecting one of these strategies with the actions of H,
as Theorem <ref> requires, therefore produces the same
constructions as before.




There is one exception: The new  contains a maximal strategy,
namely σ_5, that does not restrict to a maximal strategy in the
old .   Let us look at that strategy more carefully:



  
σ = σ_5 = {e_1, a_1, a_2, a_3}  (This strategy
converges to state #4.)


-3pt


  * τ is the intersection of σ with the actions of H, so
      τ={e_1, a_2}.


  * τ is cycle-breaking in H.


  * Now τ  is  disruptive in H, so
      Construction <ref> 2.5mudoes
      not4mu run the loop of step 2, but skips directly to
      step 3.


  * At step 3, H^* is all of H, so =∅.


  *  consists of all the core cycle actions of H, so
      = {e_1, e_2, e_3, a_2}.


  * The construction of ξ in step 4 incorporates all of τ,
      starting from ξ=∅, as follows:




  
  -3pt
    
  * For node N, step 4 adds action e_1 to ξ.
    
  * For node H, step 4 adds action a_2 to ξ.
  


  * Thus =ξ={e_1, a_2} and
      =ξ={e_2, e_3}.


  * The actions of  may be released informatively in depth
      order, as the sequence a_2, e_1.


  * For each action in , one finds an action in σ
      as per the proof of Theorem <ref>:




  
  -2pt
    
  * For action e_2∈, action a_3∈σ lies
    “downstream” from e_2, forms a minimal nonface with e_2, and
    is not implied by {a_2, e_1}.

    
  * For action e_3∈, action a_1∈σ lies
    “downstream” from e_3, forms a minimal nonface with e_3, and
    is not implied by {a_2, e_1, a_3}.

  

  (The term “downstream” refers to the partial order determined by
   η=.   Since =∅, that simply
   means  here.

    Specifically, the phrase “action b1mu lies downstream
   from action a” means that b's source lies in the forward
   projection of a's targets under η, that is,
   “2mut≥_η(b), for some
   1mut∈(a)”.

   Moreover, this and subsequent examples, following the proof of
   Theorem <ref>, further choose 1mub1.75mu
   so that not  all of b's targets lie within the
   forward projection of a's targets.)





Consequently, one may arrange all four actions of σ (=σ_5)
into an informative action release sequence for G.  This is consistent
with Theorem <ref>, since H^* is a node in the
construction.  For instance, the sequence a_2, e_1, a_3, a_1 is an
iars.  There are other orderings that will also produce iars of length
4, but not all will do so.  For instance, releasing action a_1 as the
first action in a sequence would limit the length of that sequence as an
iars to 2.  See <cit.> for further discussion of this
example.




  §.§.§ A Directed Graph with Several Cycles, Represented Hierarchically



Consider the directed graph G of Ex241_GraphSigma.  All the
actions in this graph are deterministic.  The graph has several
directed cycles in it, giving us the opportunity to explore more than
one hierarchical decomposition for G.  The figure also shows a
maximal strategy σ in .  We will focus on this one
strategy, using two different hierarchical cyclic subgraphs of G to
construct informative action release sequences for G in two
different ways, such that each sequence consists of actions contained
in σ.   For reference, G's full action relation appears in
Ex202_relation.








  
A Multi-Node Hierarchical Decomposition:  The 
decomposition H shown in Ex241_H1 models G directly
as a hierarchical cyclic graph, meaning H and G contain the same
states and actions.  In this decomposition, the smaller two cycles of
G define two nodes.  Each of these nodes contains only leaves,
comprising the state spaces {1, 2, 3} and {4, 5, 6},
respectively.  The root of the tree has these two nodes as children,
connected by a two-cycle.











  
σ={e_2, e_5, a_2, a_3, a_5, a_6}


-3pt


  * Since H=G, also τ=σ.


  * τ is not cycle-breaking in H, since it contains
      both cycle actions of H's root node.


  * τ is not disruptive in H, so
      Construction <ref> runs the loop of step 2.
      The construction may mark nodes N and M in either order.
      Here we start with N.
  



  
  -1pt
    
  * Mark node N, defining κ^(1)={a_2, a_3}.
    
  * Mark node M, defining κ^(2)={a_2, a_3, a_5, a_6}.
    
  * Mark node H.  Since τ contains both of H's cycle
          actions, the construction could add either action to
          κ^(2) in defining κ^(3).  Here we add
          e_2, so κ^(3)={a_2, a_3, a_5, a_6, e_2}.
  


  * At step 3, H^* is a leaf.  So ={a_2, a_3, a_5, a_6,
      e_2} and ==∅.


  * One may release the actions of  informatively in depth
      order, as per the proof of Lemma <ref> on
      page nocycleiars, for instance as the sequence e_2,
      a_2, a_3, a_5, a_6.


  * Observe that  is almost all of σ, excluding only
      action e_5.  The construction discarded that one action when
      forming κ^(3).









  
A Flat Decomposition:  Ex241_H2 shows another
hierarchical cyclic subgraph H of 2muG, on the same state
space but with fewer actions.  In this subgraph, the Hamiltonian cycle
of G defines a single node, necessarily the root of H, with all
six states as leaves.  Two of G's actions do not appear in H.








  
σ={e_2, e_5, a_2, a_3, a_5, a_6}


-3pt





  * τ is the intersection of σ with H's actions, so
      τ={e_2, e_5, a_3, a_6}.


  * τ is both cycle-breaking and disruptive in H.


  * Since τ is disruptive, H^*=H and =∅ in
      step 3 of Construction <ref>.
  

  *  consists of all the core cycle actions of H, which
      means all the actions of H since H defines a Hamiltonian
      cycle.   So = {a_1, e_2, a_6, a_4, e_5, a_3}.


  * The construction of ξ incorporates all of τ, since H
      consists of a single unmarked node.  Thus
      =ξ=τ={e_2, e_5, a_3, a_6} and
      =ξ={a_1, a_4}.


  * The actions of  may be released informatively in any
      order, for instance as the sequence e_2, e_5, a_3, a_6.


  * For each action in , one finds an action in σ
      as per the proof of Theorem <ref>:

      (Again, “downstream” refers to the partial order determined by
      .)




  
  -1pt
    
  * For action a_1∈, action a_2∈σ lies
         “downstream” from a_1, participates in the minimal
         nonface {a_1, a_2, a_3} with a_1, and is not implied by
         {e_2, e_5, a_3, a_6}.

    
  * For action a_4∈, action a_5∈σ lies
         “downstream” from a_4, participates in the minimal
         nonface {a_4, a_5, a_6} with a_4, and is not implied by
         {e_2, e_5, a_3, a_6, a_2}.

  





  * Consequently, all actions of σ may be arranged into the
  informative action release sequence e_2, e_5, a_3, a_6, a_2, a_5.





  
Comment:  We have seen the following: (i) With H
  as in Ex241_H1, Construction <ref> produces
  an informative action release sequence for G consisting of
  1mu5 actions in σ.  (ii) With H as in
  Ex241_H2, the construction produces an informative action
  release sequence consisting of all 6 actions in σ.
  These sequence lengths match the assertions of
  Theorem <ref> on page longiarsnondet.




  §.§.§ A Directed Graph with a Disruptive but not Cycle-Breaking Strategy


This example will illustrate an instance in which τ contains all
the cycle actions in a node during step 4 of
Construction <ref>.  Ex249_GraphSigma
depicts a graph G and a maximal strategy σ∈.
Ex249_relation displays G's action relation.
Ex249_H shows a hierarchical cyclic subgraph H of G, on
the same state space (but with fewer actions).   (Other such subgraphs
exist, of course.)









  
σ={e_2, e_4, a_2, b_1, b_2}


-3pt


  * τ is the intersection of σ with H's actions, so
      τ={e_2, e_4, a_2}.


  * τ is not cycle-breaking in H, since it contains both cycle
  actions of H's root node.


  * τ is disruptive in H, since it contains only one of node
      N's three cycle actions.


  * Since τ is disruptive, H^*=H and =∅ in
      step 3 of Construction <ref>.
  

  *  consists of all the core cycle actions of H, so
      = {a_1, a_2, a_3, e_2}.


  * The construction of ξ={a_2, e_2} in step 4 occurs as
      follows, starting from ξ=∅:




  
  -1pt
    
  * For node N, ={a_1, a_2, a_3} and
    τ={a_2}, so one adds action a_2 to ξ.

    
  * For node H, ={e_2, e_4} and τ=,
    so one must discard some action of  that is not in .
    That action is e_4.  One adds action e_2 to ξ.
  


  * Consequently, =ξ={a_2, e_2} and
      =ξ={a_1, a_3}.


  * The actions of  may be released informatively in depth
      order, so as the sequence e_2, a_2.


  * For each action in , one finds an action in σ
      as per the proof of Theorem <ref>:

      (Once again, “downstream” refers to the partial order
      determined by .)




  
  -1pt
    
  * For action a_1∈, action b_2∈σ lies
       “downstream” from a_1, forms a minimal nonface with a_1,
       and is not implied by {e_2, a_2}.

    
  * For action a_3∈, action b_1∈σ lies
      “downstream” from a_3, forms a minimal nonface with a_3,
      and is not implied by {e_2, a_2, b_2}.

  


  * Therefore e_2, a_2, b_2, b_1 is an informative action
      release sequence for G, contained in σ.

      (The order matters: Revealing either b_1 or b_2 at the
      beginning of the sequence would narrow the set of maximal
      strategies consistent with the revealed action to two instantly.
      One then could reveal only one more action informatively before
      identifying σ, that action being the other “b_i”
      action not yet revealed.  Indeed, revealing actions
      b_1-1.75mu and b_2 in either order
      identifies the maximal strategy to be σ.  Revealing
      action a_2 implies action e_2, while revealing e_2 at the
      beginning does not imply a_2.  Although not part of the
      construction, observe that revealing b_1 would in and of
      itself declare the goal to be state #3.)









§ THE STOCHASTIC SETTING

The Stochastic Setting


The aim of this section is to prove Theorem <ref> from
page longiars for the case in which the graph G is pure
stochastic.  Throughout, this section assumes that all graphs are pure
stochastic, meaning each action is either deterministic or stochastic
(but not nondeterministic).



  
Caution: Even though all actions in a pure stochastic
graph are deterministic or stochastic, there may still be a component
of nondeterminism in a strategy: When multiple actions have the same
source state, any one of those actions might execute from that state,
with the choice potentially made by an adversary.  (See again the
discussion of generalized control laws on
page actionsemantics, as well as the definitions of “moves
off”, “contains a circuit”, and “strategy complex”.)





 §.§ Expanding Fully Controllable Subgraphs via Minimal Nonfaces

Expanding Fully Controllable Subgraphs via Minimal Nonfaces

As mentioned on page minnonfacesemantics, a minimal nonface
of  in a pure stochastic graph G defines an irreducible Markov
chain and thus a fully controllable subgraph of G.  If G is itself
fully controllable, one may construct such a minimal nonface κ
for each maximal strategy σ∈, for instance by considering
some action at a goal state of σ.  The actions of the minimal
nonface κ that lie within σ then form an informative
action release sequence z for G, contained in σ.

One may expand the state space (κ) covered by this minimal
nonface by considering some action outside σ, in a manner to be
discussed.  This process yields a new minimal nonface and thus
additional actions of σ with which to enlarge the informative
action release sequence z.  Repeating this process one may
eventually encounter a situation in which there are no further useful
actions outside σ.  Instead, one forms a quotient graph by
identifying all the states covered thus far.  Recursively, one obtains
an informative action release sequence within this quotient graph.
Patching the two sequences together gives an overall informative
action release sequence contained in σ of length one less than
the number of states in G's state space.




The following construction and subsequent results describe this process formally:


[Minimal Nonface Expansion]
Let G=(V,) be a fully controllable pure stochastic graph with
n = V > 1 and suppose 1.7muσ is a maximal
strategy in .

Construct a collection {b_1, …, b_k} of convergent actions in
, a collection {κ_1, …, κ_k} of minimal
nonfaces of , a collection {_1, …, _k} of
subsets of , and a collection {W_1, …, W_k} of
subsets of V, with k ≥ 1, as follows:




1pt


  * Let g∈V(σ).  Choose b_1∈ so
      that {b_1}∈ and (b_1)=g.  Such an action exists
      since G is fully controllable and V > 1.


  * Since σ is maximal, σ{b_1}∉, so
      there exists a minimal nonface κ_1 of  such that
      b_1∈κ_1⊆σ{b_1}.

        (For later reference, observe also that κ_1 > 1.)


  * Let _1=κ_1 and W_1=(κ_1).


  * Set Done to false.  While not Done, run the
      following loop, starting from i=1:

  


  

  3pt

  
  * Consider the quotient graph G/W_i and let prime notation
        refer to the correspondence between actions in G and
        G/W_i, as per the discussion on page quotient.

  
  * Define
        ξ_i=a∈σ(a)∈VW_i.   So
        ξ_i⊆σ, ξ_i∈, and
        (ξ_i)W_i=∅.

  
  * By Fact 1 on page quotientfacts,
        ξ_i^'∈Δ_G/W_i, so extend
        ξ_i^' to a maximal simplex
        τ^'_i∈Δ_G/W_i.

  
  * If τ_i⊆σ, then set k to
        the current value of i and Done to true.
         The loop ends.

        


        Otherwise: [t]4.1in
                   
                   -1pt

                   
  – Let b_i+1∈τ_iσ.

                   
  – As in step 2, there exists a minimal nonface
                         1muκ_i+11mu of  such that
                         1mub_i+1∈κ_i+1⊆σ{b_i+1}.
                          (Again, κ_i+1 > 1.)

                   
  – Let _i+1=_iκ_i+1
                         and W_i+1=W_i(κ_i+1).

                   
  – The loop continues, with i+1 in place of i.
                   
                   

  







Let the hypotheses and notation be as in Construction <ref>.

Then 1muW_i ⊊ W_i+1, for all i such that
W_i and W_i+1-1mu are well-defined.

(Consequently, the loop of step 4 in the construction ends, that is,
k is well-defined finite.)



It is enough to show that (κ_i+1) ⊈W_i.
Suppose otherwise.  Since b_i+1∈κ_i+1, that would mean
(b_i+1)∈ W_i and (b_i+1)⊆ W_i. (The
inclusion holds because κ_i+1 is a minimal nonface in ,
so no action of κ_i+1 moves off (κ_i+1), and
because G is pure stochastic.)  Thus b^ .1em'_i+1
would become self-looping in G/W_i, contradicting b^
.1em'_i+1∈τ^'_i∈Δ_G/W_i.






Let the hypotheses and notation be as in Construction <ref>.

 Then (W_i, _i) is a fully controllable pure stochastic
graph, for i=1,…,k.



Observe that k ≥ 1, since V > 1. 



Base Case:  (W_1, _1) = ((κ_1),  κ_1).  Since κ_1 is a minimal nonface in the strategy complex of a
pure stochastic graph, ((κ_1),  κ_1) is a fully
controllable pure stochastic graph.



Inductive Step:  As in the base case, ((κ_i+1),
 κ_i+1) is a fully controllable pure stochastic graph.
Inductively, (W_i, _i) is a fully controllable pure
stochastic graph.  Showing that W_i (κ_i+1) ≠∅ would therefore establish full controllability of the pure
stochastic graph (W_i+1, _i+1).  Suppose this intersection
is empty.  Then κ^'_i+1 is a minimal nonface in
Δ_G/W_i.  On the other hand,
κ_i+1{b_i+1}⊆ξ_i, so
κ^'_i+1⊆τ^'_i ∈Δ_G/W_i, producing a contradiction.






Let the hypotheses and notation be as in Construction <ref>.

Then {b_1, …, b_k} = k, that is, the actions b_1,
…, b_k are distinct.



Suppose 1 ≤ j ≤ i < k.  Then (b_j)∈ W_j and
(b_j)⊆ W_j.  Since W_j ⊆ W_i, action
b^'_j is self-looping in G/W_i and thus b_j cannot be a
candidate for b_i+1.






Let hypotheses and notation be as in Construction <ref>.

Suppose 1 < i ≤ k.

 Let ℓ_i = W_iW_i-1.

  (By Lemma <ref>, 2muℓ_i > 0.)



Then there exist actions _i ⊆κ_i(_i-1{b_i}) such that
_i = ℓ_i and at most one action in
_i has its source in W_i-1.

  (We refer to 3mu_i as an
 expansive set of actions.)



Moreover, suppose for all ⊆κ_i(_i-1{b_i}) with
= ℓ_i, ()
W_i-1≠∅.  Then (b_i)∉W_i-1 and one may
choose _i to contain an action  such that
()∈ W_i-1 and such that the probability of reaching
(b_i) from () under actions of
_i is nonzero.


Comments:

 (a) Let _0 = ∅, W_0 = {(b_1)}, and
    _1 = κ_1{b_1}.  Then the lemma
    holds for i=1, with (_1) W_0=∅.

 (b) For i=1,…,k, _i ⊆_iσ,
    since κ_i ⊆_i and κ_i{b_i}⊆σ.



Assume 1 < i ≤ k.

 Readily,
W_iW_i-1 = (κ_i)W_i-1
and
W_i-1 = (_i-1).

 Thus

W_iW_i-1 = (κ_i)(_i-1) ⊆ (κ_i_i-1),

meaning each state in W_iW_i-1 is the source of some
action in κ_i that is not also an action in _i-1.  If
in fact every state in W_iW_i-1 is the source of some
action in κ_i that is neither an action in _i-1 nor
the action b_i, then we may construct
1.5mu_i⊆κ_i(_i-1{b_i})2mu
such that 1mu_i = ℓ_i2mu and
2mu(_i) W_i-1=∅.

Otherwise, since all actions in a minimal nonface have distinct
sources, it is only possible to find ℓ_i-1 actions in
κ_i(_i-1{b_i}) whose
sources lie outside W_i-1.  Moreover,
(b_i)∈W_iW_i-1.  By the proof of
Lemma <ref>, (κ_i) W_i-1≠∅, meaning κ_i contains at least one action with
source in W_i-1.  We now show by backchaining from (b_i) how
to select one such action e so that _i may consist of
action e and the 1.5muℓ_i-1 actions just mentioned.




To reduce index clutter, we fix i and make the following
definitions for the rest of the proof:





    =   _i-1  and   W  = (),
    
           b    =    b_i,
    κ   =   κ_i,
       =   a∈κ({b})(a)∈(κ)W.





(By assumption for this case, =ℓ_i-1 and
(b)∈(κ)W.)




We now define a backchaining algorithm, with a loop index j, for
constructing sets of actions ∅≠τ^(0)⊊⋯⊊τ^(j)⊊⋯.  Inductively, each
iteration assumes that (i) b∈τ^(j)⊊κ, (ii)
τ^(j)⊆{b}, and (iii) for each
s∈(τ^(j)), there exists a sequence of zero or more action
edges leading from s to (b), with the edges coming from
actions in τ^(j){b}.




We initialize the loop with τ^(0)={b}.  The loop will end
by defining an action  such that we may let
_i={}, establishing the lemma.

 The loop starts from j=0:
      



5.6in

  

  
  (a) Since κ is a minimal nonface in , with G
             pure stochastic, ((κ), κ) is a fully
             controllable graph in its own right and ∅≠(τ^(j)) ⊊(κ), by
             Lemma <ref> on
             page minnonfacestrat.  Thus some action
             a^(j)∈κ moves off
             (κ)(τ^(j)) in this
             graph.

  
  (b) If we can pick a^(j) so that (a^(j))∈ W,
             then we do so and in that case we let =a^(j).
             Either way, we define
             τ^(j+1)=τ^(j){a^(j)}.  Condition
             (iii) above is satisfied by τ^(j+1) since it is
             satisfied by τ^(j) and
      0.5mu(a^(j))1.1mu(τ^(j))≠∅.

  
  (c) If step (b) defined action , then the loop ends.

             Otherwise, necessarily
             a^(j)∈τ^(j).  Thus, in
             this case, τ^(j+1) also satisfies conditions (ii)
             and (i) above, since in particular some action of
             κ has source in W-1mu but no action of
             τ^(j+1) does.   The loop continues, with j+1 in
             place of j.

  






By finiteness, the loop must eventually end, for some j.  The
probability of reaching (b) from () under actions of
τ^(j+1){b} is nonzero by condition (iii), so
the same will be true under actions of _i= {}⊆κ.  Moreover,
∈κ({b}) with
()∈ W, since ∈κ and
∅≠()1.5mu(τ^(j))⊆(κ)W,
whereas (a)⊆ W, for all a∈, and (b)∉W.




  
For the remainder of Section <ref>:  Assume
the hypotheses and notation of Construction <ref>
starting on page expandminnonfaces.  Let _0 =
∅ and W_0 = {(b_1)}.  Define H_i = (W_i,
_i), for i=0, 1, …, k, with k ≥ 1.  Each H_i
is a fully controllable pure stochastic graph, by
Lemma <ref>.

Also, for i=1, …, k, H_i-1 is a subgraph of H_i, with
∅≠W_i-1⊊W_i and
_i-1⊊_i, by Lemmas <ref>
and <ref>, and since κ_1 > 1.

 Let _1 = κ_1{b_1}.  For i=2,
…, k, define _i via Lemma <ref>, choosing
_i so that (_i)W_i-1=∅
whenever possible.





  Let hypotheses and notation be as above.

Suppose 1 ≤ i ≤ k.

 Then 3mu_i τ∈,  for every 2muτ∈.



If (_i)⊆W_iW_i-1, then the lemma's
assertion follows from Lemma 7.3(b)(i) in <cit.>.



Otherwise, i>1.  Let ∈_i be as per Lemma <ref>.
There exists a sequence of action edges





    ()=v_1   v_2
             ⋯ v_m
              v_m+1=(b_i),


for some m ≥ 1, with a_j∈_i,
v_j=(a_j), and v_j+1∈(a_j), for all j=1, …, m.

Moreover, v_1 ∈ W_i-1, v_j∉W_i-1, for j = 2, …,
m, and v_m+1=(b_i)∉W_i-1-1mu0.5mu(_i).



Suppose _iτ∉, for some τ∈.
Let  be a minimal nonface of , with
∅≠⊆_iτ.  Some or all of
the actions {a_1, …, a_m} lie in .

 Certainly ∈, again by Lemma 7.3(b)(i) in <cit.>.

Since  is a minimal nonface,  is the only action of
 with source ().   Since τ∈,
(_i) ⊆ W_i-1.  The
actions in _i all have distinct sources.  Thus no action
in  other than a_j (if a_j is even in ) can have
source v_j, for j = 2, …, m.



Consequently, there is a nonzero probability that the system will
transition to and stop at a state outside () when started
at (), while moving under actions of .  Some action of
 therefore moves off (), which is a contradiction.






Let hypotheses and notation be as above.



Then -2.25mu_i=1^k_i1mu = W_k - 1.



By Construction <ref>, Lemma <ref>, and
subsequent comments,





    _i=1^k_i = ∑_i=1^k_i = ∑_i=1^kℓ_i
         = ∑_i=1^kW_iW_i-1 = ∑_i=1^k(W_i - W_i-1)
         = W_k - 1.











 §.§ Informative Action Release Sequences from Expansive Sets of Actions

Informative Action Release Sequences from Expansive Sets of Actions

This subsection shows how the constructions of the previous
subsection produce informative action release sequences.
Some notational abbreviations will be useful:






  
Notation and Terminology:


  * Rather than merely write sequences of actions, b_1, …,
  b_m, we may write sequences of sets of actions _1, …,
  _m, assuming the sets _1, …, _m are nonempty
  and pairwise disjoint.

  The meaning of a set _i of actions is to indicate a multiplicity
  of sequences of actions, one for each possible permutation of the
  actions in the set _i.  The sequence of sets _1, …,
  _m represents all possible orderings of the actions
  _i=1^m_i consistent with the top-level ordering
  _1, …, _m.   Here, “consistent” means actions in
  _i must appear before actions in _j whenever i < j,
  but the ordering is otherwise unconstrained.

  For example, the sequence of sets {a, b}, {c}, {d, e, f}
  represents 12 sequences of actions:

  


   
    [ a,b,c,d,e,f a,b,c,e,f,d a,b,c,f,d,e a,b,c,f,e,d a,b,c,e,d,f a,b,c,d,f,e; b,a,c,d,e,f b,a,c,e,f,d b,a,c,f,d,e b,a,c,f,e,d b,a,c,e,d,f b,a,c,d,f,e;             ]


  



  * We say that a sequence _1, …, _m of sets of
  actions is informative for G if each of the
  sequences of actions it represents is an informative action release
  sequence for graph G.


  * In place of a singleton set, we may also simply write the
  action it contains.  For instance, we could write the top-level
  sequence in the example above as {a, b},  c, {d, e, f}.






 Suppose G=(V,) is a fully controllable pure stochastic graph
with n = V > 1. 

 Let σ be a maximal strategy in .



From G and 1muσ construct H_1, …,
H_k and _1, …, _k, with k ≥ 1,
as per Construction <ref> on
page expandminnonfaces, Lemma <ref> on
page fullexp, and the definitions and notation of
page Hidefs.



Then, for each i, with 1 ≤ i ≤ k, the sequence _i,
_i-1, …, _1 is informative for H_i.



By induction on i.

 Let i, with 1 ≤ i ≤ k, be given.



The set _i is a nonempty proper subset of a minimal
nonface of  and thus of .   By Lemma <ref>
on page minnonfaceiars, every ordering of actions in
_i is an informative action release sequence for H_i.

 Moreover, _i∈.



If i=1, these observations establish the base case.



If i > 1, then inductively _i-1, …, _1
is informative for H_i-1 and 
_i-1⋯_1 ∈.

By Corollary <ref> on page indepexp, _i
τ∈, for every τ∈.  By construction, no
action in _i is an action in the graph H_i-1.
Therefore, by Lemma <ref> on
page combinesubgraphiars, _i, _i-1,
…, _1 is informative for H_i.  Moreover,
_i ⋯_1 ∈, since,
for instance,
_i ⋯_1⊆σ.






Let the hypotheses and notation be as for Lemma <ref>.

 For each i with 1 ≤ i ≤ k, the sequence _i,
_i-1, …, _1 is informative for G.



By the previous lemma, _i, _i-1, …,
_1 is informative for H_i.  The comment after the
statement of Lemma <ref> on
page combinesubgraphiars establishes the corollary.









 §.§ An Informative Action Release Sequence from a Quotient

An Informative Action Release Sequence from a Quotient


The loop in Construction <ref> may end in step 4(d)
(on page qloopstepd) with τ_k=∅.  This will occur
if and only if W_k=V.  In that case, Corollary <ref>
(above) and Corollary <ref> (on
page expandingcard) imply that the sequence _k,
…, _1 provides an informative action release sequence
for G of length n-1, with all actions of the sequence contained in
σ, and with n=V>1.

Otherwise, the following lemma ensures that one may add a prefix of
informative actions to that sequence whenever one can find an
informative sequence in the quotient graph G/W_k.


 Suppose G=(V,) is a fully controllable pure stochastic graph
with n = V > 1. 
 Let σ be a maximal strategy in .



From G and σ construct k, W_k, τ_k,
H_k, and _1, …, _k, as per
Construction <ref> on
page expandminnonfaces, Lemma <ref> on
page fullexp, and the definitions and notation of
page Hidefs.  (Recall that k ≥ 1.)



Suppose further that a^'_1, …, a^'_ℓ is an
informative action release sequence for G/W_k, with ℓ≥ 1
and {a^'_1, …,
a^'_ℓ}⊆τ^'_k∈Δ_G/W_k.



Then a_1, …, a_ℓ, _k, …,
_1 is informative for G, with all actions
contained in σ.



By construction, {a_1, …,
a_ℓ}⊆τ_k⊆σ and
_i=1^k_i ⊆σ.



By Lemma <ref> on page expfullcontrol, H_k
is a fully controllable subgraph of G.

 Also, ∅≠ W_k⊊ V.

By Lemma <ref> on page expandingiars,
_k, …, _1 is informative for H_k.
Any informative sequence of actions formed from _k,
…, _1 is a subset of σ, therefore convergent in
both G and H_k.

Corollary <ref> on
page combinequotientgraphiars therefore establishes the desired
result.





The following theorem instantiates Theorem <ref> of
page longiars for pure stochastic graphs:

0

Let G=(V,) be a fully controllable pure stochastic graph
with n = V > 1.

Suppose σ is a maximal strategy in .

Then σ contains an informative action release sequence for
G of length at least .135emn-1.



By induction on n.




Base Case:  n=2.



In this case,  consists of two (nonempty) maximal strategies, one
for each state in V.  (The strategy for state v consists of all
actions with source v that are not deterministic self-loops.  The
strategy converges to the other state.)  Any single action in one of
these strategies constitutes an informative action release sequence
for G and is contained in the given strategy.




Inductive Step:  n>2.



From G and σ construct k, W_k, τ_k, and
_1, …, _k, using
Construction <ref> on
page expandminnonfaces, Lemma <ref> on
page fullexp, and subsequent comments.
Recall that k ≥ 1.



As discussed on page iarsfromquotient, if
τ_k=∅, then the sequence _k, …,
_1 provides an informative action release sequence for G
of length n-1, consisting of actions in σ.



Otherwise, let ℓ = VW_k.  Then ℓ > 0.  The
quotient graph G/W_k is pure stochastic and fully controllable, by
Fact 3 on page quotientfacts.  It has state space
V^'=(VW_k){}, with  representing
all of W_k identified to a single state.



Since the minimal nonface κ_1 in
Construction <ref> contains at least two actions,
W_k contains at least two states.  Therefore 2 ≤V^'
< n.  Inductively, the theorem holds for graph G/W_k and maximal
strategy τ^'_k, producing an informative action release
sequence a^'_1, …, a^'_ℓ for G/W_k with
{a^'_1, …,
a^'_ℓ}⊆τ^'_k∈Δ_G/W_k.
By Lemma <ref>, a_1, …, a_ℓ, _k,
…, _1 is informative for G, with all actions
contained in σ.  Any consequent informative action release
sequence has length ℓ + _i=1^k_i =
VW_k + (W_k - 1) = n - 1, by
Corollary <ref> on page expandingcard.






 §.§ Examples for Pure Stochastic Graphs

Examples for Pure Stochastic Graphs

This subsection shows how the proof of Theorem <ref>
produces informative action release sequences for some pure stochastic
graphs and strategies.  For clarity, figures discard self-loops.




  §.§.§ A Directed Graph with Several Cycles




Consider again the strongly connected directed graph G and maximal
strategy σ of Ex241_GraphSigma on
page Ex241_GraphSigma.  Earlier, we viewed G as a pure
nondeterministic graph with different hierarchical cyclic subgraphs.
Now, we view G as a pure stochastic graph and apply
Construction <ref> to obtain an informative action
release sequence of length 5 for G, contained in σ.




For this example, it turns out that the loop of step 4 in the
construction runs once, ending with k=1, but without having covered
the entire state space of the graph.  Consequently, as indicated by
Theorem <ref>'s inductive proof, one needs to invoke the
construction again, on a quotient graph.  Again, the loop runs only
once.  In total, there are three invocations of the construction.  The
synopses below show how local variables in the construction are instantiated.




  * In the first invocation of Construction <ref>,
  the graph is G as in Ex241_GraphSigma and the maximal
  strategy is σ={e_2, e_5, a_2, a_3, a_5, a_6}.  For g, one
  may use either state in σ's goal set {1, 4}.  Using
  g=1, one finds b_1=a_1, yielding the minimal nonface
  κ_1={a_1, a_2, a_3}.  Thus W_1={1,2,3}.  The comments
  at the top of page commentszero produce
  _1={a_2, a_3}.

  Running the loop of step 4 in the construction, with i=1, one
  obtains ξ_1={e_5, a_5, a_6}.  In G/W_1, ξ^'_1
  has a single maximal extension, namely τ^'_1={e^'_2,
  e^'_5, a^'_5, a^'_6}.   Ex241_GWtau1
  shows both G/W_1 and τ^'_1, with  representing
  all of W_1 identified to a singleton.

  Since τ_1⊆σ, the loop ends with k=1.


  * In the second invocation of
  Construction <ref>, the graph is G/W_1 and the
  maximal strategy is τ^'_1={e^'_2, e^'_5,
  a^'_5, a^'_6}.  The strategy has goal state 4, so let
  g=4.  Therefore, in this invocation of the construction,
  b^1mu'_1=a^'_4, yielding the minimal nonface
  κ^'_1={a^'_4, a^'_5, a^'_6}.  (We use
  single prime notation to indicate actions in G/W_1, including
  references to local variables within this invocation of
  Construction <ref>.)

  We now write U_1 for (κ^'_1), in order to avoid
  confusion with the earlier W_1.  Thus U_1 = {4, 5, 6}.  The
  comments at the top of page commentszero produce
  ^'_1={a^'_5, a^'_6}.

  (Below, we will now also use double prime notation, specifically to
  indicate actions in (G/W_1)/U_1, including references to local
  variables within Construction <ref>.  We therefore
  write ξ^'_1 in place of ξ_1 in step 4(b) and
  ξ^''_1 in place of ξ^'_1 in step 4(c).)

  Running the loop of step 4, with i=1, one obtains
  ξ^'_1={e^'_2}.  In (G/W_1)/U_1,
  ξ^''_1 has a single maximal extension, namely
  itself.  We refer to that extension as
  ρ^0.5mu''_1, in order to avoid confusion with
  the earlier τ_1.  Ex241_GWUrho1 shows both (G/W_1)/U_1
  and ρ^''_1, with  as before and
  1mu representing all of U_1 identified to a
  singleton.

  Since ρ^'_1⊆τ^'_1, the loop ends with k=1.


  * Since the graph (G/W_1)/U_1 has only two states, one could now
  simply refer to the base case in the proof of
  Theorem <ref>.  However, we will invoke
  Construction <ref> yet a third time, with graph
  (G/W_1)/U_1 and maximal strategy
  ρ^''_1={e^''_2}.  This strategy has
  goal state , thus yielding minimal nonface
  κ_1^''={e^''_2, e^''_5}
  with source set {, }.  The comments at the top
  of page commentszero produce the expansive set of actions
  ^''_1={e^''_2}.  The loop ends
  because the source set is the entire state space, as discussed at
  the beginning of Section <ref> on
  page iarsfromquotient.





Finally, one assembles the various expansive sets in reverse order of
the recursive invocations of Construction <ref>.
This process produces the following sequence of sets of actions in
G:





    {e_2},  {a_5, a_6},  {a_2, a_3}.


That sequence of sets represents four informative action release
sequences for G, each consisting of actions in σ:





    [ e_2, a_5, a_6, a_2, a_3 e_2, a_5, a_6, a_3, a_2; e_2, a_6, a_5, a_2, a_3 e_2, a_6, a_5, a_3, a_2;                         ]





(We know from Section <ref> that σ
also contains other informative action release sequences.)

















  §.§.§ A Pure Stochastic Graph


Ex251_GraphSigma depicts a fully controllable pure
stochastic graph G, along with a maximal strategy that contains an
action with stochastic transitions.  The strategy complex 
appears in Ex251_DGA, along with G's action relation.
The maximal strategy under consideration is σ^+_3.

Unlike in a pure nondeterministic graph, cycling is permitted in a
pure stochastic graph, so long as the cycling is transient.  The
definition of “moves off” from page movesoff captures this
distinction.  For instance, in the current example, {a_1, a_2} is
a convergent (nonmaximal) strategy, with goal state #3.  The set of
actions {a_1, a_2} would not.10em be convergent if
action a_1 were nondeterministic, since then an adversary could
force infinite cycling between states #1 and #2.  However, a_1 is
stochastic, so there is a nonzero probability that the system will
exit such a cycle, transitioning to state #3 instead.  The precise
transition probabilities of action a_1 affect expected convergence
times, as discussed in <cit.>, but not
overall convergence.



Given G and σ=σ^+_3={a_1, a_2, d_2} as in
Ex251_GraphSigma, Construction <ref> computes
as follows:







  * There is one state outside (σ)={1,2}, so g=3.        Action b_1 in the construction should be an action with source
      g, meaning it is action a_3 of Ex251_GraphSigma.


  * One may then use minimal nonface κ_1={d_2, a_3}.
  (Another possibility is {a_1, a_2, a_3}.)


  * So _1 = {d_2, a_3} and W_1 = {2, 3}.


  * Now the loop of the construction runs:




5.64in




  i=1:




  * Ex251_GWtau1 depicts graph G/W_1, omitting
      the self-looping actions at state .


  * ξ_1=a∈σ(a)∉W_1={a_1}.


  * ξ^'_1 is not maximal in
      Δ_G/W_1.  It has unique maximal extension
      τ^'_1 = {a^'_1, d^1mu'_1}.


  * τ_1 ⊈σ.  Since
      τ_1σ={d_1}, b_2=d_1.  Thus κ_2 =
      {d_1, a_2}, _2 = _1 κ_2 = {d_2, a_3,
      d_1, a_2}, and W_2 = W_1 (κ_2) = {1, 2,
      3}.







  i=2:




  * Graph G/W_2 = ({}, ∅), with  representing
      all states of G identified to a singleton.   So
      Δ_G/W_2={∅}, the empty
      simplicial complex.


  * ξ_2=∅.


  * ξ^'_2 is maximal in Δ_G/W_2,
      so τ^'_2=∅.


  * τ_2⊆σ, so the loop ends, with k=2.









Lemma <ref> and subsequent comments construct
expansive sets _1 and _2 as follows (variable
bindings for g, W_1, W_2, b_1, b_2, κ_1, and
κ_2 are as above, actions d_2 and a_2 are as in
Ex251_GraphSigma):




6.1in

   

   
   -4pt

   
  * Let W_0={g}={3}.

   
  * Since W_1W_0= {2} = (κ_1{b_1}),
         _1 = κ_1{b_1} = {d_2}.
          (See also page commentszero.)

   
  * While W_2W_1={1}≠{2}=({a_2})=
         (κ_2{b_2}),
         (b_2)∈(a_2), so _2 = {a_2}.

   






By Corollary <ref>, the sequence _2,
_1 is informative for G, with all actions contained in
σ^+_3.  We thus obtain the informative action release
sequence a_2, d_2.   Side note: This is not the only iars
contained in σ^+_3.  The longest such iars consists of all
actions in σ^+_3, in the order a_1, d_2, a_2.






  
Interpretation:   Ex251_A2 depicts _2
as a graph.  The graph consists of two independent two-cycles.
Relationally, we may think of these two two-cycles as two independent
bits of information, forming a basis for informative action release
sequences.  In more general examples (see
Section <ref>), there may be less independence.
Consequently, Lemma <ref> (page fullexp) constructs
expansive sets of actions, which Lemma <ref>
(page expandingiars) then arranges informatively.






  §.§.§ A Pure Stochastic Graph Highlighting Expansive Set Order





We now apply Construction <ref> to the pure
stochastic graph G and maximal strategy σ∈ of
ExH5.  We may let g=1.  1muThen 1mub_1=c_1,
3muκ_1 = {c_1, a_2, e_3}, and W_1 = {1,2,3}.  Thus
_1={a_2,e_3}.  Now ξ_1=∅, so there is a
choice in constructing τ^'_1.  If we choose
τ^'_1={a^'_4}, then τ_1⊈σ and
so b_2=a_4.  There are two minimal nonfaces within σ{a_4}.  Let us use κ_2={a_4, c_2, a_3}.  Thus W_2 =
{1,2,3,4} and the loop ends with k=2.  Constructing _2
involves a choice since actions c_2 and a_3 each have action
a_4-1.5mu's source as a target.
Let us pick _2={a_3}.

Corollary <ref> on page expandingiarsG
arranges the expansive sets of actions in the order _2,
_1.  Indeed, both a_3, a_2, e_3 and a_3, e_3,
a_2 are informative action release sequences for G.  Notice that
action e_3 implies action a_3 in relation A.  Consequently, the
order _1, _2 would not  be
acceptable.



Comment: We can lengthen a_3, a_2, e_3 to the iars
c_2, a_3, a_2, e_3.  In fact, 12 of the 24 possible
permutations of all the actions in 0.5muσ constitute
informative action release sequences for G.







§ COUNTEREXAMPLES FOR MIXED GRAPHS

Counterexamples for Mixed Graphs


The assertion of Theorem <ref> on page longiars
need not hold for graphs containing a mix of deterministic,
nondeterministic, and stochastic actions.  Of course, there are many
settings in which the assertion does hold.  For instance, if one can
find a hierarchical cyclic subgraph with the same state space as the
given graph, then one can again prove the theorem, even if the graph
contains stochastic actions.  All the proof needs is for the
hierarchical cyclic subgraph to be composed only of deterministic and
nondeterministic actions.  Absent such structure, it is very easy to
construct a counterexample involving a mix of deterministic,
nondeterministic, and stochastic actions.  With some added effort, one
may also construct counterexamples involving maximal strategies that
attain singleton goals.  This section presents such counterexamples.





 §.§ A Counterexample with a Large Goal Set

A Counterexample with a Large Goal Set



Consider the graph and action relation of Ex238_top.  The
graph contains two actions that have identical action edges, but
differ in that one action is stochastic and the other action is
nondeterministic.  The stochastic action is c_1 = 1 →
p1.25mu{2,3,4}, for some probability distribution p
ascribing nonzero probabilities to each target, and the
nondeterministic action is a_1 = 1 →{2,3,4}.
Additionally, the graph contains three deterministic action, b_i = i
→ 1, for i=2,3,4.



The graph is fully controllable based just on the set of actions
{c_1, b_2, b_3, b_4}, as one can see from the action relation or
as follows: The system can attain state #1 from any other state by
using strategy {b_2, b_3, b_4}.  The system can reach a desired
state in the set {2, 3, 4} by repeatedly trying to do so using the
stochastic action c_1, cycling back to state #1 if that action
transitions to the wrong state.  For instance, strategy {c_1, b_2,
b_3} will converge to state #4.



None of the actions {b_i} can be in a strategy together with
action a_1, but action c_1 can be.  In fact, σ_234={c_1,
a_1} is a maximal strategy.  The longest informative action release
sequence contained in σ_234 is the strategy itself, revealed
in the order c_1, a_1.  That iars has length 2, which is less than
the number 3 demanded by Theorem <ref>.



One may easily generalize this example to graphs with n states, for
n>4, such that some maximal strategy consists of only two actions
and therefore has an iars of length at most 2.



Key to this example is the oddity of having two nearly identical
actions, with the only difference being that one action is stochastic
and the other is nondeterministic.  The graph would not.12em be fully controllable with just the nondeterministic action.
The stochastic action is needed to “sample with replacement”, i.e.,
“try and try again, until success”.

From a worst-case perspective, the strategy consisting of the nearly
identical stochastic and nondeterministic actions amounts to no more
than the nondeterministic action itself.  So, why even include the
nondeterministic action in the graph?

The answer is that it is a choice a system may make.  Executing the
stochastic action may entail greater cost than executing the
nondeterministic action, because the nondeterministic action relieves
the system of guaranteeing stochastic behavior.  That may be desirable
in some settings.  At first it seems hardly so, because the only goal
set one can attain using any strategy containing the nondeterministic
action is a very large set (consisting of n-1 states in the
generalized version).  However, not caring about precise transitions
is sensible when the graph is part of a larger graph and it does not
matter what state the system passes through as a subgoal while
attaining some overall goal.  The next subsection explores such graphs
further.





 §.§ A Counterexample with a Small Goal Set

A Counterexample with a Small Goal Set

Previously, we saw the basis for a family of counterexamples in which
the graph has n states but contains a maximal strategy consisting of
two actions with a goal set of size n-1.  One might therefore
hypothesize that Theorem <ref> should merely assert the
existence of an informative action release sequence of length n-k,
with k being the size of the goal set.  In fact, such a theorem
would also be false, since one can construct counterexamples to
Theorem <ref> using strategies that have goal sets of size 1,
as this subsection demonstrates.




In constructing such counterexamples, one may take the fully
controllable graph on n states of the previous subsection and glue
the set {2, …, n} to another graph, permitting direct motion
from any state in {2, …, n} to a new state, #(n+1).  In
order to retain full controllability, the system also needs to be able
to move back from state #(n+1).  In this subsection, we use a
single nondeterministic action.  In the next subsection, will will use
n-1 different nondeterministic actions.  Numerous variations exist.



Ex238_GraphArel replicates a counterexample taken from
<cit.>, showing a graph and its action relation.
Maximal strategy σ_5={a_1, d_2, d_3, d_4, c_1} converges to
singleton goal state #5.  The strategy contains 5 actions, but the
longest informative action release sequences contained in σ_5
have length 3, which is less than the 4 demanded by
Theorem <ref>.  The reason no longer iars exists is because
any one of the “downward” actions in the set {d_2, d_3, d_4}
implies the other two.  That fact is clear from the action relation,
but can also be understood as follows: First, knowing that a strategy
contains one of the actions d_2, d_3, or d_4 means the strategy
cannot contain the nondeterministic action b_5.  Second, for a
maximal strategy, not containing b_5 means the strategy must contain
the entire set {d_2, d_3, d_4}.





 §.§ A Counterexample with a Small Goal Set and Nonequivalent Inferences

A Counterexample with a Small Goal Set and Nonequivalent Inferences

Finally, we construct a counterexample similar to that of
Ex238_GraphArel, but without requiring equivalence between the
deterministic downward actions flowing into state #(n+1).  Instead,
any -0.5mutwo of these downward actions will imply
all the downward actions.  One may achieve this inference by replacing
the single nondeterministic action at state #(n+1) with n-1
different nondeterministic actions.  Each of these actions now has a
target set of size n-2 contained within the set {2, …, n}.
With this counterexample in mind, one may see yet another infinite
family of counterexamples, parameterized now by the number of downward
actions {d_i}_i=2^n that may be released before all are
implied (with n sufficiently large).




Ex239_Graph shows a graph G in three panels.  Ex239_Arel
shows G's action relation.  There are six states.  Four of the
graph's deterministic actions, namely d_2, d_3, d_4, d_5,
transition to state #6, while four nondeterministic
actions, e_2, e_3, e_4, e_5, transition away from
state #6.  Each of those nondeterministic actions has a target set of
size three that is a subset of {2, 3, 4, 5}.  The following table
shows which pairings of d_i and e_j actions create minimal
nonfaces in .  One sees that any single action drawn from {d_2,
d_3, d_4, d_5} is potentially consistent with strategies not
involving any other d_i action, but that any two of the {d_i}
actions imply them all.  (Any two of the {d_i} eliminate all
{e_j}, so the given maximal strategy must contain all {d_i}.)





    [     e_5 e_4 e_3 e_2; d_2                ; d_3                ; d_4                ; d_5                ;     ]






Maximal strategy σ-4mu=-4mu{a_1, d_2, d_3, d_4,
d_5, c_1} converges to goal state
#6 and contains
-0.05mu6-0.75mu actions.  However, since at most two of
the actions {d_i} are informative, the longest informative action
release sequences contained in σ have length 4.  That is less
than the 5 demanded by Theorem <ref>.












§ ACKNOWLEDGMENTS

tocsectionAcknowledgments

Many thanks to Rob Ghrist, Steve LaValle, Ben Mann, and Matt Mason,
for advice and support related to this research and its earlier
foundations within SToMP.









References
tocsectionReferences

10

paths:bjorner-welker
A. Björner and V. Welker.
Complexes of directed graphs.
SIAM J. Discrete Math, 12(4):413–424, 1999.

paths:DinurNissim
I. Dinur and K. Nissim.
Revealing information while preserving privacy.
In Proceedings of the 22nd ACM Symposium on Principles of
  Database Systems, pages 202–210, 2003.

paths:dworkcacm
C. Dwork.
A firm foundation for private data analysis.
Communications of the ACM, 54(1):86–95, 2011.

paths:strategies
M. A. Erdmann.
On the topology of discrete strategies.
International Journal of Robotics Research, 29(7):855–896,
  2010.

paths:plans
M. A. Erdmann.
On the topology of discrete planning with uncertainty.
In A. Zomorodian, editor, Advances in Applied and Computational
  Topology, pages 147–194. AMS, 2012.

paths:privacy
M. A. Erdmann.
Topology of privacy: Lattice structures and information bubbles for
  inference and obfuscation.
http://arxiv.org/abs/1712.04130, 2017.

paths:feller
W. Feller.
An Introduction to Probability Theory and Its Applications,
  volume 1.
John Wiley & Sons, New York, third edition, 1968.

paths:hultman
A. Hultman.
Directed subgraph complexes.
Elec. J. Combinatorics, 11(1):R75, 2004.

paths:jonsson
J. Jonsson.
Simplicial Complexes of Graphs.
PhD thesis, Department of Mathematics, KTH, Stockholm, Sweden, 2005.

paths:ktII
S. Karlin and H. M. Taylor.
A Second Course in Stochastic Processes.
Academic Press, New York, 1981.

paths:munkres
J. R. Munkres.
Elements of Algebraic Topology.
Addison-Wesley, Menlo Park, CA, 1984.

paths:netflix
A. Narayanan and V. Shmatikov.
Robust de-anonymization of large sparse datasets.
In Proceedings of the IEEE Symposium on Security and Privacy,
  pages 111–125, 2008.

paths:rotman
J. J. Rotman.
An Introduction to Algebraic Topology.
Springer-Verlag,  New York, 1988.

paths:sweeneykanon
L. Sweeney.
k-anonymity: A model for protecting privacy.
International Journal of Uncertainty, Fuzziness and
  Knowledge-Based Systems, 10(5):557–570, 2002.

paths:wachs
M. L. Wachs.
Poset Topology: Tools and Applications.
IAS/Park City Mathematics Institute, Summer 2004.
 Also available here: http://arxiv.org/abs/math/0602226.






