# Forecasting for Swap Regret for All Downstream Agents

Aaron Roth  Department of Computer and Information Sciences, University of
Pennsylvania  Mirah Shi  Department of Computer and Information Sciences,
University of Pennsylvania

###### Abstract

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 (e.g. the number of
actions). Thus the calibration approach is substantially worse, in terms of
swap regret _rates_ , compared to the approach of running a bespoke swap-
regret-minimization algorithm for each agent — an approach that requires
knowing the agent utility functions. 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, and at the optimal rate of $O(\sqrt{T})$ under a perhaps less
realistic behavioral assumption. 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.

##  1 Introduction

When acting in an adversarial environment, a popular way to evaluate the
performance of a decision-making agent is through the lens of _regret_ : Given
the sequence of outcomes actually realized, and the sequence of actions chosen
by the decision making agent, how much better could they have done had they
followed some other policy rather than what the actually did? External regret
compares the agent’s utility to a very simple benchmark: the utility they
could have obtained had they played a _constant_ policy, that played the same
fixed action at every round. Swap regret compares the agent’s utility to a
more demanding benchmark: the utility they could have obtained if,
counterfactually, they had been able to go back and modify their play using an
arbitrary _swap function_ mapping actions to replacement actions in any
consistent fashion. Swap regret is closely linked to correlated equilibrium —
in particular, if all agents in a game have no swap regret, then the empirical
distribution over their play is a correlated equilibrium (Foster and Vohra,
1997).

There are efficient algorithms that individual agents can use to guarantee
themselves no swap regret in adversarial environments (e.g. Blum and Mansour
(2007)). But these algorithms require some sophistication to run, and must be
run separately for each agent, as they are dependent on the agent’s utility
function. It would be compelling if it were possible to make public forecasts
of the payoff relevant state, such that less sophisticated agents could simply
best respond to these forecasts (as if they were correct), and be guaranteed
that they will have no swap regret. These forecasts would be valuable
universally to all agents, independently of what their utility functions are.

A candidate solution to this problem is _calibration_ , a “self-consistency”
measure of forecast quality. Informally, calibrated predictions must be
unbiased conditional on the value of the prediction itself. It is possible to
make predictions in adversarial environments that satisfy the calibration
condition (Foster and Vohra, 1998), and agents who best respond to calibrated
predictions obtain diminishing swap regret (Foster and Vohra, 1997). However,
this approach suffers from a serious shortcoming. Even in $1$-dimension, the
best known algorithms obtain calibration (and hence downstream swap regret) at
a rate of $T^{2/3}$ (Foster and Vohra, 1998; Okoroafor et al., 2023) — worse
than the $O(\sqrt{T})$ rates known to be optimal for swap regret (Blum and
Mansour, 2007). In fact, it is known that obtaining $\sqrt{T}$ rates via
calibration is impossible even in $1$-dimension: Qiao and Valiant (2021) show
an $\Omega(T^{0.528})$ lower bound on $1$-dimensional calibration rates in
adversarial environments. The situation only gets worse in higher dimensions —
the best known rates for $d$-dimensional forecasts scale as $T^{2d/(2d+1)}$. A
related notion of _smooth calibration_ (Kakade and Foster, 2008; Foster and
Hart, 2018) has similar guarantees under the assumption that downstream agents
smoothly best respond (and has other desirable properties), but is not known
to be obtainable at faster rates than traditional calibration. This suggests
that we must look elsewhere if we wish to provide forecasts which can
guarantee arbitrary downstream agents strong regret guarantees at reasonable
rates.

Recent work of Kleinberg et al. (2023) accomplishes exactly this. They abandon
swap regret, and consider the simpler goal of guaranteeing downstream agents
low external regret. They show that a weaker measure of forecast quality
called “U-calibration”—corresponding to minimizing regret over a restricted
collection of proper scoring rules—suffices for external regret minimization
for arbitrary downstream agents. Remarkably, they show how to make predictions
that guarantee diminishing external regret at a rate of $O(\sqrt{T})$
simultaneously for all downstream agents, thus bypassing the calibration lower
bound. Given these results, one might wonder if sidestepping the shortcomings
of calibration requires giving up on swap regret and settling for external
regret. Put another way, is calibration necessary to achieve the stricter goal
of guaranteeing low swap regret for all downstream agents?

###  1.1 Our Contributions

In this paper, we show that calibration is not necessary for this goal. Recall
that predictions are calibrated if they are unbiased conditional on the value
of their own prediction. We show that by requiring our predictions to be
unbiased over an alternative collection of events, we can obtain substantially
improved swap regret bounds simultaneously for all possible agents. For a
single agent, we know that they will obtain no swap regret if they best
respond to forecasts that are unbiased conditional on events defined by their
own best response correspondence (Haghtalab et al., 2023; Noarov et al.,
2023), a weaker condition than full calibration—but one that depends on their
utility function. At a high level, we take advantage of the structure of best
response functions to define a collection of events such that forecasts that
are unbiased with respect to these events suffice to guarantee no swap regret
for all downstream agents. Using the algorithm of Noarov et al. (2023) we are
able to produce forecasts that achieve this bias condition at rates that
improve dramatically over the best known rates for calibration.

In the $d=1$ dimensional setting we make forecasts that guarantee every best-
responding downstream agent diminishing swap regret at the optimal rate of
$\tilde{O}(\sqrt{T})$ (Theorem 3). We can extend this technique to the $d=2$
dimensional setting while obtaining swap regret rates of $\tilde{O}(T^{5/8})$
(Theorem 5). These results require no knowledge of either agent utility
functions or the number of actions available to the agents.

We then turn to the higher dimensional setting, which presents new challenges
(informally, that the structure of arbitrary best response functions projected
onto a finite grid of predictions appears to become much more complex). In
this higher $(d>2)$ dimensional setting, we take a different approach, which
requires two modifications to our setting. First, although we continue to
assume no knowledge of the downstream agent’s utility function, we now assume
that we know an upper bound $k$ on the number of actions that they have
available to them. Second, rather than assuming that agents exactly best
respond to our forecasts, we assume that they _smoothly_ best respond —
informally that they choose an approximate best response using a mapping that
is Lipchitz in our predictions. Quantal response e.g. satisfies this
assumption; as we discuss, this is a behavioural assumption with extensive
roots in the economics literature. Under these assumptions, we give an
algorithm that for any dimension $d>2$ guarantees that all downstream agents
with at most $k$ actions have swap regret diminishing at a rate of
$\tilde{O}(T^{2/3})$ (Theorem 7), with only a polynomial dependence on the
dimension $d$. Under a perhaps less realistic behavioral assumption (that
agents play best responses with respect to a discretization of their utility
function), we show how to guarantee all downstream agents regret at the
optimal rate of $\tilde{O}(\sqrt{T})$ for every dimension $d$ (Theorem 6).
This stands in sharp contrast to calibration bounds, which have a dimension
dependence in their exponent. Our focus here is on achievable rates; as with
calibration, the computational complexity of our algorithms scales
exponentially with $d$, and achieving similar rates in high dimensional
settings with computationally efficient algorithms is in our view the most
compelling open problem coming out of this work.

###  1.2 Related Work

The idea of sequential calibration dates to Dawid (1982), and Foster and Vohra
(1998) were the first to show that it is possible to maintain calibrated
forecasts in a sequential adversarial setting. Foster and Vohra (1997)
connected calibration to decision making in a game theoretic context, and
showed that agents who best respond to calibrated forecasts of the utilities
of their actions obtain diminishing internal (equivalently swap) regret and
hence converge to correlated equilibrium. The correct “rates” at which
calibration error can be driven to $0$ in an online setting has been an
important open question; the best known rates in $1$ dimension are $T^{2/3}$
and degrade exponentially with the dimension (Okoroafor et al., 2023). In
$1$-dimension, it is known that it is impossible to obtain $\sqrt{T}$ rates —
Qiao and Valiant (2021) show a lower bound of $\Omega(T^{0.528})$. This is
despite the fact that it is known that swap regret for a single agent can be
obtained at a rate of $O(\sqrt{T})$ (Blum and Mansour, 2007).

Kakade and Foster (2008) and Foster and Hart (2018) introduce _smooth_
calibration, and give — as we do — guarantees for agents who smoothly best
respond. The main benefit of smooth calibration is that it can be guaranteed
with deterministic algorithms in adversarial environments (unlike calibration,
which requires randomization) — and that players who smoothly best respond to
smoothly calibrated forecasts converge to Nash (rather than correlated)
equilibrium. The algorithms for smooth calibration do not converge at rates
faster than the best known rates for calibration, however.

The most closely related work is Kleinberg et al. (2023), who take the
perspective of a forecaster whose goal is to guarantee low external regret for
arbitrary downstream agents. They define “U-calibration” as a measure of
forecast quality that is necessary and sufficient to achieve this goal and
provide algorithms that minimize U-calibration error. In comparison, our work
gives stronger guarantees than low external regret, and we consider general
$d$-dimensional prediction tasks, while their work focuses on 1-dimensional
and multiclass predictions (i.e. predictions that are distributions over $d$
outcomes, which is a special case of the setting we consider). This work is
conceptually related to a recent line of work on _decision calibration_ (Zhao
et al., 2021) and _omniprediction_ that has the goal of learning a single
predictor that is a sufficient statistic to minimize any downstream loss
function in some family, with respect to some benchmark family of functions
(Gopalan et al., 2022, 2023; Hu et al., 2023; Globus-Harris et al., 2023).
Most of this literature focuses on the batch setting, but Garg et al. (2024)
give omnipredictors in the online adversarial setting. The omniprediction
literature is focused on $1$-dimensional binary valued prediction, whereas we
are interested in high dimensional real valued prediction. Noarov et al.
(2023) consider making high dimensional predictions that guarantee diminishing
swap regret to downstream agents. We take direct inspiration from their work
and make essential use of their forecasting algorithm. The main distinction is
that Noarov et al. (2023) tailors their predictions to the best response
functions of particular downstream agents, whereas our goal is to give
guarantees that hold simultaneously for _all_ downstream agents.

In our main result for high-dimensional settings, we require agents to
smoothly best respond, i.e. to choose actions randomly with probability
proportional to their utility. This is consistent with the literature on
smooth calibration (Kakade and Foster, 2008; Foster and Hart, 2018), but one
may ask: is this natural behavior? To offer some justification, we note that
our formulation of smooth best response fits into a broader theory of quantal
choice that studies probabilistic best responses, otherwise known as quantal
responses (McFadden, 1976; McKelvey and Palfrey, 1995). The quantal choice
model posits that agents are not perfectly rational; instead, they make slight
errors in choosing their actions.

