[SC]scpurple [AI]aipurple

# User Strategization and Trustworthy Algorithms

Sarah H. Cen, Andrew Ilyas, and Aleksander Mądry
MIT
<EMAIL_ADDRESS>
###### Abstract

Many human-facing algorithms—including those that power recommender systems or
hiring decision tools—are trained on data provided by their users. The
developers of these algorithms commonly adopt the assumption that the data
generating process is exogenous: that is, how a user reacts to a given prompt
(e.g., a recommendation or hiring suggestion) depends on the prompt and not on
the algorithm that generated it. For example, the assumption that a person’s
behavior follows a ground-truth distribution is an exogeneity assumption. In
practice, when algorithms interact with humans, this assumption rarely holds
because users can be strategic. Recent studies document, for example, TikTok
users changing their scrolling behavior after learning that TikTok uses it to
curate their feed, and Uber drivers changing how they accept and cancel rides
in response to changes in Uber’s algorithm.

Our work studies the implications of this strategic behavior by modeling the
interactions between a user and their data-driven platform as a repeated, two-
player game. We first find that user strategization can actually help
platforms in the short term. We then show that it corrupts platforms’ data and
ultimately hurts their ability to make counterfactual decisions. We connect
this phenomenon to user trust, and show that designing trustworthy algorithms
can go hand in hand with accurate estimation. Finally, we provide a
formalization of trustworthiness that inspires potential interventions.

###  1 Introduction

In the age of personalization, data-driven platforms have become increasingly
reliant on data provided by their users. Platforms like Facebook, Amazon, and
Uber tailor their services to each user based on the user’s interaction
history. Even data-driven tools in medicine and hiring utilize previous
interactions in order to fine-tune and improve their results.

Traditionally, platforms make a key assumption when processing user data,
namely that the data is generated exogenously, i.e., how a user behaves
depends on the user but not on the platform’s algorithm. When a user’s
behavior is exogenous, an action—say, skipping a video on YouTube—is a
reflection of the user’s preference for that video and not of YouTube’s
algorithm: the user would skip the video regardless of the algorithm that
generated it. YouTube can therefore attribute the skip to the user’s content
preferences and recommend future content accordingly.

In practice, however, users are not blind to how their platforms operate. In
fact, many users adapt their behavior—or strategize—based on their perception
of how the platform works. For instance, a Facebook user might not click on a
post not because they find it uninteresting, but because they believe the
algorithm will over-recommend similar content in the future if they do click.
Or an Uber driver may cancel low-paying rides that they would normally accept
because they have learned that Uber’s algorithm does not penalize them for
excessive cancelations [Mar20a]. In fact, [CIA+23a] recently document user
strategization in a lab experiment, discovering that over half of users
consciously strategize on online platforms.

###### Contributions.

In this paper, we study the implications of user strategization and establish
that it can be both helpful and harmful to platforms. Using a game-theoretic
model of strategization (which [CIA+23a] find to be empirically predictive of
strategization), we first demonstrate that strategization can provide the
platform with cues that the platform would otherwise miss. We then show,
however, that the platform’s data is no longer generalizable when users
strategize—data gathered under one algorithm cannot be used to make reliable
predictions in other contexts. This outcome is undesirable for platforms that
may wish to use the data for other purposes, e.g., to train alternate
algorithms, begging the question: What should platforms do when users
strategize?

To work around user strategization, some platforms attempt to gather data that
is more likely to satisfy the exogeneity assumption. For instance, Facebook
may notice that users strategize by selectively clicking the “like” button and
begin tracking how quickly users scroll down their feeds, using the dwell time
on each post as an “exogenous” signal of user interest. However, this strategy
can backfire. Upon learning that Facebook is tracking their dwell time, users
may begin strategizing how they scroll, violating the exogeneity assumption
once again and prompting a cat-and-mouse game that only serves to erode the
trust between a user and their platform.

It is natural to ask: is this outcome inevitable? Is out-maneuvering users the
only way for platforms to obtain high-quality data? Not necessarily. In this
work, we argue that trustworthy algorithm design plays a key role. When an
algorithm is trustworthy, users do not feel compelled to strategize—they
provide data that, for all intents and purposes, looks exogenous. We formalize
this intuition, calling a platform $\kappa$-trustworthy when their choice of
algorithm does not induce strategization and ensures users receive at least
$\kappa$ utility on average. Intuitively, a platform is trustworthy when a
user believes that the platform looks out for their interests along the same
axis that would induce the user to strategize. We connect this formalization
to the existing literature on trustworthiness, comparing it to definitions
that arise in political science and law. Using this framework, we show that
trustworthy design can mitigate the effects of strategization on a platform,
to the benefit of both the platform and user.

####  1.1 Summary of contributions

Below, we describe our contributions and findings in greater detail.

###### A game-theoretic model of data-driven algorithms.

We begin by modeling the interactions between a user and their data-driven
platform as a repeated, two-player game (Section 3). Under our model, there
are two agents: a user and their platform. At each time step, the platform
puts forth a proposition (e.g., a prediction or a recommendation), the user
responds with a behavior (e.g., agreeing with the prediction or ignoring the
recommendation), and each party receives a payoff based on their action. The
platform’s goal is to generate high-payoff propositions by developing a good
estimate of the user’s behavioral tendencies from repeated interactions with
the user. In our model, the platform “moves first” in that it declares how it
generates propositions, after which the user “moves second” by choosing how
they respond to propositions (akin to a Stackelberg game). Importantly, this
model allows users to observe and adapt to the platform’s algorithm.

###### Users strategize in order to optimize their long-term outcomes.

In Section 4, we use this model to define what it means for a user to be
strategic. We call a user “naive” if they adopt a best-response strategy,
i.e., if at every time step, they behave as though they are unaware that an
algorithm uses their behavior to updates its future propositions. In contrast,
we call a user “strategic” if they anticipate how their next action may affect
the platform’s future propositions and, in turn, the user’s long-term payoff.
That is, the strategic user understands that their actions can affect the
platform’s long-term behavior and adapt accordingly.

From a technical perspective, our model of strategization departs from
previous models of non-myopic agents in that we consider users who optimize
their limiting payoff rather than a sum of their discounted future payoffs. We
leverage the notion of a globally stable set [FII20a] from the misspecified
learning literature to study the platform’s limiting behavior. This approach
(a) allows us to bypass the often difficult calculations that result when
optimizing a discounted sum; and (b) better aligns with our intuition about
strategization, where users think abstractly about how platforms use their
data, without much regard for when the consequences will arise. As a result,
our model accounts for the fact that delay-based mechanisms (i.e., algorithms
that wait to incorporate new data) are unlikely to “solve” strategization even
though these mechanisms would do so in a discounted-sum formulation.

###### Main results: User strategization can both help and hurt the platform.

In Section 6, we present our main results. We first find that, when the
platform’s algorithm is fixed, user strategization can improve the platform’s
payoff when the user’s and platform’s payoffs are sufficiently aligned. We
then show that user strategization can mislead the platform by distorting the
data that the platform collects. Specifically, when a user is strategic, the
data the platform collects under one algorithm is not reflective of the user’s
behavior under a different algorithm (or in a different context). As a result,
user strategization can result in unexpected phenomena—for example, we
demonstrate that expanding the platform’s hypothesis class (an action that
typically improves platform performance) can actually lower the platform’s
payoff when users are strategic. As expected, these difficulties disappear
when the user is not strategic, i.e., when the user behaves exogenously, which
suggests that platforms should design algorithms that do not incentivize
strategization.

###### Trustworthy design can mitigate user strategization.

To counter strategization, platforms are left with a few options. They could
simply use the collected data and risk drawing incorrect inferences. They
could post-process the data, but “correcting” the data by removing the effect
of strategization is extremely challenging because a user can strategize for
many different reasons and along many different axes. Alternatively, platforms
could “correct” for strategic behavior by gathering more data. In Section 7,
we discuss when and how these approaches can fall short.

We then discuss how another approach—designing trustworthy algorithms—can
improve user and platform outcomes. Formally, we define a $\kappa$-trustworthy
algorithm as one that (i) does not incentivize users to strategize and (ii)
guarantees that the user’s payoff is at least $\kappa\geqslant 0$. We connect
this definition to existing notions of trust, e.g., trust as “encapsulated
interest” [Har06a]. We conclude by surfacing the reasons why users strategize,
then discussing two interventions for trustworthy design: offering multiple
algorithms and providing feedback mechanisms. Operationally, these two
mechanisms allow platforms to induce behavior that looks approximately
exogenous while uncovering what users find untrustworthy.

###  2 Related work

Our work draws inspiration from extensive lines of work spanning computer
science, economics, game theory, and the social sciences. We summarize a few
of the most related areas to our work below. Appendix A contains an extended
account of related work.

Conceptually related to this work are recent models of user behavior on
recommender systems that remove the traditional “fixed preferences” assumption
(e.g., [KMR22a, HHP23a, CIM22a]). In short, our work differs from prior work
in at least three ways: (a) we study users that adapt to the algorithm that a
platform uses; (b) we focus on the effects of this adaption on platforms; and
(c) our analysis applies to any data-driven platform that involves human
interaction. We further disambiguate from these models in Appendix A. Prior
work has also empirically documented user adaptation to their algorithms, most
notably in the context of TikTok [SVM22a, KL23a, SHS22a]. The closest to our
work is subsequent work by [CIA+23a], who adapt our model to directly test for
user strategization in recommendation settings using a lab experiment.

From the economics literature, our work leverages existing results on
misspecified learning [FRS17a, FLS21a, Boh16a, BH21a, FII20a] (in particular,
that of [FII20a]) to characterize the platform’s limiting behavior.
Furthermore, our definitions of strategization and trustworthiness are closely
related to concepts in mechanism design and is thus connected to mechanism
design for repeated games and auctions [MS06a, BM93a, KL93a]. In particular,
part of the definition of trustworthiness is an adaptation of incentive-
compatibility to our setting.

From the computer science literature, our model resembles that of strategic
classification as well as its many variants [LR22a, BKS12a, HMP+16a, DRS+18a,
GNE+21a, ZMS+21a, HLN+22a]. Compared to these works, in our model all of the
following are true: (a) users have idiosyncratic utility functions that they
can optimize arbitrarily, and are not bound to small perturbations of some
“ground-truth” features; (b) the platform uses a pre-specified learning
algorithm (Bayesian updating); (c) users declare a behavior strategy rather
than an action; (d) users can be myopic or non-myopic in how they interact
with the platform (and our model of non-myopic users differs from that of
prior work [HLN+22a]). Strategic classification is a special case of
performative prediction [PZM+20a], and the latter is also relevant to our
work—in particular, our characterization of platform convergence can be viewed
as a performative stability analysis. We then study the effect of data
gathered in a performative setting when used in other contexts.

Appendix A provides an extended comparison with the works mentioned above, and
also places our results into context with works from multi-agent learning
[WAO20a, HDA+16a, ZYB21a] and Human-AI collaboration [OY20a, HHC23a, EBC+19a,
BCD+21a].

###  3 Model

In this section, we present our game-theoretic model of the interactions
between a user and their data-driven platform. At its core, the model
comprises a repeated, two-player game. At every time step, the platform
generates propositions (e.g., recommendations). The user then responds to
these propositions with behaviors (e.g., chooses whether to engage with a
recommendation).

A key feature of our model is that there is no “ground-truth” user behavior.
In particular, the way that the user responds to propositions may depend on
how the platform generates them. Our model therefore departs from earlier
works that assume a user’s behaviors are drawn from a single fixed, unknown
distribution.

Since we are interested in how users adapt to their platforms, we study the
setting where the platform first declares the strategy it will use to generate
propositions. The user then decides on how they wish to behave, with full
knowledge of the platform’s intended strategy.111While full user knowledge is
a strong assumption, the effects we discuss here will only be exacerbated when
users have an imperfect model of the platform. We leave studying this case to
future work.

Figure 1: Illustration of the setup described in Section 3. (Left) At each
time step $t$, the platform issues propositions $Z_{t}$, and the user responds
with behaviors $B_{t}$. The user’s actions are determined by their strategy
$q:\mathcal{Z}\rightarrow\Delta(\mathcal{B})$. The platform’s are determined
by the algorithm $p$, the hypothesis class $\widehat{\mathcal{Q}}$, and the
platform’s belief $\mu_{t}$ over the hypothesis class at time $t$. (Right) The
platform’s actions at time $t$ depend on its belief $\mu_{t}$. Here, $\mu_{t}$
is a distribution (i.e., set of weights) over $\widehat{\mathcal{Q}}$ such
that $\mu_{t}(\hat{q}_{i})$ denotes the probability that the platform assigns
to the user model $q=\hat{q}_{i}$ at time $t$.

####  3.1 Setup

We model the interactions between a user and their platform as a two-player
game. Formally, for some $d_{1},d_{2}>0$, let
$\mathcal{Z}\subset\mathbb{R}^{d_{1}}$ and
$\mathcal{B}\subset\mathbb{R}^{d_{2}}$ denote the action spaces of the
platform and user, respectively, where we assume that $\mathcal{B}$ is finite.
Then, at every time step $t=0,1,2,\ldots$,

  1. 1.

The platform generates propositions $Z_{t}\in\mathcal{Z}$.

  2. 2.

The user responds with behavior $B_{t}\in\mathcal{B}$, drawn from the
conditional distribution $q(\cdot|Z_{t})$.

  3. 3.

The platform and user collect payoffs $V(Z_{t},B_{t})$ and $U(Z_{t},B_{t})$,
respectively.

This setup is given on the left side of Figure 1. We use the shorthand
$q:\mathcal{Z}\rightarrow\Delta(\mathcal{B})$ to denote the user’s strategy,
i.e., mappings from propositions $Z$ to behavior distributions $q(\cdot|Z)$
for all $Z\in\mathcal{Z}$. Throughout this work, $\Delta(X)$ denotes the
simplex over a probability space $X$. Furthermore, we assume that the payoffs
$V$ and $U$ as well as the action spaces $\mathcal{Z}$ and $\mathcal{B}$ are
exogeneous, i.e., they are pre-specified. We assume that the payoffs $U$ and
$V$ are bounded and scaled between $[0,1]$.

###### Generating propositions.

To generate propositions, the platform first constructs an estimate of the
user’s strategy $q\in\mathcal{Q}$. In particular, the platform believes that
$q$ belongs to some set $\widehat{\mathcal{Q}}$, which we assume to be finite.
$\widehat{\mathcal{Q}}$ can be thought of as the platform’s hypothesis class,
with each $\hat{q}_{i}\in\widehat{\mathcal{Q}}$ being one of the platform’s
“user models.” The platform constructs its estimate of $q$ using a belief
$\mu_{t}\in\Delta(\widehat{\mathcal{Q}})$ over the hypothesis class
$\widehat{\mathcal{Q}}$. For instance, $\mu_{t}(\hat{q}_{i})=1$ means that the
platform believes $q=\hat{q}_{i}$ with full certainty at time step $t$. When
there is no user model that matches the user’s chosen strategy (i.e.,
$q\not\in\widehat{\mathcal{Q}}$), we say that the platform is misspecified.

At each time step, the platform uses a (proposition) algorithm
$\smash{p:\Delta(\widehat{\mathcal{Q}})\to\Delta(\mathcal{Z})}$ to map its
belief $\mu_{t}$ to a distribution over propositions. That is, at each time
$t$, the platform uses its current belief $\mu_{t}$ to sample a proposition
$Z_{t}\sim p({\cdot};{\mu_{t}})$, as shown on the right side of Figure 1.222
One can think of $\mu_{t}$ as parameters of a machine learning model trained
on the data gathered until time step $t$. Intuitively, the algorithm $p$
captures whether the platform chooses to maximize revenue, social welfare, or
any other objective (based on its current belief $\mu_{t}$).

