---
title: "Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion"
authors:
  - "Edith Elkind"
  - "Jérôme Lang"
  - "Abdallah Saffidine"
doi: "10.5591/978-1-57735-516-8/IJCAI11-042"
url: "https://ijcai.org/proceedings/2011/42"
pdf: "https://ijcai.org/proceedings/2011/0042.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "186-190"
track: ""
keywords:
---

# Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion

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

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 186-190. DOI: [10.5591/978-1-57735-516-8/IJCAI11-042](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.