* [KL23a] Hankyung Kim and Youn-Kyung Lim “Investigating How Users Design Everyday Intelligent Systems in Use” In Proceedings of the 2023 ACM Designing Interactive Systems Conference, DIS ’23 Pittsburgh, PA, USA: Association for Computing Machinery, 2023, pp. 702–711

## Appendix

###  Appendix A Extended Related Work

In this section, we provide an extended account of related work from Section
2.

###### Endogenous learning.

One of the key aspects of our model is endogeneity on the side of the
platform, i.e., the platform’s actions affect the data it collects. There is a
vast literature in both economics and computer science that studies endogenous
learning, some of which we heavily rely on in this work.

Our work draws from a long line of work at the intersection of economics and
game theory that explores the dynamics of endogenous misspecified learning.
Although we do not explicitly rely on it here, the Berk-Nash equilibrium
concept [EP16a] provides a basis for much of this work. The concept was later
refined, expanded, and improved upon in several directions [FRS17a, FLS21a,
Boh16a, BH21a, FII20a]. In this work, we rely most heavily on the results of
[FII20a] due to their generality, but our results are portable in the sense
that new ways of characterizing globally stable beliefs will allow for even
sharper results in our setting.

There are also many related equilibrium concepts in the Economics literature
that we do not explore in this work, such as self-confirming equlibrium
[FL93a] and subjective equilbrium [KL93a, KL95a]. Relating these models (and
others) to our setting is an interesting question for future work.

Several works in the computer science literature also study misspecified
learning. Of these, the most related is the work of [PZM+20a] which introduces
the idea of performative prediction. The performative prediction setup mirrors
that of supervised learning, except that the learner’s current parameter
estimate $\theta$ affects the data distribution $D_{\theta}$. Our model can be
viewed as an instance of performative prediction (which in turn, can be viewed
as an instance of reinforcement learning [BHK22a]) that focuses on a specific
kind of performativity induced by users adapting to their platforms.

###### Strategic classification and Stackelberg games.

Strategic classification [HMP+16a] is a two-player game in which one player
(the decision-maker) deploys a machine learning algorithm, and the other
player (the decision subject) strategically reports their features to attain a
favorable decision. Strategic classification also features endogenous
learning, and is a special case of the performative prediction setup mentioned
above. Strategic classification has been the subject of a deluge of recent
work in computer science [BKS12a, HMP+16a, DRS+18a, GNE+21a, ZMS+21a].
Broadly, our model differs from one of strategic classification in that (a) we
restrict the platform to a specific learning algorithm; (b) users have their
own utility functions that they can optimize arbitrarily, and are not bound to
small perturbations of some “ground-truth” features; (c) users can be myopic
or non-myopic in how they interact with the platform.

Prior works have studied deviations from these assumptions. For (a), [ZMS+21a]
study the case where rather than reacting instantaneously, the decision
subject is learning at the same time as the the decision-maker. Closer to our
work, [LR22a] introduce generalized strategic classification, where the
decision subject has a utility function that can be more aligned with that of
the platform. Finally, [HLN+22a] study Stackelberg games (which generalize
strategic classification) with non-myopic agents (i.e., where agents seek to
optimimize their long-term, rather than immediate, payoff). As previously
discussed, our model differs from theirs in that in our case users optimize
their expected limiting payoff, which, and so delaying user input has no
bearing on the game dynamics.

###### User strategization on recommender systems.

There are several related lines of work to ours that concern user
strategization on recommender systems specifically. One line of work studies
the ways in which users try to influence (and succeed in influencing) their
recommendations on popular platforms [SVM22a, KL23a, SHS22a]. Closer to our
work are theoretical models of user strategization on recommender platforms
[CIM22a, HHP23a], where [CIM22a] is an earlier version of this work. Compared
to the latter of these works, we propose a model that (a) extends more
generally to data-driven platforms; (b) allows us to study the causes and
effects of strategization on the platform and its ability to make
counterfactual inferences; and (c) connects strategization back to
trustworthiness of the platform.

Another related work is that of [KMR22a], who study a model of inconsistent
preferences under which users have a “myopic” system 1 that consumes addictive
content and a “non-myopic” system 2 that considers the value of content.
Although we also study myopic and non-myopic users, we use these terms in way
that is subtly different from [KMR22a], and their focus (inconsistent
preferences) is neither necessary nor sufficient for strategization to emerge.
Additionally, strategization concerns users’ response to their platforms’
algorithm, whereas in [KMR22a] the platform’s algorithm is fixed.

###### Multi-agent learning and games.

There are also many lines of work on multi-agent learning, including multi-
agent reinforcement learning (see [ZYB21a, Tan93a, BBD08a] and their
references), multi-agent Bayesian learning (e.g., [WAO20a, WAO21a]), and
inverse reinforcement learning (particularly its cooperative [HDA+16a] and
adversarial [YSE19a] variants). All of these models capture agents learning
and interacting with each other at varying levels of generality. Here, we
focus on a particular instantiation of such setups where two agents interact
in a very specific way, mirroring the interaction between a user and a data-
driven platform. Our interests are also more specifically in studying the
causes and effects of strategic behavior in this setup.

Another related work studies repeated alternating two-player games [RBK+10a]
and considers the complexity of computing equilibria in such games. In our
work, we avoid having to compute such equilibria by assuming that the platform
follows a fixed Bayesian updating strategy.

###### Mechanism design and incentive-compatible auctions.

Our notion of “trustworthiness” from Section 7.1 is highly related to the idea
of incentive-compatibility in mechanism design. There is a rich line of work
in econometrics on designing incentive-compatible methods for repeated games
in general (see, e.g., [MS06a, BM93a, KL93a]), and more specifically for
repeated auctions [DLM+21a, ACK+19a, NCE+22a, ARS13a, KN19a]. In the latter, a
long line of work stems from the tight connections between incentive-
compatibility and differential privacy [MT07a, NST12a].

###### Human-AI collaboration.

Finally, our work contributes to a growing body of work on Human-AI
collaboration [WWM+19a, WCM+20a, MBF+22a] and teaming [ZMF+21a, BNK+19a],
which both study primarily collaborative interactions between AI systems and
their users. In particular, one can view our observations about conditions for
strategization (and corresponding recommendations about trustworthy algorithm
design) in Section 7.2 as principles for human-AI collaboration in the case
where the AI and the human are not entirely aligned.

Within Human-AI collaboration, one line of work in particular isolates trust
as a building block of successful interaction (see, e.g., [OY20a, HHC23a,
EBC+19a, BCD+21a] and references therein). Our work supports the high-level
idea that designing systems with trust in mind is important, but we explore a
slightly different notion of trust than what is typically considered. In
particular, in our case trustworthiness dictates whether a user will maximize
their immediate utility at each step of a game. By comparison, human-AI
collaboration usually explores trust to the end of getting users to use AI
systems in the first place (or comfortably delegate complext tasks to AI
systems).

###  Appendix B Omitted Proofs: Illustrative Example

In this section, we provide the proofs omitted from Section 5.

####  B.1 Proof of Proposition 5.1

See 5.1

###### Proof.

In this proof, we will use the result of [FII20a], restated as Theorem 6.8.
Note that the theorem cannot be applied directly due to the “bounded
likelihood ratios” regularity condition being violated—still, since
$p(\cdot;\mu)$ has full support, we can always wait until the violating user
models are eliminated by Bayes’ rule (which happens almost surely), and then
apply the results from [FII20a] thereafter.

For example, note that $\hat{q}_{3}(B|Z)>0$ for all $B\in\mathcal{B}$ and
$Z\in\mathcal{Z}$, so if $\mathrm{supp}(q)\cap\mathcal{Z}_{A}\neq\emptyset$,
then with probability one we will eventually see a $(B,Z)$ such that $B=1$ and
$Z\in\mathcal{Z}_{A}$, at which point

$\displaystyle\mu(\hat{q}_{2})=\frac{\mu_{t-1}(\hat{q}_{2})\cdot\hat{q}_{2}(B_{t}|Z_{t})}{\sum_{\hat{q}_{i}\in\widehat{\mathcal{Q}}}\mu_{t-1}(\hat{q}_{i})\cdot\hat{q}_{i}(B_{t}|Z_{t})}=0,$

and thus we can apply the results from [FII20a] to the set
$\\{\hat{q}_{1},\hat{q}_{3}\\}$.

note that for any belief $\mu$ and any user model $\hat{q}$,

$\displaystyle KL(p^{\mu}\times q,p^{\mu}\times\hat{q})$
$\displaystyle=\mathbb{E}_{(B,Z)\sim p^{\mu}\times
q}\left[\log\left(\frac{p^{\mu}(Z)\cdot
q(B|Z)}{p^{\mu}(Z)\cdot\hat{q}(B|Z)}\right)\right]$
$\displaystyle=\mathbb{E}_{Z\sim p^{\mu}}\left[\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{q(B|Z)}{\hat{q}(B|Z)}\right)\right]\right],$

and so for the user model $\hat{q}_{3}$,
$\varepsilon\leqslant\hat{q}_{3}(B|Z)\leqslant 1-\varepsilon$ for all
$B\in\mathcal{B},Z\in\mathcal{Z}$, and so the quantity above is guaranteed to
be finite.

Now, since the algorithm $p_{0}$ recommends a random item $Z$ with probability
$\varepsilon$,

$\displaystyle KL(p^{\mu}\times q,p^{\mu}\times\hat{q})$
$\displaystyle\geqslant\varepsilon\cdot\frac{1}{|\mathcal{Z}|}\sum_{Z\in\mathcal{Z}}\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{q(B|Z)}{\hat{q}(B|Z)}\right)\right]$
$\displaystyle=\varepsilon\cdot\frac{1}{|\mathcal{Z}|}\left(\sum_{Z\in\mathcal{Z}_{A}}\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{q(B|Z)}{\hat{q}(B|Z)}\right)\right]+\sum_{Z\in\mathcal{Z}_{B}}\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{q(B|Z)}{\hat{q}(B|Z)}\right)\right]\right)$
$\displaystyle\geqslant\varepsilon\cdot\frac{1}{|\mathcal{Z}|}\left(\max_{Z\in\mathcal{Z}_{A}}q(B=1|Z)\cdot\log\left(\frac{q(B=1|Z)}{\hat{q}(B=1|Z)}\right)\right.$
$\displaystyle\qquad\qquad\qquad+\left.\max_{Z\in\mathcal{Z}_{B}}q(B=1|Z)\cdot\log\left(\frac{q(B|Z)}{\hat{q}(B|Z)}\right)\right).$

Now, if $|\text{supp}(q)\cap\mathcal{Z}_{A}|>0$, then the first maximum is
infinite for $\hat{q}=\hat{q}_{2}$, since there will be at least one element
$Z\in\mathcal{Z}_{A}$ for which $q(B=1|Z)>0$, but $\hat{q}_{2}(B=1|Z)=0$ for
$Z\in\mathcal{Z}_{A}$. Similarly, if $|\text{supp}(q)\cap\mathcal{Z}_{B}|>0$,
the second maximum will be infinity for $\hat{q}_{1}$. This observation
suffices to show that if both $|\text{supp}(q)\cap\mathcal{Z}_{B}|>0$ and
$|\text{supp}(q)\cap\mathcal{Z}_{B}|>0$, the platform will converge to
$\hat{q}_{3}$.

To complete the proof, suppose without loss of generality that
$|\text{supp}(q)\cap\mathcal{Z}_{B}|=0$. We need to prove that in this case,
the platform will converge to $\hat{q}_{1}$ (and in particular, not
$\hat{q}_{3}$). We will show this by using KL-dominance—in particular, for any
belief $\mu$,

$\displaystyle KL(p^{\mu}\times q,p^{\mu}\times\hat{q}_{3})-KL(p^{\mu}\times
q,p^{\mu}\times\hat{q}_{1})$ $\displaystyle=\mathbb{E}_{(B,Z)\sim
p^{\mu}\times
q}\left[\log\left(\frac{q(B|Z)}{\hat{q}_{3}(B|Z)}\right)-\log\left(\frac{q(B|Z)}{\hat{q}_{1}(B|Z)}\right)\right]$
$\displaystyle=\mathbb{E}_{(B,Z)\sim p^{\mu}\times
q}\left[\log\left(\frac{\hat{q}_{1}(B|Z)}{\hat{q}_{3}(B|Z)}\right)\right]$
$\displaystyle=\mathbb{E}_{(B,Z)\sim p^{\mu}\times
q}\left[\log\left(\frac{\hat{q}_{1}(B|Z)}{\hat{q}_{3}(B|Z)}\right)\right].$

Since $\hat{q}_{3}(\cdot|Z)=\hat{q}_{1}(\cdot|Z)$ for $Z\in\mathcal{Z}_{A}$,
this simplifies to

$\displaystyle=\mathbb{E}_{Z\sim p^{\mu}}\left[\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{\hat{q}_{1}(B|Z)}{\hat{q}_{3}(B|Z)}\right)\right]\bigg{|}Z\in\mathcal{Z}_{B}\right]\cdot\mathbb{P}\left(Z\in\mathcal{Z}_{B}\right).$

By assumption (i.e., that $|\text{supp}(q)\cap\mathcal{Z}_{B}|=0$), we know
that $q(\cdot|Z)=\delta_{B=0}$, and so

$\displaystyle=\mathbb{E}_{Z\sim
p^{\mu}}\left[\log\left(\frac{\hat{q}_{1}(B=0|Z)}{\hat{q}_{3}(B=0|Z)}\right)\bigg{|}Z\in\mathcal{Z}_{B}\right]\cdot\mathbb{P}\left(Z\in\mathcal{Z}_{B}\right)$
$\displaystyle=\log\left(\frac{1}{\gamma}\right)\cdot\mathbb{P}\left(Z\in\mathcal{Z}_{B}\right)$
$\displaystyle>0.$

Thus, $\hat{q}_{1}$ strictly dominates $\hat{q}_{3}$ at all beliefs $\mu$, and
so the platform will converge to $\hat{q}_{1}$. ∎

####  B.2 Proof of Proposition 5.2

See 5.2

###### Proof.

We begin with the reverse direction. Suppose $\mathcal{Z}^{+}$ is not fully
contained in either $\mathcal{Z}_{A}$ or $\mathcal{Z}_{B}$. By Proposition
5.1. If the user is naive, the platform will converge to the belief
$\mu(\hat{q}_{3})=1$, and so the limiting proposition distribution will be a
uniform distribution over all items (since $\hat{q}_{3}(B=1|Z)=1-\varepsilon$
for all $Z$). The expected user payoff will then be equal to

$\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}_{3}}},q^{\text{BR}})=\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}|}.$

Without loss of generality, suppose $\mathcal{Z}_{A}$ is a better
approximation than $\mathcal{Z}_{B}$ to $\mathcal{Z}_{1}$, and in particular

$\Delta\coloneqq\frac{|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}{|\mathcal{Z}_{A}|}-\frac{|\mathcal{Z}_{B}\cap\mathcal{Z}^{+}|}{|\mathcal{Z}_{B}|}>0.$

We define $\varepsilon$ (the probability with which $p_{0}$ recommends items
uniformly at random) as

$\varepsilon<\frac{|\mathcal{Z}_{A}|\cdot|\mathcal{Z}_{B}|\cdot\Delta}{|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}.$

Now, rearranging this definition yields

$\displaystyle|\mathcal{Z}_{A}|\cdot|\mathcal{Z}_{B}|\cdot\left(\frac{|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}{|\mathcal{Z}_{A}|}-\frac{|\mathcal{Z}_{B}\cap\mathcal{Z}^{+}|}{|\mathcal{Z}_{B}|}\right)$
$\displaystyle>|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|\cdot\varepsilon$
$\displaystyle{|\mathcal{Z}_{B}|\cdot|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}-{|\mathcal{Z}_{A}|\cdot|\mathcal{Z}_{B}\cap\mathcal{Z}^{+}|}$
$\displaystyle>|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|\cdot\varepsilon$
$\displaystyle(1-\varepsilon)\cdot{|\mathcal{Z}_{B}|\cdot|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}$
$\displaystyle>\varepsilon\cdot|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|\cdot|\mathcal{Z}_{A}|+{|\mathcal{Z}_{A}|\cdot|\mathcal{Z}_{B}\cap\mathcal{Z}^{+}|}$
$\displaystyle(1-\varepsilon)\cdot|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|\cdot|\mathcal{Z}_{A}|+(1-\varepsilon)\cdot{|\mathcal{Z}_{B}|\cdot|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}$
$\displaystyle>|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|\cdot|\mathcal{Z}_{A}|+{|\mathcal{Z}_{A}|\cdot|\mathcal{Z}_{B}\cap\mathcal{Z}^{+}|}$
$\displaystyle(1-\varepsilon)\cdot|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|\cdot|\mathcal{Z}|$
$\displaystyle>|\mathcal{Z}^{+}|\cdot|\mathcal{Z}_{A}|$
$\displaystyle\frac{|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}{|\mathcal{Z}_{A}|}$
$\displaystyle>\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}|}\cdot\frac{1}{1-\varepsilon}.$

Now, consider an alternative strategy $q^{\prime}$ where the user clicks only
on items in $\mathcal{Z}_{+}\cap\mathcal{Z}_{A}$. By Proposition 5.1, this
would lead the platform to converge to $\hat{q}_{1}$, and so the user’s payoff
would be

$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}_{1}}},q^{\prime})=\varepsilon\cdot\frac{|\mathcal{Z}^{+}\cap\mathcal{Z}_{A}|}{|\mathcal{Z}|}+(1-\varepsilon)\cdot\frac{|\mathcal{Z}^{+}\cap\mathcal{Z}_{A}|}{|\mathcal{Z}_{A}|}$
$\displaystyle>\varepsilon\cdot\frac{|\mathcal{Z}^{+}\cap\mathcal{Z}_{A}|}{|\mathcal{Z}|}+\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}|},$

and so playing the strategy $q^{\prime}$ guarantees the user strictly higher
long-run payoff than $q^{\text{BR}}$.

For the forward direction, suppose without loss of generality that
$\mathcal{Z}^{+}\subset\mathcal{Z}_{A}$. Observe that conditioned on a fixed
distribution of propositions $p^{\mu}\in\Delta(Z)$ (i.e., in the absence of
any learning), $q^{\text{BR}}$ by definition yields optimal expected payoff
$\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu},q)$. As a result, $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu},q^{\text{BR}})$ gives an upper bound for the user’s payoff when
the platform’s belief is $\mu$. Now, if the platform belief is
$\mu(\hat{q}_{3})=1$, then the resulting distribution is a uniform
distribution over items $Z$, and so

$\displaystyle\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}_{3}}},q)\leqslant\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}_{3}}},q^{\text{BR}})=\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}|}=\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}_{A}|+|\mathcal{Z}_{B}|}.$

Similarly, if the platform believes $\mu(\hat{q}_{2})=1$, then it will
recommend uniformly with probability $\varepsilon$, and otherwise recommend
from $\mathcal{Z}_{B}$, and so

$\displaystyle\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}_{2}}},q)\leqslant\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}_{2}}},q^{\text{BR}})=\varepsilon\cdot\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}|}+(1-\varepsilon)\cdot
0=\varepsilon\cdot\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}|}.$

Now, by Proposition 5.1, playing any non-degenerate strategy (i.e., $q$ for
which $\max_{Z}q(B=1|Z)>0$) will lead the platform to converge to a point mass
belief. The naive strategy $q^{\text{BR}}$ will lead to the platform having
limiting belief $\hat{q}_{1}$, for which the user’s payoff is

$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}_{1}}},q^{\text{BR}})=\varepsilon\cdot\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}|}+(1-\varepsilon)\cdot\frac{|\mathcal{Z}^{+}|}{|\mathcal{Z}_{A}|}.$

This is clearly greater than the other two upper bounds, and so if the user
plays a non-degenerate strategy, $q^{\text{BR}}$ is the best option. The proof
concludes by noting that the degenerate strategy yields a utility of zero. ∎

####  B.3 Proof of Proposition 5.3

See 5.3

###### Proof.

Let $\mu_{S}$ be the platform’s long-run belief when the user is strategic,
and let $\mu_{\text{BR}}$ be the platform’s long-run belief when the user is
naive. Note that Proposition 5.1 implies that these beliefs exist and are
unique for $q^{\text{BR}}$ and for any non-degenerate $q^{*}$. Now, if the
user is incentivized to strategize, it must be that $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu_{\text{BR}}},q^{\text{BR}})\leqslant\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu_{S}},q^{*})$. In other words,

$\displaystyle\sum_{Z\in\mathcal{Z}}p^{\mu_{S}}(Z)\mathbb{E}_{q^{S}(\cdot|Z)}[U(Z,B)]$
$\displaystyle\geqslant\sum_{Z\in\mathcal{Z}}p^{\mu_{\text{BR}}}(Z)\mathbb{E}_{q^{\text{BR}}(\cdot|Z)}[U(Z,B)]$
$\displaystyle\sum_{Z\in\mathcal{Z}}p^{\mu_{S}}(Z)q^{S}(B=1|Z)a(Z)$
$\displaystyle\geqslant\sum_{Z\in\mathcal{Z}}p^{\mu_{\text{BR}}}(Z)q^{\text{BR}}(B=1|Z)\cdot
a(Z)$
$\displaystyle\sum_{Z\in\mathcal{Z}^{+}}p^{\mu_{S}}(Z)q^{S}(B=1|Z)-\sum_{Z\in\mathcal{Z}\setminus\mathcal{Z}^{+}}p^{\mu_{S}}(Z)q^{S}(B=1|Z)$
$\displaystyle\geqslant\sum_{Z\in\mathcal{Z}^{+}}p^{\mu_{\text{BR}}}(Z)q^{\text{BR}}(B=1|Z)$
$\displaystyle\sum_{Z\in\mathcal{Z}}p^{\mu_{S}}(Z)q^{S}(B=1|Z)-\sum_{Z\in\mathcal{Z}}p^{\mu_{\text{BR}}}(Z)q^{\text{BR}}(B=1|Z)$
$\displaystyle\geqslant
2\sum_{Z\in\mathcal{Z}\setminus\mathcal{Z}^{+}}p^{\mu_{S}}(Z)q^{S}(B=1|Z)$

∎

####  B.4 Proof of Proposition 5.4

See 5.4

###### Proof.

For convenience, assume $|\mathcal{Z}_{B}|$ is even (otherwise, the same proof
holds but requires us to keep track of a rounding error). We will define
$a(Z)$ to be $+1$ on a half of $\mathcal{Z}_{B}$ and $-1$ on the other half,
and $+1$ on $3/4$ of $\mathcal{Z}_{A}$ (and $-1$ on the remaining $1/4$). By
construction, defining $\mathcal{Z}^{+}=\\{Z\in\mathcal{Z}:a(Z)=1\\}$,

$\frac{|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}{|\mathcal{Z}_{A}|}\geqslant\frac{3}{4}>\frac{1}{2}=\frac{|\mathcal{Z}_{B}\cap\mathcal{Z}^{+}|}{|\mathcal{Z}_{B}|}.$

Using an identical argument to the one used in Section B.2, we see that when
$\varepsilon$ is sufficiently small, a strategic user will restrict their
clicks to $\mathcal{Z}^{+}\cap\mathcal{Z}_{1}$, in order to induce a platform
belief of $\hat{q}_{1}$. For some small $\alpha>0$ (to be defined later),
consider the toxicity function

$\displaystyle\textsc{toxicity}(Z)=\begin{cases}\alpha&\text{ if
}Z\in\mathcal{Z}_{A}\cap\mathcal{Z}^{+}\text{ or
}\mathcal{Z}_{B}\setminus\mathcal{Z}^{+}\\\ 1&\text{otherwise}.\end{cases}$

In the remainder of the proof, we introduce the following notation for
convenience:

$\displaystyle n_{1}=|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|,\qquad
n_{2}=|\mathcal{Z}_{A}\setminus\mathcal{Z}^{+}|\qquad
n_{3}=|\mathcal{Z}_{B}\cap\mathcal{Z}^{+}|,\qquad
n_{4}=|\mathcal{Z}_{B}\setminus\mathcal{Z}^{+}|.$

###### Platform’s current payoff.

The platform’s current payoff under the user’s strategic behavior is

$\displaystyle{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{0},\widehat{\mathcal{Q}})=\varepsilon\cdot\frac{n_{1}}{n_{1}+n_{2}+n_{3}+n_{4}}+(1-\varepsilon)\cdot\frac{n_{1}}{n_{1}+n_{2}}.$
(17)

Note that the platform’s predicted payoff under $p_{0}$ is given by

$\displaystyle\widehat{V}(p_{0},\widehat{\mathcal{Q}})=(1-\gamma)\left[\varepsilon\cdot\frac{n_{1}+n_{2}}{n_{1}+n_{2}+n_{3}+n_{4}}+(1-\varepsilon),\right],$

and by setting $\gamma$ appropriately we can make these two quantities equal
(intuitively, since $\varepsilon$ is small, $1-\gamma$ roughly corresponds to
the fraction of $\mathcal{Z}_{A}$ that the user actually engages with, i.e.,
$\frac{n_{1}}{n_{1}+n_{2}}$).

###### Platform’s predicted payoff.

We now derive the platform’s predicted payoff
$\widehat{V}(p_{1},\widehat{\mathcal{Q}})$—the platform believes that the
user’s strategy is $\hat{q}_{1}$, and so its predicted payoff is

$\displaystyle\widehat{V}(p_{1},\widehat{\mathcal{Q}})$
$\displaystyle=(1-\gamma)\left[\varepsilon\cdot\frac{\alpha
n_{1}+n_{2}}{\alpha n_{1}+n_{2}+n_{3}+\alpha n_{4}}+(1-\varepsilon)\right].$

From this, it is straightforward to show that

$\displaystyle\widehat{V}(p_{1},\widehat{\mathcal{Q}})-{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{0},\widehat{\mathcal{Q}})$
$\displaystyle=\widehat{V}(p_{1},\widehat{\mathcal{Q}})-\widehat{V}(p_{0},\widehat{\mathcal{Q}})$
$\displaystyle=(1-\gamma)\cdot\varepsilon\cdot\left[\frac{\alpha
n_{1}+n_{2}}{\alpha n_{1}+n_{2}+n_{3}+\alpha
n_{4}}-\frac{n_{1}+n_{2}}{n_{1}+n_{2}+n_{3}+n_{4}}\right]$ $\displaystyle<0,$

where in the last inequality we use the fact that:

$\displaystyle\frac{n_{2}}{n_{1}+n_{2}}$
$\displaystyle\leqslant\frac{1}{4}<\frac{1}{2}=\frac{n_{3}}{n_{3}+n_{4}}$
$\displaystyle n_{2}n_{3}+n_{2}n_{4}$ $\displaystyle<n_{1}n_{3}+n_{2}n_{3}$
$\displaystyle 0$ $\displaystyle>(1-\alpha)(n_{2}n_{4}-n_{1}n_{3})$
$\displaystyle=(\alpha
n_{1}+n_{2})(n_{1}+n_{2}+n_{3}+n_{4})-(n_{1}+n_{2})(\alpha
n_{1}+n_{2}+n_{3}+\alpha n_{4}).$

This sequence of calculations proves the result (b).

###### Platform’s true payoff.

We now consider the platform’s true payoff when the user is strategic. Now, we
use the fact that (a) if the user’s behavior is non-degenerate, the platform’s
belief will converge to a single $\mu(\hat{q}_{i})=1$; (b) for a fixed belief
$\mu$, the maximum user payoff is upper bounded by the payoff attained by
$q^{\text{BR}}$.

Thus, under the toxicity function above,

$\displaystyle\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{1}}},q)\leqslant\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{1}}},q^{\text{BR}})$
$\displaystyle=\varepsilon\cdot\frac{\alpha n_{1}+n_{3}}{\alpha
n_{1}+n_{2}+n_{3}+\alpha n_{4}}+(1-\varepsilon)\cdot\frac{\alpha n_{1}}{\alpha
n_{1}+n_{2}}$ $\displaystyle\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{2}}},q)\leqslant\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{2}}},q^{\text{BR}})$
$\displaystyle=\varepsilon\cdot\frac{\alpha n_{1}+n_{3}}{\alpha
n_{1}+n_{2}+n_{3}+\alpha n_{4}}+(1-\varepsilon)\cdot\frac{n_{3}}{n_{3}+\alpha
n_{4}}$ $\displaystyle\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{3}}},q)\leqslant\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{3}}},q^{\text{BR}})$
$\displaystyle=\frac{\alpha n_{1}+n_{3}}{\alpha n_{1}+n_{2}+n_{3}+\alpha
n_{4}}.$

Observe that as $\alpha\to 0$,

$\displaystyle\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{1}}},q)\to\frac{\varepsilon\cdot
n_{3}}{n_{2}+n_{3}}\qquad\text{ and
}\qquad\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{3}}},q)\to\frac{n_{3}}{n_{2}+n_{3}}.$ (18)

Also, if the user plays the strategy
$q^{\dagger}(B=1|Z)=\bm{1}\\{Z\in\mathcal{Z}^{+}\cap\mathcal{Z}_{B}\\}$, the
platform will converge to $\mu(\hat{q}_{2})=1$ (by Proposition 5.1), and so
the user’s utility will be

$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{2}}},q^{\dagger})$
$\displaystyle=\varepsilon\cdot\frac{n_{3}}{\alpha n_{1}+n_{2}+n_{3}+\alpha
n_{4}}+(1-\varepsilon)\cdot\frac{n_{3}}{n_{3}+\alpha n_{4}},$

which as $\alpha\to 0$, converges to

$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{2}}},q^{\dagger})$
$\displaystyle\to\varepsilon\cdot\frac{n_{3}}{n_{2}+n_{3}}+(1-\varepsilon)>\frac{n_{3}}{n_{2}+n_{3}}=\lim_{\alpha\to
0}\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{3}}},q).$

In particular, by comparing this to (18), there must exist some $\alpha>0$
such that

$\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{2}}},q^{\dagger})>\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{3}}},q)>\max_{q\in\mathcal{Q}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p_{1}^{\delta_{\hat{q}_{1}}},q).$

