The learnability of voting rules

Scoring rules and voting trees are two broad and concisely-representable classes of voting rules; scoring rules award points to alternatives according to their position in the preferences of the voters, while voting trees are iterative procedures that select an alternative based on pairwise comparisons. In this paper, we investigate the PAC-learnability of these classes of rules. We demonstrate that the class of scoring rules, as functions from preferences into alternatives, is efficiently learnable in the PAC model. With respect to voting trees, while in general a learning algorithm would require an exponential number of samples, we show that if the number of leaves is polynomial in the size of the set of alternatives, then a polynomial training set suffices. We apply these results in an emerging theory: automated design of voting rules by learning.     

Computational complexity of manipulation: A survey

In situations when a group of people has to make a decision based on the set of individual preferences, they use a certain aggregation method, in particular, voting. One of the main problems for any non-dictatorial social choice rule is the possibility for the voters to achieve a more preferable outcome of the voting by misrepresenting their preferences. Such actions on behalf of the voters are called manipulation, or strategic voting. One approach used to compare social choice rules in terms of how hard they are to manipulate is to find the complexity classes of manipulation problems for a given aggregation method. In this work, we present a survey of the studies of complexity classes of manipulation problems under various model assumptions and constraints.     

Positional Voting Methods Satisfying the Criteria of Weak Mutual Majority and Condorcet Loser

This paper considers a voting problem in which the individual preferences of electors are defined by the ranked lists of candidates. For single-winner elections, we apply the criterion of weak positional dominance (WPD, PD), which is closely related to the positional scoring rules. Also we formulate the criterion of weak mutual majority (WMM), which is stronger than the majority criterion but weaker than the criterion of mutual majority (MM). Then we construct two modifications for the median voting rule that satisfy the Condorcet loser criterion. As shown below, WPD and WMM are satisfied for the first modification while PD and MM for the second modification. We prove that there is no rule satisfying WPD and MM simultaneously. Finally, we check a list of 37 criteria for the constructed rules.     

Winner determination in voting trees with incomplete preferences and weighted votes

In multiagent settings where agents have different preferences, preference aggregation can be an important issue. Voting is a general method to aggregate preferences. We consider the use of voting tree rules to aggregate agents’ preferences. In a voting tree, decisions are taken by performing a sequence of pairwise comparisons in a binary tree where each comparison is a majority vote among the agents. Incompleteness in the agents’ preferences is common in many real-life settings due to privacy issues or an ongoing elicitation process. We study how to determine the winners when preferences may be incomplete, not only for voting tree rules (where the tree is assumed to be fixed), but also for the Schwartz rule (in which the winners are the candidates winning for at least one voting tree). In addition, we study how to determine the winners when only balanced trees are allowed. In each setting, we address the complexity of computing necessary (respectively, possible) winners, which are those candidates winning for all completions (respectively, at least one completion) of the incomplete profile. We show that many such winner determination problems are computationally intractable when the votes are weighted. However, in some cases, the exact complexity remains unknown. Since it is generally computationally difficult to find the exact set of winners for voting trees and the Schwartz rule, we propose several heuristics that find in polynomial time a superset of the possible winners and a subset of the necessary winners which are based on the completions of the (incomplete) majority graph built from the incomplete profiles.     

Positional scoring-based allocation of indivisible goods

We define a family of rules for dividing m indivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents’ preferences over sets of goods are additive, but that the input is ordinal: each agent reports her preferences simply by ranking single goods. Similarly to positional scoring rules in voting, a scoring vector \(s = (s_1, \ldots , s_m)\) consists of m nonincreasing, nonnegative weights, where \(s_i\) is the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function \(\star \) such as, typically, \(+\) or \(\min \). The rule associated with s and \(\star \) maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation: we show that for commonly used scoring vectors and aggregation functions this problem is NP-hard and we exhibit some tractable particular cases.     

Is computational complexity a barrier to manipulation?

When agents are acting together, they may need a simple mechanism to decide on joint actions. One possibility is to have the agents express their preferences in the form of a ballot and use a voting rule to decide the winning action(s). Unfortunately, agents may try to manipulate such an election by mis-reporting their preferences. Fortunately, it has been shown that it is NP-hard to compute how to manipulate a number of different voting rules. However, NP-hardness only bounds the worst-case complexity. In this survey article, we summarize the evidence for and against computational complexity being a barrier to manipulation. We look both at techniques identified to increase complexity (for example, hybridizing together two or more voting rules), as well as other features that may change the computational complexity of computing a manipulation (for example, if votes are restricted to be single peaked then some of the complexity barriers fall away). We discuss recent theoretical results that consider the average case, as well as simple greedy and approximate methods. We also describe how computational ??phase transitions??, which have been fruitful in identifying hard instances of propositional satisfiability and other NP-hard problems, have provided insight into the hardness of manipulating voting rules in practice. Finally, we consider manipulation of other related problems like stable marriage and tournament problems.     

