# Reconciling the accuracy-diversity trade-off in recommendations

Kenny Peng, Manish Raghavan, Emma Pierson, Jon Kleinberg†, Nikhil Garg†††Kenny
Peng, Cornell Tech<EMAIL_ADDRESS>Manish Raghavan, MIT; Emma
Pierson, Cornell Tech; Jon Kleinberg, Cornell University; Nikhil Garg, Cornell
Tech<EMAIL_ADDRESS>†Joint senior author.

###### Abstract

In recommendation settings, there is an apparent trade-off between the goals
of accuracy (to recommend items a user is most likely to want) and diversity
(to recommend items representing a range of categories). As such, real-world
recommender systems often explicitly incorporate diversity separately from
accuracy. This approach, however, leaves a basic question unanswered: Why is
there a trade-off in the first place?

We show how the trade-off can be explained via a user’s consumption
constraints—users typically only consume a few of the items they are
recommended. In a stylized model we introduce, objectives that account for
this constraint induce diverse recommendations, while objectives that do not
account for this constraint induce homogeneous recommendations. This suggests
that accuracy and diversity appear misaligned because standard accuracy
metrics do not consider consumption constraints. Our model yields precise and
interpretable characterizations of diversity in different settings, giving
practical insights into the design of diverse recommendations.

##  1 Introduction

A large body of work in recommendations has developed methods to navigate an
apparent trade-off between the goals of accuracy (to recommend items a user is
most likely to want) and diversity (to recommend items from a range of
categories) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
19, 20, 21, 22, 23]. Real-world recommender systems use heuristics to directly
incorporate diversity into recommendations [24, 25], and empirical evidence
demonstrates that users prefer diverse recommendations [26, 27, 28, 29].

A fundamental question remains: Why is there a trade-off in the first place?
More specifically, why is “accuracy” unaligned with a user’s true preference
for diversity? Without a principled understanding of the accuracy-diversity
trade-off, attempts to diversify recommendations have difficulty moving beyond
a heuristic basis—and difficulty articulating what they are accomplishing at a
deeper level.

In this work, we introduce and analyze a stylized model of recommendations
that helps explain and reconcile the apparent accuracy-diversity trade-off.
Our model studies this trade-off through the lens of a user’s consumption
constraints: users typically examine a list of recommendations and use only
the top (highest value) options. (A person can watch only one movie in an
evening, a recruiter can select only a handful of candidates to interview.)
This lens has strong explanatory power:

  * •

When the goal is to maximize the expected value of the top recommended items,
diverse recommendations are often optimal in our model. By accounting for a
user’s consumption constraints, optimizing for what they are most likely to
want is aligned with recommending a diverse set of items.

  * •

Without accounting for consumption constraints, optimal recommendations in our
model are homogeneous. This suggests that the trade-off between accuracy and
diversity can be explained by commonly-used accuracy metrics not accounting
for consumption constraints.

A strength of our model is that we can precisely and interpretably analyze the
optimal amount of diversity in different settings, allowing us to isolate the
effect of consumption constraints. This precision also yields practical
insights about the role of diversity in recommendations. In Theorem 3, for
example, we uncover natural settings where optimal recommendations
overrepresent the category of item a user is least likely to want—a paradox
that appears in grocery stores, where even though customers are less likely to
buy ice cream than milk, stores allocate much more space to ice cream.

###  1.1 Model

There are $m$ types of items indexed by $[m]=\\{1,2,\cdots,m\\}.$ A user
prefers exactly one type of item, preferring type $t\in[m]$ with probability
$p_{t}$. The value of the $i$-th item of type $t$ is a random variable
$X_{i}^{(t)}$ if the user prefers type $t$ and $0$ otherwise (so its expected
value is $p_{t}\mathbb{E}[X_{i}^{(t)}]$). The recommender knows only how
$X_{i}^{(t)}$ are distributed, not their realizations. We refer to $p_{t}$ as
the likelihood of a type and the random variable $X_{i}^{(t)}$ as a
conditional item value (the value of an item conditional on the user
preferring the item’s type).

Let $S_{n,k}$ be the set of $n$ items that maximizes the expected total value
of the $k$ items with the highest realized values. We call $S_{n,k}$ the
optimal set of $n$ recommendations with respect to this objective. (We omit
the dependency of $S_{n,k}$ on the other model parameters, as these will be
clear from context.)

$S_{n,k}$ arises naturally from an assumption that the user can only use $k$
items, so that they derive value from the $k$ highest value recommended items.
So $S_{n,1}$ results from an assumption that the user uses only one item,
while $S_{n,n}$ results from an assumption that the user uses every
recommended item.

$S_{n,n}$ maximizes the expected total value of all of the recommended items,
so by linearity of expectation, $S_{n,n}$ contains the $n$ items with the
highest individual expected values.

Meanwhile, $S_{n,1}$ maximizes the expected value of the highest-value item,
an objective that—importantly—is not maximized by choosing the individual
items with the highest expected values.

##### Our overarching technical result and interpretation.

Our main results (summarized in Table 1) show across several settings that:

> $S_{n,k}$ is diverse for $k$ fixed and $n$ growing. Meanwhile, $S_{n,n}$ is
> homogeneous.

This technical result has an interpretation explaining the accuracy-diversity
trade-off. Objectives that account for a user’s consumption constraints
naturally induce diversity, while objectives that do not account for
consumption constraints can produce homogeneous recommendations. Thus, the
observed trade-off is (partly) a consequence of common accuracy metrics not
modeling consumption constraints.

One might suggest that our results show homogeneity is desirable when users
can use all recommended items. We do not emphasize this interpretation since
there are additional reasons outside of our model to incorporate diversity.
Thus, our results are best interpreted as showing (1) that diversity arises
under minimal assumptions, and (2) that standard objectives can (mistakenly)
induce homogeneity.

##### Evaluating diversity.

To evaluate diversity, we consider the representation of each type in
$S_{n,k}$. In many of our results, representation falls on an interpretable
continuum: from complete diversity (each type represented equally) to
proportional diversity (each type represented proportionally to its likelihood
$p_{t}$) to homogeneity (only the highest likelihood type represented). We
formalize our measure of diversity in Section 2.

Table 1: Our main results broadly show: (1) consumption constraints induce diverse recommendations, and (2) without accounting for consumption constraints, recommendations tend to be homogeneous. Setting | With consumption constraints | Without consumption constraints
---|---|---
Thm. 1. $X_{i}^{(t)}\sim\mathcal{D}$ |  As $n$ grows large for fixed $k$, $S_{n,k}$ exhibits diversity depending on the tail behavior of $\mathcal{D}$.
For non-heavy-tailed $\mathcal{D}$, $S_{n,k}$ is at least proportionally diverse. |  $S_{n,n}$ contains only one type of item.
|  |
Thm. 2. $X_{i}^{(t)}\sim\operatorname{Ber}(q_{i})$ for $q_{1},q_{2},\cdots$ decaying by a power law (roughly, $q_{i}\propto i^{-\alpha}$). |  For moderate amounts of decay $(\alpha<1)$, as $n$ grows large, $S_{n,1}$ represents each item type equally. |  For moderate amounts of decay $(\alpha<1)$, as $n$ grows large, $S_{n,n}$ is less than proportionally diverse.
|  |
Thm. 3. $X_{i}^{(t)}\sim\operatorname{Ber}(q_{t})$ for $q_{1},q_{2},\cdots,q_{m}$. |  For large $n$, $S_{n,1}$ represents each item type in proportion to  $\frac{1}{\log\frac{1}{1-q_{t}}},$ so that items of lower success probability are recommended more. |  $S_{n,n}$ contains only one type of item.

##### Discussion and limitations.

Our model is purposefully stylized and minimal so that we can abstract a small
set of ingredients common to a wide set of domains—namely, those where users
prefer a certain category of items and a recommender has noisy estimates of
user preferences and item values. Importantly, our model captures the
consumption constraints of users: when a user is given a set of
recommendations, they can typically use only the best few recommendations—a
person can watch only one movie in an evening, a recruiter can select only a
handful of candidates to interview.

Other reasons for diversity. Importantly, when we refer to optimal sets of
recommendations, we mean optimal with respect to our stylized optimization
problem—maximizing the expected sum of the $k$ highest item values. In real-
world contexts, there are many reasons to incorporate diversity that we do not
consider here. For example, our model does not consider any explicit
preferences users have for diversity. While such a preference may be
empirically well-grounded, omitting such a preference makes our conclusions
stronger: simply by modeling user consumption constraints, we show that
diversity arises naturally in optimal recommendations even when our model does
not explicitly value diversity.

Model generalizations. Real-world settings can differ from our model in
natural ways. For example, users can prefer multiple types of items at a time
and some items may fall under multiple types. We discuss generalizations in
Appendix C. Here, the assumptions that users prefer only one type and items
each fall under one type allow us to analyze diversity in an interpretable
way: characterizing how represented each item type is in comparison to the
user’s likelihood of preferring that type.

###  1.2 An illustrative example: Recovering Steck’s standard of calibration

We now consider a simple instantiation of our model, motivated by a thought
experiment suggested by the Netflix researcher Harald Steck [30]. A user
watches romance movies 70 percent of the time and action movies the other 30
percent of the time. Steck raises a concern that an accuracy-maximizing
algorithm can produce entirely homogeneous recommendations in this setting,
and proposes a standard of calibration, where 70 percent of recommended movies
here are romance and 30 percent are action. The example below reflects Steck’s
concern by showing that—before accounting for consumption constraints—optimal
recommendations are homogeneous. Yet, by assuming a user can only watch one
movie, the optimal recommendations in the example are in fact naturally
calibrated.

######  Example 1 (Recovering calibration).

Suppose there are two genres of movies, romance and action, indexed 1 and 2
respectively. A user prefers romance with probability $p_{1}$ and action with
probability $p_{2}$, with $p_{1}>p_{2}.$ Movies from the user’s preferred
genre have values drawn i.i.d. from an exponential distribution
$\operatorname{Exp}(\lambda)$, while other movies have value $0$. In the
language of our model,
$X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\operatorname{Exp}(\lambda)$.

$S_{n,n}$ maximizes the expected total value of recommended items, so by
linearity of expectation it contains the items of highest individual expected
value. The expected value of each romance and action movie are
$p_{1}\mathbb{E}[\operatorname{Exp}(\lambda)]$ and
$p_{2}\mathbb{E}[\operatorname{Exp}(\lambda)]$ respectively, so $S_{n,n}$
contains only romance movies.

$S_{n,1}$ maximizes the expected value of the best recommended movie. The
expected value of the best item among $a_{1}$ romance movies and $a_{2}$
action movies (where $a_{1}+a_{2}=n$) is

$p_{1}\cdot\mathbb{E}[\text{max of $a_{1}$ draws from
$\operatorname{Exp}(\lambda)$}]+p_{2}\cdot\mathbb{E}[\text{max of $a_{2}$
draws from $\operatorname{Exp}(\lambda)$}]$ (1)
$\approx\frac{p_{1}}{\lambda}\log(a_{1})+\frac{p_{2}}{\lambda}\log(a_{2}),$
(2)

which is maximized when $a_{1}=p_{1}n$ and $a_{2}=p_{2}n$ (as shown using
Lagrange multipliers). Therefore, $S_{n,1}$ has proportional representation,
recovering Steck’s standard of calibration.

###  1.3 Intuition for our overarching result

In the model we propose, a user’s value depends only on the recommended items
from the user’s preferred type. Therefore, conditional on a user preferring
type $t$, the user’s expected value from a set of recommendations with $a_{t}$
items of type $t$ is given by $h_{t}(a_{t})$ for some function $h_{t}$. Then
the user’s expected value from a set of recommendations with $a_{t}$ items of
type $t$ for all $t\in[m]$ is of the form

$\sum_{t=1}^{m}p_{t}h_{t}(a_{t}).$ (3)

The key idea of our work is that when accounting for consumption constraints,
the function $h_{t}$ reflects diminishing returns: recommending additional
items from a type becomes less and less valuable when we care only about the
value of the best recommended items—when a user can only watch one movie,
recommending three options for romance movies might be significantly better
than two, because the platform doesn’t know which exact romance movie the user
may like; however, recommending 20 such movies is barely better than 19. Thus,
when maximizing (3), it becomes preferable to recommend items from other
types. Meanwhile, without modeling user consumption constraints, there are not
necessarily diminishing returns since the user can use all of the additional
items recommended.

The particular shape of the diminishing returns regulates the amount of
resulting diversity. In Example 1, we had that $h_{t}(x)\propto\log x,$ in
which case (3) is maximized when $a_{t}\propto p_{t}$, yielding proportional
representation.111The mathematical result in this example also appears in the
context of resource allocation (e.g., [31]) and betting (e.g., §22.2 in [32])
in the presence of logarithmic utility. Our technical work thus involves
analyzing the functions $h_{t}$ in different settings (this reduces to
analyzing the large order statistics of different distributions). Roughly
speaking, heavier-tailed conditional item values imply larger marginal
returns, resulting in less diversity.

###  1.4 Related work

As we have noted, there is a wide literature devoted to developing methods to
navigate the accuracy-diversity trade-off [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]. Such work is supported by
empirical evidence suggesting that a combination of these two metrics is
preferred by users [26, 27, 28, 29]. Of particular interest to us, however, is
work that focuses on objectives that implicitly correspond to diversity. In
the context of web search, optimizing for the probability that the user is
shown a satisfactory search result has been associated with diversification
[33, 34], since effective search results must account for different intents of
queries (“pandas” can refer to an animal or a Python package). More recent
work has adapted this objective to the recommender system setting as a metric
that unifies accuracy and diversity [35]. Our work, by explicitly
characterizing optimal amounts of diversity, identifies consumption
constraints as the underlying reason for why such approaches result in
diversity. We discuss additional related work in Appendix A.

##  2 Evaluating diversity

We now formalize our approach to evaluating diversity. For a set $S$ of items,
we define

