pith. sign in

arxiv: 1906.11513 · v1 · pith:FG57TEXVnew · submitted 2019-06-27 · 🧮 math.CO · cs.DM

Deception, Delay, and Detection of Strategies

Michael Erdmann This is my paper

Pith reviewed 2026-05-25 15:08 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords deceptiondelaydetectionstrategiesgraphsstrategy complexhomotopynondeterministic control
0
0 comments X

The pith

Maximal strategies in fully controllable graphs can shroud their identities, requiring at least n-1 action revelations before the strategy is fully known, with at least (n-1)! such sequences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that in graphs modeling systems with nondeterministic or stochastic control that are fully controllable, for each target state there exists a maximal strategy reaching it from everywhere. This strategy can be revealed action by action in orders that prevent any early deduction of the remaining actions, so that the complete strategy is only identified after at least n-1 revelations where n is the number of states. There exist at least (n-1)! such revealing orders. This matters for understanding how agents can delay or deceive about their plans in uncertain environments. The result extends an earlier sketch by providing full details using the fact that the strategy complex is homotopic to a sphere.

Core claim

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. Moreover, the strategy contains at least (n-1)! such informative action release sequences, each of length at least n-1.

What carries the argument

Informative action release sequences in maximal strategies, guaranteed by the strategy complex being homotopic to a sphere.

If this is right

  • Agents can delay identification of their goal-attaining strategies by choosing the order of revealing actions.
  • Systems with errorful control admit strategies that support bluffing or deception capabilities.
  • The number of ways to shroud a strategy is at least (n-1)! for n states.
  • Earlier sketches of proofs for the existence of at least one such sequence are now fully detailed.
  • Detection of deceit becomes possible by observing whether revealed actions match possible shrouding sequences.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • These shrouding mechanisms could model bluffing in game-theoretic settings with imperfect information.
  • Practical control systems might be designed to exploit or defend against such delayed strategy identification.
  • Similar homotopy arguments might apply to other combinatorial objects beyond graphs to find hidden structures.
  • The detection aspect suggests algorithms for inferring hidden strategies from partial revelations.

Load-bearing premise

The strategy complex of a fully controllable nondeterministic or stochastic graph is homotopic to a sphere.

What would settle it

A counterexample graph with n states that is fully controllable but has a maximal strategy with fewer than (n-1)! informative action release sequences of length at least n-1.

Figures

Figures reproduced from arXiv: 1906.11513 by Michael Erdmann.

