AI Paper Atlas

Research map / Multi-agent systems and games / Games and equilibria

Multi-agent Online Scheduling: MMS Allocations for Indivisible Items

Shengwei Zhou, Rufan Bai, Xiaowei Wu

ICML 2023 · Multi-agent systems and games › Games and equilibria · approach: Fair division and coalition formation · 0 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Add special handling for items valued at least 0.5 by both agents to greedy assignmentTwo-agent goods allocation · Goods, general valuations, n=2competitive ratio: 0.5Improved
Use irrevocable online allocation with heterogeneous valuationsGoods allocation · Goods, general valuations, n≥3competitive ratio: 0Hurt
Use dynamically updated thresholds for large items and greedy allocation in the remaining phaseGoods allocation · Goods, monotone instancescompetitive ratio: 0.5Improved
Restrict every item value to at most αGoods allocation · Small-good instancescompetitive ratio: (1-α)Improved
Greedily assign chores to the active lowest-cost agent and inactivate at 1−1/nChores allocation · Chores, general valuations, n≥3competitive ratio: (2-1/n)Improved
Apply the online thresholded allocation algorithm rather than itemwise greedy assignmentChores allocation · Chores, random arrival, small datasetaverage approximation ratio: 2.33 -> 1.09Improved
Apply the online thresholded allocation algorithm rather than itemwise greedy assignmentChores allocation · Chores, random arrival, large datasetaverage approximation ratio: 7.96 -> 1.26Improved
Maintain a lower bound on each agent's MMS and assign only when the √2 bound remains feasibleTwo-agent chores allocation · Chores, general valuations, n=2competitive ratio: \sqrt{2}Improved
Use item-index-based Sesqui-Round Robin assignmentChores allocation · Chores, monotone instancescompetitive ratio: 5/3Improved
Restrict every chore cost to at most αChores allocation · Small-chore instancescompetitive ratio: (1+α)Improved
Use an α-dependent assignment threshold for two-agent small choresTwo-agent chores allocation · Small-chore instances, n=2competitive ratio: \sqrt{\alpha^2-4\alpha+5} +\alpha -1Improved
Use greedy assignment without active-agent inactivationGoods allocation · Goods, monotone instances, small datasetaverage approximation ratio: 0.532 vs 0.113Hurt

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy