Multi-Attribute Committee Selection: Diversity, Correlation, and Approximation Guarantees

Abstract:
We study the problem of multi-attribute committee selection, where each candidate is described by categorical attributes and the objective is to match a given target distribution over these attributes. Building on the framework of Lang and Skowron, we formalize and analyze the Lp class of voting rules, including the well-studied Hamilton rule representing L1. This class of voting rules represents trade-offs between treating all attribute deviations equally and minimizing the maximal deviation. We prove strong approximation hardness for this class, showing that even modest approximation guarantees are impossible when the number of attributes grows relative to the committee size. Complementing this, we propose a conic programming relaxation that yields provable additive approximation guarantees. We then turn to analyze the effect of correlation: Correlated attributes may indicate possible duplicates, and are likely to skew the outcome of Lp rules in a given direction. We propose a correlation-aware variant of L2 and show it satisfies desired properties.

This lecture is part of the Playtime Seminar