Answer: Polynomial-time solvable (\(\mathrm{P}\)). Every \(K>0\) is feasible; for \(K=0\), feasibility holds exactly when \(x^B=x^G\).
Theorem 3.1 — class: other
Given finite supports of boy and girl types with rational masses summing to one on each side and strict rankings over opposite-side types, let \(x^G\) be the girl-proposing stable flow in the truthful market and \(A_g=\{b:x^G_{bg}>0\}\). For each girl type \(g\), choose strategic mass \(\lambda_g\in[0,\mu_g]\), split from its truthful mass, and have it blacklist boy types outside \(A_g\). Given a threshold \(K\), decide whether some choice with \(\sum_g\lambda_g\le K\) makes boy-proposing type-capacitated deferred acceptance on the split market return exactly \(x^G\).
Let \(B,G\) be nonempty finite supports of boy and girl types, with positive binary-rational masses \(\nu_b,\mu_g\) satisfying \(\sum_b\nu_b=\sum_g\mu_g=1\). Every type has a complete strict ranking of opposite-side types, all preferred to being unmatched. A society is given by its support: the list of its \(\tau\) positive-mass types and their binary-rational masses; \(\tau\) is the support size, not the number of possible types. Here set \(\tau=|B|+|G|\), \(m=\max\{|B|,|G|\}\), and let \(L\) be the total input bit length.
A feasible flow assigns nonnegative mass to acceptable pairs, with incident totals bounded by the corresponding type masses and no additional pair capacities. An acceptable pair blocks if each endpoint has either unmatched mass or positive mass assigned to a strictly worse partner; a stable flow has no blocking pair.
Mass deferred acceptance starts empty: an input-order-first proposer with free mass offers all that mass to its highest-ranked acceptable receiver that has not rejected it; receivers retain their best offered mass up to capacity and reject the rest. Partial rejection sends only the rejected mass onward; held mass remains until displaced. Stop when no further proposal is possible. Let \(x^G\) be the truthful girl-proposing outcome and \(A_g=\{b:x^G_{bg}>0\}\).
Choose real strategic masses \(0\le\lambda_g\le\mu_g\). Replace each girl type by truthful and strategic copies of masses \(\mu_g-\lambda_g\) and \(\lambda_g\), omitting zero-mass copies. The truthful copy accepts all boys; the strategic copy accepts exactly \(A_g\); both preserve the original boy ranking. Boys preserve their ordering of original girl types, placing the truthful copy immediately before the strategic copy within each type. Run boy-proposing mass deferred acceptance, and aggregate both copies' flows to obtain \(y_{bg}\).
Given a nonnegative binary-rational threshold \(K\), is deciding whether some \(\lambda\) satisfies \(\sum_g\lambda_g\le K\) and \(y_{bg}=x^G_{bg}\) for every \((b,g)\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\).
Discrete winning coalitions are exactly those intersecting every minimal rotation's girl set, where these rotations are the cyclic partner changes from immediate upper covers of the girl-optimal matching in the boy-preference order; a minimum coalition is computable in \(O(n^2)\) time for \(n\) agents per side. [Ndiaye–Norin–Vetta](https://arxiv.org/html/2007.15748v2)
For fixed continuous capacities, finding a stable allocation admits a strongly polynomial algorithm. [Baïou–Balinski](https://pubsonline.informs.org/doi/10.1287/moor.27.3.485.310) No result settling exactly the strategic-mass decision problem above was located.
The decision problem is in \(\mathrm{P}\). More precisely, writing \(x^B\) for truthful boy-proposing mass DA,
\(\displaystyle \text{YES}\quad\Longleftrightarrow\quad K>0\ \text{or}\ \bigl(K=0\ \text{and}\ x^B=x^G\bigr).\)
The key fact is that every rational choice satisfying \(0<\lambda_g<\mu_g\) for every girl type forces the target outcome. Thus arbitrarily small positive budgets suffice. The stipulated ordering of truthful before strategic copies is essential to the proof.
A conservative worst-case bound is \(O(m^2\tau^3)\) arithmetic operations and \(O(m^2\tau^3L^2)\) bit operations. The positive-budget branch takes \(O(L)\) time.
We first establish the property of DA needed below, including its applicability to partial rejections.
Consider any finite market with proposer quotas \(a_p\), receiver quotas \(c_q\), strict rankings, and no pair capacities. For a flow \(v\), define the proposer’s preference-prefix mass by
\(\displaystyle C_p(v;q)=\sum_{r\succeq_p q}v_{pr}.\)
Lemma 1. With rational quotas, the specified mass DA terminates at a stable flow \(h\). For every stable flow \(z\) in that market,
\(\displaystyle C_p(h;q)\ge C_p(z;q)\)
for every proposer \(p\) and acceptable receiver \(q\). Consequently its outcome is independent of the proposal order.
Proof. We maintain artificial bounds \(u_{pq}\), initially \(a_p\) on every acceptable pair. Whenever receiver \(q\) rejects any mass of proposer \(p\), set \(u_{pq}\) equal to the mass of \(p\) that \(q\) retains after that proposal.
Once a receiver has rejected a proposer, that proposer sends no new mass there. Consequently, on a previously rejected pair, \(u_{pq}\) always equals the currently held mass.
We prove the invariant that every stable flow \(z\) satisfies \(z_{pq}\le u_{pq}\). Initially this follows from the proposer quota.
At a current state, let \(r_p\) be the allocation obtained by greedily filling quota \(a_p\), in preference order, subject only to the current bounds \(u_{pq}\). For every flow \(z\) satisfying those bounds and the proposer quota,
\(\displaystyle C_p(z;q)\le \min\left\{a_p,\sum_{r\succeq_p q}u_{pr}\right\}=C_p(r_p;q).\)
All receivers preceding the proposer’s current proposal position have already rejected it. Their bounds equal their held masses. Thus \(r_p\) consists of its held row together with all its free mass placed at its next un-rejected receiver, if such a receiver exists.
Suppose a proposal is made to \(q\), and let \(\widehat h_{pq}\) denote the offered masses there before trimming. For every proposer,
\(\displaystyle \widehat h_{pq}\le r_{pq}.\)
If \(q\) rejects some mass of \(p\), its retained mass is
\(\displaystyle \bar h_{pq}=\max\left\{0,c_q-\sum_{s\succ_q p}\widehat h_{sq}\right\}.\)
Suppose, contrary to the invariant we want to preserve, that a stable flow \(z\) has \(z_{pq}>\bar h_{pq}\). Receiver feasibility then implies that some proposer \(s\succ_q p\) satisfies
\(\displaystyle z_{sq}<\widehat h_{sq}\le r_{sq}.\)
Indeed, otherwise the mass of proposers preferred to \(p\), together with \(z_{pq}\), would exceed \(c_q\).
The prefix inequality above now gives
\(\displaystyle C_s(z;q) \le \sum_{r\succ_s q}r_{sr}+z_{sq} < C_s(r_s;q) \le a_s. \)
Therefore proposer \(s\) has either unmatched mass or positive mass assigned below \(q\) in \(z\). Receiver \(q\) has positive mass \(z_{pq}\) assigned to the strictly worse proposer \(p\). Hence \((s,q)\) blocks \(z\), a contradiction. Updating every rejected pair’s bound therefore preserves the invariant.
For termination, choose a common denominator \(D\) for the rational quotas. Every held mass and bound remains a multiple of \(1/D\). Each proposal involving a rejection strictly decreases at least one bound by at least \(1/D\). The sum of the bounds is finite and nonnegative, so there are finitely many such proposals. A proposal without rejection exhausts its proposer’s free mass and creates no new free mass; therefore only finitely many proposals can occur between rejection events.
At termination, the greedy row \(r_p\) equals the held row \(h_p\): either the proposer has no free mass, or its list is exhausted. The invariant and the prefix inequality prove the asserted dominance over every stable \(z\).
Finally, suppose \((p,q)\) blocked \(h\). Since \(p\) has free mass or mass assigned below \(q\), it must previously have been rejected by \(q\). At that rejection, \(q\) became full with partners weakly preferred to \(p\), and subsequent proposals can only improve its retained partners. Thus \(q\) cannot have unmatched mass or a strictly worse partner. This contradiction proves stability.
Two DA outcomes each dominate the other in every preference prefix. Their rows, and hence their flows, must coincide. \(\square\)
In the original complete market, every stable flow matches all mass. Otherwise, equality of the two sides’ total masses would leave unmatched mass on both sides, producing a blocking pair.
In particular,
\(\displaystyle \sum_g x^G_{bg}=\nu_b,\qquad \sum_b x^G_{bg}=\mu_g.\)
Let \(x=x^G\), and define its support graph
\(\displaystyle H_x=\bigl(B\cup G,\{bg:x_{bg}>0\}\bigr).\)
Lemma 2. The graph \(H_x\) is a forest.
Proof. Suppose its support contains a simple cycle. Every cycle vertex strictly prefers one of its two incident cycle edges.
No edge can be preferred by both its endpoints: both would then have positive mass on their other, strictly worse cycle edges, so that pair would block \(x\).
A cycle has equally many vertices and edges. Each vertex selects one preferred edge, and no edge is selected twice. Consequently every edge is selected exactly once. Following these selections around the cycle shows that the girls’ preferred edges form one alternating matching of the cycle, and the boys’ preferred edges form the other.
Choose a positive rational \(\delta\) smaller than every mass on a cycle edge. Increase the girls’ preferred alternating edges by \(\delta\), and decrease the other alternating edges by \(\delta\). Call the resulting flow \(x'\).
Every incident total is unchanged, and every previously positive edge remains positive. Stability depends only on incident totals and on which edges carry positive mass: these determine unmatched mass and the existence of strictly worse partners. Thus \(x'\) remains stable.
Each girl on the cycle transfers \(\delta\) from a worse boy to a better boy, so at least one of her preference-prefix masses strictly increases. This contradicts Lemma 1 applied to girl-proposing DA, whose outcome \(x\) dominates every stable flow in every girl’s preference prefix. \(\square\)
We will also use the following elementary consequence.
Lemma 3. A flow supported on a forest is uniquely determined by its incident totals.
Proof. The difference of two such flows has incident sum zero at every vertex. At a leaf, its sole incident edge must therefore have difference zero. Remove that edge and repeat. This eliminates every edge of the forest. \(\square\)
Fix rational masses \(0<\lambda_g<\mu_g\). Denote the two copies by \(g^t\) and \(g^s\).
Construct a flow \(z\) in the copied market as follows. For each girl \(g\), give the truthful copy the best \(\mu_g-\lambda_g\) mass from her target column \(x_{\cdot g}\), in her boy ranking. Give the remaining \(\lambda_g\) mass to the strategic copy.
This construction fills both copies, preserves every boy’s total, and aggregates to \(x\). The strategic copy receives only boys in \(A_g\), so its assignments are acceptable.
The prefix construction has this useful property:
If \(z_{b,g^s}>0\), every boy assigned to \(g^t\) is weakly preferred by \(g\) to \(b\).
Lemma 4. The lifted flow \(z\) is stable in the copied market.
Proof. Suppose an acceptable pair consisting of boy \(b\) and a copy of \(g\) blocks \(z\).
If \(b\)’s willingness comes from mass assigned to an original girl type strictly below \(g\), then \(b\) is willing to trade with \(g\) in \(x\). Stability of \(x\) implies that every boy in \(g\)’s target column is weakly preferred to \(b\). Both copies contain only boys from that column, are full, and therefore are unwilling to trade with \(b\).
The only remaining source of willingness introduced by copying is that \(b\) holds positive mass at \(g^s\) and prefers \(g^t\). But the prefix property says that \(g^t\) holds no boy strictly worse than \(b\). It is full, so this pair cannot block either. \(\square\)
Run boy-proposing DA in this copied market. Let \(h\) be its flow before aggregation and \(y\) its aggregation.
By Lemmas 1 and 4, every boy’s allocation in \(h\) dominates its allocation in \(z\) in every copied preference prefix. Since every boy is fully matched in \(z\), every boy is fully matched in \(h\).
The total receiver capacity is also \(1\). Thus every receiver copy is full. In particular, each strategic copy holds its positive mass \(\lambda_g\).
Aggregating the boy-prefix inequalities at boundaries between original girl types gives
\(\displaystyle \sum_{r\succeq_b g}y_{br} \ge \sum_{r\succeq_b g}x_{br}. \)
We now prove that \(y\) uses only target-support edges.
Suppose \(y_{bg}>0\) but \(x_{bg}=0\). Let \(w_b\) be boy \(b\)’s worst positive-mass partner in \(x\). The prefix inequality at \(w_b\) implies that \(y\) assigns no mass below \(w_b\). Since \(x_{b,w_b}>0\), our new girl type \(g\) differs from \(w_b\), and therefore \(b\) strictly prefers \(g\) to \(w_b\).
Consequently \(b\) is willing to trade with \(g\) in \(x\). Stability of \(x\), together with \(x_{bg}=0\), implies that every boy in \(A_g\) is strictly preferred by \(g\) to \(b\).
The new mass \(y_{bg}>0\) must be held by \(g^t\), because \(g^s\) accepts only \(A_g\). Since \(g^s\) is full and has positive capacity, some boy \(c\in A_g\) satisfies \(h_{c,g^s}>0\).
Boy \(c\) prefers \(g^t\) to \(g^s\). The truthful copy holds positive mass of \(b\), whom it strictly ranks below \(c\). Thus \((c,g^t)\) blocks \(h\), contradicting Lemma 1.
We have proved
\(\displaystyle y_{bg}>0\ \Longrightarrow\ x_{bg}>0.\)
Both \(y\) and \(x\) have the same full incident totals. Their common containing support graph \(H_x\) is a forest by Lemma 2. Lemma 3 therefore yields
\(\displaystyle y=x=x^G.\)
This proves the claimed sufficiency of every rational vector with \(0<\lambda_g<\mu_g\).
If \(K>0\), set
\(\displaystyle \varepsilon=\min\{K/2,1/2\},\qquad \lambda_g=\varepsilon\mu_g.\)
These are rational masses satisfying
\(\displaystyle 0<\lambda_g<\mu_g,\qquad \sum_g\lambda_g=\varepsilon\le K.\)
Section 4 proves that their aggregated outcome equals \(x^G\). Thus the algorithm immediately answers YES. This branch requires only reading the input, taking \(O(L)\) time; the witness itself has polynomial encoding length.
If \(K=0\), nonnegativity forces every \(\lambda_g=0\). The copied market is then exactly the truthful original market. Hence feasibility holds exactly when \(x^B=x^G\).
For this branch, compute the two proposer-optimal stable allocations using the corrected Baïou–Balinski algorithms. Their inductive algorithm finds a stable allocation, and their row/column-optimal algorithms find the two optima; the relevant bounds are Theorem 2 and Corollary 4. Their optimality order implies cumulative dominance—mass gains precede mass losses in preference order—so Lemma 1 identifies these optima with the specified DA outcomes. [Baïou–Balinski, corrected paper](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302)
The hypotheses apply: the market is finite, rankings are strict, quotas are positive rational numbers, and every pair can be given the redundant capacity \(2\), which never binds because total mass is \(1\).
For an explicit conservative implementation bound, put \(p=|B|\), \(q=|G|\), and \(E=pq\). The cited algorithms have \(O(E+\tau)\) allocation changes or terminal stages. Their search paths have \(O(\tau)\) vertices. Recomputing preference-prefix sums and scanning edges at each path step costs at most \(O(E\tau)\) arithmetic operations per stage. Thus computing both outcomes takes
\(\displaystyle O\bigl(E(E+\tau)\tau\bigr)\subseteq O(m^2\tau^3)\)
arithmetic operations. Comparing them costs another \(O(E)\).
After clearing input denominators, these algorithms use additions, subtractions, comparisons, and minima on integers of \(O(L)\) bits. Including denominator conversion, schoolbook arithmetic gives the conservative bit bound
\(\displaystyle O(m^2\tau^3L^2).\)
These bounds depend on the numbers of positive-mass types, with no expansion into individual agents.
Therefore the target decision problem is polynomial-time solvable. The infimum successful strategic mass is always zero; it is attained precisely when \(x^B=x^G\).
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and resolves the decision problem. I found no false mathematical step or missing substantive lemma. One minor clarification is needed in the identification of the cited optimal allocations with the specified DA outcomes.
The established criterion is
\[
\mathrm{YES}\iff K>0\ \text{or}\ \bigl(K=0\ \text{and}\ x^B=x^G\bigr).
\]
The artificial-bound invariant is valid. Initially, every stable flow satisfies \(z_{pq}\le a_p=u_{pq}\). After a pair has rejected mass, its held mass can only decrease: the proposer never sends additional mass to that pair. Updating its bound to the retained mass therefore maintains the stated relationship between bounds and holdings.
The greedy-row description is consistent with partial rejection. Before the current proposal position, rejected pairs retain exactly their current bounds. Remaining free mass is placed at the first receiver that has not rejected the proposer. Retained mass at earlier receivers is preserved. Thus the claimed description of \(r_p\) follows from the specified algorithm.
The rejection argument checks out. When \(q\) rejects mass from \(p\), the displayed expression for \(\bar h_{pq}\) is valid because rejection means the offered mass exceeds the residual capacity after better proposers are retained. If \(z_{pq}>\bar h_{pq}\), receiver feasibility forces some better proposer \(s\) to satisfy \(z_{sq}<\widehat h_{sq}\).
The subsequent strict inequality is justified by applying the greedy prefix bound to the receivers strictly above \(q\), then adding \(z_{sq}<r_{sq}\). It establishes \(C_s(z;q)<a_s\), exactly the condition that \(s\) has unmatched mass or mass below \(q\). Together with \(z_{pq}>0\), this produces the claimed blocking pair.
Termination is proved for rational quotas. All operations preserve multiples of the common denominator. Every rejection strictly decreases a bound, while a proposal without rejection exhausts one proposer’s free mass without creating new free mass. The argument proves finite termination; it does not claim a polynomial bound for this direct DA implementation.
Stability and order independence follow. A receiver that has rejected a proposer remains full and retains only partners weakly preferred to that proposer. This rules out the proposed terminal blocking pair. Mutual prefix dominance then determines every row entry by successive prefix differences.
There is no substantive gap in Lemma 1.
The argument uses both necessary hypotheses: complete acceptability and equal total mass. If any mass were unmatched, both sides would have unmatched mass, yielding a blocking pair.
Consequently, all target row and column totals equal their prescribed masses. This also ensures that every \(A_g\) is nonempty.
Each cycle vertex selects its preferred incident cycle edge. An edge selected by both endpoints would block, since both endpoints have positive mass on their other, worse cycle edges.
The counting argument is correct: equally many vertices and edges, together with no double selection, implies exactly one selection per edge. On a simple cycle, these selections give the two opposing alternating matchings described in the proof.
The perturbation preserves feasibility, all incident totals, and the entire positive support. In this market without pair capacities, those data determine whether a pair blocks. Hence stability is preserved.
Every affected girl gains a strict preference prefix, contradicting the girl-prefix optimality established in Lemma 1. Rationality of the perturbation is available because the DA target has rational entries.
Lemma 2 is correct.
The leaf-removal argument is valid. Equal incident totals force the difference on a leaf’s edge to vanish, and iteration eliminates every edge. Isolated vertices cause no difficulty.
The construction fills both copies, preserves boy totals, and assigns only acceptable partners to strategic copies.
The blocking-pair analysis is exhaustive because boys are fully matched in \(z\). A boy’s willingness must come either from a worse original girl type or from the strategic copy of the same type.
In the first case, original stability prevents either full copy from holding a strictly worse boy. In the second case, the truthful copy’s prefix construction prevents it from holding a boy strictly worse than the boy assigned to the strategic copy.
Lemma 4 is correct.
Applying Lemma 1 to the stable lift correctly establishes that every boy is fully matched in \(h\). Since total receiver capacity equals total matched mass, every receiver copy is full.
Aggregation at original-type boundaries preserves the required boy-prefix inequalities.
For a hypothetical new edge \(bg\), the inequality at \(b\)’s worst target partner excludes any assignment below that partner. Since \(bg\) is absent from the target, \(g\) must be strictly better. Original stability therefore implies that every boy in \(A_g\) is strictly preferred to \(b\).
The new edge must belong to the truthful copy. The strategic copy’s positive capacity and fullness supply a boy \(c\in A_g\) with positive strategic assignment. The stipulated truthful-before-strategic ordering makes \(c\) willing to move, while the truthful copy prefers \(c\) to its positively assigned boy \(b\). This is a valid blocking contradiction.
Thus \(y\) is supported on the target forest. Equal incident totals and Lemma 3 then give \(y=x^G\).
This establishes precisely the rational sufficiency claimed. A claim covering all real strategic vectors is unnecessary for the existential decision problem.
For \(K>0\), the proposed \(\varepsilon\) satisfies \(0<\varepsilon\le 1/2\) and \(\varepsilon\le K\). Hence every proposed \(\lambda_g\) is strictly between zero and \(\mu_g\), and the budget constraint holds. The witness has polynomial encoding length.
For \(K=0\), nonnegativity forces the unique vector \(\lambda=0\), so the comparison \(x^B=x^G\) is necessary and sufficient.
The corrected paper supports the algorithmic claims: Theorem 2 bounds the inductive algorithm by \(3E+q\) allocations; Theorem 10 establishes the unique side-optimal allocations; Corollary 4 bounds the optimality algorithm by \(2pq\) stable allocations. These results apply to the stated finite, strict-preference market with redundant pair capacities. Their path constructions also support the conservative per-stage accounting. [Corrected Baïou–Balinski paper](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302)
The displayed arithmetic bound is consistent with \(E\le m^2\) and \(E+\tau=O(\tau^2)\). Clearing denominators yields integers with \(O(L)\) bits; the stated operations preserve that denominator and bounded allocation values. The conservative bit bound is therefore consistent.
Minor issue — the optimality-order identification is not stated precisely. The output says that “mass gains precede mass losses,” but does not define the cited preference relation. It also cites the stage-count results without explicitly identifying Theorem 10 as the correctness result for computing both optima.
Minimum clarification: state the cited preference relation formally, identify Theorem 10, and explicitly connect that relation to cumulative dominance for the fully matched original market. External verification confirms the application; this is an expositional omission requiring no new mathematics.
The positive-budget argument, zero-budget characterization, and polynomial-time conclusion stand. No blocking issue remains.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.