A Distributed Protocol for Collective Decision-Making in Combinatorial Domains

In this paper, we study the problem of collective decision-making over combinatorial domains. We focus on a particular social choice rule, namely Smith/Minimax. We introduce a distributed protocol for collective decision-making, which is general enough and does not restrict the choice of preference representation languages. The final decision chosen is guaranteed to be a Smith member, and is sufficiently close to the Smith/Minimax candidate. Moreover, it enables distributed decision-making and significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons.