Multi-agent Online Scheduling: MMS Allocations for Indivisible Items
Jul 24, 2023
Speakers
Shengwei Zhou
Speaker · 0 followers
Xiaowei Wu
Speaker · 0 followers
About
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 the allocation of goods and chores separately and propose algorithms for approximating maximin share (MMS) allocations for both settings. 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.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 the allocation of goods and chores separately and propose algorithms for approximating maximin share (MMS) allocations for both settings. When agents have identical valuation functions the problem coincides with the semi-online machine covering problem (when items are goods) and load balancing proble…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Multi-User Reinforcement Learning with Low Rank Rewards
Watch later
The Blessing of Heterogeneity in Federated Q-learning: Linear Speedup and Beyond
Watch later
Jiin Woo, …
Poster spotlight #2
Watch later
Peter Müller, …
