Efficient Algorithms for Online Subadditive Combinatorial Allocations

1 Introduction

• The open gap was whether the existential 6-competitive guarantee for subadditive valuations could be attained by an efficient online algorithm, beyond the prior O(loglog m) guarantee.Correa and Cristi’s result relied on a fixed-point theorem to establish a suitable random score generator, without a known polynomial-time construction.Source: §1 · p. 3
• A 6 + ϵ-competitive online algorithm is achieved in expected polynomial time with demand-oracle access, matching Correa and Cristi up to additive slack.The running time is polynomial in n, m, 1/ϵ, and the total support size of the valuation distributions.Source: §1 · p. 3

1.1 Our Techniques

• The BSG assigns buyer-dependent random item scores to resolve conflicts among sampled tentative bundles while retaining a constant fraction of bundle value.It recreates the symmetric-covering property used in Feige’s offline rounding and extends it online using simulated scores for future buyers.Source: §1 · p. 4, §1.1 · pp. 4, 7

1 Introduction

• Identical buyer valuation distributions improve the competitive factor to 60/11 + ϵ.Theorem 1.2 gives expected welfare at least a 1/(60/11 + ϵ) fraction of the expected offline optimum.Source: §1 · p. 4

1.1 Our Techniques

• The BSG yields Feige’s (2 + ϵ)-approximation offline and efficiently recovers the (6 + ϵ)-competitive online guarantee of Correa and Cristi.The prior offline approach needed all tentative bundles simultaneously, whereas future buyers’ bundles are unavailable online.Source: §1.1 · p. 5

2 Model and Preliminaries

• Buyers arrive in a fixed order with independently drawn valuations from publicly known distributions over normalized, monotone, subadditive valuations.Each buyer’s realized type is revealed at arrival, when the algorithm must irrevocably allocate a subset of remaining items.Source: §2 · pp. 8–9
• The model assumes finite-support valuation distributions and preprocessing access to demand oracles for each supported valuation.Running-time statements depend on n, m, the total number of types, and accuracy parameters.Source: §2 · pp. 8–9
• The algorithm maximizes expected welfare, measured against the expected value of the optimal allocation in hindsight.A γ-competitive algorithm achieves at least 1/γ times the expected offline optimum.Source: §2 · p. 9
• The ex-ante configuration LP has value at least α times the expected offline optimum, and a polynomial-support approximate solution can be computed with demand-oracle access.The LP may have exponentially many variables; dual separation and the ellipsoid method provide the stated optimization route.Source: §2 · p. 9

3.1 Motivation and definition

• Tentative bundles sampled from the configuration LP match its expected objective before conflicts, so rounding must resolve overlaps while preserving a constant fraction of value.The BSG assigns potentially correlated random scores to items within each tentative bundle.Source: §3.1 · p. 10

3.2 Stochastic Dominance and Subcriticality

• The Recursive-Height BSG is defined for subcritical distributions, and configuration-LP-induced distributions satisfy that condition.Subcriticality bounds each item’s aggregate probability of appearing in sampled interest sets.Source: §3.2 · p. 11

3.3 The Recursive-Height BSG

• The Recursive-Height BSG recursively samples scores for intersections between an input bundle and buyers’ interest sets.It uses one shared BSG for all buyers rather than a distinct generator for each buyer.Source: §3.3 · p. 11
• Theorem 3.1 establishes stochastic dominance for RecHeight and an expected running time polynomial in n, m, and (1 − α)^−1.The procedure terminates almost surely, with expected total interest-set size at most |A|/(1 − α) for input A.Source: §3.3 · p. 11, §3.4 · p. 12

3.4 Proof of Theorem 3.1

• The recursion’s expected total interest-set size is bounded by |A|/(1 − α), ensuring almost-sure termination; truncation can convert expected-polynomial guarantees to worst-case polynomial time.The truncation loss can be absorbed into the approximation slack ϵ.Source: §3.4 · p. 12

4 (2 + ϵ)-Approximation Offline Algorithm

• Each buyer independently samples a tentative bundle and generates BSG scores, then each contested item goes to a requesting buyer with the highest score.Items that appear in no tentative bundle may remain unallocated.Source: §4 · p. 13
• The rounding achieves a symmetric covering of each tentative bundle, allowing subadditivity to yield a constant-fraction value-retention guarantee.The offline rounding analysis gives expected welfare at least the stated fraction of the LP value.Source: §4 · pp. 14–15
• A (2 + ϵ)-approximation is obtained in expected polynomial time using demand-oracle access.The guarantee follows by choosing α = 2/(2 + ϵ) and rounding a feasible LP solution.Source: §4 · pp. 13, 15

5.1 Value Retention Guarantee

