Network flow methods for electoral systems

Researchers in the field of electoral systems have recently turned their attention to network flow techniques, with the intention to resolve certain practically relevant problems of contemporary electoral systems. Here we review some of this work, with a focus on ``biproportional apportionment'' and on the ``give-up'' problems. In the biproportional apportionment problem, the whole electoral region is subdivided into several electoral districts. The input data consists of a matrix of the vote counts a party receives in a district. The task is to convert the vote matrix into a (integer) seat matrix, maintaining proportionality ``as much as possible''. Moreover each district must be allocated its pre-specified number of seats, and each party must receive the number of seats it is entitled to on the basis of the aggregate, national vote counts. The give-up problem arises in the current electoral law for the Italian Parliament. For each region each party submits a blocked, ordered lists of candidates. Candidates may run on more than one list (that is, in more than one region), and many of them do in order to advertise their national standing. Candidates winning a seat in more than one region must give-up all of them but one. In the give-up problem one has to find a schedule of give-ups, for all lists of a party, that results in a globally best, in some sense, choice of deputies for that party.