smblue rrpurple dmred

# Optimal Stopping with Interdependent Values††thanks: The work of S. Mauras,
and D. Mohan has been partially funded by the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation program (grant
agreement No. 866132), by an Amazon Research Award, by the NSF-BSF (grant No.
2020788), and by a grant from TAU Center for AI and Data Science (TAD). This
research was partially conducted while Mauras and Mohan were visiting the
Simons Laufer Mathematical Sciences Institute (formerly MSRI) in Berkeley,
California, during the Fall 2023 semester, which was funded by the National
Science Foundation (grant No. DMS-1928930) and by the Alfred P. Sloan
Foundation (grant G-2021-16778).

Simon Mauras INRIA, Tel Aviv University<EMAIL_ADDRESS>Divyarthi Mohan
Tel Aviv University<EMAIL_ADDRESS>Rebecca Reiffenhäuser University of
Amsterdam<EMAIL_ADDRESS>
We study online selection problems in both the prophet and secretary settings,
when arriving agents have interdependent values. In the interdependent values
model, introduced in the seminal work of Milgrom and Weber [1982], each agent
has a private signal and the value of an agent is a function of the signals
held by all agents. Results in online selection crucially rely on some degree
of independence of values, which is conceptually at odds with the
interdependent values model. For prophet and secretary models under the
standard independent values assumption, prior works provide constant factor
approximations to the welfare. On the other hand, when agents have
interdependent values, prior works in Economics and Computer Science provide
truthful mechanisms that obtain optimal and approximately optimal welfare
under certain assumptions on the valuation functions.

We bring together these two important lines of work and provide the first
constant factor approximations for prophet and secretary problems with
interdependent values. We consider both the algorithmic setting, where agents
are non-strategic (but have interdependent values), and the mechanism design
setting with strategic agents. All our results are constructive and use simple
stopping rules.

##  1 Introduction

Consider a single-item auction, say for a piece of art, where buyers arrive
online. The goal is to sell the item to the agent with the highest value,
while making the decisions about whether to select each buyer immediately on
their arrival. Additionally, buyers’ values can depend on one another: a buyer
interested in decorating their living room might be influenced by the
impression of those arriving before him, and spontaneously attribute a higher
value to the item if it is very popular. A buyer that sees the item as a pure
investment, on the other hand, will be interested in its resale value alone,
which is fully determined only after the arrival of the very last buyer. We
analyze settings of the above type, formally, of online selection processes
with interdependent values. This means, we combine concepts from the areas of
online selection/optimal stopping with those from the theory on interdependent
values, both of which have raised a lot of recent interest due to their
central and important applications in economics.

#### Online selection.

In the online settings we consider, formally, a sequence of $n$ numbers
arriving in an online fashion. The goal is to select the highest number, with
the restriction that for each one, we have to irrevocably select or reject it
at the time of arrival. Without additional assumptions, no online algorithm
can achieve nontrivial competitive ratio in this setting.

The two central models considered to enable close-to-optimal competitive
ratios w.r.t. the (expected) maximum are prophet inequalities, and the
secretary model. In prophet inequalities, originally introduced in the $70$s,
each of the $n$ numbers is assumed to be drawn independently from a known
distribution $D_{i}$ on arrival. This assumption allows for a (best-possible)
$2-$approximation to the expected optimum via simple threshold policies (e.g.,
Krengel and Sucheston [32]). In the secretary setting, the impossibility of
obtaining good online algorithms is instead circumvented by the assumption
that all numbers will arrive not adversarially, but in _uniformly random
order_. The famous, original secretary problem dates back even further, where
an optimal $\tfrac{1}{e}$-approximation to the maximum (originally for the
ordinal variant) was known since the early 60s (see Dynkin [15]). Both models
have in past years fueled a large variety of research directions, comprising
many combinatorial problem variants and constraints on the selectable sets of
online elements. Most relevant to us, there are strong connections to
economics (especially online auctions and e-commerce) since applications
comprise a large number of auction settings.

#### Interdependence.

The celebrated interdependent values (IDV) model, introduced by Milgrom and
Weber [38] building up on Wilson [44],111The 2020 Economics Nobel Prize was
awarded to Milgrom and Wilson for their work on IDV and auction design [22].
is well-studied in the economics literature when considering settings where
agents have partial information and their values may depend on the information
of all bidders. For instance, suppose we have a house for sale, different
potential buyers might have different partial information about the house
(e.g., one may have information regarding the school district of the
neighborhood and another might have a better assessment of the structural
integrity) and a buyer’s value for the house can be influenced by any or all
of these information. In the IDV model, for a single-item allocation problem,
each agent $i$ has a private signal $s_{i}$ and a public valuation function
$v_{i}(\cdot)$ that maps the signals of all buyers $(s_{1},\ldots,s_{n})$ to a
value for the item; that is, $v_{i}(\mathbf{s})$ is $i$’s value for the item
given a signal profile $\mathbf{s}=(s_{1},\ldots,s_{n})$. There is a long
literature in economics and computer science studying mechanism design in the
interdependent values model. While in the standard model with _private values_
the well-known VCG auction obtains optimal welfare truthfully, in the IDV
model truthful welfare maximization is possible if and only if the valuation
functions satisfy the _single-crossing condition_ [37, 14, 3]. Informally,
under the single-crossing condition, each agent’s signal has the most impact
on their own valuation function compared to others’ valuation functions.
Recent work in EconCS takes an algorithmic approach and investigates
approximation guarantees. Of particular interest to this paper is the result
that when the valuation functions satisfy _submodularity over signals_ (SOS),
there are truthful mechanisms that obtain a constant factor approximation to
the optimal welfare [18, 36, 21]. Informally, a valuation function is
submodular over signals if for each $j$ the impact of increasing $s_{j}$ is
higher when the other signals $s_{-j}$ are lower.

#### Online selection with interdependence.

In order to marry the two directions above and obtain online algorithms for
settings with interdependent valuations, we assume that agents arrive online,
and the algorithm has to select one of them to sell an item or service to. We
make the standard assumption that agents’ valuation functions are public and
known beforehand. However, agents have private signals (e.g., opinions they
form on some specific property of a house when seeing it) which are drawn from
independent distributions222Note that the assumption of underlying
distributions is not necessary in the secretary model, but is w.l.o.g. as long
as we make no further assumptions on the distributions themselves..

For our results on interdependent values in online selection, an important
distinction is whether or not the agents’ values can depend on future (and
hence, yet undetermined) signals. We therefore make different modeling
assumptions on the nature of the underlying online market, specifically on the
set of signals that can influence each agent’s value:

  * •

In a first setting, we consider _myopic agents_ , who promptly consume the
item once selected; and hence receive a value dependent only on signals
observed so far, minus potentially a _prompt_ payment charged immediately by
the algorithm (which as well can only depend on signals observed so far).

  * •

In a second setting, we consider _farsighted agents_ , who if selected will
benefit from the item also in the future; and hence receive a value dependent
on all signals, minus potentially a _tardy_ payment charged only at the end of
the online algorithm (which can depend on all signals).

Note that we do not give results for myopic agents with tardy payments (since
for the former, payments can also be determined promptly), or for farsighted
agents with prompt payments (since these are only implementable when assuming
that agents do not have any knowledge of other agents’ signals or even
distributions beforehand, i.e. not for the commonly used notions of incentive
compatibility).

###  1.1 Our results

We consider agents with interdependent values for a single item, in both the
prophet and secretary models. In contrast to previous work, we do not restrict
our view to submodular-over-signals valuations, but only make the weaker
assumption of subadditivity (which, notably, constitutes a natural boundary
for constant-factor online algorithms, which are incompatible with the
existence of arbitrary complements). Our results comprise the algorithmic
setting, and the strategic setting with selfish agents for which we give (ex-
post) incentive compatible mechanisms. We summarize them in the table below.
In addition to the results listed in the table, note that for the stronger
assumption of submodular over signals valuations, the factor of $2e$ in the
secretary algorithm with farsighted/myopic agents can be improved to a $4$,
see Appendix A.

| Agents | Algorithm | Mechanism
---|---|---|---
Prophet | farsighted |  $\Omega(n)$ (Theorem 1) | $\Omega(n)$
myopic |  $\leq 4$ (Theorem 2) |  $\leq 8$ (Theorem 3)
Secretary | farsighted |  $\leq 2e$ (Theorem 4) |  $\leq 4e$ (Theorem 5)
myopic |  $\leq 2e$ (Theorem 4) |  $\leq 4e$ (Theorem 5)
Table 1: Approximation ratio of our algorithms (no incentive constraints) and
mechanisms (EPIC), when agents have subadditive-over-signals valuations.

In particular, we obtain constant-factor approximation algorithms and
mechanisms – or prove their impossibility – for each possible combination.
This constitutes not only the first, but a close-to complete picture of the
extent to which interdependent values and central paradigms in online
selection can be combined. Notably, our algorithms exactly lose a factor of
$2$ compared to the standard independent values settings, or a factor $4$ when
we also consider incentives. Moreover, when removing the dependence of the
agents’ valuations on any signal except their own, our algorithms recover the
original tight ratios from the prophet inequality and secretary problem.

Our constants are in general not optimal; this is in part due to the fact that
for the corresponding offline settings with interdependence, optimal constants
are also yet unknown.

###  1.2 Related Work

#### Interdependent values.

There is a rich economics literature on interdependent settings over the past
50 years. A common impossibility result emerging in the literature states that
truthful welfare maximization is only possible if the valuations satisfy a
strong condition such as single-crossing [3, 14, 27, 28, 26, 10]. In recent
years the computer science literature has seen much interest in studying the
IDV model through the lens of approximation, in order to circumvent these
impossibilities (e.g., [41, 9, 17, 18, 20, 12, 23, 11, 19]). Eden et al. [17]
consider a setting with an approximate single-crossing condition and obtain
approximately optimal welfare truthfully. In a breakthrough result, Eden et
al. [18] establish a $4$-approximation when the valuations satisfy
submodularity333Eden et al. [18] observe in their conclusion that some of
their results extend to subadditive valuation functions. over signals without
any single-crossing type assumption and also extend the results to
combinatorial auctions under an additional separability condition. Lu et al.
[36] provide an improved approximation bound of $3.315$ for single-item
auctions and Amer and Talgam-Cohen [2] provide a $2$-approximation in the
special case of binary signals. More recently, works of Eden et al. [20, 21]
consider the more general setting where the valuations are private and
establish a constant approximation under submodular valuations for single-item
and multi-unit auctions .