• The value-retention lemma relies on RecHeight's stochastic dominance together with valuation monotonicity and subadditivity.The lemma applies to a fixed item set and monotone subadditive valuation under a sub-critical collection of distributions.Source: §5.1 · p. 15

5.2 Valuation Distributions with Finite Supports

• The finite-support algorithm samples tentative bundles from an LP solution, scores them with RecHeight, and sets item thresholds using an independent sample's maximum scores.It follows the random-score perspective of Correa and Cristi, while using the BSG to generate correlated scores rather than nonconstructive buyer-specific generators.Source: §5.2 · p. 16
• Conditioned on a buyer's type and tentative set, its expected final value is at least 1/6 of that set's value, from a factor-2 online loss and factor-1/3 value retention.The retention analysis uses strict stochastic dominance to reduce the comparison to maximality among three i.i.d. threshold vectors.Source: §5.2 · pp. 17–18

5 (6 + ϵ)-Competitive Online Algorithm

• A (6 + ϵ)-competitive online algorithm runs in expected polynomial time for finite-support valuation distributions and with sampling access.For finite supports, the running time is polynomial in n, m, 1/ϵ, and the total support size; the sample-access variant has polynomial dependence on 1/ϵ.Source: §5.2 · p. 18, §5.3 · p. 22

5.3 Sample-Access Variant

• For sample access, the algorithm defines tentative-set distributions by sampling valuation profiles and solving the offline LP; these distributions are α-subcritical.For each arriving buyer, it completes the realized valuation with an independently sampled profile to generate a tentative set.Source: §5.3 · pp. 19–20
• The proof conditions on w(i) using Lemma 5.3 notation, invokes monotonicity of v_i across items, and combines the preceding step with Lemma 5.1.Source: §5.3 · p. 22

6 I.I.D. Arrival Model

• The section develops an improved upper bound and then shows that the ordering-cover argument cannot be improved within its analytic framework.This is the stated scope of the two parts of the i.i.d. arrival model.Source: §6 · p. 22

6.1 Improved Upper Bound

• The i.i.d. assumption permits a midpoint completion of the past, improving first-half buyers’ retained-value factor from 1/6 to 1/5 via a five-set cover.The midpoint comparison reduces value retention to an ordering-cover problem.Source: §6 · p. 22, §6.1 · p. 23
• 60/11 + ε is the competitive ratio obtained in the i.i.d. setting by aggregating the improved first-half guarantee with the general guarantee for later buyers.The proof uses retained-value factors of 1/5 for first-half buyers and 1/6 for the rest.Source: §6.1 · p. 25

6.2 Combinatorial Barrier for the Ordering Argument

• The ordering-cover construction uses five sets to cover the tentative bundle, with subadditivity converting that cover into a factor-5 value loss.In the generalized setting, the three threshold quantities consist of k, k, and ℓ independent batch-sized pieces.Source: §6.2 · p. 25
• For the generalized ordering-cover setup, every cover requires at least five permutations, so this approach cannot improve on the factor 5.The bound does not rule out an analysis using additional structure beyond symmetry and subadditivity.Source: §6.2 · pp. 26–27

AI Declaration

• The authors report using GPT-5.4 Pro to assist with the RecHeight construction, its value-retention guarantee, the i.i.d. improvement, and writing.They state that they checked the arguments and take responsibility for the paper’s content.Source: AI Declaration · p. 27

A Existence of fixed points

• The fixed-point perspective interprets the generators as buyers mirroring one another and connects the recursive procedure to the fixed-point argument.The paper also relates this view to Feige’s guiding-graph algorithm.Source: A Existence of fixed points · p. 28
• The mirroring protocol assigns each buyer scores so that, against the other buyers’ generators, the buyer retains at least a (1−ε)/2 fraction of expected tentative-set value.The resulting allocation is feasible because each item goes to at most one buyer.Source: A Existence of fixed points · pp. 28–29
• A mutually mirroring family of bundle score generators yields an integral allocation with expected welfare at least (1−ε)/2 of the configuration-LP value, so its integrality gap is at most 2 for subadditive valuations.Source: A Existence of fixed points · pp. 27, 30
• The appendix uses Brouwer’s fixed-point theorem to establish a family of mutually mirroring generators under the stated slack in the configuration-LP item constraints.The constructed strategy space is represented by probability arrays for the score distributions.Source: A Existence of fixed points · pp. 30, 32
• The appendix distinguishes a general Nash-equilibrium argument from the mutually mirroring construction, whose recursive unrolling provides a polynomial-time algorithm.The stated computation guarantee is sample access to each generator’s score distribution.Source: A Existence of fixed points · p. 32

B Applications to Maximin Share

