Answer: Polynomial-time solvable in \(m,\tau,L\); a winning rational \(y\) always exists.
Theorem 2.5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateA popular winning set of size 2 can be found in polynomial time for the general case of weighted agents with preference ties allowed. In particular, the popular dimension is at most 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type and housing-class sets \(T\) and \(H\), rational type masses \(\mu_t\), per-capita capacities \(q_h\), and each type’s acceptable classes, weak ranking, and voting weight \(w_t\), can one find in time polynomial in \(|T|\), \(|H|\), and input bit length \(L\) a rational array \(y_{t,a,b}\)? Each entry is the mass of type \(t\) receiving acceptable class \(a\) or \(\bot\) in the first matching and \(b\) or \(\bot\) in the second; each plan must respect the capacities. Require that for every feasible competing assignment, including any split of each \((t,a,b)\) cell among allowed assignments \(c\), the total weight of residents who strictly prefer their better assignment from the pair to \(c\) is at least the total weight who strictly prefer \(c\) to that pair.
A society is given by its support: a list \(T\) of \(\tau=|T|\) types with positive binary rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(H\) be the housing classes, \(m=|H|\), and \(L\) the total input bit length.
Each class has a nonnegative binary rational per-capita capacity \(q_h\). Each type has a nonnegative binary rational voting weight \(w_t\), an acceptable set \(A_t\subseteq H\), and a weak ranking on \(A_t\). Extend it to \(D_t=A_t\cup\{\bot\}\) by ranking every acceptable class strictly above being unmatched, \(\bot\); indifference contributes no vote.
A pair of assignments is a nonnegative rational array \(y_{t,a,b}\), indexed by \(a,b\in D_t\), satisfying \(\sum_{a,b}y_{t,a,b}=\mu_t\) and, for every \(h\in H\), \(\sum_{t,a,b}y_{t,a,b}\mathbf1_{a=h}\le q_h\) and \(\sum_{t,a,b}y_{t,a,b}\mathbf1_{b=h}\le q_h\). Its entries describe the same residents’ assignments in the two plans.
A competitor may split every cell arbitrarily: it is any nonnegative real array \(z_{t,a,b,c}\), with \(a,b,c\in D_t\), satisfying \(\sum_c z_{t,a,b,c}=y_{t,a,b}\) and \(\sum_{t,a,b,c}z_{t,a,b,c}\mathbf1_{c=h}\le q_h\) for every \(h\in H\). There is no capacity constraint on \(\bot\).
Let \(d_t(a,b)\) be either weakly best member of \(\{a,b\}\). Call \(y\) winning if every competitor satisfies \(\sum_{t,a,b,c}w_tz_{t,a,b,c}\bigl(\mathbf1_{d_t(a,b)\succ_t c}-\mathbf1_{c\succ_t d_t(a,b)}\bigr)\ge0\).
Is finding a winning rational \(y\), or determining that none exists, solvable in time polynomial in \(m,\tau,L\), or is this problem NP-hard?
For finite agents and individual unit-capacity houses, a popular winning set of at most two matchings always exists and can be found in polynomial time, even with nonnegative voting weights and preference ties. [Connor et al.](https://arxiv.org/html/2509.25150v3)
No result settling this precise continuous problem was identified in the literature search.
1. Result. The problem is polynomial-time solvable, and a winning rational \(y\) always exists.
We give a construction operating directly on the listed types and binary rational capacities. It is inspired by the top-choice bottleneck construction of [Connor et al.](https://arxiv.org/html/2509.25150v3), but the proof below handles arbitrary real-valued splitting by competitors and establishes polynomial complexity in the compressed input.
2. Reduction to an allocation under doubled capacities. Consider a rational array \(x_{t,d}\), indexed by \(d\in D_t\), satisfying
\(\displaystyle x_{t,d}\geq 0,\qquad \sum_{d\in D_t}x_{t,d}=\mu_t,\qquad \sum_t x_{t,h}\leq 2q_h.\)
From such an array, define
\(\displaystyle y_{t,h,\bot}=y_{t,\bot,h}=\frac{x_{t,h}}2\quad(h\in A_t),\qquad y_{t,\bot,\bot}=x_{t,\bot},\)
with all other entries zero. Each plan uses capacity at most \(q_h\), and the residents’ best assignment in the two plans has distribution \(x\).
For any competitor \(z\), aggregate its assignments into
\(\displaystyle \xi_{t,h,c}=z_{t,h,\bot,c}+z_{t,\bot,h,c},\qquad \xi_{t,\bot,c}=z_{t,\bot,\bot,c}.\)
Then
\(\displaystyle \sum_c\xi_{t,d,c}=x_{t,d},\qquad \sum_{t,d}\xi_{t,d,h}\leq q_h.\)
Define the competitor’s vote advantage on a resident with baseline assignment \(d\) by
\(\displaystyle b_t(d,c)=w_t\bigl(\mathbf1_{c\succ_t d}-\mathbf1_{d\succ_t c}\bigr).\)
It therefore suffices to construct \(x\) for which every such real array \(\xi\) satisfies
\(\displaystyle \sum_{t,d,c}b_t(d,c)\xi_{t,d,c}\leq 0.\)
Classes with \(q_h=0\) can be omitted throughout the construction: neither the constructed plans nor a feasible competitor can assign positive mass to them.
3. The flow construction. Maintain a set \(R\) of remaining positive-capacity classes and residual masses \(r_t\), initially
\(\displaystyle R=\{h:q_h>0\},\qquad r_t=\mu_t.\)
Initially all entries of \(x\) are zero. At the start of each round, assign to \(\bot\) any residual type mass having no acceptable class in \(R\), and set that residual mass to zero.
For each remaining active type, let
\(\displaystyle F_t(R)=\{h\in A_t\cap R:h\succeq_t h'\text{ for every }h'\in A_t\cap R\}.\)
These are its current favorite classes.
For a subset \(P\) of active types, use the network with source \(s\), sink \(v\), and arcs
\(\displaystyle s\longrightarrow t\ \text{ of capacity }r_t,\qquad t\longrightarrow h\ \text{ of capacity }2\quad(h\in F_t(R)),\qquad h\longrightarrow v\ \text{ of capacity }2q_h.\)
The middle capacity is effectively unlimited: the entire residual population has mass at most \(1\).
A prefix consists of all active types whose weights are at least a specified weight level. Examine these prefixes in decreasing order of weight.
If all active types can be fully served on their current favorite classes, take a flow saturating all source arcs, add its type-to-class flows to \(x\), and terminate.
Otherwise, let \(W\) be the weight level of the first infeasible prefix. Thus all active types of weight strictly greater than \(W\) can be fully served.
Choose a maximum flow \(f\) for the prefix of weights at least \(W\), subject to saturating every source arc of a type of weight strictly greater than \(W\). Such a maximum flow exists: start with a flow serving those higher-weight types, add the weight-\(W\) types, and augment along simple residual source-to-sink paths. These augmentations preserve the already saturated higher-weight source arcs. When no augmenting path remains, the flow is maximum.
Let \(U\) be the type vertices reachable from \(s\) in this maximum flow’s residual graph, and let \(B\) be the reachable class vertices.
The following facts hold:
Assign the mass \(f_{t,h}\) to \(x_{t,h}\) for \(t\in U\), \(h\in B\). Subtract these assigned amounts from the corresponding residual masses, and remove all classes in \(B\) from \(R\). Call this a bottleneck round, with threshold \(W\).
By the three facts above, the assigned mass fills every removed class exactly:
\(\displaystyle \sum_t x_{t,h}=2q_h\qquad(h\in B).\)
Moreover, \(B\) is nonempty. The prefix is infeasible, so some weight-\(W\) source arc is unsaturated. Its type is reachable and has a nonempty favorite set, which makes at least one class reachable.
Consequently, there are at most \(m\) bottleneck rounds, followed by at most one terminal round.
4. Properties of the construction. Number the bottleneck rounds chronologically, with thresholds \(W_1,W_2,\ldots\) and removed class sets \(B_1,B_2,\ldots\).
We first prove that the thresholds are nonincreasing.
Consider a round with threshold \(W\). A higher-weight type in \(U\) is fully served, since its source arc is saturated. A higher-weight type outside \(U\) sends no flow into \(B\). Its flow therefore still serves its entire residual mass after \(B\) is removed, using classes that remain current favorites.
Thus, after the round, all residual types of weight strictly greater than \(W\) remain jointly feasible on their favorite classes. The next infeasible prefix, if any, must have threshold at most \(W\). Hence
\(\displaystyle W_1\geq W_2\geq\cdots.\)
We also need a preservation property:
*If a type has weight strictly greater than \(W_s\), every portion of its mass residual at the start of round \(s\) ultimately receives a favorite class from \(R_s\), the set of classes remaining at that round.*
Indeed, such a type is either fully assigned during round \(s\), or retains a flow serving its entire residual mass on favorites that survive the round. In the latter case, its best available preference level has not changed. Every subsequent threshold is at most \(W_s\), so the same argument applies at each later bottleneck. If the type survives to the terminal round, it is fully assigned to its current favorites, still at the original preference level. It cannot become unmatched, because this argument preserves a nonempty favorite set.
Finally, every type assigned positive mass during bottleneck round \(s\) has weight at least \(W_s\). Its assigned class is a current favorite, and all its current favorites belong to \(B_s\). Consequently, it strictly prefers its assigned class to every acceptable class remaining after that round, and to \(\bot\).
5. A certificate against every real-valued competitor. Give each class a nonnegative number
\(\displaystyle \pi_h=W_s\quad\text{if }h\in B_s,\qquad \pi_h=0\quad\text{if }h\text{ survives to the terminal round},\)
and set \(\pi_\bot=0\).
We claim that whenever \(x_{t,d}>0\), and \(c\in D_t\) is either \(\bot\) or a positive-capacity class,
\[\displaystyle b_t(d,c)\leq 2\pi_c-\pi_d. \tag{1}\]
We verify all preference cases.
Case 1: \(d\succ_t c\). If \(d\) was assigned in bottleneck round \(s\), then \(w_t\geq W_s=\pi_d\). If \(d\) was assigned in the terminal round, then \(\pi_d=0\), so the same inequality holds. Therefore
\(\displaystyle b_t(d,c)=-w_t\leq-\pi_d\leq 2\pi_c-\pi_d.\)
Case 2: \(d\) and \(c\) are indifferent. If \(\pi_d=0\), inequality (1) follows from \(\pi_c\geq0\).
Otherwise, \(d\) was assigned in a bottleneck round. Its type strictly prefers \(d\) to every acceptable class surviving that round. Thus \(c\) was removed in the same round or an earlier round. The nonincreasing thresholds imply \(\pi_c\geq\pi_d\), and hence
\(\displaystyle b_t(d,c)=0\leq 2\pi_c-\pi_d.\)
Case 3: \(c\succ_t d\). The class \(c\) must have been removed in a bottleneck round before the mass assigned to \(d\) received its assignment.
To justify this, every real-class assignment is to a current favorite, so a strictly preferred class cannot still be available when \(d\) is assigned. Likewise, mass is assigned to \(\bot\) only after all its acceptable remaining classes have disappeared.
Suppose \(c\in B_s\). The preservation property shows that \(w_t\leq W_s\): otherwise the mass eventually assigned to \(d\) would receive a favorite from \(R_s\), which it could not rank strictly below \(c\in R_s\).
Therefore \(w_t\leq\pi_c\). Also \(\pi_c\geq\pi_d\), by the chronological order and the nonincreasing thresholds, with \(\pi_d=0\) for terminal or unmatched assignments. It follows that
\(\displaystyle b_t(d,c)=w_t\leq\pi_c\leq 2\pi_c-\pi_d.\)
This proves (1).
Now let \(\xi\) be any feasible real-valued competitor. Zero-capacity classes receive zero competitor mass, so (1) applies to every relevant term. Summing gives
\(\displaystyle \sum_{t,d,c}b_t(d,c)\xi_{t,d,c} \leq 2\sum_{h\in H}\pi_h\sum_{t,d}\xi_{t,d,h} -\sum_{t,d}\pi_d x_{t,d} \leq 2\sum_{h\in H}\pi_h q_h-\sum_{t,d}\pi_d x_{t,d}. \)
Every class with nonzero \(\pi_h\) was filled to doubled capacity by the construction. Thus
\(\displaystyle \sum_{t,d}\pi_d x_{t,d} =\sum_{h\in H}\pi_h\sum_t x_{t,h} =2\sum_{h\in H}\pi_hq_h.\)
The competitor’s vote advantage is therefore at most zero. By the reduction in Section 2, the constructed \(y\) is winning against every competitor allowed in the question.
6. Rationality and polynomial bit complexity. Each round uses at most \(\tau\) prefix-feasibility flow computations and one additional maximum-flow computation. The networks have at most \(\tau+m+2\) vertices and \(O(\tau m+\tau+m)\) arcs. There are at most \(m\) bottleneck rounds.
For exact arithmetic, let \(K\) be the product of the input denominators of the masses and capacities. Its bit length is \(O(L)\). Scale all flow capacities and masses by \(K\). Initial capacities are integers, and integral maximum flows ensure that all residual masses and constructed entries remain integer multiples of \(1/K\). All scaled numbers have polynomial bit length.
A polynomial-time maximum-flow algorithm, such as Edmonds–Karp, therefore implements every step in polynomial bit complexity. Weight comparisons also require only polynomial time on the input binary rationals.
The constructed \(x\) has at most \(\tau(m+1)\) entries. The resulting \(y\) has at most \(2\tau m+\tau\) nonzero entries, each an integer multiple of \(1/(2K)\), and consequently has polynomial encoding length.
This completes the proof of polynomial-time solvability and universal existence.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and establishes polynomial-time construction and universal existence for the precise continuous problem. I found one minor notation gap: the certificate does not explicitly define prices for the zero-capacity classes omitted from the construction. There are no blocking mathematical issues.
1. Reduction to doubled capacities
The proposed construction of \(y\) from \(x\) is correct.
For each type, the two entries associated with a real class have total mass \(x_{t,h}\), while the unmatched entry has mass \(x_{t,\bot}\). Consequently, the total type mass is \(\mu_t\). Each plan assigns exactly \(x_{t,h}/2\) of type \(t\) to class \(h\), so the doubled-capacity bounds on \(x\) imply the required capacity bounds on both plans.
Every positive cell has best assignment equal to its real class, or to \(\bot\) in the unmatched cell. Thus the aggregation into \(\xi\) preserves both the baseline distribution and the competitor’s vote advantage. Competitor mass in all other cells is zero by nonnegativity and the cell marginal constraints.
The reduction needs only the stated direction: every competitor against the constructed \(y\) produces a feasible \(\xi\). It does not require proving that every feasible \(\xi\) comes from a competitor.
Omitting zero-capacity classes is legitimate. Their assignment mass must be zero in either plan and in every feasible competitor.
2. Flow construction and residual reachability
The middle capacity \(2\) is sufficient: the total residual mass never exceeds \(1\), so every middle arc has strictly positive forward residual capacity.
The choice of a maximum flow saturating the higher-weight source arcs is justified. The preceding feasible prefix supplies an initial flow saturating those arcs. Augmenting along simple residual source-to-sink paths cannot reverse a source arc into a higher-weight type, since doing so would revisit the source. Hence those source arcs remain saturated throughout the augmentation process.
The three reachability assertions are correct:
These facts also justify the update. Every outgoing flow of a reachable type goes to a class in \(B\), and every incoming flow of a class in \(B\) comes from a reachable type. Thus the recorded assignments fill each removed class to exactly \(2q_h\), and subtracting them leaves nonnegative residual type masses.
Previously recorded real-class assignments occupy only previously removed classes. Therefore no earlier assignment interferes with this exact-fill assertion.
The nonemptiness argument is valid. Infeasibility leaves an unsaturated source arc, and saturation of all higher-weight arcs places its type at weight \(W\). That active type has a nonempty favorite set, so \(B\) is nonempty. Each bottleneck therefore removes at least one class, proving the claimed round bound.
3. Threshold monotonicity and preference preservation
The threshold monotonicity argument correctly retains a joint feasible flow for all residual types of weight strictly greater than \(W\):
For every surviving higher-weight type, its retained positive flow uses surviving favorites. Its best available preference level therefore remains unchanged. Restricting the old flow to the surviving higher-weight types gives joint feasibility, so the next infeasible prefix cannot have a higher threshold.
The preservation property follows from the same argument applied successively. It concerns residual portions of a type, which are interchangeable here because all portions have the same preferences and weight. A surviving higher-weight type always retains a favorite at the original preference level; it cannot subsequently be assigned to \(\bot\).
The strict-preference assertion for a bottleneck assignment is also correct. All current favorites of its type lie in \(B\). Because the ranking is weak, any acceptable class surviving that round belongs to a strictly lower preference level. Every acceptable class is strictly above \(\bot\).
4. Pointwise voting certificate
All three preference cases in inequality (1) are valid.
For \(d\succ_t c\), a bottleneck assignment satisfies \(w_t\geq\pi_d\); a terminal assignment has \(\pi_d=0\). Nonnegative prices then give the claimed bound. An unmatched baseline cannot occur in this preference case.
For indifference, \(\pi_d=0\) is immediate. Otherwise, the strict-preference property excludes any indifferent acceptable class surviving the assignment round. Such a class must have been removed in the same or an earlier round, and threshold monotonicity gives \(\pi_c\geq\pi_d\). Indifference with \(\bot\) cannot occur for a real baseline class under the task’s ranking convention.
For \(c\succ_t d\), the preferred positive-capacity class must have disappeared before the baseline portion was assigned. If \(w_t>W_s\), the preservation property would force that portion to receive a favorite from \(R_s\), contradicting its eventual assignment strictly below \(c\in R_s\). Hence \(w_t\leq\pi_c\). Chronological ordering gives \(\pi_c\geq\pi_d\), including terminal and unmatched baselines.
This checks the certificate for every relevant baseline and competitor assignment.
5. Summation and arbitrary real splitting
Summing inequality (1) uses exactly the competitor’s capacity constraints and its marginal equalities. The inequality direction is correct because all prices are nonnegative.
Every class with positive price is a bottleneck class filled to doubled capacity. Therefore the baseline price contribution cancels the capacity upper bound exactly.
The proof applies directly to every feasible real-valued competitor. It invokes neither integrality nor rationality of competitor entries, and requires no discretization or limiting argument.
Minor issue — prices of omitted classes. Section 5 says to give “each class” a price, but its definition covers only bottleneck classes and classes surviving to the terminal round. A class omitted because \(q_h=0\) belongs to neither category, although the subsequent sums run over all of \(H\).
The minimum clarification is to specify prices for omitted zero-capacity classes, or explicitly restrict those sums to retained classes. Their baseline and competitor masses are zero, so this is solely a notation issue.
6. Rationality and polynomial complexity
The arithmetic and network-size claims are correct.
The product \(K\) of the mass and capacity denominators has bit length \(O(L)\). After scaling, the source capacities, middle capacities, and class capacities are integers. Integral maximum flows apply to these finite networks with nonnegative integer capacities. The higher-weight initialization and subsequent augmentations can also be performed integrally, preserving the required saturation constraints.
Residual masses and recorded assignments therefore remain integer multiples of \(1/K\). Their numerators have polynomial bit length; the same holds for scaled capacities, even when some capacities exceed the total population.
Edmonds–Karp uses polynomially many augmentations independently of capacity magnitudes. With polynomial-size integer arithmetic, it supplies the claimed polynomial bit complexity. The number of prefix tests and rounds is polynomial in \(\tau\) and \(m\), and rational weight comparisons are polynomial in \(L\).
Dividing real-class assignments by two gives the claimed denominator bound for \(y\). Its support size and encoding length are polynomial.
7. Scope and edge cases
The argument covers empty acceptable sets, no positive-capacity classes, zero voting weights, preference ties, excess capacity, and exhausted types. When no active types remain, the terminal feasibility test is vacuous.
The cited [Connor et al. paper](https://arxiv.org/html/2509.25150v3) provides the stated finite-agent context. The continuous conclusion is established by the submitted flow construction and certificate; it does not depend on extending that finite theorem without proof.
The output resolves both requested components: it constructs a rational winning pair in polynomial time and establishes that the nonexistence outcome never arises for a valid input.
⟨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.