Choosing combinatorial social choice by heuristic search

This paper studies the problem of computing aggregation rules in combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are usually not preferentially independent. We propose a very general heuristic framework SC* for computing different aggregation rules, including rules for cardinal preference structures and Condorcet-consistent rules. SC* highly reduces the search effort and avoid many pairwise comparisons, and thus it significantly reduces the running time. Moreover, SC* guarantees to choose the set of winners in aggregation rules for cardinal preferences. With Condorcet-consistent rules, SC* chooses the outcomes that are sufficiently close to the winners.