• The proof recasts modified rounding as a fixed-point problem, then uses Brouwer’s theorem to establish that the desired distributions exist.The map sends candidate distributions to distributions produced by the modified mirroring protocol.Source: B Applications to Maximin Share · pp. 33, 37, 38
• The construction uses a special configuration-LP solution whose supported bundles give each player value at least 1 and whose item marginals satisfy the stated feasibility bounds.The passages identify these as the two properties of the special solution used for MMS instances.Source: B Applications to Maximin Share · p. 33
• The modified mirroring protocol takes d samples from each other player’s distribution and uses their pointwise maximum on a sampled set to concentrate allocations around their mean.The section presents this modification as the means of obtaining the lemma’s guarantee.Source: B Applications to Maximin Share · p. 34
• At least (1−ϵ)d/(d+1)|Q| players in Q can receive value at least 1/2 of their MMS.The construction first establishes this guarantee in expectation and then obtains an allocation with at least that many players meeting the threshold.Source: B Applications to Maximin Share · p. 38

C XOS Valuations via Online Contention Resolution Schemes

• The section’s feasibility model includes assigning an item to at most k_j buyers and can also represent matroid or knapsack constraints.These are examples of the downward-closed family for each item.Source: C XOS Valuations via Online Contention… · pp. 38–39
• If each item j has a γ_j-selectable OCRS, the online allocation algorithm for XOS valuations is γ-competitive for γ = min_j γ_j.The section also permits downward-closed feasibility families describing which buyers may simultaneously receive each item.Source: C XOS Valuations via Online Contention… · pp. 38–39
• Under uniformly random buyer arrival, a random-order contention resolution scheme can replace each item’s OCRS, improving the competitive guarantee in general.The stated improvement follows because RCRSs yield better selection guarantees than OCRSs in general.Source: C XOS Valuations via Online Contention… · p. 39

C.1 Proof of Theorem C.1

• An optimal configuration-LP solution supplies each arriving buyer’s type-conditioned tentative bundle, and item j is offered to its OCRS when it appears in that bundle.The algorithm assigns the buyer exactly those tentative-bundle items accepted by their respective OCRSs.Source: §C.1 · p. 40
• Each item’s OCRS makes feasible selections for its constraint family, so the combined allocation is feasible.The proof analyzes the chance that an item in a tentative bundle is accepted, using the OCRS selectability guarantee.Source: §C.1 · p. 40
• The algorithm’s expected welfare is at least γ times the optimal configuration-LP value, which upper-bounds the expected offline optimum.Here γ is the minimum selectability guarantee across items.Source: §C.1 · pp. 40–41

D Connection to Feige’s algorithm

• The recursive BSG is presented as a substantially simplified presentation of Feige’s guiding-graph algorithm [Fei06].The section sketches Feige’s method before explaining the conversion to the recursive algorithm.Source: D Connection to Feige’s algorithm · p. 41
• Feige’s method labels edges with sampled bundles, forms an item-specific subgraph from edges whose labels contain that item, then orients the resulting forests to resolve conflicts.A tentative bundle for each agent is taken from the labels of edges incident to a sampled vertex.Source: D Connection to Feige’s algorithm · pp. 41–42
• For vertex-transitive high-girth graphs, a fixed vertex can replace a random one without changing the distribution of allocations based on local information.The section cites as an example of such graph constructions.Source: D Connection to Feige’s algorithm · p. 42
• The BSG’s recursion tree represents the infinite regular tree suggested by Feige’s high-girth graphs, with each recursive call producing n subcalls and sampled LP interest sets labeling the branches.The section describes the recursion tree as corresponding to a depth-first traversal of the guiding graph.Source: D Connection to Feige’s algorithm · pp. 42–43
• The 1 + max y_ij recurrence computes subtree height, corresponding to orienting edges away from the tree’s diametric center and allocating an item to the player with the greatest rooted-subtree height.The passage identifies this orientation as one particular choice in Feige’s algorithm.Source: D Connection to Feige’s algorithm · p. 43

• 60/11 is the improved ratio that follows from the odd-n adaptation of Lemma 6.2.Source: E Improved Value Retention for IID… · p. 43
• D is generated from a tentative bundle sampled from μ using RecHeight, and Fh is the coordinatewise maximum of h independent draws from D.Coordinates outside the tentative bundle receive score zero; for h = 0, Fh is the all-zero vector.Source: E Improved Value Retention for IID… · p. 43
• Conditioned on buyer type and tentative bundle, the proof lower-bounds ALG's expected value by the expected value of eB.The comparison uses monotonicity to pass through BW, with eB identified as R5.Source: E Improved Value Retention for IID… · pp. 44–45
• The five sets R1 through R5 cover A for every realization and are identically distributed, though they need not be independent.The cover proof considers which score or threshold value is largest at each item; ties do not disrupt the argument.Source: E Improved Value Retention for IID… · p. 45