Multi-agent soft constraint aggregation via sequential voting: theoretical and experimental results

Abstract

We consider scenarios where several agents must aggregate their preferences over a large set of candidates with a combinatorial structure. That is, each candidate is an element of the Cartesian product of the domains of some variables (i.e., features). These scenarios are very common when candidates are described by feature vectors, such as cars, or houses, or any complex product. We assume agents to compactly express their preferences over the candidates via soft constraints. This is a compact way to model preferences which naturally models variables domains, and relationship among variables. To aggregate the preferences of the agents, we consider a sequential procedure that asks the agents to vote on one variable at a time. At each step, all agents express their preferences over the domain of a variable; based on such preferences, a voting rule is used to select one value for that variable. When all variables have been considered, the selected values constitute the returned variable assignment, that is, the elected candidate. We study several properties of this procedure (such as Condorcet consistency, anonymity, neutrality, monotonicity, consistency, efficiency, participation, independence of irrelevant alternatives, non dictatorship, and strategy-proofness), by relating them to corresponding properties of the adopted voting rules used for each variable. Moreover, we perform an experimental study on a special kind of soft constraints, namely fuzzy constraints. The experimental study shows that the proposed sequential procedure yields a considerable saving in time with respect to a non-sequential approach, while the winners satisfy the agents just as well, independently of the variable ordering, and of the presence of coalitions of agents.