Refine
Document Type
- Preprint (1)
- Working Paper (1)
Language
- English (2) (remove)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- dynamic programming (2) (remove)
Institute
- Informatik (1)
- Wirtschaftswissenschaften (1)
Integer point sets minimizing average pairwise L1 distance: What is the optimal shape of a town?
(2010)
An n-town, n[is an element of]N , is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings along the axis-parallel street grid, then an n-town has optimal shape if the sum of all pairwise Manhattan distances is minimized. This problem has been studied for cities, i.e., the limiting case of very large n. For cities, it is known that the optimal shape can be described by a differential equation, for which no closed-form solution is known. We show that optimal n-towns can be computed in O(n[superscript 7.5]) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.
This paper relates recursive utility in continuous time to its discrete-time origins and provides a rigorous and intuitive alternative to a heuristic approach presented in [Duffie, Epstein 1992], who formally define recursive utility in continuous time via backward stochastic differential equations (stochastic differential utility). Furthermore, we show that the notion of Gâteaux differentiability of certainty equivalents used in their paper has to be replaced by a different concept. Our approach allows us to address the important issue of normalization of aggregators in non-Brownian settings. We show that normalization is always feasible if the certainty equivalent of the aggregator is of expected utility type. Conversely, we prove that in general L´evy frameworks this is essentially also necessary, i.e. aggregators that are not of expected utility type cannot be normalized in general. Besides, for these settings we clarify the relationship of our approach to stochastic differential utility and, finally, establish dynamic programming results. JEL Classifications: D81, D91, C61