Choosing Combinatorial Social Choice by Heuristic Search

Minyi Li, Quoc Bao Vo

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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.
Original languageEnglish
Title of host publicationECAI 2012, 20th European conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France, Including, Prestigious Applications of Artificial Intellence (PAIS 2012), Proceedings
EditorsLuc De Raedt, Christian Bessiere, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz, Peter Lucas
Place of PublicationAmsterdam Netherlands
PublisherIOS Press
Number of pages6
ISBN (Electronic)9781614990987
ISBN (Print)9781614990970
Publication statusPublished - 2012
Externally publishedYes
EventEuropean Conference on Artificial Intelligence 2012 - Montpellier, France
Duration: 27 Aug 201231 Aug 2012
Conference number: 20th

Publication series

NameFrontiers in Artificial Intelligence and Applications
PublisherIOS Press
ISSN (Print)0922-6389
ISSN (Electronic)1879-8314


ConferenceEuropean Conference on Artificial Intelligence 2012
Abbreviated titleECAI 2012
Internet address

Cite this