###### Bayesian updating.

The platform incorporates its observations into its belief using Bayesian
updating. Specifically, at each time step $t$, the platform updates its belief
$\mu_{t}$ to $\mu_{t+1}$ based on the user’s response $B_{t}$ to the
platform’s most recent proposition $Z_{t}$ using Bayes’ rule:

$\displaystyle\mu_{t+1}(\hat{q}_{i})=\frac{\mu_{t}(\hat{q}_{i})\cdot\hat{q}_{i}(B_{t}|Z_{t})}{\sum_{j\in\Omega}\mu_{t}(\hat{q}_{j})\cdot\hat{q}_{j}(B_{t}|Z_{t})},\qquad\forall\
\hat{q}_{i}\in\widehat{\mathcal{Q}}.$ (1)

We assume that the initial belief $\mu_{0}\in\Delta(\widehat{\mathcal{Q}})$
has full support, i.e., assigns a positive probability to every possible model
$\smash{\hat{q}\in\widehat{\mathcal{Q}}}$. Although we assume that the
platform updates its beliefs in a Bayesian way, it is possible to generalize
our findings to other update strategies (e.g., empirical risk minimization).
As we discuss in Section 4.2, Bayesian updating allows us to leverage recent
results and precisely characterize the platform’s limiting behavior as
$t\rightarrow\infty$.

###### Committing to strategies.

Thus far, we have instantiated a repeated, two-player game between a user and
their platform. The platform generates propositions by applying its algorithm
$p$ to its (evolving) belief $\mu_{t}\in\Delta(\widehat{\mathcal{Q}})$ in
order to sample $Z_{t}\sim p({\cdot};{\mu_{t}})$. The user responds with
behaviors $B_{t}\sim q(\cdot|Z_{t})$. Note that, for a fixed action spaces,
payoffs, and initial beliefs $(\mathcal{B},\mathcal{Z},U,V,\mu_{0})$, the
user’s and platform’s actions are fully determined by $q$, $p$, and
$\widehat{\mathcal{Q}}$. We therefore refer to $q$ as the user’s strategy and
the tuple $(p,\widehat{\mathcal{Q}})$ as the platform’s strategy (see Table
1).

In this work, we are interested in how users adapt to their platforms. We
therefore study the setting in which the platform commits to a strategy
$(p,\widehat{\mathcal{Q}})$ at the start of the game, after which the user
chooses their strategy $q$, which may depend on $(p,\widehat{\mathcal{Q}})$.
In order to characterize user adaptation, we study the idealized setting in
which the user has perfect knowledge of $(p,\widehat{\mathcal{Q}})$.

####  3.2 Examples

Our model captures a variety of data-driven settings. For instance, the
interactions between a user and their recommender system (e.g., Netflix or
Facebook) can be viewed as a repeated, two-player game. (Indeed, we provide a
detailed recommender system example in Section 5). Our model also captures
other contexts, such as data-driven hiring and ride-share matching, as
detailed below.

######  Example 3.1 (Hiring example).

Suppose an employer (i.e., the user) uses a data-driven hiring platform to
determine which job candidates to interview. Then, at each time step $t$,
$Z_{t}$ contains the set of candidates at time $t$ and the scores that the
hiring platform assigns to the candidates. $B_{t}$ denotes the employer’s
decisions (i.e., which candidates are interviewed) and the final outcomes
(i.e., who is hired). The employer’s hiring strategy is therefore captured by
$q$. In this context, $V(Z_{t},B_{t})$ is the payoff that the platform
receives based on the scored candidate $Z_{t}$ and the employer’s decisions
$B_{t}$, e.g., it could reflect a pay-per-success scheme, scaling with how
many top-ranked applicants are successfully hired. $U(Z_{t},B_{t})$ is the
employer’s corresponding payoff, e.g., how many people it successfully hires
using the tool.

The hiring platform’s goal is to learn the employer’s preferences so that it
can provide scores attuned to the employer’s needs. It does so by first
assuming that the employer’s decision mechanism $q$ belongs to a hypothesis
class $\widehat{Q}$, which describes the set of employers that the platform
can model. As it receives more data on the employer’s hiring practices, it
updates its belief $\mu_{t}$ about the employer’s preferences. Given its
current belief $\mu_{t}$, the platform generates candidates by sampling from a
distribution $p(\cdot;\mu_{t})$. $p$ the algorithm that the hiring platform
uses. For instance, $p$ might select the candidates it believes the company
will be most likely to hire (according to $\mu_{t}$), or $p$ could be a
bandit-like algorithm that ensures exploration.

######  Example 3.2 (Uber example).

Suppose drivers use a ride-sharing app—say, Uber—to find riders. At each time
step, Uber (i.e., the platform) proposes a ride $Z_{t}$ and the driver (i.e.,
the user) decides whether to accept, reject, or accept then cancel the ride,
as denoted by $B_{t}$. Uber’s payoff from the interaction is $V(Z_{t},B_{t})$,
which could be a constant fraction of the ride’s cost if the driver accepts
it. Similarly, $U(Z_{t},B_{t})$ is the driver’s payoff, which might be zero if
they decline the ride and otherwise depend on the ride payment or whether the
ride takes the driver closer to home, among other factors.

Uber’s goal is to match drivers and riders. To minimize delays, Uber attempts
to learn each driver’s habits and preferences $q$. Specifically, it assumes
that $q$ (i.e., how the driver accepts, declines, or cancels rides) belongs to
some class $\widehat{\mathcal{Q}}$. After observing the driver’s behavior,
Uber updates its belief $\mu_{t}$ about $q$, and then uses its belief along
with its algorithm $p$ to better match riders and drivers. For instance,
whether the platform maximizes revenue, minimizes cancellations, seeks to keep
drivers in their preferred zones, or a combination of these factors is
reflected in $p$.

Table 1: Key concepts and notation from Sections 3 and 4. Object | Symbol |  Description
---|---|---
Proposition space | $\mathcal{Z}$ |  Platform action space, subset of $\mathbb{R}^{d_{1}}$ (exogeneous)
Behavior space | $\mathcal{B}$ |  User action space, finite subset of $\mathbb{R}^{d_{2}}$ (exogenous)
Payoff functions | $U,V$ |  Functions that map $\mathcal{Z}\times\mathcal{B}$ to $\mathbb{R}$ (exogeneous)
User strategy | $q$ |  Mapping $q:\mathcal{Z}\rightarrow\Delta(\mathcal{B})$ such that $B_{t}\sim q(\cdot|Z_{t})$
Hypothesis class | $\widehat{\mathcal{Q}}$ |  Finite set of models $\\{\hat{q}_{i}\\!:\\!i\\!\in\\!\Omega\\}$ that platform uses to estimate $q$
Platform belief | $\mu_{t}$ |  Distribution over $\widehat{\mathcal{Q}}$
Platform algorithm | $p$ |  Function that maps a belief $\mu\in\Delta(\widehat{\mathcal{Q}})$ to a distribution in $\Delta(\mathcal{Z})$ such that $Z_{t}\sim p({\cdot};{\mu_{t}})$

###  4 User strategization

In our model (Section 3), the user selects their strategy $q$ after the
platform has declared its strategy $\smash{(p,\widehat{\mathcal{Q}})}$.
Although our model allows us to analyze a wide range of user behaviors, there
are two types of users of particular interest. The first type—a naive
user—behaves without regard for how their current actions affect future
outcomes by playing actions that maximize their immediate payoff. On the other
hand, a strategic user plans ahead; they adapt their strategy to the
platform’s strategy $(p,\widehat{\mathcal{Q}})$ in order to elicit high
payoffs in the long run. In this way, a strategic user’s behavior is dependent
on $(p,\widehat{\mathcal{Q}})$, whereas a naive user’s behavior remains the
same across different choices of $(p,\widehat{\mathcal{Q}})$. We formalize
these two types of users below and visualize their behavior in Figure 3.

####  4.1 Naive user

At each time step $t$, the naive user chooses the action $B_{t}$ that
maximizes their payoff $U$ under the given proposition $Z_{t}$, as defined
next. If multiple behaviors $B\in\mathcal{B}$ maximize the immediate payoff,
we assume the user chooses between them uniformly at random.

######  Definition 4.1 (Naive user).

The naive user adopts the strategy $q^{\text{BR}}$, defined as

$q^{\text{BR}}(B|Z)\propto\bm{1}\\{B\in\arg\max_{B\in\mathcal{B}}U(Z,B)\\},\qquad\forall\
B\in\mathcal{B},Z\in\mathcal{Z}.$

Importantly, a naive user’s strategy $q^{\text{BR}}$ is independent of the
platform’s strategy; that is, $q^{\text{BR}}$ remains the same across all
choices of $(p,\widehat{\mathcal{Q}})$.

####  4.2 Strategic user

In contrast to a naive user, a strategic user maximizes their long-term
expected payoff. A strategic user does this by first considering how the
platform’s belief $\mu_{t}$ evolves as $t\rightarrow\infty$ if the user adopts
some strategy $q$. The user uses this understanding to predict its payoff
under all possible strategies $q$ as $t\rightarrow\infty$, then selects a
strategy that achieves the highest long-term payoff.

We formalize this idea in two stages. First, we define the notion of a
globally stable set, which tells us how the platform’s beliefs evolve as
$t\rightarrow\infty$ for a given $(q,p,\widehat{\mathcal{Q}})$.

Figure 2:  Convergence of platform beliefs about the user as
$t\rightarrow\infty$. (Left) Suppose the user adopts strategy $q$, and the
platform begins with an initial belief $\smash{\mu_{0}}$. For illustrative
purposes, we visualize the platform’s initial belief using the corresponding
estimate $\smash{\hat{q}^{0}}$, and we use the orange polygon to represent
$\text{ConvexHull}(\widehat{\mathcal{Q}})$. (In this figure, superscripts on
$q$ represent time steps, and subscripts index hypotheses/models in
$\widehat{\mathcal{Q}}$.) As the platform collects data, its estimate evolves,
eventually converging. The beliefs to which the platform converges is given by
the globally stable set, as defined in Definition 4.2; in this figure, we
visualize the globally stable set
$\widehat{\mathcal{Q}}_{\infty}\subset\widehat{\mathcal{Q}}$ as a singleton
set $\widehat{\mathcal{Q}}_{\infty}=\\{\hat{q}^{\infty}\\}$ such that the
platform’s limiting belief under $(q,p,\widehat{\mathcal{Q}})$ is the point-
mass belief $\mu_{\infty}=\delta_{\hat{q}^{\infty}}$. (Right) As formalized in
Definition 4.2, the belief to which the platform converges depends on the
platform’s strategy $\smash{(p,\widehat{\mathcal{Q}})}$ and the user’s
strategy $q$. We illustrate this dependence by visualizing how changing the
platform’s hypothesis class (from $\widehat{\mathcal{Q}}$ to
$\widehat{\mathcal{Q}}^{\prime}$) affects the platform’s limiting belief (from
$\delta_{\hat{q}^{\infty}}$ to $\delta_{\hat{q}^{\prime,\infty}}$).

######  Definition 4.2 (Globally stable set).

A set $\widehat{\mathcal{Q}}_{\infty}\subset\widehat{\mathcal{Q}}$ is
$(q,p,\widehat{\mathcal{Q}})$-globally stable under hypothesis class
$\widehat{\mathcal{Q}}$, algorithm $p$, and user strategy $q$ if and only if,
for any full-support initial belief $\mu_{0}$,

$\mathbb{P}(\mu_{t}(\widehat{\mathcal{Q}}_{\infty})\rightarrow
1)=1\qquad\text{ as }\qquad t\to\infty,$

where the probability above is taken with respect to the dynamics given in
Section 3.

A set $\widehat{\mathcal{Q}}_{\infty}\subset\widehat{\mathcal{Q}}$ is globally
stable if and only if it contains the support of the platform’s limiting
belief (i.e., of $\mu_{t}$ as $t\rightarrow\infty$) under strategies
$(q,p,\widehat{\mathcal{Q}})$. In Section 6, we discuss one way to ascertain
the globally stable set, i.e., the platform’s limiting belief.

Next, we define the platform and user’s expected payoffs.

######  Definition 4.3 (Expected payoffs).

Consider a distribution $r\in\Delta(\mathcal{Z})$ over propositions
$\mathcal{Z}$ and a user strategy $q\in\mathcal{Q}$. Then, the platform’s and
user’s expected payoffs under $(r,q)$ are

$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r,q$ $\displaystyle\coloneqq\mathbb{E}\left[V(Z,B)\right],$
$\displaystyle\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(r,q)$ $\displaystyle\coloneqq\mathbb{E}\left[U(Z,B)-\lambda\cdot
d_{TV}(q(\cdot|Z),q^{\text{BR}}(\cdot|Z))\right],$ (2)

where the expectations are taken with respect to $Z\sim r$ and $B|Z\sim
q(\cdot|Z)$, $d_{\mathcal{Q}}$ is some distance metric over
$\Delta(\mathcal{B})$, and $\lambda\geqslant 0$. The penalty term
$\lambda\cdot d_{TV}(q(\cdot|Z),q^{\text{BR}}(\cdot|Z))$ in (2) captures the
effort that the user expends to deviate from their naive (best-response)
behavior. Equipped with these definitions, we can now define the strategic
user as a user who maximizes their expected payoff under the platform’s worst-
case, limiting behavior. Since different choices of
$(q,p,\widehat{\mathcal{Q}})$ can induce different globally stable sets
(Definition 4.2), we define the strategic user with respect to a function
$S(q,p,\widehat{\mathcal{Q}})$ that maps $(q,p,\widehat{\mathcal{Q}})$ to a
corresponding globally stable set.

######  Definition 4.4 (Strategic user).

Let $S(q,p,\widehat{\mathcal{Q}})$ be a function that maps a user strategy $q$
and platform strategy $(p,\widehat{\mathcal{Q}})$ to a
$(q,p,\widehat{\mathcal{Q}})$-globally stable set
$\widehat{\mathcal{Q}}_{\infty}$, as defined in Definition 4.2. Then, we
define the $S$-strategic user as a user who adopts the strategy
$q_{S}^{*}(p,\widehat{\mathcal{Q}})$, where