$r_{t}(S):=\frac{\text{\\# of items in }S\text{ of type }t}{|S|},$ (4)

the representation of type $t$ in $S$. Intuitively, a set of recommendations
is diverse if all types are well represented. We now define an interpretable
family of representations that interpolates between maximum diversity and
maximum homogeneity, and which arises naturally in many of our results.

######  Definition 1 ($\gamma$-homogeneity).

A set $S$ is $\bm{\gamma}$-homogeneous if for all $t\in[m],$

$r_{t}(S)=\frac{p_{t}^{\gamma}}{\sum_{i=1}^{m}p_{i}^{\gamma}}.$ (5)

$\gamma$-homogeneity captures several intuitive notions of diversity, using
$p_{1},\cdots,p_{m}$ as a benchmark:

  * •

When $\gamma=0$, $r_{t}(S)=\frac{1}{m}.$ There is “equal representation.”

  * •

When $\gamma=1$, $r_{t}(S)=p_{t}.$ There is “proportional representation,”
where an item type is represented in proportion to its likelihood.

  * •

When $\gamma=\infty$, $r_{t}(S)=1$ for
$t=\operatorname*{arg\,max}_{i\in[m]}p_{i}$ and $r_{t}(S)=0$ otherwise. There
is “complete homogeneity,” where only the highest-likelihood item type is
represented.

A smaller $\gamma$ corresponds to more diversity, with $\gamma\leq 1$
indicating at least proportional representation. In practice, it is
challenging to show that individual sets are $\gamma$-homogeneous; for one,
since sets have an integer number of items from each type, it is typically
impossible to obtain the exact ratios in (5). Instead, we will give primarily
asymptotic results, showing that as $n$ grows large, the optimal set $S_{n,k}$
approaches $\gamma$-homogeneity. Formally, we define $\gamma$-homogeneity over
sequences of sets:

######  Definition 2 ($\gamma$-homogeneity for set sequences).

A sequence of sets $\\{S_{n}\\}_{n=1}^{\infty}$ is $\bm{\gamma}$-homogeneous
if for all $t\in[m],$

$\lim_{n\rightarrow\infty}r_{t}(S_{n})=\frac{p_{t}^{\gamma}}{\sum_{i=1}^{m}p_{i}^{\gamma}}.$
(6)

One perhaps surprising aspect of our results is that $\gamma$-homogeneity is
sufficient to characterize diversity in a large class of settings, as opposed
to requiring more complicated functions of proportions $p_{t}$.

##  3 Main results

We now state our main results, which consider several settings reflecting
different assumptions about the conditional item values $X_{i}^{(t)}.$ In
Section 3.1, we assume that
$X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\mathcal{D}$ are drawn from a shared
distribution, which implies that the recommender has little information about
the value of specific items. In Section 3.2, $X_{i}^{(t)}$ are Bernoulli
random variables with success probabilities differing depending on $i$ and
$t$, meaning that the recommender has information about which items are more
likely to satisfy a user.

In each setting, we analyze the diversity of optimal sets $S_{n,k}$ for when
$k$ is fixed (i.e., accounting for consumption constraints) and $k=n$ (i.e.,
not accounting for consumption constraints). We sketch our proof strategy in
Section 4 and defer full proofs to Appendix D.

###  3.1 i.i.d. conditional item values

Consider the setting in which
$X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\mathcal{D},$ i.e., conditional item
values are drawn from a shared distribution. This implies that the values of
items behave similarly across types and within types, and the platform cannot
easily distinguish between the items in a type. From the perspective of a
hiring platform, there may be many candidates with similar backgrounds (e.g.,
education or work history), none of whom can be distinguished from another by
the platform. Conditional on a recruiter preferring this background, candidate
values can be modeled as coming from a shared distribution.

We show that for a fixed $k$, as $n$ grows large, the diversity of $S_{n,k}$
theoretically varies between equal representation, proportional
representation, and near-complete homogeneity depending on the tail-behavior
of $\mathcal{D}$. In particular, distributions that are bounded or have
exponential tails induce at least proportional representation. Meanwhile,
$S_{n,n}$ is completely homogeneous.

######  Theorem 1.

Suppose $X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\mathcal{D}$ where
$\mathcal{D}$ has finite mean. Then the following statements hold.

  1. (i)

[Finite Discrete] If $\mathcal{D}$ is a finite discrete distribution,
$\\{S_{n,k}\\}_{n=1}^{\infty}$ is $0$-homogeneous.

  2. (ii)

[Bounded] If $\mathcal{D}$ has support bounded from above by $M$ with pdf
$f_{\mathcal{D}}$ satisfying

$\lim_{x\rightarrow M}\frac{f_{\mathcal{D}}(x)}{(M-x)^{\beta-1}}=c$ (7)

for some $\beta,c>0$, then $\\{S_{n,k}\\}_{n=1}^{\infty}$ is
$\frac{\beta}{\beta+1}$-homogeneous.
(This pdf class contains beta distributions, including the uniform
distribution.)

  3. (iii)

[Exponential tail] If $\mathcal{D}=\operatorname{Exp}(\lambda)$ for
$\lambda>0,$ then $\\{S_{n,k}\\}_{n=1}^{\infty}$ is $1$-homogeneous.

  4. (iv)

[Heavy tail] If $\mathcal{D}=\operatorname{Pareto}(\alpha)$ for $\alpha>1$,
then $\\{S_{n,k}\\}_{n=1}^{\infty}$ is $\frac{\alpha}{\alpha-1}$-homogeneous.

Additionally,

  1. (v)

$S_{n,n}$ contains only items of type
$t=\operatorname*{arg\,max}_{t\in[m]}p_{t}.$

As Table 2 illustrates, the theorem shows how for fixed $k$, the diversity of
optimal solutions depends on the tail behavior of $\mathcal{D}$. In fact, we
can obtain $\gamma$-homogeneity for any $\gamma$:

######  Corollary 1.

For any $\gamma\geq 0,$ there exists $\mathcal{D}$ such that when
$X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\mathcal{D}$ and $k$ is fixed,
$\\{S_{n,k}\\}_{n=1}^{\infty}$ is $\gamma$-homogeneous.

Intuitively, heavy-tailed distributions (part (iv)) induce less diverse
recommendations since the marginal returns of recommending more items from the
same type remains high: drawing more samples from a heavy-tailed distribution
produces ever-increasing item values. This contrasts with bounded
distributions like the uniform distribution (part (ii)), where once an item
has close to the maximum value, additional draws of that type will not further
improve the utility significantly.

Table 2: A summary of Theorem 1. For $X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\mathcal{D}$, distributions $\mathcal{D}$ with heavier tails induce less diversity. | bounded | exp. tail | heavy tail
---|---|---|---
| Thm. 1(ii) | Thm. 1(iii) | Thm. 1(iv)
example $\mathcal{D}$ |  | $\operatorname{Beta}(\cdot,\beta)$ |  | $\operatorname{Exp}(\lambda)$ | $\operatorname{Pareto}(\alpha)$
| $0<\beta<1$ | $\beta=1$ | $\beta>1$ | $\lambda>0$ | $\alpha>1$
|  |  |  |  |
$\\{S_{n,k}\\}_{n=1}^{\infty}$ |  |  |  |  |
$\gamma$-homog. |  |  |  |  |
for $\gamma\in$ | $(0,1/2)$ | $1/2$ | $(1/2,1)$ | $1$ | $(1,\infty)$
|  |  |  | (i.e., proportional) |
|  $\longleftarrow$ more diverse less diverse $\longrightarrow$

##### A result for finite $n$ and larger $k$.

One limitation of our main results is that they are asymptotic
$(n\rightarrow\infty)$ and are restricted to fixed consumption constraints
$k$. Stronger results can be obtained by considering specific distributions.
For example, the result below characterizes for any $n,k$ the representation
of each type when conditional item values are uniformly distributed on
$[0,1].$

######  Proposition 2.

When $X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}U([0,1])$,

$\left|r_{t}(S_{n,k})-\frac{\sqrt{p_{t}}}{\sum_{i=1}^{m}\sqrt{p_{i}}}\right|\leq\frac{m+1}{n}.$
(8)

for all $k\leq\frac{\sqrt{p_{m}}}{\sum_{i=1}^{m}\sqrt{p_{i}}}n-m-1.$

Therefore, for any $n$, $S_{n,k}$ is approximately $\frac{1}{2}$-homogeneous.
In addition, for any $k$ that is smaller than a constant fraction of $n$, the
diversity $S_{n,k}$ does not depend on $k$. Thus, even for small sets of
recommendations and large consumption constraints, diversity is optimal in
this setting. We further give simulated results for small $n$ and large $k$ in
Appendix B corroborating our theoretical results.

###  3.2 Heterogeneous Bernoulli conditional item values

Now consider when $X_{i}^{(t)}$ are independent random variables drawn from
$\operatorname{Ber}(q_{i}^{(t)})$, reflecting a model in which items have
binary values (i.e., a user is either satisfied or not satisfied by an item).
In this section, we allow $q_{i}^{(t)}$ to differ across $i$ and $t$, implying
that the recommender has knowledge about which items are more likely to be
successful conditional on a user’s preferred type. Specifically, in Section
3.2.1 we allow $q_{i}^{(t)}$ to vary across $i$ and in Section 3.2.2 we allow
$q_{i}^{(t)}$ to vary across $t$.

Our results will focus on $S_{n,1}$ and $S_{n,n}$, which both have natural
interpretations in this setting:

  * •

$S_{n,1}$ maximizes the probability that the user will be satisfied by at
least one recommended item.

  * •

$S_{n,n}$ maximizes the the expected number of recommended items the user will
be satisfied by, which is equivalent to the standard metric of accuracy.

Before proceeding, we note that the basic case $q_{i}^{(t)}=q$ for all $i,t$
is handled as a direct corollary of Theorem 1(i).

######  Corollary 3 (Conditional item values are i.i.d. Bernoulli).

When $X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\operatorname{Ber}(q)$ for $q>0,$
then $S_{n,1}$ is $0$-homogeneous.

Therefore, if the success probability is the same for all items, optimal
solutions are $0$-homogeneous (each item is equally represented) for large
$n$, even as the likelihoods $p_{t}$ vary across type.

####  3.2.1 Decaying success probabilities

We now consider a setting in which among items of the same type, the
recommender knows that some items have higher success probability. This maps
onto settings where the recommender knows which items of a type are most
likely to be satisfactory, e.g., some action movies are more commonly liked
than are others. Thus, we assume that the recommender has access to items with
decaying success probabilities.

######  Theorem 2 (Decaying success probabilities).

Suppose that
$X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\operatorname{Ber}(q_{i}^{(t)})$ are
i.i.d. Bernoulli random variables such that $q_{i}^{(t)}=c(i+d)^{-\alpha}$ for
all $i\geq 1$ and some $\alpha,c,d\geq 0.$ Then the following statements hold.

  1. (i)

$\\{S_{n,1}\\}_{n=1}^{\infty}$ is $0$-homogeneous for $\alpha<1.$

  2. (ii)

$\\{S_{n,1}\\}_{n=1}^{\infty}$ is $\frac{1}{1+c}$-homogeneous for $\alpha=1.$

  3. (iii)

$\\{S_{n,1}\\}_{n=1}^{\infty}$ is $\frac{1}{\alpha}$-homogeneous for
$\alpha>1.$

Additionally,

  1. (iv)

$\\{S_{n,n}\\}_{n=1}^{\infty}$ is $\frac{1}{\alpha}$-homogeneous for
$\alpha\geq 0.$

Figure 1: Theorem 2 considers items decay in quality within each type. Here,
we plot optimal diversity as a function of the rate of decay $\alpha$. For
realistic rates of decay we ($\alpha<1$), $S_{n,k}$ is completely diverse for
large $n$ while $S_{n,n}$ is less than proportionally diverse.

When the success probabilities of items have moderate decay ($\alpha<1$), then
$0$-homogeneity is maintained in the case $k=1$ (note that $\alpha=0$ recovers
Corollary 3). Moreover, for all rates of decay, optimal recommendations
reflect at least proportional diversity for large $n$ and $k=1$.

Theorem 2 also reveals surprising non-monotonic behavior. In particular, there
is a discontinuity at $\alpha=1$, where homogeneity suddenly increases, but
then decreases as $\alpha$ continues to increase. At $\alpha=1,$ the optimal
amount of diversity when $\alpha=1$ can range between $0$ and $1$ depending on
$c$.

When $k=n$, a larger rate of decay induces more diverse recommendations.
Intuitively, when there is a larger rate of decay, the recommender has fewer
high-quality options of a given type and is more incentivized to recommend
high-quality options of other types. Note that for moderate rates of decay
($\alpha<1$), $S_{n,n}$ remains less than proportionally diverse for large
$n$, unlike $S_{n,1}$.

####  3.2.2 Varying success probability across types

We now consider a setting in which the success probability of an item varies
across types. This can arise when a users are more picky for some types of
items, or when the recommender has more information about items from one type
than another.

######  Theorem 3 (Varying success probability across types).

Suppose that for each fixed $t$,
$X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\operatorname{Ber}(q_{t})$ are i.i.d.
Bernoulli random variables. Then

$\lim_{n\rightarrow\infty}r_{t}(S_{n,1})\propto\frac{1}{\log\frac{1}{1-q_{t}}}$
(9)

while $S_{n,n}$ contains only items of type
$t=\operatorname*{arg\,max}_{t\in[m]}p_{t}q_{t}.$

The surprising high-level takeaway from Theorem 3 is that, for large $n$, a
smaller success probability $q_{t}$ results in more representation of type
$t$. The less likely an item of a given type is satisfactory, the more that
type is recommended. Moreover, note that the amount of representation in this
setting is independent of the popularities $p_{1},\cdots,p_{m}.$

This paradox is illustrated in grocery stores, where more space is devoted to
ice cream than milk, despite milk being much more popular than ice cream.
Here, $p_{1}$ (the popularity of milk) is higher than $p_{2}$ (the popularity
of ice cream). However, $q_{1}$ (the likelihood a given milk product satisfies
a shopper looking for milk) is also higher than $q_{2}$ (the likelihood a
given ice cream product satisfies a shopper looking for ice cream), since
people tend to have more specific tastes for ice cream. Thus, since $q_{2}$ is
smaller than $q_{1}$ and the grocery store should “recommend” many more ice
creams than milks, explaining why more space is devoted to ice cream.
Intuitively, while more shoppers want milk, these consumers can be satisfied
with a small selection of milk; thus, it is more beneficial to devote more
space to ice cream, for which shoppers have more specific tastes.

##  4 Sketch of Proofs

We now sketch the proof of Theorem 1(ii). (The general strategy applies to the
rest of Theorem 1, as well as Theorem 2 and Theorem 3.) First, recall the
general setup in Theorem 1, where the conditional item values $X_{i}^{(t)}$
are drawn i.i.d. from a shared distribution $\mathcal{D}$. In other words, a
user prefers type $t\in[m]$ with probability $p_{t}$ such that the user
prefers exactly one type of item, and conditioned on the user preferring type
$t$, the value of an item of that type is drawn i.i.d. from $\mathcal{D}$. We
are interested in analyzing, depending on $\mathcal{D}$, the composition of
$S_{n,k}$, the set of $n$ items maximizing the expected sum of the $k$ highest
value items in the set. If $S_{n,k}$ contains $a_{t}^{(n)}$ items of type $t$,
we need to analyze

$\lim_{n\rightarrow\infty}r_{t}(S_{n,k})=\lim_{n\rightarrow\infty}\frac{a_{t}^{(n)}}{n}.$
(10)

We first provide an expression for the expected sum of the $k$ highest value
items in a set $S$ with $a_{t}$ items of type $t$. The following definition
will be useful.

######  Definition 3.

Define $\mu_{\mathcal{D}}(i,a)$ to be the expected value of the $i$-th order
statistic222The $i$-th order statistic of $n$ random variables is the $i$-th
smallest of the $n$ realized values. of $a$ random variables drawn i.i.d. from
$\mathcal{D}$. (Thus, $\mu_{\mathcal{D}}(1,a)$ is the expected minimum of $a$
i.i.d. draws from $\mathcal{D}$ and $\mu_{\mathcal{D}}(a,a)$ is the expected
maximum.)

Then conditioned on the user preferring type $t$, the expected sum of the $k$
highest value of items in $S$ is equal to
$h(a_{t}):=\sum_{i=1}^{\min\\{k,a_{t}\\}}\mu_{\mathcal{D}}(a_{t}-i+1,a_{t}),$
which follows from the linearity of expectation. Therefore, the expected sum
of the $k$ highest value items in $S$ is $\sum_{t=1}^{m}p_{t}h(a_{t})$. Define
$A_{n}$ to be the set of tuples of non-negative integers whose entries sum to
$n$. Then
$(a_{1}^{(n)},a_{2}^{(n)},\cdots,a_{m}^{(n)})=\operatorname*{arg\,max}_{(a_{1},\cdots,a_{m})\in
A_{n}}\sum_{t=1}^{m}p_{t}h(a_{t}).$

We can then determine the limit in (10) given asymptotic information about
$h$. In Lemma D.1 in the appendix, we develop general technical machinery for
this task. Below, we state Lemma D.1(ii), which can be used to prove Theorem
1(ii).

######  Lemma D.1(ii).

If $h$ is monotonically increasing and there exist constants $A,B>0$ and
$\sigma<0$ such that $\lim_{a\rightarrow\infty}\frac{A-h(a)}{Ba^{\sigma}}=1,$
then
$\lim_{n\rightarrow\infty}\frac{a_{t}^{(n)}}{n}=\frac{p_{t}^{\frac{1}{1-\sigma}}}{\sum_{i=1}^{m}p_{i}^{\frac{1}{1-\sigma}}}.$

Then, considering $\mathcal{D}$ as in Theorem 1(ii), we can prove the
necessary asymptotic result about $h$:

######  Lemma 4.1.

If $\mathcal{D}$ has support bounded from above by $M$ with pdf
$f_{\mathcal{D}}$ such that $\lim_{x\rightarrow
M}\frac{f_{\mathcal{D}}(x)}{(M-x)^{\beta-1}}=c$ for some $\beta,c>0$, then
$\lim_{a\rightarrow\infty}\frac{Mk-h(a)}{Ba^{-\frac{1}{\beta}}}=1.$

Combining Lemma 4.1 with Lemma D.1(ii), with $\sigma=-\frac{1}{\beta}$, we
show that for $\mathcal{D}$ as in Theorem 1(ii),

$\lim_{n\rightarrow\infty}\frac{a_{t}^{(n)}}{n}=\frac{p_{t}^{\frac{\beta}{\beta+1}}}{\sum_{i=1}^{m}p_{i}^{\frac{\beta}{\beta+1}}}.$
(11)

##  5 Conclusion

We introduce and analyze a stylized model that reconciles the apparent
accuracy-diversity trade-off in recommendations. We characterize the diversity
of optimal sets both when “optimality” captures and does not capture user
consumption constraints. Broadly speaking, we show that the former naturally
induces diversity while the latter results in homogeneity. Therefore, the
apparent accuracy-diversity trade-off is partially due to traditional accuracy
metrics not accounting for consumption constraints.

##### Limitations and future work.

A particular strength of our model is that we were able to derive precise and
interpretable characterizations of diversity in many settings. One limitation
of our work is that many of our results are asymptotic (i.e.,
$n\rightarrow\infty$). We expect that it is possible to obtain further results
in our model for finite $n$. We gave Proposition 2 as one such example, and
outline additional possible directions in Appendix B.

The purposefully stylized nature of our model—in which users prefer only one
type of item and items fall under only one type—allows for a particularly
interpretable evaluation of diversity where we compare the representation of
each type in comparison to the likelihood that the user prefers that type.
This simple model is expressive enough to admit a wide range of results.
Still, it would be interesting to generalize our findings in more complex
models of users and items. In Appendix C, we discuss these possibilities
further, providing some basic results both when users can prefer multiple
types of items and when users and items are represented by embeddings.

Finally, there are possible model characteristics beyond consumption
constraints that implicitly reward diversity. As discussed in Section 1.3,
diversity in our model is a consequence of diminishing returns when
recommending additional items of a type. Diminishing returns may arise from
other assumptions, such as decaying user attention (e.g., [18]). We point
those interested in considering these alternate assumptions to Lemma D.1 in
the appendix, in which we abstract the technical relationship between
diminishing returns and diversity.

##### Broader impacts.

Recommender systems have broad societal consequences, particularly in high-
stakes settings like employment. Our work does not model many additional
reasons for diversity in these settings, including those based on fairness and
equity. We emphasize again that our results are intended to convey minimal
assumptions that induce diversity and illustrate the tendency of certain
objectives to produce homogeneous recommendations. Designers of recommender
systems, and researchers in the area, should take a broader view when making
decisions regarding diversity.

## References

  * [1] Matevž Kunaver and Tomaž Požrl.  Diversity in recommender systems–a survey.  Knowledge-based systems, 123:154–162, 2017.
  * [2] Gediminas Adomavicius and YoungOk Kwon.  Improving aggregate recommendation diversity using ranking-based techniques.  IEEE Transactions on Knowledge and Data Engineering, 24:896–911, 2012.
  * [3] Shaina Raza and Chen Ding.  Deep neural network to tradeoff between accuracy and diversity in a news recommender system.  2021 IEEE International Conference on Big Data (Big Data), pages 5246–5256, 2021.
  * [4] Elvin Isufi, Matteo Pocchiari, and Alan Hanjalic.  Accuracy-diversity trade-off in recommender systems via graph convolutions.  Inf. Process. Manag., 58:102459, 2021.
  * [5] Georgios Alexandridis, Georgios Siolas, and Andreas Stafylopatis.  Accuracy versus novelty and diversity in recommender systems: A nonuniform random walk approach.  In Recommendation and Search in Social Networks, 2015.
  * [6] Zhipeng Hou and Jing Liu.  A two-phase evolutionary algorithm for solving the accuracy-diversity dilemma in recommendation.  2020 IEEE Congress on Evolutionary Computation (CEC), pages 1–8, 2020.
  * [7] Bushra Alhijawi, Salam Fraihat, and Arafat A. Awajan.  Multi-factor ranking method for trading-off accuracy, diversity, novelty, and coverage of recommender systems.  International Journal of Information Technology, 15:1427 – 1433, 2023.
  * [8] Bibek Paudel, Thilo Haas, and Abraham Bernstein.  Fewer flops at the top: Accuracy, diversity, and regularization in two-class collaborative filtering.  Proceedings of the Eleventh ACM Conference on Recommender Systems, 2017.
  * [9] Xiaoyun He.  Does utilizing online social relations improve the diversity of personalized recommendations?  Int. J. Strateg. Decis. Sci., 13:1–15, 2022.
  * [10] Ignacio Fernández-Tobías, Paolo Tomeo, Iván Cantador, T. D. Noia, and Eugenio Di Sciascio.  Accuracy and diversity in cross-domain recommendations for cold-start users with positive-only feedback.  Proceedings of the 10th ACM Conference on Recommender Systems, 2016\.
  * [11] Anupriya Gogna and Angshul Majumdar.  Balancing accuracy and diversity in recommendations using matrix completion framework.  Knowl. Based Syst., 125:83–95, 2017.
  * [12] Maurizio Ferrari Dacrema.  Demonstrating the equivalence of list based and aggregate metrics to measure the diversity of recommendations (student abstract).  Proceedings of the AAAI Conference on Artificial Intelligence, 2021\.
  * [13] Jianguo Liu, Kerui Shi, and Qiang Guo.  Solving the accuracy-diversity dilemma via directed random walks.  Physical review. E, Statistical, nonlinear, and soft matter physics, 85 1 Pt 2:016118, 2012.
  * [14] Farzad Eskandanian and Bamshad Mobasher.  Using stable matching to optimize the balance between accuracy and diversity in recommendation.  Proceedings of the 28th ACM Conference on User Modeling, Adaptation and Personalization, 2020.
  * [15] Shengqi Wu, Huaizhen Kou, Chao Lv, Wanli Huang, Lianyong Qi, and Hongya Wang.  Service recommendation with high accuracy and diversity.  Wirel. Commun. Mob. Comput., 2020:8822992:1–8822992:10, 2020.
  * [16] Emanuel Lacić, Dominik Kowald, Markus Reiter-Haas, Valentin Slawicek, and E. Lex.  Beyond accuracy optimization: On the value of item embeddings for student job recommendations.  ArXiv, abs/1711.07762, 2017.
  * [17] Amin Javari and Mahdi Jalili.  A probabilistic model to resolve diversity–accuracy challenge of recommendation systems.  Knowledge and Information Systems, 44:609–627, 2015.
  * [18] Jon M. Kleinberg, Emily Ryu, and Éva Tardos.  Calibrated recommendations for users with decaying attention.  ArXiv, abs/2302.03239, 2023.
  * [19] Sinan Seymen, Himan Abdollahpouri, and Edward C. Malthouse.  A constrained optimization approach for calibrated recommendations.  Proceedings of the 15th ACM Conference on Recommender Systems, 2021\.
  * [20] Himan Abdollahpouri, Zahra Nazari, Alex Gain, Clay Gibson, Maria Dimakopoulou, J. Anderton, Benjamin Carterette, Mounia Lalmas, and Tony Jebara.  Calibrated recommendations as a minimum-cost flow problem.  Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, 2023.
  * [21] Mi Zhang and Neil J. Hurley.  Avoiding monotony: improving the diversity of recommendation lists.  In ACM Conference on Recommender Systems, 2008.
  * [22] Azin Ashkan, Branislav Kveton, Shlomo Berkovsky, and Zheng Wen.  Optimal greedy diversity for recommendation.  In International Joint Conference on Artificial Intelligence, 2015\.
  * [23] Tao Zhou, Zoltan Kuscsik, Jianguo Liu, Matus Medo, Joseph R. Wakeling, and Yi-Cheng Zhang.  Solving the apparent diversity-accuracy dilemma of recommender systems.  Proceedings of the National Academy of Sciences, 107:4511 – 4515, 2008.
  * [24] Ivan Medvedev, Taylor Gordong, and Haotian Wu.  Powered by ai: Instagram’s explore recommender system.  2019\.
  * [25] David Goldberg.  Diversity in search.  2014\.
  * [26] Ashton Anderson, Lucas Maystre, Ian Anderson, Rishabh Mehrotra, and Mounia Lalmas.  Algorithmic effects on the diversity of consumption on spotify.  In Proceedings of The Web Conference 2020, WWW ’20, page 2155–2165, New York, NY, USA, 2020. Association for Computing Machinery.
  * [27] João Sá, Vanessa Queiroz Marinho, Ana Rita Magalhães, Tiago Lacerda, and Diogo Gonçalves.  Diversity vs relevance: A practical multi-objective study in luxury fashion recommendations.  Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2022.
  * [28] Jae kyeong Kim, Il Young Choi, and Qinglong Li.  Customer satisfaction of recommender system: Examining accuracy and diversity in several types of recommendation approaches.  Sustainability, 13:6165, 2021.
  * [29] Sung-Hyuk Park and Sang Pil Han.  From accuracy to diversity in product recommendations: Relationship between diversity and customer retention.  International Journal of Electronic Commerce, 18:51 – 72, 2013\.
  * [30] Harald Steck.  Calibrated recommendations.  In Proceedings of the 12th ACM conference on recommender systems, pages 154–162, 2018.
  * [31] Mo Ghorbanzadeh, Ahmed Abdel-Hadi, and Thomas Charles Clancy.  A utility proportional fairness radio resource block allocation in cellular networks.  2015 International Conference on Computing, Networking and Communications (ICNC), pages 499–504, 2014.
  * [32] David Easley and Jon Kleinberg.  Networks, crowds, and markets: Reasoning about a highly connected world.  Cambridge university press, 2010.
  * [33] Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong.  Diversifying search results.  In Proceedings of the Second ACM International Conference on Web Search and Data Mining, WSDM ’09, page 5–14, New York, NY, USA, 2009. Association for Computing Machinery.
  * [34] Filip Radlinski, Robert D. Kleinberg, and Thorsten Joachims.  Learning diverse rankings with multi-armed bandits.  In International Conference on Machine Learning, 2008.
  * [35] Javier Parapar and Filip Radlinski.  Towards unified metrics for accuracy and diversity for recommender systems.  Proceedings of the 15th ACM Conference on Recommender Systems, 2021\.
  * [36] Scott Page.  The Difference.  Princeton University Press, 2008.
  * [37] Lu Hong and Scott E Page.  Groups of diverse problem solvers can outperform groups of high-ability problem solvers.  Proceedings of the National Academy of Sciences, 101(46):16385–16389, 2004.
  * [38] Jon Kleinberg and Maithra Raghu.  Team performance with test scores.  ACM Transactions on Economics and Computation (TEAC), 6(3-4):1–26, 2018.
  * [39] Jon Kleinberg and Manish Raghavan.  Selection problems in the presence of implicit bias.  arXiv preprint arXiv:1801.03533, 2018.
  * [40] Wenshuo Guo, Karl Krauth, Michael Jordan, and Nikhil Garg.  The stereotyping problem in collaboratively filtered recommender systems.  In Equity and Access in Algorithms, Mechanisms, and Optimization, pages 1–10. 2021.
  * [41] A Gürhan Kök and Marshall L Fisher.  Demand estimation and assortment optimization under substitution: Methodology and application.  Operations Research, 55(6):1001–1021, 2007.
  * [42] Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys.  Dynamic assortment optimization with a multinomial logit choice model and capacity constraint.  Operations research, 58(6):1666–1680, 2010.
  * [43] James Mario Davis, Guillermo Gallego, and Huseyin Topaloglu.  Assortment optimization under variants of the nested logit model.  Oper. Res., 62:250–273, 2014.
  * [44] Srikanth Jagabathula.  Assortment optimization under general choice.  Available at SSRN 2512831, 2014.
  * [45] Paat Rusmevichientong, David Shmoys, Chaoxu Tong, and Huseyin Topaloglu.  Assortment optimization under the multinomial logit model with random choice parameters.  Production and Operations Management, 23(11):2023–2039, 2014.
  * [46] Guillermo Gallego and Huseyin Topaloglu.  Constrained assortment optimization for the nested logit model.  Management Science, 60(10):2583–2601, 2014.
  * [47] Dimitris Bertsimas and Velibor V Mišic.  Data-driven assortment optimization.  Management Science, 1:1–35, 2015.
  * [48] Omar El Housni, Omar Mouchtaki, Guillermo Gallego, Vineet Goyal, Salal Humair, Sangjo Kim, Ali Sadighian, and Jingchen Wu.  Joint assortment and inventory planning for heavy tailed demand.  Columbia Business School Research Paper Forthcoming, 2021.
  * [49] Qinyi Chen, Negin Golrezaei, Fransisca Susan, and Edy Baskoro.  Fair assortment planning.  arXiv preprint arXiv:2208.07341, 2022.
  * [50] Omar El Housni and Huseyin Topaloglu.  Joint assortment optimization and customization under a mixture of multinomial logit models: On the value of personalized assortments.  Operations Research, 2022.
  * [51] Jaime Carbonell and Jade Goldstein.  The use of mmr, diversity-based reranking for reordering documents and producing summaries.  In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pages 335–336, 1998.
  * [52] Kevin Gimpel, Dhruv Batra, Chris Dyer, and Gregory Shakhnarovich.  A systematic exploration of diversity in machine translation.  In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1100–1111, 2013.
  * [53] William Brown and Arpit Agarwal.  Diversified recommendations for agents with adaptive preferences.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [54] Gourab K Patro, Lorenzo Porcaro, Laura Mitchell, Qiuyue Zhang, Meike Zehlike, and Nikhil Garg.  Fair ranking: a critical review, challenges, and future directions.  In 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1929–1942, 2022.
  * [55] Meike Zehlike, Ke Yang, and Julia Stoyanovich.  Fairness in ranking: A survey.  arXiv preprint arXiv:2103.14000, 2021.
  * [56] Kit T Rodolfa, Hemank Lamba, and Rayid Ghani.  Empirical observation of negligible fairness–accuracy trade-offs in machine learning for public policy.  Nature Machine Intelligence, 3(10):896–904, 2021.

##  Appendix A Additional related work

Our work sits at the intersection of two broad sets of work. On the one hand
are arguments that diversity is key to achieving efficiency. On the other are
those that cast diversity as in conflict with efficiency or accuracy, but
perhaps that diversity should nevertheless be pursued as an axiomatic good.

Broadly, our work seeks to understand this tension by sharply characterizing
the amount of diversity in efficient solutions, as a function of key setting
characteristics: user utilities and consumption constraints, and uncertainty
in the item quality distribution. In particular, our results characterize in
what settings the intuition regarding diversity being efficient holds, and in
what settings they may be in conflict.

##### The (efficiency) benefits of diversity

The importance of diversity for efficiency is an old idea present across many
fields; [36] synthesizes the conceptual and empirical arguments in support of
this principle. [37] develop a model in which a randomly selected team of
problem solvers outperforms a team of the individually best-performing agents,
due to diversity in problem solving perspective ([38] show that, in some
settings, there exist tests under which selecting the best-performing agents
again becomes optimal). [39] show that constraints promoting diversity can
improve efficiency when they work to counteract a decision-maker’s biases.
[33] develop an algorithm to diversify search results, to minimize the risk of
user dissatisfaction. We are particularly influenced by the work of [30], who
presents the intuition that recommendations should be calibrated: “When a user
has watched, say, 70 romance movies and 30 action movies, then it is
reasonable to expect the personalized list of recommended movies to be
comprised of about 70% romance and 30% action movies as well.” [40] show that
collaborative filtering-based recommendations may not be able to effectively
show users such a diverse set of content, harming efficiency.

More broadly, researchers studying various combinatorial optimization problems
may find it obvious that homogeneous solutions can be sub-optimal; indeed, in
classical problems like maximum coverage, redundancy is undesirable.

Our work particularly is intimately connected to the large literature on
assortment optimization [41, 42, 43, 44, 45, 46, 47, 48, 49, 50]. That
literature also considers consumption-constrained consumer item selections
based on an intermediary’s recommendations (e.g., that customers picks one
item according to a multinomial choice model). The literature primarily
devises approximation algorithms to find the optimal recommendation
(“assortment”) as a function of the consumer’s choice model, platform
objective, and the item distribution. In other words, an implicit premise of
this literature is that the naive approach of presenting the items with
highest individual expected values is sub-optimal, i.e., that optimal
assortments are not completely ‘homogeneous.’ On the other hand, optimal
assortments are not necessarily diverse; roughly speaking, the results of [50]
imply that a standard assortment approach (Mixed MNL) might produce solutions
that are not “diverse” enough to satisfy multiple customer types, and so there
is benefit to personalize to each type.333We thank the authors for
highlighting this connection to us.444Furthermore, as [49] recently
characterize, standard assortment optimization approaches may be “unfair” to
items in other ways. Our work contributes to this literature by (a) examining
the implicit premise that optimal assortments are not homogeneous (i.e., when
is the naive555Note that naive is much simpler than the greedy approach
studied in the literature, which picks items iteratively potentially as a
function of previous items picked. approach sufficient?); and (b) showing the
characteristics under which optimal assortments are not diverse.

##### Diversity and fairness as a contrast to efficiency and accuracy

On the other hand, many works start with the premise that—although diversity
may conflict with efficiency or accuracy—it is an axiomatic good that should
be pursued. For example, diversity is often considered to be inherently
desirable from a fairness perspective and user satisfaction perspective. As a
result, there is a wide body of work devoted to optimizing for various metrics
of diversity. A common approach (taken, for example, in [51] and [52]) is to
consider an objective function that balances a weighted measure of “accuracy”
or “relevance” with a measure of diversity. More recently, [53] consider set
recommendation for an agent with adaptive preferences, to ensure that
consumption over time is diverse. Numerous metrics for diversity have been
proposed—we refer the reader to [1] for a survey. Similarly, the fair ranking
and recommendation literature (see [54] and [55] for recent surveys) considers
metrics and methods for fairness in such problems. On the other hand,
empirical work has demonstrated that such tradeoffs may be small in practice
[56]. Such formulations imply that there is a tension between diversity and
measures of accuracy.

##  Appendix B Computational results for finite $n$ and general $k$

Figure 2: Optimal recommendations when there are two types (say, comedy movies
and action movies) and $X_{i}^{(t)}$ are i.i.d. Bernoulli random variables
with success probability $0.4$. For large $n$, optimal recommendations have
equal representation. Here, we plot the optimal representation of type 1
depending on the popularities $p_{1}$ and $p_{2}$ for small $n$. When
popularities are very skewed (e.g., the user prefers comedy with probability
0.9), then the recommendations are relatively homogeneous for small $n$.
Figure 3: Computational estimates for the diversity of optimal sets across a
range of beta and Pareto distributions. Here, dark blue corresponds to equal
representation ($\gamma=0$), grey corresponds to proportional representation
($\gamma=1$), and brown corresponds to homogeneous ($\gamma=\infty$). Observe
that tighter consumption constraints (smaller $k$) correspond to more
diversity. Notice in particular that when $\beta=1$ (corresponding to the
uniform distribution), the optimal solution is $\frac{1}{2}$-homogeneous for
all $k\leq cn$ for $c\approx\sqrt{0.3}/(\sqrt{0.3}+\sqrt{0.7})\approx 0.4,$
matching our theoretical result in Proposition 2.

One limitation of our general theoretical approach is that it does not
directly yield results for a fixed number of recommended items $n$ or for
intermediate values of $k$. In particular, a finer-grained theoretical
analysis requires closed-form solutions for the order statistics of general
distributions, which are often not available. We were able to overcome this in
Proposition 2, where we leveraged the simplicity of uniform order statistics.

Here, we take a computational approach to determine the optimal amount of
diversity for small $n$ and arbitrary $k.$ Figure 3 shows the results of a
computational approach to calculate the diversity of the optimal set for
finite $n$ and general $k$ for a spectrum of Beta and Pareto distributions.
For each particular distribution $\mathcal{D}$, we take
$n=30,m=2,p_{1}=0.7,p_{2}=0.3$ and find the optimal choice of $a_{1}$ and
$a_{2}$ by calculating

$\sum_{t=1}^{2}p_{t}\sum_{i=1}^{\min\\{a_{t},k\\}}\mu_{\mathcal{D}}(a_{t}-i+1,a_{t})$
(12)

for each possible pair $(a_{1},a_{2})$ summing to $30$. To do this, we
obtained empirical estimates of $\mu_{\mathcal{D}}(a-i+1,a)$ by
computationally sampling $10^{6}$ sets of $a$ points from $\mathcal{D}$. Our
computational results corroborate Theorem 1, showing how the optimal amount of
diversity can range from equal representation to homogeneity.

We also compute how diverse optimal solutions are in the case of a Bernoulli
distribution as $n$, the number of recommendations, varies. In Figure 2, we
consider the distribution $\operatorname{Ber}(0.4)$ and different pairs of
popularities $(p_{1},p_{2}).$ We find that as $n$ grows, optimal solutions
indeed approach having equal representation, corroborating Theorem 1(i). For
small $n$, optimal solutions tend to be more homogeneous—especially when the
popularities are heavily skewed. Indeed, this aligns with intuition: if a user
almost exclusively prefers romance, a recommender should still recommend
mostly romance movies (even if as the number of recommendations grows very
large, the recommendations should become more diverse according to Theorem
1(i)).

##  Appendix C Generalizations

In this section, we consider two directions in which our model can be
extended. First, we consider a model in which users can prefer multiple item
types at a time. Second, we consider a model in which users and items are both
represented by vector embeddings, a common paradigm in recommender systems.

###  C.1 Preference for multiple item types

In this section, we consider an extension of our model in which a user can
prefer multiple types of items. In particular, we focus on the case when $m=2$
and when the user prefers only type $1$ with probability $p_{1}$, only type
$2$ with probability $p_{2}$, and both types with probability $p_{12}.$ We
also assume that an item of type $i$ satisfies a user that prefers type $i$
independently with probability $q$. We consider when $k=1$, when the user can
only use one item. Then, we would like to minimize the probability of having
no satisfying items:

$p_{1}(1-q)^{a_{1}}+p_{2}(1-q)^{a_{2}}+p_{12}(1-q)^{n},$ (13)

where $a_{1}+a_{2}=n$. This is equivalent to minimizing

$p_{1}(1-q)^{a_{1}}+p_{2}(1-q)^{a_{2}},$ (14)

which is mathematically equivalent to Theorem 1(i). Thus, we have that as $n$
grows large, both item types are represented equally, irrespective of
$p_{1},p_{2},$ and $p_{12}$—in other words, allowing for the possibility that
the user prefers multiple item types does not change the result in this
setting.

The setup here can be naturally generalized to the case in which there are
more than two types, and where item values can come from distributions other
than Bernoulli. We leave these generalizations to future work.

###  C.2 User and item embeddings

In this section, we consider the setting in which users and items each
correspond to vector embeddings, and where the likelihood a user $u$ is
satisfied by an item $v$ is a function of their cosine distance. Suppose that
a user has preference $u$ drawn according to a probability measure $\mu$
supported on the unit $d-$dimensional sphere $S_{d}\subset\mathbb{R}^{d}.$
Further suppose that for a movie $v\in S_{d},$ the probability that a user is
not satisfied by the movie is $p(u,v)=q(\left\lVert u-v\right\rVert)$, a
function of the cosine distance between $u$ and $v$.

If the goal is to maximize the probability a user is satisfied by at least one
item, what is the optimal choice of items to recommend as the number of
recommendations we can make grows large? Here, we will show that items should
be chosen “uniformly” from $S_{d}$—a result that may seem surprising as it is
independent of the distribution of user preferences, and which can be viewed
as an analog of Theorem 1(i).

To make things precise and tractable, rather than consider the recommendation
of individual items, we will focus on the recommendation of a “distribution of
items.” This is analogous to making a continuous relaxation of the discrete
item recommendation problem. For a set of items $V=\\{v_{1},\cdots,v_{n}\\},$
the probability a user with preference drawn according to a probability
measure $\mu$ does not like any item in $V$ is

$\int_{S_{d}}\mu(u)\prod_{v\in V}p(u,v)\,du=\int_{S_{d}}\mu(u)\exp\sum_{v\in
V}\log p(u,v)\,du.$ (15)

Then for a density function $\alpha:S_{d}\rightarrow[0,\infty)$, we can
consider the expression

$\int_{S_{d}}\mu(u)\exp\left[n\int_{S_{d}}\alpha(v)\log
p(u,v)\,dv\right]\,du,$ (16)

which can be thought of splitting the $n$ item recommendations continuously
across $S_{d}$ according to the density function $\alpha$. We can think of
$\alpha$ as representing some “profile” of items to show. Going forward, we
consider optimal distributions rather than optimal discrete sets of items.

######  Proposition 4.

Consider a non-constant function $p(u,v):S_{d}\times S_{d}\rightarrow(0,1]$,
interpreted as the probability that item $v$ does not satisfy a user with
preference $u$, such that $p(u,v)=q(\left\lVert u-v\right\rVert)$ can be
expressed as a function of the cosine distance between $u$ and $v$. Then let
$\mu$ be a probability measure with support $S_{d}$, representing the
distribution of user preferences. Then for a probability measure $\alpha$ on
$S_{d}$, define

$\Gamma(\alpha)=\lim_{n\rightarrow\infty}\frac{1}{n}\log\int_{S_{d}}\mu(u)\exp\left[n\int_{S_{d}}\alpha(v)\log
p(u,v)\,dv\right]\,du.$ (17)

Then

$\Gamma(\pi)\in\inf_{\alpha}\Gamma(\alpha),$ (18)

where $\pi$ is the uniform probability measure over $S_{d}$.

###### Proof.

Let

$\rho(u;\alpha)=\int_{S_{d}}\alpha(v)\log p(u,v)\,dv.$ (19)

Then

$\Gamma(\alpha)=\lim_{n\rightarrow\infty}\frac{1}{n}\log\int_{S_{d}}e^{n\rho(u;\alpha)}\mu(u)\,du=\lim_{n\rightarrow\infty}\frac{1}{n}\log\int_{S_{d}}e^{n\rho(u;\alpha)}\,du=\sup_{u\in
S_{d}}\rho(u;\alpha),$ (20)

where the final equality follows from the Laplace principle from large
deviations theory. Now note that

$\displaystyle\int_{S_{d}}\rho(u;\alpha)\,du$
$\displaystyle=\int_{S_{d}}\int_{S_{d}}\alpha(v)\log p(u,v)\,dv\,du$ (21)
$\displaystyle=\int_{S_{d}}\alpha(v)\int_{S_{d}}\log p(u,v)\,du\,dv$ (22)
$\displaystyle=\int_{S_{d}}\alpha(v)C\,dv$ (23) $\displaystyle=C,$ (24)

where the second to last equality follows from the observation that

$\int_{S_{d}}\log p(u,v)\,du=\int_{S_{d}}\log q(\left\lVert
u-v\right\rVert)\,du=C$ (25)

for a constant $C$ independent of $v$. Therefore, there exists $u$ such that
$\rho(u;\alpha)\geq\frac{C}{m(A)},$ so $\sup_{u\in
A}\rho(u;\alpha)\geq\frac{C}{m(A)}.$ Now note that when $\pi$ is the uniform
probability measure over $A$, we have

$\rho(u;\pi)=\int_{S_{d}}\pi(v)\log p(u,v)\,dv=\frac{C}{m(A)}$ (26)

for all $u$, so $\sup_{u\in A}\rho(u;\pi)=\frac{C}{m(A)}.$ So
$\Gamma(\pi)=\inf_{\alpha}\Gamma(\alpha).$ ∎

##  Appendix D Proofs

In this section, we prove each of our results. In Section D.1, we prove a
technical lemma that plays a central role in the proofs of each part of
Theorem 1 and Theorem 2, which we prove in Section D.2 and Section D.3
respectively. In Section D.4, we prove another useful lemma—showing that
integer solutions are close to real solutions for a class of optimization
problems—which will be helpful in the proofs of Proposition 2 and Theorem 3,
which we give in Section D.5 and Section D.6 respectively.

###  D.1 A central lemma

Let $\mathbb{Z}_{\geq 0}$ denote the set of non-negative integers and
$A_{n}\subset\mathbb{Z}_{\geq 0}^{m}$ denote the set of $m$-tuples whose
elements sum to $n$. We will say that a function $h:\mathbb{Z}_{\geq
0}\rightarrow\mathbb{R}$ is strictly concave if $h(a+1)-h(a)<h(a)-h(a-1)$ for
all $a$.

######  Lemma D.1.

Consider an integer $m$ and $p_{1},p_{2},\cdots,p_{m}\geq 0$. Let
$h:\mathbb{Z}_{\geq 0}\rightarrow\mathbb{R}$ be monotonically increasing. For
each positive integer $n$, choose $(a_{1}^{(n)},\cdots,a_{m}^{(n)})$ such that

$(a_{1}^{(n)},\cdots,a_{m}^{(n)})\in\operatorname*{arg\,max}_{(a_{1},\cdots,a_{m})\in
A_{n}}\sum_{t=1}^{m}p_{t}h(a_{t}),$ (27)

and define

$r_{t}^{(n)}:=\frac{a_{t}^{(n)}}{n}.$ (28)

Then the following statements hold.

  1. (i)

Suppose there exist constants $A,B>0$ and $\sigma<0$ such that

$\lim_{a\rightarrow\infty}\frac{\log(A-h(a))}{Ba^{\sigma}}=1.$ (29)

Then

$\lim_{n\rightarrow\infty}r_{t}^{(n)}=\frac{1}{m}.$ (30)

  2. (ii)

Suppose there exist constants $A,B>0$ and $\sigma<0$ such that

$\lim_{a\rightarrow\infty}\frac{A-h(a)}{Ba^{\sigma}}=1.$ (31)

Then

$\lim_{n\rightarrow\infty}r_{t}^{(n)}=\frac{p_{t}^{\frac{1}{1-\sigma}}}{\sum_{i=1}^{m}p_{i}^{\frac{1}{1-\sigma}}}.$
(32)

  3. (iii)

Suppose $h$ is strictly concave, and that there exist constants $B,C>0$ such
that

$\lim_{a\rightarrow\infty}h(a)-B\log a-C=0.$ (33)

Then

$\lim_{n\rightarrow\infty}r_{t}^{(n)}=p_{t}.$ (34)

  4. (iv)

Suppose $h$ is strictly concave, and that there exist constants $B>0$ and
$0<\sigma<1$ such that

$\lim_{a\rightarrow\infty}\frac{h(a)}{Ba^{\sigma}}=1.$ (35)

Then

$\lim_{n\rightarrow\infty}r_{t}^{(n)}=\frac{p_{t}^{\frac{1}{1-\sigma}}}{\sum_{i=1}^{m}p_{i}^{\frac{1}{1-\sigma}}}.$
(36)

We spend the remainder of the section proving Lemma D.1. A useful first step
is to show that in each of parts (i)-(iv), we have that

$\lim_{n\rightarrow\infty}a_{t}^{(n)}=\infty$ (37)

for each $t\in[m],$ allowing us to use the asymptotic assumptions in the
lemma’s statement.

Assume for the sake of contradiction that there exists $t\in[m]$ and an
integer $d$ such that for any integer $N$ there exists $n>N$ for which
$a_{t}^{(n)}<d.$ Since $h$ is strictly increasing and $d$ is finite, there
exists $\delta>0$ such that

$h(a+1)-h(a)>\delta$ (38)

for all $a<d.$ Also, there exists an integer $N^{\prime}$ such that for all
$a>N^{\prime}$,

$h(a)-h(a-1)<\delta\cdot\min_{i\in[m]}\frac{p_{t}}{p_{i}}.$ (39)

(39) holds in parts (i)-(ii) because $h$ is monotonically increasing and is
upper bounded by $A$, and in parts (iii)-(iv) because $h$ is strictly concave.

Now consider $N=N^{\prime}m$. Then there exists $n>N$ such that
$a_{t}^{(n)}<d.$ Since $\sum_{t=1}^{m}a_{t}^{(n)}=n>N^{\prime}m$, there exists
$t^{\prime}\in[m]$ such that $a_{t^{\prime}}^{(n)}>N^{\prime}.$ Thus,

$p_{t^{\prime}}h(a_{t^{\prime}}^{(n)})-p_{t^{\prime}}h(a_{t^{\prime}}^{(n)}-1)<p_{t}\delta<p_{t}h(a_{t}^{(n)}+1)-p_{t}h(a_{t}^{(n)}),$
(40)

which implies that the switch $a_{t}^{(n)}\rightarrow
a_{t}^{(n)}+1,a_{t^{\prime}}^{(n)}\rightarrow a_{t^{\prime}}^{(n)}-1$
increases

$\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)}),$ (41)