Roughgarden and Talgam-Cohen [41] and Li [35] study simple prior-independent
mechanisms that obtain approximately optimal revenue under different
assumptions, and Chawla et al. [9] further minimize the assumptions needed.
All these works assume some form of single-crossing type condition on the
valuations.

Prior works have also considered interdependent values in other settings
beyond auctions. For example, Chakraborty et al. [7] study interdependence in
matching markets, Cohen et al. [12] study the public projects setting with
interdependent values and Birmpas et al. [5] consider interdependence in the
fair division problem.

#### Prophet inequality.

Prophet Inequalities, originally introduced by Krengel and Sucheston [33, 32]
and Samuel-Cahn [42], are one of the most central concepts in decision making
for stochastic settings. After being employed for algorithmic mechanism design
in online markets by Hajiaghayi et al. [24] and Chawla et al. [8], prophet
inequalities have been obtained for a large variety of prominent problem
settings, e.g. online selection with matroid constraints [30], or online
matchings [1], with a strong focus on economic settings like combinatorial
auctions [16, 13]. While most results crucially exploit independence of the
value distributions $D_{i}$, few results are also known for restricted types
of dependence (see e.g. [43, 25]). Our work, in a similar spirit, follows a
new approach to incorporating dependence between online values: here, while
the distributions of online signals are independent, valuations are obtained
from signals in a dependent fashion. A model of similar type (for myopic
agents), to the best of our knowledge, has only been captured previously by
[6], who prove the existence of a $2(1+\sqrt{3})$-approximation when the
valuations are subadditive over signals, with a non-constructive proof.

#### Secretary problem.

Following the optimal solution for the original secretary problem by Dynkin
[15], a rich body of work has introduced extensions and applications in
various directions, perhaps most famous among which are matroid secretary
problems initiated by Babaioff et al. [4]. Similarly to prophet inequalities,
one major focus has been on mechanism design. For example, the optimal
approximation factor of $\tfrac{1}{e}$ has been recovered for bipartite
matchings [40] and XOS combinatorial auctions [29]. Our results contribute to
the large body of work on the above paradigms, by extending the range of
prophet and secretary algorithms to applications with interdependent
valuations.

##  2 Preliminaries and Model

We consider a problem where $n$ agents have interdependent values: each agent
$i\in[n]$ holds some private signal $s_{i}\in\mathbb{R}_{+}$ and a publicly
known monotone valuation function $v_{i}:\mathbb{R}_{\geq
0}^{n}\rightarrow\mathbb{R}_{\geq 0}$, where monotonicity means that $v_{i}$
is non-decreasing w.r.t. the input vector. We denote
$\mathbf{s}=(s_{1},\dots,s_{n})$, and for every subset $X\subseteq[n]$ we
write $\mathbf{s}_{X}=(\mathds{1}_{1\in X}\cdot s_{1},\dots,\mathds{1}_{n\in
X}\cdot s_{n})$, that is, we replace $s_{i}$ by $0$ if $i\notin X$.

We focus on online settings, where agent $t\in[n]$ arrives at time $t$ and we
observe the signal $s_{t}$ (while, as is standard in the interdependent values
literature, the valuation functions are publicly known). We say that an agent
$i$ is:

  * •

_myopic_ , if their value only depends on the signals received so far, i.e. is
equal to $v_{i}(\mathbf{s}_{[i]})$.

  * •

_farsighted_ , if their value depends on all signals, i.e. is equal to
$v_{i}(\mathbf{s}_{[n]})$.

Myopic agents model situations where the value is obtained instantly on
selection, e.g. when agents bid for a good and their value depends on the
signals they observed from agents arriving previously. Farsighted agents model
the setting where e.g. a good is assigned right now, but the opinion of people
that have not yet arrived influences the value it has to the winning agent
(for instance, an investment they might want to re-sell later). We design
online algorithms, which observe agents one at a time, deciding whether to
continue (and reject the current agent) or to stop (and select, i.e. assign
the good to the current agent). The objective is to maximize the expected
_social welfare_ , that is, the expected value of the agent selected by the
algorithm.

For approximation purposes, we compare our algorithms to the expectation of
the maximum value (in hindsight). In the secretary models, where instead of
distributions, an instance is just a set of $n$ fixed signal values, the
benchmark accordingly reduces to be the maximum such value. Note that this
benchmark depends on whether agents are farsighted or myopic. The two settings
are not directly comparable, as both the social welfare of the algorithm and
of the benchmark are larger with farsighted agents.

###  2.1 Subadditive valuation functions

We consider a natural class of valuations called subadditive over signals (or
simply subadditive). It captures contexts where signals (information) are not
complements, roughly referring to the notion that they do not increase in
value by combining them. This includes most settings explored in the
literature, such as the mineral rights model [44] and the resale model [31,
39].

######  Definition 1 (Subadditive over signals).

We say a valuation function $v(\cdot)$ is _subadditive_ over signals, if for
any signal profile $\mathbf{s}$ and any $X\subseteq[n]$ we have

$v(\mathbf{s})\leq v(\mathbf{s}_{X})+v(\mathbf{s}_{[n]\setminus X})$

We note that the class of subadditive valuation functions is strictly more
general than the class of valuation functions that are _submodular over
signals_ , which are well-studied in the IDV literature [18, 2, 36, 20, 12,
21].

###  2.2 Incentive compatibility

In order to incentivize the agents to report truthfully, mechanisms (usually)
charge the winning agent some payment. In general, a mechanism is an
allocation algorithm together with a payment rule. When agents are farsighted,
we allow those payments to be tardy, i.e. to only specify the paid amount
after the last agent has arrived. When agents are myopic, we require the
algorithm to have prompt payments, i.e. the price is specified and paid
immediately when an agent is chosen.

For each agent $i$ let $x_{i}(\mathbf{s}_{[i]})$ be the indicator variable
where $x_{i}=1$ if and only if $i$ is selected by the given algorithm and
$x_{i}=0$ else. Let $p_{i}(\mathbf{s})\geq 0$ denote the payment charged (wlog
$p_{i}=0$ if $x_{i}=0$). Notice that in a prompt mechanism, $p_{i}$ only
depends on reported signals $\mathbf{s}_{[i]}$.

######  Definition 2 (EPIC).

A mechanism $(\mathbf{x},\mathbf{p})$ is _Ex-Post Incentive Compatible (EPIC)_
if truth-telling is a Nash equilibrium, that is if for every
$i\in[n],\mathbf{s},s^{\prime}_{i}$ we have

$x_{i}(\mathbf{s}_{[i]})\cdot v-p_{i}(\mathbf{s})\geq
x_{i}(\mathbf{s}_{[i-1]},s^{\prime}_{i})\cdot
v-p_{i}(\mathbf{s}_{-i},s^{\prime}_{i})$

where $v$ is the value of agent $i$, which is equal to $v_{i}(\mathbf{s})$ if
agent $i$ is farsighted, and equal to $v_{i}(\mathbf{s}_{[i]})$ if agent $i$
is myopic.

Roughgarden and Talgam-Cohen [41] give a sufficient (and necessary) condition
for an allocation rule to be implementable truthfully, which we recall in
Lemma 1.

######  Lemma 1.

For any deterministic allocation rule $x_{i}(\mathbf{s}_{[i]})$ which is
monotone in $s_{i}$, that is

$\forall i,\forall\mathbf{s},\forall s_{i}^{\prime}\geq s_{i},\qquad
x_{i}(\mathbf{s}_{[i]})\leq x_{i}(\mathbf{s}_{[i-1]},s_{i}^{\prime}),$

there exists a payment $p_{i}(\mathbf{s})$ such that the mechanism
$(\mathbf{x},\mathbf{p})$ is EPIC. Moreover, if agents are myopic, then the
price $p_{i}$ only depends on signals $\mathbf{s}_{[i]}$.

###### Proof.

From Roughgarden and Talgam-Cohen [41]. The payment is equal to

$p_{i}(\mathbf{s})=x_{i}(\mathbf{s}_{[i]})\cdot\inf\\{v_{i}(\mathbf{s}_{-i},s_{i}^{\prime})\,|\,s_{i}^{\prime}\geq
0\text{ such that }x_{i}(\mathbf{s}_{[i-1]},s_{i}^{\prime})=1\\}$

when agent $i$ is farsighted; and is equal to

$p_{i}(\mathbf{s}_{[i]})=x_{i}(\mathbf{s}_{[i]})\cdot\inf\\{v_{i}(\mathbf{s}_{[i-1]},s_{i}^{\prime})\,|\,s_{i}^{\prime}\geq
0\text{ such that }x_{i}(\mathbf{s}_{[i-1]},s_{i}^{\prime})=1\\}$

when agent $i$ is myopic. That is, the payment of the winning agent $i$ equals
the minimum value of $i$ such that $i$ remains the winner, given the signals
of the other agents. ∎

Although we make only very limited use of randomization in our results, note
that (universally) truthful, randomized mechanisms can be defined as lotteries
over deterministic EPIC mechanisms.

##  3 The Prophet Model

We first consider the prophet model, where agents arrive online in an
adversarial order and the signals are drawn independently from a known prior
distribution. Formally, we have $n$ agents, each characterized by a signal
distribution $D_{i}$ and a valuation function $v_{i}(\cdot)$. An adversary
dictates the order in which agents arrive; without loss of generality, we
relabel the agents so that agent $t$ arrives at time $t$. Upon the arrival of
agent $i$, their signal $s_{i}$ is independently drawn from the distribution
$D_{i}$. At this point, we need to decide whether to irrevocably reject the
agent and continue the selection process, or to accept the agent and conclude
the selection. Our goal is to design simple online algorithms that maximize
the expected value of the accepted agent. We evaluate the performance of our
algorithms by comparing it to the expected maximum value.

