# Content Prompting: Modeling Content Provider Dynamics
to Improve User Welfare in Recommender Ecosystems

Siddharth Prasad1, Martin Mladenov2, Craig Boutilier2 Work performed as a
student researcher at Google Research.

###### Abstract

Users derive value from a recommender system (RS) only to the extent that it
is able to surface content (or items) that meet their needs/preferences. While
RSs often have a comprehensive view of user preferences across the entire user
base, content providers, by contrast, generally have only a _local_ view of
the preferences of users that have interacted with their content. This limits
a provider’s ability to offer _new_ content to best serve the broader
population. In this work, we tackle this _information asymmetry_ with _content
prompting policies_. A _content prompt_ is a hint or suggestion to a provider
to make available novel content for which the RS predicts _unmet user demand_.
A _prompting policy_ is a sequence of such prompts that is responsive to the
dynamics of a provider’s beliefs, skills and incentives. We aim to determine a
_joint_ prompting policy that induces a set of providers to make content
available that optimizes _user social welfare in equilibrium_ , while
respecting the incentives of the providers themselves. Our contributions
include: (i) an abstract model of the RS ecosystem, including content provider
behaviors, that supports such prompting; (ii) the design and theoretical
analysis of sequential prompting policies for individual providers; (iii) a
mixed integer programming formulation for optimal joint prompting using path
planning in content space; and (iv) simple, proof-of-concept experiments
illustrating how such policies improve ecosystem health and user welfare.

##  1 Introduction

Recommender systems (RSs) play a critical role in surfacing items (e.g.,
products, services or content) to their users, especially when the item corpus
is vast. Of course, RSs not only create value for their users; they provide a
significant service to _item providers_ by helping them identify a market or
audience for their offerings. Given the central role RSs play in facilitating
the interaction between providers and users, we view the RS as lying at the
heart of a complex _ecosystem_ comprising all users, all providers, and the RS
itself. A healthy recommender ecosystem requires that the item corpus be
updated constantly to reflect the ever-changing needs and preferences of its
users.

Naturally, one might expect the RS to assist providers in developing _new_
content (or products, services, etc.) to meet changing user needs. However,
this is rarely done—providers are generally left to their own devices to
explore, design and test new offerings. As a result, the ecosystem is often in
an _economically inefficient state_ , generating less-than-optimal social
welfare for its users (and its providers).

Generally, while RSs model user preferences for items _in the corpus_ , these
models often generalize _out-of-corpus_ to some extent, thus revealing user
preferences for “hypothetical” items the RS has not yet seen. This can be
understood as a comprehensive view of _latent consumer demand_. Unfortunately,
providers lack this global view, since they generally interact with only a
small subset of users. Moreover, the RS has a holistic view of the corpus, and
possibly the abilities of providers to source or create new items; this can be
interpreted as a deep perspective on _potential supply_ , a degree of insight
also not generally shared by providers. It is this _information asymmetry_
between the RS and the providers that induces economic friction, preventing
providers from making optimal design, sourcing or creation decisions regarding
new items they might offer to users through the RS.

In this work, we develop a stylized model for understanding this information
asymmetry and propose techniques to minimize its impact on (user) social
welfare. Specifically, we propose the use of _provider prompting policies_ by
the RS. These policies suggest novel items a provider might offer, over time,
in a way that accounts for: (i) a provider’s incentives and beliefs w.r.t.
audience/market and its skills; (ii) the dynamics of such audience and skill
beliefs; and (iii) the potential clash of policy prompts to different
providers. Under certain conditions, we show that our prompting policies lead
to a socially optimal provider equilibrium in which providers are incentivized
to make items available that maximize user welfare (i.e., sum of user
utilities for recommended items).

The remainder of the paper is organized as follows. After a brief discussion
of related work (Sec. 2), we provide a detailed problem formulation of the
process dynamics that incorporates: user affinities and social welfare;
content provider skills, beliefs, incentives and best responses; and RS
matching and prompting policies (Sec. 3). In Sec. 4, we detail _single-
provider prompting policies_ in which the RS suggests a sequence of content
points to one provider, assuming others remain fixed. These policies
_incentivize_ the provider to follow a content path that reaches a socially
optimal equilibrium (w.r.t. user welfare) in polynomial time. We extend this
model in Sec. 5 to allow for the coordinated, _joint prompting_ of all
providers, and develop a mixed integer programming (MIP) formulation to solve
the induced _multi-agent path planning problem_. In Sec. 6, we evaluate our
procedures on random problem instances to show the significant improvement in
social welfare that can be created by prompting providers. While somewhat
stylized, our model provides important first steps to a more _holistic,
incentive-aware design of recommender ecosystems_.

##  2 Related Work

RSs typically rely on some form of prediction of a user’s interests or intent,
based on past usage or ratings data (Konstan et al. 1997; Jacobson et al.
2016; Covington, Adams, and Sargin 2016). We do not commit to a specific
method for generating such models, but our approach can be understood in terms
of latent-space user and item embeddings of the type generated by
collaborative filtering (CF) methods (e.g., matrix factorization
(Salakhutdinov and Mnih 2007) or neural CF (He et al. 2017; Beutel et al.
2018)) to estimate user affinity to specific items/content.

Recently there has been a growing appreciation for the multiagent interactions
between users, or user groups, and content providers in an RS (Abdollahpouri
and Burke 2021). In this work, we focus on the incentives and behaviors of
providers and assume user interests are fixed. As such, of some relevance is
work that considers “fairness of exposure” to the items offered by different
providers, and modifications of the RS policy to increase such fairness (Singh
and Joachims 2018; Biega, Gummadi, and Weikum 2018; Wu et al. 2022; Heuss,
Sarvi, and de Rijke 2022).

More directly connected is work that explores the behavior of providers in
response to RS policies. Of special relevance is a recent line of work
investigating the incentives that providers have to change the content they
offer, and game-theoretic equilibria in such settings. Ben-Porat and
Tennenholtz (2018) develop a game-theoretic model of RSs whose providers act
strategically—by making available or withholding content—to maximize their
user engagement in an RS. Ben-Porat et al. (2019) draw a direct connection
between facility location (or Hotelling) games and RSs with strategic
providers. Both Hron et al. (2022) and Jagadeesan, Garg, and Steinhardt (2022)
study multi-dimensional content models, showing under what conditions Nash
equilibria exist, how providers “position” themselves in content space, and
the effect this can have on (say) generalization vs. specialization of content
production. While this work is similar to ours in its study of adaptive
provider behavior, it differs by assuming that providers have full knowledge
of supply and demand, something that is far from true in most RSs. By
contrast, we focus on the _information asymmetry between providers and the RS_
, and the active role the RS can play to reduce it. Our approach allows self-
interested providers to make more informed content decisions that induce
equilibria that better serve both users and providers. We also adopt a more
nuanced model of provider skill and beliefs.

We focus on how the RS can intervene to shape the desired equilibrium. Ben-
Porat et al. (2019) (see above) examine Nash equilibria in the 1-D case under
different RS matching policies while Ben-Porat, Rosenberg, and Tennenholtz
(2020) extend and generalize this analysis further. Mladenov et al. (2020)
investigate (non-strategic) provider behaviors driven by the engagement they
obtain, and RS policies that optimize long-term user welfare via matchings
that anticipate the equilibria of the induced dynamical system. Neither model
addresses information asymmetry or active provider intervention.

##  3 Problem Formulation

We begin with a formulation that adopts a somewhat stylized model of a content
RS, based on user and item embeddings. We also adopt a simplified model of
content provider _skills_ and _beliefs_ , their dynamics, their decisions, and
the RS knowledge of these elements. While simpler than a real RS ecosystem,
this model contains the essential elements required to reason effectively
about provider-prompting policies. Our multi-stage model of the RS ecosystem
uses a single-stage model based on that of Mladenov et al. (2020), though we
develop a very different dynamics model.

### Providers, Users and One-stage Recommendations

We assume an RS that matches _users_ to the content made available by _content
providers_. Our process is organized into $T$ stages. We use $T$ for both
finite and infinite-horizons, taking $\lim_{T\to\infty}$ in the latter case.)
At the beginning of each stage $t\leq T$, each provider determines the content
they will make available. During the stage, as users arrive, the RS matches
them to providers (and their content) using some fixed policy.

Providers, Content Points and Skill: We assume a finite set of _providers_
$\mathcal{K}=\\{1,\ldots,K\\}$. At stage $t$, each provider determines the
content it will make available for recommendation, from a finite set of
_content points_ $\mathcal{J}=\\{1,\ldots,J\\}\subset\mathbb{R}^{d}$, where
each point is an embedding of that content.111This can be generalized to a
continuous set of points in some embedding space. However, our user utility
and provider reward models ensure a provider only chooses from a finite set of
points in equilibrium. This contrasts with approaches that use simpler
provider rewards (e.g., those that simply count matched users (Jagadeesan,
Garg, and Steinhardt 2022), which can induce a continuum of equally good
equilibria). Let $\ell^{t}_{k}\in\mathcal{J}$ be the content generated by
provider $k$ at stage $t$, which we call $k$’s _location_ at $t$. The
_location vector_ $L^{t}=\langle\ell^{t}_{1},\ldots,\ell^{t}_{K}\rangle$
reflects the content decisions of all providers.

Some providers are more adept at producing certain types of content than
others (e.g., due to specific talent, interests, facilities, etc.). Let
$s_{k,j}\in[0,1]$, be $k$’s (true) _skill_ w.r.t. to point $j$, reflecting
this aptitude. Let $S$ be the (true) _provider skill matrix_ , and $S_{k}$
(the $k$th row of $S$) the _skill vector_ for provider $k$. We treat skill as
fixed. Skill will exhibit generalization across “similar” content points, but
we make no such assumption here.

Users, Affinity, Utility and Reward: We assume a finite set
$\mathcal{Q}\subset\mathbb{R}^{d}$ of users (or queries). At stage $t$, a set
of users/queries is drawn from (known or estimated) distribution
$P^{t}(\mathcal{Q})$. When $|\mathcal{Q}|$ is small, we interpret each
$q\in\mathcal{Q}$ as representative of a _user type_. For ease of exposition,
we take $P^{t}$ to be uniform. Each user $i\in\mathcal{Q}$ has an inherent
_affinity_ for content $j\in\mathcal{J}$ given by a non-negative, bounded
_affinity function_ $\sigma(i,j)$, e.g., dot product or cosine similarity if
we use some _latent space_ $X\subseteq\mathbb{R}^{d}$ to embed users and
content, as in matrix factorization or neural CF. Together with affinity, the
skill of the provider dictates user utility: if $j$ is offered by provider $k$
and recommended to $i$, $i$’s _utility_ for $j$ is given by _utility function_
$f(\sigma(i,j),s_{k,j})$. This might be as simple as the product
$\sigma(i,j)\cdot s_{k,j}$.

We assume a provider’s _reward_ for that recommendation is equal to the user’s
utility. Increasingly, RSs and content providers focus on user satisfaction
beyond simple engagement metrics (Garcia-Gathright et al. 2018; Goodrow 2021)
and long-term utility; we use the term “utility,” rather than engagement, to
emphasize this. We assume the RS aims to maximize total user utility. Equating
user utility with provider reward also aligns RS, user, and provider
incentives; but if providers optimize for different forms of engagement, that
can be incorporated below.

Matching Policies and Value: When user $q$ arrives, the RS recommends the
content of some provider $k$. A _(stochastic) matching_
$\mu:\mathcal{Q}\rightarrow\Delta(\mathcal{K})$ associates each
$q\in\mathcal{Q}$ with a distribution over providers.222We adopt this model
for simplicity. Generally, users issue different queries, or request
recommendations in different contexts, under which the best match differs, a
detail handled by all modern RSs. Likewise, providers offer multiple content
items, and RSs match to specific provider content. Our formulation applies
_mutatis mutandis_ if we match _queries_ to provider _content_ rather than
users to providers. We write $\mu(q,k)$ to denote the match probability. The
_value_ of $\mu$ given a location vector $L^{t}$ is its expected user utility:

$V(\mu,L^{t})=\sum_{q\in\mathcal{Q}}\sum_{k\in\mathcal{K}}\mu(q,k)f(\sigma(q,\ell^{t}_{k}),s_{k,\ell^{t}_{k}}).$

The _natural matching_ $\mu^{\ast}_{L^{t}}$ which maximizes this value would
be optimal if $L^{t}$ were stationary, but given the dynamics below, we avoid
the term “optimal” to describe this policy. Implementing $\mu^{\ast}_{L^{t}}$
requires complete knowledge of user and content embeddings and provider
skills, which we assume the RS has.

### Provider Beliefs and Decisions, and RS Prompts

We now describe the process by which the $T$ stages unfold, including how
providers update their beliefs about their skills and audience, and how these
beliefs influence their content decisions.

Skill and Audience Beliefs: Providers base their decisions about which content
to make available at stage $t$ by estimating their own audience’s utility.
This requires estimating both their own skill and the (affinity-weighted)
audience they expect to be generated for them by the RS for any content point
$j\in\mathcal{J}$ they might offer. Each provider $k$ has a _skill belief
vector_ $\widetilde{S}^{t}_{k}$, where entry $\widetilde{s}^{t}_{k,j}\in[0,1]$
denotes $k$’s _estimated skill or skill belief_ w.r.t. point $j$. Let
$\widetilde{S}^{t}$ be the matrix of such skill vectors ($k$’s beliefs are
over its own skill, not that of other providers $i\neq k$).

