We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of @math items that maximize the total derived utility of all the agents (i.e., in our example we are to pick @math movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.
@cite_5 define a family of committee election rules (which can also be used for multiple referenda) based on the following principle. Each voter specifies his or her preferred committee and each voter's disutility for a committee is given by the Hamming distance between the committee and the voter's preferred one. Then the disutilities of the voters are aggregated using an OWA operator. The committee with the lowest aggregated disutility wins. (In the particular case of the sum operator, the obtained rule is the Bloc committee election rule, while in the case of the minimum, the obtained rule is the Minimax Approval Voting rule; see the work of @cite_43 for the definition and other works for computational discussions @cite_48 @cite_33 @cite_41 .) They obtain a number of hardness and approximability results, which cannot be compared to ours because in their work, again, OWAs are used for aggregating scores coming from different agents .
@cite_33 @cite_41 @cite_48 @cite_43 @cite_5
1859600792 2181533063 2117194296 2098136663 2270513673
We consider Approval Voting systems where each voter decides on a subset of candidates he she approves. We focus on the optimization problem of finding the committee of fixed size k, minimizing the maximal Hamming distance from a vote. In this paper we give a PTAS for this problem and hence resolve the open question raised by [AAAI’10]. The result is obtained by adapting the techniques developed by [JACM’02] originally used for the less constrained Closest String problem. The technique relies on extracting information and structural properties of constant size subsets of votes. In this work, we initiate a detailed study of the parameterized complexity of Minimax Approval Voting. We demonstrate that the problem is W[2]-hard when parameterized by the size of the committee to be chosen, but does admit a FPT algorithm when parameterized by the number of strings that is more efficient than the previous ILP-based approaches for the problem. We also consider several combinations of parameters and provide a detailed landscape of the parameterized and kernelization complexity of the problem. We also study the version of the problem where we permit outliers, that is, where the chosen committee is required to satisfy a large number of voters (instead of all of them). In this context, we strengthen an APX-hardness result in the literature, and also show a simple but strong W-hardness result. Voting has been a very popular method for preference aggregation in multiagent environments. It is often the case that a set of agents with different preferences need to make a choice among a set of alternatives, where the alternatives could be various entities such as potential committee members, or joint plans of action. A standard methodology for this scenario is to have each agent express his preferences and then select an alternative according to some voting protocol. Several decision making applications in AI have followed this approach including problems in collaborative filtering [10] and planning [3, 4]. We propose in this chapter a procedure for reaching agreement on multilateral treaties that produces a compromise as close as possible to the preferences of all parties. By “close” we mean that the maximum distance of the compromise from the position of any state is minimal, which we call a minimax outcome. We show that this procedure is relatively invulnerable to strategizing by states, reducing any incentive they might have to misrepresent their preferences to try to induce a better outcome.4 We study multiple referenda and committee elections, when the ballot of each voter is simply a set of approved binary issues (or candidates). Two well-known rules under this model are the commonly used candidate-wise majority, also called the minisum rule, as well as the minimax rule. In the former, the elected committee consists of the candidates approved by a majority of voters, whereas the latter picks a committee minimizing the maximum Hamming distance to all ballots. As these rules are in some ways extreme points in the whole spectrum of solutions, we consider a general family of rules, using the Ordered Weighted Averaging (OWA) operators. Each rule is parameterized by a weight vector, showing the importance of the i-th highest Hamming distance of the outcome to the voters. The objective then is to minimize the weighted sum of the (ordered) distances. We study mostly computational, but also manipulability properties for this family. We first exhibit that for many rules, it is NP-hard to find a winning committee. We then proceed to identify cases where the problem is either efficiently solvable, or approximable with a small approximation factor. Finally, we investigate the issue of manipulating such rules and provide conditions that make this possible.