d4-journals-geb-2007-0081

I would make one focused case: the paper’s tractable result for matching with preferences over colleagues has a plausible continuous-population mirror in large school or college systems. The mirror should cover the paper’s restricted, top-coalition regime, not claim to extend its algorithm to arbitrary preferences.

A credible setting is a large school district with many students but relatively few distinct preference profiles. A type records a student’s complete preferences over schools and over the composition of their classmates; students of that type are interchangeable for the model’s purposes. The mass \(\mu_t\) is the fraction of students of type \(t\). Schools remain a finite set of institutions, and their preferences depend on the type composition of their enrolled students. A district might have tens of thousands of students but only dozens or hundreds of such types. That is a genuine high-multiplicity regime: the question is naturally about shares of the population, while each student still receives one school assignment.

My anchor is Theorem 15. It says that if a college-admissions problem satisfies the weak top-coalition property, then it has a unique core matching \(\mu\); \(\mu\) is the largest fixed point of \(T^2\); and if \(k\) is the number of groups in the partition witnessing that property, the paper’s algorithm finds \(\mu\) in at most \(k\) steps. The paper says the uniqueness and existence statement follows from Banerjee, Konishi, and Sönmez (2001), though the authors give an independent proof; the algorithmic bound is established here. With preferences given as explicit finite lists, this is an efficient algorithmic result: the number of rounds is bounded by the number of groups, and each round works with those lists. The paper does not state a standard complexity-class theorem such as membership in P, and it contains no named hardness result to use as an anchor.

Here is the continuous problem I would hand to a prover. Call it Continuous Top-Coalition College Matching. An instance has a finite set of colleges \(C\), a finite support of student types \(T\), rational type masses \(\mu_t\) summing to one, and preferences over school-and-cohort outcomes. Type \(t\) evaluates \((c,z)\), where \(z\in[0,1]^T\) is the mass vector of students enrolled at \(c\); college \(c\) evaluates its cohort vector \(z\). Use rational affine utility functions, with a fixed tie-breaking rule, so preferences have finite encodings. The allocation variable is \(x_{tc}\geq 0\), with \(\sum_c x_{tc}\leq\mu_t\); the rest of type \(t\)’s mass is unmatched, and \(z_c=(x_{tc})_{t\in T}\). There is no welfare objective: a solution is a core allocation, meaning an individually rational allocation with no internally feasible blocking coalition. In the one-college form corresponding to the paper’s stable* blocks, a college can retain some of its current cohort and recruit some other student mass into a new cohort \(y\); the participating students must weakly prefer \((c,y)\) to their current outcomes, the college must weakly prefer \(y\) to its current cohort, and at least the college or a positive mass of students must strictly prefer the change.

The input is promised to satisfy a continuous version of the weak top-coalition property: the colleges and unit mass can be partitioned into finitely many ordered layers, each containing at most one college and a vector of type masses. At each layer, every participating type ranks that layer’s school-and-cohort outcome top among outcomes formed from the remaining colleges and mass, and any college in the layer ranks its cohort top among the remaining mass. Types may be divided across layers. The task is to output the unique continuous core allocation, if the continuous analogue of Theorem 15 holds. The expected direction is tractable: with rational affine preferences, finding successive top cohorts and updating the fixed-point construction looks like a sequence of finite-dimensional linear or lexicographic linear optimization problems. That is a conjectured route for the mirror, not a consequence already proved by the finite-agent theorem. The natural complexity target would be polynomial time in \(|C|\), \(\tau=|T|\), the mass bit length \(L\), the preference encoding length, and the number \(k\) of layers.

This mirrors the paper’s actual problem: students care about who their colleagues are, colleges care about the composition of their cohorts, and the output is a stable matching. Fractional \(x_{tc}\) records how much of an indistinguishable type is assigned to each college; each unit of mass still receives an integral school assignment. Fractional population mass is therefore part of the mirror, not a change of goal to fractional outcomes. The mirror covers Theorem 15’s efficient structural subclass. It does not purport to mirror the general all-core algorithm in Theorem 10, the “core with singles” result in Theorem 11, or the couples extension.

The main questions it generates are whether the continuous top-coalition condition guarantees a unique core allocation, and whether the \(T^2\) method can find it in a number of optimization rounds controlled by \(k\). It also invites a high-multiplicity dictionary: how closely does the continuous allocation approximate discrete assignments when each \(\mu_t\) is a fraction of a large district population?

My weakest point is the change from named classmates to type composition. The paper allows preferences over exact subsets of named students; the mirror assumes students and colleges care about the distribution of student types instead. That is a meaningful restriction. If school decisions depend on particular individuals even within a proposed type, then the types must be refined, potentially until \(\tau\) is close to the population size, and the high-multiplicity advantage disappears. There is a second gap: the finite paper’s top-coalition partition is a partition of discrete agents, whereas the continuous model needs a well-defined, finitely encoded preference over cohort-mass vectors and an exact way to find top cohorts. Those are real proof and modeling obligations. Still, in a large system where peers matter through their composition, this remains recognizably the authors’ matching problem, and Theorem 15 gives a specific reason to investigate its continuous version.