Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences

Niclas Boehmer, Markus Brill, Ulrike Schmidt-Kraepelin

TL;DR

This paper introduces "matching elections," a new framework for selecting multiple fair matchings between agents based on their approval preferences. By leveraging the specific structure of matching problems, they achieve computational tractability for certain voting rules and establish stronger fairness guarantees than previously possible in general multiwinner elections.

What Problem Does This Paper Address?

Imagine a scenario where you need to form multiple pairs of agents for various tasks – think of teachers pairing students for group projects, or companies forming project teams. Traditional matching algorithms often focus on finding a single "best" matching, but what if fairness requires selecting multiple matchings? This paper tackles the challenge of selecting a set of $k$ matchings that proportionally represent the preferences of all agents. The core difficulty lies in the sheer number of possible matchings, which grows exponentially, making standard computational approaches for fair selection infeasible. The authors aim to bridge the gap between matching theory and social choice theory by applying multiwinner voting concepts to this matching problem.

Methods

The paper frames the problem as a "matching election," a specific type of "party-approval election." In this setting, each possible matching is treated as a "candidate," and agents "approve" matchings based on whether they are paired with someone they like.

Key methodological contributions include:

  • Embedding Matching Elections into Party-Approval Elections: They show how to formally translate a matching problem into a standard multiwinner election framework, allowing the application of existing voting rules and fairness axioms.
  • Exploiting Structure for Tractability: The authors demonstrate that the specific structure of matching preferences (e.g., symmetry, bipartiteness) can be exploited to make computationally intractable problems (like finding a winner under certain rules) tractable. This involves reducing complex problems to solving the "Weighted Approval Winner" problem, which they show can be solved efficiently for matching elections using maximum weight matching algorithms.
  • Algorithmic Analysis of Voting Rules: They analyze the computational complexity of several established multiwinner voting rules (e.g., Thiele rules, Phragmén's sequential rule, Rule X) in the context of matching elections, proving both positive (polynomial-time solvable) and negative (NP-hard) results.
  • Axiomatic Analysis of Fairness: The paper investigates fairness properties like Proportional Justified Representation (PJR) and Extended Justified Representation (EJR). They show that certain rules, which might not be fair in general settings, can achieve stronger fairness guarantees in symmetric matching elections.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Structure is Key: The most significant insight is that the inherent structure of matching problems, which is often overlooked in general multiwinner election settings, can be leveraged to overcome computational hurdles and achieve stronger fairness guarantees.
  • Symmetry Pays Off: Symmetric matching elections (where approvals are mutual) offer a particularly rich structure that allows for enhanced fairness properties (like EJR for sequential Thiele rules) and computational tractability for rules that are otherwise hard.
  • Bridging Two Worlds: The paper successfully bridges the gap between matching theory and computational social choice, showing how concepts from one field can illuminate and solve problems in the other.
  • New Complexity Landscape: The paper reveals that while some problems are easier in matching elections than in general party-approval elections (e.g., checking EJR), others become harder (e.g., checking PJR is coNP-complete, a contrast to general party-approval elections).

Key Results

  • Sequential Rules are Tractable: Sequential voting rules (like sequential Thiele rules, sequential Phragmén, and Rule X) can be computed in polynomial time for matching elections, even with an exponential number of candidates. This is achieved by reducing the problem to solving the Weighted Approval Winner problem.
  • Non-Sequential Thiele Rules: For general matching elections, computing winners for non-sequential Thiele rules (including Proportional Approval Voting - PAV) is NP-hard, even for a small number of agents and matchings.
  • Bipartite and Symmetric Elections Offer Efficiency: In bipartite and symmetric matching elections, non-sequential Thiele rules become computationally tractable.
  • Stronger Fairness in Symmetric Settings: Sequential Thiele rules satisfy Extended Justified Representation (EJR) in symmetric matching elections, a guarantee not met in general party-approval elections.
  • Complexity of Axiom Checking: Checking EJR is polynomial-time solvable, while checking PJR is coNP-complete, and checking core stability is coNP-hard for matching elections.

Limitations and Future Work

  • General Matching Elections: While strong results are shown for symmetric and bipartite matching elections, the axiomatic guarantees for general matching elections remain less impressive. The paper poses open questions about whether seq-w-Thiele satisfies any axioms in general or bipartite settings, and whether seq-Phragmén satisfies EJR in bipartite settings.
  • Ordinal Preferences: The current work focuses on dichotomous (approval) preferences. Future work could explore ordinal preferences (rankings) for matching partners.
  • Sequential Matchings: The paper considers selecting a multiset of matchings. An interesting extension is to select a sequence of matchings, which is relevant for applications where matchings are implemented over time. This could involve developing rules that consider the recency of representation.
  • New Axioms: The authors suggest exploring axioms specifically tailored to the structure of matching, such as deviations where groups of agents match among themselves.

Summary updated

BibTeX
@article{boehmer2025proportional,
  author = {Niclas Boehmer and Markus Brill and Ulrike Schmidt-Kraepelin},
  title = {{Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences}},
  journal = {Soc. Choice Welf.},
  year = {2025},
  doi = {10.1007/s00355-023-01453-7},
}
Figure