While true skill $S$ is fixed, estimates $\widetilde{S}^{t}$ change over time
as, say, the provider gains experience with new content. We assume a skill
belief update function of the form
$\widetilde{S}_{k}^{t+1}=\mathit{bu}_{S}(L^{t}_{k},\widetilde{S}_{k}^{t},E^{t}_{k})$,
i.e., $k$’s skill belief at stage $t+1$ depends on its prior belief
$\widetilde{S}_{k}^{t}$ and the utility $E^{t}_{k}$ garnered at its location
$L^{t}_{k}=j$. For simplicity, we sometimes assume a simple deterministic (and
non-generalizing) skill update $\mathit{bu}_{S,D}$: if $\ell^{t}_{k}=j$, $k$’s
belief for point $j$ collapses to its true skill $s_{k,j}$ for all
$t^{\prime}>t$, with no other $j^{\prime}$ being updated at time $t+1$. This
is easily generalized, though the optimization below requires (an estimate of)
an update model.

Each provider $k$ also has an _audience (affinity) belief_
$\widetilde{a}^{t}_{k,j}\leq Q$ that measures its estimate of the total
audience affinity it expects to attain if it offers content at point $j$.
Define vector $\widetilde{A}^{t}_{k}$ and matrix $\widetilde{A}^{t}$ in the
obvious way. These estimates also vary with time. As with skills, we assume an
audience update function
$\widetilde{A}_{k}^{t+1}=\mathit{bu}_{A}(L^{t}_{k},\widetilde{A}_{k}^{t},E^{t}_{k})$,
and sometimes assume a simple deterministic model $\mathit{bu}_{A,D}$: if
$\ell^{t}_{k}=j$, $k$’s audience belief for point $j$ collapses to its
realized audience $A_{k,j}$ at time $t+1$, so
$\widetilde{A}^{t+1}_{k,j}=A_{k,j}$. Unlike skill beliefs, these can change
with each new experience at point $j$. Together with deterministic skill
update, this means a provider can determine the (expected) total user
affinity—assuming the _number_ of users is observable while affinity is
estimated—to which is was matched from the utility signal under simple, say,
linear utility models (e.g., if user utility is the product of provider skill
and user affinity). This too is easily generalized. One exception to this form
of audience belief update is if the RS provides a _prompt_ , defined next.

Prompts: To encourage providers to generate content that increases user
utility, the RS uses _prompts_ , that is, suggestions to providers to make
content available at certain points. To incentivize such content, the RS can
(temporarily) commit some amount of audience affinity to a provider. Formally,
an RS _prompt_ $\nu^{t-1}_{k}=(j,E)$ of provider $k$ at time $t-1$ consists
of: (i) a suggested content point/location $j=\ell^{t}_{k}$ for $k$ to produce
at stage $t$; and (ii) a commitment to a (minimum) level of audience utility
$E=E^{t}_{k}$ at stage $t$ if $k$ produces $j$.

The effect on $k$’s audience belief depends on their level of _trust_ in the
RS. Let $\lambda^{t}_{k}\in[0,1]$ denote $k$’s current trust; then
$\widetilde{A}^{t}_{j}\leftarrow\mathit{bu}_{P}(\widetilde{A}^{t}_{j},E,\lambda^{t})$,
where $\mathit{bu}_{P}$ is an update function that determines $k$’s _prompted
belief_ used to make its next content decision (see below). This prompted
belief is tentative, as it will be updated given the _realized audience_ at
stage $t+1$ (via $\mathit{bu}_{A}$). We consider two example updates. The
first is _incremental-trust belief update_ , where: (i)
$\mathit{bu}_{P,I}(\widetilde{A}^{t}_{j},E,\lambda^{t})=(1-\lambda^{t})\cdot\widetilde{A}^{t}_{j}+\lambda^{t}\cdot
E$; and (ii) the trust parameter $\lambda^{t+1}=\tau(\lambda^{t},E,E^{t}_{r})$
is updated given $k$’s realized utility using a _trust update function_
$\tau$. The second is _full-trust belief update_ , where
$\mathit{bu}_{P,F}(\widetilde{A}^{t}_{j},E,\lambda^{t})=E$.

Process Dynamics: RS dynamics evolve as follows. The state $s^{t}=\langle
L^{t},\widetilde{S}^{t},\widetilde{A}^{t}\rangle$ at stage $t$ consists of:
location vector $L^{t}$, skill belief matrix $\widetilde{S}^{t}$, and audience
belief matrix $\widetilde{A}^{t}$. The location $\ell^{t}_{k}$ chosen by
provider $k$ is consistent with their beliefs (see below). The RS generates a
matching $\mu^{t}$, the realization of which induces value for users, and
utility for providers. Based on their realized utility, each provider updates
its (skill and audience) beliefs—thought of as a _half state_
$s^{t+\frac{1}{2}}=\langle
L^{t},\widetilde{S}^{t+\frac{1}{2}},\widetilde{A}^{t+\frac{1}{2}}\rangle$
(locations do not yet change). The RS may then _prompt_ providers by providing
information $\nu^{t}$ about the audience they will receive if they offer
content at a specific point, which can induce a further update in their
audience belief. Prompts influence only audience beliefs, not skill beliefs,
so $\widetilde{S}^{t+1}=\widetilde{S}^{t+\frac{1}{2}}$. Given updated beliefs
$\widetilde{S}_{k}^{t+1}$ and $\widetilde{A}_{k}^{t+1}$, each $k$ selects
their next location $\ell^{t+1}_{k}$, determining state $s^{t+1}$. The
process, schematically represented below, then repeats

$\textstyle\langle
L^{t},\widetilde{A}^{t},\widetilde{S}^{t}\rangle\xrightarrow{\mu}\langle
L^{t},\widetilde{A}^{t+\frac{1}{2}},\widetilde{S}^{t+\frac{1}{2}}\rangle\xrightarrow{\nu}\langle
L^{t+1},\widetilde{A}^{t+1},\widetilde{S}^{t+1}\rangle$

Provider Best Responses: To model provider choices of location at each stage,
we assume providers are _myopic utility maximizers_ w.r.t. their own beliefs,
but are not strategic in the “dynamic” sense (that is, they do not reason
about how their actions might impact the RS policy or the behavior of other
providers). Thus, given beliefs $\widetilde{S}^{t}_{k},\widetilde{A}^{t}_{k}$
at stage $t$, $k$ chooses the location $\ell^{t}_{k}$ corresponding to their
_best response_ , i.e., the content point
$\ell^{t}_{k}=\mathit{BR}(\widetilde{S}^{t}_{k},\widetilde{A}^{t}_{k})=\arg\max_{j\in\mathcal{J}}\widetilde{s}^{t}_{k,j}\widetilde{a}^{t}_{k,j}$
for which it predicts the greatest utility. We call state $s^{t}=\langle
L^{t},\widetilde{S}^{t},\widetilde{A}^{t}\rangle$ _rationalizable_ if
$\ell^{t}_{k}=\mathit{BR}(\widetilde{S}^{t}_{k},\widetilde{A}^{t}_{k})$ for
all providers $k$. We assume that provider location choice satisfies
rationalizability in what follows.

Stable Matchings and States: A matching is _(myopically) stable_ if—with no RS
prompts—it gives no incentive for a location change. Let $s^{t}=\langle
L^{t},\widetilde{S}^{t},\widetilde{A}^{t}\rangle$, let

$E_{k}^{t}=\sum_{i\in\mathcal{Q}}\mu^{t}(i,k)f(\sigma(i,\ell^{t}_{k}),s_{k,\ell^{t}_{k}})$

be $k$’s realized utility under $\mu^{t}$, and let

$\widetilde{S}_{k}^{t+1}=\mathit{bu}_{S}(L^{t}_{k},\widetilde{S}_{k}^{t},E^{t}_{k})$

be $k$’s updated skill belief. Without prompts,
$\widetilde{A}_{k}^{t+1}=\widetilde{A}_{k}^{t+\frac{1}{2}}$. We say that
$\mu^{t}$ is _myopically stable_ w.r.t. $s^{t}$ if, for all $k\in\mathcal{K}$:

$\widetilde{a}^{t+1}_{k,\ell^{t}_{k}}\widetilde{s}^{t+1}_{k,\ell^{t}_{k}}\geq\widetilde{a}^{t+1}_{k,j}\widetilde{s}^{t+1}_{k,j},\;\forall
j\neq\ell^{t}_{k},$

i.e., $k$’s current location $\ell^{t}_{k}$ remains a best response after it
experiences the utility induced by $\mu^{t}$.

While myopic stability is a desirable equilibrium property, it does not ensure
stability/equilibrium of the dynamical system. A matching/state may be
myopically stable simply due to the slowness of the process by which providers
update their beliefs. A true equilibrium notion requires that a stable state
persists indefinitely: we say state $s^{t}$ is _(non-myopically) stable_ if
there is a sequence of matchings $\mu^{t},\mu^{t+1},\ldots$ such that for all
providers $k$ and stages $t^{\prime}>t$,

$\widetilde{a}^{t^{\prime}}_{k,\ell^{t}_{k}}\widetilde{s}^{t^{\prime}}_{k,\ell^{t}_{k}}\geq\widetilde{a}^{t^{\prime}}_{k,j}\widetilde{s}^{t^{\prime}}_{k,j},\;\forall
j\neq\ell^{t}_{k}.$

A matching $\mu$ is _(non-myopically) stable_ w.r.t. $s^{t}$ if the matching
sequence $\mu^{t^{\prime}}=\mu,\forall t^{\prime}\geq t$ renders $s^{t}$
stable in the sense above. Once a desirable system state is reached, ideally
it will be stable w.r.t. a _single_ matching.

Overall Objective: Our overall objective is the maximization of user social
welfare: this may be $V(\mu,L^{T})$ at stage $T$ in the finite-horizon case,
or long-term expected average reward
$\lim_{T\to\infty}\mathbb{E}[\frac{1}{T}\sum_{t=0}^{T-1}V(\mu^{t},L^{t})]$. If
provider content decisions are fixed/cannot be influenced by the RS, this
simply requires the application of the natural matching $\mu^{\ast}_{L^{T}}$
relative to $L^{T}$. At the other extreme, if the RS could persuade providers
to move to arbitrary locations at will, the problem is akin to a facility
location or $k$-medians problem (Whelan, Harrell, and Wang 2015) where users
are clients whose (inverse) affinities reflect travel costs and provider skill
captures service costs. The reality of course is different—providers are
independent decision makers whose content decisions accord with their beliefs
and incentives.

The aim of a _prompting policy_ is to break the information asymmetry
described above to allow providers to better calibrate their audience and
skill beliefs so that their decisions lead to a (close to) welfare-optimizing
matching. Moreover, since providers make their own content decisions, we want
the final matching to be in _equilibrium_ , that is, be stable given
providers’ incentives. The RS also uses its _matching policy_ by (perhaps
temporarily) creating specific audience/utility levels that incentivize
providers to make suitable moves. Taken together, an RS policy has two parts:
a _matching policy_ that associates a matching $\mu^{t}$ with each state
$s^{t}=\langle L^{t},\widetilde{S}^{t},\widetilde{A}^{t}\rangle$; and a
_prompting policy_ that, for each half state $s^{t+\frac{1}{2}}=\langle
L^{t},\widetilde{S}^{t+\frac{1}{2}},\widetilde{A}^{t+\frac{1}{2}}\rangle$,
generates a prompt $\nu^{t}$.

##  4 Single-Provider Prompting Policies

A cornerstone of our approach and analysis is the _single-provider prompting
policy_. Here, we assume that the content decisions of all providers except
one, $k\in\mathcal{K}$, are fixed, and construct a prompting policy that
ensures $k$ moves to the location $j\in\mathcal{J}$ that maximizes user
welfare given the fixed locations of the other providers. Specifically, assume
a fixed location vector $L_{-k}$ that specifies $\ell_{k^{\prime}}$ for all
$k^{\prime}\neq k$, where $\ell^{t}_{k^{\prime}}=\ell_{k^{\prime}}$ for all
$t\leq T$; and an initial state $s^{0}=\langle
L^{0},\widetilde{S}^{0},\widetilde{A}^{0}\rangle$. Our goal is to design a
joint matching/prompting policy that induces $k$ to move to a target
$j^{\ast}_{k}\in\mathcal{J}$, inducing location vector
$L^{\texttt{prompt}}=L_{-k}\circ j_{k}^{\ast}$, that is optimal w.r.t. long-
term average reward:

$\lim_{T\to\infty}\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}V(\mu^{\ast}_{L^{\texttt{prompt}}},L^{\texttt{prompt}})\right].$

Furthermore, the policy should induce an _equilibrium_ , i.e., a stable state
where $k$ offers $j^{\ast}$ without additional prompts. Proofs of all results
in this section along with additional details of our formulation are provided
in Appendix A.

### Equilibrium with No Prompting

We illustrate the value of prompting policies with a simple example to show
the potential loss in total user utility/welfare that accrues without
prompting. Assume initial state $s^{0}$, where $k$’s beliefs are
$\widetilde{S}_{k}^{0}$ and $\widetilde{A}_{k}^{0}$, a matching policy
$\mu_{L}$ that is fixed for any location vector $L$ (e.g., the natural
matching), and let $E_{k,j}$ be $k$’s utility under $\mu_{L}$ if $\ell_{k}=j$.

Let $O\subseteq\mathcal{J}$ be $k$’s _undominated overestimates_ —these are
content points $j$ for which $k$ initially overestimates expected utility, but
for which no other point’s _true_ and _estimated_ values exceed $j$’s true
utility:

