MATWA: A Web Toolkit for Matching Under Preferences

Frederik Glitzner, David F. ManloveAAAI 2025 · DOI

Abstract

Matching Algorithm Toolkit Web Application (MATWA) is a comprehensive, open-access web toolkit that centralizes over 40 algorithms for matching problems under preferences. While matching theory has flourished for over 60 years, many sophisticated algorithms lack accessible implementations. MATWA addresses this gap by providing a unified interface for executing, visualizing, and comparing complex matching mechanisms, such as those used in hospital-resident assignments and school choice. This paper details the system's architecture, its support for diverse problem classes, and its unique visualization capabilities that facilitate deeper structural analysis of matching markets.

Introduction

Matching markets are fundamental to modern society, governing everything from the National Resident Matching Program to kidney exchanges. These markets rely on "ordinal preferences," where agents rank options to achieve stable or optimal assignments. Despite the theoretical maturity of the field, researchers and educators often struggle with fragmented codebases and a lack of standardized tools for algorithmic comparison.

MATWA was developed to bridge this divide. It serves as a centralized repository and execution environment for matching algorithms, allowing users to move beyond simple output lists to a more nuanced understanding of algorithmic behavior and market structures.

Methodology and System Features

MATWA is designed to support five major problem classes:

  • Hospitals/Residents (HR): Many-to-one matching.
  • Stable Marriage (SM): One-to-one bipartite matching.
  • Capacitated House Allocation (CHA): Item-to-person assignment.
  • Stable Roommates (SR): Non-bipartite matching.
  • Student-Project Allocation (SPA): Multi-level matching involving students, projects, and lecturers.

The toolkit includes over 40 algorithms, ranging from standard Gale-Shapley variants to rare implementations like the Tan and Hsueh algorithm for stable partitions. Users can input data through manual entry, file uploads, or a robust random generator capable of simulating complex scenarios with up to 14 customizable parameters, such as tie probabilities and preference list lengths.

Visualization and Structural Analysis

A core innovation of MATWA is its emphasis on the structural properties of matchings. Rather than just identifying a single stable matching, the toolkit explores the relationship between all possible valid matchings within an instance.

The MATWA interface displaying a Hasse Diagram of stable matchings.

As shown in Figure 1, MATWA generates interactive Hasse diagrams to represent the lattice of stable matchings. This allows researchers to visualize the "poset" (partially ordered set) of rotations and understand the trade-offs between different solutions. Additionally, the system calculates fairness metrics—including profiles, regret levels, and egalitarian costs—to provide a multi-dimensional view of algorithmic performance.

Empirical Utility and Results

MATWA has already proven its value as a research catalyst. In a 2023 study, the toolkit was used to evaluate five different algorithms for the Student-Project Allocation problem, revealing how project popularity skewness impacts overall matching size. User studies have further confirmed that the platform is intuitive for both novice learners and expert researchers, facilitating large-scale empirical studies that were previously labor-intensive.

Limitations and Future Directions

While MATWA is currently the most extensive collection of its kind, future development will focus on multi-instance batch processing to allow for broader comparative studies. The authors also plan to integrate evolving specialized algorithms and optimize visualization components for larger-scale industrial datasets.

Summary updated

BibTeX
@inproceedings{glitzner2025matwa,
  author = {Frederik Glitzner and David F. Manlove},
  title = {{MATWA: A Web Toolkit for Matching Under Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i28.35352},
}
Figure