Skip to content

Legal Dynamics Size

This note records the current size accounting for the repo's legal_joint_graph artifacts and the helper used to reproduce the counts:

  • code: notebooks/utils/legal_dynamics.py
  • regression tests: tests/test_legal_dynamics.py

Counting Convention

The tables below use:

  • |S|: number of distinct legal public states
  • |A_joint|: number of joint actions per decision point
  • |S x A_joint|: number of distinct legal (state, joint_action) groups

|S x A_joint| is the right "no duplicate states/actions" count for the strict legality contract used by GraphWorldModelAdapter: each reachable public state should expose every legal joint action exactly once as a state-action group, even when a stochastic environment fans that group out to multiple successor states.

Exact Reachable Counts

These rows are exact for the current default environment parameters:

  • Bertrand / Chicken / Inspection: |S| = 1 + 2^2, |A_joint| = 2^2
  • Congestion with N agents: |S| = 1 + 3^N, |A_joint| = 3^N
  • Pursuit with N agents on the default layout (the implementation retains the historical guard_row(...) helper name): |S| = 44^N, |A_joint| = 5^N
  • DPGG: exact recurrence over (last_joint_action, pot_idx)
  • Ice Duel: exact reachability over ordered position pairs and terminal edge states

| Environment | Agents | Kind | |S| | |A_joint| | |S×A_joint| | Derivation | |---|---:|---|---:|---:|---:|---| | Bertrand | 2 | exact | 5 | 4 | 20 | 1 initial blank state + one state per joint action profile | | Chicken | 2 | exact | 5 | 4 | 20 | 1 initial blank state + one state per joint action profile | | Inspection | 2 | exact | 5 | 4 | 20 | 1 initial blank state + one state per joint action profile | | Dynamic Public Goods Game | 2 | exact | 281 | 4 | 1,124 | exact recurrence over (last_joint_action, pot_idx) | | Ice Duel | 2 | exact | 1,980 | 25 | 49,500 | exact reachability over ordered position pairs with terminal edge states | | Congestion | 2 | exact | 10 | 9 | 90 | 1 initial blank state + one state per ordered per-agent route profile | | Congestion | 3 | exact | 28 | 27 | 756 | 1 initial blank state + one state per ordered per-agent route profile | | Congestion | 4 | exact | 82 | 81 | 6,642 | 1 initial blank state + one state per ordered per-agent route profile | | Congestion | 5 | exact | 244 | 243 | 59,292 | 1 initial blank state + one state per ordered per-agent route profile | | Congestion | 6 | exact | 730 | 729 | 532,170 | 1 initial blank state + one state per ordered per-agent route profile | | Congestion | 7 | exact | 2,188 | 2,187 | 4,785,156 | 1 initial blank state + one state per ordered per-agent route profile | | Congestion | 8 | exact | 6,562 | 6,561 | 43,053,282 | 1 initial blank state + one state per ordered per-agent route profile | | Congestion | 9 | exact | 19,684 | 19,683 | 387,440,172 | 1 initial blank state + one state per ordered per-agent route profile | | Congestion | 10 | exact | 59,050 | 59,049 | 3,486,843,450 | 1 initial blank state + one state per ordered per-agent route profile | | Pursuit Evasion | 2 | exact | 1,936 | 25 | 48,400 | 44^2 ordered agent placements over non-wall cells | | Pursuit Evasion | 3 | exact | 85,184 | 125 | 10,648,000 | 44^3 ordered agent placements over non-wall cells |

Pursuit-3 stochastic fanout limit

The |S×A_joint| count above is a state--joint-action group count, not the number of serialized successor edges. With the current independent 0.1 per-agent slip dynamics, every group can fan out over multiple joint successor positions. The August 2026 fresh build enumerated exactly 85,184 states and 415,886,464 successor edges. Its Python dataclass representation reached 205 GiB RSS, wrote 48,704,852,093 bytes to the atomic temporary pickle, and was OOM-killed before completing the pickle STOP opcode or atomic rename. The file ended in opcode byte 0x94, so its size must not be mistaken for a valid cache.

