Reitzig, Raphael and Wild, Sebastian
Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts
ArXiv e-prints, 2015

Segal-Halevi, Hassidim, and Aumann (AAMAS, 2015) propose the problem of cutting sticks so that at least k sticks have equal length and no other stick is longer. This allows for an envy-free allocation of sticks to k players, one each. The resulting number of sticks should also be minimal.

We analyze the structure of this problem and devise a linear-time algorithm for it.

arXiv


Erel Segal-Halevi posed the original question on Computer Science Stack Exchange. Our approach is based on observations in the answers by Abhishek Bansal, InstructedA and FrankW. Hence, even though the eventual algorithm and its presentation have been developed and refined offline with the use of a blackboard and lots of paper, the result has been the product of a small “crowd” collaboration made possible by the Stack Exchange platform.

We thank Chao Xu for pointing us towards the work by Cheng and Eppstein (which lead to another article of ours), and for providing the observation we utilize in Section 4.1.

Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts - Raphael Reitzig