# Optimal Stopping with Multi-Dimensional Comparative Loss Aversion

Linda Cai111Princeton University<EMAIL_ADDRESS>Joshua
Gardner222Princeton University<EMAIL_ADDRESS>S. Matthew
Weinberg333Princeton University<EMAIL_ADDRESS>Supported by NSF
CAREER CCF-1942497 and a Google Research Award.

###### Abstract

Motivated by behavioral biases in human decision makers, recent work by
Kleinberg et al. [11] explores the effects of loss aversion and reference
dependence on the prophet inequality problem, where an online decision maker
sees candidates one by one in sequence and must decide immediately whether to
select the current candidate or forego it and lose it forever. In their model,
the online decision-maker forms a reference point equal to the best candidate
previously rejected, and the decision-maker suffers from loss aversion based
on the quality of their reference point, and a parameter $\lambda$ that
quantifies their loss aversion. We consider the same prophet inequality setup,
but with candidates that have _multiple features_. The decision maker still
forms a reference point, and still suffers loss aversion in comparison to
their reference point as a function of $\lambda$, but now their reference
point is a (hypothetical) combination of the best candidate seen so far _in
each feature_.

Despite having the same basic prophet inequality setup and model of loss
aversion, conclusions in our multi-dimensional model differs considerably from
the one-dimensional model of Kleinberg et al. [11]. For example, Kleinberg et
al. [11] gives a tight closed-form on the competitive ratio that an online
decision-maker can achieve as a function of $\lambda$, for any $\lambda\geq
0$. In our multi-dimensional model, there is a sharp phase transition: if $k$
denotes the number of dimensions, then when $\lambda\cdot(k-1)\geq 1$, _no
non-trivial competitive ratio is possible_. On the other hand, when
$\lambda\cdot(k-1)<1$, we give a tight bound on the achievable competitive
ratio (similar to [11]). As another example, [11] uncovers an exponential
improvement in their competitive ratio for the random-order vs. worst-case
prophet inequality problem. In our model with $k\geq 2$ dimensions, the gap is
at most a constant-factor. We uncover several additional key differences in
the multi- and single-dimensional models.

##  1 Introduction

Reference dependence describes the tendency for human decision-makers to
compare options against a previously seen or anticipated reference point, such
that an option inferior to the reference point is perceived as being of a
lower quality than it would be had the person simply not been aware of the
reference point [22]. Similarly, loss aversion describes the tendency of human
decision-makers to be more sensitive to losses than to gains of equivalent
magnitude. Both phenomena have robust empirical support [10], and have been
observed in the context of online decision-making [19].

Recent work of Kleinberg et al. [11], has considered these behavioral biases
in the context of optimal stopping, constructing biased agents who suffer from
loss aversion in comparing their chosen candidate against previously seen and
foregone candidates. Prophet inequalities are a canonical optimal stopping
problem, where an agent sees $n$ candidates, each with a scalar value drawn
independently from known distributions. The candidates are presented online,
such that whenever the agent sees a candidate they must either accept it,
halting their search, or forego it and thus lose the candidate forever. In the
event they select a candidate, the utility they receive is exactly the value
of the candidate. Motivated by the role of reference points and loss aversion,
[11] pose a modified prophet inequality where the utility received by the
agent is discounted based on their reference point. Specifically, the biased
agent also remembers the best candidate they have previously seen, and
perceives new candidates as having decreased utility if the best candidate
previously seen had a higher value.

The elegant model of Kleinberg et al. [11] captures scenarios in which
candidates are well-represented by a single scalar (such as monetary value).
Indeed, their model is partially motivated by the empirical findings of Schunk
and Winter [19] concerning the unwillingness of investors to sell stocks below
the price at which they were purchased. Similarly, their model captures the
phenomenon of biased decision-makers stopping much sooner than optimal, once
again mirroring the empirical results of [19]. Intuitively, due to the
anticipation of experiencing regret over foregone candidates, biased decision-
makers are likely to settle earlier than they should. In this respect, the
theoretical model of Kleinberg et al. [11] reflects human behavior relatively
well, at least in the case of decisions involving scalar-valued candidates.

However, their model does not capture decisions in which candidates have
multiple features of interest. Notably, many key decisions in life including
career, romantic partner, or house typically have many dimensions. Moreover,
even simple consumer decisions such as selecting which movie to watch or
magazine subscription to purchase often have multiple dimensions. Experimental
research by Brenner et al. [2] suggests that human decision makers suffer from
“comparative loss aversion” in which they compare options along multiple
dimensions, and perceive disadvantages as being more significant than
advantages due to loss aversion, thus decreasing received utility from the
option chosen. Consider the case of selecting a house: suppose that house A is
the most aesthetically pleasing, house B is in the best location, and house C
has the most space. Regardless of which house a person selects, due to
comparative loss aversion, the mere awareness of the other options decreases
the satisfaction they experience. Empirical research [8, 3, 14] on the
phenomenon of “choice overload” (where people become less satisfied with their
choice when they are presented with a larger set of options) further supports
the existence of comparative loss aversion.

One interpretation of this phenomenon that has been popularized in
psychological literature like The Paradox of Choice [20] is that people
combine the best features of options they have previously seen into an
imagined alternative of superior quality. Later empirical work by Sagi and
Friedland [17] found that “regret is related to the comparison between the
alternative chosen and the union of the positive attributes of the
alternatives rejected.” Intuitively, compared to an imagined alternative
combining the best attributes seen, the option chosen is much less satisfying.

In our work, we model this phenomenon by associating each candidate $i$ with a
_$k$ -dimensional vector_
$\vec{\sigma}^{(i)}=\left\lparen\sigma_{1}^{(i)},\cdots,\sigma_{k}^{(i)}\right\rparen$
rather than a single scalar. The agent’s value for a single candidate is just
the sum over the agent’s value for the candidate on each dimension, namely,
$\lVert\vec{\sigma}^{(i)}\rVert_{1}$. So for an unbiased decision-maker, this
is still just an instance of the classic prophet inequality. As in [11], our
agent is biased, and maintains a reference point $\vec{s}^{(i)}$ at time $i$
based on options seen so far. The agent suffers from loss aversion
parameterized by $\lambda$, and experiences (and anticipates) a loss equal to
$\lambda\cdot\left\lparen\lVert\vec{\sigma}^{(i)}\rVert_{1}-\lVert\vec{s}^{(i)}\rVert_{1}\right\rparen$
upon selecting candidate $i$. The key distinction between our model and that
of [11] is in how the reference point is built. In Kleinberg et al. [11], the
reference point is simply the vector of a candidate $j\leq i$ maximizing the
overall value $\lVert\sigma^{(j)}\rVert_{1}$. In our model, the reference
point is instead a hypothetical super-candidate that combines the best
candidate seen so far for each feature. Formally, for each dimension $\ell$,
the value of the reference point is $s^{(i)}_{\ell}=\max_{j\leq
i}\\{\sigma^{j}_{\ell}\\}$. As previously discussed, this enables our model to
better capture the multi-dimensional problem of purchasing a house, versus the
single-dimensional problem of buying/selling stocks that are well-captured by
the model of [11]. To reiterate: our model is identical to that of [11],
_except_ for the choice of reference point. Surprisingly, this single change
from a single-dimensional reference point to a multi-dimensional reference
point drastically changes conclusions in the model.

###  1.1 Summary of Results

Our main findings are that an agent who suffers from comparative loss aversion
(i.e. our model, the multi-dimensional case) suffers in a fundamentally
different manner than an agent who only suffers from reference-dependent loss
aversion (i.e. [11], the single-dimensional case). We now overview several
results supporting this. In describing our results, “gambler” refers to the
online decision-maker in the prophet inequality setting, and “prophet” refers
to the offline decision-maker (who knows all options and simply picks the
best).

Unbounded Loss. Perhaps our most surprising finding is a phase transition in
$\lambda$ as a function of $k$ when comparing the utility of a biased gambler
to that of an unbiased gambler or unbiased prophet. Specifically, Kleinberg et
al. [11] show that a biased gambler can always guarantee at least a
$\frac{1}{2+\lambda}$-approximation to the expected utility achieved by an
unbiased prophet, and a $\frac{1}{1+\lambda}$-approximation to that of an
unbiased gambler (and both of these bounds are tight). When
$\lambda\cdot(k-1)<1$, we find a natural generalization: the biased gambler
can guarantee a $\frac{1-\lambda(k-1)}{2+\lambda}$-approximation to the
unbiased prophet, and a $\frac{1-\lambda(k-1)}{1+\lambda}$-approximation to
the unbiased gambler, and these are tight for all $k$ (including $k=1$, where
it matches [11]). However, there is a phase transition at
$\lambda\cdot(k-1)=1$: _for any $\lambda\cdot(k-1)\geq 1$, and any $C$, there
exist instances where the biased gambler achieves expected utility $1$, but
the unbiased gambler (and unbiased prophet) achieve expected utility at least
$C$_. That is, there is no non-trivial guarantee on the competitive ratio as a
function only of $\lambda$ and $k$. Interestingly, this phase transition
occurs for all $k>1$, but not for $k=1$. This marks a fundamental difference
between online decision-making with comparative loss aversion versus only
reference-dependent loss aversion.

Given the importance of the phase transition, we will call $\lambda\cdot(k-1)$
the feature-amplified bias. Intuitively, feature-amplified bias measures how
fast the gap between the utilities of unbiased and biased agents grows with
the number of candidates. As we will see in an illustrative example in section
3, when the feature-amplified bias is greater than one, the ratio between
utility of an unbiased prophet and that of a biased gambler grows
exponentially with the number of candidates. The formal statements of our main
results when feature-amplified bias is less than one can be found in theorems
4.1, 4.1 and 4.1. For the setting where feature-amplified bias is at least
one, the main results can be found in theorem 4.1.

No Improvement for Random Order, Optimal Order, and I.I.D. Distributions. One
key finding of Kleinberg et al. [11] is that the competitive ratio of a biased
gambler compared to an unbiased gambler/prophet drastically improves (the loss
is logarithmic in $\lambda$ instead of linear in $\lambda$) when the
candidates are revealed in random order. This of course holds in our model
when $k=1$ (because it is identical to [11]). When $k>1$, however, this
phenomenon no longer occurs. Specifically, for all $k\geq 2$, _even if the
instance is i.i.d._ : (a) if feature-amplified bias $\lambda\cdot(k-1)\geq 1$,
then the expected reward of the biased gambler and unbiased prophet/gambler
can be unbounded, and (b) when feature-amplified bias $\lambda\cdot(k-1)<1$,
the worst-case ratio between the biased gambler and unbiased prophet/gambler
is within a constant-factor of the worst-case ratio without the i.i.d.
assumption.444Of course, we do not nail down the tight competitive ratio for
the gambler in the i.i.d. setting, because even the tight ratio between the
gambler and prophet without loss aversion is quite involved. The tight
competitive ratio between the unbiased gambler and unbiased prophet for the
random order (but not i.i.d.) setting is still unknown. The formal statements
of our results for the i.i.d setting can be found in theorems 4.5 and 4.5.

###  1.2 Related Work.

Since its introduction, optimal stopping has been pertinent to the study of
economic behaviors with immediate applications in a wide range of economic
domains such as search theory, financial trading, auction design, etc. Various
models have been proposed based on the optimal stopping paradigm including
prophet inequalities (value distribution known), secretary problems (value
distribution unknown) and Pandora’s box problem (where a cost is associated
with inspection of options).

The model that is most relevant to our present work is that of the prophet
inequality, where the agents are given the distribution of their value for the
candidates a priori. In the seminal work of Krengel and Sucheston [13], it was
shown that for prophet inequalities where the agent is limited to picking a
single candidate, the ratio between the expected largest value (namely, the
prophet’s pick) and the expected value of the candidate an agent playing
optimally selects online is at most $2$. Furthermore, this ratio is tight.
Samuel-Cahn [18] further show that by using a threshold based algorithm, the
online agent can also guarantee that the expected value of the candidate they
select is a $1/2$-approximation of the expected optimal value over all
candidates. Prophet inequalities have since been further studied under a
variety of feasibility constraints on the set of selected candidates
(Kleinberg and Weinberg [12], Rubinstein [15], Rubinstein and Singla [16],
Duetting et al. [5]), and a variety of arrival order constraints (Esfandiari
et al. [7], Ehsani et al. [6], Yan [23], Beyhaghi et al. [1], Hill and Kertz
[9], Correa et al. [4]).

Although optimal stopping may have direct applications in human decision
making, very little research has devoted to behavioral models of optimal
stopping. Recently, Kleinberg et al. [11] constructed a model which factors in
reference dependence and loss aversion, however to our knowledge there is no
other prior work exploring behavioral phenomena in the context of optimal
stopping.

###  1.3 Organization.

The rest of the paper will be organized as follows. In section 2, we discuss
our model that incorporates comparative loss aversion and introduce notations
that will be used throughout the paper. In section 3, we present an
illustrative example that highlights the difference between our model and the
single dimensional model presented in [11]. In section 4, we analyze our model
under various ordering constraints, with a focus on the gap between the
utility of the biased gambler and that of rational agents. In Section 5 we
discuss the limitations of our model and possible directions for future work.
In Appendix A and Appendix B, we provide proofs that are omitted from Section
4. Lastly, in Appendix C we present monotonicity results which were all
analogous to those of the one dimensional case presented in Kleinberg et al.
[11].

##  2 Model and Preliminary

###  2.1 Modeling Comparative Loss Aversion

Multidimensional Optimal Stopping. We now construct a multi-dimensional model
of the optimal stopping problem such that candidates have multiple dimensions
of value. First, we must formally define the multi-dimensional optimal
stopping problem, using slight modifications of the classic definition of the
problem in one dimension. Specifically, let there be $n$ candidates each of
which has $k$ dimensions of value that are of interest to a decision making
agent, i.e. there are $n$ vector valued candidates, such that their value
vectors are $k$-dimensional. Note that the use of vector values differs from
traditional constructions of the problem in which scalar values are used, i.e.
in the traditional problem $k$ is 1.

We will use $\mathcal{F}_{t}$ with support on $\mathbb{R}^{k}_{+}$ to denote
the prior distribution of the gambler’s value vector for the $t^{th}$
candidate. Let $\sigma$ be an ordered sequence of $n$ candidates, where the
$t^{th}$ candidate has a k-dimensional vector value
$\sigma^{(t)}\in\mathbb{R}^{k}$ drawn from $\mathcal{F}_{t}$. Formally, we
will use $\mathcal{F}=\times_{t\in[n]}\mathcal{F}_{t}$ to denote the joint
distribution of the value for all candidates, such that $\sigma$ is drawn from
$\mathcal{F}$. Moreover, let it be the case that the agent sees the realized
value of $\sigma^{(t)}$ only when they reach step t in the sequence. Upon
reaching the $t^{th}$ candidate, $\sigma^{(t)}$, the agent must either accept
them - thus halting their search - or decline them, continuing their search
and losing the candidate forever. The agent attempts to select $\sigma^{(t)}$
to maximize their utility. We now need to reason about what an agent’s utility
function should look like.

The utility of agents with comparative loss aversion. In keeping with the
notation of Kleinberg et al. [11], let the parameter $\lambda\geq 0$ serve as
a multiplier representing our agent’s loss aversion. In particular, let
$\lambda$ be used to amplify the difference between the chosen candidate and
the “reference candidate” along any dimensions for which the reference
candidate is of higher value. Observe that in the case of our model, reasoning
about the reference candidate is somewhat complex since an agent with
comparative loss aversion compares each option against all previously seen
along different dimensions independently. Regardless, it is without loss of
generality to collapse the highest values previously seen along each dimension
into single vector and consider this to be the reference candidate.

Accordingly, our agent remembers the best value previously seen along each
dimension and combines these to form their reference candidate, which we refer
to as the “super candidate”, since is an upperbound on the quality of all
previously seen candidates and combines all of their best features. Observe
that this super candidate changes over time as we see new candidates that are
better than all previously seen along some dimension. Due to the agent’s
reference dependence, when the super candidate is better than the agent’s
chosen candidate on any dimension, this detracts from the utility they
receive. Let us denote the super candidate at step t in the sequence as
$\vec{s}^{(t)}$ and the $j^{th}$ entry of the super candidate at step t as
$\vec{s}^{(t)}_{j}$. We define the super candidate in step t element-wise as
follows:

$\vec{s}^{(t)}_{j}=\max\limits_{w:w\in[t]}(\sigma^{(w)}_{j})$