In Section 3.1 we study the setting with far-sighted agents and show a strong
impossibility that no online algorithm can obtain better than
$\Omega(n)$-approximation to the expected maximum value. In Section 3.2 we
consider myopic agents and provide a simple online algorithm that obtains a
$4$-approximation to the expected maximum welfare. Finally, we extend this
result to settings with incentive constraints in Section 3.3.

###  3.1 Impossibility with far-sighted agents

We show that for farsighted agents, no algorithm can guarantee a competitive
ratio below $\Omega(n)$. Our proof, on a high level, captures the fact that
when values are determined by the very last signal to arrive, any choice made
before that is reduced to essentially guessing.

######  Theorem 1.

In the prophet setting with farsighted agents, any algorithm has a competitive
ratio of at least $\Omega(n)$.

###### Proof.

Assume that signal $s_{n}$ is drawn uniformly in $[0,1]$ and that each agent
$i$ has a value $v_{i}(\mathbf{s})=2^{i}\cdot\mathds{1}[s_{n}\geq 1-1/2^{i}]$.
Then the expected maximum value is

$\mathds{E}[OPT]=\sum_{i=1}^{n-1}2^{i}\cdot\mathds{P}[1-1/2^{i+1}>s_{n}\geq
1-1/2^{i}]+2^{n}\cdot\mathds{P}[s_{n}1\geq 1-1/2^{n}]=\frac{n+1}{2}$

Note that in the myopic setting, all agents always have valuation $0$, except
for the $n\textsuperscript{th}$ agent. For farsighted agents, however, the
realized signal $s_{n}$ (drawn from distribution $D_{n}$) determines the point
in time at which the sequence of increasing $(2^{i})$-values stops (and only
zeroes arrive from then on). Any deterministic algorithm stops at a fixed $i$
and yields an expected value of exactly $1$ (for any choice of $i$). This is
because $v_{i}(\mathbf{s})=2^{i}$ with probability $1/2^{i}$ and $0$
otherwise. Using Yao’s Lemma [45], randomized algorithms cannot give any
improved approximation ratio on this random instance. Thus, we cannot do
better than an $\Omega(n)$ approximation. ∎

Notice that an equivalent example, replacing $s_{n}$ with $s_{1}$, shows that
the algorithm must indeed observe signals, and not only the agents’ values on
the signals of agents arrived so far.

###  3.2 Algorithm with myopic agents

Given the impossibility of any constant approximation with farsighted agents,
we switch our focus to myopic agents. However, the following property observes
that without any assumption (such as subadditivity) on the complementarity of
signals, it is not possible to guarantee a competitive ratio below
$\Omega(n)$.

######  Proposition 1.

In the prophet setting with myopic agents and general valuation functions, any
algorithm has a competitive ratio of at least $\Omega(n)$.

###### Proof.

Assume that all signals $s_{i}$ are draw i.i.d. and uniformly from
$\\{0,2\\}$, and that agent $i$ has a value equal to
$v_{i}(\mathbf{s}_{[i]})=\prod_{j=1}^{i}s_{j}$. This exactly reproduces the
construction of Theorem 1, where the value of an agent double at each step,
until some unpredictable time when it drops to zero for all remaining agents.
Using the same argument as in the previous section, no algorithm can guarantee
better than a $\Omega(n)$ approximation. ∎

A model which addresses the impossibilities raised by Theorems 1 and 1 was
previously considered in the work of Brunel and Krengel [6], who showed (non-
constructively) that there exists a $2(1+\sqrt{3})\approx 5.46$ approximation
when agents have subadditive valuations that do not depend on future signals.
In this section, we provide a simple stopping rules that guarantee an improved
ratio of $4$.

While our algorithm’s main idea is based on the classic threshold approach
from prophet inequalities (where the threshold is set to half the expected
optimum value), dealing with interdependent values even in this simplest
setting we consider is not without challenges. In particular, opposed to
classic prophet inequalities, the simple threshold policy does not work.
Consider the following instance: all agents except for agent $n$ have
valuation equal to $s_{1}+1$. Agent one’s distribution is such that $s_{1}=0$
with probability $(1-\varepsilon)$, and $s_{1}=\tfrac{1}{\varepsilon}$ with
very small probability $\varepsilon$. Agent $n$ has valuation equal to $n\cdot
s_{1}$. The expected maximum is therefore $n$, half of which will be set as
the algorithm’s threshold value. Consider now the rare case that indeed,
$s_{1}$ has nonzero value (due to $s_{1}=\tfrac{1}{\varepsilon}$ being drawn).
Every agent beats the threshold of $\tfrac{n}{2}$, and the algorithm will
realize only a value of $\tfrac{1}{\varepsilon}$ while the optimum is by a
factor $n$ higher. Given that for the above distribution, the standard
threshold does not obtain constant approximation, we might attempt to use a
higher threshold instead. However, consider instead the case that $D_{1}$
always returns zero. Now, any constant-approximative threshold algorithm must
choose a threshold $\leq 1$. We therefore need to take care of such phenomena,
caused by the interdependence of values, in our algorithms.

We now present a simple stopping rule which achieves a $4$-approximation, only
losing a factor $2$ compared to the standard setting with independent values.
The main idea to resolve issues caused by interdependence is that, at any
point of the algorithm, we can skip the current agent if her value is surely
smaller than any one of the future agents, given the signals we observed. In
particular, the algorithm stops at time $t$ if and only if the value of agent
$t$ (i.e., $v_{t}(\mathbf{s}_{[t])}$) satisfies the following two conditions:
(1) it is at least as much as the threshold $X=\mathds{E}[OPT]/2$, and (2) it
is no worse than the current lower bound on the value of the future agents
$i>t$ (i.e., $v_{i}(s_{[t]})$).

Set threshold  $X=\mathds{E}[\max_{i\in[n]}v_{i}(\mathbf{s}_{[i]})]/2.$ Stop
at the first time $t$ such that:

  * •

$v_{t}(\mathbf{s}_{[t]})\geq X$, and

  * •

$v_{t}(\mathbf{s}_{[t]})\geq v_{i}(\mathbf{s}_{[t]})$ for all $i>t$

ALGORITHM 1 4-approximation algorithm with myopic agents.

######  Theorem 2.

Algorithm 1 is $4$-competitive. That is, it obtains an expected (myopic)
welfare of at least
$\frac{1}{4}\mathds{E}[\max_{i\in[n]}v_{i}(\mathbf{s}_{[i]})]$.

###### Proof.

Let $I\in\text{argmax}_{i}v_{i}(\mathbf{s}{[i]})$ be the random variable that
denotes the index of the maximum value agent and let
$T\in\\{1,\ldots,n,\infty\\}$ be the stopping time of Algorithm 1. Notice that
either the algorithm stops at $T\leq I$ or the algorithm does not stop, i.e.
$T=\infty$. This is because the algorithm does not stop by time $I$ only if
$v_{I}(\mathbf{s}_{[I]})<X$, which implies all $v_{i}(\mathbf{s}_{[i]})<X$. By
using the subadditivity of $v_{I}$, we therefore have for any fixed arrival
order and fixed realization of the $n$ signals

$\displaystyle v_{I}(\mathbf{s}_{[I]})$
$\displaystyle\leq\mathds{1}[T=\infty]\cdot v_{I}(\mathbf{s}_{[I]})$
$\displaystyle+\mathds{1}[T<\infty]\cdot v_{I}(\mathbf{s}_{[T]})$
$\displaystyle+\mathds{1}[T<I]\cdot v_{I}(\mathbf{s}_{[T+1,I]}).$

Recall that, if the algorithm did not stop then $v_{I}(\mathbf{s}_{[I]})<X$,
thus bounding the first term as

$\mathds{1}[T=\infty]\cdot v_{I}(\mathbf{s}_{[I]})<\mathds{1}[T=\infty]\cdot
X.$ (1)

However, if the algorithm stops then $v_{T}(\mathbf{s}_{[T]})\geq
v_{I}(\mathbf{s}_{[T]})$, thus bounding the second term as

$\mathds{1}[T<\infty]\cdot
v_{I}(\mathbf{s}_{[T]})\leq\mathds{1}[T<\infty]\cdot v_{T}(\mathbf{s}_{[T]})$
(2)

Finally, to deal with the last term we bound it in expectation as follows

$\displaystyle\mathds{E}[\mathds{1}[T<I]\cdot v_{I}(\mathbf{s}_{[T+1,I]})]$
$\displaystyle\leq\sum_{t=1}^{n}\mathds{E}[\mathds{1}[T=t]\cdot\max_{j>t}v_{j}(\mathbf{s}_{[t+1,j]})]$
$\displaystyle=\sum_{t=1}^{n}\mathds{E}[\mathds{1}[T=t]]\cdot\mathds{E}[\max_{j>t}v_{j}(\mathbf{s}_{[t+1,j]})]$
$\displaystyle\leq\mathds{P}[T<\infty]\cdot 2X$
$\displaystyle\leq\mathds{P}[T<\infty]\cdot
X+\mathds{E}[\mathds{1}[T<\infty]\cdot v_{T}(\mathbf{s}_{[T]})],$ (3)

where the first inequality follows by the law of total probability and using
the fact that $I>t$ to upper-bound $v_{I}(\mathbf{s}_{[t+1,I]})$, the equality
observes that stopping at time $t$ is independent of all signals after $t$,
the next inequality simply uses the definition of $X$, and finally we obtain
the last inequality by observing that $v_{T}(\mathbf{s}_{[T]})\geq X$ whenever
the algorithm stops.

Overall by putting together Equations 1, 2 and 3.2 we have the following bound
on $\mathds{E}[v_{I}(\mathbf{s}_{[I]})]$

$\displaystyle\mathds{E}[v_{I}(\mathbf{s}_{[I]})]$
$\displaystyle\leq\mathds{P}[T=\infty]\cdot X+\mathds{P}[T<\infty]\cdot X$
$\displaystyle\leavevmode\nobreak\ +2\cdot\mathds{E}[\mathds{1}[T<\infty]\cdot
v_{T}(\mathbf{s}_{[T]})]$ $\displaystyle\leq
X+2\cdot\mathds{E}[\mathds{1}[T<\infty]\cdot v_{T}(\mathbf{s}_{[T]})].$

