Research map / Learning theory and algorithms / Submodular and game algorithms
Plant-and-Steal: Truthful Fair Allocations via Predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes the Plant-and-Steal framework for truthful, learning-augmented approximate MMS allocation of indivisible goods, using ordering predictions for two agents and extending to n agents.
Problem
Truthful approximation of the maximin share (MMS) for indivisible goods with additive valuations, where known truthful mechanisms have only trivial ratios (about m/2 for two agents) and predictions are used to bridge the gap.
Approach
Plant-and-Steal: compute an initial allocation from predictions, plant each agent's favorite item (per prediction) in the other's bundle, then let agents steal back one item according to their true reports; truthfulness follows because report-dependent choice is only among planted sets fixed by predictions.
Key results
- Two-agent B-RR-Plant-and-Steal is truthful, 2-consistent and ceil(m/2)-robust, matching the known truthful lower bound up to rounding.
- 1-2-RR-Plant-and-Steal achieves 3/2-consistency with floor(2m/3)-robustness.
- With Kendall tau distance d between prediction and valuations, the round-robin variant gives a (2*sqrt(d)+6)-approximation to MMS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use only predictions, without the stealing component (ablation) | Plant-and-Steal · Synthetic two-player instances with accurate predictions | MMS allocation quality | No clear effect |
| add the stealing component to prediction-based allocation (ablation) | Plant-and-Steal · Synthetic two-player instances with noisy predictions | robustness | Helped |
| combine prediction-based allocation with the stealing component | Plant-and-Steal · Synthetic two-player instances | MMS allocation quality | Helped |
Surprising findings
- No truthful mechanism with bounded robustness can achieve consistency below 6/5 for two agents with arbitrary predictions.
- Under ordering predictions, consistency better than 5/4 is impossible even with unbounded robustness.
Limitations
- Consistency-robustness tradeoff for n>2 agents is relaxed to MMS for ceil(3n/2) agents in robustness.
- Robustness for two-agent ordering predictions remains linear in m for the constant-consistency mechanisms.
Experimental setup
Datasets: synthetic valuations (High-Med-Low multi-step distribution, m=100)
Benchmarks: synthetic two-agent instances with m=100 items
Metrics: MMS approximation ratio Kendall tau distance sensitivity
Baselines: Balanced-Round-Robin 1-2-Round-Robin Water-Filling
Builds on: Round-Robin allocation water-filling Cut-and-choose Amanatidis et al. truthful MMS lower bounds
Closest papers by meaning
- Truthful and Fair Mechanisms for Matroid-Rank Valuations (AAAI 2022 · similarity 0.91)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.90)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.89)
- Epistemic Pairwise Maximin Share (NeurIPS 2026 · similarity 0.88)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.88)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.88)
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.