This implies that the strategic user will induce the belief
$\mu(\hat{q}_{2})=1$ when the platform plays the algorithm $p_{1}$. Note that
of the user strategies that induce $\mu(\hat{q}_{2})=1$, the optimal one is
clearly $q^{\dagger}$, as any strategy that does not set $B=1$ for
$Z\in\mathcal{Z}^{+}\cap\mathcal{Z}_{B}$ would increase its utility by doing
so, and any strategy that does set $B=1$ for
$Z\in\mathcal{Z}_{B}\setminus\mathcal{Z}^{+}$ would needlessly incur a
penalty.

Thus, to conclude the proof, observe that

$\displaystyle{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{1},\widehat{\mathcal{Q}})$ $\displaystyle=\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{1}^{\delta_{\hat{q}_{2}}},q^{\dagger})$
$\displaystyle=\varepsilon\cdot\frac{n_{3}}{\alpha n_{1}+n_{2}+n_{3}+\alpha
n_{4}}+(1-\varepsilon)\cdot\frac{n_{3}}{n_{3}+\alpha n_{4}},$

which, as $\alpha\to 0$ and $\varepsilon\to 0$, converges to $1$. Contrasting
this to (17) makes it clear that by choosing $\alpha$ and $\varepsilon$ small
enough, we get that ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{1},\widehat{\mathcal{Q}})>{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{0},\widehat{\mathcal{Q}})$. ∎

####  B.5 Proof of Proposition 5.5

See 5.5

###### Proof.

Define the affinity function $a(Z)$ to be $+1$ on half of the items in
$\mathcal{Z}_{A}$ (rounding down if $|\mathcal{Z}_{A}|$ is not even), and on a
single item from $\mathcal{Z}_{B}$.

Recall from Proposition 5.2 and its proof in Section B.2 that a strategic user
will try to induce the belief $\mu(\hat{q}_{1})=1$ from the platform by
restricting their clicks to $\mathcal{Z}_{A}\cap\mathcal{Z}^{+}$ (where recall
that $\mathcal{Z}^{+}$ is the subset of $\mathcal{Z}$ on which $a(Z)=1$). For
some $\eta>0$ to be defined later, define

$\hat{q}_{4}(B=1|Z)=1-\eta\quad\forall\ Z\in\mathcal{Z}$

Now, consider a strategic user in reponse to the platform strategy
$(p_{0},\widehat{\mathcal{Q}}\cup\\{\hat{q}_{4}\\})$. The user is faced with a
choice between three cases:

  * (A)

Force the platform to converge to $\hat{q}_{3}$ or $\hat{q}_{4}$. These are
indistinguishable from the user’s perspective as in either case, the resulting
proposition distribution $p_{0}^{\mu}$ will converge to a uniform distribution
over $\mathcal{Z}$.

  * (B)

Induce the platform to converge to $\mu(\hat{q}_{1})=1$, in which case the
limiting proposition distribution is a mixture of the uniform distribution
over $\mathcal{Z}$ (with probability $\varepsilon$) and the uniform
distribution over $\mathcal{Z}_{A}$ (with probability $1-\varepsilon$).

  * (C)

Conversely, induce the platform to converge to $\mu(\hat{q}_{2})=1$.

Note that playing naively results in case (A), and so the user’s utility in
that case is both upper and lower bounded by
$|\mathcal{Z}^{+}|/|\mathcal{Z}|$. Meanwhile, since we constructed
$|\mathcal{Z}_{B}\cap\mathcal{Z}^{+}|=1$, the user’s utility in case (C) is
upper bounded by $1/|\mathcal{Z}_{B}|$. We can thus remove case (C) from
consideration.

It thus remains to bound the utility of Case (B). In the absence of
$\hat{q}_{4}$, the user can restrict their clicks to
$\mathcal{Z}_{A}\cap\mathcal{Z}^{+}$ and guarantee that the platform converges
to $\hat{q}_{1}$ (see Section B.1). In the presence of $\hat{q}_{4}$, however,
we argue that the only strategy that guarantees the platform converging to
$\hat{q}_{1}$ will also result in low user payoff.

To show this, suppose there exists a strategy $q$ for which the platform
converges to $\hat{q}_{1}$. If $\eta<\gamma$,

$\displaystyle\text{KL}(q||\hat{q}_{1})-\text{KL}(q||\hat{q}_{4})$
$\displaystyle=\mathbb{E}_{Z\sim p^{\mu}}\left[\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{q(B|Z)}{\hat{q}_{1}(B|Z)}\right)-\log\left(\frac{q(B|Z)}{\hat{q}_{4}(B|Z)}\right)\right]\right]$
$\displaystyle=\mathbb{E}_{Z\sim p^{\mu}}\left[\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{\hat{q}_{4}(B|Z)}{\hat{q}_{1}(B|Z)}\right)\right]\right]$
$\displaystyle=\mathbb{E}_{Z\sim p^{\mu}}\left[\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{\hat{q}_{4}(B|Z)}{\hat{q}_{1}(B|Z)}\right)\right]\bigg{|}Z\in\mathcal{Z}_{A}\right]\cdot\mathbb{P}_{Z\sim
p^{\mu}}(Z\in\mathcal{Z}_{A})$ $\displaystyle\qquad+\mathbb{E}_{Z\sim
p^{\mu}}\left[\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left(\frac{\hat{q}_{4}(B|Z)}{\hat{q}_{1}(B|Z)}\right)\right]\bigg{|}Z\in\mathcal{Z}_{B}\right]\cdot\mathbb{P}_{Z\sim
p^{\mu}}(Z\in\mathcal{Z}_{B})$ $\displaystyle=\mathbb{E}_{Z\sim
p^{\mu}}\left[q(B=1|Z)\cdot\log\left(\frac{1-\eta}{1-\gamma}\right)+q(B=0|Z)\cdot\log\left(\frac{\eta}{\gamma}\right)\bigg{|}Z\in\mathcal{Z}_{A}\right]\cdot\mathbb{P}_{Z\sim
p^{\mu}}(Z\in\mathcal{Z}_{A})$ $\displaystyle\qquad+\mathbb{E}_{Z\sim
p^{\mu}}\left[\log\left(\eta\right)\bigg{|}Z\in\mathcal{Z}_{B}\right]\cdot\mathbb{P}_{Z\sim
p^{\mu}}(Z\in\mathcal{Z}_{B})$
$\displaystyle\geqslant\left(\log\left(1-\eta\right)+\mathbb{E}_{Z\sim
p^{\mu}}\left[q(B=0|Z)\big{|}Z\in\mathcal{Z}_{A}\right]\cdot\log\left(\frac{\eta}{\gamma}\right)\right)\cdot\mathbb{P}(Z\in\mathcal{Z}_{A})+\log\left(\eta\right).$

Thus, if

$\displaystyle\mathbb{E}_{Z\sim
p^{\mu}}\left[q(B=0|Z)\big{|}Z\in\mathcal{Z}_{A}\right]>\frac{\left(\frac{-\log(\eta)}{\mathbb{P}(Z\in\mathcal{Z}_{A})}-\log\left({1-\eta}\right)\right)}{\log\left(\frac{\eta}{\gamma}\right)},$

then $\text{KL}(q||\hat{q}_{1})-\text{KL}(q||\hat{q}_{4})>0$, and
$\hat{q}_{4}$ thus dominates $\hat{q}_{1}$ at belief $\mu$. Now, since
$\mathbb{P}(Z\in\mathcal{Z}_{A})$ is lower bounded by
$\varepsilon|\mathcal{Z}_{A}|/|\mathcal{Z}|$, we can set $\gamma$ small so
that the above expression evaluates to $\frac{1}{|\mathcal{Z}|}$.

Also, note that since none of the user models distinguish between different
elements within the partition $\mathcal{Z}_{A}$, the expectation on the left
is equivalent to the unconditional expectation
$\mathbb{E}_{Z\sim\text{Unif}(\mathcal{Z}_{A})}[\cdot]$.

Putting these two observations together, we have that if

$\displaystyle\frac{1}{|\mathcal{Z}_{A}|}\sum_{Z\in\mathcal{Z}_{A}}q(B=0|Z)>\frac{1}{|\mathcal{Z}|},$
(19)

then $\hat{q}_{4}$ strictly dominates $\hat{q}_{1}$ at all beliefs $\mu$, and
the platform will converge to $\mu(\hat{q}_{4})=1$. Since we have by
assumption that the platform converges to $\mu(\hat{q}_{1})=1$, it must be
that (19) is false, and so

$\displaystyle\frac{1}{|\mathcal{Z}_{A}|}\sum_{Z\in\mathcal{Z}_{A}}q(B=1|Z)\geqslant
1-\frac{1}{|\mathcal{Z}|}.$

By construction ($\mathcal{Z}^{+}$ containing exactly half of
$\mathcal{Z}_{A}$),

$\displaystyle\frac{1}{|\mathcal{Z}_{A}\cap\mathcal{Z}^{+}|}\sum_{Z\in\mathcal{Z}_{A}\cap\mathcal{Z}^{+}}q(B=1|Z)\geqslant
1-\frac{2}{|\mathcal{Z}|}.$

We now argue that with such a strategy, the user can attain no more than
$\frac{2}{|\mathcal{Z}|}$ utility. Since none of the user models distinguish
between elements within $\mathcal{Z}_{A}$, a coupling argument shows that for
every element $Z:a(Z)=1$ that the user clicks on with probability $\delta$,
there is at least one other element with $a(Z^{\prime})=-1$ that the user
clicks on with probability $\delta(1-\frac{2}{|\mathcal{Z}|}$) and that is
recommended with equal probability to $Z$.

We have thus shown that the maximum attainable payoff from case (B) is
$2/|\mathcal{Z}|$, which is lower than the guaranteed payoff from case (A) of
$|\mathcal{Z}^{+}|/|\mathcal{Z}|$. A strategic user will thus choose to play
naively, which in fact lowers platform payoff. We have thus shown that both
case (B) and case (C) result in low payoffs for the user, and so the user will
choose case (A). The proof concludes by observing that platform’s payoff under
case (A) decreases from the original strategic user. ∎

###  Appendix C Omitted Proofs: Main Results

####  C.1 Proof of Proposition 6.9

See 6.9

###### Proof.

Note that the left-hand side of (12) is exactly the platform’s payoff under a
strategic user, and so it only remains to show that the right-hand side
corresponds to the platform’s payoff under a naive user. First, by the min-max
inequality,