Observe that the expected welfare of the algorithm is exactly
$\mathds{E}[ALG]=\mathds{E}[\mathds{1}[T<\infty]\cdot
v_{T}(\mathbf{s}_{[T]})]$ and by definition of $X$ it holds

$\mathds{E}[v_{I}(\mathbf{s}_{[I]})]\leq\frac{1}{2}\cdot\mathds{E}[v_{I}(\mathbf{s}_{[I]})]+2\cdot\mathds{E}[ALG],$

which simplifies to

$\frac{1}{2}\cdot\mathds{E}[v_{I}(\mathbf{s}_{[I]})]\leq
2\cdot\mathds{E}[ALG],$

yielding a $4$-approximation. ∎

We remark that the above analysis is indeed crucially fueled by the idea of
evaluating all (even future) agents’ values on the current set of signals in
every step, and only stopping if the current agent is the so-far maximum
(including those who haven’t arrived). This is what allows us to relate the
value of the maximum agent to that selected by the algorithm. Moreover, it
nicely illustrates the importance of public valuation functions: in case they
are private, the above counterexample cannot be circumvented since there is no
way to identify the presence of the _better_ agent before arrival.

###  3.3 Mechanism with myopic agents

In the previous section, we presented a simple $4$-approximation in the
algorithmic setting, i.e. without considering the agents’ incentives. Next, we
show how to build a truthful stopping rule (monotone in each agent’s signal)
which achieves an $8$-approximation, losing an extra factor of $2$ compared to
the non-strategic setting.

Recall that in Algorithm 1, even if the value of agent $t$ exceeded the
threshold $X$, we did not stop if a future agent was obviously (i.e. on the
currently known set of signals) better. However, since the future agents are
evaluated (among others) on the signal $s_{t}$, agent $t$ may have an
incentive to misreport her signal. Therefore, the translation into an
incentive-compatible mechanism is no longer immediate (as it is for pure
threshold strategies). It is well-known that an allocation rule can be
truthfully implemented if and only if each agent $i$’s allocation is monotone
non-decreasing in her signal $s_{i}$ (see Lemma 1). Hence, under the single
crossing assumption,444The valuations satisfy the single crossing conditions
if for all $i,j$, $s_{i}$, $s_{-i}$, we have
$\partial_{i}v_{i}(\mathbf{s})/\partial
s_{i}\geq\partial_{i}v_{j}(\mathbf{s})/\partial s_{i}$.  we have a truthful
mechanism that is a $4$-approximation by charging appropriate payments with
Algorithm 1.

######  Corollary 1.

If the valuation functions satisfy the single crossing condition, then
Algorithm 1 provides an EPIC mechanism by charging price $p_{t}$ for the
selected agent $t$, where

$p_{t}=\max\\{X,\inf\\{v_{t}(s_{[t-1]},s^{\prime}_{t})|s^{\prime}_{t}\geq
0\text{ s.t. }v_{t}(s_{[t-1]},s^{\prime}_{t})\geq
v_{i}(s_{[t-1]},s^{\prime}_{t})\text{ for all }i>t\\}\\}.$

However, without the single crossing assumption, we cannot obtain an EPIC
mechanism using Algorithm 1. To overcome this, we use the power of
randomization. In particular, if an agent $t$’s value exceeds the threshold
$X=\mathds{E}[OPT]/2$, then with probability $1/2$ we accept her (and stop),
and with probability $1/2$ we decide to accept a future agent with highest
estimated value using the signals observed so far, $\mathbf{s}_{[t]}$.

Set threshold  $X:=\mathds{E}[\max_{i\in[n]}v_{i}(\mathbf{s}_{[i]})]/2.$ Let
$T$ be the first time $t$ such that $v_{t}(\mathbf{s}_{[t]})\geq X$.

  * •

With probability $1/2$, stop at time $T$ (and charge agent $T$ a price of
$X$).

  * •

With probability $1/2$, wait and stop at time
$\text{argmax}_{i>t}v_{i}(\mathbf{s}_{[t]})$.

ALGORITHM 2 8-approximation mechanism with myopic agents.

######  Theorem 3.

Algorithm 2 is a 8-approximation, that is, it obtains an expected (myopic)
welfare of at least
$\frac{1}{8}\mathds{E}[\max_{i\in[n]}v_{i}(\mathbf{s}_{[i]})]$.

###### Proof.

The proof follows the same principle as that for the algorithmic setting. Let
$I\in\text{argmax}_{i}v_{i}(\mathbf{s}_{[i]})$ be a random variable (index of
a maximum agent value), and let $T\in\\{1,\dots,n,\infty\\}$ be the first time
$t$ such that $v_{t}(\mathbf{s}_{[t]})\geq X$. Note that $T$ is not the
stopping time as the algorithm stops only later with probability $1/2$. By
construction, it holds that either $T\leq I$, or $T=\infty$, because if
$v_{I}(\mathbf{s}_{[I]})<X$ then $v_{t}(\mathbf{s}_{[t]})<X$ for all $t$.
Thus, using the subadditivity of $v_{I}$, we can write

$\displaystyle v_{I}(\mathbf{s}_{[I]})$
$\displaystyle\leq\mathds{1}[T=\infty]\cdot v_{I}(\mathbf{s}_{[I]})$
$\displaystyle+\mathds{1}[T<\infty]\cdot v_{I}(\mathbf{s}_{[T]})$
$\displaystyle+\mathds{1}[T<I]\cdot v_{I}(\mathbf{s}_{[T+1,I]}).$

If the algorithm did not stop, then $v_{I}(\mathbf{s}_{[I]})<X$, which bounds
the first term as

$\mathds{1}[T=\infty]\cdot
v_{I}(\mathbf{s}_{[I]})\leq\mathds{1}[T=\infty]\cdot X$

We next bound the last term in expectation,

$\displaystyle\mathds{E}[\mathds{1}[T<I]\cdot v_{I}(\mathbf{s}_{[T+1,I]})]$
$\displaystyle\leq\sum_{t=1}^{n}\mathds{E}[\mathds{1}[T=t]\cdot\max_{j>t}v_{j}(\mathbf{s}_{[t+1,j]})]$
$\displaystyle=\sum_{t=1}^{n}\mathds{E}[\mathds{1}[T=t]]\cdot\mathds{E}[\max_{j>t}v_{j}(\mathbf{s}_{[t+1,j]})]$
$\displaystyle\leq\mathds{P}[T<\infty]\cdot 2X$
$\displaystyle\leq\mathds{P}[T<\infty]\cdot
X+\mathds{E}[\mathds{1}[T<\infty]\cdot v_{T}(\mathbf{s}_{[T]})],$

where the first inequality follows by the law of total probability and using
that $I>t$ given $T=t$, the equality follows by the observation that stopping
at time $t$ does not depend on future signals after $t$, the next inequality
simply uses the definition of $X$ to upper-bound some expected values, and the
last inequality follows because whenever the $T<\infty$ we have
$v_{T}(\mathbf{s}_{[T]})\geq X$ by definition.

Overall, this gives the following bound on the expected optimum
$\mathds{E}[v_{I}(\mathbf{s}_{[I]})]$

$\displaystyle\mathds{E}[v_{I}(\mathbf{s}_{[I]})]$
$\displaystyle\leq\mathds{P}[T=\infty]\cdot X+\mathds{P}[T<\infty]\cdot X$
$\displaystyle+\mathds{E}[\mathds{1}[T<\infty]\cdot v_{I}(\mathbf{s}_{[T]})]$
$\displaystyle+\mathds{E}[\mathds{1}[T<\infty]\cdot v_{T}(\mathbf{s}_{[T]})].$

Now, observe that by design of the algorithm we have

$\mathds{E}[\mathds{1}[T<\infty]\cdot
v_{T}(\mathbf{s}_{[T]})]+\mathds{E}[\mathds{1}[T<I]\cdot
v_{I}(\mathbf{s}_{[T]})]\leq 2\cdot\mathds{E}[ALG],$ (4)

where we simply bound
$v_{I}(\mathbf{s}_{[T]})\leq\max_{j>T}v_{j}(\mathbf{s}_{[T]})$ for $T<I$.

Thus, plugging in Eq. 4 and using the definition of
$X=\mathds{E}[v_{I}(\mathbf{s}_{[I]})]/2$ we get

$\displaystyle\frac{1}{2}\cdot\mathds{E}[v_{I}(\mathbf{s}_{[I]})]$
$\displaystyle\leq 2\cdot\mathds{E}[ALG]+\mathds{E}[\mathds{1}[T=I]\cdot
v_{I}(\mathbf{s}_{[I]})].$

Finally, we bound $\mathds{E}[\mathds{1}[T=I]\cdot v_{I}(\mathbf{s}_{[I]})]$
by $2\cdot\mathds{E}[ALG]$ to obtain

$\frac{1}{2}\cdot\mathds{E}[v_{I}(\mathbf{s}_{[I]})]\leq
4\cdot\mathds{E}[ALG],$

resulting in an $8$-approximation. ∎

We next show that Algorithm 2 is indeed a truthful mechanism.

######  Lemma 2.

Algorithm 2 is an EPIC mechanism.

###### Proof.

We first observe that our mechanism is essentially a posted price mechanism
with fixed price $X$, except with probability half we don’t sell (and give it
away for free to a future agent). Note that, if an agent $i$ wins for free due
to the random coin toss, this uses no information about $s_{i}$. If an agent
$t$ wins because her value exceeds $X$, then she has no reason to misreport
because decreasing her signal $s_{t}$ can only potentially make her lose and
increasing the signal doesn’t affect her allocation or price. Crucially, we
use $s_{t}$ to estimate the future agents only after we decided to reject $t$
due to the random coin toss. ∎

##  4 The Secretary Model

We next consider the secretary model, where agents arrive in a random order.
More formally, the valuation functions and signals are formed adversarially,
then agents are shuffled uniformly at random and relabelled such that agent
$t$ arrives at time $t$. In our model, the algorithm does not have access to
the valuation functions of agents who have not arrived, but at any given time
it can query the values of all agents so far on any subset of observed
signals. Our goal is to design simple stopping rules, which guarantee a
constant fraction of the maximum value, in expectation over the random order.