contradicting the optimality of $(a_{1}^{(n)},\cdots,a_{m}^{(n)}).$

With (37) in hand, we turn to the bulk of the proof. In each part, we would
like to show that

$\lim_{n\rightarrow\infty}(r_{1}^{(n)},\cdots,r_{m}^{(n)})=(\widehat{r}_{1},\cdots,\widehat{r}_{m})$
(42)

for some specified $(\widehat{r}_{1},\cdots,\widehat{r}_{m})$ depending on the
part. We assume for the sake of contradiction that
$\\{(r_{1}^{(n)},\cdots,r_{m}^{(n)})\\}_{n=1}^{\infty}$ does not converge to
$(\widehat{r}_{1},\cdots,\widehat{r}_{m}).$ If this is the case, then by the
Bolzano-Weierstrass theorem, since $[0,1]^{m}$ is compact, there is a
subsequence

$\\{(r_{1}^{(s_{i})},\cdots,r_{m}^{(s_{i})})\\}_{i=1}^{\infty}$ (43)

such that
$\lim_{i\rightarrow\infty}(r_{1}^{(s_{i})},\cdots,r_{m}^{(s_{i})})=(r_{1},\cdots,r_{m})$
for some $(r_{1},\cdots,r_{m})\neq(\widehat{r}_{1},\cdots,\widehat{r}_{m}).$
For notational ease, we will simply assume that

