| paper | Weighted Matching Markets with Budget Constraints |
| authors | Naoto Hamada, Anisse Ismaili, Takamasa Suzuki, M. Yokoo |
| venue | ATAL 2017 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: in \(\mathrm{P}\) for the stated model with \(m=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given complete student types \(\Theta\) with rational masses \(\mu_\theta\) summing to \(1\), one college with per-capita budget \(b\), type-specific wages \(w_\theta\), additive utilities \(u_\theta\), acceptability, and a current mass matching \(y_\theta\in[0,\mu_\theta]\), decide whether there exist incoming home masses \(z_\theta\in[0,\mu_\theta-y_\theta]\) and rejected matched masses \(r_\theta\in[0,y_\theta]\) such that incoming agents strictly prefer their contract to home, \(\sum_\theta w_\theta(y_\theta-r_\theta+z_\theta)\le b\), and \(\sum_\theta u_\theta(z_\theta-r_\theta)>0\).
A one-college high-multiplicity typed weighted market in which types carry mass \(\mu\), the current assignment is \(y\), blocking coalitions choose incoming mass \(z\) and rejected mass \(r\), and the college's budget feasibility and utility improvement are linear constraints and objective.
The case asserts rather than fully formalizes the multi-college extension and does not establish that all contract histories can be represented by the proposed type-state variables; this affects broader coverage but not the one-college anchor.
fatal: False
The mirror covers Theorem 2's one-college, additively separable verification problem; it leaves Theorems 1, 3, 4, 5, and 6 and the SDA results in Theorems 7–10 unaddressed.
The strongest positive case is a single, deliberately narrow mirror of Theorem 2, and it is a Class A case: the paper’s coNP-hard verification problem becomes a polynomial-time linear program when the population, rather than the matching outcome, is made continuous.
The lead anchor is Theorem 2, proved in this paper. It states that the paper’s CSWM–\(Y\) problem—given a weighted market and a feasible matching \(Y\), decide whether \(Y\) is coalitionally stable—is coNP-complete, even for a simple weighted typed market with only one college whose preferences are represented by an additively separable utility. The paper proves coNP-membership because a blocking coalition is a polynomially checkable certificate. For hardness, it reduces SubsetSum: the single college has budget \(\alpha\); each item \(w_i\) becomes a student whose wage and college utility are \(w_i\); one special student has wage and utility \(\alpha-\frac12\) and is currently matched; all other students are at home. A blocking coalition exists exactly when some subset of the item-students has total weight \(\alpha\).
I would mirror that result in a large standardized admissions or hiring market. There are many applicants, perhaps millions, but only \(\tau\) recurring complete applicant types, with \(\tau\ll N\). A type includes the applicant’s full preference over college–wage contracts and home, eligibility, wage menu, and all attributes relevant to the college’s utility. This is plausible for repeated cohorts such as graduates with the same qualification profile, experience band, location category, and contract preferences. The type definition is intentionally complete: two applicants are interchangeable precisely when the market model cannot distinguish them.
Normalize the population to mass \(1\). Type \(\theta\) has mass \(\mu_\theta\in\mathbb{Q}_{\ge0}\), with \(\sum_\theta\mu_\theta=1\). Each type has one possible contract \((c,w_\theta)\) with the college, college utility \(u_\theta\ge0\), and preference between that contract and home. The college has per-capita budget \(b\in\mathbb{Q}_{\ge0}\). A current mass matching is \(y_\theta\in[0,\mu_\theta]\), where \(y_\theta\) is the mass of type \(\theta\) currently employed by the college and \(\mu_\theta-y_\theta\) remains at home. Feasibility requires
\[ \sum_{\theta}w_\theta y_\theta\le b. \]
This keeps each infinitesimal agent’s outcome integral—home or one college contract with one wage. Only the mass of interchangeable agents is divisible.
The continuous problem is:
\[ \textsc{Continuous-CSWM--}Y_\infty \]
Given \((\Theta,\mu,w,u,\succ,b,y)\), decide whether the current mass matching \(y\) admits a positive-mass blocking coalition. Such a coalition chooses incoming masses \(z_\theta\) from home and rejected masses \(r_\theta\) from the college, satisfying
\[ 0\le z_\theta\le \mu_\theta-y_\theta,\qquad 0\le r_\theta\le y_\theta, \]
\[ z_\theta>0\ \Longrightarrow\ (c,w_\theta)\succ_\theta \text{home}, \]
and
\[ \sum_\theta w_\theta(y_\theta-r_\theta+z_\theta)\le b. \]
It must strictly improve the college’s additive utility:
\[ \sum_\theta u_\theta(y_\theta-r_\theta+z_\theta) > \sum_\theta u_\theta y_\theta. \]
Equivalently, the prover solves
\[ \max_{z,r}\ \sum_\theta u_\theta(z_\theta-r_\theta) \]
subject to those linear constraints. The answer is “not stable” if the optimum is positive, together with the optimizing mass coalition \((z,r)\); otherwise the matching is continuously coalitionally stable.
This problem is in polynomial time for rational inputs: it is one linear program with \(O(\tau)\) variables and constraints. The same construction extends to several colleges by using type-by-current-contract mass variables and solving one blocking LP per college. Thus the expected classification is Class A.
The important point is why Theorem 2’s hardness disappears. Its reduction relies on selecting an all-or-nothing subset of named students whose weights hit \(\alpha\). In the mirror, the corresponding decision is to choose \(z_\theta\in[0,\mu_\theta]\). A type can contribute any measurable fraction of its mass, so the SubsetSum obstruction becomes a fractional budget-and-utility optimization problem. The budgets, wages, college utility, students’ strict improvement requirement, and coalitional blocking semantics all remain; what disappears is precisely the population-multiplicity integrality. That is the kind of hardness dissolution the continuization programme is designed to test.
The paper’s Theorem 2 is therefore not merely being rephrased with fractional notation. It generates a new computational question about whether verifying stability survives the high-multiplicity limit. Rational masses also give the required bridge: clearing denominators expands the instance into a finite market of cloned applicants, while the continuous formulation permits the fractional mass coalitions that a large atomless population makes meaningful.
I would not claim that this settles the paper’s other results. In particular, the continuous analogue of Theorem 3—whether some coalitionally stable mass matching exists—could retain a more difficult global, possibly continuum-specific structure. Pairwise stability and the SDA mechanism likewise require separate mirrors. The present case covers only Theorem 2, emphatically.
The weakest point is that this mirror is intentionally a fractional relaxation, and the resulting LP is clean precisely because individual SubsetSum-style selection has vanished. An opponent can fairly say that the paper’s coNP-hardness is being dissolved rather than preserved. My answer is that this is not a defect under ChoCo: the programme asks whether the hardness was caused by population multiplicity or by the matching structure itself. Here the reduction’s combinatorics visibly live in the former, while the underlying weighted-contract and budget problem remains intact.
The strongest objection is that Theorem 2’s hardness is not really a population phenomenon. Its reduction gives every item student a potentially distinct wage and utility, so under the programme’s complete-type convention the \(n\) item students are \(n\) different types. The proposed continuous instance therefore does not continuize the theorem’s regime; it replaces its indivisible subset selection by a fractional knapsack problem.
Replication does not fully rescue this objection. Once each item type has many interchangeable copies, an atomless coalition may take an arbitrarily small fraction of any type. The special student’s exact \(\alpha-\tfrac12\) threshold disappears: with additive utility, blocking becomes a marginal budget-and-utility condition. Preserving the original packing semantics would require whole-type coalitions, indivisible mass quanta, or a positive minimum coalition size. The first is an arbitrary restriction; the latter two reintroduce the finite population the mirror was meant to remove.
The proposed LP also isolates a single college with all rejected students at home. That is a fractional resource-allocation problem, not much of the paper’s two-sided matching structure. A fuller mirror would need mass indexed by current college and contract, with conservation across colleges; but that only confirms that the tractability comes from linearizing the knapsack subproblem, not from a meaningful continuous analogue of weighted matching stability.
This is a real criticism of the claimed interpretation, but it is not enough under ChoCo’s rules. A replicated cohort of applicants with a budget scaled per capita is a sensible high-multiplicity market, and an atomless blocking coalition is a legitimate continuous version of the paper’s definition. The fact that the exact SubsetSum obstruction vanishes is precisely the kind of population-multiplicity effect the programme is designed to study. I therefore cannot honestly defeat Theorem 2: the negative case is weak, and this anchor remains a worthwhile Class A mirror.
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.