Answer: The exact optimization problem is solvable in deterministic polynomial time, with a unique optimum given by the primitive integer boundary normal and its corresponding rational threshold.
Theorem 4.9 — class: algorithmic
Given positive rational type masses μ_1,μ_2 with μ_1+μ_2=1 and an explicitly described rational winning region \(W\subseteq[0,μ_1]\times[0,μ_2]\), promised to be exactly representable by ordered positive integer type weights and a positive rational quota, find \(w_1>w_2>0\) and θ∈ℚ_{>0} minimizing \(c_1w_1+c_2w_2+c_3θ\), for given rational \(c_i≥0\) not all zero, subject to \(x∈ W\iff w_1x_1+w_2x_2≥θ\) for every coalition mass vector \(x\) in the box.
A society is given by its support: the list of \(\tau\) types with positive masses, each encoded as a binary rational; \(\tau\) is the support size, not the number of possible types. Here \(\tau=2\), with \(\mu_1+\mu_2=1\).
Coalitions are all real mass vectors in \(B=[0,\mu_1]\times[0,\mu_2]\). The winning region \(W\subseteq B\) is given by \(m\) weak linear inequalities with binary rational coefficients; \(L\) is the total input bit length, including masses and costs.
Promise that \((0,0)\notin W\), \((\mu_1,\mu_2)\in W\), and \(W=\{x\in B:a_1x_1+a_2x_2\ge b\}\) for some \(a_1>a_2>0\) in \(\mathbb Z\) and \(b\in\mathbb Q_{>0}\).
Neither type is null: for each coordinate, increasing only that coordinate can turn a losing coalition into a winning one.
Define \(y\preceq x\) by \(y_1\le x_1\) and \(y_1+y_2\le x_1+x_2\). A winning point is shift-minimal if no distinct winning point precedes it; assume at least two shift-minimal winning points.
Given \(c_1,c_2,c_3\in\mathbb Q_{\ge0}\), not all zero, find \(w_1,w_2\in\mathbb Z_{>0}\) with \(w_1>w_2\) and \(\theta\in\mathbb Q_{>0}\) minimizing \(c_1w_1+c_2w_2+c_3\theta\), subject to \(x\in W\iff w_1x_1+w_2x_2\ge\theta\) for every \(x\in B\); equality is winning.
Is this exact optimization problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For discrete weighted games with two voter types, no null voters, and at least two shift-minimal winning vectors, the corresponding nonnegative linear objective admits an integral optimum computable in polynomial time from the explicit coalition-vector description. [Freixas–Kurz](https://arxiv.org/pdf/1103.0868)
No result settling this exact continuous problem was located in the searches performed.
The exact optimization problem is solvable in deterministic polynomial time. In fact, there is a unique optimum: recover the normal vector of the winning boundary, reduce it to a primitive positive integer pair, and scale the threshold accordingly.
The proof below uses the continuous geometry directly.
Write \(\mu=(\mu_1,\mu_2)\). By the promise, there exist \(a_1>a_2>0\) and \(b>0\) such that
\(W=\{x\in B:a_1x_1+a_2x_2\ge b\}\).
Set \(A=a_1\mu_1+a_2\mu_2\). Since \(\mu\) is winning, \(b\le A\).
If \(b=A\), positivity of both coefficients implies that the only winning point is \(\mu\): every distinct \(x\in B\) has at least one coordinate strictly smaller than the corresponding coordinate of \(\mu\), hence \(a_1x_1+a_2x_2<A\). Thus there would be exactly one shift-minimal winning point, contradicting the promise.
Consequently,
\(0<b<A\).
Both masses are positive because both types belong to the support. Therefore the point
\(p=(b/A)\mu\)
lies in the interior of \(B\) and satisfies \(a_1p_1+a_2p_2=b\). The winning boundary thus contains a nontrivial line segment inside \(B\).
Orient every input inequality as
\(r_{i1}x_1+r_{i2}x_2\ge q_i,\qquad i\in\{1,\ldots,m\}\),
where all coefficients are rational. Define
\(s_i=r_{i1}\mu_1+r_{i2}\mu_2\).
Since \(\mu\in W\), every row satisfies \(s_i\ge q_i\).
On the diagonal \(x=t\mu\), with \(t\in[0,1]\), the row becomes \(ts_i\ge q_i\). If \(s_i\le0\), then \(ts_i\ge s_i\ge q_i\), so this row imposes no restriction on this diagonal interval. If \(s_i>0\), it requires \(t\ge q_i/s_i\).
It follows that
\(t\mu\in W\iff t\ge t_*, \qquad t_*=\max\bigl(\{0\}\cup\{q_i/s_i:s_i>0\}\bigr)\).
The promised halfspace description also gives \(t\mu\in W\iff t\ge b/A\). Hence
\(t_*=b/A\in(0,1)\).
Choose a row attaining this positive maximum. Denote its normal by \(r=(r_1,r_2)\), its right-hand side by \(q\), and its diagonal coefficient by \(s=r\cdot\mu>0\). At \(p=t_*\mu\), this row is tight:
\(r\cdot p=q\).
We now prove that this row defines the actual winning halfspace, rather than merely some redundant supporting inequality.
Let \(d=(a_2,-a_1)\). Then \(a\cdot d=0\). Since \(p\) is interior to \(B\), for sufficiently small \(\varepsilon>0\), both \(p+\varepsilon d\) and \(p-\varepsilon d\) belong to \(B\). Both lie on the promised winning boundary, so both satisfy the selected row. Its tightness at \(p\) gives
\(\varepsilon r\cdot d\ge0 \quad\text{and}\quad -\varepsilon r\cdot d\ge0\).
Thus \(r\cdot d=0\), which in two dimensions implies \(r=\lambda a\). Moreover,
\(\lambda=s/A>0, \qquad q=r\cdot p=\lambda b\).
Therefore
\(r_1>r_2>0, \qquad W=\{x\in B:r_1x_1+r_2x_2\ge q\}\).
This recovers the exact supporting inequality using rational arithmetic on the input.
Let \(D\) be the least common multiple of the positive denominators of \(r_1\) and \(r_2\), and define
\(v_1=Dr_1,\qquad v_2=Dr_2,\qquad g=\gcd(v_1,v_2)\).
Set
\(u_1=v_1/g,\qquad u_2=v_2/g,\qquad \theta_*=Dq/g\).
Then \(u_1>u_2>0\) are integers, \(\gcd(u_1,u_2)=1\), and \(\theta_*>0\) is rational. Since \(r=(g/D)u\), we have
\(W=\{x\in B:u_1x_1+u_2x_2\ge\theta_*\}\).
Thus \((u_1,u_2,\theta_*)\) is feasible.
Suppose \((w_1,w_2,\theta)\) is any feasible representation, with \(w_1>w_2>0\) integral.
For any \(z\) on the winning boundary inside the interior of \(B\), feasibility gives \(w\cdot z\ge\theta\). For sufficiently small \(\varepsilon>0\), the point \(z-\varepsilon u\) remains in \(B\), and
\(u\cdot(z-\varepsilon u) =\theta_*-\varepsilon(u_1^2+u_2^2)<\theta_*\).
It is therefore losing, so \(w\cdot(z-\varepsilon u)<\theta\). Taking the limit as \(\varepsilon\) decreases to zero yields \(w\cdot z\le\theta\). Consequently,
\(w\cdot z=\theta\)
at every interior boundary point.
Take two such points whose difference is a nonzero multiple of \((u_2,-u_1)\); they exist by Section 1. Subtracting their equalities gives
\(w_1u_2-w_2u_1=0\).
Thus \(w=ku\) for some \(k>0\), and evaluating at a boundary point gives \(\theta=k\theta_*\).
Finally, \(k\) must be an integer. Since \(\gcd(u_1,u_2)=1\), Bézout’s identity supplies integers \(h_1,h_2\) with \(h_1u_1+h_2u_2=1\). Therefore
\(k=h_1w_1+h_2w_2\in\mathbb Z\).
Conversely, every positive integer scaling preserves the winning inequality. Hence the feasible representations are exactly
\(\{(ku_1,ku_2,k\theta_*):k\in\mathbb Z_{>0}\}\).
Define
\(C=c_1u_1+c_2u_2+c_3\theta_*\).
All three coordinates are positive, while the costs are nonnegative and not all zero. Therefore \(C>0\). The objective at the representation indexed by \(k\) is \(kC\), uniquely minimized at \(k=1\).
The unique optimum is consequently
\((w_1,w_2,\theta)=(u_1,u_2,\theta_*)\),
with optimal value \(C\).
For the running time:
Thus the algorithm runs in time polynomial in \(m\) and \(L\), and therefore polynomial in \(m,\tau,L\) for the stipulated \(\tau=2\). The output also has polynomial bit length, even when the numerical weights are large.
The continuous boundary is the decisive feature: it forces all exact representations to be proportional. The discrete minimum-representation results of [Freixas–Kurz](https://arxiv.org/pdf/1103.0868) are not needed for this proof.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct. The argument establishes a deterministic polynomial-time algorithm and a unique optimal representation under the stated promises. No major or minor mathematical gaps were found.
Because both listed types have positive masses, \(\mu_1,\mu_2>0\). With \(A=a_1\mu_1+a_2\mu_2\), the promised winning grand coalition gives \(b\le A\).
The exclusion of \(b=A\) is valid: positivity of both coefficients would make \(\mu\) the only winning coalition. A singleton winning set has exactly one shift-minimal winning point, contradicting the promise.
Therefore \(0<b<A\), and \(p=(b/A)\mu\) has both coordinates strictly between their box endpoints. It lies on the boundary \(a\cdot x=b\). A sufficiently short segment through \(p\), parallel to \((a_2,-a_1)\), lies inside the box. This establishes the interior boundary segment needed later.
Since \(\mu\) satisfies every input inequality, \(s_i\ge q_i\).
For \(s_i\le0\) and \(t\in[0,1]\), the inequalities \(ts_i\ge s_i\ge q_i\) are correct. Such a row imposes no restriction on this diagonal interval. For \(s_i>0\), division gives precisely \(t\ge q_i/s_i\).
Consequently, the stated maximum characterizes winning points on the diagonal, with the equivalence understood for \(t\in[0,1]\). The promised halfspace gives the same diagonal winning interval, so \(t_*=b/A\in(0,1)\).
Because this maximum is positive and the row set is finite, some row with \(s_i>0\) attains it. That row is tight at \(p=t_*\mu\). No existence or division-by-zero issue arises.
The points \(p+\varepsilon d\) and \(p-\varepsilon d\), where \(d=(a_2,-a_1)\), are inside the box for sufficiently small positive \(\varepsilon\). Both satisfy \(a\cdot x=b\), and equality is winning, so both satisfy the selected input row.
Tightness at \(p\) therefore yields both signs of the inequality for \(r\cdot d\), forcing \(r\cdot d=0\). In two dimensions, the vectors orthogonal to the nonzero vector \(d\) are exactly the scalar multiples of \(a\).
The calculation \(\lambda=s/A>0\) verifies the orientation of that scalar multiple. Tightness gives \(q=\lambda b\). Thus the row has \(r_1>r_2>0\), has \(q>0\), and defines exactly the promised halfspace. This also handles redundant input rows: whichever maximizing row is selected must have the required normal and threshold.
Clearing the denominators with \(D\) produces positive integers \(v_1>v_2\). Dividing by their positive greatest common divisor gives integers \(u_1>u_2>0\) with \(\gcd(u_1,u_2)=1\).
The threshold scaling is consistent: multiplying the selected inequality by \(D/g>0\) gives exactly \(u\cdot x\ge\theta_*\), where \(\theta_*=Dq/g>0\). Thus the constructed triple satisfies every output constraint.
For an interior boundary point \(z\), feasibility first gives \(w\cdot z\ge\theta\). For sufficiently small positive \(\varepsilon\), the point \(z-\varepsilon u\) remains in the box and has
\(u\cdot(z-\varepsilon u)=\theta_*-\varepsilon(u_1^2+u_2^2)<\theta_*\).
It is losing. Exact equivalence, including the winning convention at equality, therefore implies \(w\cdot(z-\varepsilon u)<\theta\). Taking the limit gives \(w\cdot z\le\theta\). Combining the two inequalities proves equality at every interior boundary point.
Two distinct points on the established boundary segment then force \(w_1u_2-w_2u_1=0\). Positivity implies \(w=ku\) for \(k>0\), and boundary equality implies \(\theta=k\theta_*\).
The application of Bézout’s identity is justified by \(\gcd(u_1,u_2)=1\). Its displayed integer combination proves that \(k\) is an integer. Conversely, positive integer scaling preserves the inequality. The claimed description of all feasible triples is therefore exact.
All three coordinates of the primitive triple are strictly positive. Since the costs are nonnegative and at least one is positive, \(C>0\).
Every feasible objective value is \(kC\) for a positive integer \(k\). Hence \(k=1\) uniquely minimizes the objective, including cases where one or two costs vanish.
Each diagonal coefficient and ratio uses only a fixed number of input rationals. Their numerators and denominators therefore have bit lengths bounded by \(O(L)\). Comparing candidate ratios by cross multiplication preserves polynomial bit complexity; selecting a maximum does not accumulate arithmetic expressions across rows.
Clearing two denominators, computing their least common multiple and the resulting greatest common divisor, and constructing the threshold all use integers of polynomial bit length. Standard exact integer arithmetic and greatest-common-divisor algorithms take polynomial time on these inputs.
The algorithm scans the rows and outputs a triple of polynomial bit length. It therefore runs in polynomial time in \(m,L\), and in \(m,\tau,L\) with \(\tau=2\).
The proof is self-contained and does not depend on the cited discrete-game result. The unused non-nullness promise creates no gap: the argument establishes the conclusion under the other stated promises alone. No additional clarification or repair is required.
⟨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.