Matchings Under Diversity Constraints

Govind S. Sankar, Anand Louis, Meghana Nasre, Prajakta Nimbhorkar

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:

  1. 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.
  2. 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

Abstract

Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. Moreover, online matching problems have lots of applications in ad allocations and other e-commerce problems like product recommendation in digital marketing. We study two problems involving assigning {\em items} to {\em platforms}, where items belong to various {\em groups} depending on their attributes; the set of items are available offline and the platforms arrive online. In the first problem, we study online matchings with {\em proportional fairness constraints}. Here, each platform on arrival should either be assigned a set of items in which the fraction of items from each group is within specified bounds or be assigned no items; the goal is to assign items to platforms in order to maximize the number of items assigned to platforms. In the second problem, we study online matchings with {\em diversity constraints}, i.e. for each platform, absolute lower bounds are specified for each group. Each platform on arrival should either be assigned a set of items that satisfy these bounds or be assigned no items; the goal is to maximize the set of platforms that get matched. We study approximation algorithms and hardness results for these problems. The technical core of our proofs is a new connection between these problems and the problem of matchings in hypergraphs. Our experimental evaluation shows the performance of our algorithms on real-world and synthetic datasets exceeds our theoretical guarantees.
BibTeX
@inproceedings{sankar2023matchings,
  author = {Govind S. Sankar and Anand Louis and Meghana Nasre and Prajakta Nimbhorkar},
  title = {{Matchings Under Diversity Constraints}},
  booktitle = {ECAI},
  year = {2023},
  url = {https://openreview.net/forum?id=Pf2CPqSBsU},
}
Figure