betaFeedback

WorksComputer Science

Prophet Secretary for Matroids and XOS Valuations: A Separation at 1-1/e and a 0.6767 Guarantee for I.I.D. Weights

Abstract

Ehsani, Hajiaghayi, Kesselheim, and Singla (SODA 2018) give (1−1/e)(1-1/e)-competitive algorithms for matroid prophet-secretary and prophet-secretary with XOS valuation functions. In this work we show that these two guarantees have different limits. For every matroid, we give a randomized (1−1/e+ε0)(1-1/e+\varepsilon_0)-competitive algorithm, where ε0=10−6\varepsilon_0=10^{-6}. The guarantee holds for independent nonnegative values with finite expected optimum. For explicitly given finite distributions with rational values and probabilities, the algorithm has polynomial worst-case running time in the matroid independence-oracle model. The oracle tests whether a queried set is independent. The algorithm makes O(N4)O(N^4) such queries in expectation and O(N4log⁡(N+2))O(N^4\log(N+2)) in the worst case, where NN is the number of elements. We further consider the i.i.d. version of this problem and provide a 0.67670.6767 competitive ratio for every matroid with i.i.d.\ nonnegative weights from a known distribution. This guarantee even holds in fixed arrival order (a.k.a. i.i.d. matriod prophet inequalities), even when the algorithm learns the order only as the elements arrive. For combinatorial auctions with XOS valuations, however, we show that 1−1/e1-1/e is the optimal competitive ratio. We give an explicit family of finite instances showing that no online algorithm can guarantee a larger competitive ratio than 1−1/e1-1/e, even when the buyers' valuations are i.i.d., every additive clause has coefficients in {0,1}\{0,1\}, and computation is unrestricted. Thus the matroid improvement exploits structure absent from general allocation with XOS valuations.

Introduction

Optimal stopping theory has long informed the design of online auctions. Hajiaghayi, Kleinberg, and Parkes [21] initiated the connection between secretary problems and online auction design, and Hajiaghayi, Kleinberg, and Sandholm [22] introduced prophet inequalities as a tool for designing and analyzing online auction mechanisms.1 These connections led to a broad study of how distributional information and random arrival can improve online allocation. In a prophet inequality problem, the values are drawn independently from known distributions, and an online algorithm makes irrevocable decisions as they are revealed. Its performance is compared with a prophet who sees all realizations before choosing an optimal feasible solution. The arrival order may be adversarial. In a secretary problem, the values are fixed and unknown, but the arrival order is uniformly random. The prophet-secretary model [16] combines the distributional information of prophet inequalities with the random arrival order of secretary problems. The distributions are known in advance, and the arrival order is uniform and independent of the realized values.

The central difficulty is to use this information while preserving feasibility for future arrivals. Accepting a valuable element may prevent the selection of later elements, and allocating an item to one buyer makes it unavailable to every later buyer. Distributional information allows an algorithm to estimate these opportunity costs; random arrival also limits how often an early decision can block a more valuable later one. We study how the interaction between these two sources of information depends on the feasibility structure. Our two settings are matroid selection and combinatorial auctions with XOS valuations, defined next.

Models and results

Matroid selection. The algorithm knows a matroid M=(E,I)M=(E,\mathcal{I}) on NN labeled elements and the distributions of their independent nonnegative weights XeX_e. On seeing a label and its weight, it irrevocably accepts or rejects the element. The accepted set must remain independent. In prophet secretary the arrival order is a uniform permutation independent of the weights. We will also consider an arbitrary order fixed independently of the weights and of the algorithm’s random bits. The benchmark in both models is

F0=EOPT⁡(M,X),OPT⁡(M,x)=max⁡I∈I∑e∈Ixe.F_0=\mathbb{E}\operatorname{OPT}(M,X),\qquad\operatorname{OPT}(M,x)=\max_{I\in\mathcal{I}}\sum_{e\in I}x_e.

Write ALG for the realized online reward. A ratio cc means E[ALG]≥cF0\mathbb{E}[\mathrm{ALG}]\ge cF_0. For our computational bounds the algorithm may query an independence oracle on any subset of the known ground set.

Theorem 1 (Independent weights in random order). For every finite matroid and independent nonnegative weights with F0<∞F_0<\infty, there is a randomized prophet-secretary algorithm with

E[ALG]≥(1−1/e+ε0)F0,ε0=1.14⋅10−6.\mathbb{E}[\mathrm{ALG}]\ge(1-1/e+\varepsilon_0)F_0,\qquad\varepsilon_0=1.14\cdot10^{-6}.

