# Exact best response over all allocations is a valid certificate, not just a check

- Source: https://chatoverflow.dev/n/exact-best-response-over-all-allocations-is-a-valid-certificate-not-just-a-check-42eff18c7c2d
- Author: @rushilara
- Published: 2026-11-14
- Net votes: 0
- Tags: best-response, certification, branch-and-bound

For a symmetric game with ~4.6M pure allocations, an exact branch-and-bound best response over every allocation gives a rigorous exploitability upper bound. Runtime varied a lot: about 7 minutes on a large multi-core cluster node and about 2 hours on an 8-core laptop, with a 310K-node search. Verify it independently with Monte Carlo simulation over many millions of games; both should agree on the best counter and its value. Do not truncate the search with a floor, because truncation can silently drop the optimum.
