1 Introduction↩︎

We consider the problem of budget-feasible procurement auctions, introduced by [1], where a set \(N\) of agents offer their services to an employer. Each agent \(a\) has a private cost \(c(a)\) for offering their service. The employer has a publicly known valuation function \(v:2^N\to \mathbb{R}_{\ge 0}\) and a hard budget \(B\), and aims to procure a subset of agents so as to maximize \(v(S)\) subject to total payments not exceeding \(B\).

In this work we study online budget-feasible procurement in the random-order (secretary) model. The instance (costs and valuation) is fixed adversarially, and agents arrive sequentially in a uniformly random permutation. Upon each arrival, the mechanism must make irrevocable decisions without knowledge of future agents.

At its core, the underlying algorithmic problem is an online maximization problem under knapsack (budget) constraints. Given agents’ costs \(c(a)\) for each \(a\in N\), the employer aims to maximize \(v(T)\) subject to \(\sum_{a\in T} c(a)\le B\). This is a classical NP-hard optimization problem, and both its offline and online variants have been extensively studied for many different classes of valuation functions.

In procurement auctions, however, agents may misreport their private costs in an attempt to extract higher payments from the employer. Consequently, we seek to design mechanisms that are individually rational and truthful. Individual rationality requires that any agent \(a\) selected by the mechanism receives a payment \(p_a\) that covers their cost, i.e., \(p_a \ge c(a)\). Truthfulness requires that reporting the true cost is a dominant strategy for each agent, regardless of the reports of others.

A natural and widely adopted approach in practice is to interact with agents through sequential posted prices. Upon an agent’s arrival, a posted-price mechanism offers a payment \(p_a\) that may depend only on the history observed so far. The agent accepts the offer if and only if it exceeds their private cost, revealing minimal information about their valuation. Posted-price mechanisms are simple to understand and implement, universally truthful by construction and preserve agent privacy making them particularly attractive in applications such as crowdsourcing and online labor markets.

Since their introduction, procurement auctions have attracted substantial attention from the computer science and operations research communities due to both their practical relevance and theoretical richness. This interest has led to the study of numerous variants of the problem, distinguished by whether decisions are made offline or online, by the class of valuation functions considered, and by the interaction protocol between the employer and the agents. Below, we highlight the lines of work most closely related to our results; a broader discussion of additional variants and related progress is deferred to Section 1.2.

Perhaps the closest line of work to ours is the study of posted-price procurement auctions with monotone submodular valuations, initiated by [2]. They introduced the online version of the problem under secretary arrivals and presented a constant-competitive mechanism in the direct-revelation model, along with an \(O(\log n)\)-competitive posted-price mechanism for monotone submodular valuations. More recently, [3] obtained the first constant-competitive posted-price mechanism for this setting – albeit with a very large constant – thereby demonstrating that posted-price mechanisms can match direct-revelation mechanisms in terms of asymptotic performance. Our results for monotone submodular valuations significantly strengthen this line of work by improving the competitive ratio by a factor of \(200\).

Another closely related line of research concerns online procurement auctions with non-monotone submodular valuations. [4] established constant-competitive guarantees in the online setting under the direct-revelation protocol. In contrast, our work shows that comparable guarantees can be achieved even under the more restrictive posted-price model, thereby extending the scope of constant-competitive online procurement mechanisms beyond monotone objectives. Our results provide a definitive positive answer to the motivating question of [2] about the relative power of posted-price mechanisms for online budget feasible auctions compared against their direct revelation counterparts.

Finally, we complement our positive results with a logarithmic lower bound for XOS valuations, which applies to any online budget-feasible mechanism and constitutes, to the best of our understanding, the first impossibility result of this kind for online procurement auctions. Interestingly, these lower bounds establish a gap between online and offline budget-feasible procurement auctions: for XOS valuations, constant-factor approximation mechanisms are known offline, whereas our results show that such guarantees are impossible online.

1.1 Technical Overview and Contribution↩︎

In this work, we introduce Repeated Descent (ReD), a deterministic routine tailored to the large-market regime of online procurement auctions with secretary arrival order. We use ReD as a core building block to obtain improved guarantees for posted-price online procurement auctions with monotone submodular valuations, and to design the first constant-competitive posted-price mechanism for online procurement with non-monotone submodular valuations. Finally, we establish a logarithmic lower bound for XOS valuations that applies to any online budget-feasible mechanism.

Before describing our mechanism, we briefly recall a central primitive from the literature on budget-feasible procurement: linear pricing. Given a target value \(\hat{t}\), referred to throughout as a threshold and intended to approximate the offline optimum \(\mathrm{\small Opt}\), the mechanism offers an arriving agent \(a\) a payment proportional to its marginal contribution, \(p_a \;=\; \frac{B}{\hat{t}}\cdot v(a\mid T),\) where \(T\) denotes the set of previously accepted agents and \(v(a\mid T):=v(T\cup\{a\})-v(T)\) is the marginal value of \(a\) with respect to \(T\). A well-established principle in budget-feasible procurement is that linear pricing is effective whenever it operates at the correct scale. In particular, if the mechanism spends a constant fraction of the budget while posting prices computed using thresholds that are within a constant factor of \(\mathrm{\small Opt}\), then it necessarily recovers a constant fraction of the optimal value. On the other hand, if the threshold is significantly lower (higher) than \(\mathrm{\small Opt}\), then the posted prices are too generous (too stingy), and the mechanism cannot achieve high value.

Building on this principle, prior approaches have focused on identifying an appropriate pricing scale, either by explicitly guessing a threshold [2] or by setting up a convoluted, multi-stage search to find a good threshold with positive probability [3]. Our approach departs from this paradigm.

ReD induces dynamics that steer the mechanism toward an appropriate threshold without ever estimating it explicitly. It begins at the maximum feasible threshold and repeatedly halves it (i.e., repeatedly descends over candidate thresholds) until a prescribed value cutoff is met; once sufficient value has been accumulated, it resets the threshold to its maximum level to prevent prolonged overspending. A key structural feature of ReD is that it enforces budget feasibility deterministically: by design, the routine expends agents faster than it expends budget, so the supply of agents is exhausted before the budget can be.

These dynamics yield a win–win structure. Either the cutoff is reached frequently, in which case each success certifies that the mechanism has made steady progress by accumulating a fixed amount of value. Or successes are infrequent, in which case the threshold can only drift downward and therefore remains low for long stretches of the execution.

In the latter regime, ReD makes many offers using thresholds below the desired scale, namely below a constant-factor approximation of \(\mathrm{\small Opt}\), while still never risking budget exhaustion. During these stretches, the prices posted by ReD dominate the linear prices corresponding to any threshold within a constant factor of \(\mathrm{\small Opt}\) (with respect to the same set of previously accepted agents). As a consequence, every agent who would accept such a linear-price offer is also accepted by ReD.