##  2 Model and Preliminaries

###  2.1 Predictions and Decisions

We consider a repeated interaction between a learner, an adversary, and
downstream agents. We use $\mathcal{C}\subseteq\mathbb{R}^{d}$ to denote a
convex prediction space for a finite dimension $d$. Without loss of
generality, we consider $\mathcal{C}\subseteq[0,1]^{d}$ (rescaling the
predictions space degrades our bounds by only a multiplicative constant). In
rounds $t\in[T]$, the learner interacts with an adversary as follows:

  1. 1.

The adversary chooses a distribution over outcomes
$Y_{t}\in\Delta\mathcal{C}$.

  2. 2.

The learner produces a distribution over predictions
$p_{t}\in\Delta\mathcal{C}$, from which a prediction $\hat{y}_{t}$ is sampled.

  3. 3.

The adversary reveals an outcome $y_{t}\sim Y_{t}$.

This interaction accumulates in a transcript $\pi_{T}$ of predictions
$\hat{y}_{1},...,\hat{y}_{t-1}$ and outcomes $y_{1},...,y_{T}$. The learner’s
output is a (possibly randomized) function of previous predictions
$\hat{y}_{1},...,\hat{y}_{t-1}$ and outcomes $y_{1},...,y_{t-1}$. In this
setting, the adversary’s choice of outcome can depend on previous predictions
$\hat{y}_{1},...,\hat{y}_{t-1}$ and outcomes $y_{1},...,y_{t-1}$ but cannot
depend on the learner’s realization of randomness on round $t$.

We want to study the value of predictions for downstream agents. Upon
observing a prediction $\hat{y}_{t}$, an agent chooses an action $a_{t}$ from
a finite action set $\mathcal{A}$. An agent’s utility depends on the chosen
action and the outcome. More specifically, when the outcome is $y$, the agent
receives utility $u(a_{t},y)$ according to a bounded utility function
$u:\mathcal{A}\times\mathcal{C}\to[0,1]$. We will assume that utility
functions are affine and Lipschitz-countinuous in $y$.

######  Assumption 1.

Fix a utility function $u:\mathcal{A}\times\mathcal{C}\to[0,1]$. We assume
that for every action $a\in\mathcal{A}$, $u(a,y)$ is affine in $y$, i.e.
$u(a,y)=\langle v_{a},y\rangle+c_{a}$ for some
$v_{a}\in\mathbb{R}^{d},c_{a}\in\mathbb{R}$. Moreover, we assume that $u(a,y)$
is $L$-Lipschitz in $y$ in the $\ell_{\infty}$ norm: for any
$y_{1},y_{2}\in\mathcal{C}$, $|u(a,y_{1})-u(a,y_{2})|\leq
L\|y_{1}-y_{2}\|_{\infty}$.

######  Remark 1.

Note that by linearity of expectation this is only more general than
considering expectation maximizing agents that have arbitrary utility
functions over $d$ discrete outcomes, and states/forecasts $y\in\Delta[d]$
that correspond to probability distributions over these $d$ outcomes. Thus,
our setting generalizes the settings of e.g. Zhao et al. (2021); Kleinberg et
al. (2023).

We will later on take advantage of the fact that it is not more restrictive to
consider utility functions that are linear in $y$.

######  Observation 1.

Any utility function over a $d$-dimensional prediction space that is affine in
$y$ can be equivalently expressed as a utility function over a
$(d+1)$-dimensional prediction space that is linear in $y$. We simply set the
$(d+1)^{st}$ coordinate of the outcome/prediction to always take value 1. This
preserves the convexity of the outcome/prediction space.

We measure agent regret by comparing the utility the agents obtain from the
sequence of chosen actions against the counterfactual utility they would have
received under another sequence of actions. We focus on swap regret, where the
counterfactual action sequence is obtained by applying an action modification
rule to the realized sequence of chosen actions.

######  Definition 1 (Swap Regret).

Fix an agent with action set $\mathcal{A}$ and utility function $u$. For a
sequence of actions $a_{1},...,a_{T}\in\mathcal{A}$ and outcomes
$y_{1},...,y_{T}$, the agent’s swap regret to an action modification rule
$\phi:\mathcal{A}\to\mathcal{A}$ is:

$Reg(u,\phi)=\frac{1}{T}\sum_{t=1}^{T}\left(u(\phi(a_{t}),y_{t})-u(a_{t},y_{t})\right)$

More generally, when an agent plays distributions over actions
$q_{1},...,q_{T}\in\Delta\mathcal{A}$, we measure swap regret to $\phi$ by:

$Reg(u,\phi)=\frac{1}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{a\sim
q_{t}}[u(\phi(a),y_{t})-u(a,y_{t})]$

We say that an agent has swap regret $\alpha$ if for any action modification
rule $\phi$, $Reg(u,\phi)\leq\alpha$.

The objective, from the learner’s perspective, is to produce a sequence of
predictions such that any agent responding to these predictions as if they
were correct experiences low swap regret, regardless of their utility
function.

###  2.2 Conditionally Unbiased Predictions

While we ultimately evaluate predictions based on the utility obtained by
downstream agents who act according to our predictions, we will ask for
predictions to satisfy some intermediate properties along the way—in
particular, unbiasedness subject to a collection of events. Recall that
calibration can be summarized as unbiasedness conditional on events
corresponding to the predictions themselves. We will make use of a relaxation
which asks for unbiasedness subject to a more coarsely defined collection of
events. Our algorithms will derive from the general framework developed by
Noarov et al. (2023). For the remainder of this section, we introduce the key
tools we use. First, we formalize the notion of events and conditional bias.

######  Definition 2 (Conditional Bias on Events).

Fix a transcript $\pi_{T}$. Let $\mathcal{E}$ be a collection of events, where
each event is defined by a subsequence indicator function
$E:\mathcal{C}\to\\{0,1\\}$. Let
$n_{T}(E)=\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[E(\hat{y}_{t})]$ denote the (expected) frequency of event $E$ up to
round $T$. We say that $\pi_{T}$ has bias $\alpha$ conditional on
$\mathcal{E}$ for some $\alpha:\mathbb{R}\rightarrow\mathbb{R}$ if for all
$E\in\mathcal{E}$:

$\frac{1}{T}\left\|\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}[E(\hat{y_{t}})(\hat{y_{t}}-y_{t})]\right\|_{\infty}\leq\alpha(n_{T}(E))$

Noarov et al. (2023) show how to achieve unbiased predictions at favorable
rates conditional on any collection of events. The algorithm requires the
learner to randomize over a finite prediction space (we defer the details to
Noarov et al. (2023)). We next define a discretized prediction space.

######  Definition 3 ($\varepsilon$-net).

We say $\mathcal{C}_{\varepsilon}\subset\mathcal{C}$ is an $\varepsilon$-net
of $\mathcal{C}$ in the $\ell_{\infty}$ norm if for every $y\in\mathcal{C}$,
there exists $y_{\varepsilon}\in\mathcal{C}_{\varepsilon}$ such that
$\|y-y_{\varepsilon}\|_{\infty}\leq\varepsilon$. Observe that we can always
obtain an $\varepsilon$-net of size
$|\mathcal{C}_{\varepsilon}|\leq\left(\frac{1}{\varepsilon}\right)^{d}$ by
simply discretizing each coordinate into multiples of $\varepsilon$.

When the learner produces predictions from a discretized prediction space
$\mathcal{C}_{\varepsilon}$, Noarov et al. (2023) show that we can make
predictions with low bias on any collection of events, with bias scaling
logarithmically in the number of events. In our results, we will make direct
use of the algorithm given by Noarov et al. (2023).

######  Theorem 1.

(Noarov et al., 2023) For a collection of events $\mathcal{E}$ and convex
prediction/outcome space $\mathcal{C}$, there is an algorithm producing
predictions $p_{1},...,p_{T}\in\Delta\mathcal{C}_{\varepsilon}$ such that for
any sequence of outcomes $y_{1},...,y_{T}\in\mathcal{C}$ chosen by the
adversary, the bias conditional on $\mathcal{E}$ is at most:

$\alpha(n_{T}(E))\leq
O\left(\frac{\ln(d|\mathcal{E}|T)+\sqrt{\ln(d|\mathcal{E}|T)\cdot
n_{T}(E)}}{T}+\varepsilon\right)\leq
O\left(\sqrt{\frac{\ln(d|\mathcal{E}|T)}{T}}+\varepsilon\right)$

For $\varepsilon\leq 1/\sqrt{T}$, the bias is at most
$O\left(\sqrt{\frac{\ln(d|\mathcal{E}|T)}{T}}\right)$. The algorithm can be
implemented with per-round running time scaling polynomially in $d$,
$|\mathcal{E}|$, and $T$.

##  3 Predictions in Low Dimensions

In this section we show how to use the framework of unbiased prediction to
produce predictions for all possible agents in the one- and two-dimensional
case (Theorem 3 and Theorem 5 respectively). To accomplish this, we build on a
key result of Noarov et al. (2023) connecting conditionally unbiased
predictions to the swap regret of downstream agents. For a particular
instantiation of events—concretely, the best response correspondences of
agents—conditional bias has a natural implication for swap regret. Next we
define an agent’s best response and their corresponding best response events.

######  Definition 4 (Best Response).

Consider an agent with utility function $u$ over an action set $\mathcal{A}$
and prediction space $\mathcal{C}$. The agent’s best response to
$y\in\mathcal{C}$ according to their utility function $u$ is the action
$a=BR(u,y)$ where $BR(u,y)=\operatorname*{arg\,max}_{a\in\mathcal{A}}u(a,y)$.

######  Definition 5 (Best Response Events).

Fix an action set $\mathcal{A}$ and utility function $u$. For any action
$a\in\mathcal{A}$, we define its corresponding best response event:

$E_{u,a}(y)=\mathbbm{1}[BR(u,y)=a]$

A sufficient condition for minimizing swap regret for any agent is minimizing
bias conditional on their best response events. More accurately, an agent with
action set $\mathcal{A}$ and utility function $u$ can achieve low swap regret
when they best respond to predictions that are unbiased subject to the
collection of events $\mathcal{E}_{u}=\\{E_{u,a}\\}_{a\in\mathcal{A}}$.
Informally, this unbiasedness condition ensures that for every action $a$,
agents’ estimates of their utilities are (on average) correct whenever they
choose to take action $a$. Therefore, since agents pick their utility-
maximizing action, they must be choosing the action that is best (on average)
conditional on that choice — and thus not have swap regret. We state the
resulting swap regret bound in the next theorem but defer further details of
the argument to Noarov et al. (2023).