$\lim_{n\rightarrow\infty}(r_{1}^{(n)},\cdots,r_{m}^{(n)})=(r_{1},\cdots,r_{m})$
(44)

for some $(r_{1},\cdots,r_{m})\neq(\widehat{r}_{1},\cdots,\widehat{r}_{m})$.
The proof holds analogously when the subsequence
$\\{(r_{1}^{(s_{i})},\cdots,r_{m}^{(s_{i})})\\}_{i=1}^{\infty}$ differs from
$\\{(r_{1}^{(n)},\cdots,r_{m}^{(n)})\\}_{n=1}^{\infty}$.

Then consider any sequence
$\\{(\widehat{a}_{1}^{(n)},\cdots,\widehat{a}_{m}^{(n)})\\}_{n=1}^{\infty}$
such that

$\lim_{n\rightarrow\infty}\left(\frac{\widehat{a}_{1}^{(n)}}{n},\cdots,\frac{\widehat{a}_{m}^{(n)}}{n}\right)=(\widehat{r}_{1},\cdots,\widehat{r}_{m}).$
(45)

(Clearly, such a sequence exists.) In each part, we will show that for
sufficiently large $n$,

$\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)})<\sum_{t=1}^{m}p_{t}h(\widehat{a}_{t}^{(n)}),$
(46)

