| paper | Matchings under One-Sided Preferences with Soft Quotas |
| authors | Santhini K. A., Raghu Raman Ravi, Meghana Nasre |
| venue | IJCAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given a finite post set \(P\), finite applicant-type set \(T\), rational masses \(\mu_t\) summing to \(1\), type-specific eligibility and weak rankings, and rational targets \(\ell(p)\le u(p)\), choose masses \(x_{t,p}\ge0\) with \(\sum_p x_{t,p}\le\mu_t\). With \(y_p=\sum_t x_{t,p}\) and \(d_p=\max\{0,\ell(p)-y_p,y_p-u(p)\}\), minimize \(\sum_p d_p\), then among its minimizers maximize the paper's rank-maximal signature order on assigned mass by rank.
A fractional many-to-one matching with applicant types \(T\), mass \(\mu\), type-post assignment variables \(x_{t,p}\), soft target deviations \(d_p\), and lexicographic rank-maximality as the secondary objective.
The exact denominator-clearing equivalence exposes no new continuum-specific combinatorics, and nontrivial normalized targets may require a deliberately scaled sequence of markets.
fatal: False
The mirror covers the rank-maximal total-deviation variants of Theorems 1 and 2, while leaving fairness variants, maximum-deviation variants, and related models untreated.
The strongest case is a Class-A mirror in which the applicants, not the posts, are continuized. My lead anchor is Theorem 2, proved in this paper: “OPT-MIN-MAX and OPT-MIN-TOT admit polynomial time algorithms.” I use its RMM-MIN-TOT member.
Call the continuous problem \(\mathrm{RMM\mbox{-}MIN\mbox{-}TOT}_\infty\). An instance has a finite post set \(P\), a finite set of applicant types \(T\), and rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\). A type records everything relevant to the paper’s matching problem: its eligible posts and its complete weak ranking of them, including ties. There are \(\tau=|T|\) types, while the represented population may have \(N\gg\tau\) applicants.
Each post \(p\) has rational lower and upper targets \(\ell(p)\le u(p)\), normalized by population size. The decision variable is an aggregate matching \(x\), where \(x_{t,p}\ge 0\) is the mass of type \(t\) assigned to \(p\), subject to \(\sum_p x_{t,p}\le\mu_t\). Let \(y_p=\sum_t x_{t,p}\) be the mass assigned to \(p\), and define \(d_p(x)=\max\{0,\ell(p)-y_p,y_p-u(p)\}\). The objective is first to minimize \(\sum_p d_p(x)\).
Preference optimality is represented by the paper’s signature with counts replaced by masses. If \(r_t(p)=i\), let \(z_i(x)=\sum_{t,p:r_t(p)=i}x_{t,p}\), and let \(z_{r+1}(x)=1-\sum_{t,p}x_{t,p}\) be unmatched mass. Among all assignments minimizing total deviation, the required solution lexicographically maximizes \((z_1,\ldots,z_r,z_{r+1})\) under precisely the paper’s rank-maximal order.
This is recognizably the paper’s problem, not merely fractional assignment with an unrelated objective. It preserves one-sided applicant preferences, unmatched applicants, soft lower and upper targets, total deviation, and rank-maximality. The continuous object is the applicant population; the posts remain named, discrete resources with target ranges.
A natural regime is centralized allocation of courses, school places, hospital positions, or jobs. For example, a large annual course-allocation market may contain \(N=100{,}000\) students but only \(\tau=500\) or \(1{,}000\) distinct preference-and-eligibility profiles, determined by programme, year, location, and prerequisites. A type’s mass is a cohort of exchangeable students, and a course section’s soft quota is its intended enrollment range. This is exactly the kind of setting in which the paper’s motivating applications—courses, schools, hospitals, and jobs—have high multiplicity.
The problem should be tractable, hence Class A. The aggregate matching constraints are a capacitated bipartite-flow system. Total deviation is linearized with variables \(d_p\) satisfying \(d_p\ge \ell(p)-y_p\), \(d_p\ge y_p-u(p)\), and \(d_p\ge0\). Rank-maximality can be implemented by \(r\) successive linear optimizations, or by polynomial-bit lexicographic weights. Thus the continuous instance has a polynomial-size rational LP or min-cost-flow formulation in \(\tau\), \(|P|\), the explicit type-edge list, and the input bit length.
The high-multiplicity bridge is unusually clean. If \(\mu_t=n_t/N\), \(\ell(p)=L(p)/N\), and \(u(p)=U(p)/N\), then the model is the normalized form of a finite instance with \(n_t\) cloned applicants of type \(t\). Conversely, a rational continuous solution can be scaled by a common denominator into integer assignment counts. Total deviation and every signature coordinate scale by the same factor, so feasibility, optimality, and ties are preserved. Splitting one type across several posts therefore does not destroy the matching interpretation: after denominator clearing, it is simply assigning different clones of that type to different posts.
The second anchor is Theorem 1, also proved in this paper: “OPT-SIGN-MIN-MAX and OPT-SIGN-MIN-TOT admit polynomial time algorithms.” I mirror its RMM-SIGN-MIN-TOT member as \(\mathrm{RMM\mbox{-}SIGN\mbox{-}MIN\mbox{-}TOT}_\infty\). Its input is the same \((T,\mu,P,\ell,u)\), together with a rational signature requirement \(\rho\). The question is to find an aggregate matching \(x\) satisfying \(\sigma(x)\succeq_R\rho\) in the paper’s rank-maximal order, and having minimum total deviation \(\sum_p d_p(x)\). If no such matching exists, the answer is infeasibility; otherwise any optimum is a valid solution.
This is a particularly faithful mirror because the signature requirement is explicitly part of the paper’s input, rather than something added by the continuization. It retains the paper’s “preference optimality first, deviation next” trade-off. It should also be Class A: the lexicographic signature constraint can be handled by considering the possible first coordinate at which \(\sigma(x)\) exceeds \(\rho\), imposing equality on earlier coordinates, and solving a polynomial number of linear programs or flow problems.
These mirrors cover only the rank-maximal members of Theorems 1 and 2, and especially the total-deviation variants. I am not claiming here that the fairness versions, max-deviation versions, two-sided preference models, or the paper’s related mechanisms automatically inherit the same formulation. Further questions include whether the max-deviation mirror admits an equally clean strongly polynomial algorithm, how much rounding loss is needed when the population size \(N\) is fixed, and what happens when the type catalogue is implicit or \(\tau\) approaches \(N\).
The weakest point is that this is a genuine high-multiplicity extension rather than a surprising new interpretation. At fixed \(N\), the continuous model drops the original integrality grid; its exact correspondence is to cloned populations after scaling, not necessarily to the original population size. Also, if applicants have individualized eligibility or rankings, then \(\tau\) may be essentially \(N\), eliminating the computational benefit. But those are limitations of the regime, not failures of the mirror. In the large centralized-allocation scenarios the paper itself motivates, rational applicant-type masses and scaled soft targets are a natural population model, and both numbered polynomial-time results have precise continuous counterparts.
The strongest negative case is that both proposed mirrors are not genuinely new continuous computational objects. They are exact normalizations of ordinary capacitated matching, with the paper’s existing flow algorithms surviving unchanged after applicant aggregation.
For Theorem 2, let \(D\) clear the denominators of \(\mu\), \(\ell\), \(u\), and a feasible solution \(x\). Then \(D\mu_t\) becomes a number of cloned applicants of type \(t\), \(Dx_{t,p}\) becomes an integer assignment, and \(D\ell(p),Du(p)\) become integer targets. Because this is a bipartite flow polytope, the scaled solution is an ordinary matching. Moreover,
\[
D\,d_p(x)=d_p(Dx)
\]
and every signature coordinate scales by \(D\), so total-deviation optimality and rank-maximality are preserved exactly.
This defeats the claim that \(\mathrm{RMM\mbox{-}MIN\mbox{-}TOT}_\infty\) reveals a new continuum-specific phenomenon. It is a compressed high-multiplicity encoding of the same flow problem. The paper already proves the relevant structural result and already solves it by flow; no configuration LP, separation problem, or new complexity boundary appears. When \(\tau\) is small, aggregation may improve implementation and input size, but that is a useful data-compression observation rather than a substantial ChoCo mirror.
The proposed course-allocation scenario does not fully repair this. If the number of seats or posts stays bounded while the applicant population grows, normalized targets tend to zero and the interesting quota violations become vanishing \(O(1/N)\) effects. To retain a nontrivial limit, capacities and targets must scale proportionally with the population. That is possible—for example, a sequence of large hospitals or course systems—but it is a deliberately constructed high-multiplicity regime, not an inherent limit of the paper’s model. In that regime the continuous problem remains exactly the same capacitated flow after cloning.
Theorem 1 does not escape this objection. The signature coordinates
\[
z_i(x)=\sum_{t,p:r_t(p)=i}x_{t,p}
\]
are linear in the assignment masses, so a signature requirement is merely a collection of linear or lexicographic constraints. Clearing denominators again converts any rational solution into a finite cloned instance, with the deviation objective and signature requirement preserved under scaling. The better interpretation—minimum service guarantees such as requiring at least a given mass to receive a first-choice post—is perfectly meaningful, but it makes the problem look even more like standard fractional transportation rather than like a new computational-social-choice object.
This is therefore a weak negative case, not a decisive one. There is no identity obstruction, no degeneracy that survives every modelling choice, and no known continuous treatment that makes the work a novelty collision. The proponent has correctly identified a sensible high-multiplicity regime, and existing high-multiplicity matching work supports rather than undermines it. The only serious objection is one of programme priority: these anchors offer compression and normalization, but little new computational structure. Under ChoCo’s stated standard, that probably is not enough to reject the mirror, and the universal claim that no worthwhile scenario exists cannot honestly be maintained.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.