Towards Fairness in Online Service with K Servers and Its Application on Fair Food Delivery

Daman Deep Singh, Amit Kumar, Abhijnan ChakrabortyAAAI 2024 · DOI

Introduction

The $k$-server problem is a fundamental model in online algorithms, where $k$ mobile servers respond to requests at various locations to minimize total travel distance. While theoretically elegant, this model fails to capture the complexities of real-world gig economy services like food delivery. Real-world scenarios involve non-instantaneous travel, specific pickup and delivery points, and time-sensitive service windows. Furthermore, traditional cost-minimization objectives often lead to extreme income inequality among drivers, where a small subset of workers captures the majority of high-value orders. This paper introduces the $k$-FOOD problem, extending the $k$-server model with realistic constraints and a focus on driver fairness.

The $k$-FOOD Problem

To bridge the gap between theory and practice, the authors define the $k$-FOOD problem. Unlike the standard $k$-server model, $k$-FOOD incorporates:

  1. Travel Time: Servers are unavailable for new tasks while in transit.
  2. Source-Destination Pairs: Requests consist of a pickup location (e.g., a restaurant) and a delivery location (e.g., a customer).
  3. Service Windows: Orders must be fulfilled within specific timeframes.

The research focuses on the FAIR $k$-FOOD variant, which adopts a max-min objective inspired by Rawlsian justice. The goal is to maximize the minimum reward earned by any driver over a given horizon, ensuring a more equitable distribution of income.

Methodology

The $k$-FOOD problem and its fair variant are proven to be strongly NP-hard. To establish a performance benchmark, the researchers developed FLOWMILP, an offline optimal solution based on a time-expanded flow network.

Time-expanded flow network used for the offline FLOWMILP solution.

As shown in Figure 1, the network models server movements across discrete time steps, allowing the problem to be solved using Mixed Integer Linear Programming (MILP). A "Two-Sided" version of FLOWMILP was also introduced to allow platforms to tune the trade-off between driver fairness and total operational cost.

For real-time applications, the paper proposes DOC4FOOD (DOuble Coverage for FOOd Delivery). This online algorithm utilizes two key strategies:

  • GreedyMin Assignment: New requests are assigned to the eligible driver with the lowest accumulated reward.
  • Non-lazy Movement: Idle drivers are proactively moved toward high-demand restaurant hubs. This "virtual movement" ensures that low-earning drivers are physically positioned to receive future orders, mimicking the behavior of experienced gig workers.

Experimental Evaluation

The approach was evaluated using both synthetic datasets (SYNSPARSE and SYNDENSE) and a real-world dataset from a major Indian food delivery platform. The real-world data includes 1,050 orders and 734 drivers across three cities, capturing authentic traffic and demand patterns over an 8-hour window.

Key Results

DOC4FOOD demonstrates substantial improvements in driver fairness across all tests. In synthetic environments, the algorithm raised the rewards of the bottom 25% of earners to nearly 20% of the total net rewards, significantly outperforming standard baselines.

Lorenz curves comparing the fairness of various algorithms against the line of equality on real-world data.

Figure 6 illustrates this through Lorenz curves, where the x-axis represents the cumulative percentage of servers and the y-axis represents the cumulative percentage of total rewards. DOC4FOOD (red line) stays significantly closer to the "line of equality" (the diagonal dashed line) compared to standard baselines like Round Robin or Random assignment. On real-world data, DOC4FOOD effectively "elevated the floor," significantly reducing the number of drivers who earned zero rewards. Importantly, these fairness gains were achieved with only a marginal increase in total travel distance and no significant impact on the number of unserved requests.

Conclusion

This work provides a viable path toward fairer online service platforms by formalizing the $k$-FOOD problem and introducing the DOC4FOOD algorithm. By combining reward-aware assignment with proactive movement, the system ensures a more equitable distribution of earnings without sacrificing operational efficiency. Future work may incorporate predictive machine learning models to anticipate demand and further optimize proactive driver positioning.

Summary updated

BibTeX
@inproceedings{singh2024towards,
  author = {Daman Deep Singh and Amit Kumar and Abhijnan Chakraborty},
  title = {{Towards Fairness in Online Service with K Servers and Its Application on Fair Food Delivery}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.29969},
}
Figure