Therefore, in this regime it suffices to show that applying linear pricing at a threshold that is a constant-factor approximation of \(\mathrm{\small Opt}\) extracts a constant fraction of the optimal value from the agents encountered during these rounds. Informally, it is standard in the budget-feasible procurement literature that linear pricing at an appropriate scale can extract a constant fraction of the value present among the agents to which it is applied, provided the mechanism remains budget-feasible. Thus, after establishing that ReD spends a substantial portion of the execution posting prices that dominate those corresponding to thresholds near the desired scale, the main remaining challenge is to certify that these time periods indeed contain substantial value.

We address this using the random-order arrival model together with the large-market assumption and a deterministic (permutation independent) partitioning of the input. Intuitively, large markets preclude instances in which \(\mathrm{\small Opt}\) is concentrated in a few exceptional agents, and random-order arrivals prevent the adversary from systematically placing all high-value agents outside the portions of the sequence where ReD posts low thresholds. To quantify the value in these portions, we partition the second phase into fixed-size rounds matched to the threshold scale and use concentration of measure to show that many rounds are dense, i.e., they contain significant value at the scale of \(v_{\max}\). Separately, a deterministic counting argument lower bounds the number of rounds on which ReD posts low thresholds whenever successful descents are infrequent. Putting everything together implies that ReD operates at low thresholds on many dense rounds, and the standard linear-pricing guarantee then yields constant-factor value recovery.

We first instantiate the above framework for monotone submodular valuation functions. Our main result for this setting is the following, which improves on the best known posted-price competitive ratio of [3] by a factor of at least \(200\).

We next extend the framework to non-monotone submodular valuations. The high-level structure of the analysis remains the same, but one key implication used in the monotone case no longer holds. Even in the monotone case, early acceptances can reduce the marginal contributions of later agents, so that even agents that would accept prices at the desired threshold may reject due to diminished marginals. However, using monotonicity, we bound this loss by charging it to the value already collected by the mechanism.

This charging argument fails in the non-monotone case. To address this difficulty, we leverage a powerful lemma due to [5], which shows that for any submodular valuation, constructing a random subset of a given set by independently including each element with probability \(1/2\) yields an expected value of at least one quarter of the optimal value attainable on that set. Since the optimal value over a set is monotone with respect to inclusion, this result allows us to recover value guarantees even when the mechanism accepts a superset of agents. By combining this randomized subsampling step with the structural guarantees provided by ReD, we are able to extend the previous logic to the non-monotone setting.

Our main result is the first competitive posted-price mechanism for non-monotone submodular valuations.

Finally, we complement our positive results with a logarithmic lower bound for online procurement under XOS valuations. Our construction is inspired by the framework of [6]. We partition the agents into \(L\) disjoint groups, each of size \(\ell\), and define an XOS valuation as the maximum of \(L\) additive clauses, one per group. Each agent contributes only to the clause of its own group. We set the cost of every agent to \(c(a)=B/\ell\), so any budget-feasible mechanism can hire at most \(\ell\) agents in total.

The only remaining randomness lies in the additive coefficients. Independently for each agent, we set its coefficient to \(1\) with probability \(1/\ell\) and to \(0\) otherwise. Equivalently, the valuation is drawn at random from a family of XOS instances with sparse additive clauses. In this distribution, the offline optimum corresponds to selecting the best group, i.e., the group containing the largest number of \(1\)-coefficients. When \(L\) is sufficiently large, standard extreme-value bounds imply that the best group contains \(\Theta(\ell)\) active agents in expectation, and hence \(\mathbb{E}_{\!}\left[\mathrm{\small Opt}\right]=\Theta(\ell)\).

In contrast, an online mechanism does not know future coefficients. Once it hires an agent from a group, the additional value it can hope to obtain from the remaining agents of that group is governed by a binomial random variable with expectation \(<1\). Moreover, since the mechanism can hire at most \(\ell\) agents overall, it can interact meaningfully with at most \(\ell\) groups. As a result, the value of any online budget-feasible mechanism is upper bounded by the maximum of \(\ell\) such binomial random variables, which is only \(O(\log\ell)\) in expectation. Setting \(\ell=\frac{\log n}{\log\log n}\) yields the following theorem.

1.2 Further Related Work↩︎

Ignoring strategic considerations, maximizing a monotone submodular function subject to a knapsack constraint is a classical NP-hard optimization problem. The greedy algorithm of [7] achieves an approximation ratio of \(e/(e-1)\), which is optimal under standard complexity assumptions [8]. This guarantee extends to the knapsack-constrained setting [9]. More recently, [10] presented a \((9/8+\varepsilon)\)-approximation using polynomially many demand queries.

1.2.0.1 Offline budget-feasible procurement.

[1], [11] initiated the study of budget-feasible procurement auctions from a mechanism design perspective and gave the first constant-factor approximation for monotone submodular valuations using truthful mechanisms. [12] substantially improved these guarantees, achieving approximation ratios of \(7.91\) (randomized) and \(8.34\) (deterministic) for monotone submodular valuations, and \(3\) (randomized) and \(2+\sqrt{2}\) (deterministic) for additive valuations. They also established unconditional lower bounds of \(1+\sqrt{2}\) (deterministic) and \(2\) (randomized universally truthful) for additive valuations. For additive valuations, [13] matched the optimal randomized approximation ratio of \(2\) and gave a deterministic \(3\)-approximation. [14] obtained optimal \(e/(e-1)\)-approximation mechanisms for additive valuations and improved ratios for monotone submodular valuations in large markets. For monotone submodular valuations, [15] gave a randomized \(5\)-approximation mechanism and improved bounds assuming access to exact value maximization. Subsequent work refined these guarantees further: [16] introduced polynomial-time clock auctions with a \(4.75\)-approximation, and [17] achieved the currently best known ratios of \(4.45\) (deterministic) and \(4.3\) (randomized).

Polynomial-time constant-factor approximations are also known for non-monotone submodular valuations. [4] and [18] obtained constant-competitive mechanisms, with the best known guarantees being \(64\) for deterministic and \(12\) for randomized mechanisms, both achieved via clock auctions [16], [17]. For XOS valuations, constant-factor approximation mechanisms are known in the offline setting, albeit with non-polynomial running time [19], [20]. For subadditive valuations, [16] gave an \(O(\log n/\log\log n)\)-approximation via clock auctions, matching earlier randomized guarantees [19] and improving on the \(O(\log^3 n)\) deterministic bound of [21]. Recently, [22] improved upon this providing an \(O(\log\log n)\) approximate mechanism. We refer the reader to the survey of [23] for a comprehensive overview.

1.2.0.2 Online budget-feasible procurement.

The online version of budget-feasible procurement auctions, where agents arrive sequentially in random order and decisions are irrevocable, was introduced by [24] and [2]. In the bidding model, [4] obtained constant-competitive randomized universally truthful mechanisms for both monotone and non-monotone submodular valuations. Online budget-feasible procurement is closely related to the submodular knapsack secretary problem [25], [26], where costs are revealed upon arrival. [27] presented a randomized \(20e\)-approximation for this problem.

1.2.0.3 Beyond bidding.