contradicting the optimality of $(a_{1}^{(n)},\cdots,a_{m}^{(n)}).$ To
complete the proof, we analyze each part separately:

  1. (i)

In this part, there exist constants $A,B>0$ and $\sigma<0$ such that

$\lim_{a\rightarrow\infty}\frac{\log(A-h(a))}{Ba^{\sigma}}=1.$ (47)

We set $\widehat{r}_{t}:=\frac{1}{m}$ for each $t\in[m].$ Observe that

$\displaystyle\lim_{a\rightarrow\infty}\frac{\log(A-h(a))}{Ba^{\sigma}}=1$
(48)

implies that for all $\epsilon>0$, there exists $c$ such that for all $a>c,$

$e^{(1-\epsilon)Ba^{\sigma}}\leq A-h(a)\leq e^{(1+\epsilon)Ba^{\sigma}}.$ (49)

Then observe that by taking sufficiently small $\epsilon,$ we have

$\displaystyle\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}(A-h(a_{t}^{(n)}))}{\sum_{t=1}^{m}p_{t}(A-h(\widehat{a}_{t}^{(n)}))}$
$\displaystyle\geq\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}\exp[(1-\epsilon)B(a_{t}^{(n)})^{\sigma})]}{\sum_{t=1}^{m}p_{t}\exp[(1+\epsilon)B(\widehat{a}_{t}^{(n)})^{\sigma})]}$
(50)
$\displaystyle=\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}\exp[(1-\epsilon)B(nr_{t})^{\sigma}]}{\exp[(1+\epsilon)B(n/m)^{\sigma}]}$
(51)
$\displaystyle=\lim_{n\rightarrow\infty}\sum_{t=1}^{m}p_{t}\exp[Bn^{\sigma}((1-\epsilon)r_{t}^{\sigma}-(1+\epsilon)(1/m)^{\sigma})]=\infty$
(52)

where the last limit holds for $\epsilon$ sufficiently small because
$r_{t}-\frac{1}{m}>0$ for some $t$.

It follows that for $n$ sufficiently large,
$\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)})<\sum_{t=1}^{m}p_{t}h(\widehat{a}_{t}^{(n)}),$
as desired.

  2. (ii)

In this part, there exist constants $A,B>0$ and $\sigma<0$ such that

$\lim_{a\rightarrow\infty}\frac{A-h(a)}{Ba^{\sigma}}=1.$ (53)

We set

$\widehat{r}_{t}:=\frac{p_{t}^{\frac{1}{1-\sigma}}}{\sum_{i=1}^{m}p_{i}^{\frac{1}{1-\sigma}}}$
(54)

for each $t\in[m].$ Then observe that

$\displaystyle\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}(A-h(a_{t}^{(n)}))}{\sum_{t=1}^{m}p_{t}(A-h(\widehat{a}_{t}^{(n)}))}$
(55) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}(A-h(a_{t}^{(n)}))}{\sum_{t=1}^{m}p_{t}(A-h(\widehat{a}_{t}^{(n)}))}\cdot\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}B(a_{t}^{(n)})^{\sigma}}{\sum_{t=1}^{m}p_{t}(A-h(a_{t}^{(n)}))}\cdot\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}(A-h(\widehat{a}_{t}^{(n)}))}{\sum_{t=1}^{m}p_{t}B(\widehat{a}_{t}^{(n)})^{\sigma}}$
(56) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}(A-h(a_{t}^{(n)}))}{\sum_{t=1}^{m}p_{t}(A-h(\widehat{a}_{t}^{(n)}))}\cdot\frac{\sum_{t=1}^{m}p_{t}B(a_{t}^{(n)})^{\sigma}}{\sum_{t=1}^{m}p_{t}(A-h(a_{t}^{(n)}))}\cdot\frac{\sum_{t=1}^{m}p_{t}(A-h(\widehat{a}_{t}^{(n)}))}{\sum_{t=1}^{m}p_{t}B(\widehat{a}_{t}^{(n)})^{\sigma}}$
(57) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}B(a_{t}^{(n)})^{\sigma}}{\sum_{t=1}^{m}p_{t}B(\widehat{a}_{t}^{(n)})^{\sigma}}$
(58) $\displaystyle=$
$\displaystyle\frac{\sum_{t=1}^{m}p_{t}r_{t}^{\sigma}}{\sum_{t=1}^{m}p_{t}\widehat{r}_{t}^{\sigma}}>1,$
(59)

where (56) follows from the latter two limits being equal to 1, (57) follows
from the product rule for limits, and (59) follows from the observation that
for $\sigma<0$

$\sum_{t=1}^{m}p_{t}x_{t}^{\sigma},$ (60)

subject to the constraint $\sum_{t=1}^{m}x_{t}=1$ for $x_{t}\geq 0$ has a
unique minimum at
$(x_{1},\cdots,x_{m})=(\widehat{r}_{1},\cdots,\widehat{r}_{m}).$ This is
direct, for example, by using Lagrange multipliers. (59) implies that

$\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)})}{\sum_{t=1}^{m}p_{t}h(\widehat{a}_{t}^{(n)})}<1.$
(61)

It follows that for $n$ sufficiently large,
$\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)})<\sum_{t=1}^{m}p_{t}h(\widehat{a}_{t}^{(n)}),$
as desired.

  3. (iii)

In this part, $h$ is strictly concave, and there exist constants $B,C>0$ such
that

$\lim_{a\rightarrow\infty}h(a)-B\log a-C=0.$ (62)

We set $\widehat{r}_{t}:=p_{t}$ for each $t\in[m].$ Then observe that

$\displaystyle\lim_{n\rightarrow\infty}\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)})-\sum_{t=1}^{m}p_{t}h(\widehat{a}_{t}^{(n)})$
$\displaystyle=\lim_{n\rightarrow\infty}\sum_{t=1}^{m}p_{t}B\log
a_{t}^{(n)}-\sum_{t=1}^{m}p_{t}B\log\widehat{a}_{t}^{(n)}$ (63)
$\displaystyle=B\log n+B\sum_{t=1}^{m}p_{t}\log r_{t}-B\log
n-B\sum_{t=1}^{m}p_{t}\log\widehat{r}_{t}$ (64) $\displaystyle<0.$ (65)

The final inequality here follows from the observation that

$\sum_{t=1}^{m}p_{t}\log x_{t},$ (66)

