We investigate the query complexity of fairly allocating $m$ indivisible chores among $n$ agents with additive cost functions. We depart from the standard cardinal model and assume only comparison access: an algorithm is only allowed to ask an agent which of two bundles is less costly, and it 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(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(n^5\log m)$ comparison queries. Our main result concerns the maximin share (MMS) guarantee. We show that for any fixed number of agents $n$ and constant $\varepsilon>0$, a $\left(13/11 +\varepsilon\right)$-MMS allocation can be computed with a comparison complexity logarithmic in $m$. Remarkably, comparison access suffices to match the state-of-the-art $13/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/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)$ comparison queries.
We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound after the removal of at most one chore. Our main result establishes that every instance admits an ex-ante proportional lottery in whose support every allocation is MMS1 and all but $o(n)$ agents satisfy MMS. Consequently, every realized allocation can be made MMS by disposing of at most $o(n)$ chores. The proposed framework further achieves ex-ante proportionality alongside ex-post $4/3$-MMS, $o(n)$-AMMS, or $1$-out-of-$d$ MMS for $d=(1-o(1))n$. These guarantees substantially improve upon state-of-the-art bounds for MMS allocation for chores with disposal or subsidy, best-of-both-worlds fairness, approximate AMMS, and ordinal MMS approximations.
We study the comparison-query complexity of computing allocations that are envy-free up to one item (EF1) for $n$ agents with heterogeneous additive preferences over $m$ 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)$ query bounds for at most three agents, leaving open whether query complexity logarithmic in $m$ is achievable for every fixed $n \ge 4$. We resolve this open question in the affirmative: for every fixed $n\ge2$, we design algorithms that compute EF1 allocations using $O(\log m)$ comparison queries, matching the known $Ω(\log m)$ lower bound. Our results hold for both chores with nonnegative costs and goods with nonnegative valuations.