$O=\\{j:\widetilde{s}^{0}_{k,j}\widetilde{a}^{0}_{k,j}>E_{k,j},\nexists
j^{\prime}\\\ \quad\quad\text{ s.t.
}(\widetilde{s}^{0}_{k,j^{\prime}}\widetilde{a}^{0}_{k,j^{\prime}}>E_{k,j}\text{
and }E_{k,j^{\prime}}>E_{k,j})\\}.$

Under reasonable (e.g., monotonically converging) belief updates, and best
response behavior, $k$ will eventually try all undominated, overestimated
content points. For instance, under immediately collapsing skill beliefs, the
system reaches equilibrium in exactly $|O|$ steps: for any undominated $j$,
any other $j^{\prime}$ whose estimated utility is greater than $j$’s estimate
is tried before $j$, but $k$’s beliefs immediately collapse to give the true
value of $j^{\prime}$, which by assumption is less than that of $j$. Thus each
undominated $j$ will be tried once. Critically, _no dominated point_
$j^{\prime\prime}$ will ever be tried, since at least one undominated point
has a _true_ utility greater than $k$’s estimate for $j^{\prime\prime}$.

This lack of exploration can lead to an _arbitrarily suboptimal_ equilibrium.
For instance, suppose there are only two points such that
$\widetilde{s}^{0}_{k,2}\widetilde{a}^{0}_{k,2}>E_{k,1}>E_{k,2}>\widetilde{s}^{0}_{k,1}\widetilde{a}^{0}_{k,1}$.
Then $k$ only offers the suboptimal point $2$, whose true value is greater
than $k$’s estimate for point $1$, despite the fact that $1$’s true value is
greater than $2$’s. An RS prompt can reveal to $k$ the true utility at point
$2$, thus incentivizing $k$ to offer $2$ (and realize its true value). This
issue is further exacerbated by the fact that $k$ will never visit any
dominated point, as detailed above.

The provider thus faces an exploration problem: indeed, natural schemes like
“optimism in the face of uncertainty” would ensure $k$ tries points such as
point 1. However, the cost of exploration (e.g., creating new content), the
lack of direct control (e.g., predicting audience), and inherent risk aversion
may prevent adequate _self-exploration_ by providers. Prompting reduces this
risk by providing additional certainty, through promised utility, and
incentivizing behavior that allows the provider to update their audience/skill
beliefs where they might otherwise not. That said, we note that in some cases,
provision of certain points may not be incentivizable by the RS, e.g., when
$k$ underestimates it skill $s_{k,j}$ so drastically that no promised audience
utility can incentivize $k$ to move to $j$, even with full trust.

### Prompting under Non-generalizing Belief Updates

Let $\mu^{t}$ be a stable matching w.r.t the current state $s^{t}$, with
$\ell^{t}_{k}=j$ and $E^{k}_{j}$ being $k$’s expected utility/engagement. The
willingness of $k$ to move to the RS target $j^{\ast}$ depends on its trust in
the RS prompts. We refer to Appendix A for details (our theorems require
specific assumptions on how provider trust is updated), but at a high-level,
our prompting policies comprises two phases: (1) the RS takes steps to
increase $k$’s level of trust in the RS by promising $k$ its expected audience
(given $\mu^{t}$) at its _current_ point $\ell_{k}^{t}$—and continuing to
match users using $\mu^{t}$—until $k$’s trust reaches a sufficient level; (2)
the RS then prompts $k$ with $(j^{\ast},\phi)$, where $\phi$ is the minimum
level of audience affinity given $k$’s skill beliefs needed to induce the
move; and matches using the optimal target policy
$\mu^{\ast}_{L^{\texttt{prompt}}}$. More precisely, our policy, parameterized
by a trust threshold $\Lambda$ and a belief convergence rate
$T(\varepsilon,\delta)$, is:

  1. 1.

While $\lambda_{k}<\Lambda$, repeat match-prompt pair

$(\mu,\nu)=\big{(}\mu^{t},(\ell_{k},\textstyle\sum_{q\in\mathcal{Q}}\mu^{t}(q,k)\sigma(q,\ell^{t}_{k}))\big{)}.$

  2. 2.

Issue match-prompt pair

$(\mu^{t},(j^{*},\phi(j^{*};\Lambda,\widetilde{S}_{k},\widetilde{A}_{k}))).$

    1. (a)

If Step 2 has been done $T(\varepsilon,\delta/2)$ times, terminate.

    2. (b)

Else if $\lambda_{k}\geq\Lambda$ go to Step 2.

    3. (c)

Else if $\lambda_{k}<\Lambda$ go to Step 1.

If
$\phi(j^{*};\Lambda,\widetilde{S}_{k},\widetilde{A}_{k})\leq\sum_{q\in\mathcal{Q}}\mu^{t}(q,k)\cdot\sigma(q,j^{*})$
then $\mu^{t}$ itself (stochastically) delivers the promised audience. If not,
the provider trust might take a hit, but is rebuilt in step (c). First, assume
the special case where $\mu^{t}$ is deterministic and $k$’s beliefs collapse
immediately. Then, we may run the above policy with $\Lambda=1$ and ignore
steps (a)-(c). Provider $k$’s trust updates are governed by a learning rate
$\eta$.

######  Theorem 1.

Let $s^{t}=\langle L^{t},\widetilde{A}^{t},\widetilde{S}^{t}\rangle$ be
rationalizable and $\mu^{t}$ be a non-myopically stable matching w.r.t.
$s^{t}$. After $\zeta=1/\eta$ iterations of the above policy, the resulting
state $s^{t+\zeta}$ remains rationalizable and $\mu^{t}$ non-myopically stable
w.r.t. $s^{t+\zeta}$. Furthermore, it maximizes the minimum trust,
$\min_{t}\lambda^{t}$, among all policies that reach $s^{t+\zeta}$.

More generally, we prove the complexity of the above policy under the
assumption of a sample complexity measure $T(\varepsilon,\delta)$ that
determines the number of times a content item must be visited for $k$’s
predicted utility to be nearly perfect.

######  Theorem 2.

Let $|\mathcal{Q}|\geq\Omega(1/(1-\Lambda)^{2})$, let $s^{t}=\langle
L^{t},\widetilde{A}^{t},\widetilde{S}^{t}\rangle$ be rationalizable, and
$\mu^{t}$ be non-myopically stable w.r.t. $s^{t}$. If we run the above policy
with
$\varepsilon<\frac{1}{2}\min_{j,j^{\prime}}|\mathbb{E}[E_{k,j}]-\mathbb{E}[E_{k,j^{\prime}}]|$,
the following hold w.h.p.: (1) the resulting state $s^{t+\zeta}$ has
$\ell_{k}=j^{*}$, and remains rationalizable, while $\mu$ remains non-
myopically stable w.r.t. $s^{t+\zeta}$; and (2) the policy terminates in
$\zeta=O(T(\varepsilon,\delta)^{3}\Lambda^{2}/(\eta^{2}\delta)^{2})$ rounds.

As $\Lambda$ varies, our policy trades off (1) quickly reaching equilibrium
and (2) keeping trust high. See Appendix A for further details and discussion.

### Prompting when Beliefs Generalize across Content

The policy above will succeed only if $k$’s skill belief at $j^{\ast}$ is such
that the promised audience will induce it to move. The fact that provider and
cumulative user utility are aligned ensure that
$\mu^{\ast}_{L^{\texttt{prompt}}}$ will, in fact, satisfy $k$ if it can be
convinced to move. If $k$’s skill beliefs for any $j^{\prime}$ are only
updated when it generates content at $j^{\prime}$, then this limits the set of
reachable points, and if $j^{\ast}$ is reachable, it can be reached with a
single prompt. By contrast, suppose $k$’s skill beliefs about $j^{\prime}$ can
be influenced by its experience at a _different_ $j^{\prime\prime}$; e.g., if
producing successful snorkelling content increases $k$’s belief it can produce
scuba content. Then the RS faces a _path planning problem_ : determining a
sequence of points $j=j_{0},j_{1},\cdots j_{n-1},j_{n}=j^{\ast}$ such that
each $j_{i}$ is _incentivizable_ (i.e., can be prompted using the two-phase
policy above) given $k$’s skill beliefs given that it has generated content at
all $j_{\leq i}$. We assume only the following about generalizing belief
updates: (1) beliefs at unvisited points never become less accurate, and (2)
belief updates for unvisited points are independent of the order in which
other points are visited. Full details are provided in Appendix A.

A trivial policy that eventually reaches the optimal incentivizable target
$j^{*}$ prompts $k$ to visit any reachable point $j^{\prime}$ the moment
$j^{\prime}$ is incentivizable. Of course, this may induce visits to
unnecessary points. In Appendix A, we formulate a MIP to find the _shortest
promptable content path_. While this problem is NP-hard, fortunately, there is
a simple, efficient greedy algorithm: at each step, if $j^{*}$ is
incentivizable, prompt with $j^{*}$ and terminate; otherwise prompt with the
(currently) incentivizable point $j$ that maximizes the increase in accuracy
in $k$’s predicted reward at $j^{*}$ if $j$ is visited.

######  Theorem 3.

[Informal] The greedy algorithm runs in polynomial time and returns a content
path at most a constant factor longer than the shortest content path.

See Appendix A for a formal statement and proof.

##  5 Joint Prompting Policies

The problem of simultaneously prompting a set of providers, that is, ensuring
that the _joint_ location (content) of all providers serves users effectively,
presents a non-trivial escalation in complexity. However, the main insight
above—viewing provider evolution as _paths through content space_ —suggests
treating audience availability for _multiple providers_ as the key requirement
and challenge in designing _joint prompting policies_. This introduces an
additional planning component to the problem, requiring a joint prompting
policy to _schedule prompts_ in a way that ensures enough available audience
to fulfil the promises needed to incentivize all providers to move to their
optimal locations.

This unfortunately rules out the greedy application of the single provider
policies above, which can be suboptimal. Consider a simple counterexample
with: two providers $a,b$; two points $x,y$; current locations
$\ell^{t}_{a}=x,\ell^{t}_{b}=y$; skills such that $s_{a,y}>s_{a,x}$,
$s_{a,y}>s_{b,y}$, $s_{b,x}>s_{b,y}$ and $s_{b,x}>s_{a,x}$; and user
affinities such that the optimal matching $\mu^{\ast}$ has equal total
affinity at points $a$ and $b$ whenever providers at those points have skills
at least (resp.) $s_{a,x},s_{b,y}$. In this situation, a Pareto improving move
is to swap the locations of $a$ and $b$, since each has greater skill at the
opposite location than at their current location and than their peer. However,
any policy that moves one provider at a time must have both providers at the
same location for at least one period, imposing significant cost on user
utility.

### Mixed Integer Programming Formulation

The complications above mean that joint prompting policies must plan provider
paths under “sufficient audience” constraints. We develop a MIP formulation to
solve this problem over a finite horizon $T$.333We briefly discuss alternative
approaches below.

In our formulation, provider behavior is represented by decision variables
$\mathit{Act}_{k,j}^{t}\in\\{0,1\\}$ indicating whether provider $k$ offers
content $j$ at stage $t$, with the requirement that each $k$ be active at
exactly one point $j$ at each $t<T$. Decisions by the RS are captured by three
sets of optimization variables: the matching policy $\pi_{q,k}^{t}\in[0,1]$;
the prompting policy $\nu_{k,j}^{t}\in\\{0,1\\}$ indicating whether the RS
prompts $k$ to offer content $j$ at stage $t$; and the commitments,
$C^{t}_{k,j}\in\mathbb{R}^{+}$, or audience promised for any such prompt.

With these variables, we can express relevant key quantities:

  * •

Provider utility:

$E_{k}^{t}=\sum_{q\in\mathcal{Q}}\pi^{t}_{q,k}\sum_{j\in\mathcal{J}}\mathit{Act}_{k,j}^{t}s^{*}_{k,j}\sigma(q,j);$

  * •

Provider audience:

$\mathit{Aud}_{k}^{t}=\sum_{q\in\mathcal{Q}}\pi^{t}_{q,k}\sum_{j\in\mathcal{J}}\mathit{Act}_{k,j}^{t}\sigma(q,j);$

  * •

Induced skill beliefs: We assume skill belief collapses to true skill the
moment $j$ is visited, hence:

$\widetilde{s}^{t}_{k,j}=\sum_{j\in\mathcal{J}}s^{0}_{k,j}(1-\mathit{Vis}_{k,j}^{t-1})+s^{*}_{k,j}\mathit{Vis}_{k,j}^{t-1}$

where $\mathit{Vis}_{k,j}^{t}$ indicates whether $k$ has visited $j$ at or
before stage $t$.

We outline only key MIP constraints that govern the RS dynamics here; the full
MIP is detailed in Appendix B. Indices are universally quantified. We use
$\lesseqgtr$ and $\pm$ to denote two constraints (in the obvious way). $M$ in
the “big-$M$” constraints is an upper bound on audience utility.

$\displaystyle C_{k,j}^{t}\leq\nu_{k,j}^{t}M$ (Cons. 1(a))
$\displaystyle\mathit{Aud}_{k}^{t}\geq C_{k,j}^{t-1}\mathit{Act}_{k,j}^{t}$
(Cons. 1(b))
$\displaystyle\widetilde{s}^{t}_{k,j}\widetilde{a}^{t}_{k,j}\geq\widetilde{s}^{t}_{k,j^{\prime}}\widetilde{a}^{t}_{k,j^{\prime}}-(1-\mathit{Act}_{k,j}^{t})M$
(Cons. 2)
$\displaystyle\widetilde{a}^{t}_{k,j}\lesseqgtr\mathit{Aud}_{k}^{t-1}\pm(1-\mathit{Act}_{k,j}^{t-1})M\pm\nu_{k,j}^{t-1}M$
(Cons. 3)
$\displaystyle\widetilde{a}^{t}_{k,j}\lesseqgtr\widetilde{a}^{t-1}_{k,j}\pm\mathit{Act}_{k,j}^{t-1}M\pm\nu_{k,j}^{t-1}M$
(Cons. 4) $\displaystyle\widetilde{a}^{t}_{k,j}\lesseqgtr
C_{k,j}^{t-1}\pm(1-\nu_{k,j}^{t-1})M$

