  Given a set of agents with approval preferences over each other, we study the
task of finding $k$ matchings fairly representing everyone's preferences. We
model the problem as an approval-based multiwinner election where the set of
candidates consists of all possible matchings 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\'en) 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 general 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 its sequential variant (seq-PAV), which does not provide any
proportionality guarantees in general, fulfills a rather strong guarantee known
as extended justified representation. Some of our positive computational
results extend to other types of compactly representable elections with an
exponential candidate space.

Computer Science and Game Theory;Theoretical Economics