This is an architectural limit of the current materialized list[Edge] path. More memory alone is not sufficient for the complete pipeline: world-model augmentation clones the edge list and groups it by 10,648,000 state--joint-action keys, and the opponent-model adapter materializes another grouped index. Pursuit-3 is therefore excluded from the fresh primary reward--safety campaign, while Pursuit-2 remains valid. The 48.7 GB atomic temporary file remains in the dedicated Pursuit-3 workspace, and an older 10.9 GB truncation is retained as recovery evidence under /vol/gpudata/oja24-optimisations/exports/omsh/recovery/pursuit3/; no reward or safety result may be reconstructed from either file. A future three-agent run requires compact or procedural transition storage plus streaming/batched augmentation and adapter construction.

The builder now preflights serialized successor fanout rather than only state--joint-action groups. For Pursuit-3 with non-degenerate slip, the conservative bound is 1,331,000,000 successor edges, so both exhaustive-start and reset-reachable builds fail immediately unless allow_large_graph=True is explicitly supplied after memory sizing. Pursuit-2's corresponding bound remains below the default guard.

Export Verification

The following cached exports/**/wm/legal_joint_graph.pkl files were checked directly. In every verified artifact:

  • duplicate state encodings = 0
  • duplicate (src, joint_action, dst) edges = 0

For the simple families, the export counts match the exact formulas above. For Gathering and Markov Stag Hunt, the checked exports show that a simple "public-state only" combinatorial count overestimates the exact reachable legal dynamics because the visible frozen / damaged bits still encode one-step causal history constraints.

| Environment | Agents | Kind | |S| | |A_joint| | |S×A_joint| | Export |S| | Export |S×A_joint| | dup states | dup edges | |---|---:|---|---:|---:|---:|---:|---:|---:|---:| | Bertrand | 2 | exact | 5 | 4 | 20 | 5 | 20 | 0 | 0 | | Chicken | 2 | exact | 5 | 4 | 20 | 5 | 20 | 0 | 0 | | Inspection | 2 | exact | 5 | 4 | 20 | 5 | 20 | 0 | 0 | | Dynamic Public Goods Game | 2 | exact | 281 | 4 | 1,124 | 281 | 1,124 | 0 | 0 | | Congestion | 2 | exact | 10 | 9 | 90 | 10 | 90 | 0 | 0 | | Congestion | 4 | exact | 82 | 81 | 6,642 | 82 | 6,642 | 0 | 0 | | Pursuit Evasion | 2 | exact | 1,936 | 25 | 48,400 | 1,936 | 48,400 | 0 | 0 | | Ice Duel | 2 | exact | 1,980 | 25 | 49,500 | 1,980 | 49,500 | 0 | 0 | | Gathering | 2 | upper_bound | 45,512 | 81 | 3,686,472 | 20,496 | 1,660,176 | 0 | 0 | | Markov Stag Hunt | 2 | upper_bound | 1,135,680 | 25 | 28,392,000 | 177,252 | 4,431,300 | 0 | 0 |

Scaling Upper Bounds

For Gathering and Markov Stag Hunt, the helper currently reports no-duplicate public-state upper bounds for 2..10 agents. These are still useful as scaling estimates, but they are not exact reachable legal-graph counts because the public frozen / damaged bits are not arbitrary labels.