subject to the constraint $\sum_{t=1}^{m}x_{t}=1$ for $x_{t}>0$ has a unique
minimum at $(x_{1},\cdots,x_{m})=(\widehat{r}_{1},\cdots,\widehat{r}_{m}).$
This is direct, for example, by using Lagrange multipliers.

It follows that for $n$ sufficiently large,
$\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)})<\sum_{t=1}^{m}p_{t}h(\widehat{a}_{t}^{(n)}),$
as desired.

  4. (iv)

In this part, $h$ is strictly concave, and there exist constants $B>0$ and
$0<\sigma<1$ such that

$\lim_{a\rightarrow\infty}\frac{h(a)}{Ba^{\sigma}}=1.$ (67)

We set

$\widehat{r}_{t}:=\frac{p_{t}^{\frac{1}{1-\sigma}}}{\sum_{i=1}^{m}p_{i}^{\frac{1}{1-\sigma}}}$
(68)

for each $t\in[m].$ Then observe that

$\displaystyle\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)})}{\sum_{t=1}^{m}p_{t}h(\widehat{a}_{t}^{(n)})}=\lim_{n\rightarrow\infty}\frac{\sum_{t=1}^{m}p_{t}B(a_{t}^{(n)})^{\sigma}}{\sum_{t=1}^{m}p_{t}B(\widehat{a}_{t}^{(n)})^{\sigma}}=\frac{\sum_{t=1}^{m}p_{t}r_{t}^{\sigma}}{\sum_{t=1}^{m}p_{t}\widehat{r}_{t}^{\sigma}}<1.$
(69)

The first equality is a consequence of the asymptotic assumption on $h$ and
the product rule for limits (as in part (ii). The final inequality here
follows from the observation that for $\sigma>0$,

$\sum_{t=1}^{m}p_{t}x_{t}^{\sigma},$ (70)

subject to the constraint $\sum_{t=1}^{m}x_{t}=1$ for $x_{t}>0$ has a unique
maximum at $(x_{1},\cdots,x_{m})=(\widehat{r}_{1},\cdots,\widehat{r}_{m}).$
This is direct, for example, by using Lagrange multipliers.

It follows that for $n$ sufficiently large,
$\sum_{t=1}^{m}p_{t}h(a_{t}^{(n)})<\sum_{t=1}^{m}p_{t}h(\widehat{a}_{t}^{(n)}),$
as desired.

###  D.2 Proof of Theorem 1

We now turn to the proofs of Theorem 1(i)-(iv). In each of these parts, we
consider a set of recommendations with $a_{t}$ items of type $t$ for each
$t\in[m].$ Then observe that the expected total value of the $k$ highest value
recommended items is equal to

$\sum_{t=1}^{m}p_{t}h(a_{t}),$ (71)

for

$h:\mathbb{Z}_{\geq 0}\rightarrow\mathbb{R},\quad
h:a\mapsto\mathbb{E}\left[\operatorname{top}_{k}\\{X_{1},\cdots,X_{a}\overset{\mathrm{iid}}{\sim}\mathcal{D}\\}\right],$
(72)

where $\operatorname{top}_{k}$ evaluates the sum of the $k$ highest values in
a set. Intuitively, conditional on a user preferring type $t$, the top $k$
items are just the top $k$ items recommended of type $t$. The sum of their
values, conditioned on the user preferring type $t$, is simply the sum of the
$k$ highest values among $a$ random draws from $\mathcal{D}$. Clearly, $h$
here is monotonically increasing.

Then, with Lemma D.1 in hand, parts (i)-(iv) reduces to showing the following:

  1. (i)

If $\mathcal{D}$ is a finite discrete distribution, there exist constants
$A,B>0$ and $\sigma>0$ such that

$\lim_{a\rightarrow\infty}\frac{\log(A-h(a))}{Ba^{\sigma}}=1.$ (73)

  2. (ii)

If $\mathcal{D}$ has support bounded from above by $M$ with pdf
$f_{\mathcal{D}}$ satisfying

$\lim_{x\rightarrow M}\frac{f_{\mathcal{D}}(x)}{(M-x)^{\beta-1}}=c$ (74)

for some $\beta,c>0$, then there exist constants $A,B>0$ such that

$\lim_{a\rightarrow\infty}\frac{A-h(a)}{Ba^{-\frac{1}{\beta}}}=1.$ (75)

  3. (iii)

If $\mathcal{D}=\operatorname{Exp}(\lambda)$ for $\lambda>0,$ then $h$ is
strictly concave and there exists a constant $B>0$ such that

$\lim_{a\rightarrow\infty}\frac{h(a)}{B\log a}=1.$ (76)

  4. (iv)

If $\mathcal{D}=\operatorname{Pareto}(\alpha)$ for $\alpha>1$, then $h$ is
strictly concave and there exists a constant $B>0$ such that

$\lim_{a\rightarrow\infty}\frac{h(a)}{Ba^{\frac{1}{\alpha}}}=1.$ (77)

The following identity, mentioned in Section 4, will be useful for parts
(ii)-(iv).

######  Proposition 5.

For $X_{i}^{(t)}\overset{\mathrm{iid}}{\sim}\mathcal{D}$,

$h(a)=\sum_{i=1}^{\min\\{k,a\\}}\mu_{\mathcal{D}}(a-i+1,a).$ (78)

Recall that $\mu_{\mathcal{D}}(i,a)$ is the expected value of the $i$-th order
statistic of $a$ random variables drawn i.i.d. from $\mathcal{D}$.

###### Proof.

Let $Y_{k,n}$ be the $k$-th order statistic of $n$ random variables
distributed i.i.d. from $\mathcal{D}$. Then

$\operatorname{top}_{k}\\{X_{1}^{(t)},\cdots,X_{a}^{(t)}\\}=\sum_{i=1}^{\min\\{k,a\\}}Y_{a-i+1,a}.$
(79)

So, as desired,

$\mathbb{E}\left[\operatorname{top}_{k}\\{X_{1}^{(t)},\cdots,X_{a}^{(t)}\\}\right]=\sum_{i=1}^{\min\\{k,a\\}}\mathbb{E}\left[Y_{a-i+1,a}\right]=\sum_{i=1}^{\min\\{k,a\\}}\mu_{\mathcal{D}}(a-i+1,a),$
(80)

where the first equality follows from (79) and the linearity of expectation. ∎

##### Proof of Theorem 1(i).

Suppose $\mathcal{D}$ has support $\\{x_{1},\cdots,x_{r}\\}$ with
$x_{1}>\cdots>x_{r}$ such that for $X\sim\mathcal{D}$, $\Pr[X=x_{1}]=q.$ Now
consider a set of recommendations with $a_{t}$ items of type $t$ for each
$t\in[m].$ Then consider
$X_{1},\cdots,X_{a}\overset{\mathrm{iid}}{\sim}\mathcal{D}$. Let $E$ be the
event that at least $k$ of $X_{1},\cdots,X_{a}$ equal $x_{1}$. Then,

$\displaystyle h(a)$
$\displaystyle\geq\mathbb{E}[\operatorname{top}_{k}\\{X_{1},\cdots,X_{a}\\}|E]\cdot\Pr[E]$
(81)
$\displaystyle=x_{1}k\cdot\left(1-\sum_{j=0}^{k-1}\binom{a}{j}(1-q)^{a-j}q^{j}\right)$
(82) $\displaystyle\geq x_{1}k(1-a^{k}(1-q)^{a-k+1})$ (83)

for all $a>2.$ Now let $E^{\prime}$ be the event that at least one of
$X_{1},\cdots,X_{a}$ equals $x_{1}$. Then,

$\displaystyle h(a)$
$\displaystyle=\mathbb{E}[\operatorname{top}_{k}\\{X_{1},\cdots,X_{a}\\}|E^{\prime}]\cdot\Pr[E^{\prime}]+\mathbb{E}[\operatorname{top}_{k}\\{X_{1},\cdots,X_{a}\\}|\overline{E^{\prime}}]\cdot(1-\Pr[E^{\prime}])$
(84) $\displaystyle\leq x_{1}k(1-(1-q)^{a})+x_{2}k(1-q)^{a}$ (85)
$\displaystyle=x_{1}k(1-(1-\frac{x_{2}}{x_{1}})(1-q)^{a}).$ (86)

Now note that for $A=x_{1}k,$ we have that

$\displaystyle x_{1}k(1-\frac{x_{2}}{x_{1}})(1-q)^{a}$ $\displaystyle\leq
A-h(a)\leq x_{1}ka^{k}(1-q)^{a-k+1}$ (87)
$\displaystyle\log(x_{1}k(1-\frac{x_{2}}{x_{1}})(1-q)^{a})$
$\displaystyle\leq\log(A-h(a))\leq\log(x_{1}ka^{k}(1-q)^{a-k+1})$ (88)
$\displaystyle\log(x_{1}k)+\log(1-\frac{x_{2}}{x_{1}})+a\log(1-q)$
$\displaystyle\leq\log(A-h(a))\leq\log(x_{1}k)+k\log(a)+(a-k+1)\log(1-q).$
(89)

It follows that for $B=\log(1-q),$

$\lim_{a\rightarrow\infty}\frac{\log(A-h(a))}{Ba}=1,$ (90)

as desired. The result follows from Lemma D.1(i).

##### Proof of Theorem 1(ii).

First recall from Proposition 5 that

$h(a)=\sum_{i=1}^{\min\\{k,a\\}}\mu_{\mathcal{D}}(a-i+1,a).$ (91)

We will show that

$\lim_{a\rightarrow\infty}\frac{Mk-h(a)}{Ba^{-\frac{1}{\beta}}}=1$ (92)

for a constant $B>0.$ Theorem 1(ii) then follows immediately by applying Lemma
D.1(ii) with $\sigma=-\frac{1}{\beta}$.

Consider a probability distribution $\mathcal{D}^{\prime}$ with pdf
$g_{X}(x)=f_{X}(M-x)$ and cdf $G_{X}(x).$ Then

$\mu_{\mathcal{D}}(a-i+1,a)=M-\mu_{\mathcal{D}^{\prime}}(i,a),$ (93)

which implies that

$Mk-\sum_{i=1}^{k}\mu_{\mathcal{D}}(a-i+1,a)=\sum_{i=1}^{k}\mu_{\mathcal{D}^{\prime}}(i,a)$
(94)

Since

$\mu_{\mathcal{D}^{\prime}}(i,a)=\sum_{j=0}^{i-1}\int_{0}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx,$
(95)

it remains to show that for all fixed $j$,

$\lim_{a\rightarrow\infty}\frac{\int_{0}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx}{a^{-\frac{1}{\beta}}}=B$
(96)

for some constant $B$ (that can vary depending on $j$). Verifying (96)
comprises the bulk of the technical work of the proof, and we isolate it in
the following lemma.

######  Lemma D.2.

For $\beta>0$,

$\int_{0}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx\propto
a^{-\frac{1}{\beta}}.$ (97)

###### Proof.

We have that

$\lim_{x\rightarrow 0^{+}}\frac{g_{X}(x)}{cx^{\beta-1}}=\lim_{x\rightarrow
M^{-}}\frac{f_{X}(x)}{c(M-x)^{\beta-1}}=1$ (98)

for a positive constant $c$. So for all $\epsilon>0$ there exists $\delta>0$
such that

$(1-\epsilon)cx^{\beta-1}\leq g_{X}(x)\leq(1+\epsilon)cx^{\beta-1}$ (99)

for all $x<\delta.$ Now note that $g_{X}(x)\leq(1+\epsilon)cx^{\beta-1}$
implies that

$G_{X}(x)=\int_{0}^{x}g_{X}(u)\,du\leq(1+\epsilon)\int_{0}^{x}cu^{\beta-1}\,du=(1+\epsilon)\frac{c}{\beta}x^{\beta}.$
(100)

Likewise, $g_{X}(x)\geq(1-\epsilon)cx^{\beta-1}$ implies that

$G_{X}(x)=\int_{0}^{x}g_{X}(u)\,du\geq(1-\epsilon)\int_{0}^{x}cu^{\beta-1}\,du=(1-\epsilon)\frac{c}{\beta}x^{\beta}.$
(101)

Now write

$\displaystyle
a^{\frac{1}{\beta}}\int_{0}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx$
(102)
$\displaystyle=a^{\frac{1}{\beta}}\int_{0}^{\delta}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx+a^{\frac{1}{\beta}}\int_{\delta}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx.$
(103)

We will analyze these two integral separately. It will turn out that the
second integral vanishes as $a$ grows. ∎

##### The first integral.

We have that

$\displaystyle
a^{\frac{1}{\beta}}\int_{0}^{\delta}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx$
(104) $\displaystyle\leq
a^{\frac{1}{\beta}}\int_{0}^{\delta}\binom{a}{j}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}(1-(1-\epsilon)\frac{c}{\beta}x^{\beta})^{a-j}\,dx$ (105)
$\displaystyle=\int_{0}^{\delta
a^{\frac{1}{\beta}}}\binom{a}{j}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}\left(\frac{x}{a^{\frac{1}{\beta}}}\right)^{\beta
j}\left(1-(1-\epsilon)\frac{c}{\beta}\left(\frac{x}{a^{\frac{1}{\beta}}}\right)^{\beta}\right)^{a-j}\,dx$
(106) $\displaystyle=\int_{0}^{\delta
a^{\frac{1}{\beta}}}\binom{a}{j}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}\frac{x^{\beta}j}{a^{j}}\left(1-(1-\epsilon)\frac{c}{\beta}\frac{x}{a}\right)^{a-j}\,dx.$
(107)

Then

$\int_{0}^{\delta
a^{\frac{1}{\beta}}}\binom{a}{j}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}\frac{x^{\beta}j}{a^{j}}\left(1-(1-\epsilon)\frac{c}{\beta}\frac{x}{a}\right)^{a-j}\,dx=\int_{0}^{\infty}\phi_{a}(x)\,dx,$
(108)

where

$\phi_{a}(x):=\begin{cases}\binom{a}{j}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}\frac{x^{\beta}j}{a^{j}}\left(1-(1-\epsilon)\frac{c}{\beta}\frac{x}{a}\right)^{a-j}\,dx&\quad\text{for
}0\leq x\leq\delta a^{\frac{1}{\beta}}\\\ 0&\quad\text{for }x>\delta
a^{\frac{1}{\beta}}.\end{cases}$ (109)

We have that

$\lim_{a\rightarrow\infty}\phi_{a}(x)=\frac{1}{j!}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-(1-\epsilon)\frac{c}{\beta}x^{\beta}}$ (110)

and

$\phi_{a}(x)\leq\frac{1}{j!}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-(1-\epsilon)\frac{c}{\beta}x^{\beta}}(1-(1-\epsilon)\frac{c}{\beta}\epsilon^{\beta}))^{-j}=C(j,\epsilon)x^{\beta
j}e^{-(1-\epsilon)\frac{c}{\beta}x^{\beta}}$ (111)

