Strategy model selection improves stability in multi-agent games
Rank Without an Oracle: Deviation-Aware Interaction-Rank Selection from Offline Multi-Agent Logs
Multiagent SystemsComputer Science and Game Theory
Summary
Predicting how multiple decision-makers interact often uses data from past play, but this can mislead if the situation changes. The authors offer a method called SIRV that better chooses models by checking how well they predict outcomes including possible player changes. This approach helps find models that keep strategic incentives accurate and avoids selecting models that only fit past data well. The method provides guarantees about prediction quality and identifies when data is insufficient, tested on thousands of simulated games.
What this means in practice
- •For game theorists: Selects strategic models that maintain accurate incentives when evaluating multi-player game outcomes from observational data.
- •For algorithm designers: Improves robustness of multi-agent reinforcement learning evaluations by avoiding misleading model choices based on biased logged data.
Tested on simulated data.
Authors
Xiangwu Wang, Chengwei Cao, Hongyuan Tang
Abstract
Offline multi-agent payoff models are estimated under a logging distribution but used on distributions induced by learned solutions and unilateral deviations. Standard held-out loss can therefore favor an interaction class that predicts logged play well while distorting strategic incentives. We introduce Selective Interaction-Rank Validation (SIRV) for finite games with known logging distributions. A training split fits nested payoff models and constructs a common union of all candidate deployment and unilateral-replacement distributions; an independent calibration split evaluates every candidate on this same union. SIRV returns the smallest rank whose simultaneous upper worst-target risk is within tolerance of the best upper score, and abstains when a declared target is unsupported or too imprecisely estimated. A common coverage event yields a finite-candidate target-risk bound and a candidate-specific coarse correlated equilibrium (CCE) gap certificate. We also isolate an exact two-point off-support non-identifiability result. In a controlled factorial study with 2,048 independent games per family, empirical-Bernstein bounds reduce the median CCE-gap certificate by 42.5% relative to Hoeffding bounds on common returns, with a 1.36-point reduction in supported return. Under paired rank misspecification and in a separately generated congestion family, the SIRV-EB fallback rule lowers mean true candidate-selection CCE regret relative to ID-Mean, while retaining game-level losses. Across 384 games at $N=3,5,8$, ID-Mean-relative mean CCE-regret effects stay positive while certified return falls sharply under weak coverage. These results separate certifiable model selection from universal strategic improvement.