Mathematics and Democracy

Preface xiii

PART 1. VOTING PROCEDURES 1

Chapter 1: Electing a Single Winner: Approval Voting in Practice 3
1.1. Introduction 3
1.2. Background 6
1.3. Early History 8
1.4. The Adoption Decisions in the Societies 10
1.5. Does AV Make a Difference? 14
1.6. Does AV Elect the Lowest Common Denominator? 16
1.7. Is Voting Ideological? 18
1.8. Summary and Conclusions 21

Chapter 2: Electing a Single Winner: Approval Voting in Theory 23
2.1. Introduction 23
2.2. Preferences and Strategies under AV 25
2.3. Election Outcomes under AV and Other Voting Systems 26
2.4. Stability of Election Outcomes 37
2.5. Summary and Conclusions 42
Appendix 43

Chapter 3: Electing a Single Winner: Combining Approval and Preference 46
3.1. Introduction 46
3.2. Definitions and Assumptions 48
3.3. Preference Approval Voting (PAV) 49
3.4. Fallback Voting (FV) 52
3.5. Monotonicity of PAV and FV 56
3.6. Nash Equilibria under PAV and FV 58
3.7. The Effects of Polls in 3-Candidate Elections 61
3.8. Summary and Conclusions 66

Chapter 4: Electing Multiple Winners: Constrained Approval Voting 69
4.1. Introduction 69
4.2. Background 70
4.3. Controlled Roundings 72
4.4. Further Narrowing: The Search May Be Futile 75
4.5. Constrained Approval Voting (CAV) 80
4.6. Unconstraining Votes: Two Alternatives to CAV 82
4.7. Summary and Conclusions 87

Chapter 5: Electing Multiple Winners: The Minimax Procedure 89
5.1. Introduction 89
5.2. Minisum and Minimax Outcomes 91
5.3. Minimax versus Minisum Outcomes: They May Be Antipodes 97
5.4. Endogenous versus Restricted Outcomes 101
5.5. Manipulability 103
5.6. The Game Theory Society Election 105
5.7. Summary and Conclusions 108
Appendix 109

Chapter 6: Electing Multiple Winners:

Minimizing Misrepresentation 112
6.1. Introduction 112
6.2. Obstacles to the Implementation of Proportional Representation (PR) 113
6.3. Integer Programming 115
6.4. Monroe's System 116
6.5. Assigning More than One Candidate to a Voter 119
6.6. Approval Voting 121
6.7. Fractional Assignments 123
6.8. Noninteger k 125
6.9. The Chamberlin-Courant System 126
6.10. Tullock's System 127
6.11. Weighted Voting 129
6.12. Nonmanipulability 130
6.13. Representativeness 131
6.14. Hierarchical PR 133
6.15. Summary and Conclusions 136
Appendixes 138

Chapter 7: Selecting Winners in Multiple Elections 143
7.1. Introduction 143
7.2. Referendum Voting: An Illustration of the Paradox of Multiple Elections 145
7.3. The Coherence of Support for Winning Combinations 149
7.4. Empirical Cases 155
7.5. Relationship to the Condorcet Paradox 160
7.6. Normative Questions and Democratic Political Theory 165
7.7. Yes-No Voting 167
7.8. Summary and Conclusions 169

PART 2. FAIR-DIVISION PROCEDURES 171

Chapter 8: Selecting a Governing Coalition in a Parliament 173
8.1. Introduction 173
8.2. Notation and Definitions 176
8.3. The Fallback (FB) and Build-Up (BU) Processes 177
8.4. The Manipulability of FB and BU 181
8.5. Properties of Stable Coalitions 182
8.6. The Probability of Stable Coalitions 186
8.7. The Formation of Majorities in the U.S. Supreme Court 189
8.8. Summary and Conclusions 193
Appendix 195

Chapter 9: Allocating Cabinet Ministries in a Parliament 199
9.1. Introduction 199
9.2. Apportionment Methods and Sequencing 202
9.3. Sophisticated Choices 206
9.4. The Twin Problems of Nonmonotonicity and Pareto-Nonoptimality 209
9.5. Possible Solutions: Trading and Different Sequencing 214
9.6. A 2-Party Mechanism 215
9.7. Order of Choice and Equitability 218
9.8. Summary and Conclusions 220
Appendix 221

Chapter 10: Allocating Indivisible Goods: Help the Worst-Off or Avoid Envy? 224
10.1. Introduction 224
10.2. Maximin and Borda Maximin Allocations 227
10.3. Characterization of Efficient Allocations 229
10.4. Maximin and Borda Maximin Allocations May Be Envy-Ensuring 234
10.5. Finding Envy-Unensuring Allocations 244
10.6. Unequal Allocations and Statistics 248
10.7. Summary and Conclusions 250

Chapter 11: Allocating a Single Homogeneous Divisible Good:

Divide-the-Dollar 252
11.1. Introduction 252
11.2. DD1: A Reasonable Payoff Scheme 254
11.3. DD2: Adding a Second Stage 257
11.4. DD3: Combining DD1 and DD2 262
11.5. The Solutions with Entitlements 263
11.6. Summary and Conclusions 266
Appendix 267

Chapter 12: Allocating Multiple Homogeneous Divisible Goods:

Adjusted Winner 271
12.1. Introduction 271
12.2. Proportionality, Envy-Freeness, and Efficiency 272
12.3. Adjusted Winner (AW) 273
12.4. Issues at Camp David 275
12.5. The AW Solution 279
12.6. Practical Considerations 282
12.7. Summary and Conclusions 287

Chapter 13: Allocating a Single Heterogeneous Good:

Cutting a Cake 289
13.1. Introduction 289
13.2. Cut-and-Choose: An Example 290
13.3. The Surplus Procedure (SP) 292
13.4. Three or More Players: Equitability and Envy-Freeness May Be Incompatible 296
13.5. The Squeezing Procedure 297
13.6. The Equitability Procedure (EP) 299
13.7. Summary and Conclusions 303

Chapter 14: Allocating Divisible and Indivisible Goods 305
14.1. Introduction 305
14.2. Definitions and Assumptions 306
14.3. Difficulties with Equal and Proportional Reductions in the High Bids 308
14.4. The Gap Procedure 312
14.5. Pareto-Optimality 314
14.6. Envy-Freeness: An Impossible Dream 316
14.7. Sincerity and In dependence 322
14.8. Extending the Gap Procedure 323
14.9. Other Applications 324
14.10. Summary and Conclusions 327

Chapter 15: Summary and Conclusions 329

Glossary 337
References 343
Index 363