# Optimal Stopping with Interdependent Values

Simon Mauras, Divyarthi Mohan, Rebecca Reiffenhäuser

► To cite this version:

Simon Mauras, Divyarthi Mohan, Rebecca Reiffenhäuser. Optimal Stopping with Interdependent Values. EC 2024 - 25th ACM Conference on Economics and Computation, Jul 2024, New Haven, United States. pp.246-265, 10.1145/3670865.3673628 . hal-04923199

HAL Id: hal-04923199

https://hal.science/hal-04923199v1

Submitted on 31 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Optimal Stopping with Interdependent Values

SIMON MAURAS*, INRIA, FairPlay joint team, France

DIVYARTHI MOHAN, Tel Aviv University, Israel

REBECCA REIFFENHÄUSER, University of Amsterdam, Netherlands

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.

**CCS Concepts: • Theory of computation → Algorithmic game theory and mechanism design; Online algorithms.**

**Additional Key Words and Phrases:** Optimal Stopping, Online Selection, Truthful Mechanisms

## ACM Reference Format:

Simon Mauras, Divyarthi Mohan, and Rebecca Reiffenhäuser. 2024. Optimal Stopping with Interdependent Values. In *Conference on Economics and Computation (EC '24), July 8–11, 2024, New Haven, CT, USA*. ACM, New York, NY, USA, 20 pages. https://doi.org/10.1145/3670865.3673628

## 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

Authors' Contact Information: Simon Mauras, simon.mauras@inria.fr, INRIA, FairPlay joint team, France; Divyarthi Mohan, divyarthim@tau.ac.il, Tel Aviv University, Israel; Rebecca Reiffenhäuser, r.e.m.reiffenhauser@uva.nl, University of Amsterdam, Netherlands.

<figure><img src="image_2.png" /></figure>

<footnote>*Also with Tel Aviv University.</footnote>
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 70s, each of the *n* numbers is assumed to be drawn independently from a known distribution *D*ᵢ on arrival. This assumption allows for a (best-possible) 2-approximation to the expected optimum via simple threshold policies (e.g., Krengel and Sucheston [1978]). 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 1/e-approximation to the maximum (originally for the ordinal variant) was known since the early 60s (see Dynkin [1963]). 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 [1982] building up on Wilson [1969],<fnref n="1" /> 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*ᵢ and a public valuation function *v*ᵢ(·) that maps the signals of all buyers (*s*₁, . . . , *s*ₙ) to a value for the item; that is, *v*ᵢ(s) is *i*'s value for the item given a signal profile **s** = (*s*₁, . . . , *s*ₙ). 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* [Ausubel et al., 1999, Dasgupta and Maskin, 2000, Maskin, 1992]. 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 [Eden et al., 2019, 2023, Lu et al., 2022]. Informally, a valuation function is submodular over signals if for each *j* the impact of increasing *s*ⱼ is higher when the other signals *s*₋ⱼ 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

<footnote n="1">¹The 2020 Economics Nobel Prize was awarded to Milgrom and Wilson for their work on IDV and auction design [for the Prize in Economic Sciences in Memory of Alfred Nobel, 2020].</footnote>
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 distributions<fnref n="2" />.

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.

<table><caption>Table 1. Approximation ratio of our algorithms (no incentive constraints) and mechanisms (EPIC), when agents have subadditive-over-signals valuations.</caption><thead><tr><th></th><th>Agents</th><th>Algorithm</th><th>Mechanism</th></tr></thead><tbody><tr><td rowspan="2">Prophet</td><td>farsighted</td><td>Ω(n) (Theorem 1)</td><td>Ω(n)</td></tr><tr><td>myopic</td><td>≤ 4 (Theorem 2)</td><td>≤ 8 (Theorem 3)</td></tr><tr><td rowspan="2">Secretary</td><td>farsighted</td><td>≤ 2e (Theorem 4)</td><td>≤ 4e (Theorem 5)</td></tr><tr><td>myopic</td><td>≤ 2e (Theorem 4)</td><td>≤ 4e (Theorem 5)</td></tr></tbody></table>

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

<footnote n="2">²Note 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.</footnote>
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 [Ausubel et al., 1999, Che et al., 2015, Dasgupta and Maskin, 2000, Ito and Parkes, 2006, Jehiel and Moldovanu, 2001, Jehiel et al., 2006]. 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., [Chawla et al., 2014, Chen et al., 2022, Cohen et al., 2023, Eden et al., 2018, 2019, 2021, 2022, Gkatzelis et al., 2021, Roughgarden and Talgam-Cohen, 2016]). Eden et al. [2018] consider a setting with an approximate single-crossing condition and obtain approximately optimal welfare truthfully. In a breakthrough result, Eden et al. [2019] establish a 4-approximation when the valuations satisfy submodularity<fnref n="3" /> over signals without any single-crossing type assumption and also extend the results to combinatorial auctions under an additional separability condition. Lu et al. [2022] provide an improved approximation bound of 3.315 for single-item auctions and Amer and Talgam-Cohen [2021] provide a 2-approximation in the special case of binary signals. More recently, works of Eden et al. [2023, 2024, 2022] 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 [2016] and Li [2013] study simple prior-independent mechanisms that obtain approximately optimal revenue under different assumptions, and Chawla et al. [2014] 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. [2010] study interdependence in matching markets, Cohen et al. [2023] study the public projects setting with interdependent values and Birmpas et al. [2023] consider interdependence in the fair division problem.

