The apportionment problem : a monograph

The apportionment problem

A monograph

by

Bjørne-Dyre Hougen Syversten

Dissertation submitted to the Norwegian School of Economics and Business Administration in partial fulfillment of the requirements for the degree ofDoctor oeconomiae

Sla, , gle).

$jC)~

Contents

Contents .

Preface vii

Key terms :... ^Xl

Notation xv

Part I

Chapter 1: Introduction 3

l.1 Basic terminology and conditions 3

1.2 The method of the largest fraction 8

Chapter 2: Divisor methods 11

2.1 A definition of divisor methods 11

2.2 The method of the highest average 13

2.3 The method of major fractions 14

2.4 The method of equal proportions 15

2.5 Theharmonic mean method 16

2.6 The method of the smallest divisor 17 2.7 An alternative formulation of divisor methods 18 2.8 Categories of strict divisor methods . 21 2.9 The constant parametric divisor methods 22 2.10 Approximative tvalues for non-Cl', methods 23

Chapter 3: Conditions 33

3.1 House monotonicity :.. 33

3.2 Consistency 34

3.3 Population monotoni city 37

3.4 Quota related conditions 38

Chapter 4: Properties 47

4.1 Treatment of merger and division 47

4.2 The distribution of remainders and fractions 51 4.3 Treatment of small versus large constituencies 54

Chapter 5: Bias . 63

5. 1 Introduction and basic grouping terminology ., '" 63

5.2 Number division 65

5.3 Quota dIVISIon 66

5.4 The population distribution 70

5.5 Size division 73

5.6 Cluster division 74

5.7 Illustration of the division methods 76

5.8 Bias test 80

Chapter 6: Formulations . 87

6.1 The method of the largest fraction 87

6.2 An attempt for Lowndes' method 88

6.3 Attempts for the harmonic mean method 89

6.4 The method of the highest average 89

6.5 The method of the smallest divisor 90

6.6 The method of major fractions 90

6.7 The method of equal proportions 91

6.8 The constant parametric divisor methods 91

6.9 Maximization of utility 92

6.10 Pairwise comparisons 95

Chapter 7: Thresholds and payoffs 101

7.1 Terminology 102

7.2 Payoff functions for CPt 104

7.3 Preservation of the majority 109

7.4 Payoff functions for LF 113

7.5 Threshold methods 114

7.6 Possible threshold methods for Norway 118

Chapter 8: Choice of apportionment method 121

8.1 Constituencyapportionment 121

8.2 Constituencyapportionment in Norway 124

8.3 Party apportionment 128

8.4 Exploiting the Norwegian election system 130 8.5 House sizes inthe Nordic countries 132 8.6 Motivation for the matrix problem 133

Contents

Part II

Chapter 9: Introduction 139

9.1 Basic terminology 139

9.2 The free matrix apportionment problem 140 9.3 Additional constraints for the matrix problem 141 9.4 Types of matrix apportionment problems 143

9.5 Balinski and Demange's axioms 144

9.6 Existence of matrix allocations 149

9.7 Existence of matrix apportionments 151

Chapter 10: Formulations 155

10.1 Entropy formulation 155

10.2 The dual problem 159

10.3 Utility approach 161

Chapter 11: Relaxed formulations 163

11.1 Helgason and Jornsten's formulation 163

11.2 The measure of goodness 165

11.3 Initialization of constituency multipliers 168 11.4 Consequences for the additive version 172 11.5 Determination of a good value for 't 173 11.6 Politically acceptable algorithms 176

Chapter 12: An apportionment algorithm 181

12.1 A sketch of the algorithm 182

12.2 Upadjustment 184

12.3 Downadjustment 189

12.4 Determination of a good value for u 191

12.5 Calculation of p-effect 193

12.6 Practical problems 197

Chapter 13: Algorithm example 203

13.1 The problem 203

13.2 Initial stage 204

13.3 First iteration 207

13.4 Second iteration 213

13.5 Last iteration 217

Chapter 14:Empirical tests of the algorithm 219

14.1 Data sets 219

14.2 Test parameters 221

14.3 Test method 223

14.4 Comparison of selection methods 225

