Abstract
We study the classic cake cutting problem from
a mechanism design perspective, in particular focusing on deterministic mechanisms that are strategyproof and fair. We begin by looking at mechanisms that are non-wasteful and primarily show that
for even the restricted class of piecewise constant
valuations there exists no direct-revelation mechanism that is strategyproof and even approximately
proportional. Subsequently, we remove the nonwasteful constraint and show another impossibility result stating that there is no strategyproof and
approximately proportional direct-revelation mechanism that outputs contiguous allocations, again,
for even the restricted class of piecewise constant
valuations. In addition to the above results, we
also present some negative results when considering an approximate notion of strategyproofness,
show a connection between direct-revelation mechanisms and mechanisms in the Robertson-Webb
model when agents have piecewise constant valuations, and finally also present a (minor) modification to the well-known Even-Paz algorithm that has
better incentive-compatible properties for the cases
when there are two or three agents