Network models and biproportional rounding for fai

Authors: Kerem Akartunalı Philip A Knight

Publish Date: 2016/09/22

Volume: 253, Issue: 1, Pages: 1-19

PDF Link

Abstract

Systems for allocating seats in an election offer a number of socially and mathematically interesting problems We discuss how to model the allocation process as a network flow problem and propose a wide choice of objective functions and allocation schemes Biproportional rounding which is an instance of the network flow problem is used in some European countries with multiseat constituencies We discuss its application to single seat constituencies and the inevitable consequence that seats are allocated to candidates with little local support However we show that variants can be selected such as regional apportionment to mitigate this problem In particular we introduce a parameter based family of methods which we call balanced majority voting that can be tuned to meet the public’s demand for local and global “fairness” Using data from the 2010 to 2015 UK general elections we study a variety of network models and implementations of biproportional rounding and address conditions of existence and uniquenessThe fundamental ideal of a functioning democracy namely “one person one vote” is easy to understand but has never been perfectly met Balinski and Young 2001 There are myriad systems for electing governments in use throughout the world In particular most countries in Europe use some form of proportional representation PR as a means of allocating members to parliaments and councils at both local and national level though there are many competing arguments as to the best way to achieve a fair system Nurmi 2014 The UK is a latecomer to PR but a number of recent elections eg European Scottish have adopted it at least in part Among the systems tried are the Alternative Vote AV system for one seat constituencies and the Single Transferrable Vote STV for multiseat constituencies In both systems the voter ranks candidates in order of preference and candidates are elected once their support reaches a certain quota an absolute majority in the case of AV In STV surplus votes of the elected candidates are transferred to the remaining candidates according to second preferences and anyone pushed over the quota is then elected If noone reaches the necessary threshold the least popular candidate is eliminated and their votes are reallocated This process is iterated until all seats are filled In AV only the second reallocation stage is necessaryStill there is strong resistance to bringing it into the election for members of parliament MPs to Westminster as the 2011 referendum on AV indicates White 2011 Currently UK elections are fought on the first past the post FPTP system where the winner takes all in each constituency In a multiparty election this can skew results significantly from proportionality For example in the 2005 and 2015 general elections Labour and Conservatives each gained a majority of the seats 57 and 51  respectively with a minority share of votes 36 and 37  respectively Conversely in 2010 the Liberal Democrats received 23  of the votes but only 9  of the seats Thrasher et al 2011 and in 2015 UKIP received 13  of the votes but won just one of the 614 seats they contested The Electoral Commission 2015FPTP is also alleged to be responsible for effectively disenfranchising many voters as the demographics of some constituencies means that they almost never change hands For example Gower Normanton and Makerfield have elected Labour MPs without exception since 1906 If the result is a foregone conclusion voter turnout can be expected to be adversely affected A similar problem in Switzerland led a disgruntled voter to sue successfully providing impetus for a subsequent change in the local electoral law Balinski and Pukelsheim 2006One of the main objections to PR for the UK parliamentary elections is that it breaks the link of MPs with individual constituencies as well as being members of a party MPs have traditionally represented the interests of individual voters in the towns or districts they have been elected to Suppose that a voting area has n districts where sigma i seats are to be allocated to district i = 1ldots n and a list system typically allocates the sigma i seats proportionally to party shares in i If sigma i=1 as in the UK then this simply becomes FPTP whereas using a single transferable vote reduces to AV If we are to devise a model of PR which retains a constituency link a balance must be made between nationwide and local voting patterns In particular it should accommodate the strong support for nationalist parties in certain regions and the consistent levels of support for other smaller partiesAny electoral system implicitly attempts to solve an optimization problem given a set of votes one allocates seats to parties based on their proportionate strength at regional or national level while minimizing a particular objective function1 For some systems such as FPTP the minimization part of the problem is trivial however explicitly framing electoral systems in the language of optimization offers insight In particular we choose to interpret electoral systems as instances of network flow taking care when translating continuous models to the integer problem underlying the allocation of MPs Pukelsheim et al 2012 provides an excellent review of network models in this area for the interested reader In our work we look at a wide range of objective functions that we can attempt to optimize chosen to promote criteria that seem reasonable for PR to achieve If the proportional strengths are calculated at constituency level we simply recover FPTP If proportionality at national level is too great a leap our methods offer a halfway house that may prove more satisfactory to the general populace than AVFor one particular choice of objective function network flow can be viewed as a well known linear algebra problem namely of finding a diagonal scaling of the matrix with prescribed row and column sums which respects as far as possible the proportionality of the original matrix of votes This process is commonly known as biproportional rounding Zachariasen 2006 and has formed the mathematical basis for reforming PR systems with multiseat districts as epitomised by research groups such as BAZI2 Biproportional rounding applies a global scaling which means that each individual influences the result in every constituency In elections over regions with multiseat districts biproportional rounding can be applied to ensure that as closely as possible the number of seats awarded to a district is proportional to its population while simultaneously ensuring that the number of seats awarded to a party over the whole region is proportional to the total number of votes it receives Finding the closest fit is known as the biproportional apportionment problem It was first proposed as a system for proportional representation in Balinski and Demange 1989 and has since been adopted successfully in a number of legislatures Balinski and Pukelsheim 2006 Maier et al 2010 It is possible to apply biproportional rounding to single seat constituencies For example in Balinski 2008 an implementation is presented for the House of Representatives in the USA Balinski’s method which he calls fair majority voting exploits the fact that the US constitution insists that states should be awarded a quota of representatives proportionate to the population but no such condition applies in the UK The size of the electorate of individual constituencies can vary widely3 in the 2015 General Election the electorate for the Isle of Wight was 108804 while that for Na hEileanan an Iar was just 21744 The Electoral Commission 2015 This means that no allocation will be a biproportional apportionment but biproportional rounding is still applicable To some extent Balinski’s method is also reliant on the fact that US elections are essentially between two parties which doesn’t fit the UK model If biproportional rounding is applied to elections involving many smaller parties then it can result in seats being awarded to candidates with a very small constituency vote To mitigate against this Balinski suggests that parties must reach a certain threshold in their overall popularity before they are legible for seats a feature common to many PR systems Choosing an appropriate threshold is difficult in the UK where some small parties are closely tied to particular regions while others have a broad national level of support and we will discuss a number of methods for accommodating these parties while avoiding the award of a large number of seats to candidates without a strong constituency mandateWe believe that this paper is the first to look at biproportional rounding and network flow models in the UK context As in fair majority voting we ensure that each party receives seats proportionate to its total vote by scaling the votes in each constituency Because of its links to Balinski’s method we will call our proposed family of allocations “balanced majority voting” or BMV We will investigate in detail the feasibility of BMV as a means of distributing seats in any election where each constituency has a single representative We discuss some aspects of implementation of algorithms for finding a biproportional rounding in this case and in a corollary to the results in Balinski and Demange 1989 we give an existence result

Keywords: