Making Serial Dictatorships Fair

This paper demonstrates that to minimize justified envy in serial dictatorship mechanisms, agents should be ordered according to a Kemeny ranking of their priorities when preferences are identical and uniformly distributed, or a weighted Kemeny ranking when these assumptions are relaxed.

The Gist

Imagine you are the principal of a school, and you have a bunch of students who all want to get into specific classes. You also have a list of rules (priorities) for each class: maybe some students live nearby, others have siblings already there, or some have special needs.

You need to assign students to classes. You want a system that is:

1. Fair: No student should be able to say, "I got a worse class than him, but I deserved it more because of my rules." (This is called "justified envy").
2. Honest: Students shouldn't be able to lie about which class they like to get a better spot.
3. Efficient: No one should be left with a bad option if a better one was available.

The most famous tool for this is called Serial Dictatorship. It works like a game of musical chairs, but with a twist:

• You line up the students in a specific order.
• The first student in line picks their favorite available class.
• The second student picks their favorite remaining class.
• And so on, until everyone is seated.

The Problem:
The problem is deciding who gets to go first.

• If you pick the order randomly, the student who lives right next to the school (and has the highest priority) might end up last in line. They might get stuck with the worst class, while a student who lives far away gets the best one. The local student has "justified envy."
• If you just let the highest-priority student go first, you might ignore the fact that they actually hate that specific class, or you might create a bottleneck where other high-priority students get nothing.

The Paper's Big Idea:
This paper asks: "How do we arrange the line so that the 'unfairness' (justified envy) is as low as possible, on average?"

The author, Adam Hamdan, discovers a surprising connection to a concept from voting theory called the Kemeny Ranking.

The "Group Vote" Analogy

Imagine that every single class (object) has its own "voting booth" where it ranks the students.

• Class A thinks: "Student 1 is best, Student 2 is second, Student 3 is last."
• Class B thinks: "Student 2 is best, Student 3 is second, Student 1 is last."
• Class C thinks: "Student 3 is best, Student 1 is second, Student 2 is last."

Now, you need to create one single line (the serial order) to run the game. How do you combine these three different opinions into one line?

If you just pick a random line, you might anger Class A, Class B, and Class C.
The paper says: The fairest line is the one that disagrees the least with all the classes' individual lists.

This is exactly what the Kemeny Ranking does. It's like a "consensus builder." It looks at all the different priority lists and finds the single line that minimizes the total number of "arguments" or "disagreements" with the original lists.

The Three Scenarios (The "What Ifs")

The paper explores what happens when the real world gets messy.

1. The Perfect World (Identical Preferences)
Imagine every student loves the exact same classes in the exact same order (e.g., everyone wants the Art room first, then Gym, then Math).

• The Solution: Just use the Kemeny Ranking. You take all the classes' priority lists, find the "average" opinion, and put that order in line. This is mathematically proven to be the fairest way to run the game.

2. The "Popular Class" Problem (Non-Uniform Preferences)
What if everyone loves the Art room way more than the Gym? The Art room will be picked very early in the line.

• The Solution: You need a Weighted Kemeny Ranking. You give the Art room's priority list a "heavy weight" (like a louder voice) because it matters more. If you mess up the order for the Art room, it causes more chaos than messing up the Gym. The algorithm adjusts the line to respect the "loudest" priorities more.

3. The "Big School" Problem (Multiple Seats)
What if the Art room has 50 seats, but the Gym only has 5?

• The Solution: The math gets a bit more complex, but the idea is the same. If a student picks the Art room, they don't "use it up" immediately. The algorithm calculates the probability that a seat will run out. It creates a Weighted Kemeny Ranking that accounts for how likely it is that a specific class will fill up at a specific time in the line.

Why This Matters

In the real world, we often use simple, random lines (like drawing names out of a hat) to assign things like dorm rooms or school seats. This paper shows that we can do much better without making the system complicated or letting people cheat.

By using a "consensus builder" (the Kemeny Ranking) to decide the order, we can keep the system simple and honest, but significantly reduce the number of angry students who feel they were treated unfairly.

In short: Don't just guess who goes first. Look at all the rules, find the "middle ground" that respects everyone's priorities the most, and put that person first. It's like finding the perfect playlist that satisfies the most people in the car.

Technical Summary

Here is a detailed technical summary of the paper "Making Serial Dictatorships Fair" by Adam Hamdan.

1. Problem Statement

The paper addresses the fundamental trade-off between efficiency and fairness in priority-based matching markets (e.g., school choice, public housing, organ allocation).

