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 ob- jective is to match a given target distribution over these attributes. Building on the framework of Lang and Skowron [20 ], we formalize and analyze the 𝐿𝑝 class of voting rules, including the well-studied Hamilton rule representing 𝐿1. This class of voting rules repre- sents 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. Com- plementing this, we propose a conic programming relaxation that yields provable additive approximation guarantees. We then turn to analyze the effect of correlation : Correlated at- tributes may indicate possible duplicates, and are likely to skew the outcome of 𝐿𝑝 rules in a given direction. We propose a correlation- aware variant of 𝐿2 and show it satisfies desired properties.