Candidate Selections with Proportional Fairness Constraints

摘要: Selecting a subset of candidates with various attributes under fairness constraints has been attracting considerable attention from the AI community, applications ranging school admissions to committee selections. The are usually captured by absolute upper bounds and/or lower on number selected in specific attributes. In many scenarios, however, total is not predetermined. It is, therefore, more natural express these terms proportions final selection size. this paper, we study proportional candidate problem, where goal select maximum cardinality while meeting certain constraints. We first analyze computational complexity problem and show strong inapproximability results. Next, investigate algorithmic aspects two directions. First, treating as soft constraints, devise polynomial-time algorithms that could return (near) optimal solutions bounded violations each constraint. Second, design an exact algorithm fast running time practice. Simulations based both synthetic publicly available data confirm effectiveness efficiency our proposed algorithms.