Answer: The continuous decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). The optimization supremum and its attainment are computable in polynomial time, although a maximizing finite forest need not exist.
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWMaxP is NP-complete and OWMaxP cannot be ap- proximated with an approximation ratio better than 1−1/𝑒 if 𝑃≠𝑁𝑃, even when all voters have weight one. To obtain more positive results, we consider both the approxi- mation and the parameterized complexity viewpoints. An approximation algorithm point of view. Interestingly, a variant of OWMaxP, called DTO (Directed Tree Orienteering), has been investigated by Ghuge and Nagarajan [20].
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite complete role types \(T\), rational masses \(\mu_t\) summing to \(1\), a role-symmetric support relation \(A\subseteq T\times T\), a baseline action \(d_0:T\to T\cup\{\mathrm{vote}\}\), target role \(r\in T\), normalized budget \(B\), and target mass \(\theta\), choose a finite mass-valued acyclic delegation forest whose subcohort masses sum to \(\mu_t\), whose arcs obey \(A\), and whose changed-delegation mass \(\sum_v a_v\mathbf{1}[p(v)\ne d_0(\ell(v))]\) is at most \(B\); decide whether at least \(\theta\) mass has a delegation root of type \(r\), and maximize that rooted mass in the optimization version.
A society is given by its support: a nonempty list \(T\) of \(\tau\) complete role types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; there are no separate candidates, so set \(m=\tau\). Let \(L\) be the total input bit length.
Input also specifies a directed relation \(A\subseteq T\times T\), a baseline action \(d_0:T\to T\cup\{\mathrm{vote}\}\), a target role \(r\in T\), and binary-rational numbers \(B,\theta\in[0,1]\). Every baseline delegation \(d_0(t)=s\) obeys \((t,s)\in A\), and the baseline delegation arcs are acyclic. Voting directly is always permitted.
Roles determine all delegation permissions and baseline actions: any subcohort of type \(t\) may delegate to any distinct subcohort of type \(s\) exactly when \((t,s)\in A\). The relation need not be reciprocal.
A solution is a finite directed forest with vertices \(v\) carrying labels \(\ell(v)\in T\) and positive real masses \(a_v\), satisfying \(\sum_{v:\ell(v)=t}a_v=\mu_t\). Each vertex either votes directly or has one outgoing arc to its parent; every delegation arc obeys \(A\), and every chain terminates at a voting root.
Define \(p(v)=\mathrm{vote}\) at a root and \(p(v)=\ell(u)\) when \(u\) is its parent. The change cost is \(C=\sum_v a_v\mathbf{1}[p(v)\ne d_0(\ell(v))]\); changing the recipient within the same role costs nothing. There are no recipient capacities.
Let \(\rho(v)\) be the root reached from \(v\), including \(v\) itself when it is a root. The target-rooted mass is \(M_r=\sum_{v:\ell(\rho(v))=r}a_v\), summed over all roots of role \(r\). The decision problem asks whether a solution satisfies \(C\le B\) and \(M_r\ge\theta\); the optimization version maximizes \(M_r\) subject to \(C\le B\).
Is this continuous decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite indivisible voters, maximizing one voter's accumulated weight by changing a budgeted number of delegation choices is \(\mathrm{NP}\)-complete, even with unit weights; its optimization version has no polynomial-time approximation ratio better than \(1-1/e\) unless \(\mathrm{P}=\mathrm{NP}\). [Source](https://ifaamas.org/Proceedings/aamas2022/pdfs/p336.pdf)
No result settling exactly the mass-valued problem above was located in the literature search.
The continuous decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
The proof requires more than an ordinary linear relaxation: positive-mass recipients must actually exist and have paths to voting roots. These requirements can be enforced by a polynomial sequence of linear programs and graph reachability computations.
For optimization, the supremum is computable exactly in polynomial time, and its attainment is decidable in polynomial time. However, a maximizing forest need not exist, even under the stated baseline-acyclicity assumption.
Partition vertices into two classes according to their terminal roots:
For every \((t,s)\in A\) and \(k\in\{0,1\}\), introduce a nonnegative variable \(x_{ts}^k\). It represents the own mass of class-\(k\) vertices of role \(t\) that delegate to role \(s\). It does not represent the accumulated mass carried by that delegation.
Also introduce nonnegative variables \(z_t^k\), representing the mass of class-\(k\) voting roots of role \(t\). Require
\[ z_t^1=0\quad(t\ne r),\qquad z_r^0=0. \]
For every \(t\in T\), mass conservation is
\[ \sum_{k\in\{0,1\}}\left(z_t^k+\sum_{s:(t,s)\in A}x_{ts}^k\right)=\mu_t. \]
Define the linear cost and target-mass functions by
\[ c(x,z)= \sum_{k\in\{0,1\}}\sum_{(t,s)\in A} \mathbf 1[s\ne d_0(t)]x_{ts}^k + \sum_{k\in\{0,1\}}\sum_{t\in T} \mathbf 1[\mathrm{vote}\ne d_0(t)]z_t^k \]
and
\[ f(x,z)=\sum_{t\in T}\left(z_t^1+\sum_{s:(t,s)\in A}x_{ts}^1\right). \]
Every forest induces these variables by summing vertex masses according to their class and action. Its cost and target-rooted mass are exactly \(c(x,z)\) and \(f(x,z)\).
Thus the decision constraints yield a rational polytope \(P\): nonnegativity, mass conservation, the root restrictions, and
\[ c(x,z)\le B,\qquad f(x,z)\ge\theta. \]
There are \(N=2|A|+2\tau\) variables. Every variable is at most \(1\), so \(P\) is bounded.
The missing requirement is whether an aggregate point can actually be realized by a finite forest.
For a nonnegative aggregate point satisfying mass conservation and the root restrictions, define, for each class \(k\),
\[ E_k=\{(t,s)\in A:x_{ts}^k>0\}, \qquad V_k=\{t\in T:z_t^k>0\}. \]
Let \(R_k\) be the roles from which some role in \(V_k\) is reachable in the directed graph \((T,E_k)\). A path of length zero is permitted, so \(V_k\subseteq R_k\).
Lemma. The aggregate point is realizable by a finite forest if and only if
\[ x_{ts}^k>0\ \Longrightarrow\ s\in R_k \]
for every delegation coordinate.
Suppose \(x_{ts}^k>0\) in a forest. Some positive-mass class-\(k\) vertex of role \(t\) delegates to a vertex of role \(s\).
Follow that recipient’s chain to its voting root. Every delegation along this chain contributes positive own mass to the corresponding class-\(k\) coordinate, and the root contributes positive mass to the corresponding \(z^k\) coordinate. Consequently, this chain gives a directed walk from \(s\) to \(V_k\), using only arcs in \(E_k\).
Hence \(s\in R_k\).
Assume the condition holds. We construct a forest realizing every coordinate exactly.
For each positive delegation coordinate \(x_{ts}^k\), choose a simple directed path from \(s\) to \(V_k\) in \((T,E_k)\). Create a fresh vertex path beginning with the delegation \(t\to s\), continuing along the chosen path, and ending at a voting root.
For each positive root coordinate \(z_t^k\), also create a fresh singleton voting root.
All these paths use distinct vertices. Their labels may repeat: even if the initial role \(t\) appears later on its path, the corresponding vertices are distinct subcohorts.
Let \(K\) be the total number of vertices created. Each positive coordinate contributes one path with at most \(\tau+1\) vertices, so
\[ K\le N(\tau+1). \]
Let \(h\) be the smallest positive aggregate coordinate, and assign every created vertex mass
\[ \delta=\frac{h}{2K}. \]
Each vertex consumes mass from its corresponding action coordinate. A coordinate occurs at most \(K\) times, so its total consumption is at most
\[ K\delta=\frac h2. \]
Therefore every positive coordinate still has a positive residual.
Allocate these residuals as follows:
Every added delegating vertex is a new leaf attached to an existing path. Thus no directed cycle is created, and every chain terminates at a voting root.
All vertices have positive mass, every delegation respects \(A\), and every coordinate is realized exactly. Consequently, role masses, cost, and target-rooted mass are preserved.
This construction uses at most \(N(\tau+1)+N\) vertices. It relies on the absence of recipient capacities.
We use the standard theorem that rational linear programming is solvable in time polynomial in its encoding length, with exact rational optimal solutions of polynomial bit length. See, for example, [Nemirovski’s linear-programming lecture notes](https://www2.isye.gatech.edu/~nemirovs/Lec_EMCO.pdf).
For any nonempty current polytope \(P\), maximize each coordinate separately over \(P\).
For every coordinate whose maximum is positive, choose a maximizing point. Average these chosen points, obtaining a point \(w\in P\).
Because all coordinates are nonnegative,
\[ w_i>0 \quad\Longleftrightarrow\quad \text{some point of }P\text{ has coordinate }i\text{ positive}. \]
Thus \(w\) has maximal support: the support of every point in \(P\) is contained in the support of \(w\).
Computing \(w\) requires at most \(N\) linear-program optimizations.
Start with the decision polytope from Section 1. Repeat:
Maintain the invariant that every forest satisfying the original decision constraints induces a point in the current polytope.
Suppose a positive coordinate \(w_{ts}^k\) has \(s\notin R_k\). If a feasible forest had \(x_{ts}^k>0\), necessity in the realization lemma would give a path from \(s\) to a class-\(k\) voting root using positive coordinates of that forest.
But all those coordinates belong to the support of \(w\), by maximality of its support. The same path would therefore exist in the graph constructed from \(w\), contradicting \(s\notin R_k\).
Hence every feasible forest has \(x_{ts}^k=0\). Adding that equation preserves the invariant.
Every pruning round sets to zero at least one coordinate that was positive at the current point. Such a coordinate cannot already have been fixed to zero. There are only \(N\) coordinates, so there are at most \(N\) pruning rounds.
If the algorithm returns NO, the invariant shows that no feasible forest exists.
If it returns YES, the realization lemma produces a finite forest whose cost is at most \(B\) and whose target-rooted mass is at least \(\theta\).
Therefore the algorithm decides the problem exactly.
There are at most \(N+1\) rounds, each using at most \(N\) linear-program optimizations and two graph reachability computations. Pruning adds only coordinate-zero equations, so every linear program has encoding length polynomial in \(L\) and \(N\).
Since
\[ N=2|A|+2\tau=O(\tau^2), \]
the running time is polynomial in \(m,\tau,L\), where \(m=\tau\).
The averaged LP solutions have polynomial rational bit length. The realization construction uses polynomially many vertices, and its masses are obtained through rational arithmetic of polynomial bit length. Thus every YES instance also has a polynomial-size rational forest witness.
Run the same pruning algorithm with the budget constraint but without the target threshold. Let \(Q\) be the final polytope and \(w\) its maximal-support point.
The baseline forest is feasible with cost zero: use one vertex of mass \(\mu_t\) for each role and its baseline action. Baseline acyclicity ensures every chain terminates at a voting root. Therefore this run cannot end with an empty polytope.
Compute
\[ S=\max_{q\in Q}f(q) \]
by rational linear programming.
Every budget-feasible forest induces a point in \(Q\), by soundness of pruning. Hence its target-rooted mass is at most \(S\).
Conversely, let \(q^\star\) attain the displayed LP maximum. For any \(0<\lambda\le1\), define
\[ q_\lambda=(1-\lambda)q^\star+\lambda w. \]
This point belongs to \(Q\). Its support equals the support of \(w\), because all coordinates are nonnegative and every coordinate positive in \(q^\star\) is also positive in \(w\).
Therefore the realization lemma applies to \(q_\lambda\), and
\[ f(q_\lambda)=(1-\lambda)S+\lambda f(w)\longrightarrow S \]
as \(\lambda\) tends to zero.
Thus \(S\) is exactly the supremum over finite forests. It is rational and computable in polynomial time.
To decide whether the supremum is attained, run the decision algorithm with threshold \(\theta=S\). A YES answer produces a maximizing forest; a NO answer certifies nonattainment. Arbitrarily close rational forests can also be constructed using \(q_\lambda\).
Consider three roles \(T=\{r,s,t\}\), with
\[ \mu_r=\frac14,\qquad \mu_s=\frac14,\qquad \mu_t=\frac12. \]
Let
\[ A=\{(t,s),(s,t),(t,r)\}, \]
and let the baseline actions be
\[ d_0(r)=\mathrm{vote},\qquad d_0(s)=\mathrm{vote},\qquad d_0(t)=s. \]
The baseline delegation graph is acyclic. Set \(B=\frac18\).
For any forest, let \(x\) be its target-rooted mass of role \(s\), and let \(y\) be the mass of role-\(t\) vertices delegating directly to role \(r\).
Every target-rooted role-\(s\) vertex must delegate, changing its baseline action. Every role-\(t\) vertex delegating to \(r\) also changes its baseline action. These are disjoint sets of vertices, so
\[ C\ge x+y. \]
If any role-\(s\) or role-\(t\) mass reaches \(r\), its chain must contain a \(t\to r\) arc. Its source vertex has positive mass, so \(y>0\). In that case,
\[ M_r\le\mu_r+\mu_t+x \le\frac34+B-y <\frac78. \]
If no role-\(s\) or role-\(t\) mass reaches \(r\), then \(M_r\le\frac14\). Thus no budget-feasible forest attains \(\frac78\).
Nevertheless, for every \(0<\varepsilon<\frac18\), construct the chain
\[ t_{\mathrm{bulk}}\to s_{\mathrm{target}}\to t_{\mathrm{connector}}\to r \]
with respective masses
\[ \frac12-\varepsilon,\qquad \frac18-\varepsilon,\qquad \varepsilon,\qquad \frac14. \]
The remaining role-\(s\) mass, \(\frac18+\varepsilon\), votes directly.
The only changed actions are those of \(s_{\mathrm{target}}\) and \(t_{\mathrm{connector}}\). Hence
\[ C=\left(\frac18-\varepsilon\right)+\varepsilon=\frac18, \]
while
\[ M_r=\frac78-\varepsilon. \]
Therefore the supremum is \(\frac78\), but no maximizing forest exists.
This nonattainment does not affect the decision classification: exact feasibility, including equality at a proposed threshold, is decided by the support-pruning algorithm.
⟨structured verdict parsed — rendered above⟩
The output resolves the continuous decision problem as stated. The realization lemma, support-pruning algorithm, polynomial bit-complexity claim, and optimization conclusions are correct. I found no major or minor issues requiring repair.
The variables record each vertex’s own mass according to its role, action, and terminal-root class. This matches both quantities in the task: change cost depends on the vertex’s own action, and target-rooted mass counts its own mass according to the eventual root.
The root restrictions correctly characterize the two classes: class \(1\) roots must have role \(r\), and class \(0\) roots must have a different role. The conservation equations count each vertex exactly once.
Consequently, every admissible forest induces a point satisfying the stated constraints, with cost \(c(x,z)\) and target-rooted mass \(f(x,z)\). The prover correctly treats the converse as requiring a separate realization argument.
Nonnegativity and conservation imply that every coordinate is at most its source role’s mass, hence at most \(1\). Thus the polytope is bounded. Its constraints have rational coefficients and polynomial encoding length.
A positive aggregate delegation coordinate comes from at least one positive-mass vertex because the forest is finite. Its recipient belongs to the same terminal-root class.
Following that recipient’s chain yields a directed walk using positive coordinates of that class and ending at a positive root coordinate. Therefore the recipient role belongs to \(R_k\).
Repeated role labels along this walk cause no problem: reachability is defined on roles, while the forest’s vertices remain distinct. Necessity is established.
Every selected recipient-to-root path uses positive delegation coordinates and ends at a positive root coordinate. Thus every vertex created on a scaffold path has an available coordinate from which to draw its mass.
A simple path from \(s\) to a root role has at most \(\tau\) vertices. Prepending the source vertex of the initial delegation gives at most \(\tau+1\) vertices. The stated bound \(K\le N(\tau+1)\) is valid, including singleton roots.
The minimum positive coordinate \(h\) exists: there are finitely many coordinates, and conservation with total mass \(1\) ensures that at least one is positive. Giving each scaffold vertex mass
\(\delta=h/(2K)\) consumes at most \(h/2\) from any coordinate. Every positive coordinate therefore retains a strictly positive residual.
Residual delegation vertices attach to an existing recipient vertex on the corresponding scaffold. Residual root vertices vote directly. These operations preserve termination at roots and create no cycles. All delegation endpoints are distinct vertices, including when their role labels coincide.
The construction realizes every action coordinate exactly. Its class assignments agree with its actual terminal roots because each scaffold ends at a root permitted for its designated class. Conservation, cost, and target-rooted mass are therefore preserved.
The lemma is fully established. The absence of recipient capacities is used exactly where needed: arbitrarily large residual masses may delegate to small scaffold recipients.
Each coordinate maximum exists because the current polytope is nonempty and compact.
For every coordinate that can be positive, its selected maximizing point makes that coordinate positive. Averaging these points preserves feasibility by convexity. Nonnegativity prevents cancellation.
Conversely, a coordinate that cannot be positive is zero at every feasible point and therefore zero in the average. The claimed support equivalence follows.
The averaging family cannot be empty on a nonempty current polytope: mass conservation forces positive coordinates. Thus this procedure has no undefined empty-average case.
The maintained invariant initially holds by the aggregate construction.
If a forest represented in the current polytope used a coordinate proposed for deletion, the necessity direction of the realization lemma would supply a positive-coordinate path from its recipient to an appropriate root.
Maximal support guarantees that every coordinate on this path, including the root coordinate, is positive in \(w\). The same path would therefore appear in the graph used to compute \(R_k\), contradicting the deletion criterion.
Hence every deleted coordinate is zero in every feasible forest still under consideration. Simultaneously deleting all such coordinates preserves the invariant. This argument applies to forests with arbitrary real masses; it does not assume rationality of their aggregates.
Each unsuccessful nonempty round fixes at least one previously unfixed coordinate to zero. A coordinate already fixed to zero cannot be positive in \(w\). Therefore there are at most \(N\) pruning rounds and at most \(N+1\) iterations overall.
An empty current polytope excludes every feasible forest by the invariant. An accepted maximal-support point satisfies the realization lemma and yields a forest meeting both inequalities.
Thus both NO and YES answers are justified, including exact equality at the budget or threshold. The argument does not replace exact feasibility with feasibility in a closure.
The invoked theorem is applicable: feasibility and exact optimization for rational linear programs are polynomial-time operations in the binary encoding length; nonempty bounded feasible regions admit rational optimal solutions of polynomial bit length. The cited notes discuss polynomial-time feasibility, polynomial-size rational solutions, and recovery of exact solutions in Sections 4.2–4.2.2. [Nemirovski’s lecture notes](https://www2.isye.gatech.edu/~nemirovs/Lec_EMCO.pdf)
All LPs here have rational data and bounded feasible regions. Pruning adds only coordinate-zero equations. No progressively larger rational coefficients enter subsequent LP constraints.
There are polynomially many LP calls: at most \(N\) coordinate optimizations per iteration, together with feasibility checks. Reachability computations are also polynomial. Since \(N=O(\tau^2)\) and \(m=\tau\), the claimed running time is polynomial in \(m,\tau,L\).
Averaging polynomially many rational solutions of polynomial bit length preserves polynomial bit length. Selecting \(h\), dividing by \(2K\), and allocating residuals also preserve polynomial bit length. Together with the polynomial vertex bound, this establishes the claimed rational witness size.
The baseline construction is admissible: each delegation respects \(A\), and finite acyclicity ensures every chain terminates at a voting vertex. It has cost zero. Thus the budget-only pruning run cannot eliminate all feasible points.
At termination, \(Q\) is nonempty and compact, and its maximal-support point \(w\) satisfies the realization criterion. Every budget-feasible forest induces a point in \(Q\), so the LP optimum \(S\) is an upper bound on attainable target-rooted mass.
For every \(0<\lambda\le1\), the stated convex combination belongs to \(Q\) and has exactly the support of \(w\). The realization criterion depends only on that support, so it applies to every such combination. Their objective values converge to \(S\).
This correctly establishes that \(S\) is the supremum, without assuming that an LP optimizer itself is realizable.
Testing threshold \(S\) correctly decides attainment: no feasible forest exceeds \(S\), so meeting that threshold is equivalent to attaining the supremum. The polynomial-size rational encoding of \(S\) makes the additional decision run polynomial-time.
All role masses are positive and sum to \(1\). The baseline’s sole delegation is \(t\to s\), which belongs to \(A\) and is acyclic.
Every target-rooted role-\(s\) vertex changes its baseline voting action. Every role-\(t\) vertex delegating to \(r\) also changes its baseline action. These vertex sets are disjoint, so \(C\ge x+y\) is correct.
The only permitted delegation entering role \(r\) is \(t\to r\). Therefore, if any role-\(s\) or role-\(t\) mass reaches \(r\), a positive-mass source of such an arc exists and \(y>0\). The resulting bound
\(M_r\le3/4+B-y<7/8\)
is valid. If no such mass reaches \(r\), only role-\(r\) mass contributes, giving the stated alternative bound.
In the proposed family, all masses are positive for \(0<\varepsilon<1/8\). Role-\(t\) masses sum to \(1/2\), role-\(s\) masses sum to \(1/4\), and the role-\(r\) mass is \(1/4\). All three delegation arcs are permitted, and the two role-\(t\) vertices are distinct.
Exactly the claimed actions change. Rechecking the totals gives \(C=1/8\) and \(M_r=7/8-\varepsilon\). The family therefore approaches the upper bound without attaining it. The nonattainment claim is proved.
Empty terminal-root classes are handled by empty root and reachability sets. Zero-length recipient-to-root paths are explicitly permitted. Self-role delegation permissions are handled through distinct vertices. The reasoning also covers \(\tau=1\), zero budget, and thresholds \(0\) and \(1\), without division by a vanishing quantity.
No additional lemma, clarification, or correction is needed. The output establishes polynomial-time exact decision, polynomial-time computation of the optimization supremum, and polynomial-time determination of its attainment.
⟨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.