Voting almost maximizes social welfare despite limited communication

In cooperative multiagent systems an alternative that maximizes the social welfare—the sum of utilities—can only be selected if each agent reports its full utility function. This may be infeasible in environments where communication is restricted. Employing a voting rule to choose an alternative greatly reduces the communication burden, but leads to a possible gap between the social welfare of the optimal alternative and the social welfare of the one that is ultimately elected. Procaccia and Rosenschein (2006) [13] have introduced the concept of distortion to quantify this gap.In this paper, we present the notion of embeddings into voting rules: functions that receive an agent?s utility function and return the agent?s vote. We establish that very low distortion can be obtained using randomized embeddings, especially when the number of agents is large compared to the number of alternatives. We investigate our ideas in the context of three prominent voting rules with low communication costs: Plurality, Approval, and Veto. Our results arguably provide a compelling reason for employing voting in cooperative multiagent systems.     

A Movie Recommendation System – An Application of Voting Theory in User Modeling

Our research agenda focuses on building software agents that can employ user modeling techniques to facilitate information access and management tasks. Personal assistant agents embody a clearly beneficial application of intelligent agent technology. A particular kind of assistant agents, recommender systems, can be used to recommend items of interest to users. To be successful, such systems should be able to model and reason with user preferences for items in the application domain. Our primary concern is to develop a reasoning procedure that can meaningfully and systematically tradeoff between user preferences. We have adapted mechanisms from voting theory that have desirable guarantees regarding the recommendations generated from stored preferences. To demonstrate the applicability of our technique, we have developed a movie recommender system that caters to the interests of users. We present issues and initial results based on experimental data of our research that employs voting theory for user modeling, focusing on issues that are especially important in the context of user modeling. We provide multiple query modalities by which the user can pose unconstrained, constrained, or instance-based queries. Our interactive agent learns a user model by gaining feedback aboutits recommended movies from the user. We also provide pro-active information gathering to make user interaction more rewarding. In the paper, we outline the current status of our implementation with particular emphasis on the mechanisms used to provide robust and effective recommendations.     

Social choice rules driven by propositional logic

Several rules for social choice are examined from a unifying point of view that looks at them as procedures for revising a system of degrees of belief in accordance with certain specified logical constraints. Belief is here a social attribute, its degrees being measured by the fraction of people who share a given opinion. Different known rules and some new ones are obtained depending on which particular constraints are assumed. These constraints allow to model different notions of choiceness. In particular, we give a new method to deal with approval-disapproval-preferential voting.     

Deterministic voting in distributed systems using error-correctingcodes

Distributed voting is an important problem in reliable computing. In an N Modular Redundant (NMR) system, the N computational modules execute identical tasks and they need to periodically vote on their current states. In this paper, we propose a deterministic majority voting algorithm for NMR systems. Our voting algorithm uses error-correcting codes to drastically reduce the average case communication complexity. In particular, we show that the efficiency of our voting algorithm can be improved by choosing the parameters of the error-correcting code to match the probability of the computational faults. For example, consider an NMR system with 31 modules, each with a state of m bits, where each module has an independent computational error probability of 10^-3. 1, this NMR system, our algorithm can reduce the average case communication complexity to approximately 1.0825 m compared with the communication complexity of 31 m of the naive algorithm in which every module broadcasts its local result to all other modules. We have also implemented the voting algorithm over a network of workstations. The experimental performance results match well the theoretical predictions     

Every team deserves a second chance: an extended study on predicting team performance

Voting among different agents is a powerful tool in problem solving, and it has been widely applied to improve the performance in finding the correct answer to complex problems. We present a novel benefit of voting, that has not been observed before: we can use the voting patterns to assess the performance of a team and predict their final outcome. This prediction can be executed at any moment during problem-solving and it is completely domain independent. Hence, it can be used to identify when a team is failing, allowing an operator to take remedial procedures (such as changing team members, the voting rule, or increasing the allocation of resources). We present three main theoretical results: (1) we show a theoretical explanation of why our prediction method works; (2) contrary to what would be expected based on a simpler explanation using classical voting models, we show that we can make accurate predictions irrespective of the strength (i.e., performance) of the teams, and that in fact, the prediction can work better for diverse teams composed of different agents than uniform teams made of copies of the best agent; (3) we show that the quality of our prediction increases with the size of the action space. We perform extensive experimentation in two different domains: Computer Go and Ensemble Learning. In Computer Go, we obtain high quality predictions about the final outcome of games. We analyze the prediction accuracy for three different teams with different levels of diversity and strength, and show that the prediction works significantly better for a diverse team. Additionally, we show that our method still works well when trained with games against one adversary, but tested with games against another, showing the generality of the learned functions. Moreover, we evaluate four different board sizes, and experimentally confirm better predictions in larger board sizes. We analyze in detail the learned prediction functions, and how they change according to each team and action space size. In order to show that our method is domain independent, we also present results in Ensemble Learning, where we make online predictions about the performance of a team of classifiers, while they are voting to classify sets of items. We study a set of classical classification algorithms from machine learning, in a data-set of hand-written digits, and we are able to make high-quality predictions about the final performance of two different teams. Since our approach is domain independent, it can be easily applied to a variety of other domains.     

Towards a dichotomy for the Possible Winner problem in elections based on scoring rules

To make a joint decision, agents (or voters) are often required to provide their preferences as linear orders. To determine a winner, the given linear orders can be aggregated according to a voting protocol. However, in realistic settings, the voters may often only provide partial orders. This directly leads to the Possible Winner problem that asks, given a set of partial votes, whether a distinguished candidate can still become a winner. In this work, we consider the computational complexity of Possible Winner for the broad class of voting protocols defined by scoring rules. A scoring rule provides a score value for every position which a candidate can have in a linear order. Prominent examples include plurality, k-approval, and Borda. Generalizing previous NP-hardness results for some special cases, we settle the computational complexity for all but one scoring rule. More precisely, for an unbounded number of candidates and unweighted voters, we show that Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule defined by the scoring vector (2,1,…,1,0), while it is solvable in polynomial time for plurality and veto.     

A social network approach to trust management in VANETs

In the past few years, vehicular ad hoc networks(VANETs) was studied extensively by researchers. VANETs is a type of P2P network, though it has some distinct characters (fast moving, short lived connection etc.). In this paper, we present several limitations of current trust management schemes in VANETs and propose ways to counter them. We first review several trust management techniques in VANETs and argue that the ephemeral nature of VANETs render them useless in practical situations. We identify that the problem of information cascading and oversampling, which commonly arise in social networks, also adversely affects trust management schemes in VANETs. To the best of our knowledge, we are the first to introduce information cascading and oversampling to VANETs. We show that simple voting for decision making leads to oversampling and gives incorrect results in VANETs. To overcome this problem, we propose a novel voting scheme. In our scheme, each vehicle has different voting weight according to its distance from the event. The vehicle which is more closer to the event possesses higher weight. Simulations show that our proposed algorithm performs better than simple voting, increasing the correctness of voting.     

Predicting user demographics from music listening information

Online activities such as social networking, online shopping, and consuming multi-media create digital traces, which are often analyzed and used to improve user experience and increase revenue, e. g., through better-fitting recommendations and more targeted marketing. Analyses of digital traces typically aim to find user traits such as age, gender, and nationality to derive common preferences. We investigate to which extent the music listening habits of users of the social music platform Last.fm can be used to predict their age, gender, and nationality. We propose a feature modeling approach building on Term Frequency-Inverse Document Frequency (TF-IDF) for artist listening information and artist tags combined with additionally extracted features. We show that we can substantially outperform a baseline majority voting approach and can compete with existing approaches. Further, regarding prediction accuracy vs. available listening data we show that even one single listening event per user is enough to outperform the baseline in all prediction tasks. We also compare the performance of our algorithm for different user groups and discuss possible prediction errors and how to mitigate them. We conclude that personal information can be derived from music listening information, which indeed can help better tailoring recommendations, as we illustrate with the use case of a music recommender system that can directly utilize the user attributes predicted by our algorithm to increase the quality of it’s recommendations.

     

Anyone but him: The complexity of precluding an alternative

