📈 economics

Random Matching with Minimums

This paper introduces the Minimums Probabilistic Serial (MPS) mechanism, a novel random assignment algorithm for objects with minimum and maximum constraints that guarantees Pareto efficiency, envy-freeness, and weak strategyproofness.

Original authors: Will Sandholtz, Andrew Tai

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Will Sandholtz, Andrew Tai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the organizer of a massive, chaotic school fair. You have a group of students (agents) and a bunch of different booths or activities (objects). Every student wants to try exactly one booth.

Usually, the fairest way to handle this is a lottery: everyone gets a ticket, and the tickets are drawn randomly. But there's a catch. Some booths are popular clubs (like a basketball team) that must have at least 5 students to be allowed to open, but they can't hold more than 20. Other booths are limited workshops that can only take 5 people total.

If you just use a simple random lottery, you might end up with a disaster: the basketball team might only get 3 students and have to cancel, or the workshop might get 25 people and have to turn people away. You need a system that guarantees the minimums are met while still being fair and efficient.

This paper introduces a new system called Minimums Probabilistic Serial (MPS) to solve exactly this problem.

The Old Way: The "Serial Dictatorship" Lottery

Imagine a game where students line up in a random order. The first person picks their favorite booth. The second person picks their favorite remaining booth, and so on.

The Problem: If the basketball team needs 5 people, but the first 4 people in line all hate basketball and pick other things, the team might never get enough people. Or, if the line is unlucky, the basketball team might get 6 people, but the "Art Club" (which needs 5) might only get 2. The result is often inefficient and unfair.

The New Way: The "Eating" Mechanism

The authors propose a mechanism inspired by a famous idea called "Probabilistic Serial." Imagine this:

Instead of picking one by one, imagine time is a fluid.

Every student starts at the same time, holding a cup.
They all "eat" (consume) their favorite booth at the same speed.
As they eat, the booth gets "fuller."
The Twist: A booth can't be eaten past its maximum capacity (it closes when full). But, a booth also has a minimum requirement. If a booth hasn't reached its minimum number of "eaters" by the time the game ends, the whole system fails.

The MPS mechanism is a smart set of rules for this eating game. It tells the students:

"Keep eating your favorite booth."
"If a booth hits its maximum limit, stop eating it and move to your next favorite."
"If a booth is about to run out of time but hasn't met its minimum requirement, we have to force everyone to stop eating other things and help fill that booth to meet the minimum."

Why is this special?

The paper claims this new system has three superpowers:

It's Pareto Efficient (No Waste): You can't rearrange the results to make one student happier without making someone else worse off. The system finds the "best possible" lottery given the strict rules.
It's Envy-Free: No student will look at another student's result and say, "I wish I had what they got." Everyone feels their chance is fair compared to everyone else's.
It's Hard to Cheat (Strategyproof): If a student lies about their preferences (e.g., pretending they love the basketball team when they actually hate it) to try and game the system, they won't end up with a better result. In fact, they might end up with a worse one.

The "Polytope" Puzzle (The Math Part, Simplified)

The authors had to solve a tricky math problem. Usually, to figure out all the possible ways to assign students to booths, you have to list every single possible combination.

The Analogy: Imagine trying to list every possible way to arrange 100 people into 100 seats. The number of combinations is so huge (a "factorial" number) that even the fastest supercomputers would take longer than the age of the universe to list them all.
The Solution: The authors didn't list the combinations. Instead, they drew a shape (a "polytope") using simple lines and rules (inequalities). They proved that if you stay inside this shape, you are guaranteed to have a valid solution. This allowed them to build a fast computer algorithm that doesn't need to check every single possibility.

The Bottom Line

This paper gives us a new, fair, and efficient way to assign things when there are strict "minimums" and "maximums." Whether it's assigning students to mandatory school clubs, workers to projects that need a minimum team size, or even dividing territory, this mechanism ensures that:

The rules are followed (minimums are met).
No one is left out unfairly.
No one can game the system to get a better deal.

It turns a chaotic, potentially broken lottery into a smooth, fair, and mathematically perfect process.

Technical Summary: Random Matching with Minimums

Problem Statement
This paper addresses stochastic object assignment problems where objects are subject to both maximum capacity constraints ( $c_j$ ) and minimum requirement constraints ( $m_j$ ). While standard random assignment mechanisms (such as Random Serial Dictatorship or the Probabilistic Serial mechanism) handle capacity constraints, they fail to guarantee implementable allocations when minimum quotas are present. The core challenge is to construct a random allocation mechanism that:

Produces an implementable random allocation (one that can be decomposed into a lottery over feasible deterministic allocations satisfying all $m_j$ and $c_j$ ).
Achieves Stochastic Dominance (SD) efficiency (Pareto efficiency under first-order stochastic dominance).
Maintains fairness properties (envy-freeness and anonymity).
Preserves weak strategyproofness in the unit demand setting.