In fact, we prove a much stronger statement where even when considering only
the myopic welfare of the online algorithm and mechanism (i.e., the value of
the accepted agent is evaluated only on the signals observed so far), we prove
a constant approximation to the farsighted benchmark (i.e., the maximum value
when considering all signals). Since the valuation functions are monotone over
the signals, we observe that any algorithm that obtains an $\alpha$-fraction
of the farsighted benchmark also obtains an $\alpha$-fraction of the myopic
benchmark. Moreover, the farsighted welfare of the algorithm is greater than
or equal to the myopic welfare of the algorithm.

In Section 4.1 we provide a simple stopping rule such that the (myopic)
welfare is a $2e$-approximation to the maximum farsighted value in
expectation. In Section 4.2 we extend our results to obtain a truthful
mechanism such that the (myopic) welfare is a $4e$-approximation to the
maximum farsighted value in expectation. These results imply a
$2e$-approximate algorithm (without incentive constraints) and a
$4e$-approximate truthful mechanism for both the myopic and farsighted
settings.

Before we present our stopping rules we discuss two properties of interest.
One crucial property of secretary algorithms is that the probability of
stopping is independent of the subset of agents who have arrived (but depends
on the ordering of that subset). This is formalized in Lemma 3, which will be
used in the analysis of Algorithms 3 and 4.

######  Lemma 3.

In the secretary setting, a fixed set of agents $A$ arrive in a random order
$a_{1},\dots,a_{n}$. Consider an algorithm which stops at time $t$ if and only
if

  * •

$t>k$, for some fixed integer $k\geq 0$, and

  * •

$a_{t}=\texttt{best}(\\{a_{1},\dots,a_{t}\\})$, where best maps each subset
$S\subseteq A$ to an agent $a\in S$.

Then the algorithm stops at time $T=t$ with probability equal to
$\frac{k}{t(t-1)}$, and this is independent of the (random) set of agents who
arrived on or before time $t$. More formally,

$\forall t>k,\forall S\subseteq A\text{ such that
}|S|=t,\qquad\mathds{P}[T=t\,|\,\\{a_{1},\dots,a_{t}\\}=S]=\frac{k}{t(t-1)}.$

###### Proof.

We will show by induction on $t\geq k$ that

$\forall S\subseteq A\text{ such that
}|S|=t,\qquad\mathds{P}[T>t\,|\,\\{a_{1},\dots,a_{t}\\}=S]=\frac{k}{t}.$

This is trivially true at time $t=k$, because the stopping rule skips the
first $k$ agents. Now, Let us compute the probability that $T>t+1$. For all
subset $S\subseteq A$ of size $|S|=t+1$, we have that

$\mathds{P}[T>t+1\,|\,\\{a_{1},\dots,a_{t+1}\\}=S]=\mathds{P}[T>t\text{ and
}a_{t+1}\neq\texttt{best}(S)\,|\,\\{a_{1},\dots,a_{t+1}\\}=S].$

Using the law of total probability, we pick $a_{t+1}\in S$, and we obtain

$\mathds{P}[T>t+1\,|\,\\{a_{1},\dots,a_{t+1}\\}=S]=\frac{1}{|S|}\sum_{\begin{subarray}{c}a\in
S\\\
a\neq\texttt{best}(S)\end{subarray}}\mathds{P}[T>t\,|\,\\{a_{1},\dots,a_{t}\\}=S\setminus\\{a\\}]$

Finally, using the induction hypothesis, we have

$\mathds{P}[T>t+1\,|\,\\{a_{1},\dots,a_{t+1}\\}=S]=\frac{|S|-1}{|S|}\cdot\frac{k}{t}=\frac{k}{t+1},$

which concludes the induction. Next, for all $t>k$ and for all subset
$S\subseteq A$ of size $|S|=t$ we write

$\displaystyle\mathds{P}[T=t\,|\,\\{a_{1},\dots,a_{t}\\}=S]$
$\displaystyle=\mathds{P}[T>t-1\text{ and
}a_{t}=\texttt{best}(S)\,|\,\\{a_{1},\dots,a_{t}\\}=S]$
$\displaystyle=\frac{1}{|S|}\cdot\mathds{P}[T>t-1\,|\,\\{a_{1},\dots,a_{t-1}\\}=S\setminus\texttt{best}(S)],$

because with probability $1/|S|$ the best of $S$ arrives at time $t$.

We know that the probability that $T>t-1$ is $\frac{k}{t-1}$ from the above
argument, and hence we conclude that $T=t$ with probability
$\frac{k}{t(t-1)}$. ∎

A second important property of secretary settings is that given a stopping
rule which asymptotically achieves a constant approximation when the number of
agents becomes large, one can turn it into a stopping rule which achieves that
exact constant for every value of $n$. Indeed, the stopping rule can pretend
to observe many dummy agents with value $0$, which will never be selected but
are only here to artificially increase the value of $n$.

###  4.1 Algorithm with myopic or farsighted agents

Equipped with Lemma 3, we propose a simple stopping rule which achieves a
$2e$-approximation, only losing a factor $2$ compared to the standard
secretary setting. The main intuition is that after the sampling phase (first
$\lfloor n/e\rfloor$ steps), the algorithm knows sufficiently many signals to
have a good estimate of the agents true value (on all signals).

At step $t$, when agent $t$ arrives, stop if:

  * •

$t>n/e$ (i.e., skip a constant fraction of agents), and

  * •

$v_{t}(\mathbf{s}_{[t]})>v_{i}(\mathbf{s}_{[t]})$ for all $i<t$.

ALGORITHM 3 2e-approximation algorithm for the secretary model.

######  Theorem 4.

Algorithm 3 is a $2e$-approximation. That is, the expected (myopic) value of
the accepted agent is at least $\frac{1}{2e}\max_{i}v_{i}(\mathbf{s})$.

###### Proof.

We define the random variable $T\in\\{1,\dots,n,\infty\\}$ to be the stopping
time of the algorithm. In the secretary setting, $n$ agents from a set $A$
arrive in a uniformly random order $a_{1},\dots,a_{n}$. Recall that we labeled
agents according to their arrival order, that is, in the algorithm,

$\forall i\in[n],\forall J\subseteq[n],\qquad
v_{i}(\mathbf{s}_{J}):=\bar{v}_{a_{i}}(\bar{\mathbf{s}}_{\\{a_{j}|j\in
J\\}}),$

where $\bar{v}$ and $\bar{\mathbf{s}}$ are the original, fixed valuation
functions and signals (determined adversarially) before applying the random
ordering. In particular, there exists an agent $a^{\star}\in A$ with the
largest value $OPT=\bar{v}_{a^{\star}}(\bar{\mathbf{s}})$. For convenience, we
define the set function

$\forall X\subseteq A,\qquad f(X):=\bar{v}_{a^{\star}}(\bar{s}_{X}),$

that is, $f(X)$ denotes the estimated value of $a^{\star}$ only using the
signals of $X\subseteq A$.

Next, we define the (random) set $A_{t}:=\\{a_{1},\dots,a_{t}\\}$ of agents
who have arrived at time $t$. Observe that the stopping rule of Algorithm 3
corresponds to Lemma 3 with $k=\lfloor n/e\rfloor$ and

$\forall S\subseteq A,\qquad\texttt{best}(S):=\text{argmax}_{a\in
S}\bar{v}_{a}(\bar{\mathbf{s}}_{S}).$

Using Lemma 3, the event where the algorithm stops at time $T=t$ is
independent of $A_{t}$, and has probability equal to

$\forall t>n/e,\qquad\mathds{P}[T=t\,|\,A_{t}]=\frac{\lfloor
n/e\rfloor}{t(t-1)}$ (5)

We write the expected welfare obtained by the algorithm as

$\displaystyle\mathds{E}[ALG]$ $\displaystyle\geq\sum_{t=\lceil
n/e\rceil}^{n}\mathds{E}[\mathds{1}[T=t]\cdot v_{t}(\mathbf{s}_{[t]})]$
(equality holds for myopic) $\displaystyle\geq\sum_{t=\lceil
n/e\rceil}^{n}\mathds{E}[\mathds{1}[T=t]\cdot
v_{t}(\mathbf{s}_{[t]})\cdot\mathds{1}[a^{\star}\in A_{t}]]$ (always smaller)
$\displaystyle\geq\sum_{t=\lceil n/e\rceil}^{n}\mathds{E}[\mathds{1}[T=t]\cdot
f(A_{t})\cdot\mathds{1}[a^{\star}\in A_{t}]]$ (by the stopping condition)
$\displaystyle=\sum_{t=\lceil n/e\rceil}^{n}\frac{\lfloor
n/e\rfloor}{t(t-1)}\cdot\mathds{E}[f(A_{t})\cdot\mathds{1}[a^{\star}\in
A_{t}]]$ (using Equation 5) $\displaystyle=\sum_{t=\lceil
n/e\rceil}^{n}\frac{\lfloor
n/e\rfloor}{t(t-1)}\cdot\frac{t}{n}\cdot\mathds{E}[f(A_{t})\,|\,a^{\star}\in
A_{t}]$ ($a^{\star}\in A_{t}$ with probability $t/n$)

Next we define

$\forall t\in[n],\qquad\alpha_{t}:=\mathds{E}[f(A_{t})\,|\,a^{\star}\in
A_{t}].$

which gives the inequality

$\mathds{E}[ALG]\geq\frac{\lfloor n/e\rfloor}{n}\sum_{t=\lceil
n/e\rceil}^{n}\frac{\alpha_{t}}{t-1}.$

Alternatively, $\alpha_{t}$ it is the expected value of
$f(X\cup\\{a^{\star}\\})$, given a random subset $X\subseteq
A\setminus\\{a^{\star}\\}$ of size $|X|=t-1$. In particular, $\alpha_{n}=OPT$,
the optimal farsighted welfare, and the sequence $\alpha_{t}$ is non-
decreasing. By linearity of expectation, and using the fact that $f$ is a
monotone subadditive set function, we have that