######  Theorem 2.

(Noarov et al., 2023) Fix a transcript $\pi_{T}$. Consider an agent with
action set $\mathcal{A}$ and utility function $u$ who, at every round
$t\in[T]$, takes action $a_{t}=BR(u,\hat{y}_{t})$, where $\hat{y}_{t}\sim
p_{t}$. Let $E_{u,a}$ be the best response event corresponding to $u$ and
$a\in\mathcal{A}$. Then, if $\pi_{T}$ has bias $\alpha$ conditional on events
$\mathcal{E}$ such that $\\{E_{u,a}\\}_{a\in\mathcal{A}}\subseteq\mathcal{E}$,
the agent has swap regret bounded by:

$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
2L\sum_{a\in\mathcal{A}}\alpha(n_{T}(E_{u,a}))$

For any concave $\alpha$, this is at most:
$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
2L|\mathcal{A}|\alpha(T/|\mathcal{A}|)$. In particular, if we plug in the
bound obtained by Theorem 1, then we have:

$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
O\left(L\sqrt{\frac{|\mathcal{A}|\ln(d|\mathcal{E}|T)}{T}}\right)$

This implies that given any set of utility functions $\mathcal{U}$, running
the algorithm of Theorem 1 with the corresponding collection of best response
events $\\{E_{u,a}:u\in\mathcal{U},a\in\mathcal{A}\\}$ promises any agent
regret at most
$O\left(L\sqrt{|\mathcal{A}|\ln(d|\mathcal{U}||\mathcal{A}|T)/T}\right)$, as
long as their utility function belongs to $\mathcal{U}$.

Our present goal is to promise low swap regret with respect to any utility
function an agent may possess. We will approach this by considering the
augmented collection of best response events corresponding to not just any
particular set $\mathcal{U}$, but the set of all possible utility functions.
If our predictions are unbiased subject to all possible best response events,
then we can be certain that our predictions are unbiased subject to the best
response events of any particular agent. However, recall that the bounds on
conditional bias given by Theorem 1 scale with the number of events. Thus, we
must be careful to ensure that we define a reasonably sized collection of
events. We show that for one- and two-dimensional prediction spaces, the
collection of best response events is not too large and hence we can derive
meaningful swap regret bounds.

To do so, we will take advantage of a key structural property of the best
response function—namely, that its level sets are convex.

######  Lemma 1.

For any utility function $u$ that is affine in $y$ , the level set of the
corresponding best response function $\\{y:BR(u,y)=a\\}$ is convex for all
$a\in\mathcal{A}$, i.e. for any $y_{1},y_{2}\in\mathcal{C}$ and any
$\lambda\in[0,1]$, if $BR(u,y_{1})=BR(u,y_{2})=a$, then $BR(u,\lambda
y_{1}+(1-\lambda)y_{2})=a$.

###### Proof.

We use the definition of an affine function to compute, for any alternate
action $a^{\prime}\in\mathcal{A}$:

$\displaystyle u(a,\lambda y_{1}+(1-\lambda)y_{2})$ $\displaystyle=\langle
v_{a},\lambda y_{1}+(1-\lambda)y_{2}\rangle+c_{a}$
$\displaystyle=\lambda\langle v_{a},y_{1}\rangle+(1-\lambda)\langle
v_{a},y_{2}\rangle+c_{a}$ $\displaystyle=\lambda
u(a,y_{1})+(1-\lambda)u(a,y_{2})+c_{a}-\lambda c_{a}-(1-\lambda)c_{a}$
$\displaystyle=\lambda u(a,y_{1})+(1-\lambda)u(a,y_{2})$
$\displaystyle\geq\lambda u(a^{\prime},y_{1})+(1-\lambda)u(a^{\prime},y_{2})$
$\displaystyle=u(a^{\prime},\lambda y_{1}+(1-\lambda)y_{2})$

where the inequality follows by definition of the best response function and
the last line follows from applying the same transformation. Hence,
$a=BR(u,\lambda y_{1}+(1-\lambda)y_{2})$, proving the claim. ∎

In other words, the set of predictions that activate a best response event
form a convex set. As a result, we can enumerate all possible best response
events (across all possible utility functions) by enumerating all convex hulls
of predictions in our prediction space. Our results in this section proceed by
bounding the number of such convex hulls when the prediction space is an
$\varepsilon$-net of $\mathcal{C}$ (as required by the algorithm of Theorem
1). Given a bound on the number of such convex hulls, an application of
Theorem 2 bounds the swap regret for any downstream agent.

The $d=1$ case is particularly elegant: convex hulls over any finite set of
grid points on the unit interval $\mathcal{C}_{\varepsilon}\subseteq[0,1]$ are
simply intervals with endpoints $y_{1},y_{2}\in\mathcal{C}_{\varepsilon}$,
i.e. they can be specified by two points in $\mathcal{C}_{\varepsilon}$.
Hence, the number of convex hulls—and thus, the number of events we must
define—is only quadratic in the discretization parameter $\varepsilon$. We
show that setting $\varepsilon$ to optimally trade off between the number of
events and the precision of predictions, we can guarantee the optimal swap
regret rate of $O(\sqrt{T})$ (up to logarithmic factors) simultaneously for
every downstream agent.

######  Theorem 3.

Consider the prediction/outcome space $\mathcal{C}=[0,1]$ and let
$\mathcal{C}_{\varepsilon}$ be an $\varepsilon$-net of $\mathcal{C}$. Let
$\mathcal{E}=\\{E_{y_{1},y_{2}}:y_{1},y_{2}\in\mathcal{C}_{\varepsilon}\\}$ be
the collection of events $E_{y_{1},y_{2}}(y)=\mathbbm{1}[y\in[y_{1},y_{2}]]$.
Then, using the algorithm given by Noarov et al. (2023) and setting
$\varepsilon=1/\sqrt{T}$, an agent who best responds according to action set
$\mathcal{A}$ and utility function $u$ obtains swap regret bounded by:

$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
O\left(L|\mathcal{A}|\sqrt{\frac{\ln T}{T}}\right)$

Moreover, the forecasts can be made with per-round running time polynomial in
$T$.

###### Proof.

As we remarked above, convex sets in one dimension are simply intervals.
Therefore, given that our predictions lie on a finite $\varepsilon$-net, it
follows from Lemma 1 that for any utility function $u$ and any action $a$, the
best response event $E_{u,a}$ exactly corresponds to an event
$E_{y_{1},y_{2}}\in\mathcal{E}$. That is, for any action $a\in\mathcal{A}$,
there exist $y_{1},y_{2}\in\mathcal{C}_{\varepsilon}$ such that for all
$y\in\mathcal{C}_{\varepsilon}$, $BR(u,y)=a$ if and only if
$E_{y_{1},y_{2}}(y)=1$. Thus to prove the regret bound, all we need is to
determine $|\mathcal{E}|$. Since
$|\mathcal{C}_{\varepsilon}|\leq\frac{1}{\varepsilon}$, we have that
$|\mathcal{E}|\leq\frac{1}{\varepsilon^{2}}$. Plugging this into Theorem 1 and
using our setting of $\varepsilon$, we have that the bias conditional on every
event $E_{y_{1},y_{2}}\in\mathcal{E}$ is bounded by:

