Motivated by the common academic problem of allocating papers to referees for conference reviewing we propose a novel mechanism for solving the assignment problem when we have a two sided matching problem with preferences from one side (the agents reviewers) over the other side (the objects papers) and both sides have capacity constraints. The assignment problem is a fundamental problem in both computer science and economics with application in many areas including task and resource allocation. We draw inspiration from multi-criteria decision making and voting and use order weighted averages (OWAs) to propose a novel and flexible class of algorithms for the assignment problem. We show an algorithm for finding a @math -OWA assignment in polynomial time, in contrast to the NP-hardness of finding an egalitarian assignment. Inspired by this setting we observe an interesting connection between our model and the classic proportional multi-winner election problem in social choice.
We make use of Order weighted averages (OWAs), often employed in multi-criteria decision making @cite_6 . OWAs have recently received attention in computational social choice for voting and ranking @cite_17 , finding a collective set of items for a group @cite_29 , and multi-winner voting with proportional representation @cite_14 @cite_8 . The key difference between CPAP and voting using OWAs in the ComSoc literature is that CPAP does not select a set of winners that all agents will share. Instead, all agents are allocated a possibly disjoint set of objects.
@cite_14 @cite_8 @cite_29 @cite_6 @cite_17
2060907774 1972375916 2270513673 2269108872
The author is primarily concerned with the problem of aggregating multicriteria to form an overall decision function. He introduces a type of operator for aggregation called an ordered weighted aggregation (OWA) operator and investigates the properties of this operator. The OWA's performance is found to be between those obtained using the AND operator, which requires all criteria to be satisfied, and the OR operator, which requires at least one criteria to be satisfied. > In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using protocols where determining a beneficial manipulation is hard. Especially among computational agents, it is reasonable to measure this hardness by computational complexity. Some earlier work has been done in this area, but it was assumed that the number of voters and candidates is unbounded. Such hardness results lose relevance when the number of candidates is small, because manipulation algorithms that are exponential only in the number of candidates (and only slightly so) might be available. We give such an algorithm for an individual agent to manipulate the Single Transferable Vote (STV) protocol, which has been shown hard to manipulate in the above sense. This motivates the core of this article, which derives hardness results for realistic elections where the number of candidates is a small constant (but the number of voters can be large). The main manipulation question we study is that of coalitional manipulation by weighted voters. (We show that for simpler manipulation problems, manipulation cannot be hard with few candidates.) We study both constructive manipulation (making a given candidate win) and destructive manipulation (making a given candidate not win). We characterize the exact number of candidates for which manipulation becomes hard for the plurality, Borda, STV, Copeland, maximin, veto, plurality with runoff, regular cup, and randomized cup protocols. We also show that hardness of manipulation in this setting implies hardness of manipulation by an individual in unweighted settings when there is uncertainty about the others' votes (but not vice-versa). To our knowledge, these are the first results on the hardness of manipulation when there is uncertainty about the others' votes. 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. Weighted voting games provide a simple model of decision-making in human societies and multi-agent systems. Such games are described by a set of players, a list of [email protected]? weights, and a quota; a coalition of the players is said to be winning if the total weight of its members meets or exceeds the quota. The power of a player in a weighted voting game is traditionally identified with her Shapley-Shubik index or her Banzhaf index, two classic power measures that reflect the [email protected]?s marginal contribution under different coalition formation scenarios. In this paper, we investigate by how much one can change a [email protected]?s power, as measured by these indices, by modifying the quota. We give tight bounds on the changes in the individual [email protected]?s power that can result from a change in quota. We then describe an efficient algorithm for determining whether there is a value of the quota that makes a given player a dummy, i.e., reduces her power (as measured by both indices) to 0. We also study how the choice of quota can affect the relative power of the players. Finally, we investigate scenarios where [email protected]?s choice in setting the quota is constrained. We show that optimally choosing between two values of the quota is complete for the complexity class PP, which is believed to be significantly more powerful than NP. On the other hand, we empirically demonstrate that even small changes in quota can have a significant effect on a [email protected]?s power.