# Online Combinatorial Allocation with Interdependent Values

Michal Feldman, Simon Mauras, Divyarthi Mohan, Rebecca Reiffenhäuser

► To cite this version:

Michal Feldman, Simon Mauras, Divyarthi Mohan, Rebecca Reiffenhäuser. Online Combinatorial Allocation with Interdependent Values. EC 2025 - 26th ACM Conference on Economics and Computation, Jul 2025, Stanford, United States. pp.189-205, 10.1145/3736252.3742518 . hal-05225654

HAL Id: hal-05225654

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

Submitted on 27 Aug 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>
# Online Combinatorial Allocation with Interdependent Values

MICHAL FELDMAN, Tel Aviv University, Israel

SIMON MAURAS, INRIA, FairPlay joint team, France

DIVYARTHI MOHAN, Boston University, USA

REBECCA REIFFENHÄUSER, University of Amsterdam, Netherlands

We study online combinatorial allocation problems in the secretary setting, under interdependent values. In the interdependent model, introduced by Milgrom and Weber (1982), each agent possesses a private signal that captures her information about an item for sale, and the value of every agent depends on the signals held by all agents. Mauras, Mohan, and Reiffenhäuser (2024) were the first to study interdependent values in online settings, providing constant-approximation guarantees for secretary settings, where agents arrive online along with their signals and values, and the goal is to select the agent with the highest value.

In this work, we extend this framework to *combinatorial* secretary problems, where agents have interdependent valuations over *bundles* of items, introducing additional challenges due to both combinatorial structure and interdependence. We provide 2e-competitive algorithms for a broad class of valuation functions, including submodular and XOS functions, matching the approximation guarantees in the single-choice secretary setting. Furthermore, our results cover the same range of valuation classes for which constant-factor algorithms exist in classical (non-interdependent) secretary settings, while incurring only an additional factor of 2 due to interdependence. Finally, we extend our study to strategic settings, and provide a 4e-competitive truthful mechanism for online bipartite matching with interdependent valuations, again meeting the frontier of what is known, even without interdependence.

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

**Additional Key Words and Phrases:** Online Algorithms, Combinatorial Auctions, Interdependent Valuations

## ACM Reference Format:

Michal Feldman, Simon Mauras, Divyarthi Mohan, and Rebecca Reiffenhäuser. 2025. Online Combinatorial Allocation with Interdependent Values. In *The 26th ACM Conference on Economics and Computation (EC '25), July 7–10, 2025, Stanford, CA, USA*. ACM, New York, NY, USA, 17 pages. https://doi.org/10.1145/3736252.3742518

## 1 Introduction

The secretary problem lies at the heart of optimal stopping theory, serving as a paradigmatic problem in online algorithms [Dynkin, 1963, Ferguson, 1989, Gardner, 1966]. In this setting, elements arrive sequentially in a random order, with their value revealed upon arrival. Upon observing a value, an online algorithm must make an immediate and irrevocable decision: accept the current value and end the game, or continue to the next element, losing the current one forever. The goal is to compete against the maximum value. This framework captures a wide range of applications, such as hiring, ad auctions, and online resource allocation, where decisions must be made immediately and

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

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

This work is licensed under a Creative Commons Attribution 4.0 International License.

EC '25, July 7–10, 2025, Stanford, CA, USA

© 2025 Copyright held by the owner/author(s).

ACM ISBN 979-8-4007-1943-1/25/07

https://doi.org/10.1145/3736252.3742518
irrevocably. A celebrated result in this area establishes the existence of an *e*-competitive algorithm for this problem, and this is tight [Dynkin, 1963].

While the classic secretary problem is well understood, its basic formulation is too simplistic to capture many real-world complexities. Three major challenges are the following:

(1) **Combinatorial settings:** Many real-life applications involve structured decision-making beyond single-choice problems, requiring solutions for complex allocation problems.

(2) **Interdependent values:** The standard model assumes that arriving values are independent, whereas in many settings, values are correlated across agents.

(3) **Truthful mechanisms:** When dealing with strategic agents, there is a need for mechanisms that incentivize truthful reporting.

To address the first challenge, prior work has generalized the secretary problem to combinatorial assignment settings [Goel and Mehta, 2008, Kesselheim et al., 2013, Kleinberg, 2005, Korula and Pál, 2009]. These models include weighted bipartite matching and combinatorial allocations, where items are offline, and agents arrive online, revealing their combinatorial valuation function upon arrival. A major breakthrough by Kesselheim et al. [2013] established an *e*-competitive online algorithm even for combinatorial allocation problems with XOS valuations (a strict superset of submodular valuations). For the special case of (weighted) bipartite matching, Reiffenhäuser [2019] extended this to a truthful *e*-competitive mechanism, addressing challenges (1) and (3) simultaneously.

The second challenge, that of interdependent values, has only recently been addressed. The interdependent value model was introduced in the seminal work of Milgrom and Weber [1982], where each agent has a private signal about the item, and their valuation depends on the signals of all agents. Interestingly, Mauras et al. [2024] devised a 2e-competitive algorithm for the single-choice secretary problem with interdependent values, proving that interdependence incurs at most a factor 2 loss in the competitive ratio. Furthermore, they established a 4e-competitive truthful mechanism for this setting, addressing challenges (2) and (3) simultaneously.

**Our work: Combining all Three Challenges.** In this work, we provide the first study of the secretary problem that addresses all three challenges simultaneously. We explore combinatorial allocations with interdependent values, both in strategic and non-strategic settings. Notably, even the non-strategic case, that of combinatorial settings with interdependent values, has not been previously studied.

**Our Model.** We consider the problem of allocating a set of *m* items to a set of *n* agents. Every agent has a combinatorial valuation function, specifying her value for any bundle of items. These valuations are *interdependent* in the following sense: alongside her valuation function, each agent also has a *signal*, given by a single nonnegative number, which captures her personal information or belief about the quality of the items. Each agent's valuation function depends, besides the allocated bundle of items, also on the signal profile of all agents.

A valuation function thus assigns a real value to every tuple of a bundle of items and a signal profile. It will be convenient to also think of the valuation function as a set function over items, for a fixed signal profile. Similarly, one can think of the valuation function over signal profiles, for a fixed bundle of items. For valuations over bundles, we consider XOS valuations (a superset of submodular valuations), and unit-demand valuations (inducing a weighted bipartite matching problem). For valuations over signals, we consider XOS over signals and subadditive over signals.

The agents arrive online, in a random order. Upon the arrival of an agent *i*, her signal and valuation function are revealed, and the online algorithm should make an immediate and irrevocable decision about which items (if any) to assign to her. The goal is to be competitive against the maximum social welfare (i.e., the sum of agent values for their bundles), given the entire information.
<figure><img src="image_3.png" /><figcaption>Fig. 1. Our work lies at the intersection of three fundamental lines of work: Online (secretary) algorithms, combinatorial auctions, and interdependent values. Works in red provide truthful mechanisms, while works in blue provide algorithms for non-strategic settings. Mauras et al. [2024] consider both strategic and non-strategic settings.</figcaption></figure>

Our two key questions are the following:

**Question 1:** What is the competitive ratio that can be obtained for combinatorial secretary problems with interdependent valuations?

**Question 2:** What is the competitive ratio that can be achieved by truthful mechanisms for combinatorial secretary problems with interdependent valuations?

## 1.1 Our Results

In this paper, we provide answers to both of our questions above, establishing the first constant-competitive algorithms and truthful mechanisms for combinatorial secretary problems with interdependent values. Our results are summarized in Table 1, where they are compared to previous work. As depicted in Figure 1, this work lies at the intersection of three fundamental lines of work: online (secretary) algorithms, combinatorial auctions, and interdependent values.

<table><caption>Table 1. Competitive ratios of algorithms (non-strategic settings) and truthful mechanisms for combinatorial allocations in the secretary model. Rows represent valuation functions over items, further divided based on valuations over signals.</caption><thead><tr><th>Item Valuations</th><th>Interdependence</th><th>Algorithm</th><th>Truthful Mechanism</th></tr></thead><tbody><tr><td rowspan="3">Single-choice</td><td>None</td><td>e [Dynkin, 1963]</td><td>e [Dynkin, 1963]</td></tr><tr><td>Subadditive</td><td>2e [Mauras et al., 2024]</td><td>4e [Mauras et al., 2024]</td></tr><tr><td>XOS</td><td>4 [Mauras et al., 2024]</td><td>"</td></tr><tr><td rowspan="3">Bipartite matching</td><td>None</td><td>e [Kesselheim et al., 2013]</td><td>e [Reiffenhäuser, 2019]</td></tr><tr><td>Subadditive</td><td>2e (Theorem 1)</td><td>4e (Theorem 4)</td></tr><tr><td>XOS</td><td>4 (Theorem 2)</td><td>"</td></tr><tr><td rowspan="3">XOS</td><td>None</td><td>e [Mauras et al., 2024]</td><td rowspan="3">Unknown</td></tr><tr><td>Subadditive</td><td>2e (Theorem 1)</td></tr><tr><td>XOS</td><td>4 (Theorem 2)</td></tr></tbody></table>

For non-strategic settings we show the following:
**INFORMAL THEOREM 1.** *There exists a 2e-competitive secretary algorithm for combinatorial settings with interdependent valuations that are XOS over items and subadditive over signals.*

*Under the stricter condition of XOS over signals (while remaining XOS over items), we improve this to a 4-competitive algorithm.*

Notably, we don't impose any additional assumptions on valuations to obtain our results. In particular, subadditivity over signals is used even for results in the non-combinatorial (single-choice) secretary setting [Mauras et al., 2024]. Furthermore, XOS (over items) is the most general class of valuations for which there are known constant-competitive algorithms in secretary settings, even without interdependence.

For strategic settings we show the following:

**INFORMAL THEOREM 2.** *There exists a 4e-competitive truthful mechanism for secretary weighted bipartite matching with interdependent valuations that are separable and subadditive over signals.*

Once again, both assumptions (separability and subadditivity over signals) are made even in (offline) truthful mechanisms for matching with interdependent valuations [Eden et al., 2019]; that is, no additional assumptions are imposed to obtain our results for the combined setting.

Moreover, in the classic secretary setting, the current frontier for truthful mechanisms in combinatorial problems is edge-weighted bipartite matching, where an *e*-competitive truthful mechanism is known to exist [Reiffenhäuser, 2019]. Extending this result to broader combinatorial settings remains a challenging open problem, even without interdependence.

Our results show that secretary assignment problems with interdependent values extend to the same level of generality as their traditional, non-interdependent counterparts, with small loss in the competitive ratio. This is again demonstrated nicely in Table 1. In fact, also for other classes of secretary algorithms, there exist such counterparts that accommodate interdependent values, as outlined in Section 3.3.

Furthermore, while the competitive ratios we obtain fall slightly short of those in the non-interdependent setting, they exactly match those established for the single-choice case (with interdependent values) [Mauras et al., 2024]. This mirrors the non-interdependent landscape, where competitive ratios for single-choice settings also carry over to more complex combinatorial settings.

Our work is particularly timely, as central offline results under interdependent values are still emerging [Eden et al., 2019, 2023, 2024, 2022, Lu et al., 2022], and online versions are only beginning to be explored [Mauras et al., 2024]. For the first time, we demonstrate that constant-competitive online algorithms can be designed in the presence of interdependent values, even in complex combinatorial settings with strategic agents.

**A Natural Approach.** Results on secretary algorithms, closely resembling those for the classic secretary problem, all hinge on utilizing independence in the following ways: First, all values (or combinatorial valuations) are assumed to be fixed in advance, meaning they are not random variables (and thus independent). Second, which value/valuation function arrives in each time step is drawn uniformly at random from the set of remaining (fixed) ones. As a result, at any step *t*, the set of arrived values forms a uniformly random subset of size *t*. This randomness enables the algorithm to treat the initial part of the sequence as a *random sample* of the full valuation set, a key property used in existing solutions.

Leveraging this same fact, we observe that one can *separate* the issue of interdependence from the others. In addition, any pair of the three challenges above (secretary model, combinatorial problem, interdependent values) have been addressed together by previous research. One work, most relevant to ours, integrates interdependent values with the secretary problem, but is limited to allocating a single item. A second line of research addresses the combinatorial secretary problem,
but without interdependence. The third approach focuses on designing truthful mechanisms under the secretary model, and is based on analyzing independent probabilities of allocation, and VCG payments, requiring precise knowledge of each item's value — information that is unavailable at the time of allocation.

A natural and intuitive approach is therefore to pursue the following strategy. First, we separate the issue of interdependence by using a sufficiently-sized sample. We then apply techniques from all of the above lines of research to obtain constant-competitive algorithms for a large class of combinatorial secretary problems with interdependent values. This approach, as taken in Section 3.3, loses a factor of 4 compared to secretary algorithms without interdependent values. However, as expected, it is inherently wasteful: Separating value interdependence and the online nature of the problem means also separating the information used to handle each one of them, restricting us to using only part of the instance for each.

**Integrated Algorithms with Improved Competitive Ratio.** Aiming to avoid wasting a large part of the instance's information, we design algorithms that use both the signal and the valuation function of each agent, thus developing techniques that address all challenges in a unified way. Beyond leading to better competitive ratios, this approach also deepens our understanding of the exact restrictions posed by interdependence on the competitive ratio. Moreover, it is technically considerably more challenging than the mere combination of existing techniques.

Introducing value interdependence fundamentally changes the independence properties utilized by classic secretary algorithms. We overcome these challenges by carefully leveraging the aspects of the original independence properties that “survive” the introduction of interdependence, ultimately achieving similarly concise and intuitive proofs for our results. These are fueled, in addition to the above, by the exact choices we make in our algorithms and analysis: while many similar versions of our techniques appear initially promising, they differ in how they handle the fundamental tension between utilizing information and maintaining analyzable (in)dependence properties. Identifying the “right” balance is a key aspect of our contribution.

## 1.2 Related Work

**Online Resource Allocation.** The work most closely related is that of Mauras et al. [2024], who study optimal stopping problems with interdependent values. To the best of our knowledge, other work on online algorithms under the interdependent values model does not yet exist. The secretary problem, in its most fundamental formulation was studied by Dynkin [1963], who provided the optimal stopping result and e-approximation. There is now a long line of work studying a plethora of extensions and generalizations, including e.g. combinatorial allocations [Hoefer and Kodric, 2017, Kesselheim et al., 2013, Reiffenhäuser, 2019], or multi-choice secretary under cardinality or feasibility constraints [Babaioff et al., 2007b,a, Kleinberg, 2005].

Another important paradigm for online resource allocation is the prophet model, where the arrival order is fixed adversarially but the values are drawn independently from known prior distributions. Starting from the seminal works of Krengel and Sucheston [Krengel and Sucheston, 1977, 1978] and Samuel-Cahn [1984], who provided optimal prophet inequalities for the single-choice setting, this model has also been well-studied with extensions to combinatorial settings (e.g. [Dütting et al., 2020, Feldman et al., 2015, Kleinberg and Weinberg, 2012]), variations on arrival order (e.g. [Arsenis et al., 2021, Peng and Tang, 2022, Yan, 2011]) and even exploring the combined power of both models, via the so-called prophet secretary [Esfandiari et al., 2017]. A key assumption in almost all works is that the values are independent.

**Interdependent Values.** The interdependent values model introduced by Milgrom and Weber [1982], building on Wilson [1969], paved the road for a long line of work over the past five decades
to tackle the standard assumption in mechanism design and resource allocation that agents have independent private values. Given strong impossibility results in this model for obtaining optimal welfare truthfully [Ausubel et al., 1999, Che et al., 2015, Dasgupta and Maskin, 2000, Ito and Parkes, 2006, Jehiel and Moldovanu, 2001, Jehiel et al., 2006], recent works in computer science study approximation mechanisms for natural classes of interdependent valuations (e.g., see [Chawla et al., 2014, Chen et al., 2022, Eden et al., 2018, 2019, 2021, 2022, Gkatzelis et al., 2021, Roughgarden and Talgam-Cohen, 2016]). While much of the focus is on single item auctions, Eden et al. [2019] provide the first approximation guarantee for combinatorial auctions for any general monotone valuations (over items). Later works consider other combinatorial settings such as public projects [Cohen et al., 2023], or fair division [Birmpas et al., 2023]. Notably, these works address two of our three challenges, those of (1) combinatorial problems and (2) interdependent values together in an offline setting.

## 2 Model and Preliminaries

We consider a setting with $n$ agents and $m$ heterogeneous items, where agents have interdependent values over bundles of items. Specifically, every agent $i \in [n]$ holds some private $s_i \in \mathbb{R}_{\ge 0}$, capturing her personal information about the items, and a monotone valuation function

$$v_i : 2^{[m]} \times \mathbb{R}_{\ge 0}^n \to \mathbb{R}_{\ge 0},$$

where $v_i(X, s)$ is the value of agent $i$ for a bundle of items $X \subseteq [m]$ under a signal profile $s = (s_1, \dots, s_n)$. We also consider strategic settings, where the agents may misreport their signals. As is standard in the interdependent values model we assume that an agent's signal is private while the valuations function is publicly known (upon the arrival of the agent). For every subset $A \subseteq [n]$ we write $s_A = (1_{1 \in A} \cdot s_1, \dots, 1_{n \in A} \cdot s_n)$, that is, we replace $s_i$ by 0 if $i \notin A$.

It would sometimes be convenient to consider the valuation function as a function over signals, for a fixed bundle, or as a function over bundles, for a fixed signal profile. That is, for any fixed subset of items $X$, $v_i(X, \cdot)$ is a function over signals, and similarly, for any fixed signal profile $s$, $v_i(\cdot, s)$ is a function over bundles.

### 2.1 Complement-Free Valuations over Signals

We first fix a set of items $T \subseteq [m]$ and consider properties of the function $v(s) = v(T, s)$, which maps every signal profile to a value.

**DEFINITION 1 (SUBADDITIVE OVER SIGNALS).** A valuation function $v(\cdot)$ is subadditive over signals, if for any signal profile $s$ and any $X \subseteq [n]$ we have

$$v(s) \le v(s_X) + v(s_{[n] \setminus X}).$$

**DEFINITION 2 (XOS OVER SIGNALS).** A function $v(\cdot)$ is XOS over signals, if for any distribution $\mathcal{A} \in \Delta(2^{[n]})$ over subset of agents, and any signal profile $s$, we have

$$E_{X \sim \mathcal{A}}[v(s_X)] \ge v(s) \cdot \min_{i \in [n]} \mathbb{P}[i \in X].$$

### 2.2 Complement-Free Valuations over Items

We now fix a signal profile $s$ and consider properties of the function $v(X) = v(X, s)$, which maps every bundle of items to a value.

**DEFINITION 3 (UNIT DEMAND).** A valuation function $v(\cdot)$ is unit-demand over items, if there exists a vector of weights $w \in \mathbb{R}_{\ge 0}^m$ such that for any bundle $X$ we have

$$v(X) = \max_{j \in X} w_j.$$
**DEFINITION 4 (XOS).** A valuation function $v(\cdot)$ is XOS over items, if for set $S \subseteq [m]$ and any distribution $\mathcal{B} \in \Delta(2^S)$ over bundles, we have

$$v(\mathcal{B}) := \mathbb{E}_{X \sim \mathcal{B}}[v(X)] \geq v(S) \cdot \min_{j \in S} \mathbb{P}_{X \sim \mathcal{B}}[j \in X].$$

## 2.3 Approximation Ratio

We study online secretary setting, where at each time step $t \in [n]$ agent $i_t$ arrives and we observe their signal $s_{i_t}$. For convenience, we define $A^t := \{i_1, \dots, i_t\}$ the set of agents arrived so far by time step $t$, and we denote $v_i^t(\cdot) := v_i(\cdot, s_{A^t})$ the valuation of agent $i$ using signals that have been observed at time $t$. At the end of step $t$, we irrevocably allocate some bundle $B^t$ to agent $i_t$, which prevents us from computing the optimal allocation.

Given a set of agents $A \subseteq [n]$ and items $J \subseteq [m]$, we denote by $OPT(A, w; J)$ the value of optimal allocation of items in $J$ to agents in $A$, considering the weights $w := \{w_i : 2^J \to \mathbb{R}_{\ge 0}\}_{i \in A}$. For convenience, we also denote $OPT_i(A, w; J)$ and $OPT_{-i}(A, w; J)$ to be respective contribution of agent $i$ and of the others to $OPT(A, w; J)$.

For simplicity of notations, we may write $OPT(A, w)$ or $OPT(A)$, dropping $J$ and (possibly) $w$, for special cases where we consider all items $J = [m]$ and specific weights $w = \{v_i(\cdot, s_A)\}_{i \in A}$ defined by evaluating bundles using valuations and signals from $A$. Finally, we denote $OPT := OPT([n])$ the value of the overall optimal, which we seek to approximate with our online algorithms.

Given an algorithm, we denote ALG the value of its allocation, which is a random variable which depends on the random arrival of agents and the (possible) internal randomness of the algorithm. We say that the algorithm is an $\alpha$-approximation with $\alpha \ge 1$ if $\mathbb{E}[ALG] \ge OPT/\alpha$.

# 3 Secretary Algorithm when Buyers are XOS, and Subadditive over Signals.

In this section we provide a $2e$-approximation for combinatorial allocations in the non-strategic setting, when valuation functions are XOS over items and subadditive over signals.

## 3.1 Algorithm for Subadditive over Signals

Our algorithm is a natural extension of the online algorithm by [Kesselheim et al., 2013] for the classic (non-interdependent) setting, where our decisions at each step are made based on valuations that are only partially informed with the signals so far. This is modeled by setting all yet unknown signals to zero when evaluating the valuation functions of buyers, where subadditivity ensures that a randomly-chosen signal subset will suffice to approximate the real valuations over all, including future, signals. In particular, the algorithm skips/samples the first $n/e$ agents, and for $t > n/e$, on arrival of the $t^{th}$ agent $i_t$ she is allocated a subset of items $B_t$ that are available from those she would receive in an optimal allocation $OPT(A^t)$ for the currently known instance. Recall that $A^t$ is the set of agents arrived so far by time step $t$.

A key insight of the analysis resides in decoupling the randomness that affects the information and the availability of the items. More precisely, to bound the contribution of the $t^{th}$ agent, we draw the random variables in the following order:

(1) We first draw (uniformly at random) the set $A^t \subseteq [n]$ containing the first $t$ agents;

(2) Then, we draw (uniformly at random) the agent $i_t \in A^t$ who arrives last within $A^t$;

(3) Finally, we draw (uniformly at random) the arrival order $\sigma_{t-1}$ of $A^{t-1} = A^t \setminus \{i_t\}$.

**THEOREM 1.** *Algorithm 1 is a $2e$-approximation, in expectation, to the offline optimal allocation with interdependent valuations that are XOS over items and subadditive over signals.*

**PROOF.** Let the $k$ denote the size of the sample set. For each time step $t > k$, we compute the contribution $ALG_t$ of the $t^{th}$ agent to value obtained by algorithm, by carefully decomposing the
ALGORITHM 1: 2e-approximation algorithm for subadditive over signals

Sample the first ⌊n/e⌋ agents. Let $J^{[n/e]+1} = [m]$.

On the arrival of t-th agent $i_t$, for $t > ⌊n/e⌋$:

* Compute an optimal allocation OPT($A^t$) of all items to the agents $A^t := \{i_1, \dots, i_t\}$ who have arrived, w.r.t. the valuation functions $\{v_i^t(\cdot) = v_i(\cdot, \mathbf{s}_{A^t})\}_{i \in A^t}$, denoting $O_i^t$ the bundle received by agent $i \in A^t$.

* From the available items, allocate $B^t = O_i^t \cap J^t$ to agent $i_t$.

* Let $J^{t+1} = J^t \setminus B^t$ denote the remaining items.

randomness of the arrival order as follows:

$$ALG_t = E[v_{i_t}(B^t, \mathbf{s}_{A^t})] = E_{A^t} \left[ E_{i_t \in A^t} \left[ E_{\sigma_{t-1}} \left[ v_{i_t}(B^t, \mathbf{s}_{A^t}) \mid i_t, A^t \right] \mid A^t \right] \right].$$

We first invoke the XOS over items property to bound the expected value of the allocated bundle $B^t$ in terms of the value for the set $O_{i_t}^t$ from the optimal allocation OPT($A^t$) that does not take availability into consideration. First, we condition on $A^t = A \subseteq [n]$ and $i_t = i \in A$, and we denote $O = O_i^t$ to be i's allocation in OPT($A^t$). By Lemma 1, we have that

$$E_{\sigma_{t-1}}[v_i(O \cap J^t, \mathbf{s}_A) | A^{t-1} = A \setminus \{i\}] \ge \frac{k}{t-1} \cdot v_i(O, \mathbf{s}_A).$$

This yields,

$$ALG_t \ge \frac{k}{t-1} \cdot E_{A^t} \left[ E_{i_t \in A^t} \left[ v_{i_t}^t (O_{i_t}^t) \mid A^t \right] \right]. \quad (1)$$

Next we recall that $i_t$ is a uniformly random agent from the set $A^t$. We denote $O_i^*$ the bundle of $i$ in the overall optimal OPT([n]). Then, we lower-bound the optimal value of OPT($A^t$) with the value that agents from $A_t$ receive in the restriction of OPT([n]).

$$\begin{aligned} ALG_t &\ge \frac{k}{t-1} \cdot \frac{1}{t} \cdot E_{A^t} \left[ \sum_{i \in A^t} v_i^t (O_i^t) \right] \\ &\ge \frac{k}{t-1} \cdot \frac{1}{t} \cdot E_{A^t} \left[ \sum_{i \in A^t} v_i^t (O_i^*) \right] \end{aligned} \quad (2)$$

Note that for any agent $i$, the probability of $i \in A^t$ is $t/n$. Moreover, given $i \in A^t$, the rest of the $t-1$ agents are random. Thus we can re-write the above inequality as,

$$ALG_t \ge \frac{k}{t-1} \cdot \frac{1}{t} \cdot \frac{t}{n} \sum_{i=1}^{n} E_{A^t} [v_i^t(O_i^*) | i \in A^t] = \frac{k}{n} \cdot \frac{1}{t-1} \cdot \sum_{i=1}^{n} \alpha_t(i),$$

where for all agents $i$, we define $\alpha_t(i) = E_{A^t}[v_i(O_i^*, \mathbf{s}_{A^t}) | i \in A^t]$, the expected value of $v_i$ for their optimal bundle on the signal $\mathbf{s}_{A \cup \{i\}}$ for a random set $A \subseteq [n] \setminus \{i\}$ of size $t-1$.

We bound the expected value of the algorithm, by summing over the contribution of all time steps $t > k$, as follows

$$E[ALG] = \sum_{t=k+1}^{n} ALG_t \ge \frac{k}{n} \cdot \sum_{i=1}^{n} \sum_{t=k+1}^{n} \frac{1}{t-1} \cdot \alpha_t(i). \quad (3)$$

By subadditivity over signals of the valuation functions, we note that $\alpha_n(i) \le \alpha_t(i) + \alpha_{n-t}(i)$. Moreover, since $v_i$ is monotone (over the signals) we have $\alpha_t(i) \ge \alpha_{t-1}(i)$ for all $t$.

Using similar arguments as [Mauras et al., 2024] we obtain the following claim for any such $\alpha_t$'s. We include a proof in the Appendix for completeness.
CLAIM 1. Given any $\alpha_1 \le \dots \le \alpha_n$ such that $\alpha_n \le \alpha_t + \alpha_{n-t}$ for all $t \in [n]$, we have

$$ \sum_{t=\lfloor n/e \rfloor}^{n} \frac{\alpha_t}{t-1} \ge \frac{\alpha_n}{2} + \alpha_n \cdot \Theta(1/n) $$

With this claim in hand we have, for all agents i,

$$ \sum_{t=\lfloor n/e \rfloor}^{n} \frac{1}{t-1} \cdot \alpha_t(i) \ge \frac{\alpha_n(i)}{2} + \alpha_n(i) \cdot \Theta(1/n) = \left( \frac{1}{2} + \Theta(1/n) \right) OPT_i, $$

where $\alpha_n(n) = v_i(O_i^*, s) = OPT_i$ by definition. By plugging this into Equation (3) for $k = \lfloor n/e \rfloor$ we have,

$$ \begin{aligned} E[ALG] &\ge \frac{|n/e|}{n} \sum_{i=1}^{n} \sum_{t=\lfloor n/e \rfloor}^{n} \frac{1}{t-1} \cdot \alpha_t(i) \\ &\ge \frac{|n/e|}{n} \sum_{i=1}^{n} \left( \frac{1}{2} + \Theta(1/n) \right) OPT_i \\ &\ge \left( \frac{1}{2e} + \Theta(1/n) \right) OPT. \end{aligned} $$

□

LEMMA 1. Let $k$ be the size of the sample set. Fix any subset of agents $A \subseteq [n]$ of size $\ell \ge k$, a bundle of items $B \subseteq [m]$, and an XOS valuation function $\hat{v}: 2^{|m|} \to \mathbb{R}_{\ge 0}$. We condition on $A^\ell = A$, that is $A$ is the set of agents that arrive by time step $\ell$. Let $J^{\ell+1}$ denote the random subset of remaining items after step $\ell$. The expected value of $\hat{v}(B \cap J^{\ell+1})$, over the random arrival order of agents in $S$, is at least $\frac{k}{\ell} \cdot \hat{v}(B)$. That is,

$$ E_{\sigma_{\ell}}[\hat{v}(B \cap J^{\ell+1}) | A^{\ell} = A] \ge \frac{k}{\ell} \cdot \hat{v}(B) $$

PROOF. We will show that for any item $j$ the probability that $j \in J^\ell$ is $\frac{k}{\ell-1}$ for all $\ell \ge k$. This immediately proves the lemma since $\hat{v}$ is an XOS function and by Definition 4 we have $E[\hat{v}(B \cap J^{\ell+1}) | A^\ell = A] \ge \hat{v}(B) \cdot \min_{j \in B} P[j \in B \cap J^{\ell+1} | A^\ell = A] = \hat{v}(B) \cdot \frac{k}{\ell}$. Fix any item $j$. We prove by induction on $\ell \ge k$ that

$$ \forall A \text{ s.t. } |A| = \ell, \quad P_{\sigma_{\ell}}[j \in J^{\ell+1} | A^{\ell} = A] = \frac{k}{\ell}. $$

The base case $\ell = k$ holds trivially as all the items are still available in the sample phase. Consider a subset of agents $A$ of size $\ell$. The probability the item $j$ is still not allocated after time step $\ell$ is

$$ P[j \in J^{\ell+1} | A^{\ell} = A] = P[j \in J^{\ell} \text{ and } j \notin O_{i_{\ell}}^{\ell} | A^{\ell} = A]. $$

Observe that for any available item $j$ to be allocated in step $\ell$, the agent $i^* \in A^\ell$ whose bundle contains $j$ in the allocation $OPT(A^\ell, v^\ell)$ has to be the last amongst $A^\ell$ to arrive (i.e., the $\ell^{th}$). Since the arrival order is random, the probability of $i^*$ arriving last amongst $A^\ell$ (given any $A^\ell$) is exactly $1/\ell$. Thus, we have

$$ P[j \in J^{\ell+1} | A^{\ell} = A] = \sum_{i \in A \setminus \{i^*\}} \frac{1}{\ell} \cdot P[j \in J^{\ell} | A^{\ell-1} = A \setminus \{i\}] $$
By the induction hypothesis it further holds that $\mathbb{P}[j \in J^l | A^{l-1} = A \setminus \{i\}] = k/(l-1)$. This simplifies the above equation to,

$$ \mathbb{P}[j \in J^{l+1} | A^l = A] = \frac{1}{l} \cdot \frac{k}{l-1} \cdot (l-1) = \frac{k}{l} $$

□

## 3.2 Improved Bounds for XOS over Signals

We present a modified online algorithm that obtains a 4-approximation to the offline optimal when the agents have interdependent valuations that are XOS over signals. In particular, we modify the sample phase to $n/2$ agents instead of $n/e$.

**ALGORITHM 2:** 4-approximation algorithm for XOS over signals

Sample the first $\lfloor n/2 \rfloor$ agents. Let $J^{\lfloor n/2 \rfloor+1} = [m]$.

On the arrival of $t^{\text{th}}$ agent $i_t$, for $t > \lfloor n/2 \rfloor$:

* Compute an optimal allocation $\text{OPT}(A^t)$ of all items to the agents $A^t := \{i_1, \dots, i_t\}$ who have arrived, w.r.t. the valuation functions $\{v_i^t(\cdot) = v_i(\cdot, s_{A^t})\}_{i \in A^t}$, denoting $O_i^t$ the bundle received by agent $i \in A^t$.

* From the available items, allocate $B^t = O_{i_t}^t \cap J^t$ to agent $i_t$.

* Let $J^{t+1} = J^t \setminus B^t$ denote the remaining items.

**THEOREM 2.** *Algorithm 2 is an 4-approximation to offline optimal for online combinatorial allocation in expectation when the interdependent valuations are XOS over items and XOS over signals.*

**PROOF.** Observe that the only difference between Algorithm 2 and Algorithm 1 is the sample size. Therefore we can reuse much of the analysis of Algorithm 1. In particular, we note that the proof of Theorem 1 does not use subadditivity over signals until Equation (3). Hence we have,

$$ \mathbb{E}[\text{ALG}] \geq \frac{k}{n} \cdot \sum_{i=1}^{n} \sum_{t=k+1}^{n} \frac{1}{t-1} \cdot \alpha_t(i), \quad (\text{Equation (3)}) $$

where $\alpha_t(i) = \mathbb{E}_{A^t}[v_i(O_i^*, s_{A^t}) | i \in A^t]$.

Next, recall that conditioning on $i \in A^t$, the other $t-1$ agents are a random subset of size $t-1$. Thus, we consider a random set $X$ drawn uniformly from the subsets of size $t$ which include $i$. We use the property that valuation functions are XOS over signals, as defined in Definition 2

$$ \alpha_t(i) = \mathbb{E}_{A^t}[v_i(O_i^*, s_{A^t}) | i \in A^t] = \mathbb{E}_X[v_i(O_i^*, s_X)] \geq \min_{j \in [n]} \mathbb{P}[j \in X] \cdot v_i(O_i^*, s) = \frac{t-1}{n-1} \cdot \text{OPT}_i. $$

Thus by plugging into Equation (3) for $k = \lfloor n/2 \rfloor$ we have,

$$ \mathbb{E}[\text{ALG}] \geq \frac{k}{n} \sum_{i=1}^{n} \sum_{t=k+1}^{n} \frac{1}{t-1} \left( \frac{t-1}{n-1} \text{OPT}_i \right) \geq \frac{k(n-k)}{n(n-1)} \text{OPT} \geq \frac{1}{4} \text{OPT} $$

□

## 3.3 Framework for 4$\alpha$-Competitive Algorithms

We provide a framework to lift up any $\alpha$-competitive algorithm for classic secretary problems (in the absence of interdependence) to an 4$\alpha$-competitive algorithm under interdependent valuations that are subadditive over signals. While this takes a black-box approach to re-purpose existing secretary algorithms in the classic setting, it provides a *worse competitive ratio* when applied directly to our secretary problems with interdependence (4e instead of 2e). The algorithm essentially samples
$n/2$ agents to purely use their signals to estimate “proxy values” for other agents. Then, it runs any classic $\alpha$-approximation algorithm as a blackbox on a modified instance comprising of the remaining $n/2$ agents, using their non-interdependent proxy values.

<caption>**ALGORITHM 3:** 4$\alpha$-approximation for any secretary problem</caption>

(1) **First Sample Phase:**
Skip the first $k_1 = n/2$ agents $\hat{A} = \{i_1, \dots, i_{k_1}\}$.
For all agents $i$, define a proxy valuation function $w_i = v_i(s_{\hat{A}\cup\{i\}})$.

(2) **$\alpha$-approx-Subroutine on Modified Instance:**
As the rest of the $n/2$ agents arrive online, run the $\alpha$-approximation online algorithm for this instance with $n/2$ agents whose values are given by the proxy valuations $\{w_i\}$.

Since the modified instance has no interdependence, we get an $\alpha$-approximation to an optimal solution of the modified instance. By subadditivity over signals, the proxy values provide a good estimate of the true values in expectation. In fact, the expected optimal of the modified instance is a 4-approximation to the true optimal (w.r.t to the true values of all $n$ agents). This implies that the expected value obtained by the algorithm is a 4$\alpha$-approximation to the true optimal.

We note that this framework can be applied for other combinatorial secretary problems, such as multi-choice secretary under downward closed feasibility constraints (cardinality, matroid, knapsack etc.), with competitive algorithms in the classic non-interdependent setting.

We will see an instantiation of this framework formally in the next section, while also tackling the added challenge of strategic agents, to obtain a truthful 4e-approximation.

# 4 Truthful Mechanism for Bipartite Matching

In this section we consider the case where the agents are strategic and may misreport their signals for their own benefit.<fnref n="1" /> We provide a truthful mechanism for online weighted bipartite matching that obtains a 4e-approximation to the offline optimal, when agents have interdependent valuations that are separable and subadditive over signals.

## 4.1 Incentive Compatibility: Preliminaries

A mechanism is a tuple of an allocation rule and a payment rule, where the allocation rule determines the bundle that every agent gets, and the payment rule determines how much they pay. Such a mechanism is said to be *truthful* if it incentivizes agents to report their private valuations truthfully.

For each agent $i$ let $x_i(s)$ denote the (possibly random) subset of items that $i$ receives<fnref n="2" />. Let $p_i(s) \ge 0$ denote the (expected) payment charged (wlog $p_i = 0$ if $x_i = 0$).

**DEFINITION 5 (EPIC).** A deterministic 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

$$v_i(x_i(\mathbf{s}), \mathbf{s}) - p_i(\mathbf{s}) \ge v_i(x_i(\mathbf{s}_{-i}, \mathbf{s}'_i), \mathbf{s}) - p_i(\mathbf{s}_{-i}, \mathbf{s}'_i).$$

We say that a randomized mechanism is EPIC (or *universally truthful*) if it is a distribution over deterministic EPIC mechanisms. We note that this strong notion of incentive compatibility ensures

<footnote n="1">¹We make the standard assumption in the interdependent values model that the valuation function will be publicly known when the agent arrives.</footnote>

<footnote n="2">²We note that this notation implicitly depends on the arrival order given the online nature of the mechanism. Moreover, the allocation/payment of agent $i$ may depend on the randomness of the instance and any potential randomness in the choices of the mechanism so far.</footnote>
that each agent reports her signal truthfully even when she is aware of all information about others and the random choices of the mechanism.

To provide truthful mechanism we make an additional assumption of separability on the valuation functions. This assumption is also present in work studying truthful approximation mechanisms for combinatorial auctions in the offline interdependent values model [Eden et al., 2019].

**Separable valuations.** We say that a valuation function $v_i$ is separable over signals if there exists $f_i : 2^{[m]} \times S_i \to \mathbb{R}_{\ge 0}$ and $g_i : 2^{[m]} \times S_{-i} \to \mathbb{R}_{\ge 0}$ such that

$$v_i(X, s) = f_i(X, s_i) + g_i(X, s_{-i})$$

Although universal truthfulness and separability can be defined for general valuation functions over items, we will assume from this point onward that valuations are unit-demand (the optimal allocation will be a bipartite matching). This assumption is necessary, as no online truthful mechanisms are known to exist beyond bipartite matching even without interdependence.

## 4.2 Truthful Mechanism

Our mechanism combines the random sampling generalized VCG mechanism of Eden et al. [2019] for offline combinatorial interdependent auctions and the truthful mechanism of Reiffenhäuser [2019] for online bipartite matching (without interdependence). In particular, we sample the first $n/2$ agents to define proxy valuations $w_i$, which only depend on $i$'s own signal and the signals of these $n/2$ sample agents. By subadditivity over signals the proxy valuations are a good estimate of the real valuations using all signals (including those arriving in the future). We now consider a modified instance of the problem with only the rest of the $n/2$ agents and their proxy valuations. Observe that the modified instance has no interdependence, so we can run the truthful e-approximation mechanism of [Reiffenhäuser, 2019]. We then prove that the expected optimal of the modified instance is a 1/4 approximation to true optimal. Combining these yields a 4e-approximation.

We start by restating the result of [Reiffenhäuser, 2019] in Theorem 3 along with a description of the corresponding allocation algorithm, which we will be using as a sub-routine.

**THEOREM 3 ([REIFFENHÄUSER, 2019]).** For any instance of classic (non-interdependent) weighted bipartite matching in the secretary setting, Rei19-Allocation-Subroutine is an e-competitive algorithm.

**Rei19-allocation-subroutine [Reiffenhäuser, 2019]:** Given $n$ agents arriving online with valuations $\{w_i\}_{i=1}^n$.

Sample $k = \lfloor n/e \rfloor$ agents. Let $J^{k+1} = [m]$.

For $t > k$, on the arrival of the $t^{th}$ agent $i_t$ with valuation function $w_{it}$:

* Compute an optimal allocation $OPT(A^t, w; J^t)$ of the available items $J^t$ to the agents in $A^t$ w.r.t. the valuation functions $w = \{w_i\}_{i \in A^t}$.

* Allocate $B^t = \{j_t\}$ to $i_t$ if they receive $j^t$ in $OPT(A^t, w; J^t)$, and $B^t = \emptyset$ otherwise.

* Let $J^{t+1} = J^t \setminus B^t$

The following is a useful lemma from [Eden et al., 2019] that bounds the expected value of the modified instance on a random subset of agents. We include a proof in the Appendix for completeness.

**LEMMA 2 ([EDEN ET AL., 2019]).** Given a combinatorial allocation problem with $n$ agents who have interdependent valuations $v_i$ that are subadditive-over signals. For a uniformly random subset $\hat{A} \subseteq [n]$ of size $n/2$ we have,

$$E_{\hat{A}}[OPT([n] \setminus \hat{A}, w, [m])] \geq \frac{1}{4} \cdot OPT,$$
where OPT([n] \ A, w, [m]) is the optimal welfare from allocating to only agents in [n] \ A w.r.t to proxy valuation functions wᵢ(X, sᵢ) = vᵢ(X, ŝA).

**ALGORITHM 4:** Truthful 4e-approximation for weighted bipartite matching

(1) **First Sample Phase:**

Skip the first $k_1 = \lfloor n/2 \rfloor$ agents $\hat{A} = \{i_1, \dots, i_{k_1}\}$.

For all agents i, define a proxy valuation function $w_i(\cdot) := v_i(\cdot, s_{\hat{A} \cup \{i\}})$

(2) **Rei19-Allocation-Subroutine [Reiffenhäuser, 2019] on Modified Instance:**

Sample the next $k_2 = \lfloor n/2e \rfloor$ agents. Let $J^{k_1+k_2+1} = [m]$.

For $t > k_1 + k_2$, on the arrival of the $t^{th}$ agents $i_t$:

* Elicit signal $s_{i_t}$ and use it to compute the proxy valuation function $w_{i_t}$ of agent $i_t$.

* Compute an optimal allocation OPT($\hat{A}^t$, w; J^t) of the available items J^t to the agents in $\hat{A}^t := \{i_{k_1+1}, \dots, i_t\}$, w.r.t to the proxy valuation functions w = {$w_i$}$_{i \in \hat{A}^t}$.

* Allocate $B^t = \{j_t\}$ to $i_t$ if they receive $j^t$ in OPT($A^t$, w; J^t), and $B^t = \emptyset$ otherwise.

* Let $J^{t+1} = J^t \setminus B^t$

(3) **Payment Rule:**

At the end, for all $t > k_1 + k_2$, charge $i_t$ price

$$p_t(s) = \mathrm{OPT}(\hat{A}^{t-1}, w; J^t) - \mathrm{OPT}_{-i_t}(\hat{A}^t, w; J^t) + g_{i_t}(B^t, s_{[n]-(i_t-1)} - g_{i_t}(B^t, s_{\hat{A}}).$$

We now show that Algorithm 4 is a truthful mechanism.

**LEMMA 3.** *Algorithm 4 is a universally truthful mechanism.*

**PROOF.** Fix any arrival order, for simplicity we rename agents so that agent i is the $i^{th}$ agent to arrive. Note that all sample agents, i.e, $\hat{A} = [k_1]$ and $\hat{A}^{k_1+k_2} = \{k_1+1, \dots, k_1+k_2\}$ do not receive any allocation and are charged no payments. More precisely, they have no incentive to misreport as their utility will be 0 regardless.

Fix any $i > k_1 + k_2$ with true signal $s_i$, given that all $[n] \setminus i$ agents report $s_{-i}$ truthfully we show that it is utility maximizing for i to report $s_i$ truthfully. For reported signal $s'_i$, denote $w'_i(\cdot) = v_i(\cdot, s_{\hat{A}^i, s'_i})$ the corresponding proxy valuation function, and $w_{-i} = \{w_t\}_{t \in \hat{A}^{i-1}}$ the proxy valuation of agents strictly before i (not part of $\hat{A}$), which does not depend on agent i.

We compute $B^i(s'_i)$ the bundle received by i in allocation OPT($\hat{A}^i$, $w_{-i}$, $w'_i; J^i$). Using the separability of the valuation function, the price paid by agent i is then

$$ \begin{aligned} p_i(\mathbf{s}_{-i}, s'_i) &= \mathrm{OPT}(\hat{A}^{i-1}, \mathbf{w}_{-i}; J^i) - \mathrm{OPT}_{-i}(\hat{A}^i, \mathbf{w}_{-i}, w'_i; J^i) \\ &\quad + g_i(B^i(s'_i), \mathbf{s}_{[n]-(i-1)}) - g_i(B^i(s'_i), \mathbf{s}_{\hat{A}^i}) \\ &\quad + f_i(B^i(s'_i), s_i) - f_i(B^i(s'_i), s_i) \\ &= \mathrm{OPT}(\hat{A}^{i-1}, \mathbf{w}_{-i}; J^i) - \mathrm{OPT}_{-i}(\hat{A}^i, \mathbf{w}_{-i}, w'_i; J^i) \\ &\quad + v_i(B^i(s'_i), \mathbf{s}) - v_i(B^i(s'_i), \mathbf{s}_{\hat{A}^i \cup \{i\}}) \end{aligned} $$

With this we are ready to compute i's utility $u_i(s; s'_i)$ for true signals s and signal $s'_i$

$$ \begin{aligned} u_i(s; s'_i) &= v_i(B^i(s'_i), s) - p_i(\mathbf{s}_{-i}, s'_i) \\ &= v_i(B^i(s'_i), \mathbf{s}_{\hat{A}^i \cup \{i\}}) + \underbrace{\mathrm{OPT}_{-i}(\hat{A}^i, \mathbf{w}_{-i}, w'_i; J^i)}_{\text{Proxy welfare of step } i \text{ for } s'_i} - \underbrace{\mathrm{OPT}(\hat{A}^{i-1}, \mathbf{w}_{-i}; J^i)}_{\text{Does not depend on } i} \end{aligned} $$

where the first set of terms denotes the proxy welfare obtained by $\hat{A}^i$ (on true signals) for the allocation OPT($\hat{A}^i$, $w_{-i}$, $w'_i; J^i$). By the definition, this will be at most the proxy welfare for the allocation computed using i's true signal,

$$v_i(B^i(s'_i), \mathbf{s}_{\hat{A}^i \cup \{i\}}) + \mathrm{OPT}_{-i}(\hat{A}^i, \mathbf{w}_{-i}, w'_i; J^i) \le \mathrm{OPT}(\hat{A}^i, \mathbf{w}; J^i).$$
Hence we have,

$$u_i(s; s'_i) \leq \mathrm{OPT}(\hat{\mathrm{A}}, \mathrm{w}_{-i}, w'_i; J^i) - \mathrm{OPT}(\hat{\mathrm{A}}^{i-1}, \mathrm{w}_{-i}; J^i)$$

Observe that the right hand side is precisely $i$'s utility $u_i(s; s_i)$ for reporting the true signal $s_i$. Thus proving that the mechanism is truthful. □

We are now ready to prove the main result of this section, namely that Algorithm 4 is a 4e-approximation to the optimal bipartite matching.

**THEOREM 4.** *Algorithm 4 is a truthful mechanism that obtains a 4e-approximation to the optimal offline welfare for online bipartite matching with interdependent valuations that are separable and subadditive over signals.*

**PROOF.** By Lemma 3 we have that our mechanism is truthful for any realization of arrival order. We now show that the expected value of the algorithm is a 4e-approximation.

Fix any sample $\hat{\mathrm{A}}$ of the first $\lfloor n/2 \rfloor$ agents. Conditioned on $\hat{\mathrm{A}}$, we consider the modified instance on $[n] \setminus \hat{\mathrm{A}}$ with valuation functions $w_i$ as defined in Algorithm 4. We note that this modified instance does not have any interdependence; in particular, the $\lfloor n/2 \rfloor$ agents in $[n] \setminus \hat{\mathrm{A}}$ arrive in uniform random order and each agent $i$ arrives with a valuation function $w_i$ that only depends on agent $i$'s signal $s_i$ (along with the signals of the sample $\hat{\mathrm{A}}$ which are not part of the modified instance). This allows us to run the Rei19-Allocation-Subroutine [Reiffenhäuser, 2019] for online bipartite matching in the classic secretary setting (without interdependence). By Theorem 3 this provides an e-approximation to the optimal offline allocation—restricted to the modified instance, which implies

$$\mathrm{E}\left[\sum_{i \in [n] \setminus \hat{\mathrm{A}}} w_i(B(i)) \mid \hat{\mathrm{A}}\right] \geq \frac{1}{e} \cdot \mathrm{OPT}([n] \setminus \hat{\mathrm{A}}, \mathbf{w}, [m]) \quad (4)$$

By subadditivity over the signals, the expected value of $\mathrm{OPT}([n] \setminus \hat{\mathrm{A}}, \mathbf{w}, [m])$ over the randomness of $\hat{\mathrm{A}}$ is at least $\mathrm{OPT}/4$, following the result of [Eden et al., 2019]. We cast this in Lemma 2 and include a proof in the Appendix for completeness.

Putting these together we get the required bound as follows

$$\begin{align*}
\mathrm{E}[\mathrm{ALG}] &= \mathrm{E}\left[\sum_{i=1}^{n} v_i(B(i), \mathbf{s})\right] &\geq \mathrm{E}_{\hat{\mathrm{A}}}\left[\mathrm{E}\left[\sum_{i=1}^{n} w_i(B(i)) \mid \hat{\mathrm{A}}\right]\right] &\quad (\text{By monotonicity}) \\
&\geq \mathrm{E}_{\hat{\mathrm{A}}}\left[\frac{1}{e} \cdot \mathrm{OPT}([n] \setminus \hat{\mathrm{A}}, \mathbf{w}, [m])\right] &\quad (\text{By Equation (4)}) \\
&\geq \frac{1}{4e} \cdot \mathrm{OPT} &\quad (\text{By Lemma 2})
\end{align*}$$

## Acknowledgments

This work was supported in part 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 Israel Science Foundation Breakthrough Program (grant No. 2600/24), by a grant from the TAU Center for AI and Data Science (TAD), and by the National Science Foundation (NSF) CAREER Award (CCF-2441071). Simon Mauras benefited from the support of the FMJH Program PGMO (P-2024-0034).
References

Makis Arsenis, Odysseas Drosis, and Robert Kleinberg. 2021. Constrained-Order Prophet Inequalities. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). 2034–2046. https://doi.org/10.1137/1.9781611976465.121

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

Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. 2007b. A knapsack secretary problem with applications. In International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer, 16–28.

Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. 2007a. 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

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

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

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 EC. ACM, 19–20.

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

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

Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. 2017. Prophet Secretary. SIAM Journal on Discrete Mathematics 31, 3 (2017), 1685–1701. https://doi.org/10.1137/15M1029394

Michal Feldman, Nick Gravin, and Brendan Lucier. 2015. Combinatorial Auctions via Posted Prices. In Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 123–135. https://doi.org/10.1137/1.9781611973730.10

Thomas S. Ferguson. 1989. Who Solved the Secretary Problem? Statist. Sci. 4, 3 (08 1989), 282–289.

Martin Gardner. 1966. New Mathematical Diversions from Scientific American. Simon and Schuster, Chapter 3, problem 3. Reprint of the original column published in February 1960 with additional comments.

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

Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to Adwords (SODA '08). Society for Industrial and Applied Mathematics, USA, 982–991.

Martin Hoefer and Bojana Kodric. 2017. Combinatorial Secretary Problems with Ordinal Information. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland (LIPICS, Vol. 80), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 133:1–133:14. https://doi.org/10.4230/LIPICS.ICALP.2017.133

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 Tönnis, and Berthold Vöcking. 2013. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. In *ESA (Lecture Notes in Computer Science, Vol. 8125)*. Springer, 589–600.

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

Robert D. Kleinberg. 2005. A multiple-choice secretary algorithm with applications to online auctions. In *SODA. SIAM*, 630–631.

Nitish Korula and Martin Pál. 2009. Algorithms for secretary problems on graphs and hypergraphs. In *International Colloquium on Automata, Languages, and Programming*. Springer, 508–520.

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.

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.

Simon Mauras, Divyarthi Mohan, and Rebecca Reiffenhäuser. 2024. Optimal Stopping with Interdependent Values. In *Proceedings of the 25th ACM Conference on Economics and Computation (EC '24)*. ACM, 246–265.

Paul R Milgrom and Robert J Weber. 1982. A theory of auctions and competitive bidding. *Econometrica* (1982).

Bo Peng and Zhihao Gavin Tang. 2022. Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design. In *2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)*. IEEE Computer Society, Los Alamitos, CA, USA, 171–178. https://doi.org/10.1109/FOCS54457.2022.00023

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

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

Qiqi Yan. 2011. Mechanism Design via Correlation Gap. In *Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*. 710–719. https://doi.org/10.1137/1.9781611973082.56

## A Missing Proofs

PROOF OF CLAIM 1. We consider three different parts of the sum, (i) from $t_0 = \lceil n/e \rceil$ to $t_1 = \lceil n/(e-1) \rceil$, (ii) from $t_1$ to $t_2 = n - \lceil n/e \rceil + 1$, and (iii) from $t_2$ to $n$. Since $\alpha_t \ge \alpha_{t-1}$ for all $t$, we have

$$ \sum_{t=\lceil n/e \rceil} \frac{\alpha_t}{t-1} \ge \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}. $$

We now simplify the sum of $1/(t-1)$ and replace $t_0, t_1, t_2$ with their respective values,

$$ \begin{aligned} \sum_{t=\lceil n/e \rceil} \frac{\alpha_t}{t-1} &\ge \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) \\ &\ge \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) \\ &\ge (\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). \end{aligned} $$
Finally, observe that $t_2 \ge n - t_0$ and $t_1 \ge n - t_1$. Since $\alpha_n \le \alpha_t + \alpha_{n-t}$ for all $t$ and $\alpha_t \ge \alpha_{t'}$ for $t \ge t'$, we bound $\alpha_{t_0} + \alpha_{t_2}$ and $2\alpha_{t_1}$ by $\alpha_n$ to get

$$ \sum_{t=[n/e]} \frac{\alpha_t}{t-1} \ge \alpha_n \ln\left(\frac{e}{e-1}\right) + \alpha_n \ln\left(\frac{e-1}{\sqrt{e}}\right) + \alpha_n \Theta(1/n) \\ = \frac{\alpha_n}{2} + \alpha_n \Theta(1/n) $$

□

PROOF OF LEMMA 2. For any realization of $\hat{A}$, we define $\hat{O}_i$ to be $i$'s bundle in the allocation $OPT([n] \setminus \hat{A}, \mathbf{w}, [m])$ if $i \in [n] \setminus A$ and $\emptyset$ otherwise.

$$ \begin{aligned} \mathbb{E}_{\hat{A}}[OPT([n] \setminus \hat{A}, \mathbf{w}, [m])] &= \sum_{i=1}^{n} \mathbb{E}_{\hat{A}}[v_i(\hat{O}_i, \mathbf{s}_{\hat{A}\cup\{i\}}) \cdot \mathbb{1}\{i \notin \hat{A}\}] \\ &\ge \sum_{i=1}^{n} \mathbb{E}_{\hat{A}}[v_i(O_i^*, \mathbf{s}_{\hat{A}\cup\{i\}}) \cdot \mathbb{1}\{i \notin \hat{A}\}] \\ &= \sum_{i=1}^{n} \mathbb{P}[i \in \hat{A}] \cdot \mathbb{E}_{\hat{A}}[v_i(O_i^*, \mathbf{s}_{\hat{A}\cup\{i\}}) \mid i \notin \hat{A}] \\ &\ge \frac{1}{2} \sum_{i=1}^{n} \frac{1}{2} \cdot v_i(O_i^*, \mathbf{s}), \end{aligned} $$

where the last inequality follows because $i$ has 1/2 probability of being chosen in $\hat{A}$, and by subadditivity over signals we have

$$ v_i(O_i^*, \mathbf{s}) \le v_i(O_i^*, \mathbf{s}_{\hat{A}}) + v_i(O_i^*, \mathbf{s}_{[n]\setminus\hat{A}}), $$

with probability of $\hat{A} = A$ and probability of $\hat{A} = [n] \setminus (A \cup \{i\})$ are equal for any $A \subseteq [n] \setminus \{i\}$ of size $\lfloor n/2 \rfloor$.<fnref n="3" /> □

<footnote n="3">³We assume wlog that $n$ is odd by adding a dummy agent with value zero.</footnote>