Cons. 1(a) and Cons. 1(b) are prompting constraints: the first limits the
promised audience if a prompt is given, and ensures the promise is zero if no
prompt is given; the second ensures that if $k$ “accepted” a prompt (i.e.,
moved to the prompted location), the matching delivers the promised audience.
Cons. 2 ensures providers only offer content that are best responses. The
final constraints control audience belief updates: Cons. 3 when $k$ is at $j$
but was not prompted (belief updated to realized audience); Cons. 4 at points
that are inactive and unprompted (beliefs persist); and 5 handles prompts
(belief updated to promised audience).

Our objective is to maximize time-averaged user utility
$\frac{1}{T}\sum_{t=0}^{T-1}\sum_{k\in\mathcal{K}}E^{t}_{k}$. The only
quadratic terms in the MIP involve the product of a binary and a (non-
negative) real-valued variable, which can be linearized in standard
fashion.444The “big-$M$” trick for linearizing the product of a binary
vairable $I$ and a (non-negative) real-valued variable $x$: replace the
product $x\cdot I$ with a real variable $y$, and add constraints $y\leq IM$,
$y\geq 0$, $y\leq x$ and $y\geq x-(1-I)M$.

##  6 Empirical Evaluation

We present some simple proof-of-concept experiments to demonstrate the value
that can be generated by prompting policies. We generate random problem
instances, using relatively small numbers of users and providers to illustrate
key points, and compare the user welfare (or utility) generated over time of
specific policies. While large-scale experiments and empirically determined
models of behavior and incentives will be needed for practical deployment,
these results suggest that prompting has an important role to play in
improving RS ecosystem health.

Figure 1: 2-D problem instance illustration. Red crosses are content points
(locations). Blue markers are user/query locations. Orange and green circles
represent content providers: Green reflects a provider’s true skills, while
the connected orange circles capture’s that providers skill beliefs.

Problem Generation: Due to the infeasibility of testing our approach in a
fully data-driven way, we generate synthetic (fully simulated) and semi-
synthetic (preferences extracted from the MovieLens dataset (Harper and
Konstan 2016)) scenarios. For each scenario, we generate multiple instances of
problem size $(J,K,Q)$ with $J$ content points $\mathcal{J}$, $K$ providers
$\mathcal{K}$, and $Q$ users $\mathcal{Q}$. Sizes vary across families of
instance, but are kept small. In synthetic scenarios, instances are generated
from a cluster model in 2-D space that emulates (implicit) communities of
users with similar preferences. User content affinities decay linearly with
Euclidean distance from a content point. The semi-synthetic model adopts user
and movie embeddings obtained by factorizing the MovieLens dataset. Movie
embeddings are clustered with $k$-means to generate the possible content
types. For each type $j$, the top $U_{j}$ users w.r.t. affinity are selected,
where $U_{j}$ is determined based on the number of users with non-negative
affinity to the cluster. (Affinities are inner products). Full data generation
details are in Appendix C. See Fig. 1 for an illustration.

Evaluation of the MIP: We evaluate the MIP formulation on random small problem
instances, using various metrics, which we describe here:

  * •

Let $E^{T}=\sum_{k\in\mathcal{K}}E_{k}^{T}$ be the utility of the _optimal
prompting policy_ , as determined by the MIP, at the final stage $T$, and
$E=\frac{1}{T}\sum_{t=0}^{T-1}\sum_{k\in\mathcal{K}}E_{k}^{t}$ be its _time-
averaged utility_ —the latter is the MIP objective.

  * •

Let $\overline{E}^{T}$ and $\overline{E}$ denote the same quantities for the
_optimal policy that does not prompt providers_ , but that does adapt its
matching as providers update their locations (content).

  * •

Let $E_{0}$ be the utility of the _optimal stationary policy_ (no prompting, a
fixed matching).

  * •

Define $P^{T}=(E^{T}-\overline{E}^{T})/\overline{E}^{T}$ to be the _final
prompt gap_ , i.e., the improvement obtained (at the final stage) by
prompting, and $\widehat{P}=(E-\overline{E})/\overline{E}$ the time-averaged
prompt gap, that is, the time-averaged improvement in utility obtained by
prompting.

  * •

Let $D=(\overline{E}-E_{0})/E_{0}$ be the improvement obtained by the
adaptive, non-prompting policy over the stationary policy.

  * •

Finally, let

$U_{q}=\frac{1}{T}\sum_{t=0}^{t-1}\sum_{k\in\mathcal{K}}\pi^{t}_{q,k}\sum_{j\in\mathcal{J}}\mathit{Act}^{t}_{k,j}s^{\ast}_{k,j}\sigma(q,j)$

denote the time-averaged user utility of user $q$.

Figure 2: Total per-period utility $E^{t}$ (20 synthetic instances) for
different policies ($J=20,K=5,Q=50,T=10$). Figure 3: User utility $U_{q}$
counts (10 MovieLens instances) for different policies
($J=20,K=10,Q=100,T=5$).

We solve the MIP with Gurobi (the fastest commercial MIP
solver).555https://www.gurobi.com/. Fig. 2 plots per-period utility $E^{t}$ as
a function of $t$ for each the described policies averaged over 20 random
synthetic instances with $J=20$ content points, $K=5$ providers, $Q=50$ users
over a time horizon of $T=10$, and Table 1 contains key quantities for these
instances in addition to a smaller set of instances with $J=10$. The larger
$(J=20)$ instances exhibit larger final (9.3%) and time-averaged (10.7%)
prompt gaps (roughly $2\times$) than the smaller $(J=10)$ instances.

Table 2 displays the same quantities averaged over 20 random MovieLens
instances with $J\in\\{10,20\\}$, $K=10$, $Q=100$, and $T=5$. Here, increasing
the number of content locations seems to have a negligible impact on $P^{T}$
and $\hat{P}$, but the improvement over the stationary policy is significant
(61.8% for the $J=20$ instances), showing the importance of dynamically
matching and prompting based on the RS dynamics. The standard deviations of
all quantities are fairly large, illustrating that for some instances the
utility improvement due to prompting is not too large, but for other instances
it is dramatic. Finally, as another means of visualization, Fig. 3 displays
the user utility histogram for the larger ($J=20$) MovieLens instances,
showing a clear improvement due to prompting in both aggregate user utility
and its distribution across users. The full set of experimental results is
provided in Appendix C.

$J$ |  | Avg $P^{T}$
---
| SD $P^{T}$
---
| Avg $\widehat{P}$
---
| SD $\widehat{P}$
---
| Avg $D$
---
SD $D$
10 | 3.4% | 4.8% | 5.8% | 6.2% | 24.5% | 20.3%
20 | 9.3% | 7.2% | 10.7% | 7.5% | 18.2% | 9.0%
Table 1: Final gap $P^{T}$, time-avg. gap $\widehat{P}$, stationary gap $D$ (20 synthetic instances), varying $J$ ($K=5,Q=50,T=10$). $J$ |  | Avg $P^{T}$
---
| SD $P^{T}$
---
| Avg $\widehat{P}$
---
| SD $\widehat{P}$
---
| Avg $D$
---
SD $D$
10 | 3.3% | 1.7% | 3.3% | 1.7% | 25.2% | 14.2%
20 | 3.7% | 3.1% | 3.5% | 2.6% | 61.8% | 71.6%
Table 2: Final gap $P^{T}$, time-avg. gap $\widehat{P}$, stat. gap $D$ (10
MovieLens instances), varying $J$ ($K\\!=\\!10,Q\\!=\\!100,T\\!=\\!5$).

We note that our MIP does not scale well beyond the instance sizes above. For
example, on a MovieLens instance with $J=50$, $K=10$, $Q=100$, $T=5$, Gurobi
was unable to find a feasible solution after 12 hours. Experimentally, the MIP
scales poorly in the number of providers $K$ and the time horizon $T$.
Improving our methods work at the scale of modern content ecosystems is a
critical direction for future research. We discuss one such extension next.

Column Generation: In Appendix C we outline the initial ideas behind a _column
generation (CG)_ approach that offers both a more general and more scalable
solution to this complex _multi-agent (i.e., multi-provider) planning
problem_. The problem of “moving” providers through location space has strong
analogies with multi-robot path planning (Haghani et al. 2021), where the goal
is determine the best deployment of a set of robots to specific tasks (e.g.,
in-warehouse order fulfillment), together with collision-free paths that allow
them to complete their assigned tasks. While there are significant
differences—providers are self-determining agents with their own goals and
incentives—our CG formulation draws inspiration from the model of Haghani et
al. (2021).

##  7 Concluding Remarks

We have developed a model of content provider incentives and behaviors that
allows an RS to prompt providers to offer novel content items that help
improve user social welfare and overall ecosystem health. Our prompting
policies incentivize providers to “explore” w.r.t. their own skills and
auidence beliefs, and _de-risk_ this exploration, nudging the RS to an
equilibrium that improves user welfare and the utility of individual
providers. Our prompting policies effectively break the fundamental
information asymmetry that exists in many RS ecosystems. Apart from
theoretical guarantees, our empirical results demonstrate that such prompting
can significantly improve outcomes.

A number of important theoretical and practical extensions of this model are
needed. Scalability is of critical importance—CG appears quite promising, but
online adaptive policies using multi-agent RL should be investigated as well.
Various extensions and generalizations of our model should prove valuable,
including relaxing some of its more restrictive assumptions, such as: the
stationarity of user/query affinities and provider skills; the non-strategic
decision making of providers (who best respond only myopically); and the
extensive knowledge of the RS (e.g., of provider skills, user affinities). Of
special interest is the case when the RS is uncertain of provider abilities
(skill) and incentives (reward), which moves us into the realm of dynamic
mechanism design (Bergemann and Välimäki 2019). A formal study of
supply/demand information “leakage” embedded in prompts should generate useful
insights as well. in Finally, the _practical_ prompting of providers requires
translating the abstract notion of content points into _actionable_ prompts
for providers (e.g., using generative modeling techniques to describe/suggest
novel items), a topic of considerable importance.

