Search

This paper presents some models and algorithms for social choice in agent networks. Agent networks are graphical models used to represent systems involving multiple, locally interacting, agents. They allow the representation of complex decision-making situations where the utility function of every agent depends on the actions of its neighbors. In this context, coordination requires some optimization method able to determine a combination of individual actions that maximizes social efficiency. We study here the maximization of different social welfare functions covering various attitudes ranging from utilitarianism to egalitarianism. For all these models we propose graph-based algorithms as well as MIP formulations to find optimal sets of actions. We also provide numerical tests to assess their practical efficiency. [ABSTRACT FROM AUTHOR]

We continue previous work by Mattei et al. (Ann. Math. Artif. Intell. 1042 68(1-3), 135-160 2013) in which they study the computational complexity of bribery schemes when voters have conditional preferences modeled as CP-nets. For most of the cases they considered, they showed that the bribery problem is solvable in polynomial time. Some cases remained open-we solve several of them and extend the previous results to the case that voters are weighted. Additionally, we consider negative (weighted) bribery in CP-nets, when the briber is not allowed to pay voters to vote for his preferred candidate. [ABSTRACT FROM AUTHOR]

The paper presents a focused survey about the presence and the use of the concept of 'preferences' in Artificial Intelligence. Preferences are a central concept for decision making and have extensively been studied in disciplines such as economy, operational research, decision analysis, psychology and philosophy. However, in the recent years it has also become an important topic both for research and applications in Computer Science and more specifically in Artificial Intelligence, in fields spanning from recommender systems to automatic planning, from non monotonic reasoning to computational social choice and algorithmic decision theory. The survey essentially covers the basics of preference modelling, the use of preference in reasoning and argumentation, the problem of compact representations of preferences, preference learning and the use of non conventional preference models based on extended logical languages. It aims at providing a general reference for all researchers both in Artificial Intelligence and Decision Analysis interested in this exciting interdisciplinary topic. [ABSTRACT FROM AUTHOR]

We study the complexity of priced control in elections. Naturally, if a given control type is NP-hard for a given voting system ɛ then its priced variant is NP-hard for this rule as well. It is, however, interesting what effect introducing prices has on the complexity of those control problems that without prices are tractable. We show that for four prominent voting rules (plurality, approval, Condorcet, and Copeland) introducing prices does not increase the complexity of control by adding/deleting candidates/voters. However, we do show an example of a scoring rule for which such an effect takes place. [ABSTRACT FROM AUTHOR]

Schulze and ranked-pairs elections have received much attention recently, and the former has quickly become a quite widely used election system. For many cases these systems have been proven resistant to bribery, control, or manipulation, with ranked pairs being particularly praised for being NP-hard for all three of those. Nonetheless, the present paper shows that with respect to the number of candidates, Schulze and ranked-pairs elections are fixed-parameter tractable to bribe, control, and manipulate: we obtain uniform, polynomial-time algorithms whose running times' degrees do not depend on the number of candidates. We also provide such algorithms for some weighted variants of these problems. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses various reports within the issue including manipulation and bribery in voting rules, matching problems and hedonic games.