betaFeedback

WorksComputer Science

On the Complexity of Envy Cycle Elimination

Abstract

The envy cycle elimination (ECE) algorithm is a fundamental algorithm for the fair allocation of indivisible goods, guaranteeing an allocation that is envy-free up to one good under arbitrary monotone utilities. We show that the ECE algorithm can be implemented in O(nm)O(nm) time for nn agents and mm goods, and establish the tightness of this bound.

Paper details

vlnc:W_aqtvnvnq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra (bare)

View statement
Looking for related papers…