Improved Multi-Dimensional Forecasting for Swap Regret
Joey Rivkin Ramiro N. Deo-Campo Vuong Robert Kleinberg [email protected] [email protected] [email protected] Chido Onyeze Erald Sinanaj Eva Tardos [email protected] [email protected] [email protected] Cornell University · 2026
Read Improved Multi-Dimensional Forecasting for Swap Regret by Joey Rivkin Ramiro N. Deo-Campo Vuong Robert Kleinberg [email protected] [email protected] [email protected] Chido Onyeze Erald Sinanaj Eva Tardos [email protected] [email protected] [email protected] Cornell University (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29533.txt.
Description
Rivkin and five colleagues at Cornell study forecasting for many downstream agents whose objectives are unknown. Each agent best-responds to the forecaster's predictions. The goal is one forecaster that guarantees sublinear swap regret, a measure of how much each agent wishes it had swapped its choices, for all agents at once.
For two-dimensional outcome spaces, they give a polynomial-time algorithm with a much better swap regret bound than previously known. It also avoids the exponential runtime of earlier algorithms in that setting. The algorithm extends to other low-dimensional environments, keeping the same time scaling while dimension raises other exponents. For arbitrary dimension, a second algorithm guarantees a bound that improves on prior results, which had worse time dependence and needed extra behavioural assumptions. The forecaster must know an upper bound on each agent's action count, and runtime in high dimensions stays long.
Catalog record
| CREATOR | Joey Rivkin Ramiro N. Deo-Campo Vuong Robert Kleinberg [email protected] [email protected] [email protected] Chido Onyeze Erald Sinanaj Eva Tardos [email protected] [email protected] [email protected] Cornell University |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.29533