In this paper 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 $\ellnorm_\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.

Parametric maximum flow methods for minimax approximation of target quotas in biproportional apportionment

SERAFINI, Paolo;
2012-01-01

Abstract

In this paper 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 $\ellnorm_\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.
File in questo prodotto:
File Dimensione Formato  
DOI=10.1002-net.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 192.42 kB
Formato Adobe PDF
192.42 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/867542
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 10
social impact