• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Bounded Single-Peaked Width and Proportional Representation

Thumbnail
View/Open
paper_54.pdf (273.0Kb)
Date
2012
Dewey
Intelligence artificielle
Sujet
election problem; multi-winner; proportional representation; single-peaked
Conference name
ECAI 2012, 20th European Conference on Artificial Intelligence
Conference date
08-2012
Conference city
Montpellier
Conference country
France
Book title
ECAI 2012, 20th European Conference on Artificial Intelligence
Publisher
Ios Press
Year
2012
ISBN
978-1-61499-097-0
URI
https://basepub.dauphine.fr/handle/123456789/10476
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Cornaz, Denis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Galand, Lucie
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Spanjaard, Olivier
233 Laboratoire d'Informatique de Paris 6 [LIP6]
Type
Communication / Conférence
Item number of pages
270-275
Abstract (EN)
This paper is devoted to the proportional representation (PR) problem when the preferences are clustered single-peaked. PR is a “multi-winner” election problem, that we study in Chamberlin and Courant’s scheme [6]. We define clustered single-peakedness as a form of single-peakedness with respect to clusters of candidates, i.e. subsets of candidates that are consecutive (in arbitrary order) in the preferences of all voters. We show that the PR problem becomes polynomial when the size of the largest cluster of candidates (width) is bounded. Furthermore, we establish the polynomiality of determining the single-peaked width of a preference profile (minimum width for a partition of candidates into clusters compatible with clustered single-peakedness) when the preferences are narcissistic (i.e., every candidate is the most preferred one for some voter).

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.