Envy-Free and Truthful Cake-Cuttings Based on Parametric Flows (New Trends in Algorithms and Theory of Computation)

Abstract

For the cake-cutting problem, Alijani, et al. [2, 30] and Asano and Umeda [3, 4] gave envy-free and truthful mechanisms with a small number of cuts, where the desired part of each player's valuation function is a single interval on the given cake. In this paper, based on parametric flows, we give efficient envy-free and truthful mechanisms with a small number of cuts, which are much simpler than those proposed by Alijani, et al. [2, 30] and Asano and Umeda [3, 4]. Furthermore, we show that this approach can be applied to the envy-free and truthful mechanism proposed by Chen, et al. [16], where the valuation function of each player is piecewise uniform. Thus, we can obtain an envy-free and truthful mechanism with a small number of cuts, even if the valuation function of each player is piecewise uniform.