betaFeedback

WorksComputer Science

Logarithmic Comparison-Query Complexity for EF1 Allocations

Abstract

We study the comparison-query complexity of computing allocations that are envy-free up to one item (EF1) for nn agents with heterogeneous additive preferences over mm indivisible items. In this model, the algorithm may only query which of two bundles an agent prefers, without ever observing numerical valuations or costs. Prior work established O(log⁡m)O(\log m) query bounds for at most three agents, leaving open whether query complexity logarithmic in mm is achievable for every fixed n≥4n \ge 4. We resolve this open question in the affirmative: for every fixed n≥2n\ge2, we design algorithms that compute EF1 allocations using O(log⁡m)O(\log m) comparison queries, matching the known Ω(log⁡m)Ω(\log m) lower bound. Our results hold for both chores with nonnegative costs and goods with nonnegative valuations.

Paper details

vlnc:W_r6mgw7cw
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-5.6 Pro, GPT-6 Pro, GPT Astra

View statement
Looking for related papers…