Redividing the Cake

Erel Segal-HaleviIJCAI 2018 · DOI

TL;DR

This paper tackles the problem of re-dividing an already-allocated resource (like land or cloud computing time) among agents. It introduces protocols that balance two competing goals: ensuring each agent gets a minimum share of the total resource (proportionality) while also guaranteeing they retain a significant portion of their original allocation (ownership). The authors show that these goals can be simultaneously achieved under certain conditions, even with geometric constraints like pieces needing to be contiguous intervals or rectangles.

What Problem Does This Paper Address?

Imagine a scenario where a valuable resource, like a plot of land or computing power, has already been divided among several users. This initial division might be unfair or outdated, and a new division is needed. This "re-division" problem is common in areas like land reform, spectrum allocation, or managing cloud computing resources where new users join or existing ones need adjustments.

The core challenge is to create a new division that satisfies two potentially conflicting principles:

  1. Proportionality: Each agent should receive a fair share of the entire resource, typically defined as at least $1/n$ of the total value (where $n$ is the number of agents).
  2. Ownership: Agents who previously held a portion of the resource should be allowed to keep a substantial fraction of its value. This is crucial for practical reasons, like incentivizing existing stakeholders or respecting prior investments.

The paper investigates how to achieve both proportionality and ownership simultaneously, especially when geometric constraints are imposed on the shape of the allocated pieces.

Methods

The paper presents several re-division protocols, each tailored to different geometric constraints on the resource and the allocated pieces. The core idea is to leverage existing cake-cutting algorithms (like the Even-Paz protocol for interval division) and adapt them to the re-division context.

Key methodological elements include:

  • Defining New Fairness Notions:
    • $r$-Proportionality: Each agent receives at least $r/n$ of the total cake value.
  • $w$-Ownership: Each agent receives at least $w$ times the value of its original allocation.
  • Democratic Ownership: A relaxed version of ownership, stating that for any $k$, at least $n-k$ agents receive at least $1/\lceil n/k \rceil$ of their original value. This is inspired by scenarios where a majority's support is sufficient.
  • Protocol Design: The protocols often involve a two-step process:
  • Allocation Completion: Extending the initial, potentially incomplete, division to cover the entire resource. This step is particularly tricky when geometric constraints (like rectangularity) prevent simple merging of unallocated "blanks."
    1. Re-division: Applying a modified fair division algorithm to the completed allocation, ensuring both proportionality and ownership. For instance, a "helper agent" strategy is used to satisfy democratic ownership.
  • Handling Geometric Constraints: The paper extends results from 1D (intervals) to 2D (rectangles and convex polygons), requiring specialized geometric algorithms for the allocation completion step.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Trade-off Between Proportionality and Ownership: The paper establishes a fundamental limit: if the sum of the desired proportionality fraction ($r$) and ownership fraction ($w$) exceeds 1 ($r+w > 1$), it's impossible to guarantee both simultaneously. However, if $r+w \le 1$, it is possible. This provides a clear boundary for what can be achieved.
  • Geometric Constraints Matter: While basic proportionality and ownership can be achieved without geometric constraints, adding requirements like pieces being contiguous intervals or rectangles significantly complicates the problem. In some cases, these constraints make it impossible to achieve strong proportionality and ownership simultaneously (Proposition 3).
  • Democratic Ownership as a Practical Alternative: When strict ownership is too restrictive, "democratic ownership" offers a viable compromise, ensuring a large majority of agents retain a significant portion of their original stake.
  • The "Helper Agent" Trick: A clever algorithmic technique involves creating a "helper agent" for each original agent. This allows the protocol to satisfy democratic ownership by giving agents a choice between their original piece (or a part of it) and a piece allocated to their helper, ensuring a minimum value from either.
  • The Challenge of "Blanks": In 2D divisions with geometric constraints, the initial allocation might leave unallocated "blank" regions. Extending these blanks without violating the geometric shape constraints (e.g., rectangles must remain rectangles) is a non-trivial geometric problem that requires specific algorithms.

Key Results

  • Theorem 2: For any rational $r, w$ such that $r+w \le 1$, it's possible to find a re-division that simultaneously satisfies $r$-proportionality and $w$-ownership. This can be done with $O(n^2)$ queries. For example, $r=w=1/2$ is achievable.
  • Proposition 3: For 1D interval division with contiguous interval pieces, simultaneous $r$-proportionality and $w$-ownership is impossible if $r > 0$ and $w > 0$ and geometric constraints are present.
  • Theorem 4: For 1D interval division with contiguous interval pieces, democratic ownership and $1/3$-proportionality can be simultaneously achieved in $O(n^2 \log n)$ time.
  • Theorem 5: For 2D rectangular division with rectangular pieces, democratic ownership and $1/4$-proportionality can be achieved.
  • Theorem 6: For 2D convex division with convex pieces, democratic ownership and $1/5$-proportionality can be achieved.

Limitations and Future Work

  • Computational Complexity of Geometric Steps: While Theorems 5 and 6 guarantee the existence of such divisions, the paper notes that finding the "maximal extension" for convex pieces (Theorem 6) is a computationally challenging problem left for future work.
  • Improving Proportionality Constants: The paper's protocols achieve $1/3$, $1/4$, or $1/5$-proportionality. There's a conjecture that these constants could be improved (e.g., to $1/2$ for the 1D case) if agents could strategically choose between their normal and helper agents.
  • Handling More Complex Geometric Constraints: The paper discusses future work on convexity in higher dimensions and connectivity in 2D, noting that current algorithms don't fully address these.
  • Two Pieces per Agent: The current results assume agents receive a single piece. The paper poses an open question about what happens if agents can receive up to two pieces.
  • Envy-Freeness: The paper focuses on proportionality. Future work could explore the compatibility of envy-freeness with ownership.

Summary updated

BibTeX
@inproceedings{segalhalevi2018redividing,
  author = {Erel Segal-Halevi},
  title = {{Redividing the Cake}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/69},
}
Figure