Forecasting for Swap Regret for All Downstream Agents
Aaron Roth Mirah Shi
We study the problem of making predictions so that downstream agents who best
respond to them will be guaranteed diminishing swap regret, no matter what
their utility functions are. It has been known since Foster and Vohra (1997)
that agents who best-respond to calibrated forecasts have no swap regret.
Unfortunately, the best known algorithms for guaranteeing calibrated forecasts
in sequential adversarial environments do so at rates that degrade
exponentially with the dimension of the prediction space. In this work, we show
that by making predictions that are not calibrated, but are unbiased subject to
a carefully selected collection of events, we can guarantee arbitrary
downstream agents diminishing swap regret at rates that substantially improve
over the rates that result from calibrated forecasts -- while maintaining the
appealing property that our forecasts give guarantees for any downstream agent,
without our forecasting algorithm needing to know their utility function.
  We give separate results in the ``low'' (1 or 2) dimensional setting and the
``high'' ($> 2$) dimensional setting. In the low dimensional setting, we show
how to make predictions such that all agents who best respond to our
predictions have diminishing swap regret -- in 1 dimension, at the optimal
$O(\sqrt{T})$ rate. In the high dimensional setting we show how to make
forecasts that guarantee regret scaling at a rate of $O(T^{2/3})$ (crucially, a
dimension independent exponent), under the assumption that downstream agents
smoothly best respond. Our results stand in contrast to rates that derive from
agents who best respond to calibrated forecasts, which have an exponential
dependence on the dimension of the prediction space.