Abstract
We study truthful mechanisms in the context of cake cutting when agents not only value their own pieces of cake but also care for the pieces assigned to other agents. In particular, agents derive benefits or costs from the pieces of cake assigned to other agents. This phenomenon is often referred to as positive or negative externalities. We propose and study the following model: given an allocation, externalities of agents are modeled as percentages of the reported values that other agents have for their pieces. We show that even in this restricted class of externalities, under some natural assumptions, no truthful cake cutting mechanisms exist when externalities are either positive or negative. However, when the percentages agents get from each other are small, we show that there exists a truthful cake cutting mechanism with other desired properties.
Introduction
The "cake cutting" problem is a foundational challenge in mathematical economics and game theory: how can a heterogeneous resource (the "cake") be divided among $n$ agents such that the allocation is fair? Traditionally, this problem assumes agents are entirely self-interested, valuing only the specific slice they receive. However, in real-world applications—such as revenue-sharing contracts, market competition, or international resource management—agents often experience externalities.
A positive externality occurs when an agent benefits from another’s success (e.g., a supplier benefiting from a retailer's high sales). Conversely, a negative externality occurs when one agent’s gain is perceived as another’s loss (e.g., competitors vying for the same market share). This paper investigates whether it is possible to design truthful mechanisms—where no agent has an incentive to lie about their preferences—when these external values are factored into their utility.
Modeling Externalities
The authors model externalities as a percentage ($\alpha_{i,j}$) of the value that agent $j$ receives, which is then added to (or subtracted from) agent $i$’s total utility. The study focuses on piecewise uniform valuation functions, a standard model where an agent either values a specific segment of the cake at a constant rate or has no interest in it at all.
To test the limits of truthfulness, the researchers analyze an existing algorithm known as Mechanism 1 (originally proposed by Chen et al. in 2013). This mechanism operates by:
- Identifying a subset of agents whose desired cake sections have the smallest average length.
- Providing those agents with an "exact allocation" in their preferred intervals.
- Recursively repeating the process for the remaining agents and cake.
The Spite Barrier and Impossibility Results
The research establishes that externalities significantly complicate the pursuit of truthfulness. The authors present two primary "impossibility results":
- The Spite Barrier: Negative externalities are found to be fundamentally disruptive. If agents are even slightly "spiteful" (deriving negative value from others' pieces), the authors prove that no mechanism can be simultaneously truthful, non-wasteful, and position-independent.
- The $1/n$ Threshold: For positive externalities, if agents care "too much" about others (specifically if the benefit they derive from others is greater than $1/n$), truthfulness collapses. In these cases, an agent might lie about their own preferences to ensure a neighbor receives a "better" piece, as the resulting positive externality boosts their own total utility more than their own slice would.
Possibility and Robustness
Despite these challenges, the paper offers a significant "possibility result." The authors demonstrate that Mechanism 1—which was originally designed for a world without externalities—is surprisingly resilient.
As long as the positive externalities are kept within a specific mathematical limit ($\alpha_{i,j} \le 1/n^2$), the mechanism remains perfectly truthful, proportional, and "swap envy-free" (meaning no two agents would want to trade their slices and their associated externalities). This suggests that existing fair-division algorithms can be robust against minor external influences, provided the agents do not "care for others too much."
Conclusion and Future Work
This research clarifies the boundaries of fair division in the presence of externalities. While negative externalities and high levels of altruism make truthful division impossible under current models, small positive externalities are manageable.
The study leaves open a mathematical "gray area": while truthfulness is guaranteed for $\alpha \le 1/n^2$ and impossible for $\alpha > 1/n$, the behavior of the system in the gap between these two values remains unknown. Additionally, the authors suggest that randomized mechanisms might eventually provide a way to bypass the impossibility results identified for deterministic mechanisms in this paper.
Summary updated