Towards Fairness in Online Service with k Servers and its Application on Fair Food Delivery
The k-SERVER problem is one of the most prominent problems in online algorithms with several variants and extensions. However, simplifying assumptions like instantaneous server movements and zero service time has hitherto limited its applicability to real-world problems. In this paper, we introduce a realistic generalization of k-SERVER without such assumptions - the k-FOOD problem, where requests with source-destination locations and an associated pickup time window arrive in an online fashion, and each has to be served by exactly one of the available k servers. The k-FOOD problem offers the versatility to model a variety of real-world use cases such as food delivery, ride sharing, and quick commerce. Moreover, motivated by the need for fairness in online platforms, we introduce the FAIR k-FOOD problem with the max-min objective. We establish that both k-FOOD and FAIR k-FOOD problems are strongly NP-hard and develop an optimal offline algorithm that arises naturally from a time-expanded flow network. Subsequently, we propose an online algorithm DOC4FOOD involving virtual movements of servers to the nearest request location. Experiments on a real-world food-delivery dataset, alongside synthetic datasets, establish the efficacy of the proposed algorithm against state-of-the-art fair food delivery algorithms.
Code (1)
Tasks
FairnessMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Reinforced Workload Distribution Fairness
Network load balancers are central components in data centers, that distributes workloads across multiple servers and thereby contribute to offering scalable services. However, when load balancers operate in dynamic envi…
FairnessReinforcement Learning (RL)Two-Sided Fairness in Non-Personalised Recommendations
Recommender systems are one of the most widely used services on several online platforms to suggest potential items to the end-users. These services often use different machine learning techniques for which fairness is a…
ArticlesFairnessRecommendation SystemsVocal Bursts Valence PredictionPrivate Recommender Systems: How Can Users Build Their Own Fair Recommender Systems without Log Data?
Fairness is a crucial property in recommender systems. Although some online services have adopted fairness aware systems recently, many other services have not adopted them yet. In this work, we propose methods to enable…
FairnessRecommendation SystemsGuaranteeing Accuracy and Fairness under Fluctuating User Traffic: A Bankruptcy-Inspired Re-ranking Approach
Out of sustainable and economical considerations, two-sided recommendation platforms must satisfy the needs of both users and providers. Previous studies often show that the two sides' needs show different urgency: provi…
FairnessRecommendation SystemsRe-RankingTrustworthy AI-Generative Content for Intelligent Network Service: Robustness, Security, and Fairness
AI-generated content (AIGC) models, represented by large language models (LLM), have revolutionized content creation. High-speed next-generation communication technology is an ideal platform for providing powerful AIGC n…
FairnessSentiment Analysis