d4-conf-atal-2013-0084 (d4-conf-atal-2013-0084)

Let \(C=\{p,a,b\}\), let \(R\) be its six rankings, and let \(T=\{(p,a,b),(p,b,a)\}\) be the sincere-ranking types of manipulators who prefer \(p\). An instance gives binary-rational masses \(\nu_r\) of fixed voters of each ranking \(r\in R\), and \(\kappa_t\) of manipulators of each type \(t\in T\), with \(\sum_{r\in R}\nu_r+\sum_{t\in T}\kappa_t=1\). Decide whether there exist \(x_{t,r}\ge 0\) such that \(\sum_{r\in R}x_{t,r}=\kappa_t\) for every \(t\), and \(p\) wins CondorcetTHENPlurality on the resulting masses \(\lambda_r=\nu_r+\sum_{t\in T}x_{t,r}\), using the paper’s tie-breaking convention.

Let \(C=\{p,a,b\}\), \(m=3\), \(R\) be the six strict rankings of \(C\), and \(T=\{(p,a,b),(p,b,a)\}\) be the sincere types of manipulators.
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Types are tagged as fixed voters or manipulators; \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Write \(\nu_r\geq0\) for fixed-voter masses and \(\kappa_t\geq0\) for manipulator masses, with omitted masses zero and \(\sum_{r\in R}\nu_r+\sum_{t\in T}\kappa_t=1\).
Manipulators may divide their mass arbitrarily among reported rankings: choose real \(x_{t,r}\geq0\) satisfying \(\sum_{r\in R}x_{t,r}=\kappa_t\), producing \(\lambda_r=\nu_r+\sum_{t\in T}x_{t,r}\). Reports need not rank \(p\) first, and the same reports are used in both stages.
CondorcetTHENPlurality elects the strict Condorcet winner if one exists; otherwise it elects the plurality winner. Pairwise ties do not count as victories; plurality ties use the priority \(p\prec a\prec b\).

Is deciding whether such an allocation makes \(p\) win solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard, already with \(m=3\)?

For indivisible integer-weighted voters, coalitional manipulation of CondorcetTHENPlurality is \(\mathrm{NP}\)-complete already with three candidates and ties favoring the preferred candidate. Weighted coalitional manipulation of plurality alone is polynomial-time solvable. These discrete results do not settle the divisible-mass problem.

Result

The divisible-mass problem is polynomial-time solvable for \(m=3\). In fact, it reduces to computing six rational statistics and checking an interval. An exact implementation takes \(O((m\tau+1)L^2)\) bit operations on the stated three-candidate inputs.

We interpret the given priority as favoring \(p\) in plurality ties.

1. Aggregate the manipulator masses

Let \(K=\sum_{t\in T}\kappa_t\), and let \(z_r=\sum_{t\in T}x_{t,r}\) denote the total manipulator mass reporting ranking \(r\). Every admissible allocation satisfies \(z_r\geq0\) and \(\sum_{r\in R}z_r=K\).

Conversely, every such vector \(z\) is admissible. If \(K>0\), set

\(x_{t,r}=\kappa_tz_r/K.\)

These quantities are nonnegative, have row sums \(\kappa_t\), and aggregate to \(z_r\). If \(K=0\), take every \(x_{t,r}=0\).

Thus only the total manipulator mass matters. This uses the premise that either sincere type may report any ranking.

2. Successful reports may be assumed to rank \(p\) first

Lemma. If some allocation makes \(p\) win, moving \(p\) to the top of every manipulator report, while preserving the relative order of \(a\) and \(b\), also makes \(p\) win.

Proof. This transformation:

• weakly increases \(p\)’s pairwise margin against each rival;
• preserves the pairwise margin between \(a\) and \(b\);
• weakly increases \(p\)’s plurality score and weakly decreases each rival’s plurality score.

If \(p\) originally wins as a strict Condorcet winner, its strict victories persist.

Otherwise, originally no strict Condorcet winner exists, and \(p\) wins the plurality fallback. After the transformation, \(p\) still wins plurality, including its ties.

Neither rival can become a strict Condorcet winner: its margin against \(p\) weakly decreases, and its margin against the other rival stays unchanged. Consequently, either \(p\) becomes a strict Condorcet winner or no strict Condorcet winner exists and \(p\) wins plurality. This proves the lemma.

Therefore, it suffices to consider total manipulator reports

\(z_{(p,a,b)}=y,\qquad z_{(p,b,a)}=K-y,\qquad 0\leq y\leq K.\)

These are the reports used in both stages.

3. Express both stages using one variable

For each candidate \(c\), define its fixed-voter plurality score by

\(S_c=\sum_{r:\,c\text{ is first in }r}\nu_r.\)

For distinct candidates \(c,d\), define the fixed-voter pairwise margin by

\(D_{cd}=\sum_{r:\,c\text{ precedes }d}\nu_r-\sum_{r:\,d\text{ precedes }c}\nu_r.\)