$\displaystyle\alpha_{n}=f(A)$
$\displaystyle=\mathds{E}_{A_{t}}[f(A)\,|\,a^{\star}\in A_{t}]$ (by
definition) $\displaystyle\leq\mathds{E}_{A_{t}}[f(A_{t})+f(A\setminus
A_{t})\,|\,a^{\star}\in A_{t}]$ $\displaystyle(\text{by subadditivity})$
$\displaystyle\leq\mathds{E}_{A_{t}}[f(A_{t})+f(A\setminus
A_{t}\cup\\{a^{\star}\\})\,|\,a^{\star}\in A_{t}]$ (by monotonicity)
$\displaystyle=\mathds{E}_{A_{t}}[f(A_{t})\,|\,a^{\star}\in
A_{t}]+\mathds{E}_{A_{n-t+1}}[f(A_{n-t+1})\,|\,a^{\star}\in A_{n-t+1}]$ (by
symmetry) $\displaystyle=\alpha_{t}+\alpha_{n-t+1}$ (by definition)

Finally, we will split the sum from $t_{0}=\lceil n/e\rceil$ to $n$ in three:
from $t_{0}$ to $t_{1}=\lceil n/(e-1)\rceil$, from $t_{1}$ to $t_{2}=n-\lceil
n/e\rceil+1$, and from $t_{2}$ to $n$. By monotonicity of the $\alpha_{t}$’s,
we have that

$\displaystyle\sum_{t=\lceil n/e\rceil}\frac{\alpha_{t}}{t-1}$
$\displaystyle\geq\alpha_{t_{0}}\sum_{t=t_{0}}^{t_{1}}\frac{1}{t-1}+\alpha_{t_{1}}\sum_{t=t_{1}+1}^{t_{2}-1}\frac{1}{t-1}+\alpha_{t_{2}}\sum_{t=t_{2}}^{n}\frac{1}{t-1}$
$\displaystyle\geq\alpha_{t_{0}}\ln\left(\frac{t_{1}}{t_{0}-1}\right)+\alpha_{t_{1}}\ln\left(\frac{t_{2}-1}{t_{1}}\right)+\alpha_{t_{2}}\ln\left(\frac{n}{t_{2}-1}\right)$
$\displaystyle\geq\alpha_{t_{0}}\ln\left(\frac{e}{e-1}\right)+\alpha_{t_{1}}\ln\left(\frac{(e-1)^{2}}{e}\right)+\alpha_{t_{2}}\ln\left(\frac{e}{e-1}\right)+\alpha_{t_{1}}\Theta(1/n)$
$\displaystyle\geq(\alpha_{t_{0}}+\alpha_{t_{2}})\ln\left(\frac{e}{e-1}\right)+2\alpha_{t_{1}}\ln\left(\frac{e-1}{\sqrt{e}}\right)+\alpha_{t_{1}}\Theta(1/n)$
$\displaystyle\geq\alpha_{n}\ln\left(\frac{e}{e-1}\right)+\alpha_{n}\ln\left(\frac{e-1}{\sqrt{e}}\right)+\alpha_{n}\Theta(1/n)=\alpha_{n}/2+\alpha_{n}\Theta(1/n)$

Multiplying both sides by $\lfloor n/e\rfloor/n$, we obtain that
$OPT/\mathds{E}[ALG]\leq 2e+O(1/n)$. Recalling our remark (dummy agents) from
the beginning of the section, we can drop the lower-order term and consider
only the limit of the approximation ratio for $n\rightarrow\infty$. ∎

###  4.2 Mechanism with myopic or farsighted agents

In the previous section, we presented a simple $2e$-approximation in the
algorithmic setting, without considering the agents’ incentives. As before, if
the valuation functions satisfy the single crossing condition, then our
$2e$-approximation algorithm can be implemented truthfully with appropriate
payments (which is prompt for myopic agents and tardy for farsighted agents
respectively).

######  Corollary 2.

If the valuation functions satisfy the single crossing condition, then
Algorithm 3 provides an EPIC mechanism by charging price $p_{t}$ for the
selected agent $t$, where for farsighted agents

$p_{t}=\inf\\{v_{t}(s_{-t},s^{\prime}_{t})|s^{\prime}_{t}\geq 0\text{ s.t.
}v_{t}(s_{[t-1]},s^{\prime}_{t})\geq v_{i}(s_{[t-1]},s^{\prime}_{t})\text{ for
all }i>t\\},$

and for myopic agents

$p_{t}=\inf\\{v_{t}(s_{[t-1]},s^{\prime}_{t})|s^{\prime}_{t}\geq 0\text{ s.t.
}v_{t}(s_{[t-1]},s^{\prime}_{t})\geq v_{i}(s_{[t-1]},s^{\prime}_{t})\text{ for
all }i>t\\}.$

However, without the single crossing assumption, we cannot obtain an EPIC
mechanism using Algorithm 3. In this section, we show how to achieve a
$4e$-approximation with a truthful stopping rule (monotone in each agent’s
signal). The intuition behind our mechanism is quite simple: we combine the
random sampling mechanism of [18], which achieves a $4$-approximation in the
offline setting, with the $e$-approximation stopping rule of the standard
secretary problem.

Define $t_{0}=\lfloor n/2\rfloor$. Stop at the first time $t$ such that:

  * •

$t>t_{0}+\lfloor n/(2e)\rfloor$ (i.e., skip a constant fraction of agents),
and

  * •

$v_{t}(\mathbf{s}_{[t_{0}]\cup\\{t\\}})>v_{i}(\mathbf{s}_{[t_{0}]\cup\\{i\\}})$
for all $t_{0}<i<t$.

At the end, charge $t$ a price of
$\inf\\{v_{t}(\mathbf{s}_{-t},s_{t}^{\prime})\,|\,s_{t}^{\prime}\geq 0\text{
s.t.
}v_{t}(\mathbf{s}_{[t_{0}]},s_{t}^{\prime})>\max_{t_{0}<i<t}v_{i}(\mathbf{s}_{[t_{0}]\cup\\{i\\}})\\}$.

ALGORITHM 4 4e-approximation mechanism for the secretary model.

######  Theorem 5.

Algorithm 4 is a $4e$-approximation. That is, the expected (myopic) value of
the accepted agent is at least $\frac{1}{4e}\max_{i}v_{i}(\mathbf{s})$.

###### Proof.

We define the random variable $T\in\\{1,\dots,n,\infty\\}$ to be the stopping
time of the algorithm. In the secretary setting, $n$ agents from a set $A$
arrive in a uniformly random order $a_{1},\dots,a_{n}$. Recall that we labeled
agents according to their arrival order, that is, in the algorithm,

$\forall i\in[n],\forall J\subseteq[n],\qquad
v_{i}(\mathbf{s}_{J}):=\bar{v}_{a_{i}}(\bar{\mathbf{s}}_{\\{a_{j}|j\in
J\\}}),$

where $\bar{v}$ and $\bar{\mathbf{s}}$ are fixed valuation functions and
signals (worst case). In particular, there exist an agent $a^{\star}\in A$
with the largest value $OPT=\bar{v}_{a^{\star}}(\bar{\mathbf{s}})$. For
convenience, we define the set function

$\forall X\subseteq A,\qquad f(X):=\bar{v}_{a^{\star}}(\bar{s}_{X}).$

Let $t_{0}:=\lfloor n/2\rfloor$ and $t_{1}:=t_{0}+\lfloor n/(2e)\rfloor$. Now,
observe that the stopping rule of Algorithm 4 does not exactly correspond to
the hypothesis in Lemma 3. Indeed, the agent arriving at time $t$ is only
compared to agents $t_{0}<i<t$, so the best agent of $A_{t}$ depends on the
order in which they arrived. This is easily fixed if we say that the first
$t_{0}$ are here to initialize the mechanism, which only start at time
$t_{0}+1$. More formally, for every fixed set $A_{t_{0}}=R$ we define

$\forall S\subseteq A\setminus
R,\qquad\texttt{best}_{R}(S):=\text{argmax}_{a\in
S}\bar{v}_{a}(\mathbf{s}_{R\cup\\{a\\}}).$

Applying Lemma 3 to the mechanism defined by $\texttt{best}_{R}$ and starting
at time $t_{0}+1$, we have

$\forall
t>t_{1},\qquad\mathds{P}[T=t\,|\,A_{t},A_{t_{0}}]=\frac{t_{1}-t_{0}}{(t-t_{0})(t-t_{0}-1)}.$
(6)

Next, we write the expected welfare of the algorithm as

$\displaystyle\mathds{E}[ALG]$
$\displaystyle\geq\sum_{t=t_{1}+1}^{n}\mathds{E}[\mathds{1}[T=t]\cdot
v_{t}(\mathbf{s}_{[t]})]$ (equality holds for myopic)
$\displaystyle\geq\sum_{t=t_{1}+1}^{n}\mathds{E}[\mathds{1}[T=t]\cdot
v_{t}(\mathbf{s}_{[t_{0}]\cup\\{t\\}})\cdot\mathds{1}[a^{\star}\in
A_{t}\setminus A_{t_{0}}]]$ (always smaller)
$\displaystyle\geq\sum_{t=t_{1}+1}^{n}\mathds{E}[\mathds{1}[T=t]\cdot
f(A_{t_{0}}\cup\\{a^{\star}\\})\cdot\mathds{1}[a^{\star}\in A_{t}\setminus
A_{t_{0}}]]$ (stopping condition)
$\displaystyle\geq\sum_{t=t_{1}+1}^{n}\frac{t_{1}-t_{0}}{(t-t_{0})(t-t_{0}-1)}\cdot\mathds{E}[f(A_{t_{0}}\cup\\{a^{\star}\\})\cdot\mathds{1}[a^{\star}\in
A_{t}\setminus A_{t_{0}}]]$ (using LABEL:{eq:secretary_farsighted_mechanism})
$\displaystyle\geq\sum_{t=t_{1}+1}^{n}\frac{t_{1}-t_{0}}{(t-t_{0})(t-t_{0}-1)}\cdot\frac{t-t_{0}}{n}\cdot\mathds{E}[f(A_{t_{0}}\cup\\{a^{\star}\\})]$
$\displaystyle(\mathds{P}[a^{\star}\in A_{t}\setminus A_{t_{0}}]=(t-t_{0})/n)$

Using the subadditivity of $f$, we have that