$\alpha(n_{T}(E_{y_{1},y_{2}})\leq
O\left(\sqrt{\frac{\ln(T/\varepsilon^{2})}{T}}+\varepsilon\right)=O\left(\sqrt{\frac{\ln
T}{T}}\right)$

Thus by Theorem 2, any agent with utility function $u$ and action set
$\mathcal{A}$ has swap regret at most:

$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
O\left(L|\mathcal{A}|\sqrt{\frac{\ln T}{T}}\right)$

∎

For $d=1$, the set of all convex hulls over a discrete prediction space was
particularly simple: the set of intervals over the same discretization. In
higher dimensions, characterizing the set of all convex hulls of discrete
points is considerably more difficult. The main ingredient for our result in
the $d=2$ dimensional case is the following theorem shown by Ivic et al.
(1994), which establishes the number of convex hulls of points in a two-
dimensional grid space. Thus, taking our predictions to lie in such a grid
space, the number of possible best response events directly follows from this
result.

######  Theorem 4.

(Ivic et al., 1994) Consider an integer grid of size $m\times m$. Let $D(m)$
denote the number of convex polygons whose vertices have integer coordinates
(i.e. number of convex hulls of grid points) that are distinct up to
translation. Then, there exists a constant $C$ such that $\ln D(m)\leq
Cm^{2/3}$.

######  Remark 2.

To count the total number of convex polygons $I(m)$ with integer vertices in
the $m\times m$ integer grid, observe that there are at most $m^{2}$ possible
translations of any polygon in the grid to another polygon in the grid with
integer vertices. Thus, $I(m)\leq m^{2}D(m)$.

######  Theorem 5.

Consider a prediction space $\mathcal{C}=[0,1]^{2}$ and let
$\mathcal{C}_{\varepsilon}$ be an $\varepsilon$-net of $\mathcal{C}$ obtained
by discretizing each coordinate to multiples of $\varepsilon$. Let
$\mathcal{P}_{\varepsilon}$ be the set of all convex polygons with vertices
belonging to $\mathcal{C}_{\varepsilon}$. Define $E_{P}(y)=\mathbbm{1}[y\in
P]$ to be the event indicating whether $y$ lies in a polygon $P$. Then, using
the algorithm of Noarov et al. (2023) with
$\mathcal{E}=\\{E_{P}\\}_{P\in\mathcal{P}_{\varepsilon}}$ and
$\varepsilon=\frac{1}{T^{3/8}}$, an agent with any action set $\mathcal{A}$
and utility function $u$ who best responds to the forecasts obtains swap
regret bounded by:

$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
O\left(\frac{L|\mathcal{A}|\sqrt{\ln(T)}}{T^{3/8}}\right)$

###### Proof.

By construction of $\mathcal{C}_{\varepsilon}$, our predictions lie in a
$\frac{1}{\varepsilon}\times\frac{1}{\varepsilon}$ grid, and so
$|\mathcal{E}|=I(\frac{1}{\varepsilon})$. Plugging into Theorem 1, it follows
from Theorem 4 and Remark 2 that the bias conditional on every event
$E_{P}\in\mathcal{E}$ is at most:

$\displaystyle\alpha(n_{T}(E_{P}))\leq
O\left(\sqrt{\frac{\ln(I(\frac{1}{\varepsilon})T)}{T}}+\varepsilon\right)\leq
O\left(\sqrt{\frac{\ln(\frac{T}{\varepsilon^{2}}D(\frac{1}{\varepsilon}))}{T}}+\varepsilon\right)\leq
O\left(\sqrt{\frac{\frac{1}{\varepsilon^{2/3}}\ln(\frac{T}{\varepsilon^{2}})}{T}}+\varepsilon\right)$

For $\varepsilon=\frac{1}{T^{3/8}}$, we get $\alpha(n_{T}(E_{P}))\leq
O\left(\frac{\sqrt{\ln(T)}}{T^{3/8}}\right)$. By Theorem 2, we can conclude
that the agent has swap regret at most:

$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
O\left(\frac{L|\mathcal{A}|\sqrt{\ln(T)}}{T^{3/8}}\right)$

∎

##  4 Predictions in Higher Dimensions

In the previous section we showed that by taking advantage of nice structural
properties of best response correspondences, we can—in one- and two-
dimensional settings—straightforwardly enumerate the set of all best response
events across all possible downstream utility functions. Making predictions
that are unbiased with respect to this set yields low swap regret for all
possible downstream agents who best respond to forecasts. Turning now to the
general setting, i.e. where we consider $d$-dimensional predictions, this
approach will no longer be tractable. This is because our previous results
crucially rely on the fact that in low dimensions, convex regions over grid
points—and correspondingly best response events induced by predictions made
over grid points—have boundedly low complexity. Most saliently, convex regions
in one dimension are specified by just two points. In two dimensions, already,
convex regions on grid points are substantially more complex —although
fortunately, we can exploit a geometric result bounding the number of convex
regions. In higher dimensions, we cannot in general expect to furnish a
reasonably sized collection of events in this way. Naively, the number of
convex hulls taken over $\left(\frac{1}{\varepsilon}\right)^{d}$ discrete
predictions is doubly exponential in $d$ (remember that we can only obtain
bias that depends logarithmically in the number of events).

Thus to solve the general case, we take a different approach: we enumerate all
possible utility functions—up to some discretization, and then subsequently
define events corresponding to agent responses for agents with utility
functions within this discretization. Recall that the bias obtained by Theorem
1 depends on the number of conditioning events. The space of utility functions
is continuously large, and so in order to obtain reasonable bounds, we cannot
discretize the utility functions too finely.

When we restrict our attention to this finite net of utility functions, we can
only hope to approximate the utility function of any particular agent. This is
problematic due to the fact that the best response function is discontinuous;
best response events corresponding to this discretized set of utility
functions are not guaranteed to be close to an agent’s actual best responses,
even if their utility function is close to that of one of the discretized
utility functions. We illustrate this in the following lemma, which states
that there are utility functions such that even as the difference between
their payoffs approach 0, bias conditional on their best response events
differ by a constant, and the cumulative swap regret of best responding agents
differ by $\Omega(T)$.

######  Lemma 2.

Fix $\delta\in(0,0.5)$. Consider a prediction and outcome space
$\mathcal{C}=[0,1]$. There exist utility functions $u,\tilde{u}$ and a
sequence of predictions $\hat{y}_{1},...,\hat{y}_{T}$ and outcomes
$y_{1},...,y_{T}$ such that
$|u(a,y)-\tilde{u}(a,y)|\leq\frac{2\delta}{1+2\delta}$ for all
$a\in\mathcal{A},y\in\mathcal{C}$, but $\alpha(E_{u,a})=0$ while
$\alpha(E_{\tilde{u},a})=0.5+\delta$, where $E_{u,a}$ and $E_{\tilde{u},a}$
denote the best response events corresponding to $u$ and $\tilde{u}$
respectively. Furthermore, an agent who takes action
$a_{t}=BR(\tilde{u},\hat{y}_{t})$ for all $t\in[T]$ accumulates average swap
regret $\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(\tilde{u},\phi)=1$.

###### Proof.

Consider an agent who chooses from two actions $\mathcal{A}=\\{0,1\\}$. We
will define $u$ so that the best response function induced by $u$ is a
thresholding at $y=0.5-\delta$: an agent chooses action 1 if and only if
$y\geq 0.5-\delta$ (we assume tie-breaking in favor of action 1). Similarly,
$\tilde{u}$ will induce a thresholding at $y=0.5$. Formally, we can write
$u(a,y)=\frac{1}{1+2\delta}(a(y+\delta)+(1-a)(1-y-\delta)+\delta)$ and
$\tilde{u}(a,y)=ay+(1-a)(1-y)$. It is easy to check that both utility
functions are affine in $y$. Moreover, we can compute their absolute
difference: for $a=1$, we have that

$\displaystyle|u(1,y)-\tilde{u}(1,y)|=\left|\frac{y+2\delta}{1+2\delta}-y\right|=\left|\frac{2\delta}{1+2\delta}-y\left(\frac{2\delta}{1+2\delta}\right)\right|\leq\frac{2\delta}{1+2\delta}$

and for $a=0$, we have that

$\displaystyle|u(0,y)-\tilde{u}(0,y)|=\left|\frac{1-y}{1+2\delta}-(1-y)\right|=\left|y\left(\frac{2\delta}{1+2\delta}\right)-\frac{2\delta}{1+2\delta}\right|\leq\frac{2\delta}{1+2\delta}$

Now, consider a sequence of predictions where $\hat{y}_{t}=0.5-\delta$ for odd
$t$ and $\hat{y}_{t}=0.5+\delta$ for even $t$. For odd $t$, the outcome is
$y_{t}=1$, and for even $t$, the outcome is $y_{t}=0$.

An agent who best responds according to $u$ takes action $a_{t}=1$ at every
round. Thus, the bias conditioned on the best response event corresponding to
$u$ is the bias taken over the entire sequence, and we can see that
$\alpha(E_{u,1})=\left|\frac{1}{T}\sum_{t=1}^{T}\mathbbm{1}[BR(u,\hat{y}_{t})=1](\hat{y}_{t}-y_{t})\right|=0$.
On the other hand, an agent who best responds according to $\tilde{u}$ takes
action $a_{t}=0$ on odd rounds and action $a_{t}=1$ on even rounds. In this
case, observe that the bias conditioned on the best response events
corresponding to $\tilde{u}$ is:
$\alpha(E_{\tilde{u},0})=\alpha(E_{\tilde{u},1})=0.5+\delta$. Furthermore,
$\tilde{u}(a_{t},y_{t})=0$ for all $t$, while applying a counterfactual swap
would grant the agent utility 1 at every round. The claim then follows. ∎

To circumvent this issue, we consider agents who play a continuous
approximation to their best response, which will, intuitively speaking, smooth
out the discontinuities of strictly best responding. As we will discuss, this
modelling of agent behavior is well-founded in an extensive line of work on
quantal choice in the economics literature. Our main result in this section is
Theorem 7, which states that there is an algorithm that guarantees diminishing
swap regret at a rate of $\tilde{O}(T^{2/3})$ for any possible agent with $k$
actions who smoothly best responds to our forecasts, in any dimension $d$. We
remark that while this result substantially improves upon what is achievable
via calibrated predictions, we do not recover optimal swap regret bounds of
$O(\sqrt{T})$. Along the way, however, we show (in Theorem 6) how to recover
$O(\sqrt{T})$ swap regret for agents who respond in a slightly different, but
perhaps less realistic, manner — in particular, agents who act by best
responding according not to their own utility function, but to the closest
utility function in an appropriately defined $\delta$-cover of utility
functions. We remark that, unlike in our previous results, our algorithms in
this section require as input a parameter $k$ that serves as an upper bound on
the number of actions available to any downstream agent to whom we give
guarantees.

###  4.1 Discretizing the Space of Utility Functions

We begin by describing a suitable discretization of utility functions. Recall
that to linearize a utility function that is affine over a $d$-dimensional
prediction space, we can simply augment the prediction space by one dimension
and consider instead the $(d+1)$-dimensional prediction space
$\mathcal{C}\subseteq[0,1]^{d+1}$ where every $y\in\mathcal{C}$ takes value 1
in its last coordinate. We will overload notation by extending affine utility
functions over a $d$-dimensional prediction space to linear functions over a
$(d+1)$-dimensional prediction space in this way and henceforth restrict our
attention to utility functions that are linear in $y$.

We will choose a discretization that approximates any possible utility
function within a distance of $\delta$.

######  Definition 6 ($\delta$-Cover of Utility Functions).

Let $\mathcal{U}$ be a set of utility functions. We say that
$\mathcal{U}_{\delta}$ is a $\delta$-cover of $\mathcal{U}$ if for every
$u\in\mathcal{U}$, there exists $u_{\delta}\in\mathcal{U}_{\delta}$ such that
for every $a\in\mathcal{A}$ and $y\in\mathcal{C}$,
$|u(a,y)-u_{\delta}(a,y)|\leq\delta$.

######  Lemma 3.

Let $\mathcal{U}^{k}$ be the set of utility functions over an action set
$\mathcal{A}$ of size at most $k$ and a prediction space
$\mathcal{C}\subseteq[0,1]^{d+1}$ that are linear in their second argument.
For some parameter $\delta>0$, let $\delta^{\prime}=\delta(d+1)$. Then, there
is a $\delta^{\prime}$-cover of $\mathcal{U}^{k}$, denoted by
$\mathcal{U}^{k}_{\delta^{\prime}}$, with
$|\mathcal{U}^{k}_{\delta^{\prime}}|\leq\left(\frac{1}{\delta}\right)^{k(d+1)}$.

###### Proof.

Consider any $u\in\mathcal{U}^{k}$. By linearity of $u$ in its second
argument, for any $i\in\mathcal{A}$ we can write $u(i,y)=\langle
v^{i},y\rangle$ from some $v^{i}\in[0,1]^{d+1}$ (note that entries of $v^{i}$
must be bounded within $[0,1]$, since $u(i,y)$ is bounded within $[0,1]$). In
other words, since $|\mathcal{A}|\leq k$, $u$ is parameterized by a set of at
most $k$ vectors $v^{1},...,v^{k}\in[0,1]^{d+1}$.

We construct a $\delta^{\prime}$-cover of $\mathcal{U}^{k}$ by considering a
discretized set of representative vectors. Specifically, let
$\mathcal{V}_{\delta}\subseteq[0,1]^{d+1}$ be a $\delta$-net of
$[0,1]^{d+1}$—that is, for every $v\in[0,1]^{d+1}$, there exists
$v_{\delta}\in\mathcal{V}_{\delta}$ such that
$\|v-v_{\delta}\|_{\infty}\leq\delta$. Observe that we can obtain such a
$\delta$-net by discretizing each coordinate to multiplies of $\delta$. Thus,
we have $|\mathcal{V}_{\delta}|\leq\left(\frac{1}{\delta}\right)^{d+1}$.
Define $\mathcal{U}_{\delta^{\prime}}^{k}$ to be the set of utility functions
parameterized by discretized vectors
$v^{1}_{\delta},...,v^{k}_{\delta}\in\mathcal{V}_{\delta}$. That is, given any
$u_{\delta^{\prime}}\in\mathcal{U}_{\delta^{\prime}}^{k}$, we have for every
$i\in\mathcal{A}$, $u_{\delta^{\prime}}(i,y)=\langle v^{i}_{\delta},y\rangle$
for some $v^{i}_{\delta}\in\mathcal{V}_{\delta}$.

By the fact that $\mathcal{V}_{\delta}$ is a $\delta$-net, it follows that for
any $u\in\mathcal{U}^{k}$ parameterized by $v^{1},...,v^{k}$, we can find a
nearby $u_{\delta^{\prime}}\in\mathcal{U}_{\delta^{\prime}}^{k}$ parameterized
by $v^{1}_{\delta},...,v^{k}_{\delta}$ such that
$\|v^{i}-v^{i}_{\delta}\|_{\infty}\leq\delta$ for all $i\in[k]$. Thus, we have
that $\mathcal{U}_{\delta^{\prime}}^{k}$ is indeed a $\delta^{\prime}$-cover
of $\mathcal{U}^{k}$:

$|u(i,y)-u_{\delta^{\prime}}(i,y)|=|\langle
v^{i}-v^{i}_{\delta},y\rangle|\leq\|v^{i}-v^{i}_{\delta}\|_{\infty}\cdot(d+1)\leq\delta(d+1)$

Moreover, we have that
$|\mathcal{U}_{\delta^{\prime}}^{k}|=|\mathcal{V}_{\delta}|^{k}\leq\left(\frac{1}{\delta}\right)^{k(d+1)}$,
which completes the proof. ∎

With this discretized set of utility functions in hand, our next result shows
how to recover $\tilde{O}(\sqrt{T})$ swap regret bounds under a particular
assumption on agent behavior. Imagine an agent with utility function $u$ who
computes their best response not according to $u$, but rather according to the
utility function given by “snapping” $u$ to a nearby $u_{\delta^{\prime}}$ in
the $\delta^{\prime}$-cover. By definition of a $\delta^{\prime}$-cover,
$u_{\delta^{\prime}}$ closely approximates $u$, and hence, the agent does not
lose too much utility—at most $\delta^{\prime}$ each round—by best responding
to $u_{\delta^{\prime}}$ instead of $u$. Then, as we shall see, requiring our
predictions to be unbiased conditional on the best response correspondences of
the $\delta^{\prime}$-cover yields optimal swap regret guarantees (up to
logarithmic factors) for the agent—of course as measured with respect to their
real utility function $u$.

######  Theorem 6.

Fix a transcript $\pi_{T}$. Let $\mathcal{U}^{k}$ be the set of utility
functions over an action set of size at most $k$ and prediction space
$\mathcal{C}$ that are linear in its second argument. Let
$\mathcal{U}_{\delta^{\prime}}^{k}$ be the $\delta^{\prime}$-cover of
$\mathcal{U}^{k}$ given by Lemma 3, where $\delta^{\prime}=\delta(d+1)$ for
some parameter $\delta>0$. Define
$\mathcal{E}_{\mathcal{U}_{\delta^{\prime}}^{k}}$ to be the collection of best
response events corresponding to all
$u_{\delta^{\prime}}\in\mathcal{U}_{\delta^{\prime}}^{k}$:

$\mathcal{E}_{\mathcal{U}_{\delta^{\prime}}^{k}}=\\{E_{u_{\delta^{\prime}},a}(y)=\mathbbm{1}[BR(u_{\delta^{\prime}},y)=a]:u_{\delta^{\prime}}\in\mathcal{U}_{\delta^{\prime}}^{k},a\in[k]\\}$

Consider an agent with action set $\mathcal{A}$ such that $|\mathcal{A}|\leq
k$, and utility function $u\in\mathcal{U}^{k}$. Suppose at every round
$t\in[T]$, the agent takes action $a_{t}=BR(u_{\delta^{\prime}},\hat{y}_{t})$
for a nearby $u_{\delta^{\prime}}$ satisfying
$|u(a,y)-u_{\delta^{\prime}}(a,y)|\leq\delta^{\prime}$ for all
$a\in\mathcal{A},y\in\mathcal{C}$. Then, setting
$\delta=\frac{1}{(d+1)\sqrt{T}}$ and using the prediction algorithm of Noarov
et al. (2023) with the set of events
$\mathcal{E}_{\mathcal{U}_{\delta^{\prime}}^{k}}$, the agent has swap regret
bounded by:

$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
O\left(L\sqrt{\frac{|\mathcal{A}|dk\ln(Tdk)}{T}}\right)$

###### Proof.

By Lemma 3, we have that
$|\mathcal{U}_{\delta^{\prime}}^{k}|\leq\left(\frac{1}{\delta}\right)^{k(d+1)}$.
Thus $|\mathcal{E}_{\mathcal{U}_{\delta^{\prime}}^{k}}|\leq
k\left(\frac{1}{\delta}\right)^{k(d+1)}$. Plugging this into Theorem 1, we
have that for sufficiently small $\varepsilon$, the bias conditional on
$\mathcal{E}_{\mathcal{U}_{\delta^{\prime}}^{k}}$ is at most:

$\alpha(n_{T}(E_{u_{\delta^{\prime}},a}))\leq
O\left(\frac{\ln(Tdk\left(\frac{1}{\delta}\right)^{k(d+1)})+\sqrt{\ln(Tdk\left(\frac{1}{\delta}\right)^{k(d+1)})\cdot
n_{T}(E_{u_{\delta^{\prime}},a})}}{T}\right)$

Then, since our predictions are unbiased subject to the best response events
of $u_{\delta^{\prime}}$, Theorem 2 bounds the swap regret as measured with
respect to $u_{\delta^{\prime}}$. For any action modification rule
$\phi:\mathcal{A}\to\mathcal{A}$, we have:

$\sum_{t=1}^{T}\left(u_{\delta^{\prime}}(\phi(a_{t}),y_{t})-u_{\delta^{\prime}}(a_{t},y_{t})\right)\leq
O\left(L\sqrt{\frac{|\mathcal{A}|\ln(Tdk\left(\frac{1}{\delta}\right)^{k(d+1)})}{T}}\right)\leq
O\left(L\sqrt{\frac{|\mathcal{A}|dk\ln(Tdk\left(\frac{1}{\delta}\right))}{T}}\right)$

The proof then follows from the fact the agent’s payoff under $u$ is
comparable to their payoff under $u_{\delta^{\prime}}$ for any sequence of
realized actions and benchmarks. We have that

$\displaystyle\max_{\phi:\mathcal{A}\to\mathcal{A}}\sum_{t=1}^{T}\left(u(\phi(a_{t}),y_{t})-u(a_{t},y_{t})\right)$
$\displaystyle\leq\left(\max_{\phi:\mathcal{A}\to\mathcal{A}}\sum_{t=1}^{T}\left(u_{\delta^{\prime}}(\phi(a_{t}),y_{t})-u_{\delta^{\prime}}(a_{t},y_{t})\right)\right)+2\delta^{\prime}$
$\displaystyle\leq
O\left(L\sqrt{\frac{|\mathcal{A}|dk\ln(Tdk\left(\frac{1}{\delta}\right))}{T}}\right)+2\delta(d+1)$
$\displaystyle\leq O\left(L\sqrt{\frac{|\mathcal{A}|dk\ln(Tdk)}{T}}\right)$

where in the last step we use our setting of $\delta$. ∎

###  4.2 Predicting for Arbitrary Agents

One might worry that it is unreasonable to expect agents to best respond using
a snapped utility function, even if it is payoff-wise close to their true
utility function. Motivated by this concern, we now turn to a behavioral
assumption that is well-studied in the economics literature—namely, that
agents choose their actions from a smoothed distribution. In our main result
in this section, we show how to construct a collection of events such that,
using the algorithm of Theorem 1, downstream agents who smoothly best respond
are guaranteed diminishing swap regret at a rate of $\tilde{O}(T^{2/3})$.

####  4.2.1 Smooth Best Response

We first define our notion of smooth best response, which is called logistic
response in the literature. Whereas the best response function places all of
the mass of an agent’s response onto the utility-maximizing action, the smooth
analogue assigns mass to each action in proportion to its utility. Under
logistic response, an agent with action set $\mathcal{A}$ and utility function
$u$ plays the distribution $q(u,y)\in\Delta\mathcal{A}$ where the weight
placed on action $a$ is given by:

$q_{a}(u,y)=\frac{\exp(\eta\cdot
u(a,y))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\eta\cdot u(a^{\prime},y))}$