14.5 Comparison of relaxations 226

14.6 The average decrease in p per iteration 229 14.7 Comparison of initialization procedures 231

14.8 Final remarks 234

Chapter 15: Controlled rounding 237

15.1 Two-dimensional formulation 237

15.2 Divisor method formulation with total entries 242 15.3 Rounding of only internal entries 243 15.4 Rounding of all or only internal entries? 246 15.5 Divisor methods instead of controlled rounding? 250

Chapter 16: Matrix bias . 251

16.1 Ideal for the matrix apportionment 251 16.2 Determining the fair share matrix 252

16.3 Fair share example 257

16.4 Matrix bias tests 261

16.5 Explanation of the matrix bias paradox 266 16.6 Choice of matrix apportionment method 268

Chapter 17: Decomposition 271

17.1 Utilized multiplier sets 271

17.2 The components 272

17.3 Normalization of multiplier sets 274

17.4 Numerical example 276

Chapter 18: Three dimensions 281

18.1 The three-dimensional apportionment problem 281 18.2 Example of a non-integer LP-solution 285 18.3 Motivation for introducing a third dimension 287

References 295

Contents

Appendices

Appendix 1: Divisions and Results of vector bias test .

Description of Division and Vector bias tables .

2 groups .

3 groups .

4 groups

A3

A4 A5 A7 A 10

Appendix 2: Flow charts and Pascal programs A 15

Explanation of flow chart symbols A 16

Example of an inputfile . A 17

Flow charts for the ElectionAlgorithm program A 18

The ElectionAlgorithm program A 25

Flow charts for the MatrixBias program A 54

The MatrixBias program . A 62

Appendix 3: Data regarding the apportionment algorithm A 81

Description of Data set tables A 82

Data sets (countries in alphabetical order) A 83 Description of Algorithm data tables . A 87 Algorithm data (countries in alphabetical order) A 88 Description of Algorithm test tables A 97

Algorithm tests A 98

Appendix 4: Various data and Results of matrix bias tests A 103

Description ofVarious data and Matrix bias tables A 104

Various data main test A 105

Results of main matrix bias test A 106

Various data Icelandic test A 112

Results of Icelandic matrix bias test .. A 113

Preface

This dissertation deals with the field of study known as the apportionment problem. In addition to giving an overview of the field, it treats some topics in greater detail. The dissertation is divided in two parts. The first part, chapter 1 through 8, deals with the vector apportionment problem, while the second part, chapter 9 through 18, treats the matrix apportionment problem. Inaddition to the text, the dissertation contains 4 appendices.

The apportionment problem concerns the problem of dividing the seats in an elected assembly fairly, i.e. proportionally, among the constituencies and/or parties according to the populations/votes. What makes it impossible to achieve a perfectly proportional division in every situation is the indivisibility of seats.

During history many methods for apportioning seats have been proposed. The most important of these are presented in chapters 1 and 2. Due to the indivisi- bility of seats, it is not clear what one should put into the term proportional in the apportionment context. Chapter 3 reviews some natural principles in the vector case, while chapter 9 presents some principles inthe matrix case. Although the common use of apportionment methods is distribution of seats in elected assemblies, it should be noted that such methods are applicable in every situation where indivisible entities are to be distributed proportionally. The test of time has revealed the properties of different apportionment methods. Chapter 4 studies some properties, while chapter 8 contains a discussion regarding suitable properties for different kinds of apportionment. Apportionment methods may also be formulated as constrained optimization problems. Chapter 6 presents formulations for the vector case and chapters 10 - 11 for the matrix case.

I first became aware of the apportionment problem when I read Balinski and Young's book "Fair Representation: Meeting the Ideal of One Man, One Vote" in the early 1990s. My mentor, Professor Kurt Jornsten of the Norwegian School of Economics and Business Administration, then drew my attention to the matrix apportionment problem. An unpublished working paper he had written together with Professor Thorkell Helgason of the University of Iceland, which presented

an entropy formulation of the matrix problem, became the starting point for my HAS-thesis. During the work with that thesis I tried to fmd an efficient algorithm for solving the matrix apportionment problem. The thesis (1992) ended with a sketch of an apportionment algorithm.