$\displaystyle OPT=f(A)$ $\displaystyle=\mathds{E}[f(A)]$ (by definition)
$\displaystyle\leq\mathds{E}[f(A_{t_{0}}\cup\\{a^{\star}\\})+f(A\setminus(A_{t_{0}}\cup\\{a^{\star}\\}))]$
(by subadditivity) $\displaystyle\leq
2\cdot\mathds{E}[f(A_{t_{0}}\cup\\{a^{\star}\\})]$ (by symmetry)

Overall, we obtain that

$\displaystyle\mathds{E}[ALG]$
$\displaystyle\geq\frac{OPT}{2}\cdot\frac{(t_{1}-t_{0})}{n}\sum_{t=t_{1}+1}^{n}\frac{1}{t-t_{0}-1}\geq
OPT\cdot\frac{(t_{1}-t_{0})}{2n}\ln\left(\frac{n-t_{0}}{t_{1}-t_{0}}\right)\geq
OPT\cdot\frac{\lfloor n/(2e)\rfloor}{2n}$

Overall, we obtain $OPT/\mathds{E}[ALG]\leq 4e+O(1/n)$. Once again, using the
remark made at the beginning of the section, we can drop the lower order term
$O(1/n)$ by taking $n\to\infty$.

∎

We observe that Algorithm 4 is a truthful mechanism by using Lemma 1.

######  Lemma 4.

Algorithm 4 is an EPIC mechanism

###### Proof.

This follows by observing that the allocation for agent $t$ is monotone non-
decreasing in her signal $s_{t}$. Because: first, none of the sample agents
will be allocated no matter their signal, and second, and at time $t$ agent
$t$’s signal is only used to to determine her own estimated value
$v_{t}(\mathbf{s}_{[t_{0}]\cup\\{t\\}})$ and this is monotone in her signal
$s_{t}$. Thus we can charge the appropriate payments given by Lemma 1 to
obtain EPIC mechanism for both the myopic and farsighted settings. Moreover,
for the myopic setting the value and payments don’t depend on future signals,
and hence, the mechanism can be implemented with prompt payments. ∎

###  4.3 Extensions beyond our mechanisms

We remark that the secretary setting with myopic agents is especially well-
behaved. In particular, the random order gives (in expectation) an outlook on
all agents’ valuations, since we see a random subset of them (i.e. the yet-
arrived ones), evaluated on a random subset of the signals. This continues to
hold even if the valuations are _not_ known, but private information of the
agents. Only recently, Eden et al. [20, 21] give a constant approximation
mechanism in the offline setting with submodular valuations (approximation
ratio $5.55$). A construction similar to that of Algorithm 4 can be combined
with their result to obtain a constant approximation mechanism for the
secretary problem with myopic agents and submodular valuations. However,
obtaining similar results for more challenging settings than this (secretary,
myopic) seems out of reach with standard reductions, as having private
valuations gives too much strategic power to the agents interacting with the
mechanism.

##  5 Conclusion

Our results consider agents with interdependent valuations in context of the
celebrated secretary and prophet inequalities problems, capturing (stochastic)
online versions of single-item auctions with agents that exhibit
interdependent valuations. We give the first secretary and prophet algorithms
and mechanisms for this setting, achieving small constant-factor
approximations to the according standard benchmarks. This resolves (up to
possibly improvements in the constant) the according algorithmic and mechanism
design problems for both myopic and farsighted agents with public, subadditive
valuations. The fact that our results are all constructive and obtained by
simple stopping rules especially raises hope that in future work, they can be
extended to different settings. As one direction, it is an interesting
question to investigate the case of private valuations, and prove for which
settings constant approximations are/are not possible (see short discussion
for the secretary setting in Section 4.3).

While arguably, our considered class of subadditive valuation functions poses
a natural barrier for the performance of online algorithms, one should also
investigate performance of such stopping rules when values satisfy other
properties from the hierarchy of complement-free valuations defined by Lehmann
et al. [34] (see also the discussion for submodular valuations in Appendix A).

Finally, extending from the simple setting, where only one online agent can be
chosen, towards combinatorial problems (e.g., with cardinality/matroid
constraints on the chosen subset, or for certain combinatorial auctions) would
be a consequential next step.

## References

  * Alaei et al. [2012] Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat.  Online prophet-inequality matching with applications to ad allocation.  06 2012.  doi: 10.1145/2229012.2229018.
  * Amer and Talgam-Cohen [2021] Ameer Amer and Inbal Talgam-Cohen.  Auctions with Interdependence and SOS: Improved Approximation.  In _14th International Symposium on Algorithmic Game Theory (SAGT)_ , 2021.
  * Ausubel et al. [1999] Lawrence M Ausubel et al.  A generalized vickrey auction.  _Econometrica_ , 1999.
  * Babaioff et al. [2007] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg.  Matroids, secretary problems, and online mechanisms.  pages 434–443, 01 2007.
  * Birmpas et al. [2023] Georgios Birmpas, Tomer Ezra, Stefano Leonardi, and Matteo Russo.  Fair division with interdependent values.  _CoRR_ , abs/2305.14096, 2023.  doi: 10.48550/ARXIV.2305.14096.  URL https://doi.org/10.48550/arXiv.2305.14096.
  * Brunel and Krengel [1979] Antoine Brunel and Ulrich Krengel.  Parier avec un prophète dans le cas d’un processus sous-additif.  1979\.  URL https://gallica.bnf.fr/ark:/12148/bpt6k98138170/f73.item.
  * Chakraborty et al. [2010] Archishman Chakraborty, Alessandro Citanna, and Michael Ostrovsky.  Two-sided matching with interdependent values.  _Journal of Economic Theory_ , 145(1):85–105, 2010.
  * Chawla et al. [2010] Shuchi Chawla, Jason Hartline, David Malec, and Balasubramanian Sivan.  Sequential posted pricing and multi-parameter mechanism design.  _Northwestern University, Center for Mathematical Studies in Economics and Management Science, Discussion Papers_ , 06 2010.  doi: 10.1145/1807406.1807428.
  * Chawla et al. [2014] Shuchi Chawla, Hu Fu, and Anna Karlin.  Approximate revenue maximization in interdependent value settings.  In _15th ACM Conference on Economics and Computation (EC)_ , 2014\.
  * Che et al. [2015] Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima.  Efficient assignment with interdependent values.  _Journal of Economic Theory_ , 158:54–86, 2015.
  * Chen et al. [2022] Yiling Chen, Alon Eden, and Juntao Wang.  Cursed yet Satisfied Agents.  In _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_ , 2022.
  * Cohen et al. [2023] Avi Cohen, Michal Feldman, Divyarthi Mohan, and Inbal Talgam-Cohen.  Interdependent public projects.  In _34th ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2023\.
  * Correa and Cristi [2023] Jose Correa and Andrés Cristi.  A constant factor prophet inequality for online combinatorial auctions.  pages 686–697, 06 2023.  doi: 10.1145/3564246.3585151.
  * Dasgupta and Maskin [2000] Partha Dasgupta and Eric Maskin.  Efficient auctions.  _The Quarterly Journal of Economics_ , 2000.
  * Dynkin [1963] E. Dynkin.  The optimum choice of the instant for stopping a markov process.  _Soviet Mathematics. Doklady_ , 4, 01 1963.
  * Dütting et al. [2020] Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier.  Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs.  _SIAM Journal on Computing_ , 49:540–582, 04 2020.  doi: 10.1137/20M1323850.
  * Eden et al. [2018] Alon Eden, Michal Feldman, Amos Fiat, and Kira Goldner.  Interdependent values without single-crossing.  In _19th ACM Conference on Economics and Computation (EC)_ , 2018\.
  * Eden et al. [2019] Alon Eden, Michal Feldman, Amos Fiat, Kira Goldner, and Anna R. Karlin.  Combinatorial auctions with interdependent valuations: Sos to the rescue.  In _20th ACM Conference on Economics and Computation (EC)_ , 2019\.
  * Eden et al. [2021] Alon Eden, Michal Feldman, Inbal Talgam-Cohen, and Ori Zviran.  Poa of simple auctions with interdependent values.  In _35th AAAI Conference on Artificial Intelligence (AAAI)_ , 2021\.
  * Eden et al. [2022] Alon Eden, Kira Goldner, and Shuran Zheng.  Private interdependent valuations.  In _33rd ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2022\.
  * Eden et al. [2023] Alon Eden, Michal Feldman, Kira Goldner, Simon Mauras, and Divyarthi Mohan.  Constant approximation for private interdependent valuations.  In _64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023_ , pages 148–163. IEEE, 2023.  doi: 10.1109/FOCS57990.2023.00018.
  * for the Prize in Economic Sciences in Memory of Alfred Nobel [2020] The Committee for the Prize in Economic Sciences in Memory of Alfred Nobel.  Scientifc background on the sveriges riksbank prize in economic sciences, 2020.  URL https://www.nobelprize.org/uploads/2020/09/advanced-economicsciencesprize2020.pdf.
  * Gkatzelis et al. [2021] Vasilis Gkatzelis, Rishi Patel, Emmanouil Pountourakis, and Daniel Schoepflin.  Prior-free clock auctions for bidders with interdependent values.  In _14th International Symposium on Algorithmic Game Theory (SAGT)_ , 2021.
  * Hajiaghayi et al. [2007] Mohammad Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm.  Automated online mechanism design and prophet inequalities.  volume 1, pages 58–65, 01 2007.
  * Immorlica et al. [2023] Nicole Immorlica, Sahil Singla, and Bo Waggoner.  Prophet inequalities with linear correlations and augmentations.  _ACM Transactions on Economics and Computation_ , 11, 09 2023.  doi: 10.1145/3623273.
  * Ito and Parkes [2006] Takayuki Ito and David C. Parkes.  Instantiating the contingent bids model of truthful interdependent value auctions.  In _Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems_ , page 1151–1158, 2006.
  * Jehiel and Moldovanu [2001] Philippe Jehiel and Benny Moldovanu.  Efficient design with interdependent valuations.  _Econometrica_ , 69(5):1237–1259, 2001.
  * Jehiel et al. [2006] Philippe Jehiel, Moritz Meyer ter Vehn, Benny Moldovanu, and William R. Zame.  The limits of ex post implementation.  _Econometrica_ , 74(3):585–610, 2006.  ISSN 00129682, 14680262.
  * Kesselheim et al. [2013] Thomas Kesselheim, Klaus Radke, Andreas Abels, and Berthold Vöcking.  An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions.  09 2013.  ISBN 978-3-642-40449-8.  doi: 10.1007/978-3-642-40450-4˙50.
  * Kleinberg and Weinberg [2012] Robert Kleinberg and S. Weinberg.  Matroid prophet inequalities.  _Proceedings of the Annual ACM Symposium on Theory of Computing_ , 01 2012.  doi: 10.1145/2213977.2213991.
  * Klemperer [1998] Paul Klemperer.  Auctions with almost common values: The ’wallet game’ and its applications.  _European Economic Review_ , 42(3-5):757–769, 1998.  URL https://EconPapers.repec.org/RePEc:eee:eecrev:v:42:y:1998:i:3-5:p:757-769.
  * Krengel and Sucheston [1978] Ulrich Krengel and L. Sucheston.  On semiamarts, amarts, and processes with finite value.  _Probability on Banach Spaces_ , pages 197–266, 01 1978.
  * Krengel and Sucheston [1977] Ulrich Krengel and Louis Sucheston.  Semiamarts and finite values.  _Bulletin of The American Mathematical Society - BULL AMER MATH SOC_ , 83, 10 1977.  doi: 10.1090/S0002-9904-1977-14378-4.
  * Lehmann et al. [2006] Benny Lehmann, Daniel Lehmann, and Noam Nisan.  Combinatorial auctions with decreasing marginal utilities.  _Games Econ. Behav._ , 55(2):270–296, 2006.
  * Li [2013] Yunan Li.  Approximation in mechanism design with interdependent values.  In _Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013_ , pages 675–676. ACM, 2013.  doi: 10.1145/2492002.2482580.  URL https://doi.org/10.1145/2492002.2482580.
  * Lu et al. [2022] Pinyan Lu, Enze Sun, and Chenghan Zhou.  Better approximation for interdependent SOS valuations.  In _WINE_ , volume 13778 of _Lecture Notes in Computer Science_ , pages 219–234. Springer, 2022.
  * Maskin [1992] Eric Maskin.  Auctions and privatization.  _Privatization, H. Siebert, ed. (Institut fur Weltwirtschaften der Universität Kiel: 1992)_ , 1992.
  * Milgrom and Weber [1982] Paul R Milgrom and Robert J Weber.  A theory of auctions and competitive bidding.  _Econometrica_ , 1982.
  * Myerson [1981] Roger B Myerson.  Optimal auction design.  _Mathematics of operations research_ , 6(1):58–73, 1981.
  * Reiffenhäuser [2019] Rebecca Reiffenhäuser.  An optimal truthful mechanism for the online weighted bipartite matching problem.  In Timothy M. Chan, editor, _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019_ , pages 1982–1993. SIAM, 2019.  doi: 10.1137/1.9781611975482.120.  URL https://doi.org/10.1137/1.9781611975482.120.
  * Roughgarden and Talgam-Cohen [2016] Tim Roughgarden and Inbal Talgam-Cohen.  Optimal and robust mechanism design with interdependent values.  _ACM Trans. Econ. Comput._ , 2016.
  * Samuel-Cahn [1984] Ester Samuel-Cahn.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  _The Annals of Probability_ , 12, 11 1984.  doi: 10.1214/aop/1176993150.
  * Samuel-Cahn [1991] Ester Samuel-Cahn.  Prophet inequalities for bounded negatively dependent random variables.  _Statistics & Probability Letters_, 12:213–216, 09 1991\.  doi: 10.1016/0167-7152(91)90080-B.
  * Wilson [1969] Robert B Wilson.  Communications to the editor—competitive bidding with disparate information.  _Management science_ , 1969.
  * Yao [1977] Andrew Chi-Chih Yao.  Probabilistic computations: Toward a unified measure of complexity (extended abstract).  In _FOCS_ , pages 222–227. IEEE Computer Society, 1977.

