Answer: —
Theorem 4.3 — class: algorithmic
1-Euclid-Reg-SMT can be solved in polynomial time when preference profile is complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite male coordinate types \(i\in I\) with masses \(p_i\) at \(x_i\in\mathbb R\), female coordinate types \(j\in J\) with masses \(q_j\) at \(y_j\in\mathbb R\), and \(\rho\in[0,1]\), does a stable transport \(z_{ij}\geq0\) with marginals \(p,q\) exist that assigns mass only to pairs whose strict-distance population rank is at most \(\rho\) for both endpoints?
Definitions. Input rational coordinates \(x_1,\dots,x_m\) for male types and \(y_1,\dots,y_n\) for female types, rational masses \(p_i,q_j>0\) of total mass \(1\), and rational \(
ho\in[0,1]\). A transport is \(f\ge0\) with row sums \(p_i\) and column sums \(q_j\). Types strictly prefer smaller distance and are indifferent at equal distance.
A transport is stable if there are no \(i,j,i',j'\) with \(f_{ij'}>0,f_{i'j}>0\), \(|x_i-y_j|<|x_i-y_{j'}|\), and \(|x_i-y_j|<|x_{i'}-y_j|\). Define \(r^F_i(j)=\sum_{h:|x_i-y_h|<|x_i-y_j|}q_h\) and \(r^M_j(i)=\sum_{h:|x_i-y_j|<|x_h-y_j|}p_h\).
Target. Is it polynomial-time decidable, or NP-hard, whether there is a stable transport \(f\) such that every \(f_{ij}>0\) satisfies \(r^F_i(j)\le
ho\) and \(r^M_j(i)\le
ho\)?
Known results. For unit-mass agents with complete distance-induced preferences on a line, the discrete regret version is solvable in polynomial time. No result is assumed for this exact finite-type mass-transport formulation.
The exact complexity classification remains unresolved here. I prove:
Thus any remaining hardness must exploit distance ties together with binary-encoded masses.
Write
$$ d_{ij}=|x_i-y_j|. $$
Define the acceptable-edge set
$$ A_\rho=\{(i,j):r_i^F(j)\le \rho\text{ and }r_j^M(i)\le \rho\}. $$
For fixed $i$, the function $r_i^F(j)$ is nondecreasing with $d_{ij}$: if $d_{ij}<d_{ik}$, every female type strictly closer than $j$ is also strictly closer than $k$. The analogous statement holds on the female side.
Suppose every positive entry of $f$ belongs to $A_\rho$. If $(i,j)\notin A_\rho$, then $(i,j)$ cannot be part of a blocking configuration for $f$.
Suppose first that $r_i^F(j)>\rho$. For every $j'$ with $f_{ij'}>0$,
$$ r_i^F(j')\le \rho<r_i^F(j). $$
If $d_{ij}<d_{ij'}$, monotonicity would give
$$ r_i^F(j)\le r_i^F(j'), $$
a contradiction. Hence $i$ does not strictly prefer $j$ to any partner in its support.
If instead $r_j^M(i)>\rho$, the symmetric argument shows that $j$ does not strictly prefer $i$ to any positively assigned male type. In either case $(i,j)$ cannot block. $\square$
Consequently, the target problem is equivalently the existence of a weakly stable, quota-filling allocation in the incomplete graph $A_\rho$, although the special geometric structure of $A_\rho$ must be retained.
For a transport $f$, define
$$ R_i(f)=\max\{d_{ij}:f_{ij}>0\}, $$
and
$$ C_j(f)=\max\{d_{ij}:f_{ij}>0\}. $$
These maxima exist because all margins are positive.
A transport $f$ is stable if and only if
$$ d_{ij}\ge \min\{R_i(f),C_j(f)\} $$
for every $i,j$.
If $f$ is unstable, there are $j',i'$ with $f_{ij'}>0$, $f_{i'j}>0$, and
$$ d_{ij}<d_{ij'},\qquad d_{ij}<d_{i'j}. $$
Therefore
$$ d_{ij}<R_i(f),\qquad d_{ij}<C_j(f), $$
so $d_{ij}<\min\{R_i(f),C_j(f)\}$.
Conversely, suppose
$$ d_{ij}<R_i(f),\qquad d_{ij}<C_j(f). $$
Choose $j'$ and $i'$ attaining the respective maxima. Then
$$ f_{ij'}>0,\qquad f_{i'j}>0, $$
and
$$ d_{ij}<d_{ij'},\qquad d_{ij}<d_{i'j}. $$
Thus $(i,j,i',j')$ is a blocking configuration. $\square$
This exposes the nonconvex part of the problem: for each pair $(i,j)$, at least one of the two worst-distance thresholds must not exceed $d_{ij}$.
Define the largest individually admissible distances
$$ \alpha_i=\max\{d_{ij}:r_i^F(j)\le\rho\}, $$
and
$$ \beta_j=\max\{d_{ij}:r_j^M(i)\le\rho\}. $$
The sets are nonempty because every nearest type has strict-better mass zero. By monotonicity,
$$ r_i^F(j)\le\rho\quad\Longleftrightarrow\quad d_{ij}\le\alpha_i, $$
and analogously on the female side.
A target transport exists if and only if there are thresholds $T_i,U_j$, chosen from incident distances, such that:
$$ T_i\le\alpha_i,\qquad U_j\le\beta_j; $$
$$ d_{ij}\ge\min\{T_i,U_j\}\quad\text{for every }i,j; $$
and the transportation problem with margins $p_i,q_j$ is feasible using only edges satisfying
$$ d_{ij}\le T_i\quad\text{and}\quad d_{ij}\le U_j. $$
Given a target transport, take
$$ T_i=R_i(f),\qquad U_j=C_j(f). $$
The rank restrictions give the first condition, Lemma 3.1 gives the second, and the support of $f$ gives the third.
Conversely, let $f$ be a feasible transport on the specified edges. Its actual worst distances satisfy
$$ R_i(f)\le T_i,\qquad C_j(f)\le U_j. $$
If $f$ were unstable, Lemma 3.1 would give some $i,j$ with
$$ d_{ij}<R_i(f)\le T_i,\qquad d_{ij}<C_j(f)\le U_j, $$
contradicting $d_{ij}\ge\min\{T_i,U_j\}$. The cutoff inequalities imply all support edges meet both rank bounds. $\square$
For fixed thresholds, the remaining feasibility test is a rational max-flow problem. The unresolved difficulty is selecting the thresholds without enumerating exponentially many profiles.
The target decision problem belongs to NP.
A certificate is a set $S\subseteq A_\rho$ of type-pair edges, intended to contain the positive support.
The verifier performs the following polynomial-time checks.
$$ R_i(S)=\max\{d_{ij}:(i,j)\in S\}, $$
and
$$ C_j(S)=\max\{d_{ij}:(i,j)\in S\}, $$
and verify
$$ d_{ij}\ge\min\{R_i(S),C_j(S)\} $$
for every $i,j$.
If these checks pass, take any feasible rational flow on $S$. Its actual support is a subset of $S$, so its actual worst distances do not exceed $R_i(S),C_j(S)$. The proof of Proposition 3.2 shows that it is stable and meets the rank bounds.
Conversely, if a target transport exists, its positive support is a valid certificate. Although the original transport might initially be represented by arbitrary real values, the transportation polytope on its support has rational data and hence contains a rational feasible point of polynomial encoding length.
Thus there is a polynomially verifiable certificate. $\square$
Consequently, an NP-hardness result would establish NP-completeness.
Let $D$ be a common multiple of the denominators of all $p_i$ and $q_j$. Replace male type $i$ by
$$ P_i=Dp_i $$
unit male agents at $x_i$, and replace female type $j$ by
$$ Q_j=Dq_j $$
unit female agents at $y_j$.
For a clone of male type $i$, the number of female clones strictly closer than female type $j$ is exactly
$$ D r_i^F(j). $$
Hence the mass inequality $r_i^F(j)\le\rho$ is equivalent to
$$ D r_i^F(j)\le \lfloor D\rho\rfloor. $$
The same holds on the female side.
A target transport exists if and only if the clone instance has a perfect weakly stable matching in which every matched clone has at most $\lfloor D\rho\rfloor$ strictly preferred agents on the opposite side.
Suppose first that a suitable clone matching exists. Let $F_{ij}$ be the number of matched clone pairs of types $i,j$ and set
$$ f_{ij}=\frac{F_{ij}}D. $$
The clone counts give the required margins and rank bounds. If the transport had a blocking configuration, choosing clones from the two positive matched type-pairs would give a blocking pair in the clone matching. Thus the transport is stable.
Conversely, suppose a target transport exists and let $S$ be its positive support. After multiplying margins by $D$, the transportation problem on $S$ has integral supplies and demands. By integrality of bipartite network flow, it has an integral feasible flow $F_{ij}$.
Pair the clones according to $F$. Every used type-pair lies in $S$. A blocking clone pair would therefore induce a blocking configuration between two edges of $S$, contradicting stability of the original transport. The rank bounds translate exactly as above. $\square$
The known polynomial algorithm for unit-agent one-dimensional Regret-SMT therefore gives an algorithm polynomial in the expanded population
$$ N=D. $$
This is only pseudo-polynomial for the rational-mass input: $D$ can be exponentially large in the binary encoding length of the denominators. Thus the known discrete result does not by itself establish polynomial-time solvability of the compressed problem. The relevant discrete result is stated in [Wen, Zhang, and Guo, “Stable Marriage in Euclidean Space”](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p994.pdf).
Here $(i,j)$ is acceptable on the male side precisely when no female type is strictly closer to $i$ than $j$. Thus every acceptable support partner of $i$ is a nearest female type. The same holds symmetrically.
For $\rho=0$, the answer is decidable in polynomial time by one max-flow computation on $A_0$.
If a feasible transport exists on $A_0$, consider any positive edge $(i,j')$. Since $r_i^F(j')=0$, there cannot be a female type $j$ with
$$ d_{ij}<d_{ij'}. $$
Therefore $i$ cannot strictly prefer any candidate to a positive support partner. No blocking configuration is possible, so every feasible transport on $A_0$ is stable.
Conversely, every target transport must be supported on $A_0$. Hence existence is exactly ordinary transportation feasibility on $A_0$. $\square$
For every $i,j$,
$$ r_i^F(j)\le 1-q_j<1, $$
and
$$ r_j^M(i)\le 1-p_i<1. $$
Thus every edge meets the rank bounds.
For $\rho=1$, every instance is a yes-instance.
Expand the rational masses into finitely many clones as in Section 5. Break all distance ties arbitrarily and apply Gale–Shapley to obtain a perfect stable matching for the refined strict preferences.
The matching remains weakly stable for the original distance preferences: a pair that strictly blocks under the original preferences would also strictly block under every refinement of the ties. Aggregating the clone matching gives a stable transport. Since all edges satisfy the rank bounds, it is a target transport. $\square$
Assume that every type has strict preferences:
$$ d_{ij}\ne d_{ik}\quad\text{whenever }j\ne k, $$
and
$$ d_{ij}\ne d_{hj}\quad\text{whenever }i\ne h. $$
Globally equal distances on vertex-disjoint edges are allowed.
Consider the following greedy algorithm. Maintain residual masses $a_i,b_j$, initially $p_i,q_j$. Repeatedly:
$$ \delta=\min\{a_i,b_j\}; $$
There are at most $m+n-1$ iterations.
The distances of the successively selected edges are nondecreasing, since active vertices and their incident edges are only deleted.
Suppose the output were unstable. By Lemma 3.1, there would be $i,j$ such that
$$ d_{ij}<R_i(f),\qquad d_{ij}<C_j(f). $$
Consider the iteration at which the first of $i,j$ is exhausted. Immediately before that iteration both are active, so $(i,j)$ is an active edge. The selected edge therefore has distance at most $d_{ij}$. All earlier selected edges also have distance at most $d_{ij}$. Consequently every edge carrying mass incident to the type exhausted at this iteration has distance at most $d_{ij}$, contradicting that its worst supported distance is strictly larger than $d_{ij}$. $\square$
At any residual stage, let $(i,j)$ be a minimum-distance active pair and let
$$ \delta=\min\{a_i,b_j\}. $$
Because preferences at each endpoint are strict, every other active edge incident to $i$ or $j$ is strictly longer than $(i,j)$.
Let $g$ be any stable residual transport. If $g_{ij}<\delta$, then both residual quantities
$$ a_i-g_{ij}>0,\qquad b_j-g_{ij}>0 $$
are positive. Hence $i$ sends positive mass to some $j'\ne j$, and $j$ receives positive mass from some $i'\ne i$. Minimality and strictness give
$$ d_{ij}<d_{ij'},\qquad d_{ij}<d_{i'j}, $$
which is a blocking configuration. Therefore $g_{ij}=\delta$.
Thus every stable transport contains the greedy assignment made at the first iteration. Removing the exhausted type and subtracting $\delta$ from the other margin preserves stability of the remaining transport. Induction proves that every stable transport agrees with every greedy step. $\square$
On instances without distance ties, the target problem is polynomial-time decidable.
Compute the unique stable transport by the greedy algorithm. Then inspect every positive entry and test its two rank inequalities. A target transport exists exactly when this unique stable transport passes all tests.
The algorithm uses at most $m+n-1$ greedy iterations and polynomially many exact comparisons and rational additions, so its running time is polynomial in the input bit length. $\square$
The unresolved case is therefore sharply localized:
The threshold criterion in Proposition 3.2 gives a polynomial verifier but still leaves an exponential threshold-selection problem. A complete result would require either a compressed algorithm exploiting the one-dimensional tie structure or an NP-hardness reduction realizable by symmetric one-dimensional distances and the mass-defined prefix constraints.
⟨structured verdict parsed — rendered above⟩
The prover does not answer the target complexity question: it proves neither a polynomial-time algorithm for the general problem nor NP-hardness. Its stated status is therefore accurately partial.
Most intermediate mathematical results are correct and useful. In particular, the worst-distance characterization, NP membership, clone equivalence, and the algorithms for $\rho=0$, $\rho=1$, and strict type preferences are substantively sound. No counterexample was found to these results.
The monotonicity statement is correct, including in the presence of ties. If $d_{ij}<d_{ik}$, every type strictly closer than $j$ is strictly closer than $k$, so $r_i^F(j)\le r_i^F(k)$.
Lemma 2.1 then follows correctly. If an edge violates one endpoint’s rank bound, that endpoint cannot strictly prefer the edge to any acceptable supported edge.
The informal conclusion concerning an “incomplete graph” is correct provided “weak stability” means that only mutually acceptable edges may block. That convention should be stated explicitly, but the later formal arguments do not depend on this terminology.
The characterization
$$ f\text{ stable}\quad\Longleftrightarrow\quad d_{ij}\ge\min\{R_i(f),C_j(f)\}\quad\text{for all }i,j $$
is correct.
Both directions match the definition exactly:
No distinctness assumption on $i,i',j,j'$ is needed beyond what is already forced by the strict inequalities.
The threshold formulation is correct.
The characterization
$$ r_i^F(j)\le\rho\quad\Longleftrightarrow\quad d_{ij}\le\alpha_i $$
remains valid with ties because equal-distance alternatives have equal strict-better mass.
In the converse direction, instability would imply simultaneously
$$ d_{ij}<R_i(f)\le T_i,\qquad d_{ij}<C_j(f)\le U_j, $$
contradicting $d_{ij}\ge\min\{T_i,U_j\}$. The cutoff conditions also imply the required rank restrictions.
This proposition gives a finite exact formulation, but it does not establish that threshold selection is polynomial-time solvable.
The support certificate is polynomial in size. Transportation feasibility with rational margins is polynomial-time decidable, and the stability inequalities can be checked exactly.
The soundness argument is valid even if the feasible flow uses only a subset of $S$: its actual worst distances can only decrease relative to $R_i(S)$ and $C_j(S)$.
For completeness, a target transport’s support supplies a valid certificate. Rational transportation feasibility has polynomial-size rational witnesses.
A small presentation omission is that $R_i(S)$ and $C_j(S)$ are undefined when a vertex is not incident with $S$. A successful feasibility check with strictly positive margins ensures nonempty incidence, but this implication should be stated before taking the maxima.
The equivalence is correct.
For an integral scaling $D$,
$$ D r_i^F(j) $$
is exactly the number of female clones strictly closer than a clone of type $i$. Since this number is integral,
$$ r_i^F(j)\le\rho \quad\Longleftrightarrow\quad D r_i^F(j)\le\lfloor D\rho\rfloor. $$
The integral-flow argument is also valid. An integral type-pair flow can be realized by pairing individual clones, and any blocking clone pair would use two positive type-pair edges from the original support, contradicting transport stability.
The cited paper does state polynomial-time solvability of complete-preference one-dimensional Euclidean Regret-SMT in its Theorem 4.3. Its setting therefore covers the expanded clone instance [Wen, Zhang, and Guo](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p994.pdf).
However, the write-up does not specify how the paper’s “position” convention translates to the number of strictly preferred clones. Under the common convention, position equals the number of strictly preferred agents plus one, so the regret threshold requires a corresponding offset. This is a routine clarification, but it is necessary for the invocation to be fully verifiable.
The description of the resulting algorithm as “pseudo-polynomial” is not established under the standard definition. Runtime polynomial in the least common denominator $D$ need not be polynomial in the unary size or maximum numerical magnitude of the individual denominators: an LCM can be exponentially large in the number of individually small denominators. The safe established statement is only that the expanded algorithm runs in time polynomial in $D$ and the remaining input length.
The proof is correct. Every acceptable supported edge is nearest at both endpoints. In fact, the male-side nearest condition alone suffices to rule out a blocking configuration involving that row. Thus feasibility on $A_0$ is exactly the desired condition.
The rank inequalities are automatic because
$$ r_i^F(j)\le1-q_j<1,\qquad r_j^M(i)\le1-p_i<1. $$
The existence argument is correct. Refining distance ties, applying Gale–Shapley, and then forgetting the refinement preserves weak stability: a strict distance improvement remains a strict preference in every refinement.
Lemma 6.3 is correct. Selected distances are nondecreasing because the active edge set only shrinks. Immediately before the first exhaustion of $i$ or $j$, the edge $(i,j)$ is active, so every previously selected incident edge has distance at most $d_{ij}$, contradicting the asserted strict inequality for the exhausted endpoint.
Lemma 6.4 is also correct. For a minimum active edge $(i,j)$, if a stable residual flow placed less than $\min\{a_i,b_j\}$ on it, both endpoints would have positive mass on strictly worse edges, producing a blocking configuration.
The induction sentence should explicitly cover:
The latter follows immediately because a residual blocking configuration would also block the original transport. This is a minor omitted justification, not a substantive gap.
The polynomial running-time claim is valid.
The general case with ties and compressed rational masses is expressly left open. NP membership, special cases, and a common-denominator expansion do not decide whether the original binary-encoded problem is in polynomial time or NP-hard.
Repairing this is not a matter of clarification: a general polynomial-time algorithm or a valid NP-hardness reduction is still required.
⟨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.