2607.24676

Total: 1

#1 The Degree of Strategy-Proofness for Risk-Averse Committee Selection [PDF] [Copy] [Kimi] [REL]

Authors: Dael Sinay, Rica Gonen

The classic notion of strategyproofness implicitly assumes that a manipulating agent either possesses complete knowledge of what all other agents are going to report, or is willing to take the risk and act as if they know these reports. To capture the profound uncertainty of real-world voters, recent work introduced \emph{risk-avoiding truthfulness (RAT)} and the \emph{RAT-degree}, which quantifies the exact number of known reports required for a manipulation to be strictly safe. While the RAT-degree has been analyzed in settings such as single-winner elections, its implications for multi-winner voting remain unexplored. In this paper, we bridge this gap by extending the RAT-degree framework to approval-based committee (ABC) selection, a domain characterized by a fundamental tension between proportional representation and strategic robustness. Focusing on the prominent Proportional Approval Voting (PAV) rule, we investigate its susceptibility to safe subset manipulations. We establish tight bounds on its superset risk-avoiding strategy-proofness under dropping candidates, demonstrating that PAV is vulnerable to safe manipulation when the agent knows the exact ballots of $f = \lceil n/k \rceil$ other voters, but remains completely immune given knowledge of at most $f = \lfloor \frac{n}{k+1} \rfloor - 1$ voters.

Subject: Computer Science and Game Theory

Publish: 2026-07-27 17:17:19 UTC