Research map / Learning theory and algorithms / Prediction and decision losses

Achieving Balanced Representation in School Choice with Diversity Goals

AAAI 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Adaptive testing and experiments · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a choice function for a single school with one-to-one diversity quotas that uniquely satisfies maximal diversity, non-wastefulness, justified envy-freeness and balanced representation, and implements it via flow networks for faster computation.

Problem

School choice with overlapping student types under a one-to-one convention: existing diversity-quota algorithms can give severely imbalanced outcomes across type combinations (groups), and bipartite-graph methods are computationally costly.

Approach

Introduces balanced representation (maximize the minimum selection ratio across type-combination groups among rank-maximal matchings) and models the problem as a minimum-cost maximum flow network over groups and types, whose size depends on the number of groups rather than students.

Key results

• The proposed choice function is shown to uniquely satisfy non-wastefulness, maximal diversity, justified envy-freeness and balanced representation.
• The flow-network validity check runs in O(m log(n)(m + n log n)) strongly polynomial time, independent of the number of students.
• The choice function does not satisfy substitutability, so GDA with it cannot achieve the stability notion of Hatfield and Milgrom.

Measured effects reported in the paper

Surprising findings

• The proposed choice function violates substitutability, so it cannot be combined with GDA to yield the standard stability guarantee.

Limitations

• Analysis is for a single school; multi-school extension loses substitutability.
• Efficiency gains are argued theoretically without empirical experiments.

Experimental setup

Baselines: smart reserves multiple ranks of reserves choice function ranked reservation graph algorithm

Builds on: ranked reservation graph smart reserves multiple ranks of reserves rank-maximal matching generalized deferred acceptance

Closest papers by meaning

• High School Course Scheduling: Student Preferences and Fairness Constraints (Student Abstract) (AAAI 2025 · similarity 0.86)
• Matchings Under Biased and Correlated Evaluations (NeurIPS 2025 · similarity 0.84)
• Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.84)
• Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.84)
• Inherent Trade-Offs between Diversity and Stability in Multi-Task Benchmarks (ICML 2024 · similarity 0.82)
• Centralized Selection with Preferences in the Presence of Biases (ICML 2024 · similarity 0.82)