Optimal Interval Division

This paper develops a theory of optimal interval division for capacity-constrained problems in which a continuum is divided into finitely many intervals, or classes, and choices are class-targeted. Examples include the location of public facilities by a social planner, the distribution of product characteristics by firms, coarse matching, bounded memory, and mechanism design with limited communication.Optimal interval division refers to the problem of finding the interval partition of a given continuum maximizing an associated value, constrained by the number of classes. The value of each finite interval partition is derived by summation from a basic primitive that I call a cell function defined over all subintervals. I identify an important and common property of cell functions: they are submodular over the interval structure. This yields the following results.First, the maximum value exhibits decreasing marginal returns in the number of classes, and converges rapidly with an additional simple condition. Second, I uncover a novel sandwiching property: when allowing an extra class, the new optimal cut- offs are more spread compared with the original optimal ones in the sense that each new cut point lands in a different original partition element. This property helps elucidate the effects of various capacity constraints on economic behavior. Third, by a characterization theorem, I show that a submodular optimal interval division problem can often be interpreted as scalar quantization in information theory with a general error function, despite arising from seemingly unrelated contexts like coarse matching