*Prophet inequality.* Prophet Inequalities, originally introduced by Krengel and Sucheston [1977, 1978] and Samuel-Cahn [1984], 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. [2007] and Chawla et al. [2010], prophet inequalities have been obtained for a large variety of prominent problem settings, e.g. online selection with matroid constraints [Kleinberg and Weinberg, 2012], or online matchings [Alaei et al., 2012], with a strong focus on economic settings like combinatorial auctions [Correa and Cristi, 2023, Dütting et al., 2020]. 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. [Immorlica et al., 2023, Samuel-Cahn, 1991]). 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 [Brunel and Krengel, 1979], who prove the existence of a

<footnote n="3">³Eden et al. [2019] observe in their conclusion that some of their results extend to subadditive valuation functions.</footnote>
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 [1963], 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. [2007]. Similarly to prophet inequalities, one major focus has been on mechanism design. For example, the optimal approximation factor of $\frac{1}{e}$ has been recovered for bipartite matchings [Reiffenhäuser, 2019] and XOS combinatorial auctions [Kesselheim et al., 2013]. 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}_{\ge 0}^n \to \mathbb{R}_{\ge 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 = (\mathbb{1}_{1 \in X} \cdot s_1, \dots, \mathbb{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 [Wilson, 1969] and the resale model [Klemperer, 1998, Myerson, 1981].

**Definition 1** (Subadditive over signals). We say a valuation function $v(\cdot)$ is subadditive over signals, if for any signal profile $s$ and any $X \subseteq [n]$ we have

$$v(\mathbf{s}) \le 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 [Amer and Talgam-Cohen, 2021, Cohen et al., 2023, Eden et al., 2019, 2023, 2022, Lu et al., 2022].

## 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(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(s) \ge 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 $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}, \mathbf{s}'_i$ we have

$$x_i(s_{[i]}) \cdot v - p_i(s) \ge x_i(s_{[i-1]}, s'_i) \cdot v - p_i(s_{-i}, s'_i)$$

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

Roughgarden and Talgam-Cohen [2016] 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(s_{[i]})$ which is monotone in $s_i$, that is

$$\forall i, \forall \mathbf{s}, \forall s'_i \ge s_i, \quad x_i(s_{[i]}) \le x_i(s_{[i-1]}, s'_i),$$

there exists a payment $p_i(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 $s_{[i]}$.

**PROOF.** From Roughgarden and Talgam-Cohen [2016]. The payment is equal to

$$p_i(s) = x_i(s_{[i]}) \cdot \inf\{v_i(s_{-i}, s'_i) | s'_i \ge 0 \text{ such that } x_i(s_{[i-1]}, s'_i) = 1\}$$

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

$$p_i(s_{[i]}) = x_i(s_{[i]}) \cdot \inf\{v_i(s_{[i-1]}, s'_i) | s'_i \ge 0 \text{ such that } x_i(s_{[i-1]}, s'_i) = 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. $\square$

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(s) = 2^i \cdot 1[s_n \ge 1 - 1/2^i]$. Then the expected maximum value is

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

Note that in the myopic setting, all agents always have valuation 0, except for the $n^{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(s) = 2^i$ with probability $1/2^i$ and 0 otherwise. Using Yao's Lemma [Yao, 1977], randomized algorithms cannot give any improved approximation ratio on this random instance. Thus, we cannot do better than an $\Omega(n)$ approximation. $\square$

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(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. $\square$

A model which addresses the impossibilities raised by Theorem 1 and Proposition 1 was previously considered in the work of Brunel and Krengel [1979], 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 - \epsilon)$, and $s_1 = \frac{1}{\epsilon}$ with very small probability $\epsilon$. 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 = \frac{1}{\epsilon}$ being drawn). Every agent beats the threshold of $\frac{n}{2}$, and the algorithm will realize only a value of $\frac{1}{\epsilon}$ 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 $\le 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(s_{[t]})$ satisfies the following two conditions: (1) it is at least as much as the threshold $X = \mathbb{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]})$).

<caption>**ALGORITHM 1:** 4-approximation algorithm with myopic agents.</caption>

Set threshold

$$X = \mathbb{E}[\max_{i \in [n]} v_i(s_{[i]})]/2.$$

Stop at the first time $t$ such that:

* $v_t(s_{[t]}) \ge X$, and

* $v_t(s_{[t]}) \ge v_i(s_{[t]})$ for all $i > t$

**THEOREM 2.** *Algorithm 1 is 4-competitive. That is, it obtains an expected (myopic) welfare of at least $\frac{1}{4}\mathbb{E}[\max_{i \in [n]} v_i(s_{[i]})]$.*

**PROOF.** Let $I \in \argmax_i v_i(s_{[i]})$ be the random variable that denotes the index of the maximum value agent and let $T \in \{1, \dots, n, \infty\}$ be the stopping time of Algorithm 1. Notice that either the algorithm stops at $T \le 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(s_{[I]}) < X$, which implies all $v_i(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

$$v_I(s_{[I]}) \le \mathbb{1}[T = \infty] \cdot v_I(s_{[I]}) \\ + \mathbb{1}[T < \infty] \cdot v_I(s_{[T]}) \\ + \mathbb{1}[T < I] \cdot v_I(s_{[T+1,I]}).$$

Recall that, if the algorithm did not stop then $v_I(s_{[I]}) < X$, thus bounding the first term as

$$\mathbb{1}[T = \infty] \cdot v_I(s_{[I]}) < \mathbb{1}[T = \infty] \cdot X. \qquad (1)$$
However, if the algorithm stops then $v_T(s_{[T]}) \ge v_I(s_{[T]})$, thus bounding the second term as

$$1[T < \infty] \cdot v_I(s_{[T]}) \le 1[T < \infty] \cdot v_T(s_{[T]}) \quad (2)$$

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

$$\begin{align*}
\mathbb{E}[1[T < I] \cdot v_I(s_{[T+1,I]})] &\le \sum_{t=1}^{n} \mathbb{E}[1[T = t] \cdot \max_{j>t} v_j(s_{[t+1,j]})] \\
&= \sum_{t=1}^{n} \mathbb{E}[1[T = t]] \cdot \mathbb{E}[\max_{j>t} v_j(s_{[t+1,j]})] \\
&\le \mathbb{P}[T < \infty] \cdot 2X \\
&\le \mathbb{P}[T < \infty] \cdot X + \mathbb{E}[1[T < \infty] \cdot v_T(s_{[T]})], \tag{3}
\end{align*}$$

where the first inequality follows by the law of total probability and using the fact that $I > t$ to upper-bound $v_I(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(s_{[T]}) \ge X$ whenever the algorithm stops.

Overall by putting together Equations (1) to (3) we have the following bound on $\mathbb{E}[v_I(s_{[I]})]$

$$\begin{align*}
\mathbb{E}[v_I(s_{[I]})] &\le \mathbb{P}[T = \infty] \cdot X + \mathbb{P}[T < \infty] \cdot X \\
&\quad + 2 \cdot \mathbb{E}[1[T < \infty] \cdot v_T(s_{[T]})] \\
&\le X + 2 \cdot \mathbb{E}[1[T < \infty] \cdot v_T(s_{[T]})].
\end{align*}$$

Observe that the expected welfare of the algorithm is exactly $\mathbb{E}[ALG] = \mathbb{E}[1[T < \infty] \cdot v_T(s_{[T]})]$ and by definition of $X$ it holds

$$\mathbb{E}[v_I(s_{[I]})] \le \frac{1}{2} \cdot \mathbb{E}[v_I(s_{[I]})] + 2 \cdot \mathbb{E}[ALG],$$

which simplifies to

$$\frac{1}{2} \cdot \mathbb{E}[v_I(s_{[I]})] \le 2 \cdot \mathbb{E}[ALG],$$

yielding a 4-approximation. $\square$

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,<fnref n="4" /> 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'_t) | s'_t \ge 0 \text{ s.t. } v_t(s_{[t-1]}, s'_t) \ge v_i(s_{[t-1]}, s'_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 = 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, $s_{[t]}$.

**ALGORITHM 2:** 8-approximation mechanism with myopic agents.

Set threshold

$$X := \mathbb{E}[\max_{i \in [n]} v_i(s_{[i]})]/2.$$

Let $T$ be the first time $t$ such that $v_t(s_{[t]}) \ge 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 $\max_{i>T} v_i(s_{[T]})$.

**THEOREM 3.** *Algorithm 2 is a 8-approximation, that is, it obtains an expected (myopic) welfare of at least $\frac{1}{8}\mathbb{E}[\max_{i \in [n]} v_i(s_{[i]})]$.*

**PROOF.** The proof follows the same principle as that for the algorithmic setting. Let $I \in \max_{i \in [n]} v_i(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(s_{[t]}) \ge 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 \le I$, or $T = \infty$, because if $v_I(s_{[I]}) < X$ then $v_t(s_{[t]}) < X$ for all $t$. Thus, using the subadditivity of $v_I$, we can write

$$\begin{aligned} v_I(s_{[I]}) &\le 1[T = \infty] \cdot v_I(s_{[I]}) \\ &\quad + 1[T < \infty] \cdot v_I(s_{[T]}) \\ &\quad + 1[T < I] \cdot v_I(s_{[T+I]}) \end{aligned}$$

If the algorithm did not stop, then $v_I(s_{[I]}) < X$, which bounds the first term as

$$1[T = \infty] \cdot v_I(s_{[I]}) \le 1[T = \infty] \cdot X$$

We next bound the last term in expectation,

$$\begin{aligned} \mathbb{E}[1[T < I] \cdot v_I(s_{[T+I]})] &\le \sum_{t=1}^{n} \mathbb{E}[1[T = t] \cdot \max_{j>t} v_j(s_{[t+1,j]})] \\ &= \sum_{t=1}^{n} \mathbb{E}[1[T = t]] \cdot \mathbb{E}[\max_{j>t} v_j(s_{[t+1,j]})] \\ &\le \mathbb{P}[T < \infty] \cdot 2X \\ &\le \mathbb{P}[T < \infty] \cdot X + \mathbb{E}[1[T < \infty] \cdot v_T(s_{[T]})], \end{aligned}$$

<footnote n="4">⁴The valuations satisfy the single crossing conditions if for all $i, j, s_i, s_{-i}$, we have $\partial_i v_i(s)/\partial s_i \ge \partial_i v_j(s)/\partial s_j$.</footnote>
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 the first time $t$ when $v_I(s_{[T]}) \ge X$ 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(s_{[T]}) \ge X$ by definition.

Overall, this gives the following bound on the expected optimum $E[v_I(s_{[I]})]$

$$ 
\begin{aligned}
E[v_I(s_{[I]})] &\le P[T = \infty] \cdot X + P[T < \infty] \cdot X \\
&\quad + E[1[T < \infty] \cdot v_I(s_{[T]})] \\
&\quad + E[1[T < \infty] \cdot v_T(s_{[T]})].
\end{aligned}
$$

Now, observe that by design of the algorithm we have

$$ E[1[T < \infty] \cdot v_T(s_{[T]})] + E[1[T < I] \cdot v_I(s_{[T]})] \le 2 \cdot E[ALG], \quad (4) $$

where we simply bound $v_I(s_{[T]}) \le \max_{J>T} v_J(s_{[T]})$ for $T < I$.

Thus, plugging in Eq. (4) and using the definition of $X = E[v_I(s_{[I]})]/2$ we get

$$ \frac{1}{2} \cdot E[v_I(s_{[I]})] \le 2 \cdot E[ALG] + E[1[T = I] \cdot v_I(s_{[I]})]. $$

Finally, we bound $E[1[T = I] \cdot v_I(s_{[I]})]$ by $2 \cdot E[ALG]$ to obtain

$$ \frac{1}{2} \cdot E[v_I(s_{[I]})] \le 4 \cdot E[ALG], $$

resulting in an 8-approximation. $\square$

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

# 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 \ge 0$, and

* $a_t = \text{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, \quad \mathbb{P}[T = t | \{a_1, \dots, a_t\} = S] = \frac{k}{t(t-1)}. $$

**PROOF.** We will show by induction on $t \ge k$ that

$$ \forall S \subseteq A \text{ such that } |S| = t, \quad \mathbb{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

$$ \mathbb{P}[T > t + 1 | \{a_1, \dots, a_{t+1}\} = S] = \mathbb{P}[T > t \text{ and } a_{t+1} \neq \text{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

$$ \mathbb{P}[T > t + 1 | \{a_1, \dots, a_{t+1}\} = S] = \frac{1}{|S|} \sum_{\substack{a \in S \\ a \neq \text{best}(S)}} \mathbb{P}[T > t | \{a_1, \dots, a_t\} = S \setminus \{a\}] $$

Finally, using the induction hypothesis, we have

$$ \mathbb{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

$$ \begin{aligned} \mathbb{P}[T = t | \{a_1, \dots, a_t\} = S] &= \mathbb{P}[T > t - 1 \text{ and } a_t = \text{best}(S) | \{a_1, \dots, a_t\} = S] \\ &= \frac{1}{|S|} \cdot \mathbb{P}[T > t - 1 | \{a_1, \dots, a_{t-1}\} = S \setminus \text{best}(S)], \end{aligned} $$

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

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

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

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

* $v_t(s_{[t]}) > v_i(s_{[t]})$ for all $i < t$.

**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(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], \quad v_i(s_J) := \bar{v}_{a_i}(\bar{s}_{\{a_j | j \in J\}}), $$

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

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

that is, $f(X)$ denotes the estimated value of $a^*$ 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, \quad \text{best}(S) := \underset{a \in S}{\operatorname{argmax}} \bar{v}_a(\bar{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, \quad \mathbb{P}[T = t | A_t] = \frac{\lfloor n/e \rfloor}{t(t-1)} \quad (5) $$

We write the expected welfare obtained by the algorithm as

$$ \mathbb{E}[ALG] \geq \sum_{t=[n/e]}^{n} \mathbb{E}[1[T=t] \cdot v_t(s_{[t]})] \quad (\text{equality holds for myopic}) $$

$$ \geq \sum_{t=[n/e]}^{n} \mathbb{E}[1[T=t] \cdot v_t(s_{[t]}) \cdot 1[a^* \in A_t]] \quad (\text{always smaller}) $$

$$ \geq \sum_{t=[n/e]}^{n} \mathbb{E}[1[T=t] \cdot f(A_t) \cdot 1[a^* \in A_t]] \quad (\text{by the stopping condition}) $$

$$ = \sum_{t=[n/e]}^{n} \frac{\lfloor n/e \rfloor}{t(t-1)} \cdot \mathbb{E}[f(A_t) \cdot 1[a^* \in A_t]] \quad (\text{using Equation (5)}) $$
$$= \sum_{t=[n/e]}^{n} \frac{\lfloor n/e \rfloor}{t(t-1)} \cdot \frac{t}{n} \cdot \mathbb{E}[f(A_t) | a^* \in A_t] \quad (a^* \in A_t \text{ with probability } t/n)$$

Next we define

$$\forall t \in [n], \quad \alpha_t := \mathbb{E}[f(A_t) | a^* \in A_t].$$

which gives the inequality

$$\mathbb{E}[\text{ALG}] \geq \frac{\lfloor n/e \rfloor}{n} \sum_{t=[n/e]}^{n} \frac{\alpha_t}{t-1}.$$

Alternatively, $\alpha_t$ is the expected value of $f(X \cup \{a^*\})$, given a random subset $X \subseteq A \setminus \{a^*\}$ of size $|X| = t - 1$. In particular, $\alpha_n = \text{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

$$\alpha_n = f(A) = \mathbb{E}_{A_t}[f(A) | a^* \in A_t] \quad (\text{by definition})$$

$$\leq \mathbb{E}_{A_t}[f(A_t) + f(A \setminus A_t) | a^* \in A_t] \quad (\text{by subadditivity})$$

$$\leq \mathbb{E}_{A_t}[f(A_t) + f(A \setminus A_t \cup \{a^*\}) | a^* \in A_t] \quad (\text{by monotonicity})$$

$$= \mathbb{E}_{A_t}[f(A_t) | a^* \in A_t] + \mathbb{E}_{A_{n-t+1}}[f(A_{n-t+1}) | a^* \in A_{n-t+1}] \quad (\text{by symmetry})$$

$$= \alpha_t + \alpha_{n-t+1} \quad (\text{by definition})$$

Finally, we will split the sum from $t_0 = \lfloor n/e \rfloor$ to $n$ in three: from $t_0$ to $t_1 = \lfloor n/(e-1) \rfloor$, from $t_1$ to $t_2 = n - \lfloor n/e \rfloor + 1$, and from $t_2$ to $n$. By monotonicity of the $\alpha_t$'s, we have that

$$\begin{aligned} \sum_{t=[n/e]} \frac{\alpha_t}{t-1} &\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} \\ &\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) \\ &\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) \\ &\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) \\ &\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) \end{aligned}$$

Multiplying both sides by $\lfloor n/e \rfloor/n$, we obtain that $\text{OPT}/\mathbb{E}[\text{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 \to \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'_t)|s'_t \geq 0 \text{ s.t. } v_t(s_{[t-1]}, s'_t) \geq v_i(s_{[t-1]}, s'_t) \text{ for all } i > t\},$$
and for myopic agents

$$p_t = \inf \{ v_t(s_{[t-1]}, s'_t) | s'_t \ge 0 \text{ s.t. } v_t(s_{[t-1]}, s'_t) \ge v_i(s_{[t-1]}, s'_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 [Eden et al., 2019], which achieves a 4-approximation in the offline setting, with the e-approximation stopping rule of the standard secretary problem.

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

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(s_{[t_0]} \cup \{t\}) > v_i(s_{[t_0]} \cup \{i\})$ for all $t_0 < i < t$.

At the end, charge $t$ a price of $\inf \{v_t(s_{-t}, s'_t) | s'_t \ge 0 \text{ s.t. } v_t(s_{[t_0]}, s'_t) > \max_{t_0 < i < t} v_i(s_{[t_0]} \cup \{i\})\}$.

**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(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], \quad v_i(s_J) := \bar{v}_{a_i}(\bar{s}_{\{a_j | j \in J\}}),$$

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

$$\forall X \subseteq A, \quad f(X) := \bar{v}_{a^*}(\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 then only starts at time $t_0 + 1$. More formally, for every fixed set $A_{t_0} = R$ we define

$$\forall S \subseteq A \setminus R, \quad \text{best}_R(S) := \underset{a \in S}{\operatorname{argmax}} \bar{v}_a(s_{R \cup \{a\}}).$$

Applying Lemma 3 to the mechanism defined by best$_R$ and starting at time $t_0 + 1$, we have

$$\forall t > t_1, \quad \mathbb{P}[T = t | A_t, A_{t_0}] = \frac{t_1 - t_0}{(t - t_0)(t - t_0 - 1)}. \qquad (6)$$

Next, we write the expected welfare of the algorithm as

$$\mathbb{E}[\text{ALG}] \ge \sum_{t=t_1+1}^{n} \mathbb{E}[1[T=t] \cdot v_t(s_{[t]})] \qquad (\text{equality holds for myopic})$$

$$\ge \sum_{t=t_1+1}^{n} \mathbb{E}[1[T=t] \cdot v_t(s_{[t_0]} \cup \{t\}) \cdot 1[a^* \in A_t \setminus A_{t_0}]] \qquad (\text{always smaller})$$

$$\ge \sum_{t=t_1+1}^{n} \mathbb{E}[1[T=t] \cdot f(A_{t_0} \cup \{a^*\}) \cdot 1[a^* \in A_t \setminus A_{t_0}]] \qquad (\text{stopping condition})$$
$$ 
\begin{align*}
&\geq \sum_{t=t_1+1}^{n} \frac{t_1 - t_0}{(t - t_0)(t - t_0 - 1)} \cdot \mathrm{E}[f(A_{t_0} \cup \{a^*\}) \cdot 1[a^* \in A_t \setminus A_{t_0}]] \quad (\text{using Equation (6)}) \\
&\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 \mathrm{E}[f(A_{t_0} \cup \{a^*\})],
\end{align*}
$$

where the last inequality follows because $(\mathrm{P}[a^* \in A_t \setminus A_{t_0}] = (t - t_0)/n)$.

Using the subadditivity of $f$, we have that

$$ 
\begin{align*}
\mathrm{OPT} = f(A) &= \mathrm{E}[f(A)] \tag{by definition} \\
&\leq \mathrm{E}[f(A_{t_0} \cup \{a^*\}) + f(A \setminus (A_{t_0} \cup \{a^*\}))] \tag{by subadditivity} \\
&\leq 2 \cdot \mathrm{E}[f(A_{t_0} \cup \{a^*\})] \tag{by symmetry}
\end{align*}
$$

Overall, we obtain that

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

Overall, we obtain $\mathrm{OPT}/\mathrm{E}[\mathrm{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$. $\square$

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(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. $\square$

## 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. [2023, 2022] 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).

Since our algorithms recover the optimal approximation ratios (for prophet and secretary) when handling instances without interdependence, understanding if there is a separation between the interdependent settings and the standard setting with no interdependence is an important direction.

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. [2006] (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.

## Acknowledgments

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

## References

* Saeed Alaei, Mohammad Taghi Hajiaghayi, and Vahid Liaghat. 2012. Online prophet-inequality matching with applications to ad allocation. *Proceedings of the ACM Conference on Electronic Commerce*. https://doi.org/10.1145/2229012.2229018

* Ameer Amer and Inbal Talgam-Cohen. 2021. Auctions with Interdependence and SOS: Improved Approximation. In *14th International Symposium on Algorithmic Game Theory (SAGT)*.

* Lawrence M Ausubel et al. 1999. A generalized Vickrey auction. *Econometrica* (1999).

* Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. 2007. Matroids, secretary problems, and online mechanisms. *SODA*, 434–443.

* Georgios Birmpas, Tomer Ezra, Stefano Leonardi, and Matteo Russo. 2023. Fair Division with Interdependent Values. *CoRR* abs/2305.14096 (2023). https://doi.org/10.48550/ARXIV.2305.14096 arXiv:2305.14096

* Antoine Brunel and Ulrich Krengel. 1979. Parier avec un prophète dans le cas d'un processus sous-additif. (1979). https://gallica.bnf.fr/ark:/12148/bpt6k98138170/f73.item

* Archishman Chakraborty, Alessandro Citanna, and Michael Ostrovsky. 2010. Two-sided matching with interdependent values. *Journal of Economic Theory* 145, 1 (2010), 85–105.

* Shuchi Chawla, Hu Fu, and Anna Karlin. 2014. Approximate Revenue Maximization in Interdependent Value Settings. In *15th ACM Conference on Economics and Computation (EC)*.

* Shuchi Chawla, Jason Hartline, David Malec, and Balasubramanian Sivan. 2010. Sequential Posted Pricing and Multi-parameter Mechanism Design. *Northwestern University, Center for Mathematical Studies in Economics and Management Science, Discussion Papers* (06 2010). https://doi.org/10.1145/1807406.1807428

* Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima. 2015. Efficient assignment with interdependent values. *Journal of Economic Theory* 158 (2015), 54–86.

* Yiling Chen, Alon Eden, and Juntao Wang. 2022. Cursed yet Satisfied Agents. In *13th Innovations in Theoretical Computer Science Conference (ITCS 2022)*.
Avi Cohen, Michal Feldman, Divyarthi Mohan, and Inbal Talgam-Cohen. 2023. Interdependent Public Projects. In *34th ACM-SIAM Symposium on Discrete Algorithms (SODA)*.

Jose Correa and Andrés Cristi. 2023. A Constant Factor Prophet Inequality for Online Combinatorial Auctions. 686–697. https://doi.org/10.1145/3564246.3585151

Partha Dasgupta and Eric Maskin. 2000. Efficient Auctions. *The Quarterly Journal of Economics* (2000).

E. Dynkin. 1963. The Optimum Choice of the Instant for Stopping a Markov Process. *Soviet Mathematics. Doklady* 4 (01 1963).

Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. 2020. Prophet Inequalities Made Easy: Stochastic Optimization by Pricing NonStochastic Inputs. *SIAM J. Comput.* 49 (04 2020), 540–582. https://doi.org/10.1137/20M1323850

Alon Eden, Michal Feldman, Amos Fiat, and Kira Goldner. 2018. Interdependent Values Without Single-Crossing. In *19th ACM Conference on Economics and Computation (EC)*.

Alon Eden, Michal Feldman, Amos Fiat, Kira Goldner, and Anna R. Karlin. 2019. Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue. In *20th ACM Conference on Economics and Computation (EC)*.

Alon Eden, Michal Feldman, Kira Goldner, Simon Mauras, and Divyarthi Mohan. 2023. 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*. IEEE, 148–163. https://doi.org/10.1109/FOCS57990.2023.000108

Alon Eden, Michal Feldman, Simon Mauras, and Divyarthi Mohan. 2024. Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids. *CoRR* abs/2402.12017 (2024). https://doi.org/10.48550/ARXIV.2402.12017 arXiv:2402.12017

Alon Eden, Michal Feldman, Inbal Talgam-Cohen, and Ori Zviran. 2021. PoA of Simple Auctions with Interdependent Values. In *35th AAAI Conference on Artificial Intelligence (AAAI)*.

Alon Eden, Kira Goldner, and Shuran Zheng. 2022. Private Interdependent Valuations. In *33rd ACM-SIAM Symposium on Discrete Algorithms (SODA)*.

The Committee for the Prize in Economic Sciences in Memory of Alfred Nobel. 2020. Scientific Background on the Sveriges Riksbank Prize in Economic Sciences. https://www.nobelprize.org/uploads/2020/09/advanced-economicsciencesprize2020.pdf

Vasilis Gkatzelis, Rishi Patel, Emmanouil Pountourakis, and Daniel Schoepflin. 2021. Prior-free clock auctions for bidders with interdependent values. In *14th International Symposium on Algorithmic Game Theory (SAGT)*.

Mohammad Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. 2007. Automated Online Mechanism Design and Prophet Inequalities. *Proceedings of the National Conference on Artificial Intelligence* 1, 58–65.

Nicole Immorlica, Sahil Singla, and Bo Waggoner. 2023. Prophet Inequalities with Linear Correlations and Augmentations. *ACM Transactions on Economics and Computation* 11 (09 2023). https://doi.org/10.1145/3623273

Takayuki Ito and David C. Parkes. 2006. Instantiating the Contingent Bids Model of Truthful Interdependent Value Auctions. In *Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems*. 1151–1158.

Philippe Jehiel and Benny Moldovanu. 2001. Efficient Design with Interdependent Valuations. *Econometrica* 69, 5 (2001), 1237–1259.

Philippe Jehiel, Moritz Meyer ter Vehn, Benny Moldovanu, and William R. Zame. 2006. The Limits of Ex Post Implementation. *Econometrica* 74, 3 (2006), 585–610.

Thomas Kesselheim, Klaus Radke, Andreas Abels, and Berthold Vöcking. 2013. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. https://doi.org/10.1007/978-3-642-40450-4_50

Robert Kleinberg and S. Weinberg. 2012. Matroid Prophet Inequalities. *Proceedings of the Annual ACM Symposium on Theory of Computing* (01 2012). https://doi.org/10.1145/2213977.2213991

Paul Klemperer. 1998. Auctions with almost common values: The 'Wallet Game' and its applications. *European Economic Review* 42, 3-5 (1998), 757–769. https://EconPapers.repec.org/RePEc:eee:eecrev:v:42:y:1998:i:3-5:p:757-769

Ulrich Krengel and Louis Sucheston. 1977. Semiamarts and finite values. *Bulletin of The American Mathematical Society - BULL AMER MATH SOC* 83 (10 1977). https://doi.org/10.1090/S0002-9904-1977-14378-4

Ulrich Krengel and L. Sucheston. 1978. On semiamarts, amarts, and processes with finite value. *Probability on Banach Spaces* (01 1978), 197–266.

Benny Lehmann, Daniel Lehmann, and Noam Nisan. 2006. Combinatorial auctions with decreasing marginal utilities. *Games Econ. Behav.* 55, 2 (2006), 270–296.

Yunan Li. 2013. 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*. ACM, 675–676. https://doi.org/10.1145/2492002.2482580

Pinyan Lu, Enze Sun, and Chenghan Zhou. 2022. Better Approximation for Interdependent SOS Valuations. In *WINE (Lecture Notes in Computer Science, Vol. 13778)*. Springer, 219–234.

Eric Maskin. 1992. Auctions and Privatization. *Privatization, H. Siebert, ed.* (Institut für Weltwirtschaften der Universität Kiel: 1992) (1992).
Paul R Milgrom and Robert J Weber. 1982. A theory of auctions and competitive bidding. *Econometrica* (1982).

Roger B Myerson. 1981. Optimal auction design. *Mathematics of operations research* 6, 1 (1981), 58–73.

Rebecca Reiffenhäuser. 2019. An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem. In *Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019*, Timothy M. Chan (Ed.). SIAM, 1982–1993. https://doi.org/10.1137/1.9781611975482.120

Tim Roughgarden and Inbal Talgam-Cohen. 2016. Optimal and Robust Mechanism Design with Interdependent Values. *ACM Trans. Econ. Comput.* (2016).

Ester Samuel-Cahn. 1984. Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables. *The Annals of Probability* 12 (11 1984). https://doi.org/10.1214/aop/1176993150

Ester Samuel-Cahn. 1991. Prophet inequalities for bounded negatively dependent random variables. *Statistics & Probability Letters* 12 (09 1991), 213–216. https://doi.org/10.1016/0167-7152(91)90080-B

Robert B Wilson. 1969. Communications to the editor—competitive bidding with disparate information. *Management science* (1969).

Andrew Chi-Chih Yao. 1977. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In *FOCS. IEEE Computer Society*, 222–227.

## 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 $s \ge s'$ we have

$$v(s_i, s_{-i}) - v(s'_i, s_{-i}) \le v(s_i, s'_{-i}) - v(s'_i, s'_{-i})$$

The following lemma is a generalization of the Key lemma from [Eden et al., 2019], which was proved in [Lu et al., 2022].

**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

$$E_A[v(s_A)] \ge \frac{k}{n} \cdot v(s)$$

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

**ALGORITHM 5:** 4-approximation algorithm under submodular valuations.

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

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

* $v_t(s_{[t]}) > v_i(s_{[t]})$ for all $i < t$.

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(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], \quad v_i(s_J) := \bar{v}_{a_i}(\bar{s}_{\{a_j, j \in J\}}),$$
where $\bar{\nu}$ and $\bar{s}$ are the original, fixed valuation functions and signals (determined adversarially) before applying the random ordering. In particular, there exists an agent $a^* \in A$ with the largest value $OPT = \bar{\nu}_{a^*}(\bar{s})$. For convenience, we define the set function

$$ \forall X \subseteq A, \quad f(X) := \bar{\nu}_{a^*}(\bar{s}_X), $$

that is, $f(X)$ denotes the estimated value of $a^*$ 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, \quad \text{best}(S) := \underset{a \in S}{\operatorname{argmax}} \bar{\nu}_a(\bar{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, \quad \mathbb{P}[T = t | A_t] = \frac{\lfloor n/2 \rfloor}{t(t-1)} \quad (7) $$

We write the expected welfare obtained by the algorithm as

$$ \mathbb{E}[ALG] \geq \sum_{t=\lceil n/2 \rceil}^{n} \mathbb{E}[1[T=t] \cdot v_t(s_{[t]})] \quad (\text{equality holds for myopic}) $$

$$ \geq \sum_{t=\lceil n/2 \rceil}^{n} \mathbb{E}[1[T=t] \cdot v_t(s_{[t]}) \cdot 1[a^* \in A_t]] \quad (\text{always smaller}) $$

$$ \geq \sum_{t=\lceil n/2 \rceil}^{n} \mathbb{E}[1[T=t] \cdot f(A_t) \cdot 1[a^* \in A_t]] \quad (\text{by the stopping condition}) $$

$$ = \sum_{t=\lceil n/2 \rceil}^{n} \frac{\lfloor n/2 \rfloor}{t(t-1)} \cdot \mathbb{E}[f(A_t) \cdot 1[a^* \in A_t]] \quad (\text{using Equation (7)}) $$

$$ = \sum_{t=\lceil n/2 \rceil}^{n} \frac{\lfloor n/2 \rfloor}{t(t-1)} \cdot \frac{t}{n} \cdot \mathbb{E}[f(A_t) | a^* \in A_t] \quad (a^* \in A_t \text{ with probability } t/n) $$

Next we define

$$ \forall t \in [n], \quad \alpha_t := \mathbb{E}[f(A_t) | a^* \in A_t]. $$

which gives the inequality

$$ \mathbb{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^*\})$, given a random subset $X \subseteq A \setminus \{a^*\}$ of size $|X| = t - 1$. In particular, using Lemma 5 we have that $\alpha_t \geq \frac{t-1}{n-1} \cdot OPT$. Therefore

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

which concludes the proof. □