Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion

Elkind, Edith; Lang, Jérôme; Saffidine, Abdallah

doi:10.5591/978-1-57735-516-8/IJCAI11-042

Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion

Edith Elkind, Jérôme Lang, Abdallah Saffidine

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 186-190.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-042

Abstract

In elections, an alternative is said to be a Condorcet winner if it is preferred to any other alternative by a majority of voters. While this is a very attractive solution concept, many elections do not have a Condorcet winner. In this paper, we propose a setvalued relaxation of this concept, which we call a Condorcet winning set: such sets consist of alternatives that collectively dominate any other alternative. We also consider a more general version of this concept, where instead of domination by a majority of voters we require domination by a given fraction theta of voters; we refer to this concept as theta-winning set. We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically.

Edith Elkind, Jérôme Lang, and Abdallah Saffidine. 2011. Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 186–190. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-042

@inproceedings{ijcai2011p42,
  title     = {Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion},
  author    = {Elkind, Edith and Lang, Jérôme and Saffidine, Abdallah},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {186--190},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-042},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-042},
}

TY  - CPAPER
TI  - Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion
AU  - Elkind, Edith
AU  - Lang, Jérôme
AU  - Saffidine, Abdallah
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 186
EP  - 190
DO  - 10.5591/978-1-57735-516-8/IJCAI11-042
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-042
ER  -