$\displaystyle q_{S}^{*}(p,\widehat{\mathcal{Q}})$
$\displaystyle\in\arg\max_{q\in\mathcal{Q}}\min_{\mu\in\Delta(S(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).$ (3)

###### Understanding the definition.

To tease apart Definition 4.4, consider each component of (3). First, recall
from Definition 4.2 that a set of user models $\widehat{\mathcal{Q}}$ is
globally stable if it contains all the user models to which the platform
assigns positive probability as $t\rightarrow\infty$. That is, if the user and
platform adopt strategies $(q,p,\widehat{\mathcal{Q}})$ and $S$ is as defined
in Definition 4.4, the platform’s beliefs as $t\rightarrow\infty$ are
contained in $\Delta(S(q,p,\widehat{\mathcal{Q}}))$. Second, note that
$\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p({\cdot};{{\mu}}),\cdot)$ is the user’s expected payoff if the
platform uses algorithm $p$ to generate propositions under belief $\mu$.
Putting these two observations together,

$\min_{\mu\in\Delta(S(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),$

is the $S$-strategic user’s envisioned worst-case expected payoff as
$t\rightarrow\infty$. The user then chooses the strategy $q\in\mathcal{Q}$
that maximizes this worst-case, limiting payoff. Therefore, a $S$-strategic
user maximizes their worst-case limiting payoff under the chosen strategies
$(q,p,\widehat{\mathcal{Q}})$ and mapping $S$.

Importantly, a strategic user pays attention to the platform’s strategy
$(p,\widehat{\mathcal{Q}})$ whereas a naive user’s $q^{\text{BR}}$ is the same
regardless of the platform’s chosen strategy. We illustrate the differences
between naive and strategic users in Figure 3.

Figure 3:  Illustration of a naive user (Section 4.1) and a strategic user
(Section 4.2). (Left) The (convex hull of the) platform’s hypothesis class
$\widehat{\mathcal{Q}}$ is given by the orange polygon. The naive user’s
strategy $q^{\text{BR}}$ is given by the solid green dot. As in Figure 2, the
platform’s estimate of $q^{\text{BR}}$ evolves as $t\rightarrow\infty$; we
visualize the limiting estimate as $\hat{q}_{i}=\hat{q}^{\text{BR},\infty}$.
(Right) The strategic user considers their payoff under the platform’s
limiting estimate, i.e., $\smash{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}^{\text{BR},\infty}}},q^{\text{BR}})}$ and finds that
they can instead adopt the strategy $q^{*}(p,\widehat{\mathcal{Q}})$ that
leads the platform to a belief (and in turn, a proposition distribution) that
is more favorable for the user, i.e., $\smash{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}^{*,\infty}}},q^{*}(p,\widehat{\mathcal{Q}}))}>\smash{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\delta_{\hat{q}^{\text{BR},\infty}}},q^{\text{BR}})}$.

###### Remarks on globally stable sets.

A few remarks are in order. First, there is no unique globally stable set, in
general. For instance, the entire hypothesis class $\widehat{\mathcal{Q}}$ is
trivially a globally stable set because $\mu_{t}(\widehat{\mathcal{Q}})=1$ for
all $t$. More fine-grained stable sets provide stronger analyses. We will show
in Section 6 that there is a principled way to obtain rather fine-grained
globally stable sets.

Second, in some cases, we will show the existence a globally stable singleton
set, i.e., $S^{\infty}(q,p,\widehat{\mathcal{Q}})=\\{\hat{q}^{\infty}\\}$.
Figure 2 illustrates on such example. In this case, the platform converges
(almost surely) to the point mass belief
$\mu_{\infty}=\delta_{\hat{q}^{\infty}}$ that depends on
$(q,p,\widehat{\mathcal{Q}})$, and thus that the platform generates
propositions from $p({\cdot};{{\mu_{\infty}}})$. As we discuss later on, we
cannot always guarantee that the platform converges to a single unique belief
$\mu_{\infty}$. When a unique limiting belief does not exist, the globally
stable set is our next best tool, as it characterizes the set of possible
limiting beliefs.

Finally, even though strategization is defined with respect to a function $S$,
when $S$ is clear from context we omit it and say “strategic user” instead of
“$S$-strategic user.” Similarly, we omit $S$ or $\widehat{\mathcal{Q}}$ from
our notation for the strategic user’s strategy
$q^{*}_{S}(p,\widehat{\mathcal{Q}})$ (see (3)) when clear from context.

###  5 Stylized Example

What are the implications of user strategization? Is it good or bad for
platforms? In this section, we consider a styled setting that allows us to
answer these questions. Our goal is to illustrate and motivate our main
results, which we establish in their full generality in Section 6.

At a high level, we consider a simple recommender system that partitions its
users into “types” (e.g., comedy lovers and horror lovers) and recommends
content based on these types. The platform’s payoff is high when the user
engages with the recommendations, and the user’s payoff depends on both their
engagement and their personal taste. Within this setting, we show that:

  1. 1.

The user is incentivized to be strategic, i.e., there is a user strategy that
guarantees higher payoff than the naive (best-response) strategy
$q^{\text{BR}}$ defined in Definition 4.1 (Proposition 5.2).

  2. 2.

Whenever the recommendation strategy $(p,\widehat{\mathcal{Q}})$ is fixed, the
platform’s payoff is never lower when the user behaves strategically than it
is when the user is naive (Proposition 5.3).

  3. 3.

At the same time, user strategization can indirectly hurt the platform.
Specifically, suppose that the platform wishes to update its recommendation
algorithm from $p$ to a counterfactual algorithm $p_{\text{CF}}$. We show that
the data that a platform obtains under $p$ cannot be used to reliably make
inferences under $p_{\text{CF}}$ (Proposition 5.4).

  4. 4.

In the same vein, user strategization makes it harder to predict the effect of
design choices. Specifically, we show that, when the user is strategic,
expanding the hypothesis class $\widehat{\mathcal{Q}}$ can unexpectedly hurt
the platform’s payoff. That is, if the platform uses a richer class of user
models to estimate the user’s preferences, the platform’s payoff can actually
decrease when the user is strategic. (Proposition 5.5)

Figure 4: The recommender system that we consider in our stylized example
(Section 5). The platform’s hypothesis class consists of three user models.
Under one model, the user watches exclusively horror movies; under the other,
exclusively comedies; and under the last model, the user is equally interested
in comedy and horror. The platform represents the user as a convex combination
of these models, which dictates the recommendations that the platform gives.
For example, as shown at the bottom of the figure, if the platform believes
the user is of type 1, then the platform shows the user horror movies with 99%
probability.

####  5.1 A simple recommender system

Consider a platform that recommends from a finite set of items $\mathcal{Z}$
and allows the user to click or ignore the recommended item (i.e., let
$\mathcal{B}=\\{0,1\\}$). Let the platform’s and user’s payoffs be

$\displaystyle V(Z,B)=B,\qquad U(Z,B)=B\cdot a(Z),$ (4)

for all $Z\in\mathcal{Z}$ and $B\in\mathcal{B}$, where
$a:\mathcal{Z}\rightarrow\\{-1,1\\}$ is a fixed function that encodes the
user’s affinity for item $Z$. As such, the platform gains utility when the
user clicks on any recommendation, and the user gets (possibly negative)
utility $a(Z)$ from clicking on an item $Z$, and $0$ from not clicking. We
summarize our setup in Fig. 4.

###### User types and the platform’s hypothesis class.

Suppose that there are two disjoint types of content on the platform,
$\mathcal{Z}_{1}$ and $\mathcal{Z}_{2}$ (e.g., horror movies and comedies)
with $\mathcal{Z}_{2}=\mathcal{Z}\setminus\mathcal{Z}_{1}$. Let there be three
types of users: those who prefer $\mathcal{Z}_{1}$ (i.e.,
$a(Z)\leqslant\bm{1}\\{Z\in\mathcal{Z}_{1}\\}$), those who prefer
$\mathcal{Z}_{2}$ (i.e., $a(Z)\leqslant\bm{1}\\{Z\in\mathcal{Z}_{2}\\}$), and
those who fall into neither of the two former categories. Note that
$a(Z)\leqslant\bm{1}\\{Z\in\mathcal{Z}_{1}\\}$ means that the user definitely
does not enjoy anything outside of $\mathcal{Z}_{1}$ and may sometimes enjoy
content in $\mathcal{Z}_{1}$.

The platform is aware of the three user types, but it does not know the
correct partitioning $(\mathcal{Z}_{1},\mathcal{Z}_{2})$ and instead believes
that the two kinds of content are $(\mathcal{Z}_{A},\mathcal{Z}_{B})$. This
setting is common and can be generalized to capture instances in which the
platform does not account for all possible users (e.g., there are “minority”
users that do not follow mainstream trends).

The platform thus estimates user behavior using the hypothesis class
$\widehat{\mathcal{Q}}=\\{\hat{q}_{1},\hat{q}_{2},\hat{q}_{3}\\}$, where

$\hat{q}_{i}(B=1|Z)=\begin{cases}(1-\gamma)\bm{1}\\{Z\in\mathcal{Z}_{A}\\}&\text{if
}i=1,\\\ (1-\gamma)\bm{1}\\{Z\in\mathcal{Z}_{B}\\}&\text{if }i=2,\\\
(1-\gamma)\bm{1}\\{Z\in\mathcal{Z}\\}&\text{if }i=3\end{cases}\qquad\forall\
Z\in\mathcal{Z},$ (5)

and $\gamma>0$ is a constant that captures the fact that users will not click
on all items of a given type.

Intuitively, the platform believes there are three possible users: users tend
to like either only content in $\mathcal{Z}_{A}$, or only content in
$\mathcal{Z}_{B}$, or all content. Formally, this means that under the user
model $\hat{q}_{1}$ the user only clicks on items in $\mathcal{Z}_{A}$ and
does so with probability $1-\gamma$. Under $\hat{q}_{2}$, the user behaves
analogously toward $\mathcal{Z}_{B}$. Under $\hat{q}_{3}$, the user clicks on
any item with probability $1-\gamma$.

###### Recommendation algorithm.

Finally, suppose that the platform uses a simple algorithm $p$ that with small
probability $\varepsilon$ (which we specify later) recommends a random item
$Z\in\mathcal{Z}$, and otherwise recommends $Z_{i}$ with probability
proportional to its likelihood of inducing a “click” from the user (under the
platform’s current belief about the user). That is, for all $Z\in\mathcal{Z}$,

$\displaystyle
p({Z};{\mu})\coloneqq\underbrace{\varepsilon\cdot\frac{1}{|\mathcal{Z}|}}_{\text{Uniform
w.p.
$\varepsilon$}}+\underbrace{(1-\varepsilon)\cdot\frac{\sum_{\hat{q}_{i}\in\widehat{\mathcal{Q}}}\mu(\hat{q}_{i})\cdot\hat{q}_{i}(B=1|Z)}{\sum_{Z\in\mathcal{Z}}\sum_{\hat{q}_{i}\in\widehat{\mathcal{Q}}}\mu(\hat{q}_{i})\cdot\hat{q}_{i}(B=1|Z)}}_{\text{
Proportional to click probability $\hat{q}(B=1|Z)$ w.p. $1-\varepsilon$ }},$
(6)

where recall from Section 3 that $\mu$ is the platform’s belief, and so
$\mu(\hat{q})$ is the probability that the platform assigns to the user’s
strategy being $\hat{q}$. We visualize this setup in Fig. 4.

####  5.2 User behavior

Now, consider a user of the first type, i.e., a user for which
$a(Z)\leqslant\bm{1}\\{Z\in\mathcal{Z}_{1}\\}.$ Define the set
$\mathcal{Z}^{+}=\\{Z:a(Z)=1\\}\subset\mathcal{Z}_{1}$ as the items that the
user enjoys. Recall that a user presented with a recommendation $Z_{t}$
responds with behavior $B_{t}$ sampled from their behavior strategy
$q(\cdot|Z_{t})$, where this behavior strategy depends on whether the user is
naive or strategic, as follows.

###### Naive users.

In this setting, a naive user will click on items for which they have positive
affinity (i.e., for which $a(Z)=1$), and ignore items for which they have
negative affinity, i.e.,

$\displaystyle q^{\text{BR}}(B=1|Z)=\bm{1}\\{a(Z)\geqslant 0\\}\ \forall\
Z\in\mathcal{Z}.$ (7)

Figure 5: Naive and strategic user strategies in our stylized example (Section
5). We consider a user whose affinity $a(Z)$ is encoded by items’ opacity in
the Figure above. A naive strategy for this user (left) would click on item
$Z$ if and only if $a(Z)=1$. This strategy would result in the platform
modeling the user as the “clicks on anything” user $\hat{q}_{3}$ (see Fig. 4),
and thus serve a feed that is 50% comedy and 50% horror. If the user is
strategic (right), they recognize that the naive strategy is suboptimal, and
they avoid clicking on “outlier” comedy videos that they enjoy. The platform
thus estimates the user as a “clicks only on horror” user $\hat{q}_{1}$, and
serves a feed that better suits the user. Notably, both user and platform
payoffs are higher when the user is strategic.

###### Strategic users.

A strategic user, on the other hand, chooses a strategy that elicits the
highest long-term payoffs. For example, they might not click on an item $Z$
that they like (i.e., for which $a(Z)=1$) in order to influence the
distribution of recommended items in the future. To characterize the strategic
user, we first need to understand the limiting beliefs of the platform.

######  Proposition 5.1.

Let $\widehat{\mathcal{Q}}$ be the hypothesis class defined by (5). Consider a
user strategy $q$ and a platform algorithm $p$ such that $p({\cdot};{\mu})$
has full support for all $\mu\in\Delta(\widehat{\mathcal{Q}})$. Let
$\text{supp}(q)=\\{Z\in\mathcal{Z}:q(B=1|Z)>0\\}$. If $|\text{supp}(q)|>0$,
then the following function $S$ maps $(q,p,\widehat{\mathcal{Q}})$ to a
globally stable set:

$\displaystyle
S(q,p,\widehat{\mathcal{Q}})\coloneqq\\{\hat{q}_{i^{*}}\\},\qquad\text{where}\qquad
i^{*}=\begin{cases}1&\text{if }|\text{supp}(q)\cap\mathcal{Z}_{B}|=0,\\\
2&\text{if }|\text{supp}(q)\cap\mathcal{Z}_{A}|=0,\\\
3&\text{otherwise.}\end{cases}$

In other words, the platform’s limiting belief is
$\mu_{\infty}=\delta_{\hat{q}_{i^{*}}}$.

###### Proof.

See Section B.1. ∎

With this established, we show that unless the content that the user likes
belongs entirely to $\mathcal{Z}_{A}$ or to $\mathcal{Z}_{B}$ (i.e.,
$\mathcal{Z}^{+}\subset\mathcal{Z}_{A}$ or
$\mathcal{Z}^{+}\subset\mathcal{Z}_{B}$), then strategization strictly
improves the user’s utility.

######  Proposition 5.2.

Consider the setting described in Section 5.1, and suppose that the platform’s
partition $(\mathcal{Z}_{A},\mathcal{Z}_{B})$ is not “orthogonal” to the
user’s preferences, i.e.,

$\frac{|\mathcal{Z}^{+}\cap\mathcal{Z}_{A}|}{|\mathcal{Z}_{A}|}\neq\frac{|\mathcal{Z}^{+}\cap\mathcal{Z}_{B}|}{|\mathcal{Z}_{B}|}.$

Then, for sufficiently small $\varepsilon$ in (6), a strategic user’s
$q^{*}=q^{\text{BR}}$ if and only if $\mathcal{Z}^{+}\subset\mathcal{Z}_{A}$
or $\mathcal{Z}^{+}\subset\mathcal{Z}_{B}$.

###### Proof.

See Section B.2. In short, when the user is naive and the platform is
misspecified, the platform learns $\mu=\delta_{\hat{q}_{3}}$ by Proposition
5.1 and thus recommends a uniform distribution over all items. If either
$\mathcal{Z}_{A}$ or $\mathcal{Z}_{B}$ is closer to $\mathcal{Z}_{1}$, the
strategic user can improve their utility by restricting their clicks to only
the set $\mathcal{Z}^{+}\cap\mathcal{Z}_{A}$ (which would lead to the platform
recommending from $\mathcal{Z}_{A}$) or $\mathcal{Z}^{+}\cap\mathcal{Z}_{B}$
(which would lead to the platform recommending from $\mathcal{Z}_{B}$). ∎

####  5.3 User strategization improves platform payoffs

We now examine the impact of strategic behavior on the platform. We begin by
showing that, in our stylized example, user strategization improves (or at
least does not hurt) the platform’s payoffs.

