Cargando…

How hard is it to tell which is a Condorcet committee?()

This paper establishes the computational complexity status for a problem of deciding on the quality of a committee. Starting with individual preferences over alternatives, we analyse when it can be determined efficiently if a given committee [Formula: see text] satisfies a weak (resp. strong) Condor...

Descripción completa

Detalles Bibliográficos
Autor principal: Darmann, Andreas
Formato: Online Artículo Texto
Lenguaje:English
Publicado: North-Holland 2013
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4376023/
https://www.ncbi.nlm.nih.gov/pubmed/25843993
http://dx.doi.org/10.1016/j.mathsocsci.2013.06.004
Descripción
Sumario:This paper establishes the computational complexity status for a problem of deciding on the quality of a committee. Starting with individual preferences over alternatives, we analyse when it can be determined efficiently if a given committee [Formula: see text] satisfies a weak (resp. strong) Condorcet criterion–i.e., if [Formula: see text] is at least as good as (resp. better than) every other committee in a pairwise majority comparison. Scoring functions used in classic voting rules are adapted for these comparisons. In particular, we draw the sharp separation line between computationally tractable and intractable instances with respect to different voting rules. Finally, we show that deciding if there exists a committee which satisfies the weak (resp. strong) Condorcet criterion is computationally hard.