Answer: A deterministic polynomial-time \(4/3\)-approximation exists; every fixed factor \(a>1\) is achievable. Computing additive \(\epsilon\)-approximations in time polynomial in \(m,\tau,L,1/\epsilon\) is NP-hard, and therefore impossible unless \(\mathrm{P}=\mathrm{NP}\).
Proposition 3.5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo polynomial-time algorithm approximat- ing the UCO problem under Maximin can do better than 1 1 2, unless P = NP. PROOF. Suppose, for contradiction, that there exists a polynomial- time approximation algorithm A to the UCO problem under Max- imin having approximation ratio r < 1 1 2. Then when opt = 2, the minimal size of manipulating coalition returned by A is n ≤ r · opt < 3. Since the size of the coalition is an integer, it fol- lows that n = 2. Therefore, A can decide the CCUM problem for the coalition of 2 manipulators, which contradicts the fact that this problem is NP-complete [13] (unless P = NP). 4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), target \(p\), and a rational distribution \(\mu\) over the nonmanipulators’ ranking types, find the infimum \(\lambda^\star=\inf_{\nu\ge 0}\sum_r\nu_r\) such that \(p\) is the unique Maximin winner under the normalized society \(\rho=(\mu+\nu)/(1+\sum_r\nu_r)\), where \(\nu_r\) is manipulator mass reporting ranking \(r\). Determine the computational complexity of this optimization in \(m\), the support size \(\tau\), and the input bit length \(L\), including whether an \(\epsilon\)-approximate optimum can be computed efficiently.
Let \(C\) contain \(m\ge 2\) candidates, with target \(p\in C\), and let \(R\) be all strict linear rankings of \(C\). The nonmanipulators have a distribution \(\mu\) on \(R\), with \(\sum_r\mu_r=1\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
Manipulators may add arbitrary nonnegative real masses \(\nu_r\) on any rankings, including rankings outside the input support. Their cost is \(\lambda=\sum_r\nu_r\), and the resulting society is \(\rho=(\mu+\nu)/(1+\lambda)\).
Apply Maximin using pairwise masses. A manipulation is feasible precisely when \(p\) is the unique winner; ties with \(p\) count as failure. Define \(\lambda^\star=\inf\{\sum_r\nu_r:\nu\text{ is feasible}\}\).
For \(\lambda^\star>0\), an \(a\)-approximation returns a feasible rational manipulation of cost at most \(a\lambda^\star\). An additive \(\epsilon\)-approximation returns one of cost at most \(\lambda^\star+\epsilon\), including when \(\lambda^\star=0\).
Can a polynomial-time \(a\)-approximation for some fixed \(1<a<3/2\) be obtained, or is attaining such a factor NP-hard?
Can additive \(\epsilon\)-approximations be computed in time polynomial in \(m,\tau,L,1/\epsilon\), for binary rational \(0<\epsilon<1\)?
For discrete unweighted coalitions, every approximation factor below \(3/2\) is impossible in polynomial time unless \(\mathrm{P}=\mathrm{NP}\), while a polynomial-time \(5/3\)-approximation exists ([source](https://tzin.bgu.ac.il/~omerlev/papers/aamas11.pdf)).
No result settling these approximation questions for this precise continuous model was located in the literature search.
Both questions can be settled for the stated continuous model:
The constructions below allow manipulator rankings outside the input support and return explicitly listed rational manipulations.
The discrete \(3/2\) hardness argument uses integer coalition sizes; it therefore does not establish hardness for this continuous model. See [Zuckerman–Lev–Rosenschein, Proposition 3.5](https://tzin.bgu.ac.il/~omerlev/papers/aamas11.pdf).
For distinct candidates \(x,y\), define the original pairwise mass
\(A_{xy}=\sum_{r:\,x\succ_r y}\mu_r.\)
Thus \(A_{xy}+A_{yx}=1\). Write \(V=C\setminus\{p\}\), and define
\(s=\min_{q\in V}A_{pq},\qquad S(q)=\min_{y\ne q}A_{qy}.\)
These numbers can be computed exactly in polynomial time from the supplied support.
The normalization by \(1+\lambda\) multiplies every Maximin score by the same positive number. Consequently, all winner comparisons may use the unnormalized pairwise masses.
Lemma 1. Moving \(p\) to the top of every manipulator ranking preserves feasibility and cost.
Proof. This operation increases or preserves every pairwise mass favoring \(p\). For each rival \(q\), it decreases or preserves its pairwise mass against \(p\), while preserving all comparisons between rivals. Hence \(p\)'s score cannot decrease, and no rival's score can increase. \(\square\)
Assume henceforth that every manipulator ranks \(p\) first. Let \(t\) be the total manipulator mass, and let \(x_{jq}\) be the manipulator mass ranking \(j\) above \(q\), for distinct \(j,q\in V\). Then \(p\)'s unnormalized score is exactly \(s+t\).
Consider the weak relaxation in which \(p\) may tie for first place. A rival \(q\) has score at most \(s+t\) precisely when at least one of the following holds:
Define
\(e_q=A_{qp}-s,\qquad d_{qj}=\max\{0,A_{qj}-s\}.\)
Thus a witness against \(p\) requires \(t\ge e_q\), while a witness against another rival requires \(x_{jq}\ge d_{qj}\).
A candidate with \(S(q)\le s\) needs no imposed ranking constraint for the weak relaxation: choose an original comparison attaining \(S(q)\). Its pairwise mass increases by at most \(t\), so its resulting score remains at most \(s+t\).
Lemma 2. Any rational weak manipulation of mass \(t\) can be converted into a rational strict manipulation of mass \(t+\eta\), for every rational \(\eta>0\).
Proof. Fix any order of \(V\). Add mass \(\eta/2\) on each of the two rankings consisting of \(p\) first, followed by this order and its reverse.
The score of \(p\) increases by \(\eta\). Every pairwise mass between two rivals increases by exactly \(\eta/2\); every rival's pairwise mass against \(p\) stays fixed. Therefore a comparison witnessing a rival's weak defeat now witnesses its strict defeat. \(\square\)
The minimum weak cost exists. Indeed, weak feasibility holds at cost \(1\): \(p\)'s score is \(s+1\), while every rival's comparison against \(p\) is at most \(1\). Restricting to \(p\)-first manipulations of cost at most \(1\) gives a compact finite-dimensional set, and weak feasibility is closed because Maximin scores are continuous.
By Lemmas 1 and 2, this minimum weak cost equals \(\lambda^\star\).
We also obtain an exact test for the zero-infimum case:
\(\lambda^\star=0\quad\Longleftrightarrow\quad S(q)\le s\text{ for every }q\in V.\)
The reverse implication follows from Lemma 2 applied to the zero manipulation. For the forward implication, if \(S(q)>s\), adding nonnegative masses leaves \(q\)'s score at least \(S(q)\), whereas \(p\)'s score is at most \(s+t\). Thus every feasible manipulation has \(t>S(q)-s>0\).
A witness choice can be represented by a directed graph on \(V\):
A graph with at most one outgoing arc per vertex consists of trees leading to roots or to vertex-disjoint directed cycles.
Lemma 3. Such witness choices can be realized by a rational manipulation of total mass \(T>0\), provided:
\(\displaystyle\sum_{q\to j\in Q}d_{qj}\le(k-1)T.\)
The manipulation can be constructed in polynomial time with \(O(m)\) rankings.
Proof. Every strict ranking must violate at least one desired comparison on a directed cycle. Thus, for any distribution of total mass \(T\),
\(\displaystyle\sum_{q\to j\in Q}x_{jq}\le(k-1)T.\)
This proves the necessity of the cycle inequality for fixed witnesses.
For sufficiency, consider a cycle with demands \(d_1,\ldots,d_k\). Choose rational numbers \(f_1,\ldots,f_k\) satisfying
\(0\le f_i\le T-d_i,\qquad \sum_{i=1}^k f_i=T.\)
They exist because the capacities have sum
\(\displaystyle\sum_{i=1}^k(T-d_i)\ge T.\)
They can be obtained by greedily filling these capacities.
For mass \(f_i\), break only the \(i\)-th cycle arc and satisfy every other cycle comparison. The successful mass for the \(i\)-th comparison is then \(T-f_i\ge d_i\).
To combine different cycles, partition the same interval of length \(T\) according to the masses \(f_i\) for each cycle. Refine all these partitions jointly. There are \(O(m)\) resulting intervals.
For each interval, remove its selected broken arc from every cycle. The remaining witness graph is acyclic. Topologically order its precedence requirements, placing each witness \(j\) before its dependent candidate \(q\), and place \(p\) first. Give this ranking the interval's length as its mass.
Every tree comparison is satisfied on all mass \(T\); each cycle comparison receives the required successful mass. Roots are certified as specified. All masses are rational, and the number of intervals and arithmetic operations is polynomial. \(\square\)
Set \(\gamma=5/4\). We first construct a rational weak manipulation of cost at most \(\gamma\lambda^\star\).
For a rational parameter \(b\ge0\), define the directed graph \(G_b\) on \(V\) by
\(q\to j\in E(G_b)\quad\Longleftrightarrow\quad d_{qj}\le b.\)
Declare the following vertices to be available roots:
\(Z_b=\{q:S(q)\le s\}\cup\{q:e_q\le b\}.\)
A directed cycle \(Q\) of length \(k\) in \(G_b\) is called acceptable if either:
Every acceptable cycle satisfies Lemma 3 at mass \(T=\gamma b\). For a cycle of length at least five, this follows from
\(\displaystyle\sum_{q\to j\in Q}d_{qj}\le kb\le(k-1)\frac54b.\)
Define a test that accepts \(b\) when every sink strongly connected component of \(G_b\) contains either an available root or an acceptable cycle.
Cycles of lengths two, three, and four can be enumerated.
A directed cycle of length at least five can also be found in polynomial time by an elementary procedure. Enumerate ordered sequences of five distinct vertices \(v_1,\ldots,v_5\). When their consecutive arcs form a path, search for a path from \(v_5\) to \(v_1\) after deleting \(v_2,v_3,v_4\).
A simple return path produces a simple cycle of length at least five. Conversely, any cycle of length at least five contains a five-vertex prefix whose remaining part supplies such a return path. Thus this procedure detects exactly whether a sufficiently long cycle exists.
Together with strongly connected component computation, this gives a polynomial-time test.
For every sink component, select an available root or an acceptable cycle.
Every vertex reaches one of the selected objects: the condensation graph is finite and acyclic, and each of its vertices reaches a sink component.
For vertices outside the selected objects, choose one arc decreasing the shortest distance to the selected objects. On each selected cycle, choose its cycle arcs. Selected roots have no outgoing arc. The resulting witness graph has exactly the selected cycles, together with trees leading to those cycles and roots.
All chosen demands are at most \(b\), all roots using \(p\) satisfy \(e_q\le b\), and all selected cycles satisfy the required inequality at mass \(\gamma b\). Lemma 3 constructs the weak manipulation.
Take a minimum-cost weak manipulation of mass \(\lambda^\star\).
Consider a sink component of \(G_{\lambda^\star}\) containing no available root. Every vertex \(q\) in this component has \(S(q)>s\), and cannot use \(p\) as its witness. Its weak defeat therefore has some rival witness \(j\) with
\(d_{qj}\le x_{jq}\le\lambda^\star.\)
Consequently \(q\to j\) belongs to \(G_{\lambda^\star}\), and the sink property keeps \(j\) in the same component.
Choose such a witness for each vertex. The resulting functional graph contains a directed cycle \(Q\). If its length is \(k\), the necessity calculation in Lemma 3 gives
\(\displaystyle\sum_{q\to j\in Q}d_{qj}\le(k-1)\lambda^\star.\)
This cycle is acceptable: the displayed inequality suffices when \(k\le4\), and a longer cycle is acceptable by definition. Hence every sink component passes the test.
There is no need to know \(\lambda^\star\), or to approximate it numerically.
Form the following finite set of rational parameters:
\(\displaystyle\frac{\sum_{q\to j\in Q}d_{qj}}{\gamma(k-1)}.\)
The set has polynomial size.
Between successive values in this set, the graph, available roots, and acceptable short cycles remain unchanged. Long-cycle existence depends only on the graph. Because all comparisons are non-strict, the test has the same value throughout each interval beginning at a breakpoint and ending just before the next breakpoint.
The test accepts at \(1\), since every vertex then has its comparison against \(p\) available. Evaluate the test at all listed parameters and let \(b_0\) be the smallest accepted one.
Since the test accepts \(\lambda^\star\), the breakpoint observation implies
\(b_0\le\lambda^\star.\)
If \(\lambda^\star>0\), then \(b_0>0\). Indeed, a vertex with \(S(q)>s\) has every \(d_{qj}>0\) and \(e_q>0\); at \(b=0\) it is an isolated sink without an available root.
Construct the weak manipulation of cost \(5b_0/4\), and apply Lemma 2 with
\(\eta=b_0/12.\)
The resulting rational manipulation makes \(p\) the unique winner and has cost
\(\displaystyle\frac54b_0+\frac1{12}b_0=\frac43b_0\le\frac43\lambda^\star.\)
This proves the requested polynomial-time approximation below \(3/2\).
All rational numbers have polynomial encoding length: pairwise masses are sums of input rationals, breakpoint formulas involve at most four demands, and the ranking construction uses polynomially many rational additions, subtractions, and comparisons. The output has \(O(m)\) rankings.
The same proof works with a fixed integer \(K\ge3\) and
\(\gamma=K/(K-1).\)
Enumerate cycles shorter than \(K\), and detect cycles of length at least \(K\) by enumerating \(K\)-vertex prefixes and searching for a return path.
For any fixed \(a>1\), choose \(K\) so that \(\gamma<a\), and add a positive rational perturbation within the remaining budget \((a-\gamma)b_0\). The running time remains polynomial for fixed \(a\), although its exponent depends on \(a\).
We now construct societies whose optimum encodes the longest directed cycle.
Directed Hamiltonian Cycle is NP-complete; see [Karp's original paper, reprinted here](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
It remains NP-hard on strongly connected oriented graphs, where “oriented” means that opposite arcs never both occur.
Here is the reduction establishing the needed restriction. Non-strongly-connected inputs are immediate NO-instances and can be mapped to a fixed strongly connected NO-instance. For a strongly connected loopless directed graph \(G\), replace every vertex \(v\) by
\(v_{\mathrm{in}}\to v_{\mathrm{mid}}\to v_{\mathrm{out}},\)
and replace every original arc \(v\to w\) by
\(v_{\mathrm{out}}\to w_{\mathrm{in}}.\)
The resulting graph \(H\) is strongly connected and oriented. Every Hamiltonian cycle must traverse each three-vertex block consecutively, because the middle vertex has only its designated predecessor and successor, and the out-vertex has only its designated predecessor. Contracting these blocks gives a Hamiltonian cycle of \(G\). Conversely, expanding a Hamiltonian cycle of \(G\) gives one of \(H\).
Let \(H\) have \(n\ge3\) vertices, and let \(\ell\) be its longest directed cycle length. Strong connectivity and orientation imply \(\ell\ge3\).
Use one rival for each vertex of \(H\), together with \(p\). Choose
\(b=\lceil\log_2(n(n+3))\rceil,\qquad h=2^{-b},\qquad d=h/2,\qquad s=1/2-h.\)
Prescribe
\(A_{pq}=1/2-h\)
for every rival \(q\). For two rivals, prescribe:
Accordingly, the witness demands are
\(A_{qj}-s=h/2\) on arcs of \(H\),
\(A_{qj}-s=3h/2\) on reverse arcs,
and \(A_{qj}-s=h\) on nonadjacent pairs.
Every witness against \(p\) requires mass \(2h\).
We explicitly realize the pairwise matrix as a distribution of strict rankings.
For any pair \(u,v\) and dyadic bias \(\beta>0\), let \(z_1,\ldots,z_{m-2}\) list the remaining candidates. Give mass \(\beta\) to each ranking
\(u\succ v\succ z_1\succ\cdots\succ z_{m-2}\)
and
\(z_{m-2}\succ\cdots\succ z_1\succ u\succ v.\)
This block has total mass \(2\beta\). Relative to half its total mass, it contributes bias \(\beta\) favoring \(u\) over \(v\), and zero bias on every other pair.
Use such a block:
If \(H\) has \(e\) arcs, the total block mass is
\(B=2nh+eh.\)
Since \(H\) is oriented, \(e\le n(n-1)/2\), and hence
\(\displaystyle B\le\frac{h\,n(n+3)}2\le\frac12.\)
Give the remaining mass \(1-B\) equally to any ranking and its reverse. These last two rankings contribute zero pairwise bias. The resulting distribution realizes every prescribed pairwise mass exactly.
There are at most \(2(n+e)+2=O(n^2)\) ranking types before merging duplicates. All input masses are positive dyadic rationals of \(O(\log n)\) bits. Thus \(m,\tau,L\) are polynomially bounded in the graph size.
Lemma 4. For the society constructed from \(H\),
\(\displaystyle\lambda^\star=\frac h2\frac{\ell}{\ell-1}.\)
Proof: lower bound. Move \(p\) first in any feasible manipulation.
The proposed value is at most \(3h/4<h\). Therefore any manipulation of mass at least \(h\) already exceeds it.
Now suppose the manipulation has mass \(t<h\). No rival can use its comparison against \(p\), which requires mass greater than \(2h\) for strict defeat. A nonadjacent pair requires successful witness mass greater than \(h\), and a reverse arc requires more than \(3h/2\); both are impossible because successful mass is at most \(t\).
Consequently, every rival must choose an arc of \(H\) as its witness. These choices contain a directed cycle of some length \(k\le\ell\). Strict defeat requires successful mass greater than \(h/2\) on every one of its \(k\) comparisons. Since every ranking satisfies at most \(k-1\) of them,
\(\displaystyle(k-1)t>k\frac h2.\)
Thus
\(\displaystyle t>\frac h2\frac{k}{k-1}\ge\frac h2\frac{\ell}{\ell-1},\)
where the last inequality uses that \(k/(k-1)\) decreases with \(k\). Taking the infimum proves the lower bound.
Proof: upper bound. Select a longest cycle. Strong connectivity ensures that every other vertex reaches it. Choose tree arcs leading to the cycle, all belonging to \(H\).
Set
\(\displaystyle T=\frac h2\frac{\ell}{\ell-1}.\)
Every selected arc has demand \(h/2\le T\), and the cycle satisfies
\(\displaystyle\ell\frac h2=(\ell-1)T.\)
Lemma 3 supplies a rational weak manipulation of mass \(T\). Lemma 2 supplies strict feasible manipulations of mass \(T+\eta\) for arbitrarily small rational \(\eta>0\). Hence \(\lambda^\star\le T\). \(\square\)
This also handles the unattained-infimum issue explicitly: every feasible manipulation costs strictly more than the displayed optimum, but feasible rational costs approach it.
If \(H\) is Hamiltonian, Lemma 4 gives
\(\displaystyle\lambda^\star=Y:=\frac h2\frac n{n-1}.\)
If it is not Hamiltonian, then \(\ell\le n-1\), and therefore
\(\displaystyle\lambda^\star\ge N:=\frac h2\frac{n-1}{n-2}.\)
The gap is
\(\displaystyle\Delta=N-Y=\frac{h}{2(n-1)(n-2)}.\)
Because \(h\) is bounded above and below by constant multiples of \(1/n^2\), this gap is bounded above and below by constant multiples of \(1/n^4\).
Choose a dyadic rational \(\epsilon\) satisfying
\(\Delta/8<\epsilon\le\Delta/4.\)
Such an \(\epsilon\) can be computed in polynomial time, has \(O(\log n)\) bits, and satisfies \(1/\epsilon=O(n^4)\).
Suppose an additive approximation algorithm had running time polynomial in \(m,\tau,L,1/\epsilon\). Apply it to the constructed society, and let \(t\) be the cost of its returned feasible manipulation.
Comparing the rational output cost with \((Y+N)/2\) decides Hamiltonian Cycle in polynomial time. Thus the requested additive approximation algorithm cannot exist unless \(\mathrm{P}=\mathrm{NP}\).
The hardness already holds on instances with positive optimum, polynomial support, and dyadic input masses. It does not depend on the zero-infimum case.
⟨structured verdict parsed — rendered above⟩
Verdict: proved with minor gaps. The output resolves both assigned questions in substance: it establishes a polynomial-time multiplicative approximation below \(3/2\), and establishes NP-hardness of the requested additive approximation guarantee. No major mathematical error was found.
The stronger claim that every fixed multiplicative factor \(a>1\) is achievable also follows from the written construction. The issues below concern scope, wording, and routine boundary cases.
Normalization. Correct. Dividing all pairwise masses by the same positive quantity \(1+\lambda\) divides every Maximin score by that quantity and preserves winner comparisons.
Lemma 1. Correct. Moving \(p\) first preserves all comparisons between rivals, improves comparisons favoring \(p\), and weakens every rival’s comparison against \(p\). Thus it preserves strict feasibility and cost.
Witness inequalities. Correct. Under the standing assumption that manipulators rank \(p\) first, its score is \(s+t\). A rival’s comparison against another rival is
\[
A_{qj}+t-x_{jq},
\]
so weak defeat through that comparison is equivalent to
\[
x_{jq}\ge A_{qj}-s.
\]
Replacing the right side by its maximum with zero is valid because \(x_{jq}\) is nonnegative. The condition for a witness against \(p\) is also correct.
Unconstrained roots. Correct. If \(S(q)\le s\), an original comparison attaining \(S(q)\) increases by at most \(t\). It therefore continues to witness weak defeat.
Lemma 2. Correct under the already stated \(p\)-first convention. The two added rankings increase every rival–rival comparison by exactly \(\eta/2\), leave rivals’ comparisons against \(p\) fixed, and increase \(p\)’s score by \(\eta\). Every previously weak witness becomes strict. This also works when \(m=2\): the two listed rankings coincide, and their masses may be merged.
Existence and identification of the weak optimum. Correct. Although there are factorially many rankings, their number is finite; compactness here is an existence argument, not a polynomial-time claim. Restricting total mass to at most one gives a compact domain, and weak feasibility is closed. Lemmas 1 and 2 correctly identify its minimum with the strict-feasibility infimum.
Zero-infimum test. Correct. If some \(S(q)>s\), nonnegative additions cannot lower that rival’s score, while the manipulated score of \(p\) is at most \(s+t\). This gives the asserted positive lower bound. The reverse implication follows from Lemma 2.
Functional-graph structure. Correct. With at most one outgoing arc per vertex, each component leads to a root or to one directed cycle.
Cycle inequality. Correct. A strict ranking cannot satisfy all precedence requirements around a directed cycle. Summing successful masses therefore gives the necessary bound
\[
\sum_{q\to j\in Q}x_{jq}\le (k-1)T.
\]
Capacity construction. Correct when \(T\) is rational. The individual demand bounds make all capacities nonnegative, and the cycle inequality makes their sum at least \(T\). The greedy construction then has the claimed properties.
Combining cycles. Correct. Refining partitions of a common interval couples the cycle constructions without increasing total mass. The number of partition endpoints is bounded by the total number of cycle vertices, so the refinement has \(O(m)\) intervals.
After one arc is removed from each selected cycle, the remaining precedence constraints are acyclic and admit a topological ordering. Tree comparisons hold throughout the entire mass, and each cycle comparison receives the required mass. Rankings outside the original support are permitted by the task.
Minor issue 1 — missing rationality hypothesis. Lemma 3 promises a rational manipulation of total mass \(T>0\), without explicitly assuming that \(T\) is rational. Literally, this is false for irrational \(T\): a finite sum of rational output masses cannot equal an irrational total.
Minimum clarification: state that \(T\) is a positive rational number. Every algorithmic application in the output already satisfies this requirement, so the conclusions survive.
Acceptable-cycle bound. Correct. For \(k\ge5\),
\[
kb\le (k-1)\frac54b.
\]
The short-cycle test directly checks the remaining cycle inequalities.
Long-cycle detection. Correct. A simple return path after deleting the three internal prefix vertices intersects the prefix only at its endpoints. Its union with the four prefix arcs forms a simple cycle of length at least five. Conversely, a simple cycle of sufficient length supplies one of the enumerated prefixes and a permitted return path.
Enumeration and reachability are polynomial because the prefix length is fixed. The searches must be performed inside the sink component being tested; this is implicit in the stated component test.
Acceptance implies constructibility. Correct. Every vertex reaches a selected object. Choosing arcs that decrease shortest distance prevents additional cycles outside the selected objects. The selected cycles and roots satisfy Lemma 3 at total mass \(\gamma b\).
Acceptance at the optimum. Correct. A sink component without an available root contains only candidates requiring rival witnesses. Each such witness has demand at most \(\lambda^\star\), and the sink property keeps its endpoint inside the component. The resulting functional graph supplies a cycle whose necessary inequality establishes acceptance.
This argument does not require the optimum manipulation to be rational; it uses only its existence and its real pairwise masses.
Breakpoint search. Correct. The listed values contain every threshold that changes the graph, root set, or short-cycle acceptability. All predicates use non-strict inequalities, so the state at a breakpoint agrees with the interval immediately to its right. Hence acceptance at \(\lambda^\star\) implies acceptance at a listed value no larger than \(\lambda^\star\).
No monotonicity of the test is needed because all listed parameters are evaluated.
Minor issue 2 — “isolated sink” is too strong. In Section 3.4, a vertex with \(S(q)>s\) has no outgoing arcs at \(b=0\), but it may have incoming arcs. Thus it need not be isolated in the usual graph-theoretic sense.
Minimum clarification: describe it as a singleton sink strongly connected component with no available root. This is precisely the property needed to establish rejection at zero.
Approximation arithmetic. Correct:
\[
\frac54b_0+\frac1{12}b_0=\frac43b_0
\le\frac43\lambda^\star.
\]
For positive optimum, the preceding argument ensures \(b_0>0\), so the perturbation is positive and produces a strict winner.
Encoding and running time. Correct. Pairwise sums, constant-length breakpoint formulas, partition endpoints, and output masses have polynomial encoding length. The construction lists \(O(m)\) rankings rather than enumerating all rankings.
Every fixed factor above one. Correct. For fixed \(K\), enumeration of shorter cycles and \(K\)-vertex prefixes remains polynomial. The bound
\[
kb\le (k-1)\frac{K}{K-1}b
\]
holds for \(k\ge K\). Choosing fixed \(K\) with \(\gamma<a\) leaves a positive perturbation budget. Selecting a fixed positive rational coefficient within that budget is a routine implementation detail.
The exponent depends on \(a\), as the output explicitly acknowledges. This is consistent with the later additive-hardness claim.
The invoked source theorem is the NP-completeness of deciding whether a finite directed graph has a directed cycle visiting every vertex exactly once. This is included in [Karp’s original list of complete problems](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
Three-vertex transformation. Correct for strongly connected loopless source graphs with at least two vertices:
Minor issue 3 — boundary cases and fixed NO-instance are underspecified. A one-vertex loopless graph is commonly considered strongly connected, but its transformed block is not strongly connected. Also, the proposed fixed strongly connected NO-instance is not identified; it must belong to the oriented target class.
Minimum clarification: explicitly handle bounded-size source instances, restrict the transformation to source graphs with at least two vertices, and identify the fixed strongly connected oriented NO-instance used for rejected inputs. These are routine finite-case details and do not require a new hardness argument.
For the resulting nontrivial strongly connected oriented graph, existence of a directed cycle and absence of loops or opposite arcs justify \(\ell\ge3\).
Prescribed matrix. Correct. The entries are complementary, and subtracting \(s\) gives exactly the three stated rival-witness demands. The demand against \(p\) is \(2h\).
Two-ranking bias block. Correct. Both rankings favor the designated pair in the same direction. Every other pair is ordered in opposite directions across the two rankings, yielding zero bias relative to half the block’s total mass.
Total mass bound. Correct:
\[
B=2nh+eh
\le \frac{hn(n+3)}2
\le\frac12.
\]
Thus the remaining mass is positive and can be split between a ranking and its reverse.
Representation requirements. Satisfied. The construction has polynomial support, positive dyadic masses, total mass one, and polynomial input length. Merging duplicate rankings preserves these properties; their mass encodings remain of logarithmic length.
Lemma 4, lower bound. Correct. Since the proposed optimum is at most \(3h/4\), manipulations of mass at least \(h\) already exceed it.
Below \(h\), strict defeat excludes witnesses against \(p\), nonadjacent pairs, and reverse arcs. Every rival must therefore choose an arc of \(H\). A resulting cycle of length \(k\) requires successful mass strictly greater than \(h/2\) on every arc, giving
\[
(k-1)t>k\frac h2.
\]
The monotonicity of \(k/(k-1)\), together with \(k\le\ell\), establishes the lower bound.
Lemma 4, upper bound. Correct. Strong connectivity supplies paths to a longest cycle. The chosen demands and cycle equality satisfy Lemma 3 at the displayed rational \(T\); Lemma 2 then approaches that value with strict feasible manipulations. The unattained infimum is handled correctly.
Gap calculation. Correct:
\[
N-Y=\frac{h}{2(n-1)(n-2)}.
\]
The definition of \(h\) gives the asserted inverse-polynomial gap. The dyadic choice of \(\epsilon\) has logarithmic encoding length and polynomially bounded \(1/\epsilon\).
Decision reduction. Correct. In Hamiltonian instances the returned cost lies below the midpoint; in non-Hamiltonian instances feasibility alone places it above the midpoint. Polynomial running time bounds the length of the explicit rational output, so summing its masses and comparing costs is polynomial-time computable.
The cited discrete hardness argument indeed depends on integer coalition sizes, as [Proposition 3.5](https://tzin.bgu.ac.il/~omerlev/papers/aamas11.pdf) explicitly shows. Its distinction from the continuous construction is justified.
All substantive steps support the claimed answers. Only the three minor clarifications above are needed; no blocking issue or missing substantive lemma was found.
The complexity classification below records the established additive hardness. The simultaneous polynomial-time result for fixed multiplicative factors is not an encoding-dependent split.
⟨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.