Algorithms that compute Nash equilibria, the strategy profiles where no player gains by deviating alone, are almost always tested on games that are randomly generated. Path-tracing solvers are a major family of such algorithms. They start from an easy game with an obvious equilibrium and continuously deform it into the target game, following the equilibrium as it moves. Worst-case theory says these paths can be exponentially long. Whether that happens on games people actually play is unknown, because the published evidence comes from synthetic road, ring, grid and chain games and from random small matrices. This is the same synthetic-data reliance problem documented in perception and behavioral modeling: conclusions drawn from a clean generator can fail on real data. In equilibrium computation the problem has not been measured at all.
We propose to measure it directly. We will estimate multi-player games from real behavior, specifically the U.S. Congressional roll-call games learned by Honorio et al.. We will run path-tracing solvers on them and record the geometry of each traced path: its length, the number of times a player adds or drops an action from the set it randomizes over (a "support transition"), and the number of times the path doubles back in the deformation parameter. We then ask whether synthetic generators reproduce that geometry. The test is a simulation Turing test, borrowed from cognitive modeling. A synthetic benchmark is trusted only if its path geometry is no farther from the real-derived games than two bootstrap re-estimates of the real game are from each other. In two sentences: equilibrium solvers are benchmarked on synthetic games whose relevance to real strategic structure has never been checked. We check it by comparing the shape of solver paths on behavior-derived games against synthetic ones, and we test whether path shape predicts solver performance better than simpler descriptions of the game do.
Core Claim
The claim has three parts. First, the path a continuation solver traces is a measurable fingerprint of a game's strategic structure. Second, games estimated from real behavior have structure that standard synthetic generators lack, notably signed, community-structured influence, which Honorio et al. found as "stronger influence within parties than between them." Third, this mismatch changes solver conclusions: path length, failure rates and the relative ranking of solvers. If the third part holds, the field's synthetic benchmarks are misleading in a specific, correctable way. If it fails, meaning path signatures on real-derived games fall inside synthetic variability, that is also worth reporting. It would mean the worst-case hardness results are not what practitioners meet, and synthetic benchmarks can be trusted for this class of games.
Position Relative to Prior Work
Three groups of prior work play different roles.
The method comes from the continuation literature. Blum, Shelton and Koller trace equilibria in graphical games, where each player's payoff depends only on its neighbors. They compute the needed derivatives in time polynomial in the number of players when neighborhoods are small, and they add a quick-start initializer (IPA). They report equilibrium errors "within machine precision (10⁻¹²)", but only on synthetic road, ring, grid and chain games. We reuse their solver unchanged and move it onto behavior-derived games.
Two papers motivate the question. Goldberg, Papadimitriou and Savani show that following a homotopy path is PSPACE-complete in general, so the gap between worst case and typical case is real and open. On the evaluation side, Learning Real-Life Approval Elections shows that simple synthetic voter models collapse polarized real populations into a "middle" where no real voters exist. Hinder et al. make the parallel point for drift detectors tuned on simple synthetic streams.
The evaluation design comes from two further papers. Rosenberg-Kima and Pardos judge a model's realism by asking whether real data differs from simulated data more than two simulations differ from each other. We apply that logic to path geometry rather than likelihood surfaces. Chang et al. show that what makes synthetic data useful is behavioral complexity rather than surface realism: multi-group crowd synthesis raised DanceTrack HOTA from 68.8 to 73.5 where simple synthesis hurt. That suggests the relevant property of a synthetic game generator is likewise interaction structure.
The closest existing work differs in clear ways. Gargiani et al. use homotopy to move a single model's loss minimizer from a synthetic source distribution to a real target. Their setting has no players and no equilibria, and it uses the path only as an optimization aid, not as an object of measurement. Honorio et al. learn games from behavior but analyze only static pure-strategy equilibria, and they never run a path tracer on the learned games. Patris and Panageas exploit monotone equilibrium paths in rank-1 games, a class where the two players' payoffs sum to a rank-one matrix. That paper tests only random 6×6 games. It does not address whether such structure appears in practice.
Research Program
Building real-derived games. We fit linear influence games to the 104th, 107th and 110th Congress roll calls using Honorio et al.'s convex logistic formulation. A linear influence game is a graphical game in which each legislator's payoff for a yes/no vote is a weighted sum of neighbors' votes minus a threshold. The continuation solver's cost grows exponentially in neighborhood size, so we sweep the sparsity penalty to obtain graphs with maximum degree in a solvable range. We report how conclusions vary along that sweep. To separate real structure from estimation noise, we refit on 50 bootstrap resamples of roll calls for each Congress and penalty level. That yields a distribution of real-derived games rather than a single point.
Synthetic comparison sets. We draw synthetic games matched to each real-derived game in player count, edge count and fraction of negative weights. They come from three generators. The first is Honorio et al.'s own synthetic linear influence game generator, which is the status quo. The second is Blum et al.'s road, ring, grid and chain topologies with matched weight distributions. The third is a signed two-block generator in which edge probabilities and signs depend on block membership, calibrated to party structure. The third generator tests whether one obvious structural ingredient is enough to close the gap.
Path signatures. For every game we run the continuation solver from many random base perturbations and record a signature. It contains arc length in strategy space, the count and per-player distribution of support transitions, the number of turning points where the path reverses direction in the deformation parameter, wall-clock time, final equilibrium error, and whether the run fails to finish within budget. The turning-point count is the quantity worst-case theory says can explode. Rank-1 monotone paths have none, which makes it the most diagnostic single number. Signature distributions are compared with an energy distance. The fidelity test is passed when the distance from synthetic to real-derived is no larger than the 95th percentile of the distance between two bootstrap sets of real-derived games.
Solver conclusions. We record the ranking of cont, IPA+cont and a decentralized learning baseline by runtime and success rate on each game family. The learning baseline is optimistic multiplicative weights run directly on the game. It is known to cycle when the game lacks the Minty variational inequality property, a monotonicity condition that guarantees gradient-style dynamics converge, as Patris and Panageas show. The practical question is whether a ranking computed on synthetic games reproduces the ranking on real-derived ones.
Baselines
The naive reference point is current practice. Solvers are evaluated on Honorio-style synthetic linear influence games and Blum-style road, ring, grid and chain games, matched only in size, and the results are assumed to transfer. Every solver and signature is computed on these sets with the same random seeds, step-size schedules and time budgets used for the real-derived games. Our proposal beats this reference if the synthetic sets fail the bootstrap fidelity test, or if they mis-rank solvers relative to real-derived games, on at least two of the three Congresses.
The strongest existing solver is Blum et al.'s continuation method with IPA initialization. The file reports its accuracy only on synthetic games: errors within 10⁻¹² for exact equilibria and around 10⁻⁴ for ε-perfect equilibria. Honorio et al. report no raw precision, recall or KL numbers for their learned Congressional games ("no reported result found on Lacuna" for solver behavior on such games). Our first result is therefore that missing number: IPA+cont error, runtime and failure rate on behavior-derived games. Each solver gets an identical per-game compute budget and the same tolerance. Step sizes are tuned once on held-out synthetic games and then frozen for all families, so that tuning favors the status quo rather than our real-derived games.
The strongest competitor for the fidelity measurement itself is a set of static descriptors. One option compares degree distribution, weight-sign balance, modularity and the number of pure equilibria. The other compares behavior: sample vote profiles from each game's equilibria and compare them to real roll calls with a voter-anonymous Hamming distance, as in the Pabulib study. We count our path signature as better only if it predicts the real-versus-synthetic difference in solver runtime and failure rate more accurately than these descriptors in held-out regression across all generated games.
The key ablation replaces the full signature with endpoint-only quantities: runtime and final error, with no transitions and no turning points. This tests whether path geometry adds information beyond simply running the solver.
Why not just…?
Why not just match simple graph statistics between synthetic and real-derived games? This is the most serious threat. If signed two-block graphs with matched modularity already reproduce solver behavior, path signatures add nothing. The design addresses it head on. The calibrated two-block generator is one of the synthetic families, and the static-descriptor regression is a named baseline. If static descriptors predict solver differences as well as path signatures, we will report that and recommend structure-matched generators as the cheap fix. Prior work hints that static fit can mislead. In Rosenberg-Kima and Pardos, parameter values judged "implausible" by static reasoning turned out to match real behavior, which is evidence that summary statistics and generative behavior can diverge. That hint is not proof for games.
Why not just compare the behavior each game produces with real votes? Behavioral fit measures whether the game explains the data. It does not measure whether a solver will struggle on it. Honorio et al. obtain good behavioral fit while modeling only pure equilibria, and mixed-strategy path geometry is invisible to that fit. The held-out regression tests directly whether behavior-level distance predicts solver differences. We expect it will not, because two games can induce similar vote marginals while having very different support-transition structure.
Why not just run solvers on real-derived games and skip synthetic benchmarks? Real-derived games are few: three Congresses and a handful of sparsity levels. Synthetic games remain necessary for scaling studies and for stress tests. The useful output is not a one-off report of numbers on Congress. It is a test that says when a synthetic generator can stand in for real structure, in the spirit of Chang et al.'s substitutability measurements. The endpoint-only ablation also checks whether running the solver is itself an adequate fidelity probe.
Proposed Experiments and Decisive Checks
The first decisive check is the fidelity test. For each Congress and sparsity level, compute the energy distance between the path-signature distributions of each synthetic family and the real-derived bootstrap set, and compare it with the bootstrap-to-bootstrap distance. The hypothesis predicts that the size-matched synthetic families fail, with turning-point counts and support transitions concentrated on cross-party edges in the real-derived games. The calibrated two-block family should close part but not all of the gap. A null result, where all families pass, would show that synthetic benchmarks are adequate for this class of games.
The second check is ranking transfer. Compare the Kendall rank correlation of solver performance between each synthetic family and the real-derived games. A correlation clearly below 1 for the status-quo generator would show that published solver comparisons do not transfer.
The third check is predictive value. Across all generated games, regress real-versus-synthetic solver runtime and failure differences on path signatures, on static descriptors and on behavior-level Hamming distance, using held-out Congresses. The proposal's central bet succeeds only if path signatures win.
A final robustness check controls for estimation artifacts. Real-derived structure could be an artifact of the learning method. To rule this out, we plant known synthetic linear influence games, simulate roll calls from them with Honorio et al.'s mixture of equilibria and noise, re-estimate, and confirm that the estimated games keep the planted games' path signatures. If they do not, the estimator rather than reality is the source of any gap, and we will say so.
References
- Learning the structure and parameters of large-population graphical games from behavioral data
- A Continuation Method for Nash Equilibria in Structured Games
- The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
- One or two things we know about concept drift - a survey on monitoring in evolving environments. Part A: detecting concept drift
- Is this Model for Real? Simulating Data to Reveal the Proximity of a Model to Reality
- On the Equivalency, Substitutability, and Flexibility of Synthetic Data
- Transferring Optimality Across Data Distributions via Homotopy Methods
- Learning Nash Equilibria in Rank-1 Games