Research map / Learning theory and algorithms / Fairness
Towards Fairness in Online Service with K Servers and Its Application on Fair Food Delivery
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the k-FOOD problem (k-server with travel time, service time and pickup windows) and its max-min fair variant, proves strong NP-hardness, gives a time-expanded-flow MILP offline optimum, and proposes the online Doc4Food heuristic evaluated on synthetic and Indian food-delivery data.
Problem
Online assignment of servers (delivery drivers) to source-destination requests with pickup time windows, where server travel takes time and fairness is measured by maximizing the minimum reward any server earns.
Approach
Generalizes k-server/k-taxi/k-serverTW to account for non-instantaneous movement and service time, adds a max-min fairness objective, solves the offline version via a time-expanded flow MILP, and proposes Doc4Food, a GreedyMin-based online rule with virtual non-lazy server movements toward likely request locations (inspired by Double Coverage).
Key results
- On the food-delivery subset, Doc4Food achieves a minimum reward of 2381 versus 2319 for GreedyMin and 786 for Random among purely online methods, with 7 unserved requests.
- On SynSparse, Doc4Food attains min reward 1186 with 5 unserved, compared with GreedyMin 1065 and Random 723; FlowMILP achieves equal rewards for all servers (2444.50) as the offline fractional optimum.
- The offline semi-online FoodMatch and FairFoody baselines and FlowMILP are reported; Doc4Food is claimed to achieve the highest minimum reward among purely online algorithms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add virtual non-lazy movements toward the nearest restaurant locations | GreedyMin to form Doc4Food · SynSparse | #Unserved: 10 -> 5 | Helped |
| Add virtual non-lazy movements toward the nearest restaurant locations | GreedyMin to form Doc4Food · SynDense | #Unserved: 8 -> 7 | Helped |
| Add virtual non-lazy movements toward the nearest restaurant locations | GreedyMin to form Doc4Food · Food-delivery dataset (FlowMILP comparison) | Min.R: 2319 -> 2381 | Helped |
| Add virtual non-lazy movements toward the nearest restaurant locations | GreedyMin to form Doc4Food · Food-delivery dataset (FlowMILP comparison) | #Unserved: 11 -> 7 | Helped |
| Add the two-sided cost constraint (ablation) | FlowMILP · SynSparse | Cost: 2444.50 -> 1399.56 | Helped |
| Add the two-sided cost constraint (ablation) | FlowMILP · SynDense | Cost: 7137.44 -> 1282.93 | Helped |
| Add the two-sided cost constraint (ablation) | FlowMILP · Food-delivery dataset (FlowMILP comparison) | Cost: 19049.20 -> 8505.19 | Helped |
| Add the two-sided cost constraint (ablation) | FlowMILP · SynSparse | Min.R: 2444.50 -> 1399.56 | Hurt |
| Add the two-sided cost constraint (ablation) | FlowMILP · SynDense | Min.R: 7137.44 -> 1282.93 | Hurt |
| Add the two-sided cost constraint (ablation) | FlowMILP · Food-delivery dataset (FlowMILP comparison) | Min.R: 19049.20 -> 8505.19 | Hurt |
Surprising findings
- MinDelta, a fairness-driven online method, yields zero-reward servers (32 servers with zero reward on the food dataset) despite minimizing cost, showing cost-efficiency and fairness can conflict.
- RoundRobin serves few requests well but leaves servers with zero reward, illustrating that feasibility-focused online methods fare poorly on min-reward fairness.
Limitations
- The FlowMILP offline optimum is only solvable for moderate instances (largest 8-hour subset), and full 24-hour scaling needs re-optimization techniques.
- Doc4Food is a heuristic without a competitive-ratio guarantee.
- The real dataset is not released publicly, limiting reproducibility of food-delivery experiments.
Experimental setup
Datasets: Real Indian food-delivery dataset (3 cities, 6 days; obtained from authors of prior work) SynSparse (synthetic, 500 nodes, 250 requests) SynDense (synthetic, 500 nodes, 250 requests)
Benchmarks: SynSparse SynDense Indian food-delivery dataset (8-hour subset, 1034 orders, 650 drivers)
Metrics: number of unserved requests cost (average server reward / platform cost) minimum server reward (max-min objective) Lorenz curves
Baselines: Random GreedyMin MinDelta RoundRobin FoodMatch FairFoody Work4Food
Builds on: k-server k-taxi k-serverTW Double Coverage min-cost flow LP formulation for k-server
Closest papers by meaning
- Time Fairness in Online Knapsack Problems (ICLR 2024 · similarity 0.84)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.81)
- Fast & Fair: A Collaborative Platform for Fair Division Applications (AAAI 2024 · similarity 0.81)
- Interpolating Item and User Fairness in Multi-Sided Recommendations (NeurIPS 2024 · similarity 0.80)
- Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (AAAI 2024 · similarity 0.79)
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.78)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.