Answer: The decision problem is in \(\mathrm{P}\), and a rational witnessing flow can be computed in polynomial time in \(m,\tau,L\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateA top-k preference profile P admits an NPO matching if and only if there is a matching of size at least n−1 w.r.t. P. Moreover, there is a polynomial time algorithm to determine whether a top-k preference profile admits an NPO matching, and to compute an NPO matching if it exists.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(\mu_t\) of finitely many reported top-\(k\) preference types \(P_t\), and rational category supplies \(q_j\) with \(\sum_j q_j=1\), decide whether there is a feasible assignment flow \(x_{t,j}\ge 0\), with row sums \(\mu_t\) and column sums \(q_j\), whose measurable implementation gives each agent one whole category and is Pareto optimal under every measurable completion of the reported rankings; return such a flow if one exists. Pareto optimality means there is no feasible reassignment that weakly improves almost every agent and strictly improves a positive mass.
A society is given by its support: the list of the \(\tau\) reported types with positive masses \(\mu_t\), each encoded as a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
There are \(m\geq1\) categories with binary rational supplies \(q_j\geq0\), satisfying \(\sum_jq_j=1\). Type \(t\) reports a strict ordered prefix \(P_t\) of length \(1\leq k_t\leq m\); every reported category precedes every unreported category in every completion.
Represent agents by the Lebesgue probability space \([0,1]\), partitioned into measurable type sets \(A_t\) of measures \(\mu_t\). A completion assigns each agent a strict total ranking extending its reported prefix, measurably; completions may differ within a type.
A feasible flow has real entries \(x_{t,j}\geq0\), with \(\sum_jx_{t,j}=\mu_t\) and \(\sum_tx_{t,j}=q_j\). An implementation is a measurable assignment \(f:[0,1]\to\{1,\ldots,m\}\) satisfying \(\lambda(A_t\cap f^{-1}(j))=x_{t,j}\); each agent receives one whole category.
An implementation is necessarily Pareto optimal if, under every measurable completion, no measurable reassignment with the same category supplies weakly improves almost every agent and strictly improves a set of positive measure. The implementation is fixed before the completion is chosen.
Is deciding whether a feasible flow with a necessarily Pareto optimal implementation exists in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard? If it is in \(\mathrm{P}\), can a witnessing flow also be computed in polynomial time?
For \(n\) discrete agents and \(n\) distinct objects, existence and construction of a necessarily Pareto optimal matching are polynomial-time solvable; existence is equivalent to a matching assigning at least \(n-1\) agents reported objects. [Hosseini et al.](https://arxiv.org/pdf/2007.09079)
No result settling this exact atomless problem with arbitrary measurable completions within types was located.
The decision problem belongs to \(\mathrm{P}\), and a witnessing rational flow can be computed in polynomial time in \(m,\tau,L\).
The key characterization is: choose one positive-supply category \(c\) as a fallback. Every agent assigned a different category must receive a reported category that necessarily precedes \(c\). Existence reduces to testing these restrictions for each possible \(c\), followed by one minimum-cost flow computation.
The proof below allows arbitrary measurable completions within each type.
Write \(R_t\) for the set of categories in the reported prefix of type \(t\), and \(r_t(j)\) for the reported position of \(j\in R_t\), starting at \(1\). Let \(C=\{j:q_j>0\}\).
For distinct categories \(j,k\), some completion of type \(t\)'s prefix ranks \(k\) above \(j\) exactly when either:
Indeed, an unreported \(j\) lies below every reported category, and any other unreported category can be placed above it. If \(j\) is reported, only earlier reported categories can precede it.
For a feasible flow \(x\), define a directed graph \(G_x\) on \(C\). Include an edge \(j\to k\), with \(j\ne k\), if some type \(t\) satisfies \(x_{t,j}>0\) and can rank \(k\) above \(j\).
Lemma 1. Every implementation of \(x\) is necessarily Pareto optimal if and only if \(G_x\) is acyclic.
Proof. Fix an implementation \(f\).
Suppose first that \(G_x\) contains a simple directed cycle \(j_1\to j_2\to\cdots\to j_\ell\to j_1\). Use cyclic indices, so \(j_{\ell+1}=j_1\). For each edge choose a witnessing type \(t_i\). Then \(x_{t_i,j_i}>0\), and a completion of that type can rank \(j_{i+1}\) above \(j_i\).
Choose \(0<\varepsilon<\min_i x_{t_i,j_i}\). Atomlessness gives measurable sets \(B_i\subseteq A_{t_i}\cap f^{-1}(j_i)\) of measure \(\varepsilon\). These sets are disjoint because the categories \(j_i\) are distinct.
On each \(B_i\), give agents a completion ranking \(j_{i+1}\) above \(j_i\). Elsewhere use any fixed completion for each type. This completion is measurable: it is constant on finitely many measurable pieces. The choices remain consistent even if several \(t_i\) coincide, because the sets \(B_i\) are disjoint.
Reassign each \(B_i\) to \(j_{i+1}\), leaving everyone else unchanged. Each cycle category loses and gains exactly \(\varepsilon\), so supplies are preserved. Every agent in the union of the \(B_i\) strictly improves. Thus \(f\) is not necessarily Pareto optimal.
Conversely, suppose a measurable completion admits a Pareto-improving reassignment \(g\). Define \(y_{j,k}=\lambda(\{a:f(a)=j,\ g(a)=k\})\). Both assignments have the same supplies, so for every category \(j\),
\(\displaystyle \sum_{k\ne j}y_{j,k}=\sum_{k\ne j}y_{k,j}.\)
Strict rankings imply that almost every agent whose category changes strictly improves. Consequently, if \(j\ne k\) and \(y_{j,k}>0\), finiteness of the type support gives a type \(t\) with a positive-measure set of such agents. Hence \(x_{t,j}>0\), and ranking \(k\) above \(j\) is possible for that type. Therefore \(j\to k\) belongs to \(G_x\).
The off-diagonal entries of \(y\) form a nonzero nonnegative circulation. Its positive edges contain a directed cycle: starting with a positive edge, conservation ensures another positive outgoing edge at its endpoint; continuing must eventually repeat a vertex. Thus \(G_x\) contains a cycle.
Zero-supply categories occur only on null sets under either assignment and do not affect this argument. This proves the lemma. \(\square\)
In particular, necessary Pareto optimality depends only on the flow, even though the implementation is fixed before the completion.
For a candidate \(c\in C\), define:
Set \(F_t(c)=B_t(c)\cup\{c\}\). Thus \(F_t(c)\) consists of the fallback \(c\), together with the categories necessarily preferred to \(c\).
Theorem 2. A necessarily Pareto optimal implementation exists if and only if, for some \(c\in C\), there is a feasible flow satisfying \(x_{t,j}=0\) whenever \(j\notin F_t(c)\).
Suppose \(x\) has a necessarily Pareto optimal implementation. By Lemma 1, \(G_x\) is acyclic. Since \(C\) is nonempty, this finite graph has a vertex \(c\) with no incoming edge.
Consider \(x_{t,j}>0\) with \(j\ne c\).
First, \(j\) must be reported. Otherwise type \(t\) could rank \(c\) above \(j\), producing an incoming edge \(j\to c\).
If \(c\) is reported, \(j\) must precede \(c\) in the reported prefix; otherwise again \(j\to c\). If \(c\) is unreported, every reported \(j\) necessarily precedes it.
Therefore \(j\in B_t(c)\), establishing the required restrictions.
Fix \(c\in C\) for which the restricted feasible set is nonempty. On that set minimize
\(\displaystyle \Phi_c(x)=\sum_t\sum_{j\in B_t(c)}r_t(j)x_{t,j}.\)
Assignments to \(c\) have cost zero. The restricted feasible set is closed and bounded, so a minimizer \(x^\star\) exists.
We prove that \(G_{x^\star}\) is acyclic.
There is no incoming edge to \(c\): any positive assignment to \(j\ne c\) has \(j\in B_t(c)\), so that type necessarily prefers \(j\) to \(c\).
Suppose, for contradiction, that there is a simple directed cycle. It therefore avoids \(c\); write it as \(j_1\to\cdots\to j_\ell\to j_1\), with witnessing types \(t_i\).
Because \(j_i\ne c\), the category \(j_i\) is reported by \(t_i\). Thus each edge implies that \(j_{i+1}\) is also reported and
\(\displaystyle r_{t_i}(j_{i+1})<r_{t_i}(j_i).\)
Moreover, \(j_{i+1}\in B_{t_i}(c)\). If \(c\) is reported, this follows because \(j_{i+1}\) precedes \(j_i\), which precedes \(c\); if \(c\) is unreported, every reported category belongs to \(B_{t_i}(c)\).
Choose \(0<\varepsilon<\min_i x^\star_{t_i,j_i}\). For each \(i\), decrease \(x^\star_{t_i,j_i}\) by \(\varepsilon\) and increase \(x^\star_{t_i,j_{i+1}}\) by \(\varepsilon\). These simultaneous changes preserve every row sum and every column sum. They preserve nonnegativity and use only allowed entries.
The objective change is
\(\displaystyle \varepsilon\sum_{i=1}^{\ell}\bigl(r_{t_i}(j_{i+1})-r_{t_i}(j_i)\bigr)<0,\)
contradicting optimality. Hence \(G_{x^\star}\) is acyclic, and Lemma 1 shows that every implementation of \(x^\star\) is necessarily Pareto optimal. \(\square\)
For each \(c\in C\), construct a network with a source \(s\), one vertex per reported type, one vertex per category, and a sink \(z\). Its edges are:
A flow of value \(1\) exists exactly when the restrictions for \(c\) admit a feasible society flow. Indeed, value \(1\) saturates all source edges and all sink edges, because each of their total capacities is \(1\).
Test the candidates by maximum flow. If every test fails, Theorem 2 proves nonexistence. Otherwise, for one successful candidate, compute a minimum-cost flow of value \(1\), giving \(t\to j\) cost \(r_t(j)\) for \(j\in B_t(c)\) and cost zero for \(j=c\). All other edges have cost zero. Theorem 2 proves that its type-to-category entries constitute a witness.
Here are explicit conservative running-time bounds. Let \(N=m+\tau+2\), \(M=m\tau+m+\tau\), and \(H=L+\lceil\log_2(Nm+1)\rceil\).
Let \(D\) be the product of the denominators of all masses and supplies. Its bit length is \(O(L)\). Multiplying capacities by \(D\) produces integer networks with capacities at most \(D\). This is an arithmetic scaling operation; no agents or object copies are created.
Edmonds–Karp uses \(O(NM^2)\) operations per candidate. Thus decision takes \(O(mNM^2H^2)\) bit operations.
For construction, start from the successful integral maximum flow and apply minimum-mean-cost cycle cancellation. For integer edge costs bounded in absolute value by \(m\), this algorithm performs \(O(MN\log(Nm))\) cancellations, each requiring \(O(MN)\) operations. These bounds are stated in Section 8, particularly Corollary 8.4, of [Zwick’s minimum-cost-flow notes](https://www.cs.tau.ac.il/~zwick/grad-algo-13/min-cost-flow.pdf). The hypotheses hold here: the starting flow is maximum, all capacities are integral after scaling, and residual costs lie between \(-m\) and \(m\).
Capacities and flow entries remain integers of \(O(L)\) bits; minimum-mean-cycle computations use costs and comparisons of polynomial bit length. A conservative total bound for decision and construction is therefore
\(\displaystyle O\!\left(\bigl[mNM^2+M^2N^2\log(Nm)\bigr]H^2\right).\)
Dividing the resulting integral entries by \(D\) gives a rational witnessing flow, with total output length \(O(m\tau(L+1))\).
Every computed feasible flow has a measurable implementation. For each type \(t\), the function \(u\mapsto\lambda(A_t\cap[0,u])\) is continuous and ranges from \(0\) to \(\mu_t\). Cutting at the cumulative values of \(x_{t,1},\ldots,x_{t,m}\) partitions \(A_t\) into measurable pieces of those measures. Assign each piece its corresponding category.
By Lemma 1 and Theorem 2, this fixed implementation is Pareto optimal under every measurable completion.
The case \(m=1\) is included automatically: the unique category is the fallback and the graph has no edges. There are no remaining open claims needed for the classification or construction.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated atomless problem. The characterization, polynomial-time decision procedure, and rational-flow construction are correct. No major or minor repair is needed.
For distinct categories \(j,k\), if \(j\) is unreported, a completion can place \(k\) above \(j\), whether \(k\) is reported or unreported. If \(j\) is reported, precisely the earlier reported categories can precede it. This uses the stipulated ordered-prefix model correctly.
Restricting \(G_x\) to positive-supply categories is valid: feasibility forces zero flow into every zero-supply category, and implementations and supply-preserving reassignments assign such categories only on null sets.
Each witnessing cell \(A_{t_i}\cap f^{-1}(j_i)\) has positive measure. Atomlessness therefore permits the stated equal-measure subsets.
A simple directed cycle has distinct source categories, so these subsets are disjoint even when witnessing types repeat. Consequently, the separately chosen completions do not conflict. The resulting completion is measurable because it uses finitely many measurable pieces.
The reassignment preserves each category’s supply exactly and strictly improves a positive-measure set. The completion is chosen after fixing \(f\), as required by the task’s quantifier order.
The transition quantities \(y_{j,k}\) are measurable and satisfy the displayed conservation identity because \(f\) and \(g\) have identical category supplies.
Under strict rankings, a changed category is strictly better wherever weak improvement holds. Any exceptions belong to the permitted null set and cannot account for a positive transition mass.
For every positive off-diagonal transition, finiteness of the type support supplies a witnessing type with positive assigned mass. Thus every positive transition is an edge of \(G_x\).
Positive-measure strict improvement makes the off-diagonal circulation nonzero. Conservation and finiteness justify the directed-cycle argument given. Both directions of the lemma therefore hold for arbitrary measurable completions within types.
Since total supply is one, \(C\) is nonempty. A finite acyclic directed graph has a vertex with no incoming edge.
For such a vertex \(c\), any positive assignment to another category \(j\) would create \(j\to c\) unless \(j\) is reported and necessarily precedes \(c\). The two cases defining \(B_t(c)\) capture exactly this restriction.
The argument correctly selects a vertex with no incoming edge, consistent with the graph’s orientation.
The restricted feasible set is nonempty by hypothesis, closed, and bounded. Its linear objective consequently attains a minimum.
Every allowed positive assignment outside \(c\) necessarily precedes \(c\), so there is no incoming edge to \(c\). Any directed cycle therefore avoids \(c\).
On such a cycle, each source category is reported. The preference-edge characterization then forces the destination category to be an earlier reported category of the witnessing type. The destination remains allowed in both cases defining \(B_t(c)\).
The simultaneous perturbation preserves row and column sums. Repeated witnessing types cause no difficulty: because the source categories are distinct, each coordinate is decreased at most once; increases can only offset decreases. The chosen bound on \(\varepsilon\) ensures nonnegativity.
Every rank difference in the objective-change formula is strictly negative. The contradiction establishes acyclicity of every restricted minimizer.
A value-one network flow saturates every source-to-type edge and every category-to-sink edge, since each collection has total capacity one. Its middle-edge entries therefore satisfy precisely the required marginal constraints and restrictions.
Conversely, a restricted society flow supplies such a network flow. Capacity one on each middle edge is sufficient because every society-flow entry is at most one.
Testing all \(c\in C\) therefore decides existence, and the stated minimum-cost computation produces a witnessing flow.
Corollary 8.4 states that minimum-mean-cost cycle cancellation with integral edge costs of absolute value at most \(A\) performs \(O(MN\log(NA))\) cancellations. Section 8 also gives \(O(MN)\) time for finding a minimum-mean-cost cycle and specifies initialization with a maximum flow. These support the prover’s substitution \(A=m\). [Zwick’s minimum-cost-flow notes, Section 8](https://www.cs.tau.ac.il/~zwick/grad-algo-13/min-cost-flow.pdf)
The hypotheses hold: the successful maximum flow remains maximum after scaling, costs remain integral and bounded by \(m\), and residual reverse edges merely negate those costs. Residual edges increase the edge count by at most a constant factor.
The denominator product \(D\) has \(O(L)\) bits. Scaling gives integral capacities bounded by \(D\); integral augmentations preserve integral flow entries of \(O(L)\) bits.
Edmonds–Karp’s \(O(NM^2)\) arithmetic-operation bound, multiplied by at most \(m\) candidates, supports the decision bound. The cancellation count multiplied by the per-cancellation cost supports the construction term \(O(M^2N^2\log(Nm))\).
Minimum-mean-cycle calculations involve bounded-length sums of integral costs and comparisons of means with denominators bounded by \(N\). The stated \(H\) accommodates these quantities and the scaled capacities. The \(H^2\) factor is conservative. Scaling, network preparation, and output production fit within the displayed total bound.
Dividing integral entries by \(D\) yields exact rational entries with the claimed polynomial output length. No expansion into discrete agents or object copies occurs.
The cumulative-measure function for each measurable \(A_t\) is continuous and reaches every value between zero and \(\mu_t\). The indicated cuts therefore produce measurable pieces with the required masses. Boundary points have measure zero and do not affect any implementation constraint.
This implementation is fixed before completion selection. Lemma 1 supplies the required universal guarantee afterward.
Zero supplies, zero flow entries, fully reported rankings, a single positive-supply category, and \(m=1\) are all handled by the written argument. The task requests polynomial computation of the flow; it does not require a finite encoding or algorithmic construction of the arbitrary measurable type sets.
⟨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.