Choosing Combinatorial Social Choice by Heuristic Search

Abstract. 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 in-dependent. 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 re-duces the search effort and avoid many pairwise comparisons, and thus it significantly reduces the running time. Moreover, SC * guar-antees to choose the set of winners in aggregation rules for cardinal preferences. With Condorcet-consistent rules, SC * chooses the out-comes that are sufficiently close to the winners.