We define the utility received by a biased gambler, who suffers from loss
aversion $\lambda$ and who selects the $t^{th}$ candidate in sequence
$\sigma$, as follows:

$U_{g_{b}}(\sigma,t)=\sum_{j}\bigg{(}\sigma^{(t)}_{j}-\lambda(\vec{s}^{(t)}_{j}-\sigma^{(t)}_{j})\bigg{)}=\|\sigma^{(t)}\|_{1}-\lambda\bigg{(}\|\vec{s}^{(t)}\|_{1}-\|\sigma^{(t)}\|_{1}\bigg{)},$

and we define the difference between the value selected by the biased gambler
and their utility as the biased gambler’s regret.

Recall that, by construction, we have already restricted all values to be non-
negative, allowing us to make use of L1 norms. Moreover, let’s compare this to
the utility received by biased prophet who selects option t:

$U_{p_{b}}(\sigma,t)=\sum_{j}\bigg{(}\sigma^{(t)}_{j}-\lambda(\vec{s}^{(n)}_{j}-\sigma^{(t)}_{j})\bigg{)}=\|\sigma^{(t)}\|_{1}-\lambda\bigg{(}\|\vec{s}^{(n)}\|_{1}-\|\sigma^{(t)}\|_{1}\bigg{)}$

Note that the only difference between the utility of the biased gambler and
biased prophet is that the super option of the biased prophet is constructed
from all n candidates, whereas that of the biased gambler is constructed only
from the t candidates it has seen so far.

Next let us reason about the utilities received by a rational gambler and
rational prophet, respectively. In particular, observe that since they do not
suffer from any reference dependence or loss aversion, their payoff is just
equal to the value of the option they select:

$U_{p_{r}}(\sigma,t)=U_{g_{r}}(\sigma,t)=\sum_{j}\sigma^{(t)}_{j}=\|\sigma^{(t)}\|_{1}$

Furthermore, assuming that our agents seek to maximize their utilities, the
payoff of a rational prophet does not need parameter t since it selects t
deterministically to maximize realized utility. Namely, it suffices to denote
the utility of a rational prophet as follows:

$U_{p_{r}}(\sigma)=\max\limits_{t:t\in[n]}(U_{p_{r}}(\sigma,t))$

Similarly, since the biased prophet sees all options and selects t
deterministically to maximize realized utility, we can remove the parameter t
here as well:

$U_{p_{b}}(\sigma)=\max\limits_{t:t\in[n]}(U_{p_{b}}(\sigma,t))$

Now that the model has been developed, we can proceed to begin analyzing it.
Next we will develop notations to describe the expected utility of biased and
rational agents, and their relative differences. These notations will be used
throughout the paper.

###  2.2 Preliminaries

In keeping with standard conventions, we use $\mathbb{E}_{\mathcal{F}}$ to
denote the expectation with respect to the distribution $\mathcal{F}$. To
abbreviate notation, we will use
$\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]$ and
$\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]$ to denote the expected
utility of the biased gambler and a rational gambler, respectively, when they
use a utility optimal online algorithm. Similarly, we will use
$\mathbb{E}_{\mathcal{F}}\left[U_{p_{b}}\right]$ and
$\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]$ to denote the expected
utility of the biased prophet and rational prophet, respectively. In addition,
we will use $V^{*}$ to denote the maximum value of all candidates, namely,
$V^{*}=\max\limits_{t\in[n]}\lVert\sigma^{(t)}\rVert_{1}$. We will use
$S_{j}^{*}$ to the denote the maximum value on the $j^{th}$ dimension, namely,
$S_{j}^{*}=\max\limits_{t\in[n]}\sigma_{j}^{(t)}$.

Next, we will create several definitions to describe the relationship between
utility of the biased gambler and the utility of rational agents, which will
be frequently referenced in subsequent sections. Informally, the
prophet/online utility ratio describes how well the biased gambler can do
compared to the rational prophet/gambler given a specific prior distribution
$\mathcal{F}$. On the other hand, the prophet/online competitive ratio
describes how well the biased gambler can do compared to the rational
prophet/gambler given the most adversarial prior distribution $\mathcal{F}$.

######  Definition 2.1 (Prophet Utility Ratio).

We will use the term prophet utility ratio to denote the ratio between the
expected utility of a rational prophet and the expected optimal utility from a
biased gambler under the prior distribution $\mathcal{F}$. More formally, we
define the prophet utility ratio as
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$.

Note that the Prophet Utility Ratio captures the loss that the biased gambler
experiences _both due to bias and due to making decisions online_.

######  Definition 2.2 (Online Utility Ratio).

We will use the term online utility ratio to denote the ratio between the
expected optimal utility of a rational gambler and the expected optimal
utility from a biased gambler under the prior distribution is $\mathcal{F}$.
Formally, we define the online utility ratio as
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{g^{*}_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$.

Note that the Online Utility Ratio captures the loss that the biased gambler
experiences _just due to bias_.

######  Definition 2.3 (Prophet/Online Competitive Ratio).

Given a setting (such as adversarial arrival order or i.i.d prior
distribution), we define the terms prophet competitive ratio and online
competitive ratio as the maximum prophet and online utility ratio possible in
the setting. Specifically, in the adversarial arrival order setting, the
prophet and online competitive ratio are formally defined as
$\max\limits_{\mathcal{F}}\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
and
$\max\limits_{\mathcal{F}}\frac{\mathbb{E}_{\mathcal{F}}\left[U_{g^{*}_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
, respectively. In the i.i.d prior distribution setting, we will denote
$\mathcal{U}$ as the set of all i.i.d distributions. The prophet and online
competitive ratio in the i.i.d prior distribution setting are then formally
defined as
$\max\limits_{\mathcal{F}\in\mathcal{U}}\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
and
$\max\limits_{\mathcal{F}\in\mathcal{U}}\frac{\mathbb{E}_{\mathcal{F}}\left[U_{g^{*}_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$.

As stated in the introduction, we define $\lambda\cdot(k-1)$ to be the
feature-amplified bias. We will soon see that whether the feature-amplified
bias $\lambda\cdot(k-1)$ is greater or less than one is critical in
determining whether the biased gambler has a non trivial prophet/online
competitive ratio.

Finally, the following claim that directly follows from classical prophet
inequality results will be referenced and used throughout proofs in the rest
of the paper.

######  Claim 2.4.

For any prior distribution $\mathcal{F}$ and any assumption about candidate
arrival order,
$\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]\geq\frac{1}{2}\cdot\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]$.

###### Proof.

In our model, rational agents’ utilities are simply their value for the option
they select. Therefore our claim follows directly from the classical prophet
inequality result [13, 12] that the expected value from a value-optimal online
algorithm is a $\frac{1}{2}$ approximation of the expected value from an
offline prophet. ∎

##  3 Unbounded Loss: A Motivating Example

Prior to proving more general claims, we will first show an adversarial
example that illustrates a fundamental difference between our multi-
dimensional optimal stopping problem with biased agents and the single
dimensional model. Specifically, in the single dimensional model, the biased
gambler attain worse utility than rational agents only when there is
uncertainty. (Imagine if the biased agent already knows all values of the
candidates, they can simply pick the one with the largest value and suffers no
regret.) However, in our multi-dimensional model, we will show an example
where the biased gambler attains arbitrarily worse utility than rational
agents, even when the prior distribution is deterministic.

######  Example 1.

Consider $n$ candidates arriving in adversarial order, where the biased
gambler considers $k=2$ features of candidates and has loss aversion parameter
$\lambda=2$. Furthermore, let $\sigma$ be the following sequence of candidate
values:

$\displaystyle(1,0),(0,1),(2,0),(0,2),(2^{2},0),(0,2^{2}),\cdots,(2^{n/2-1},0),(0,2^{n/2-1}),$

and let the prior distribution $\mathcal{F}$ be deterministic – where the
realized sequence from $\mathcal{F}$ is exactly $\sigma$ with probability one.

In our example, the overall value of the candidates increases exponentially
over time. Consequently, the rational prophet will receive high utility by
simply selecting one of the last two candidates. However, the fact that the
candidates are excellent on alternating dimensions causes the biased gambler
to suffer from increasing regret as they see more candidates. In fact, should
the biased gambler choose a later candidate rather than an earlier candidate,
the increment in their regret roughly cancels out the increment in their value
for the candidate.

With this intuition in mind, let’s formally reason about the behaviors of our
agents. Recall that the gambler is aware of the prior distribution
$\mathcal{F}$ and thus is aware of $\sigma$ a priori for this example. The
rational gambler is essentially the same as the rational prophet in this case
since they know $\sigma$ a priori and experience no regret. Thus, the expected
utility of both the rational prophet and the rational gambler is simply
$2^{n/2-1}$.

Under our stylized model, the biased gambler only experiences regret for
realized options, completely disregarding any future options they may be aware
of a priori. Consequently, the biased gambler has utility $1$ if they just
take the first candidate and are not presented other candidates, and they have
utility $\leq 0$ if they take any other candidate. (e.g. If the gambler
decides to select let’s say the candidate $(4,0)$, then the super candidate
has value $(4,2)$, which means that the biased gambler’s utility is
$\lVert(4,0)\rVert_{1}-2\cdot\left\lparen\lVert(4,2)\rVert_{1}-\lVert(4,0)\rVert_{1}\right\rparen=4-2\cdot(6-4)=0$.)
Therefore we know $\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]\leq 1$.
As a result, the biased gambler’s prophet utility ratio,
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\frac{U_{p_{r}}(\sigma)}{U_{g_{b}}(\sigma)}$,
and online utility ratio,
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\frac{U_{g_{r}}(\sigma)}{U_{g_{b}}(\sigma)}$,
are both equal to $2^{n/2-1}$, and thus tend toward $\infty$ as $n$ increases.
Recall that prophet and online utility ratios lower bound the prophet and
online competitive ratio, respectively, implying that both competitive ratios
must also be $\infty$.

As we will soon show in Section 4.1 and Section 4.1, our present adversarial
example with candidates that are excellent on alternating dimensions can be
generalized to any $k$ and $\lambda$ such that the feature-amplified bias
$\lambda\cdot(k-1)$ is at least one in the adversarial setting. Furthermore,
as we will show in Lemma 4.5 and Lemma 4.5, we can extend our example to i.i.d
setting (and thus to random and optimal candidate ordering setting) by
carefully constructing the prior distribution so that with high probability,
the sequence of realized candidate values presented to the agent is
adversarial and (after deleting subsequent duplicates) similar to the sequence
$\sigma$ in this example. Our capability to generalize the adversarial example
under any arrival order constraint drives our model’s departure from the
single dimensional model. Further, our adversarial example for the i.i.d
setting is highly randomized, which shows that the adversarial examples are
not an artifact of deterministic distributions.

Lastly, this example illustrates an additional property unique to our model:
the biased gambler may outperform the biased prophet. Notice that in our
example, the biased prophet is forced to see both $(2^{n/2-1},0)$ and
$(0,2^{n/2-1})$ as realized values, resulting in a reference point
$(2^{n/2-1},2^{n/2-1})$ – much larger than any value they could have chosen.
Consequently, the biased prophet has negative utility and is worse off
compared to the biased gambler. In contrast, in [11]’s model (where $k=1$),
the biased prophet is guaranteed to attain at least as much utility as that of
online agents.

##  4 Effects of Comparative Loss Aversion

In this section we formally analyze the effect of comparative loss aversion on
the biased gambler’s utility. Specifically, we compare the biased gambler’s
utility with those of both the rational prophet and rational gambler. We will
focus on the two extremes of arrival order constraints: adversarial order and
optimal order (even more specifically, we consider sequences drawn from an
i.i.d. prior distribution, where any arrival order is optimal). Under both
ordering constraints, we show a phase transition when the feature-amplified
bias $\lambda\cdot(k-1)$ is equal to one. When the feature-amplified bias
$\lambda(k-1)\geq 1$, the biased gambler’s prophet and online competitive
ratio are both equal to infinity. On the other hand, when the feature-
amplified bias $\lambda(k-1)<1$, the biased gambler can achieve a competitive
ratio that is only dependent on $\lambda$ and $k$, and of similar magnitude
under both ordering constraints.

It is surprising that our model exhibits similar behavior in terms of
competitive ratios regardless of constraints on arrival order. In contrast,
[11] shows that for the single dimensional model, assuming the arrival order
to be random rather than adversarial results in an exponential improvement in
utility guarantees in terms of $\lambda$.

Missing proofs and the complete version of the proof sketches in Section 4.1
and Section 4.2 can be found in Appendix A and Appendix B respectively.

###  4.1 Utility Loss under Adversarial Arrival Order

Firstly, we generalize Example 1 to show that when the feature-amplified bias
$\lambda\cdot(k-1)\geq 1$, as $n$ grows arbitrarily large, the prophet and
online utility ratios (namely, the ratio between expected utility from the
biased gambler and the expected utility from the rational prophet or gambler)
can be arbitrarily large. In particular, we construct a prior distribution
$\mathcal{F}_{0}(n)$, parameterized by the number of candidates $n$ such that,
when the feature-amplified bias $\lambda\cdot(k-1)>1$, both the prophet and
online utility ratio are exponential in terms of $n$. When the feature-
amplified bias $\lambda(k-1)=1$, we obtain a more conservative result that
prophet and online utility ratio can be linear in terms of $n$.
propositionclaimExpUtilityGap When the feature-amplified bias
$\lambda\cdot(k-1)>1$, for any $n\in N^{+}$, there exists a sequence $\sigma$
with $n$ candidates such that when the distribution $\mathcal{F}_{0}(n)$ takes
the values of $\sigma$ deterministically, i.e. with probability 1, and when
our prior distribution $\mathcal{F}$ equals $\mathcal{F}_{0}(n)$, the prophet
utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
and the online utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
are both equal to
$\Omega\left\lparen\left\lparen\lambda(k-1)\right\rparen^{\frac{n}{k}-1}\right\rparen$.

###### Proof Sketch.

The proposition can be proven by considering the following deterministic
distribution, where $\beta=\lambda\cdot(k-1)$:

$(1,0,\cdots,0)$, |  $(0,1,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,1)$,
---|---|---|---|---
$(\beta,0,\cdots,0)$, |  $(0,\beta,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,\beta)$,
$(\beta^{2},0,\cdots,0)$, |  $(0,\beta^{2},0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,\beta^{2})$,
|  | $\cdots$ |  |
$(\beta^{\lceil n/k\rceil-1},0,\cdots,0)$, |  $(0,\beta^{\lceil n/k\rceil-1},0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,\beta^{\lceil n/k\rceil-1},0,\cdots,0)$. |

While the rational prophet and gambler are able to get utility $\beta^{\lceil
n/k\rceil-1}$ by selecting an option in the last row, the biased gambler could
only get utility $1$, in particular by selecting the first option. ∎

propositionclaimLinearUtilityGap When the feature-amplified bias
$\lambda\cdot(k-1)=1$, for any $n\in\mathbb{N}^{+}$, there exists a sequence
$\sigma$ with $n$ candidates such that when the distribution
$\mathcal{F}_{0}(n)$ takes the values of $\sigma$ deterministically, i.e. with
probability 1, and when our prior distribution $\mathcal{F}$ equals
$\mathcal{F}_{0}(n)$, the prophet utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
and the online utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
are both equal to $\Omega\left\lparen\frac{n}{k}\right\rparen$.

###### Proof Sketch.

The proposition can be proven by considering the following deterministic
distribution:

$(1,0,\cdots,0)$, |  $(0,1,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,1)$,
---|---|---|---|---
$(2,0,\cdots,0)$, |  $(0,2,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,2)$,
$(3,0,\cdots,0)$, |  $(0,3,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,3)$,
|  | $\cdots$ |  |
$(\lceil\frac{n}{k}\rceil,0,\cdots,0)$, |  $(0,\lceil\frac{n}{k}\rceil,0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,\lceil\frac{n}{k}\rceil,0,\cdots,0)$. |

Here, the rational prophet and gambler are able to get utility $\lceil
n/k\rceil$, while the biased gambler could get utility no better than $1$. ∎

theoremthmadvInftyGap When the feature-amplified bias $\lambda\cdot(k-1)\geq
1$, the prophet and online competitive ratio are both equal to $\infty$.

###### Proof.

By Section 4.1 and Section 4.1 we know that when $\lambda\cdot(k-1)\geq 1$,
for any $n\in\mathbb{N}^{+}$, there exists a distribution $\mathcal{F}_{0}(n)$
such that the prophet and online utility ratio are $\Omega(\frac{n}{k})$ (note
that
$\Omega\left\lparen\left\lparen\lambda(k-1)\right\rparen^{\frac{n}{k}-1}\right\rparen=\omega(\frac{n}{k})$).
Thus for any $T\in\mathbb{N}$, there exists a $n\in\mathbb{N}^{+}$ such that
the prophet and online utility of $\mathcal{F}_{0}(n)$ both exceed $T$. Since
the prophet competitive ratio
$\max\limits_{\mathcal{F}}\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
is at least
$\max\limits_{n\in\mathbb{N}^{+}}\frac{\mathbb{E}_{\mathcal{F}_{0}(n)}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}_{0}(n)}\left[U^{*}_{g_{b}}\right]}$,
any $T\in\mathbb{N}$ serves as a lower bound to the prophet utilty gap, and
thus the prophet competitive ratio is equal to $\infty$. Similarly, the online
competitive ratio is equal to $\infty$. ∎

On the other hand, when the feature-amplified bias $\lambda(k-1)<1$, we prove
that the biased gambler, by using a simple threshold based algorithm, can get
at least a $\frac{1-\lambda(k-1)}{2+\lambda}$ fraction of the prophet’s
utility and a $\frac{1-\lambda(k-1)}{1+\lambda}$ fraction of the optimal
rational gambler’s utility regardless of the value of $n$. We also show that
both of these ratios are tight. More formally, we prove the following
theorems.

theoremthmLBOfflineBound When the feature-amplified bias
$\lambda\cdot(k-1)<1$, for any prior distribution $\mathcal{F}$, the inverse
of the prophet utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}\geq(1-\lambda(k-1))\cdot\max\left\\{\frac{\gamma}{1+\lambda+k},\frac{1}{2+\lambda}\right\\}$,
where
$\gamma=\frac{\mathbb{E}_{\mathcal{F}}[\sum_{j=1}^{k}S_{j}^{*}]}{\mathbb{E}_{\mathcal{F}}[V^{*}]}$.
Consequently, the prophet competitive ratio is at most
$\frac{2+\lambda}{1-\lambda(k-1)}$.

theoremthmLBOnlineBound When the feature-amplified bias $\lambda\cdot(k-1)<1$,
for any prior distribution $\mathcal{F}$, the online utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\leq\frac{1+\lambda}{(1-\lambda(k-1))}$.
Consequently, the online competitive ratio is at most
$\frac{1+\lambda}{1-\lambda(k-1)}$.

theoremthmUBBoundedUtility When the feature-amplified bias
$\lambda\cdot(k-1)<1$, for any $\delta\in(0,1)$, there exists a prior
distribution $\mathcal{F}$ such that the prophet utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}\right]}\geq\frac{2+\lambda}{1-\lambda(k-1)}\cdot(1-\delta)$
and that the online utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq\frac{1+\lambda}{1-\lambda(k-1)}\cdot(1-\delta)$.
Consequently, the prophet competitive ratio is at least
$\frac{2+\lambda}{1-\lambda(k-1)}$ and the online competitive ratio is at
least $\frac{1+\lambda}{1-\lambda(k-1)}$.

