• 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

Conference Program Design with Single-Peaked and Single-Crossing Preferences

Thumbnail
Date
2016
Dewey
Intelligence artificielle
Sujet
choix social computationnel
DOI
http://dx.doi.org/10.1007/978-3-662-54110-4_16
Conference name
12th International Conference, WINE 2016
Conference date
12-2016
Conference city
Montreal
Conference country
Canada
Book title
Web and Internet Economics
Author
Cai, Yang; Vetta, Adrian
Publisher
Springer
Publisher city
Berlin Heidelberg
Year
2016
Pages number
482
ISBN
978-3-662-54109-8
Book URL
10.1007/978-3-662-54110-4
URI
https://basepub.dauphine.fr/handle/123456789/16132
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Fotakis, Dimitris
245158 School of Electrical and Computer Engineering, National Technical University of Athens [ICCS]
Gourvès, Laurent
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
221-235
Abstract (EN)
We consider the Conference Program Design (CPD) problem, a multi-round generalization of (the maximization versions of) q-Facility Location and the Chamberlin-Courant multi-winner election, introduced by (Caragiannis, Gourvès and Monnot, IJCAI 2016). CPD asks for the selection of kq items and their assignment to k disjoint sets of size q each. The agents receive utility only from their best item in each set and we want to maximize the total utility derived by all agents from all sets. Given that CPD is NP-hard for general utilities, we focus on utility functions that are either single-peaked or single-crossing. For general single-peaked utilities, we show that CPD is solvable in polynomial time and that Percentile Mechanisms are truthful. If the agent utilities are given by distances in the unit interval, we show that a Percentile Mechanism achieves an approximation ratio 1 / 3, if q=1, and at least (2q−3)/(2q−1), for any q≥2. On the negative side, we show that a generalization of CPD, where some items must be assigned to specific sets in the solution, is NP-hard for dichotomous single-peaked preferences. For single-crossing preferences, we present a dynamic programming exact algorithm that runs in polynomial time if k is constant.

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