## References

  * Abdollahpouri and Burke (2021) Abdollahpouri, H.; and Burke, R. 2021.  Multistakeholder Recommender Systems.  In _Recommender Systems Handbook_ , 647–677. New York: Springer.
  * Ben-Porat et al. (2019) Ben-Porat, O.; Goren, G.; Rosenberg, I.; and Tennenholtz, M. 2019.  From Recommendation Systems to Facility Location Games.  In _Proceedings of the Thirty-third AAAI Conference on Artificial Intelligence (AAAI-19)_ , 1772–1779. Honolulu.
  * Ben-Porat, Rosenberg, and Tennenholtz (2020) Ben-Porat, O.; Rosenberg, I.; and Tennenholtz, M. 2020.  Content Provider Dynamics and Coordination in Recommendation Ecosystems.  In _Advances in Neural Information Processing Systems 33 (NeurIPS-20)_ , 18931–18941. virtual.
  * Ben-Porat and Tennenholtz (2018) Ben-Porat, O.; and Tennenholtz, M. 2018.  A Game-Theoretic Approach to Recommendation Systems with Strategic Content Providers.  In _Advances in Neural Information Processing Systems 31 (NeurIPS-18)_ , 1118–1128. Montreal.
  * Bergemann and Välimäki (2019) Bergemann, D.; and Välimäki, J. 2019.  Dynamic Mechanism Design: An Introduction.  _Journal of Economic Literature_ , 57(2): 235–274.
  * Beutel et al. (2018) Beutel, A.; Covington, P.; Jain, S.; Xu, C.; Li, J.; Gatto, V.; and Chi, E. H. 2018\.  Latent Cross: Making Use of Context in Recurrent Recommender Systems.  In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining (WSDM-18)_ , 46–54. Marina Del Rey, CA.
  * Biega, Gummadi, and Weikum (2018) Biega, A. J.; Gummadi, K. P.; and Weikum, G. 2018.  Equity of Attention: Amortizing Individual Fairness in Rankings.  In _Proceedings of the 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR-18)_, 405–414. Ann Arbor, MI.
  * Covington, Adams, and Sargin (2016) Covington, P.; Adams, J.; and Sargin, E. 2016.  Deep Neural Networks for YouTube Recommendations.  In _Proceedings of the 10th ACM Conference on Recommender Systems_ , 191–198. Boston.
  * Garcia-Gathright et al. (2018) Garcia-Gathright, J.; Hosey, C.; St. Thomas, B.; Carterette, B.; and Diaz, F. 2018\.  Mixed Methods for Evaluating User Satisfaction.  In _Proceedings of the 12th ACM Conference on Recommender Systems (RecSys18)_ , 541–542. Vancouver.
  * Goodrow (2021) Goodrow, C. 2021.  On YouTube’s Recommendation System.
  * Haghani et al. (2021) Haghani, N.; Li, J.; Koenig, S.; Kunapuli, G.; Contardo, C.; Regan, A.; and Yarkony, J. 2021.  Multi-robot Routing with Time Windows: A Column Generation Approach.  AxXiv 2103.08835.
  * Harper and Konstan (2016) Harper, F. M.; and Konstan, J. A. 2016.  The MovieLens Datasets: History and Context.  _ACM Transactions on Interactive Intelligent Systems_ , 5(4): 19:1–19:19.
  * He et al. (2017) He, X.; Liao, L.; Zhang, H.; Nie, L.; Hu, X.; and Chua, T. 2017.  Neural Collaborative Filtering.  In _Proceedings of the 26th International Conference on World Wide Web (WWW-17)_ , 173–182. Perth, Australia.
  * Heuss, Sarvi, and de Rijke (2022) Heuss, M.; Sarvi, F.; and de Rijke, M. 2022.  Fairness of Exposure in Light of Incomplete Exposure Estimation.  In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR-22)_ , 759–769. Madrid.
  * Hron et al. (2022) Hron, J.; Krauth, K.; Jordan, M. I.; Kilbertus, N.; and Dean, S. 2022.  Modeling Content Creator Incentives on Algorithm-curated Platforms.  ArXiv 2206.13102.
  * Jacobson et al. (2016) Jacobson, K.; Murali, V.; Newett, E.; Whitman, B.; and Yon, R. 2016.  Music Personalization at Spotify.  In _Proceedings of the 10th ACM Conference on Recommender Systems (RecSys16)_ , 373–373. Boston, Massachusetts, USA.
  * Jagadeesan, Garg, and Steinhardt (2022) Jagadeesan, M.; Garg, N.; and Steinhardt, J. 2022.  Supply-Side Equilibria in Recommender Systems.  ArXiv 2206.13489.
  * Konstan et al. (1997) Konstan, J. A.; Miller, B. N.; Maltz, D.; Herlocker, J. L.; Gordon, L. R.; and Riedl, J. 1997.  GroupLens: Applying Collaborative Filtering to Usenet News.  _Communications of the ACM_ , 40(3): 77–87.
  * Levin and Peres (2017) Levin, D. A.; and Peres, Y. 2017.  _Markov Chains and Mixing Times_ , volume 107.  American Mathematical Society.
  * Lübbecke and Desrosiers (2005) Lübbecke, M. E.; and Desrosiers, J. 2005.  Selected Topics in Column Generation.  _Operations Research_ , 53(6): 1007–1023.
  * Mladenov et al. (2020) Mladenov, M.; Creager, E.; Swerksy, K.; Ben-Porat, O.; Zemel, R. S.; and Boutilier, C. 2020.  Optimizing Long-term Social Welfare in Recommender Systems: A Constrained Matching Approach.  In _Proceedings of the Thirty-seventh International Conference on Machine Learning (ICML-20)_ , 6987–6998. Vienna.
  * Salakhutdinov and Mnih (2007) Salakhutdinov, R.; and Mnih, A. 2007.  Probabilistic Matrix Factorization.  In _Advances in Neural Information Processing Systems 20 (NIPS-07)_ , 1257–1264. Vancouver.
  * Singh and Joachims (2018) Singh, A.; and Joachims, T. 2018.  Fairness of Exposure in Rankings.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD-18)_, 2219–2228. London: Association for CompMachinery.
  * Whelan, Harrell, and Wang (2015) Whelan, C.; Harrell, G.; and Wang, J. 2015.  Understanding the k-medians Problem.  In _Proceedings of the International Conference on Scientific Computing (CSC)_ , 219. The Steering Committee of The World Congress in Computer Science, Computer ….
  * Wu et al. (2022) Wu, H.; Mitra, B.; Ma, C.; Diaz, F.; and Liu, X. 2022.  Joint Multisided Exposure Fairness for Recommendation.  In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR-22)_ , 703–714. Madrid.

##  Appendix A Omitted Results and Proofs from Section 4

### Prompting under Non-generalizing Belief Updates

Given the fixed locations of all other providers, let $j^{\ast}\in\mathcal{J}$
be the optimal location for provider $k$, i.e., the point that maximizes long-
term average reward. Before addressing policy optimization in its full
generality, we first how the RS can move a (rationalizable) state
$s^{t}=\langle L^{t},\widetilde{A}^{t},\widetilde{S}^{t}\rangle$ to
$s^{t+1}=\langle L^{t+1},\widetilde{A}^{t+1},\widetilde{S}^{t+1}\rangle$,
where for all providers $k^{\prime}\neq k$, $\nu_{k^{\prime}}=\texttt{None}$,
and $k$’s location moves from $j$ to $j^{*}$ assuming specific audience and
skill belief updates.

Let $\mu^{t}$ be a (non-myopically) stable matching w.r.t $s^{t}$,666Stability
may be induced by earlier prompting (see next section), or by simple _self-
exploration_ by providers (see discussion of exploration above). and let
$M_{q,k}$ be the Bernoulli random variable denoting whether $q\in\mathcal{Q}$
is matched to $k$, with $\Pr(M_{q,k}=1)=\mu^{t}(q,k)$. We assume an utility
function of the form $f(\sigma(q,j),s_{k,j})=\sigma(q,j)\cdot s_{k,j}$. Thus,
$k$’s audience and user utility under $\mu^{t}$ are the random variables
(resp.):

$A_{k,j}=\sum_{q\in\mathcal{Q}}M_{q,k}\cdot\sigma(q,j);\quad\quad
E_{k,j}=s_{k,j}\cdot
A_{k,j}=\sum_{q\in\mathcal{Q}}M_{q,k}\cdot\sigma(q,j)\cdot s_{k,j}.$

Provider $k$’s willingness to act based on an RS prompt $(j,C_{k,j})$ is
governed by their trust $\lambda^{t}_{k}\in[0,1]$: $k$’s tentative audience
belief is updated using incremental-trust belief update:
$\widetilde{a}^{t+1}_{k,j}=(1-\lambda^{t}_{k})\cdot\widetilde{a}^{t+1/2}_{k,j}+\lambda^{t}_{k}\cdot
C_{k,j}$. We define an _accuracy-based_ trust update as follows:

$\tau(\lambda_{k},C_{k,j},A_{k,j})=\begin{cases}\max\\{1,\lambda_{k}+\eta\cdot(1-|C_{k,j}-A_{k,j}|/|\mathcal{Q}|)\\}&\text{if
}1-|C_{k,j}-A_{k,j}|/|\mathcal{Q}|>\lambda_{k}\\\
\min\\{0,\lambda_{k}-\eta\cdot(1-|C_{k,j}-A_{k,j}|/|\mathcal{Q}|)\\}&\text{if
}1-|C_{k,j}-A_{k,j}|/|\mathcal{Q}|<\lambda_{k}\\\ \lambda_{k}&\text{if
}1-|C_{k,j}-E_{k,j}|/|\mathcal{Q}|=\lambda_{k}\end{cases}$

where $\eta$ is a provider-specific learning rate. Informally, this trust
update takes a step in the direction of the accuracy of the promised utility
(with $1$ being perfect accuracy and $0$ the least accuracy). Let

$\phi(j;\lambda_{k},\widetilde{S}_{k},\widetilde{A}_{k})=\max\left\\{\frac{1}{\lambda_{k}}\left(\frac{\widetilde{s}_{k,\ell}\cdot\widetilde{a}_{k,\ell}}{\widetilde{s}_{k,j}}-(1-\lambda_{k})\widetilde{A}_{k,j}\right):\widetilde{s}_{k,\ell}\cdot\widetilde{a}_{k,\ell}>\widetilde{s}_{k,j}\cdot\widetilde{a}_{k,j},\ell\in\mathcal{J}\right\\}$

denote the minimum level of utility the RS must guarantee to incentivize $k$
to move to $j$ given trust $\lambda_{k}$, skill beliefs $\widetilde{S}_{k}$,
and audience beliefs $\widetilde{A}_{k}$, given the form of incremental-trust
tentative audience belief update. Naturally, the minimum level of promised
utility decreases as $\lambda_{k}$ increases:

######  Lemma 4.

For any $j,\widetilde{S}_{k},\widetilde{A}_{k}$, if
$\lambda_{k}\geq\lambda_{k}^{\prime}$ then
$\phi(j;\lambda_{k},\widetilde{S}_{k},\widetilde{A}_{k})\leq\phi(j;\lambda_{k}^{\prime},\widetilde{S}_{k},\widetilde{A}_{k})$.

###### Proof.

For a fixed $\ell$ such that
$\widetilde{s}_{k,\ell}\cdot\widetilde{a}_{k,\ell}>\widetilde{s}_{k,j}\cdot\widetilde{a}_{k,j}$,
we have

$\frac{\partial}{\partial\lambda}\left(\frac{1}{\lambda}\left(\frac{\widetilde{s}_{k,\ell}\cdot\widetilde{a}_{k,\ell}}{\widetilde{s}_{k,j}}-(1-\lambda)\widetilde{a}_{k,j}\right)\right)=-\frac{\widetilde{s}_{k,\ell}\cdot\widetilde{a}_{k,\ell}-\widetilde{s}_{k,j}\cdot\widetilde{a}_{k,j}}{\widetilde{s}_{k,j}\lambda^{2}}<0,$

so
$\frac{1}{\lambda}(\frac{\widetilde{s}_{k,\ell}\cdot\widetilde{a}_{k,\ell}}{\widetilde{s}_{k,j}}-(1-\lambda)\widetilde{a}_{k,j})$
is decreasing in $\lambda$. Therefore the maximum over all $\ell$ such that
$\widetilde{s}_{k,\ell}\widetilde{a}_{k,\ell}>\widetilde{s}_{k,j}\widetilde{a}_{k,j}$
is also decreasing in $\lambda\in[0,1]$. ∎

The main challenge the RS needs to address is the fact that a the provider
might require a high degree of trust for a prompt to induce a location change.
Consider first the case where $\mu^{t}$ is deterministic and $k$’s beliefs
collapse immediately. The following simple scheme allows the RS to induce a
move from $j$ to $j^{*}$ (if at all possible) while keeping $\mu^{t}$
unchanged until the move occurs.

  1. 1.

_Phase 1 (build trust):_ While $\lambda_{k}<1$, repeat the match-prompt pair

$(\mu,\nu)=\big{(}\mu^{t},(j,\textstyle\sum_{q\in\mathcal{Q}}\mu^{t}(q,k)\cdot\sigma(q,j))\big{)}.$

  2. 2.

_Phase 2 (prompt to goal):_ Issue match-prompt pair

$(\mu^{t},(j^{*},\phi(j^{*};1,\widetilde{S}_{k},\widetilde{A}_{k}))).$

If
$\phi(j^{*};1,\widetilde{S}_{k},\widetilde{A}_{k})\leq\sum_{q\in\mathcal{Q}}\mu^{t}(q,k)\cdot\sigma(q,j^{*})$
then $\mu^{t}$ itself (stochastically) delivers the promised audience. If not,
the provider trust might take a hit, but can be rebuilt later. We expand on
this further consequently.

###### Theorem 1.

Let $s^{t}=\langle L^{t},\widetilde{A}^{t},\widetilde{S}^{t}\rangle$ be
rationalizable and $\mu^{t}$ be a non-myopically stable matching w.r.t.
$s^{t}$. After $\zeta=1/\eta$ iterations of the above policy, the resulting
state $s^{t+\zeta}$ remains rationalizable and $\mu^{t}$ non-myopically stable
w.r.t. $s^{t+\zeta}$. Furthermore, it maximizes the minimum trust,
$\min_{t}\lambda^{t}$, among all policies that reach $s^{t+\zeta}$.

###### Proof.

Trust is built up to $1$ in Phase 1 over the course of at most $1/\eta$ steps,
since
$\tau(\lambda_{k}^{t},A_{k,j},A_{k,j})=\max\\{1,\lambda_{k}^{t}+\eta\\}$. In
Phase 2 (a single step), $j^{*}$ is prompted, and accepted due to the promise
of $\phi(j^{*};1,\widetilde{S}_{k},\widetilde{A}_{k})$, which collapses and
induces equilibrium. No policy that induces this equilibrium can attain a
higher value of $\min_{t}\lambda^{t}_{k}$. This is because the prompt in Phase
2 is the only step that can cause trust to decrease, and building up trust to
$1$ in the previous phase ensures that the final trust value is as high as
possible (by Lemma 4). ∎

We now relax the deterministic-matching and immmediate-belief-collapse
assumptions. Instead, we assume a sample complexity measure
$T(\varepsilon,\delta)\in\mathbb{N}$ that satisfies (letting $j\in\mathcal{J}$
and $\mu$ be s.t. $\mu^{t}=\mu$ for all $t$ where $\ell_{k}^{t}=j$):

$|\\{t:\ell_{k}^{t}=j\\}|\geq T(\varepsilon,\delta)\implies\Pr\left(\forall
t\geq\bar{t}\;|\widetilde{s}^{t}_{k,j}\cdot\widetilde{a}^{t}_{k,j}-s_{k,j}\cdot\mathbb{E}[A_{k,j}]|\leq\varepsilon\right)\geq
1-\delta$

where $\bar{t}$ is the latest stage where $\ell_{k}^{t}=j$. That is, if $k$
offers item $j$ enough, its predicted utility (product of skill, audience
beliefs) is nearly perfect (and remains so) with high probability. With only
this assumption, the RS adopts the following policy to induce a move to
$j^{*}$, parameterized by a trust threshold $\Lambda$ and an error threshold
$\varepsilon$:

  1. 1.

_Phase 1 (build trust):_ While $\lambda_{k}<\Lambda$, repeat the match-prompt
pair

$(\mu,\nu)=\left(\mu,\left(\ell_{k},\textstyle\sum_{q\in\mathcal{Q}}\mu(q,k)\cdot\sigma(q,\ell_{k})\right)\right).$

(Here $\ell_{k}$ is creator $k$’s location at the current time. We omit time
in the superscripts for brevity.)

  2. 2.

_Phase 2 (prompt to goal):_ Issue match-prompt pair