for a constant $C(j,\epsilon)$ independent of $a.$ Now note that
$\int_{0}^{\infty}x^{\beta
j}e^{-(1-\epsilon)\frac{c}{\beta}x^{\beta}}<\infty.$ It follows from the
dominated convergence theorem that

$\lim_{a\rightarrow\infty}\int_{0}^{\infty}\phi_{a}(x)\,dx=\int_{0}^{\infty}\lim_{a\rightarrow\infty}\phi_{a}(x)\,dx=\int_{0}^{\infty}\frac{1}{j!}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-(1-\epsilon)\frac{c}{\beta}x^{\beta}}\,dx<\infty.$ (112)

Therefore, for $a$ sufficiently large,

$\int_{0}^{\delta}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx\leq
a^{-\frac{1}{\beta}}(1+\epsilon)\int_{0}^{\infty}\frac{1}{j!}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-(1-\epsilon)\frac{c}{\beta}x^{\beta}}\,dx.$ (113)

Analogously, we can show that for $a$ sufficiently large,

$\int_{0}^{\delta}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx\geq
a^{-\frac{1}{\beta}}(1-\epsilon)\int_{0}^{\infty}\frac{1}{j!}(1-\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-(1+\epsilon)\frac{c}{\beta}x^{\beta}}\,dx.$ (114)

Now observe that

$\displaystyle\lim_{\epsilon\rightarrow
0^{+}}(1+\epsilon)\int_{0}^{\infty}\frac{1}{j!}(1+\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-(1-\epsilon)\frac{c}{\beta}x^{\beta}}\,dx$ (115)
$\displaystyle=\int_{0}^{\infty}\frac{1}{j!}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-\frac{c}{\beta}x^{\beta}}\,dx$ (116)
$\displaystyle=\lim_{\epsilon\rightarrow
0^{+}}(1-\epsilon)\int_{0}^{\infty}\frac{1}{j!}(1-\epsilon)^{j}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-(1+\epsilon)\frac{c}{\beta}x^{\beta}}\,dx,$ (117)

where we once again apply the dominated convergence theorem. It follows that

$\lim_{a\rightarrow\infty}\frac{\int_{0}^{\delta}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx}{a^{-\frac{1}{\beta}}}=\int_{0}^{\infty}\frac{1}{j!}\left(\frac{c}{\beta}\right)^{j}x^{\beta
j}e^{-\frac{c}{\beta}x^{\beta}}\,dx.$ (118)

##### The second integral.

We now analyze

$a^{\frac{1}{\beta}}\int_{\delta}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx.$
(119)

Observe that

$\displaystyle
a^{\frac{1}{\beta}}\int_{\delta}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx$
$\displaystyle<a^{\frac{1}{\beta}}\binom{a}{j}\int_{\delta}^{\infty}(1-G_{X}(x))^{a-j}\,dx$
(120)
$\displaystyle<a^{\frac{1}{\beta}}\binom{a}{j}(1-G_{X}(\delta))^{a-j}\int_{\delta}^{\infty}1-G_{X}(x)\,dx$
(121)
$\displaystyle<a^{\frac{1}{\beta}}\binom{a}{j}(1-G_{X}(\delta))^{a-j}\mathbb{E}[X].$
(122)

Thus,

$\lim_{a\rightarrow\infty}\frac{\int_{\delta}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx}{a^{\frac{1}{\beta}}}=0.$
(123)

Combining (118) and (123) gives us that

$\int_{0}^{\infty}\binom{a}{j}G_{X}(x)^{j}(1-G_{X}(x))^{a-j}\,dx\propto
a^{-\frac{1}{\beta}},$ (124)

as desired.

##### Proof of Theorem 1(iii).

Recall again that

$h(a):=\sum_{i=1}^{\min\\{k,a\\}}\mu_{\mathcal{D}}(a-i+1,a).$ (125)

We show that $h$ is strictly concave and

$\lim_{a\rightarrow\infty}h(a)-B\log a-C=0$ (126)

for constants $B,C>0$. Both of these facts follow directly from the lemma
below. Theorem 1(iii) then follows immediately by applying Lemma D.1(iii).

######  Lemma D.3.

For $\mathcal{D}$ an exponential distribution with rate parameter $\lambda$,
so that $f_{X}(x)=\lambda e^{-\lambda x}$ for $\lambda>0,$

$\lim_{a\rightarrow\infty}\mu_{\mathcal{D}}(a-i,a)-\log a-B(j)=0$ (127)

for a constant $B(j)>0.$ Moreover, $\mu_{\mathcal{D}}(a-i,a)$ is strictly
concave.

###### Proof.

For an exponential distribution with rate parameter $\lambda,$ it is well
known that

$\mu_{\mathcal{D}}(a-i,a)=\sum_{j=i+1}^{a}\frac{1}{\lambda n}.$ (128)

It is clear, then, that $\mu_{\mathcal{D}}(a-i,a)$ is strictly concave. (128)
is equal to

$\frac{1}{\lambda}\left(\log
n+\gamma+\epsilon(a)-\sum_{j=1}^{i}\frac{1}{j}\right),$ (129)

where $\gamma$ is the Euler-Mascheroni constant and
$\lim_{a\rightarrow\infty}\epsilon(a)=0,$ from which (127) follows. ∎

##### Proof of Theorem 1(iv).

Recall again that

$h(a):=\sum_{i=1}^{\min\\{k,a\\}}\mu_{\mathcal{D}}(a-i+1,a).$ (130)

Then it suffices to show that $h$ is strictly concave and

$\lim_{a\rightarrow\infty}\frac{h(a)}{Ba^{\frac{1}{\alpha}}}=1$ (131)

for a constant $B>0.$ Both of these facts follow directly from the lemma
below. Theorem 1(iv) then follows immediately by applying Lemma D.1(iv).

######  Lemma D.4.

For $\mathcal{D}$ a Pareto distribution with pdf $f_{X}(x)=x^{-\alpha-1}$ for
$\alpha>1,$

$\lim_{a_{t}\rightarrow\infty}\frac{\mu_{\mathcal{D}}(a-i,a)}{a^{\frac{1}{\alpha}}}=C$
(132)

for a constant $C>0.$ Moreover, $\mu_{\mathcal{D}}(a-i,a)$ is strictly
concave.

###### Proof.

The result follows directly from Lemmas D.10 and D.11 in [39], where it is
shown (in our notation) that

$\displaystyle\lim_{a\rightarrow\infty}\frac{\mu_{\mathcal{D}}(a,a)}{a^{\frac{1}{\alpha}}}=\Gamma\left(\frac{\alpha-1}{\alpha}\right)$
(133)

and

$\mu_{\mathcal{D}}(a-i,a)=\prod_{j=1}^{i}\left(1-\frac{1}{j\alpha}\right)\mu_{\mathcal{D}}(a,a).$
(134)

∎

Thus,

$\lim_{a\rightarrow\infty}\frac{\sum_{i=1}^{k}\mu_{\mathcal{D}}(a-i+1,a)}{B\log
a}=1$ (135)

for a constant $B$. Also, note that $\mu_{\mathcal{D}}(a-i,a)$ is a constant
multiple of $\mu_{\mathcal{D}}(a,a)$, and that $\mu_{\mathcal{D}}(a,a)$ is
strictly concave, since the mean of the largest order statistic of a
distribution is strictly concave in sample size. Thus,
$\mu_{\mathcal{D}}(a-i,a)$ is strictly concave.

###  D.3 Proof of Theorem 2

Suppose that for each fixed $i$, $X_{i}^{(t)}$ are i.i.d. Bernoulli random
variables with success probability $q_{i}$ such that $q_{i}=c(i+d)^{-\beta}$
for some $\beta,c,d\geq 0.$ We begin by proving parts (i),(ii), and (iii),
wherein the user only utilizes the highest value recommended item. In the
Bernoulli setting, this amounts to determining the probability that at least
one movie is satisfactory, i.e.,

$\sum_{t=1}^{m}p_{t}h(a_{t}),$ (136)

where

$\displaystyle h(a)=1-\prod_{i=1}^{a}(1-c(i+d)^{-\beta}).$ (137)

It suffices now to show the desired asymptotic properties for $h$ depending on
$\beta$, and applying Lemma D.1.

We note the following fact, which will be helpful in our analysis:

$1-x>e^{-x-x^{2}}\quad\text{for $0<x<\frac{1}{2}$}.$ (138)

####  D.3.1 Proof of Theorem 2(i)

We now consider the case $0\leq\beta<1$. We analyze

$1-h(a)=\prod_{i=1}^{a}(1-c(i+d)^{-\beta})=\prod_{i=d+1}^{a+d}(1-ci^{-\beta}),$
(139)

and bound it from above and below. Let $i^{\prime}$ be the smallest
$i^{\prime}$ such that $c(i^{\prime})^{-\beta}<\frac{1}{2}$. Bounding from
above,

$\displaystyle\prod_{i=i^{\prime}+1}^{a+d}(1-ci^{-\beta})$
$\displaystyle<\prod_{i=i^{\prime}+1}^{a+d}e^{-ci^{-\beta}}$ (140)
$\displaystyle=\exp\left[\sum_{i=i^{\prime}}^{a+d}-ci^{-\beta}\right]$ (141)
$\displaystyle<\exp\left[\int_{i^{\prime}}^{a+d+1}-cx^{-\beta}\,dx\right]$
(142)
$\displaystyle=\exp\left[-\left[\frac{cx^{1-\beta}}{1-\beta}\right]_{i^{\prime}}^{a+d+1}\right]$
(143)
$\displaystyle=\exp\left[-\frac{c}{1-\beta}\left((a+d+1)^{1-\beta}-(i^{\prime})^{1-\beta}\right)\right]$
(144)

Now, bounding from below,

$\displaystyle\prod_{i=i^{\prime}}^{a+d}(1-ci^{-\beta})$
$\displaystyle>\prod_{i=i^{\prime}}^{a+d}e^{-ci^{-\beta}-c^{2}i^{-2\beta}}$
(145)
$\displaystyle=\exp\left[\sum_{i=i^{\prime}}^{a+d}-ci^{-\beta}-c^{2}i^{-2\beta}\right]$
(146)
$\displaystyle>\exp\left[\int_{i^{\prime}-1}^{a+d}-cx^{-\beta}-c^{2}x^{-2\beta}\,dx\right]$
(147)
$\displaystyle=\exp\left[-\left[\frac{cx^{1-\beta}}{1-\beta}+\frac{c^{2}x^{2-\beta}}{2-\beta}\right]_{i^{\prime}-1}^{a+d}\right]$
(148)
$\displaystyle=\exp\left[-\frac{c}{1-\beta}\left((a+d)^{1-\beta}-(i^{\prime}-1)^{1-\beta}\right)-\frac{c^{2}}{1-2\beta}\left((a+d)^{2-\beta}-(i^{\prime}-1)^{2-\beta}\right)\right],$
(149)

where the first inequality follows from (138). Then observing that

$1-h(a)=\prod_{i=d+1}^{i^{\prime}-1}(1-ci^{-\beta})\cdot\prod_{i=i^{\prime}}^{a+d}(1-ci^{-\beta}),$
(150)

where the first product is constant in $a$, it follows that

$\lim_{a\rightarrow\infty}\frac{\log(1-h(a))}{-\frac{c}{1-\beta}a^{1-\beta}}=1,$
(151)

as desired. The result follows from Lemma D.1(i).

####  D.3.2 Proof of Theorem 2(ii)

We turn to the case $\beta=1$. We have that

$\displaystyle 1-h(a)=\prod_{i=d+1}^{a+d}\left(1-\frac{c}{i}\right)$
$\displaystyle=\frac{d+1-c}{d}\cdot\frac{d+2-c}{d+1}\cdot\ldots\cdot\frac{a+d-c}{a+d},$
(152)

which telescopes to

$\prod_{i=1}^{c}\frac{d+i-c}{a+d-i+1}.$ (153)

Now note that

$\lim_{a\rightarrow\infty}\frac{\prod_{i=1}^{c}\frac{d+i-c}{a+d-i+1}}{a^{-c}}=\prod_{i=1}^{c}(d+i-c)$
(154)

is a finite constant. Therefore,

$\lim_{a\rightarrow\infty}\frac{1-h(a)}{Ba^{-c}}=1$ (155)

for constant $B$.

####  D.3.3 Proof of Theorem 2(iii)

We now consider the case $\beta>1$. In this case, we will again bound (137)
from above and below. First note that

$1-h(a)=\prod_{i=d+1}^{\infty}(1-ci^{-\beta})=S$ (156)

for a finite constant $S$.

We have that

$\displaystyle\prod_{i=a+d+1}^{\infty}(1-ci^{-\beta})$
$\displaystyle<\prod_{i=a+d+1}^{\infty}e^{-ci^{-\beta}}$ (157)
$\displaystyle=\exp\left[\sum_{i=a+d+1}^{\infty}-ci^{-\beta}\right]$ (158)
$\displaystyle<\exp\left[\int_{a+d+1}^{\infty}-cx^{-\beta}\,dx\right]$ (159)
$\displaystyle=\exp\left[-\left[\frac{cx^{1-\beta}}{1-\beta}\right]_{a+d+1}^{\infty}\right]$
(160) $\displaystyle=\exp\left[-\frac{c}{1-\beta}(a+d+1)^{1-\beta}\right]$
(161)

Therefore,

$\prod_{i=1}^{a+d}(1-ci^{-\beta})=\frac{S}{\prod_{i=a+d+1}^{\infty}}(1-ci^{-\beta})>S/\exp\left[-\frac{c}{1-\beta}(a+d+1)^{1-\beta}\right].$
(162)

Also,

$\displaystyle\prod_{i=a+d+1}^{\infty}(1-ci^{-\beta})$
$\displaystyle>\prod_{i=a+d+1}^{\infty}e^{-ci^{-\beta}-c^{2}i^{-2\beta}}$
(163)
$\displaystyle=\exp\left[\sum_{i=a+d+1}^{\infty}-ci^{-\beta}-c^{2}i^{-2\beta}\right]$
(164)
$\displaystyle<\exp\left[\int_{a+d}^{\infty}-cx^{-\beta}-c^{2}x^{-2\beta}\,dx\right]$
(165)
$\displaystyle=\exp\left[-\left[\frac{cx^{1-\beta}}{1-\beta}+\frac{c^{2}x^{2-\beta}}{2-\beta}\right]_{a+d}^{\infty}\right]$
(166)
$\displaystyle=\exp\left[-\frac{c}{1-\beta}(a+d)^{1-\beta}-\frac{c^{2}}{1-2\beta}(a+d)^{2-\beta}\right],$
(167)

where the first inequality holds for $a$ sufficiently large due to (138).

Therefore,

