Answer: Exactly polynomial-time solvable for every fixed \(\ell\); hence the requested \((1+\ell(\ell-2)/6+\varepsilon)\)-approximation is achievable.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any ϵ > 0, there is a polynomial time (1 + L(L −2)/6 + ϵ)-approximation for L-Exchange.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\ge0\) summing to \(1\), a directed compatibility relation \(A\subseteq\Theta\times\Theta\), and a cycle cap \(L\), choose nonnegative masses \(\lambda_q\) of feasible directed cycle patterns \(q\) of lengths \(2,\ldots,L\) to maximize \(\sum_q |q|\lambda_q\), subject to \(\sum_q a_{\theta q}\lambda_q\le\mu_\theta\) for every \(\theta\in\Theta\).
A society is given by its support: the list \(\Theta\) of its \(\tau\) types with positive mass, each mass \(\mu_\theta\) a binary rational, with \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Compatibility is an explicitly given relation \(A\subseteq\Theta\times\Theta\); write \(m=|A|\), and let \(L\) denote the total input bit length. Fix an integer cycle cap \(\ell\ge3\).
A feasible cycle pattern is a cyclic sequence \(q=(\theta_1,\ldots,\theta_r)\), up to rotation, with \(2\le r\le\ell\) and \((\theta_i,\theta_{i+1})\in A\), taking \(\theta_{r+1}=\theta_1\). Types may repeat: different positions represent distinct agents of the same type. Diagonal compatibility permits exchanges between distinct agents of that type; one-agent exchanges and chains are excluded.
Let \(a_{\theta q}\) count occurrences of \(\theta\) in \(q\). Choose divisible masses \(\lambda_q\ge0\), subject to \(\sum_q a_{\theta q}\lambda_q\le\mu_\theta\), maximizing \(\sum_q|q|\lambda_q\); unused mass is permitted. Denote the optimum by \(\mathrm{OPT}\).
For every fixed \(\ell\ge3\) and \(\varepsilon>0\), does this problem admit a polynomial-time \((1+\ell(\ell-2)/6+\varepsilon)\)-approximation, or is achieving this guarantee NP-hard? Running time is measured in \(m,\tau,L\), with dependence on \(\ell,\varepsilon\) explicit.
For finite agents, maximizing the number covered by vertex-disjoint directed cycles of lengths \(2,\ldots,\ell\) admits this approximation guarantee for fixed \(\ell,\varepsilon\). A unit-capacity fractional cycle-packing LP is also explicitly studied, but no result for the exact distributional formulation above was identified. [Jia et al.](https://hanruizha.github.io/papers/approximate_barter_exchange.pdf)
The problem is exactly solvable in polynomial time for every fixed \(\ell\). Consequently, it admits the requested \((1+\ell(\ell-2)/6+\varepsilon)\)-approximation.
A direct proof enumerates all type sequences of lengths \(2,\ldots,\ell\). There are at most \(\sum_{r=2}^{\ell}\tau^r\) such sequences, so the stated optimization problem is an explicitly constructible rational linear program of polynomial size for fixed \(\ell\).
Below is a smaller formulation with running time
\(\bigl(1+L+\ell^2\tau(m+\tau)\bigr)^{O(1)}\)
in bit operations, where the exponent is an absolute constant. Thus dependence on the numerical value of \(\ell\) is polynomial, and there is no dependence on \(\varepsilon\).
For every \(s\in\Theta\) and \(r\in\{2,\ldots,\ell\}\), construct a directed graph \(H_{s,r}\). Its vertices are the source \((0,s)\), the sink \((r,s)\), and the internal vertices
\(\{(i,\theta):1\le i\le r-1,\ \theta\in\Theta\}\).
Edges go only from layer \(i\) to layer \(i+1\). Include an edge from \((i,u)\) to \((i+1,v)\) exactly when both endpoints exist and \((u,v)\in A\).
Every source-to-sink path has exactly \(r\) edges. Its sequence of tail types is a feasible cycle pattern of length \(r\): the final edge returns to type \(s\). Repeated types are permitted because different layers represent different positions. In particular, diagonal compatibility creates the path \((0,s),(1,s),(2,s)\), representing a two-agent exchange of type \(s\).
Introduce a nonnegative variable \(x^{s,r}_e\) for every edge of every graph. Require flow conservation at every internal vertex \(v\):
\(\displaystyle \sum_{e\in\delta^-(v)}x^{s,r}_e=\sum_{e\in\delta^+(v)}x^{s,r}_e.\)
Write \(t(e)\) for the type of the tail of edge \(e\). Impose the type-capacity constraints
\(\displaystyle \sum_{s\in\Theta}\sum_{r=2}^{\ell}\sum_{\substack{e\in E(H_{s,r})\\t(e)=\theta}}x^{s,r}_e\le\mu_\theta\qquad(\theta\in\Theta).\)
The objective is
\(\displaystyle \max\sum_{s\in\Theta}\sum_{r=2}^{\ell}\sum_{e\in E(H_{s,r})}x^{s,r}_e.\)
Counting edge tails is deliberate: a path representing \(q\) has exactly \(a_{\theta q}\) edges whose tails have type \(\theta\). Its final endpoint does not contribute an additional occurrence.
Take any feasible assignment \((\lambda_q)_q\). For each pattern \(q\), choose a representative \((\theta_1,\ldots,\theta_r)\), set \(s=\theta_1\), and send flow \(\lambda_q\) along the corresponding path in \(H_{s,r}\).
Each path satisfies internal flow conservation. Its contribution to the capacity constraint of type \(\theta\) is \(a_{\theta q}\lambda_q\), and its contribution to the objective is \(r\lambda_q\).
Adding these path flows therefore gives a feasible layered solution with exactly the same objective value.
Conversely, take any feasible layered solution. Fix one graph \(H_{s,r}\). Its positive flow decomposes into nonnegative source-to-sink path flows, as follows.
If a positive-flow edge exists, trace backward from its tail. At any internal vertex with a positive outgoing edge, conservation guarantees a positive incoming edge. Layer indices strictly decrease, so this tracing reaches the source. Hence a positive outgoing source edge exists.
Starting with such an edge, extend forward. At every internal vertex reached by a positive incoming edge, conservation guarantees a positive outgoing edge. Layer indices strictly increase, so the path reaches the sink.
Let \(\alpha>0\) be the minimum flow on this path. Subtract \(\alpha\) from each path edge and record the path with weight \(\alpha\). This preserves nonnegativity and internal conservation, and makes at least one positive edge zero. Repeating terminates after at most \(|E(H_{s,r})|\) iterations.
Every recorded path yields a feasible cycle pattern of length \(r\). Assign its weight to that pattern and add weights when patterns agree up to rotation. Because the decomposition reproduces every edge flow, the resulting masses satisfy
\(\displaystyle \sum_q a_{\theta q}\lambda_q=\sum_{s,r}\sum_{\substack{e\in E(H_{s,r})\\t(e)=\theta}}x^{s,r}_e\le\mu_\theta.\)
Likewise,
\(\displaystyle \sum_q |q|\lambda_q=\sum_{s,r}\sum_{e\in E(H_{s,r})}x^{s,r}_e.\)
Thus both formulations have exactly the same feasible objective values, and hence the same optimum. This argument uses the task’s permission to repeat types; every extracted path is an allowed pattern.
Each graph \(H_{s,r}\) has at most \(rm\) edges and \((r-1)\tau\) internal vertices. Across all graphs, the LP therefore has at most
\(\displaystyle \tau m\sum_{r=2}^{\ell}r=O(\tau m\ell^2)\)
variables, and at most
\(\displaystyle \tau^2\sum_{r=2}^{\ell}(r-1)+\tau=O(\tau^2\ell^2+\tau)\)
constraints, apart from nonnegativity.
All matrix coefficients belong to \(\{-1,0,1\}\), all objective coefficients equal \(1\), and the right-hand sides are the input rational masses. Consequently, even a dense encoding has bit length polynomial in \(1+L+\ell^2\tau(m+\tau)\).
The zero solution is feasible. Moreover, summing the type-capacity constraints gives
\(\displaystyle \sum_{s,r,e}x^{s,r}_e\le\sum_{\theta\in\Theta}\mu_\theta=1.\)
Since all variables are nonnegative, each variable lies in \([0,1]\). The feasible set is therefore nonempty and bounded, so an optimum exists.
The standard polynomial-time theorem for rational linear programming computes an exact rational optimum in time polynomial in the LP’s encoding length. Rational right-hand sides cause no difficulty: multiplying each capacity row by its input denominator produces integer data with polynomial encoding length. See the feasibility and optimization results in these [MIT lecture notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
The path-decomposition procedure also runs in polynomial time and outputs at most \(O(\tau m\ell^2)\) positive pattern masses. Exact arithmetic remains polynomial: a common denominator for all optimal edge-flow coordinates has bit length at most the sum of their denominator bit lengths, and every subsequent subtraction preserves that denominator.
This establishes the claimed bit-operation bound and produces an explicit optimal cycle allocation.
Set \(\rho=1+\ell(\ell-2)/6+\varepsilon\). For the stipulated parameters, \(\rho>1\). The algorithm returns a feasible allocation of value exactly \(\mathrm{OPT}\), and therefore of value at least \(\mathrm{OPT}/\rho\). This also handles \(\mathrm{OPT}=0\).
The finite-agent problem imposes integrality through vertex-disjoint cycle selection. The given distributional problem permits divisible pattern masses, making the LP itself the optimization problem. [Jia et al.](https://hanruizha.github.io/papers/approximate_barter_exchange.pdf) formulate the finite-agent problem in Definition 1 and study its fractional LP relaxation in Section 4.3. The equivalence proved above directly settles the specified distributional formulation.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. Both the direct enumeration argument and the layered formulation are correct. The latter establishes the stronger stated running-time bound, polynomial in the numerical value of \(\ell\). No major or minor mathematical issues were found.
The argument addresses the specified divisible-mass optimization problem, including repeated types, diagonal compatibility, unused mass, and exclusion of one-agent exchanges and chains.
For each length \(r\), there are at most \(\tau^r\) ordered type sequences. Testing their compatibility and identifying rotations are finite, polynomial-time operations for fixed \(\ell\). Each capacity coefficient is an integer between \(0\) and \(\ell\), and the objective coefficient is the sequence length. Thus the initial enumeration argument correctly gives a rational LP of polynomial encoding length for every fixed \(\ell\).
Counting multiple representatives of a pattern would not change the optimum, provided their variables are aggregated when producing the allocation. The subsequent formulation explicitly performs the necessary aggregation.
The construction is correct:
The terminal copy of the starting type is correctly excluded from capacity counting. Consequently, the number of path edges with tail type \(\theta\) equals \(a_{\theta q}\), including when \(\theta\) occurs repeatedly.
Choosing one representative of each rotation class yields an available path in the appropriate graph. Sending its mass along that path satisfies internal conservation.
The claimed capacity contribution \(a_{\theta q}\lambda_q\) and objective contribution \(r\lambda_q\) follow directly from the tail counts. Summing the path flows preserves feasibility and objective value. There is no requirement for integrality or for distinct types.
The decomposition argument is valid as written.
For any positive edge, backward tracing reaches the unique source: conservation supplies a positive incoming edge at every internal vertex having positive outgoing flow, and the layer index strictly decreases. Forward tracing similarly reaches the unique sink.
Subtracting the minimum positive flow on the chosen path preserves internal conservation and nonnegativity. At least one positive edge becomes zero, and no zero edge becomes positive. Therefore there are at most \(|E(H_{s,r})|\) iterations.
No residual circulation can remain, because edges strictly advance layers. Every extracted path represents an allowed pattern. Aggregating weights by rotation class preserves both occurrence counts and lengths, so the two displayed equalities are correct.
These conversions establish equality of feasible objective values in both directions, not merely an inequality between optima.
The size bounds are correct. Each of the \(r\) layer transitions contributes at most \(m\) edges, and each graph has \((r-1)\tau\) internal vertices. Summing over starting types and lengths gives the stated bounds:
\(O(\tau m\ell^2)\) variables and \(O(\tau^2\ell^2+\tau)\) constraints.
Conservation and capacity coefficients belong to \(\{-1,0,1\}\). In particular, diagonal compatibility does not create a self-loop at a layered vertex, because its endpoints occupy different layers.
Even dense storage has encoding length polynomial in \(1+L+\ell^2\tau(m+\tau)\). This justifies an absolute polynomial exponent after applying polynomial-time rational LP optimization. The claim concerns polynomial dependence on the numerical value of \(\ell\); it does not claim polynomial dependence on its binary encoding length when \(\ell\) varies.
The zero solution is feasible. Each edge variable appears in exactly one type-capacity constraint, so summing those constraints bounds the objective by \(1\). Nonnegativity then bounds every variable by \(1\).
The feasible region is closed, nonempty, and bounded; hence an optimum exists. All input data are rational. These are sufficient hypotheses for the stated exact rational LP optimization theorem, which also supplies an optimal solution with polynomial encoding length. Clearing each capacity row’s denominator preserves polynomial encoding length.
The cited [MIT lecture notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) support polynomial-time feasibility and optimization for integer-data LPs, including the finite-precision complexity discussion. The prover’s denominator-clearing step connects that result to this rational-data formulation.
The total number of recorded paths is at most the total number of layered edges, giving the claimed polynomial output size. Each decomposition iteration requires only polynomially many graph operations and rational comparisons or subtractions.
The common-denominator argument is sound: its bit length is bounded by the sum of the original coordinate denominator bit lengths, and subtraction preserves that denominator. Residual flows remain between \(0\) and \(1\), so numerator growth does not invalidate the polynomial arithmetic bound. Rotation identification and aggregation also have polynomial cost.
For \(\ell\ge3\) and \(\varepsilon>0\), the requested ratio exceeds \(1\). An exact optimal allocation therefore satisfies the requested approximation inequality, including when \(\mathrm{OPT}=0\). There is no dependence on \(\varepsilon\).
Empty compatibility, graphs with no source-to-sink paths, and support consisting of one type cause no failure in the construction or decomposition.
The contextual citation is also accurate: [Jia et al.](https://hanruizha.github.io/papers/approximate_barter_exchange.pdf) define the finite disjoint-cycle problem in Definition 1 and display its unit-capacity fractional cycle LP in Section 4.3. The prover does not rely on transferring their integral approximation theorem to this distributional setting.
No repair or additional clarification is necessary.
⟨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.