Preference Handling in Combinatorial Domains: From AI to Social Choice
Chevaleyre, Yann, Endriss, Ulle, Lang, Jérôme, Maudet, Nicolas, AI Magazine
In both individual and collective decision making, the space of alternatives from which the agent (or the group of agents) has to choose often has a combinatorial (or multiattribute) structure. We give an introduction to preference handling in combinatorial domains in the context of collective decision making and show that the considerable body of work on preference representation and elicitation that AI researchers have been working on for several years is particularly relevant. After giving an overview of languages for compact representation of preferences, we discuss problems in voting in combinatorial domains and then focus on multiagent resource allocation and fair division. These issues belong to a larger field, which is known as computational social choice and which brings together ideas from AI and social choice theory, to investigate mechanisms for collective decision making from a computational point of view. We conclude by briefly describing some of the other research topics studied in computational social choice.
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. …