What question did this study set out to answer?

This work explores the impact of non-additive functions on discrepancy theory and fair division.

January 25, 20260 citationsOpen Access

Discrepancy Beyond Additive Functions with Applications to Fair Division (Extended Abstract)

AHAlexandros HollenderOracle (United States)PMPasin Manurangsi RMRaghu MekaUniversity of California, Los Angeles

Key Points

This work explores the impact of non-additive functions on discrepancy theory and fair division.
Consider a ground set of elements and real-valued set functions.
Analyze partitions into two sets to minimize the difference between function values.
Derive upper bounds for the discrepancy without assuming additivity.
Establish that the upper bound remains at most O(√{n log n}) without additivity.
Demonstrate the existence of a consensus halving for n agents with monotone utilities, refining previous O(n) bounds.

Abstract

We consider a setting where we have a ground set ℳ together with real-valued set functions f₁, …, fₙ, and the goal is to partition ℳ into two sets S₁, S₂ such that |fᵢ (S₁) - fᵢ (S₂) | is small for every i. Many results in discrepancy theory can be stated in this form with the functions fᵢ being additive. In this work, we initiate the study of the unstructured case where fᵢ is not assumed to be additive. We show that even without the additivity assumption, the upper bound remains at most O (√n log n). Our result has implications on the fair allocation of indivisible goods. In particular, we show that a consensus halving up to O (√n log n) goods always exists for n agents with monotone utilities. Previously, only an O (n) bound was known for this setting.

问 AI

Bookmark

View Full Paper