Research map / Learning theory and algorithms / Submodular and game algorithms
MATWA: A Web Toolkit for Matching Under Preferences
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Presents MATWA, a web application and REST API offering over 40 algorithms for matching under preferences problem classes (SM, HA, CHA, HR, SR, SPA) with instance upload/random generation, visualisations, and exports, plus a usability study.
Problem
Researchers, students and practitioners lack an accessible, comprehensive tool to run, compare, and visualise matching-under-preferences algorithms on uploaded or random instances, since most algorithms lack public implementations and existing web tools cover few problem classes or algorithms.
Approach
A web-based toolkit consolidating over 40 matching-under-preferences algorithms across six problem classes, with uploadable and randomly generated instances, statistics, visualisations (rotation posets, Hasse diagrams, switching graphs), exportable results, and an open REST API.
Key results
- Usability study with 15 participants: most Likert items had median 'Strongly Agree', with means from 4.40 to 5.00 (instance upload 5.00, easy navigation 4.93).
- MATWA offers 41 algorithms across CHA, HR, SR, SM and SPA, versus at most 6 algorithms in the compared web tools (per the paper's comparison table).
- Research use case on over 10,000 random SPA/SPA-S instances showed average student cost near 1.8 for student-optimal stable vs 1.4 for student-profile-optimal matchings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use stable matching algorithms instead of student-profile optimal algorithms | SPA matching algorithms · Randomly generated SPA instances | average student cost: 1.4 -> 1.8 | Hurt |
| Increase project popularity skewness | SPA instance generation · Matching size as project popularity varies | matching size | Hurt |
| Increase student popularity skewness | SPA instance generation · Matching size as student popularity varies | matching size | Hurt |
Limitations
- Some algorithms (e.g., all-popular-matchings and multi-instance) have restricted availability; multi-instance analysis supports fewer algorithms.
- Runtimes are not output accurately for each algorithm.
- Usability study was conducted on an earlier version of the system with 15 participants.
Experimental setup
Metrics: Likert usability ratings (median, mean) matching size egalitarian cost computation time
Baselines: MatchU AlgMatch Python Matching package matchingproblems (Cooper) O'Malley CHA tool Morey SPA-S web app TUM matching tool Visual Matching Algorithm tool
Builds on: Gale-Shapley algorithm Tan-Hsueh algorithm Kiraly approximation
Closest papers by meaning
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.86)
- Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences (NeurIPS 2025 · similarity 0.86)
- Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity (AAAI 2025 · similarity 0.85)
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · similarity 0.85)
- Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty (NeurIPS 2024 · similarity 0.84)
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.