| paper | Pareto Optimal and Popular House Allocation with Lower and Upper Quotas |
| authors | — |
| venue | AAMAS 2022 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given finite applicant types \(T\) with rational masses \(\mu_t\ge0\) summing to \(1\), projects \(P\), strict preferences over \(P\cup\{\bot\}\), and rational mass quotas \(0\le\ell_p\le u_p\), decide whether there exists a feasible mass assignment \(x_{tq}\ge0\) and opening variables \(y_p\in\{0,1\}\) satisfying \(\sum_q x_{tq}=\mu_t\) and \(\ell_p y_p\le\sum_t x_{tp}\le u_p y_p\), such that no feasible challenger \((x',y')\) admits a coupling \(z_{t,p,q}\ge0\) with \(\sum_q z_{t,p,q}=x_{t,p}\), \(\sum_p z_{t,p,q}=x'_{t,q}\), and positive vote mass \(\sum_{t,p,q}z_{t,p,q}\sigma_t(q,p)>0\), where \(\sigma_t(q,p)\) is \(1\), \(-1\), or \(0\) according as \(q\succ_t p\), \(p\succ_t q\), or \(p=q\).
A one-sided high-multiplicity quota-matching model with type masses \(\mu_t\), mass assignments \(x\), Boolean project openings \(y\), and challenger couplings \(z\); the decision objective is existence of an assignment undominated by every positive-mass majority challenger.
With fixed \(\ell_{\max}=2=u_{\max}\), normalization makes every quota \(O(1/N)\), whereas proportional quotas change the reduction's pair gadget; the proponent notes this but does not establish which regime the paper's authors would accept.
fatal: False
The mirror is anchored only in Theorem 3's popular-matching existence result; it leaves Theorem 1's other hardness results, Theorem 2's algorithms, Theorems 4–11's parameterized results, and the weighted-matching open questions untouched.
The strongest mirror I would defend is a continuous version of the paper’s popular-matching existence problem, \(\mathrm{pop\text{-}ha}^{U}_{L}\). My lead anchor is Theorem 3: proved in this paper, it shows that \(\mathrm{pop\text{-}ha}^{U}_{L}\) is NP-complete even when \(\ell_{\max}=2=u_{\max}\) and \(\Delta_P=2\).
The natural scenario is a large centralized allocation of course projects, internships, or training placements. There may be \(N=10^5\) applicants but only a few dozen projects. Applicants are grouped into cohorts with identical acceptable projects and identical strict rankings: for example, students in the same programme, year, eligibility class, and advising track. A type is the complete preference-and-eligibility description used by the allocation problem. If there are \(\tau\) such cohorts, the high-multiplicity regime is \(N\gg\tau\), perhaps \(N=100{,}000\) and \(\tau=30\)–\(300\).
Here is the precise continuous problem I would give to a prover.
Let \(T\) be the finite set of applicant types, with type masses \(\mu_t\ge0\), \(\sum_t\mu_t=N\). Let \(P\) be the projects. Each type \(t\) has a strict order \(\succ_t\) over its acceptable projects and being unmatched, denoted \(\bot\). Project \(p\) has lower and upper mass quotas \(\ell_p,u_p\). A mass assignment is \(x_{tq}\ge0\), for \(t\in T\) and \(q\in P\cup\{\bot\}\), satisfying \(\sum_q x_{tq}=\mu_t\). There is also an opening variable \(y_p\in\{0,1\}\), with \(\ell_p y_p\le\sum_t x_{tp}\le u_p y_p\). Thus projects remain genuinely open or closed; only the applicant population is fractionalized.
Call an assignment \(x\) mass-popular if no other feasible assignment \(x'\) defeats it by mass majority. To define that exactly, let \(z_{t,p,q}\) be the mass of type \(t\) currently assigned to \(p\) that is reassigned to \(q\). Its row sums must equal \(x_{tp}\), and its column sums must form a feasible challenger assignment \(x'\). Define \(\sigma_t(q,p)=1\) if \(q\succ_t p\), \(-1\) if \(p\succ_t q\), and \(0\) otherwise. The challenger defeats \(x\) precisely when \(\sum_{t,p,q}z_{t,p,q}\sigma_t(q,p)>0\). The continuous problem, which I would call Mass-Popular-House Allocation with Lower and Upper Quotas, asks whether a mass-popular assignment exists, and outputs \(x\) if one does.
This is not a different matching objective disguised as an LP. It preserves the paper’s projects, closures, lower and upper quotas, incomplete preference lists, unmatched option, and head-to-head definition of popularity. The only change is that “a majority of applicants” becomes “a larger mass of applicants.” In normalized notation, divide all masses and quotas by \(N\), giving the programme’s distribution \(\mu\).
Theorem 3 is my strongest and only anchor. Its restriction \(\Delta_P=2\) is especially useful: in the mirror, each project can be acceptable to at most two applicant types, while those types may have large masses. The paper’s own course-project motivation makes this credible: a specialized project may draw from only two recurring cohorts, and it may open only when its minimum group size is met.
My working prediction is that the general continuous problem is a Class B candidate: hardness may transfer because the reduction’s combinatorics appear to live in project incidence, project activation, and the popularity comparison, rather than merely in having many individually named applicants. But this is precisely a question to investigate, not something Theorem 3 proves automatically. Once the set of open projects is fixed, the mass-assignment and challenger problems are transportation or flow LPs. The difficult part is retaining the binary open/closed quota disjunction and asking whether any challenger wins. If fractional splitting destroys the discrete reduction, the resulting problem could instead become tractable; if the activation structure itself remains hard, that would be the boundary the programme seeks.
The paper gives further support for this mirror’s legitimacy: the proof of Theorem 5 already groups applicants by identical preference structures and counts those types, using at most \(O((m+1)!)\) preference types. That is very close to the high-multiplicity representation above, even though Theorem 5 is not my hardness anchor.
The weakest point is the literal \(\ell_{\max}=2=u_{\max}\) restriction. With normalized population mass, a two-person quota becomes \(2/N\), which may be negligible in a genuinely large population. One can retain the theorem literally by measuring mass in applicant-equivalents, or instead study quotas that scale as population fractions; those are different regimes. Also, fractional assignment may erase the integrality that makes the discrete reduction work. I therefore claim a faithful and useful continuous question, not a hardness transfer.
The immediate follow-up questions are whether Mass-Popular-House Allocation has a polynomial separation or LP formulation, whether it is fixed-parameter tractable in the number of projects or the number of types, and whether Theorem 3’s hardness survives when every type has multiplicity tending to infinity and quotas scale proportionally with population size.
The best negative case attacks the fit between Theorem 3 and high multiplicity, rather than the existence of a formal mass model.
Theorem 3’s restriction \(\ell_{\max}=2=u_{\max}\) is not cosmetic. In the reduction, an open project is effectively a pair of named applicants. Together with \(\Delta_P=2\), the quota gadget encodes which two individuals occupy which project. That combinatorial object disappears under the proposed continuum.
If masses are normalized, the quota \(2\) becomes \(2/N\), which vanishes as the population grows. If quotas remain in applicant-equivalent units, they affect only a negligible fraction of the population. If quotas scale proportionally, an open project accepting \(2N\) units of mass can be filled by arbitrary fractions of its two eligible types; the pair-selection gadget is replaced by a fractional flow constraint. Requiring whole cohorts or integral mass would restore the original problem, but would also restore precisely the indivisibility that continuization was meant to remove.
A proportional-quota model is possible, but it is a new model rather than a high-multiplicity version clearly suggested by the theorem. A course project’s minimum group size is normally an absolute requirement, not a fixed fraction of the entire applicant population. The paper therefore gives no compelling evidence that its central hardness result survives in a genuinely meaningful population-continuum regime.
There is also a less obvious issue with popularity. In the discrete problem, \(M\) and \(M'\) assign the same named applicant two projects, so the majority comparison is well-defined. Aggregate assignments \(x\) and \(x'\) provide only marginals. When a type is split across several projects in both assignments, the vote depends on how those masses are coupled. The proposed \(z_{t,p,q}\) chooses a coupling favourable to the challenger, thereby defining a new “maximum-over-couplings” notion of popularity. A fixed-identity, worst-case, or randomized coupling would produce different problems. This is a genuine modelling choice, not a consequence of the paper’s definition.
These objections do not defeat the mirror outright. The cohort scenario is credible, and the paper’s own grouping of applicants by identical preference structures in Theorem 5 is evidence that high multiplicity is mathematically natural here. Consequently, the honest negative conclusion is limited: Theorem 3 does not itself justify the claimed high-multiplicity anchor, and the literal quota regime degenerates or becomes a different fractional problem. But I cannot honestly sustain the universal claim that no worthwhile continuous mirror exists. A well-designed proportional-quota, explicitly coupled mass-popularity problem remains a legitimate programme question.
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.