Proportional representation in matching markets: selecting multiple matchings under dichotomous preferences

Abstract

Given a set of agents with approval preferences over each other, we study the task of finding k matchings fairly representing everyone’s preferences. To formalize fairness, we apply the concept of proportional representation as studied in approval-based multiwinner elections. To this end, we model the problem as a multiwinner election where the set of candidates consists of matchings of the agents, and agents’ preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmén) are rendered inefficient.