d4-conf-ecai-2020-0271 (d4-conf-ecai-2020-0271)

Given candidates \(C\), a target \(p\), and a finite support \(\mathcal A\) of approval types with binary rational masses \(\mu_A\) summing to \(1\), compute the maximum retained mass \(\sum_{A\in\mathcal A}x_A\), subject to \(0\le x_A\le\mu_A\) and, for every \(a\ne p\), \(\sum_{A:p\in A,\ a\notin A}x_A\ge\sum_{A:a\in A,\ p\notin A}x_A\).

Let \(C\) be a finite nonempty candidate set, \(m=|C|\), and \(p\in C\). An approval type \(A\subseteq C\) strictly prefers approved candidates to disapproved candidates and is indifferent within each group; \(A=\varnothing\) and \(A=C\) are allowed.
A society is given by its support: the list \(\mathcal A\) of the \(\tau\) types with positive mass, each mass \(\mu_A\) a binary rational, with \(\sum_{A\in\mathcal A}\mu_A=1\). Here \(\tau\) is the support size, not the number of possible approval types.
Retention may split each type's mass: choose real numbers \(0\le x_A\le\mu_A\), without renormalizing the retained masses. Define the continuous Young score by
\(S(p)=\max\left\{\sum_{A\in\mathcal A}x_A:\ \sum_{A\in\mathcal A:p\in A,\ a\notin A}x_A\ge\sum_{A\in\mathcal A:a\in A,\ p\notin A}x_A\text{ for every }a\in C\setminus\{p\}\right\}\), subject also to the retention bounds.
Pairwise ties are permitted, and retaining zero mass is allowed. The threshold problem additionally takes a binary rational \(q\in[0,1]\) and asks whether \(S(p)\ge q\). Let \(L\) be the total input bit length.

Can \(S(p)\) be computed exactly in time polynomial in \(m,\tau,L\), or is its threshold problem NP-hard?

For finite electorates with dichotomous preferences, deciding whether a candidate's Young score is at least a given integer is NP-complete, whereas deciding whether a candidate has maximum Young score is in \(\mathrm P\).

Theorem. The continuous Young score \(S(p)\) can be computed exactly in time polynomial in \(m,\tau,L\). Its threshold problem belongs to \(\mathrm P\), and therefore is not NP-hard under polynomial-time many-one reductions unless \(\mathrm P=\mathrm{NP}\).

Proof: linear programming formulation. Enumerate the supported types as \(\mathcal A=\{A_1,\ldots,A_\tau\}\), and write \(\mu_j=\mu_{A_j}\). For each opponent \(a\in C\setminus\{p\}\), define
\( d_{aj}=\mathbf 1_{\{p\in A_j,\ a\notin A_j\}}-\mathbf 1_{\{a\in A_j,\ p\notin A_j\}}. \)
Thus \(d_{aj}\in\{-1,0,1\}\).

Consider the rational linear program
\( \max \sum_{j=1}^{\tau}x_j \)
subject to
\( \sum_{j=1}^{\tau}d_{aj}x_j\ge 0 \)
for every \(a\ne p\), and
\( 0\le x_j\le\mu_j \)
for every \(j\).

For each opponent, its constraint states precisely that the retained mass strictly preferring \(p\) to that opponent is at least the mass strictly preferring that opponent to \(p\). Types indifferent between the two contribute zero. Consequently, this program’s feasible points are exactly the permitted retentions, and its optimum is \(S(p)\).

The feasible region contains the zero vector. It is closed and contained in the bounded box \(\prod_{j=1}^{\tau}[0,\mu_j]\), so it is compact. Hence the maximum is attained, and \(0\le S(p)\le\sum_j\mu_j=1\). This argument also covers \(m=1\), when there are no opponent constraints and \(S(p)=1\).

Proof: polynomial encoding and exact computation. We use the standard rational linear programming theorem: a linear program with binary rational data can be solved in polynomial bit complexity; for a nonempty bounded feasible region, an exact rational optimum and an optimal rational solution can be returned. This is the rational-data polynomial-time solvability theorem underlying the ellipsoid method. See [Adler and Beling, introduction](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).

Here there are \(\tau\) variables and \(m-1+2\tau\) inequalities. Every constraint coefficient belongs to \(\{-1,0,1\}\); the only nonconstant right-hand sides are the input masses. Membership tables for the explicitly listed types, and hence all coefficients, can be constructed in polynomial time in \(m,\tau,L\). Even a dense encoding of the full program has length \(O(m\tau+\tau^2+L)\). The theorem therefore yields exact computation in the required polynomial time.

For completeness, exact output also has polynomial length. Write each input mass as \(\mu_j=u_j/v_j\), where \(u_j,v_j\) are integers and \(v_j>0\), and let \(D=\prod_jv_j\). Then \(\log_2 D\le L\). After setting \(y_j=Dx_j\), every right-hand side is an integer, and every constraint coefficient remains in \(\{-1,0,1\}\).

