Query complexity limits fairness in dividing good and bad resources

The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources

Computer Science and Game Theory

Summary

Fairly dividing things that people like (cake) and dislike (chores) is tricky, especially when both are mixed together. The authors studied how many questions you need to ask to guarantee a perfectly fair split without envy. They showed it can be done for just cake or chores with a certain number of steps, but when mixing positive and negative parts, no simple method exists with a predictable number of questions. This means splitting mixed resources fairly requires more complex approaches and possibly infinite effort.

What this means in practice

  • For resource allocators: Design fair division methods for allocating chores or positive tasks based on expected query complexity bounds.
  • For automation engineers: Avoid using fixed-expected-query algorithms for fair division of mixed positive and negative resources due to theoretical limits.

A theory result. No direct application yet.

Authors

Alireza Farhadi, Mohammadtaghi Hajiaghayi

Abstract

We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using $2^{3n\log_2 n+O(n)}$ queries and cuts. For both cake and chores, a Las Vegas protocol uses $O(n^{21}\log^2(2n))$ expected queries and $O(n^{20}\log^2(2n))$ expected cuts. Conversely, every exact protocol with fixed positive success probability requires $Ω(n^2)$ expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.