Fairness and Efficiency in Online Class Matching
Authors: MohammadTaghi Hajiaghayi, Shayan Jahan, Mohammad Sharifi, Suho Shin, Max Springer
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The online bipartite matching problem, extensively studied in the literature, deals with the allocation of online arriving vertices (items) to a predetermined set of offline vertices (agents). However, little attention has been given to the concept of class fairness, where agents are categorized into different classes, and the matching algorithm must ensure equitable distribution across these classes. We here focus on randomized algorithms for the fair matching of indivisible items, subject to various definitions of fairness. Our main contribution is the first (randomized) non-wasteful algorithm that simultaneously achieves a 1/2 approximation to class envy-freeness (CEF) while simultaneously ensuring an equivalent approximation to the class proportionality (CPROP) and utilitarian social welfare (USW) objectives. We supplement this result by demonstrating that no non-wasteful algorithm can achieve an α-CEF guarantee for α > 0.761. In a similar vein, we provide a novel input instance for deterministic divisible matching that demonstrates a nearly tight CEF approximation. Lastly, we define the price of fairness, which represents the trade-off between optimal and fair matching. We demonstrate that increasing the level of fairness in the approximation of the solution leads to a decrease in the objective of maximizing USW, following an inverse proportionality relationship. |
| Researcher Affiliation | Academia | Mohammad Taghi Hajiaghayi University of Maryland Shayan Chashm Jahan University of Maryland Mohammad Sharifi Sharif University of Technology Suho Shin University of Maryland Max Springer University of Maryland |
| Pseudocode | Yes | Algorithm 1 RANDOM |
| Open Source Code | No | The paper does not contain an explicit statement about providing open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on algorithms, proofs, and problem instances. It does not use or provide access to real-world datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets; therefore, it does not specify training, validation, or test splits. |
| Hardware Specification | No | The paper is theoretical and does not report on empirical experiments; therefore, it does not specify any hardware used. |
| Software Dependencies | No | The paper is theoretical and does not report on empirical experiments; therefore, it does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not report on empirical experiments; therefore, it does not provide details about an experimental setup, such as hyperparameters or system-level training settings. |