In the impartial selection problem, a subset of agents up to a fixed size k among a group of n is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is α-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of α of the votes received by the subset of size k with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly 1/[2n/k]. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best-known approximation ratio of 1/k for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to k agents are to be selected, with a loss in the approximation ratio of 1/2.

We introduce a general problem about bribery in voting systems. In theR-Multi-Briberyproblem,the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the perturbedelection under the voting ruleR. Voters assign prices for withdrawing their vote, for swapping thepositions of two consecutive candidates in their preference order, and for perturbing their approval countto favour candidates.As our main result, we show thatR-Multi-Briberyis fixed-parameter tractable parameterized bythe number of candidates for many natural voting rulesR, including Kemeny rule, all scoring protocols,maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves theparameterized complexity ofR-Swap Briberyfor all those voting rules, thereby solving a long-standingopen problem and “Challenge #2” of the “Nine Research Challenges in Computational Social Choice”by Bredereck et al.Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlierdouble-exponential time algorithm by Dorn and Schlotter that is restricted to the uniform-cost case forall scoring protocols, the maximin rule, and Bucklin rule.