Single-or-Sample: Online Fair Allocation for Combinatorial Agents

1 Introduction

• The paper asks whether nontrivial MMS guarantees are possible against an oblivious adversary when the allocator lacks prior knowledge of agents’ valuations.Source: §1 · p. 3
• Constant MMS for all agents with constant probability is achievable for additive and submodular valuations, but XOS admits no 1/loglog n-MMS guarantee with constant probability.The overview also reports a matching XOS algorithm for the regime c ∈ Ω(log n), achieving 1/c-MMS with probability 1−O(1/c).Source: §1 · p. 4, §1.1 · p. 6

1.1 Technical Overview: Adaptive Bucketing and Sampling

• Bucketed sampling gives each arriving additive agent an Ω(1/n) fraction of remaining value, while single-item reduction handles agents whose MMS is concentrated in high-valued items.The overview states that Single-or-Sample guarantees every submodular agent 1/24 of MMS with probability at least 0.423.Source: §1.1 · pp. 5–6

1.2 Technical Overview: Concentration

• Adaptive sampling can create positive correlations, but upper-cylinder domination by independent Bernoulli sampling composes across iterations and supports Chernoff-style concentration.Source: §1.2 · pp. 6–7

1.3 Technical Overview: Incentives and Sharper Guarantees

• The algorithms use ordinal reports; truthful highest-marginal-value reporting is a safe submodular strategy even when other agents behave adversarially.Modifications also give individual constant-MMS guarantees with polynomially high probability, guarantees for all but log(n) uniformly random agents, and a 1-out-of-(n+o(n)) guarantee to all agents with probability 1−1/n.Source: §1.3 · pp. 7–8

1.4 Other Related Work

• Prior online indivisible-good work considered known-type stochastic arrivals, while existing concentration results do not cover this adaptive iterative sampling process.Source: §1.4 · pp. 8–9

2 Notation and Preliminaries

• For positive integer n, [n] denotes {1, 2, …, n}, [i, j] denotes the integers from i through j, and |N| denotes a set or list’s size.Source: §2 · p. 9

2.1 Problem Setting

• An online MMS instance has n agents and m indivisible goods, with each agent’s nonnegative, nondecreasing valuation revealed at arrival and an irrevocable allocation from the remaining goods.The adversary chooses valuations without seeing the algorithm’s random coin tosses.Source: §2.1 · pp. 9–10
• The paper considers additive, submodular, and fractionally subadditive XOS valuation functions.Additive valuations sum item values; submodular valuations have diminishing marginal returns, and XOS generalizes submodular valuations.Source: §2.1 · pp. 9–10

2.2 An Approximation vs Success Probability Tradeoff

• For any c ∈ (0, 1], no randomized algorithm is (c, β)-competitive for every β ≥ 1 − c^2 on some binary-additive instance.The lower-bound construction forces a choice between allocating goods to the first agent and preserving valued goods for later agents.Source: §2.2 · p. 11

3 Concentration for Iterative Hypergeometric Sampling

• Upper-cylinder domination survives adaptive bucketing and repeated sampling, enabling concentration bounds for iterative sampling without replacement.The analysis uses the surviving bound to control a moment generating function and then derive concentration.Source: §3 · p. 11

3.1 Single-iteration sampling without replacement

• For any fixed set, the probability that multi-bucket sampling selects every element is at most the corresponding probability under independent Bernoulli sampling with rate p.Later buckets may depend on earlier sample outcomes.Source: §3.1 · p. 12
• The weighted MGF bound supports concentration for linear functions of sampled elements, beyond counting surviving elements in a set.Source: §3.1 · p. 13

3.2 Iterative sampling without replacement

• Across iterations, the upper-cylinder bound composes, and the section gives a concentration theorem for a fixed set under IterSwR.The process removes each round’s sample before the next; Theorem 3.6 states a concentration bound for any subset S.Source: §3.2 · pp. 13–14

4 Warm-Up: Constant MMS Guarantee in the Absence of Large Values

• The warm-up assumes additive valuations normalized to MMSi = 1, with every item worth less than 1/12; agents partition remaining goods into 3n-sized buckets and receive a uniformly random item from each.The analysis combines high probability that enough value remains with a safe strategy that secures a fraction of that value, less the most valuable item.Source: §4 · pp. 14–15
• 1/12 − o(1) MMS to every agent simultaneously with probability 1 − 1/poly(n), when agents use the safe strategies in the static-bucketing algorithm.Source: §4 · p. 16