######  Proposition 5.3.

Consider the setting described in Section 5.1. The platform’s payoff is as
least as high when the user is strategic as when the user is naive.

###### Proof.

See Section B.3. Informally, the user only strategizes to get “better” content
in the long term, and the platform benefits from this behavior because it
receives a positive payoff every time the user clicks. ∎

Note that Proposition 5.3 holds regardless of the platform’s choice of
strategy $(p,\widehat{\mathcal{Q}})$, and depends only on the structure of the
payoff functions $U$ and $V$.

####  5.4 User strategization results in unexpected phenomena

Suppose that, having deployed algorithm $p$ and converged to the limiting
belief $\mu_{\infty}$ given by Proposition 5.1, the platform considers
changing its algorithm to downweight toxic content. Specifically, the platform
considers replacing $p$ with a counterfactual algorithm $p_{\text{CF}}$:

$\displaystyle p_{\text{CF}}(Z;\mu)\propto\textsc{toxicity}(Z)\cdot
p({Z};{\mu}),$ (8)

where for some $\alpha\in(0,1)$, the function
$\textsc{toxicity}(Z)\in\\{\alpha,1\\}$ discounts content $Z$ that is toxic.
We show that strategic behavior (on the part of the user) can corrupt the
platform’s data so that data gathered under $p$ cannot be used to make
reliable inferences under $p_{\text{CF}}$.

###### Unreliable counterfactual inferences.

A natural way for the platform to gauge whether using the algorithm
$p_{\text{CF}}$ is a good idea is to predict its (counterfactual) payoff under
$(p_{\text{CF}},\widehat{\mathcal{Q}})$. Formally, the platform tries to
estimate $\smash{{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{\text{CF}},\widehat{\mathcal{Q}})}$, where for any $p$ we
define ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p,\widehat{\mathcal{Q}})$ as

${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p,\widehat{\mathcal{Q}})\coloneqq\max_{\mu\in\Delta(S(q^{*},p,\widehat{\mathcal{Q}}))}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p({\cdot};{\mu}),q^{*}(p,\widehat{\mathcal{Q}})).$ (9)

We recall that $\smash{q^{*}(p,\widehat{\mathcal{Q}})}$ characterizes how the
strategic user behaves in response to the platform strategy
$\smash{(p,\widehat{\mathcal{Q}})}$. Of course, the platform does not have
access to $\smash{{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{\text{CF}},\widehat{\mathcal{Q}})}$, as it does not know what
the user’s strategy would be in response to
$\smash{(p_{\text{CF}},\widehat{\mathcal{Q}})}$, and so it must instead
predict its payoff using its current user model $\hat{q}_{i^{*}}$ (collected
under $p$). In other words, it computes

$\widehat{V}(p_{\text{CF}},\widehat{\mathcal{Q}})\coloneqq\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{\text{CF}}(\cdot;\delta_{\hat{q}_{i^{*}}}),\hat{q}_{i^{*}}),$ (10)

where we recall that $\hat{q}_{i^{*}}$ is the platform’s limiting belief from
playing the algorithm $p$.

We show below that for some choices of the toxicity function, the above
approach (10) produces a drastically wrong estimate of the platform’s long-run
utility under $p_{\text{CF}}$. In particular, this mis-estimation might cause
the platform to think that switching to $p_{\text{CF}}$ would lower the
platform’s payoffs when it would actually do the opposite.

######  Proposition 5.4.

Consider the setting described in Section 5.1, and the counterfactual
algorithm $p_{\text{CF}}$ given by (8). For any content partitioning
$(\mathcal{Z}_{A},\mathcal{Z}_{B})$ where
$|\mathcal{Z}_{A}|,|\mathcal{Z}_{B}|\geqslant 4$, there exists an affinity
function $a(Z)$ (see (4)), constants $\gamma>0$ (see (5)), $\varepsilon>0$
(see (6)),› and a function $\textsc{toxicity}:\mathcal{Z}\to\\{\alpha,1\\}$
such that applying (10) simultaneously yields the following outcomes:

  1. (a)

the platform correctly predicts its own utility under $p$, i.e.,
$\widehat{V}(p,\widehat{\mathcal{Q}})={\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p,\widehat{\mathcal{Q}})$;

  2. (b)

the platform thinks its payoff will decrease if it switches to algorithm
$p_{\text{CF}}$, i.e.,
$\widehat{V}(p_{\text{CF}},\widehat{\mathcal{Q}})<{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p,\widehat{\mathcal{Q}})$;

  3. (c)

in reality, the platform’s payoff will increase if it switches to
$p_{\text{CF}}$, i.e., ${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{\text{CF}},\widehat{\mathcal{Q}})>{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p,\widehat{\mathcal{Q}}).$

###### Proof.

See Section B.4. Intuitively, when the user strategizes and only engages with
items from $\mathcal{Z}^{+}\cap\mathcal{Z}_{A}$, the platform has no
information about how much the user likes items from $\mathcal{Z}_{B}$. If,
under $p_{\text{CF}}$, the user switches to engaging only with items from
$\mathcal{Z}^{+}\cap\mathcal{Z}_{B}$ (say, due to elements in
$\mathcal{Z}^{+}\cap\mathcal{Z}_{A}$ being marked as toxic), the platform’s
predicted payoffs will be far from the true ones. ∎

We generalize (and in fact, strengthen) this result in Section 6 (Proposition
6.13).

###### Expanding $\widehat{\mathcal{Q}}$ can hurt the platform when users are
strategic.

To further illustrate the counterintuitive phenomena induced by user
strategization, we also demonstrate that expanding the hypothesis class of
user models can actually lower the platform’s payoff. This finding is
unexpected, as considering a richer class of models typically does not hurt a
learning algorithm.

######  Proposition 5.5.

Consider the setting described in Section 5.1. For any partitioning
$(\mathcal{Z}_{A},\mathcal{Z}_{B})$ of $\mathcal{Z}$ there exists an affinity
function $a(Z)$ (see (4)), constants $\gamma>0$ (see (5)), $\varepsilon>0$
(see (6)), and a user model $\hat{q}_{4}$ such that when $\hat{q}_{4}$ is
added to hypothesis class $\widehat{\mathcal{Q}}$, the platform’s payoff under
user strategization decreases.

###### Proof.

See Section B.5. Intuitively, the platform can inadvertently eliminate the
user’s means of strategization, by adding a candidate user model $\hat{q}_{4}$
that is more similar to $q^{*}$ than $\hat{q}_{i^{*}}$ is to $q^{*}$, but
whose corresponding distribution over content $p(\cdot;\delta_{\hat{q}_{4}})$
is unfavorable for the user. This incentivizes the user to switch to a
strategy that lowers the platform’s payoff. ∎

We prove a general version of this result in Section 6 (Proposition 6.14).

###  6 User strategization and its discontents

In this section, we present our main results. These results generalize and
strengthen our findings from Section 5 and can be summarized as follows.

  1. 1.

In Section 6.2, we show that one can recover a globally stable set using a
result from [FII20a]. Recalling the definition of strategization, this result
allows us to characterize the platform’s beliefs as $t\rightarrow\infty$ and,
as a result, how a strategic user behaves.

  2. 2.

In Section 6.3, we show that user strategization can help the platform.
Specifically, when user and platform payoffs are sufficiently aligned, then
user strategization improves both user and platform outcomes under a fixed
platform strategy $(p,\widehat{\mathcal{Q}})$.

  3. 3.

In Section 6.4, we find that user strategization can mislead the platform when
the platform makes changes to $(p,\widehat{\mathcal{Q}})$. In particular, when
a user is strategic, (a) the data that a platform obtains under its current
algorithm $p$ cannot reliably predict the platform’s payoff under a different
algorithm $p_{\text{CF}}$, even if $p$ and $p_{\text{CF}}$ are close; and (b)
counter to what the platform might expect, expanding the hypothesis class
$\widehat{\mathcal{Q}}$ can lower the platform’s payoff.

  4. 4.

In Section 6.5, we show that, in contrast to when users behave strategically,
it is straightforward for the platform to anticipate how changing $(p,\Omega)$
affects its payoff when users behave naively. This finding begs the question:
When are users incentivized to behave naively?

####  6.1 Preliminaries

We now introduce definitions and assumptions that we use in the remainder of
the section.

###### Definitions.

For any two probability measures $\Pi_{1}$ and $\Pi_{2}$ defined on a
measurable space $(\Omega,\mathcal{F})$ with probability mass (or density)
functions $\pi_{1}$ and $\pi_{2}$, the Kullback-Leibler divergence and total
variation distance are given by

$\displaystyle\text{KL}(\Pi_{1},\Pi_{2})$
$\displaystyle\coloneqq\mathbb{E}_{x\sim\pi_{1}}\left[\log\left(\frac{\pi_{1}(x)}{\pi_{2}(x)}\right)\right]\quad\text{(when
$\Pi_{1}$ is absolutely continuous w.r.t. $\Pi_{2}$)},$
$\displaystyle\text{TV}(\Pi_{1},\Pi_{2})$
$\displaystyle\coloneqq\sup_{A\in\mathcal{F}}\left|\Pi_{1}(A)-\Pi_{2}(A)\right|.$

Recall that $p:\Delta(\widehat{\mathcal{Q}})\to\Delta(\mathcal{Z})$ denotes
the platform’s algorithm, i.e., a map between its belief about the user and
the distribution over propositions it plays. We quantify the distance between
two algorithms using their maximum total variation distance; that is, we let

$d_{\mathcal{P}}(p_{1},p_{2})\coloneqq\sup_{\mu\in\Delta(\widehat{\mathcal{Q}})}\text{TV}(p_{1}(\cdot;\mu),p_{2}(\cdot;\mu)).$

Recall that $q$ denotes the user’s strategy. Let $p(\cdot;\mu)\times q$ denote
the joint distribution of $(Z,B)$ when the platform’s propositions are drawn
according to $Z\sim p(\cdot;\mu)$ and the user’s behavior is given by $B\sim
q(\cdot|Z)$. Similarly, for any user model
$\hat{q}_{i}\in\widehat{\mathcal{Q}}$, let $p(\cdot;\mu)\times\hat{q}_{i}$
denote the joint distribution of $(Z,B)$ when $Z\sim p(\cdot;\mu)$ and the
user’s behavior is given by $B\sim\hat{q}_{i}(\cdot|Z)$.

For a fixed proposition distribution $p({\cdot};{\mu})$ and a fixed user
strategy $q$, we say that the user model $\hat{q}_{i}$ strictly dominates the
user model $\hat{q}_{j}$ when $p(\cdot;\mu)\times\hat{q}_{i}$ better explains
$p(\cdot;\mu)\times q$ than $p(\cdot;\mu)\times\hat{q}_{j}$ does (in the
information-theoretic sense described below).

######  Definition 6.1 (Strict KL dominance).

A user model $\hat{q}_{i}$ strictly KL-dominates $\hat{q}_{j}$ at
$(p(\cdot;\mu),q)$, as denoted by
$\hat{q}_{i}\succ^{q}_{p(\cdot;\mu)}\hat{q}_{j}$ if and only if
$\text{KL}(p(\cdot;\mu)\times
q,p(\cdot;\mu)\times\hat{q}_{i})<\text{KL}(p(\cdot;\mu)\times
q,p(\cdot;\mu)\times\hat{q}_{j})$.

###### Pervasive assumptions.

We now lay out the assumptions that we will use in the remainder of this work.
Throughout the entire section (even when not explicitly mentioned), we make
the following two assumptions adapted from [FII20a].

######  Assumption 6.2 ([FII20a]).

The distributions $p({\cdot};{\mu})\times q$ and
$p({\cdot};{\mu})\times\hat{q}_{i}$ are continuous Radon-Nikodym derivatives
with respect to some $\sigma$-finite measure $\nu$ on
$\mathcal{Z}\times\mathcal{B}$. When $\mathcal{Z}$ is discrete (resp.,
continuous), $\nu$ is a product of the counting (resp., Lebesgue) measure on
$\mathcal{Z}$ and the counting measure on $\mathcal{B}$. In particular,
$p({\cdot};{\mu})$, $q(\cdot|Z)$, and $\hat{q}_{i}(\cdot|Z)$ are all well-
defined probability densities.

######  Assumption 6.3 ([FII20a]).

The platform’s recommendation algorithm $p$ and hypothesis class
$\widehat{\mathcal{Q}}$ satisfy the following three conditions:

  1. 1.

(Support). For any user strategy $q$, user model $\hat{q}$, and
$Z\in\mathcal{Z}$, $\mathrm{supp}\ q(\cdot|Z)\subset\mathrm{supp}\
\hat{q}(\cdot|Z)$.

  2. 2.

(Bounded likelihood ratios). There exists a $\nu$-integrable function $h(Z,B)$
such that

$\sup_{\mu\in\Delta(\widehat{\mathcal{Q}})}\max_{\hat{q}_{1},\hat{q}_{2}\in\widehat{\mathcal{Q}}}\frac{\hat{q}_{1}(B|Z)}{\hat{q}_{2}(B|Z)}\cdot
p({Z};{\mu})\cdot q(B|Z)\leqslant h(B,Z)\text{ for all
}B,Z\in\mathcal{B}\times\mathcal{Z}.$

  3. 3.

(Belief continuity). For each user model $\hat{q}\in\widehat{\mathcal{Q}}$,
there exists a neighborhood $\mathcal{N}\ni\delta_{\hat{q}}$ such that for all
$Z\in\mathcal{Z}$ and $\mu\in\mathcal{N}$, the function $p(Z;\mu)$ is
continuous in $\mu$.

Assumption 6.2 simply ensures that the probability distributions we are
dealing with are well-defined, while Assumption 6.3 establishes (mild)
conditions under which we can characterize the platform’s limiting belief
(which the rest of our analysis relies on).

###### Regularity assumptions.

In the coming sections, we also make certain assumptions about the platform
payoff, algorithm, and hypothesis class being well-behaved. Rather than being
necessary for our negative results, these assumptions (Assumptions 6.6, 6.4
and 6.5) actually strengthen them. In particular, we will show (in Section
6.4) that in spite of these regularity conditions, platform payoffs are still
poorly behaved and unpredictable when users are strategic. Unlike Assumptions
6.2 and 6.3, we explicitly reference the following assumptions when they are
in place.

######  Assumption 6.4 (Payoff landscape).

For any distribution $r\in\Delta(\mathcal{Z})$ and user behavior $q$, and for
any $\varepsilon>0$, there exists $r^{\prime}\in\Delta(\mathcal{Z})$ such that
$\text{TV}(r,r^{\prime})<\varepsilon$ and $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r,q)\neq\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(r^{\prime},q)$.

######  Assumption 6.5 (Well-behaved algorithm).

We call an algorithm $p:\Delta(\widehat{\mathcal{Q}})\to\Delta(\mathcal{Z})$
well-behaved if it maps similar beliefs $\mu$ (in terms of the corresponding
user models) to similar recommendation distributions $p(\cdot;\mu)$, i.e., if

$d_{\mathcal{P}}(p(\cdot;\mu_{1}),p(\cdot;\mu_{2}))\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]\qquad\forall\
\mu_{1},\mu_{2}\in\Delta(\widehat{\mathcal{Q}}).$

######  Assumption 6.6 (Hypothesis class expansion).

