Residential College | false |
Status | 已發表Published |
Multi-agent Online Scheduling: MMS Allocations for Indivisible Items | |
Shengwei Zhou; Rufan Bai; Xiaowei Wu | |
2023-07 | |
Conference Name | 40th International Conference on Machine Learning (ICML 2023) |
Conference Date | July 23rd - July 29th, 2023 |
Conference Place | Honolulu, Hawaii USA |
Publisher | ML 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 ID | 2-s2.0-85174400913 |
Citation statistics | |
Document Type | Conference paper |
Collection | THE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU) |
Corresponding Author | Xiaowei Wu |
Affiliation | IOTSC, University of Macau |
First Author Affilication | University of Macau |
Corresponding Author Affilication | University 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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment