Justifiable Priority Violations

This paper proposes a question-free, endogenous framework for justifying priority violations in school choice that outperforms existing consent-based mechanisms by enabling Pareto improvements through a polynomial-time algorithm, while also demonstrating the theoretical and practical limitations of both approaches in achieving full efficiency.

The Gist

Imagine a high-stakes game of musical chairs, but instead of music, the chairs are school seats, and the rules are strict. Some students have "VIP passes" (priority) based on where they live or their siblings' attendance. The current standard rule for this game is called Deferred Acceptance (DA). It's fair and stable—nobody can claim, "I should have gotten that seat because I have a VIP pass and the person sitting there doesn't." But, there's a catch: DA often leaves the game inefficient. It might leave a student sitting in a chair they hate, while another student who loves that chair is sitting in a worse one, simply because the rules prevented them from swapping.

The authors of this paper, Josué Ortega and R. Pablo Arribillaga, ask a big question: How can we make the game more efficient (so everyone gets a better seat) without breaking the rules of fairness?

To do this, we sometimes have to break the "VIP pass" rule. But which rules can we break without getting yelled at?

The Problem with Asking for Permission

Currently, the leading solution is to ask students in advance: "Hey, if giving up your VIP pass helps someone else get a better seat, and you don't lose anything, will you agree to it?" This is called Ex-Ante Consent.

The authors argue this is like asking everyone in a room to raise their hand before a fire drill. It's messy, and often, even if everyone raises their hand, the system still can't find the best possible arrangement. Sometimes, the person who could have helped the most doesn't raise their hand, or the system gets stuck in a loop.

The New Idea: "Justifiable" Violations

The authors propose a new way to think about fairness. Instead of asking for permission before the game starts, they ask: "Did the person whose VIP pass was broken actually gain something from the swap?"

They divide students into three groups:

1. The Winners: Students who get a better seat because of the swap. (They are happy; they have no reason to complain).
2. The Unchangeables: Students who are stuck in their current seat no matter what swap we try. (They can't be helped, so they can't really complain about being left behind).
3. The "Could-Have-Beens": Students who could have gotten a better seat in a different scenario, but didn't get one in this specific swap. These are the ones who get angry.

The Golden Rule of Justifiability:
You are allowed to break a VIP pass only if the person whose pass you broke is either a Winner or an Unchangeable.

