Residential Collegefalse
Status已發表Published
Multi-agent Online Scheduling: MMS Allocations for Indivisible Items
Shengwei Zhou; Rufan Bai; Xiaowei Wu
2023-07
Conference Name40th International Conference on Machine Learning (ICML 2023)
Conference DateJuly 23rd - July 29th, 2023
Conference PlaceHonolulu, Hawaii USA
PublisherML Research Press
Abstract

We consider the problem of fairly allocating a sequence of indivisible items that arrive online in an arbitrary order to a group of n agents with additive normalized valuation functions. We consider both the allocation of goods and chores, and propose algorithms for approximating maximin share (MMS) allocations. When agents have identical valuation functions the problem coincides with the semi-online machine covering problem (when items are goods) and load balancing problem (when items are chores), for both of which optimal competitive ratios have been achieved. In this paper we consider the case when agents have general additive valuation functions. For the allocation of goods we show that no competitive algorithm exists even when there are only three agents and propose an optimal 0.5-competitive algorithm for the case of two agents. For the allocation of chores we propose a (2 − 1/n)-competitive algorithm for n ≥ 3 agents and a √ 2 ≈ 1.414-competitive algorithm for two agents. Additionally, we show that no algorithm can do better than 15/11 ≈ 1.364-competitive for two agents.

Language英語English
Scopus ID2-s2.0-85174400913
Citation statistics
Document TypeConference paper
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorXiaowei Wu
AffiliationIOTSC, University of Macau
First Author AffilicationUniversity of Macau
Corresponding Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Shengwei Zhou,Rufan Bai,Xiaowei Wu. Multi-agent Online Scheduling: MMS Allocations for Indivisible Items[C]:ML Research Press, 2023.
APA Shengwei Zhou., Rufan Bai., & Xiaowei Wu (2023). Multi-agent Online Scheduling: MMS Allocations for Indivisible Items. .
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Shengwei Zhou]'s Articles
[Rufan Bai]'s Articles
[Xiaowei Wu]'s Articles
Baidu academic
Similar articles in Baidu academic
[Shengwei Zhou]'s Articles
[Rufan Bai]'s Articles
[Xiaowei Wu]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Shengwei Zhou]'s Articles
[Rufan Bai]'s Articles
[Xiaowei Wu]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.