##  Appendix A Improved bounds for submodular valuations

In this section we present an online algorithm that obtains an improved
approximation ratio of $4$ for the secretary model when the valuations are
submodular over signals (for both the myopic and farsighted settings).

######  Definition 3 (Submodular over signals).

We say a valuation function $v(\cdot)$ is submodular over signals, if for any
$i\in[n]$ and signal profiles $\mathbf{s}\geq\mathbf{s}^{\prime}$ we have

$v(s_{i},\mathbf{s}_{-i})-v(s^{\prime}_{i},\mathbf{s}_{-i})\leq
v(s_{i},\mathbf{s}^{\prime}_{-i})-v(s^{\prime}_{i},\mathbf{s}^{\prime}_{-i})$

The following lemma is a generalization of the Key lemma from [18], which was
proved in [36].

######  Lemma 5.

For any monotone submodular valuation function $v$, and for any random subset
$A\subseteq[n]$ such that $A$ is drawn uniformly among subsets of size $k$, we
have

$\mathds{E}_{A}[v(\mathbf{s}_{A})]\geq\frac{k}{n}\cdot v(\mathbf{s})$

The algorithm is a slight modification of Algorithm 3. In particular, the
sampling phase involves $n/2$ agents instead of $n/e$.

At step $t$, when agent $t$ arrives, stop if:

  * •

$t>n/2$ (i.e., skip a constant fraction of agents), and

  * •

$v_{t}(\mathbf{s}_{[t]})>v_{i}(\mathbf{s}_{[t]})$ for all $i<t$.

ALGORITHM 5 4-approximation algorithm under submodular valuations.

We are now ready to prove the main results of this section. In fact we prove a
stronger statement that, in expectation, the myopic value of the accepted
agent is a $4$-approximation to the farsighted benchmark. This immediately
implies a $4$-approximation for both the myopic and farsighted settings.

######  Theorem 6.

Algorithm 5 is a $4$-approximation under submodular valuations. That is, the
expected (myopic) values of the accepted agent is at least
$\frac{1}{4}\max_{i}v_{i}(\mathbf{s})$.

###### Proof.

We define the random variable $T\in\\{1,\dots,n,\infty\\}$ to be the stopping
time of the algorithm. In the secretary setting, $n$ agents from a set $A$
arrive in a uniformly random order $a_{1},\dots,a_{n}$. Recall that we labeled
agents according to their arrival order, that is, in the algorithm,

$\forall i\in[n],\forall J\subseteq[n],\qquad
v_{i}(\mathbf{s}_{J}):=\bar{v}_{a_{i}}(\bar{\mathbf{s}}_{\\{a_{j}|j\in
J\\}}),$

where $\bar{v}$ and $\bar{\mathbf{s}}$ are the original, fixed valuation
functions and signals (determined adversarially) before applying the random
ordering. In particular, there exists an agent $a^{\star}\in A$ with the
largest value $OPT=\bar{v}_{a^{\star}}(\bar{\mathbf{s}})$. For convenience, we
define the set function

$\forall X\subseteq A,\qquad f(X):=\bar{v}_{a^{\star}}(\bar{s}_{X}),$

that is, $f(X)$ denotes the estimated value of $a^{\star}$ only using the
signals of $X\subseteq A$.

Next, we define the (random) set $A_{t}:=\\{a_{1},\dots,a_{t}\\}$ of agents
who have arrived at time $t$. Observe that the stopping rule of Algorithm 5
corresponds to Lemma 3 with $k=\lfloor n/2\rfloor$ and

$\forall S\subseteq A,\qquad\texttt{best}(S):=\text{argmax}_{a\in
S}\bar{v}_{a}(\bar{\mathbf{s}}_{S}).$

Using Lemma 3, the event where the algorithm stops at time $T=t$ is
independent of $A_{t}$, and has probability equal to

$\forall t>n/2,\qquad\mathds{P}[T=t\,|\,A_{t}]=\frac{\lfloor
n/2\rfloor}{t(t-1)}$ (7)

We write the expected welfare obtained by the algorithm as

$\displaystyle\mathds{E}[ALG]$ $\displaystyle\geq\sum_{t=\lceil
n/2\rceil}^{n}\mathds{E}[\mathds{1}[T=t]\cdot v_{t}(\mathbf{s}_{[t]})]$
(equality holds for myopic) $\displaystyle\geq\sum_{t=\lceil
n/2\rceil}^{n}\mathds{E}[\mathds{1}[T=t]\cdot
v_{t}(\mathbf{s}_{[t]})\cdot\mathds{1}[a^{\star}\in A_{t}]]$ (always smaller)
$\displaystyle\geq\sum_{t=\lceil n/2\rceil}^{n}\mathds{E}[\mathds{1}[T=t]\cdot
f(A_{t})\cdot\mathds{1}[a^{\star}\in A_{t}]]$ (by the stopping condition)
$\displaystyle=\sum_{t=\lceil n/2\rceil}^{n}\frac{\lfloor
n/2\rfloor}{t(t-1)}\cdot\mathds{E}[f(A_{t})\cdot\mathds{1}[a^{\star}\in
A_{t}]]$ (using Equation 7) $\displaystyle=\sum_{t=\lceil
n/2\rceil}^{n}\frac{\lfloor
n/2\rfloor}{t(t-1)}\cdot\frac{t}{n}\cdot\mathds{E}[f(A_{t})\,|\,a^{\star}\in
A_{t}]$ ($a^{\star}\in A_{t}$ with probability $t/n$)

Next we define

$\forall t\in[n],\qquad\alpha_{t}:=\mathds{E}[f(A_{t})\,|\,a^{\star}\in
A_{t}].$

which gives the inequality

$\mathds{E}[ALG]\geq\frac{\lfloor n/2\rfloor}{n}\sum_{t=\lceil
n/2\rceil}^{n}\frac{\alpha_{t}}{t-1}.$

Alternatively, $\alpha_{t}$ it is the expected value of
$f(X\cup\\{a^{\star}\\})$, given a random subset $X\subseteq
A\setminus\\{a^{\star}\\}$ of size $|X|=t-1$. In particular, using Lemma 5 we
have that $\alpha_{t}\geq\frac{t-1}{n-1}\cdot OPT$. Therefore

$\mathds{E}[ALG]\geq\frac{\lfloor n/2\rfloor}{n}\cdot\frac{n-\lceil
n/2\rceil+1}{n-1}\cdot OPT\geq\frac{OPT}{4},$

which concludes the proof. ∎