The early part of the work with the doctoral dissertation focused on developing the apportionment algorithm. The process of programming the algorithm contributed to its development. Chapter 12 presents the proposed algorithm.

Another task has been the testing of different set-ups of the algorithm. The results of these tests are presented in chapter 14. Chapter 17 is also connected to the algorithm. It presents a way of decomposing the multiplier set for an optimal matrix apportionment. An important part of the dissertation is the empirical measurement of bias for both the vector and matrix apportionment problem. In this connection I propose new ways of grouping the constituencies in chapter 5.

The results of the bias tests are presented in chapters 5 and 16 respectively. Three other chapters worth mentioning are chapter 7 which deals with thresholds, chapter 15 which describes controlled rounding, and chapter 18 which presents the three-dimensional apportionment problem.

Compared with my HAS-thesis, the contents of chapters 5, 7, and 12 - 18 are new, while the contents of the other chapters have been refined. In a wider per- spective, I consider the following to be the new contributions of the dissertation:

- The apportionment algorithm.

[The apportionment initialization procedure (section 11.3) plus the rules for the adjustments (chapter 12)]

- A constructed measure for Norway.

[Section 8.2]

- The measurement of bias of matrix apportionments.

[Chapter 16]

- Division of constituencies (cells) in new ways when measuring bias.

[Sections5.3 - 5.6]

- Some minor results in part I regarding CPt may also be characterized as new.' - The payoff functions in chapter 7 were derived independently of Lijphart and Gibberd. Compared with their article, only the general functions for constant parametric divisor methods represent something new.

Preface

During the last couple of years I have revised the dissertation. A lot of errors have been corrected during this revision. The contents of the language have also been improved. However, since my English could have been better, there IS

certainly some bits of incorrect English left.

The comments of Professor Thorkell Helgason of the University of Iceland have been valuable during the revision process. Thanks also to my mentor, Professor Kurt Jornsten of the Norwegian School of Economics and Business Administra- tion, for ideas and discussions along the way. Finally, thanks to Professor Aanund Hylland of the University of Oslo for his comments on my HAS-thesis.

I also wish to thank the Norwegian School of Economics and Business Administration and Sør-Trøndelag College, School of Economics and Business Administration for financial support during the lengthy work with the dissertation. Finally, thanks to the Norwegian School of Economics and Business Administration, Department of Finance and Management Science for provision of office after my employment period there.

Trondheim, December 1998 / October 1999 Bjørne-Dyre Hougen Syversten

Key terms

Term

Rdjacency .

Rdjustment weight Rllocation matriH

Rllocatlon problem : .

Rpportlonment initialization Rpportionment matriH

Rpportlonment method .

Rpportionment uector

Ruerage number of people per seat for a constituency

RHtal sums .

Balanced .

Benchmark: quotients (upadjustment) Benchmark: quotients (downadjustment)

Bound component .

Bound uector (matrlH problem) Bound uector (matriH problem)

Bound uector (three-dimensional problem) .

Canonical form : .

Cell

Cell quota

Challenging quotients .

Cluster diuision Common diuisor

Completeness (uector problem) .

Completeness (matrlH problem) Consistency (uector problem)

Consistency (matriH problem) .

Constant parametric diuisor methods (CPt)

Constituency component

Constituency multiplier .

Constituency quotient Constituency ralaaattnn

Constructed measure .

CPt

Introduced

Section 15.1 page 238 Section 12.2 page 187 Section 9.3 page 143 Section 9.3 page 143 Section 11.3 page 169 Section 9.1 page 140 Section 1.1 page 4 Section 1.1 page 4 Section 6.4 page 89 Section 18.1 page 282 Section 1.1 page 7 Section 12.2 page 185 Section 12.3 page 190 Section 17.2 page 272 Section 9.3 page 143 Section 14.2 page 221 Section 18.1 page 282 Section 15.1 page 240 Section 9.1 page 139 Section 16.1 page 251 Section 12.2 page 185 Section 5.6 page 74 Section 2.7 page 18 Section 1.1 page 5 Section 9.5 page 146 Section 3.2 page 34 Section 9.5 page 145 Section 2.9 page 22 Section 17.2 page 273 Section 11.2 page 168 Section 2.7 page 18 Section 11.1 page 165 Section 1.1 page 4 Section 2.9 page 22