Figure 1
Figure 1. Figure 1: Four islands along with some directional bridges connecting the islands. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: describes the islands and bridges of [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Two simplicial complexes derived from the relation of Figure 2. The two complexes [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A river along with islands that create three passages and consequent currents of [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Left Panel: A directed graph that describes the possible transitions a boat might make while traversing the river of [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 5
Figure 5. Figure 5: σ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 u1, u2, and u3, with ui = i → i+3.) • The strategy σ123 only makes sense for a boat with a powerful enough motor to traverse the strong current of [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Left Panel: Relation describing permissible strategies for attaining state #7 in [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Left Panel: Simplified version of the river from [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Relation describing permissible strategies [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Two simplicial complexes derived from the relation of Figure 8, with underlying [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Simplicial complex derived from the relation of Figure 8, with underlying vertex [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Here is a version of the relation from Figure 8 and the simplicial complex from [PITH_FULL_IMAGE:figures/full_fig_p016_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Left Panel: A relation describing the permissible strategies for a boat that is incapable of moving upstream over the strong current of [PITH_FULL_IMAGE:figures/full_fig_p017_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: In the complex of Figure 12, the downstream transition [PITH_FULL_IMAGE:figures/full_fig_p018_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Left Panel: A deterministic graph with four states and four actions that form a directed cycle. Middle Panel: The graph’s action relation A, along with each maximal strategy’s goal. Right Panel: The Dowker attribute complex ΦA (which is necessarily the same as the strategy complex ∆G). It is a hollow tetrahedron. Vertices are actions and triangles are maximal strategies, as indicated by the labels. As a f… view at source ↗
Figure 15
Figure 15. Figure 15: A pure nondeterministic graph with four states, 1 [PITH_FULL_IMAGE:figures/full_fig_p029_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Left Panel: The action relation A for the graph G of [PITH_FULL_IMAGE:figures/full_fig_p030_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: The Dowker association complex ΨA for the action relation of [PITH_FULL_IMAGE:figures/full_fig_p031_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Left Panel: Modified relation from [PITH_FULL_IMAGE:figures/full_fig_p032_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: Left Panel: A pure nondeterministic graph with four states, 1, 2, 3, 4, four deterministic actions, e1, e2, e3, e4, and two nondeterministic actions, a1, a2. The graph here is the graph from [PITH_FULL_IMAGE:figures/full_fig_p033_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: The 1-skeleton of the strategy complex ∆ [PITH_FULL_IMAGE:figures/full_fig_p034_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: A view of graph G from [PITH_FULL_IMAGE:figures/full_fig_p052_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: Left Panel: A pure nondeterministic graph G with four states, 1, 2, 3, 4, four deterministic actions, e1, e2, e3, a2, and three nondeterministic actions, a1, a3, b4. Right Panel: G’s action relation and goal sets. (This figure is a copy of Figures 47 and 48 in [6].) [PITH_FULL_IMAGE:figures/full_fig_p053_22.png] view at source ↗
Figure 24
Figure 24. Figure 24: Action relation and goal sets for the graph of Figure 23. The row corresponding to [PITH_FULL_IMAGE:figures/full_fig_p055_24.png] view at source ↗
Figure 23
Figure 23. Figure 23: Left Panel: A directed graph G, consisting of six states and eight directed edges. Right Panel: A maximal strategy σ ∈ ∆G, depicted by its directed edges. A a1 a2 a3 a4 a5 a6 e2 e5 σ • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • Goal {1, 4} 4 {3, 4} 1 5 2 3 {1, 6} 6 {3, 6} [PITH_FULL_IMAGE:figures/full_fig_p055_23.png] view at source ↗
Figure 25
Figure 25. Figure 25: A view of graph G from [PITH_FULL_IMAGE:figures/full_fig_p056_25.png] view at source ↗
Figure 26
Figure 26. Figure 26: A hierarchical cyclic subgraph H of graph G from [PITH_FULL_IMAGE:figures/full_fig_p057_26.png] view at source ↗
Figure 27
Figure 27. Figure 27: Left Panel: A directed graph G, consisting of four states and seven directed edges. Right Panel: A maximal strategy σ ∈ ∆G, depicted by its directed edges. A a1 a2 a3 b1 b2 e2 e4 • • • • • • • • • • • • • • • • σ • • • • • Goal 1 4 2 3 3 [PITH_FULL_IMAGE:figures/full_fig_p058_27.png] view at source ↗
Figure 28
Figure 28. Figure 28: Action relation and goals for the graph of Figure 27. The row corresponding to [PITH_FULL_IMAGE:figures/full_fig_p058_28.png] view at source ↗
Figure 29
Figure 29. Figure 29: A hierarchical cyclic subgraph H of graph G from [PITH_FULL_IMAGE:figures/full_fig_p059_29.png] view at source ↗
Figure 30
Figure 30. Figure 30: Left Panel: The quotient graph G/W1, with G as in [PITH_FULL_IMAGE:figures/full_fig_p066_30.png] view at source ↗
Figure 31
Figure 31. Figure 31: Left Panel: The quotient graph (G/W1)/U1, with G/W1 as in [PITH_FULL_IMAGE:figures/full_fig_p067_31.png] view at source ↗
Figure 32
Figure 32. Figure 32: Left Panel: A pure stochastic graph G, consisting of three states, four deterministic actions, and one stochastic action. The stochastic action is a1 = 1 → p{2, 3}; its action edges appear as dashed lines. The precise probability distribution p is not significant here, except to indicate that each of the transitions 1 → 2 and 1 → 3 has nonzero probability. Right Panel: The maximal strategy σ + 3 ∈ ∆G, dep… view at source ↗
Figure 33
Figure 33. Figure 33: The strategy complex ∆G of the graph G from [PITH_FULL_IMAGE:figures/full_fig_p068_33.png] view at source ↗
Figure 34
Figure 34. Figure 34: Left Panel: The quotient graph G/W1, with G as in [PITH_FULL_IMAGE:figures/full_fig_p069_34.png] view at source ↗
Figure 35
Figure 35. Figure 35: The set of actions A2 viewed as a graph. Construction 29 produces this set when applied to graph G and maximal strategy σ + 3 of [PITH_FULL_IMAGE:figures/full_fig_p070_35.png] view at source ↗
Figure 36
Figure 36. Figure 36: The left panel displays a pure stochastic graph [PITH_FULL_IMAGE:figures/full_fig_p070_36.png] view at source ↗
Figure 37
Figure 37. Figure 37: Left Panel: A graph G with four states, 1, 2, 3, 4, three deterministic actions, b2, b3, b4, one nondeterministic action, a1, and one stochastic action, c1. Right Panel: G’s action relation and goal sets. Consider the graph and action relation of [PITH_FULL_IMAGE:figures/full_fig_p071_37.png] view at source ↗
Figure 38
Figure 38. Figure 38: Left Panel: A graph with five states, 1, 2, 3, 4, 5, six deterministic actions, d2, d3, d4, b2, b3, b4, two nondeterministic actions, a1, b5, and one stochastic action, c1. Right Panel: The graph’s action relation and goal sets. (This figure is a copy, with minor notational changes, of Figures 67 and 68 in [6].) [PITH_FULL_IMAGE:figures/full_fig_p072_38.png] view at source ↗
Figure 39
Figure 39. Figure 39: A graph G with eight deterministic actions, one stochastic action, and five nondeterministic actions, depicted in three panels [PITH_FULL_IMAGE:figures/full_fig_p074_39.png] view at source ↗
Figure 40
Figure 40. Figure 40: Action relation and goal sets for the graph [PITH_FULL_IMAGE:figures/full_fig_p075_40.png] view at source ↗
read the original abstract

Homology generators in a relation offer individuals the ability to delay identification, by guiding the order via which the individuals reveal their attributes (see arXiv:1712.04130). 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 $\sigma_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 $\sigma_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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims that for any fully controllable nondeterministic or stochastic graph on n states, each state v admits a maximal strategy σ_v converging to v from every other state, and that the actions of σ_v admit at least (n-1)! release orders of length ≥ n-1 with the property that the full strategy is identified only after at least n-1 actions are revealed and no revealed action is inferable from those already shown. The justification rests on the strategy complex being homotopic to a sphere. The report states that its primary purpose is to supply the missing details from an earlier sketch (arXiv:1712.04130) that established only the existence of at least one such sequence.

Significance. If the derivation of the factorial multiplicity from the sphere homotopy can be supplied, the result would give a precise combinatorial count of maximal deception sequences in strategy complexes, furnishing a topological account of delayed identification that extends the homology-generator perspective of the cited earlier work. The explicit filling-in of the prior sketch for the weaker statement is a positive step toward reproducibility.

major comments (2)
  1. [Abstract] Abstract: the central claim asserts the existence of at least (n-1)! informative release sequences whose non-inference property follows from the sphere homotopy, yet the manuscript text is described as expanding only the earlier sketch for the weaker 'at least one' statement; no derivation is supplied showing how the homotopy type produces the precise factorial count or the non-inference condition.
  2. [The strategy complex homotopy] The strategy complex homotopy (invoked throughout): the equivalence to a sphere is used as the sole premise guaranteeing both existence and the (n-1)! multiplicity, but the report supplies no steps, edge-case handling, or reference to a prior proof that converts the homotopy type into the stated combinatorial count; this leaves the load-bearing step unexamined.
minor comments (1)
  1. [Introduction] The transition between the weaker result of arXiv:1712.04130 and the stronger multiplicity claim could be made explicit by adding a sentence or subsection that isolates which new combinatorial arguments address the factorial count.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the careful reading and for identifying the mismatch between the abstract's claims and the manuscript's actual content and proofs. We respond point-by-point to the major comments.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim asserts the existence of at least (n-1)! informative release sequences whose non-inference property follows from the sphere homotopy, yet the manuscript text is described as expanding only the earlier sketch for the weaker 'at least one' statement; no derivation is supplied showing how the homotopy type produces the precise factorial count or the non-inference condition.

    Authors: The referee correctly notes the inconsistency. The abstract states the stronger (n-1)! result and invokes the sphere homotopy for both existence and multiplicity, but the body explicitly describes the primary purpose as filling in the details of the earlier sketch for at least one sequence. No step-by-step derivation from the homotopy type to the factorial count or non-inference condition is supplied. We will revise the abstract to accurately describe the manuscript's scope and remove the unproven (n-1)! claim. revision: yes

  2. Referee: [The strategy complex homotopy] The strategy complex homotopy (invoked throughout): the equivalence to a sphere is used as the sole premise guaranteeing both existence and the (n-1)! multiplicity, but the report supplies no steps, edge-case handling, or reference to a prior proof that converts the homotopy type into the stated combinatorial count; this leaves the load-bearing step unexamined.

    Authors: We agree that the manuscript invokes the sphere homotopy type without providing the intermediate steps, edge-case analysis, or explicit conversion to the combinatorial (n-1)! count. Since the work is limited to elaborating the existence proof for at least one sequence, this stronger claim is not supported by detailed reasoning in the text. We will revise the relevant sections to clarify the limited scope and ensure all claims are backed by the supplied arguments. revision: yes

standing simulated objections not resolved
  • Derivation of the (n-1)! multiplicity and non-inference property from the sphere homotopy type, with all steps and edge cases.

Circularity Check

1 steps flagged

Homotopy of strategy complex to sphere invoked via self-citation to guarantee (n-1)! release sequences

specific steps
  1. self citation load bearing [Abstract]
    "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 s"

    The shrouding property, non-inference condition, and exact lower bound of (n-1)! informative sequences are asserted immediately after invoking the sphere homotopy; that homotopy type is justified solely by citation to the author's own earlier paper (arXiv:1712.04130), which the text itself describes only as having sketched the weaker 'at least one' case.

full rationale

The paper's central existence and multiplicity claims rest on the homotopy type being a sphere, which is asserted by direct reference to the author's prior arXiv:1712.04130 without re-derivation here. The current work fills details only for the weaker 'at least one' statement from that sketch; the stronger (n-1)! count and non-inference property are presented as following from the cited homotopy without an independent chain shown in this document. This qualifies as load-bearing self-citation but does not reduce any quantity to a fitted parameter or self-definition by construction, leaving independent content in the expanded examples and sketch details.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on one domain assumption drawn from the abstract; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption The strategy complex of a fully controllable nondeterministic or stochastic graph is homotopic to a sphere.
    Invoked in the abstract as the topological foundation that guarantees the existence and count of the informative action-release sequences.

pith-pipeline@v0.9.0 · 5794 in / 1337 out tokens · 35682 ms · 2026-05-25T15:08:03.323170+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · 2 internal anchors

  1. [1]

    Bj¨ orner and V

    A. Bj¨ orner and V. Welker. Complexes of directed graphs. SIAM J. Discrete Math , 12(4):413–424, 1999

    work page 1999

  2. [2]

    Dinur and K

    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

    work page 2003

  3. [3]

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

    work page 2011

  4. [4]

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

    work page 2010

  5. [5]

    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

    work page 2012

  6. [6]

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

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  7. [7]

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

    work page 1968

  8. [8]

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

    work page 2004

  9. [9]

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

    work page 2005

  10. [10]

    Karlin and H

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

    work page 1981

  11. [11]

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

    work page 1984

  12. [12]

    Narayanan and V

    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

    work page 2008

  13. [13]

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

    work page 1988

  14. [14]

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

    work page 2002

  15. [15]

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

    work page internal anchor Pith review Pith/arXiv arXiv 2004