Answer: Polynomial-time computable for every fixed rational \(\rho>1\) and \(\varepsilon>0\).
Theorem 4.1 — class: algorithmic
Given a finite path template \(P=(V,E)\), a fixed rational agent-to-copy density \(\rho>1\), a homogeneous rational weight function \(w:E\to\mathbb{Q}_{\ge0}\), and \(\varepsilon>0\), take \(N,K\to\infty\) with \(N/K=\rho\) and \(K\) zero-bridge copies of \(P\). For integral whole-vertex bundle configurations \(B\), find masses \(\lambda_B\ge0\) satisfying \(\sum_B\lambda_B=1\) and \(\sum_B\lambda_B a_{B,v}=1/\rho\) for every template position \(v\), where \(a_{B,v}\) counts occurrences, such that every supported nonempty pair \(B,B'\) has some \(g\in B'\) with \(u(B)\ge u(B'\setminus\{g\})\), and \(\mathrm{SW}(\lambda)=\sum_B\lambda_Bu(B)\ge(2/3-\varepsilon)\mathrm{OPT}_\infty\), where \(\mathrm{OPT}_\infty\) drops EF1 but keeps the same discrete supplies.
Let \(P=(V,E)\) be a finite path with \(m=|V|\ge1\), homogeneous weights \(w:E\to\mathbb Q_{\ge0}\), fixed rational density \(\rho>1\), and rational \(\varepsilon>0\). Copies of the path are joined by edges of weight zero; bundles need not be connected.
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here the single valuation type has mass \(1\), so \(\tau=1\). Let \(L\) be the input bit length.
A whole-vertex configuration \(B=(S_1,\ldots,S_q)\), considered up to permutation, consists of nonempty subsets \(S_r\subseteq V\) from distinct copies; \(q\) is any finite nonnegative integer, including the empty configuration. Set \(a_{B,v}=\sum_{r=1}^q\mathbf1_{v\in S_r}\) and \(u(B)=\sum_{r=1}^q\sum_{e\in E(P[S_r])}w(e)\). Removing a vertex occurrence changes only its corresponding subset.
An allocation is a finitely supported distribution of configurations with binary rational masses \(\lambda_B\ge0\), satisfying \(\sum_B\lambda_B=1\) and \(\sum_B\lambda_Ba_{B,v}=1/\rho\) for every \(v\in V\).
It is EF1 if, for every supported \(B\) and supported nonempty \(B'\), some vertex occurrence \(g\in B'\) satisfies \(u(B)\ge u(B'\setminus\{g\})\); the observing configuration \(B\) may be empty.
Define \(\mathrm{SW}(\lambda)=\sum_B\lambda_Bu(B)\) and let \(\mathrm{OPT}_\infty\) be its supremum over these distributions with EF1 omitted but all supply equalities retained.
For every fixed rational \(\rho>1\) and \(\varepsilon>0\), can an EF1 allocation with \(\mathrm{SW}(\lambda)\ge(2/3-\varepsilon)\mathrm{OPT}_\infty\) always be computed in time polynomial in \(m,\tau,L\), or is achieving this guarantee NP-hard for some fixed \(\rho,\varepsilon\)?
For finite paths and \(n\) homogeneous agents, a polynomial-time algorithm guarantees EF1 and welfare at least \((2/3-2/(3(n+1)))\) times unrestricted optimal welfare; a four-vertex, two-agent example rules out a universal guarantee above \(2/3\). [Source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p2641.pdf)
No result settling the configuration-distribution approximation question above was located.
The first alternative holds. For every fixed rational \(\rho>1\) and \(\varepsilon>0\), an EF1 allocation satisfying the requested guarantee can be computed in time polynomial in \(m,\tau,L\).
The key is to apply the finite-path algorithm to a sufficiently large, but constant, number of copies and then take the empirical distribution of its agents’ configurations. Throughout, rational numbers are encoded by binary numerators and denominators.
Write \(W=\sum_{e\in E}w(e)\). We first prove that \(\mathrm{OPT}_\infty=W/\rho\), with the supremum attained.
For an edge \(e=\{v,z\}\) and a configuration \(B=(S_1,\ldots,S_q)\), define
\[
c_{B,e}=\sum_{r=1}^{q}\mathbf 1_{\{v,z\}\subseteq S_r}.
\]
Equivalently, using the requested inline delimiters, \(c_{B,e}\) counts the copies in which both endpoints belong to the configuration. Every such copy contributes an occurrence of \(v\), so \(c_{B,e}\le a_{B,v}\). Consequently, every feasible distribution satisfies
\(\displaystyle \mathrm{SW}(\lambda)=\sum_{e\in E}w(e)\sum_B\lambda_Bc_{B,e}\le\sum_{e\in E}w(e)\sum_B\lambda_Ba_{B,v}=\frac{W}{\rho},\)
where the supply equality is applied separately at an endpoint of each edge.
Conversely, assign mass \(1/\rho\) to the configuration consisting of one whole copy \(V\), and mass \(1-1/\rho\) to the empty configuration. This satisfies every supply equality and has welfare \(W/\rho\). Hence
\(\displaystyle \mathrm{OPT}_\infty=\frac{W}{\rho}.\)
If \(W=0\), this distribution is also EF1 because every configuration has utility zero, and it solves the problem. Assume henceforth that \(W>0\).
We use the following established result: on a finite path with nonnegative edge weights and \(n\) homogeneous agents, a polynomial-time algorithm produces a complete EF1 allocation whose welfare is at least \(\bigl(2/3-2/(3(n+1))\bigr)\) times unrestricted optimal welfare. This is [Theorem 4.1 of Chen, Li, Li, and Zhang](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p2641.pdf).
Write \(\rho=a/b\), where \(a>b\ge1\) are coprime integers. Choose
\(\displaystyle t=\max\left\{1,\left\lceil\frac{2}{3a\varepsilon}\right\rceil\right\},\qquad K=bt,\qquad n=at.\)
Then \(K/n=1/\rho\) and \(2/(3(n+1))\le\varepsilon\).
Construct a finite path \(Q\) by concatenating \(K\) labeled copies of \(P\), joining consecutive copies by edges of weight zero. Give each of the \(n\) agents the same induced-edge valuation.
The finite theorem applies: \(Q\) is a path, all weights are nonnegative, valuations are homogeneous, and bundles may be disconnected. Its unrestricted optimal welfare is exactly \(KW\). Indeed, allocating all vertices to one agent attains \(KW\), while no allocation can count any edge more than once.
Therefore the theorem produces a partition \(X_1,\ldots,X_n\) of \(V(Q)\), which is EF1 and satisfies
\(\displaystyle \sum_{i=1}^{n}u_Q(X_i)\ge\left(\frac23-\frac{2}{3(n+1)}\right)KW.\)
Identify each labeled copy with \(V\). For agent \(i\) and copy \(r\), let
\(S_{i,r}=\{v\in V:\text{the occurrence of }v\text{ in copy }r\text{ belongs to }X_i\}.\)
Let \(B_i\) consist of the nonempty subsets among \(S_{i,1},\ldots,S_{i,K}\), considered up to permutation. Repeated subsets remain repeated entries, since they come from distinct copies. If all subsets are empty, \(B_i\) is the empty configuration.
Assign mass \(1/n\) to each \(B_i\), combining identical configurations. Thus
\(\displaystyle \lambda_B=\frac{|\{i:B_i=B\}|}{n}.\)
These are nonnegative binary-encoded rational masses, with finite support and total mass one.
For each \(v\in V\), its \(K\) labeled occurrences are each allocated exactly once. Hence
\(\displaystyle \sum_{i=1}^{n}a_{B_i,v}=K,\qquad \sum_B\lambda_Ba_{B,v}=\frac{K}{n}=\frac1\rho.\)
This verifies every required supply equality exactly.
The joining edges have weight zero. Therefore
\(u(B_i)=u_Q(X_i)\)
for every \(i\). Moreover, deleting a vertex \(x\in X_i\) corresponds to deleting its occurrence \(g\) in the appropriate subset of \(B_i\), and
\(u(B_i\setminus\{g\})=u_Q(X_i\setminus\{x\}).\)
If deletion makes that subset empty, omitting it does not change utility.
Take any supported configurations \(B,B'\), with \(B'\) nonempty. Choose representatives \(i,j\) such that \(B_i=B\) and \(B_j=B'\). Then \(X_j\) is nonempty.
Finite EF1 supplies a vertex \(x\in X_j\) satisfying
\(u_Q(X_i)\ge u_Q(X_j\setminus\{x\}).\)
For the corresponding occurrence \(g\in B'\), utility preservation gives
\(u(B)\ge u(B'\setminus\{g\}).\)
This also covers an empty observing configuration. Combining identical configurations therefore preserves EF1.
Finally,
\(\displaystyle \mathrm{SW}(\lambda)=\frac1n\sum_{i=1}^{n}u_Q(X_i)\ge\left(\frac23-\frac{2}{3(n+1)}\right)\frac{KW}{n}\ge\left(\frac23-\varepsilon\right)\frac{W}{\rho}=\left(\frac23-\varepsilon\right)\mathrm{OPT}_\infty.\)
For fixed \(\rho\) and \(\varepsilon\), the integers \(K\) and \(n\) are constants. The replicated path has \(Km\) vertices and a rational encoding of length polynomial in \(m,L\).
The finite algorithm performs polynomially many utility computations and comparisons. Exact arithmetic has polynomial bit complexity: multiplying the input weights by the product of their denominators converts them to integers of polynomial bit length, without changing EF1 or the welfare ratio. Utility sums then also have polynomial bit length.
The output has at most \(n\) supported configurations, each containing at most \(K\) subsets of \(V\). Their subsets can be encoded explicitly, and every mass has denominator \(n\). Forming and combining the configurations takes polynomial time.
Thus the construction meets the requested polynomial bound. The auxiliary agents all share the single supported valuation type, so the society still has \(\tau=1\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The replication construction resolves the configuration-distribution question for every fixed rational \(\rho>1\) and \(\varepsilon>0\). No mathematical gaps or false steps were found.
For every configuration and edge \(e=\{v,z\}\), the inequality \(c_{B,e}\le a_{B,v}\) holds occurrence by occurrence: each copy counted by \(c_{B,e}\) contains an occurrence of \(v\) counted by \(a_{B,v}\). Nonnegative weights permit summing these inequalities.
The support of an allocation and the edge set are finite, so interchanging the sums is justified. Applying the supply equality separately at the chosen endpoint of each edge gives \(\mathrm{SW}(\lambda)\le W/\rho\).
The proposed distribution on one whole copy and the empty configuration has nonnegative rational masses summing to one, because \(\rho>1\). Its expected occurrence count is \(1/\rho\) at every vertex, and its welfare is \(W/\rho\). Thus the supremum is attained and equals the stated benchmark.
Since the weights are nonnegative, \(W=0\) implies that all edge weights vanish. Every configuration then has utility zero, including after deletion. The proposed distribution satisfies EF1 and all supply equalities.
This also covers the single-vertex case \(m=1\).
Theorem 4.1 of the cited paper states the polynomial-time EF1 guarantee with approximation factor \(2/3-2/(3(n+1))\). Its model permits nonnegative edge weights, arbitrary vertex bundles, and complete allocations; its EF1 definition includes empty observing bundles and requires deletion only from nonempty compared bundles. These match the application in the write-up. [Chen, Li, Li, and Zhang, Definitions in Section 2 and Theorem 4.1](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p2641.pdf)
In particular, zero-weight joining edges and disconnected bundles introduce no hypothesis violation. No condition requiring fewer agents than vertices is imposed in the stated model.
Writing \(\rho=a/b\) in lowest terms gives positive integers \(a>b\). The selected \(t\) is a positive integer, and \(K=bt\), \(n=at\) satisfy \(K/n=1/\rho\).
The bound \(t\ge 2/(3a\varepsilon)\) implies \(n\ge 2/(3\varepsilon)\), hence \(2/(3(n+1))\le\varepsilon\). This remains valid for every positive \(\varepsilon\).
Concatenating the copies produces a finite path. Its total edge weight is \(KW\), since joining edges contribute zero. Assigning every vertex to one agent attains this welfare; no allocation can count an edge more than once. Therefore its unrestricted optimum is exactly \(KW\), as claimed.
Each nonempty intersection \(S_{i,r}\) belongs to a distinct labeled copy. Omitting empty intersections yields a permitted configuration; retaining repeated subsets as repeated entries correctly preserves their multiplicity.
Passing to configurations up to permutation loses no occurrence counts or utilities. Combining identical configurations produces nonnegative rational masses with total mass one and support size at most \(n\).
For every original vertex \(v\), the finite partition allocates its \(K\) occurrences exactly once. Consequently, averaging over the \(n\) agents gives the required supply equality exactly, rather than approximately.
Every positive-weight edge lies within an original copy. Therefore the utility of \(B_i\) equals that of \(X_i\). This identity also holds after removing a corresponding vertex occurrence: the only additional finite-path edges potentially affected are zero-weight joining edges.
For any supported pair \(B,B'\) with \(B'\) nonempty, representatives \(i,j\) exist, and \(X_j\) is nonempty. The finite EF1 witness therefore transfers to an occurrence in \(B'\), giving precisely the required inequality.
Empty observing configurations are covered by the finite EF1 definition. If the representatives coincide, deleting a vertex cannot increase induced-edge utility because weights are nonnegative; thus self-comparisons cause no exception. Combining identical configurations creates no new comparison without such representatives.
Combining equal configurations preserves their total weighted utility, so \(\mathrm{SW}(\lambda)=n^{-1}\sum_i u_Q(X_i)\). Substituting the finite guarantee, \(K/n=1/\rho\), the parameter bound, and the established benchmark yields the requested approximation.
All inequality directions are valid because \(W/\rho\ge0\). The calculation also remains valid when \(2/3-\varepsilon\) is nonpositive.
For fixed \(\rho\) and \(\varepsilon\), both \(K\) and \(n\) are constants. Replication therefore increases the input size by only a constant factor.
The product of the input denominators has bit length bounded by their total encoding length. Scaling weights by this positive integer preserves EF1 and welfare ratios and gives integer weights of polynomial bit length. Utility sums and comparisons consequently admit exact polynomial-bit arithmetic.
Each output configuration contains at most \(K\) explicitly represented subsets, and there are at most \(n\) supported configurations. Comparing and combining these finite multisets is polynomial time. The construction introduces auxiliary agents, but no additional supported valuation types, so \(\tau=1\) is respected.
No additional clarification is needed to verify the mathematical argument. The result establishes the polynomial-time alternative under the encoding specified in the task; it does not require a limiting argument or growing replication count.
⟨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.