$\prod_{i=1}^{a+d}(1-ci^{-\beta})=\frac{S}{\prod_{i=a+d+1}^{\infty}}(1-ci^{-\beta})<S/\exp\left[-\frac{c}{1-\beta}(a+d-1)^{1-\beta}-\frac{c^{2}}{1-2\beta}(a+d)^{2-\beta}\right].$
(168)

Now observe that

$\lim_{a\rightarrow\infty}-\frac{c}{1-\beta}(a+d+1)^{1-\beta}=0$ (169)

and

$\lim_{a\rightarrow\infty}-\frac{c}{1-\beta}(a+d-1)^{1-\beta}-\frac{c^{2}}{1-2\beta}(a+d)^{2-\beta}=0.$
(170)

Therefore,

$\lim_{a\rightarrow\infty}\frac{\prod_{i=1}^{a+d}(1-ci^{-\beta})}{\frac{S}{1-\frac{c}{1-\beta}(a+d+1)^{1-\beta}}}=1.$
(171)

Also note that

$\frac{S}{1-\frac{c}{1-\beta}(a+d+1)^{1-\beta}}=S-\frac{S\frac{c}{1-\beta}}{(a+d+1)^{\beta-1}+\frac{c}{1-\beta}}$
(172)

Also,

$\lim_{a\rightarrow\infty}\frac{\prod_{i=1}^{a+d}(1-ci^{-\beta})}{\frac{S}{1-\frac{c}{1-\beta}(a+d-1)^{1-\beta}-\frac{c^{2}}{1-2\beta}(a+d)^{2-\beta}}}=1$
(173)

and

$\lim_{a\rightarrow\infty}\frac{1-\frac{c}{1-\beta}(a+d)^{1-\beta}-\frac{c^{2}}{1-2\beta}(a+d)^{2-\beta}}{1-\frac{c}{1-\beta}(a+d)^{1-\beta}}=1.$
(174)

It follows that

$\lim_{a\rightarrow\infty}\frac{1-S-h(a)}{-\frac{Sc}{1-\beta}a^{1-\beta}}=1$
(175)

as desired. The result follows from Lemma D.1(ii).

####  D.3.4 Proof of Theorem 2(iv)

We now prove part (iv), where we consider the expected total value of all
recommended items, which is equal to

$\sum_{t=1}^{m}p_{t}h(a_{t}),$ (176)

where

$h(a)=\sum_{i=1}^{a}c(i+d)^{-\beta}.$ (177)

Again, we consider three cases, $0<\beta<1,\beta=1,\beta>1.$

##### Case 1: $0<\beta<1$.

For $0<\beta<1,$ observe that

$\displaystyle\sum_{i=1}^{a}c(i+d)^{-\beta}<\int_{d}^{a+d}cx^{-\beta}\,dx$
$\displaystyle=\left[\frac{c}{1-\beta}x^{1-\beta}\right]_{d}^{a+d}$ (178)
$\displaystyle=\frac{c}{1-\beta}(a+d)^{1-\beta}-\frac{c}{1-\beta}d^{1-\beta}$
(179)

and

$\displaystyle\sum_{i=1}^{a}c(i+d)^{-\beta}>\int_{d+1}^{a+d+1}cx^{-\beta}\,dx$
$\displaystyle=\left[\frac{c}{1-\beta}x^{1-\beta}\right]_{d+1}^{a+d+1}$ (180)
$\displaystyle=\frac{c}{1-\beta}(a+d+1)^{1-\beta}-\frac{c}{1-\beta}(d+1)^{1-\beta}.$
(181)

It follows that

$\displaystyle\lim_{a\rightarrow\infty}\frac{h(a)}{a^{1-\beta}}=\frac{c}{1-\beta},$
(182)

and the result in this case follows by applying Lemma D.1(iv).

##### Case 2: $\beta=1$.

Now for $\beta=1,$ we have that

$\displaystyle\sum_{i=1}^{a}c(i+d)^{-\beta}=c\sum_{i=d+1}^{a+d}\frac{1}{i}.$
(183) $\displaystyle\lim_{a\rightarrow\infty}h(a)-c\log
a+c\gamma-c\sum_{i=1}^{d}\frac{1}{i}=0,$ (184)

where $\gamma$ is the Euler-Mascheroni constant The result in this case
follows by applying Lemma D.1(iii).

##### Case 3: $\beta>1$.

Finally, for $\beta>1,$ we have that

$\sum_{i=1}^{\infty}c(i+d)^{-\beta}=S$ (185)

for some finite $S$. Then note that

$\sum_{i=1}^{a}c(i+d)^{-\beta}=S-\sum_{i=a+1}^{\infty}c(i+d)^{-\beta}.$ (186)

Then we have

$\displaystyle\sum_{i=a+1}^{\infty}c(i+d)^{-\beta}<\int_{a}^{\infty}cx^{-\beta}\,dx$
$\displaystyle=\left[\frac{c}{1-\beta}x^{1-\beta}\right]_{a}^{\infty}=-\frac{c}{1-\beta}a^{1-\beta}$
(187)

and

$\displaystyle\sum_{i=a+1}^{\infty}c(i+d)^{-\beta}>\int_{a+1}^{\infty}cx^{-\beta}\,dx$
$\displaystyle=\left[\frac{c}{1-\beta}x^{1-\beta}\right]_{a+1}^{\infty}=-\frac{c}{1-\beta}(a+1)^{1-\beta}$
(188)

It follows that

$\lim_{a\rightarrow\infty}\frac{h(a)}{S-\frac{c}{\beta-1}a^{1-\beta}}=1.$
(189)

The result in this case follows again by applying Lemma D.1(ii).

###  D.4 A rounding lemma

The following lemma is useful for showing that—for the class of problems we
consider here—optimal integer solutions are well-approximated by optimal real
solutions.

######  Lemma D.5.

Let $g_{1},g_{2},\cdots,g_{m}:[0,\infty)^{m}\rightarrow\mathbb{R}$ be strictly
convex functions over the non-negative reals. Then define

$g(x_{1},\cdots,x_{m}):=\sum_{t=1}^{m}g_{t}(x_{t}).$ (190)

Then, under the constraint that $\sum_{t=1}^{m}x_{t}=n$, if
$(x_{1}^{*},\cdots,x_{m}^{*})$ is the maximum of $g$ over the non-negative
reals and $(a_{1}^{*},\cdots,a_{m}^{*})$ is the maximum of $g$ over the non-
negative integers, then

$\lfloor x_{t}^{*}\rfloor-m<a_{t}^{*}<\lfloor x_{t}^{*}\rfloor+m$ (191)

for all $t$.

###### Proof.

The key idea is to show that there cannot be $i,j$ such that
$a_{i}^{*}\geq\lceil x_{i}\rceil+1$ and $a_{j}^{*}\leq\lceil x_{j}\rceil-1.$
If such a pair does exist, we show that

$g(\cdots,a_{i}^{*}-1,\cdots,a_{j}^{*}+1,\cdots)\geq
g(\cdots,a_{i}^{*},\cdots,a_{j}^{*},\cdots),$ (192)

contradicting the optimality of $a_{1}^{*},\cdots,a_{m}^{*}.$ It suffices to
show that

$g_{i}(a_{i}^{*}-1)+g_{j}(a_{j}^{*}+1)\geq g_{i}(a_{i}^{*})+g_{j}(a_{j}^{*}),$
(193)

or equivalently,

$g_{j}(a_{j}^{*}+1)-g_{j}(a_{j}^{*})\geq g_{i}(a_{i}^{*})-g_{i}(a_{i}^{*}-1).$
(194)

This holds, as

$\displaystyle g_{j}(a_{j}^{*}+1)-g_{j}(a_{j}^{*})\geq\frac{\partial
g_{j}}{\partial x_{j}}=\frac{\partial g_{i}}{\partial x_{i}}\geq
g_{i}(a_{i}^{*})-g_{i}(a_{i}^{*}-1).$ (195)

∎

###  D.5 Proof of Proposition 2

For ease of exposition, we will begin by proving the result for $k=1$ and then
handle the more general case.

##### First case ($k=1$).

Let us first consider the case $k=1.$ We would like to find an ordered tuple
of non-negative integers $(a_{1},\cdots,a_{m})$ that maximizes

$\sum_{t=1}^{m}p_{t}\mu_{\mathcal{D}}(a_{t},a_{t})=\sum_{t=1}^{m}p_{t}\left(1-\frac{1}{a_{t}+1}\right)$
(196)

subject to the constraint $\sum_{t=1}^{m}a_{t}=n.$ Our strategy will be to
solve the relaxed optimization problem over non-negative reals, and then show
that the optimal integer solution is “close to” the optimal real solution.
Consider the function $g:[0,\infty)^{m}\rightarrow\mathbb{R}$, where

$g(x_{1},\cdots,x_{m})=\sum_{t=1}^{m}p_{t}\left(1-\frac{1}{x_{t}+1}\right).$
(197)

Subject to the constraint $\sum_{t=1}^{m}x_{t}=n,$ $g(x_{1},\cdots,x_{m})$ is
maximized exactly when

$\frac{\partial g}{\partial x_{1}}=\frac{\partial g}{\partial
x_{2}}=\cdots=\frac{\partial g}{\partial x_{m}}.$ (198)

This is clear after noting that $g$ is convex on its domain and applying
Lagrange multipliers. We have that

$\frac{\partial g}{\partial x_{t}}=p_{t}\left(\frac{1}{x_{t}+1}\right)^{2}.$
(199)

So if $(x_{1}^{*},\cdots,x_{m}^{*})$ is a maximum, then
$x_{t}^{*}+1\propto\sqrt{p_{t}},$ meaning that

$x_{t}^{*}=\left(\frac{\sqrt{p_{t}}}{\sum_{i=1}^{m}\sqrt{p_{i}}}\right)n-1.$
(200)

We now apply Lemma D.5: if $(a_{1}^{*},\cdots,a_{m}^{*})$ is the optimal
integer solution, then $|a_{t}^{*}-x_{t}^{*}|\leq m$. Thus,

$\left|a_{t}^{*}-\frac{\sqrt{p_{t}}}{\sum_{i=1}^{m}\sqrt{p_{i}}}n\right|\leq
m+1$ (201)

for all $n$.

##### General case $k$.

More generally, we would like to maximize

$\sum_{t=1}^{m}p_{t}\sum_{i=1}^{\min\\{a_{t},k(n)\\}}\mu_{\mathcal{D}}(a_{t}-i+1,a_{t}).$
(202)

subject to the constraint $\sum_{t=1}^{m}a_{t}=n,$ where we let $k=k(n)$ be a
function of $n$. We first analyze each case of the inner summation:

$\sum_{i=1}^{\min\\{a_{t},k(n)\\}}\mu_{\mathcal{D}}(a_{t},a_{t}-i+1)=\begin{cases}\frac{a_{t}}{2}&\quad
a_{t}\leq k(n)\\\
\sum_{i=1}^{k(n)}1-\frac{i}{a_{t}+1}=k(n)-\frac{k(n)^{2}+k(n)}{2(a_{t}+1)}&\quad
a_{t}>k(n)\end{cases}.$ (203)

The top case $a_{t}\leq k(n)$ follows from all $a_{t}$ items of that type
contributing to the objective, each with a mean value of $\frac{1}{2}$.

Then define

$g:[0,\infty)^{m}\rightarrow\mathbb{R},\quad(x_{1},\cdots,x_{m})\mapsto\sum_{t=1}^{m}p_{t}h(x_{t})$
(204)

where

$h(x):=\begin{cases}\frac{x}{2}&\quad x\leq k(n)\\\
\sum_{i=1}^{k(n)}1-\frac{i}{x+1}=k(n)-\frac{k(n)^{2}+k(n)}{2(x+1)}&\quad
x>k(n)\end{cases}.$ (205)

So we have

$\frac{\partial g}{\partial x_{t}}=\begin{cases}\frac{p_{t}x}{2}&\quad
x_{t}\leq k(n)\\\ p_{t}(k(n)^{2}+k(n))\left(\frac{1}{x_{t}+1}\right)^{2}&\quad
x_{t}>k(n)\end{cases}.$ (206)

We first consider possible solutions where $x_{t}>k(n)$ for all $t\in[m].$ In
this case,

$\frac{\partial g}{\partial
x_{t}}=p_{t}(k(n)^{2}+k(n))\left(\frac{1}{x_{t}+1}\right)^{2}$ (207)

is equal for all $t$ at the maximum, as before. Remarkably, the new
$k(n)^{2}+k(n)$ term drops out. So if $(x_{1}^{*},\cdots,x_{m}^{*})$ is the
optimal real solution, again, $x_{t}^{*}+1\propto\sqrt{p_{t}},$ and the result
follows as in the first case. Here, $x_{t}^{*}>k(n)$ holds whenever
$k\leq\frac{\sqrt{p_{m}}}{\sum_{i=1}^{m}\sqrt{p_{i}}}n-m-1.$

###  D.6 Proof of Theorem 3

###### Proof.

We would like to find $a_{1},\cdots,a_{m}$ that maximizes

$\sum_{t=1}^{m}p_{t}\left(1-(1-q_{t})^{a_{t}}\right)=1-\sum_{t=1}^{m}p_{t}(1-q_{t})^{a_{t}}.$
(208)

subject to the constraint $\sum_{t=1}^{m}p_{t}=n.$ This is equivalent to
minimizing

$\sum_{t=1}^{m}p_{t}(1-q_{t})^{a_{t}}.$ (209)

Now define a function

$g:[0,\infty)^{m}\rightarrow\mathbb{R},\quad(x_{1},\cdots,x_{m})\mapsto\sum_{t=1}^{m}p_{t}(1-q_{t})^{x_{t}}.$
(210)

Subject to the constraint $\sum_{t=1}^{m}x_{t}=n,$ $g(x_{1},\cdots,x_{m})$ is
maximized exactly when

$\frac{\partial g}{\partial x_{1}}=\frac{\partial g}{\partial
x_{2}}=\cdots=\frac{\partial g}{\partial x_{m}}.$ (211)

We have

$\frac{\partial g}{\partial x_{t}}=-p_{t}(1-q_{t})^{x_{t}}\log(1-q_{t}).$
(212)

Solving $\partial g/\partial x_{i}=\partial g/\partial x_{j}$ gives

$\displaystyle p_{i}(1-q_{i})^{x_{i}}\log(1-q_{i})$
$\displaystyle=p_{j}(1-q_{j})^{x_{j}}\log(1-q_{j})$ (213)
$\displaystyle\implies\log p_{i}+x_{i}\log(1-q_{i})+\log\log(1-q_{i})$
$\displaystyle=\log p_{j}+x_{j}\log(1-q_{j})+\log\log(1-q_{j})$ (214)

It follows that $a_{t}\propto\frac{1}{\log(1-q_{t})}$ for all $t$, where we
have once again applied Lemma D.5. ∎