Our proof for Section 4.1 and Section 4.1 follows a similar outline to the
single dimensional case presented in Kleinberg et al. [11]. However, our
analysis deals with the additional complexity from having multiple dimensions,
and often requires a tighter analysis for intermediate terms in order to find
the exact competitive ratios. For instance, in Section 4.1, we require an
additional term when bounding prophet utility ratio (which will later be used
in Section 4.1) compared to a similar claim in [11].

We will start by defining threshold based algorithms.

######  Definition 4.1 (Thresholding algorithms.).

We define a thresholding algorithm parameterized by $\alpha\in(0,1)$ and
denoted $A^{\alpha}$ as follows. First, $A^{\alpha}$ sets threshold $T$ such
that $\alpha=\Pr\left[V^{*}\geq T\right]$ (recall that $V^{*}$ is defined as
the maximum value of all candidates). Next, during the selection process, the
algorithm will select the first candidate whose value
$\lVert\sigma^{(t)}\rVert_{1}$ is at least the threshold $T$. We will denote
the expected utility from $A^{\alpha}$ as
$\mathbb{E}_{\mathcal{F}}[U_{g_{b}}^{\alpha}]$.

We will now reason about the biased gambler’s utility from using a
thresholding algorithm $A^{\alpha}$. In the following two claims, we first
bound the utility (and regret) of a biased gambler that uses the thresholding
algorithm when they encounter a particular sequence of values $\sigma$. This
utility bound can then be used to bound the expected utility of the biased
gambler given the prior distribution of values.

claimclaimUtilityBound When the feature-amplified bias $\lambda\cdot(k-1)<1$,
for any sequence $\sigma$, for any threshold $T$, and for timestep $t$ such
that $t$ is the smallest timestep where $\lVert\sigma^{(t)}\rVert_{1}\geq T$,
it must be the case that
$U_{g_{b}}(\sigma,t)\geq\lVert\sigma^{(t)}\rVert_{1}-\lambda(k-1)\cdot T$.

claimclaimThresholdUtility When the feature-amplified bias
$\lambda\cdot(k-1)<1$, for any prior distribution $\mathcal{F}$ and any
$\alpha\in(0,1)$,
$\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\right]\geq\left\lparen(1+\lambda)\alpha-k\lambda\right\rparen\cdot
T+(1-\alpha)\cdot\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]$.

###### Proof Sketch.

Let $T$ be the threshold where $\alpha=\Pr\left[V^{*}\geq T\right]$, then $T$
is the threshold used by the algorithm $A^{\alpha}$. Observe that when the
gambler uses the algorithm $A^{\alpha}$, with probability $\alpha$ the
algorithm will select some item, and with probability $1-\alpha$ the algorithm
will select nothing.

Conditioned on $A^{\alpha}$ selecting no item, we know that all items have
value $<T$. Thus even at the end of the algorithm, the gambler’s value for the
super candidate must not exceed $k\cdot T$. This means that the gambler’s
utility is at least $-\lambda\cdot k\cdot T$. On the other hand, we can prove
by using Definition 4.1 that conditioned on $A^{\alpha}$ selecting an item at
step $t$, the gambler’s utility is at least $(1-\lambda(k-1))\cdot
T+\frac{\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]}{\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]}$. The proof of the claim then follows a standard argument for
prophet inequality where we take the expectation of agent utility over all
events (for all t: selecting an item at step $t$; selecting no item). ∎

We can now bound the utility ratio between a biased gambler using algorithm
$A^{\alpha}$ and the rational prophet, which can then be used to prove Section
4.1 and Section 4.1. It turns out that Section 4.1 and Section 4.1 requires
two different ways of bounding the the utility ratio.

lemmalemLBOfflineBound When the feature-amplified bias $\lambda\cdot(k-1)<1$,
for any prior distribution $\mathcal{F}$, there exists an $\alpha$ such that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}\geq(1-\lambda(k-1))\cdot\max\left\\{\frac{\gamma}{1+\lambda+k},\frac{1}{2+\lambda}\right\\}$,
where
$\gamma=\frac{\mathbb{E}_{\mathcal{F}}[\sum_{j=1}^{k}S_{j}^{*}]}{\mathbb{E}_{\mathcal{F}}[V^{*}]}$
(recall that $S_{j}^{*}$ denotes the maximum value in the sequence along
dimension $j$ and $V^{*}=\max\limits_{t}\lVert\sigma^{(t)}\rVert_{1}$).

###### Proof Sketch.

The key step in this lemma is to bound the term
$\displaystyle\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]$
from Definition 4.1.

Let us call $(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}$ the surplus from the
$t^{th}$ candidate. Note that
$\displaystyle\sum_{t\in[n]}\mathbb{E}_{\lVert\sigma^{(t)}\rVert_{1}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]$
is the sum over the expected surplus from each candidate. Thus, it must be at
least the expected surplus from the candidate with the largest overall value.
Moreover, it must be at least the sum over the expected surplus from
candidates that have the largest value on each individual dimension. Formally,
the following two inequalities always hold:

$\displaystyle\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]\geq\mathbb{E}_{\mathcal{F}}\left[(V^{*}-T)^{+}\right]\geq\mathbb{E}_{\mathcal{F}}\left[V^{*}-T\right],$
(1)

and

$\displaystyle\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]\geq\sum_{j=1}^{k}\mathbb{E}_{\mathcal{F}}\left[(S_{j}^{*}-T)^{+}\right]\geq\mathbb{E}_{\mathcal{F}}\left[\sum_{j=1}^{k}S_{j}^{*}\right]-k\cdot
T\geq\gamma\cdot\mathbb{E}_{\mathcal{F}}\left[V^{*}\right]-k\cdot T.$ (2)

Equation 1 and Equation 2 can then be used to bound the utility of the biased
gambler, and in particular its relation to the utility of the rational
prophet. ∎

We are now ready to prove Section 4.1 and Section 4.1.

###### Proof.

(of Section 4.1) The first line of the theorem follows directly by Definition
4.1 and the fact that
$\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]\geq\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\right]$.
(Because $\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]$ is defined as
the expected utility from a biased gambler that uses the utility optimal
online algorithm, $\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]$ is at
least the expected utility from a biased gambler using some specific online
algorithm).

Now we will derive the second line of the theorem. From the first line of the
theorem we know that for any prior distribution $\mathcal{F}$,

$\displaystyle\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}\geq(1-\lambda(k-1))\cdot\max\left\\{\frac{\gamma}{1+\lambda+k},\frac{1}{2+\lambda}\right\\}\geq\frac{1-\lambda(k-1))}{2+\lambda}.$

Hence, for any prior distribution $\mathcal{F}$, the prophet utilit ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
is at most $\frac{2+\lambda}{1-\lambda(k-1))}$. We conclude that the prophet
competitive ratio
$\max\limits_{\mathcal{F}}\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
is at most $\frac{2+\lambda}{1-\lambda(k-1))}$. ∎

###### Proof.

(of Section 4.1) Let
$\beta=\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
and let
$\Delta=\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}$.
Since
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\frac{\beta}{\Delta}$,
proving our theorem is equivalent to proving that
$\frac{\Delta}{\beta}\geq\frac{(1-\lambda(k-1))}{1+\lambda}$, and we will do
exactly this for the rest of the proof.

Firstly, let
$\gamma=\frac{\mathbb{E}_{\mathcal{F}}[\sum_{j=1}^{k}S_{j}^{*}]}{\mathbb{E}_{\mathcal{F}}[V^{*}]}$,
then by Section 4.1 we know that
$\frac{1}{\beta}=\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}\geq(1-\lambda(k-1))\cdot\frac{\gamma}{1+\lambda+k}$.

Next, because $\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]$ represents
the highest expected utility a biased gambler can gain from using an online
algorithm, $\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]$ must be at
least the expected utility a biased gambler can gain from using the value-
optimal online algorithm, which is equal to the optimal utility of a rational
gambler minus the loss aversion the biased gambler experience from using the
value-optimal online algorithm. Recall that $S_{j}^{*}$ is defined as the
maximum value on the $j^{th}$ dimension among all candidates, thus the value
of super candidate the biased gambler experiences loss aversion against must
be at most $\sum_{j=1}^{k}S_{j}^{*}$. Thus

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]\geq\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}-\lambda\cdot\left\lparen\sum_{j=1}^{k}S_{j}^{*}-U^{*}_{g_{r}}\right\rparen\right]=(1+\lambda)\cdot\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]-\lambda\cdot\mathbb{E}_{\mathcal{F}}\left[\sum_{j=1}^{k}S_{j}^{*}\right].$

By the definition of $\Delta$, we know that
$\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]=\frac{1}{\Delta}\cdot\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]$.
Similarly, by the definition of $\gamma$,
$\mathbb{E}_{\mathcal{F}}\left[\sum_{j=1}^{k}S_{j}^{*}\right]=\gamma\cdot\mathbb{E}_{\mathcal{F}}[V^{*}]=\gamma\cdot\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]$.
Therefore combining these two statements with the previous inequality we know
the following:

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]\geq\left\lparen\frac{1+\lambda}{\Delta}-\lambda\cdot\gamma\right\rparen\cdot\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right].$

Re-expressing algebraically, we have
$\frac{1}{\beta}=\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}\geq\left\lparen\frac{1+\lambda}{\Delta}-\lambda\cdot\gamma\right\rparen=\frac{1+\lambda-\lambda\cdot\gamma\cdot\Delta}{\Delta}$.

Now we have two bounds on $\frac{1}{\beta}$: we know that
$\frac{1}{\beta}\geq(1-\lambda(k-1))\cdot\frac{\gamma}{1+\lambda+k}$ and that
$\frac{1}{\beta}\geq\frac{1+\lambda-\lambda\cdot\gamma\cdot\Delta}{\Delta}$.
By these two bounds, we conclude that

$\displaystyle\frac{\Delta}{\beta}=\Delta\cdot\frac{1}{\beta}\geq\max\left\\{(1-\lambda(k-1))\cdot\frac{\Delta\cdot\gamma}{1+\lambda+k},\enspace
1+\lambda-\lambda\cdot\gamma\cdot\Delta\right\\}.$

Notice that inside the max bracket, the first term monotonically increases
with $\Delta$, while the second term monotonically decreases with $\Delta$,
therefore the minimum of the max of two terms occurs when the two terms are
equal, namely, when
$(1-\lambda(k-1))\cdot\frac{\Delta\cdot\gamma}{1+\lambda+k}=1+\lambda-\lambda\cdot\gamma\cdot\Delta$.
This is achieved when $\Delta=\frac{1+\lambda+k}{\gamma\cdot(1+\lambda)}$, at
which point

$\displaystyle(1-\lambda(k-1))\cdot\frac{\Delta\cdot\gamma}{1+\lambda+k}=1+\lambda-\lambda\cdot\gamma\cdot\Delta=\frac{1-\lambda(k-1)}{1+\lambda}.$

We thus conclude that it is always the case that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}=\frac{\Delta}{\beta}\geq\frac{1-\lambda(k-1)}{1+\lambda}$
regardless of the value of $\Delta$. ∎

We remain to discuss Section 4.1, which we prove by constructing a worst case
prior distribution. Our construction combines a generalization of Example 1
with the canonical two item example showing a $1/2$-competitive ratio for
classical prophet inequality. In our construction, all but the last candidate
has deterministic values constructed similarly to those in Example 1 (but the
value of the candidates grow much slower due to the fact that the feature-
amplified bias is less than one). The last candidate has a high value with a
very small probability, which is similar to constructions for classical
prophet inequality.

###### Proof Sketch.

(of Section 4.1) Let the first $n-1$ candidates have the following
deterministic value:

$(1,0,\cdots,0)$, |  $(0,1,0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1)$,
---|---|---|---
$(1+\beta,0,\cdots,0)$, |  $(0,1+\beta,0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1+\beta)$,
$(1+\beta+\beta^{2},0,\cdots,0)$, |  $(0,1+\beta+\beta^{2},0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1+\beta+\beta^{2})$,
| $\cdots$ |  |
$(\sum_{j=0}^{\lceil n/k\rceil-1}\beta^{j},0,\cdots,0)$, |  $(0,\sum_{j=0}^{\lceil n/k\rceil-1}\beta^{j},0,\cdots,0)$, |  $\cdots$, | $(0,\cdots,0,\sum_{j=0}^{\lceil n/k\rceil-1}\beta^{j}).$

Then, the last randomized candidate is equal to
$\left\lparen(1-\epsilon)(1+\lambda)\cdot\sum_{j=0}^{\lceil
n/k\rceil-1}\beta^{j}/\epsilon,0,\cdots,0\right\rparen$ with probability
$\epsilon$ and is equal to $(0,0,\cdots,0)$ with probability $1-\epsilon$. One
can then verify that the biased gambler can only get utility at most $1$,
since by the time the biased gambler reach the last randomized candidate,
their imaginary super candidate is too strong for the biased gambler to gain
positive expected utility from the randomized candidate. However, the rational
prophet can simply select the maximum between the best deterministic option
and the randomized option, getting utility that approaches
$\frac{2+\lambda}{1-\lambda(k-1)}$ as $\epsilon$ approaches $0$ and $n$
approaches $\infty$. Similarly, the rational gambler can simply always select
the randomized option and get utility that approaches and
$\frac{1+\lambda}{1-\lambda(k-1)}$. ∎

