# Online Task Assignment Problems with Reusable Resources

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 15 Mar 2022.

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

- [Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms During High-Demand Hours](https://mlsanity.com/paper/1912.08388/) (2019)
- [Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources](https://mlsanity.com/paper/1711.08345/) (2017)
- [Online Stochastic Matching: New Algorithms and Bounds](https://mlsanity.com/paper/1606.06395/) (2016)
- [Algorithms for Hiring and Outsourcing in the Online Labor Market](https://mlsanity.com/paper/2002.07618/) (2020)
- [Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources](https://mlsanity.com/paper/2002.02430/) (2020)
- [Online Assignment of Heterogeneous Tasks in Crowdsourcing Markets](https://mlsanity.com/paper/1508.03593/) (2015)
- [Competitive Ratios for Online Multi-capacity Ridesharing](https://mlsanity.com/paper/2009.07925/) (2020)

## Built on by (most cited first, 1 of 1)

- [Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources](https://mlsanity.com/paper/2610.19038/) (2026)

## Abstract (arXiv)

We study online task assignment problem with reusable resources, motivated by practical applications such as ridesharing, crowdsourcing and job hiring. In the problem, we are given a set of offline vertices (agents), and, at each time, an online vertex (task) arrives randomly according to a known time-dependent distribution. Upon arrival, we assign the task to agents immediately and irrevocably. The goal of the problem is to maximize the expected total profit produced by completed tasks. The key features of our problem are (1) an agent is reusable, i.e., an agent comes back to the market after completing the assigned task, (2) an agent may reject the assigned task to stay the market, and (3) a task may accommodate multiple agents. The setting generalizes that of existing work in which an online task is assigned to one agent under (1). In this paper, we propose an online algorithm that is 1/2-competitive for the above setting, which is tight. Moreover, when each agent can reject assigned tasks at most Delta times, the algorithm is shown to have the competitive ratio Delta/(3Delta-1)≥ 1/3. We also evaluate our proposed algorithm with numerical experiments.