A setup $(\mathcal{Z},\mathcal{B},V,p,\widehat{\mathcal{Q}})$ satisfies the
hypothesis class expansion assumption if for any fixed user strategy $q$ any
two hypothesis classes
$\widehat{\mathcal{Q}}_{1},\widehat{\mathcal{Q}}_{2}\subset\widehat{\mathcal{Q}}$
such that $\widehat{\mathcal{Q}}_{1}\subset\widehat{\mathcal{Q}}_{2}$, and a
globally stable set function $S$ (as defined in Definition 4.2),

$\min_{\mu\in S(q,p,\widehat{\mathcal{Q}}_{1})}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\mu),q)\leqslant\min_{\mu\in
S(q,p,\widehat{\mathcal{Q}}_{2})}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\mu),q).$

In other words, for a fixed user strategy $q$, the platform cannot decrease
its payoff by expanding its hypothesis class.

####  6.2 Platforms converge to beliefs that best approximate user in KL-sense

We now present an intermediate result that lets us characterize user
strategization. Specifically, recall that strategic users plan ahead using a
globally stable set (Definition 4.2), a set of user models
$\smash{S^{\infty}\subset\widehat{\mathcal{Q}}}$ that almost surely contains
the support of the limiting belief. To characterize the globally stable set,
we use a concept introduced by [FII20a] known as the iterated elimination of
dominated states, wherein, given a subset
$\smash{\widehat{\mathcal{Q}}^{\prime}\subset\widehat{\mathcal{Q}}}$, one
eliminates user models $\hat{q}_{j}$ that are strictly KL-dominated by another
user model $\hat{q}_{i}$ in the set (according to Definition 6.1).

######  Definition 6.7 (Iterated elimination of dominated parameters).

Consider a platform strategy $(p,\widehat{\mathcal{Q}})$ and user strategy
$q$. Define the elimination operator $R:2^{\widehat{\mathcal{Q}}}\to
2^{\widehat{\mathcal{Q}}}$ as

$\displaystyle
R(\widehat{\mathcal{Q}}^{\prime})=\\{\hat{q}_{j}\in\widehat{\mathcal{Q}}^{\prime}:\
\not\exists\ \hat{q}_{i}\in\widehat{\mathcal{Q}}^{\prime}\text{ such that
}\hat{q}_{i}\succ^{q}_{p(\cdot;\mu)}\hat{q}_{j}\ \forall\
\mu\in\Delta(\widehat{\mathcal{Q}}^{\prime})\\}.$

Let $R^{0}(\widehat{\mathcal{Q}})=\widehat{\mathcal{Q}}$ and recursively
define $R^{n}(\widehat{\mathcal{Q}})=R(R^{n-1}(\widehat{\mathcal{Q}}))$.
Finally, define
$S^{\infty}(q,p,\widehat{\mathcal{Q}})=\cap_{n=1}^{\infty}R^{n}(\widehat{\mathcal{Q}})$.

[FII20a] show that the fixed point of the elimination operator
$S^{\infty}(q,p,\widehat{\mathcal{Q}})$ is a globally stable set, i.e., the
platform converges to the parameters that best approximate $q$ in a KL-sense.

######  Theorem 6.8 (Theorem [FII20a]).

For algorithm $p$ and user strategy $q$, $S^{\infty}_{p,q}(\Omega)$ is
$(p,q)$-globally stable.

Theorem 6.8 allows us to characterize strategic users. Suppose, for example,
that given any user strategy $q$, the set
$S^{\infty}(q,p,\widehat{\mathcal{Q}})$ contains a single element
$\hat{q}^{*}(q)$. In this case, we can be certain that the platform’s belief
converges to $\delta_{\hat{q}^{*}(q)}$ as $t\rightarrow\infty$. A
$S^{\infty}$-strategic user would then choose the strategy $q$ that maximizes
their limiting payoff $\smash{\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p({\cdot};{\delta_{\hat{q}^{*}(q)}}),q)}$.

In many cases, $\smash{S^{\infty}(q,p,\widehat{\mathcal{Q}})}$ reduces to a
single element, called the Berk-Nash equilibrium [EP16a]. In general, however,
$\smash{S^{\infty}(q,p,\widehat{\mathcal{Q}})}$ can contain more than one
element. In these cases, Theorem 6.8 tells us that the platform’s proposition
distribution as $t\rightarrow\infty$ is contained within the set
$\\{p(\cdot;\mu):\mu\in\Delta(S^{\infty}(q,p,\widehat{\mathcal{Q}}))\\}$.

####  6.3 User strategization can help the platform

Our first main result shows that user strategization can improve the
platform’s payoff $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{V}$.
This occurs when the payoffs of the user and platform are sufficiently
aligned.

To see why this might be the case, consider YouTube. YouTube would like to
engage and retain users (by serving users good recommendations) while ensuring
the profitability of their platform. Although users on YouTube may not care
about the platform’s profitability, they do want good recommendations. In this
way, there is some alignment between the user and platform payoff. Users on
YouTube often have an idea of how the YouTube algorithm works and, in
response, adapt to the algorithm in order to elicit better recommendations.
This strategization can ultimately help the platform by improving their
recommendations and therefore increasing user engagement.

The following result (whose interpretation we discuss below) corroborates this
relationship, showing that user strategization can increase the platform’s
payoffs.

######  Proposition 6.9.

Consider a platform strategy $(p,\widehat{\mathcal{Q}})$ and suppose that
$U(B,Z)$ has a unique maximizer in $\mathcal{B}$ for all $Z$. For a user
strategy $q$, let $\widetilde{V}(q)$ be the platform’s worst-case limiting
payoff,

$\displaystyle\widetilde{V}(q)\coloneqq\min_{\mu\in\Delta(S^{\infty}(q,p,\widehat{\mathcal{Q}}))}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\mu),q),\qquad\forall q\in\mathcal{Q},$ (11)

where $S^{\infty}$ is defined in Definition 6.7. Then, user strategization
strictly improves the platform’s worst-case limiting payoff if

$\displaystyle\widetilde{V}\left(\arg\max_{q\in\mathcal{Q}}\min_{\mu\in\Delta(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)\right)$
$\displaystyle>\widetilde{V}\left(\arg\max_{q\in\mathcal{Q}}\min_{\mu\in\Delta(\widehat{\mathcal{Q}})}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p(\cdot;\mu),q)\right).$ (12)

The same is true if the $\min$ in (11) is swapped out for a $\max$.

###### Proof.

See Section C.1. ∎

Proposition 6.9 gives simple conditions under which platform payoff is
strictly higher when a user strategizes than when a user is naive. In
particular, there are two takeaways from Proposition 6.9:

  1. 1.

Strategization helps platforms when $U$ and $V$ are sufficiently aligned.
Observe that the right-hand side of (11) is identical to the analogous
expression on the left-hand side of (12), except that $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{V}$
is swapped out for $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{U}$
in (12). Therefore, when $U$ and $V$ are sufficiently aligned, finding a $q$
that maximizes the worst-case user payoff (i.e.,
$\min_{\mu\in\Delta(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)$) will also yield a high platform payoff.

The following corollary confirms this intuition, showing that user
strategization can never lower the platform’s payoff when $U$ and $V$ are
perfectly aligned.

######  Corollary 6.10.

Under the setup of Proposition 6.9, the platform’s payoff under a strategic
user is at least as high as its payoff under a naive user when $U=V$.

  2. 2.

Strategization can be viewed as a form of coordination. This follows from the
fact that the left- and right-hand sides of (12) look similar, with the only
difference being the set of beliefs over which $\mu$ is minimized. The set on
the left-hand side is constrained by the user’s anticipation of how the
platform will behave. When the user and platform have aligned incentives, and
the user has a good idea of how the platform will behave, the resulting
“coordination” helps both the user and the platform.

The following corollary solidifies this intuition, showing that even when user
and platform have only partially aligned payoffs, they can coordinate (via
strategization) to find a region of proposition space where their payoffs are
aligned.

######  Corollary 6.11.

Assume the same setting as Proposition 6.9. The platform’s payoff under a
strategic user is at least as high as its payoff under a naive user when there
exist functions $g:\mathcal{B}\to\mathbb{R}$ and $f:\mathcal{Z}\to\\{-1,1\\}$
such that user and platform payoffs decompose as $U(B,Z)=g(B)\cdot f(Z)$ and
$V(B,Z)=g(B)$ respectively.

####  6.4 User strategization can cause unexpected behavior

Although user strategization can help the platform under its current strategy
$(p,\widehat{\mathcal{Q}})$, we show that strategization interferes with
learning by “corrupting” the data that the platform collects. We further show
strategization can cause other unexpected behavior—specifically, expanding the
hypothesis class $\widehat{\mathcal{Q}}$ that the platform uses can
unexpectedly hurt the platform under strategization.

#####  6.4.1 Changing the algorithm $p$ results in unpredictable payoff

In this section, consider a fixed hypothesis class $\widehat{\mathcal{Q}}$.
Suppose that, after deploying algorithm $p$, the platform wants to change its
algorithm to a counterfactual algorithm $p_{\text{CF}}$. In these cases, the
platform may wish to estimate their expected payoff if they were to switch to
$p_{\text{CF}}$. Formally, for any belief
$\mu\in\Delta(\widehat{\mathcal{Q}})$ and algorithm $p^{\prime}$, we define
the platform’s predicted payoff as

$\widehat{V}(p^{\prime},\mu)\coloneqq\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^{\prime}(\cdot;\mu),\hat{q})\right].$ (13)

Now, consider a user who is $S^{\infty}$-strategic. Recall from Section 4.2
that $q^{*}\\!(p_{\text{CF}},\widehat{\mathcal{Q}})$ denotes the strategy that
the strategic user adopts if the platform employs strategy
$(p_{\text{CF}},\widehat{\mathcal{Q}})$. We can consequently write the
platform’s worst-case payoff under $p_{\text{CF}}$ and user strategization as

${\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}}^{*}(p_{\text{CF}})\coloneqq\min_{\mu\in\Delta(S^{\infty}(q,p_{\text{CF}}))}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p_{\text{CF}},q^{*}(p_{\text{CF}})).$ (14)

The following result shows that if a platform gathers data under $p$ but is
interested in estimating its payoff under an alternative algorithm
$p_{\text{CF}}$, its estimate may be arbitrarily bad when the user is
strategic. This result holds even when the platform is (nearly) correctly
specified, i.e., even for the highly expressive hypothesis class
$\widehat{\mathcal{Q}}$ defined below:

######  Definition 6.12 ($\varepsilon$-net hypothesis class).

For a finite proposition space $\mathcal{Z}$ and some $\varepsilon>0$, let
$\Delta_{\varepsilon}(\mathcal{B})$ be an $\varepsilon$-net of
$\Delta(\mathcal{B})$ with respect to the $\ell_{\infty}$ metric. An
$\varepsilon$-net hypothesis class is the set of all possible mappings from
propositions in $\mathcal{Z}$ to behavior distributions in
$\Delta_{\varepsilon}(\mathcal{B})$, i.e.,
$\widehat{\mathcal{Q}}_{\varepsilon}\coloneqq{\Delta_{\varepsilon}(\mathcal{B})}^{\mathcal{Z}}$
(and thus
$|\widehat{\mathcal{Q}}_{\varepsilon}|\approx(\frac{1}{\varepsilon})^{|B|\cdot|Z|}$).

By proving the result below under Definition 6.12, we rule out the case where
the platform is unable to predict counterfactual payoffs simply because it
cannot accurately model the user.

######  Proposition 6.13.

Consider a given platform strategy $(p,\widehat{\mathcal{Q}})$ and platform
payoff function $V$. Suppose that $\widehat{\mathcal{Q}}$ is an
$\varepsilon$-net (Definition 6.12) for some sufficiently small $\varepsilon$,
that $p({\cdot};{\mu})$ has full support for all $\mu$, and that Assumption
6.4 holds. Define $\zeta$ as the maximum gap in predicted platform payoff,
i.e.,

$\displaystyle\zeta(p^{\prime})=\max_{\hat{q}_{1},\hat{q}_{2}\in\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}_{1}}),\hat{q}_{1})-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p^{\prime}(\cdot;\delta_{\hat{q}_{2}}),\hat{q}_{2}).$

Further assume that there exists $\beta\geqslant\alpha\geqslant 0$ such that
$\alpha\leqslant\text{Var}_{p(\cdot;\mu)\times q}[V(B,Z)]\leqslant\beta$ for
any belief $\mu$ and user strategy $q$. Then, for any
$\varepsilon_{0},\varepsilon_{1}>0$, there exists a $p_{\text{CF}}$ and $U$
such that $d_{\mathcal{P}}(p,p_{\text{CF}})\leqslant\varepsilon_{0}$, and

$\displaystyle\min_{\mu\in
S^{\infty}(q,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}}^{*}(p_{\text{CF}})\right|\geqslant\sqrt{\zeta(p_{\text{CF}})^{2}-4(\beta-\alpha)}-\varepsilon_{1}.$
(15)

###### Proof.

See Section C.2. ∎

If the variance of the platform’s payoff does not change much across beliefs
(i.e., if $\alpha\approx\beta$), the right side of (15) is effectively the
largest gap that can exist between an estimated payoff and the true payoff. As
such, Proposition 6.13 states that data collected under $p$ can be unhelpful
for making predictions about a counterfactual algorithm. The intuition behind
this result is that, when users strategize, the platform limiting payoff is
nonsmooth in $p$, i.e., there exists a $p_{\text{CF}}$ that is
$\varepsilon$-close to $p$ for which the payoff under strategization is far
from that under $p$.

#####  6.4.2 Expanding $\widehat{\mathcal{Q}}$ can hurt the platform

Next, we show that when a user is strategic, expanding $\widehat{\mathcal{Q}}$
can hurt the platform’s payoff. This is somewhat counterintuitive, as
$\widehat{\mathcal{Q}}$ is the hypothesis class that the platform uses to
infer the user’s behavior $q$, and expanding one’s model family typically does
not hurt estimation.

To make this statement formal, suppose that the user is $S^{\infty}$-strategic
and that the algorithm $p$ is fixed. (Since $p$ is held fixed in this section,
we suppress its notation below.) Let $q^{*}(\widehat{\mathcal{Q}})$ denote the
strategy that the strategic user adopts if the platform uses hypothesis class
$\widehat{\mathcal{Q}}$. That is, let

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

######  Proposition 6.14.

Consider a platform strategy $\\!(p,\widehat{\mathcal{Q}})\\!$ and a platform
payoff function $V$ bounded in $[0,1]$. Suppose
$(\mathcal{Z},\mathcal{B},V,p,\widehat{\mathcal{Q}})$ satisfy the expansion
assumption (Assumption 6.6), and that $V(Z,B)$ has a unique maximizer with
respect to $B$ for each $Z\in\mathcal{Z}$. Then, there exist a user payoff
function $U$ and sets
$\widehat{\mathcal{Q}}_{1},\widehat{\mathcal{Q}}_{2}\subset\widehat{\mathcal{Q}}$
such that $\widehat{\mathcal{Q}}_{1}\subseteq\widehat{\mathcal{Q}}_{2}$, but

$\displaystyle\min_{\mu\in
S^{\infty}(q^{*}(\widehat{\mathcal{Q}}_{1}),\widehat{\mathcal{Q}}_{1})}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\mu),q^{*}(\widehat{\mathcal{Q}}_{1}))>\max_{\mu\in
S^{\infty}(q^{*}(\widehat{\mathcal{Q}}_{2}),\widehat{\mathcal{Q}}_{2})}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}(p(\cdot;\mu),q^{*}(\widehat{\mathcal{Q}}_{2})).$

###### Proof.

