Papers for

matching algorithm designers

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.

Stable matching instances have unique prime factorizations and exact counts

Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census

Abstract: Every balanced instance of the stable marriage problem with strict complete preferences has a unique finest partition into prime blocks, and that single partition simultaneously factors three different structures: the reachable execution digraph as a Cartesian product, the proposal-prefix antimatroid as a direct sum, and the stable-matching lattice as a direct product. The converse fails, and fails at every size from two on: two explicit families share the identical Boolean-cube execution while one is maximally decomposable with a single stable matching and the other is prime with n. Uniqueness yields an exact census, a recursion counting the prime instances at every size, under which exactly 88,478,208 of the 110,075,314,176 profiles with four agents on each side are decomposable and the decomposable fraction is asymptotically n! / n^(2n). The blocks are characterised as the square components of the mutual-rank filtration, so the partition is computable in polynomial time and the factorisation is a tool rather than only a fact.

Sun 4 OctData Structures and Algorithms
The gist
Finding stable matches is a classic math problem about pairing groups fairly. The authors show that any balanced instance can be uniquely broken down into fundamental parts called prime blocks. These blocks reveal deep connections between different ways to look at the problem's structure. They also count exactly how many cases can be broken down this way, showing most are decomposable, and provide a way to find this breakdown efficiently.
Open → 2610.05617v1

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