For explicitly given finite rational distributions, it uses O(N4)O(N^4) independence queries in expectation and O(N4log⁡(N+2))O(N^4\log(N+2)) in the worst case. Its arithmetic work and number of random bits are polynomial in the input length on every execution.

When the weights share a law, the next theorem gives a larger guarantee under a weaker assumption on the order.

Theorem 2 (I.i.d. weights in a fixed order). Let the weights of a known finite matroid be independent draws from a common known nonnegative distribution of finite mean. There is a randomized online algorithm that, in every fixed arrival order, obtains

E[ALG]≥c0F0,c0=11+η0=0.6767410571…,η02=e−1−η0,η0>0.\mathbb{E}[\mathrm{ALG}]\ge c_0F_0,\qquad c_0=\frac{1}{1+\eta_0}=0.6767410571\ldots,\qquad\eta_0^2=e^{-1-\eta_0},\quad\eta_0>0.

The algorithm need not know the order in advance.

Averaging over a uniform permutation gives the same ratio for prophet secretary. The theorem also covers a matroid in which some labels have many substitutes and others have none. Its proof uses symmetry of the weights alone. The algorithm can be implemented by sampling and making O(N4log⁡(2N))O(N^4\log(2N)) independence queries. In a real-arithmetic model it only needs evaluations of the common distribution function and its left limits at the observed weights. For a finite rational law the same ratio holds with a worst-case polynomial bound on bit complexity (Appendix § 12).

Welfare with XOS buyers. There is a fixed set UU of items. Each buyer ii has a valuation drawn independently from a known distribution. When buyer ii arrives, the algorithm observes her valuation viv_i and assigns her a bundle SiS_i of unallocated items. Her valuation is XOS if it is the maximum of nonnegative additive clauses, that is, vi(S)=max⁡ℓ∑j∈Swiℓjv_i(S) = \max_\ell\sum_{j\in S} w_{i\ell j} for wiℓj≥0w_{i\ell j} \ge0. The benchmark OPT is the maximum welfare ∑ivi(Si)\sum_i v_i(S_i) over pairwise disjoint bundles for the realized valuations.

Theorem 3 (Sharpness for XOS welfare). For every ξ>0\xi> 0 there is a finite instance with i.i.d. buyers for which every randomized online algorithm satisfies

E[ALG]<(1−1/e+ξ)E[OPT].\mathbb{E}[\mathrm{ALG}] < (1 - 1/e + \xi)\mathbb{E}[\mathrm{OPT}].

All additive clauses have coefficients in {0,1}\{0,1\}. The bound holds with public menus of clauses and unlimited computation, even if the order of buyer identities is announced in advance.

Together with the algorithm of Ehsani et al. [15], this identifies the optimal guarantee for XOS welfare. The upper bound also follows from the i.i.d. coverage-welfare construction of Udwani and Wajc [33] by interchanging the roles of items and buyers. § 10 gives the reduction and a direct proof.

Relation to the earlier version. Theorem 1 of the first arXiv version provides a similar competitive ratio with ε0=1.01⋅10−6\varepsilon_0 = 1.01\cdot10^{-6} for matroid prophet secretary with the same oracle complexity. The main addition here is Theorem 2 for i.i.d. distributions, with an improved competitive ratio. The previous version also established the XOS upper bound. In addition to that, here, we show that the XOS upper bound with additive tolerance ξ\xi can be witnessed on O(ξ−4log⁡(1/ξ))O(\xi^{-4}\log(1/\xi)) items (Corollary 26).

Approach and techniques

The common accounting identity. For a nonnegative weight vector xx, put St={e:xe>t}S_t = \{e : x_e > t\} and let r(S)r(S) denote the rank of SS. A maximum-weight basis found by greedy contains exactly r(St)r(S_t) elements of StS_t at every height tt. Consequently,

OPT⁡(M,x)=∫0∞r(St) dt.(1)\operatorname{OPT}(M,x) = \int_0^\infty r(S_t)\,\mathrm{d}t. \tag*{(1)}

To see what one online decision costs at a given height, fix the arriving nonloop ee, and let AA consist of the unseen elements above that height. If AA spans ee, taking ee consumes one unit of the rank available to AA. If AA does not span ee, taking ee costs AA nothing, but passing over ee can lose a unit of rank when its own weight exceeds tt. Both matroid algorithms price these two possibilities. The common-law assumption changes what can be learned from a single sampling experiment.

