d4-conf-atal-2013-0343 (d4-conf-atal-2013-0343)

Given two agendas \(A_1,A_2\), a finite support \(T\) of joint ranking types with rational masses \(\mu_t\) summing to \(1\), rational committee masses \(\alpha_1,\alpha_2>0\) with \(\alpha_1+\alpha_2\le1\), and target winners \(a_1^\star,a_2^\star\), decide whether there are allocations \(x_{t,j}\ge0\) satisfying \(\sum_j x_{t,j}\le\mu_t\) and \(\sum_t x_{t,j}=\alpha_j\), such that each target wins under weighted 2-Approval and the paper’s fixed tie-breaking rule.

There are two agendas \(A_j=\{a^j_1,\ldots,a^j_m\}\), \(j\in\{1,2\}\), with \(m\ge2\); their indexing fixes lexicographic tie-breaking, with smaller indices preferred. Each type consists of a strict total ranking of each agenda.
A society is given by its support: the list \(T\) of its \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
The input also specifies binary rational committee masses \(\alpha_1,\alpha_2>0\) with \(\alpha_1+\alpha_2\le1\), and targets \(a_j^\star\in A_j\).
An allocation consists of real masses \(x_{t,j}\ge0\) satisfying \(x_{t,1}+x_{t,2}\le\mu_t\) for every type and \(\sum_{t\in T}x_{t,j}=\alpha_j\) for each committee. Every type may serve either committee; its mass may be split, and unused mass is allowed.
Each committee votes sincerely under weighted 2-Approval: an alternative's score is the total assigned mass ranking it in the top two positions. The unique winner has maximum score, with ties resolved by the fixed agenda ordering.

Is deciding whether an allocation makes both targets win solvable in polynomial time in \(m,\tau,L\), or is this problem NP-hard?

