betaFeedback

WorksComputer Science

Comparison-Based Fair Division of Indivisible Chores

Abstract

We investigate the query complexity of fairly allocating mm indivisible chores among nn agents with additive cost functions. We depart from the standard cardinal model and assume only comparison access: an algorithm may ask an agent which of two bundles is less costly, but never observes numerical costs. Our first results concern proportionality up to one item (PROP1). We design comparison-based algorithms that compute PROP1 allocations using O(n3log⁡m)O(n^3\log m) comparison queries. When the chores are arranged in a fixed order and allocations are required to be contiguous, we compute a contiguous PROP1 allocation using O(n3log⁡2m)O(n^3 \log^2 m) comparison queries. Our main result concerns the maximin share (MMS) guarantee. We show that for any fixed number of agents nn and constant ε>0\varepsilon>0, a (13/11+ε)\left(13/11 +\varepsilon\right)-MMS allocation can be computed with a comparison complexity logarithmic in mm. Remarkably, comparison access suffices to match the state-of-the-art 13/1113/11 cardinal-access guarantee of Huang and Segal-Halevi up to an arbitrarily small loss. Furthermore, our result implies that the MMS distortion of comparison access (i.e., the worst-case multiplicative loss in MMS fairness incurred by observing only comparisons rather than numerical costs) is at most 13/1113/11. Finally, we show that, for three agents, an allocation satisfying envy-freeness up to one item (EF1) can be computed using O(log⁡m)O(\log m) comparison queries.

Paper details

vlnc:W_xqtrufbc
Version
v1 · latest
Published
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

Not recorded for this paper

View statement
Looking for related papers…