See Section C.3. The intuition is that the platform can unintentionally remove
the user’s means of strategization. That is, a user may want to induce a
specific belief from the platform without straying too far from their best-
response strategy. Thus, they purposefully pick a strategy $q^{*}_{1}$ that
the platform misinterprets in a desirable way. 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. ∎

Like Proposition 6.13, Proposition 6.14 shows that user strategization can
cause unexpected behavior. Both imply that strategization makes it difficult
to use its data under one strategy $(p,\widehat{\mathcal{Q}})$ make inferences
about a different strategy.

####  6.5 System behavior is more predictable for best-response users

The previous section establishes that strategization can make it difficult for
the platform to predict how the system behaves if either $p$ or
$\widehat{\mathcal{Q}}$ is changed. This is consequential because the platform
may wish to use the data that they have collected under
$(p,\widehat{\mathcal{Q}})$ to estimate some quantity under a counterfactual
$\smash{(p^{\prime},\widehat{\mathcal{Q}}^{\prime})}$. In this section, we
show that these problems do not arise when users are naive. In other words,
when the user plays according to their best-response at each timestep, the
platform benefits because it is easier for them to make inferences under
changes to $(p,\widehat{\mathcal{Q}})$.

Formally, suppose we have a best-response user, and fix a platform hypothesis
class $\widehat{\mathcal{Q}}$. Recall the platform’s payoff estimator (13)
(restated below), and let $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{V}_{\text{BR}}(p_{\text{CF}})$ denote the true payoff under
$(p_{\text{CF}},\widehat{\mathcal{Q}})$ (i.e., analagous to (14)) when the
user is naive:

$\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).$

Our first result shows that, in contrast to Proposition 6.13, using data
gathered under $p$ to estimate the platform’s payoff under $p_{\text{CF}}$ is
a good idea for best-response users.

######  Proposition 6.15.

Suppose that the platform’s strategy $(p,\widehat{\mathcal{Q}})$ is such that
the hypothesis class $\widehat{\mathcal{Q}}$ is an $\varepsilon$-net
(Definition 6.12). Let $p_{\text{CF}}$ be a counterfactual algorithm that is
well-behaved (Assumption 6.5); then,

$\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\sqrt{\varepsilon}\left((2L_{\mathcal{P}}+1)\sqrt{|\mathcal{B}|}\right).$
(16)

As a result, by using a sufficiently fine $\varepsilon$-net hypothesis class
$\widehat{\mathcal{Q}}$, the platform can estimate its payoff under
counterfactual algorithms up to arbitrary precision.

###### Proof.

See Section C.4. ∎

Next, suppose that the hypothesis class $\widehat{Q}$ can change but the
algorithm $p$ is fixed. In addition, the next result shows that, in direct
contrast to Proposition 6.14, payoffs cannot decrease when the hypothesis
class $\widehat{\mathcal{Q}}$ is expanded and the user plays naively.

######  Proposition 6.16.

Consider a given $(p,\widehat{\mathcal{Q}})$ and $V$. Under Assumption 6.6,
for any $\widehat{\mathcal{Q}}^{\prime}\subset\widehat{\mathcal{Q}}$, Then

$V(\widehat{\mathcal{Q}},q^{\text{BR}})\geqslant
V(\widehat{\mathcal{Q}}^{\prime},q^{\text{BR}}).$

###### Proof.

This follows directly from Assumption 6.6. ∎

Propositions 6.15 and 6.16 show that incentivizing the user to play their
best-response behavior can lead to more reliable data and payoffs for the
platform, begging the question: When are users incentivized to play naively?

###  7 Trustworthy algorithm design

In the previous sections, we found that strategic behavior can hurt the
platform. Specifically, we showed that user strategization violates a key
assumption of most data-driven algorithms that user behavior is exogenous,
which compromises the platform’s ability to re-use the data that it collects,
e.g., to train future algorithms. In contrast, we found that the platform’s
data looks exogenous if the user behaves naively. That is, a platform can
recover the exogeneity assumption if it encourages users to behave naively.

In this section, we argue that this analysis suggests that trustworthy design
can help platforms. We discuss how trustworthiness produces two beneficial
outcomes: users are not incentivized to strategize—which allows platforms to
recover the exogeneity assumption—and users are incentivized to engage with
the platform over alternatives. We begin in Section 7.1 with a formal
definition of trustworthiness. Importantly, we draw a distinction between
trustworthiness and strategy-proofness, connecting our definition to the
concept of individual rationality in mechanism design. We then discuss how
this definition relates to existing notions of trust in Section 7.2. In
Sections 7.3-7.4, we use this definition to unpack four reasons why users do
not trust their platforms and propose two interventions for improving
trustworthiness.

####  7.1 Trustworthiness and its effect on the platform

Building on our analysis in Section 6, we present a formal definition of
trustworthiness.

######  Definition 7.1 (Trustworthy).

Let $q^{*}$ denote the policy that the $S^{\infty}_{\Omega}$-strategic user
adopts when the platform employs algorithm $p$. A platform’s policy
$(p,\widehat{\mathcal{Q}})$ is $\kappa$-trustworthy when the user is not
incentivized to strategize and the naive user’s limiting payoff under
$(p,\widehat{\mathcal{Q}})$ is at least $\kappa\in\mathbb{R}$, i.e.,

  1. 1.

$\min_{\mu\in\Delta(S^{\infty}_{\Omega}(p,q^{*}))}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu},q^{*})\leqslant\min_{\mu\in\Delta(S^{\infty}_{\Omega}(p,q^{\text{BR}}))}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu},q^{\text{BR}})$ and

  2. 2.

$\min_{\mu\in\Delta(S^{\infty}_{\Omega}(p,q^{\text{BR}}))}\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{U}(p^{\mu},q^{\text{BR}})\geqslant\kappa$.

###### First requirement of trustworthiness.

One can think of Definition 7.1(1) as follows: a platform satisfies the first
requirement of trustworthiness if the user does not have to strategize because
the platform looks out for the user’s interests so they do not have to do so
themselves. When the platform meets this requirement, the user might as well
play their best-response action.

As an example, consider YouTube. Suppose that a user likes to alternate
between “junk” content and “healthy” content based on their mood [KMR22a]. If
they were “truthful,” then they would always pick the video that fits their
current mood.333Note that this setting can be modeled by allowing $U$ to be
stochastic, with a hidden variable that represents the user’s underlying
stochastic mood. Suppose that the platform adopts an algorithm that only
accounts for one possible mood and can therefore only model the user as liking
“junk” or “healthy” content, but not both. Then, the user is better off
behaving strategically; for instance, only using YouTube for one—but not
both—of their moods (or maintaining two YouTube accounts, as has been observed
anecdotally). Intuitively, the user does not trust that the platform
interprets their behavioral data correctly; they do not trust that the
platform will use their behavioral data to generate good content in the
future. On the other hand, if YouTube is able to correctly parse the user’s
mood and recommend content to suit both moods, the user does not have to
behave strategically. The user therefore trusts the platform to correctly
interpret their actions. In addition to this example, there are many other
factors that affect trustworthiness, such as a platform’s willingness to
protect user privacy.

###### Second requirement of trustworthiness.

Definition 7.1(2) states that trustworthiness is earned only if the user’s
expected limiting payoff is at least $\kappa$ when the user plays their best-
response action. That is, it is not enough that the platform is strategy-
proof, as required by Definition 7.1(1). Trustworthiness additionally requires
that behaving naively is sufficiently beneficial for the user. Consider, for
instance, a platform that adopts a strategy $(p,\widehat{\mathcal{Q}})$ under
which the user’s limiting payoff is $-1$ no matter what strategy the user
adopts. Then, $(p,\widehat{\mathcal{Q}})$ satisfies Definition 7.1(1) because
the user is not incentivized to strategize since all strategies induce a
payoff of $-1$, but the system is not $\kappa$-trustworthy under Definition
7.1(2) for any $\kappa>-1$.

This requirement echoes individual rationality, a concept in mechanism design
under which agents continue engaging with the platform (which is known in
mechanism design as “participating in the mechanism”) if it is beneficial for
them to do so. Using this interpretation, $\kappa$ determines the expected
limiting payoff at which the user does not trust the platform although they
may be willing to continue engaging with the platform. In this way, $\kappa$
captures the user’s ability to tolerate the untrustworthy behavior. The higher
$\kappa$ is, the more trust the user places in the platform, and the more
likely the user is to engage with the platform over alternatives.

###### Implication of trustworthiness on the platform.

As shown in Sections 5-6, trust is central to the platform’s ability to
collect reliable data. Without trust, users are incentivized to strategize,
which is particularly harmful for platforms because it means that the data
that they use for multiple purposes—such as training future algorithms or
predicting the performance of candidate algorithms—is unreliable. More
broadly, earning user trust is often beneficial to platforms when they rely
not only on the continued participation of their users, but also on the amount
of user engagement. The more time users spend on the platform, the more data
the platform collects. This facet of trustworthiness is captured by the second
requirement in Definition 7.1—if a platform is only $\kappa$-trustworthy, but
another platform is $\kappa^{\prime}$-trustworthy for
$\kappa^{\prime}>\kappa$, users may be compelled to spend more time on the
other platform (or even switch platforms). There are, of course, occasions
when a platform is not incentivized to build trust, which could occur when the
platform benefits so greatly from strategization (enough to overshadow the
potential harms of unreliable data) that platform does not rely greatly on
data collection for prediction, or there is little risk of users leaving the
platform.

####  7.2 Elements of trustworthiness

The goal of this section is to place our definition of trustworthiness within
the broader discussion of trustworthiness. Below, we identify several key
elements of trustworthiness that appear in the literature on trust [Kra99a,
Har06a, Nis01a], where we examine situations in which “I” trust “you.” The
following are five common elements of trust:

  1. 1.

Trustworthiness does not imply that you and I have perfectly aligned
interests; only that your behavior takes some of my interests into account.

  2. 2.

Distrust arises when I expect to incur losses from interacting with you
(unless I behave strategically) and, conversely, trust arises when I expect to
gain from interaction.

  3. 3.

Trust is inherently relational in that trusting you to look after my interests
may depend on who “you” and “I” are, so that “you” are not necessarily
universally trustworthy.

  4. 4.

Trust is generally meaningful only when there are repeated interactions. In
particular, I only put trust in you if I must rely on you in the future.
Moreover, I only trust you to take my interests into account if I believe you
value a continued relationship with me.

  5. 5.

Trust involves vulnerability—the possibility of harm—because to trust is to
allow another to affect one’s interests.

We now connect these elements of trust to our Definition 7.1. First, a user
and platform need not have the exact same interests for the results in Section
6, which show that untrustworthiness can be harmful to the platform, to hold.
Second, distrust in our work arises when a user is incentivized to strategize
because the platform does not account for the user’s interests, meaning that
trust and distrust are linked to gains and losses from interactions. Third,
our formulation of trust is relational; a user’s best-response and strategic
behavior are specific to them, meaning that a platform’s trustworthiness may
differ across users. Fourth, a continuing relationship is pivotal to our
formulation of trust. In fact it matters in two ways: (i) users only
strategize because they can anticipate future interactions, and (ii) platforms
typically rely on the continued participation of users for success. Lastly,
user payoffs, as modeled in Section 3.1, depend on both the user’s action as
well as the platform’s. As such, the user’s utility is influenced by the
platform. This point is salient because the risk of being harmed is why trust
often matters in data-driven decision-making.

######  Remark 7.2.

Note that there are other factors that may influence trustworthiness, such as
the credibility of the trusted party, their reputation, and even whether they
are virtuous or reliable. These factors are based on the perceived qualities
of the trusted party. Although perception has a significant impact on trust,
we leave perception-based factors of trust to future discussions. By putting
perception aside, we align more closely with conceptualizations of trust such
as Hardin’s, who states that trust is determined by the interests of each
party and the desire of one party to take the other party’s interests into
account in order to foster a continuing relationship [Har06a].

####  7.3 Reasons why a user may not trust their platform

Under Definition 7.1 of trustworthiness, there are several reasons why a user
might not trust their platform’s policy. We discuss three reasons in this
section. These insights can be used to inform methods for building
trustworthiness, as discussed in the following section.

###### Misspecification.

We say that a platform is misspecified with respect to $q^{\text{BR}}$ when
$q^{\text{BR}}\not\in\widehat{\mathcal{Q}}$. Misspecification implies that,
should a user choose to play their best-response actions, the platform would
not be able to model their behavior perfectly. For example, misspecification
occurs when a platform believes that there are a few canonical “types” of
users, but the user of interest does not fit into any of these types.
Misspecification often induces users to strategize because the platform’s
inability to model the user correctly can mean that a user gains more by
strategizing (e.g., by pretending to be one of the canonical types of user).

###### Hidden, changing state.

Suppose that a user has different “modes.” For instance, a user on an online
shopping platform sometimes needs clothes for everyday wear and sometimes
needs clothes for special occasions. Alternatively, suppose that there is
salient information that is only available to the user but not to the
platform.

In such cases, there is a state that changes across time and is hidden from
the platform. We do not explicitly model this setting in our setup in Section
3; however, one can encompass such cases by adding a Step 0 to the game in
Section 3.1 during which a state $x_{t}$ is drawn at the start of each time
step, i.e., “nature” selects a state $x_{t}$. The user then chooses action
$B_{t}\sim q(\cdot|Z_{t},x_{t})$ in Step 2, and the user receives a payoff
$U(Z_{t},B_{t},x_{t})$ in Step 3. Because the platform does not have access to
salient information $x_{t}$, the user may find that their $x_{t}$-dependent
behavior is misattributed to other factors. This misattribution can lead the
platform to behave unexpectedly (to the user’s detriment), therefore prompting
the user to strategize.

###### Algorithm incompatible with user payoffs.

Recall that $p$ denotes the platform’s algorithm and $U$ denotes the user’s
payoff. A user may strategize if $p$ is incompatible with $U$. Even if the
platform is not misspecified with respect to the best-response strategy
$q^{\text{BR}}$ and the platform has access to all salient information (such
that the two reasons for strategization given above are absent), a user may
wish to strategize if the platform’s method for generating propositions is
detrimental to a user following $q^{\text{BR}}$. This would, for instance, be
the reason why users often strategize when an algorithm is known to have
feedback loops or why users strategize when their recommendation algorithm
shows too much content of type $X$ after a user clicks on a piece of content
of type $X$.

####  7.4 Interventions for improving trustworthiness

Data-driven platforms can determine whether users strategize by testing the
exogeneity assumption. For example, [CIA+23a] determined through a lab
experiment that (i) users strategize on online platforms and (ii) a user’s
strategic behavior reflects how they believe their current actions affect
their long-term outcomes when their platform is data-driven.

When exogeneity does not hold (i.e., users strategize), platforms may wish to
intervene. In this section, we first describe why interventions that do not
build trustworthiness (as formalized by Definition 7.1) but attempt to
overcome the challenges untrustworthiness often fall short. We then discuss
how two interventions for improving trustworthiness can complement these
efforts.

#####  7.4.1 Naive interventions

Recall that the main challenge of untrustworthiness is that user
strategization distorts the platform’s data, which compromises its ability to
estimate user behavior under alternate strategies $(p,\widehat{\mathcal{Q}})$.
The platform might wish to overcome the challenges of untrustworthiness by:
(i) designing a strategy-proof mechanism, (ii) modeling the user’s payoff
function $U$ in order to predict their behavior under any counterfactual
$(p,\widehat{\mathcal{Q}})$, (iii) expanding the hypothesis class
$\widehat{\mathcal{Q}}$, (iv) guessing the user’s hidden state $x_{t}$, as
described in Section 7.3, or (v) improving one’s algorithm $p$. Below, we
discuss how these approaches can fall short of methods that directly boost
trustworthiness.

