Research map / Learning theory and algorithms / Submodular and game algorithms
Optimizing the Envy Cycle Elimination Algorithm
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.
Studies heuristics for choosing the good and unenvied agent in envy cycle elimination (ECE) for EF1 allocations, proving strong utilitarian and egalitarian price bounds for each heuristic and running average-case experiments.
Problem
Vanilla envy cycle elimination yields EF1 allocations, but the choice of good and receiving agent in each round can lead to very different welfare; the worst-case welfare loss of arbitrary ECE allocations (strong price) is large.
Approach
Define greedy ECE heuristics that choose the agent, the good, or both (maximizing utility) and a max-min matching heuristic for the first n rounds, then analyze their strong utilitarian and egalitarian prices against the vanilla ECE baseline.
Key results
- Heuristic choosing agent and good with max utility in the first round only gives strong utilitarian price 8/3 for n=2 and n+sqrt(n/2) approximately for n>=3, versus n^2 for vanilla ECE.
- Max-min matching heuristic improves strong egalitarian price from infinity to m-n+1.
- Experiments show the agent-and-good max-utility heuristic performs best on average in utilitarian and egalitarian welfare for most tested n and m.
Surprising findings
- Heuristics choosing only the agent or only the good do not improve worst-case prices over vanilla ECE.
- For n=2 the every-round agent-and-good heuristic has finite strong egalitarian price (at most 3), while the first-round-only version is infinite.
Limitations
- Strong egalitarian price remains infinite for n>=3 for all greedy heuristics.
- Under subadditive utilities some upper bounds fail; under monotone utilities ECE weak prices are infinite.
- Average-case gains from first-round-only heuristics diminish as the number of goods grows.
Experimental setup
Datasets: Spliddit instances
Benchmarks: Spliddit instances
Metrics: strong utilitarian price strong egalitarian price average utilitarian price average egalitarian price
Baselines: vanilla ECE algorithm round-robin algorithm
Builds on: envy cycle elimination round-robin algorithm price of fairness
Closest papers by meaning
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.91)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.90)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.90)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.90)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.90)
- EF2X Exists for Four Agents (AAAI 2025 · similarity 0.90)
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.