###  4.2 No Improvement Under Relaxed Arrival Order

We now show that most of our results for adversarial arrival order can be used
to derive analogous results for the case where the prior distribution is
i.i.d.

Specifically, in the next claim (4.4), we will show that removing repeated
candidate values from a sequence does not affect the biased gambler’s optimal
utility. We will then use the claim to establish in a subsequent lemma (Lemma
4.5) that for each deterministic distribution (i.e. each distribution such
that values drawn from it are equal to some sequence $\sigma$ with probability
$1$), we can find an i.i.d prior distribution $\mathcal{F}$ with a similar
realized sequence (after deleting duplicates), and hence similar prophet and
online utility ratio. As we have discussed in Section 3 and Section 4.1, the
construction of the worst case instances for the adversarial arrival order
setting is either a fully deterministic sequence, or with few randomized
options. Consequently, Lemma 4.5 can be leveraged to translate all lower
bounds on the utility ratios in adversarial setting into lower bounds in the
i.i.d setting.

######  Definition 4.2.

A sequence $\sigma$ is called succinct if there are no two identical
candidates in the sequence and no candidate’s value is a zero vector.

######  Definition 4.3.

The representation $r(\sigma)$ of a sequence $\sigma$ is the sequence of
unique elements in $\sigma$ ordered in the ascending order of their first
occurance in $\sigma$. (e.g. r(1, 2, 1, 2, 3) = 1, 2, 3.)

######  Claim 4.4.

$U_{p_{r}}(\sigma)=U_{p_{r}}(r(\sigma))$ and
$U_{g_{b}}(\sigma)=U_{g_{b}}(r(\sigma))$.

###### Proof.

It is clear that $U_{p_{r}}(\sigma)=U_{p_{r}}(r(\sigma))$ since $r(\sigma)$
contains all the unique elements in $\sigma$. Let $a$ be an arbitrary
candidate in $\sigma$, let $I_{a}$ be the set of all indices $t$ where
$\sigma^{(t)}=a$ and let $t_{a}$ be the minimum index in $I_{a}$. Let
$\sigma^{\prime}$ be the same sequence as $\sigma$ except for
$\lVert\sigma^{(t)}\rVert_{1}=0$ for all $t\in I_{a}\setminus\\{t_{a}\\}$. We
will show that $U_{g_{b}}(\sigma^{\prime})=U_{g_{b}}(\sigma)$.

Firstly, for any index $t$, the super candidate $s^{(t)}$ is only affected by
the set of unique candidates at indices $<t$. Therefore $s^{(t)}$ takes the
same value in $\sigma$ and $\sigma^{\prime}$ for any $t\not\in
I_{a}\setminus\\{t_{a}\\}$. As a result,
$U_{g_{b}}(\sigma,t)=U_{g_{b}}(\sigma^{\prime},t)$ for any $t\not\in
I_{a}\setminus\\{t_{a}\\}$.

Also, when seeing the same candidate value, having seen more candidates in the
past can only decrease the biased gambler’s utility. Thus for any $t\in
I_{a}$, $U_{g_{b}}(\sigma,t_{a})\geq U_{g_{b}}(\sigma,t)$. We conclude that
$U_{g_{b}}(\sigma)=\max_{t\in[n]}U_{g_{b}}(\sigma,t)=\max_{t\in[n]}(\sigma^{\prime},t)=U_{g_{b}}(\sigma^{\prime})$.

By applying the above construction repeatedly, we can arrive at a sequence
$\sigma^{*}$ where the only non zero entries are the first occurrence of each
candidate in $\sigma$. $r(\sigma)$ is simply the result of removing candidates
that have value $0$ from $\sigma^{*}$. Clearly, this operation does not affect
the biased gambler’s maximum utility. Thus
$U_{g_{b}}(r(\sigma))=U_{g_{b}}(\sigma^{*})=U_{g_{b}}(\sigma)$.

∎

######  Lemma 4.5.

For any $\epsilon\in(0,1)$, any succinct sequence $\sigma$ such that its
length $m=|\sigma|$ is greater than $1$, there exists a distribution
$\mathcal{F}$ where all candidates are i.i.d with support on the set
$\\{\sigma^{(1)},\cdots,\sigma^{(m)}\\}$ such that the prophet utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq(1-\epsilon)\cdot\frac{U_{p_{r}}(\sigma)}{U_{g_{b}}(\sigma)}$.

###### Proof.

Given an $x\in(0,1)$ that we will set later, consider a distribution
$\mathcal{D}$ that takes value $\sigma_{i}$ ($i^{th}$ candidate in the
sequence $\sigma$) with probability $\frac{x^{i-1}(1-x)}{1-x^{m}}$ for all
$i\in[m]$. First we will verify that $\mathcal{D}$ is a valid distribution
(namely, the probability sums up to be 1):

$\displaystyle\sum_{i=1}^{m}\frac{x^{i-1}(1-x)}{1-x^{m}}=\frac{1-x}{1-x^{m}}\sum_{i=1}^{m}x^{i-1}=\frac{1-x^{m}}{1-x}\cdot\frac{1-x}{1-x^{m}}=1.$

Now, let $\mathcal{F}=\times_{i\in[n]}\mathcal{D}$, where
$n=m^{\alpha(m-1)}\cdot\log^{\alpha}(m)$ for some $\alpha>1$ that we will set
later. Let $\widetilde{\sigma}$ be a sequence drawn from $\mathcal{F}$, from
4.4 we know that as long as $r(\widetilde{\sigma})=\sigma$, then
$U_{p_{r}}(\widetilde{\sigma})=U_{p_{r}}(\sigma)$ and
$U_{g_{b}}(\widetilde{\sigma})=U_{g_{b}}(\sigma)$. Furthermore, by
construction the maximum value in a sequence $\widetilde{\sigma}$ that is
drawn from $\mathcal{F}$ is at most the maximum value in $\sigma$,
consequently, $U_{g_{b}}(\widetilde{\sigma})\leq
U_{p_{r}}(\widetilde{\sigma})\leq U_{p_{r}}(\sigma)$. Therefore

$\displaystyle\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}$
$\displaystyle\leq\frac{\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})=\sigma\right]\cdot
U_{g_{b}}(\sigma)+\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})\neq\sigma\right]\cdot
U_{p_{r}}(\sigma)}{\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})=\sigma\right]\cdot
U_{p_{r}}(\sigma)}$
$\displaystyle\leq\frac{U_{g_{b}}(\sigma)}{U_{p_{r}}(\sigma)}+\frac{\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})\neq\sigma\right]}{\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})=\sigma\right]}.$

Now we want to bound the probability that $r(\widetilde{\sigma})\neq\sigma$.
There are two ways for this to happen, either $\widetilde{\sigma}$ does not
contain all candidates in $\sigma$, or $r(\widetilde{\sigma})$ is ordered
differently than $\sigma$. Formally, by union bound,

$\displaystyle\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})\neq\sigma\right]\leq\sum_{i\in[m]}\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[\sigma_{i}\not\in
r(\widetilde{\sigma})\right]+\sum_{i\in[m-1]}\Pr_{\widetilde{\sigma}\sim\mathcal{F}}[\sigma_{i+1}\text{
occur before }\sigma_{i}\text{ in
}r(\widetilde{\sigma})\,|\,\mathopen{}\sigma_{i},\sigma_{i+1}\in
r(\widetilde{\sigma})].$

Firstly, we bound the probability that $\widetilde{\sigma}$ does not contain
$\sigma_{i}$ as follows

$\displaystyle\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[\sigma_{i}\not\in
r(\widetilde{\sigma})\right]=\left\lparen
1-\frac{x^{i-1}(1-x)}{1-x^{m}}\right\rparen^{n}\leq\left\lparen
1-\frac{x^{m-1}(1-x)}{1-x^{m}}\right\rparen^{n}\leq\left\lparen
1-x^{m-1}\right\rparen^{n}.$

Next, let $r_{i,i+1}(\widetilde{\sigma})$ denote the smallest index $j$ such
that $\widetilde{\sigma}_{j}=\sigma_{i}$ or $\sigma_{i+1}$.

$\displaystyle\Pr_{\widetilde{\sigma}\sim\mathcal{F}}[\sigma_{i+1}\text{ occur
before }\sigma_{i}\text{ in
}r(\widetilde{\sigma})\,|\,\mathopen{}\sigma_{i},\sigma_{i+1}\in
r(\widetilde{\sigma})]$
$\displaystyle=\Pr_{\widetilde{\sigma}\sim\mathcal{F}}[\widetilde{\sigma}_{r_{i,i+1}(\widetilde{\sigma})}=\sigma_{i+1}\,|\,\mathopen{}\sigma_{i},\sigma_{i+1}\in
r(\widetilde{\sigma})]$
$\displaystyle=\Pr_{v\sim\mathcal{D}}[v=\sigma_{i+1}\,|\,\mathopen{}v\in\\{\sigma_{i+1},\sigma_{i}\\}]$
$\displaystyle=\frac{\frac{x^{i-1}(1-x)}{1-x^{m}}}{\frac{x^{i-1}(1-x)}{1-x^{m}}+\frac{x^{i}(1-x)}{1-x^{m}}}=\frac{x}{x+1}.$

Now we set $x=m^{-\alpha}$, and conclude that

$\displaystyle\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})\neq\sigma\right]$
$\displaystyle\leq m\cdot\left\lparen
1-x^{m-1}\right\rparen^{n}+(m-1)\cdot\frac{x}{x+1}$ $\displaystyle\leq
m\cdot\left\lparen
1-m^{-\alpha\cdot(m-1)}\right\rparen^{m^{\alpha(m-1)}\cdot\log^{\alpha}(m)}+(m-1)\cdot
m^{-\alpha}$ $\displaystyle\leq m\cdot m^{-\alpha}+(m-1)\cdot m^{-\alpha}$
$\displaystyle\leq m^{-(\alpha-1)}+m^{-(\alpha-1)}.$

By choosing $\alpha=\log_{m}\left\lparen\frac{U_{p_{r}}(\sigma)}{\epsilon\cdot
U_{g_{b}}(\sigma)}\right\rparen+2$, the above entity is
$<\epsilon\cdot\frac{U_{g_{b}}(\sigma)}{U_{p_{r}}(\sigma)}$, thus

$\displaystyle\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}$
$\displaystyle\leq\frac{U_{g_{b}}(\sigma)}{U_{p_{r}}(\sigma)}+\frac{\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})\neq\sigma\right]}{\Pr_{\widetilde{\sigma}\sim\mathcal{F}}\left[r(\widetilde{\sigma})=\sigma\right]}\leq\frac{U_{g_{b}}(\sigma)}{U_{p_{r}}(\sigma)}+\frac{\epsilon\cdot\frac{U_{g_{b}}(\sigma)}{U_{p_{r}}(\sigma)}}{1-\epsilon\cdot\frac{U_{g_{b}}(\sigma)}{U_{p_{r}}(\sigma)}}.$

Since $\frac{U_{g_{b}}(\sigma)}{U_{p_{r}}(\sigma)}$ is at most $1$, we
conclude that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}\leq\left\lparen
1+\frac{\epsilon}{1-\epsilon}\right\rparen\cdot\frac{U_{g_{b}}(\sigma)}{U_{p_{r}}(\sigma)}$.
Consequently,

$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq(1-\epsilon)\cdot\frac{U_{p_{r}}(\sigma)}{U_{g_{b}}(\sigma)}.$

∎

We can now use Lemma 4.5 to prove that when the candidate values are i.i.d, it
is also the case that when the feature-amplified bias $\lambda(k-1)\geq 1$,
prophet and online utility ratios can get progressively worse as the number of
candidates $n$ increases, and as a result, both the prophet and online
competitive ratio are equal to $\infty$.

propositionclaimIIDExpUtilityGap When the feature-amplified bias
$\lambda\cdot(k-1)>1$, for all $n\in\mathbb{N}^{+}$, there exists a prior
distribution $\mathcal{F}_{0}(n)$ where all candidates are i.i.d such that
when $\mathcal{F}=\mathcal{F}_{0}(n)$, the prophet utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
and the online utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
are both equal to
$\Omega\left\lparen(\lambda(k-1))^{f(\lambda,k)\cdot\log^{\frac{1}{2}}n}\right\rparen$,
where $f(\lambda,k)$ is a function that only depends on $\lambda$ and $k$.

###### Proof Sketch.

Let $\sigma(m)$ be the adversarial sequence considered in Section 4.1 of
length $m$. Then
$\frac{U_{p_{r}}(\sigma(m))}{U_{g_{b}}(\sigma(m))}=\Omega\left\lparen(\lambda(k-1))^{\frac{m}{k}-1}\right\rparen$.
By construction $\sigma(m)$ contains distinct entries, and thus is succinct.
Thus by Lemma 4.5, we can construct a randomized and i.i.d distribution
$\mathcal{F}$ with $n=m^{\alpha(m-1)}\cdot\log^{\alpha}(m)$ candidates where
$\alpha=\log_{m}\left\lparen\frac{(\lambda(k-1))^{\frac{m}{k}-1}}{\epsilon}\right\rparen+2$
that has a similar prophet and online utility ratio (within $\epsilon$
multiplicative difference). A careful relation between $n$ and $m$ then proves
the claim. ∎

propositionclaimIIDlogUtilityGap When the feature-amplified bias
$\lambda\cdot(k-1)=1$, for all $n\in\mathbb{N}^{+}$, there exists a prior
distribution $\mathcal{F}_{0}(n)$ where all candidates are i.i.d such that
when $\mathcal{F}=\mathcal{F}_{0}(n)$, the prophet utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
and the online utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
are both equal to $\Omega\left\lparen\frac{\log n}{k\cdot\log\log
n}\right\rparen$.

###### Proof Sketch.

The proof follows similarly to Lemma 4.5, except that we consider the
adversarial sequence $\sigma(m)$ from Section 4.1, which has a prophet and
online utility ratio of $\Omega(\frac{m}{k})$. ∎

theoremthmIIDInftyGap In the i.i.d prior distribution setting, when the
feature-amplified bias $\lambda\cdot(k-1)\geq 1$, the prophet and online
competitive ratio are both equal to $\infty$.

On the other hand, when the feature-amplified bias $\lambda(k-1)<1$, we can
utilize Lemma 4.5 to show a lower bound for the prophet and online competitive
ratios that matches those in the adversarial setting within constant factors.
claimclaimUBBoundedUtilityIID When the feature-amplified bias
$\lambda(k-1)<1$, for any $\delta\in(0,1)$, there exists an i.i.d prior
distribution $\mathcal{F}$ where the prophet utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq(1-\delta)\cdot\frac{1}{(1-\lambda(k-1))}$.

###### Proof Sketch.

We will consider a sequence of length $m$ that is similar to the mostly
deterministic distribution considered in theorem 4.1, except that the last
candidate, which has randomized value, is excluded. Specifically, let $\sigma$
be the following sequence:

$(1,0,\cdots,0)$, |  $(0,1,0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1)$,
---|---|---|---
$(1+\beta,0,\cdots,0)$, |  $(0,1+\beta,0,\cdot(1-\lambda(k-1))(1+\delta)s,0)$, |  $\cdots$, |  $(0,\cdots,0,1+\beta)$,
$(1+\beta+\beta^{2},0,\cdots,0)$, |  $(0,1+\beta+\beta^{2},0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1+\beta+\beta^{2})$,
| $\cdots$ |  |
$(\sum_{i=0}^{\lceil\frac{m}{k}\rceil-1}\beta^{i},0,\cdots,0)$, |  $(0,\sum_{i=0}^{\lceil\frac{m}{k}\rceil-1}\beta^{i},0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,\sum_{i=0}^{\lceil\frac{m}{k}\rceil-1}\beta^{i})$.

For a deterministic distribution equal to $\sigma$, the prophet utility ratio
is $\frac{1}{1-\lambda(k-1)}$. We will then apply Lemma 4.5 to obtain an i.i.d
distribution with a larger number of candidates that has a similar prophet
utility ratio. ∎