First, designing strategy-proof mechanisms does not necessarily elicit higher
payoffs for the user or the platform. For instance, an algorithm $p$ that
recommends YouTube videos that all users universally dislike is strategy-
proof. In this scenario, the user’s best-response (i.e., naive) strategy is to
ignore on any recommended video. This strategy is also their highest-payoff
strategy because clicking on any video incurs a negative payoff. Therefore,
$p$ is strategy-proof, but it does not lead to positive outcomes for the user
or the platform.

The second option seeks to model each user’s payoff function $U$ so that it is
possible to infer how the user would behave under alternative platform
strategies $(p,\widehat{\mathcal{Q}})$. While this approach may work in simple
settings, it is difficult to do in complex settings. In particular, this
approach becomes challenging when users are heterogeneous, there is unobserved
confounding, and the space of possible platform strategies
$(p,\widehat{\mathcal{Q}})$ is large. Imagine, for instance, predicting how an
arbitrary social media user would behave under any possible feed. Such an
estimation task is notoriously challenging. For one, both the user’s and
platforms action spaces are large (i.e., the user can interact with content in
many possible ways, and there are many possible posts that the platform could
recommend). For another, each user behaves differently (i.e., there is high
heterogeneity). In similarly complex (or high-risk) settings, developing
reliable models is difficult.

Third, one might naturally think to expand $\widehat{\mathcal{Q}}$ in order to
address issues that arise from misspecification. We show in Proposition 6.14,
however, that expanding the hypothesis class $\widehat{\mathcal{Q}}$ can,in
fact, lower the platform’s payoff and does not necessarily remove
misspecification unless $q^{\text{BR}}$ is guaranteed to be in the new
hypothesis class. Since it is difficult (if not impossible) to determine
whether the new hypothesis class contains $q^{\text{BR}}$ a priori, this
approach should be taken with caution.

Finally, we argue in the following section that the fourth and fifth
approaches described above can indeed improve outcomes for the user and
platform, but are less straightforward than interventions that directly boost
trustworthiness.

#####  7.4.2 Interventions that target trustworthiness

In this section, we provide two simple recommendations that target
trustworthiness. The goal of these interventions is to induce the user to
behave naively (i.e., “exogenously”). Recall from Definition 4.4 that a user
strategizes when the effort to deviate from their best-response (naive)
behavior is low compared to the payoff gained by strategizing. At the core of
the interventions below is the idea that, instead of increasing the effort
required to deviate from best-response behavior (i.e., adding a barrier to
strategization, as strategy-proof mechanisms often do), the platform can
instead reduce the gains of strategization below the effort to deviate.

###### Recommendation #1: Offering multiple algorithms.

Offering users multiple algorithms from which they can choose addresses
several issues simultaneously. As an example, consider Twitter, which offers
personalized, chronological, and trending feeds. Returning to the three
reasons users strategize, as given in Section 7.3, allowing users to select
between multiple algorithms at each time step $t$ is a straightforward way of
accommodating unobserved confounding, e.g., a hidden state $x_{t}$. While the
platform could predict $x_{t}$, doing so is inevitably less reliable than
giving users the ability to select an algorithm based on $x_{t}$ themselves.
Second, if one algorithm is incompatible with a user’s payoffs, the user will
simply ignore that algorithm. On the other hand, if the platform only offers
one algorithm $p$, it inevitably alienates users whose payoffs are
incompatible with $p$.

Offering multiple algorithms can therefore diminish two of the reasons that
users strategize (as given in Section 7.3) and guarantee that a user’s
limiting payoff is at least as high as under a single algorithm. It therefore
improves trustworthiness by Definition 7.1.

###### Recommendation #2: Providing feedback mechanisms.

Another intervention that builds trust and therefore mitigates the risks of
strategization is providing users opportunities to give meaningful feedback.
Returning to the reasons for strategization in Section 7.3, feedback can serve
as a simple and reliable indicator for misspecification. If a user
consistently indicates that the platform is not behaving in their interest,
then the platform not only learns that this user is misspecified under
$\widehat{\mathcal{Q}}$, but also gains insight into how
$\widehat{\mathcal{Q}}$ can be improved. If the feedback mechanism is designed
such that giving feedback requires little effort and the platform incorporates
feedback well, then the user’s payoff under best-response behavior is improved
without much effort. As a result, strategization offers little benefit
compared to the effort of deviating from $q^{\text{BR}}$.

There are many ways of eliciting feedback, and not all mechanisms are made
equal. Platforms must ensure that they are comprehensive but not overwhelming,
easily accessible but not so pervasive that users simply treat it as an
annoyance. Determining the precise design of feedback mechanisms is out of the
scope of this work and may be of interest in future work.

###  8 Acknowledgements

The authors would like to thank Manolis Zampetakis for comments on an earlier
version of this manuscript, and Hannah Li and Jennifer Allen for fruitful
discussions. Work supported in part by the NSF grants CNS-1815221 and
DMS-2134108, and Open Philanthropy.

[sorting=nyt]

### References

  * [ACK+19] Jacob D Abernethy, Rachel Cummings, Bhuvesh Kumar, Sam Taggart and Jamie H Morgenstern “Learning auctions with robust incentive guarantees” In Advances in neural information processing systems 32 proceedings.neurips.cc, 2019
  * [ARS13] Kareem Amin, Afshin Rostamizadeh and Umar Syed “Learning prices for repeated auctions with strategic buyers” In Advances in neural information processing systems 26 proceedings.neurips.cc, 2013
  * [BNK+19] Gagan Bansal, Besmira Nushi, Ece Kamar, Walter S Lasecki, Daniel S Weld and Eric Horvitz “Beyond accuracy: The role of mental models in human-AI team performance” In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing 7 Association for the Advancement of Artificial Intelligence (AAAI), 2019, pp. 2–11
  * [BCD+21] Ying Bao, Xusen Cheng, Triparna De Vreede and Gert-Jan De Vreede “Investigating the relationship between AI and trust in human-AI collaboration” In Hawaii International Conference on System Sciences 2021 (HICSS-54) aisel.aisnet.org, 2021
  * [BM93] James Bergin and W Bentley MacLeod “Continuous Time Repeated Games” In International economic review 34.1 [Economics Department of the University of Pennsylvania, Wiley, Institute of SocialEconomic Research, Osaka University], 1993, pp. 21–37
  * [Boh16] J Aislinn Bohren “Informational herding with model misspecification” In Journal of Economic Theory 163 Elsevier, 2016, pp. 222–247
  * [BH21] J Aislinn Bohren and Daniel N Hauser “Learning with heterogeneous misspecified models: Characterization and robustness” In Econometrica: journal of the Econometric Society 89.6 The Econometric Society, 2021, pp. 3025–3077
  * [BHK22] Gavin Brown, Shlomi Hod and Iden Kalemaj “Performative Prediction in a Stateful World” In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics 151, Proceedings of Machine Learning Research PMLR, 2022, pp. 6045–6061
  * [BKS12] Michael Brückner, Christian Kanzow and Tobias Scheffer “Static prediction games for adversarial learning problems” Accessed: 2023-10-31 jmlr.org, https://www.jmlr.org/papers/volume13/brueckner12a/brueckner12a.pdf, 2012
  * [BBD08] Lucian Busoniu, Robert Babuska and Bart De Schutter “A comprehensive survey of multiagent reinforcement learning” In IEEE transactions on systems, man and cybernetics. Part C, Applications and reviews: a publication of the IEEE Systems, Man, and Cybernetics Society 38.2 Institute of ElectricalElectronics Engineers (IEEE), 2008, pp. 156–172
  * [CIM22] S H Cen, A Ilyas and A Madry “A Game-Theoretic Perspective on Trust in Recommendation” In NeurIPS Workshop on Responsible Decision Making in Dynamic Environments (RDD), 2022
  * [CIA+23] Sarah H. Cen, Andrew Ilyas, Jennifer Allen, Hannah Li, David Rand and Aleksander Madry “Measuring Strategization in Recommendation: Users Adapt Their Behavior to Shape Future Content” In Preprint, 2023
  * [DLM+21] Yuan Deng, Sebastien Lahaie, Vahab Mirrokni and Song Zuo “Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing” In Proceedings of the 38th International Conference on Machine Learning 139, Proceedings of Machine Learning Research PMLR, 2021, pp. 2601–2610
  * [DRS+18] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner and Zhiwei Steven Wu “Strategic Classification from Revealed Preferences” In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18 Ithaca, NY, USA: Association for Computing Machinery, 2018, pp. 55–70
  * [EP16] Ignacio Esponda and Demian Pouzo “Berk–Nash equilibrium: A framework for modeling agents with misspecified models” In Econometrica 84.3 Wiley Online Library, 2016, pp. 1093–1130
  * [EBC+19] Neta Ezer, Sylvain Bruni, Yang Cai, Sam J Hepenstal, Christopher A Miller and Dylan D Schmorrow “Trust Engineering for Human-AI Teams” In Proceedings of the Human Factors and Ergonomics Society … Annual Meeting Human Factors and Ergonomics Society. Meeting 63.1 SAGE Publications Inc, 2019, pp. 322–326
  * [FII20] Mira Frick, Ryota Iijima and Yuhta Ishii “Stability and robustness in misspecified learning models” Cowles Foundation Discussion Paper, 2020
  * [FRS17] D Fudenberg, G Romanyuk and P Strack “Active learning with a misspecified prior” In Theoretical Economics Wiley Online Library, 2017
  * [FLS21] Drew Fudenberg, Giacomo Lanzani and Philipp Strack “Limit points of endogenous misspecified learning” In Econometrica: journal of the Econometric Society 89.3 The Econometric Society, 2021, pp. 1065–1098
  * [FL93] Drew Fudenberg and David K Levine “Self-Confirming Equilibrium” In Econometrica: journal of the Econometric Society 61.3 [Wiley, Econometric Society], 1993, pp. 523–545
  * [GNE+21] Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen and Nir Rosenfeld “Strategic Classification in the Dark” In Proceedings of the 38th International Conference on Machine Learning 139, Proceedings of Machine Learning Research PMLR, 2021, pp. 3672–3681
  * [HDA+16] Dylan Hadfield-Menell, Anca Dragan, Pieter Abbeel and Stuart Russell “Cooperative inverse reinforcement learning” In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16 Barcelona, Spain: Curran Associates Inc., 2016, pp. 3916–3924
  * [HLN+22] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert and Alexander Wei “Learning in Stackelberg Games with Non-myopic Agents” In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22 Boulder, CO, USA: Association for Computing Machinery, 2022, pp. 917–918
  * [Har06] Russell Hardin “Trust” Polity, 2006
  * [HMP+16] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou and Mary Wootters “Strategic Classification” In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS ’16 Cambridge, Massachusetts, USA: Association for Computing Machinery, 2016, pp. 111–122
  * [HHP23] Andreas Haupt, Dylan Hadfield-Menell and Chara Podimata “Recommending to Strategic Users” In Foundations of Responsible Computing, 2023
  * [HHC23] Keke Hou, Tingting Hou and Lili Cai “Exploring Trust in Human–AI Collaboration in the Context of Multiplayer Online Games” In Systems 11.5 Multidisciplinary Digital Publishing Institute, 2023, pp. 217
  * [KL93] Ehud Kalai and Ehud Lehrer “Subjective Equilibrium in Repeated Games” In Econometrica: journal of the Econometric Society 61.5 [Wiley, Econometric Society], 1993, pp. 1231–1240
  * [KL95] Ehud Kalai and Ehud Lehrer “Subjective games and equilibria” In Games and economic behavior 8.1, 1995, pp. 123–163
  * [KN19] Yash Kanoria and Hamid Nazerzadeh “Incentive-Compatible Learning of Reserve Prices for Repeated Auctions” In Companion Proceedings of The 2019 World Wide Web Conference, WWW ’19 San Francisco, USA: Association for Computing Machinery, 2019, pp. 932–933
  * [KL23] 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
  * [KMR22] Jon Kleinberg, Sendhil Mullainathan and Manish Raghavan “The Challenge of Understanding What Users Want: Inconsistent Preferences and Engagement Optimization” In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22 Boulder, CO, USA: Association for Computing Machinery, 2022, pp. 29
  * [Kra99] Roderick M Kramer “Trust and distrust in organizations: Emerging perspectives, enduring questions” In Annual review of psychology 50.1 Annual Reviews 4139 El Camino Way, PO Box 10139, Palo Alto, CA 94303-0139, USA, 1999, pp. 569–598
  * [LR22] Sagi Levanon and Nir Rosenfeld “Generalized Strategic Classification and the Case of Aligned Incentives” In Proceedings of the 39th International Conference on Machine Learning 162, Proceedings of Machine Learning Research PMLR, 2022, pp. 12593–12618
  * [MS06] George J Mailath and Larry Samuelson “Repeated games and reputations: Long-Run relationships” New York, NY: Oxford University Press, 2006
  * [Mar20] Aarian Marshall “Uber Changes Its Rules, and Drivers Adjust Their Strategies”, 2020 URL: https://www.wired.com/story/uber-changes-rules-drivers-adjust-strategies/
  * [MT07] Frank McSherry and Kunal Talwar “Mechanism Design via Differential Privacy” In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) ieeexplore.ieee.org, 2007, pp. 94–103
  * [MBF+22] Hussein Mozannar, Gagan Bansal, Adam Fourney and Eric Horvitz “Reading Between the Lines: Modeling User Behavior and Costs in AI-Assisted Programming”, 2022 arXiv:2210.14306 [cs.SE]
  * [NCE+22] Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui and Vianney Perchet “Learning in Repeated Auctions” In Foundations and Trends® in Machine Learning 15.3 Now Publishers, 2022, pp. 176–334
  * [Nis01] Helen Nissenbaum “Securing trust online: Wisdom or oxymoron” In BUL Rev. 81 HeinOnline, 2001, pp. 635
  * [NST12] Kobbi Nissim, Rann Smorodinsky and Moshe Tennenholtz “Approximately optimal mechanism design via differential privacy” In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12 Cambridge, Massachusetts: Association for Computing Machinery, 2012, pp. 203–213
  * [OY20] Kazuo Okamura and Seiji Yamada “Adaptive trust calibration for human-AI collaboration” In PloS one 15.2 journals.plos.org, 2020, pp. e0229132
  * [PZM+20] Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner and Moritz Hardt “Performative Prediction” In Proceedings of the 37th International Conference on Machine Learning 119, Proceedings of Machine Learning Research PMLR, 2020, pp. 7599–7609
  * [RBK+10] Aaron Roth, Maria Florina Balcan, Adam Kalai and Yishay Mansour “On the Equilibria of Alternating Move Games” In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings Society for IndustrialApplied Mathematics, 2010, pp. 805–816
  * [SVM22] Ignacio Siles, Luciana Valerio-Alfaro and Ariana Meléndez-Moran “Learning to like TikTok . . . and not: Algorithm awareness as process” In New Media & Society SAGE Publications, 2022, pp. 14614448221138973
  * [SHS22] Ellen Simpson, Andrew Hamann and Bryan Semaan “How to Tame “Your” Algorithm: LGBTQ+ Users’ Domestication of TikTok” In Proc. ACM Hum.-Comput. Interact. 6.GROUP New York, NY, USA: Association for Computing Machinery, 2022, pp. 1–27
  * [Tan93] Ming Tan “Multi-agent reinforcement learning: Independent vs. cooperative agents” In Proceedings of the tenth international conference on machine learning, 1993
  * [WCM+20] Dakuo Wang, Elizabeth Churchill, Pattie Maes, Xiangmin Fan, Ben Shneiderman, Yuanchun Shi and Qianying Wang “From Human-Human Collaboration to Human-AI Collaboration: Designing AI Systems That Can Work Together with People” In Extended Abstracts of the 2020 CHI Conference on Human Factors in Computing Systems, CHI EA ’20 Honolulu, HI, USA: Association for Computing Machinery, 2020
  * [WWM+19] Dakuo Wang, Justin D Weisz, Michael Muller, Parikshit Ram, Werner Geyer, Casey Dugan, Yla Tausczik, Horst Samulowitz and Alexander Gray “Human-AI Collaboration in Data Science: Exploring Data Scientists’ Perceptions of Automated AI” In Proc. ACM Hum.-Comput. Interact. 3.CSCW New York, NY, USA: Association for Computing Machinery, 2019, pp. 1–24
  * [WAO20] M Wu, S Amin and A Ozdaglar “Multi-agent Bayesian Learning with Adaptive Strategies: Convergence and Stability” In arXiv preprint arXiv:2010.09128 arxiv.org, 2020
  * [WAO21] M Wu, S Amin and A Ozdaglar “Multi-agent Bayesian Learning with Best Response Dynamics: Convergence and Stability” In arXiv preprint arXiv:2109.00719 arxiv.org, 2021
  * [YSE19] Lantao Yu, Jiaming Song and Stefano Ermon “Multi-Agent Adversarial Inverse Reinforcement Learning” In Proceedings of the 36th International Conference on Machine Learning 97, Proceedings of Machine Learning Research PMLR, 2019, pp. 7194–7201
  * [ZYB21] Kaiqing Zhang, Zhuoran Yang and Tamer Başar “Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms” In Handbook of Reinforcement Learning and Control Cham: Springer International Publishing, 2021, pp. 321–384
  * [ZMF+21] Rui Zhang, Nathan J McNeese, Guo Freeman and Geoff Musick ““An Ideal Human”: Expectations of AI Teammates in Human-AI Teaming” In Proc. ACM Hum.-Comput. Interact. 4.CSCW3 New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–25
  * [ZMS+21] Tijana Zrnic, Eric Mazumdar, Shankar Sastry and Michael Jordan “Who Leads and Who Follows in Strategic Classification?” In Advances in neural information processing systems 34 proceedings.neurips.cc, 2021, pp. 15257–15269