A linear objective over a nonempty bounded polyhedron has an optimal vertex. At such a vertex, \(\tau\) linearly independent active constraints give a system \(By=b\), with \(B\) an invertible integer matrix and \(b\) an integer vector. Cramer’s rule implies that
\( \sum_jy_j=K/\det B \)
for some integer \(K\). The determinant expansion gives
\( 1\le|\det B|\le\tau!, \)
because it has \(\tau!\) terms, each of absolute value at most one. Thus the reduced denominator of
\( S(p)=K/(D\det B) \)
is at most \(D\tau!\). Since \(S(p)\in[0,1]\), its reduced numerator is no larger than its denominator. Both therefore have \(O(L+\tau\log(\tau+1))\) bits.

Threshold decision and the finite-electorate distinction. Given the rational threshold \(q\), add the single inequality
\( \sum_jx_j\ge q. \)
The resulting rational system is feasible exactly when \(S(p)\ge q\): attainment of the maximum justifies the forward implication, and any feasible retention justifies the reverse implication. Rational linear programming feasibility decides this in polynomial time.

The stated finite-electorate hardness does not contradict this result. If type \(A_j\) contains \(n_j\) voters, retaining whole voters requires an integer variable \(z_j\in\{0,\ldots,n_j\}\). With normalized masses \(\mu_j=n_j/n\), the continuous problem instead permits every real \(x_j\in[0,n_j/n]\), including fractions of individual voters. The finite problem’s integrality restriction is absent here; the continuous problem is exactly the linear program proved above.

⟨structured verdict parsed — rendered above⟩

The prover’s conclusion is correct: the continuous score is exactly computable in polynomial time, and the threshold problem belongs to \(\mathrm P\). The argument resolves the assigned task without substantive or minor gaps.

• Linear programming formulation.

The coefficient \(d_{aj}\) correctly records the contribution of type \(A_j\) to the pairwise margin of \(p\) against \(a\): it is positive when the type strictly prefers \(p\), negative when it strictly prefers \(a\), and zero when it is indifferent.

Thus every opponent inequality is exactly the corresponding inequality in the definition of \(S(p)\). The variable bounds and objective also match the definition. Both directions of the claimed correspondence between feasible points and permitted retentions hold.

The allowed types \(A=\varnothing\) and \(A=C\) cause no exception: their coefficients are zero for every opponent, as required by indifference.

• Feasibility, boundedness, and attainment.

The zero vector satisfies every constraint. The feasible region is closed because all inequalities are non-strict, and it lies in the bounded retention box. Compactness and continuity of the objective therefore justify attainment.

The bound \(0\le S(p)\le1\) follows directly from the retention bounds and the normalization of the input masses. For \(m=1\), retaining every type’s full mass is feasible and yields \(S(p)=1\), so the stated edge case is correct.

• Polynomial-size encoding.

The counts of \(\tau\) variables and \(m-1+2\tau\) inequalities are correct. Constraint coefficients and objective coefficients have constant bit length; the nonconstant right-hand sides are the given binary rationals.

Since the support is explicitly listed, constructing membership tables and the coefficient matrix takes polynomial time in \(m,\tau,L\). The claimed dense encoding bound is valid. In particular, the argument uses the actual support size rather than enumerating all possible approval types.

• Application of polynomial-time rational linear programming.

The prover states the needed theorem precisely enough: binary-rational linear programs admit polynomial bit-complexity solution, including exact rational optimal output when their feasible regions are nonempty and bounded.

All its hypotheses are verified here: the data are rational, the encoding is polynomial in the requested parameters, and feasibility and boundedness have already been established. Lower-dimensional feasible regions present no additional hypothesis requirement.

The cited introduction confirms polynomial-time solvability of rational linear programs measured in the number of coefficients and their total binary encoding length. The invoked exact-output theorem is the standard rational linear programming result. [Adler and Beling](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf)

• Exact output-length calculation.

The supplementary calculation is correct throughout:

• The positive integer \(D=\prod_jv_j\) satisfies \(\log_2D\le L\) under the stated binary-rational encoding.
• Substitution \(y_j=Dx_j\) makes every right-hand side integral while preserving the constraint coefficients.
• A nonempty bounded polyhedron has an optimal vertex. At a vertex, the active constraint normals span the ambient variable space, permitting the stated selection of \(\tau\) independent active constraints.
• Cramer’s rule gives each coordinate a common denominator \(\det B\), so their sum has the asserted form \(K/\det B\).
• Since \(B\) has entries in \(\{-1,0,1\}\) and is invertible, the determinant bound \(1\le|\det B|\le\tau!\) is valid.
• Reduction of \(K/(D\det B)\) cannot increase its positive denominator. The previously established interval \(S(p)\in[0,1]\) bounds its reduced numerator by that denominator.

Consequently, the stated polynomial bit-length bound holds, including when \(\tau=1\) or \(S(p)=0\).

• Threshold decision.

Adding \(\sum_jx_j\ge q\) gives a rational feasibility problem of polynomial encoding length. Attainment ensures that \(S(p)\ge q\) implies feasibility; any feasible point of the augmented system implies \(S(p)\ge q\). The equivalence includes both endpoint thresholds.

Polynomial-time feasibility therefore proves membership in \(\mathrm P\). The qualification concerning NP-hardness under polynomial-time many-one reductions is correct.

• Finite-electorate distinction.

The explanation correctly identifies the whole-voter integrality restriction absent from the continuous problem. It does not infer that finite scores equal continuous scores or misuse the separate maximum-score result. The stated finite-electorate hardness therefore creates no inconsistency.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