theorem thmUBBoundedUtilityIID When the feature-amplified bias
$\lambda(k-1)<1$ and $k>1$, for any $\delta\in(0,1)$, there exists an i.i.d
prior distribution $\mathcal{F}$ where the prophet utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq\frac{(1-\delta)}{3}\cdot\frac{2+\lambda}{1-\lambda(k-1)}$
and the online utility ratio
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq\frac{(1-\delta)}{4}\cdot\frac{1+\lambda}{1-\lambda(k-1)}$.
Consequently, the prophet competitive ratio is at least
$\frac{1}{3}\cdot\frac{2+\lambda}{(1-\lambda(k-1))}$ and the online
competitive ratio is at least
$\frac{1}{4}\cdot\frac{1+\lambda}{(1-\lambda(k-1))}$.

###### Proof.

By Lemma 4.5, there exists an i.i.d prior distribution $\mathcal{F}$ such that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq(1-\delta)\cdot\frac{1}{(1-\lambda(k-1))}$.
Combining this with 2.4, we have
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq\frac{(1-\delta)}{2}\cdot(1-\lambda(k-1))$.

Since $\lambda(k-1)<1$ and $k>1$, it must be the case that $2+\lambda<3$ and
that $1+\lambda<2$. Hence
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq\frac{(1-\delta)}{3}\cdot\frac{2+\lambda}{1-\lambda(k-1)}$
and
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq\frac{(1-\delta)}{4}\cdot\frac{1+\lambda}{1-\lambda(k-1)}$.
This implies that the upper bound matches the lower bounds proved for
adversarial setting within constant factors. ∎

##  5 Conclusion and Directions for Future Work

We consider an online decision-maker who suffers from comparative loss
aversion. Our model is identical to that of [11], _except_ for how the
reference point is formed. This change alone accounts for fundamental
differences in conclusions. For example, even the prophet suffers loss in our
model, and this enables novel phenomena to occur. Additionally, the loss due
to bias in our model can be unboundedly bad, and is not significantly
mitigated by assumptions on the prophet inequality arrival order.

Empirically observed biases have only recently been incorporated into research
on optimal stopping. Our work takes a step beyond [11] and uncovers new
phenomena by changing just one aspect of their model. An important direction
for future work is to continue developing models that uncover additional
phenomena of behavioral game theory (one such possibility is those studied in
[21], where adding inferior options can influence decision-making).

## References

  * Beyhaghi et al. [2018] Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme, Martin Pal, and Balasubramanian Sivan.  Improved approximations for free-order prophets and second-price auctions.  _CoRR_ , abs/1807.03435, 2018.  URL http://arxiv.org/abs/1807.03435.
  * Brenner et al. [1999] Lyle Brenner, Yuval Rottenstreich, and Sanjay Sood.  Comparison, grouping, and preference.  _Psychological Science_ , 10(3):225–229, 1999\.
  * Chernev et al. [2015] Alexander Chernev, Ulf Böckenholt, and Joseph Goodman.  Choice overload: A conceptual review and meta-analysis.  _Journal of Consumer Psychology_ , 25(2):333–358, 2015.
  * Correa et al. [2017] José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld.  Posted price mechanisms for a random stream of customers.  In _Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017_ , pages 169–186, 2017\.  doi: 10.1145/3033274.3085137.  URL https://doi.org/10.1145/3033274.3085137.
  * Duetting et al. [2017] Paul Duetting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier.  Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs.  In _58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017_ , pages 540–551, 2017.  doi: 10.1109/FOCS.2017.56.  URL https://doi.org/10.1109/FOCS.2017.56.
  * Ehsani et al. [2018] Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla.  Prophet secretary for combinatorial auctions and matroids.  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018_ , pages 700–714, 2018.  doi: 10.1137/1.9781611975031.46.  URL https://doi.org/10.1137/1.9781611975031.46.
  * Esfandiari et al. [2015] Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh.  Prophet secretary.  In _Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings_ , pages 496–508, 2015.  doi: 10.1007/978-3-662-48350-3“˙42.  URL https://doi.org/10.1007/978-3-662-48350-3_42.
  * Haynes [2009] Graeme A Haynes.  Testing the boundaries of the choice overload phenomenon: The effect of number of options and time pressure on decision difficulty and satisfaction.  _Psychology & Marketing_, 26(3):204–212, 2009\.
  * Hill and Kertz [1982] Theodore P. Hill and Robert P. Kertz.  Comparisons of stop rule and supremum expectations of i.i.d. random variables.  _The Annals of Probability_ , 10:336–345, 1982.
  * Kahneman and Tversky [2013] Daniel Kahneman and Amos Tversky.  Prospect theory: An analysis of decision under risk.  In _Handbook of the fundamentals of financial decision making: Part I_ , pages 99–127. World Scientific, 2013.
  * Kleinberg et al. [2021] Jon Kleinberg, Robert Kleinberg, and Sigal Oren.  Optimal stopping with behaviorally biased agents: The role of loss aversion and changing reference points.  _arXiv preprint arXiv:2106.00604_ , 2021.
  * Kleinberg and Weinberg [2012] Robert Kleinberg and S. Matthew Weinberg.  Matroid prophet inequalities.  In _Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012_ , pages 123–136, 2012.  doi: 10.1145/2213977.2213991.  URL https://doi.org/10.1145/2213977.2213991.
  * Krengel and Sucheston [1978] Ulrich Krengel and Louis Sucheston.  On semiamarts, amarts, and processes with finite value.  _Advances in Probability and Related Topics_ , 4:197–266, 1978.
  * Park and Jang [2013] Jeong-Yeol Park and SooCheong Shawn Jang.  Confused by too many choices? choice overload in tourism.  _Tourism Management_ , 35:1–12, 2013.
  * Rubinstein [2016] Aviad Rubinstein.  Beyond matroids: secretary problem and prophet inequality with general constraints.  In _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ , pages 324–332, 2016.  doi: 10.1145/2897518.2897540.  URL https://doi.org/10.1145/2897518.2897540.
  * Rubinstein and Singla [2017] Aviad Rubinstein and Sahil Singla.  Combinatorial prophet inequalities.  In _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19_ , pages 1671–1687, 2017.  doi: 10.1137/1.9781611974782.110.  URL https://doi.org/10.1137/1.9781611974782.110.
  * Sagi and Friedland [2007] Adi Sagi and Nehemia Friedland.  The cost of richness: The effect of the size and diversity of decision sets on post-decision regret.  _Journal of personality and social psychology_ , 93(4):515, 2007.
  * Samuel-Cahn [1984] Ester Samuel-Cahn.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  _Annals of Probability_ , 12(4):1213–1216, 1984\.
  * Schunk and Winter [2009] Daniel Schunk and Joachim Winter.  The relationship between risk attitudes and heuristics in search tasks: A laboratory experiment.  _Journal of Economic Behavior & Organization_, 71(2):347–360, 2009.
  * Schwartz [2004] Barry Schwartz.  The paradox of choice: Why more is less.  Ecco New York, 2004.
  * Simonson and Tversky [1992] Itamar Simonson and Amos Tversky.  Choice in context: Tradeoff contrast and extremeness aversion.  _Journal of marketing research_ , 29(3):281–295, 1992.
  * Tversky and Kahneman [1991] Amos Tversky and Daniel Kahneman.  Loss aversion in riskless choice: A reference-dependent model.  _The quarterly journal of economics_ , 106(4):1039–1061, 1991.
  * Yan [2011] Qiqi Yan.  Mechanism design via correlation gap.  In Dana Randall, editor, _Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011_ , pages 710–719. SIAM, 2011\.  doi: 10.1137/1.9781611973082.56.  URL https://doi.org/10.1137/1.9781611973082.56.

##  Appendix A Omitted Proofs of Section 4.1

*

###### Proof.

Let $\beta=\lambda\cdot(k-1)$, consider a sequence $\sigma$ with $n$
candidates where the $t^{th}$ candidate takes value $\sigma^{(t)}$ such that
for dimension $j=(t\mod k)$,
$\sigma^{(t)}_{j}=\beta^{\lceil\frac{t}{k}\rceil-1}$ and for any dimension
$j\neq(t\mod k)$, $\sigma^{(t)}_{j}=0$. Below is a more intuitive
representation of the sequence $\sigma$:

$(1,0,\cdots,0)$, |  $(0,1,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,1)$,
---|---|---|---|---
$(\beta,0,\cdots,0)$, |  $(0,\beta,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,\beta)$,
$(\beta^{2},0,\cdots,0)$, |  $(0,\beta^{2},0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,\beta^{2})$,
|  | $\cdots$ |  |
$(\beta^{\lceil n/k\rceil-1},0,\cdots,0)$, |  $(0,\beta^{\lceil n/k\rceil-1},0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,\beta^{\lceil n/k\rceil-1},0,\cdots,0)$. |

Clearly, if the biased gambler selects the first candidate, they will get
utility $1$. Further, we will show that the biased gambler gets utility at
most $0$ whenever it accepts a candidate that is not the first candidate.

Firstly, observe that for any fixed $i$, among all the candidates in $i^{th}$
row, the biased gambler’s utility for the first candidate in $i^{th}$ row is
the highest. This is because the gambler has the same value for all candidates
in $i^{th}$ row, however, the super candidate’s value increases as the gambler
sees more items, and thus the utility of the gambler decreases as they see
more items in the same row.

Thus it suffices for us to consider the biased gambler’s utility when they
accept the first candidate in the $i^{th}$ row of the above matrix for some
$i>0$. In this case, the super candidate $s^{((i-1)\cdot
k+1)}=(\beta^{i-1},\beta^{i-2},\cdots,\beta^{i-2})$. We conclude that

$\displaystyle U_{g_{b}}(\sigma,(i-1)\cdot k+1)$
$\displaystyle=\lVert\sigma^{((i-1)\cdot
k+1)}\rVert_{1}-\lambda\cdot\left\lparen\lVert s^{((i-1)\cdot
k+1)}\rVert_{1}-\lVert\sigma^{((i-1)\cdot k+1)}\rVert_{1}\right\rparen$
$\displaystyle=\beta^{i-1}-\lambda\cdot(k-1)\cdot\beta^{i-2}=\beta^{i-1}-\beta\cdot\beta^{i-2}=0.$

Thus, under $\sigma$, the optimal strategy for the biased gambler is to accept
the very first candidate, yielding
$\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]=1$. Meanwhile, the
rational prophet’s expected utility
$\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]$ is equal to the expected
largest value, which is
$\beta^{\lceil\frac{n}{k}\rceil-1}\geq\left\lparen\lambda(k-1)\right\rparen^{\frac{n}{k}-1}$.
Thus
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\Omega\left\lparen\left\lparen\lambda(k-1)\right\rparen^{\frac{n}{k}-1}\right\rparen$.

By claim 2.4 this immediately implies that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\Omega\left\lparen\left\lparen\lambda(k-1)\right\rparen^{\frac{n}{k}-1}\right\rparen$
as well. ∎

*

###### Proof.

We will consider a sequence $\sigma$ with $n$ candidates where the $t^{th}$
candidate takes value $\sigma^{(t)}$ such that for dimension $j=(t\mod k)$,
$\sigma^{(t)}_{j}=\lceil\frac{t}{k}\rceil$ and for any dimension $j\neq(t\mod
k)$, $\sigma^{(t)}_{j}=0$. Below is a more intuitive representation of the
sequence $\sigma$:

We will consider an example similar to the one in claim 4.1, where $\sigma$ is
equal to the following sequence:

$(1,0,\cdots,0)$, |  $(0,1,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,1)$,
---|---|---|---|---
$(2,0,\cdots,0)$, |  $(0,2,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,2)$,
$(3,0,\cdots,0)$, |  $(0,3,0,\cdots,0)$, |  $\cdots$, |  $\cdots$, |  $(0,\cdots,0,3)$,
|  | $\cdots$ |  |
$(\lceil\frac{n}{k}\rceil,0,\cdots,0)$, |  $(0,\lceil\frac{n}{k}\rceil,0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,\lceil\frac{n}{k}\rceil,0,\cdots,0)$. |

We will show that the biased gambler gets utility at most $1$ no matter what
candidate they accept.

For the same reason as in claim 4.1 it suffice for us to consider the biased
gambler’s utility when they accept the first candidate in the $i^{th}$ row of
the above matrix. In this case, the super candidate $s^{((i-1)\cdot
k+1)}=(i,i-1,\cdots,i-1)$. Thus

$\displaystyle U_{g_{b}}(\sigma,(i-1)\cdot k+1)$
$\displaystyle=\lVert\sigma^{((i-1)\cdot
k+1)}\rVert_{1}-\lambda\cdot\left\lparen\lVert s^{((i-1)\cdot
k+1)}\rVert_{1}-\lVert\sigma^{((i-1)\cdot k+1)}\rVert_{1}\right\rparen$
$\displaystyle=i-\lambda\cdot(k-1)\cdot(i-1)=i-(i-1)=1.$

Thus, under $\sigma$, one of the optimal strategies for the biased gambler is
to accept the very first candidate, yielding
$\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]=U_{g_{b}}(\sigma,1)=1$. On
the other hand, the rational prophet’s expected utility
$\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]$ is equal to the expected
largest value, which is at least $\frac{n}{k}$. Thus
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\Omega(\frac{n}{k})$.
By claim 2.4, this immediately implies that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\Omega(\frac{n}{k})$
as well. ∎

*

###### Proof.

We know by definition that

$\displaystyle U_{g_{b}}(\sigma,t)$
$\displaystyle=\lVert\sigma^{(t)}\rVert_{1}-\lambda\cdot(\lVert\vec{s}^{(t)}\rVert_{1}-\lVert\sigma^{(t)}\rVert_{1})$
$\displaystyle=\lVert\sigma^{(t)}\rVert_{1}-\lambda\cdot(\lVert\vec{s}^{(t)}\rVert_{1}-\lVert\sigma^{(t)}\rVert_{1})=(1+\lambda)\cdot\lVert\sigma^{(t)}\rVert_{1}-\lambda\cdot\lVert\vec{s}^{(t)}\rVert_{1}.$

Since $t$ is the smallest timestep where $\lVert\sigma^{(t)}\rVert_{1}\geq T$,
we know that $\lVert\sigma^{(t^{\prime})}\rVert_{1}<T$ for any $t^{\prime}<t$.
Thus, the value at any particular index of the super candidate at step $t-1$
is at most $T$. As a result, for any $j$,
$\lVert\vec{s}^{(t)}_{j}\rVert_{1}\leq\max(\lVert\sigma^{(t)}_{j}\rVert_{1},\lVert\vec{s}^{(t-1)}_{j}\rVert_{1})\leq\max(\lVert\sigma^{(t)}_{j}\rVert_{1},T)$.
This implies that

$\displaystyle\lVert\vec{s}^{(t)}\rVert_{1}=\sum_{j}\vec{s}^{(t)}_{j}\leq\sum_{j}\max(\sigma^{(t)}_{j},T)$
$\displaystyle=\sum_{j}T+\sum_{j}\left\lparen\sigma^{(t)}_{j}-T\right\rparen^{+}.$

Observe that since $\lVert\sigma^{(t)}\rVert_{1}-T\geq 0$, in the case where
for all $j$, $\lVert\sigma^{(t)}\rVert_{1}-T<0$,
$\sum_{j}\left\lparen\sigma^{(t)}_{j}-T\right\rparen^{+}=0\leq\lVert\sigma^{(t)}\rVert_{1}\geq
T$. On the other hand, when for at least one dimension $j^{*}$,
$\lVert\sigma^{(t)}\rVert_{1}-T\geq 0$, we can write
$\sum_{j}\left\lparen\sigma^{(t)}_{j}-T\right\rparen^{+}=\sigma^{(t)}_{j^{*}}-T+\sum_{j\neq
j^{*}}\left\lparen\sigma^{(t)}_{j}-T\right\rparen^{+}$, which is at most
$\sigma^{(t)}_{j^{*}}-T+\sum_{j\neq
j^{*}}\sigma^{(t)}_{j}=\lVert\sigma^{(t)}\rVert_{1}-T$. We thus conclude that

$\displaystyle\lVert\vec{s}^{(t)}\rVert_{1}\leq k\cdot
T+(\lVert\sigma^{(t)}\rVert_{1}-T)=\lVert\sigma^{(t)}\rVert_{1}+(k-1)\cdot T.$

Combining everything together, we get that

$\displaystyle
U_{g_{b}}(\sigma,t)=(1+\lambda)\cdot\lVert\sigma^{(t)}\rVert_{1}-\lambda\cdot\lVert\vec{s}^{(t)}\rVert_{1}$
$\displaystyle\geq(1+\lambda)\cdot\lVert\sigma^{(t)}\rVert_{1}-\lambda\cdot(\lVert\sigma^{(t)}\rVert_{1}+(k-1)\cdot
T)$ $\displaystyle\geq\lVert\sigma^{(t)}\rVert_{1}-\lambda(k-1)\cdot T.$