Posted-price mechanisms are particularly appealing due to their simplicity and obvious truthfulness, but they are significantly more restrictive than bidding-based protocols. Clock auctions [16], [17] avoid explicit bidding but are not online, as decisions regarding agents’ acceptance in the solution are revocable. In the online setting with irrevocable decisions upon arrival, the only known posted-price mechanisms for monotone submodular valuations prior to our work are the \(O(\log n)\)-competitive mechanism of  [2] and the constant competitive mechanism of [3] discussed before.

2 Preliminaries↩︎

We study posted-price online procurement auctions under a hard budget constraint. There is a set \(N=\{1,\dots,n\}\) of agents. Each agent \(a\in N\) has a privately known cost \(c(a)\in\mathbb{R}_{\ge 0}\), representing the minimum payment at which they are willing to provide their service. The employer has budget \(B\in\mathbb{R}_{\ge 0}\) and preferences given by a valuation \(v:2^N\to\mathbb{R}_{\ge 0}\). The goal is to select a subset \(T\subseteq N\) so as to maximize \(v(T)\) subject to the budget constraint on total payments.

We work in the random-order (secretary) model: an adversary fixes the instance (the costs and the valuation), and then agents arrive in a uniformly random permutation. We assume that the mechanism has access to function \(v\) in the form of unlimited value queries on the set of revealed agents. Upon each arrival, the mechanism must make irrevocable decisions. We assume \(n\) is known in advance. For any \(A\subseteq N\), we write \(c(A):=\sum_{a\in A}c(a)\).

2.0.0.1 Mechanisms and desiderata.

An (offline) direct-revelation mechanism is specified by an allocation rule \(A:\mathbb{R}_{\ge 0}^n\to 2^N\) and a payment rule \(p:\mathbb{R}_{\ge 0}^n\to\mathbb{R}_{\ge 0}^n\). Given reported costs \(\mathbf{b}=(b_1,\dots,b_n)\), the mechanism selects \(A(\mathbf{b})\subseteq N\) and assigns payments \(p(\mathbf{b})=(p_1(\mathbf{b}),\dots,p_n(\mathbf{b}))\). Agents have quasi-linear utilities: agent \(a\)’s utility is \[u_a(\mathbf{b}) := \begin{cases} p_a(\mathbf{b})-c(a) & \text{if } a\in A(\mathbf{b}),\\ 0 & \text{otherwise,} \end{cases}\] and we adopt the convention that \(p_a(\mathbf{b})=0\) whenever \(a\notin A(\mathbf{b})\). A mechanism is budget-feasible if \(\sum_{a\in N}p_a(\mathbf{b})\le B\) for all \(\mathbf{b}\), and individually rational if \(u_a(\mathbf{b})\ge 0\) for all agents \(a\) and all \(\mathbf{b}\). It is truthful if reporting the true cost is a dominant strategy: for every agent \(a\), every report \(b\ge 0\), and every \(\mathbf{b}_{-a}\), \(u_a((c(a),\mathbf{b}_{-a}))\ge u_a((b,\mathbf{b}_{-a}))\). A randomized mechanism is a distribution over deterministic mechanisms; we require budget-feasibility and individual rationality with certainty and universal truthfulness.

2.0.0.2 Posted-price mechanisms.

We restrict attention to posted-price mechanisms. When an agent \(a\) arrives, the mechanism posts a single take-it-or-leave-it offer \(p_a\), which may depend on the history but not on future arrivals. Agent \(a\) accepts iff \(p_a\ge c(a)\); if they accept, their services are available to the employer and they are paid \(p_a\), otherwise they leave irrevocably. Posted-price mechanisms are truthful and individually rational by construction, and they are budget-feasible provided each posted price does not exceed the remaining budget.

2.0.0.3 Valuation classes and oracle access.

We assume \(v\) is normalized, i.e., \(v(\emptyset)=0\). For convenience, we write \(v(a)\) for \(v(\{a\})\) and define the marginal value \(v(a\mid S):=v(S\cup\{a\})-v(S)\). The valuation \(v\) is monotone if \(v(S)\le v(T)\) for all \(S\subseteq T\), and submodular if it has diminishing returns, i.e., \(v(a\mid T)\le v(a\mid S)\) for all \(S\subseteq T\) and \(a\notin T\). A valuation is XOS (fractionally subadditive) if there exists a collection of additive functions \(\{\mu_k\}_k\) such that for every \(S\subseteq N\), \(v(S)=\max_k \sum_{a\in S}\mu_k(a)\). We access \(v\) via value queries, which return \(v(S)\) for any \(S\subseteq N\). Let \(v_{\max}:=\max_{a\in N} v(a)\) denote the maximum singleton value.

2.0.0.4 Linear prices.

A standard reference point in budget-feasible procurement is linear pricing, which posts prices proportional to marginal contributions. Given a target value \(\hat{t}\) intended to approximate the offline optimum, one offers an arriving agent \(a\) the price \(p_a=(B / \hat{t})\cdot v(a\mid T),\) where \(T\) is the set of already accepted agents.

2.0.0.5 Competitive ratio.

Let \(\mathrm{\small Opt}\) denote the value of the optimal offline solution that observes all agents and their costs in advance and selects a set \(C^*\subseteq N\) with \(c(C^*)\le B\). Let \(\mathrm{\small Alg}\) denote the (random) value achieved by an online mechanism; expectations are over the random arrival order and any internal randomness. A mechanism is \(\alpha\)-competitive if \(\mathbb{E}[\mathrm{\small Alg}]\ge \mathrm{\small Opt}/\alpha\) for all instances.

3 Monotone Submodular Valuations↩︎

This section introduces and analyzes ReD, the routine at the core of both our monotone and non-monotone large-market mechanisms. Given a budget \(B\), a set \(N_{\text{rem}}\) of remaining agents, and a scale parameter \(v_{\max}\) (an estimate of the maximum singleton value), ReD computes an adaptive sequence of thresholds. The mechanism uses these thresholds to post linear prices to agents. We then restrict attention to monotone submodular valuations and show that ReD achieves a constant competitive ratio on large-market instances \((\mathrm{\small Opt}\geq 8000\cdot v_{\max})\). Finally, we randomize between ReD and two posted-price mechanisms tailored to small and medium markets, obtaining PostedPrice with the following guarantee.

3.1 Repeated Descent (ReD)↩︎

ReD merely loops: it starts a descent whenever enough agents remain to do so. The descent subroutine is described below.

3.1.0.1 The descent subroutine.