Existing literature faces a trade-off: mechanisms like the Generalized Probabilistic Serial (GPS) of Budish et al. (2013) handle bihierarchical constraints (maximums only) but cannot represent minimums. Conversely, the Generalized Constrained Probabilistic Serial (GCPS) of Balbuzanov (2022) handles arbitrary constraints but requires enumerating all allowable deterministic allocations to characterize the feasible polytope. This enumeration is factorial in complexity, making GCPS computationally intractable for even modest problem sizes.

Methodology
The authors propose the Minimums Probabilistic Serial (MPS) mechanism. The methodology proceeds in two main stages:

Characterization of the Feasible Polytope:
Instead of enumerating the set of deterministic allocations $D$ (which is computationally prohibitive), the authors directly characterize the set of implementable random allocations, denoted $\Delta_D$ , using a system of positive linear inequalities.
- For the unit demand case ( $d=1$ $d = 1$ ), they derive a specific system of inequalities (Proposition 3) that defines the lower contour set $lcs(\Delta_D)$ $l cs (Δ_{D})$ . This system includes:
  - Unit demand constraints ( $\sum_j \mu_{ij} \leq 1$ ).
  - Capacity constraints ( $\mu_j \leq c_j$ ).
  - A novel set of constraints (Min-III) ensuring that for any subset of objects $S$ with minimums, the total probability assigned to objects outside $S$ does not exceed the remaining agents' capacity to satisfy the minimums of $S$ .
- This characterization is further simplified into a compact form (Proposition 4) involving $\sum_j \max\{m_j, \mu_j\} \leq N$ , which facilitates an algorithmic implementation.
- For general demand ( $d > 1$ ), they provide a more complex system of inequalities (Proposition 5) derived using Hoffman's existence theorem for circulations in networks.
Mechanism Design and Algorithm:
- Continuous-Time Definition: The MPS mechanism is defined as a continuous-time "eating" process (analogous to Probabilistic Serial) where agents consume their most preferred available object at a uniform speed. An object is "available" only if consuming it does not violate the derived linear inequalities.
- Discrete-Time Algorithm: Leveraging the specific structure of the unit demand inequalities, the authors construct Algorithm 1, a polynomial-time discrete algorithm. The algorithm proceeds in steps where agents consume objects until a constraint binds. Crucially, the algorithm identifies a critical time $\tau$ where the global minimum constraints become binding. At $\tau$ , any object that has met its minimum requirement is closed to further consumption, ensuring that remaining agents are forced to satisfy the minimums of other objects.

Key Results
The paper establishes the following theoretical properties for the MPS mechanism:

SD Efficiency: The MPS mechanism produces allocations that are Stochastically Dominance efficient. No other implementable random allocation is preferred by all agents via first-order stochastic dominance.
Fairness: The mechanism is anonymous (invariant to agent re-indexing) and envy-free (no agent strictly prefers another agent's lottery).
Strategyproofness: In the unit demand case, MPS is weakly strategyproof. Agents cannot achieve a stochastically dominant allocation by misreporting their preferences. The proof relies on showing that manipulating preferences to alter the critical time $\tau$ $τ$ or the closing times of objects never yields a net benefit to the misreporter.
- Note: For general demand ( $d > 1$ ), the mechanism remains SD efficient, anonymous, and envy-free, but weak strategyproofness is lost, consistent with findings in Kojima (2009b).
Implementation: The resulting random allocation is guaranteed to be implementable. Since the constraints are bihierarchical (in the sense of Budish et al., 2013), the Birkhoff-von Neumann theorem (or its generalization in BCKM13) ensures the random allocation can be decomposed into a lottery over feasible deterministic allocations.

Significance and Claims
The paper claims to bridge the gap between theoretical random assignment mechanisms and practical applications involving minimum quotas (e.g., school clubs, project teams, jury selection).

Computational Feasibility: The primary contribution is providing the first feasible algorithm for random matching with minimums. By avoiding the factorial complexity of enumerating deterministic allocations and the exponential complexity of the facet enumeration problem (FEP) required by Balbuzanov (2022), the authors provide a polynomial-time algorithm for the unit demand case.
Preservation of Incentives: Unlike the more general GCPS mechanism, which loses weak strategyproofness, the MPS mechanism preserves this property in the unit demand setting.
Theoretical Extension: The work generalizes the Probabilistic Serial mechanism to settings with lower bounds, demonstrating that efficiency and fairness can be maintained even when the constraint structure prevents the use of standard bihierarchical maximum-only frameworks.

The authors explicitly state that while they provide a polynomial-time algorithm for unit demand, the algorithmic description for general demand ( $d > 1$ ) remains an open question for future research due to the increased complexity of the inequality system.