For indivisible voters and prescribed committee sizes, 2-Approval delegation is NP-complete with two committees and polynomial-time solvable with one committee ([Elkind, Pasechnik and Wooldridge, 2013](https://www.ifaamas.org/Proceedings/aamas2013/docs/p439.pdf)). No published result settling this exact divisible-mass problem was located.

Result. The problem is polynomial-time solvable, with running time \((m+\tau+L)^{O(1)}\) in the bit model. Divisibility makes the allocation constraints linear; lexicographic tie-breaking can be handled exactly by maximizing a common score margin.

1. Encoding the winner conditions.

Write each target as \(a_j^\star=a^j_{k_j}\). For every listed type \(t\), agenda \(j\), and alternative index \(i\), define \(b_{t,j,i}\in\{0,1\}\) to equal \(1\) precisely when type \(t\) ranks \(a_i^j\) among its top two alternatives.

Under allocation \(x\), alternative \(a_i^j\) has score

\(s_{j,i}(x)=\sum_{t\in T}b_{t,j,i}x_{t,j}.\)

Define its score deficit relative to the target by

\(d_{j,i}(x)=s_{j,k_j}(x)-s_{j,i}(x)=\sum_{t\in T}(b_{t,j,k_j}-b_{t,j,i})x_{t,j}.\)

The target wins committee \(j\) if and only if both of the following hold:

• \(d_{j,i}(x)>0\) for every \(i<k_j\).
• \(d_{j,i}(x)\ge 0\) for every \(i>k_j\).

Indeed, an earlier alternative defeats the target whenever its score is at least the target’s score. A later alternative defeats the target only when its score is strictly greater. These conditions therefore encode the specified tie-breaking exactly.

2. A rational linear program.

Introduce one additional real variable \(\varepsilon\). Maximize \(\varepsilon\), subject to:

• \(x_{t,j}\ge 0\) for every \(t\in T\) and \(j\in\{1,2\}\).
• \(x_{t,1}+x_{t,2}\le\mu_t\) for every \(t\in T\).
• \(\sum_{t\in T}x_{t,j}=\alpha_j\) for each \(j\in\{1,2\}\).
• \(d_{j,i}(x)\ge\varepsilon\) for every \(j\in\{1,2\}\) and \(i<k_j\).
• \(d_{j,i}(x)\ge 0\) for every \(j\in\{1,2\}\) and \(i>k_j\).
• \(0\le\varepsilon\le 1\).

Call its feasible region \(P\). This is a closed, bounded rational polyhedron: the allocation constraints imply \(0\le x_{t,j}\le\mu_t\le 1\), and the margin variable is explicitly bounded. Consequently, if \(P\) is nonempty, its maximum \(\varepsilon^\star\) exists.

The algorithm rejects if the linear program is infeasible. Otherwise, it accepts precisely when \(\varepsilon^\star>0\).

3. Proof of equivalence.

Suppose first that an allocation \(x\) makes both targets win. Let

\(H=\{(j,i):j\in\{1,2\},\ i<k_j\}.\)

If \(H\) is nonempty, every \(d_{j,i}(x)\) indexed by \(H\) is strictly positive. Since \(H\) is finite,

\(\varepsilon=\min\bigl(\{1\}\cup\{d_{j,i}(x):(j,i)\in H\}\bigr)>0.\)

All linear-program constraints hold for this pair \((x,\varepsilon)\). If \(H\) is empty, take \(\varepsilon=1\); all remaining score constraints hold because both targets win. Thus, in either case, the program is feasible and \(\varepsilon^\star>0\).

Conversely, suppose the program is feasible and \(\varepsilon^\star>0\). Take an optimal solution \((x^\star,\varepsilon^\star)\). Its allocation coordinates satisfy all prescribed mass constraints. Every earlier opponent satisfies

\(d_{j,i}(x^\star)\ge\varepsilon^\star>0,\)

and every later opponent satisfies

\(d_{j,i}(x^\star)\ge 0.\)

By the winner characterization above, both targets win. This proves the algorithm’s correctness.

4. Polynomial bit complexity and exact positivity.

The program has \(n=2\tau+1\) variables. After replacing the two committee equalities by pairs of inequalities, it has \(3\tau+2m+4\) inequalities. Every matrix coefficient belongs to \(\{-1,0,1\}\); the only nonconstant right-hand sides are the input masses \(\mu_t,\alpha_1,\alpha_2\). A dense representation therefore has total bit length

\(B=O\bigl(\tau(\tau+m)+L\bigr).\)

Only the explicitly listed support types are used. There is no enumeration of unlisted rankings.

We apply the standard rational linear-programming theorem: feasibility and, for a feasible bounded program, an exact rational optimum can be computed in time polynomial in the number of variables, constraints, and total coefficient bit length. See the [ellipsoid-method theorem in these University of Washington notes](https://courses.cs.washington.edu/courses/cse521/22au/521-lecture-16.pdf). Its hypotheses hold here because all coefficients are rational and \(P\) is bounded. The resulting bit running time is

\(\operatorname{poly}\bigl(2\tau+1,\ 3\tau+2m+4,\ B\bigr)=(m+\tau+L)^{O(1)}.\)

For completeness, positivity does not require an arbitrarily precise numerical tolerance. Let \(D\) be the product of the denominators of all input masses. Then \(\log_2 D=O(L)\). A nonempty bounded polyhedron has an optimal vertex. At such a vertex, choose \(n\) linearly independent active constraints, yielding \(Mz=q\), where \(M\) is an integer matrix with entries in \(\{-1,0,1\}\), and \(Dq\) is integral.

By Cramer’s rule, each coordinate has the form

\(z_\ell=\dfrac{u_\ell}{D\det M}\)

for some integer \(u_\ell\). The determinant is a nonzero integer, and the Leibniz formula gives \(|\det M|\le n!\). Hence, if \(\varepsilon^\star>0\), then

\(\varepsilon^\star\ge\dfrac{1}{Dn!}.\)

This bound has bit length \(O(L+\tau\log(\tau+1))\). Thus an exact comparison with zero is fully compatible with polynomial bit complexity. Equivalently, one could decide feasibility after adding \(\varepsilon\ge 1/(Dn!)\).

5. Boundary case and conclusion.

When \(m=2\), every assigned type approves both alternatives, so both receive score \(\alpha_j\) in committee \(j\). The winner is necessarily the first alternative. Both targets can therefore win exactly when both have index \(1\): an allocation of the required masses exists, for example \(x_{t,j}=\alpha_j\mu_t\). The general algorithm includes this case.

The [indivisible-voter hardness theorem](https://www.ifaamas.org/Proceedings/aamas2013/docs/p439.pdf) concerns discrete committee membership. Under the divisible allocations specified here, the linear program above gives a complete polynomial-time decision procedure.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated divisible-mass problem correctly. The decision procedure runs in polynomial time in \(m,\tau,L\). No major or minor mathematical issues were found.

• Score definitions and winner conditions are correct.

The indicators \(b_{t,j,i}\) represent sincere weighted 2-Approval exactly, and the scores and differences are linear in the allocation variables.

An opponent with index \(i<k_j\) wins a tie against the target, so the target must satisfy \(d_{j,i}(x)>0\). An opponent with index \(i>k_j\) loses a tie, so \(d_{j,i}(x)\ge0\) suffices. Checking these inequalities against every opponent is both necessary and sufficient.

• The linear program encodes the allocation restrictions exactly.

Nonnegativity, the per-type capacity constraints, and the two committee equalities match the task. They permit splitting and unused mass without imposing any additional membership restrictions.

The margin constraints correctly distinguish earlier and later opponents. The upper bound \(\varepsilon\le1\) does not exclude any winning allocation: the forward implication explicitly chooses a positive margin no larger than \(1\).

The boundedness argument is valid. Each allocation coordinate lies in \([0,\mu_t]\), and \(\varepsilon\in[0,1]\). Thus a nonempty feasible region is compact, and the continuous linear objective attains its maximum.

• Both directions of the equivalence are rigorous.

For a winning allocation, every difference indexed by \(H\) is positive. Because \(H\) is finite, the stated minimum is positive and satisfies every margin constraint.

The case \(H=\varnothing\) is handled explicitly: choosing \(\varepsilon=1\) is valid because no constraint links the margin to an earlier opponent.

Conversely, an attained positive optimum forces all required strict inequalities, while the remaining constraints supply the weak inequalities. The resulting allocation therefore makes both targets win.

• The LP size and encoding bounds are correct.

There are \(2\tau+1\) variables. The inequality count is
\[ 2\tau+\tau+4+2(m-1)+2=3\tau+2m+4. \]
These terms respectively account for nonnegativity, type capacities, converted committee equalities, opponent comparisons, and margin bounds.

All matrix coefficients belong to \(\{-1,0,1\}\). The objective also has constant-size coefficients. The dense encoding bound \(B=O(\tau(\tau+m)+L)\) correctly includes the input rational right-hand sides. Computing the approval indicators requires only reading the listed rankings, so it introduces no enumeration of possible types.

• The polynomial-time LP theorem applies.

The prover states the needed theorem for rational LP feasibility and exact optimization and checks its hypotheses. The cited notes state polynomial-time solvability in the rational encoding length; their theorem concerns general LPs, rather than requiring this particular feasible region to have nonempty interior. The committee equalities therefore cause no invalid application. See [Theorem 17.1 in the cited notes](https://courses.cs.washington.edu/courses/cse521/22au/521-lecture-16.pdf).

Consequently, the claimed running time \((m+\tau+L)^{O(1)}\) follows.

• The exact-positivity argument is valid.

The denominator product \(D\) has \(\log_2D=O(L)\). A nonempty bounded polyhedron has an optimal vertex, and its active constraint normals contain \(n\) linearly independent rows, including when the polyhedron has lower dimension.

For the selected system \(Mz=q\), the matrix is integral and \(Dq\) is integral. Cramer’s rule gives the stated coordinate representation. Since \(M\) is nonsingular and its entries have absolute value at most \(1\), the Leibniz bound \(|\det M|\le n!\) holds.

A positive optimal margin therefore satisfies \(\varepsilon^\star\ge1/(Dn!)\). The stated polynomial bit-length bound follows, and the proposed additional feasibility constraint is equivalent to positive optimal margin.

• The boundary case and contextual comparison are correct.

When \(m=2\), every type approves both alternatives, so only the first-indexed target can win. The proposed allocation \(x_{t,j}=\alpha_j\mu_t\) satisfies both committee totals and every type capacity because \(\alpha_1+\alpha_2\le1\).

The cited discrete hardness result concerns indivisible committee membership and does not contradict the continuous LP procedure. This distinction agrees with the model and Theorem 5.3 in the [cited paper](https://www.ifaamas.org/Proceedings/aamas2013/docs/p439.pdf).

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