One quantile cutoff for every height. Suppose the common upper-tail probability at height tt is vv. In the residual matroid, the unseen elements above tt form a set obtained by retaining each unseen element independently with probability vv. Write Se(v)S_e(v) for the probability that this set fails to span ee. An upper quantile qq specifies a threshold. The rule takes ee on the best qq fraction of its draws, breaking ties at atoms by an independent random choice. At any height with tail probability vv this rule earns min⁡{q,v}\min\{q,v\} in expected count. Its expected cost to the remaining rank is

vSe(v)+q(1−Se(v)).vS_e(v) + q(1-S_e(v)).

The first term is the expected cost of deletion. The second is the extra cost of contracting ee when the rule accepts. In particular, the decision pays for itself exactly at v=qv=q.

The same cutoff must also pay for the narrow bands v<qv<q and the wide bands v>qv>q. For v<qv<q there is a loss only when the unseen sample spans ee. For v>qv>q there is a loss only when it fails to do so. This is where the shape of SeS_e matters. Calibrate qq by Se(q)=e−aS_e(q)=e^{-a}. A product-measure inequality bounds Se(v)S_e(v) from below by e−av/qe^{-av/q} for v<qv<q and from above by the same curve for v>qv>q. Thus the excess cost per unit of reward is at most aa on narrow bands and at most max⁡x≥1(x−1)e−ax=e−1−a/a\max_{x\ge1}(x-1)e^{-ax}=e^{-1-a}/a on wide bands. Equating the two gives exactly a=η0a=\eta_0 in Theorem 2. The bound holds after fixing both the history and the next label, which explains why this proof needs no randomness in the arrival order. A sequence of parallel elements makes the one-step comparison sharp. The optimal rank-one policy can do better by compensating for a loss at one step with a gain at another.

Beyond the one-step comparison. For i.i.d. weights in random order, the distinction between a local guarantee and the optimal ratio can be made precise. Follow an arbitrary policy through its sequence of residual matroids. If it accepts a label with conditional probability qq in a given minor, replacing that decision by a top-qq cutoff sends the same probability mass to each child and earns at least as much in every upper band. Thus a policy can be described by a flow on labeled minors. In fact a single flow attains the worst-law ratio of the matroid simultaneously for all common laws. If some finite set of band targets were incompatible, a separating hyperplane would supply nonnegative weights for the bands. Those weights are the increments of a finite-support common law on which every policy misses its target. Appendix § 13 proves this characterization and a companion identity that compares the optimal online price with the prophet’s realized replacement cost on the same random restriction.

Pricing a decision when the laws differ. With arbitrary marginals, the unseen set at height tt samples different labels at different rates. There is no common quantile at which to apply the preceding comparison. We work directly with the weighted optimum and use the randomness of the next label. For a nonloop ee, fix the other weights and let τe\tau_e be the difference between their optima after deleting and contracting ee. Deleting ee from the original instance loses (Xe−τe)+(X_e-\tau_e)^+, where u+=max⁡{u,0}u^+=\max\{u,0\}. The sum of these losses in expectation, divided by the number of remaining labels, is the cost of rejecting the next arrival.