∎

*

###### Proof.

Let $T$ be the threshold where $\alpha=\Pr\left[V^{*}\geq T\right]$, then $T$
is the threshold used by the algorithm $A^{\alpha}$. Observe that when the
gambler uses the algorithm $A^{\alpha}$, with probability $\alpha$ the
algorithm will select some item, and with probability $1-\alpha$ the algorithm
will select nothing.

Conditioned on $A^{\alpha}$ selecting no item, we know that all items have
value $<T$. Thus even at the end of the algorithm, the gambler’s value for the
super candidate must not exceed $k\cdot T$. This means that the gambler’s
utility is at least $-\lambda\cdot k\cdot T$.

On the other hand, we will prove by using claim 4.1 that conditioned on
$A^{\alpha}$ selecting an item at step $t$, the gambler’s utility is at least
$\lVert\sigma^{(t)}\rVert_{1}-\lambda(k-1)\cdot T$. We will begin by showing a
block of formal deduction, which we subsequently unpack in the following
paragraphs.

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\,\middle|\,\mathopen{}A^{\alpha}\text{
selects item }t\right]$
$\displaystyle=\mathbb{E}_{\sigma\sim\mathcal{F}}\left[U_{g_{b}}(\sigma,t)\,\middle|\,\mathopen{}t=\operatorname*{argmin}_{i\in[n]}\\{\lVert\sigma^{(i)}\rVert_{1}\geq
T\\}\right]$
$\displaystyle\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t)}\rVert_{1}-\lambda(k-1)\cdot
T\,\middle|\,\mathopen{}t=\operatorname*{argmin}_{i\in[n]}\\{\lVert\sigma^{(i)}\rVert_{1}\geq
T\\}\right]$ $\displaystyle\geq(1-\lambda(k-1))\cdot
T+\mathbb{E}_{\sigma\sim\mathcal{F}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\,\middle|\,\mathopen{}\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]$ $\displaystyle\geq(1-\lambda(k-1))\cdot
T+\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\,\middle|\,\mathopen{}\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]$ $\displaystyle\geq(1-\lambda(k-1))\cdot
T+\frac{\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]}{\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]}.$

In the above argument, the first line is due to $A^{\alpha}$ selecting the
first candidate with value at least $T$. Furthermore, the second line follows
from the first line due to claim 4.1. The second line to the third line is
because the value of the candidates are independent, and thus “$\sigma^{(t)}$
is the first candidate that has value at least $T$” and “$\sigma^{(t)}$ has
value at least $T$” have equivalent implications for the value of
$\sigma^{(t)}$. The fourth line follows from the third because our formula
only involves $\sigma^{(t)}$ and thus the expectation over $\sigma$ drawn from
$\mathcal{F}$ is equivalent to the expectation over $\sigma^{(t)}$ drawn from
$\mathcal{F}_{t}$. The forth line to the fifth line is because when
$\lVert\sigma^{(t)}\rVert_{1}<T$, $(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}$ takes
the value $0$, thus

$\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]=\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\,\middle|\,\mathopen{}\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]\cdot\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq T\right].$

We will now bound the expected utility of the biased gambler when they use the
algorithm $A^{\alpha}$. The argument is presented in the inequalities
immediately below, which will be unpacked in the following paragraphs.

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\right]$
$\displaystyle=\Pr\left[U_{g_{b}}^{\alpha}\text{ selects no
item}\right]\cdot(-k\lambda\cdot
T)+\sum_{t\in[n]}\Pr\left[U_{g_{b}}^{\alpha}\text{ selects item
}j\right]\cdot\mathbb{E}\left[U_{g_{b}}^{\alpha}\,\middle|\,\mathopen{}A^{\alpha}\text{
selects item }j\right]$ $\displaystyle\geq(1-\alpha)\cdot(-k\lambda\cdot
T)+\sum_{t\in[n]}\Pr\left[U_{g_{b}}^{\alpha}\text{ selects item
}t\right]\cdot\left\lparen(1-\lambda(k-1))\cdot
T+\frac{\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]}{\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]}\right\rparen$ $\displaystyle\geq(1-\alpha)\cdot(-k\lambda\cdot
T)+\alpha\cdot(1-\lambda(k-1))\cdot T$
$\displaystyle\quad\quad\quad\quad+(1-\alpha)\cdot\sum_{t\in[n]}\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]\cdot\frac{\mathbb{E}_{\sigma^{(t)}_{1}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert-T)^{+}\right]}{\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]}$
$\displaystyle\geq\left\lparen(1+\lambda)\alpha-k\lambda\right\rparen\cdot
T+(1-\alpha)\cdot\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right].$

For the above equation, the first and second line is just summing over all
possible conditions and using inequalities that we established previous. The
second line to the third line is because
$\sum_{t\in[n]}\Pr\left[U_{g_{b}}^{\alpha}\text{ selects item
}j\right]=\alpha$ and the following inequalities,

$\displaystyle\Pr\left[U_{g_{b}}^{\alpha}\text{ selects item }t\right]$
$\displaystyle=\Pr\left[\forall
i<t,\lVert\sigma^{(i)}\rVert_{1}<T\right]\cdot\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]$ $\displaystyle\geq\Pr\left[\forall
i\in[n],\lVert\sigma^{(i)}\rVert_{1}<T\right]\cdot\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq
T\right]=(1-\alpha)\cdot\Pr\left[\lVert\sigma^{(t)}\rVert_{1}\geq T\right].$

The third line to the fourth line is simply due to a cancellation of terms. ∎

*

###### Proof.

Let $\alpha\in(0,1)$ be a fixed value that we will set later. By claim 4.1, we
know that

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\right]\geq\left\lparen(1+\lambda)\alpha-k\lambda\right\rparen\cdot
T+(1-\alpha)\cdot\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right].$

In order to further reason about the above quantity, we need to bound
$\displaystyle\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]$,
which is what we will do next.

Let us call $(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}$ the surplus from the
$t^{th}$ candidate. Note that
$\displaystyle\sum_{t\in[n]}\mathbb{E}_{\lVert\sigma^{(t)}\rVert_{1}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]$
is the sum over the expected surplus from each candidate. Thus, it must be at
least the expected surplus from the candidate with the largest overall value.
Moreover, it must be at least the sum over the expected surplus from
candidates that have the largest value on each individual dimension. Formally,
the following two inequalities always hold:

$\displaystyle\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]\geq\mathbb{E}_{\mathcal{F}}\left[(V^{*}-T)^{+}\right]\geq\mathbb{E}_{\mathcal{F}}\left[V^{*}-T\right],$
(3)

and

$\displaystyle\sum_{t\in[n]}\mathbb{E}_{\sigma^{(t)}\sim\mathcal{F}_{t}}\left[(\lVert\sigma^{(t)}\rVert_{1}-T)^{+}\right]\geq\sum_{j=1}^{k}\mathbb{E}_{\mathcal{F}}\left[(S_{j}^{*}-T)^{+}\right]\geq\mathbb{E}_{\mathcal{F}}\left[\sum_{j=1}^{k}S_{j}^{*}\right]-k\cdot
T\geq\gamma\cdot\mathbb{E}_{\mathcal{F}}\left[V^{*}\right]-k\cdot T.$ (4)

Now, we will use these bounds to derive the final bound on the biased
gambler’s utility from using algorithm $A^{\alpha}$. By combining inequality 3
and claim 4.1, we know that

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\right]\geq\left\lparen(1+\lambda)\alpha-k\lambda\right\rparen\cdot
T+(1-\alpha)\cdot\mathbb{E}_{\mathcal{F}}\left[V^{*}-T\right].$

When we set $\alpha=\frac{\lambda k+1}{2+\lambda}$,
$\left\lparen(1+\lambda)\alpha-k\lambda\right\rparen=1-\alpha=\frac{1-\lambda(k-1)}{2+\lambda}$.
This means that for this choice of $\alpha$, the preceding inequality becomes:

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\right]\geq\frac{1-\lambda(k-1)}{2+\lambda}\cdot(T+\mathbb{E}\left[V^{*}-T\right])\geq\frac{1-\lambda(k-1)}{2+\lambda}\cdot\mathbb{E}_{\mathcal{F}}\left[V^{*}\right]=\frac{1-\lambda(k-1)}{2+\lambda}\cdot\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right].$

On the other hand, by combining inequality 4 and claim 4.1, we know that

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}^{\alpha}\right]$
$\displaystyle\geq\left\lparen(1+\lambda)\alpha-k\lambda\right\rparen\cdot
T+(1-\alpha)\cdot\left\lparen\gamma\cdot\mathbb{E}_{\mathcal{F}}\left[V^{*}\right]-k\cdot
T\right\rparen$
$\displaystyle\geq\left\lparen(1+\lambda)\alpha-k\cdot\lambda-(1-\alpha)\cdot
k\right\rparen\cdot
T+(1-\alpha)\cdot\left\lparen\gamma\cdot\mathbb{E}_{\mathcal{F}}\left[V^{*}\right]\right\rparen.$

When we set $\alpha=\frac{k\cdot(1+\lambda)}{1+\lambda+k}$,
$\left\lparen(1+\lambda)\alpha-k\cdot\lambda-(1-\alpha)\cdot
k\right\rparen=0$, therefore for this choice of $\alpha$,

$\displaystyle\mathbb{E}\left[U_{g_{b}}^{\alpha}\right]\geq(1-\alpha)\cdot\gamma\cdot\mathbb{E}_{\mathcal{F}}\left[V^{*}\right]=\left\lparen
1-\frac{k\cdot(1+\lambda)}{1+\lambda+k}\right\rparen\cdot\gamma\cdot\mathbb{E}_{\mathcal{F}}\left[V^{*}\right]=(1-\lambda(k-1))\cdot\frac{\gamma}{1+\lambda+k}\cdot\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right].$

Combining the above two cases we conclude that

$\displaystyle\mathbb{E}\left[U_{g_{b}}^{\alpha}\right]\geq\max\left\\{\frac{1}{2+\lambda},\frac{\gamma}{1+\lambda+k}\right\\}\cdot(1-\lambda(k-1))\cdot\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right],$

which implies our lemma statement. ∎

*

###### Proof.

Let $\beta=\lambda\cdot(k-1)$, and fix some positive integer
$w\in\mathbb{N}^{+}$ and some small constant $\epsilon$ that we will set
later. In our example there will be $n=w\cdot k+1$ candidates, and all
candidates will be deterministic except for the last candidate, i.e.
$\sigma^{(1)}....\sigma^{(n-1)}$ are drawn from deterministic
$\mathcal{F}_{1}....\mathcal{F}_{n-1}$ but $\sigma^{n}$ is drawn from
stochastic $\mathcal{F}_{n}$. We define the sequence of deterministic values
as follows:

$(1,0,\cdots,0)$, |  $(0,1,0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1)$,
---|---|---|---
$(1+\beta,0,\cdots,0)$, |  $(0,1+\beta,0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1+\beta)$,
$(1+\beta+\beta^{2},0,\cdots,0)$, |  $(0,1+\beta+\beta^{2},0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1+\beta+\beta^{2})$,
| $\cdots$ |  |
$(\sum_{j=0}^{w-1}\beta^{j},0,\cdots,0)$, |  $(0,\sum_{j=0}^{w-1}\beta^{j},0,\cdots,0)$, |  $\cdots$, | $(0,\cdots,0,\sum_{j=0}^{w-1}\beta^{j}).$

The last randomized candidate is equal to
$\left\lparen(1-\epsilon)(1+\lambda)\cdot\sum_{j=0}^{w-1}\beta^{j}/\epsilon,0,\cdots,0\right\rparen$
with probability $\epsilon$ and is equal to $(0,0,\cdots,0)$ with probability
$1-\epsilon$. We will prove that given our prior distribution $\mathcal{F}$,
the gambler’s expected utility is always at most $1$ no matter which candidate
they choose.

Notice that as with similar constructions in claim 4.1 and claim 4.1, if the
gambler picks a deterministic candidate in some row $i$, then their utility is
maximized by picking the first candidate in row $i$, which results in utility

$\displaystyle\mathbb{E}_{\sigma\sim\mathcal{F}}\left[U_{g_{b}}(\sigma,i\cdot
k+1)\right]$ $\displaystyle=\lVert\sigma^{(i\cdot
k+1)}\rVert_{1}-\lambda\cdot\left\lparen\lVert\vec{s}^{(i\cdot
k+1)}\rVert_{1}-\lVert\sigma^{(i\cdot
k+1)}\rVert_{1}\right\rparen=\sum_{j=0}^{i-1}\beta^{j}-\lambda\cdot(k-1)\cdot\sum_{j=0}^{i-2}\beta^{j}$
$\displaystyle=\sum_{j=0}^{i-1}\left\lparen\lambda(k-1)\right\rparen^{j}-\lambda\cdot(k-1)\cdot\sum_{j=0}^{i-2}\left\lparen\lambda(k-1)\right\rparen^{j}=1.$

Finally, if the gambler picks the last candidate(i.e. the randomized
candidate), then their expected utility is

$\displaystyle\mathbb{E}_{\sigma\sim F}\left[U_{g_{b}}(\sigma,wk+1)\right]$
$\displaystyle=\epsilon\cdot\left\lparen(1-\epsilon)(1+\lambda)\cdot\sum_{i=0}^{w-1}\beta^{i}/\epsilon-\lambda\cdot(k-1)\cdot\sum_{i=0}^{w-1}\beta^{i}\right\rparen+(1-\epsilon)\cdot\left\lparen-\lambda\cdot
k\cdot\sum_{i=0}^{w-1}\beta^{i}\right\rparen$
$\displaystyle\leq(1-\epsilon)\cdot\left\lparen(1+\lambda)\cdot\sum_{i=0}^{w-1}\beta^{i}-\lambda\cdot
k\cdot\sum_{i=0}^{w-1}\beta^{i}\right\rparen$
$\displaystyle=(1-\epsilon)\cdot(1-\lambda(k-1))\cdot\frac{1-\left\lparen\lambda(k-1)\right\rparen^{w}}{1-\lambda(k-1)}=(1-\epsilon)\cdot\left\lparen
1-\left\lparen\lambda(k-1)\right\rparen^{w}\right\rparen<1.$

Therefore it is not possible for the biased gambler to get utility more than
$1$, consequently, $\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]\leq 1$.
On the other hand, the rational prophet can get expected utility

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]=\mathbb{E}\left[V^{*}\right]$
$\displaystyle=\epsilon\cdot\lVert\sigma^{(wk+1)}\rVert_{1}+(1-\epsilon)\cdot\lVert\sigma^{(wk)}\rVert_{1}$
$\displaystyle=\epsilon\cdot\left\lparen(1-\epsilon)(1+\lambda)\cdot\sum_{i=0}^{w-1}\beta^{i}/\epsilon\right\rparen+(1-\epsilon)\cdot\sum_{i=0}^{w-1}\beta^{i}$
$\displaystyle=(1-\epsilon)(2+\lambda)\cdot\frac{1-\left\lparen\lambda(k-1)\right\rparen^{w}}{1-\lambda(k-1)}.$

Similarly, the rational gambler can simply always choose the last candidate,
thus

$\displaystyle\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]\geq\epsilon\cdot\left\lparen(1-\epsilon)(1+\lambda)\cdot\sum_{i=0}^{w-1}\beta^{i}/\epsilon\right\rparen=(1-\epsilon)(1+\lambda)\cdot\frac{1-\left\lparen\lambda(k-1)\right\rparen^{w}}{1-\lambda(k-1)}.$

Let $\epsilon$ be such that $(1-\epsilon)^{2}=1-\delta$ and let
$w=\log_{\lambda(k-1)}\epsilon$. Then $(\lambda(k-1))^{w}=\epsilon$ and thus

$\displaystyle\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq\frac{(2+\lambda)\cdot(1-\epsilon)^{2}}{1-\lambda(k-1)}=\frac{2+\lambda}{1-\lambda(k-1)}\cdot(1-\delta).$

Similarly,

$\displaystyle\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq\frac{(1+\lambda)\cdot(1-\epsilon)^{2}}{1-\lambda(k-1)}=\frac{1+\lambda}{1-\lambda(k-1)}\cdot(1-\delta).$

∎

##  Appendix B Omitted Proofs of Section 4.2

*

###### Proof.

The corollary follows in a relatively straightforward manner from claim 4.1
and lemma 4.5. Let $\sigma(m)$ be the sequence considered in claim 4.1 of
length $m$. Then
$\frac{U_{p_{r}}(\sigma(m))}{U_{g_{b}}(\sigma(m))}=\Omega\left\lparen(\lambda(k-1))^{\frac{m}{k}-1}\right\rparen$,
and in particular
$\frac{U_{p_{r}}(\sigma(m))}{U_{g_{b}}(\sigma(m))}\geq(\lambda(k-1))^{\frac{m}{k}-1}$.
Observe that $\sigma(m)$ is succinct. Thus by lemma 4.5, for any
$\epsilon\in(0,1)$, there exists a distribution $\mathcal{F}$ with
$n=m^{\alpha(m-1)}\cdot\log^{\alpha}(m)$ where
$\alpha=\log_{m}\left\lparen\frac{(\lambda(k-1))^{\frac{m}{k}-1}}{\epsilon}\right\rparen+2$
such that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq(1-\epsilon)\cdot(\lambda(k-1))^{\frac{m}{k}-1}$.
Now in order to get a bound in terms of $n$ we only need to establish the
relationship between $n$ and $m$.

Since $n=m^{\alpha(m-1)}\cdot\log^{\alpha}(m)\leq
m^{m\cdot\alpha}=e^{\log{m}\cdot m\cdot\alpha}$, this means that

$\displaystyle\log n$ $\displaystyle\leq m\cdot\log
m\cdot\left\lparen\log_{m}\left\lparen\frac{(\lambda(k-1))^{\frac{m}{k}-1}}{\epsilon}\right\rparen+2\right\rparen$
$\displaystyle\leq
m\cdot\log\left\lparen\frac{(\lambda(k-1))^{\frac{m}{k}-1}}{\epsilon}\right\rparen+2\cdot
m\cdot\log m$ $\displaystyle\leq
m\cdot\left\lparen\frac{m}{k}-1\right\rparen\cdot\log(\lambda(k-1))+m\cdot\log\left\lparen\frac{1}{\epsilon}\right\rparen+2m\cdot\log
m.$

Let $\epsilon=1/2$, since $m\geq 2$, we know that $\log m\geq 1$, this means
that

$\displaystyle\log n$
$\displaystyle\leq\frac{m^{2}}{k}\cdot\log(\lambda(k-1))+m\cdot\log 2+2m\log
m$ $\displaystyle\leq\frac{m^{2}}{k}\cdot\log(\lambda(k-1))+4m\log m$
$\displaystyle\leq
2\cdot\max\left\lparen\frac{m^{2}}{k}\cdot\log(\lambda(k-1)),4m\log
m\right\rparen.$

Now there are two cases:

  1. 1.

When $\frac{m^{2}}{k}\cdot\log(\lambda(k-1))\geq 4m\log m$, we know that $\log
n\leq 2\cdot\frac{m^{2}}{k}\cdot\log(\lambda(k-1))$. This implies that
$m^{2}\geq\frac{k\cdot\log n}{2\cdot\log(\lambda(k-1))}$ and thus
$m\geq\frac{\sqrt{k}\cdot\log^{\frac{1}{2}}n}{\sqrt{2}\cdot\log^{1/2}(\lambda(k-1))}$.

  2. 2.

When $\frac{m^{2}}{k}\cdot\log(\lambda(k-1))<4m\log m$, we know that $\log
n\leq 8m\log m\leq 8m^{2}$, which means that
$m\geq\frac{\log^{\frac{1}{2}}n}{2\sqrt{2}}$.

We conclude that no matter which case we are in,
$m\geq\frac{1}{\sqrt{2}}\cdot\log^{\frac{1}{2}}n\cdot\min\left\lparen\frac{\sqrt{k}}{\log^{1/2}(\lambda(k-1))},\frac{1}{2}\right\rparen$,
which means that

$\displaystyle\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq(1-\epsilon)\cdot\left\lparen\lambda(k-1))^{\frac{m}{k}-1}\right\rparen=\Omega\left\lparen(\lambda(k-1))^{\frac{1}{\sqrt{2k}}\cdot\log^{\frac{1}{2}}n\cdot\min\left\lparen\frac{1}{\log^{1/2}(\lambda(k-1))},\frac{1}{2\sqrt{k}}\right\rparen-1}\right\rparen.$

Let
$f(\lambda,k)=\frac{1}{\sqrt{2k}}\cdot\min\left\lparen\frac{1}{\log^{1/2}(\lambda(k-1))},\frac{1}{2\sqrt{k}}\right\rparen-1$,
and we get the desired claim that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\Omega\left\lparen(\lambda(k-1))^{f(\lambda,k)\cdot\log^{\frac{1}{2}}n}\right\rparen$.
By claim 2.4,
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\Omega\left\lparen(\lambda(k-1))^{f(\lambda,k)\cdot\log^{\frac{1}{2}}n}\right\rparen$
as well. ∎

*

###### Proof.

The corollary follows in a relatively straightforward manner from claim 4.1
and lemma 4.5. Let $\sigma(m)$ be the sequence considered in claim 4.1 of
length $m$. Then
$\frac{U_{p_{r}}(\sigma(m))}{U_{g_{b}}(\sigma(m))}=\Omega\left\lparen\frac{m}{k}\right\rparen$,
and in particular
$\frac{U_{p_{r}}(\sigma(m))}{U_{g_{b}}(\sigma(m))}\geq\frac{m}{k}$. Observe
that $\sigma(m)$ is succinct. Thus by lemma 4.5, for any $\epsilon\in(0,1)$,
there exists a distribution $\mathcal{F}$ with
$n=m^{\alpha(m-1)}\cdot\log^{\alpha}(m)$ where
$\alpha=\log_{m}\left\lparen\frac{m}{k\cdot\epsilon}\right\rparen+2$ such that
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U_{g_{b}}\right]}\geq(1-\epsilon)\cdot\frac{m}{k}$.

By using a similar analysis as in corollary 4.5, we can compute the
relationship between $n$ and $m$ as follows:

$\displaystyle\log n\leq\log\left\lparen
m^{\alpha(m-1)}\cdot\log^{\alpha}(m)\right\rparen\leq\log\left\lparen
m^{\alpha m}\right\rparen=\alpha\cdot m\log m.$

Now let us set $\epsilon=1/2$ and $\beta=\alpha-3$, then

$\displaystyle\beta=\left\lparen\log_{m}\left\lparen\frac{m}{k\cdot\epsilon}\right\rparen+2\right\rparen-(2+\log_{m}m)=\log_{m}\left\lparen\frac{1}{kx\cdot\epsilon}\right\rparen=\log_{m}\left\lparen\frac{2}{k}\right\rparen=O(1).$

We conclude that $\alpha=3+\beta=3+O(1)=\Theta(1)$. We will now show that
$m=\Omega(\frac{\log n}{\log\log n})$.

  1. 1.

Assume $m\geq\log n$, then it’s clear that $m=\Omega(\frac{\log n}{\log\log
n})$.

  2. 2.

Assume $m\leq\log n$, then $\log m\leq\log\log n$, since $\log
n\leq\alpha\cdot m\log m$, we conclude that

$m\geq\frac{\log n}{\alpha\log m}\geq\frac{\log n}{\alpha\log\log
n}=\Omega\left\lparen\frac{\log n}{\log\log n}\right\rparen.$

Consequently,
$\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}\geq(1-\epsilon)\cdot\frac{m}{k}=\Omega\left\lparen\frac{\log
n}{k\cdot\log\log n}\right\rparen$ and by claim 2.4
$\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}=\Omega\left\lparen\frac{\log
n}{k\cdot\log\log n}\right\rparen$ as well. ∎

*

###### Proof.

By corollaries 4.5 and 4.5 we know that when $\lambda\cdot(k-1)\geq 1$, for
any $n\in\mathbb{N}^{+}$, there exists an i.i.d distribution
$\mathcal{F}_{0}(n)$ such that the prophet and online utility ratio of
$\mathcal{F}_{0}(n)$ is an unboundedly increasing function in terms of the
number of candidates $n$. Thus for any $T\in\mathbb{N}$, there exists a
$n\in\mathbb{N}^{+}$ such that the prophet and online utility of
$\mathcal{F}_{0}(n)$ both exceed $T$.

Recall that the formal definition for competitive ratio is slightly different
in the i.i.d prior distribution setting in contrast to the adversarial order
setting. Namely, the prophet and online competitive ratios are defined as
$\max\limits_{\mathcal{F}\in\mathcal{U}}\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
and
$\max\limits_{\mathcal{F}\in\mathcal{U}}\frac{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$,
where $\mathcal{U}$ is the set of all i.i.d distribution. Observe that the
prophet competitive ratio
$\max\limits_{\mathcal{F}\in\mathcal{U}}\frac{\mathbb{E}_{\mathcal{F}}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}}\left[U^{*}_{g_{b}}\right]}$
is at least
$\max\limits_{n\in\mathbb{N}^{+}}\frac{\mathbb{E}_{\mathcal{F}_{0}(n)}\left[U_{p_{r}}\right]}{\mathbb{E}_{\mathcal{F}_{0}(n)}\left[U^{*}_{g_{b}}\right]}$,
thus any $T\in\mathbb{N}$ serves as a lower bound to the prophet competitive
ratio, and thus the prophet competitive ratio is equal to $\infty$. Similarly,
the online competitive ratio is equal to $\infty$. ∎

*

###### Proof.

We will consider a sequence that is similar to the mostly deterministic
distribution considered in theorem 4.1, except that the last candidate, which
has randomized value, is excluded. Specifically, let $\beta=\lambda\cdot k$,
let $w$ be a parameter that we will set later and let $\sigma$ be the
following sequence:

$(1,0,\cdots,0)$, |  $(0,1,0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1)$,
---|---|---|---
$(1+\beta,0,\cdots,0)$, |  $(0,1+\beta,0,\cdot(1-\lambda(k-1))(1+\delta)s,0)$, |  $\cdots$, |  $(0,\cdots,0,1+\beta)$,
$(1+\beta+\beta^{2},0,\cdots,0)$, |  $(0,1+\beta+\beta^{2},0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,1+\beta+\beta^{2})$,
| $\cdots$ |  |
$(\sum_{i=0}^{w-1}\beta^{i},0,\cdots,0)$, |  $(0,\sum_{i=0}^{w-1}\beta^{i},0,\cdots,0)$, |  $\cdots$, |  $(0,\cdots,0,\sum_{i=0}^{w-1}\beta^{i})$.

As reasoned in theorem 4.1, the biased gambler has utility $\leq 1$ when
selecting any candidate in this sequence. However, the rational prophet will
pick a candidate in the last row, and gains utility
$\sum_{i=0}^{w-1}\beta^{i}=\frac{1-\beta^{w}}{1-\beta}$. Thus,

$\displaystyle\frac{U_{p_{r}}(\sigma)}{U_{g_{b}}(\sigma)}\geq\frac{1-\beta^{w}}{1-\beta}=\frac{1-(\lambda(k-1))^{w}}{1-\lambda(k-1)}.$

Let $\epsilon$ be such that $(1-\epsilon)^{2}=1-\delta$, and let
$w=\epsilon\cdot\log_{\lambda(k+1)}$, then $(\lambda(k-1))^{w}=\epsilon$. Thus

$\displaystyle\frac{U_{p_{r}}(\sigma)}{U_{g_{b}}(\sigma)}\geq\frac{1-(\lambda(k-1))^{w}}{1-\lambda(k-1)}\geq(1-\epsilon)\cdot\frac{1}{1-\lambda(k-1)}.$

Since all candidates in $\sigma$ are distinct, $\sigma$ is succinct, hence by
lemma 4.5, there exists a prior distribution $\mathcal{F}$ where all
candidates are i.i.d such that

$\displaystyle\frac{\mathbb{E}_{\mathcal{F}}[U_{p_{r}}]}{\mathbb{E}_{\mathcal{F}}[U^{*}_{g_{b}}]}\geq(1-\epsilon)\cdot\frac{U_{p_{r}}(\sigma)}{U_{g_{b}}(\sigma)}=(1-\epsilon)^{2}\cdot\frac{1}{1-\lambda(k-1)}=(1-\lambda(k-1))\cdot(1-\delta).$

∎

##  Appendix C Monotonicity Results

######  Claim C.1.

If $\|s^{\prime(t)}\|_{1}<\|s^{(t)}\|_{1}$ for sequences $\sigma^{\prime}$ and
$\sigma$, where $\sigma^{(t)}=\sigma^{\prime(t)}$, then
$U_{g_{b}}(\sigma,t)\leq U_{g_{b}}(\sigma^{\prime},t)$.

###### Proof.

From the definition of the biased gambler’s utility we have:

$\|\sigma^{(t)}\|_{1}-\lambda\bigg{(}\|\vec{s}^{(t)}\|_{1}-\|\sigma^{(t)}\|_{1}\bigg{)}\leq\|\sigma^{\prime(t)}\|_{1}-\lambda\bigg{(}\|\vec{s}^{\prime(t)}\|_{1}-\|\sigma^{\prime(t)}\|_{1}\bigg{)}\implies
U_{g_{b}}(\sigma,t)\leq U_{g_{b}}(\sigma^{\prime},t)$

∎

######  Claim C.2.

For any super candidate $s^{(t)}$ and candidate $\sigma^{(t)}$, if
$\lambda^{\prime}>\lambda\geq 0$, then, when they select candidate
$\sigma^{(t)}$, the biased gambler receives greater utility with loss aversion
$\lambda$ than with loss aversion $\lambda^{\prime}$, namely
$U_{g_{b_{\lambda}}}(\sigma,t)\geq U_{g_{b_{\lambda^{\prime}}}}(\sigma,t)$.

###### Proof.

From the definition of the biased gambler’s utility and the fact that
$\lambda^{\prime}>\lambda$, we have:

$\|\sigma^{(t)}\|_{1}-\lambda\bigg{(}\|\vec{s}^{(t)}\|_{1}-\|\sigma^{(t)}\|_{1}\bigg{)}\geq\|\sigma^{(t)}\|_{1}-\lambda^{\prime}\bigg{(}\|\vec{s}^{(t)}\|_{1}-\|\sigma^{(t)}\|_{1}\bigg{)}\implies
U_{g_{b_{\lambda}}}(\sigma,t)\geq U_{g_{b_{\lambda^{\prime}}}}(\sigma,t)$

∎

Next, we conduct analysis regarding Kleinberg et al. [11]’s construct of
patience in our multidimensional setting. For sake of semantic clarity, we re-
iterate their definition here:

######  Definition C.3 (Patient).

A stopping rule $\pi$ is more patient than a stopping rule $\pi^{\prime}$ if
for every realization of the candidates the stopping rule $\pi$ either selects
the same candidate as $\pi^{\prime}$ or selects a candidate that is later in
the sequence.

Furthermore, for any stopping rule $\pi$, let us define the notation
$\pi(\sigma)$ to denote the value of the candidate selected by the $\pi$ when
the realization of the candidates is the sequence $\sigma$. Specifically,
$\pi_{\lambda}(\sigma)$ denotes the value of the candidate selected by the
optimal $\lambda$-biased stopping rule.

######  Claim C.4.

Given a prior distribution $\mathcal{F}$, if an optimal multidimensional
$\lambda$-biased stopping rule $\pi_{\lambda}$ is more patient than another
multidimensional stopping rule $\pi$, then the expected value of the candidate
selected by $\pi_{\lambda}$ is higher than the expected value of the candidate
selected by $\pi$ (i.e.
$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\pi_{\lambda}(\sigma)\right]\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\pi(\sigma)\right]$).

###### Proof.

First, note that we are reasoning about the objective value of the selected
candidates not about the utilities that they yield to the agents. Let
$t(\sigma)$ and $w(\sigma)$ denote the index of the candidate selected by
$\pi$ and $\pi_{\lambda}$ when the realization of candidates is the sequence
$\sigma$.

By the definition of patience, for any sequence $\sigma$ in the support of
$\mathcal{F}$, $t(\sigma)\leq w(\sigma)$. Since $\pi_{\lambda}$ is optimal for
a $\lambda$-biased agent, for a $\lambda$-biased agent playing optimally on
$\sigma$:

$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[U_{g_{b}}(\sigma,w(\sigma))\right]\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[U_{g_{b}}(\sigma,t(\sigma))\right]$

