A Cryptographic Moving-Knife Cake-Cutting Protocol
This enables fair cake-cutting in real-world asynchronous settings, though it is an incremental improvement by adapting a known protocol to new network constraints.
The paper tackles the problem of fairly dividing a heterogeneous good (cake) among players on asynchronous networks like the Internet, where existing synchronous protocols fail, and achieves this with a discrete protocol using secure auctions that requires only n-1 cuts, the minimum possible.
This paper proposes a cake-cutting protocol using cryptography when the cake is a heterogeneous good that is represented by an interval on a real line. Although the Dubins-Spanier moving-knife protocol with one knife achieves simple fairness, all players must execute the protocol synchronously. Thus, the protocol cannot be executed on asynchronous networks such as the Internet. We show that the moving-knife protocol can be executed asynchronously by a discrete protocol using a secure auction protocol. The number of cuts is n-1 where n is the number of players, which is the minimum.