| Environment | Agents | Kind | |S| | |A_joint| | |S×A_joint| | Derivation | |---|---:|---|---:|---:|---:|---| | Gathering | 2 | upper_bound | 45,512 | 81 | 3,686,472 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 2 | upper_bound | 1,135,680 | 25 | 28,392,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history | | Gathering | 3 | upper_bound | 12,840,536 | 729 | 9,360,750,744 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 3 | upper_bound | 29,527,680 | 125 | 3,690,960,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history | | Gathering | 4 | upper_bound | 2,171,806,080 | 6,561 | 14,249,219,690,880 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 4 | upper_bound | 767,719,680 | 625 | 479,824,800,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history | | Gathering | 5 | upper_bound | 252,789,457,744 | 59,049 | 14,926,964,690,325,456 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 5 | upper_bound | 19,960,711,680 | 3,125 | 62,377,224,000,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history | | Gathering | 6 | upper_bound | 22,488,098,658,552 | 531,441 | 11,951,097,639,199,533,432 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 6 | upper_bound | 518,978,503,680 | 15,625 | 8,109,039,120,000,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history | | Gathering | 7 | upper_bound | 1,693,132,963,234,296 | 4,782,969 | 8,098,202,476,027,777,504,824 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 7 | upper_bound | 13,493,441,095,680 | 78,125 | 1,054,175,085,600,000,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history | | Gathering | 8 | upper_bound | 118,173,896,351,863,424 | 43,046,721 | 5,086,998,745,741,582,643,032,704 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 8 | upper_bound | 350,829,468,487,680 | 390,625 | 137,042,761,128,000,000,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history | | Gathering | 9 | upper_bound | 8,082,732,306,895,682,048 | 387,420,489 | 3,131,416,102,793,623,211,024,681,472 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 9 | upper_bound | 9,121,566,180,679,680 | 1,953,125 | 17,815,558,946,640,000,000,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history | | Gathering | 10 | upper_bound | 551,755,855,079,085,724,416 | 3,486,784,401 | 1,923,853,708,650,172,725,235,493,634,816 | no-duplicate public-state bound; exact reachable count is smaller because frozen bits encode one-step line-of-sight history | | Markov Stag Hunt | 10 | upper_bound | 237,160,720,697,671,680 | 9,765,625 | 2,316,022,663,063,200,000,000,000 | no-duplicate public-state bound; exact reachable count is smaller because damaged bits encode one-step maul history |

Simulator disagreement in Markov Stag Hunt (2026-09-20)

The first Stage 1 sweep found one transition in 750,000 where the Markov Stag Hunt simulator reached a successor that msh_successors does not enumerate:

UnresolvedTransitionError: 1 of 750000 buffered transitions did not resolve
against the legal joint graph.
Reasons: {'successor_outside_legal_set': 1}
Example: src=12f11929 joint=(0, 1) dst=e45ba6d2

No other environment produced any unresolved transition in the same sweep.

This is concrete evidence for the caveat already recorded in ../shielding/exact-anytime-adversarial.md: the gridworld successor functions are a separate reimplementation of the simulator's dynamics, so a gridworld is certified relative to the serialised graph rather than to the simulator until its successor function has an exhaustive equivalence audit. Bertrand and Chicken are simulator-bound because their builder snapshots and steps the live environment; Markov Stag Hunt is not.

The rate is tiny, and it is not a memory or scale problem — that build peaked at 18.5 GB against a 64 GiB reservation. But it is a modelling defect rather than noise, so it is handled explicitly rather than absorbed:

  • resolve_transitions hard-errors on an unresolved row by default, which is how this was found at all;
  • scripts/wm_variant_study.py allows up to MAX_UNRESOLVED_FRACTION (1e-4) of dropped transitions so that one bad row cannot cost a predeclared environment, records the exact count, and fails above that;
  • scripts/summarize_wm_variants.py reports any non-zero fraction as a caveat in the summary, so it cannot live only in a cell JSON.

Open: the discrepancy has not been localised to a specific rule. The stag move distribution, the respawn enumeration, and the maul/damage interaction are the plausible candidates, since those are where msh_successors reimplements multi-step simulator logic. An exhaustive equivalence audit against the simulator would settle it and would also let Markov Stag Hunt be described as simulator-bound.