We consider approval voting elections in which each voter votes for a (possibly empty) set of candidates and the outcome consists of a set of k candidates for some parameter k, e.g., committee elections. We are interested in the minimax approval voting rule in which the outcome represents a compromise among the voters, in the sense that the maximum distance between the preference of any voter is minimized. This voting rule has two main drawbacks. First, computing an outcome that minimizes the maximum distance is computationally hard. Furthermore, any algorithm that always returns such an outcome provides incentives to voters to misreport their true preferences. In order to circumvent these drawbacks, we resort to approximation algorithms. We present a polynomial-time 2-approximation algorithm that uses a natural linear programming relaxation for the underlying optimization problem; this result improves upon the previously best known algorithm that has an approximation ratio of 3. We are furthermore interested in approximation algorithms that are resistant to manipulation by (coalitions of) voters. We complement previous results in the literature with new upper and lower bounds on strategyproof and group-strategyproof algorithms.

Joint work with Ioannis Caragiannis and Dimitris Kalaitzis.