Note that this is a statement about utilities not about the objective values
of the items selected. Now we can substitute in the definition of $U_{g_{b}}$
and relate the values of candidates $\sigma^{(t(\sigma))}$ and
$\sigma^{(w(\sigma))}$.

$\displaystyle\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(w(\sigma))}\rVert_{1}-\lambda(\lVert
s^{(w(\sigma))}\rVert_{1}-\lVert\sigma^{(w(\sigma))}\rVert_{1})\right]\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t(\sigma))}\rVert_{1}-\lambda(\lVert
s^{(t(\sigma))}\rVert_{1}-\lVert\sigma^{(t(\sigma))}\rVert_{1})\right].$

Re-expressing this algebraically, we have:

$\displaystyle(1+\lambda)\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(w(\sigma))}\rVert_{1}\right]-\lambda\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert
s^{(w(\sigma))}\rVert_{1}\right]\geq(1+\lambda)\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t(\sigma))}\rVert_{1}\right]-\lambda\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert
s^{(t(\sigma))}\rVert_{1}\right].$

Now assume for contradiction that
$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(w(\sigma))}\rVert_{1}\right]<\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t(\sigma))}\rVert_{1}\right]$.
Observe that since for any sequence $\sigma$ in the support of $\mathcal{F}$,
$w(\sigma)\geq t(\sigma)$, it follows that
$\|s^{(t(\sigma))}\|_{1}\leq\|s^{(w(\sigma))}\|_{1}$ and thus
$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert
s^{(t(\sigma))}\rVert_{1}\right]\leq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert
s^{(w(\sigma))}\rVert_{1}\right]$. Consequently, our assumption violates the
above inequality which we know to be true, thus it must be the case that
$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(w(\sigma))}\rVert_{1}\right]>\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t(\sigma))}\rVert_{1}\right]$.
∎

######  Claim C.5.

The optimal $\lambda$-biased stopping rule, $\pi_{\lambda}$, is more patient
than the optimal $\lambda^{\prime}$-biased stopping rule,
$\pi_{\lambda^{\prime}}$, for $\lambda\leq\lambda^{\prime}$.

###### Proof.

Let $t^{\prime}$ denote the random variable representing the index of the
candidate $\pi_{\lambda}^{\prime}$ selects. For contradiction, assume that
there exists realization
$\sigma^{(1)},\cdots,\sigma^{(t)}=\sigma_{1},....,\sigma_{t}$ for which
$\pi_{\lambda}$ selects $\sigma^{(t)}$ and $t^{\prime}$ (the choice of
$\pi_{\lambda^{\prime}}$) is the index of some candidate after $t$. Let event
$A$ be the event where
$\sigma^{(1)},\cdots,\sigma^{(t)}=\sigma_{1},....,\sigma_{t}$ and let $s_{t}$
be the super candidate at time step $t$ conditioned on event $A$. We claim
that after seeing $\sigma_{1},....,\sigma_{t}$, the $\lambda^{\prime}$-biased
agent will get higher expected utility by using a strategy that selects
$\sigma_{t}$ with probability $1$ than by using any other strategy. Thus our
assumption must be false. We now prove our claim. Since $\pi_{\lambda}$ is
optimal for a $\lambda$-biased agent, it must be the case that
$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[U_{g_{b_{\lambda}}}(\sigma,t)\,\middle|\,\mathopen{}A\right]\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[U_{g_{b_{\lambda}}}(\sigma,t^{\prime})\,\middle|\,\mathopen{}A\right]$,
namely for a $\lambda$-biased agent, we have:

$\displaystyle\lVert\sigma_{t}\rVert_{1}-\lambda(\lVert
s_{t}\rVert_{1}-\lVert\sigma_{t}\rVert_{1})\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\|\sigma^{(t^{\prime})}\|_{1}-\lambda(\|s^{(t^{\prime})}\|_{1}-\|\sigma^{(t^{\prime})}\|_{1})\,\middle|\,\mathopen{}A\right].\qquad(1)$

As an intermediate claim, We show that $\lVert
s_{t}\rVert_{1}-\lVert\sigma_{t}\rVert_{1}\leq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert
s^{(t^{\prime})}\rVert_{1}-\lVert\sigma^{(t^{\prime})}\rVert_{1}\,\middle|\,\mathopen{}A\right].$
First, let’s consider the case where
$\lVert\sigma_{t}\rVert_{1}\leq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t^{\prime})}\rVert_{1}\,\middle|\,\mathopen{}A\right]$.
Due to the fact that the value of the super candidate is monotonically
increasing, we have $\lVert
s_{t}\rVert_{1}\leq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert
s^{(t^{\prime})}\rVert_{1}\,\middle|\,\mathopen{}A\right].$ Combining the two
inequalities gives us the desired inequality.

Next, we consider the case where
$\lVert\sigma_{t}\rVert_{1}>\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t^{\prime})}\rVert_{1}\,\middle|\,\mathopen{}A\right]$.
Observe that

$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert
s^{(t^{\prime})}\rVert_{1}\,\middle|\,\mathopen{}A\right]-\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t^{\prime})}]\rVert_{1}\,\middle|\,\mathopen{}A\right]\geq\lVert
s_{t}\rVert_{1}-\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t^{\prime})}]\rVert_{1}\,\middle|\,\mathopen{}A\right],$

since
$s_{t}\leq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\|s^{(t^{\prime})}\|_{1}\,\middle|\,\mathopen{}A\right]$.
Combining this with the assumption that
$\lVert\sigma_{t}\rVert_{1}>\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t^{\prime})}\rVert_{1}\,\middle|\,\mathopen{}A\right]$,
we get $\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert
s^{(t^{\prime})}\rVert_{1}\,\middle|\,\mathopen{}A\right]-\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\lVert\sigma^{(t^{\prime})}]\rVert_{1}\,\middle|\,\mathopen{}A\right]\geq\lVert
s_{t}\rVert_{1}-\lVert\sigma_{t}\rVert_{1}$, as desired.

Having shown the intermediate claim, we can re-express it algebraically as
follows:

$-(\lambda^{\prime}-\lambda)\cdot(\lVert
s_{t}\rVert_{1}-\lVert\sigma_{t}\rVert_{1})\geq-(\lambda^{\prime}-\lambda)\cdot\mathbb{E}_{\sigma\sim\mathcal{F}}\left[(\|s^{(t^{\prime})}\|_{1}-\|\sigma^{(t^{\prime})}\|_{1})\,\middle|\,\mathopen{}A\right].\qquad(2)$

Combining statements (1) and (2), we get the following:

$\displaystyle\lVert\sigma_{t}\rVert_{1}-\lambda^{\prime}(\lVert
s_{t}\rVert_{1}-\lVert\sigma_{t}\rVert_{1})\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\|\sigma^{(t^{\prime})}\|_{1}-\lambda^{\prime}(\|s^{(t^{\prime})}\|_{1}-\|\sigma^{(t^{\prime})}\|_{1})\,\middle|\,\mathopen{}A\right].\qquad(3)$

By the definition of the biased agents utility, statement (3) is equivalent to
the statement that
$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[U_{g_{b_{\lambda^{\prime}}}}(\sigma,t)\,\middle|\,\mathopen{}A\right]\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[U_{g_{b_{\lambda^{\prime}}}}(\sigma,t^{\prime})\,\middle|\,\mathopen{}A\right]$,
namely that conditioned on event $A$, a $\lambda^{\prime}$-biased agent is at
least as well off selecting $t$ as selecting $t^{\prime}$ thus contradicting
our initial assumption and showing no such $\sigma_{1},\cdots,\sigma_{t}$ can
exist. ∎

######  Corollary C.6.

If $\lambda\leq\lambda^{\prime}$, then, when both are playing optimally, the
expected value of the candidate selected by a $\lambda$-biased agent is higher
than the expected value of a candidate selected by a $\lambda^{\prime}$-biased
agent(i.e.
$\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\pi_{\lambda}(\sigma)\right]\geq\mathbb{E}_{\sigma\sim\mathcal{F}}\left[\pi_{\lambda^{\prime}}(\sigma)\right]$).

###### Proof.

It follows as a direct consequence of claims C.4 and C.5 when they are taken
together. ∎

We now move on to consider monotonicity in the number of candidates.

######  Claim C.7.

Let $n,m$ be two integers such that $m>n$. Let
$\mathcal{F}_{1},\cdots,\mathcal{F}_{m}$ be $m$ value distributions for each
of n+1 distinct candidates. Let $\mathcal{F}=\times_{i\in[n]}\mathcal{F}_{i}$
and $\mathcal{F}^{\prime}=\times_{i\in[m]}\mathcal{F}_{i}$. We will use
$\pi_{\lambda}$ and $\pi_{\lambda}^{\prime}$ to denote the optimal
$\lambda$-biased stopping rule for $\sigma\sim\mathcal{F}$ and
$\sigma^{\prime}\sim\mathcal{F}^{\prime}$ respectively. We claim that
$\pi_{\lambda}^{\prime}$ is more patient than $\pi_{\lambda}$.

###### Proof.

Assume for the sake of contradiction that there exist
$\sigma_{1},\cdots,\sigma_{m}$ where $\sigma=\sigma_{1},\cdots,\sigma_{n}$ and
$\sigma^{\prime}=\sigma_{1},\cdots,\sigma_{m}$ such that
$\pi_{\lambda}(\sigma)$ is later in the sequence than
$\pi_{\lambda}^{\prime}(\sigma^{\prime})$. Since, $\pi_{\lambda}$ is the
optimal $\lambda$-biased stopping rule, this assumption implies that

$U_{g_{b_{\lambda}}}(\sigma,\pi_{\lambda}(\sigma))>U_{g_{b_{\lambda}}}(\sigma,\pi_{\lambda}^{\prime}(\sigma^{\prime}))=U_{g_{b_{\lambda}}}(\sigma^{\prime},\pi_{\lambda}^{\prime}(\sigma^{\prime})).$

This is a contradiction since a stopping rule for
$\sigma^{\prime}\sim\mathcal{F}^{\prime}$ can get strictly better utility
compared to $\pi_{\lambda}^{\prime}$ by taking the same action as
$\pi_{\lambda}$ and never selecting candidates with index greater than $n$. ∎

######  Claim C.8.

Let $n,m$ be two integers such that $m>n$. Let
$\mathcal{F}_{1},\cdots,\mathcal{F}_{m}$ be $m$ value distributions for each
of $m$ distinct candidates. Let $\mathcal{F}=\times_{i\in[n]}\mathcal{F}_{i}$
and $\mathcal{F}^{\prime}=\times_{i\in[m]}\mathcal{F}_{i}$. Consider
$\sigma\sim\mathcal{F}$ and $\sigma^{\prime}\sim\mathcal{F}^{\prime}$ where
$\sigma$ is a prefix of $\sigma^{\prime}$. For any $\lambda\geq 0$ and optimal
$\lambda$-biased stopping rule $\pi_{\lambda}$ and $\pi_{\lambda}^{\prime}$
for $\sigma\sim\mathcal{F}$ and $\sigma^{\prime}\sim\mathcal{F}^{\prime}$
respectively, $U_{g_{b_{\lambda}}}(\sigma,\pi_{\lambda}(\sigma))\leq
U_{g_{b_{\lambda}}}(\sigma^{\prime},\pi_{\lambda}^{\prime}(\sigma^{\prime}))$
and $\pi_{\lambda}(\sigma)\leq\pi_{\lambda}^{\prime}(\sigma^{\prime})$.
Semantically, both the utility and expected value of the selected candidate
improve monotonically as more candidates are added to the end of the sequence.

###### Proof.

Since $\sigma$ is a prefix of $\sigma^{\prime}$, an agent can simply select
candidate $\pi_{\lambda}(\sigma)$ and receive at least as much utility on
$\sigma^{\prime}$ as on $\sigma$, thus
$U_{g_{b_{\lambda^{\prime}}}}(\sigma,\pi_{\lambda}(\sigma))\leq
U_{g_{b_{\lambda^{\prime}}}}(\sigma^{\prime},\pi_{\lambda}^{\prime}(\sigma^{\prime}))$.
By claim C.7, the agent is more patient on $\sigma^{\prime}$ than on $\sigma$;
combining this with claim C.4, it must be the case that the expected value of
the candidate selected on $\sigma^{\prime}$ is greater than or equal to the
expected value of that selected on $\sigma$. ∎

Following the outline of Kleinberg et al. [11], we now consider adding a
candidate at the beginning of the sequence. Such addition can decrease the
expected utility of a $\lambda$-biased agent with comparative loss aversion,
whereas it cannot decrease that of a rational agent.

######  Claim C.9.

Let $\mathcal{F}_{1},\cdots,\mathcal{F}_{n+1}$ be $n+1$ value distributions
for each of $n+1$ distinct candidates. Let
$\mathcal{F}=\times_{i=2}^{n+1}\mathcal{F}_{i}$ and
$\mathcal{F}^{\prime}=\times_{i\in[n+1]}\mathcal{F}_{i}$. For any $\lambda\geq
0$ and optimal $\lambda$-biased stopping rule $\pi_{\lambda}$ and
$\pi_{\lambda}^{\prime}$ for $\mathcal{F}$ and $\mathcal{F}^{\prime}$
respectively, consider sequences $\sigma\sim\mathcal{F}$ and
$\sigma^{\prime}\sim\mathcal{F}^{\prime}$, where
$\sigma^{\prime}=\sigma^{(0)^{\prime}}+\sigma$. (We can view $\sigma^{\prime}$
as the result of appending a candidate, $\sigma^{(0)^{\prime}}$, to the
beginning of $\sigma$.) We have
$U_{g_{b}}(\sigma^{\prime},\pi_{\lambda}^{\prime}(\sigma^{\prime}))\geq\frac{1}{1+\lambda}U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))$.

###### Proof.

We lower bound $U_{g_{b}}(\sigma^{\prime},\pi_{\lambda}(\sigma^{\prime}))$ by
considering the utilities for two possible stopping rules:

  1. 1.

Accept the first candidate in $\sigma^{\prime}$, namely
$\sigma^{(0)^{\prime}}$

  2. 2.

Ignore the first candidate, $\sigma^{(0)^{\prime}}$ and instead accept the
same candidate selected on $\sigma$, namely candidate $\pi_{\lambda}(\sigma)$.

In the first case, since the first candidate seen is selected, there is no
regret and the utility of the gambler is $\|\sigma^{(0)^{\prime}}\|_{1}$. In
the second case, since the same candidate is chosen as under $\sigma$ and the
super candidate can increase by at most the value of the candidate appended to
the beginning, the utility is lower bounded by
$U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))-\lambda\|\sigma^{(0)^{\prime}}\|_{1}$.
Since $\pi_{\lambda}$ is the utility maximizing strategy we thus have:

$U_{g_{b}}(\sigma^{\prime},\pi_{\lambda}(\sigma^{\prime}))\geq
max\\{U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))-\lambda\|\sigma^{(0)^{\prime}}\|_{1},\|\sigma^{(0)^{\prime}}\|\\}\qquad(1)$

Consider the case where
$U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))-\lambda\|\sigma^{(0)^{\prime}}\|_{1}\leq\|\sigma^{(0)^{\prime}}\|_{1}$,
which algebraically re-expressed is
$\|\sigma^{(0)^{\prime}}\|_{1}\geq\frac{U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))}{1+\lambda}$.
Combining this with inequality $(1)$ yields
$U_{g_{b}}(\sigma^{\prime},\pi_{\lambda}(\sigma^{\prime}))\geq\frac{U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))}{1+\lambda}$.
Now consider the case where
$U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))-\lambda\|\sigma^{(0)^{\prime}}\|_{1}>\|\sigma^{(0)^{\prime}}\|_{1}$,
algebraically re-expressed this is the case where
$\|\sigma^{(0)^{\prime}}\|_{1}<\frac{U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))}{1+\lambda}$.
Here we get:

$U_{g_{b}}(\sigma^{\prime},\pi_{\lambda}(\sigma^{\prime}))\geq
U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))-\lambda\|\sigma^{(0)^{\prime}}\|_{1}\geq
U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))-\lambda\frac{U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))}{1+\lambda}=\frac{U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))}{1+\lambda}$

Thus, we have proven the first the claim, namely that
$U_{g_{b}}(\sigma^{\prime},\pi_{\lambda}^{\prime}(\sigma^{\prime}))\geq\frac{U_{g_{b}}(\sigma,\pi_{\lambda}(\sigma))}{1+\lambda}$.
∎