Near-Feasible Stable Matchings with Budget Constraints (d4-conf-ijcai-2017-0124)

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 society is given by its support: a list of \(\tau\) doctor types \(\Theta\) with positive binary rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types. Each type represents an atomless population.
There are \(m\) hospitals \(H\). Each type has an explicitly listed finite menu \(X_\theta\) of contracts \(x=(\theta,h,w_x)\) and a strict preference order over \(X_\theta\cup\{\varnothing\}\), where \(\varnothing\) means unmatched. Hospital budgets \(b_h\) and wages are binary rationals satisfying \(0<w_x\le b_h\); hospital utility densities \(u_h(x)\) are nonnegative binary rationals. Every offered contract is acceptable to its hospital.
An allocation consists of real masses \(y_{\theta,a}\ge0\), with \(\sum_{a\in X_\theta\cup\{\varnothing\}}y_{\theta,a}=\mu_\theta\). Each individual receives one contract or remains unmatched; type mass may split. Require \(y_{\theta,x}=0\) whenever \(\varnothing\succ_\theta x\). Define \(W_h(y)=\sum_{\theta,x:x_H=h}w_xy_{\theta,x}\) and \(U_h(y)=\sum_{\theta,x:x_H=h}u_h(x)y_{\theta,x}\).
For a common inflation \(\delta\ge0\), feasibility means \(W_h(y)\le b_h+\delta\) for every hospital. A blocking alternative for hospital \(h\) selects disjoint submasses from the current allocation and assigns each selected individual a contract with \(h\): an existing contract may be retained, but every changed contract must be strictly preferred to that individual's current assignment. The hospital may discard incumbents. The alternative must have positive mass, total wage at most \(b_h+\delta\), and utility strictly greater than \(U_h(y)\). Stability means feasibility and absence of such an alternative.
Let \(N=\sum_\theta|X_\theta|\) and let \(L\) be the total binary input length, including any rational threshold \(q\ge0\). Running times are measured in \(m,\tau,N,L\).

Is computing the minimum inflation \(\delta\) admitting a stable allocation solvable in polynomial time, or is it NP-hard, with the threshold question asking whether such an allocation exists for some \(0\le\delta\le q\)? Is \(\delta=0\) always attainable?