We should think of the parameter $\eta>0$ as controlling the smoothness of the
distribution. In particular, taking $\eta\to\infty$, logistic response
coincides with strictly best responding.

As previously mentioned, smoothening the best response function harks back to
an extensive line of work on quantal choice theory in the economics
literature. Specifically, quantal choice models agents who best respond to
utilities that are perturbed by a noise vector. The logistic response function
is a popular instantiation of quantal response (Luce, 1959; McFadden, 1976;
McKelvey and Palfrey, 1995; Anderson et al., 2002; Goeree et al., 2002), where
the noise vector is drawn from the Gumbel distribution which has cumulative
distribution function $F(x)=\exp(-\exp(-\eta x))$; in this case, it can be
shown that the probability an agent chooses an action $a$ is proportional to
$\exp(\eta\cdot u(a,y))$.

Finally, note that while we prove the next result with this particular
instantiation of smoothed response in mind, our result extends to any response
function satisfying two conditions: first, the function gives an approximate
best response, and second, the induced weights are sufficiently Lipschitz in
utilities (the swap regret bounds will depend on the approximation factor and
the Lipschitz constant). We focus on logistic response just for concreteness.

####  4.2.2 Connecting Unbiased Predictions and Agent Swap Regret

As before, to argue that agents acting according to our predictions will have
diminishing swap regret according to the actual realizations, it is crucial
for agents to be able to estimate their payoffs using our predictions in an
unbiased way. One might hope that the technique used to derive our results in
low-dimensional cases—namely, requiring our predictions to be unbiased
conditional on best response events—might also apply here. However, agents now
choose from a much richer action space: distributions over $\mathcal{A}$. In
some sense, best response events are too coarse in that they only capture the
rounds on which some action was assigned the highest probability. Instead, we
would like our predictions to be unbiased conditional on the event the agent
plays some distribution over $\mathcal{A}$. This would be prohibitive, since
there are exponentially many such distributions (up to discretization).
Fortunately, we will show that it suffices to consider only events defined by
the marginal probabilities placed on actions—i.e. events defined by an agent
placing some probability $p$ on some action $a$. This will be sufficient
because of the linearity of the agents’ utility functions. To construct a
finite set of events, we let
$S_{\tau}=\\{0,...,\left\lfloor\frac{1}{\tau}\right\rfloor-1\\}$ parameterize
a bucketing of width $\tau$. Let $B^{i}_{\tau}=[i\tau,(i+1)\tau)$ for
$i=0,...,\left\lfloor\frac{1}{\tau}\right\rfloor-2$ and
$B_{\tau}^{i}=[i\tau,(i+1)\tau]$ for
$i=\left\lfloor\frac{1}{\tau}\right\rfloor-1$ denote the $i^{th}$ bucket. Next
we define events corresponding to bucketed marginal probabilities and
establish a regret bound for the general setting.

