Reproduce “Logarithmic Comparison-Query Complexity for EF1 Allocations” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
The authors give a deterministic algorithm for EF1 allocation of indivisible goods or chores with heterogeneous additive preferences, using pairwise bundle comparisons. EF1 means that removing one item eliminates envy, from the envious agent’s bundle for chores and the envied bundle for goods. The algorithm uses O(n^8 log m) queries, logarithmic in m for fixed n and matching the known lower bound; this is not a runtime guarantee.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.