$\displaystyle\max_{q\in\mathcal{Q}}\min_{\mu\in\Delta(\widehat{\mathcal{Q}})}\overline{U}(p({\cdot};{\mu}),q)$
$\displaystyle\leqslant\min_{\mu\in\Delta(\widehat{\mathcal{Q}})}\max_{q\in\mathcal{Q}}\overline{U}(p({\cdot};{\mu}),q)$
$\displaystyle\leqslant\min_{\mu\in\Delta(\widehat{\mathcal{Q}})}\overline{U}(p({\cdot};{\mu}),q^{\text{BR}}),$

and so

$q^{\text{BR}}\in\arg\max_{q\in\mathcal{Q}}\min_{\mu\in\Delta(\widehat{\mathcal{Q}})}\overline{U}(p({\cdot};{\mu}),q).$

Now, suppose $q\neq q^{\text{BR}}$ satisfies

$q\in\arg\max_{q\in\mathcal{Q}}\min_{\mu\in\Delta(\widehat{\mathcal{Q}})}\overline{U}(p({\mu};{\cdot}),q).$

Since $q\neq q^{\text{BR}}$ and $U$ has a unique maximizer $B^{*}(Z)$ for each
$Z\in\mathcal{Z}$, there must exist some $Z_{0}\in\mathcal{Z}$ for which
$q(\cdot|Z_{0})\neq\bm{1}\\{B^{*}(Z_{0})\\}$. Define

$q^{\prime}(\cdot|Z)=\begin{cases}q(\cdot|Z)&\text{ if $Z\neq Z_{0}$}\\\
\bm{1}\\{B^{*}(Z_{0})\\}&\text{ otherwise.}\end{cases}$

Clearly, $q^{\prime}$ attains the same payoff $U$ as $q$ for any $Z\neq
Z_{0}$, and when $Z=Z_{0}$, $q^{\prime}$ attains better payoff than $q$. If
there exists a $\mu$ such that $p(Z_{0};\mu)>0$ we have thus reached a
contradiction, and otherwise $Z_{0}$ will never by played by the platform, and
so user actions under $q$ are indistinguishable to the platform from user
actions under $q^{\text{BR}}$.

∎

####  C.2 Proof of Proposition 6.13

See 6.13

###### Proof.

Now, we define $\hat{q}_{1}$ and $\hat{q}_{2}$ as the lowest and highest
attainable platform payoff by a user who chooses a strategy
$\hat{q}\in\widehat{\mathcal{Q}}$, i.e.,

$\displaystyle\hat{q}_{1}=\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q}),\qquad\hat{q}_{2}=\arg\min_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q}).$

Note that for our bound to meaningful, we must have that

$\displaystyle\gamma\coloneqq\frac{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}_{1}}}),\hat{q}_{1})-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}_{2}}}),\hat{q}_{2})}{4}-(\beta-\alpha)>0,$

and so we assume that this inequality holds for the remainder of the proof.
Now, recall that the payoff function $V$ is scaled so that $0\leqslant
V(B,Z)\leqslant 1$. For some constant $c\in[0,1]$ to be set later, let

$U(B,Z)=(V(B,Z)-c)^{2},$

so that for any belief $\mu$ and user strategy $q$,

$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu},q,c)=\text{Var}_{(B,Z)\sim p^{\mu}\times
q}[V(B,Z)]+\left(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\mu},q)-c\right)^{2},$

where we make the dependence on the unset constant $c$ explicit for notational
convenience. In turn, the function that the strategic user aims to maximize is

$\displaystyle\widetilde{U}(q,c)\coloneqq\min_{\mu\in
S^{\infty}(q,p,\widehat{\mathcal{Q}})}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu},q).$

When $q=\hat{q}\in\widehat{\mathcal{Q}}$ and $p(\cdot;\mu)$ has full support
for all $\mu$, $\widetilde{U}(q,c)$ simplifies to

$\displaystyle\widetilde{U}(\hat{q},c)\coloneqq\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p({\cdot};{\delta_{\hat{q}}}),\hat{q}).$

We now prove a few lemmata that will be useful later in the proof. First, we
show that our condition on the loss landscape of $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{V}$
suffices to show a similar condition for the loss landscape of
$\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{U}$:

######  Lemma C.1.

For any proposition distribution $r\in\Delta(\mathcal{Z})$, any fixed user
strategy $q$, and any $\varepsilon>0$, there exists a distribution
$r^{\prime}\in\Delta(\mathcal{Z})$ so that
$\mathcal{W}_{1}(r,r^{\prime})\leqslant\varepsilon$ and
$\delta_{r,q}(c)\coloneqq\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(r,q,c)-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(r^{\prime},q,c)\neq 0$ almost everywhere (with respect to $c$).

###### Proof.

We can use Assumption 6.4 to find a distribution
$r^{\prime}\in\Delta(\mathcal{Z})$ such that
$d(r,r^{\prime})\leqslant\varepsilon$ and $\delta\coloneqq\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r^{\prime},q)-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r,q)\neq 0$. Then, note that $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(r,q,c)=\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(r^{\prime},q,c)$ if and only if

$\displaystyle\text{Var}_{(B,Z)\sim r\times q}[V(B,Z)]+(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r,q)-c)^{2}$ $\displaystyle=\text{Var}_{(B,Z)\sim r^{\prime}\times
q}[V(B,Z)]+(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r^{\prime},q)-c)^{2}$ $\displaystyle\text{Var}_{(B,Z)\sim r\times
q}[V(B,Z)]-\text{Var}_{(B,Z)\sim r^{\prime}\times q}[V(B,Z)]$
$\displaystyle=2\delta(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r,q)-c)+\delta^{2},$

and in particular, if and only if

$\displaystyle c=\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r,q)-\frac{1}{2\delta}\left(\text{Var}_{(B,Z)\sim r\times
q}[V(B,Z)]-\text{Var}_{(B,Z)\sim r^{\prime}\times
q}[V(B,Z)]-\delta^{2}\right),$

which is a measure-zero set. ∎

Next, we show that given a collection of proposition distributions
$\\{r_{1},\ldots r_{m}\\}$ corresponding to a set of user models
$\\{\hat{q}_{1},\ldots,\hat{q}_{m}\\}$ such that $r_{i}$ is
$\varepsilon_{0}$-close to $p({\cdot};{\delta_{\hat{q}_{i}}})$, we can
construct a new algorithm $p^{\prime}$ that is $2\varepsilon_{0}$-close to $p$
such that $p^{\prime}$ satisfies the regularity conditions in Assumption 6.3,
and $p^{\prime}(\cdot;\delta_{\hat{q}_{i}})=r_{i}$ for all $i\in[m]$.

######  Lemma C.2.

Given an algorithm $p$ satisfying Assumption 6.3, a collection of proposition
distributions $\\{r_{1},\ldots r_{m}\\}$, and a set of user models
$\\{\hat{q}_{1},\ldots,\hat{q}_{m}\\}$ such that

$\mathcal{W}_{1}(p({\cdot};{\delta_{\hat{q}_{i}}}),r_{i})\leqslant\varepsilon_{0}\
\forall\ i\in[m],$

there exists an algorithm $p^{\prime}$ such that
$d_{\mathcal{P}}(p,p^{\prime})\leqslant 2\varepsilon_{0}$ and

$p(\cdot;\delta_{\hat{q}_{i}})=r_{i}\forall\ i\in[m].$

###### Proof.

By Assumption 6.3, we know that for all $Z\in\mathcal{Z}$, $p(Z;\mu)$ is
continuous in $\mu$ around point mass beliefs. This continuity also implies
continuity in Wasserstein distance. Thus, there exists a single constant
$\delta$ such that for any $i\in[m]$,

$d(\delta_{\hat{q}_{i}},\mu)<\delta\implies\mathcal{W}_{1}(p(\cdot;\delta_{\hat{q}}),p(\cdot;\mu))\leqslant\varepsilon_{0},$

where $d(\cdot,\cdot)$ is the same distance metric with respect to which
Assumption 6.3 (ii) holds. Then, define the new algorithm

$p^{\prime}(Z;\mu)=\begin{cases}r_{i}&\text{if
}d(\delta_{\hat{q}_{i}},\mu)<\delta\\\ p(Z;\mu)&\text{otherwise.}\end{cases}$

Clearly, this algorithm satisfies $p(\cdot;\delta_{\hat{q}_{i}})=r_{i}\forall\
i\in[m].$ Furthermore, it satisfies the continuity condition since it is
actually constant in the neighborhood of each point mass belief
$\delta_{\hat{q}}$. Finally,

$\displaystyle d_{\mathcal{P}}(p,p^{\prime})$
$\displaystyle=\sup_{\mu\in\Delta(\widehat{\mathcal{Q}})}\mathcal{W}_{1}(p(\cdot;\mu),p^{\prime}(\cdot;\mu))$
$\displaystyle=\max_{i\in[m]}\
\sup_{d(\mu,\delta_{\hat{q}_{i}})<\delta}\mathcal{W}_{1}(p(\cdot;\mu),r_{i})$
$\displaystyle\leqslant\max_{i\in[m]}\
\sup_{d(\mu,\delta_{\hat{q}_{i}})<\delta}\mathcal{W}_{1}(p(\cdot;\mu),p(\cdot;\delta_{\hat{q}_{i}}))+\mathcal{W}_{1}(p(\cdot;\delta_{\hat{q}_{i}}),r_{i})$
$\displaystyle\leqslant 2\varepsilon_{0},$

concluding the proof. ∎

We now resume the main proof. For any $c$, we partition the set of user models
into

$\displaystyle\widehat{\mathcal{Q}}_{+}(c)$
$\displaystyle=\\{\hat{q}\in\widehat{\mathcal{Q}}:\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})>c\\},$
$\displaystyle\widehat{\mathcal{Q}}_{-}(c)$
$\displaystyle=\\{\hat{q}\in\widehat{\mathcal{Q}}:\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})<c\\},$
$\displaystyle\widehat{\mathcal{Q}}_{=}(c)$
$\displaystyle=\\{\hat{q}\in\widehat{\mathcal{Q}}:\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})=c\\}.$

For any value of $c$, we define the functions

$\displaystyle
M_{+}(c)=\max_{\hat{q}\in\widehat{\mathcal{Q}}_{+}(c)}\widetilde{U}(\hat{q},c),\qquad
M_{-}(c)=\max_{\hat{q}\in\widehat{\mathcal{Q}}_{-}(c)}\widetilde{U}(\hat{q},c),\qquad
M(c)=\max_{\hat{q}\in\widehat{\mathcal{Q}}}\widetilde{U}(\hat{q},c),$

then let

$Q^{*}(c)\coloneqq\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}}\widetilde{U}(q,c)$

be the set of possible strategies for a strategic user, assuming they play
according to one of the user models $\hat{q}\in\widehat{\mathcal{Q}}$.

Observe that for any $\hat{q}\in Q^{*}(c)$,

$\displaystyle\beta+(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})-c)^{2}$
$\displaystyle\geqslant\widetilde{U}(\hat{q},c)$
$\displaystyle\geqslant\max\left\\{\widetilde{U}(\hat{q}_{1}),\widetilde{U}(\hat{q}_{2}),\right\\}$
$\displaystyle\geqslant\alpha+\max\left\\{\left(\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\delta_{\hat{q}}},\hat{q})-c\right)^{2},\left(\min_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\delta_{\hat{q}}},\hat{q})-c\right)^{2}\right\\}$
$\displaystyle\geqslant\alpha+\frac{\left({\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\delta_{\hat{q}}},\hat{q})-\min_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\delta_{\hat{q}}},\hat{q})}\right)^{2}}{4}$
$\displaystyle(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})-c)^{2}$
$\displaystyle\geqslant\frac{\left({\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\delta_{\hat{q}}},\hat{q})-\min_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\delta_{\hat{q}}},\hat{q})}\right)^{2}}{4}-(\beta-\alpha)$
$\displaystyle=\gamma>0.$ (20)

In particular, this implies that $\hat{q}\not\in\widehat{\mathcal{Q}}_{=}(c)$,
and thus

$M(c)=\max\\{M_{+}(c),M_{-}(c)\\}.$

Now, as $c$ increases, the set $\widehat{\mathcal{Q}}_{-}(c)$ grows and each
$\widetilde{U}(\hat{q},c)$ is non-decreasing for each
$\hat{q}\in\widehat{\mathcal{Q}}_{-}(c)$, and so $M-_{(}c)$ is non-decreasing
in $c$. Similar logic shows that $M_{+}(c)$ is non-increasing in $c$.
Furthermore, by definition, $M_{+}(c)>M_{-}(c)$ when $c=0$ and
$M_{-}(c)>M_{+}(c)$ when $c=1$. We thus let $c_{0}=\inf\\{c:M_{-}(c)\geqslant
M(c)\\},$ and let $c_{1}=\sup\\{c:M_{+}(c)\geqslant M(c)\\}.$

######  Lemma C.3.

There exists a constant $\psi>0$ such that the function $M_{-}(c)$ is
uniformly continuous over the interval $[c_{0}-\psi,1]$, and $M_{+}(c)$ is
uniformly continuous over $[0,c_{1}+\psi]$

###### Proof.

We start by considering $M_{-}(c)$. For any $\psi$, the interval
$[c_{0}-\psi,1]$ is compact and so by the Heine-Cantor theorem it suffices to
show that $M_{-}(c)$ is pointwise continuous at each $c$ in the interval. Let
$P\subset\mathbb{R}$ be the (finite) set $\\{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q}):\hat{q}\in\widehat{\mathcal{Q}}\\}$.
Now, for any $c$ in the interval, one of the following two cases must hold:

  * (A)

$c\not\in P$, i.e., there does not exist a $\hat{q}\in\widehat{\mathcal{Q}}$
whose corresponding platform payoff is equal to $c$. In this case, we can
always find a $\delta$ small enough such that for all
$c^{\prime}\in(c-\delta,c+\delta)$, the set
$\widehat{\mathcal{Q}}_{-}(c^{\prime})=\widehat{\mathcal{Q}}_{-}(c)$ does not
change (by the finite nature of $\widehat{\mathcal{Q}}$). We then use the
continuity of $\widetilde{U}(\hat{q},c)$ in $c$ for each
$\hat{q}\in\widehat{\mathcal{Q}}$, and the fact that a maximum of continuous
functions is continuous to show that $M_{-}$ is continuous at $c$.

  * (B)

$c\in P$, i.e., there exists at least one user model in
$\widehat{\mathcal{Q}}$ whose corresponding payoff is $c$ (in other words,
$\widehat{\mathcal{Q}}_{=}(c)\neq\emptyset$). Let
$\hat{q}\in\widehat{\mathcal{Q}}_{=}(c)$ be any such model. Define
$\bar{c}=c+2\psi$, so that $\bar{c}>c_{0}$. We will first show by
contradiction that there exists a user model
$\hat{q}^{\prime}\in\widehat{\mathcal{Q}}_{-}(\bar{c})$ such that
$\widetilde{U}(\hat{q},\bar{c})<\widetilde{U}(\hat{q}^{\prime},\bar{c})$. In
particular, if this were not the case, we would have
$\widetilde{U}(\hat{q},\bar{c})=M_{-}(\bar{c})$, and since $\bar{c}>c_{0}$ we
would have that $\widetilde{U}(\hat{q},\bar{c})\geqslant M(\bar{c})$, and thus
by (20),

$\displaystyle(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})-\bar{c})^{2}=\gamma>0.$

By supposition, $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})=c$. Thus, by setting $\psi$
small enough (i.e., as $\bar{c}\to c$), we reach a contradiction. We can also
set $\psi$ small enough so that
$\widehat{\mathcal{Q}}_{-}(\bar{c})=\widehat{\mathcal{Q}}_{-}(c)\cup\widehat{\mathcal{Q}}_{=}(c)$.
In this case, the logic above applies to any
$\hat{q}\in\widehat{\mathcal{Q}}_{=}(c)$, and so it must be that for some
$\hat{q}^{\prime}\in\widehat{\mathcal{Q}}_{-}(c)$,

$\eta\coloneqq\min_{\hat{q}\in\widehat{\mathcal{Q}}_{=}(c)}\left({\widetilde{U}(\hat{q}^{\prime},\bar{c})-\widetilde{U}(\hat{q},\bar{c})}\right)>0,$

For the same $\hat{q}^{\prime}$ (and again, any
$\hat{q}\in\widehat{\mathcal{Q}}_{=}(c)$), and any $c^{\prime}\in(c,\bar{c})$,

$\displaystyle\widetilde{U}(\hat{q}^{\prime},c^{\prime})-\widetilde{U}(\hat{q},c^{\prime})$
$\displaystyle\geqslant\eta+(\widetilde{U}(\hat{q}^{\prime},\bar{c})-\widetilde{U}(\hat{q}^{\prime},c^{\prime}))-(\widetilde{U}(\hat{q},\bar{c})-\widetilde{U}(\hat{q},c^{\prime})).$

Observing that

$\displaystyle\widetilde{U}(\hat{q}^{\prime},\bar{c})-\widetilde{U}(\hat{q}^{\prime},c^{\prime})$
$\displaystyle=2(\bar{c}-c^{\prime})(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}-c)+(\bar{c}-c^{\prime})^{2}$ $\displaystyle=4\psi(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}-c)+4\psi^{2},$

we can again set $\psi$ small enough so that
$\widetilde{U}(\hat{q}^{\prime},c^{\prime})>\widetilde{U}(\hat{q},c^{\prime})$.
As a result, we have shown that for any $c^{\prime}\in(c,\bar{c}),$ the
maximizer corresponding to $M_{-}(c^{\prime})$ is not a member of
$\widehat{\mathcal{Q}}_{=}(c)$, i.e.,

$\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}_{-}(c^{\prime})}\widetilde{U}(\hat{q},c^{\prime})\cap\widehat{\mathcal{Q}}_{=}(c)=\emptyset.$

Now, there exists a $\delta$ such that for all
$c^{\prime}\in[c-\delta,c+\delta]$,

$\widehat{\mathcal{Q}}_{-}(c^{\prime})=\begin{cases}\widehat{\mathcal{Q}}_{-}(c)&\text{
if }c^{\prime}<c\\\
\widehat{\mathcal{Q}}_{-}(c)\cap\widehat{\mathcal{Q}}_{=}(c)&\text{ if
}c^{\prime}>c,\end{cases}$

and in both cases
$\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}_{-}(c^{\prime})}\subset\widehat{\mathcal{Q}}_{-}(c)$,
and thus we can use continuity of $\widetilde{U}(\hat{q},c)$ in $c$.

The same logic implies that $M_{+}(c)$ is uniformly continuous on the interval
$[0,c_{1}+\psi]$. ∎

Note that by definition of $c_{1}$, and because $c_{1}+\psi>c_{1}$, it must be
that $M_{+}(c_{1}+\psi)<M(c_{1}+\psi)$ (otherwise $c_{1}$ would not be an
upper bound on the set of which it is the $\sup$), which means that
$M_{-}(c_{1}+\psi)=M(c_{1}+\psi)$, which means that $c_{1}+\psi\geqslant
c_{0}$. Conversely, $c_{0}-\psi\leqslant c_{1}$, and thus
$[c_{0}-\psi,c_{1}+\psi]$ is a well-defined interval on which both $M_{-}(c)$
and $M_{+}(c)$ are uniformly continuous.

Consider the function $h(c)\coloneqq M_{+}(c)-M_{-}(c)$ on the interval
$[c_{0}-\psi,c_{1}+\psi]$. At the beginning of the interval, $h(c)>0$, while
at the end of the interval $h(c)<0$. By the intermediate value theorem, there
exists $c^{*}\in[c_{0}-\psi,c_{1}+\psi]$ such that $h(c^{*})=0$.

Now, $\widehat{\mathcal{Q}}^{*}(c^{*})$ is surely not a singleton, as it must
contain at least one element $\hat{q}^{+}\in\widehat{\mathcal{Q}}_{+}(c^{*})$
and one element $\hat{q}^{-}\in\widehat{\mathcal{Q}}_{-}(c^{*})$. We apply the
following procedure to each $\hat{q}\in\widehat{\mathcal{Q}}^{*}(c^{*})$:

  1. 1.

Use Lemma C.1 to find a distribution $r_{\hat{q}}\in\Delta(\mathcal{Z})$ such
that
$\mathcal{W}_{1}(r_{\hat{q}},p({\cdot};{\delta_{\hat{q}}}))<\varepsilon_{0}$,
and $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(r_{\hat{q}},\hat{q})\neq\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})$. For simplicity, we assume that
$c^{*}$ is not one of the finite number of values of $c$ such that we cannot
apply Lemma C.1—if this is not the case, we can simply perturb $c^{*}$ by some
sufficiently small amount so as not to affect the calculations in the rest of
the proof.

  2. 2.

If $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(r_{\hat{q}},\hat{q})>\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})$, terminate.

  3. 3.

Otherwise, continue to the next $\hat{q}\in\widehat{\mathcal{Q}}^{*}(c^{*})$.

  4. 4.

If that is the last $\hat{q}\in\widehat{\mathcal{Q}}^{*}(c^{*})$, terminate
and do not perform Step 1.

At the end of the procedure, we will have some
$\hat{q}^{*}\in\widehat{\mathcal{Q}}^{*}(c^{*})$ such that $\hat{q}^{*}$ is
strictly preferred by the user to any other
$\hat{q}\in\widehat{\mathcal{Q}}^{*}(c^{*})$ (and thus, to any
$\hat{q}\in\widehat{\mathcal{Q}}$) under the constructed proposition
distributions. In particular, we can use Lemma C.2 to construct a new
algorithm $p^{\prime}$ such that

$d_{\mathcal{P}}(p,p^{\prime})<\varepsilon_{0}\qquad\text{ and
}\qquad\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\prime}(\cdot;\delta_{\hat{q}}),\hat{q})=\\{\hat{q}^{*}\\}.$

Without loss of generality, suppose that
$\hat{q}^{*}\in\widehat{\mathcal{Q}}_{-}(c^{*})$.

Now, let $\varepsilon_{2}>0$ be a small enough constant to ensure that
$Q^{*}(c^{*}-\varepsilon_{2})\subset Q_{+}(c^{*})$ (note that
$Q^{*}(c^{*}-\varepsilon_{2})\subset Q_{+}(c^{*}-\varepsilon_{2})$ for all
$\varepsilon_{2}>0$; then, by setting $\varepsilon_{2}$ small enough we can
also ensure that $Q_{+}(c^{*}-\varepsilon_{2})=Q_{+}(c^{*})$). Thus, we can
set $\varepsilon_{2}$ small enough to ensure the following two conditions:

  * (a)

$\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p(\cdot;\delta_{\hat{q}}),\hat{q})\subset\widehat{\mathcal{Q}}_{+}(c^{*}),$
and

  * (b)

$\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\prime}(\cdot;\delta_{\hat{q}}),\hat{q})\subset\widehat{\mathcal{Q}}_{-}(c^{*}).$

In particular, in combination with (20), these two conditions imply that

  * (a)

For all
$\hat{q}^{*}(p)\in\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p(\cdot;\delta_{\hat{q}}),\hat{q})$, we have $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\delta_{\hat{q}}),\hat{q})\geqslant
c^{*}+\sqrt{\gamma^{\prime}}$

  * (b)

For all
$\hat{q}^{*}(p^{\prime})\in\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\prime}(\cdot;\delta_{\hat{q}}),\hat{q})$, we have $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\delta_{\hat{q}}),\hat{q})\leqslant
c^{*}-\sqrt{\gamma^{\prime}}$,

where we define

$\gamma^{\prime}\coloneqq\frac{\max_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\prime}(\cdot;\delta_{\hat{q}}),\hat{q})-\min_{\hat{q}\in\widehat{\mathcal{Q}}}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\prime}(\cdot;\delta_{\hat{q}}),\hat{q})}{4}-(\beta-\alpha)>0,$

which can be made arbitrarily close to $\gamma$ by setting $\varepsilon_{0}$
small enough. Putting these two together, we get that

$\left|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\delta_{\hat{q}^{*}(p^{\prime})}),\hat{q}^{*}(p^{\prime}))-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\delta_{\hat{q}^{*}(p)}),\hat{q}^{*}(p))\right|\geqslant
2\sqrt{\gamma^{\prime}}.$

To conclude the proof, we show that for a sufficiently granular
$\varepsilon$-net, the user does not gain much by deviating from the set of
user models $\widehat{\mathcal{Q}}$.

######  Lemma C.4.

Fix any any user strategy $q$ and any full-support algorithm $p$, and suppose
that $\widehat{\mathcal{Q}}$ is an $\varepsilon$-net hypothesis class for some
$\varepsilon\in(0,\frac{1}{|\mathcal{B}|})$. Then for every user model
$\hat{q}\in\widehat{\mathcal{Q}}$,

$\displaystyle\hat{q}\in
S^{\infty}(q,p,\widehat{\mathcal{Q}})\implies\max_{Z\in\mathcal{Z}}\text{KL}(q(\cdot|Z),\hat{q}(\cdot|Z))\leqslant\log\left(\frac{1}{1-|\mathcal{B}|\cdot\varepsilon}\right),$

and as a result,
$\widetilde{U}(\hat{q},c)\geqslant\widetilde{U}(q,c)-\sqrt{-\frac{1}{2}\log(1-|\mathcal{B}|\varepsilon)}$.

###### Proof.

Note that because $\widehat{\mathcal{Q}}$ is the Cartesian product of
$\Delta_{\varepsilon}(\mathcal{B})$ across $Z$, when $p$ has full support
every element $\hat{q}\in S^{\infty}(q,p,\widehat{\mathcal{Q}})$ must satisfy

$\hat{q}(\cdot|Z)\in\arg\min_{p_{B}\in\Delta_{\varepsilon}(\mathcal{B})}\text{KL}(q(\cdot|Z),p_{B})\
\forall\ Z\in\mathcal{Z}.$

In particular, we can find a $\hat{q}^{\prime}$ that strictly dominates any
$\hat{q}$ that violates this condition by swapping its behavior at violating
values of $Z$. Now, for $\nu=\varepsilon\cdot|\mathcal{B}|$, let $q_{\nu}$ be
a mixture of $q$ with the uniform distribution over $\mathcal{B}$, i.e.,

$q_{\nu}(\cdot|Z)\coloneqq\nu\cdot\frac{1}{|\mathcal{B}|}+(1-\nu)\cdot
q(\cdot|Z).$

By definition of the $\varepsilon$-net, there must be some $\hat{q}_{i}$ such
that $\hat{q}_{i}(B|Z)\geqslant q_{\nu}(B|Z)-\varepsilon$, and in turn,

$\displaystyle\text{KL}(q(\cdot|Z),\hat{q}_{i}(\cdot|Z))$
$\displaystyle\leqslant\mathbb{E}_{B\sim
q(\cdot|Z)}\left[\log\left({\frac{q(\cdot|Z)}{\nu\cdot\frac{1}{|\mathcal{B}|}+(1-\nu)\cdot
q(\cdot|Z)-\varepsilon}}\right)\right]=\log\left({\frac{1}{1-\nu}}\right).$

Next, observe that the function $U(B,Z)=(V(B,Z)-c)^{2}$ is

bounded in $[0,1]$, and so

$\displaystyle\widetilde{U}(q,c)$ $\displaystyle=\min_{\mu\in
S^{\infty}(q,p,\widehat{\mathcal{Q}})}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p({\cdot};{\mu}),q)$ $\displaystyle\leqslant\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p({\cdot};{\delta_{\hat{q}}}),q)$ (since $\hat{q}\in S^{\infty}$)
$\displaystyle\leqslant\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p({\cdot};{\delta_{\hat{q}}}),\hat{q})+\max_{Z\in\mathcal{Z}}\
\text{TV}(\hat{q}(\cdot|Z),q(\cdot|Z))$ (since $U$ is bounded in $[0,1]$)
$\displaystyle\leqslant\widetilde{U}(\hat{q},c)+\sqrt{\frac{1}{2}\log\left({\frac{1}{1-\nu}}\right)},$

where above we used the definition of total variation distance, as well as the
fact that for any two probability distributions $A$ and $B$,
$\text{TV}(A,B)<\sqrt{\frac{1}{2}\text{KL}(A,B)}$ by Pinsker’s inequality. ∎

For any $\varepsilon_{1}>0$, we can use Lemma C.4 and set

$\varepsilon=\frac{1-\exp\left({-\varepsilon_{1}^{2}}\right)}{|\mathcal{B}|}$

to get that
$\widetilde{U}(\hat{q},c)\geqslant\widetilde{U}(q,c)-\varepsilon_{1}$. Thus,
if $\hat{q}\in S^{\infty}(q,p,\widehat{\mathcal{Q}})$ for some strategy $q$,
then $q$ cannot yield a significantly higher payoff than $\hat{q}$. This
allows us to reduce the case of picking the optimal user strategy $q$ to
picking the optimal user model $\hat{q}\in\widehat{\mathcal{Q}}$. That is, if
the user strictly prefers a user model $\hat{q}^{*}$ to any other user model,
we can set $\varepsilon$ sufficiently small so that the user strictly prefers
their globally stable set to be $\\{\hat{q}^{*}\\}$, which entails playing a
strategy close to $\hat{q}^{*}$.

Thus, the smallest possible gap between the platform’s predicted payoff under
$p^{\prime}$ and its true payoff under $p^{\prime}$ is given by

$\displaystyle\min_{\mu\in\Delta(\\{\hat{q}^{*}(p)\\})}\left|\widehat{V}(p^{\prime},\mu)-{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p^{\prime})\right|$
$\displaystyle=\left|\widehat{V}(p^{\prime},\delta_{\hat{q}^{*}(p)})-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\prime}(\cdot;\delta_{\hat{q}^{*}(p^{\prime})},q^{*}(p^{\prime})))\right|$
$\displaystyle=\left|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\prime}(\cdot;\delta_{\hat{q}^{*}(p)}),\hat{q}^{*}(p))-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\prime}(\cdot;\delta_{\hat{q}^{*}(p^{\prime})},q^{*}(p^{\prime})))\right|$
$\displaystyle\geqslant 2\sqrt{\gamma^{\prime}}-\left|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\prime}(\cdot;\delta_{\hat{q}^{*}(p^{\prime})},\hat{q}^{*}(p^{\prime})))-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\prime}(\cdot;\delta_{\hat{q}^{*}(p^{\prime})},q^{*}(p^{\prime})))\right|$
$\displaystyle\geqslant 2\sqrt{\gamma^{\prime}}-\varepsilon_{1},$

