Allocation of Indivisible Items with Connected Bundles

Suppose a collection of indivisible goods are arranged in a line, and we wish to allocate these items to agents so that each agent receives a connected bundle (an interval). This makes sense when the items have a spatial or temporal structure, for example when allocating time slots, and agents are interested in receiving a contiguous chunk of time. We study the computation of Pareto-optimal (PO) allocations with connected bundles, and find some surprising hardness results. We further study the existence of allocations that are envy-free up to one good (EF1). We show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Please note that the seminar will take place on Friday (not Thursday, as usual) at 12.15.