### References

  * [BM93a] James Bergin and W Bentley MacLeod “Continuous Time Repeated Games” In International economic review 34.1 [Economics Department of the University of Pennsylvania, Wiley, Institute of SocialEconomic Research, Osaka University], 1993, pp. 21–37
  * [FL93a] Drew Fudenberg and David K Levine “Self-Confirming Equilibrium” In Econometrica: journal of the Econometric Society 61.3 [Wiley, Econometric Society], 1993, pp. 523–545
  * [KL93a] Ehud Kalai and Ehud Lehrer “Subjective Equilibrium in Repeated Games” In Econometrica: journal of the Econometric Society 61.5 [Wiley, Econometric Society], 1993, pp. 1231–1240
  * [Tan93a] Ming Tan “Multi-agent reinforcement learning: Independent vs. cooperative agents” In Proceedings of the tenth international conference on machine learning, 1993
  * [KL95a] Ehud Kalai and Ehud Lehrer “Subjective games and equilibria” In Games and economic behavior 8.1, 1995, pp. 123–163
  * [Kra99a] Roderick M Kramer “Trust and distrust in organizations: Emerging perspectives, enduring questions” In Annual review of psychology 50.1 Annual Reviews 4139 El Camino Way, PO Box 10139, Palo Alto, CA 94303-0139, USA, 1999, pp. 569–598
  * [Nis01a] Helen Nissenbaum “Securing trust online: Wisdom or oxymoron” In BUL Rev. 81 HeinOnline, 2001, pp. 635
  * [Har06a] Russell Hardin “Trust” Polity, 2006
  * [MS06a] George J Mailath and Larry Samuelson “Repeated games and reputations: Long-Run relationships” New York, NY: Oxford University Press, 2006
  * [MT07a] Frank McSherry and Kunal Talwar “Mechanism Design via Differential Privacy” In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07) ieeexplore.ieee.org, 2007, pp. 94–103
  * [BBD08a] Lucian Busoniu, Robert Babuska and Bart De Schutter “A comprehensive survey of multiagent reinforcement learning” In IEEE transactions on systems, man and cybernetics. Part C, Applications and reviews: a publication of the IEEE Systems, Man, and Cybernetics Society 38.2 Institute of ElectricalElectronics Engineers (IEEE), 2008, pp. 156–172
  * [RBK+10a] Aaron Roth, Maria Florina Balcan, Adam Kalai and Yishay Mansour “On the Equilibria of Alternating Move Games” In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings Society for IndustrialApplied Mathematics, 2010, pp. 805–816
  * [BKS12a] Michael Brückner, Christian Kanzow and Tobias Scheffer “Static prediction games for adversarial learning problems” Accessed: 2023-10-31 jmlr.org, https://www.jmlr.org/papers/volume13/brueckner12a/brueckner12a.pdf, 2012
  * [NST12a] Kobbi Nissim, Rann Smorodinsky and Moshe Tennenholtz “Approximately optimal mechanism design via differential privacy” In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12 Cambridge, Massachusetts: Association for Computing Machinery, 2012, pp. 203–213
  * [ARS13a] Kareem Amin, Afshin Rostamizadeh and Umar Syed “Learning prices for repeated auctions with strategic buyers” In Advances in neural information processing systems 26 proceedings.neurips.cc, 2013
  * [Boh16a] J Aislinn Bohren “Informational herding with model misspecification” In Journal of Economic Theory 163 Elsevier, 2016, pp. 222–247
  * [EP16a] Ignacio Esponda and Demian Pouzo “Berk–Nash equilibrium: A framework for modeling agents with misspecified models” In Econometrica 84.3 Wiley Online Library, 2016, pp. 1093–1130
  * [HDA+16a] Dylan Hadfield-Menell, Anca Dragan, Pieter Abbeel and Stuart Russell “Cooperative inverse reinforcement learning” In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16 Barcelona, Spain: Curran Associates Inc., 2016, pp. 3916–3924
  * [HMP+16a] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou and Mary Wootters “Strategic Classification” In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS ’16 Cambridge, Massachusetts, USA: Association for Computing Machinery, 2016, pp. 111–122
  * [FRS17a] D Fudenberg, G Romanyuk and P Strack “Active learning with a misspecified prior” In Theoretical Economics Wiley Online Library, 2017
  * [DRS+18a] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner and Zhiwei Steven Wu “Strategic Classification from Revealed Preferences” In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18 Ithaca, NY, USA: Association for Computing Machinery, 2018, pp. 55–70
  * [ACK+19a] Jacob D Abernethy, Rachel Cummings, Bhuvesh Kumar, Sam Taggart and Jamie H Morgenstern “Learning auctions with robust incentive guarantees” In Advances in neural information processing systems 32 proceedings.neurips.cc, 2019
  * [BNK+19a] Gagan Bansal, Besmira Nushi, Ece Kamar, Walter S Lasecki, Daniel S Weld and Eric Horvitz “Beyond accuracy: The role of mental models in human-AI team performance” In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing 7 Association for the Advancement of Artificial Intelligence (AAAI), 2019, pp. 2–11
  * [EBC+19a] Neta Ezer, Sylvain Bruni, Yang Cai, Sam J Hepenstal, Christopher A Miller and Dylan D Schmorrow “Trust Engineering for Human-AI Teams” In Proceedings of the Human Factors and Ergonomics Society … Annual Meeting Human Factors and Ergonomics Society. Meeting 63.1 SAGE Publications Inc, 2019, pp. 322–326
  * [KN19a] Yash Kanoria and Hamid Nazerzadeh “Incentive-Compatible Learning of Reserve Prices for Repeated Auctions” In Companion Proceedings of The 2019 World Wide Web Conference, WWW ’19 San Francisco, USA: Association for Computing Machinery, 2019, pp. 932–933
  * [WWM+19a] Dakuo Wang, Justin D Weisz, Michael Muller, Parikshit Ram, Werner Geyer, Casey Dugan, Yla Tausczik, Horst Samulowitz and Alexander Gray “Human-AI Collaboration in Data Science: Exploring Data Scientists’ Perceptions of Automated AI” In Proc. ACM Hum.-Comput. Interact. 3.CSCW New York, NY, USA: Association for Computing Machinery, 2019, pp. 1–24
  * [YSE19a] Lantao Yu, Jiaming Song and Stefano Ermon “Multi-Agent Adversarial Inverse Reinforcement Learning” In Proceedings of the 36th International Conference on Machine Learning 97, Proceedings of Machine Learning Research PMLR, 2019, pp. 7194–7201
  * [FII20a] Mira Frick, Ryota Iijima and Yuhta Ishii “Stability and robustness in misspecified learning models” Cowles Foundation Discussion Paper, 2020
  * [Mar20a] Aarian Marshall “Uber Changes Its Rules, and Drivers Adjust Their Strategies”, 2020 URL: https://www.wired.com/story/uber-changes-rules-drivers-adjust-strategies/
  * [OY20a] Kazuo Okamura and Seiji Yamada “Adaptive trust calibration for human-AI collaboration” In PloS one 15.2 journals.plos.org, 2020, pp. e0229132
  * [PZM+20a] Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner and Moritz Hardt “Performative Prediction” In Proceedings of the 37th International Conference on Machine Learning 119, Proceedings of Machine Learning Research PMLR, 2020, pp. 7599–7609
  * [WCM+20a] Dakuo Wang, Elizabeth Churchill, Pattie Maes, Xiangmin Fan, Ben Shneiderman, Yuanchun Shi and Qianying Wang “From Human-Human Collaboration to Human-AI Collaboration: Designing AI Systems That Can Work Together with People” In Extended Abstracts of the 2020 CHI Conference on Human Factors in Computing Systems, CHI EA ’20 Honolulu, HI, USA: Association for Computing Machinery, 2020
  * [WAO20a] M Wu, S Amin and A Ozdaglar “Multi-agent Bayesian Learning with Adaptive Strategies: Convergence and Stability” In arXiv preprint arXiv:2010.09128 arxiv.org, 2020
  * [BCD+21a] Ying Bao, Xusen Cheng, Triparna De Vreede and Gert-Jan De Vreede “Investigating the relationship between AI and trust in human-AI collaboration” In Hawaii International Conference on System Sciences 2021 (HICSS-54) aisel.aisnet.org, 2021
  * [BH21a] J Aislinn Bohren and Daniel N Hauser “Learning with heterogeneous misspecified models: Characterization and robustness” In Econometrica: journal of the Econometric Society 89.6 The Econometric Society, 2021, pp. 3025–3077
  * [DLM+21a] Yuan Deng, Sebastien Lahaie, Vahab Mirrokni and Song Zuo “Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing” In Proceedings of the 38th International Conference on Machine Learning 139, Proceedings of Machine Learning Research PMLR, 2021, pp. 2601–2610
  * [FLS21a] Drew Fudenberg, Giacomo Lanzani and Philipp Strack “Limit points of endogenous misspecified learning” In Econometrica: journal of the Econometric Society 89.3 The Econometric Society, 2021, pp. 1065–1098
  * [GNE+21a] Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen and Nir Rosenfeld “Strategic Classification in the Dark” In Proceedings of the 38th International Conference on Machine Learning 139, Proceedings of Machine Learning Research PMLR, 2021, pp. 3672–3681
  * [WAO21a] M Wu, S Amin and A Ozdaglar “Multi-agent Bayesian Learning with Best Response Dynamics: Convergence and Stability” In arXiv preprint arXiv:2109.00719 arxiv.org, 2021
  * [ZYB21a] Kaiqing Zhang, Zhuoran Yang and Tamer Başar “Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms” In Handbook of Reinforcement Learning and Control Cham: Springer International Publishing, 2021, pp. 321–384
  * [ZMF+21a] Rui Zhang, Nathan J McNeese, Guo Freeman and Geoff Musick ““An Ideal Human”: Expectations of AI Teammates in Human-AI Teaming” In Proc. ACM Hum.-Comput. Interact. 4.CSCW3 New York, NY, USA: Association for Computing Machinery, 2021, pp. 1–25
  * [ZMS+21a] Tijana Zrnic, Eric Mazumdar, Shankar Sastry and Michael Jordan “Who Leads and Who Follows in Strategic Classification?” In Advances in neural information processing systems 34 proceedings.neurips.cc, 2021, pp. 15257–15269
  * [BHK22a] Gavin Brown, Shlomi Hod and Iden Kalemaj “Performative Prediction in a Stateful World” In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics 151, Proceedings of Machine Learning Research PMLR, 2022, pp. 6045–6061
  * [CIM22a] S H Cen, A Ilyas and A Madry “A Game-Theoretic Perspective on Trust in Recommendation” In NeurIPS Workshop on Responsible Decision Making in Dynamic Environments (RDD), 2022
  * [HLN+22a] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert and Alexander Wei “Learning in Stackelberg Games with Non-myopic Agents” In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22 Boulder, CO, USA: Association for Computing Machinery, 2022, pp. 917–918
  * [KMR22a] Jon Kleinberg, Sendhil Mullainathan and Manish Raghavan “The Challenge of Understanding What Users Want: Inconsistent Preferences and Engagement Optimization” In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22 Boulder, CO, USA: Association for Computing Machinery, 2022, pp. 29
  * [LR22a] Sagi Levanon and Nir Rosenfeld “Generalized Strategic Classification and the Case of Aligned Incentives” In Proceedings of the 39th International Conference on Machine Learning 162, Proceedings of Machine Learning Research PMLR, 2022, pp. 12593–12618
  * [MBF+22a] Hussein Mozannar, Gagan Bansal, Adam Fourney and Eric Horvitz “Reading Between the Lines: Modeling User Behavior and Costs in AI-Assisted Programming”, 2022 arXiv:2210.14306 [cs.SE]
  * [NCE+22a] Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui and Vianney Perchet “Learning in Repeated Auctions” In Foundations and Trends® in Machine Learning 15.3 Now Publishers, 2022, pp. 176–334
  * [SVM22a] Ignacio Siles, Luciana Valerio-Alfaro and Ariana Meléndez-Moran “Learning to like TikTok . . . and not: Algorithm awareness as process” In New Media & Society SAGE Publications, 2022, pp. 14614448221138973
  * [SHS22a] Ellen Simpson, Andrew Hamann and Bryan Semaan “How to Tame “Your” Algorithm: LGBTQ+ Users’ Domestication of TikTok” In Proc. ACM Hum.-Comput. Interact. 6.GROUP New York, NY, USA: Association for Computing Machinery, 2022, pp. 1–27
  * [CIA+23a] Sarah H. Cen, Andrew Ilyas, Jennifer Allen, Hannah Li, David Rand and Aleksander Madry “Measuring Strategization in Recommendation: Users Adapt Their Behavior to Shape Future Content” In Preprint, 2023
  * [HHP23a] Andreas Haupt, Dylan Hadfield-Menell and Chara Podimata “Recommending to Strategic Users” In Foundations of Responsible Computing, 2023
  * [HHC23a] Keke Hou, Tingting Hou and Lili Cai “Exploring Trust in Human–AI Collaboration in the Context of Multiplayer Online Games” In Systems 11.5 Multidisciplinary Digital Publishing Institute, 2023, pp. 217