Introduction
Matching problems are fundamental to modern resource allocation, appearing in contexts ranging from school choice and committee selection to digital advertising and product recommendations. Traditionally, matching algorithms focus on maximizing the total number of assignments. However, in many real-world scenarios, the quality of a matching is also defined by its adherence to group-fairness or diversity requirements. For instance, a university committee must represent diverse departments, or an advertising platform must ensure a balanced distribution of content types.
This paper investigates online matching problems where items (available offline) are assigned to platforms (arriving online) under complex group constraints. We focus on two primary models: Proportional Fairness and Diverse Matching, providing both theoretical guarantees and empirical validation for our proposed algorithms.
Problem Formulations
We consider a bipartite setting where a set of items is known in advance, and platforms arrive sequentially. Each item belongs to one or more groups based on its attributes. When a platform arrives, the system must decide immediately which items to assign to it, or whether to leave it unmatched.
1. Proportional Fairness
In this model, each platform requires a set of items where the fraction of items from each group falls within specified lower and upper bounds. For example, a platform might require that at least 20% but no more than 30% of its assigned items belong to a specific category. The objective is to maximize the total number of items assigned across all platforms.
2. Diverse Matching
In the diversity model, platforms specify absolute lower bounds for each group. A platform is considered "matched" only if it receives a set of items that satisfies all its minimum requirements (e.g., at least two experts from AI and two from Ethics). The goal here is to maximize the total number of platforms that are successfully matched.
Methodology: The Hypergraph Connection
The core technical innovation of this work is the reduction of these constrained matching problems to Hypergraph Matching. In a standard graph, an edge connects two vertices. In a hypergraph, a "hyperedge" can connect an arbitrary subset of vertices.
We observe that a set of items satisfying a platform's constraints can be treated as a single hyperedge. This mapping allows us to leverage hypergraph theory to address the complexities of group constraints.
Algorithm Design
- Greedy Strategy: Given that finding an optimal matching in hypergraphs is NP-hard, we employ a greedy approach. When a platform arrives, the algorithm searches for a valid set of available items (a hyperedge) that satisfies the constraints and assigns them immediately.
- Constraint Relaxation: For proportional fairness, achieving a competitive approximation ratio is mathematically impossible without some flexibility. We developed an algorithm that allows for a minor additive violation of the fairness bounds, which enables high efficiency and provable performance ratios.
Theoretical Results
Our analysis establishes the following bounds, where $\ell$ represents the maximum number of items a platform can receive:
- Approximation Ratios: We achieve a competitive ratio of $(\ell + 1)$ for the Diverse Matching problem and a $2(\ell + 1)$-approximation for Proportional Fairness (with minor constraint relaxation).
- Hardness of Approximation: We prove that these problems are NP-hard to approximate within a factor of $O(\ell / \ln \ell)$. This suggests that our algorithms are near-optimal, as their performance closely matches the theoretical lower bounds.
Experimental Evaluation
We evaluated our algorithms using both synthetic and real-world datasets:
- Real-World Data: We used anonymized course allocation data from the Indian Institute of Technology (IIT) Madras, involving approximately 3,000 students and 100 courses with specific enrollment constraints.
- Synthetic Data: We generated large-scale Erdős-Rényi random graphs (10,000 items and 250 platforms) to test scalability and performance under varying match densities.
Key Findings
- Practical Efficiency: In practice, the greedy algorithms significantly outperformed their theoretical worst-case bounds. On the IIT Madras datasets, the solutions were within 10-15% of the absolute optimum calculated via Integer Linear Programming (ILP).
- Scalability: Our algorithms are substantially faster than standard ILP solvers, particularly as the number of available options per platform increases, making them suitable for high-velocity online environments.
Conclusion and Future Work
By bridging the gap between diversity constraints and hypergraph theory, this research provides a robust framework for fair online allocation. While our proportional fairness model requires a small degree of constraint relaxation, it offers a practical path forward for complex matching scenarios. Future research will explore whether polynomial-time algorithms can achieve similar approximation ratios without any constraint violations and extend these models to weighted matching scenarios where different assignments carry different values.
Summary updated