Free-Riding in Multi-Issue Decisions

The strongest positive case is for the paper’s sequential PAV result: the individual free-rider should become a coordinated, like-minded bloc. This is not a covert change of subject—the authors themselves observe that with many voters it makes sense to consider groups that free-ride, subject to a coordination assumption.

Call the lead problem Sequential PAV Mass-Free-Riding. An instance has a finite set \(T\) of true approval-profile types \(t=(A^t_1,\ldots,A^t_k)\), rational masses \(\mu_t\) summing to one, ordered issues and candidate sets, fixed tie-breaking, and a designated strategic type \(p\). Initially every type reports truthfully. For a PAV score, write \(H(q)=\sum_{j=1}^q 1/j\). At each issue, sequential PAV chooses the candidate with greatest mass-weighted marginal score
\[ \sum_{t\text{ reporting approval of }c}\mu_t/(q_t+1), \]
where \(q_t\) is that reporting group’s prior reported satisfaction.

The action is a mass decision: choose \(0<x\leq\mu_p\), a set \(I\) of issues, and alternative reports \(B_i\subseteq C_i\) for that mass \(x\) of type \(p\); the remaining \(\mu_p-x\) reports truthfully. Let \(w\) be the truthful sequence and \(w'\) the sequence after the split. The action is valid free-riding if, for every \(i\in I\),
\[ w_i\in A^p_i,\qquad w_i\notin B_i,\qquad w'_i=w_i. \]
The question is whether some valid action strictly improves the bloc’s true satisfaction:
\[ |\{i:w'_i\in A^p_i\}|>|\{i:w_i\in A^p_i\}|. \]
A solution is the mass \(x\), the affected issues, and the altered reports; its objective can also naturally be strengthened to minimize the mass needed for a given gain.

This is a direct continuous analogue of the paper’s Theorem 13, which proves that \(R\)-Free-Riding is NP-complete for every sequential \(f\)-Thiele rule satisfying the stated plateau-then-strict-decrease condition—explicitly including sequential PAV. It is proved in the paper, with the AAMAS version giving a 3-SAT proof sketch and referring to the full version for details.

I expect this continuous problem to be Class B: hardness transfers. Restrict the mass action to \(x=\mu_p\), give each voter in the Theorem 13 construction its own approval-profile type, and assign equal rational mass to each type. The sequential PAV score is just the original score divided by the electorate size, so every comparison and tie-break is unchanged. To make the regime genuinely high-multiplicity rather than merely notational, replace every construction voter by \(B\) identical voters, for an arbitrarily large \(B\). There are then \(B(2n+2)\) people but only \(2n+2\) types, and the same outcome path and manipulation exist. The reduction’s combinatorics live in the issues, alternatives, and type roles that encode the truth assignment—not in the multiplicity of indistinguishable voters. Continuization therefore does not dissolve this hardness, but it identifies exactly why it survives.

There is a plausible deployment regime. Think of a national association, union federation, or large platform repeatedly deciding policy positions. Many members share an approval profile across the policy sequence: for example, members of a regional or occupational constituency with the same bundle of priorities. A constituency coordinator can recommend that its supporters withhold approval from an already-secure policy plank to obtain more consideration later. There may be millions of voters, hundreds of empirically relevant approval types, and a relatively small number of organised blocs. That is recognisably the paper’s sequential multi-issue/perpetual-voting setting, now stated at the scale where its own Section 5 says group free-riding becomes the appropriate question.

A worthwhile second anchor is Theorem 10, proved in this paper: for every non-utilitarian \(f\)-Thiele rule, both ordinary and generalized \(R\)-Free-Riding Recognition are NP-hard. For global PAV, the corresponding question is Global PAV Mass-Free-Riding Recognition. The instance is the same finite distribution of true approval types, a designated type \(p\), issue \(i\), and a currently winning candidate \(c\in A^p_i\). The outcome maximizes
\[ \sum_{t\in T}\mu_t H(\operatorname{sat}_t(\bar w)) \]
with reports replacing true approvals for strategic subgroups. Does there exist \(0<x\leq\mu_p\) and a false report for that mass on issue \(i\), excluding \(c\), such that \(c\) remains the selected candidate on issue \(i\)? The generalized version only requires the new winner to remain truly approved by \(p\).

This exactly preserves the theorem’s recognition question, except that the strategic voter is a mass of indistinguishable voters. Again, restricting to an entire type bloc and normalizing the replicated discrete construction yields the same PAV optimization problem. Thus it is also Class B. It covers the paper’s optimization-based feasibility result, while the sequential problem above covers its more substantive “is free-riding beneficial?” result.

The important scope limit is that I am not claiming to continuize every result in the paper. In particular, a literal single voter has zero mass and cannot manipulate a continuum outcome; Theorem 13 becomes meaningful only after replacing unilateral action with coordinated type-level action. That is also the weakest point of the case: coordination is an extra behavioural assumption, and a constituency need not be able to act as one. The case survives because it is explicit rather than hidden, because the authors themselves flag exactly this group extension, and because there are credible settings with organised blocs. It would be weak for an informal committee of seven; it is a strong continuous object for a large repeated public-decision process with real demographic or organisational types.