Answer: \(\mathrm{NP}\text{-hard}\)
Corollary 2 — class: algorithmic
Given finite supported proposer and receiver type sets \(I,J\), positive rational masses \(a_i,b_j\) each summing to \(1\), strict rankings over opposite-side types, and designated positive-mass types \(i^\star,j^\star\), compute a strict ranking reported by all of type \(i^\star\) and the resulting rational fluid deferred-acceptance matching \(x\). In each round, unheld proposer mass advances to its next ranked receiver type, and each receiver type holds its highest-ranked incoming mass up to capacity \(b_j\), rejecting excess. Minimize \(S_{j^\star}(x)=\sum_i x_{ij^\star}s_{j^\star}(i)/b_{j^\star}\), subject to \(R_{i^\star}(x)=\sum_j x_{i^\star j}r_{i^\star}(j)/a_{i^\star}\le R_{i^\star}(x^0)\), where \(x^0\) is the truthful fluid deferred-acceptance outcome; determine whether this exact optimization is solvable in \(\operatorname{poly}(|I|+|J|,L)\) time, for input bit length \(L\).
Let \(I,J\) be nonempty finite proposer and receiver type supports, with positive binary rational masses \(a_i,b_j\) satisfying \(\sum_i a_i=\sum_j b_j=1\). A society is given by its support: only types of positive mass are listed; \(\tau=|I|+|J|\) is the support size, not the number of possible preference types. Set \(m=\max\{|I|,|J|\}\), and let \(L\) be the total input bit length.
Each type has a strict total ranking of all opposite-side types, all acceptable. Let \(r_i(j)\in\{1,\ldots,|J|\}\) and \(s_j(i)\in\{1,\ldots,|I|\}\) be positions in the true rankings, with position \(1\) best. Fix designated types \(i^\star\in I\) and \(j^\star\in J\).
Fluid proposer-side deferred acceptance starts with all mass unheld. In simultaneous rounds, each unheld portion proposes to its next receiver in its reported ranking; each receiver pools new proposals with previously held mass, retains its highest-ranked proposer mass up to capacity \(b_j\), and rejects the excess. Mass at a cutoff type is divisible; only rejected portions advance next round, and a previously displaced portion resumes after the receiver that rejected it. Stop when no proposals remain.
The outcome \(x_{ij}\ge0\) is the rational mass held between types, with \(\sum_jx_{ij}=a_i\) and \(\sum_ix_{ij}=b_j\). Write \(x^0\) for the truthful outcome. All mass of \(i^\star\) must report one common strict total ranking of \(J\); all other reports remain truthful, and truthful reporting is allowed.
Compute a report and its resulting outcome minimizing \(S_{j^\star}(x)=\sum_i x_{ij^\star}s_{j^\star}(i)/b_{j^\star}\), subject to \(R_{i^\star}(x)=\sum_jx_{i^\star j}r_{i^\star}(j)/a_{i^\star}\le R_{i^\star}(x^0)\).
Is this exact optimization solvable in \(\operatorname{poly}(m,\tau,L)\) time, or is it NP-hard?
For discrete one-to-one matching with strict complete preferences and a fixed accomplice–beneficiary pair, an optimal permutation report preserving the accomplice’s truthful partner is computable in \(O(n^3)\) time, where \(n\) is the number of agents on each side ([source](https://arxiv.org/pdf/2012.04518)).
No result settling the exact fluid optimization defined here was located in the literature search.
The exact optimization is NP-hard, even with positive dyadic masses, strict complete rankings, and one designated accomplice–beneficiary pair. Its rational-threshold decision version is also NP-complete.
The reduction below is from Subset Sum. Its main ingredient is a receiver capacity that absorbs the first half of an item’s displaced mass. The beneficiary gains only from the remaining half. Equality in a resulting bound forces every item to be selected completely or not at all.
We use two established facts about bipartite stable allocation with strict rankings and rational vertex quotas:
These are covered by Lemma 1 and Section 3 of [Dean and Munshi, *Faster Algorithms for Stable Allocation Problems*](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
The hypotheses apply here: the graph is bipartite, quotas are rational, and rankings are strict. Edge capacities can be set to the redundant bounds \(\min\{a_i,b_j\}\). Simultaneous pooling implements the same proposal-and-rejection operation; proposals at a receiver can be serialized because retaining its highest-ranked mass depends only on the pooled mass.
Consequently, we may verify the truthful outcome and a witnessing report using convenient sequential proposal schedules. We do not assume that literal round-by-round simulation runs in polynomial time.
All construction calculations initially use unnormalized quotas. Uniform scaling preserves DA and both average-rank scores. Section 7 converts the construction to positive dyadic masses summing to one.
Take a Subset Sum instance with positive binary integers \(\nu_1,\ldots,\nu_n\) and target \(T>0\), where \(n\ge 2\). The question is whether some subset \(F\subseteq\{1,\ldots,n\}\) satisfies
\[ \sum_{i\in F}\nu_i=T. \]
Define
\[ c_i=i+2,\qquad w_i=\frac{\nu_i}{c_i},\qquad M=\sum_{i=1}^n w_i,\qquad g=\frac{T}{5}. \]
There are proposer types \(p,u,v,q_1,\ldots,q_n,t_1,\ldots,t_n,d\), with quotas
| Proposer | Quota |
|---|---:|
| \(p\) | \(M+4g\) |
| \(u,v\), each | \(2g\) |
| \(q_i\) | \(w_i\) |
| \(t_i\) | \(w_i/2\) |
| \(d\) | \(M\) |
The designated accomplice is \(p\).
There are receiver types \(A,B,H,C,D,X_1,\ldots,X_n,Y_1,\ldots,Y_n,J\), with capacities
| Receiver | Capacity |
|---|---:|
| \(A,B\), each | \(g\) |
| \(H\) | \(M\) |
| \(C\) | \(2g\) |
| \(D\) | \(4g\) |
| \(X_i\) | \(w_i\) |
| \(Y_i\) | \(w_i/2\) |
| \(J\) | \(M\) |
The designated beneficiary is \(J\). Both sides have total quota
\[ \frac{7}{2}M+8g. \]
The accomplice’s true ranking is
\[ A\succ B\succ H\succ C\succ D \succ X_1\succ\cdots\succ X_n \succ Y_1\succ\cdots\succ Y_n\succ J. \]
In particular,
\[ r_p(H)=3,\qquad r_p(X_i)=i+5=3+c_i. \]
All other proposers have the following ranking prefixes:
| Proposer | Ranking prefix |
|---|---|
| \(u\) | \(D\succ A\succ C\succ B\) |
| \(v\) | \(C\succ B\succ A\succ D\) |
| \(q_i\) | \(X_i\succ Y_i\succ J\) |
| \(t_i\) | \(Y_i\succ H\) |
| \(d\) | \(J\succ H\) |
Receiver ranking prefixes are:
| Receiver | Ranking prefix |
|---|---|
| \(A\) | \(u\succ v\succ p\) |
| \(B\) | \(v\succ p\succ u\) |
| \(C\) | \(u\succ p\succ v\) |
| \(D\) | \(v\succ p\succ u\) |
| \(X_i\) | \(p\succ q_i\) |
| \(Y_i\) | \(q_i\succ t_i\) |
| \(H\) | all \(t_i\) and \(d\), then \(p\) |
| \(J\) | \(q_n\succ\cdots\succ q_1\succ t_1\succ t_2\succ d\) |
Complete every prefix by appending all omitted types in an arbitrary strict order. Thus all types are acceptable. At \(H\), every omitted proposer is below \(p\); at \(J\), every omitted proposer is below \(d\).
The beneficiary’s ranks satisfy
\[ s_J(d)=n+3,\qquad s_J(d)-s_J(q_i)=i+2=c_i. \]
If types are required to have distinct rankings, choose different bottom tails for \(B\) and \(D\); their displayed prefixes are the only repeated receiver prefixes. This does not affect the argument.
Write \(h\) for an unnormalized DA outcome.
Fix any common permutation report by \(p\), and put
\[ x_i=h_{pX_i}. \]
We establish properties that hold independently of that report.
Receiver \(X_i\) ranks \(p\) first and \(q_i\) second. Consequently,
\[ 0\le x_i\le w_i, \]
and \(q_i\) is displaced from \(X_i\) by exactly \(x_i\). It next proposes to \(Y_i\), where it has highest priority. Hence the eventual allocations are
\[ \begin{aligned} h_{q_iX_i}&=w_i-x_i,\\ h_{q_iY_i}&=\min\{x_i,w_i/2\},\\ h_{q_iJ}&=(x_i-w_i/2)_+, \end{aligned} \]
where \(z_+=\max\{z,0\}\).
Here is a justification that these routes cannot spill into their unspecified tails. Start all non-accomplice proposers before processing \(p\), which is permitted by schedule independence. Initially \(q_i,t_i,d\) fill \(X_i,Y_i,J\), respectively.
During the subsequent execution, the mass of \(p\) retained at \(X_i\) never decreases, because \(p\) has highest priority there. If its current value is \(e_i\), at most
\[ \min\{e_i,w_i/2\} \]
of \(t_i\) has been displaced toward \(H\), and at most
\[ (e_i-w_i/2)_+ \]
of \(q_i\) has advanced toward \(J\). Total \(q_i\)-mass reaching \(J\) is at most \(M\), so \(J\) can retain all of it ahead of \(d\). The mass of \(d\) displaced toward \(H\) is at most that incoming \(q_i\)-mass.
Thus total \(t_i\)- and \(d\)-mass reaching \(H\) is at most
\[ \sum_i\left( \min\{e_i,w_i/2\}+(e_i-w_i/2)_+ \right) =\sum_i e_i\le M. \]
All this mass has priority over every other proposer at \(H\), so it is retained. These bounds give an induction over proposals: none of \(q_i,t_i,d\) ever reaches an unspecified tail. In particular, the two \(t_i\) types ranked above \(d\) at \(J\) never propose there.
At termination, therefore,
\[ h_{t_iH}=\min\{x_i,w_i/2\},\qquad h_{dH}=\sum_i(x_i-w_i/2)_+. \]
Their combined mass at \(H\) is exactly \(\sum_i x_i\).
Receivers \(Y_i\) and \(J\) remain full of these designated types and retain no mass of \(p\).
No item proposer reaches these four receivers.
Proposer \(u\) has highest priority at \(A\) and \(C\), whose combined capacity is \(3g\), exceeding its entire quota \(2g\). After any rejection at \(D\), these receivers retain all its remaining mass. Thus \(u\) never reaches \(B\), and all its mass remains local.
Proposer \(v\) has highest priority at \(B\) and \(D\). In particular, \(D\) has capacity \(4g\), exceeding \(v\)’s entire quota. Thus \(v\) also remains local.
Since the four local receivers are full, their total capacity \(8g\) consists of \(4g\) from \(u,v\) and exactly \(4g\) from \(p\). Consequently,
\[ h_{pH}=M-\sum_i x_i. \]
Define the local cost relative to assigning the same mass to \(H\):
\[ \Delta=-2h_{pA}-h_{pB}+h_{pC}+2h_{pD}. \]
We prove
\[ \boxed{\Delta\ge g.} \]
Let
\[ a=h_{uA},\quad d_0=h_{uD},\quad z=h_{vA},\quad c=h_{vC},\quad b=h_{vB}. \]
Because \(u\) has no allocation at \(B\),
\[ h_{uC}=2g-a-d_0. \]
Because \(v\) proposes first to \(C\), then to \(B\), where it has highest priority,
\[ b=\min\{2g-c,g\}, \qquad h_{vD}=2g-z-b-c. \]
Subtracting the \(u,v\) allocations from the four capacities gives
\[ \Delta =g+3a+4z+3b+c-d_0. \]
We have \(d_0\le 2g\). Also \(3b+c\ge 2g\): if \(c\le g\), then \(b=g\); if \(c\ge g\), then \(b=2g-c\), so
\[ 3b+c=6g-2c\ge 2g. \]
Since \(a,z\) are nonnegative, the claimed bound follows.
Under truthful reporting, the item types stay at their initial receivers. The remaining truthful allocations are
\[ h^0_{pH}=M,\qquad h^0_{pC}=2g,\qquad h^0_{pD}=2g, \]
\[ h^0_{uD}=2g,\qquad h^0_{vA}=h^0_{vB}=g. \]
To verify this, initially hold \(u\) at \(D\), \(v\) at \(C\), and all item types at their first choices. Process \(p\) in its truthful order. It is initially retained by \(A,B\), then fills \(H\), and sends \(2g\) to \(C\). This displaces \(v\), which takes \(B\) and \(A\), displacing the \(2g\) of \(p\) held there. Those portions pass the already full \(H,C\) and are retained at \(D\) alongside \(u\).
The truthful total true-rank cost of \(p\) is consequently
\[ C_p^0=3(M+4g)+6g. \]
For an arbitrary report, Section 3 gives the exact identity
\[ C_p(h) =\sum_j r_p(j)h_{pj} =3(M+4g)+\Delta+\sum_i c_i x_i. \]
The average-rank no-regret constraint compares these total costs, since the accomplice’s quota is fixed. Using \(\Delta\ge g\), every feasible report satisfies
\[ \sum_i c_i x_i\le 5g=T. \]
Thus
\[ \boxed{\text{No regret implies }\sum_i c_i x_i\le T.} \]
Truthfully, \(J\) holds only \(d\), so its average rank is \(n+3\).
Under any report, the beneficiary’s improvement in its unnormalized rank sum is
\[ P(h)=\sum_i c_i(x_i-w_i/2)_+. \]
Indeed, \(q_i\) replaces precisely \((x_i-w_i/2)_+\) of \(d\), and its rank advantage over \(d\) is \(c_i\). Hence
\[ S_J(h)=n+3-\frac{P(h)}{M}. \]
For every \(x\in[0,w]\),
\[ (x-w/2)_+\le \frac{x}{2}, \]
with equality exactly when \(x=0\) or \(x=w\). Therefore every no-regret report satisfies
\[ P(h) \le \frac12\sum_i c_i x_i \le \frac{T}{2}. \]
Set the decision threshold to
\[ \theta=n+3-\frac{T}{2M}. \]
Suppose a no-regret report attains \(S_J(h)\le\theta\). Then \(P(h)\ge T/2\), so equality must hold throughout the preceding inequalities. All \(c_i\) are positive; consequently,
\[ x_i\in\{0,w_i\}\quad\text{for every }i, \qquad \sum_i c_i x_i=T. \]
Thus the set \(F=\{i:x_i=w_i\}\) satisfies
\[ \sum_{i\in F}\nu_i =\sum_{i\in F}c_iw_i =T. \]
A successful fluid report therefore yields a Subset Sum solution.
Conversely, suppose \(F\) satisfies \(\sum_{i\in F}\nu_i=T\). Let
\[ W=\sum_{i\in F}w_i\le M. \]
Have \(p\) report the selected \(X_i\) first, followed by
\[ A\succ B\succ H\succ D\succ C, \]
and then all remaining receivers in any strict order.
We verify its outcome with a sequential DA schedule. First place all other proposers at their first choices. For each selected \(X_i\), process \(p\)’s proposal and the resulting rejection chain:
After these chains, \(H\) holds \(W\) of higher-priority mass. Next, \(A,B\) each retain \(g\) of \(p\); \(H\) retains \(M-W\) of \(p\); and \(D\) retains its remaining \(2g\) alongside \(u\). All mass is now held.
Thus
\[ h_{pA}=h_{pB}=g,\qquad h_{pC}=0,\qquad h_{pD}=2g, \]
so \(\Delta=g\), while \(x_i=w_i\) exactly for selected items. Its total true-rank cost is
\[ C_p(h) =3(M+4g)+g+\sum_{i\in F}c_iw_i =3(M+4g)+g+T =C_p^0. \]
The report therefore satisfies no regret with equality. Its beneficiary improvement is
\[ P(h)=\frac12\sum_{i\in F}c_iw_i=\frac{T}{2}, \]
so \(S_J(h)=\theta\).
We have proved the equivalence
\[ \boxed{ \text{Subset Sum is YES} \iff \text{a no-regret report attains }S_J\le\theta. } \]
The construction has \(2n+4\) proposer types and \(2n+6\) receiver types. Every quota is positive.
To obtain dyadic masses, multiply all quotas by
\[ K_0=10\prod_{i=1}^n c_i. \]
This makes every quota integral, including \(w_i/2\) and \(g\). Let \(N\) be the resulting total quota on either side, and choose an integer \(k\) with \(2^k>N\).
Add one proposer and one receiver, each with quota \(2^k-N\), ranking each other first. Append these added types last in every original true ranking, and rank every original proposer below the added proposer at the added receiver.
The added pair remains fully matched to itself. Every proposal from an original proposer to the added receiver is wholly rejected; deleting these proposals leaves the original DA problem. In particular, arbitrary insertion of this receiver into \(p\)’s report cannot change the original attainable outcomes.
Finally divide all quotas by \(2^k\). The masses are positive dyadic rationals and sum to one on each side. Original true ranks, the no-regret condition, and the beneficiary scores are unchanged.
Moreover,
\[ \log K_0=O(n\log n), \]
and the integer quotas, \(k\), and \(\theta\) have polynomial bit length in the Subset Sum input. There are only \(O(n)\) supported types and \(O(n^2)\) ranking entries. Thus this is a polynomial-time reduction respecting the task’s support-size convention.
An exact optimizer would compute the optimal beneficiary score and compare it with \(\theta\), thereby deciding Subset Sum. Hence the requested exact optimization is NP-hard.
For completeness, the threshold decision problem belongs to NP: a certificate is \(p\)’s permutation report. The polynomial stable-allocation evaluator computes its DA outcome and the truthful outcome, after which both rational inequalities can be checked exactly. Clearing the input denominators requires only polynomial bit length; the accelerated algorithm uses additions, subtractions, comparisons, and minimum operations on these scaled quantities.
Therefore the threshold decision problem is NP-complete, and the exact optimization cannot have a \(\operatorname{poly}(m,\tau,L)\)-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The reduction is sound in substance. It establishes NP-hardness of the requested exact optimization and NP-completeness of the rational-threshold decision version. I found no false central step or substantive mathematical gap. One minor clarification concerns the auxiliary-vertex convention in the cited algorithm.
The citation supports the required conclusions: Lemma 1 gives finite termination and proposal-order independence, with the unique proposer-optimal allocation as output; Section 3 supplies an accelerated algorithm computing that allocation. Thus the prover correctly distinguishes polynomial-time evaluation from potentially expensive literal proposal simulation. See [Dean and Munshi, Sections 2–3](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
Strict rankings, rational quotas, and redundant edge capacities fit the cited stable-allocation model. Serialization of proposals within a simultaneous round preserves receiver holdings because each receiver retains the highest-priority mass from the same pool.
Minor issue: The cited presentation uses auxiliary dummy vertices to represent unassigned mass. The prover lists the principal hypotheses but does not explicitly account for that convention. The minimum clarification is to explain how that convention applies to the balanced, complete instance and confirm that the evaluator returns the same original-edge allocation. This is a routine modeling clarification, not a missing hardness argument.
The construction contains \(2n+4\) proposer types and \(2n+6\) receiver types before padding. All quotas are positive.
Both quota sums are correctly computed as
\[
\frac{7}{2}M+8g.
\]
The accomplice’s displayed ranking gives
\[
r_p(H)=3,\qquad r_p(X_i)=i+5=3+c_i.
\]
The beneficiary’s displayed prefix gives
\[
s_J(q_i)=n-i+1,\qquad s_J(d)=n+3,
\]
and consequently
\[
s_J(d)-s_J(q_i)=i+2=c_i.
\]
The assumption \(n\ge2\) makes both displayed types \(t_1,t_2\) available. The arbitrary ranking tails do not affect these ranks or the subsequent priority comparisons.
The universal quantifier over the accomplice’s reports is adequately addressed.
At \(X_i\), the accomplice has highest priority, so its retained mass cannot decrease. At \(Y_i\), the designated types \(q_i,t_i\) outrank every other proposer; at \(J\), the initial type \(d\) outranks all omitted types. The induction therefore excludes interference from arbitrary proposals by \(p\).
The bound on higher-priority mass reaching \(H\) is correct:
\[
\sum_i\left(\min\{e_i,w_i/2\}+(e_i-w_i/2)_+\right)
=\sum_i e_i\le M.
\]
This verifies that the designated item types do not enter their unspecified tails. Their final allocations, including the formulas involving \(x_i\), follow from their routes and the stated capacities. In particular, \(p\) receives no final allocation at \(Y_i\) or \(J\).
The local confinement argument also checks out. Proposer \(u\) has highest priority at \(A,C\), with sufficient combined capacity; proposer \(v\) has highest priority at \(B,D\), with sufficient capacity at \(D\). Neither reaches an unspecified tail.
The task’s balanced, complete setting guarantees full receiver capacities at termination. Consequently, the local receivers hold exactly \(4g\) of \(p\), and
\[
h_{pH}=M-\sum_i x_i.
\]
Re-expanding the definition of \(\Delta\) using the stated allocations confirms
\[
\Delta=g+3a+4z+3b+c-d_0.
\]
The identity
\[
b=\min\{2g-c,g\}
\]
is justified by \(v\)’s proposal order and highest priority at \(B\).
The bound \(3b+c\ge2g\) is correct in both cases. In the case \(c\ge g\), the calculation also uses \(c\le2g\), which follows immediately from \(v\)’s quota. Together with \(d_0\le2g\) and nonnegativity, this establishes
\[
\Delta\ge g.
\]
No substantive gap occurs here.
The truthful proposal schedule is consistent with the displayed rankings and capacities. The displacement of \(p\) from \(A,B\) sends exactly \(2g\) onward to \(D\), while the final holdings at \(H,C\) remain as stated.
The truthful cost calculation is correct:
\[
3M+4(2g)+5(2g)=3(M+4g)+6g.
\]
The arbitrary-report cost identity correctly accounts for every possible final destination of \(p\):
\[
C_p(h)=3(M+4g)+\Delta+\sum_i c_i x_i.
\]
Because the accomplice’s quota is fixed, comparison of average ranks is equivalent to comparison of these total costs. Thus no regret indeed implies
\[
\sum_i c_i x_i\le5g=T.
\]
The beneficiary improvement formula is correct: only the specified \(q_i\)-mass replaces \(d\), with rank advantage \(c_i\).
For positive \(w\), the inequality
\[
(x-w/2)_+\le x/2
\]
holds throughout \(0\le x\le w\), with equality precisely at \(x=0\) and \(x=w\).
Therefore the threshold condition forces equality in both bounds
\[
P(h)\le\frac12\sum_i c_i x_i\le\frac T2.
\]
Since every coefficient \(c_i\) is positive, equality forces every item individually to satisfy \(x_i\in\{0,w_i\}\). The extracted set then satisfies
\[
\sum_{i\in F}\nu_i=T.
\]
This direction excludes fractional false positives.
The proposed report is a single common strict permutation, as required.
Each selected item’s rejection chain has the stated allocations. After all selected chains, \(H\) holds exactly \(W\) of higher-priority mass. The remaining quota of \(p\) is correctly exhausted by
\[
g+g+(M-W)+2g=M+4g-W.
\]
At this outcome, \(u\) remains at \(D\), and \(v\) remains at \(C\). No further rejection chain is triggered. Hence the claimed local allocations and \(\Delta=g\) are correct.
The resulting cost equals the truthful cost, and the beneficiary improvement equals \(T/2\). This verifies the converse direction, including exact equality in the no-regret constraint.
The multiplier \(K_0\) clears all quota denominators, including those in \(w_i/2\) and \(g\).
The added pair ranks each other first, so it remains matched internally. Its receiver rejects original proposers; inserting it into the accomplice’s report cannot change the original attainable allocations.
Appending the added types last preserves all original rank positions. Uniform scaling preserves both average-rank scores and the no-regret comparison.
The stated polynomial-size claim is valid with a power of two immediately above \(N\). The product defining \(K_0\) has polynomial bit length, and the construction has only linearly many supported types and quadratically many ranking entries. No expansion into individual agents is used.
An exact optimizer would decide the established threshold equivalence, so the NP-hardness conclusion follows.
A permutation report has polynomial certificate length. The cited accelerated evaluator, together with exact rational comparisons and the denominator-size argument, supports NP membership of the threshold version.
The only requested clarification is the applicability of the cited algorithm’s auxiliary dummy-vertex convention. No modification of the reduction or its inequalities is needed.
⟨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.