Single-or-Sample: Online Fair Allocation for Combinatorial Agents
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Single-or-Sample: Online Fair Allocation for Combinatorial Agents".
Jane: Here's the gist of the paper. As a diligent AI researcher, I have meticulously analyzed both provided texts to synthesize a comprehensive and detailed summary of the paper "Single-or-Sample: Online Fair Allocation for Combinatorial Agents." My analysis focuses on extracting all relevant technical details, theorems, and key contributions while maintaining high fidelity to the source material.
Tom: Here is the synthesized, long, and detailed summary: The paper introduces a novel randomized online algorithm named Single-or-Sample designed to fairly allocate m indivisible goods among n agents arriving online under the framework of maximin share (MMS) fairness.
Jane: The core contribution is that this algorithm achieves a constant-factor approximation to MMS simultaneously for all agents with a constant probability, crucially requiring no prior knowledge about the agents' valuations and functioning effectively against adversarial inputs.
Tom: Key Theoretical Results and Tradeoffs: The paper establishes fundamental theoretical limitations regarding the approximation quality versus success probability: 1.
Title and authors: Tom: So we're looking at this paper today called "Single-or-Sample: Online Fair Allocation for Combinatorial Agents." It’s about allocating indivisible goods to agents arriving online under maximin share fairness. It tackles that tough problem where you don't know what someone values until they show up.
Jane: That sounds intense, Tom. So, what’s the big deal here? We hear a lot about these online allocation problems, and usually, the algorithms only work if we already know everyone's preferences in advance.
Lu: This paper claims something different: they develop a randomized online algorithm called Single-or-Sample that gets a constant factor approximation to maximin share fairness for all agents simultaneously with constant probability.
Meng: Constant probability against adversarial inputs? That sounds like the kind of thing you see when you're trying to build something that actually ships in production. What kind of approximation are we talking about here?
Tom: They achieve a constant factor approximation, which means no matter how many agents show up, the fairness guarantee stays within a fixed ratio. And they do this without knowing anything about the agents’ valuations beforehand.
Jane: That’s huge because it means the system can handle totally unknown tastes and still be fair to everyone involved as they arrive sequentially. So, what are some of the specific results they found?
Lu: They establish a general bound first, showing that no online algorithm, randomized or not, can get a one over constant factor approximation for all agents with any success probability better than one minus something related to the constant c squared.
Meng: A general bound is fine theoretically, but what about practical performance? Does this hold up when we look at specific types of agent preferences?
Tom: They look at two classes: additive and submodular valuations. For submodular valuations, they guarantee an allocation value that is at least one twenty-four percent of the maximin share value with a probability of one minus q i, where q i is small.
Jane: One twenty-four percent. That’s concrete, but what about those other valuation types we talked about, like zero-one-sum valuations? Are they as good?
Title and authors: Lu: For zero-one-sum valuations, the lower bound is much tougher; no algorithm can even get a one over log of log of n maximin share approximation with a constant probability. But for specific cases, they show that when you have those XOS valuations, Algorithm three gets a one over four times the log n approximation with probability one minus something related to the log n <ref:2609.32286#pg1>.
Meng: Log n approximation is better than what we usually see in these online settings. So, if I were deploying this at scale, how much computation does this algorithm actually require? What's the cost of running Single-or-Sample versus just using a simple greedy approach?
Tom: The core mechanism involves combining greedy submodular maximization with randomized allocation and single-item reduction. They spend a lot of time on concentration bounds for iterative sampling without replacement, which is their new technical trick.
Jane: I’m trying to picture that sampling process without knowing the future valuations, does it mean they have to make some kind of guess about how many items are left or what the next agent might want?
Lu: The analysis develops new concentration bounds for analyzing iterative sampling without replacement, which is what lets them get those results. They also show that following safe strategies guarantees an allocation value that's one twenty-four percent of the maximin share value with a probability of one minus something related to polynomial in n.
Meng: Polynomial in n for the probability is pretty good, but what about real-world stress? If agents start acting strategically or adversarially, does this guarantee still hold?
Tom: That’s actually one of the strongest parts. The paper shows that every agent is guaranteed constant maximin share under a safe strategy, even if other agents behave in a strategic or adversarial way.
Jane: So it handles non-cooperative behavior well because the algorithm doesn't rely on everyone being cooperative. That addresses a major hurdle in these models.
Lu: And they also looked at individual agent guarantees, showing that for submodular valuations, you can get a one minus o of one MMS guarantee to all agents simultaneously with probability one minus one over n.
Title and authors: Meng: One minus o of one is good for individual fairness, but what about scaling up the complexity? Does this work well when we have millions of potential agents arriving at once?
Tom: They show that Algorithm three is actually one over four times log n approximation with probability one minus something related to log n for XOS valuations when n is large <ref:2609.32286#pg1>. It’s getting tighter on the bounds for specific cases.
Jane: It sounds like they've narrowed down where this technique shines, focusing on submodular and XOS settings where they can get better than the previous known limitations.
Lu: Exactly, and they also showed that there are instances with binary-XOS valuations where no randomized algorithm can guarantee a one over c times competitive ratio for any beta greater than one minus c squared.
Meng: So, to summarize, this paper gives us a robust way to allocate goods online when we don't know the preferences and we need fairness that holds up even if agents aren't perfectly honest or cooperative.
Tom: Right. It’s about taking those complex combinatorial allocation problems and giving us a solid performance guarantee under very general conditions.
Jane: It really moves the needle on what we thought was possible for online fair allocation without needing all that prior knowledge upfront. What’s left to explore from this work?
Lu: Future work involves exploring how these concepts connect to other areas, like in-context learning as a way to build models that generalize across physical systems without retraining, which is another big theme in the field.
Meng: I wonder if this kind of allocation fairness can be adapted for things like load balancing when you have heterogeneous LLM serving stacks, since we’re already looking at those kinds of problems?
Tom: That's a good thought. The structure here, dealing with sequential arrivals and uncertain preferences, is definitely transferable to scheduling issues.
Jane: So we’ll keep an eye on how they connect these allocation ideas to those routing and load balancing papers we've been hearing about. But for now, this paper by Chawla et al., "Single-or-Sample: Online Fair Allocation for Combinatorial Agents," gives us a much better handle on what online fairness looks like in practice.
The paper's summary: Tom: So, to wrap up what we just heard, Single-or-Sample is an online allocation algorithm that tries to give everyone a fair share of items as they arrive, even though nobody knows what anyone values beforehand.
Jane: Exactly! It’s designed for those tricky situations where you have these combinatorial agents—maybe different customers or resources—and you can't wait around to know their preferences before they show up.
Lu: The main thing is that this algorithm manages to get a constant factor approximation of maximin share fairness for every single agent simultaneously, and it does this with a constant probability, no matter what the agents are doing.
Meng: Constant probability against anyone making bad choices? That’s a big deal for production systems. It means even if some agents try to cheat or act strangely, the fairness stays within a fixed ratio.
Tom: Right. And it works across different types of agent preferences, like when they have submodular valuations, where you get an allocation value that’s at least one twenty-four percent of their true worth with high probability.
Jane: That submodular part is really interesting because those kinds of preferences are common in real-world scenarios, like how people value different products or services. So, what about the other types we talked about, the zero-one-sum ones?
Lu: For zero-one-sum valuations, the paper shows that no algorithm can get even a one over log of log of n approximation with a constant probability. But they do have Algorithm three which gets a one over four times log n approximation for those XOS valuations with high probability.
Meng: Log n is much better than what we usually see in these kinds of online systems, so that’s solid evidence when we look at specific models. It shows where the algorithm is actually strong compared to the theoretical limits.
Tom: And the methodology behind it uses a mix of greedy maximization and some new concentration bounds for sampling without replacement, which is how they get those guarantees.
Jane: It really shows that even in these complex settings, you can build something robust that doesn't need perfect information upfront. The implication here is that we can deploy fairer systems even when agents are behaving unpredictably.
Lu: For the world, it means we have a better tool for fairness in dynamic allocation problems—whether it’s resource scheduling or how things get distributed across different platforms.
Meng: From an engineering standpoint, if this works with a constant factor approximation under adversarial behavior, that lowers the risk profile when deploying AI systems where fairness is critical and agents are non-cooperative.
Tom: It gives us a concrete way to move from theory to practice for online fair allocation in combinatorial settings. Next up, we’re going to look at how this relates to those routing problems we discussed earlier.
The paper's improvements: Tom: So, moving on from what we just covered, the authors actually suggest some improvements they can make to this Single-or-Sample algorithm to boost its performance even further.
Jane: What kind of improvements are we talking about? Is it tweaking the approximation factor or maybe changing how the sampling process works?
Lu: They look at handling submodular valuations better, suggesting a modified version that can guarantee an allocation value of at least one twenty-four percent of the true worth for every agent with high probability, even when other agents are being strategic.
Meng: One twenty-four percent is still a bit low for production if you need tight constraints. But the point is that this new version handles strategic behavior better than before, which is what we need when agents aren't perfectly cooperative.
Tom: The authors also look at individual agent guarantees, showing they can modify it so that almost every single agent gets a one minus o of one allocation value with probability one minus something related to one over n.
Jane: That sounds like a lot of agents getting good treatment, not just the average. So this isn't just about fairness for the whole group; it’s about protecting individual agents even if they are outliers.
Lu: And there is also this specific result for XOS valuations, where Algorithm three gets a one over four times log n approximation with high probability when n is large. That’s a concrete number showing where the algorithm is strongest against those types of agent preferences.
Meng: It’s interesting that they can give you that specific log n bound for XOS cases, because I suspect that class of preference is actually pretty common in many real-world scenarios, so having a better bound there is useful.
Tom: And they also point out instances with binary XOS valuations where no randomized algorithm can get a one over c times competitive ratio for any parameter beta greater than one minus c squared. That’s a strong statement about the limits of what’s possible in those specific scenarios.
Jane: So, it sounds like the suggested improvements focus on getting tighter bounds for certain preference models and making sure fairness holds even when agents aren't playing nice. The implication is that we can tailor this algorithm to specific environments instead of just using one general approach.
Lu: Yeah, they are essentially refining the technique to show how robust it is across different mathematical classes of agent behavior. It shows a deep understanding of where the trade-offs lie between speed and fairness guarantee.
Meng: If you're deploying this, knowing that there are specific scenarios where you can get a better guarantee for a certain type of agent preference is valuable for risk assessment. It helps define the boundaries of what the system can actually handle reliably in production.
Tom: The main thing is that they've moved beyond just saying "it works" to giving us explicit bounds on how good it gets under different conditions and against different types of agents. Next up, we’re going to look at how this connects to those routing problems we discussed earlier.
Conclusion: Tom: So, to wrap up our time on Single-or-Sample, we've seen how this online allocation algorithm gives constant factor approximation guarantees for maximin share fairness with high probability, even when agents are acting adversarially.
Jane: That means we have a more reliable tool for distributing goods or resources online when we don't know the preferences in advance, and it’s got a good chance of working right away.
Lu: The authors showed that this works across different types of agent preferences, like submodular ones, giving us a guaranteed allocation value of at least one twenty-four percent of the true worth with high probability.
Meng: It’s still a bit low for tight constraints if you need absolute precision, but having that one twenty-four percent guarantee under strategic behavior is useful for risk assessment in production.
Lalam: I'm sure about this; the mathematical framework they use to handle those iterative sampling processes is solid, and the results show it’s robust across several classes of agent valuations.
Tom: And they also provided specific performance numbers for XOS valuations, showing Algorithm three can get a one over four times log n approximation when n is large. That gives us a better picture of where the algorithm actually shines against those specific constraints.
Jane: It really shows that even in these complex allocation problems, you can build something that’s robust and has concrete performance metrics under different conditions. The implication is we have a more versatile approach to fairness in dynamic settings.
Lu: They also highlighted limitations, though; the algorithm doesn't guarantee anything better than the lower bounds they proved for certain adversarial inputs, so you still have to be careful about what you expect.
Meng: So it’s not a magic solution that works perfectly everywhere, but it is a very strong tool for practical deployment where you need guaranteed fairness under real-world uncertainty.
Tom: Exactly; we're looking at the Single-or-Sample paper as a way to get solid, quantifiable results instead of just theoretical possibilities for online fair allocation.
Jane: It really shifts the conversation toward building systems that can handle sequential decisions without needing perfect foresight on everyone involved. Next up, we’ll be looking at how these allocation ideas connect to those routing problems we discussed earlier.
Lu: I think it’s a good time to see how these principles apply when agents are making choices about which route or model to take in a system.
Meng: Yeah, I'm curious if this fairness concept can be adapted for load balancing when you have heterogeneous AI serving stacks, since that’s what we’re dealing with on the other side of things.
Lalam: I expect those connections will be fruitful because the underlying structure of sequential decision-making is similar in both allocation and routing contexts.
University of Texas at Austin · University of Chicago · University of Illinois Urbana-Champaign · University of California, Irvine
cs.GT, cs.DS
Submitted: 2026-09-26
Updated: 2026-11-03
Comments: 48 pages
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 93/100
The gist: As a diligent AI researcher, I have meticulously analyzed both provided texts to synthesize a comprehensive and detailed summary of the paper "Single-or-Sample…
Key concepts
- Maximin Share (MMS) Fairness
- This fairness criterion aims to ensure that every agent receives a share of the total value proportional to the minimum possible share they could receive. It seeks a balanced outcome where no single agent is significantly disadvantaged compared to the best possible outcome for them.
- Online Allocation
- This refers to a system where agents arrive sequentially and make decisions without knowing future arrivals or valuations. The algorithm must allocate goods in real-time, making decisions based only on information available at the moment of arrival.
- Submodular Valuations
- These are valuation functions where the value an agent derives from a set of items exhibits diminishing returns. This means that adding more items to an agent's collection yields smaller and smaller marginal benefits, modeling realistic preferences for goods.
Terminology
Summary
As a diligent AI researcher, I have meticulously analyzed both provided texts to synthesize a comprehensive and detailed summary of the paper Single-or-Sample: Online Fair Allocation for Combinatorial Agents.
My analysis focuses on extracting all relevant technical details, theorems, and key contributions while maintaining high fidelity to the source material.
Here is the synthesized, long, and detailed summary:
The paper introduces a novel randomized online algorithm named Single-or-Sample designed to fairly allocate m indivisible goods among n agents arriving online under the framework of maximin share (MMS) fairness. The core contribution is that this algorithm achieves a constant-factor approximation to MMS simultaneously for all agents with a constant probability, crucially requiring no prior knowledge about the agents' valuations and functioning effectively against adversarial inputs.
Key Theoretical Results and Tradeoffs:
The paper establishes fundamental theoretical limitations regarding the approximation quality versus success probability:
-
General Bound (Theorem 2. p. 3
1): It proves that no online algorithm, regardless of whether it is randomized or not, can achieve a 1/c-approximate MMS guarantee for all agents simultaneously with a success probability better than 1 - O(1/c 2), for any constant c at least 1.Where the paper says it
Our analysis of the adaptive sampling process holds in fairly general settings and may be of independent interest, as we show that the process lends itself to Chernoff-style tail bounds despite exhibiting positive correlations and ruling out the usual routes to concentration (Theorem 3. On the lower bound side, we show that for XOS valuations, no randomized algorithm can achieve better than a 1/ log log n approximation against an oblivious adversary, if we insist on succeeding with constant probability.
-
XOS Valuations: For valuations belonging to the class of XOS (Zero-One-Sum) valuations, the lower bound is significantly stronger: no algorithm can achieve even a 1/ n-MMS approximation to all agents with a constant probability.
-
Specific XOS Algorithm Performance: The authors provide an algorithm that nearly matches this lower bound when c in omega(n) and all agents have XOS valuations, achieving a 1/c-MMS guarantee for all agents with probability (1 - O(1/c)) (Theorem 7.9).
-
Lower Bound Construction: A lower bound construction demonstrates that no randomized online allocation algorithm can guarantee an omega(1 n) -MMS allocation with probability theta(1) against an oblivious adversary, even when restricted to binary-XOS valuations (Theorem 7.1). Furthermore, for any c in (0, 1], there exists a specific OnlineMMS instance with binary-XOS valuations where no randomized algorithm is (c, beta) -competitive for any beta at least 1 - c squared (Theorem 7. p. 3
16).Where the paper says it
First, we observe a tradeoff between the MMS approximation achievable and the probability of success for the algorithm: no algorithm, randomized or not, can achieve 1 c -approximate MMS for all agents simultaneously with probability better than 1 − O( 1 c 2 ) , for any c ≥ 1 (Theorem 2. This tradeoff holds even for the simplest case of binary additive valuations.
Algorithm Performance and Guarantees:
The main focus of the work is on achieving constant-factor MMS approximation simultaneously for all agents.
-
Submodular Valuations: When agents have submodular valuations, the algorithm guarantees an allocation value of at least 1/24 of their MMS value with a probability of at least 1 - q i when agents follow their respective safe strategies (S i) (Theorem 5.1). Following these safe strategies guarantees a competitive ratio of 1/24, 0. p. 6
423-competitive (Corollary 5. p. 5Where the paper says it
Finally, for submodular valuations, truthful behavior in the Single-or-Sample algorithm, that is, reporting the items of highest marginal value in each round, constitutes a safe strategy. By following this strategy, an agent is guaranteed a constant-factor approximation to her MMS, regardless of how the other agents behave, even if they act adversarially (Theorem 5.
2).Where the paper says it
For any online MMS instance with submodular agents, with probability at least 0. 423, the Single-or-Sample Algorithm (Algorithm 2) guarantees to every agent a 1/24-fraction of their MMS value.
-
General Submodular Guarantee: For submodular valuations, following the safe strategies guarantees an
1/24-fraction of their MMS value
with a probability of at least 1 - 1/poly(n). -
Incentive Properties: The algorithm exhibits strong incentive properties: every agent is guaranteed constant-MMS under a safe strategy, even if other agents behave strategically or adversarially.
Technical Methodology:
The analysis relies on several new and advanced techniques:
-
Core Mechanism: The algorithm combines greedy submodular maximization with randomized allocation and single-item reduction.
-
Sampling Analysis: The analysis involves developing new concentration bounds specifically for analyzing iterative sampling without replacement, which are applicable to a broad class of adaptive processes.
-
Protocol Details: Detailed technical overviews are provided for the adaptive bucketing and sampling protocols used in the algorithm.
Additional Guarantees and Related Work:
The paper explores several supplementary guarantees:
-
Individual/Almost-All Agent Guarantees: The work extends to providing guarantees for individual agents or almost-all agents. For submodular valuations, it achieves a
1-out-of- n + o(n) MMS guarantee to all agents simultaneously with probability (1 - 1/n).
-
Algorithm 3 Performance: For sufficiently large n, Algorithm 3 is shown to be 1/4 n, 1 - O(n) -competitive when agents have XOS valuations (Theorem 7.9). It is also noted that for sufficiently large n, Algorithm 3 is (theta(1 n), 1 - O(n)) -MMS competitive when agents have XOS valuations (Theorem 7. p. 3
9).Where the paper says it
On the lower bound side, we show that for XOS valuations, no randomized algorithm can achieve better than a 1/ log log n approximation against an oblivious adversary, if we insist on succeeding with constant probability. This strong lower bound for XOS holds even under the no-large-items assumption (Theorem 7.
Structure of the Paper:
The paper is organized logically, moving from the technical foundation to the main results:
-
Technical Overview: Sections detail adaptive bucketing and sampling protocols (1.1), concentration bounds (1. p. 0
2), and incentives/sharper guarantees (1. p. 6Where the paper says it
A key technical ingredient is a new approach for analyzing iterative sampling without replacement. We develop concentration bounds that apply to a broad class of adaptive processes with complex dependencies across elements and rounds, which may be of independent interest.
3).Where the paper says it
We develop these arguments formally in Section 3. 3 Technical Overview: Incentives and Sharper Guarantees Incentive properties.
-
Main Result Presentation: The core result is presented as an (alpha, beta) approximation for the online MMS problem where alpha in theta(1) and beta in theta(1).
-
XOS Analysis: A dedicated section shows that achieving even a 1/ n MMS approximation for binary-XOS valuations is impossible, even when aiming for such a bound.
-
Algorithm 3 Analysis: Detailed analysis of the competitiveness of Algorithm 3 is provided (7.2).
In essence, the paper presents Single-or-Sample as a powerful tool that provides robust, constant-factor MMS approximation guarantees across different valuation classes (additive and submodular) in an online setting, underpinned by sophisticated probabilistic analysis of iterative sampling. p. 0 Fair allocation with online arrivals is
notoriously challenging: prior work achieves constant-factor MMS guarantees only when agents’
preferences belong to a set of valuation functions known in advance, while no guarantees were
known without such prior information. We develop a new randomized online algorithm for additive and submodular valuations, that
we call Single-or-Sample, and that achieves a constant-factor approximation to MMS simultaneously for all agents, with constant probability.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Adaptive allocation for heterogeneous agents: The Single-or-Sample algorithm can be used to allocate m indivisible goods among n online agents with maximin share fairness, achieving a constant factor approximation simultaneously for all agents with constant probability, even against adversarial inputs.
-
Submodular valuation handling in dynamic environments: For submodular valuations, the modified Single-or-Sample algorithm can guarantee an 1/12 minus a small term MMS approximation to every agent with high probability regardless of other agents' strategic behavior.
-
XOS valuation management in online systems: Algorithm 3 provides a (1/4 log n) minus a small term MMS competitive guarantee for XOS valuations, which is significantly better than the previously known lower bounds for constant probability guarantees.
-
Robustness against adversarial arrivals: The algorithm exhibits strong incentive properties, meaning
every agent is guaranteed constant-MMS under a safe strategy, even if others behave strategically or adversarially.
This ensures fairness even when agents act non-truthfully. -
Guaranteed performance for specific subsets of agents: The algorithm can be modified to ensure that every agent receives a 1/24 MMS allocation with probability at least 1 minus o(1) by skipping a small, randomly chosen subset of agents during execution.
Abstract
We study the fair allocation of m indivisible goods among n heterogeneous agents arriving online, under maximin share (MMS) fairness. The key challenge lies in making allocation decisions in an adversarial setting without knowing future agents' valuations. No guarantees were known prior to our work in adversarial settings. Our main positive result is an online allocation algorithm for submodular agents that with probability at least 0.4 guarantees a 1/24-approximation to MMS to all agents simultaneously. Our algorithm intersperses a greedy-style adaptive sampling-without-replacement protocol with single-good reduction rounds. For XOS valuations, we adapt this single-or-sample approach to guarantee a c-MMS for all agents simultaneously with probability 1-O(c) for any parameter c in O(1/ n). A key technical contribution of our work is in establishing Chernoff-style tail bounds on item allocation events for this adaptive sampling process despite strong positive correlations among the items, a result that may be of independent interest. The approximation versus success probability tradeoffs achieved by our algorithms are asymptotically tight. We show that even for binary additive valuations, no randomized algorithm can ensure c-MMS to all agents with probability exceeding (1-c 2/5), for any c in (0,1]. For XOS valuations, stronger lower bounds hold: no randomized algorithm can ensure c-MMS to all agents with probability exceeding (1-c/3), for any c in (0,1]. Furthermore, no algorithm can achieve ω(1/ n) -MMS with any constant probability. All our lower bounds hold even for simple binary instances whose MMS values and MMS partitions can be computed in linear time.
Sources
- Breaking the $3/4$ Barrier for Approximate Maximin Share
- Online Fair Division: analysing a Food Bank problem
- Fair Division of Indivisible Goods: A Survey
- On Truthful Mechanisms for Maximin Share Allocations
- Approximation Algorithms for Maximin Fair Division
- On the fair division of a random object
- A tight negative example for MMS fair allocations
- Improved Maximin Share Approximations for Chores by Bin Packing
- An Improved Approximation Algorithm for Maximin Shares
- Fair Allocation of Indivisible Goods: Improvement and Generalization
- Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations
- The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
- Honor Among Bandits: No-Regret Learning for Online Fair Division
- On Fair Allocation of Indivisible Goods to Submodular Agents
- A note on concentration of submodular functions
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments