An Envy-free and Truthful Mechanism for the Cake-cutting Problem (New Trends in Algorithms and Theory of Computation)

Abstract

Alijani, Farhadi, Ghodsi, Seddighin, and Tajik considered a restricted version of the cake-cutting problem and proposed a mechanism based on the expansion process with unlocking [1, 6]. They claimed that their mechanism uses a small number of cuts, and that it is envy-free and truthful. We first show that it is not actually envy-free and truthful. Then, for the same cake-cutting problem, we give a new envy-free and truthful mechanism with a small number of cuts, which is not based on their expansion process with unlocking.