We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional approval voting, and reweighted approval voting. We first show that computing the winner for proportional approval voting is NP-hard, closing a long standing open problem. As none of the rules are strategyproof, even for dichotomous preferences, we study various strategic aspects of the rules. In particular, we examine the computational complexity of computing a best response for both a single agent and a group of agents. In many settings, we show that it is NP-hard for an agent or agents to compute how best to vote given a fixed set of approval ballots from the other agents.
The Handbook of Approval Voting discusses various approval-based multi-winner rules including @math , @math and @math . Another prominent multi-winner rule in the Handbook is @cite_15 . Each agent's approval ballot and the winning set can be seen as a binary vector. Minimax approval voting selects the set of @math candidates that minimizes the maximum Hamming distance from the submitted ballots. Although minimax approval voting is a natural and elegant rule, showed that computing the winner set is unfortunately NP-hard. Strategic issues and approximation questions for minimax approval voting are covered in @cite_19 and @cite_12 where the problem is known as the closest string problem.''
@cite_19 @cite_15 @cite_12
132136377 2017492304 1979149941
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 min-imax 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 and the outcome is as small as possible. 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 consider approximation algorithms, i.e., algorithms that produce an outcome that approximates the minimax distance for any given instance. Such algorithms can be considered as alternative voting rules. We present a polynomial-time 2-approximation algorithm that uses a natural linear programming relaxation for the underlying optimization problem and deterministically rounds the fractional solution in order to compute the outcome; 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, i.e., algorithms that do not motivate voters to misreport their true preferences in order to improve their distance from the outcome. We complement previous results in the literature with new upper and lower bounds on strategyproof and group-strategyproof algorithms. A new voting procedure for electing committees, called the minimax procedure, is described. Based on approval balloting, it chooses the committee that minimizes the maximum Hamming distance to voters’ ballots, where these ballots are weighted by their proximity to other voters’ ballots. This minimax outcome may be diametrically opposed to the outcome obtained by aggregating approval votes in the usual manner, which minimizes the sum of the Hamming distances and is called the minisum outcome. The manipulability of these procedures, and their applicability when election outcomes are restricted in various ways, are also investigated. CLOSEST STRING is one of the core problems in the field of consensus word analysis with particular importance for computational biology. Given k strings of the same length and a nonnegative integer d , find a center string'' s such that none of the given strings has the Hamming distance greater than d from s . CLOSEST STRING is NP-complete. In biological applications, however, d is usually very small. We show how to solve CLOSEST STRING in linear time for fixed d —the exponential growth in d is bounded by O(dd) . We extend this result to the closely related problems d -MISMATCH and DISTINGUISHING STRING SELECTION. Moreover, we also show that CLOSEST STRING is solvable in linear time when k is fixed and d is arbitrary. In summary, this means that CLOSEST STRING is fixed-parameter tractable with respect to parameter d and with respect to parameter k . Finally, the practical usefulness of our findings is substantiated by some experimental results.