######  Theorem 7.

Fix a transcript $\pi_{T}$. Let $\mathcal{U}^{k}$ be the set of utility
functions over an action set of size at most $k$ and prediction space
$\mathcal{C}$ that are linear in its second argument. Let
$\mathcal{U}_{\delta^{\prime}}^{k}$ be the $\delta^{\prime}$-cover of
$\mathcal{U}^{k}$ given by Lemma 3, where $\delta^{\prime}=\delta(d+1)$ for
some parameter $\delta>0$. Consider an agent with action set $\mathcal{A}$ and
utility function $u\in\mathcal{U}^{k}$ who, at every round $t\in[T]$, plays
the distribution $q(u,\hat{y}_{t})\in\Delta\mathcal{A}$ given by the logistic
response function specified by some parameter $\eta>0$. Let
$q_{a}(u,\hat{y}_{t})$ be the weight assigned to action $a$. Let
$E_{u,a,i}(y)=\mathbbm{1}[q_{a}(u,y)\in B^{i}_{\tau}]$. Define $\mathcal{E}$
to be the collection of events
$\mathcal{E}=\\{E_{u_{\delta^{\prime}},a,i}:u_{\delta^{\prime}}\in\mathcal{U}_{\delta^{\prime}}^{k},a\in[k],i\in
S_{\tau}\\}$. Then, using the algorithm given by Noarov et al. (2023)
parameterized by event set $\mathcal{E}$ to make predictions, any such agent
is guaranteed swap regret bounded by:

$\max_{\phi:\mathcal{A}\to\mathcal{A}}Reg(u,\phi)\leq
O\left(\frac{|\mathcal{A}|L\sqrt{Ldk\ln(TLdk)}}{T^{1/3}}\right)$

for $\eta=O(\sqrt{T}\ln
k),\delta=O\left(\frac{\ln(1/k\sqrt{T})}{d\sqrt{T}}\right)$, and
$\tau=O\left(\frac{1}{kLT^{1/3}}\right)$.

###### Proof.

Recall that the guarantees of conditional bias given by Noarov et al. (2023)
depend on the number of events. By Lemma 3, we have that
$|\mathcal{E}|=k|S_{\tau}||\mathcal{U}_{\delta^{\prime}}^{k}|\leq
k\left\lfloor\frac{1}{\tau}\right\rfloor\left(\frac{1}{\delta}\right)^{k(d+1)}$.
Plugging this into Theorem 1, we can conclude that for sufficiently small
$\varepsilon$, the conditional bias on $\mathcal{E}$ is at most

$\displaystyle\alpha(n_{T}(E_{u,a,i}))$ $\displaystyle\leq
O\left(\frac{\ln(Tdk\left\lfloor\frac{1}{\tau}\right\rfloor\left(\frac{1}{\delta}\right)^{k(d+1)})+\sqrt{\ln(Tdk\left\lfloor\frac{1}{\tau}\right\rfloor\left(\frac{1}{\delta}\right)^{k(d+1)})\cdot
n_{T}(E_{u,a,i})}}{T}\right)$ $\displaystyle\leq
O\left(\frac{dk\ln(Tdk\left\lfloor\frac{1}{\tau}\right\rfloor\left(\frac{1}{\delta}\right))+\sqrt{dk\ln(Tdk\left\lfloor\frac{1}{\tau}\right\rfloor\left(\frac{1}{\delta}\right))\cdot
n_{T}(E_{u,a,i})}}{T}\right)$

The remainder of the proof is structured as follows. Recall that an agent’s
utility function $u$ can be closely approximated by a nearby utility function
$u_{\delta^{\prime}}$ in the $\delta^{\prime}$-cover
$\mathcal{U}_{\delta^{\prime}}^{k}$. We first measure the swap regret of the
agent had they behaved and received payoff according to $u_{\delta^{\prime}}$.
Here, we rely on the fact that the predictions are unbiased conditional on
(bucketed) marginal probabilities assigned to each action. Thus, the agent’s
estimate of their utility whenever they assign a certain probability to an
action is (on average) correct, and so the agent’s calculation of their
expected utility over the distribution they play—and any other distribution—is
correct. Therefore, since the agent plays an approximate best response, the
distribution they play yields no swap regret up to the bias of our predictions
and the gap introduced by the approximation.

Of course, the agent actually behaves and receives payoff according to $u$
rather than $u_{\delta^{\prime}}$. Here, we use the fact that the logistic
response function is Lipschitz in utilities—in particular, since $u$ and
$u_{\delta^{\prime}}$ give similar utilities, $u$ and $u_{\delta^{\prime}}$
induce similar distributions over actions. Thus, we can establish that the
expected utility the agent obtains by responding according to $u$ cannot be
too much smaller than the expected utility the agent could have obtained by
responding according to $u_{\delta^{\prime}}$. Similarly, the expected utility
obtained by any benchmark class of actions under $u$ cannot be too much larger
than the expected utility obtained by the same benchmark class under
$u_{\delta^{\prime}}$. This then bounds the swap regret of the agent.

Thus, to prove Theorem 7, we first introduce the following intermediate lemma
that bounds the swap regret as measured with respect to $u_{\delta^{\prime}}$.

######  Lemma 4.

Fix a utility function
$u_{\delta^{\prime}}\in\mathcal{U}_{\delta^{\prime}}^{k}$ and consider an
agent who, at round $t$, plays the distribution
$q(u_{\delta^{\prime}},\hat{y}_{t})$ given by the logistic response function.
Then, for any action modification rule $\phi:\mathcal{A}\to\mathcal{A}$, we
have:

$\frac{1}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}\operatorname*{\mathbb{E}}_{a\sim
q(u_{\delta^{\prime}},\hat{y}_{t})}[u_{\delta^{\prime}}(\phi(a),y_{t})-u_{\delta^{\prime}}(a,y_{t})]\leq\frac{\ln|\mathcal{A}|+1}{\eta}+2|\mathcal{A}|L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+2|\mathcal{A}|L\tau$

The proof of Lemma 4 will make use of two lemmas. The first lemma will help us
establish that in expectation over the rounds in which the agent plays action
$a$, our conditional bias guarantees are (approximately) preserved.

######  Lemma 5.

Fix any $a\in\mathcal{A}$. If $\pi_{T}$ results in bias at most
$\alpha(n_{T}(E_{u_{\delta^{\prime}},a,i}))$ conditional on the event
$E_{u_{\delta^{\prime}},a,i}$ for all $i\in S_{\tau}$, then we have:

$\left\|\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y_{t}})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})(\hat{y_{t}}-y_{t})]\right\|_{\infty}\leq\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+\tau$

###### Proof.

Observe that

$\displaystyle\left\|\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y_{t}})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})(\hat{y_{t}}-y_{t})]\right\|_{\infty}$
$\displaystyle=\Bigg{\|}\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}[\mathbbm{1}[(\hat{y_{t}}-y_{t})\geq
0]\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}]q_{a}(u_{\delta^{\prime}},\hat{y}_{t})(\hat{y_{t}}-y_{t})$
$\displaystyle\hskip
70.0001pt+\mathbbm{1}[(\hat{y_{t}}-y_{t})<0]\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}]q_{a}(u_{\delta^{\prime}},\hat{y}_{t})(\hat{y_{t}}-y_{t})]\Bigg{\|}_{\infty}$
$\displaystyle\leq\Bigg{\|}\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}[\mathbbm{1}[(\hat{y_{t}}-y_{t})\geq
0]\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}]\cdot((i+1)\tau)(\hat{y_{t}}-y_{t})$ $\displaystyle\hskip
70.0001pt+\mathbbm{1}[(\hat{y_{t}}-y_{t})<0]\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}]\cdot(i\tau)(\hat{y_{t}}-y_{t})]\Bigg{\|}_{\infty}$
$\displaystyle\leq\left\|\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}[\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}]\cdot(i\tau)(\hat{y_{t}}-y_{t})+\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}]\cdot\tau]\right\|_{\infty}$
$\displaystyle=\left\|\frac{1}{T}\sum_{i\in
S_{\tau}}i\tau\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}\left[\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}](\hat{y_{t}}-y_{t})\right]\right\|_{\infty}+\frac{\tau}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}\left[\sum_{i\in
S_{\tau}}\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}]\right]$ $\displaystyle\leq\sum_{i\in
S_{\tau}}i\tau\cdot\frac{1}{T}\left\|\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}\left[\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}](\hat{y_{t}}-y_{t})\right]\right\|_{\infty}+\frac{\tau}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y_{t}}\sim
p_{t}}\left[\sum_{i\in
S_{\tau}}\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in
B_{\tau}^{i}]\right]$ $\displaystyle\leq\sum_{i\in
S_{\tau}}\alpha(n_{T}(E_{u_{\delta^{\prime}},a,i}))+\tau$

The last inequality follows from our assumption of $\alpha$-unbiasedness, the
fact that $i\tau\leq 1$ for all $i$, and the fact that for any utility
function $u_{\delta^{\prime}}$ and action $a$, the events
$\\{E_{u_{\delta^{\prime}},a,i}\\}_{i\in S_{\tau}}$ are disjoint—the indicator
$\mathbbm{1}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\in B_{\tau}^{i}]=1$ for
exactly one $i\in S_{\tau}$, i.e. $\sum_{i\in
S_{\tau}}E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})=1$. Thus, it also follows
that $\sum_{i\in S_{\tau}}n_{T}(E_{u_{\delta^{\prime}},a,i})=T$, and so by
concavity of $\alpha$, we have that $\sum_{i\in
S_{\tau}}\alpha(n_{T}(E_{u_{\delta^{\prime}},a,i}))\leq|S_{\tau}|\alpha((\sum_{i\in
S_{\tau}}n_{T}(E_{u_{\delta^{\prime}},a,i}))/|S_{\tau}|)=|S_{\tau}|\alpha(T/|S_{\tau}|)$,
which completes the proof. ∎

