# Design a Win-Win Strategy That Is Fair to Both Service Providers and Tasks When Rejection Is Not an Option

arXiv: https://arxiv.org/abs/2407.00032 · HTML: https://mlsanity.com/paper/2407.00032/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 22 May 2024.

## Builds on (most cited first, 8 of 8)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms](https://mlsanity.com/paper/2002.10764/) (2020)
- [Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources](https://mlsanity.com/paper/1711.08345/) (2017)
- [Group-level Fairness Maximization in Online Bipartite Matching](https://mlsanity.com/paper/2011.13908/) (2020)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Subgroup Fairness in Two-Sided Markets](https://mlsanity.com/paper/2106.02702/) (2021)
- [Online Bipartite Matching with Reusable Resources](https://mlsanity.com/paper/2110.07084/) (2021)
- [Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction](https://mlsanity.com/paper/2203.08019/) (2022)

## Abstract (arXiv)

Assigning tasks to service providers is a frequent procedure across various applications. Often the tasks arrive dynamically while the service providers remain static. Preventing task rejection caused by service provider overload is of utmost significance. To ensure a positive experience in relevant applications for both service providers and tasks, fairness must be considered. To address the issue, we model the problem as an online matching within a bipartite graph and tackle two minimax problems: one focuses on minimizing the highest waiting time of a task, while the other aims to minimize the highest workload of a service provider. We show that the second problem can be expressed as a linear program and thus solved efficiently while maintaining a reasonable approximation to the objective of the first problem. We developed novel methods that utilize the two minimax problems. We conducted extensive simulation experiments using real data and demonstrated that our novel heuristics, based on the linear program, performed remarkably well.