| paper | Optimal Matchings with One-Sided Preferences: Fixed and Cost-Based Quotas |
| authors | — |
| venue | AAMAS 2022 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1.2
statement extracted from the paper’s text layer
Given finite posts \(P\), finite applicant types \(T\), rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), rational normalized capacities \(q_p\), strict preference and eligibility data assigning each eligible pair \((t,p)\) a rank \(r_t(p)\in\{1,\ldots,r\}\), and a target signature \(\rho=(\rho_1,\ldots,\rho_{r+1})\), decide whether there exist masses \(x_{t,p}\ge0\) and unmatched masses \(u_t\ge0\) such that \(\sum_p x_{t,p}+u_t=\mu_t\), \(\sum_t x_{t,p}\le q_p\), \(z_j=\sum_{t,p:r_t(p)=j}x_{t,p}\), \(z_{r+1}=\sum_tu_t\), and \(\sum_{j=1}^{\ell}z_j\ge\sum_{j=1}^{\ell}\rho_j\) for every \(\ell\); output such an allocation if one exists.
A nonatomic high-multiplicity many-to-one allocation model in which each type \(t\) supplies mass \(\mu_t\), \(x_{t,p}\) assigns mass to eligible post \(p\), \(u_t\) leaves mass unmatched, post capacities are \(q_p\), and cumulative signature feasibility is expressed by a linear program.
The mirror assumes repeated complete applicant types and capacities proportional to population, while the paper gives no evidence that its empirical instances have this structure; it therefore does not relax the theorem's hard instances themselves.
fatal: False
Theorem 1.1 and Theorem 1.2 are mirrored through exact and cumulative signature mass allocation. Proposition 1.3 and Theorem 1.4 have natural cost-based mass-flow extensions but are not needed as anchors, while the LABELLED MATCHING source problem and experiments are not independently mirrored.
My lead anchor is Theorem 1.2, proved in this paper: CUM-SIGN-Q is NP-hard even when all preferences are strict and every post has unit quota, while it has a randomized polynomial-time algorithm when the number of ranks is \(O(1)\). This is the paper’s central cumulative-better-signature problem, so it is a better anchor than an unrelated matching variant.
I would mirror it by the following problem, CUM-SIGN-Q\(_\infty\). An instance contains a finite set of posts \(P\), a finite set of applicant types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational post capacities \(q_p\), and a target signature \(\rho=(\rho_1,\ldots,\rho_{r+1})\). A type \(t\) is a complete strict preference list over its eligible posts, including the rank \(r_t(p)\) of every eligible post. The last rank, \(r+1\), denotes being unmatched.
The decision variables are \(x_{t,p}\ge 0\), the mass of type \(t\) assigned to post \(p\), and \(u_t\ge0\), the unmatched mass of type \(t\). They must satisfy \(\sum_p x_{t,p}+u_t=\mu_t\) for every \(t\), \(\sum_t x_{t,p}\le q_p\) for every post, and \(z_j=\sum_{t,p:r_t(p)=j}x_{t,p}\), with \(z_{r+1}=\sum_tu_t\). The question is whether there is such an allocation with \(\sum_{j=1}^{\ell}z_j\ge\sum_{j=1}^{\ell}\rho_j\) for every \(\ell\). A solution is the allocation \(x\), not merely a yes/no certificate.
This is recognisably the authors’ problem: the graph, eligibility, preference ranks, fixed quotas, signature, and cumulative-better relation are all retained. The only change is that a large cohort of indistinguishable applicants is represented by mass and may be divided among posts. Each infinitesimal applicant still receives one discrete post; posts have not become divisible goods. The continuous object is the applicant population.
For an explicit type support, CUM-SIGN-Q\(_\infty\) is directly a rational linear-feasibility problem with \(O(\lvert T\rvert\lvert P\rvert)\) variables and \(O(\lvert T\rvert+\lvert P\rvert+r)\) constraints. Thus I expect a clear Class A result: polynomial time in \(\lvert T\rvert\), \(\lvert P\rvert\), \(r\), and the input bit length. The discrete NP-hardness can disappear because the labelled perfect-matching obstruction is an integrality obstruction among individual assignments. In the mass model, the same cohort can send fractions to several posts while preserving the aggregate rank counts.
The intended regime is, for example, a large centralized course-allocation system: perhaps \(10^5\) students, \(10^2\) courses or course sections, and only tens or hundreds of recurring preference-and-eligibility types. A type might mean students in the same programme, year, timetable category, and advising track who submit the same ranking. Course capacities scale with the population and become rational capacity fractions after normalization. This is a genuine high-multiplicity regime, with \(\lvert T\rvert\ll n\), not a claim that every arbitrary matching instance is naturally continuous. The paper itself motivates the problem through students-to-courses allocation, so the authors should recognise the scenario.
The high-multiplicity dictionary is straightforward. Given a discrete instance with \(n_t\) applicants of type \(t\), total population \(N\), quotas \(q_p^{\mathrm{disc}}\), and signature \(\rho^{\mathrm{disc}}\), set \(\mu_t=n_t/N\), \(q_p=q_p^{\mathrm{disc}}/N\), and \(\rho_j=\rho_j^{\mathrm{disc}}/N\). Every discrete matching induces a feasible mass allocation. Conversely, a rational mass allocation becomes an ordinary matching after replicating the population by a common denominator. At a fixed \(N\), rounding and the resulting signature error become separate, useful questions rather than hidden assumptions.
My second anchor is Theorem 1.1, also proved in this paper: EXACT-SIGN-Q is NP-hard even with strict preferences and unit post quotas, and has a randomized polynomial-time algorithm for \(r=O(1)\). Its continuous mirror, EXACT-SIGN-Q\(_\infty\), is the same explicitly specified mass-allocation problem, but asks for \(z_j=\rho_j\) for every \(j\), rather than the cumulative inequalities. The action is again \(x_{t,p}\) and \(u_t\); the objective is exact realization of the requested rank signature.
This second mirror matters because it shows that the tractability is not an artefact of weakening equality to inequality. Both the exact signature and the paper’s new cumulative ordering become linear constraints once the population is nonatomic. EXACT-SIGN-Q\(_\infty\) is likewise Class A under explicit types. Theorem 1.2’s hardness reduction from EXACT-SIGN-Q therefore becomes a useful boundary question: precisely which integrality or indivisibility restrictions are needed to make the hardness survive?
These mirrors cover the paper’s fixed-quota results, including the strict-preference/unit-quota hard core, but not every result. Theorem 1.4 is also naturally extensible: adding a post cost \(c(p)\) gives the objective \(\min\sum_{t,p}c(p)x_{t,p}\) subject to exact or cumulative signature constraints, yielding a mass version of the paper’s min-cost-flow algorithms. I would not count Theorem 1.4 as a separate anchor because it is already algorithmic and would add little to the hardness-dissolution case.
The weakest point is that the paper’s hardness instances may have essentially one complete preference/eligibility type per applicant. Then \(\lvert T\rvert=\Theta(n)\), and the proposed mirror provides compression only in a different instance regime. Moreover, the unit-quota restriction does not survive literally when a fixed catalogue of posts serves a large population: capacities must scale with population mass. So this is not a claim that Theorem 1.2’s NP-hardness disappears on every family covered by the theorem.
The positive claim is narrower and, I think, defensible: the paper’s exact and cumulative signature questions have a faithful high-multiplicity form for large applicant cohorts, and in that regime their central combinatorics collapses to linear optimization. The important follow-up questions are whether one can round mass solutions with controlled signature loss, whether posts themselves can be compressed into types, whether implicitly represented preference types create a pricing problem, and how much hardness returns if cohorts must remain indivisible or if each type can be assigned only as an integral block.
The strongest case against the proposed mirrors is that they erase the only combinatorial object responsible for Theorems 1.1 and 1.2: an applicant is an indivisible vertex that must choose one incident post.
Theorem 1.2 reduces from LABELLED MATCHING. Each applicant’s particular eligible edges encode the graph vertex, and the requirement that every rank be represented is meaningful only because one applicant cannot simultaneously use several edges. In the proposed \( \mathrm{CUM\text{-}SIGN\text{-}Q}_\infty \), a type’s mass can be partitioned among posts. Fractions of one cohort can then satisfy several rank constraints simultaneously, even when no matching exists. Requiring each type to move as an indivisible block would preserve the combinatorics, but that is no longer the usual nonatomic or high-multiplicity interpretation: many identical applicants are individually assignable, so their aggregate mass should be splittable.
There is also a serious regime problem. In the hardness constructions, applicants encode graph vertices through their distinct eligibility sets and rankings. Since a type is a complete description, these applicants cannot be merged without losing the reduction; the support then has size \( \lvert T\rvert=\Theta(n) \). Conversely, making \( \lvert T\rvert\ll n \) removes precisely the incidence structure that makes the theorem hard. The resulting LP may be useful, but it is a relaxation for a different, highly regular cohort regime rather than a continuous version of the paper’s hard instances.
The unit-quota restriction creates a related difficulty. With a fixed catalogue of posts and fixed unit capacities, letting the applicant population grow makes the matched fraction tend to zero. The signature becomes dominated by unmatched applicants. To obtain a nondegenerate limit, one must scale capacities with population size or replicate posts. That is a sensible course-allocation model, but it is an additional proportional-capacity assumption, not the fixed-capacity setting used in the theorem.
These objections apply equally to Theorem 1.1. EXACT-SIGN-Q has the same identity-level matching structure, and its continuous version is again just linear feasibility in variables \(x_{t,p}\). The exact signature constraints \(z_j=\rho_j\) are perfectly well-defined, but their tractability comes from allowing nonatomic splitting, not from a deeper continuation of the paper’s exact-matching problem.
Still, these objections do not defeat the best version of the mirror. A large course-allocation system with recurring cohorts, identical eligibility and preference lists, and capacities proportional to enrollment is a coherent high-multiplicity regime. The variables \(x_{t,p}\) can be interpreted as assigning different infinitesimal members of a cohort to different posts; no individual need literally receive two posts. Rational mass solutions can be lifted to ordinary matchings after replication. The paper’s applicant-to-course motivation makes this scenario plausible, even if its experiments do not establish that the observed data have small type support.
Nor can one object that the continuous problem is merely easy: the programme explicitly treats the disappearance of discrete NP-hardness under continuization as a valuable outcome. Theorem 1.4’s cost-based flow results likewise extend naturally, though they provide little additional conceptual challenge.
Consequently, the negative case is weak. It can demand evidence that the intended application really has repeated complete types and proportionally scalable capacities, and it can point out that the hard reductions do not survive in a compressed type space. But it cannot honestly establish that no worthwhile continuous mirror exists. Both Theorem 1.2 and Theorem 1.1 have faithful, nontrivial high-multiplicity formulations under a plausible cohort model.
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.