A candidate strictly defeats another exactly when the corresponding final margin is positive.

Under the reports above, the final plurality scores are

\(S_p+K,\qquad S_a,\qquad S_b.\)

Define

\(P=D_{pa}+K,\qquad Q=D_{pb}+K,\qquad H=D_{ab}.\)

The final margins of \(p\) against \(a\) and \(b\) are respectively \(P\) and \(Q\), independently of \(y\). The final margin of \(a\) against \(b\) is

\(W(y)=H+y-(K-y)=H+2y-K.\)

As \(y\) ranges over \([0,K]\), the margin \(W(y)\) ranges over the entire closed interval \([H-K,H+K]\).

There are now three exact characterizations:

• \(p\) is a strict Condorcet winner if and only if \(P>0\) and \(Q>0\).
• \(a\) is a strict Condorcet winner if and only if \(P<0\) and \(W(y)>0\).
• \(b\) is a strict Condorcet winner if and only if \(Q<0\) and \(W(y)<0\).

For example, the second characterization follows because \(a\)’s margins against \(p\) and \(b\) are \(-P\) and \(W(y)\).

If \(p\) is not a strict Condorcet winner, the fallback elects \(p\) precisely when

\(S_p+K\geq S_a,\qquad S_p+K\geq S_b,\)

and neither rival is a strict Condorcet winner. By the characterizations above, the latter requirement is exactly

\(P<0\ \Longrightarrow\ W(y)\leq0,\qquad Q<0\ \Longrightarrow\ W(y)\geq0.\)

The weak inequalities are essential because pairwise ties do not count as victories.

4. Exact decision algorithm and correctness

Compute \(K,S_p,S_a,S_b,D_{pa},D_{pb},D_{ab}\), and hence \(P,Q,H\).

• If \(P>0\) and \(Q>0\), return YES.
• Otherwise, if \(S_p+K<S_a\) or \(S_p+K<S_b\), return NO.
• Initialize \(\ell=H-K\) and \(u=H+K\).
• If \(P<0\), replace \(u\) by \(\min(u,0)\).
• If \(Q<0\), replace \(\ell\) by \(\max(\ell,0)\).
• Return YES if and only if \(\ell\leq u\).

Sufficiency. A YES in step 1 makes \(p\) a strict Condorcet winner using any \(p\)-first allocation.

For a YES in step 6, choose \(w=\ell\) and set

\(y=(w-H+K)/2.\)

Because \(w\in[H-K,H+K]\), this satisfies \(0\leq y\leq K\), and \(W(y)=w\). The interval restrictions ensure that neither rival is a strict Condorcet winner. Step 1 failed, so \(p\) is not one either. Step 2 passed, so the plurality fallback elects \(p\).

Necessity. Suppose some allocation makes \(p\) win. By the lemma, a successful \(p\)-first allocation exists. If \(P>0\) and \(Q>0\), step 1 accepts. Otherwise, this allocation must win through plurality, so step 2 passes. Its value \(W(y)\) belongs to \([H-K,H+K]\) and satisfies every restriction imposed in steps 4–5. Hence the resulting interval is nonempty, and step 6 accepts.

This proves both directions, including the case \(K=0\).

5. Boundary case and running time

When \(P<0\) and \(Q<0\), \(p\) loses both pairwise contests. Nevertheless, it can win the fallback if it wins plurality and the manipulators can arrange \(W(y)=0\). The interval test handles this exactly.

For example, take fixed masses

\(\nu_{(p,a,b)}=1/10,\qquad \nu_{(a,b,p)}=\nu_{(b,a,p)}=3/10,\)

and total manipulator mass \(K=3/10\). Reporting masses \(1/10\) on \((p,a,b)\) and \(2/10\) on \((p,b,a)\) gives plurality scores \(4/10,3/10,3/10\). Candidate \(p\) loses both pairwise contests, but \(a\) and \(b\) tie each other. Thus no strict Condorcet winner exists, and \(p\) wins.

For complexity, the statistics require \(O(m\tau)\) ranking-processing work and \(O(\tau)\) rational arithmetic operations. The decision then uses a constant number of arithmetic operations and exact comparisons.

Every intermediate rational has \(O(L)\) bits: a common denominator may be formed from the product of input denominators, whose total bit length is \(O(L)\). Using elementary integer arithmetic, each rational operation costs \(O(L^2)\) bit operations. Therefore the total running time is \(O((m\tau+1)L^2)\) for \(m=3\).

The decision uses exact comparisons, so arbitrarily small margins and exact ties require no numerical approximation.

⟨structured verdict parsed — rendered above⟩

Verdict

The argument establishes polynomial-time solvability for the stated divisible-mass problem with \(m=3\). The aggregation, transformation of reports, interval characterization, and decision algorithm are correct, including strict pairwise comparisons, plurality ties, and zero manipulator mass.

There is one minor bookkeeping discrepancy: the introduction says “six rational statistics,” whereas the algorithm explicitly computes seven. This does not affect correctness or the running-time bound.

