Proportional representation in matching markets: selecting multiple matchings under dichotomous preferences
研究在代理人有二分偏好时，如何选出k个匹配来公平代表所有人的偏好。通过将问题建模为多赢家选举，利用偏好结构设计高效算法，并证明比例批准投票在对称偏好下可多项式时间计算且满足强公平性保证。
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. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the classical approval-based multiwinner setting: Assuming that approvals are symmetric, we show that Proportional Approval Voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and that its sequential variant, which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our algorithmic results extend to other types of compactly representable elections with an exponential candidate space.