Size-Relaxed Committee Selection under the Chamberlin-Courant Rule

The Chamberlin-Courant (CC) family of committee selection rules aim to select a committee of size k from a set of m candidates to maximize the satisfaction of n agents. The satisfaction of an agent from a committee depends only on the rank of her favorite candidate and is determined by a satisfaction function. Unfortunately, computing an optimal committee of size k is hard in general, which has led to the development of approximation algorithms that select a committee of size k, which guarantees some fraction of the optimal satisfaction. However, there is often some flexibility in the size of the committee to be selected. In this paper, we initiate the study of size-relaxed committee selection for the family of CC rules. Our main results are polynomialtime algorithms to select committees of size at most k • O(log n), whose satisfaction is guaranteed to be at least that of the optimal committee of size k, and show that this is tight. We also provide a constant-factor approximation algorithm for a class of approval ballot based CC rules.