Dynamic Necklace Splitting
This work addresses the need for dynamic fair division algorithms, which is relevant for applications like data-informed hash maps, but the results are incremental extensions of existing static algorithms.
The paper extends the necklace splitting problem to a dynamic setting with relocation, insertion, and deletion of beads, providing linear-time optimal algorithms for two colors and restricted multi-color cases, as well as a randomized polylogarithmic-time algorithm for two colors with approximate fairness.
The necklace splitting problem is a classic problem in fair division with many applications, including data-informed fair hash maps. We extend necklace splitting to a dynamic setting, allowing for relocation, insertion, and deletion of beads. We present linear-time, optimal algorithms for the two-color case that support all dynamic updates. For more than two colors, we give linear-time, optimal algorithms for relocation subject to a restriction on the number of agents. Finally, we propose a randomized algorithm for the two-color case that handles all dynamic updates, guarantees approximate fairness with high probability, and runs in polylogarithmic time when the number of agents is small.