Discrepancy . Diulslon methods

DM

EL .

Election situation (uector problem) Election situation (matrlH problem)

Encourage dlulsion .

Encourage merger

Equality constrained problem

EP .

EHact proportionality

EHactness (uector problem)

EHactness (matrlH problem) .

EHcluslon payoff

EHtended fair share matrlH

Fair share matriH .

Fauourlng small constituencies compared to Free problem

Global distance .

Grand total entry

HR .

HM

Homogeneity (uector problem)

Homogeneity (matriH problem) .

d'Hondt's method House monotonicity

House size .

Inequality constrained problem .

I nitial marginal ualue of representation I nltial measure of goodness

Internal entry .

Internal uote monotonicity

Lague's method .

LF

Lowndes' method

lp-norm .

Section 16.1 page 253 Section 5.1 page 64 Section 2.9 page 22

Section 14.1 page 221 Section 1.1 page 4 Section 9.3 page 143 Section 4.1 page 48 Section 4.1 page 47 Section 9.3 page 141 Section 2.4 page 15 Section 1.1 page 7 Section 1.1 page 7 Section 9.5 page 144 Section 7.1 page 103 Section 9.5 page 150

Section 9.5 page 148 Section 4.3 page 54 Section 9.2 page 140

Section 12.2 page 186 Section 15.1 page 238

Section 2.2 page 13 Section 2.5 page 16 Section 1.1 page 6 Section 9.5 page 146 Section 2.2 page 13 Section 3.1 page 33 Section 1.1 page 3

Section 9.4 page 143 Section 11.3 page 170 Section 11.3 page 170 Section 15.1 page 238 Section 1.1 page 8

Section 2.3 page 14 Section 1.2 page 9 Section 1.2 page 10 Section 6.1 page 88

Key terms

Malrepresented .

MatrlH apportionment problem MatrlH bias paradoH

MatrlH component ..

Measure of goodness MF

Monotonicity ..

National auerage population per seat ..

National auerage number of seats per indiuidual No Initialization

Number diuision .

Number o f constituencies Number o f parties

Ouerrepresented .

Outgoing quotients

Partial inequality constrained problem ..

Party relaHation Planar sums

Population monotonicity .

Population uector Posltiue problem

Proportional ..

Quota ..

Quota dluislon Quota matriH

Quota ratio initialization ..

Quota uector

Releuance ..

Representation payoff Representation selection

Rightly represented ..

p-effect

p-effect selection

Section 11.2 page 166 Section 9.1 page 139 Section 16.4 page 263 Section 17.2 page 273 Section 11.2 page 165 Section 2.3 page 15 Section 9.5 page 146 Section 1.1 page 6 Section 6.6 page 90 Section 11.3 page 168 Section 5.2 page 65 Section 1.1 page 3 Section 7.1 page 103 Section 11.2 page 166 Section 12.3 page 189 Section 9.4 page 144 Section 11.1 page 165 Section 18.1 page 282 Section 3.3 page 38 Section 1.1 page 3 Section 9.1 page 140 Section 1.1 page 7 Section 1.1 page 6 Section 5.3 page 66 Section 9.5 page 145 Section Il. 3 page 168 Section 1.1 page 6 Section 9.5 page 145 Section 7.1 page 103 Section 12.1 page 183 Section 11.2 page 166 Section 12.5 page 194 Section 12.5 page 196

SO . Seat-quota ratio

Set of allocations

Set o f apportionments .

Suitable multiplier set Size dluision

Staying aboue lower quota .

staying below upper quota Staying within the quota

Strict dlulsor method .

strict diuisor method

Target quotient .

Target weight

The Danish method (DM)

The harmonic mean method (HM) .

The method o f equal proportions (EP) The method o f major fractions (MF)

The method o f the highest auerage ..(HR) .

The method o f the largest fraction (LF) The method o f the smallest diulsor (SO)