• If you break a pass for a "Winner," they are happy, so it's fair.
• If you break a pass for an "Unchangeable," they couldn't have done better anyway, so it's fair.
• But, if you break a pass for a "Could-Have-Been" (someone who could have won but didn't), that is Unjustifiable. It's like taking a candy from a kid who was about to win the race, just to give it to someone else, when you could have just let the race happen differently.

The Solution: The "Just-Below-Cutoff" Mechanism

To put this into practice, the authors built a computer algorithm (a set of instructions) called SJBC+.

Think of it like a domino effect:

1. Step 1: The algorithm finds the easiest, safest swaps first. These are swaps where no one gets hurt (no VIP passes are broken for anyone who could have won). It's like finding a group of people who can just swap seats with each other without anyone losing out.
2. Step 2: Once those swaps happen, some students become "Winners." Now, the algorithm looks again. Because these new "Winners" are happy, the algorithm is allowed to break their VIP passes in the next round to help other people.
3. Step 3: It keeps doing this, expanding the circle of "Winners" like a ripple in a pond, until it can't find any more swaps that don't hurt the "Could-Have-Beens."

Why This Matters

The authors ran thousands of simulations (like running the game 2,000 times with different random rules) to see how well this works compared to the old "Ask for Permission" method.

• The Old Way (Consent): When only half the students agreed to give up their passes, the system was terrible at finding efficient solutions. It often got stuck.
• The New Way (Justifiability): Their algorithm found the best possible outcome (Pareto-efficient) in over 60% to 85% of cases, even without asking for permission in advance. It helped more students get better seats than the old method, even when the old method had everyone's permission.

The Big Takeaway

The paper proves that you can't always get a perfect, 100% efficient outcome without breaking some rules. However, by using this new "Justifiable" logic, you can get much closer to perfection than before, without needing to ask for permission or breaking rules in ways that make people feel cheated.

It's a new way to balance fairness (respecting priorities) and efficiency (getting the best seats for everyone), showing that sometimes, the best way to be fair is to look at who actually benefits from the change, rather than who gave permission beforehand.

Technical Summary

1. Problem Statement

The paper addresses the tension between stability (respecting legally defined priorities) and efficiency (Pareto-optimal allocation) in school choice mechanisms.

• The Baseline: The student-proposing Deferred Acceptance (DA) algorithm is the dominant mechanism because it produces a stable, student-optimal matching. However, DA is often Pareto-inefficient, generating significant welfare losses.
• The Dilemma: Any Pareto improvement over DA necessarily requires violating some students' priorities. The core question is: Which priority violations are "justifiable"?
• Existing Approaches: The leading alternative is Ex-Ante Consent (e.g., the Efficiency-Adjusted Deferred Acceptance or EADA mechanism), where students agree in advance to waive their priorities if doing so benefits others without harming themselves.
• The Gap: The authors argue that ex-ante consent has limitations. It relies on pre-defined permissions, which may be too restrictive or fail to capture efficiency gains that are defensible based on the outcome rather than pre-approval.

2. Methodology and Framework

A. Conceptual Framework: Justifiability

The authors introduce an endogenous criterion for justifiable priority violations. Instead of asking for permission beforehand, they evaluate violations based on the realized outcome of the improvement.
Students are categorized into three groups relative to a DA-improvement matching $\mu$:

1. Beneficiaries ($B(\mu)$): Students who strictly improve their assignment compared to DA.
2. Unimprovable Students ($U(P)$): Students who cannot be helped by any Pareto improvement over DA (they remain at their DA assignment in all efficient matchings).
3. Improvable Non-Beneficiaries: Students who could have improved under some DA-improvement but do not improve under the specific matching $\mu$.

Definition of Justifiability: A priority violation against student $i$ is justifiable if and only if $i \in U(P) \cup B(\mu)$.

• Violations against unimprovable students are acceptable because they gain nothing anyway.
• Violations against beneficiaries are acceptable because they gain from the trade.
• Violations against improvable non-beneficiaries are unjustifiable. These are students who could have been helped but were left behind; overriding their priority for others is indefensible.

B. The "Just Below Cutoffs" (JBC) Mechanism

The authors first construct a baseline mechanism called JBC to find "Strongly Justifiable" improvements (where no improvable student's priority is violated).

• Logic: For every school that rejected an improvable student during DA, identify the "cutoff" student (the lowest priority student assigned to that school in DA).
• Selection: Identify the highest-priority student below that cutoff who prefers the school to their DA assignment.
• Execution: Construct a directed graph of schools based on these "just below cutoff" students. Execute disjoint cycles in this graph.
• Result: JBC guarantees a Strongly Justifiable matching (violations only occur against unimprovable students) whenever DA is inefficient.

C. The Sequential Just Below Cutoffs (SJBC+) Algorithm

Recognizing that JBC is too conservative (it forbids violating the priorities of improvable students even if they eventually benefit), the authors propose SJBC+, a polynomial-time iterative algorithm.

1. Expansion Phase:
   • Start with the JBC matching and its set of beneficiaries $B_1$.
   • Construct a bipartite graph of improvable students.
   • Allow edges (trades) where the set of violated priorities (labels) is a subset of the current beneficiary set $B_t$.
   • Find a maximum-cardinality matching to expand the set of beneficiaries.
   • Iterate: As new students become beneficiaries, they "justify" further priority violations against themselves in subsequent rounds.
2. Refinement Phase:
   • Once the expansion phase converges, perform a refinement step to permute assignments among the final set of beneficiaries to ensure no further Pareto improvements are possible within that set.
3. Output: A matching that is justifiable and cannot be Pareto-improved by any other justifiable matching without strictly expanding the set of beneficiaries.

3. Key Contributions and Theoretical Results

• Existence of Justifiable Improvements (Theorem 1): If DA is inefficient, a strongly justifiable improvement always exists (guaranteed by JBC).
• Incompatibility with Full Efficiency (Proposition 1): Justifiability and full Pareto-efficiency are generally incompatible. Achieving full efficiency often requires violating the priorities of improvable non-beneficiaries, which the criterion explicitly forbids.
• Superiority over EADA (Theorem 3): The set of justifiable matchings is distinct from the set of EADA outcomes.
  • There exist problems where the unique justifiable and Pareto-efficient matching is not produced by EADA under any consent set.
  • Conversely, EADA with full consent can produce outcomes that are not justifiable (violating the priorities of improvable non-beneficiaries).
• Limitations of Ex-Ante Consent (Theorem 4): The authors prove a fundamental impossibility result for consent-based mechanisms. No mechanism can simultaneously satisfy:
  1. Incentivizing Consent: Consenting does not harm the student.
  2. Constrained Efficiency: The outcome is not Pareto-dominated by another matching respecting non-consenters.
  3. Efficiency Whenever Possible: If an efficient matching respecting non-consenters exists, the mechanism finds it.
  • Implication: Ex-ante consent frameworks inherently struggle to realize all feasible efficiency gains under partial consent without undermining incentives.

4. Empirical Results (Simulations)

The authors simulate random school choice markets ($N=50, 100$) with independent and correlated preferences, comparing SJBC+, DA, and EADA (with 50% and 100% consent).

• Pareto Efficiency:
  • SJBC+ achieves Pareto efficiency in 63–85% of instances.
  • EADA (50% consent) achieves efficiency in <10% of instances (0% in correlated markets).
  • EADA (Full consent) achieves 100% efficiency (by design) but at the cost of justifiability.
• Justifiability:
  • SJBC+ is 100% justifiable by construction.
  • EADA (Full consent) has a very low justifiability rate (dropping to 0.3% in large, correlated markets), meaning it frequently violates the priorities of improvable students who do not benefit.
• Beneficiaries:
  • SJBC+ generates more beneficiaries on average than EADA with 50% consent and often more than EADA with full consent, while maintaining justifiability.

5. Significance and Conclusion

• New Normative Framework: The paper establishes "Justifiability" as a robust, outcome-based alternative to ex-ante consent. It allows for controlled priority violations that are defensible because the affected parties either gain or could not have gained.
• Practical Algorithm: The SJBC+ algorithm provides a computationally efficient (polynomial time) method for Education Authorities to improve upon DA. It offers a "sweet spot" where efficiency gains are maximized without resorting to the ethically questionable violations of improvable non-beneficiaries.
• Theoretical Insight: The work highlights that the trade-off between efficiency and stability is not merely a function of "how many people consent," but depends on the structure of the improvement. It demonstrates that endogenous justification can unlock efficiency gains that ex-ante consent mechanisms miss, while also showing that full efficiency is often unattainable under strict justifiability constraints.
• Policy Implication: For school districts, SJBC+ offers a defensible path to improve student welfare beyond DA without requiring complex pre-surveys or risking the violation of priorities for students who are left worse off.

In summary, the paper argues that justifiability is a superior criterion for priority violations in school choice, offering a mechanism that is more efficient than partial-consent approaches and more ethically defensible than full-consent approaches, backed by a rigorous algorithm and empirical evidence.