$(\mu,(j^{*},\phi(j^{*};\Lambda,\widetilde{S}_{k},\widetilde{A}_{k}))).$

    1. (a)

If Phase 2 has been entered $\geq T(\varepsilon,\delta/2)$ times, terminate.

    2. (b)

Else if $\lambda_{k}\geq\Lambda$ go to Phase 2.

    3. (c)

Else if $\lambda_{k}<\Lambda$ go to Phase 1.

###### Theorem 2.

Assume $|\mathcal{Q}|\geq 6\log 2/(1-\Lambda)^{2}$, let $s^{t}=\langle
L^{t},\widetilde{A}^{t},\widetilde{S}^{t}\rangle$ be rationalizable, and
$\mu^{t}$ be non-myopically stable w.r.t. $s^{t}$. If we run the above policy
with
$\varepsilon<\frac{1}{2}\min_{j,j^{\prime}}|\mathbb{E}[E_{k,j}]-\mathbb{E}[E_{k,j^{\prime}}]|$,
the following hold with probability at least $1-\delta$: (1) the resulting
state $s^{t+\zeta}$ has $\ell_{k}=j^{*}$, and remains rationalizable, while
$\mu$ remains non-myopically stable w.r.t. $s^{t+\zeta}$; and (2) the policy
terminates in
$\zeta=O\big{(}\frac{T(\varepsilon,\delta)^{3}\Lambda^{2}}{\eta^{2}\delta^{2}}\big{)}$
rounds.

###### Proof.

We show that with high probability, at most a quadratic number of time steps
are spent in Phase 1 before the creator’s trust exceeds the threshold
$\Lambda$. Since the prompts in Phase 1 mirror the content item
$\ell_{k}^{t}=BR(\widetilde{S}^{t}_{k},\widetilde{A}^{t}_{k})$ and since $\mu$
is non-myopically stable, the creator is guaranteed to accept each Phase 1
prompt. Furthermore, due to stability, a single content item $j$ achieves
$BR(\widetilde{S}^{t}_{k},\widetilde{A}^{t}_{k})$ for all $t$ in the absence
of prompts. For simplicity, we will assume that the creator’s beliefs for item
$j$ are already $\varepsilon$-accurate, that is,
$|\widetilde{S}_{k,j}\cdot\widetilde{A}_{k,j}-S_{k,j}\cdot\mathbb{E}[A_{k,j}]|\leq\varepsilon$.
If this is not the case, we simply add a waiting phase at the very beginning
of the policy that allows for this belief to reach the desired accuracy (which
would only affect the constants in the convergence rate).

Let $\lambda_{k}^{t}<\Lambda$ be the creator’s trust at the beginning of some
execution of Phase 1 (if trust is larger than $\Lambda$, we would not be in
Phase 1). Observe that

$\displaystyle\frac{|A_{k,j}-\mathbb{E}[A_{k,j}]|}{|\mathcal{Q}|}\leq\frac{1-\lambda_{k}^{t}}{2}$
$\displaystyle\implies\frac{|A_{k,j}-\mathbb{E}[A_{k,j}]|}{|\mathcal{Q}|}\leq\min\left\\{1-\lambda_{k}^{t},\frac{1}{2}\right\\}$
$\displaystyle\implies
1-\frac{|A_{k,j}-\mathbb{E}[A_{k,j}]|}{|\mathcal{Q}|}\geq\max\left\\{\lambda_{k}^{t},\frac{1}{2}\right\\}$
$\displaystyle\implies\tau(\lambda_{k},\mathbb{E}[A_{k,j}],A_{k,j})\geq\lambda_{k}^{t}+\frac{\eta}{2}.$

Therefore

$\Pr\left(\tau(\lambda_{k}^{t},\mathbb{E}[A_{k,j}],A_{k,j})\geq\lambda_{k}^{t}+\frac{\eta}{2}\right)\geq\Pr\left(|A_{k,j}-\mathbb{E}[A_{k,j}]|\leq\frac{(1-\lambda_{k}^{t})|\mathcal{Q}|}{2}\right)\geq
1-2\exp\left(-\frac{(1-\lambda_{k}^{t})^{2}|\mathcal{Q}|}{2}\right)$

by a Chernoff-Hoeffding bound. For $|\mathcal{Q}|\geq\frac{6\log
2}{(1-\Lambda)^{2}}$ this probability is $\geq 3/4$. Therefore, every time
$(j,\mathbb{E}[A_{k,j}])$ is given as a prompt to the provider in Phase 1,
trust increases by at least $\eta/2$ with probability $\geq 3/4$, and trust
decreases by at most $\eta$ with probability $\leq 1/4$ (if trust is already
at $0$, it increases by at least $\eta/2$ with probability $\geq 3/4$, and
stays at $0$ with probability $\leq 1/4$). We show that with high probability,
trust $\lambda_{k}^{t}$ exceeds $\Lambda$ in quadratically many time steps. To
prove this, we bound the hitting time of the trust process $(\lambda_{k}^{t})$
by the hitting time of a simple random walk on $\mathbb{Z}$ via a standard
coupling argument. For $s\in\mathbb{N}$ let $X_{s}$ be $+1$ with probability
$1/2$ and $-1$ with probability $1/2$. Consider the process $(Y_{t})$ defined
as follows: every time $(X_{s})$ walks one unit to the right, so does
$(Y_{t})$. If $(X_{s})$ walks one unit to the left, we have two cases: (1) If
$(X_{s})$ walks one unit to the right in the subsequent time step, then
$(Y_{t})$ walks one unit to the right. (2) If $(X_{s})$ walks one unit to the
left in the subsequent time step, then $(Y_{t})$ walks two units to the left.
Then, $\Pr(Y_{t}=+1)=3/4$ and $\Pr(Y_{t}=-2)=1/4$, and by how we defined the
coupling,

$\inf\left\\{t:\textstyle\sum_{t^{\prime}\leq t}Y_{t^{\prime}}\geq
k\right\\}\leq\inf\left\\{s:\textstyle\sum_{s^{\prime}\leq
s}X_{s^{\prime}}\geq k\right\\}$

for any $k$. So, coupling the trust process $(\lambda_{k}^{t})$ to $(Y_{s})$
in the obvious way, we can bound the the hitting time $\tau_{\Lambda}$ of the
trust process:

$\tau_{\Lambda}:=\inf\\{t:\lambda_{k}^{t}\geq\Lambda\\}=\inf\left\\{t:\textstyle\sum_{t^{\prime}\leq
t}Y_{t^{\prime}}\geq\frac{2\Lambda}{\eta}\right\\}\leq\inf\left\\{s:\textstyle\sum_{s^{\prime}\leq
s}X_{s^{\prime}}\geq\frac{2\Lambda}{\eta}\right\\}.$

Classical results (Levin and Peres 2017) yield

$\Pr(\tau_{\Lambda}\geq\kappa)\leq\Pr\left(\inf\left\\{t:\textstyle\sum_{t^{\prime}\leq
t}X_{t^{\prime}}\geq\frac{2\Lambda}{\eta}\right\\}\geq\kappa\right)\leq\frac{6\cdot(2\Lambda/\eta)}{\sqrt{\kappa}},$

and so

$\Pr(\tau_{\Lambda}\leq\kappa\text{ for every execution of Phase 1})\geq
1-\frac{12\Lambda T(\varepsilon,\delta/2)}{\eta\sqrt{\kappa}}$

by a union bound. Taking $\kappa\geq
576\Lambda^{2}T(\varepsilon,\delta/2)^{2}/(\eta^{2}\delta^{2})$ yields
$\Pr(\tau_{\Lambda}\leq\kappa\text{ for every execution of Phase 1})\geq
1-\delta/2$. We enter Phase 1 at most $T(\varepsilon,\delta/2)$ times, so with
probability $\geq 1-\delta/2$ the total number of time steps spent in Phase 1
is $O(T(\varepsilon,\delta/2)^{3}(\Lambda/\eta\delta)^{2})$.

Finally, the prompting policy terminates once $j^{*}$ has been visited at
least $T(\varepsilon,\delta/2)$ times, which means the creator’s believed
engagement for $j^{*}$ is $\varepsilon$-accurate throughout the execution of
the policy with probability at least $1-\delta/2$. Therefore, since
$\varepsilon<\frac{1}{2}(\mathbb{E}[E_{k,j^{*}}]-\mathbb{E}[E_{k,j}])$,
$j^{*}=BR(\widetilde{S}_{k},\widetilde{A}_{k})$ at the end of the policy with
probability at least $1-\delta/2$. This, combined with the above high-
probability guarantee on the number of iterations spent in Phase 1, completes
the proof. ∎

By varying $\Lambda$, our policy interpolates between (1) reaching the optimal
equilibrium as quickly as possible and (2) maintaining the greatest trust at
each step. Indeed,
$\Lambda_{*}=\min\\{\lambda:\phi(j^{*};\lambda,\widetilde{S}^{t}_{k},\widetilde{A}^{t}_{k})\leq
Q\\}$ is the least trust threshold s.t. the RS successfully prompts $k$ to
offer $j^{*}$ in Phase 2. The hitting time of $\Lambda$ in Phase 1 is
increasing in $\Lambda$, so $\Lambda_{*}$ minimizes (in expectation) the
number of steps needed to reach equilibrium. As $\Lambda\geq\Lambda_{*}$
increases, the post-prompt drop in provider trust in Phase 2 decreases, but
the number of steps needed to reach equilibrium increases.

### Prompting when Beliefs Generalize across Content

To abstract away the details of provider dynamics, we assume deterministic
matchings, and that $k$’s skill and audience beliefs for any point $j$
collapse to their true values the first time $j$ is produced (this can be
relaxed with only minor modifications to our argument). We now allow
observations at $j$ to affect beliefs at other points as well. We assume only
the following:

  1. 1.

Beliefs at unvisited points never become less accurate, i.e., if
$\widetilde{s}^{t}_{k,j}\geq s_{k,j}$ (resp. $\widetilde{s}^{t}_{k,j}\leq
s_{k,j}$) and some $j^{\prime}\neq j$ is produced at time $t$, then
$\widetilde{s}^{t}_{k,j}\geq\widetilde{s}^{t+1}_{k,j}\geq s_{k,j}$ (resp.
$\widetilde{s}^{t}_{k,j}\leq\widetilde{s}^{t+1}_{k,j}\leq s_{k,j}$), and
similarly for audience beliefs.

  2. 2.

Belief updates for unvisited points are independent of the order in which
other points are visited; specifically for any $j,j^{\prime}$, the accuracy
increase in $k$’s predicted reward at $j^{\prime}$ if $j$ is visited is
independent of other visited points.

For $\mathcal{J}^{\prime}\subseteq\mathcal{J}$, let

$I(\mathcal{J}^{\prime})=\\{j\in\mathcal{J}:\phi(j;1,\widetilde{S}_{k},\widetilde{A}_{k})\leq
Q\\}\supset\mathcal{J}^{\prime}$

be the set of all incentivizable points given that $k$ has visited all and
only points in $\mathcal{J}^{\prime}$ ($I(\mathcal{J}^{\prime})$ is well-
defined and unique given our second assumption). We make the following
additional assumption: for any unvisited
$j,j^{\prime}\in\mathcal{J}\setminus\mathcal{J}^{\prime}$, visiting $j$ does
not make $j^{\prime}$ harder to incentivize, i.e.,

$I(\mathcal{J}_{1}\cup\mathcal{J}_{2})\supseteq I(\mathcal{J}_{1})\cup
I(\mathcal{J}_{2})$

for any $\mathcal{J}_{1},\mathcal{J}_{2}\subseteq\mathcal{J}$. We can readily
determine if a point $j^{\ast}$ is (or can be made to be) incentivizable. Let
$I^{m}(\mathcal{J}^{\prime})=I(I(\cdots I(\mathcal{J}^{\prime})\cdots))$
(closure under $m$ iterations) for any $m\leq J$. All points in this set are
incentivizable with no more than $|I^{m}(\mathcal{J}^{\prime})|$ prompts:

######  Lemma 5.

Given initial beliefs $\widetilde{S}^{0}_{k},\widetilde{A}^{0}_{k}$ and a
target content point $j^{\ast}$, determining if $j^{\ast}\in
I^{J}(\mathcal{J}^{\prime})$, i.e., whether $j^{\ast}$ can be incentivized by
prompting, can be done in polynomial time.

###### Proof.

Let $\mathcal{J}_{0}$ be the set of undominated overestimates that will be
produced by the provider without any prompting by the RS. For each $t\geq 1$,
compute $\mathcal{J}_{t}=I(\mathcal{J}_{t-1})$, and stop when
$\mathcal{J}_{t}=\mathcal{J}_{t-1}$. If $j^{*}\in\mathcal{J}_{t}$, then there
is a sequence of content items that leads to $j^{*}$ being incentivizable,
otherwise no such path exists. ∎

If $j^{\ast}$ is incentivizable, there must be a prompting policy that induces
$k$ to visit $j^{\ast}$. In one naive such policy, the RS prompts $k$ to visit
all points in $I(\mathcal{J}^{\prime})$ in some order, i.e., along a specific
_content path_ , then prompts visits to all points in
$I(I(\mathcal{J}^{\prime}))$, and so on, until $j^{*}$ belongs to the
incentivizable set (at which point it is prompted). Of course, this may induce
visits to unneeded points. The shortest promptable content path can be
formulated as the following mixed integer program (MIP).

