| paper | Near-Feasible Stable Matchings with Budget Constraints |
| authors | Yasushi Kawase, Atsushi Iwasaki |
| venue | IJCAI 2017 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\delta_{\min}=0\) for every stated instance, with a polynomial-time constructible stable allocation. Every threshold instance with \(q\ge 0\) has answer YES. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given finite doctor types \(\Theta\) with rational masses \(\mu_\theta\), hospitals \(H\), type-specific contract menus and preferences, positive wages \(w_x\), additive hospital utility densities \(u_h(x)\), and per-capita budgets \(b_h\), compute a mass allocation \(y_{\theta,x}\) minimizing the budget inflation \(\delta\) required for continuous stability. Each individual receives one integral contract, while type mass may split across contracts; a blocking coalition is positive mass assigned to strictly preferred contracts that gives some hospital strictly higher additive utility within budget \(b_h+\delta\). Determine whether fractional density-greedy generalized deferred acceptance computes an optimum in polynomial time, in particular whether it achieves \(\delta=0\).
A finite-type high-multiplicity matching market with mass variables \(y_{\theta,x}\), wage expenditure \(W_h(y)=\sum_x w_xy_{\theta,x}\), additive utility \(U_h(y)\), and per-capita budgets \(b_h\); the objective is to minimize the inflation needed for continuous stability, with fractional density-greedy deferred acceptance as the candidate algorithm.
The mirror covers Theorem 5's non-strategy-proof near-feasible mechanism with additive hospital utilities. It leaves the impossibility results, arbitrary weak hospital preferences, Theorems 1–4 and 6–8, and the special-case mechanisms untreated.
The strongest honest positive case is a qualified Class A mirror anchored on Theorem 5. It is an algorithmic anchor, not a hardness anchor; the paper contains no named NP-hardness theorem proved by its authors.
Theorem 5, proved in this paper, states that under additive hospital utilities, the generalized deferred-acceptance mechanism using Algorithm 3’s choice functions returns a matching \(X'\) that is \(B'_H\)-stable with \(B_h\le B'_h<B_h+\overline w_h\) for every hospital \(h\), where \(\overline w_h\) is that hospital’s maximum offered wage. The mechanism runs in \(O(|X|\log |X|)\) time. Algorithm 3 sorts proposed contracts by hospital utility per unit wage and accepts contracts in that order until the budget is reached, accepting the contract that crosses the budget as well. The theorem deliberately sacrifices strategy-proofness to obtain the best possible budget-violation bound.
My mirror is Continuous Per-Capita Budget-Stable Matching, \(\mathrm{CBSM}_\infty\).
An instance contains:
The type description is complete: doctors of the same type have identical contract menus, preferences, wages, utilities, and all other parameters used by the problem.
A solution is a mass allocation \(y=(y_x)_{x}\), where \(y_x\ge0\), \(\sum_{x\text{ for }\theta}y_x\le\mu_\theta\), and each unit of mass receives at most one integral contract. Thus a cohort may be split across hospitals, but no individual receives a fractional contract. Hospital \(h\)'s wage expenditure and utility are \(W_h(y)=\sum_{x:h(x)=h}w_xy_x\) and \(U_h(y)=\sum_{x:h(x)=h}u_h(x)y_x\).
The optimization version asks for a stable allocation minimizing the per-capita budget excess \(\delta\), where \(W_h(y)\le b_h+\delta_h\), and stability is defined by excluding every positive-mass blocking coalition. A blocking coalition consists of a positive mass of doctors who can all move to contracts they strictly prefer while giving some hospital a strictly better additive contract bundle within its inflated budget.
The direct continuous analogue of Algorithm 3 is clear: when hospital \(h\) receives proposal mass, sort proposed contract mass by \(u_h(x)/w_x\), accept it in that order, and take only the necessary fraction of the boundary type to fill \(b_h\) exactly. Doctors whose mass is rejected propose their next contracts. The expected result is an exact \(b\)-stable allocation, so the optimum is \(\delta=0\).
This is a genuine high-multiplicity regime. Consider a national medical-placement market with millions of doctors but perhaps a few dozen hospitals. A type might specify specialty, qualification, location, contract preferences, and wage schedule. Large graduating cohorts can share these profiles, giving \(N\) doctors but only \(\tau\ll N\) types. Hospital budgets scale naturally as \(B_h=Nb_h\).
The finite-to-continuous bridge is especially strong here. Replicate each type \(N\mu_\theta\) times and give hospital \(h\) budget \(B_h=Nb_h\). Theorem 5 yields \(B_h\le B'_h<B_h+\overline w_h\), hence \(b_h\le B'_h/N<b_h+\overline w_h/N\). The discrete budget violation is therefore exactly one indivisible contract in the worst case, and it vanishes in the continuum. Fractionally assigning the boundary cohort is the high-multiplicity limit, not outcome-space fractionalization.
I would expect \(\mathrm{CBSM}_\infty\) to be Class A. Each hospital’s local choice is a fractional-knapsack calculation, solvable by sorting density ratios and filling one boundary type. The remaining global computation is a type-compressed deferred-acceptance process, plausibly polynomial in \(\tau\), \(|H|\), the number of contract types, and the input bit length. A configuration-LP or separation proof would formalize this expectation.
The mirror covers only Theorem 5: general additive hospital utilities and the non-strategy-proof near-feasible mechanism. It does not claim to continuize the paper’s impossibility theorem, its arbitrary weak hospital preferences, or the strategy-proof special cases.
The weakest point is the anchor rule. The paper’s Section 4 mentions that exact budget-constrained choice is knapsack-hard, but this is prose supported by cited literature, not a numbered hardness theorem proved here. Theorem 5 is therefore acceptable only if a named polynomial-time mechanism theorem counts as a computational anchor. Under a narrower rule requiring an explicit theorem saying “this problem is in P,” the paper has no qualifying anchor, and this should be reported plainly.
Even with that caveat, the mirror is worth asking: it preserves contracts, preferences, additive hospital choice, budgets, stability, and deferred acceptance, while testing whether the paper’s \(+\overline w_h\) obstruction is merely one-doctor granularity. Further questions are whether polynomial termination can be proved for the compressed fractional DA, how to round its solution back to finite markets, and whether cardinality quotas or implicit contract menus restore genuine hardness.
The strongest objection is that Theorem 5 is fundamentally an integrality theorem, not a population-multiplicity theorem. Its substantive guarantee is that an integral hospital choice crosses the budget by less than one indivisible wage, \(B_h' < B_h+\overline w_h\). In the proposed mirror, the boundary contract is fractionally accepted, so the very phenomenon Theorem 5 measures disappears: \(\delta_h=0\). Under replication by \(N\), the bound is merely \(\overline w_h/N\), and the continuum is just the fractional-knapsack relaxation of the hospital’s choice problem.
That objection survives the proponent’s insistence that every individual receives an integral contract. In an atomless cohort, the hospital can still accept an arbitrary fraction of a type. Thus the population limit has silently replaced an integral subset of contracts by divisible quantities. If one preserves indivisibility by requiring whole cohorts or atomic doctors, the one-contract obstruction returns—but then one has abandoned the continuous high-multiplicity regime.
The same issue removes the paper’s most interesting mechanism tradeoff. Algorithm 3 is useful because it obtains the best possible finite budget violation while sacrificing strategy-proofness. In \(\mathrm{CBSM}_\infty\), exact budget filling is automatic through the boundary mass, so the theorem’s tight approximation guarantee and its economic interpretation no longer survive. What remains is a finite type-compressed deferred-acceptance process with fractional knapsack choices, not a new continuous-population version of the paper’s central result.
The proposed medical-placement story does establish that a high-multiplicity regime is conceivable: additive utilities, repeated doctor profiles, and per-capita budgets are all defensible. Nor can one object that the paper has no computational anchor; Theorem 5 gives an explicit \(O(|X|\log |X|)\) mechanism. Those objections would be mistakes.
Accordingly, the negative case is weak. The vanishing of the \(+\overline w_h\) term is precisely the kind of integrality phenomenon a continuization programme may reasonably want to study. I cannot honestly defeat this anchor universally: the mirror is a legitimate limit question, even if its answer may be algorithmically straightforward.
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.