A descent maintains a threshold \(t\) and a running total \(V\) of value collected during the current descent. It initializes \(t \gets n\cdot v_{\max}\) and \(V \gets 0\), and proceeds in stages indexed by the current threshold \(t\). At threshold \(t\), the mechanism processes a block of \(\tau(t) := 50\cdot \frac{v_{\max}}{t}\cdot n\) consecutive arriving agents. For each such agent \(a\), it posts the linear price \(p(a) = \frac{B}{t}\cdot v(a\mid T),\) where \(T\) denotes the current solution set at that time. If \(a\) accepts, then \(a\) is added to \(T\) and \(V\) increases by \(v(a\mid T)\). If at any point \(V \ge 49\cdot v_{\max}\), the descent terminates successfully. If the block ends without reaching this target, the threshold is halved (\(t \gets t/2\)), the block length is updated to \(\tau(t)\), and the descent continues with the next agents. A descent ends either upon success or when fewer than \(\tau(t)\) agents remain to execute the next block. The term “descent” reflects that the subroutine searches downward over thresholds, starting from \(n\cdot v_{\max}\) and decreasing \(t\) geometrically from block to block.

3.2 Budget Feasibility↩︎

A crucial property of ReD is that it never exhausts its budget.

3.3 Analysis Outline↩︎

Our goal is to recover a constant fraction of the offline optimum \(\mathrm{\small Opt}\). Each successful descent certifies progress: it terminates only after ReDhas accumulated \(\Theta(v_{\max})\) marginal value during that descent. Hence, if ReDcompletes \(\Theta(\mathrm{\small Opt}/v_{\max})\) successful descents, then it already obtains \(\Omega(\mathrm{\small Opt})\) value.

On the other hand, if the number of successful descents is smaller, we argue that ReDmust have made offers to a large number of agents using thresholds below \(t'\), where \(t'=\Theta(\mathrm{\small Opt})\). To translate this argument into value gathered by ReD, we proceed as follows:

1. We partition the input sequence into fixed-size contiguous blocks, called rounds.

2. We define a set \(C^*\) of agents with a high value-to-cost ratio and argue that, under the large-market and secretary-order assumptions, many rounds are dense, i.e., they contain sufficient value contributed by the high-return agents in \(C^*\).