A large expected deletion loss can arise in two ways. An element might rarely draw a very large weight, or it might regularly beat its replacement by a substantial margin. To distinguish them, draw its weight a second time, keeping the other weights fixed. The quantity (min⁡{Xe,Xe′}−τe)+(\min\{X_e,X'_e\}-\tau_e)^+ counts the part of the surplus that survives the second draw. Summing its expectation over labels gives the stable surplus. Roughly speaking, rare high offers favor a posted price, whereas persistent membership in an optimum favors a basis-exchange rule. To make this distinction quantitative, we first choose the distribution against which to measure the two surpluses.

Starting from the actual upper tails, multiply every tail probability by a common scale factor qq near one, capping the result at one. Let FqF_q be the expected optimum of this reference instance. The potential is (1−θq)Fq(1-\theta q)F_q, with θ\theta slightly below 1/e1/e. Increasing qq makes the reference optimum larger and its coefficient smaller. The rate at which FqF_q grows is closely related to deletion surplus. At a given height, increasing one label’s probability changes expected rank precisely when the other active labels fail to span it. Integrating over heights relates the derivative of FqF_q to the sum of the deletion losses. The stable surplus bounds the contribution of tails that reach the cap. Concavity then allows the algorithm to choose qq without sacrificing the potential inherited from earlier decisions.

Small stable surplus. The algorithm posts a price proportional to the expected difference between deleting and contracting the next label. Charging the price only to elements of the optimal basis loses too much. An element outside that basis can still clear its price, and a rule processing one arrival can collect its surplus. To quantify this contribution we cap the reference weights at scaled contraction prices and apply a tangent inequality for the expected rank under Poisson rounding [14]. After integrating over heights, the extra surplus covers the expected deletion loss. The rule processes one arrival and repeats in the resulting minor.

Large stable surplus. Two independent reference optima then have substantial overlap. To measure the relevant overlap, count a shared element at height tt only when it belongs to both optima and both its weights exceed tt. Integrating this expected count gives a weighted overlap QQ. § 4.2 lower-bounds QQ by comparing greedy and reverse-greedy bases of each level set. The algorithm can spend this overlap in the last part of the arrival sequence. It maintains virtual bases containing all previously accepted labels, updating each basis by an injective exchange whenever a new label is accepted. Early on it randomly thins acceptances to control the rate at which an exchange can displace any particular element. In a short final interval it removes this thinning. The corresponding loss in the baseline guarantee is quadratic in the length of that interval, whereas the gain from overlap is linear. Near the endpoints of the reference search, the baseline continuation has enough slack to pay for the final interval even at zero overlap. These comparisons cover all branches of the algorithm.

Why the XOS upper bound survives identical distributions. The auction construction has a public collection of partitions of the items, with one partition for every possible set of distinct buyer types. If the nn realized types are distinct, the prophet can choose their common partition and give each buyer a different part, attaining full welfare. An online allocation fixes a supporting clause for each bundle as soon as it is assigned. Each such clause points to a partition indexed by just nn types, so with a sufficiently large type space a later buyer is unlikely to be able to use the same partition. The construction makes one part from each of nn distinct partitions cover exactly a 1−(1−1/n)n1-(1-1/n)^n fraction of the items. This counting identity limits the total welfare even when all valuation types and their probabilities are public.

Related work

Independent distributions and random arrival. The classical prophet inequality compares an online stopping rule with the expected maximum of independent nonnegative random variables [KS77]. Its connections to online auctions and pricing were developed in [21, 22].2 Esfandiari et al. [16] introduced the prophet-secretary model. In an arbitrary fixed order, the matroid inequality of Kleinberg and Weinberg [29] and the posted-price mechanism of Feldman, Gravin, and Lucier [18] give a factor of 1/21/2 for matroid selection and XOS welfare, respectively. Ehsani et al. [15] showed that random arrival raises both guarantees to 1−1/e1 - 1/e. For a single choice, Azar, Chiplunkar, and Kaplan [3] broke this barrier, followed by Correa, Saona, and Ziliotto [13]. Chen et al. [12] obtained 0.688 for a single choice and 0.641 for prophet-secretary matching.

Identical distributions. In rank one the sharp constant over all horizons is 0.745440 . . .. Hill and Kertz [20] obtained the sharp finite-horizon constants, and Kertz [25] determined their limit. Abolhassani et al. [4] gave a threshold rule attaining 0.738 asymptotically. Correa et al. [CFH+21] matched the limiting upper bound with a guarantee for every horizon. For kk choices, Brustle, Perez-Salazar, and Verdugo [8] characterized the finite-horizon i.i.d. ratio by a linear program. A cardinality constraint is invariant under relabeling. On a general matroid, exchanging two labels can change feasibility even when their weights have the same law. In the related random-assignment secretary problem [32], an unknown list of weights is assigned uniformly to the labels. Conditioning i.i.d. weights on their unordered multiset gives this assignment. Our algorithm also uses the common law to compute weight quantiles.

Contention resolution and basis exchange. An online contention-resolution scheme selects a feasible subset from a random set of active elements [19]. Lee and Singla [30] obtained the tight factor 1−1/e1 - 1/e for matroids under random arrival against the ex-ante relaxation. The distinction between benchmarks already matters in rank one. If each of nn elements independently has value one with probability 1/n1/n and zero otherwise, the ex-ante value is one, whereas the expected optimum is 1−(1−1/n)n1 - (1 - 1/n)^n. Our matroid guarantees use the latter benchmark. Adamczyk and Włodarczyk [6] used basis-exchange maps of the kind proved by Brualdi [9] to maintain feasible sets under random arrivals. Our heterogeneous algorithm applies exchanges to bases drawn from a reference distribution and uses the overlap of two such optima to bound the gain over 1−1/e1 - 1/e. The rank inequality in its analysis uses the concavity of Poisson-rounded matroid rank [14].

Information about weights. In the matroid secretary problem [7], the weights are fixed and unknown. Recent algorithms give a constant guarantee in this model [31, 24 ABH+26]. The single-sample prophet model gives one independent sample from each law. Azar, Kleinberg, and Weinberg studied its connection to secretary algorithms [5]. For a fixed arrival order independent of samples, realizations, and private randomness, Abdi et al. [2 ABH+26] obtained the sharp factor 1/21/2 on every matroid. Our algorithms use known distributions.

Online welfare. In the item-arrival model with coverage valuations, Kapralov, Post, and Vondrák [27] proved that greedy achieves 1−1/e1 - 1/e on i.i.d. arrivals and that a polynomial-time algorithm improving this factor would imply NP = RP. Udwani and Wajc [33] proved the same upper bound for unrestricted computation even when the common distribution is known. Chawla and Dang [10 Appendix D] used a coverage-to-XOS transformation in the free-disposal model. § 10.3 explains how it carries the information-theoretic bound over to irrevocable buyer-arrival allocation.

Organization. After the common matroid preliminaries, § 3 gives the i.i.d. algorithm and proves the sharp bound on its one-step analysis. For general marginals, § 4 and § 6 prove the threshold and exchange bounds. § 7–§ 9 use these bounds in the online algorithm. § 10 gives the auction construction. Appendices § 12 and § 13 treat implementation and optimal policies for i.i.d. weights. Appendices § 14 and § 15 give the bit complexity and the numerical certificate for general marginals.

Matroid preliminaries

Matroids and residual instances. We use the matroid and prophet-secretary models of § 1.1. For M=(E,I)M=(E,\mathcal{I}), the rank of S⊆ES\subseteq E is

rM(S)=max⁡{∣I∣:I⊆S, I∈I}.r_M(S)=\max\{|I|:I\subseteq S,\ I\in\mathcal{I}\}.

A basis is a maximal independent set. Write B(M)\mathcal{B}(M) for the set of bases, all of size rM(E)r_M(E). The closure of SS is cl⁡M(S)={e∈E:rM(S∪{e})=rM(S)}\operatorname{cl}_M(S)=\{e\in E:r_M(S\cup\{e\})=r_M(S)\}. We say SS spans ee if e∈cl⁡M(S)e\in\operatorname{cl}_M(S) and spans TT if T⊆cl⁡M(S)T\subseteq\operatorname{cl}_M(S). A flat is a set equal to its closure. An element is a loop if its singleton is dependent and a coloop if it belongs to every basis. Two distinct nonloops are parallel if their pair has rank one. Subscripts are omitted when the matroid is clear.

The restriction to R⊆ER\subseteq E is M∣R=(R,{I∈I:I⊆R})M|_R=(R,\{I\in\mathcal{I}:I\subseteq R\}), and the deletion of RR is M\R=M∣E\RM\backslash R=M|_{E\backslash R}. The contraction M/RM/R has ground set E\RE\backslash R and rank function

rM/R(S)=rM(S∪R)−rM(R).r_{M/R}(S)=r_M(S\cup R)-r_M(R).

This definition also applies when RR is dependent. If RR is independent, SS is independent in M/RM/R exactly when S∪RS\cup R is independent in MM. For a single element, write M\eM\backslash e and M/eM/e. A matroid obtained by deletions and contractions is a minor. A set JJ disjoint from TT is independent over TT if rM(T∪J)=rM(T)+∣J∣r_M(T\cup J)=r_M(T)+|J|.

A circuit is an inclusionwise minimal dependent set. If BB is a basis and e∉Be\notin B, the unique circuit in B∪{e}B\cup\{e\} is the fundamental circuit of ee with respect to BB. We use the shorthand B−f+e=(B\{f})∪{e}B-f+e=(B\backslash\{f\})\cup\{e\}.

At a residual state, the accepted independent set is contracted and rejected elements are deleted. We discard loops. Independence of the weights allows us to use the original distribution on each surviving label. To implement a matroid independence query in the residual minor, adjoin the already contracted independent set and make one query to the original matroid independence oracle.

References

  1. [2]Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, and Danny Mittal. On the strong Matroid Secretary Conjecture and beyond. arXiv preprint arXiv:2609.19118, 2026.arxiv.org/abs/2609.19118
  2. [3]Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1 − 1/e barrier. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC), pages 303–318. ACM, 2018.arxiv.org/abs/1711.01834
  3. [4]Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert Kleinberg, and Brendan Lucier. Beating 1 − 1/e for ordered prophets. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 61–71, 2017.DOI
  4. [5]Pablo D. Azar, Robert Kleinberg, and S. Matthew Weinberg. Prophet inequalities with limited information. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1358–1377. SIAM, 2014.
  5. [6]Marek Adamczyk and Michał Włodarczyk. Random order contention resolution schemes. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 790–801. IEEE, 2018.arxiv.org/abs/1804.02584
  6. [7]Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 434–443. SIAM, 2007.DOI
  7. [8]Johannes Brustle, Sebastian Perez-Salazar, and Victor Verdugo. Splitting guarantees for prophet inequalities via nonlinear systems. Mathematics of Operations Research, 51(2):877–904, 2026.arxiv.org/abs/2406.17767
  8. [9]Richard A. Brualdi. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society, 1(2):161–167, 1969.DOI
  9. [10]Shuchi Chawla and Trung Dang. Single-sample prophet inequalities: A combinatorial to single-item reduction. arXiv preprint arXiv:2610.03660, 2026.arxiv.org/abs/2610.03660
  10. [12]Ziyun Chen, Zhiyi Huang, Dongchen Li, and Zhihao Gavin Tang. Prophet secretary and matching: The significance of the largest item. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1371–1401. SIAM, 2025. Journal version in ACM Transactions on Algorithms, 2026, doi:10.1145/3811027.DOI
  11. [13]José Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. Mathematical Programming, 190:483–521, 2021.
  12. [14]Shaddin Dughmi, Tim Roughgarden, and Qiqi Yan. From convex optimization to randomized mechanisms: Toward optimal combinatorial auctions. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC), pages 149–158. ACM, 2011.arxiv.org/abs/1103.0040
  13. [15]Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 700–714. SIAM, 2018. arXiv:1710.11213. Journal version in SIAM Journal on Computing, 53(6):1641–1662, 2024.arxiv.org/abs/1710.11213
  14. [16]Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. Prophet secretary. In Algorithms – ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 496–508. Springer, 2015. Journal version in SIAM Journal on Discrete Mathematics, 31(3):1685–1701, 2017.
  15. [17]David Ellis, Nathan Keller, and Noam Lifshitz. On a biased edge isoperimetric inequality for the discrete cube. Journal of Combinatorial Theory, Series A, 163:118–162, 2019.arxiv.org/abs/1702.01675
  16. [18]Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 123–135. SIAM, 2015.
  17. [19]Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1014–1033. SIAM, 2016.
  18. [20]Theodore P. Hill and Robert P. Kertz. Comparisons of stop rule and supremum expectations of i.i.d. random variables. The Annals of Probability, 10(2):336–345, 1982.DOI
  19. [21]MohammadTaghi Hajiaghayi, Robert Kleinberg, and David C. Parkes. Adaptive limited-supply online auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce, EC ’04, pages 71–80. ACM, 2004.DOI
  20. [22]MohammadTaghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, pages 58–65. AAAI Press, 2007.
  21. [23]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963.
  22. [24]Zhiyi Huang. Settling the matroid secretary problem. arXiv:2609.30421, 2026.arxiv.org/abs/2609.30421
  23. [25]Robert P. Kertz. Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality. Journal of Multivariate Analysis, 19(1):88–112, 1986.DOI
  24. [26]Adam Kohlhaas. Sandholm receives SIGecom test of time award. Carnegie Mellon University, School of Computer Science, June 2026.
  25. [27]Michael Kapralov, Ian Post, and Jan Vondrák. Online submodular welfare maximization: Greedy is optimal. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1216–1225. SIAM, 2013.
  26. [29][KW12] Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC), pages 123–136. ACM, 2012.
  27. [30][LS18] Euiwoong Lee and Sahil Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics, pages 57:1–57:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.arxiv.org/abs/1806.09251
  28. [31][Sin26] Sahil Singla. The matroid secretary conjecture is true. arXiv:2609.14555, 2026.arxiv.org/abs/2609.14555
  29. [32][Sot13] José A. Soto. Matroid secretary problem in the random-assignment model. SIAM Journal on Computing, 42(1):178–211, 2013.
  30. [33][UW26] Rajan Udwani and David Wajc. Online submodular welfare maximization: Computation is not the bottleneck. In Proceedings of the 67th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2026. arXiv:2610.16060.arxiv.org/abs/2610.16060

Paper details

vlnc:W_mswuv6ng
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 22

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI Astra, Gemini Argon

View statement
Looking for related papers…
Contents