Let $m(j)$ be the minimal $m$ such that $j\in I^{m}(\mathcal{J}_{0})$, where
$\mathcal{J}_{0}$ is the initial set of content items (undominated
overestimates) that $k$ visits without RS prompts. Consider the following
weighted directed graph with vertex set $I(\mathcal{J}_{0})\cup
I^{2}(\mathcal{J}_{0})\cup\cdots\subseteq\mathcal{K}$: the edges in this graph
are of the form $(j,j^{\prime})$ for every $m(j)\leq m(j^{\prime})$, and the
weight of edge $(j,j^{\prime})$, denoted $w_{j,j^{\prime}}$, is the increase
in accuracy in the provider $k$’s believed reward for $j^{\prime}$ when $j$ is
visited. Finally, let $r_{j^{\prime}}$ denote the minimum believed reward
($\widetilde{s}_{k,j^{\prime}}\cdot\widetilde{a}_{k,j^{\prime}}$) needed to
incentivize $j^{\prime}$ given that $\mathcal{J}_{0}$ is the only set of
content that has been produced (this is the “lowest bar” for
incentivizability, and the assumption that
$I(\mathcal{J}_{1}\cup\mathcal{J}_{2})\supset I(\mathcal{J}_{1})\cup
I(\mathcal{J}_{2})$ ensures that raising predicted belief above this threshold
suffices to render $j^{\prime}$ incentivizable). Given this, we can formulate
the shortest feasible content path problem as a binary integer program. The
variables of the IP are of the form $x_{j,j^{\prime}}$ for every content
points $j,j^{\prime}\in\mathcal{K}$ with either $m(j)=m(j^{\prime})$ or
$m(j)+1=m(j^{\prime})$ (any path that moves from a given level to a lower
level can be replaced by a feasible path of equal length where the path
traverses levels in nondecreasing order, due to the assumption that
information gain on predicted rewards is order-independent). Let $j^{*}$
denote the target content point. The integer program is:

$\begin{array}[]{ll}\text{minimize
}&\sum_{j_{1},j_{2}\in\mathcal{K}}x_{j_{1},j_{2}}\\\ \,\text{subject to
}&\sum_{j\in\mathcal{K}}x_{j,j^{*}}=1\\\ &\sum_{j_{2}\in
N(j_{1})}x_{j_{1},j_{2}}+x_{j_{2},j_{1}}=2\hfill\forall
j_{1}\in\mathcal{K}\setminus\\{j^{\ast}\\}\\\ &\sum_{m(j_{1}^{\prime})\leq
m(j_{2})}w_{j_{1}^{\prime},j_{2}}\Big{(}\sum_{j_{2}^{\prime}\in\mathcal{K}}x_{j_{1}^{\prime},j_{2}^{\prime}}\Big{)}\geq
r_{j_{2}}\cdot x_{j_{1},j_{2}}\qquad\forall j_{1},j_{2}\in\mathcal{K}\\\
&x_{j_{1},j_{2}}\in\\{0,1\\}\hfill\forall
j_{1},j_{2}\in\mathcal{K}\end{array}$

The first two constraints ensure that the solution defines a valid path
through the content graph that ends at $j^{*}$. The third third constraint
ensures feasibility of the path with respect to incentivizability (if $j_{2}$
is visited after $j_{1}$, the sum of the accuracy gains on predicted belief at
$j_{2}$ thus far must exceed the incentivizability threshold $j_{2}$).

While this MIP finds the shortest promptable path, the problem is NP-hard (by
reduction from weighted-constrained shortest path). Fortunately, there is a
simple, efficient greedy algorithm: at each step, if $j^{\ast}$ is
incentivizable, prompt with $j^{\ast}$ and terminate; otherwise prompt with
the (currently) incentivizable point $j$ that maximizes $w_{j,j^{*}}$, the
increase in accuracy in $k$’s predicted reward at $j^{\ast}$ if $j$ is
visited. Let Greedy denote the length of the greedy path, and let OPT denote
the length of the shortest path.

###### Theorem 3.

Let $r$ denote the minimum predicted reward threshold such that if
$\widetilde{s}_{k,j^{*}}^{0}\cdot\widetilde{a}_{k,j^{*}}^{0}\geq r$, then
$j^{*}\in I(\emptyset)$ (that is, $j^{*}$ would be immediately
incentivizable). Let $w_{min}$ be the minimum $w_{j,j^{\ast}}$ for any point
$j$ in the shortest path. Then
$\textsc{Greedy}\leq\frac{r}{w_{min}}\cdot\textsc{OPT}$.

###### Proof.

Consider the first point the greedy algorithm deviates from the shortest
content path. Let $j$ be the content item chosen by the shortest path. The
length of the greedy content path until it either reaches $j^{*}$ or rejoins
the shortest content path at $j$ is at most $\frac{r}{w_{j,j^{*}}}$, since
every content item $j^{\prime}$ on the greedy content path satisfies
$w_{j^{\prime},j^{*}}>w_{j,j^{*}}$. The greedy content path can deviate from
and rejoin the shortest content path at most OPT times, so its length is at
most

$\sum_{j\in\widetilde{\mathcal{J}}}\frac{r}{w_{j,j^{*}}}\leq\frac{r}{w_{min}}\cdot\textsc{OPT},$

where $\widetilde{\mathcal{J}}$ denotes the set of content items on the
shortest content path where the greedy content path deviates. ∎

Lemma 5 and Thm. 3 together provide a polynomial-time procedure for computing
a prompting policy for $k$ that moves it to the optimal incentivizable content
point along a content path not much longer than the shortest such path.

##  Appendix B Omitted Details and Mixed Integer Programming Formulations in
Section 5

In this appendix section, we provide full details of the joint provider
prompting MIP formulation.

### MIP Formulation

We provide the full MIP formulation that computes the optimal joint-provider
prompting policy below:

$\begin{array}[]{ll}\text{maximize
}&\frac{1}{T}\sum_{t=0}^{T-1}\sum_{k\in\mathcal{K}}E_{k}^{t}\\\
\,\text{subject to }\par&(1a)\;C_{k,j}^{t}\leq\nu_{k,j}^{t}M\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},t<T\\\ &(1b)\;\mathit{Aud}_{k}^{t}\geq
C_{k,j}^{t-1}\mathit{Act}_{k,j}^{t}\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},t<T\\\
&(2)\;\widetilde{s}^{t}_{k,j}\widetilde{a}^{t}_{k,j}\geq\widetilde{s}^{t}_{k,j^{\prime}}\widetilde{a}^{t}_{k,j^{\prime}}-(1-\mathit{Act}_{k,j}^{t})M\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},j^{\prime}\in\mathcal{J},t<T\\\
&(3)\;\widetilde{a}^{t}_{k,j}\lesseqgtr\mathit{Aud}_{k}^{t-1}\pm(1-\mathit{Act}_{k,j}^{t-1})M\pm\nu_{k,j}^{t-1}M\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},t<T\\\
&(4)\;\widetilde{a}^{t}_{k,j}\lesseqgtr\widetilde{a}^{t-1}_{k,j}\pm\mathit{Act}_{k,j}^{t-1}M\pm\nu_{k,j}^{t-1}M\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},t<T\\\ &(5)\;\widetilde{a}^{t}_{k,j}\lesseqgtr
C_{k,j}^{t-1}\pm(1-\nu_{k,j}^{t-1})M\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},t<T\\\
&(6)\;E_{k}^{t}=\sum_{q\in\mathcal{Q}}\pi_{q,k}^{t}\sum_{j\in\mathcal{J}}\mathit{Act}^{t}_{k,j}s^{\ast}_{k,j}\sigma(q,j)\hfill\forall
k\in\mathcal{K},t<T\\\
&(7)\;\mathit{Aud}_{k}^{t}=\sum_{q\in\mathcal{Q}}\pi_{q,k}^{t}\sum_{j\in\mathcal{J}}\mathit{Act}_{k,j}^{t}\sigma(q,j)\hfill\forall
k\in\mathcal{K},t<T\\\
&(8)\;\widetilde{s}^{t}_{k,j}=\widetilde{s}^{0}_{k,j}(1-\mathit{Vis}_{k,j}^{t-1})+s^{\ast}_{k,j}\mathit{Vis}_{k,j}^{t-1}\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},1\leq t<T\\\
&(9a)\;\mathit{Vis}_{k,j}^{t}\geq\mathit{Act}_{k,j}^{t^{\prime}}\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},1\leq t<T,t^{\prime}\leq t\\\
&(9b)\;\mathit{Vis}_{k,j}^{t}\leq\sum_{t^{\prime}=0}^{t}\mathit{Act}_{k,j}^{t^{\prime}}\hfill\forall
k\in\mathcal{K},j\in\mathcal{J},1\leq t<T\\\
&(10)\;\sum_{j\in\mathcal{J}}\mathit{Act}_{k,j}^{t}=1\hfill\forall
k\in\mathcal{K},t<T\\\
&(11)\;\sum_{k\in\mathcal{K}}\pi_{q,k}^{t}=1\hfill\forall
q\in\mathcal{Q},t<T\\\ &(12)\;\sum_{j\in\mathcal{J}}\nu_{k,j}^{t}\leq
1\hfill\forall k\in\mathcal{K},t<T\\\
&(13)\;\pi_{q,k}^{t}\in[0,1],\nu_{k,j}^{t}\in\\{0,1\\},C_{k,j}^{t}\geq
0,\mathit{Act}_{k,j}^{t}\in\\{0,1\\},\mathit{Vis}_{k,j}^{t}\in\\{0,1\\}\qquad\forall
k\in\mathcal{K},j\in\mathcal{J},q\in\mathcal{Q},t<T\par\par\end{array}$

Constraints 1–5 are discussed in Section 5. Constraint 6 is the definition of
welfare, Constraint 7 is the definition of audience, Constraint 8 enforces
collapsing skill belief updates, Constraints 9a and 9b enforce that
$\mathit{Vis}_{k,j}^{t}=\max\\{\mathit{Act}_{k,j}^{t^{\prime}}:t^{\prime}\leq
t\\}$, Constraint 10 ensures that a provider is at exactly one location at any
given time, Constraint 11 ensures that the matching determines a probability
distribution over providers, and Constraint 12 ensures that the RS provides at
most one nudge to any given provider at any given time.

The constants (generated as described in the next section and given as input
to the MIP) in the above formulation are (1) affinities $\sigma(q,j)$ for all
$q\in\mathcal{Q},j\in\mathcal{J}$, (2) true skills $s^{\ast}_{k,j}$ for all
$k\in\mathcal{K},j\in\mathcal{J}$, (3) initial skill beliefs
$\widetilde{s}_{k,j}^{0}$ for all $k\in\mathcal{K},j\in\mathcal{J}$, and (4)
initial audience beliefs $\widetilde{a}_{k,j}^{0}$ for all
$k\in\mathcal{K},j\in\mathcal{J}$.

##  Appendix C Omitted Details and Results in Section 6

Here we describe details pertaining to problem instance generation used in our
experiments, present and describe the full set of experiments we ran, and
include some initial thoughts on a column generation (CG) approach to the
multi-provider planning problem.

### Problem Generation for Synthetic Data

We first describe the process used to generate random synthetic problem
instances. Content and user embeddings lie in $\mathbb{R}^{d}_{+}$ (we use
$d=2$). Our $J$ content points are sampled from a $d$-dimensional Gaussian
$P_{\mathcal{J}}=\mathcal{N}(\mathbf{0},a\mathbf{I})$, where $a$ is a scalar.

Provider $k$’s skills are stationary and are represented by points
$k\in\mathbb{R}^{d}_{+}$ in the same space (we equate provider $k$ with its
“skill point”). A provider is sampled from a Gaussian mixture with one
component per content point $j\leq J$, where the mixture coefficient for
component $i$ proportional to $p_{C}(c_{i})$. For any content point $j$, $k$’s
true skill is
$-\frac{d(k,j)-\max_{j^{\prime}}-d(k,j^{\prime})}{\min_{j^{\prime}}-d(k,j^{\prime})}$.
To generate initial skill beliefs $\widetilde{S}^{0}_{k}$ for provider $k$, a
tentative“confused skill point” is sampled from $\mathcal{J}$ with probability
proportional to its (inverse) distance to their true skill $k$. Gaussian noise
is added to determine their initial “confused skill point” $k_{c}$. Provider
$k$’s skill belief $\widetilde{s}^{0}_{k,j}$ is determined analogously to true
skill, but w.r.t. its confused skill $k_{c}$.

Users $q\in\mathbb{R}^{d}_{+}$ are sampled from a Gaussian mixture whose
components are centered on providers in a similar fashion. User affinities for
content points are inversely proportional to their distance from that point:
$\sigma(q,j)=G-d(q,j)$, where $G$ is a global constant ensuring affinities are
positive. We keep $Q$ small, so interpret each $q\in\mathcal{Q}$ as a user
type/cluster.

### Problem Generation for Semi-Synthetic/MovieLens Data

Problems in this scenario were generated by drawing from a pool of embeddings
generated by factorizing the MovieLens dataset. First, a subset of
approximately 100000 users and 1000 movies is used to generate a binary
affinity matrix by conditioning on whether the users’ movie rating is more
than or equal to 4. The resulting sparse matrix is factorized using weighted
alternating least squares (WALS). The movies embeddings are clustered with
k-means into 200 clusters. Each cluster’s center becomes a possible item.

For each individual scenario, a subset of $I$ items is sampled from the
cluster centers without replacement, with probabilities proportional to the
size (number of movies) of each cluster. For each sampled item, the set of
users with affinity greater than $0.005$ is counted to estimate the popularity
of the item. To generate $U$ users, we randomly choose to attach each one of
them to one of the items with probability proportional to the item popularity
as computed above. We then end up with a partition $U$ into $U_{I}$ classes.
For each item $i$, we extract the top $U_{i}$ (in terms of affinity) users
from the dataset and their corresponding embeddings. Affinities between user-
item pairs are computed based on inner product and can be between 0 and 1 due
to the original binarization of the matrix. Providers are generated based on
sub- or super- sampling a set of items and adding uniform Gaussian noise.
Since we have no data-driven way to generate confused beliefs, we then apply
the confusion process of the synthetic scenario.

