Cycle Cancellation for Submodular Fractional Allocations and Applications

Chandra Chekuri, Pooja Kulkarni, Ruta Mehta, Jan VondrákarXiv 2025 · DOI · arXiv

Introduction

The fair allocation of indivisible goods is a fundamental problem in computational social choice and algorithmic game theory. While the case of additive valuations—where an agent's total value is simply the sum of individual item values—is well-understood, real-world scenarios often involve submodular valuations. Submodularity captures the principle of diminishing marginal utility: the more items an agent already possesses, the less they value an additional item. This paper introduces a novel "cycle-canceling" lemma for submodular functions, providing a unified framework for rounding fractional allocations into discrete ones while maintaining strong fairness guarantees.

The Submodular Allocation Problem

In a typical fair division problem, $m$ items must be distributed among $n$ agents. Each agent $i$ has a valuation function $v_i(S)$ for any subset of items $S \subseteq \{1, \dots, m\}$. When $v_i$ is submodular, traditional rounding techniques used for additive functions often fail. Researchers typically approach these problems by first finding an optimal fractional allocation $x$ (where $x_{ij} \in [0, 1]$ represents the fraction of item $j$ assigned to agent $i$) and then rounding it to an integral allocation. The challenge lies in rounding without significantly degrading the "fairness" of the outcome, measured by metrics such as Nash Social Welfare (NSW), Maximin-share (MMS), or the Max-min (Santa Claus) objective.

Technical Contribution: The Cycle-Canceling Lemma

The core innovation of this work is the generalization of the cycle-canceling lemma to the submodular setting via the multilinear extension $F(x)$. The multilinear extension is a continuous relaxation of a discrete set function, representing the expected value of a set where each item $j$ is included independently with probability $x_j$.

The authors prove that for any submodular function, the multilinear extension is convex along directions that shift fractions of items between agents (specifically, directions of the form $e_{i,j} - e_{i',j}$). This property allows for the NonUniformPipageRounding algorithm:

  1. Cycle Cancellation: If the bipartite graph of the fractional allocation contains a cycle, the algorithm shifts values along the cycle. Due to the proven convexity, there always exists a direction that ensures no agent's expected value (under the multilinear extension) decreases.
  2. Forest Reduction: This process is repeated until the allocation graph becomes a forest. In a forest structure, each agent is connected to at most one fractional item.
  3. Final Rounding: By rooting the trees in the forest and assigning each fractional item to its parent agent, the algorithm produces an integral allocation where each agent loses at most the value of a single item compared to their fractional starting point.

Applications and Approximation Results

The cycle-canceling lemma serves as a "plug-and-play" tool, yielding state-of-the-art or simplified results for several classic fairness objectives.

Comparison of approximation ratios achieved in this paper versus prior work and lower bounds across various fairness notions.

As shown in the table above, the paper achieves several notable results:

  • Nash Social Welfare (NSW): For general submodular valuations, the authors provide a simple $1/5$-approximation algorithm. While more complex methods exist, this approach is significantly more intuitive and easier to implement.
  • Maximin-share (MMS): The paper derives a $\approx 0.316$ ($1/2(1-1/e)$) approximation for general submodular valuations.
  • Max-min (Santa Claus): In settings where items are "small" relative to the total value (specifically $v_i(j) \leq \epsilon \text{OPT}$), the algorithm achieves a $(1 - 1/e - \epsilon)$ approximation.
  • Constant Number of Agents: For a fixed number of agents $n$, the framework provides a $(1 - 1/e - \epsilon)$ approximation for both NSW and Max-min objectives more efficiently than prior specialized techniques.

Conclusion and Future Directions

By bridging the gap between additive and submodular rounding through the lens of multilinear extensions and convexity, this work provides a powerful new tool for fair division. The primary limitation remains the "one-item loss" inherent in rounding a forest to an integer allocation, which bounds the approximation ratios when items are large. Future research may explore combining cycle-canceling with local search techniques to further close the gap between these new upper bounds and known NP-hardness lower bounds, particularly for the Nash Social Welfare objective.

Summary updated

Abstract

We consider discrete allocation problem where $m$ indivisible goods are to be divided among $n$ agents. When agents' valuations are additive, the well-known cycle cancelling lemma by Lenstra, Shmoys, and Tardos plays a key role in design and analysis of rounding algorithms. In this paper, we prove an analogous lemma for the case of submodular valuations. Our algorithm removes cycles in the support graph of a fractional allocation while guaranteeing that each agent's value, measured using the multilinear extension, does not decrease. We demonstrate applications of the cycle-canceling algorithm, along with other ideas, to obtain new algorithms and results for three well-studied allocation objectives: max-min (Santa Claus problem), Nash social welfare (NSW), and maximin-share (MMS). For the submodular NSW problem, we obtain a $\frac{1}{5}$-approximation; for the MMS problem, we obtain a $\frac{1}{2}(1-1/e)$-approximation through new simple algorithms. For various special cases where the goods are "small" valued or the number of agents is constant, we obtain tight/best-known approximation algorithms. All our results are in the value-oracle model.
BibTeX
@misc{chekuri2025cycle,
  author = {Chandra Chekuri and Pooja Kulkarni and Ruta Mehta and Jan Vondrák},
  title = {{Cycle Cancellation for Submodular Fractional Allocations and Applications}},
  year = {2025},
  eprint = {2511.21099},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.21099},
}
Figure