文摘
We consider a geographic optimization problem in which we are given a region R, a probability density function f(⋅) defined on R, and a collection of n utility density functions ui(⋅) defined on R. Our objective is to divide R into n sub-regions Ri so as to “balance” the overall utilities on the regions, which are given by the integrals \(\iint _{R_{i}}f(x)u_{i}(x)\, dA\). Using a simple complementary slackness argument, we show that (depending on what we mean precisely by “balancing” the utility functions) the boundary curves between optimal sub-regions are level curves of either the difference function ui(x) − uj(x) or the ratio ui(x)/uj(x). This allows us to solve the problem of optimally partitioning the region efficiently by reducing it to a low-dimensional convex optimization problem. This result generalizes, and gives very short and constructive proofs of, several existing results in the literature on equitable partitioning for particular forms of f(⋅) and ui(⋅). We next give two economic applications of our results in which we show how to compute a market-clearing price vector in an aggregate demand system or a variation of the classical Fisher exchange market. Finally, we consider a dynamic problem in which the density function f(⋅) varies over time (simulating population migration or transport of a resource, for example) and derive a set of partial differential equations that describe the evolution of the optimal sub-regions over time. Numerical simulations for both static and dynamic problems confirm that such partitioning problems become tractable when using our methods.KeywordsShadow pricesOptimizationComputational geometryMarket clearing pricesDistrictingVoronoi diagramsPower diagrams