### Additional Experiments

We include the full set of experiments we ran. These include

  * •

Synthetic instances of sizes

    * –

$(J\in\\{10,15,20,25\\},K=5,Q=30,T=10)$ (Table 3, Figure 4)

    * –

$(J\in\\{10,20\\},K=5,Q=50,T=10)$ (Table 1, Figure 5)

    * –

$(J\in\\{10,20,30,40\\},K=10,Q=50,T=5)$ (Table 4, Figure 6)

  * •

Semi-synthetic/MovieLens instances of sizes

    * –

$(J\in\\{10,20,30,40\\},K=10,Q=50,T=5)$ (Table 5, Figure 7, Figure 8)

    * –

$(J\in\\{10,20\\},K=10,Q=100,T=5)$ (Table 2, Figure 9, Figure 10).

We ran Gurobi with a relative MIP gap of zero (guaranteeing the optimal
solution) for only the smallest set of instances with $Q=30$. For all others,
we set the relative MIP gap to 0.05%, meaning the solution returned is only
guaranteed to be within $0.05\%$ of the truly optimal solution’s objective
value. We did not explicitly linearize our formulation as Gurobi itself
recognizes and performs such linearizations in an optimized fashion.

Fig. 4 plots per-period utility $E^{t}=\sum_{k\in\mathcal{K}}E_{k}^{t}$ as a
function of $t$ for each the described policies averaged over 20 random
instances (each) with $K=5$ content providers, $Q=30$ user queries, $T=10$
time steps, and $J\in\\{10,15,20,25\\}$ content points. We see that for the
smaller instances, namely $J=10$ and $J=15$, the utility of the non-prompting
policy is able to eventually approach the utility of the prompting policy. But
for the larger instances, namely $J=20$ and $J=25$, the non-prompting policy
has a tougher time increasing its per-period utility over the $T$ time steps.
This is further illustrated in Table 3, which records the quantities (averaged
over the $20$ instances) $P^{T}$, $\widehat{P}$, and $D$. The final prompt gap
$P^{T}$ distinctly increases with the size of the instances, and the time-
averaged prompt gap $\widehat{P}$ of the larger instances
($J\in\\{15,20,25\\}$) is twice that of the smallest instance ($J=10$). The
improvement over the stationary policy is significant; ranging from
$40\%-60\%$, showing the importance of dynamically matching and prompting
based on the provider dynamics. Finally, the standard deviations of all
quantities are fairly large, illustrating that for some instances the utility
improvement due to prompting is not too large, but for other instances it is
dramatic. We also solved the compact MIP for a set of slightly larger
instances with $Q=50$ user queries. For these instances, we terminated Gurobi
once a relative MIP gap of $0.05\%$ was obtained. This means that the plotted
utilities are within $0.05\%$ of the truly optimal utilities (though in most
cases they are in fact optimal; for only a few of the instances Gurobi was
unable to close the MIP gap completely even after 8 hours). Fig. 5 plots per-
period utility averaged over 20 random instances (each) with $K=5$, $Q=50$,
$T=10$, and $J\in\\{10,20\\}$, and Table 1 records $P^{T}$, $\widehat{P}$, and
$D$. The policies displayed similar trends on these larger instances: the
improvements due to prompting are more significant for the instances with
$J=20$, and for these instances the per-period utility of the non-prompting
policy has a tougher time approaching that of the prompting policy over the
$T$ periods. Similar trends arise when the number of providers and items are
bumped up to $K=10$ and $J\in\\{10,20,30,40\\}$ (Fig. 6 and Table 4).

On the MovieLens instances, larger numbers of content items has less of an
effect on the (final and time-averaged prompt gap), and the gaps are generally
smaller than those of the synthetic instances. But, increasing the number of
content items has a marked impact on $D$, the improvement over the stationary
policy (Tables 5 and 2). Furthermore, unlike the synthetic instances where the
non-prompting policy appears to improve over time, the non-prompting policy
doesn’t exhibit any discernible improvement over the 5 time steps, accruing
significant user regret. Finally, for the MovieLens instances, we generated
histograms of user utility counts to compare time-averaged utilities $U_{q}$
of individual users between the prompting and non-prompting policy (Figures 8
and 10). These reflect a clear improvement due to prompting—reducing the
number of low-utility users and increasing the number of high-utility users.

Scalability: We generally observed that the MIP suffered from scalability
issues. One explanation is the large number of “big-M” constraints—Constraints
Cons. 1(a), Cons. 2, Cons. 3, Cons. 4, 5 all contain a term $M$ that increases
with $Q$ (we define it to be $Q$ times the maximum query-content affinity).
This inherently makes the dual bounds in branch-and-bound significantly
weaker, slowing the search dramatically. One avenue towards a scalable
solution is the column generation formulation we discuss next.

$J$ |  | Avg $P^{T}$
---
| SD $P^{T}$
---
| Avg $\widehat{P}$
---
| SD $\widehat{P}$
---
| Avg $D$
---
SD $D$
10 | 1.7% | 2.5% | 5.2% | 4.3% | 39.8% | 24.9%
15 | 6.6% | 5.8% | 10.5% | 5.7% | 54.1% | 26.5%
20 | 8.2% | 5.1% | 9.7% | 5.6% | 58.7% | 41.2%
25 | 9.2% | 5.3% | 10.1% | 5.7% | 40.6% | 25.1%
Table 3: (Synthetic) Final gap $P^{T}$, time-avg. gap $\widehat{P}$, stationary gap $D$ (avg. over 20 instances), varying $J$ ($K=5,Q=30,T=10)$. $J$ |  | Avg $P^{T}$
---
| SD $P^{T}$
---
| Avg $\widehat{P}$
---
| SD $\widehat{P}$
---
| Avg $D$
---
SD $D$
10 | 5.6% | 4.5% | 6.2% | 4.0% | 25.9% | 13.4%
20 | 7.1% | 3.1% | 6.9% | 2.7% | 20.8% | 12.3%
30 | 8.8% | 3.6% | 8.2% | 3.4% | 27.0% | 13.8%
40 | 8.9% | 3.7% | 8.4% | 3.0% | 27.7% | 12.6%
Table 4: (Synthetic) Final gap $P^{T}$, time-avg. gap $\widehat{P}$, stationary gap $D$ (avg. over 20 instances), varying $J$ ($K=10,Q=50,T=5)$. $J$ |  | Avg $P^{T}$
---
| SD $P^{T}$
---
| Avg $\widehat{P}$
---
| SD $\widehat{P}$
---
| Avg $D$
---
SD $D$
10 | 3.3% | 2.8% | 3.1% | 2.4% | 29.9% | 14.1%
20 | 5.0% | 3.5% | 4.3% | 3.0% | 25.7% | 14.4%
30 | 4.7% | 2.1% | 4.1% | 1.9% | 48.3% | 42.7%
40 | 4.1% | 3.1% | 3.7% | 2.8% | 51.2% | 39.5%
Table 5: (MovieLens) Final gap $P^{T}$, time-avg. gap $\widehat{P}$,
stationary gap $D$ (avg. over 20 instances), varying $J$ ($K=10,Q=50,T=5)$.

Figure 4: (Synthetic) Total per-period utility $E^{t}$ (avg. over 20
instances) for different policies, varying $J$ ($K=5,T=10,Q=30$).

Figure 5: (Synthetic) Total per-period utility $E^{t}$ (avg. over 20
instances) for different policies, varying $J$ ($K=5,T=10,Q=50$).

Figure 6: (Synthetic) Total per-period utility $E^{t}$ (avg. over 20
instances) for different policies, varying $J$ ($K=10,Q=50,T=5$).

Figure 7: (MovieLens) Total per-period utility $E^{t}$ (avg. over 20
instances) for different policies, varying $J$ ($K=10,Q=50,T=5$).

Figure 8: (MovieLens) User utility histograms (avg. over 20 instances),
varying $J$ ($K=10,Q=50,T=5$).

Figure 9: (MovieLens) Total per-period utility $E^{t}$ (avg. over 10
instances) for different policies, varying $J$ ($K=10,Q=100,T=5$).

Figure 10: (MovieLens) User utility histograms (avg. over 10 instances),
varying $J$ ($K=10,Q=100,T=5$).

### Column Generation Formulation

Our column generation (CG) formulation differs considerably from the first
(which we refer to as the compact formulation). Instead of articulating a
(relatively) small integer program, it provides a large linear program whose
solutions are likely to be integer points. The idea is to enumerate (somewhat
implicitly) the possible content location paths a provider can take. More
precisely, for each provider and stage, we consider explicitly the audience
(subset of users) matched to the provider at that stage, as well as any
audience commitment made by an RS prompt. Given any _entire sequence_ of such
matchings/prompts, assuming only that provider belief updates are
deterministic, the location path of the provider is then fixed. This extended
model enumerates all such sequences, requiring a doubly exponential number of
variables, in contrast to the compact MIP formulation. For this reason we
develop a CG formulation. With CG, our second model has a number of
advantages: the MIP is “naturally linear,” without the need to linearize
quadratic terms; it also contains fewer, less complicated constraints;
finally, it supports arbitrarily complex belief dynamics (requiring only
deterministic update).

Let a _star_ be a subset $Q\subseteq\mathcal{Q}$ of users, representing a
possible audience that can be matched to a provider at a given stage. A
_multi-star_ is a sequence of stars $\bar{Q}=(Q_{1},\ldots,Q_{T})$ of length
$T$ (one per stage). There are $2^{|\mathcal{Q}|^{T}}$ multi-stars. A
_promise_ $C\in\mathbb{R}^{J}_{\geq 0}$ is a non-negative vector with at most
one non-zero coordinate (bounded by $|\mathcal{Q}|$), reflecting the audience
utility promised to a provider via some prompt, with a _multi-promise_
$\bar{C}=(C_{1},\ldots,C_{T})$ defined in the obvious way. A _treatment_
$\tau=(\bar{Q},\bar{C})$ reflects the impact of an RS matching/prompting
policy on a provider; $\tau$ is _honest_ if the realised audiences at each
stage meet (or exceed) the promises. Let $\mathcal{T}$ be set of honest
treatments.

Key to our MIP is the use of binary variables for each provider-treatment pair
$\mu_{k,\tau}$, $k\in\mathcal{K},\tau\in\mathcal{T}$ dictating the treatment
(audiences and prompted commitments) associated with each provider. We omit
full details, but describe the main components and concepts underlying the
formulation. First, we assume deterministic skill and audience belief updates
(e.g., as described above). This means that, given the initial state $S^{0}$,
and the treatment $\tau$ assigned to provider $k$, we can _precompute_ the
exact utility $E_{k,\tau}$ across all $T$ stages, i.e., these are constants.
With standard constraints (e.g., one treatment per provider; no user matched
to more than one provider per stage, i.e., no “star overlap”), we optimize
total user utility:
$\sum_{k\in\mathcal{K},\tau\in\mathcal{T}}E_{k,\tau}\mu_{k,\tau}$. Notice that
this approach makes very few assumptions about provider belief dynamics or
best response behavior—it is all encoded in the computation of objective
coefficients $E_{k,\tau}$.777Suppose that we allowed content points to fall
anywhere in $\mathbb{R}^{d}$. Once a star (or audience
$Q\subseteq\mathcal{Q}$) is fixed at stage $t$, the fact that $k$’s best
response is to maximize utility dictates a unique content point suitable for
that audience. Given the finite number of user subsets, this justifies the
assumption of a finite (though possible large) set of viable content points.
The size of this set, fortunately, plays no role when we use CG.

The price one pays in this MIP is the explosion in the number of decision
variables, which enumerates _all treatments_ (per provider). Of course, only a
small number of these will be active at the optimal solution (or in _any_
feasible solution), so we can solve the problem using _column generation (CG)_
(Lübbecke and Desrosiers 2005). In CG, we solve the problem using only a
subset of these variables (or columns in the LP relaxation of the MIP), solve
a _subproblem_ to determine the missing variable (column) whose addition
offers the greatest marginal increase in objective value, then add that
variable/column and re-solve. This process is repeated until no improving
values are found or some other termination criterion is met (e.g., reaching a
max number of iterations, or minimum improvement threshold). The reduced LP
has one constraint for every provider $k$ and one for every user-stage pair
$(q,t)$. The CG subproblem requires finding the variable with maximum _reduced
cost_ : given the values of the dual variables (one per constraint,
$\lambda_{k}$ for $k\in K$ and $\lambda_{qt}$ for
$(q,t)\in\mathcal{Q}\times[1,\ldots,T]$) at the optimal solution of the
current reduced LP, we find the provider/treatment pair

$(k^{\ast},\tau^{\ast})=\operatorname*{argmax}_{k\in
K,\tau\in\mathcal{T}}E_{k,\tau}-\lambda_{k}-\sum_{t}\sum_{q\in
Q_{t}^{\tau}}\lambda_{qt}$

and add the corresponding variable $\mu_{k^{\ast},\tau^{\ast}}$ to the LP.
(Here $Q_{t}^{\tau}$ is the $t$th star in treatment $\tau$.)

Another advantage of our star/treatment formulation is evident: the dual
decomposition reduces the subproblem to a collection of _single-provider_
location-path planning problems. We find the max reduced-cost improving
treatment for each provider, then add the treatment for the maximizing
provider.