• Context: In these markets, agents (students) must be matched to objects (schools) based on their preferences and the objects' priority rankings over agents.
• The Conflict: No mechanism can simultaneously satisfy Pareto efficiency, strategyproofness, and the elimination of justified envy (where an agent prefers another's assignment and has higher priority for that object).
• The Focus: The paper focuses on Serial Dictatorship (SD), a mechanism known for being strategyproof and Pareto efficient but generally failing to eliminate justified envy because the order of agents is arbitrary.
• The Research Question: Given that the planner cannot condition the serial order on reported preferences (to maintain strategyproofness), how should the planner determine the serial order $\rho$ based only on the objects' priority rankings to minimize the expected number of justified envy cases?

2. Methodology

The author employs a probabilistic approach combined with rank aggregation theory from social choice.

• Model Setup:

  • A set of agents $I$ and objects $S$.
  • Strict priority orderings $\succ_s$ for each object $s$.
  • A distribution over agent preference profiles $P$.
  • The planner commits to a serial order $\rho$ before preferences are realized.
  • Objective: Minimize $E_P[N(\mu^{SD}_\rho(P, \succ))]$, where $N$ is the count of justified envy cases.

• Analytical Framework:

  • The problem is decomposed into calculating the probability that a specific pair of agents $(t, t')$ with $t < t'$ (where $t$ is earlier in the sequence) generates a justified envy case.
  • A justified envy case occurs if agent $\rho(t')$ prefers the object assigned to $\rho(t)$ and $\rho(t')$ has higher priority for that object than $\rho(t)$.
  • The author maps this minimization problem to the Kemeny ranking problem, which seeks a consensus ranking that minimizes the sum of pairwise disagreements with a set of input rankings.

• Assumptions Tested:
  The paper establishes a baseline and then relaxes assumptions one by one:

  1. Baseline: Identical preferences (across agents), uniformly distributed, and unit capacities.
  2. Relaxation 1: Identical preferences but non-uniform distribution.
  3. Relaxation 2: Independent (non-identical) preferences.
  4. Relaxation 3: Non-unit capacities (many-to-one matching).

3. Key Contributions

1. Novel Connection: The paper establishes the first formal link between minimizing justified envy in matching mechanisms and the Kemeny rule (a classical rank aggregation method).
2. Optimality of Kemeny Ranking: It proves that under specific conditions, the optimal serial order is exactly the Kemeny ranking of the objects' priorities.
3. Generalization to Weighted Kemeny: It demonstrates that when standard assumptions are relaxed, the solution remains a Weighted Kemeny Ranking, where the weights reflect the probability of a priority violation resulting in justified envy.
4. Strategyproofness Preservation: The proposed method improves fairness without sacrificing the strategyproofness of SD, as the order is determined by exogenous priorities rather than reported preferences.

4. Key Results

Theorem 1: The Baseline Case

• Conditions: Preferences are identical across all agents, drawn uniformly at random, and objects have unit capacities.
• Result: The serial order that minimizes expected justified envy is the Kemeny ranking of the agents' priorities.
• Intuition: With identical preferences, envy is guaranteed to occur between any two agents if the earlier agent gets a better object. The planner must therefore minimize the "justified" component. Since every object is equally likely to be the source of envy, the planner should treat every object's priority ranking equally. The Kemeny rule achieves this by minimizing the total number of pairwise disagreements across all priority rankings.

Proposition 1: Non-Uniform Preferences

• Condition: Preferences are identical but follow an arbitrary distribution (some objects are more desirable than others).
• Result: The optimal order is a Weighted Kemeny Ranking.
• Mechanism: Disagreements involving object $s$ at position $t$ in the serial order are weighted by $p(s, t)$, the probability that object $s$ appears at position $t$ in the preference ranking. Objects likely to be chosen early (and thus generate more subsequent envy) receive higher weight in the aggregation.

Proposition 2: Independent Preferences

• Condition: Agents' preferences are independently and uniformly distributed.
• Result: The optimal order is a Weighted Kemeny Ranking with weights $p(t', t)$.
• Mechanism: The weight depends on the distance between agents in the serial order ($t' - t$). Disagreements are weighted more heavily when the gap between agents is larger because the probability of the later agent being envious of the earlier agent increases with the number of intervening choices.

Proposition 3: Non-Unit Capacities

• Condition: Objects have capacities $q_s > 1$ (e.g., schools with multiple seats).
• Result: The optimal order is a Weighted Kemeny Ranking with weights $p(s, t', t, q)$.
• Mechanism: The weight accounts for two factors:
  1. The likelihood that agent $\rho(t)$ is matched to object $s$.
  2. The likelihood that object $s$ reaches full capacity between steps $t$ and $t'$.
  • If an object has multiple seats, the second agent assigned to it will not feel envy toward the first. The weights adjust to reflect that priority violations only cause envy if the object is "full" by the time the lower-priority agent arrives.

5. Significance and Implications

• Practical Application: The results provide a concrete, implementable guide for planners (e.g., school districts) to design fairer SD mechanisms. Instead of using a random or arbitrary order, they can compute the Kemeny (or weighted Kemeny) ranking of student priorities to significantly reduce justified envy.
• Theoretical Bridge: The paper bridges matching theory and social choice theory. It shows that tools developed for aggregating voter preferences (Kemeny's rule) are directly applicable to aggregating priority rankings in allocation problems.
• Fairness vs. Strategy: It resolves a critical tension in mechanism design. By optimizing the serial order based on priorities (which are law-determined and non-manipulable) rather than preferences, the mechanism retains strategyproofness while moving closer to the ideal of fairness (eliminating justified envy).
• Relation to RSD: The paper clarifies that Random Serial Dictatorship (RSD) is optimal only in "house allocation" (no priorities). In priority-based settings, RSD is suboptimal for fairness. The proposed optimal SD is a generalization of RSD that incorporates priority information.

Conclusion

Adam Hamdan's paper demonstrates that the "fairness" of Serial Dictatorship can be significantly enhanced by optimally ordering agents. By framing the problem as a rank aggregation task, the author proves that the Kemeny ranking (and its weighted generalizations) is the mathematically optimal solution for minimizing justified envy, offering a robust, strategyproof, and efficient mechanism for real-world priority-based matching markets.