Step-by-step verification

1. Aggregating manipulator masses

This reduction is valid.

Every feasible allocation produces nonnegative totals \(z_r\) with \(\sum_r z_r=K\). Conversely, when \(K>0\), the proposed formula
\[ x_{t,r}=\kappa_t z_r/K \]
satisfies both required identities:
\[ \sum_r x_{t,r}=\kappa_t, \qquad \sum_t x_{t,r}=z_r. \]

When \(K=0\), nonnegativity forces every manipulator mass and every \(z_r\) to be zero, so the proposed zero allocation suffices.

No restriction involving sincere preferences has been overlooked: the task explicitly permits either manipulator type to report any ranking.

2. Moving \(p\) to the top

The lemma is correct, and its proof addresses both election stages.

Moving \(p\) upward preserves the ordering of \(a\) and \(b\), weakly improves both pairwise margins involving \(p\), and weakly improves \(p\)’s plurality position.

If \(p\) was a strict Condorcet winner, both positive margins remain positive.

If \(p\) won through fallback, neither rival was originally a strict Condorcet winner. For each rival, its margin against \(p\) can only decrease, while its margin against the other rival stays fixed. Thus a rival cannot acquire the two strict victories required to become a strict Condorcet winner. Meanwhile, \(p\) retains its plurality victory, including ties.

The lemma therefore justifies restricting attention to the two \(p\)-first rankings. The same transformed reports determine both stages, as required.

3. Scores, margins, and the feasible interval

All displayed formulas are correct.

The plurality scores are \(S_p+K,S_a,S_b\). The margins involving \(p\) are \(P=D_{pa}+K\) and \(Q=D_{pb}+K\), independently of \(y\).

The remaining margin is
\[ W(y)=H+2y-K. \]
For \(0\leq y\leq K\), its image is exactly \([H-K,H+K]\), including when \(K=0\).

The three Condorcet characterizations have the correct signs:

• \(p\) requires \(P>0\) and \(Q>0\).
• \(a\) requires \(P<0\) and \(W(y)>0\).
• \(b\) requires \(Q<0\) and \(W(y)<0\).

Consequently, excluding both rivals requires exactly the stated implications. Equality is correctly permitted because a pairwise tie is not a victory.

The plurality inequalities also correctly implement the supplied priority favoring \(p\).

4. Decision algorithm

Both directions of correctness are established.

Step 1 correctly accepts whenever \(p\) can be a strict Condorcet winner under the restricted reports.

After step 1 fails, the margins \(P,Q\) ensure that \(p\) is never a strict Condorcet winner within this family. Therefore failure of either plurality inequality justifies step 2’s rejection.

Steps 3–5 intersect the attainable interval with precisely the restrictions excluding rival Condorcet winners. Step 6 therefore tests the correct feasibility condition.

For sufficiency, the chosen \(w=\ell\) belongs to the original attainable interval whenever the final interval is nonempty. The formula
\[ y=(w-H+K)/2 \]
then yields an admissible allocation with \(W(y)=w\). No strict Condorcet winner exists, and the plurality inequalities elect \(p\).

For necessity, the lemma supplies a successful restricted allocation. Its margin satisfies every interval restriction, so the interval cannot be empty.

No assumption of positive \(K\), positive margins, or positive interval length enters this argument.

5. Boundary example

The example checks out. Its fixed-voter quantities are
\[ S_p=\frac{1}{10},\qquad S_a=S_b=\frac{3}{10}, \]
\[ D_{pa}=D_{pb}=-\frac{5}{10},\qquad H=\frac{1}{10}. \]

With \(K=\frac{3}{10}\) and \(y=\frac{1}{10}\), the resulting margins are
\[ P=Q=-\frac{2}{10},\qquad W(y)=0. \]

Thus \(p\) loses both pairwise contests, neither rival strictly defeats the other, and \(p\) wins plurality with score \(\frac{4}{10}\). The masses sum to one.

6. Exact arithmetic and running time

The complexity argument is valid for the stated three-candidate inputs.

The statistics require \(O(m\tau)\) ranking processing and \(O(\tau)\) rational operations. The decision phase performs a constant number of additional operations.

The product of input denominators has \(O(L)\) bits. The sums and differences used here consequently admit exact rational representations of \(O(L)\) bits. Elementary exact arithmetic supports the stated \(O(L^2)\) bound per operation, giving the claimed total bound
\[ O((m\tau+1)L^2). \]

This establishes polynomial time for \(m=3\); the output does not assert an algorithm for unrestricted candidate counts.

7. Minor issue and actionable feedback

Minor — introductory statistic count. The introduction says “six rational statistics,” but Section 4 explicitly lists seven: \(K,S_p,S_a,S_b,D_{pa},D_{pb},D_{ab}\).

Minimum clarification: make the introductory count consistent with the quantities explicitly computed, or explain the counting convention. No mathematical repair is needed.

⟨structured verdict parsed — rendered above⟩