Answer: Polynomial-time exactly solvable; consequently a polynomial-time \(\tfrac12\log_2 k\)-approximation exists. A conservative exact running time is \(O(\tau(m+\tau)^2L^3)\) bit operations.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to approximate the MinMaxWeight problem to a factor of 1 2 log2 |V |, even when each node has outdegree at most 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T=D\dot\cup V\), rational distribution \(\mu\), and at most two permitted target types \(R(t)\) for each \(t\in D\), choose a measurable acyclic resolution in which every infinitesimal delegator selects one concrete delegate from a permitted target type, retain maximum reachable mass, and minimize \(z=\max_{v\in V:\mu_v>0} w_v/\mu_v\), where \(w_v\) is the total mass ultimately voting through voter type \(v\).
A society is given by its support: \(T=D\dot\cup V\), the list of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each delegator type has permitted target types \(R(t)\subseteq T\), with \(|R(t)|\leq2\); voter types have no delegation options. Write \(k=|V|\geq4\), \(m=\sum_{t\in D}|R(t)|\), and let \(L\) be the total input bit length.
Realize type \(t\) as the atomless interval \(X_t=\{t\}\times[0,\mu_t)\), with Lebesgue mass \(\lambda\), and put \(X=\dot\bigcup_tX_t\).
A resolution consists of a Borel retained set \(S\subseteq X\) containing every voter interval and a Borel map \(f:S\cap\bigcup_{t\in D}X_t\to S\). For \(x\in X_t\), the concrete delegate \(f(x)\) must belong to a type in \(R(t)\).
Every retained delegator's chain must terminate at a voter after finitely many steps; cycles and infinite chains are forbidden. Each person sends all mass received onward to that person's single delegate; different persons of the same type may choose different delegates.
First maximize \(\lambda(S)\). Among such resolutions, minimize \(z=\max_{v\in V}w_v/\mu_v\), where \(w_v\) is the mass of retained persons whose terminal voter belongs to \(X_v\), including the voters' own mass.
Does this continuous problem admit a polynomial-time \(\tfrac12\log_2 k\)-approximation, or is achieving that approximation factor NP-hard? State running times in \(m,\tau,L\).
For finite unit-weight agents, achieving factor \(\tfrac12\log_2 k\) is NP-hard even with at most two options per delegator; a polynomial-time \((1+\ln k)\)-approximation is known. [Source](https://procaccia.info/wp-content/uploads/2020/03/fluid.pdf).
No result settling the approximation question for this concrete-delegate atomless model was located.
The problem is polynomial-time exactly solvable. Consequently, it admits a polynomial-time \(\tfrac12\log_2 k\)-approximation, because \(k\geq4\) implies \(\tfrac12\log_2 k\geq1\).
A conservative bound for computing the exact optimum and a finite description of an optimal Borel resolution is
\(O\!\left(\tau(m+\tau)^2L^3\right)\)
bit operations. Since \(m\leq2\tau\), this is also \(O(\tau^3L^3)\).
The essential feature is that the stated model permits a concrete person of zero Lebesgue mass to receive positive mass. Distinct such persons can forward distinct streams through the same type. The construction below respects the requirement that each concrete person has only one delegate.
Form the directed type graph with vertex set \(T\) and arcs \(t\to u\) for \(t\in D\) and \(u\in R(t)\). Let
\(A=\{t\in T:\text{some directed path from }t\text{ ends in }V\}\), and \(D_A=A\cap D\).
Every voter belongs to \(A\). Every person in a valid resolution belongs to a type in \(A\): their finite delegation chain gives a directed walk to a voter, hence reachability in the type graph. Therefore every valid resolution satisfies
\(\lambda(S)\leq\sum_{t\in A}\mu_t\).
This bound is attainable. For each \(t\in D_A\), choose a successor \(h(t)\in R(t)\cap A\) whose distance to \(V\) is one less than that of \(t\). Retain all intervals of types in \(A\), and send every person of type \(t\) to the point \((h(t),0)\). Distances strictly decrease along every chain, so termination is finite. The map is Borel because it is constant on each of finitely many type intervals.
Thus the maximum retained mass is exactly
\(M_A=\sum_{t\in A}\mu_t\).
Moreover, every maximizing resolution retains almost all of every interval \(X_t\) with \(t\in A\). Indeed, its retained set is contained in \(X_A=\dot\bigcup_{t\in A}X_t\), and the total omitted mass there is zero.
Computing \(A\) by reverse reachability takes \(O(m+\tau)\) graph operations. Henceforth use the graph induced by \(A\), and write
\(M=\sum_{t\in D_A}\mu_t\).
If \(D_A=\varnothing\), retaining precisely the voters gives the exact optimum \(z^*=1\). Assume below that \(M>0\).
Call \(U\subseteq A\) closed under permitted successors if
\(t\in U\cap D_A,\ u\in R(t)\cap A\quad\Longrightarrow\quad u\in U\).
Define
\(a(U)=\sum_{t\in U\cap D_A}\mu_t,\qquad b(U)=\sum_{v\in U\cap V}\mu_v\).
If a closed set \(U\) contains a delegator type, it contains a voter type: take a path from that delegator to a voter and apply closure at every step. Consequently, \(b(U)=0\) implies \(U=\varnothing\).
Consider any resolution attaining maximum retained mass. Every retained person whose type lies in a closed set \(U\) terminates at a voter whose type also lies in \(U\). Therefore
\(\sum_{v\in U\cap V}w_v\geq a(U)+b(U)\).
The quantities being measured are well-defined Borel sets. To see this, extend \(f\) to a Borel map \(F:S\to S\) by fixing voters. The persons terminating in \(X_v\) form the Borel set \(\bigcup_{n\geq0}(F^n)^{-1}(X_v)\).
If the resolution has objective value \(z\), then \(w_v\leq z\mu_v\) for every voter type. For every closed \(U\) with \(b(U)>0\), it follows that
\(zb(U)\geq a(U)+b(U)\),
and hence
\(z\geq1+\dfrac{a(U)}{b(U)}\).
Define the finite maximum
\(\rho=1+\max_{\substack{U\subseteq A\text{ closed}\\b(U)>0}}\dfrac{a(U)}{b(U)}\).
The indexing family is nonempty because it contains \(A\). We have proved that every maximum-retention resolution has objective value at least \(\rho\).
For a rational parameter \(z\geq1\), construct a network with source \(s\), sink \(q\), and one vertex for each type in \(A\):
Self-loops may be omitted. The network has at most \(\tau+2\) vertices and \(m+\tau\) arcs.
Its maximum possible flow value is \(M\), the total capacity leaving \(s\). Also, \(M<1\), since voter masses are positive.
Consider a source–sink cut, and let \(U\subseteq A\) be its type vertices on the source side. If a permitted type arc crosses the cut, its capacity alone is \(1>M\). Such a cut cannot prevent a flow of value \(M\).
Otherwise \(U\) is closed, and the cut capacity is
\(M-a(U)+(z-1)b(U)\).
When \(b(U)=0\), we have \(U=\varnothing\), and this capacity equals \(M\). When \(b(U)>0\), the capacity is at least \(M\) precisely when
\(z\geq1+\dfrac{a(U)}{b(U)}\).
The max-flow/min-cut theorem therefore gives the exact equivalence
\(\text{a flow of value }M\text{ exists}\quad\Longleftrightarrow\quad z\geq\rho\).
The theorem applies to this finite directed network with nonnegative capacities; rational capacities can also be scaled to integers. See the [MIT maximum-flow notes](https://courses.csail.mit.edu/6.854/21/Notes/n07-flow_computation.html).
In particular, a rational flow of value \(M\) exists at \(z=\rho\). It remains to prove that such a flow represents an actual concrete-delegate resolution.
Let a rational flow of value \(M\) be given. All source arcs are saturated, because their capacities sum to \(M\).
Decompose the flow into simple source–sink paths and directed cycles, and discard the cycles. This preserves the source flow and the flow entering each voter. The decomposition is finite: subtracting the minimum positive flow along each extracted path or cycle zeros at least one arc and never creates a new positive-flow arc. Thus there are at most \(m+\tau\) positive path components. This is the standard [finite flow decomposition](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/84ea6cf153a2841c6fb7d25812bd69ff_lec3.pdf).
After removing source and sink, write each positive path component as
\(P_i=(t_{i,0},t_{i,1},\ldots,t_{i,\ell_i})\),
with mass \(\alpha_i>0\), where \(t_{i,0}\in D_A\), \(t_{i,\ell_i}\in V\), and every preceding type is a delegator. Because source arcs are saturated,
\(\sum_{i:\,t_{i,0}=t}\alpha_i=\mu_t\qquad(t\in D_A)\).
We now construct the resolution.
Partition each source interval. For each \(t\in D_A\), partition \(X_t\) into half-open intervals \(I_i\), indexed by paths starting at \(t\), with \(\lambda(I_i)=\alpha_i\). Such a partition exists because the displayed masses sum to \(\mu_t\).
Choose distinct relay points. For every internal delegator occurrence \(t_{i,j}\), where \(1\leq j<\ell_i\), choose a point \(r_{i,j}\in X_{t_{i,j}}\). Make all relay points within a type distinct, including occurrences belonging to different paths. There are only finitely many required points, and every type interval has positive length. Choose also \(q_v=(v,0)\) for each voter type.
Define delegates. Let \(H\) be the finite set of relay points.
For \(x\in I_i\setminus H\), send \(x\) to the first internal relay of \(P_i\), or directly to \(q_{t_{i,\ell_i}}\) if the path has no internal delegator. At each relay \(r_{i,j}\), define its delegate to be the next relay on the same path, or the final voter point.
Retain \(S=X_A\).
This definition has the following properties.
\(\sum_{i:\,t_{i,\ell_i}=v}\alpha_i\).
Hence
\(w_v=\mu_v+\sum_{i:\,t_{i,\ell_i}=v}\alpha_i\leq z\mu_v\).
Each relay forwards all its received mass to one delegate. Streams using different continuations through a type use different concrete relay persons. No concrete person splits received mass.
Applying this construction at \(z=\rho\), together with the lower bound from Section 2, proves
\(z^*=\rho\),
with the optimum attained by a Borel resolution.
The cut formula has exponentially many terms, but only \(O(L)\) max-flow computations are needed to identify its maximum exactly.
Write each input mass as \(\mu_t=p_t/q_t\), and let
\(Q=\prod_{t\in T}q_t,\qquad c_t=Q\mu_t\).
Then every \(c_t\) is a positive integer, \(\sum_t c_t=Q\), and \(Q\) has \(O(L)\) bits.
Every cut ratio has the form
\(1+\dfrac{\sum_{t\in U\cap D_A}c_t}{\sum_{v\in U\cap V}c_v}\).
Its reduced denominator is at most \(Q\). Therefore any two distinct cut ratios differ by at least \(1/Q^2\): for rational numbers with denominators at most \(Q\), the numerator of their nonzero difference is a nonzero integer.
Also,
\(1<z^*\leq Q+1\).
The strict lower bound follows from \(M>0\). For the upper bound, every positive denominator in the cut formula is at least \(1/Q\), while every numerator is at most \(1\).
Use exact bisection with initial endpoints \(l=1\) and \(h=Q+1\). Test each midpoint using the network from Section 3, preserving
\(l<z^*\leq h\).
After \(O(L)\) tests, obtain
\(h-l<1/Q^2\).
Compute a minimum cut at the infeasible value \(l\). Its capacity is below \(M\), so it crosses no capacity-\(1\) type arc. Its type set \(U\) is therefore closed, has \(b(U)>0\), and satisfies
\(l<r(U):=1+\dfrac{a(U)}{b(U)}\leq z^*\).
But \(z^*-r(U)<1/Q^2\). Since both numbers are cut ratios, the separation bound forces \(r(U)=z^*\).
This recovers the optimum exactly. One final max-flow computation at \(z^*\), followed by Section 4’s construction, produces an optimal resolution.
Use Edmonds–Karp, which takes \(O(ne^2)\) arithmetic operations on a network with \(n\) vertices and \(e\) arcs; see the [MIT algorithm notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/b1e5ac3c8f7d60db9b8d5b66c40bc55e_MIT6_046JS12_Notes.pdf).
Here \(n=O(\tau)\) and \(e=O(m+\tau)\). During the \(O(L)\) bisection tests, capacities can be scaled to integers of \(O(L)\) bits: each tested parameter has a dyadic denominator with \(O(L)\) bits, and a common capacity denominator is its denominator times \(Q\). Residual capacities and flow values also have \(O(L)\) bits. The final computation has the same bit bound because the denominator of \(z^*\) is at most \(Q\).
Using ordinary integer arithmetic, a conservative bound covering capacity construction, all flow computations, decomposition, and output is
\(O\!\left(\tau(m+\tau)^2L^3\right)\).
The resolution has a polynomial-size finite description: at most \(m+\tau\) source intervals and \(O(\tau(m+\tau))\) relay points, with rational coordinates and interval endpoints of polynomial bit length. For example, if a type needs \(N_t\) relay points, choose coordinates \(\mu_t j/(N_t+1)\) for \(1\leq j\leq N_t\).
The cited [finite-agent result](https://procaccia.info/wp-content/uploads/2020/03/fluid.pdf) concerns indivisible agents. Its approximation hardness does not transfer to this model.
Here a type interval can be partitioned into prescribed masses, and separate zero-mass relay persons can carry streams with different continuations. The proof explicitly realizes these choices through concrete delegates and finite chains, so it establishes exact solvability for the model stated in the question.
⟨structured verdict parsed — rendered above⟩
The output resolves the intended continuous model up to two minor clarifications. The retention argument, cut characterization, concrete-delegate realization, and exact optimization procedure are sound. No major gap or false central step was found.
The established running time is \(O\!\left(\tau(m+\tau)^2L^3\right)\) bit operations, simplifying to \(O(\tau^3L^3)\) under \(m\leq2\tau\).
Every retained person’s finite chain supplies a type-level walk to a voter. Thus every retained person belongs to \(X_A\), including exceptional persons of zero mass. This proves the claimed upper bound on retention.
The distance-decreasing construction attains that bound. Every selected successor exists by reachability, and \((h(t),0)\) belongs to its interval because every support mass is positive. Distances strictly decrease, so the construction permits neither cycles nor infinite chains. Its finitely many constant pieces make the delegate map Borel.
A maximizing resolution therefore omits only a null subset of \(X_A\). This justifies using the full type masses in subsequent lower bounds.
The case \(D_A=\varnothing\) is handled correctly: every retained person is a voter, and \(z^*=1\).
Closure is appropriately defined using successors within \(A\): Section 1 has already shown that a valid retained delegate cannot lie outside \(A\).
Every nonempty closed set contains a voter. This is immediate if it already contains a voter; otherwise, a path from any delegator in the set remains inside it by closure and eventually reaches a voter. Positive voter masses then imply that \(b(U)=0\) forces \(U=\varnothing\).
Every retained person starting in \(U\) terminates in a voter type in \(U\). Because a maximizing resolution retains the full mass of \(U\) up to a null set, the inequality
\[
\sum_{v\in U\cap V}w_v\geq a(U)+b(U)
\]
is valid. Combining it with the objective constraints yields the stated ratio lower bound.
The measurability argument also works. Extending the delegate map by fixing voters produces a Borel map on the Borel space \(S\). Its iterates are Borel, and the countable union of their preimages describes precisely the persons terminating in the specified voter interval.
The network is finite, with nonnegative rational capacities for every tested \(z\geq1\). The source capacity totals \(M<1\). Thus a cut crossing a capacity-\(1\) type arc cannot have capacity below \(M\).
For every remaining cut, its type set is closed and its capacity is exactly
\[
M-a(U)+(z-1)b(U).
\]
The treatment of \(b(U)=0\) is correct. The resulting inequalities characterize feasibility of a flow of value \(M\). The [cited max-flow/min-cut notes](https://courses.csail.mit.edu/6.854/21/Notes/n07-flow_computation.html) support the theorem and the rational-to-integer scaling used here.
Minor issue: “Its maximum possible flow value is \(M\)” is inaccurate if read as asserting that the maximum flow equals \(M\) for every parameter. At \(z=1\), all voter-to-sink capacities vanish, so the maximum flow is zero when \(M>0\). The subsequent equivalence correctly distinguishes feasibility from the source-capacity upper bound.
Minimum clarification: Replace that sentence with “Its flow value is at most \(M\), the total capacity leaving \(s\).”
A flow of value \(M\) saturates every source arc, since their capacities sum to \(M\).
The [cited decomposition theorem](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/84ea6cf153a2841c6fb7d25812bd69ff_lec3.pdf), Theorem 2, supplies a decomposition into at most the number of network arcs many path and cycle components. The subtraction argument given in the output correctly explains this bound.
Cycles cannot contain the source, sink, or any voter: the source has no incoming arcs, the sink has no outgoing arcs, and each voter’s only outgoing network arc enters the sink. Discarding cycles consequently preserves every source contribution and voter inflow. All intermediate type vertices on the remaining simple paths are delegators.
The saturated source arcs justify every interval partition: the positive component masses starting at each type sum exactly to that type’s mass.
Finitely many distinct relay points can be chosen in each positive-length interval. Distinctness across all internal occurrences ensures that no relay receives conflicting delegate assignments.
Ordinary persons follow their assigned path’s relay sequence. A relay point follows its explicitly assigned sequence, even if its coordinate lies in an interval associated with another path. The exclusion of \(H\) from the ordinary-person rule handles this overlap correctly.
Each transition follows a permitted type arc, every delegate is retained, and every sequence terminates. The bound of at most \(\tau-1\) delegation steps follows from simplicity of the type paths.
The delegate map is Borel and single-valued. Overriding finitely many persons changes no Lebesgue mass, so the terminal loads equal the claimed path-component totals. Receiving positive mass at a zero-mass relay is permitted by the stated model; each such relay forwards its entire received stream to one delegate.
Therefore the construction genuinely establishes attainment of the cut lower bound in the concrete-delegate model.
The product \(Q\) has \(O(L)\) bits, and every scaled mass \(c_t\) is a positive integer. Every cut ratio has reduced denominator at most \(Q\), including after adding \(1\).
Distinct ratios are separated by at least \(1/Q^2\). The bounds \(1<z^*\leq Q+1\) hold in the branch \(M>0\).
Bisection preserves the strict lower endpoint invariant \(l<z^*\leq h\), including when a midpoint equals the optimum. Reducing an initial width \(Q\) below \(1/Q^2\) requires \(O(\log Q)=O(L)\) tests.
At the final infeasible lower endpoint, a minimum cut has capacity below \(M\), crosses no type arc, and has positive \(b(U)\). Its ratio lies in \((l,z^*]\). Since \(z^*\) itself is a cut ratio, the separation argument correctly forces equality.
The dyadic parameters produced by \(O(L)\) bisection steps have \(O(L)\)-bit numerators and denominators. Scaling by their denominator times \(Q\) gives integer capacities of \(O(L)\) bits. The final optimum likewise permits scaling with \(O(L)\)-bit integers.
Combining \(O(L)\) flow computations with \(O(\tau(m+\tau)^2)\) arithmetic operations per computation and a conservative \(O(L^2)\) arithmetic cost supports the claimed bound. Decomposition and the finite resolution description fit within it. The proposed relay coordinates have polynomial bit length and lie strictly inside their respective intervals.
Minor issue: The [cited Edmonds–Karp notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/b1e5ac3c8f7d60db9b8d5b66c40bc55e_MIT6_046JS12_Notes.pdf) state the \(O(ne^2)\) bound, but their displayed residual-network implementation assumes that the original network has no antiparallel arcs. The permitted type graph can contain antiparallel arcs.
This does not invalidate the standard Edmonds–Karp bound or the complexity conclusion; it leaves the implementation convention implicit.
Minimum clarification: Specify that the algorithm uses an implementation supporting antiparallel original arcs, and cite the bound in that convention.
The result concerns the support representation specified in the task and supplies a polynomial-size description of an actual optimal Borel resolution. It does not rely on an unintended degenerate interpretation.
Since \(k\geq4\), the requested factor \(\tfrac12\log_2 k\) is at least \(1\). Exact optimization therefore satisfies the requested approximation guarantee. The finite-agent hardness statement does not obstruct the explicit construction proved here.
⟨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.