4.1 Modifications needed for submodular agents

• For submodular agents, buckets are chosen greedily by marginal value, and the analysis tracks a potential over the agent’s MMS-defining partition rather than remaining total value.The section notes that the additive proof’s remaining-value and 1-out-of-n MMS properties need not hold for submodular agents.Source: §4.1 · p. 16
• 1/12 − o(1) MMS to every agent simultaneously with probability 1 − 1/poly(n), when submodular agents use the specified safe strategies.Source: §4.1 · p. 17

5 Constant MMS guarantee for Submodular Valuations

• Special rounds let agents take a maximum-value item with certainty, while tracking their count adjusts later agents’ allocation probabilities.This single-item reduction addresses the problem that a few high-value items can dominate an agent’s value and defeat randomization over a large set.Source: §5 · p. 17

5.1 Safe strategy and MMS guarantee

• The safe strategy takes a maximum-value item when one reaches threshold τ; otherwise it uses randomized bucketing, guaranteeing at least 1/24 MMS with probability 1−q_i despite others’ actions.The strategy needs only ordinal information about highest-marginal goods and is simple for agents to implement.Source: §5.1 · p. 18

5.2 Analysis of a single agent

• For a single agent, the analysis normalizes MMS to one and studies the safe strategy against arbitrary behavior by preceding agents.If a sufficiently valuable item remains, the agent takes it; otherwise the agent enters adaptive bucketing.Source: §5.2 · p. 18

5.2.1 Greedy bucketing (Counterpart of Lemma 4.2)

• If the active MMS bundles retain total value Π ≥ (2k + 1)τN, greedy bucketing guarantees the agent value at least τ.Here N is the number of active bundles after t special rounds.Source: §5.2.1 · p. 19

5.2.2 The deficit: a weighted loss function

• The analysis measures losses using supporting prices and a deficit: active-bundle count minus surviving supporting weight.It deactivates one active MMS bundle per special round, so a special round cannot increase the deficit.Source: §5.2.2 · p. 20

5.2.3 An exponential-moment bound for the deficit

• The deficit’s exponential-moment bound holds even when preceding agents choose round types and buckets as arbitrary functions of the observed history.This adaptive-process bound replaces a fixed-set concentration argument.Source: §5.2.3 · p. 21

5.2.4 Failure probability for one agent (Counterpart of Lemma 4.1)

• To bound one agent’s failure probability, it suffices to keep the deficit below (1−(2k+1)τ)N_i, after which the exponential-moment bound and Markov’s inequality apply.The failure bound uses a parameter λ satisfying the stated condition in Lemma 5.5.Source: §5.2.4 · pp. 21–22

5.3 Bounding the total failure probability (Proof of Theorem 5.1)

• With the stated parameter choice, the agent’s MMS approximation guarantee is τ = 1/24, and each agent’s failure probability q_i is below 0.577; the constants are not optimized.For online MMS with submodular valuations, the approximation and success parameters α and β are both Θ(1).Source: §5 · p. 17, §5.3 · p. 22

6 Additional Properties of the Single-or-Sample Algorithm

• Skipping ⌈2 ln n⌉ fixed agents gives every remaining agent at least 1/24 MMS simultaneously with probability at least 1−1/n.The guarantee applies to submodular valuations.Source: §6 · p. 23
• Randomly choosing the skipped agents raises each agent’s 1/24-MMS success probability to at least 1−o(1), while increasing the chance that some agent fails.The modification trades a lower individual failure probability for a larger overall failure probability.Source: §6 · p. 23
• Relaxing the benchmark to 1-out-of-N-MMS for N slightly larger than n allows the simultaneous failure probability to be made polynomially small.The stated condition is N ≤ n + ⌈2 ln N⌉.Source: §6 · p. 23

7.1 Ruling out 1/ log log n-MMS

• No randomized online algorithm guarantees an Ω(1/log log n)-MMS allocation to all agents with constant probability against an oblivious adversary, even for binary-XOS valuations.The lower bound rules out this approximation with success probability Θ(1).Source: §7.1 · p. 24

7.1.1 Warm-up: a two-round construction.

