Papers for

school district planners

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Revealing lottery numbers can help or hurt school assignments

The Double-Edged Sword of Information: Revealed versus Hidden Lotteries in School Choice

Abstract: In school choice, a lottery number is often used by the matching mechanism to break ties when there are more students who prefer the same school than the number of seats available. There has been growing theoretical and empirical interest in understanding the impact of revealing the lottery number to students. In practice, in recent years, the NYC Public Schools started revealing the lottery number to students to improve transparency. Theoretical findings from prior literature also suggest that revealing the lottery number strictly improves the number of matches under the deferred acceptance algorithm. However, these theoretical results are based on the over-simplifying assumption that all students share the same preference ranking for schools. In this work, we relax this assumption and allow students to have heterogeneous preference rankings. Under a game-theoretic model where student strategies form a Bayesian Nash equilibrium, we characterize scenarios where revealing the lottery number can either improve or worsen the matching outcome, measured by two metrics of match rate and social welfare. We further consider revealing partial information about the lottery, and demonstrate non-monotonic effects in the amount of information available to students. These results together illustrate complex tradeoffs induced by the lottery revealing policy.

Mon 28 SeptComputer Science and Game TheoryMachine Learning
The gist
When schools assign students using lotteries, sometimes students see their lottery number and sometimes they don’t. This paper studies what happens if students know their lottery number before choosing schools, especially when students like different schools. The authors find that showing the lottery number doesn’t always improve school assignments and can sometimes make things worse. They also explore how giving students only some information about the lottery creates complicated effects.
Open → 2609.34074v1

Top trading cycles handle matroid constraints and ties in preferences

Top Trading Cycles with Indifferences under Matroid Constraints

Abstract: We study the reallocation of indivisible objects among agents who may hold initial endowments and may be indifferent between objects. Each agent has her own set of admissible objects, and a matroid constraint specifies which combinations of assigned objects are feasible. The model contains the housing market, house allocation with newcomers who hold no endowment, and the assignment of students to schools under matroidal constraints at each school. For this model, we introduce the top-class trading cycles mechanism (TCTC), which extends the top trading cycles mechanism (TTC) to matroid constraints and weak preferences. When a trading cycle is selected, TCTC fixes each agent's top indifference class rather than a specific object and postpones the choice within the class to the end. TCTC is individually rational, Pareto efficient, and weakly group-strategy-proof on the full domain of weak preferences, and it runs in polynomial time. When preferences and reports are strict, TCTC is strongly group-strategy-proof. Together with a known impossibility result, our theorem establishes a maximal domain of school-by-school constraints for individual rationality, Pareto efficiency, and strategy-proofness.

Sat 26 SeptComputer Science and Game Theory
The gist
This work looks at how to exchange items among people who may start with some items and might not have clear preferences among them. Each person has a limited choice of items according to special rules (called matroid constraints), and the authors develop a method called top-class trading cycles (TCTC) to handle this. TCTC lets people trade fairly, efficiently, and without lying about preferences, even when they are unsure between items. The method works quickly and generalizes previous approaches used in housing and school assignments. It helps ensure everyone gets a good and fair deal under complex rules.
Open → 2609.32337v1