Parametric maximum flow methods for minimax approximation of target quotas in biproportional apportionment
Authors:
Abstract
In this article, we study the biproportional apportionment problem, which deals with the assignment of seats to parties within regions. We consider the minimization of both the maximum absolute error and the maximum relative error of the apportioned seats with respect to target quotas. We show that this can be done polynomially through a reduction to a parametric maximum flow problem. Moreover, the maximum absolute error can be minimized in strongly polynomial time. More generally, our method can be used for computing $\ell_{\infty}$ projections onto a flow polytope. We also address the issue of uniqueness of the solution, proposing a method based on finding unordered lexicographic minima. Our procedure is compared to other well‐known ones available in the literature. Finally we apply our procedures to the data of the 2008 Italian political elections, for which the procedure stated by the law produced an inconsistent assignment of seats. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012
Keywords
This publication has 20 references indexed in Scilit:
- A bi-proportional method applied to the Spanish CongressMathematical and Computer Modelling, 2008
- Divisor methods for proportional representation systems: An optimization approach to vector and matrix apportionment problemsMathematical Social Sciences, 2008
- Complexity and algorithms for convex network optimization and other nonlinear problems4OR, 2005
- Mexican electoral law: 1996 versionElectoral Studies, 1997
- Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with ApplicationsSIAM Journal on Computing, 1997
- Two-dimensional rounding for a quasi-proportional representationEuropean Journal of Political Economy, 1988
- Solving integer minimum cost flows with separable convex cost objective polynomially1986
- A polynomial algorithm for minimum quadratic cost flow problemsEuropean Journal of Operational Research, 1984
- On the structure of all minimum cuts in a network and applications1980
- A theorem on flows in networksPacific Journal of Mathematics, 1957