📈 economics

The Domain of RSD Characterization by Efficiency, Symmetry, and Strategy-Proofness

This paper resolves the long-standing open question regarding the axiomatic characterization of the Random Serial Dictatorship mechanism by precisely identifying all market sizes $(n,m)$ for which the combination of Ex-Post Efficiency, Equal Treatment of Equals, and Strategy-Proofness uniquely defines the mechanism, while constructing alternative mechanisms for cases where it does not.

Original authors: Maor Ben Zaquen, Ron Holzman

Published 2026-02-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maor Ben Zaquen, Ron Holzman

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 gift exchange. You have a group of people (agents) and a pile of unique, indivisible items (houses, schools, dorm rooms). You can't use money to trade them; you can only ask everyone to write down their favorite items in a list. Your goal is to hand out these items in a way that feels fair, efficient (nobody is left with something terrible when a better option was available), and honest (nobody can cheat the system by lying about what they like).

The paper by Maor Ben Zaquen and Ron Holzman investigates a specific method for doing this called Random Serial Dictatorship (RSD).

The RSD Game: A Musical Chairs Analogy

Think of RSD as a game of musical chairs, but with a twist.

The Draw: You randomly draw an order for the people (like drawing names from a hat).
The Pick: The first person picks their absolute favorite item. The second person picks their favorite item from what's left. The third person picks from the remaining items, and so on.
The Randomness: Since the order is random, everyone gets a "lottery ticket" for every item. Over many rounds, this creates a fair probability distribution.

This method is famous because it seems to hit the "Holy Trinity" of good allocation rules:

Efficiency: No one is wasting a good item.
Fairness: If two people have the exact same list of favorites, they get the exact same chances.
Honesty: You can't trick the system by lying about your preferences; telling the truth is always your best bet.

The Big Question: Is RSD the Only Game in Town?

For a long time, mathematicians wondered: Is RSD the only way to satisfy these three rules?

The Small World (2 or 3 people): Yes. If you have a small group (like 2 or 3 people) and any number of items, RSD is the only solution that works. It's the unique champion.
The Balanced 4x4 Case: Even with 4 people and 4 items, RSD is still the unique champion. This was a hard puzzle that took computers to solve, but the answer was "Yes."
The Big World (5 or more): Here is where the plot twists. If you have 5 or more people and 5 or more items, RSD is NOT the only solution. The authors prove that you can build other "games" (mechanisms) that are just as fair, efficient, and honest as RSD, but they give people slightly different odds.

The "Goldilocks" Zone

The paper maps out exactly where the magic happens. They created a "map" (Table 1 in the paper) showing:

Green Zones (Unique): If you have 2 or 3 people, RSD is the only answer. If you have 4 people and 4 items, RSD is the only answer.
Red Zones (Multiple Solutions): If you have 5+ people and 5+ items, or if you have 4 people but more than 4 items, there are infinite other ways to run the game that satisfy all the rules.

How They Found the "Cheat Codes" (Alternative Mechanisms)

In the "Red Zones," the authors didn't just say "other solutions exist"; they actually built them.

Imagine RSD as a perfectly balanced scale. The authors found a way to add a tiny, invisible weight to one side of the scale for specific situations.

They took a standard RSD game.
They found a very specific scenario (a specific set of preference lists).
They tweaked the rules just a tiny bit to shift a tiny amount of probability from one person to another.
Crucially: They proved that this tiny tweak didn't break the rules. It was still efficient, still fair to identical people, and still honest.
Then, to make it fair for everyone (since the tweak favored specific people), they "symmetrized" it. This means they ran the tweaked game for every possible permutation of people and averaged the results. The result is a new, valid mechanism that is different from RSD but satisfies all the same rules.

The "Super-Strong" Rules

You might ask: "If RSD isn't unique, can we just add more rules to force it to be unique again?"

The authors tested this. They added extra "super-rules" like:

Bounded Invariance: If you change your mind about items you don't care about, it shouldn't change your chances for the ones you do care about.
Non-Bossiness: You can't change your own mind to help someone else without changing your own outcome.
Cross Monotonicity: If I move an item up my list, it shouldn't accidentally help someone else get that item.

The Verdict: Even with these super-strong rules, RSD is still not unique in large markets (5+ people/items). The system is too flexible; there are too many ways to wiggle the probabilities without breaking the rules.

Summary

Think of the allocation problem as a puzzle.

Small Puzzles (2-3 people): There is only one way to solve it. RSD is the unique solution.
Medium Puzzles (4 people, 4 items): Still only one way.
Large Puzzles (5+ people): There are many ways to solve it. RSD is just one of many valid solutions.

The paper completes the map of this puzzle, telling us exactly when RSD is the sole ruler and when it has to share the throne with other, equally valid mechanisms. It shows that while RSD is a great tool, it isn't the only tool that fits the job description once the group gets big enough.

Technical Summary: The Domain of RSD Characterization by Efficiency, Symmetry, and Strategy-Proofness

Problem Statement
The paper addresses the axiomatic characterization of the Random Serial Dictatorship (RSD) mechanism in the context of allocating indivisible objects to agents with strict preferences. RSD operates by drawing a random order of agents, who then sequentially select their most preferred available object. While RSD is widely used in applications like school choice and housing assignment due to its satisfaction of three core axioms—Ex-Post Efficiency (ExPE), Equal Treatment of Equals (ETE), and Strategy-Proofness (SP)—it was an open question whether these three axioms uniquely characterize RSD for all market sizes $(n, m)$ .