Three-dimensional apportionment problem . Threshold Interual

Threshold Interual for the Ith seat

Threshold of eHcluslon .

Threshold o f representation Total entry

Underrepresented .

Uniformity (uector problem) Uniformity (matrlH problem)

Dector apportionment problem .

Dote matriH

Weale population monotonicity .

Zero restrlctedness (uector problem) ..

Zero restrictedness (controlled rounding)

Section 2.6 page 17 Section 5.8 page 80 Section 9.3 page 143 Section 9.3 page 143 Section 12.1 page 182 Section 5.5 page 73 Section 3.4 page 38 Section 3.4 page 38 Section 3.4 page 41 Section 2.1 page 11 Section 2.7 page 19

Section 11.3 page 170 Section 11.3 page 170 Section 2.9 page 22 Section 2.5 page 16 Section 2.4 page 15 Section 2.3 page 15 Section 2.2 page 13 Section 1.2 page 9 Section 2.6 page 17 Section 18.1 page 283 Section 7.1 page 102 Section 7.1 page 103 Section 7.1 page 102 Section 7.1 page 102 Section 15.1 page 238

Section 11.2 page 166 Section 3.2 page 34 Section 9.5 page 145

Section 1.1 page 4 Section 9.1 page 139

Section 3.3 page 37

Section 3.4 page 43 Section 15.1 page 238

Notation

Stands for

Basic apportionment notation

h House size .

m Number of constituencies n Number of parties

o Number of levels .

i Index for constituencies j Index for parties

k Index for levels .

l Index for seats

M The set of all constituencies

N The set of all parties .

O The set of alilevels H The set of seats

p Population vector / Vote matrix .

Pi Population inconstituency i

Pij Votes for partyj inconstituency i

Pijk Votes for level kofpartyj inconstituency i .

a Apportionment vector/matrix

ai Apportionment to constituency i

aij Apportionment topartyjinconstituency i . aijk Apportionment to level kof partyj inconstituency i

A Apportionment method

(p,h) Election situation for vector problem .

P National average population per seat

Pi Average number of people per seat for constituency i

q Quota vector/matrix .

qi Quota of constituency i

ri Fractional part of quota

r

*

dl Divisor number lina divisor series

z Common divisor

ZJ Common divisor for HA .

ZA Common divisor for SD

Introduced

Page 3 Page 3 Page 103 Page 281 Page 3 Page 103 Page 281 Page 11 Page 3 Page 103 Page 281 Page 11

Page 3, 139,281 Page 3

Page 139 Page 281

Page 4,140,281 Page 4

Page 140 Page 281 Page 4 Page 4 Page 6 Page 168 Page 6, 145 Page 6 Page 8 Page 9 Page 11 Page 18 Page 19 Page 19

ri

t Parameter for constant parametric divisor method Page 22

r R

Lower constituency bounds vector Upper constituency bounds vector ri Lower bound for constituency (row) i

Ri

c

C .

Lower party bounds vector

Upper party bounds vector .

Lower bound for party (column)j Upper bound for party (column) j

c·_'}

C·

a

Page 141 Page 141 Page 141 Page 141 Page 142 Page 142 Page 141 Page 141

O' Bound vector Page 143,282

(p,O') Election situation for matrix problem Page 143

f Allocationmatrix Page 143

R (0') Set of allocations Page 143

RO(p,O') Subset ofR(a) Page 149

R+(p,O') Subset of RO(p,a) Page 149

R1(p,0') Subset of RO(p,a) Page 151

l

Abbreviations

LF The method of the largest fraction .

HA The method of the highest average

MF The method of major fractions

SD The method of the smallest divisor .

EP The method of equal proportions

HM The harmonic mean method

DM The Danish method .

CPt Constant parametric divisor method with parameter t EL Election apportionment

X-Y ...Bound vector for which the constituency andparty bounds have been determined by apportionment methods X and Y respectively ...•....•.

Page 149

Page 9

Page 13 Page 15 Page 17 Page 15 Page 16 Page 22 Page 22 Page 221

Page 221

Notation

Algorithm notation

o

A.i Constituency multiplier for constituency i Jlj Party multiplier for partyj

S Set of positive vote cells .

S Set of zero vote cells

aijl °/1variable for the lth seat in cell(i.;)

L{A.) Constituency relaxed objective function . il Current assignment

Measure of goodness

Constituency i's contribution to p .

Set of underrepresented constituencies Set of overrepresented constituencies Set of rightly represented constituencies Initial constituency multiplier

P

Pi .

M-

Ar"

MO .

ti Target quotient for constituency i

't Target weight .

K. Initial marginal value of representation

o

P Q

Q Set of quotients which are unassigned qijl Quotient number Iin cell (i.;)

q~{x) xthchallenging quotient in cell (u,v) .

q5>v(x) The xthoutgoing quotient in cell (u,v)

qJt{x) xthbenchmark quotient in connection with cell (u,v)

d&e{xe) ..xth distance for constituency uwithin party eand where the benchmark quotient comes from constituency c .

d&e(y) yth global distance for constituency u,which occurs within party eand where the benchmark quotient comes from constituency c

'Xu Adjustment distance for constituency u

U Adjustment weight .

A.u Former value of constituency multiplier Initial measure of goodness

Set of quotients which are assigned a seat

qujl Former value of quotient

<I>i p-effect for constituency i .

M The opposite malrepresentation group

p

Page 147 Page 147, 159 Page 147, 159 Page 155 Page 155 Page 156 Page 167 Page 165 Page 165 Page 183 Page 165 Page 165 Page 166 Page 168 Page 170 Page 170 Page 170 Page 170 Page 184 Page 184 Page 184 Page 185 Page 189 Page 185, 190 Page 195 Page 195 Page 187 Page 187 Page 188 Page 187 Page 194 Page 194 Page 194

Sundry

Ll:;J ^{o o o o o} Highest integer not larger than ~

rl:;l

u(l)

Lowest integer not smaller than ~

Utility anindividual derives frombeing represented by Irepresentatives

Page Page Page

8 8 92

f.DEo ^{o o o o o} Bias between group D andE o o o o o o o o o o o o. o o o o o o o o o o o o o o o o o o o o o o o .. o Page ⁸¹

Ho

Alternative hypothesis

a Miscellaneous

s Miscellaneous

Controlled rounding

b o o o o o o o o o A tabular array(matrix) o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o

b Rounding base

ay

bij

il

ay

zp o o o o o o o o Objective function for controlled rounding problem o o o o o o o o o o o o

Grouping

c o o o o o o... Number of groups

g Index for groups C The set of all groups

Go. ^{o •• o. o} The set of all constituencies belonging tog o o o o o o o o o o o o o o o o o o o o o o

n Grouping vector

ng Number of constituencies in group g

Page 82

Page 237 Page 237 Page 239 Page 239 Page 239 Page 240 Page 240

Page 64 Page 64 Page 64 Page 64 Page 64 Page 64

Part I:

The Vector Apportionment

Problem

Chapter 1: Introduction

Chapter 1 presents the vector apportionment problem. Section 1.1 introduces the basic terminology and presents some basic conditions, while the main topic in the last section is the apportionment method called the method of the largest fraction.

1.1 Basic terminology and conditions

To introduce the basic terminology for the vector apportionment problem we look at the situation where h seats shall be distributed among m constituencies based on the populations of these constituencies. We could just as well have looked at the apportionment of seats among parties because the methodology is similar. However, the apportionment among constituencies is chosen. h = O results in the trivial situation where no constituency gets any seat, while m = O means that there is not any constituency to distribute the seats to. We therefore let the house size h and the number of constituencies m be positive integers. If m = 1, the sole constituency must get all h seats available. Thus, for all practical purposes we can assume that m ~ 2. The index i, where i ^E M = {l, 2, ..., m} is used for the constituencies. The populations of the constituencies, or alternatively the number of eligible voters in the constituencies, are represented by the population uector, p

=

For other areas where the use of apportionment methods might be desirable, Pi may be real. To cover all possibilities we assume that Pi is positive and real.

Population is just one possible basis for apportionment of seats in parliament.

Other possible bases are the number of eligible voters, the number of votes, or another quantitative measure, including constructed measures. An example of a constructed measure is: Population +Eligible voters +20·Area, which is used in Denmark, [H-S] (page Ill.d), In section 8.2 we propose a constructed measure for Norway.

The final apportionment of seats among the constituencies is represented by the apportionment uector, which we denote a = (ai). A seat cannot be divided, so

ai must be integer valued. It is possible that constituency i is not apportioned any seat. Thus, ai is a non-negative integer, i.e. a ;;:::O and integer. It is obvious that the sum of seats over all constituencies aMequals h:

(1.1) 'Lai=aM=h

ieM

We let PM denote the total population of the country:

(1.2)

The vector (p}, P2, ... , Pm, h), which we usually abbreviate to (p,h), contains all data of interest for the apportionment. We call such a vector an election situation for the uector apportionment problem. The task ahead is to determine an apportionment vector which is ''proportional'' to the population vector. A method utilized in such a determination process is called apportionment method and denoted A.

An apportionment method should be able to handle every possible election situation, i.e. A should be well defmed and non-empty for all election situations.

It is reasonable to allow more than one possible apportionment for election situations where there is a tie between two or more constituencies for the last seat(s). A simple example:

Chapter 1: Introduction

Example 1.1

We face an election situation where h is an odd number and the country consists of two constituencies with equal populations. Then any reasonable apportionment

h+1 h-l h-l h+1 .

method should allow both a

=

=

Ties can also arise when populations are unequal, but this depends on the properties of the apportionment method being used. Even if p is integer or rational, ties may involve irrational numbers. A tie can be broken by lottery, toss of coin or another tie breaking procedure. However, in most practical election situations the populations are so large that ties rarely occur.

A tie can be thought of as a point where the apportionment is about to change. In the immediate neighbourhood of a tie point arbitrarily small population changes will lead to different apportionments, and all these apportionments should be allowed at the tie point. The fact that a tie point together with its immediate neighbourhood involve irrational numbers is why we allowed p to be real from the beginning. [B&Y] (page 98) define a condition called completeness:

Completeness is a continuity condition which extends the concept of apportion- ment methods to all real populations. An apportionment method A is completed by letting a E A(p,h) for real population vectors p E 9lm if and only if there is a sequence ofrational m-vectors pa converging to p such that a E A(pa,h) for all a. The mathematical formulation of completeness in [B&D-l] (page 711) is:

Definition 1.1

A is complete ifJf ~ p and a ^EA(pa,h) for every a, then a ^E A(p,h).

The central question regarding the apportionment problem is: When restricted to integer solutions, what do we mean by proportional? Below we review some basic conditions concerning proportionality.

Proportionality concerns the size of populations, not their names or other characteristics. Therefore, permuting the populations should only result in apportionments that are permuted in the same way. [H-A] (page 23) calls this condition neutrality:

Definition 1.2

A is neutral if for all h, p, and a and all permutations ro ofM,

a ^EA(p,h) if and only if am ^E A(Pm,h).

Other names which have been used for this condition are symmetry, [B&Y]

(page 97), and anonymity, [B] (page 139). An apportionment method which orders constituencies alphabetically and breaks ties in favour of the constituency ordered first is not neutral.

The same proportional change in the population of every constituency should not alter the apportionment, since there is no change in the proportional shares of the constituencies. [B&Y] (page 97) call this condition homogeneity, while [H-A]

(page 9) uses the name scale independence.

Definition 1.3

A is homogeneous ifA(p,h) =A(~·p,h) for all (p,h) and all real numbers ~>O.

We use the notationp for the national auerage population per seat:

(1.3) P -_- .E..M_h

The quota of constituency i is denoted qi and defmed as the population of this constituency divided by the national average population per seat:

(1.4)

qi shows the exact number of seats constituency i would be entitled to if partial seats were allowed. The quota uector is denoted q = (qi). It can be interpreted as the ideal assignment. Clearly, the sum of all quotas equals h:

(1.5) ^{~ q.}£..J l = ~£..J K.hPM =l!_.~p.PM£..J l =

.s..

ieM ieM ieM

Chapter 1: Introduction

In practice there are few election situations where any qi is integer. When the quota of every constituency is integer, we have euact proportionality. Incase this highly unlikely event occurs, the apportionment method should distribute the seats according to the quotas. This condition is called euactness, [B] (page 139), or weak proportionality, [B&Y] (page 97).

Definition 1.4

A is eHact if qi ^E N for every i implies that A(p,h)

=

=

[B&Y] (page 97) and [B] (page 139) present the condition that as the house size grows the apportionment should become "no less proportional". Let us call this condition integer proportionality:

Definition 1.5

A is integer proportional if a ^E A(p,h) and il =~'a is integer valued, where O< ~ < 1 and rational, imply that il =A(p,h), where h =~·h.

Notice that ilshould be the unique apportionment with the smaller house size

h.

Consider an election situation with two constituencies and a house size of 6. IfA apportions 4 seats to the first and 2 seats to the second constituency, then integer proportionality demands that A gives 2 seats to the first and 1 seat to the second constituency when the house size is only 3.

An apportionment method which is neutral, homogeneous, exact, and integer proportional is proportional, [B] (page 139). All methods we encounter in this and the next chapter are proportional and complete.

Whenever two constituencies have equal populations, it seems reasonable that their apportionments do not differ by more than one seat. The reason for allowing the apportionments to differ by one seat is that the two constituencies may have to share an odd number of seats, as in Example 1.1 above.

Apportionment methods which obey the stated condition are called balanced, [B&Y] (page 144), or strongly balanced, [H-A] (page 24):

Definition 1.6

A is balanced if a ^E A(p,h) and Pi =ps imply

I

I ~

A natural requirement is that a constituency with a larger population than another constituency should never get less seats. This condition has been presented under the name weak. population monotonicity, [B&Y] (page 147). [H-A] (page 27) calls it internal uote monotonicity:

Definition 1.7

A is internal uote monotone if a ^E A(p,h) and Pi>Ps imply ai ~ as.

1.2 The method of the largest fraction

Let ~ ~ O be a real number. We define L~ J and I ~lthe following way:

(1.6) _L~ J =The greatest integer equal to or lower than ~.

I ~ l =The smallest integer equal to or higher than ~.

It is clear that L~ J = I ~l if and only if ~ is integer valued. A constituency's quota can be divided in two parts, an integer and a fractional part. We denote the fractional part ri, so the quota can be written as:

(1.7) qi =LqiJ +ri where O ~ ri < 1

It seems reasonable that each constituency should get at least as many seats as the integer part of its quota LqiJ. After such an assignment there are still ~ ri =

ru

seats left for distribution. The number of remaining seats ^rM is bolinded the following way: O ~ 1"M ~ m-I.

The normal way of dealing with fractions is to round fractions greater than

i

upwards and fractions smaller than

i

i

Chapter 1: Introduction

fractions equal to ~ in the following explanation: The described rounding procedure only works if the number of fractions greater than ~ is equal to ru. If there are more than ru fractions greater than ~, too many seats will be distributed, and if there are less, too few seats will be distributed.

The natural modification of the rounding procedure above is to sort the fractions in descending order and distribute the remaining

ru

The procedure described above is a well-known apportionment method. It is often called the method of the largest remainder. We prefer the name the method of the largest fraction, since this name is closest to our description of the method. The method is also known as Hamilton's method, named after Alexander Hamilton who proposed the method in 1792. Alexander Hamilton was the first Secretary of the Treasury of the United States and a prominent political figure in the early years of the US. We use the abbreviation LF for the method of the largest fraction. Algorithm 1.1 is a formal description of how the apportion- ment process is carried out with LF:

Algorithm 1.1

Step 1: Give each constituency as many seats as the integer part of its quota LqiJ.

Step 2: Order the fractional parts ^ri in descending order. If there is a tie for a position, break it in favour of any of the eligible fractions. Find the sum of all fractional parts ru; either a~ru ~h - ~ LqiJ or ru = ~ ri. .Give one seat each to the first

ru

Step 3: The fmal apportionment to a constituency is the sum of seats given to it in step 1 and 2.