Preference Handling in Combinatorial Domains: From AI to Social Choice
Chevaleyre, Yann, Endriss, Ulle, Lang, Jerome, Maudet, Nicolas, AI Magazine
Individual decision making is mostly guided by the agent's preferences over his or her possible decisions. Similarly, group decision making is guided by the preferences of the agents in the group. For instance, when a group of autonomous agents need to agree on an allocation of resources among themselves, then each individual will judge the outcome according to his or her own preferences and will have to transmit parts of these preferences (possibly indirectly and possibly reluctantly so) to his or her peers in the process of negotiation. Also, to be able to assess whether the negotiation outcome should be considered a "good" allocation (say, whether it reflects a fair agreement) requires knowledge of the individual preferences. Similarly, when voting on a proposition or for a candidate, the ballot submitted by each individual reflects some aspect of his or her own preferences, and the voting protocol in place is charged with aggregating these preferences into a decision that (we hope) constitutes a good reflection of the collective will of the population.
The classical discipline concerned with the study of mechanisms for collective decision making is social choice theory (Arrow, Sen, and Suzumura 2002). Much work in the field has concentrated on normative questions and on establishing abstract results regarding the possibility of designing mechanisms meeting certain requirements. For instance, a seminal result in the field, Arrow's Impossibility Theorem, shows that there can exist no preference-aggregation mechanism that would simultaneously satisfy a small number of natural requirements (for example, the aggregation function shouldn't be dictatorial). Computational concerns, however, have mostly been neglected: What is the computational complexity of the mechanisms proposed by social choice theorists? What are the appropriate algorithmic techniques for these problems? What happens if the number of alternatives to choose from becomes very large?
Such considerations have given rise to an interdisciplinary research effort at the interface of AI and computer science with social choice theory, sometimes dubbed computational social choice. On the one hand, computational social choice is concerned with the application of techniques developed in computer science, such as complexity analysis or algorithm design, to the study of social choice mechanisms, such as voting procedures or fair division algorithms. On the other hand, computational social choice seeks to import concepts from social choice theory into AI and computing. For instance, social welfare orderings originally developed to analyze the quality of resource allocations in human society are equally well applicable to problems in multiagent systems or network design.
Known methods for collective decision making and classical results from social choice theory may not always be applicable when the number of alternatives from which to choose is large. This is particularly true when the set of alternatives has a combinatorial structure. Examples include negotiation over indivisible goods (where the number of bundles an agent may obtain is exponential in the number of goods) or the election of a committee (where the number of possible committees is exponential in the number of seats to be filled). For such combinatorial problems, the mere representation of the preferences of individuals over different alternatives becomes a nontrivial problem. Here methods for preference representation and elicitation developed in AI can make an important contribution.
In this article we are going to review some of the languages for compact representation of preferences that are good candidates for modeling problems of collective decision making in combinatorial domains. We are then going to focus on two classes of collective decision-making problems where the space of alternatives has a combinatorial structure. …