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
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 changed | Where | Measured | Effect |
|---|---|---|---|
| Add special handling for items valued at least 0.5 by both agents to greedy assignment | Two-agent goods allocation · Goods, general valuations, n=2 | competitive ratio: 0.5 | Improved |
| Use irrevocable online allocation with heterogeneous valuations | Goods allocation · Goods, general valuations, n≥3 | competitive ratio: 0 | Hurt |
| Use dynamically updated thresholds for large items and greedy allocation in the remaining phase | Goods allocation · Goods, monotone instances | competitive ratio: 0.5 | Improved |
| Restrict every item value to at most α | Goods allocation · Small-good instances | competitive ratio: (1-α) | Improved |
| Greedily assign chores to the active lowest-cost agent and inactivate at 1−1/n | Chores allocation · Chores, general valuations, n≥3 | competitive ratio: (2-1/n) | Improved |
| Apply the online thresholded allocation algorithm rather than itemwise greedy assignment | Chores allocation · Chores, random arrival, small dataset | average approximation ratio: 2.33 -> 1.09 | Improved |
| Apply the online thresholded allocation algorithm rather than itemwise greedy assignment | Chores allocation · Chores, random arrival, large dataset | average approximation ratio: 7.96 -> 1.26 | Improved |
| Maintain a lower bound on each agent's MMS and assign only when the √2 bound remains feasible | Two-agent chores allocation · Chores, general valuations, n=2 | competitive ratio: \sqrt{2} | Improved |
| Use item-index-based Sesqui-Round Robin assignment | Chores allocation · Chores, monotone instances | competitive ratio: 5/3 | Improved |
| Restrict every chore cost to at most α | Chores allocation · Small-chore instances | competitive ratio: (1+α) | Improved |
| Use an α-dependent assignment threshold for two-agent small chores | Two-agent chores allocation · Small-chore instances, n=2 | competitive ratio: \sqrt{\alpha^2-4\alpha+5} +\alpha -1 | Improved |
| Use greedy assignment without active-agent inactivation | Goods allocation · Goods, monotone instances, small dataset | average approximation ratio: 0.532 vs 0.113 | Hurt |
Closest papers by meaning
- Improved Maximin Share Approximations for Chores by Bin Packing (AAAI 2025 · similarity 0.90)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.88)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.88)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.87)
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.87)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.87)
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.