For finite doctors, density-greedy generalized deferred acceptance computes a stable matching in \(O(|X|\log|X|)\) time for hospital-specific budgets satisfying \(B_h\le B'_h<B_h+\max_{x:x_H=h}w_x\); this does not assert minimum inflation ([Kawase–Iwasaki](https://arxiv.org/pdf/1705.07643v5)). No result settling exactly the atomless problem defined above was identified in the search.

Result for the stated problem

The minimum inflation is always \(\delta_{\min}=0\). It is polynomial-time computable, and a stable allocation witnessing this value can also be constructed in polynomial time. Every threshold instance with \(q\ge 0\) has answer YES.

The normalization makes the stated budgets nonbinding. Below I prove this directly, then address the intended binding-budget case: even there, atomless divisibility implies existence at zero inflation.

1. A polynomial-time construction

For each type \(\theta\), let \(a_\theta\) be its most-preferred element of \(X_\theta\cup\{\varnothing\}\). Define the allocation by giving its entire mass \(\mu_\theta\) to \(a_\theta\), with all other coordinates zero.

The menu is finite and preferences are strict, so \(a_\theta\) exists and is unique. If it is a contract, it is preferred to being unmatched. Thus the allocation satisfies individual acceptability and all type-mass constraints.

Budget feasibility

In fact, every allocation satisfying the type-mass constraints is feasible at zero inflation. For each hospital \(h\),

\(\displaystyle W_h(y)=\sum_{\theta,x:x_H=h}w_xy_{\theta,x}\le b_h\sum_{\theta,x:x_H=h}y_{\theta,x}\le b_h\sum_\theta\mu_\theta=b_h.\)

The first inequality uses \(w_x\le b_h\). The second uses nonnegativity and the fact that each type’s total allocated mass, including unmatched mass, is \(\mu_\theta\). As usual, budgets are nonnegative.

Absence of blocking alternatives

Every individual receives their most-preferred available assignment. Consequently, no individual can make a strictly preferred change.

An admissible alternative for hospital \(h\) can therefore only retain some of its current incumbents. Since all utility densities are nonnegative, retaining a submass and discarding other incumbents gives utility at most \(U_h(y)\). Such an alternative cannot block.

The constructed allocation is therefore stable at \(\delta=0\).

Computational conclusion

Since inflation must be nonnegative and zero is attainable, \(\delta_{\min}=0\).

Scanning the explicitly listed preference orders identifies each \(a_\theta\). The output coordinates are simply input masses or zero, so the construction has polynomial running time and output length in \(m,\tau,N,L\). For every permitted threshold \(q\ge0\), the same allocation witnesses existence with \(0\le\delta\le q\).

2. The binding-budget case also admits zero inflation

To address the substantive question beyond the normalization observation, consider the same allocation and blocking definitions, but allow arbitrary positive rational type masses and positive wage densities. In particular, drop both \(\sum_\theta\mu_\theta=1\) and \(w_x\le b_h\). Assume hospital budgets are strictly positive; hospitals with no contracts can be omitted.

Proven claim. This more general atomless model also admits a stable allocation at zero inflation.

The proof uses the finite-doctor theorem supplied in the question, with a separate argument establishing that strict blockers survive discretization.

Finite theorem used

For finite doctors with strict contract preferences and additive hospital utilities, Kawase–Iwasaki’s Theorem 5 gives a matching stable under budgets satisfying \(B_h\le B'_h<B_h+\max_{x:x_H=h}w_x\), provided individual wages satisfy \(0<w_x\le B_h\). Their blocking definition permits retaining incumbents and requires strictly preferred changed contracts, as here. [Kawase–Iwasaki, Definition 1 and Theorem 5](https://arxiv.org/pdf/1705.07643v5).

Construction of finite approximations

Let \(M=\sum_\theta\mu_\theta\), and choose a positive integer \(D\) such that every \(D\mu_\theta\) is integral.

For each sufficiently large positive multiple \(n\) of \(D\), replace type \(\theta\) by \(n\mu_\theta\) distinct finite doctors. Each represents mass \(1/n\), inherits the type’s preferences, and receives a copy of each contract \(x\) with wage \(w_x/n\).

Give that copied contract hospital utility \((u_h(x)+1/n)/n\). The perturbation makes all contract utilities strictly positive and will vanish in the limit.

Keep the original budgets \(b_h\). Define \(\bar w_h=\max_{x:x_H=h}w_x\). For sufficiently large \(n\), every copied wage is at most its hospital’s budget. The remaining hypotheses also hold: menus are finite, doctor preferences are strict, utilities are additive, and contracts are hospital-acceptable. Hence the finite theorem supplies a matching stable under budgets

\(\displaystyle b_h\le b_h^{(n)}<b_h+\frac{\bar w_h}{n}.\)

Let \(y_{\theta,a}^{(n)}\) be the number of type-\(\theta\) clones assigned to \(a\), divided by \(n\). These coordinates satisfy the original type-mass constraints and individual acceptability. Moreover,

\(\displaystyle W_h(y^{(n)})\le b_h^{(n)}<b_h+\frac{\bar w_h}{n}.\)

There are finitely many coordinates, each between zero and its type mass. Thus some subsequence converges to an allocation \(y\). Type-mass constraints and individual acceptability pass to the limit, and continuity of the wage sums gives \(W_h(y)\le b_h\).

It remains to prove stability.

A strict atomless blocker would yield a finite blocker

Suppose, for contradiction, that hospital \(h\) has a blocking alternative against \(y\).

Represent its selected submasses by \(z_{\theta,a,x}\), where the current assignment is \(a\) and the proposed contract is \(x\in X_\theta\) with \(x_H=h\). A coordinate is permitted only when either \(x=a\), retaining an incumbent, or \(x\succ_\theta a\). Disjointness means

\(\displaystyle z_{\theta,a,x}\ge0,\qquad \sum_xz_{\theta,a,x}\le y_{\theta,a}.\)

Let its wage and utility be

\(\displaystyle C=\sum_{\theta,a,x}w_xz_{\theta,a,x}\le b_h,\qquad V=\sum_{\theta,a,x}u_h(x)z_{\theta,a,x}>U_h(y).\)

Since \(U_h(y)\ge0\), we have \(V>0\). Choose \(t\) satisfying \(U_h(y)/V<t<1\). Scaling the alternative by \(t\) preserves a strict utility improvement and creates budget slack:

\(\displaystyle tV>U_h(y),\qquad tC\le tb_h<b_h.\)

For each permitted coordinate, select

\(\displaystyle k_{\theta,a,x}^{(n)}=\left\lfloor ntz_{\theta,a,x}\right\rfloor\)

clones currently assigned to \(a\), and assign them to the copied contract \(x\).

These selections are possible for all sufficiently large \(n\) along the convergent subsequence. Indeed, if \(y_{\theta,a}>0\), convergence and \(t<1\) imply \(y_{\theta,a}^{(n)}\ge ty_{\theta,a}\) eventually. Therefore,

\(\displaystyle \frac1n\sum_x k_{\theta,a,x}^{(n)}\le t\sum_xz_{\theta,a,x}\le ty_{\theta,a}\le y_{\theta,a}^{(n)}.\)

If \(y_{\theta,a}=0\), every corresponding selection coordinate is zero. Thus distinct clones can be selected for all proposed assignments. Their changes satisfy the inherited strict preferences.

The finite alternative’s wage is at most \(tC<b_h\le b_h^{(n)}\). Its utility before the perturbation converges to \(tV\), because there are finitely many coordinates and \(k_{\theta,a,x}^{(n)}/n\to tz_{\theta,a,x}\).

The current finite matching’s unperturbed utility is \(U_h(y^{(n)})\to U_h(y)\). Its total utility perturbation is at most \(M/n\): there are \(nM\) clones and each selected contract contributes an additional \(1/n^2\).

Since \(tV>U_h(y)\), the proposed finite alternative has strictly greater perturbed utility than the current finite matching for all sufficiently large \(n\). It also has positive mass, since its limiting utility is positive. It therefore blocks that matching, contradicting finite stability.

This proves the stronger existence claim.

3. Scope of the conclusion

For the problem exactly stated, both the optimum and an explicit optimal stable allocation are polynomial-time computable by the top-choice construction.

For the binding-budget variant, the limit argument proves zero-inflation existence and consequently settles the minimum-value and threshold questions there as well. It does not provide a polynomial-time construction of a stable allocation for that broader variant: expanding rational masses into clones can require arbitrarily many doctors.

⟨structured verdict parsed — rendered above⟩

The prover correctly resolves the intended stated problem: zero inflation admits a stable allocation, and that allocation is computable in polynomial time. The additional existence argument for the broader binding-budget model is also sound. The only issue is a minor clarification concerning the sign of budgets at hospitals with empty menus.

1. Scope and budget assumptions

The top-choice argument uses both explicit restrictions: total population mass is \(1\), and every wage offered by hospital \(h\) is at most \(b_h\). Its conclusion therefore follows from the actual input restrictions, rather than from an unintended interpretation of atomless stability.

Minor issue — budgets at hospitals with no contracts. The task does not explicitly impose \(b_h\ge 0\). For hospitals offering contracts, this follows from \(0<w_x\le b_h\). For hospitals offering none, it does not. The prover explicitly adopts nonnegative budgets in “As usual, budgets are nonnegative.”

This is the natural intended assumption and is a minor domain clarification under the prescribed verification standard. Nevertheless, without it, an empty-menu hospital with negative budget would violate zero-inflation feasibility.

Minimum clarification: State at the beginning that hospital budgets are interpreted as nonnegative, including those of hospitals offering no contracts.

2. Verification of the polynomial-time construction

2.1 Selecting each type’s favorite assignment

The assignment \(a_\theta\) is well-defined and unique because the preference order is strict and its domain is finite and includes \(\varnothing\).

Assigning mass \(\mu_\theta\) to this assignment and zero to every other assignment satisfies nonnegativity and the type-mass equality. If \(a_\theta\) is a contract, it is strictly preferred to \(\varnothing\), so individual acceptability holds.

Empty menus cause no difficulty: their favorite assignment is \(\varnothing\).

Assessment: Correct.

2.2 Budget feasibility

The displayed inequality is valid under the nonnegative-budget interpretation:

\[ W_h(y) \le b_h\sum_{\theta,x:x_H=h}y_{\theta,x} \le b_h\sum_\theta\mu_\theta =b_h. \]

The first inequality uses the wage bound separately for every offered contract. The second uses nonnegative allocation coordinates and the type-mass equalities; multiplying the resulting mass inequality by \(b_h\) preserves its direction because \(b_h\ge0\).

There is no assumption that a type has only one contract with a given hospital. The sum over all such contracts remains bounded by that type’s total mass.

Thus the assertion that every allocation satisfying the type-mass constraints is budget-feasible is correct, regardless of individual acceptability.

Assessment: Correct, subject only to the domain clarification above.

2.3 Absence of blocking alternatives

Every individual receives their type’s unique favorite assignment. Consequently, no changed contract can satisfy the required strict preference improvement.

A permissible alternative can therefore select only individuals already assigned to the same hospital contract it proposes retaining. Individuals unmatched or assigned elsewhere cannot be selected without a changed assignment.

The alternative can retain only submasses of incumbents. Since utility densities are nonnegative, its utility cannot exceed the hospital’s current utility. This excludes every strict utility improvement.

The argument also covers zero utility densities and hospitals with no incumbents. The positive-mass requirement creates no exception.

Assessment: Correct.

2.4 Optimum, threshold question, and running time

The construction establishes attainability at \(\delta=0\); the definition restricts inflation to nonnegative values. Therefore the asserted minimum follows.

For every permitted \(q\ge0\), the same allocation satisfies \(0\le\delta\le q\).

Scanning explicit preference orders takes polynomial time in the input size. Every output coordinate is either zero or an input rational mass. There are \(N+\tau\) coordinates, so their binary encoding has polynomial length. No discretization or expansion of binary-encoded masses is needed.

Assessment: Correct. Section 1 alone resolves all questions in USER_TASK.

3. Verification of the additional binding-budget claim

This section concerns a broader model and is unnecessary for the assigned result. It nevertheless contains a substantive argument that can be audited independently.

3.1 Cited finite-doctor theorem

The cited paper’s Theorem 5 supplies stability for hospital-specific budgets between the original budget and that budget plus the maximum individual wage. Its model permits multiple contracts per doctor, strict doctor preferences, additive hospital utilities, and positive wages bounded by the original hospital budget. Definition 1 permits retained contracts and requires strict doctor improvement for newly selected contracts. The prover’s stated application matches these conditions. [Kawase–Iwasaki, Definition 1 and Theorem 5](https://arxiv.org/pdf/1705.07643v5)

The copied utilities are strictly positive, so hospital acceptability is satisfied even when an original density is zero. Individual acceptability of the resulting matching is supported by the cited generalized deferred acceptance mechanism, whose doctor choices reject contracts below unmatched.

Assessment: The theorem application is verified.

3.2 Finite approximations

A common denominator \(D\) exists because there are finitely many rational masses. Taking positive multiples \(n\) of \(D\) makes all clone counts integral.

Strictly positive budgets and finitely many wage densities ensure that all copied wages \(w_x/n\) eventually satisfy the finite theorem’s wage bound.

The copied utility is

\[ \frac{u_h(x)+1/n}{n} =\frac{u_h(x)}n+\frac1{n^2}. \]

Thus both utility scaling and the stated perturbation size are correct. Aggregating clone assignments gives the stated mass equalities, acceptability constraints, and wage inequalities.

Assessment: Correct.

3.3 Passage to a feasible limit

The allocation vectors have a fixed finite number of coordinates and lie in a bounded, closed product of intervals. A convergent subsequence therefore exists.

The type-mass equalities and prohibited-assignment zero coordinates are preserved under convergence. The wage sums are continuous, and the excess bound tends to zero.

Assessment: Correct. The limit is individually acceptable and feasible at the original budgets.

3.4 Representation and scaling of a blocker

The coordinates \(z_{\theta,a,x}\) correctly describe selected disjoint submasses, including retained incumbents. Their supply constraints match the blocking definition.

From \(V>U_h(y)\ge0\), the ratio \(U_h(y)/V\) is defined and strictly less than \(1\). The specified choice of \(t\) therefore exists and preserves strict utility improvement.

Because the broader claim explicitly assumes \(b_h>0\), scaling creates strict budget slack:

\[ tC\le tb_h<b_h. \]

Assessment: Correct.

3.5 Availability of selected clones

For every positive limiting assignment mass, convergence and \(t<1\) imply eventual availability of at least the fraction \(t\) of that mass. Flooring each proposed clone count can only reduce demand.

For a zero limiting assignment mass, the supply constraint forces every corresponding blocker coordinate to vanish.

There are finitely many assignment groups, so the eventual availability assertions hold simultaneously along the subsequence. Distinct clones can therefore implement all selections without violating disjointness.

Assessment: Correct.

3.6 Finite blocking contradiction

The rounded alternative costs at most \(tC\), hence is feasible under the finite matching’s inflated budget.

Its unperturbed utility converges to \(tV\), whereas the current matching’s unperturbed utility converges to \(U_h(y)\). The current matching’s perturbation is at most \(M/n\), as claimed: at most \(nM\) assigned clones each contribute \(1/n^2\).

The alternative’s perturbation is nonnegative. Therefore the fixed strict limiting utility gap survives for sufficiently large \(n\). Positive limiting unperturbed utility also ensures that the alternative selects at least one clone eventually.

Retained contracts and strictly preferred changed contracts meet the finite blocking definition, contradicting finite stability.

Assessment: Correct. The broader zero-inflation existence claim follows. The prover appropriately does not claim that this limiting construction yields a polynomial-time allocation algorithm.

4. Overall assessment and actionable feedback

The target is settled by a direct, rigorous polynomial-time construction. The supplementary argument contains no major gap or false step.

The sole requested repair is to make the nonnegative-budget interpretation explicit at the outset. No additional lemma or new mathematical argument is needed.

⟨structured verdict parsed — rendered above⟩