Preference aggregation in a multiagent setting is a central issue in both human and computer contexts. In this paper, we study in terms of complexity the vulnerability of preference aggregation to destructive control. In particular, we study the ability of an election's chair to, through such mechanisms as voter/candidate addition/suppression/partition, ensure that a particular candidate (equivalently, alternative) does not win. And we study the extent to which election systems can make it impossible, or computationally costly (NP-complete), for the chair to execute such control. Among the systems we study—plurality, Condorcet, and approval voting—we find cases where systems immune or computationally resistant to a chair choosing the winner nonetheless are vulnerable to the chair blocking a victory. Beyond that, we see that among our studied systems no one system offers the best protection against destructive control. Rather, the choice of a preference aggregation system will depend closely on which types of control one wishes to be protected against. We also find concrete cases where the complexity of or susceptibility to control varies dramatically based on the choice among natural tie-handling rules.     

Discovering relationship types between users using profiles and shared photos in a social network

In this paper, we propose a new approach to discover the relationship types between a user and her contacts in a social network. This is of key importance for many applications in the domain of photo sharing, privacy protection, information enriching, etc. Our approach is based, on one hand, on information extracted from users’ profiles and their shared photos, and, on the other hand, on a set of predefined rules validated by the main user before being mined and derived according to her preferences and social network content. The contribution of our method is twofold: 1) it is user-based enabling the user to set her preferences and give her feedbacks on the derived rules and results, and 2) it is multi-criteria that exploits and combines several attributes and features from user profiles and shared photos respectively. It also allows the user to define new relationship types. We conducted a set of experiments to validate our approach. The obtained results show the accuracy of our approach in different scenarios.     

Computational aspects of strategic behaviour in elections with top-truncated ballots

Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. Much of this literature, however, makes the assumption that the voters or agents specify a complete preference ordering over the set of candidates. There are many multiagent systems applications, and even real-world elections, where this assumption is not warranted, and this in turn raises a series of questions on the impact of partial voting on the complexity of manipulative actions. In this paper, we focus on two of these questions. First, we address the question of how hard it is to manipulate elections when the agents specify only top-truncated ballots. Here, in particular, we look at the weighted manipulation problem—both constructive and destructive manipulation—when the voters are allowed to specify top-truncated ballots, and we provide general results for all scoring rules, for elimination versions of all scoring rules, for the plurality with runoff rule, for a family of election systems known as Copeland\(^{\alpha }\), and for the maximin protocol. The second question we address is the impact of top-truncated voting on the complexity of manipulative actions in electorates with structured preference profiles. In particular, we consider electorates that are single-peaked and we show how, for many voting protocols, allowing top-truncated voting reimposes the \(\mathcal {NP}\)-hardness shields that normally vanish in such electorates.     

Stable Marriage with General Preferences

We propose a generalization of the classical stable marriage problem. In our model, the preferences on one side of the partition are given in terms of arbitrary binary relations, which need not be transitive nor acyclic. This generalization is practically well-motivated, and as we show, encompasses the well studied hard variant of stable marriage where preferences are allowed to have ties and to be incomplete. As a result, we prove that deciding the existence of a stable matching in our model is NP-complete. Complementing this negative result we present a polynomial-time algorithm for the above decision problem in a significant class of instances where the preferences are asymmetric. We also present a linear programming formulation whose feasibility fully characterizes the existence of stable matchings in this special case. Finally, we use our model to study a long standing open problem regarding the existence of cyclic 3D stable matchings. In particular, we prove that the problem of deciding whether a fixed 2D perfect matching can be extended to a 3D stable matching is NP-complete, showing this way that a natural attempt to resolve the existence (or not) of 3D stable matchings is bound to fail.     

Reasoning about Actions and Planning with Preferences Using Prioritized Default Theory

This paper shows how action theories, expressed in an extended version of the language     , can be naturally encoded using Prioritized Default Theory . We also show how prioritized default theory can be extended to express preferences between rules . This extension provides a natural framework to introduce different types of preferences in action theories— preferences between actions and preferences between final states . In particular, we demonstrate how these preferences can be expressed within extended prioritized default theory. We also discuss how this framework can be implemented in terms of answer set programming.     

Bribery in voting with CP-nets

We investigate the computational complexity of finding optimal bribery schemes in voting domains where the candidate set is the Cartesian product of a set of variables and voters use CP-nets, an expressive and compact way to represent preferences. To do this, we generalize the traditional bribery problem to take into account several issues over which agents vote, and their inter-dependencies. We consider five voting rules, three kinds of bribery actions, and five cost schemes. For most of the combinations of these parameters, we find that bribery in this setting is computationally easy.