• If every first-round agent gets a 2/3-MMS allocation, each uses at least 2m/(3n) goods from a distinct bin, so at least n/2 bins are damaged.Conditioned on first-round success, a damaged bin in the pool leaves at most m/(3n) unallocated goods. With probability 1−o(1), every part of every damaged bin in the pool contains fewer than 2m/(3n2) unallocated goods, so no associated second-round agent can receive a 2/3-MMS allocation.Source: §7.1.1 · p. 24

7.1.2 The complete construction

• The full lower-bound construction uses d+1 rounds, with randomly selected bins becoming hidden pools in the next round and each pool’s agents valuing its bins by their largest intersection.The adversary samples the instance before arrivals, so the input distribution is independent of the algorithm; agents learn pool and bin information only as they arrive.Source: §7.1.2 · p. 25

7.1.3 Analysis of deterministic algorithms

• Every constructed instance admits an offline MMS allocation, but online agents must allocate before learning which bins remain for later rounds.Successful pool groups damage at least αs_r bins; a retained damaged bin leads the witness sequence toward a final pool whose bins are too depleted for α-MMS.Source: §7.1.3 · pp. 26–27

7.2 Tight Logarithmic MMS Approximation for XOS valuations

• Greedy bucketing can reduce an agent’s value from MMS n to 1, so Algorithm 3 selects a sufficiently valuable MMS bundle and samples only within it.The example uses n agents and n² goods; after one good is selected from each part, the allocation has value 1 despite each good initially having singleton value 1.Source: §7.2 · p. 27
• For sufficiently large n, Algorithm 3 achieves (Θ(1/log n), 1−O(1/log n))-MMS competitiveness for agents with XOS valuations.The algorithm uses either a high-valued single good or a bundle formed by randomized sampling.Source: §7.2 · pp. 27–28

7.2.1 Analysis

• The success analysis divides agents into cases with many high-valued goods or substantial low-valued-goods value, then uses retention bounds and a union bound.A concentration lemma bounds preservation of the value of a fixed set through non-special rounds, with a related bound for its cardinality.Source: §7.2.1 · p. 29

Case 1: Agent has large number of high valued goods

• For an agent with many high-valued goods, the analysis couples the actual algorithm with a virtual process to bound losses in special rounds and show a high-valued good remains available.The goods considered lie in the agent’s untouched MMS bundles; the virtual process makes the relevant high-valued set deterministic.Source: Case 1: Agent has large number of high… · pp. 29–30
• For agents with many high-valued goods, the probability of a first failure at one of them is at most O(1/log n).The proof couples the algorithm to a virtual process that allocates available high-valued goods in a fixed order.Source: Case 1: Agent has large number of high… · p. 30

Case 2: Agent has small number of high-valued goods

• For sufficiently large n, the total probability that Algorithm 3 declares a first failure for some agent i in L′ is at most 1/n².Source: Case 2: Agent has small number of… · p. 31

Combining the cases: Proof of Theorem 7.9

• Algorithm 3’s failure probability is O(1/log n) after combining the two cases.This completes the proof of Theorem 7.9.Source: Combining the cases: Proof of Theorem… · p. 31

7.2.2 Tightness of Algorithm 3

• For any c in (0, 1], no randomized algorithm is (c, β)-competitive on every binary-XOS instance when β ≥ 1 − c^2.The construction uses one binary-XOS agent and n − 1 binary-additive agents.Source: §7.2.2 · pp. 31–32

8 AI Disclosure

• The authors say they developed the algorithms, used GPT 5.6 Sol and GPT 6 Astra for some analysis ideas and proofs, and verified and rewrote all proofs themselves.They take full responsibility for the correctness of all claims.Source: §8 · p. 32

A.1 Normalization of the Valuation Function

• Normalizing additive valuations sets each agent’s MMS to 1, and an α-approximation in the normalized instance transfers to an α-approximation of the original MMS.The construction rescales values using an MMS partition.Source: §A.1 · p. 38
• For submodular valuations, normalization divides values by the agent’s MMS and assumes without loss of generality that the instance is normalized.The MMS partition then has bundles of value at least 1, with the least-valued bundle equal to 1.Source: §A.1 · p. 38

A.2 Fractional Extensions for Submodular Functions

• The multilinear extension gives expected value when goods are included independently at specified marginal probabilities.The concave extension models the maximum expected value under correlated rounding that preserves those marginals.Source: §A.2 · p. 38
• For submodular functions, the passage states that the multilinear extension is at least the concave extension up to a correlation-gap bound.The bound’s displayed value is not provided in the supplied text.Source: §A.2 · p. 39