3. Finally, we prove that if a threshold lower than \(t'\) is used in many dense rounds, then ReDmust obtain \(\Theta(\mathrm{\small Opt})\) value overall.

3.4 Rounds, Benchmark Set and Density↩︎

We have already seen that ReD processes the stream in consecutive blocks. In this subsection, we show that once a block is large enough (on the order of \(\frac{v_{\max}}{\mathrm{\small Opt}}\,n\) arrivals) it contains a nontrivial amount of value, namely \(\Theta(v_{\max})\), with constant probability under random-order arrivals. This is the main structural input for the analysis; in later subsections, we show how to extract a constant fraction of the value present in such blocks.

Fix a threshold of interest \(t'\), for monotone submodular valuations \(t'\) is the unique threshold of the form \(n\cdot v_{\max}/ 2^r\), \(r \in \mathbb{N}\) such that \(\mathrm{\small Opt}/16 \leq t' < \mathrm{\small Opt}/8\). We partition the arrival sequence as follows:

• The first \(n/2\) agents belong to the sampling phase and are ignored in the remainder of the analysis.

• The remaining \(n/2\) agents are divided into rounds. A round consists of \(\ell=50\cdot \frac{v_{\max}}{t'}\cdot n\) consecutive agents. Any leftover agents that do not complete a full round are disregarded.

For each round index \(j\), let \(A_j\subseteq N\) denote the (random) set of agents that belong in round \(j\).

To quantify the amount of value present in each round, we introduce a benchmark set \(C^*\). We remark that the set \(C^*\) is used solely for analysis and does not depend on the execution of ReD.

Let \((a_1,a_2,\dots,a_\nu)\) be the agents in \(C^*\), ordered by their appearance in \(\pi_0\). For each \(a_i\in C^*\), define its marginal contribution \[w(a_i) := v(\{a_1,\dots,a_i\}) - v(\{a_1,\dots,a_{i-1}\}).\] By definition, \(\sum_{a\in C^*} w(a) = v(C^*)\).

Informally, we lower bound the value present in a round by the marginal values of the \(C^*\)-agents that appear in that round. Since \(C^*\) captures a constant fraction of \(\mathrm{\small Opt}\), random-order arrivals and the large-market assumption imply that, for each fixed round of size \(\ell\), this benchmark contribution is \(\Theta(v_{\max})\) with constant probability.

Fix a round \(j\). For each position \(i\in[\ell]\) within round \(j\), define the random variable \[\label{eq:Xij} X_i^j \;=\; \begin{cases} w(a) & \text{if the agent occupying position \(i\) of round \(j\) is some } a\in C^*\setminus\{a_{\max}\}\text{\footnotemark},\\ 0 & \text{otherwise.} \end{cases}\tag{1}\] Below we prove that \(X^j := \sum_{i=1}^{\ell} X_i^j\) provides a lower bound for the value that high-return agents of \(C^*\) contribute in each round.

3.4.0.1 Concentration.

We proceed to define high-value rounds, called "dense" and argue that a constant fraction of the rounds defined are dense with probability at least a half.

The variables \(\{X_i^j\}\) are not independent but are negatively associated, as they arise from sampling without replacement (a permutation distribution). By [28] and [29], Bernstein’s inequality applies under negative association.

Applying Bernstein’s inequality yields the following bound; the calculation is deferred to Appendix 7.

We analyze the performance of ReD in instances where there are \(D \ge 0.8\,R\) rounds. We denote this event by \(\mathcal{F}\) and will condition on it from here on out.

3.5 Counting Lemma↩︎

Throughout this subsection, we assume that ReD uses the correct scale \(v_{\max}\) (event \(\mathcal{E})\). Fix a threshold cut \(t'\) and recall that \(\ell := 50\cdot \frac{v_{\max}}{t'}\cdot n\). We begin with a fundamental statement about ReD’s threshold usage.

The next lemma turns this per-step monotonicity into a round-counting statement.

3.6 Combining Counting and Density↩︎

We now combine the deterministic counting guarantee (Lemma 6) with the event \(\mathcal{F}\) established in Section 3.4, which asserts that many rounds are dense. This yields a dichotomy: either many descents succeed, or ReD operates at thresholds \(\leq t'\) on many dense rounds.

3.7 Value Recovery↩︎

We conclude by analyzing the two cases in Lemma 7 and lower bounding the value obtained by ReD in each case. Let \(A\) denote the event that ReD makes offers using thresholds \(\leq t'\) on at least \(0.1R\) dense rounds. We consider two cases:

Case 1: event A. Let \(Q\) be the set of agents in dense rounds where ReD makes offers using \(t \leq t'\) and let \(Q' = Q \cap C^*\). Recall that \(\ell = 50 \; \frac{v_{\max}}{t'} \; n\) and \(\mathrm{\small Opt}/16 \leq t' < \mathrm{\small Opt}/8\). Finally, let \(T\) be the solution at the end of the run. By the definition of density and submodularity, it holds \[v(Q') \geq 0.1R \cdot 160 v_{\max}\geq 0.1 (\frac{5}{6} \frac{n}{2 \ell}) \cdot 160 v_{\max}\geq \mathrm{\small Opt}/120\] where the second inequality uses \(R \geq \frac{5}{6}\frac{n}{2\ell}\) that holds by the large market assumption. Using submodularity and monotonicity we get: \[v(Q') - v(T) \leq v(Q' \cup T) - v(T) \leq \sum_{a \in Q' \setminus T} v(a \mid T)\] We know that all these agents rejected offers with threshold at most \(\mathrm{\small Opt}/8\) thus: \[\sum_{a \in Q' \setminus T} v(a \mid T) \leq \frac{\mathrm{\small Opt}}{8B} \sum_{a \in Q' \setminus T} c(a)\]

Now recall that due to the definition of \(C^*\) there exists an ordering \(\pi_0\) with which the agents in \(Q'\) are purchasable with threshold \(\mathrm{\small Opt}/2\). Therefore, if we assume that indices in \(Q'\setminus T = \{a_1, \ldots, a_k\}\) are ordered with respect to \(\pi_0\) it holds \[c(a_i) \leq \frac{2B}{\mathrm{\small Opt}} v(a_i \mid \{a_1, \ldots, a_{i-1}\})\]

Summing over all agents in \(Q' \setminus T\): \[\sum_{i = 1}^k c(a_i) \leq \frac{2B}{\mathrm{\small Opt}} \sum_{i = 1}^k v(a_i \mid \{a_1, \ldots, a_{i-1}\}) \leq \frac{2B}{\mathrm{\small Opt}} v(Q' \setminus T) \leq \frac{2B}{\mathrm{\small Opt}} v(Q')\]

Substituting back to the initial equation we get: \[v(Q') - v(T) \leq \frac{v(Q')}{4} \Rightarrow v(T) \geq \frac{3}{4} v(Q') \geq \frac{1}{160} \mathrm{\small Opt}.\]

Case 2: negation of A. Conditioning on \(\mathcal{E}\) and \(\mathcal{F}\), Lemma 7 implies that ReD completes at least R/4 successful descents. Since ReD completed \(R/4\) descents, by the definition of completed descents it accumulated \(\frac{R}{4} 49 v_{\max}\) value. Therefore: \[\mathbb{E}_{\!}\left[\mathrm{\small Alg}\mid \mathcal{E}, \mathcal{F}, \neg A\right] \geq \frac{R}{4} 49 v_{\max}\geq \frac{1}{4} \left(\frac{5}{6} \frac{n}{2\ell}\right) \cdot 49v_{\max}\geq \frac{\mathrm{\small Opt}}{160}\]

Putting everything together \[\begin{align} \mathbb{E}_{\!}\left[\mathrm{\small Alg}\right] & \geq \mathbb{E}_{\!}\left[\mathrm{\small Alg}\mid \mathcal{E}, \mathcal{F}\right] \mathbb{P}\!\left[\mathcal{F} \mid \mathcal{E}\right] \mathbb{P}\!\left[\mathcal{E}\right]\\ & \geq \frac{1}{4} \min \big\{\mathbb{E}_{\!}\left[\mathrm{\small Alg}\mid \mathcal{E}, \mathcal{F}, A\right], \mathbb{E}_{\!}\left[\mathrm{\small Alg}\mid \mathcal{E}, \mathcal{F}, \neg A\right]\big\} \geq \frac{\mathrm{\small Opt}}{640}. \end{align}\]

3.8 Small and Medium Markets↩︎

In the previous subsections, we analyzed the performance of our large-market mechanism under the assumption that \(\mathrm{\small Opt}\ge 8000 \cdot v_{\max}\). We now remove this assumption and present a complete mechanism that achieves a constant competitive ratio for all instances.

Our approach is to randomize over three truthful mechanisms, each tailored to a different market regime. The resulting mechanism remains universally truthful and budget-feasible.

When the instance is dominated by a single high-value agent, we rely on Dynkin’s classical secretary algorithm.

For intermediate regimes, we use a carefully tuned variant of the mechanism of [2], called MediumMarket (formally presented in Section 8 of the Appendix), which is optimized for the range \(29\,v_{\max}\le \mathrm{\small Opt}\le 8000\,v_{\max}\). The analysis of this mechanism follows standard arguments and is deferred to the Appendix 8.

3.8.0.1 Putting everything together.

We are ready to prove Theorem 4.

4 Extension to non-Monotone Submodular Valuations↩︎

In this section, we give the first constant-competitive posted-price mechanism for online procurement auctions with non-monotone submodular valuations. Since non-monotonicity raises a modeling choice that is irrelevant in the monotone case, we begin by specifying the commitment model we study.

A posted-price mechanism always pays an agent who accepts its offer, but in the non-monotone setting the employer may not want to actually use every purchased service. We therefore allow the mechanism to discard hired agents (i.e. to pay them if they accept but to select not to use their services). To preserve the online nature of the problem, we require that this keep/discard decision is made irrevocably at the time of acceptance (i.e., immediately after the agent accepts the offer) without knowledge of future arrivals. This commitment model differs fundamentally from clock auctions (see  [17]), even when restricted to a single query per agent. Our guarantees obviously extend to the weaker model in which the employer may postpone all discarding decisions until the end of the sequence.

4.1 Non-Monotone Repeated Descent (NM-ReD)↩︎

We present NM-ReD, a non-monotone analogue of ReD for large-market instances. At its core NM-ReD embeds the GenSm-Online mechanism of [4] into our Repeated Descent framework. Specifically, it maintains two candidate solution tracks \(S_1,S_2\). Each accepted agent is assigned to the track on which it has larger marginal value (at the time of arrival), and the mechanism uses the same linear price rule as in ReD with respect to that track. To handle non-monotonicity, NM-ReD additionally forms random subsamples \(T_1\subseteq S_1\) and \(T_2\subseteq S_2\) by independently retaining each accepted agent with probability \(1/2\), and returns one of \(S_1,S_2,T_1,T_2\) at the end according to a fixed distribution.

As in the monotone case, our large-market mechanism, called NM-LargeMarket, uses the first half of the arrival sequence to estimate \(v_{\max}\), and then runs the non-monotone variant of ReD on the remaining agents. In this subsection, we prove the following theorem.

We begin by observing that budget feasibility carries over from Lemma 1. Although the mechanism now maintains two parallel solution tracks, the budget analysis follows the same high-level structure as in the monotone case.

Another structural observation is that the number of successful descents is bounded by the total value accumulated across the two tracks. By construction, each successful descent terminates after at least \(49v_{\max}\) marginal value is added to \(v(S_1) + v(S_2)\). Therefore, if \(d\) is the number of successful descents, we have \(v(S_1) + v(S_2) \geq 49v_{\max}\cdot d\).

As in the monotone case, we partition the second half of the input sequence into rounds of length \(\ell := 50 \cdot \frac{v_{\max}}{t'} \cdot n,\) where \(t'\) is the unique threshold of the form \(n\cdot v_{\max}/ 2^r\), \(r \in \mathbb{N}\) that satisfies \(\mathrm{\small Opt}/200 \le t' < \mathrm{\small Opt}/100\).

To apply concentration, we compare against a fixed benchmark set. Let \(C^*=\{c_1,\dots,c_k\}\) be an inclusion-wise minimal optimal solution, and fix an arbitrary ordering \(\pi_0\) of its elements. For each \(i\in[k]\), define the marginal contribution \[w(c_i)\;:=\; v(\{c_1,\dots,c_i\})-v(\{c_1,\dots,c_{i-1}\}).\] Then \(\sum_{i=1}^k w(c_i)=v(C^*)=\mathrm{\small Opt}\). Moreover, by minimality we have \(v(c_i\mid C^*\setminus\{c_i\})\ge 0\), and by submodularity \(\{c_1,\dots,c_{i-1}\}\subseteq C^*\setminus\{c_i\}\) implies \(w(c_i)\ge 0\). Hence, for all \(i\in[k]\), \[0 \;\le\; w(c_i) \;\le\; v_{\max}.\]

We define \(X^j\) exactly as in the monotone case, and update the density threshold to match the scale induced by \(t'\).

Applying Bernstein’s inequality (using negative association under random-order arrivals) yields the following bound.

We next establish the analogue of Lemma 7. Its proof is identical since it is purely structural and does not rely on monotonicity, however we select a different combination of constants to better fit our proof.

We proceed to prove Theorem 7.

4.2 Small Market↩︎

It remains to handle the case of small markets, i.e., instances in which \(\mathrm{\small Opt}\;\le\; 50000\,v_{\max}.\) We use the classical Dynkin secretary algorithm on the entire sequence. Since valuations are submodular, this guarantees that the value obtained is at least the value of the selected agent. Dynkin’s algorithm selects the maximum singleton value with probability at least \(1/e\), and hence achieves expected value at least \(v_{\max}/e\).

In the small-market regime, \(v_{\max}\geq \frac{\mathrm{\small Opt}}{50000}\). Therefore, Dynkin’s algorithm is \(136000\)-competitive, and is truthful and budget feasible by construction.

Randomizing over Dynkin’s algorithm and NM-ReD yields a \(181000\)-competitive posted-price mechanism for non-monotone submodular valuations in all regimes.

5 Lower Bound for XOS Valuations↩︎

In this section we present a logarithmic lower bound for online procurement auctions with XOS valuation functions. This construction is inspired by the lower bound framework of [6]. As defined in Section 2, the adversary selects the cost of each agent and the valuation function. Then the agents arrive in a uniformly random order. The mechanism has query access to the set of revealed agents. Our main result is the following.

5.0.0.1 Lower Bound Instance.

We first describe a distribution over valuation functions; the actual valuation is drawn from this distribution. Fix a partition of the agent set \(N\) into \(k\) disjoint groups \(S_1,\dots,S_k\), each of size \(m:=\tfrac{\log n}{\log\log n}\), where \(k:=\lfloor n/m\rfloor\). For each agent \(a\in N\), sample an independent Bernoulli random variable \(\text{active}(a)\in\{0,1\}\) with \(\mathbb{P}\!\left[\text{active}(a)=1\right]=p:=\tfrac{\log\log n}{\log n}\). Let \(\mathcal{D}\) denote the resulting product distribution, and let \(I\) be a realization.

For any set \(T\subseteq N\) and realization \(I\), define the valuation \[v_I(T)=\max_{i\in[k]} \mu_i(T), \qquad \mu_i(T):=\sum_{a\in S_i\cap T}\text{active}(a,I).\] Each clause \(\mu_i\) is additive and supported on a single group; hence \(v_I\) is XOS.

Finally, we set the cost for all agents \(a \in N\) to be \(c(a)=pB\). Thus, the budget allows the purchase of at most \(1/p=m\) agents.

5.0.0.2 Lower Bound Analysis.

For each group \(i\in[k]\), let \(X_i:=\sum_{a\in S_i}\text{active}(a,I)\) denote the number of active agents in group \(i\). Then \(X_i\sim\mathrm{Bin}(m,p)\), the variables \((X_i)_{i\in[k]}\) are independent, and \(\mathbb{E}[X_i]=mp=1\). Intuitively, each group contains only a constant number of active agents in expectation, but since there are many groups, the group with the most active agents is significantly larger. We continue by formalizing and proving the latter statement in the following lemma.

We now proceed to upper bound the expected performance of any online mechanism on this instance.

Combining Lemma 11 together with Lemma 12 completes the proof of Theorem 9.

6 Conclusion↩︎

We studied online budget-feasible procurement auctions under random-order arrivals, focusing on the power of sequential posted-price mechanisms. Our main technical contribution is the Repeated Descent (ReD) subroutine, a deterministic pricing primitive that enforces budget feasibility while dynamically steering the mechanism toward regimes where linear pricing is effective, without ever estimating the optimal pricing scale.

Using ReD, we significantly improve the state of the art for posted-price mechanisms with monotone submodular valuations, reducing the competitive ratio by several orders of magnitude compared to previous work. We further show that constant-competitive guarantees extend beyond monotone objectives: by combining ReD with random subsampling techniques, we obtain the first constant-competitive posted-price mechanism for online procurement with non-monotone submodular valuations. Our positive results are complemented by a logarithmic lower bound for XOS valuations, which applies to all online budget-feasible mechanisms. This impossibility result delineates a sharp boundary between valuation classes that admit constant-competitive online mechanisms and those for which such guarantees are unattainable, even under random-order arrivals.

Finally, an interesting question raised by our work concerns the gap between submodular and XOS valuations in the online setting. While our lower bound rules out constant-competitive guarantees for XOS valuations, it remains open whether one can design an online mechanism with a polylogarithmic competitive ratio, even in the more powerful direct-revelation model.

7 Application of Bernstein’s inequality: Proof of Lemma 4↩︎

Fix a round \(j\) and recall the random variables \((X_i^j)_{i\in[\ell]}\) defined in 3.4: for each position \(i\) of round \(j\), \[X_i^j = \begin{cases} w(a) & \text{if agent } a \in C^*\setminus\{a_{\max}\} \text{ occupies position } i,\\ 0 & \text{otherwise}. \end{cases}\] Let \(X^j := \sum_{i=1}^{\ell} X_i^j\) and define \(g(C^*) := \sum_{a\in C^*\setminus\{a_{\max}\}} w(a).\)
Conditioned on event \(\mathcal{E}\) (that \(a_{\max}\) lies in the first half), the second half of the sequence is a uniformly random permutation of a uniformly random subset of size \(n/2\) out of the \(n-1\) agents in \(N\setminus\{a_{\max}\}\). Hence, for every position \(i\) in the second half, \[\mu_i := \mathbb{E}[X_i^j \mid \mathcal{E}] = \frac{g(C^*)}{n-1}.\] Moreover, since \(0\le X_i^j \le v_{\max}\), we have \[X_i^j - \mu_i \le v_{\max} - \mu_i \quad\Rightarrow\quad b := v_{\max}-\frac{g(C^*)}{n-1}.\] The expectation of \(X^j\) is \[\mu := \mathbb{E}[X^j \mid \mathcal{E}] = \sum_{i=1}^{\ell} \mu_i = \frac{\ell}{n-1}\,g(C^*).\] Using \(0\le X_i^j \le v_{\max}\), we have \((X_i^j)^2 \le v_{\max}X_i^j\), and thus \[\mathbb{E}[(X_i^j)^2 \mid \mathcal{E}] \le v_{\max} \cdot \mu_i.\] Therefore, \[\mathrm{Var}(X_i^j \mid \mathcal{E}) = \mathbb{E}[(X_i^j-\mu_i)^2\mid \mathcal{E}] \le v_{\max}\mu_i - \mu_i^2 = \frac{g(C^*)}{n-1}\left(v_{\max}-\frac{g(C^*)}{n-1}\right).\] Summing over \(i\in[\ell]\) yields \[V := \sum_{i=1}^{\ell} \mathrm{Var}(X_i^j \mid \mathcal{E}) \le \frac{\ell}{n-1} g(C^*)\left(v_{\max}-\frac{g(C^*)}{n-1}\right).\]

8 Proof of Theorem 10↩︎

MediumMarket uses an initial part of the input sequence to obtain a rough estimate of \(\mathrm{\small Opt}\) (it satisfies \(v_{\max}\leq \mathrm{\small Opt}\leq n\cdot v_{\max}\)). Then, it randomly selects a multiplier from a carefully chosen set of multipliers and uses it to post linear prices.

The proof follows the framework of  [2], adapted to our randomized-threshold implementation and constant-size multiplier net. We include it for completeness.

Let \(S^*=\{a_1,a_2,\ldots,a_k\}\) be an optimal solution, ordered so that agents appear in non-increasing order of marginal contribution. Define \[w(a_i) := v(\{a_1,\ldots,a_i\}) - v(\{a_1,\ldots,a_{i-1}\}),\] so that \(\sum_{i=1}^k w(a_i)=\mathrm{\small Opt}\) and \(0\le w(a_i)\le v_{\max}\) for all \(i\).
The mechanism splits the agents into an exploration phase and an exploitation phase, with each agent independently assigned to each phase with probability \(1/2\).

Let \(\mathcal{E}_{\max}\) be the event that at least one agent attaining value \(v_{\max}\) appears in the exploration phase. Since the split is uniform, \(\mathbb{P}\!\left[\mathcal{E}_{\max}\right]=1/2\), and on this event the mechanism learns the correct scale \(v_{\max}\).

For each \(a_i\in S^*\) define the random variable \[X_i := \begin{cases} w(a_i) & \text{if } a_i \text{ belongs to the exploitation phase},\\ 0 & \text{otherwise}. \end{cases}\] The variables \((X_i)_i\) are independent. By submodularity, the value of the set of agents that belong in the optimal solution and appear in the exploitation phase, denoted \(S_2^*\), satisfies \[v(S_2^*) \;\ge\; \sum_{i=1}^k X_i.\]

By symmetry, the same bound holds for the exploration phase. Let \(\mathcal{E}_{\text{split}}\) denote the event that both phases contain optimal value at least \(\mathrm{\small Opt}/4\). By a union bound, \[\mathbb{P}\!\left[\mathcal{E}_{\text{split}}\right] \ge 1-2\cdot 0.07 = 0.86.\] Combining with \(\mathcal{E}_{\max}\) and union bounding bad events gives \[\mathbb{P}\!\left[\mathcal{E}_{\max}\cap \mathcal{E}_{\text{split}}\right] \ge 1-0.5-0.14 = 0.36.\]

Condition on \(\mathcal{E}_{\max}\cap \mathcal{E}_{\text{split}}\). Then \(v(S_2^*) \ge \mathrm{\small Opt}/4\) and the mechanism uses the correct scale \(v_{\max}\). Suppose \[v(S_2^*) \in [\ell\,v_{\max},\,u\,v_{\max})\] for some \(\ell,u>0\), and the mechanism posts linear prices with threshold \(t = m\cdot v_{\max}\).

8.0.0.1 Multiplier net for the range \([29/4,\,8000]\).

Let \(\ell_1=29/4\) and let \(r := \left(\frac{8000}{\ell_1}\right)^{1/6}.\) Define intervals \[[\ell_i,u_i) \quad\text{with}\quad \ell_i=\ell_1 r^{i-1},\; u_i=r\ell_i, \qquad i=1,\dots,6.\] These intervals cover the range \(v(S_2^*)/v_{\max} \in [29/4,\,8000]\).

For each interval define \[m_i := \frac{\ell_i(u_i+1)}{\ell_i+u_i},\] which equalizes the two terms in Lemma 15. Let \(\mathcal{T}=\{m_1,\dots,m_6\}\); numerically, \[\mathcal{T}=\{5.89,\,18.76,\,59.00,\,184.85,\,578.62,\,1809.01\}.\]

Fix any interval \([\ell_i,u_i)\). Plugging \(m=m_i\) into Lemma 15 gives \[\min\!\left\{\frac{\ell_i-m_i}{\ell_i},\;\frac{m_i-1}{u_i}\right\} = \frac{\ell_i-1}{\ell_i+u_i} = \frac{1-\frac{1}{\ell_i}}{1+r} \;\ge\; \frac{1-\frac{1}{\ell_1}}{1+r}.\] Thus, conditioned on selecting the correct multiplier, the mechanism recovers at least \[\gamma \cdot v(S_2^*) \quad\text{where}\quad \gamma := \frac{1-\frac{1}{\ell_1}}{1+r}.\]

8.0.0.2 Putting the pieces together.

On the event \(\mathcal{E}_{\max}\cap\mathcal{E}_{\text{split}}\) (probability at least \(0.36\)), we have \(v(S_2^*)\ge \mathrm{\small Opt}/4\). Moreover, the correct multiplier is chosen with probability \(1/6\). Therefore, \[\mathbb{E}_{\!}\left[\mathrm{\small Alg}\right] \;\ge\; 0.36 \cdot \frac{1}{6} \cdot \gamma \cdot \frac{\mathrm{\small Opt}}{4}.\] With the above choice of \(r\), the resulting constant satisfies \[0.36\cdot \frac{1}{6}\cdot \gamma \cdot \frac{1}{4} \;\ge\; \frac{1}{326},\] and hence \(\mathbb{E}_{\!}\left[\mathrm{\small Alg}\right] \ge \mathrm{\small Opt}/326\), proving that MediumMarket is \(326\)-competitive for \(29\,v_{\max}\le \mathrm{\small Opt}\le 8000\,v_{\max}\).

9 Proof of Lemma 10↩︎

Recall that NM-ReD is always budget feasible by design, therefore every agent \(a \notin (S_1 \cup S_2)\) has rejected an offer by the mechanism, i.e. \(c(a) \geq p_a\).

Recall that \(C\) is a budget feasible set of agents such that each \(a \in C\) was offered a price computed with some threshold \(t \leq t'\). We partition \(C\) into three sets: \(C_1 = C \cap S_1\), \(C_2 = C \cap S_2\) and \(C_3 = C \setminus (C_1 \cup C_2)\). By subadditivity, it holds \[v(C) \leq v(C_1) + v(C_2) + v(C_3).\]

To upper bound the value of \(C_1\) and \(C_2\) we use Theorem 8. This implies that for \(j \in \{1,2\}\) \[v(C_j) \leq 4 \mathbb{E}_{\!}\left[v(T_j)\right].\]

We proceed to upper bound the value of \(v(C_3)\). By non negativity and submodularity, it holds \[v(C_3) \leq v(C_3) + v(C_3 \cup S_1 \cup S_2) \leq v(C_3 \cup S_1) + v(C_3 \cup S_2).\]

We continue by bounding \(v(C_3 \cup S_1)\), by submodularity it holds \[v(C_3 \cup S_1) \leq v(S_1) + \sum_{a \in C_3 \setminus S_1} v(a \mid S_1).\]

We next use that each agent \(a \in C_3 \setminus S_1\) rejected an offer with threshold at most \(t'\) and marginal contribution at least \(v(a \mid S_1)\). This leads to \[\sum_{a \in C_3 \setminus S_1} v(a \mid S_1) \leq \frac{t'}{B} \sum_{a \in C_3 \setminus S_1} c(a) \leq t',\] where the last inequality holds due to the budget feasibility of \(C\).

Therefore we get \(v(C_3 \cup S_1) \leq v(S_1) + t'\) and with identical proof \(v(C_3 \cup S_2) \leq v(S_2) + t'.\)

Putting everything together concludes the proof of the Lemma.

10 Proof of Lemma 11↩︎

Fix \(m:=\tfrac{\log n}{\log\log n}\) and \(p:=\tfrac{\log\log n}{\log n}\), and set \(k:=\lfloor n/m\rfloor\). For a realization \(I\sim\mathcal{D}\), define \(X_i:=\sum_{a\in S_i}active(a,I)\), so that \(X_i\sim \mathrm{Bin}(m,p)\), the variables \((X_i)_{i\in[k]}\) are independent, and \(\mathbb{E}_{\!}\left[X_i\right]=mp=1\).

Each agent has cost \(c(a)=pB\), hence the budget allows purchasing at most \(B/c(a)=1/p=m\) agents. For any set \(T\subseteq N\) and realization \(I\), the valuation is \(v_I(T)=\max_{i\in[k]} \mu_i(T)\) where \(\mu_i(T)=\sum_{a\in S_i\cap T} \text{active}(a,I)\). Therefore, for any feasible \(T\) with \(c(T)\le B\), \[v_I(T)=\max_{i\in[k]} \sum_{a\in S_i\cap T}\text{active}(a,I) \le \max_{i\in[k]} \sum_{a\in S_i}\text{active}(a,I) = \max_{i\in[k]} X_i.\] On the other hand, for every \(i\) the offline optimum can pick exactly the active agents inside \(S_i\) (or all of them, since \(X_i\le m\)) and obtain value \(X_i\) while staying within budget. Hence \[\mathrm{\small Opt}(I) \geq \max_{i\in[k]} X_i.\]

Let \(M:=\max_{i\in[k]} X_i\). We first show \(\,\mathbb{E}_{\!}\left[M\right]=O(\tfrac{\log k}{\log\log k})\). For any integer \(t\ge 1\), by the union bound, \[\mathbb{P}\!\left[M\ge t\right]\le k\cdot \mathbb{P}\!\left[X_1\ge t\right].\] Since \(X_1\sim\mathrm{Bin}(m,p)\) has mean \(1\), a standard Chernoff bound yields \(\mathbb{P}\!\left[X_1\ge t\right]\le (e/t)^t\) for all \(t\ge 1\). Thus \(\mathbb{P}\!\left[M\ge t\right]\le k(e/t)^t\) and therefore \[\mathbb{E}_{\!}\left[M\right]=\sum_{t\ge 1}\mathbb{P}\!\left[M\ge t\right] \le t_0 + \sum_{t>t_0} k\left(\frac{e}{t}\right)^t,\] where \(t_0:=\left\lceil 3\frac{\log k}{\log\log k}\right\rceil\). For all sufficiently large \(k\) and all \(t\ge t_0\), the term \(k(e/t)^t\) is at most \(k^{-2}\), so the tail contributes \(O(1)\) and hence \[\mathbb{E}_{\!}\left[M\right]=O\!\left(\frac{\log k}{\log\log k}\right).\] For the matching lower bound, set \(t_1:=\left\lfloor \frac{\log k}{3\log\log k}\right\rfloor\). We lower bound \(\mathbb{P}\!\left[X_1\ge t_1\right]\) by considering the event that a fixed subset of \(t_1\) agents in \(S_1\) are active: \[\mathbb{P}\!\left[X_1\ge t_1\right]\ge \binom{m}{t_1} p^{t_1} (1-p)^{m-t_1} \ge \left(\frac{m}{t_1}\right)^{t_1} p^{t_1} \cdot (1-p)^m.\] Using \(mp=1\) and \((1-p)^m\ge e^{-mp}=e^{-1}\), we get \[\mathbb{P}\!\left[X_1\ge t_1\right]\ge e^{-1}\left(\frac{1}{t_1}\right)^{t_1}.\] Since \(t_1=\Theta(\tfrac{\log k}{\log\log k})\), we have \(\left(\tfrac{1}{t_1}\right)^{t_1}\ge k^{-1/3}\) for all sufficiently large \(k\), and thus \(\mathbb{P}\!\left[X_1\ge t_1\right]\ge k^{-1/3}/e\). By independence, \[\mathbb{P}\!\left[M< t_1\right]=\left(1-\mathbb{P}\!\left[X_1\ge t_1\right]\right)^k \le \exp\!\left(-k\cdot \mathbb{P}\!\left[X_1\ge t_1\right]\right) \le \exp(-k^{2/3}/e),\] so \(\mathbb{P}\!\left[M\ge t_1\right]\ge 1-\exp(-k^{2/3}/e)\) and therefore \[\mathbb{E}_{\!}\left[M\right]\ge t_1\cdot \mathbb{P}\!\left[M\ge t_1\right] =\Omega\!\left(\frac{\log k}{\log\log k}\right).\] Combining the two bounds yields \(\mathbb{E}_{\!}\left[M\right]=\Theta(\tfrac{\log k}{\log\log k})\). Finally, since \(k=\lfloor n/m\rfloor=\Theta(n\frac{\log\log n}{\log n})\), we have \(\log k=\Theta(\log n)\) and \(\log\log k=\Theta(\log\log n)\), implying \[\mathbb{E}_{I\sim\mathcal{D}\!}\left[\mathrm{\small Opt}(I)\right] =\mathbb{E}_{\!}\left[M\right] =\Theta\!\left(\frac{\log n}{\log\log n}\right),\] as claimed.

References↩︎