where the last inequality follows from Lemma C.4.

∎

####  C.3 Proof of Proposition 6.14

We prove this result using a highly oversimplified example in order to
illustrate the main principle behind the proof. First, let the user’s payoff
function be $U(B,Z)=V(B,Z)+\lambda\cdot g(Z)$, where $V(B,Z)$ is the platform
payoff and $g(Z)$ is a function to be specified later (along with the scalar
$\lambda$). Even without specifying $g(Z)$, it is clear that for any
$Z\in\mathcal{Z}$, $q^{\text{BR}}(\cdot|Z)=\arg\max_{B\in\mathcal{B}}V(B,Z)$.

Now, find the following two user models $\hat{q}_{1}$ and $\hat{q}_{2}$:

$\displaystyle\hat{q}_{1}$
$\displaystyle=\arg\min_{\hat{q}\in\widehat{\mathcal{Q}}}\text{KL}\left[p(\cdot;\delta_{\hat{q}})\times
q^{\text{BR}},p(\cdot;\delta_{\hat{q}})\times\hat{q}\right],$
$\displaystyle\hat{q}_{2}$
$\displaystyle=\arg\max_{\hat{q}\in\widehat{\mathcal{Q}}}\mathcal{W}\left[p(\cdot;\delta_{\hat{q}_{1}}),p(\cdot;\delta_{\hat{q}})\right].$

(In the literature, $\hat{q}_{1}$ is referred to as a Berk-Nash equilibrium
[EP16a, FII20a].) Consider the distributions $p(\cdot;\delta_{\hat{q}_{1}})$
and $p(\cdot;\delta_{\hat{q}_{2}})$, and define

$g(\cdot)\coloneqq\arg\max_{\|f\|_{L}\leqslant 1}\mathbb{E}_{Z\sim
p(\cdot;\delta_{\hat{q}_{2}})}[f(Z)]-\mathbb{E}_{Z\sim
p(\cdot;\delta_{\hat{q}_{1}})}[f(Z)],$

where $\|f\|_{L}$ represents the Lipschitz constant of the function
$f:\mathcal{Z}\to\mathbb{R}$.

By construction of $g$, we have that for any user strategy $q$,

$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p(\cdot;\delta_{\hat{q}_{2}}),q)-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p(\cdot;\delta_{\hat{q}_{1}}),q)$
$\displaystyle\geqslant\lambda\cdot\mathcal{W}(p({\cdot};{\delta_{\hat{q}_{1}}}),p({\cdot};{\delta_{\hat{q}_{2}}}))-1$
$\displaystyle\geqslant\frac{\lambda}{2}\max_{\hat{q},\hat{q}^{\prime}\in\widehat{\mathcal{Q}}}\mathcal{W}(p({\cdot};{\delta_{\hat{q}}}),p({\cdot};{\delta_{\hat{q}^{\prime}}}))-1$
$\displaystyle>0,$

as long as $\lambda>\frac{2}{R}$.

Now, let $\widehat{\mathcal{Q}}_{1}=\\{\hat{q}_{2}\\}$ and
$\widehat{\mathcal{Q}}_{2}=\\{\hat{q}_{2},\hat{q}_{1}\\}$. Under
$\widehat{\mathcal{Q}}_{1}$, the platform will trivally converge to
$\hat{q}_{2}$ regardless of the user’s behavior, and so the user is
incentivized to play according to $q^{\text{BR}}$.

When $\hat{q}_{1}$ is added to the set of user models, the naive user strategy
$q^{\text{BR}}$ will lead to the user model $\hat{q}_{1}$ never being
eliminated from the globally stable set (due to its status as a Berk-Nash
equilibrium for $q^{\text{BR}}$). By construction of the user payoff function,
this is always suboptimal for the user, since $\delta_{\hat{q}_{1}}$ will be
in $\Delta(S^{\infty}(q,p,\widehat{\mathcal{Q}}))$, and so they will be
incentivized to switch to a strategy that ensures only $\hat{q}_{2}$ is in the
globally stable set.

Since, by assumption, $V(B,Z)$ has a unique maximizer for each
$Z\in\mathcal{Z}$, the strategic user’s new strategy must result in strictly
lower platform payoff, concluding the proof of the theorem.

######  Remark C.5.

Note that while the example presented in this proof is rather contrived, the
principle behind it is actually quite general. The principle is that the
strategic user wants to induce a specific proposition distribution from the
platform, but does not want to stray too far from their best-response
behavior. Thus, they purposefully pick a strategy that the platform
misinterprets (in this case, that strategy is just $q^{\text{BR}}$, but it
could be any strategy $q_{1}^{*}$). When the platform gets “better” at
capturing their behavior by adding a user model that is close to $q_{1}^{*}$,
the user is forced to move even further away from their best-response
behavior, making things worse for the platform.

####  C.4 Proof of Proposition 6.15

See 6.15

###### Proof.

We first restate the two quantities being compared:

$\displaystyle\widehat{V}(p_{\text{CF}},\mu)$
$\displaystyle=\mathbb{E}_{\hat{q}\sim\mu}\left[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{\text{CF}}(\cdot;\mu),\hat{q})\right].$
$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}_{\text{BR}}(p_{\text{CF}})$
$\displaystyle=\min_{\mu\in\Delta(S^{\infty}(q^{\text{BR}},p_{\text{CF}}))}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}\left(p_{\text{CF}}(\cdot;\mu),q^{\text{BR}}\right).$

Using the triangle inequality,

$\displaystyle\max_{\mu\in\Delta(S^{\infty}(q^{\text{BR}},p))}\left|\widehat{V}(p_{\text{CF}},\mu)-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}_{\text{BR}}(p_{\text{CF}})\right|$
$\displaystyle\leqslant\\!\\!\\!\\!\\!\max_{\mu_{1},\mu_{2}\in\Delta(S^{\infty}(q^{\text{BR}},p))}\\!\left|\mathbb{E}_{\hat{q}\sim\mu_{1}}\\!\left[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{\text{CF}}(\cdot;\mu_{1}),\hat{q})\right]\\!-\\!\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}\\!\left(p_{\text{CF}}(\cdot;\mu_{2}),q^{\text{BR}}\right)\right|$
$\displaystyle\leqslant\max_{\mu_{1},\mu_{2}\in\Delta(S^{\infty}(q^{\text{BR}},p))}\\!\left|\mathbb{E}_{\hat{q}\sim\mu_{1}}\\!\left[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{\text{CF}}(\cdot;\mu_{1}),\hat{q})\\!-\\!\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}\\!\left(p_{\text{CF}}(\cdot;\mu_{2}),\hat{q}\right)\right]\right|$
$\displaystyle\qquad+\left|\mathbb{E}_{\hat{q}\sim\mu_{1}}\\!\left[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{\text{CF}}(\cdot;\mu_{2}),\hat{q})\\!-\\!\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}\\!\left(p_{\text{CF}}(\cdot;\mu_{2}),q^{\text{BR}}\right)\right]\right|$
$\displaystyle\leqslant\max_{\mu_{1},\mu_{2}\in\Delta(S^{\infty}(q^{\text{BR}},p))}\\!\left(\left|\mathbb{E}_{\hat{q}\sim\mu_{1}}\\!\left[\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{\text{CF}}(\cdot;\mu_{1}),\hat{q})\\!-\\!\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}\\!\left(p_{\text{CF}}(\cdot;\mu_{2}),\hat{q}\right)\right]\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\phantom{q^{\text{BR}^{2}}_{2}}\right|\right.$
$\displaystyle+\left.\max_{\hat{q}\in
S^{\infty}(q^{\text{BR}},p)}\left|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{\text{CF}}(\cdot;\mu_{2}),\hat{q})\\!-\\!\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}\\!\left(p_{\text{CF}}(\cdot;\mu_{2}),q^{\text{BR}}\right)\right|\right)$

Note that the second term above is bounded by the maximum total variation
distance between $\hat{q}$ and $q^{\text{BR}}$, which we can bound using Lemma
C.4, restated below: See C.4 We can then bound the first term using the well-
behavedness condition which implies that

$\displaystyle
d_{\mathcal{P}}(p_{\text{CF}}(\cdot;\mu_{1}),p_{\text{CF}}(\cdot;\mu_{2}))$
$\displaystyle\leqslant
L_{\mathcal{P}}\cdot\mathbb{E}_{\hat{q}_{1}\sim\mu_{1},\,\hat{q}_{2}\sim\mu_{2}}\left[\max_{Z\in\mathcal{Z}}\
\text{TV}(\hat{q}_{1}(\cdot|Z),\hat{q}_{2}(\cdot|Z))\right]$
$\displaystyle\leqslant L_{\mathcal{P}}\cdot$
$\displaystyle\mathbb{E}_{\hat{q}_{1}\sim\mu_{1},\,\hat{q}_{2}\sim\mu_{2}}\left[\max_{Z\in\mathcal{Z}}\
\text{TV}(\hat{q}_{1}(\cdot|Z),q^{\text{BR}}(\cdot|Z))+\text{TV}(\hat{q}_{2}(\cdot|Z),q^{\text{BR}}(\cdot|Z))\right],$

which we can again bound using Lemma C.4. Thus,

$\displaystyle\max_{\mu\in\Delta(S^{\infty}(q^{\text{BR}},p))}\left|\widehat{V}(p_{\text{CF}},\mu)-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}_{\text{BR}}(p_{\text{CF}})\right|\leqslant(2\cdot
L_{\mathcal{P}}+1)\sqrt{\frac{1}{2}\log\left(\frac{1}{1-|\mathcal{B}|\cdot\varepsilon}\right)}\leqslant(2L_{\mathcal{P}}+1)\cdot\sqrt{|\mathcal{B}|\cdot\varepsilon},$

where the last inequality follows from $-\log(1-x)\leqslant 2x$ for all
$x\in[0,\frac{1}{2}]$. ∎