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 |