Answer: Polynomial-time solvable: \(\mathrm P\).
Theorem 11 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateMaximin-pessimistic-voter-losing is coNP- complete. PROOF. It is clear that the problem is in coNP and thus we focus on the proof of its coNP-hardness. We do so via a reduc- tion from the complement of X3C (that is, the problem that is identical to X3C, except that if the answer for a given X3C in- stance is “yes” then in the complement the answer is “no”, and the other way round). Let I = (B,S ) be an instance of X3C, where B = {b1,...,b3k} and S = {S1,...,Sn} is a family of three-eleemt subsets of B. We build the following election E = (C,V,P) with disciplined parties.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Input a finite candidate set \(C\), a society \(\mu\) with rational masses over complete ranking and party types, a distinguished leading type \(\ell\) of mass \(\mu_\ell\), its top candidate \(w\) (initially a Maximin winner), a finite list \(\mathcal D\) of allowed destination types including types with zero current mass, and a rational threshold \(q\). Is there a departure mass \(r\in[q,\mu_\ell]\) such that, for every \(x\in\mathbb R_{\ge 0}^{\mathcal D}\) with \(\sum_{j\in\mathcal D}x_j=r\), \(w\) remains a Maximin winner in \(\mu^x=\mu-r\delta_\ell+\sum_{j\in\mathcal D}x_j\delta_j\)? For each society \(\nu\), define \(M_\nu(a,b)=\sum_t\nu_t\,\operatorname{sgn}_t(a,b)\) and \(\operatorname{score}_\nu(a)=\min_{b\ne a}M_\nu(a,b)\); \(w\) remains a winner exactly when \(\operatorname{score}_{\mu^x}(w)\ge\operatorname{score}_{\mu^x}(c)\) for every \(c\in C\).
Each type consists of a party identity and a strict complete ranking of a candidate set \(C\), where \(m=|C|\ge 2\); distinct parties may share a ranking. A society \(\mu\) is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also specifies a leading type \(\ell\) with \(\mu_\ell>0\), its top candidate \(w\), a nonempty finite list \(\mathcal D\) of destination party types other than \(\ell\), and a binary rational threshold \(0\le q\le\mu_\ell\). Destination types may have zero initial mass; their rankings are explicitly supplied.
For distinct candidates \(a,b\), let \(\operatorname{sgn}_t(a,b)=1\) if type \(t\) ranks \(a\) above \(b\), and \(-1\) otherwise. Define \(M_\nu(a,b)=\sum_t\nu_t\operatorname{sgn}_t(a,b)\) and \(\operatorname{score}_\nu(a)=\min_{b\ne a}M_\nu(a,b)\). Maximin elects every candidate with maximum score, including ties; assume \(w\) initially wins.
Only leading-party mass may move. A departure of real mass \(r\) is distributed without capacities as \(x\in\mathbb R_{\ge0}^{\mathcal D}\), with \(\sum_jx_j=r\), giving \(\mu^x=\mu-r\delta_\ell+\sum_jx_j\delta_j\), where \(\delta_t\) is unit mass at type \(t\). Departing mass adopts its destination's ranking.
The decision problem asks whether some \(r\in[q,\mu_\ell]\) satisfies \(\operatorname{score}_{\mu^x}(w)\ge\operatorname{score}_{\mu^x}(c)\) for every \(c\in C\) and every such distribution \(x\). Let \(L\) be the total binary input length; state running times in \(m,\tau,|\mathcal D|,L\).
Is this continuous Maximin pessimistic voter-losing decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
The discrete version with indivisible voters is \(\mathrm{coNP}\)-complete. [Source](https://www.ifaamas.org/Proceedings/aamas2013/docs/p407.pdf)
No result settling exactly the continuous problem above was verified.
The stated continuous problem is in \(\mathrm P\). The algorithm uses at most \(5(m-1)^2\) rational linear programs, followed by a polynomial-time interval coverage test.
If \(q=0\), the answer is immediately yes: choose \(r=0\), and use the assumption that \(w\) initially wins. The argument below handles the substantive case \(q>0\), as well as all boundary cases.
Write \(k=|\mathcal D|\), \(u=\mu_\ell\), and \(A(a,b)=M_\mu(a,b)\). Index destinations by \(j\in\{1,\ldots,k\}\). Define
\(\Delta_j(a,b)=\operatorname{sgn}_j(a,b)-\operatorname{sgn}_\ell(a,b)\).
For a departure vector \(x\), its total mass is \(r=\sum_jx_j\), and therefore
\(M_{\mu^x}(a,b)=A(a,b)+\sum_jx_j\Delta_j(a,b)\).
The set of all permitted departure vectors is the nonempty compact polytope
\(K=\{x\in\mathbb R_{\ge0}^k:q\le\sum_jx_j\le u\}\).
Indeed, nonemptiness follows from \(k\ge1\) and \(q\le u\); compactness follows from \(0\le x_j\le u\). Every vector in \(K\) produces nonnegative society masses summing to one.
Fix \(c\ne w\) and \(b\ne w\). For every \(d\ne c\), define the affine function
\(F_{cb,d}(x)=A(c,d)-A(w,b)+\sum_jx_j\bigl(\Delta_j(c,d)-\Delta_j(w,b)\bigr)\).
Thus \(F_{cb,d}(x)=M_{\mu^x}(c,d)-M_{\mu^x}(w,b)\).
Loss characterization. For any permitted \(x\), candidate \(w\) fails to win if and only if there exist \(c\ne w\) and \(b\ne w\) such that
\(F_{cb,d}(x)>0\quad\text{for every }d\ne c.\)
To prove the forward implication, choose \(c\) with \(\operatorname{score}_{\mu^x}(c)>\operatorname{score}_{\mu^x}(w)\), and choose \(b\) attaining \(w\)’s minimum margin. Then every margin of \(c\) exceeds \(M_{\mu^x}(w,b)\).
Conversely, the displayed inequalities imply
\(\operatorname{score}_{\mu^x}(c)>M_{\mu^x}(w,b)\ge\operatorname{score}_{\mu^x}(w)\).
Strict inequalities are essential here: a tie preserves \(w\)’s status as a winner.
For each pair \((c,b)\), define
\(S_{cb}=\{x\in K:F_{cb,d}(x)>0\text{ for every }d\ne c\}\),
and its set of total masses
\(B_{cb}=\{\sum_jx_j:x\in S_{cb}\}\).
By the loss characterization, a mass \(r\in[q,u]\) is unsafe precisely when
\(r\in\bigcup_{c\ne w,\ b\ne w}B_{cb}\).
Consequently, the answer to the decision problem is yes precisely when this union does not cover \([q,u]\).
We now prove that each nonempty \(B_{cb}\) is an interval and show how to compute it exactly.
Suppose \(S_{cb}\ne\varnothing\), and introduce the weak relaxation
\(P_{cb}=\{x\in K:F_{cb,d}(x)\ge0\text{ for every }d\ne c\}\).
This is a nonempty compact convex polytope. Let
\(\alpha_{cb}=\min_{x\in P_{cb}}\sum_jx_j,\qquad \beta_{cb}=\max_{x\in P_{cb}}\sum_jx_j.\)
Both extrema are attained.
Closure lemma. If \(S_{cb}\ne\varnothing\), then \(\overline{S_{cb}}=P_{cb}\).
The inclusion \(\overline{S_{cb}}\subseteq P_{cb}\) follows from continuity of the affine functions and closedness of \(K\). For the reverse inclusion, fix \(x^*\in S_{cb}\). Given \(y\in P_{cb}\) and \(0<\varepsilon\le1\), put
\(y_\varepsilon=(1-\varepsilon)y+\varepsilon x^*.\)
Convexity gives \(y_\varepsilon\in K\), and for every \(d\ne c\),
\(F_{cb,d}(y_\varepsilon)=(1-\varepsilon)F_{cb,d}(y)+\varepsilon F_{cb,d}(x^*)>0.\)
Thus \(y_\varepsilon\in S_{cb}\), and \(y_\varepsilon\) tends to \(y\).
It follows that
\(\overline{B_{cb}}=[\alpha_{cb},\beta_{cb}].\)
For completeness, the image of \(P_{cb}\) under \(x\mapsto\sum_jx_j\) is exactly this closed interval, by convexity and attainment of both extrema. Every point of \(P_{cb}\) is approximated by points of \(S_{cb}\), so every mass in that image belongs to \(\overline{B_{cb}}\). The reverse inclusion holds because that image is closed and contains \(B_{cb}\).
Moreover, \(S_{cb}\) is convex, so \(B_{cb}\) is convex. If \(\alpha_{cb}<\beta_{cb}\), every mass strictly between these endpoints belongs to \(B_{cb}\): its closure contains both endpoints, so there are masses in \(B_{cb}\) on either side of it, and convexity supplies the desired mass.
Therefore \(B_{cb}\) consists of the entire interval interior, with each endpoint included or excluded according to strict feasibility. If \(\alpha_{cb}=\beta_{cb}\), nonemptiness implies \(B_{cb}=\{\alpha_{cb}\}\).
All computations below use exact rational linear programming.
First solve the linear program with variables \(x\) and \(z\):
\(\text{maximize }z,\quad x\in K,\quad -2\le z\le2,\quad F_{cb,d}(x)\ge z\text{ for every }d\ne c.\)
Every pairwise margin lies in \([-1,1]\), so every \(F_{cb,d}(x)\) lies in \([-2,2]\). Hence this program is feasible: any \(x\in K\), together with \(z=-2\), satisfies its constraints. Its feasible set is compact, so the optimum is attained.
Its optimum is positive if and only if \(S_{cb}\ne\varnothing\). A positive feasible \(z\) gives all the strict inequalities. Conversely, a vector satisfying all those inequalities has a positive minimum over the finitely many values \(F_{cb,d}(x)\), which supplies a positive feasible \(z\).
If the optimum is nonpositive, discard this pair. Otherwise:
The endpoint belongs to \(B_{cb}\) exactly when its endpoint program has positive optimum. These programs are feasible because each endpoint is attained in \(P_{cb}\); choosing \(z=0\) suffices.
Thus at most five linear programs determine each interval, including its endpoint membership.
There are at most \(N=(m-1)^2\) nonempty intervals.
Let \(E\) contain \(q\), \(u\), and every computed interval endpoint. Sort its distinct elements. Test whether the union of the unsafe intervals contains:
Return yes if any tested point is uncovered; otherwise return no.
This test is complete. On an open interval between consecutive elements of \(E\), membership in each unsafe interval is constant, because none of its endpoints occurs there. Its midpoint therefore determines whether that entire open interval is covered. Testing the elements of \(E\) separately handles excluded endpoints and singleton intervals. These points and open intervals partition \([q,u]\).
An uncovered tested mass is consequently a valid witness: every redistribution of that mass preserves \(w\)’s win.
The algorithm uses the supplied support and destination rankings only; it never enumerates other possible types.
Precomputing ranking signs and initial margins takes \(O((\tau+k)m^2)\) rational arithmetic operations. The resulting rational coefficients have bit length polynomial in \(L\): a common denominator can be obtained from the product of the input mass denominators, whose bit length is bounded by their total encoding length.
Each linear program has at most \(k+1\) variables and \(O(k+m)\) constraints. Its encoding length is polynomial in \(m+k+L\). We apply the standard polynomial-time theorem for rational linear programming: feasibility and a finite optimum can be computed exactly in time polynomial in the rational input encoding length. All programs here have rational data and compact, nonempty feasible sets, so its hypotheses hold.
The endpoint optima also have polynomial bit length. This follows, for example, by expressing a vertex optimizer through determinants of rational constraint matrices. Thus the subsequent endpoint programs and rational comparisons retain polynomial encoding length.
There are at most \(5(m-1)^2\) linear programs. The coverage procedure uses \(O(m^4)\) rational comparisons if each test point is checked against every interval. A valid overall bit-time bound is therefore
\(O\bigl((\tau+|\mathcal D|)m^2\operatorname{poly}(L)+m^4\operatorname{poly}(m+|\mathcal D|+L)\bigr).\)
This proves membership in \(\mathrm P\). The discrete \(\mathrm{coNP}\)-completeness result is Theorem 11 of the [cited paper](https://www.ifaamas.org/Proceedings/aamas2013/docs/p407.pdf). The continuous algorithm above depends on convex combinations of departure vectors, which need not remain feasible for indivisible voters.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated continuous problem: its polynomial-time algorithm is correct, and no mathematical gaps or false steps were found.
\(M_{\mu^x}(a,b)=A(a,b)+\sum_jx_j\Delta_j(a,b)\)
follows directly from the specified mass transfer. The polytope \(K\) is nonempty because \(k\ge1\) and \(q\le u\), and compact because it is closed and each coordinate lies in \([0,u]\). Removing at most \(u\) from the leading type preserves nonnegative masses; adding departure mass to destinations preserves total mass. Zero initial destination masses and shared rankings cause no difficulty.
\(\overline{B_{cb}}=[\alpha_{cb},\beta_{cb}]\)
correctly establishes both inclusions, rather than assuming that projection commutes with closure. Convexity then supplies every interior mass. The singleton case is also handled correctly.
No repair or additional clarification is needed.
⟨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.