B Deferred Proofs for Sampling Without Replacement

• The claim is stated for positive integers q ≤ y < m and x in [0, 1], with the falling factorial defined as a product of descending factors.The supplied passage does not show the claim’s inequality.Source: B Deferred Proofs for Sampling Without… · p. 39
• The proof’s stated goal is to show that a function is nonpositive throughout [0, 1] by checking its maximum.It notes concavity and then evaluates the function at its maximizer.Source: B Deferred Proofs for Sampling Without… · p. 39
• The final inequality in the proof uses 1 ≤ q ≤ y + 1 and x ≤ 1.Source: B Deferred Proofs for Sampling Without… · p. 39

• Sampling with both fixed and adaptive bucketing can fail to satisfy negative association.Source: C Negative Association Can Fail Under… · p. 39
• The counterexamples correspond to a run of Algorithm 2 on submodular valuations.Source: C Negative Association Can Fail Under… · p. 39
• The counterexamples are carefully constructed and involved.Source: C Negative Association Can Fail Under… · p. 39

C.1 A counterexample with a monotone submodular valuation, and adaptive bucketing

• Negative association fails in a five-agent, ten-item instance after one execution of MSwR(G, 1/2).Source: §C.1 · p. 39
• The first agent’s valuation is monotone and submodular, and its MMS-defining bundles are {j, j + 5} for j in [5], each worth 1.Source: §C.1 · p. 40
• At each step, the algorithm selects the two remaining items with the largest marginal values and samples one item from that bucket.Source: §C.1 · p. 40
• After the initial bucket {1, 2}, the subsequent buckets depend on which item was sampled, producing distinct core-item arrangements under E and Ec.Source: §C.1 · pp. 40–41
• The core-item survival indicators yield increasing functions on disjoint coordinates, and the resulting calculation contradicts the inequality required by negative association.Source: §C.1 · p. 41

C.2 A counterexample with additive valuation, and fixed-probability SwR

• The instance has an item a and groups U and V; both agents’ fixed partitions are MMS-defining, with MMS exactly 1.Source: §C.2 · pp. 41–42
• In each round, buckets are intersections of the fixed MMS bundles with the remaining goods, and each bucket is sampled using the fixed-probability SwR rule.Source: §C.2 · p. 42
• The first-round sampling leaves both second-round buckets nonempty, while the resulting dependence yields the stated failure of negative association.Source: §C.2 · pp. 42–43
• The example’s survival indicators produce increasing functions on disjoint coordinates whose joint expectation exceeds the product of their expectations.Source: §C.2 · pp. 42–43
• Negative association fails after two rounds for two agents with additive valuations, fixed MMS bucket partitions, and common sampling probability p = 1/4.Source: §C.2 · pp. 41, 43

D Deferred Proofs for the XOS Lower Bound

• The offline allocation is feasible because agents can receive distinct full bins while later pools occupy bins retained in earlier rounds; each agent then gets value equal to her MMS.Source: D Deferred Proofs for the XOS Lower… · p. 43
• Sampling a bin without replacement gives nonpositive covariance between distinct draw indicators, yielding Var(X) ≤ M/4.Source: D Deferred Proofs for the XOS Lower… · p. 44
• The proof uses balance and newly allocated goods to inductively increase the deleted fraction along the selected pool sequence.Source: D Deferred Proofs for the XOS Lower… · pp. 44–45
• By the final round, every bin has at most (α/2)n² goods remaining, below the αn² value required by the witness agent.Source: D Deferred Proofs for the XOS Lower… · p. 45
• The selected witness sequence preserves the needed conditional randomness by exposing each lottery only after the round’s allocations and selecting the next pool before the next partition.Source: D Deferred Proofs for the XOS Lower… · p. 45
• If every encountered group succeeds and each selected refinement is balanced, the witness sequence forces a last-round agent to fail.Source: D Deferred Proofs for the XOS Lower… · p. 45
• For each selected lottery, the proof bounds the chance of missing a charged set, and for each selected refinement it bounds the chance of imbalance.Source: D Deferred Proofs for the XOS Lower… · p. 45
• For non-special rounds, the proof uses a supermartingale and bounds the cumulative exponent in its analysis by 1.Source: D Deferred Proofs for the XOS Lower… · p. 46