Trading Proportionality for Strategic Robustness in Multi-Winner Approval Voting

Abstract

Classical strategyproofness assumes a manipulator either knows how everyone else votes or is willing to gamble as if they did. Real voters rarely do. The recently introduced RAT-degree measures how many other participants' reports an agent must actually observe before a manipulation becomes strictly safe, interpolating between full truthfulness and immunity to blind manipulation. While previously explored in auctions and single-winner settings, we bring this measure to multi-winner elections. We apply it to Approval-Based Committee (ABC) rules under free-riding: a voter drops approved candidates from their truthful ballot to concentrate weight on marginal ones. We first analyze Proportional Approval Voting (PAV). Knowledge of $\lceil n/k\rceil$ ballots already enables a safe and strictly profitable drop, whereas knowledge of at most $\lfloor n/(k+1)\rfloor -1$ ballots leaves the rule completely immune; an explicit instance shows the latter bound cannot be raised in general. Since a manipulator informed about roughly a $1/k$ fraction of the electorate therefore suffices, we ask how much proportionality must be surrendered to buy strategic robustness. We introduce $d$-RPAV, a parameterized family of Thiele rules with weights $d/(j+d-1)$ that recovers PAV at $d=1$ and approaches Approval Voting (AV) as $d$ grows. We prove that $d$-RPAV satisfies $\alpha$-Justified Representation ($\alpha$-JR) for $\alpha =d$, and is immune to safe free-riding given up to $\lfloor dn/(k+2d-1)\rfloor -1$ known ballots, yielding a clean and tunable trade-off between proportional representation and strategic robustness.