Previous literature established that for the balanced case of $n=m=3$ , these axioms uniquely identify RSD (Bogomolnaia and Moulin [8]). However, for larger markets, the question remained unresolved. Recent work by Basteck and Ehlers [5] demonstrated that for all markets with $n, m \ge 5$ , the axioms are insufficient to uniquely characterize RSD, as alternative mechanisms exist. The central problem of this work is to provide a complete classification of the pairs $(n, m)$ for which the axioms uniquely determine RSD and to identify the specific domains where non-uniqueness occurs.

Methodology
The authors employ a rigorous axiomatic approach, utilizing both positive characterization proofs and constructive counterexamples.

Axiomatic Weakening for Uniqueness Proofs: In proving uniqueness for specific market sizes, the authors demonstrate that the full strength of ExPE and SP is not required. Instead, they rely on:
- Support Efficiency: An agent receives an object with positive probability only if that object is assigned to them in some Pareto efficient deterministic assignment.
- Full Assignment Property: If an agent (or object) is matched in every Serial Dictatorship (SD) outcome, they must be matched with probability 1.
- Upper and Lower Invariance: These are local conditions equivalent to SP regarding adjacent swaps in preferences, ensuring probabilities of other objects remain unchanged when an agent swaps two adjacent items in their ranking.
Local Analysis and Induction: For cases where uniqueness holds, the proofs utilize a "local analysis" of the axioms. By examining adjacent swaps in agents' rankings, the authors propagate constraints across different preference profiles. A key lemma (Lemma 2.4) establishes that if agents exhibit "near-unanimity" (all but at most one agent agree on the binary preference of every pair of objects), the assignment matrix is uniquely determined. This serves as a base for inductive arguments on the "disagreement parameter" of a profile.
Constructive Counterexamples: For domains where uniqueness fails, the authors construct explicit alternative mechanisms. These constructions generally follow a strategy inspired by Basteck and Ehlers [5]:
- Start with a base mechanism (often a specific SD ordering or RSD itself).
- Identify a restricted family of preference profiles where specific adjustments can be made without violating ExPE or SP.
- Perform a small probability shift (transfer of $\epsilon$ mass) between efficient assignments for specific agents.
- Symmetrize the adjusted mechanism over all agent (and sometimes house) renamings to ensure ETE (and often Anonymity and Neutrality) is preserved.
Parameterization for $m=2$ : For the specific case of two objects, the authors provide a complete parameterization of all mechanisms satisfying the axioms, showing they correspond to a specific class of functions mapping subsets of agents to probabilities.

Key Contributions and Results
The paper provides a complete classification of the pairs $(n, m)$ regarding the uniqueness of RSD:

Uniqueness Domains: The axioms ExPE, ETE, and SP uniquely characterize RSD if and only if:
- $n \le 3$ and $m \ge 2$ (including the balanced case $n=m=3$ ).
- $n = 4$ and $m = 4$ (the balanced case with four agents).
- $n = 2$ and $m > 2$ .
- Notably, for $n=4$ , uniqueness holds only when $m=4$ . If $n=4$ and $m \ge 5$ , uniqueness fails.
Non-Uniqueness Domains: For all other pairs $(n, m)$ with $n, m \ge 2$ , the axioms do not uniquely characterize RSD. Specifically:
- For $n > m \ge 3$ , alternative mechanisms exist.
- For $n = 4, m \ge 5$ , alternative mechanisms exist.
- For $n, m \ge 5$ , the result confirms the negative finding of Basteck and Ehlers [5].
Parameterization of $m=2$ : The paper fully characterizes the space of mechanisms for two objects, showing that for $n \ge 4$ , there is a continuum of mechanisms satisfying the axioms, whereas for $n=2, 3$ , the mechanism is unique.
Strengthened Axioms: The authors investigate whether adding stronger axioms can restore uniqueness in the non-unique domains. They test:
- Bounded Invariance (BI): They show that adding BI (along with Anonymity and Neutrality) does not restore uniqueness for $n \ge m-1 \ge 5$ .
- Non-Bossiness (NB) and Cross Monotonicity (CM): Even adding these axioms to the system (Anonymity, Neutrality, ExPE, SP, BI) fails to restore uniqueness for sufficiently large markets ( $n \ge m-1 \ge 7$ ).
Welfare Dominance: In the non-uniqueness domains, the constructed alternative mechanisms often dominate RSD. That is, they weakly improve every agent's allocation relative to RSD and strictly improve at least one agent's allocation at certain profiles.

Significance
The paper completes the picture of RSD's axiomatic characterization, resolving a long-standing open question regarding the boundary between uniqueness and non-uniqueness. It clarifies why the case $n=m=4$ was particularly difficult to resolve analytically (it is the unique balanced case where uniqueness holds, unlike $n=3$ or $n \ge 5$ ). Furthermore, by demonstrating that strengthening the axiom system with standard properties like Bounded Invariance, Non-Bossiness, and Cross Monotonicity fails to restore uniqueness in large markets, the paper highlights fundamental limitations in characterizing RSD solely through these normative criteria. The work also establishes that in domains where RSD is not unique, it is not necessarily welfare-optimal, as it can be dominated by other mechanisms satisfying the same axioms.