The next lemma establishes that the utility gained by playing the logistic
response distribution cannot be too much smaller than the utility gained by
playing the best response action (note that this is a general statement that
applies to any utility function). The difference between the two quantities
will be controlled by the parameter $\eta$.

######  Lemma 6.

Fix any utility function $u$ and any $y\in\mathcal{C}$. Let $a^{*}=BR(u,y)$.
We have that:

$\operatorname*{\mathbb{E}}_{a\sim q(u,y)}[u(a,y)]\geq
u(a^{*},y)-\frac{\ln|\mathcal{A}|+1}{\eta}$

###### Proof.

First, we see that for any constant $x$,

$\displaystyle\Pr[u(a,y)\leq x]$ $\displaystyle\leq\frac{\Pr[u(a,y)\leq
x]}{\Pr[u(a,y)=u(a^{*},y)]}\leq\frac{|\mathcal{A}|\exp(\eta x)}{\exp(\eta
u(a^{*},y)}=|\mathcal{A}|\exp(\eta(x-u(a^{*},y)))$

Taking $x=u(a^{*},y)-\frac{1}{\eta}(\ln|\mathcal{A}|+c)$, we have that

$\displaystyle\Pr[u(a,y)\leq
u(a^{*},y)-\frac{1}{\eta}(\ln|\mathcal{A}|+c)]\leq|\mathcal{A}|e^{-\ln|\mathcal{A}|-c}=e^{-c}$

or equivalently, $\Pr[\eta(u(a^{*},y)-u(a,y))\geq\ln|\mathcal{A}|+c]\leq
e^{-c}$. Let $X=\eta(u(a^{*},y)-u(a,y))$. $X$ is a non-negative random
variable, so we have

$\displaystyle\operatorname*{\mathbb{E}}[X]=\int_{0}^{\infty}\Pr[X\geq
x]dx=\int_{c=-\ln|\mathcal{A}|}^{\infty}\Pr[X\geq\ln|\mathcal{A}|+c]dc\leq\int_{c=-\ln|\mathcal{A}|}^{0}1dc+\int_{0}^{\infty}e^{-c}dc=\ln|\mathcal{A}|+1$

where the inequality uses the fact that $\Pr[X\geq\ln|\mathcal{A}|+c]\leq 1$
for $c\leq 0$. Hence it follows that
$u(a^{*},y)-\operatorname*{\mathbb{E}}[u(a,y)]\leq\frac{\ln|\mathcal{A}|+1}{\eta}$,
which proves the lemma. ∎

We are now ready to prove Lemma 4.

Proof of Lemma 4. Fix any action modification rule
$\phi:\mathcal{A}\to\mathcal{A}$. Using linearity of $u_{\delta^{\prime}}$ in
the second argument, we derive:

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}\operatorname*{\mathbb{E}}_{a\sim
q(u_{\delta^{\prime}},\hat{y}_{t})}[u_{\delta^{\prime}}(\phi(a),y_{t})-u_{\delta^{\prime}}(a,y_{t})]$
$\displaystyle=\sum_{a\in\mathcal{A}}\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}\left[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})(u_{\delta^{\prime}}(\phi(a),y_{t})-u_{\delta^{\prime}}(a,y_{t}))\right]$
$\displaystyle=\sum_{a\in\mathcal{A}}\Bigg{(}u_{\delta^{\prime}}(\phi(a),\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})]y_{t})$
$\displaystyle\hskip 25.00003pt-
u_{\delta^{\prime}}(a,\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})]y_{t})\Bigg{)}$
$\displaystyle\leq\Bigg{(}\sum_{a\in\mathcal{A}}\Bigg{(}u_{\delta^{\prime}}(\phi(a),\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\hat{y}_{t}])$
$\displaystyle\hskip 30.00005pt-
u_{\delta^{\prime}}(a,\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\hat{y}_{t}])\Bigg{)}\Bigg{)}+2|\mathcal{A}|L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+2|\mathcal{A}|L\tau$
$\displaystyle=\left(\sum_{a\in\mathcal{A}}\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}\left[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})(u_{\delta^{\prime}}(\phi(a),\hat{y}_{t})-u_{\delta^{\prime}}(a,\hat{y}_{t}))\right]\right)$
$\displaystyle\hskip
10.00002pt+2|\mathcal{A}|L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+2|\mathcal{A}|L\tau$
$\displaystyle=\left(\frac{1}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}\operatorname*{\mathbb{E}}_{a\sim
q(u_{\delta^{\prime}},\hat{y}_{t})}\left[u_{\delta^{\prime}}(\phi(a),\hat{y}_{t})-u_{\delta^{\prime}}(a,\hat{y}_{t})\right]\right)+2|\mathcal{A}|L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+2|\mathcal{A}|L\tau$
which, by the fact that the benchmark action $\phi(a)$ cannot obtain higher
utility than the best response at round $t$, letting
$a^{*}_{t}=BR(u_{\delta^{\prime}},\hat{y}_{t})$, this quantity is at most
$\displaystyle\leq\left(\frac{1}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[u_{\delta^{\prime}}(a^{*}_{t},\hat{y}_{t})-\operatorname*{\mathbb{E}}_{a\sim
q(u_{\delta^{\prime}},\hat{y}_{t})}\left[u_{\delta^{\prime}}(a,\hat{y}_{t})\right]]\right)+2|\mathcal{A}|L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+2|\mathcal{A}|L\tau$
$\displaystyle\leq\left(\frac{1}{T}\sum_{t=1}^{T}\frac{\ln|\mathcal{A}|+1}{\eta}\right)+2|\mathcal{A}|L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+2|\mathcal{A}|L\tau$
$\displaystyle=\frac{\ln|\mathcal{A}|+1}{\eta}+2|\mathcal{A}|L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+2|\mathcal{A}|L\tau$

Here we apply Lemma 5 and $L$-Lipschitzness of $u_{\delta^{\prime}}$ to get
the first inequality: for any action $a$,

$\displaystyle\left|u_{\delta^{\prime}}(a,\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})\hat{y}_{t}])-u_{\delta^{\prime}}(a,\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})]y_{t})\right|$
$\displaystyle\leq L\left\|\frac{1}{T}\sum_{t=1}^{T}\sum_{i\in
S_{\tau}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[E_{u_{\delta^{\prime}},a,i}(\hat{y}_{t})q_{a}(u_{\delta^{\prime}},\hat{y}_{t})(\hat{y}_{t}-y_{t})]\right\|_{\infty}$
$\displaystyle\leq
L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+L\tau$

Finally, we apply Lemma 6 to get the last inequality. This completes the
proof. ∎

Before proving Theorem 7, we introduce one more lemma which states that nearby
utility functions induce nearby distributions over actions—in particular,
perturbing the payoff of any action by a little bit does not change its
assigned weight by too much.

######  Lemma 7.

Fix any $a\in\mathcal{A},y\in\mathcal{C}$. For any utility functions
$u_{1},u_{2}$, if $|u_{1}(a,y)-u_{2}(a,y)|\leq\delta$, then
$|q_{a}(u_{1},y)-q_{a}(u_{2},y)|\leq e^{2\eta\delta}-1$.

###### Proof.

W.l.o.g. assume that $u_{1}(a,y)\geq u_{2}(a,y)$. Then we have that

$\displaystyle\frac{q_{a}(u_{1},y)}{q_{a}(u_{2},y)}$
$\displaystyle=\frac{\left(\frac{\exp(\eta
u_{1}(a,y))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\eta
u_{1}(a^{\prime},y))}\right)}{\left(\frac{\exp(\eta
u_{2}(a,y))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\eta
u_{2}(a^{\prime},y))}\right)}$
$\displaystyle=\exp(\eta(u_{1}(a,y)-u_{2}(a,y)))\cdot\left(\frac{\sum_{a^{\prime}\in\mathcal{A}}\exp(\eta
u_{2}(a^{\prime},y))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\eta
u_{1}(a^{\prime},y))}\right)$
$\displaystyle\leq\exp(\eta\delta)\cdot\left(\frac{\sum_{a^{\prime}\in\mathcal{A}}\exp(\eta(u_{1}(a^{\prime},y)+\delta)}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\eta
u_{1}(a^{\prime},y))}\right)$
$\displaystyle=\exp(\eta\delta)\cdot\exp(\eta\delta)$
$\displaystyle=\exp(2\eta\delta)$

Rearranging the expression, we get
$q_{a}(u_{1},y)\leq\exp(2\eta\delta)q_{a}(u_{2},y)$ and hence, since
$q_{a}(u_{2},y)\leq 1$, we have that

$q_{a}(u_{1},y)-q_{a}(u_{2},y)\leq\exp(2\eta\delta)q_{a}(u_{2},y)-q_{a}(u_{2},y)\leq\exp(2\eta\delta)-1$

which proves the lemma. ∎

We now proceed with the proof of Theorem 7. Recall that by definition of a
$\delta^{\prime}$-net, we can find
$u_{\delta^{\prime}}\in\mathcal{U}_{\delta^{\prime}}^{k}$ such that
$|u(a,y)-u_{\delta^{\prime}}(a,y)|\leq\delta^{\prime}$ for all
$a\in\mathcal{A},y\in\mathcal{C}$. Hence, together with Lemma 7, we can relate
the cumulative utility of the agent to their cumulative utility if they
instead had utility function $u_{\delta^{\prime}}$—for both the realized and
benchmark sequence of actions. An application of Lemma 4 will then bound the
agent’s swap regret. In particular, for any $\phi:\mathcal{A}\to\mathcal{A}$,
we have that

$\displaystyle Reg(u,\phi)$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}\operatorname*{\mathbb{E}}_{a\sim
q(u,\hat{y}_{t})}[u(\phi(a),y_{t})-u(a,y_{t})]$
$\displaystyle\leq\left(\frac{1}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}\operatorname*{\mathbb{E}}_{a\sim
q(u,\hat{y}_{t})}[u_{\delta^{\prime}}(\phi(a),y_{t})-u_{\delta^{\prime}}(a,y_{t})]\right)+2\delta^{\prime}$
$\displaystyle=\left(\frac{1}{T}\sum_{t=1}^{T}\sum_{a\in\mathcal{A}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[q_{a}(u,\hat{y}_{t})(u_{\delta^{\prime}}(\phi(a),y_{t})-u_{\delta^{\prime}}(a,y_{t}))]\right)+2\delta^{\prime}$
$\displaystyle\leq\left(\frac{1}{T}\sum_{t=1}^{T}\sum_{a\in\mathcal{A}}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}[q_{a}(u_{\delta^{\prime}},\hat{y}_{t})(u_{\delta^{\prime}}(\phi(a),y_{t})-u_{\delta^{\prime}}(a,y_{t}))]\right)+|\mathcal{A}|(e^{2\eta\delta^{\prime}}-1)+2\delta^{\prime}$
$\displaystyle=\left(\frac{1}{T}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\hat{y}_{t}\sim
p_{t}}\operatorname*{\mathbb{E}}_{a\sim
q(u_{\delta^{\prime}},\hat{y}_{t})}[u_{\delta^{\prime}}(\phi(a),y_{t})-u_{\delta^{\prime}}(a,y_{t})]\right)+|\mathcal{A}|(e^{2\eta\delta^{\prime}}-1)+2\delta^{\prime}$
$\displaystyle\leq\frac{\ln|\mathcal{A}|+1}{\eta}+2|\mathcal{A}|L\left\lfloor\frac{1}{\tau}\right\rfloor\alpha\left(T/\left\lfloor\frac{1}{\tau}\right\rfloor\right)+2|\mathcal{A}|L\tau+|\mathcal{A}|(e^{2\eta\delta^{\prime}}-1)+2\delta^{\prime}$
$\displaystyle\leq\frac{\ln|\mathcal{A}|+1}{\eta}+O\left(|\mathcal{A}|L\sqrt{\frac{\left\lfloor\frac{1}{\tau}\right\rfloor
dk\ln(Tdk\left\lfloor\frac{1}{\tau}\right\rfloor\left(\frac{1}{\delta}\right))}{T}}\right)+2|\mathcal{A}|L\tau+|\mathcal{A}|(e^{2\eta\delta^{\prime}}-1)+2\delta^{\prime}$

where the first inequality follows from our choice of $u_{\delta^{\prime}}$,
the second inequality follows from Lemma 7, and the last inequality follows
from Lemma 4. In the last step, we substitute in the conditional bias bound
established previously. For $\eta=(\ln
k+1)\sqrt{T},\delta=\frac{\ln((1/k\sqrt{T})+1)}{(d+1)\sqrt{T}},\tau=\frac{1}{kLT^{1/3}}$,
we get

$Reg(u,\phi)\leq
O\left(\frac{|\mathcal{A}|L\sqrt{Ldk\ln(TLdk)}}{T^{1/3}}\right)$

∎

##  5 Discussion and Conclusion

We have shown that it is possible to make predictions that guarantee
diminishing swap regret to _all_ downstream agents simultaneously, at rates
that are substantially faster than are possible by making calibrated
predictions. In particular, for best responding agents, we have shown how to
do this at the optimal $O(\sqrt{T})$ rate for $d=1$ — a rate that is
impossible to obtain via calibration. For agents that are assumed to best
respond according to a discretized version of their own utility function,
we’ve shown how to obtain these optimal $O(\sqrt{T})$ rates for _every_
dimension $d$, and for agents that _smoothly_ best respond according to their
own utility function, we’ve shown how to guarantee all downstream agents swap
regret at the dimension-independent rate $O(T^{2/3})$ in $d$ dimensions. Thus
we have established—perhaps surprisingly—that a substantially weaker condition
than calibration suffices, even when the goal is to guarantee downstream swap
regret simultaneously for all agents. Prior work was able to obtain similar
guarantees only by either relaxing from swap to external regret (Kleinberg et
al., 2023) or by restricting to a fixed collection of downstream agents,
rather than offering guarantees simultaneously to all downstream agents
(Noarov et al., 2023).

Although our approach is computationally efficient for $d=1$, like algorithms
promising calibration, the computational complexity of our approach scales
badly with $d$. We leave as the main open question from our work:

> Is there an algorithm that can make $d$ dimensional predictions that
> guarantee all downstream agents swap regret diminishing at a rate of
> $\tilde{O}(T^{O(1)})$ with per-round running time scaling polynomially with
> $d$?

### Acknowledgements

We thank Georgy Noarov for enlightening conversations and for pointing us to
Ivic et al. (1994). This work was supported in part by the Simons
Collaboration on the Theory of Algorithmic Fairness, NSF grants FAI-2147212
and CCF-2217062, an AWS AI Gift for Research on Trustworthy AI, and the Hans
Sigrist Prize.

## References

  * (1)
  * Anderson et al. (2002) Simon P. Anderson, Jacob K. Goeree, and Charles A. Holt. 2002.  The Logit Equilibrium: A Perspective on Intuitive Behavioral Anomalies.  _Southern Economic Journal_ 69, 1 (2002), 21–47.  http://www.jstor.org/stable/1061555
  * Blum and Mansour (2007) Avrim Blum and Yishay Mansour. 2007.  From External to Internal Regret.  _Journal of Machine Learning Research_ 8, 47 (2007), 1307–1324.  http://jmlr.org/papers/v8/blum07a.html
  * Dawid (1982) A. P. Dawid. 1982.  The Well-Calibrated Bayesian.  _J. Amer. Statist. Assoc._ 77, 379 (1982), 605–610.  https://doi.org/10.1080/01621459.1982.10477856
  * Foster and Hart (2018) Dean P. Foster and Sergiu Hart. 2018.  Smooth calibration, leaky forecasts, finite recall, and Nash dynamics.  _Games and Economic Behavior_ 109 (2018), 271–293.  https://doi.org/10.1016/j.geb.2017.12.022
  * Foster and Vohra (1997) Dean P. Foster and Rakesh V. Vohra. 1997.  Calibrated Learning and Correlated Equilibrium.  _Games and Economic Behavior_ 21, 1 (1997), 40–55.  https://doi.org/10.1006/game.1997.0595
  * Foster and Vohra (1998) Dean P. Foster and Rakesh V. Vohra. 1998.  Asymptotic Calibration.  _Biometrika_ 85, 2 (1998), 379–390.  http://www.jstor.org/stable/2337364
  * Garg et al. (2024) Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. 2024.  _Oracle Efficient Online Multicalibration and Omniprediction_.  2725–2792.  https://doi.org/10.1137/1.9781611977912.98 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.98
  * Globus-Harris et al. (2023) Ira Globus-Harris, Varun Gupta, Christopher Jung, Michael Kearns, Jamie Morgenstern, and Aaron Roth. 2023.  Multicalibrated regression for downstream fairness. In _Proceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society_. 259–286.
  * Goeree et al. (2002) Jacob K. Goeree, Charles A. Holt, and Thomas R. Palfrey. 2002.  Quantal Response Equilibrium and Overbidding in Private-Value Auctions.  _Journal of Economic Theory_ 104, 1 (2002), 247–272.  https://doi.org/10.1006/jeth.2001.2914
  * Gopalan et al. (2023) Parikshit Gopalan, Lunjia Hu, Michael P Kim, Omer Reingold, and Udi Wieder. 2023.  Loss Minimization Through the Lens Of Outcome Indistinguishability. In _14th Innovations in Theoretical Computer Science Conference (ITCS 2023)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Gopalan et al. (2022) Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. 2022.  Omnipredictors. In _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Haghtalab et al. (2023) Nika Haghtalab, Chara Podimata, and Kunhe Yang. 2023.  Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents. In _Thirty-seventh Conference on Neural Information Processing Systems_.  https://openreview.net/forum?id=fHsBNNDroC
  * Hu et al. (2023) Lunjia Hu, Inbal Rachel Livni Navon, Omer Reingold, and Chutong Yang. 2023.  Omnipredictors for constrained optimization. In _International Conference on Machine Learning_. PMLR, 13497–13527.
  * Ivic et al. (1994) A. Ivic, J. Koplowitz, and J. Zunic. 1994.  On the number of digital convex polygons inscribed into an (m,m)-grid.  _IEEE Transactions on Information Theory_ 40, 5 (1994), 1681–1686.  https://doi.org/10.1109/18.333894
  * Kakade and Foster (2008) Sham M. Kakade and Dean P. Foster. 2008.  Deterministic calibration and Nash equilibrium.  _J. Comput. System Sci._ 74, 1 (2008), 115–130.  https://doi.org/10.1016/j.jcss.2007.04.017 Learning Theory 2004.
  * Kleinberg et al. (2023) Bobby Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng. 2023.  U-Calibration: Forecasting for an Unknown Agent. In _Proceedings of Thirty Sixth Conference on Learning Theory_ _(Proceedings of Machine Learning Research, Vol. 195)_ , Gergely Neu and Lorenzo Rosasco (Eds.). PMLR, 5143–5145.  https://proceedings.mlr.press/v195/kleinberg23a.html
  * Luce (1959) R. Duncan Luce. 1959.  _Individual Choice Behavior: A Theoretical analysis_.  Wiley, New York, NY, USA.
  * McFadden (1976) Daniel L. McFadden. 1976.  _Quantal Choice Analysis: A Survey_.  NBER, 363–390.  http://www.nber.org/chapters/c10488
  * McKelvey and Palfrey (1995) Richard D. McKelvey and Thomas R. Palfrey. 1995.  Quantal Response Equilibria for Normal Form Games.  _Games and Economic Behavior_ 10, 1 (1995), 6–38.  https://doi.org/10.1006/game.1995.1023
  * Noarov et al. (2023) Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. 2023.  High-Dimensional Prediction for Sequential Decision Making.  arXiv:2310.17651 [cs.LG]
  * Okoroafor et al. (2023) Princewill Okoroafor, Robert Kleinberg, and Wen Sun. 2023.  Faster Recalibration of an Online Predictor via Approachability.  _arXiv preprint arXiv:2310.17002_ (2023).
  * Qiao and Valiant (2021) Mingda Qiao and Gregory Valiant. 2021.  Stronger calibration lower bounds via sidestepping. In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ (Virtual, Italy) _(STOC 2021)_. Association for Computing Machinery, New York, NY, USA, 456–466.  https://doi.org/10.1145/3406325.3451050
  * Zhao et al. (2021) Shengjia Zhao, Michael Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon. 2021.  Calibrating predictions to decisions: A novel approach to multi-class calibration.  _Advances in Neural Information Processing Systems_ 34 (2021), 22313–22324.