Skip to content

Scaling beyond two agents: what happened and what is tractable (20 Oct 2026)

An assessment written for the user's question of which environment could test OmSh with more than two agents. Nothing in it has been run yet. Graph sizes are exact counts or upper bounds from the environment definitions. OM-time figures are measured where stated; projections are labelled as estimates.

What Congestion did beyond two agents

Congestion shields every role (shielded_agent_ids=player_0,…). The other five paper environments shield only player_0 against unshielded IPPO learners.

n OmSh R / worst U TrueSh IPPO-Lag CPO (convention seeds) OM wall-clock
2 about 0.98 (convention 5/5) / 0 – convention 0/5 convention 4/5 0.33 h for both roles
3 0.197 every seed / 0 0.197 0.196 0.511 (2/5) 35 h over three roles (CX3)
4 0.197 every seed / 0 0.197 0.194 0.825 (4/5) about 4.4 days per role, four roles
6 not run (measured limit) ran ran 0/5 not run
  • From n = 3, OmSh, TrueSh and IPPO-Lagrangian all converge to the uncoordinated fallback. CPO sometimes finds the alternating convention. The audits show zero excess, so the safety guarantee holds; the loss is in reward.
  • The shield was not over-restrictive: on average about 2.97 of 3 actions were admissible. Even the exact-model shield collapses, so this is a learning outcome. Shielded IPPO learners do not find an n-way convention.
  • The paper reports two agents only (user decisions, 7–8 Oct 2026). Sources: goal.md (n = 3/4 entries) and scalable-opponent-shielding-candidates.md.

Where the cost grows

  • Exact and learned graphs enumerate states × A^n state–joint-action groups, times the stochastic successor fanout (../joint-graphs/legal-dynamics-size.md).
  • OM level training (soft_rollout_policy_improvement) treats the opponents as one team controller over A^(n−1) joint actions. Every sampled root state runs n_rollouts rollouts for every legal joint team action.
  • From two opponents up, MBOMConfig switches from the flat MLP to the autoregressive joint OM, and the rollouts enumerate its joint log-probabilities.
  • Together these explain Congestion's jump of about 70× per role from n = 2 to n = 3, where the team grows only from 3 to 9 joint actions.
  • Existing knob. SoftRolloutPIConfig.eval_topk / eval_rand restrict the rollouts to the top-k joint team actions plus random picks. Every environment runs them at 0, meaning all actions. Non-zero values make per-root cost roughly independent of team size, but the level becomes an approximate best response. That would have to be declared.
  • Shielded roles multiply the OM cost. Shielding only player_0 needs one OM role, while Congestion's design needs n.
  • Measured n = 2 OM times (clean timing run, ../experiments/clean-timing-run.md): Chicken 2.6 h, Bertrand 2.4 h, Pursuit 9.2 h, Gathering 26.6 h, MSH 29.7 h.

Candidates

Sizes assume one shielded focal (player_0), as in the paper's other environments.

Environment n States Groups Edge bound OM team actions Notes
n-player Chicken / Bertrand (last joint action as state) 3 / 4 / 6 / 8 9 / 17 / 65 / 257 72 / 272 / 4,160 / 65,792 deterministic 4 / 8 / 32 / 128 Zero-risk fallback at every n if unsafe means the focal plays the aggressive action and at least one other agent does too.
Pursuit, 9×9 (current) 3 85,184 10.6M 1.33B 25 The materialised graph reached 48.7 GB and was abandoned.
Pursuit, 7×7 (22 free cells) 2 / 3 484 / 10,648 12,100 / 1.33M 0.3M / 166M 5 / 25 Slip to Stay instead of a random cardinal move would cut the n = 3 bound to 10.6M edges.
Ice Duel, 7×7 rink (25 interior cells) 3 15,625 1.95M about 53M 25 At n = 2, CPO had higher reward and lower risk.
Ice Duel, 6×6 / 5×5 3 4,096 / 729 512k / 91k about 14M / 2.5M 25 No robust-safe start with two shoving opponents has been shown; it needs checking.
DPGG, pot coarsened to 51 levels 4 / 6 about 870 / 3,300 14k / 212k deterministic 8 / 32 Retired because the exploitation label makes eventual risk 1 under any stochastic opponent. More opponents make that worse.
Inspection, one inspector and n−1 inspectees 3 / 4 small small deterministic 4 / 8 One inspection cannot cover two simultaneous violators, so there is no safe action. The structural infeasibility that retired it gets worse.

Assessment

  1. n-player Chicken or Bertrand. This is the only family whose full exact pipeline stays small enough for a real scaling curve at n = 2, 3, 4 and 6: WM, OM, OmSh, TrueSh, exact baseline U_∞ and the dominance audit.
  2. It keeps the zero-risk fallback.
  3. OmSh was positive at n = 2 in both games (it dominates CPO in Bertrand, and ties it in Chicken under U_H).
  4. Work needed: generalise the stage payoffs and the safety rule to n players (the envs assert n = 2), and pass n_agents through the notebooks.
  5. OM time at n ≥ 3 is unmeasured. A short pilot (a few percent of the schedule) should measure roots per second before any campaign.
  6. Pursuit-3 on a smaller layout with capture-terminal dynamics. This is OmSh's strongest n = 2 result. It is also the only candidate where the OM must model a correlated team of two intruders.
  7. At n = 3 the 7×7 graph has about 27× the groups of today's Pursuit-2 (48,400). Its edge bound is 166M with the current slip, against about 1.2M for Pursuit-2. Slip to Stay would bring the bound down to 10.6M.
  8. Feasibility at the paper's p is plausible but not shown (../shielding/pursuit-3-agent-infeasibility.md).
  9. A matched n = 2 run on the same 7×7 layout is needed for the comparison.
  10. Not recommended as adaptations:
  11. Ice Duel: weak n = 2 prior, and robust safety at n = 3 is unproven on small rinks.
  12. DPGG and Inspection: the safety semantics that retired them get worse with more opponents. They would need new safety definitions, for example a commons tipping point for DPGG, which makes them new environments rather than adaptations.