Preference Handling in Combinatorial Domains: From AI to Social Choice

By Chevaleyre, Yann; Endriss, Ulle et al. | AI Magazine, Winter 2008 | Go to article overview

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. …

The rest of this article is only available to active members of Questia

Already a member? Log in now.

Notes for this article

Add a new note
If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
One moment ...
Default project is now your active project.
Project items

Items saved from this article

This article has been saved
Highlights (0)
Some of your highlights are legacy items.

Highlights saved before July 30, 2012 will not be displayed on their respective source pages.

You can easily re-create the highlights by opening the book page or article, selecting the text, and clicking “Highlight.”

Citations (0)
Some of your citations are legacy items.

Any citation created before July 30, 2012 will labeled as a “Cited page.” New citations will be saved as cited passages, pages or articles.

We also added the ability to view new citations from your projects or the book or article where you created them.

Notes (0)
Bookmarks (0)

You have no saved items from this article

Project items include:
  • Saved book/article
  • Highlights
  • Quotes/citations
  • Notes
  • Bookmarks
Notes
Cite this article

Cited article

Style
Citations are available only to our active members.
Buy instant access to cite pages or passages in MLA, APA and Chicago citation styles.

(Einhorn, 1992, p. 25)

(Einhorn 25)

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

Cited article

Preference Handling in Combinatorial Domains: From AI to Social Choice
Settings

Settings

Typeface
Text size Smaller Larger Reset View mode
Search within

Search within this article

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

Why can't I print more than one page at a time?

Help
Full screen

matching results for page

    Questia reader help

    How to highlight and cite specific passages

    1. Click or tap the first word you want to select.
    2. Click or tap the last word you want to select, and you’ll see everything in between get selected.
    3. You’ll then get a menu of options like creating a highlight or a citation from that passage of text.

    OK, got it!

    Cited passage

    Style
    Citations are available only to our active members.
    Buy instant access to cite pages or passages in MLA, APA and Chicago citation styles.

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn, 1992, p. 25).

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn 25)

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences."1

    1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

    Cited passage

    Thanks for trying Questia!

    Please continue trying out our research tools, but please note, full functionality is available only to our active members.

    Your work will be lost once you leave this Web page.

    Buy instant access to save your work.

    Already a member? Log in now.

    Oops!

    An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.