A Guided Tour of the Mathematics of Seat Allocation and Political Districting

This chapter focuses on Seat Allocation and Political Districting, two of the main topics in the study of electoral systems. Models and algorithms from discrete mathematics and combinatorial optimization are used to formalize the problems and find solutions that meet some fairness requirements. The first problem concerns the assignment of seats to parties in political elections. In particular, we discuss the well-known Biproportional Apportionment Problem (BAP), that is, the problem of assigning the House seats in those countries that adopt a two-level proportional system. The problem is difficult also from a mathematical viewpoint, since it combines a matrix feasibility problem with the requirement of double proportionality. The second topic, Political Districting (PD), is a territorial problem in which electoral districts must be designed so that each voter is univocally assigned to one district. This is a relevant problem, since, given the same vote outcome of an election, depending on the district shape and size, the final seat allocation to parties could be drastically different. For this reason, PD procedures have been proposed to output district maps that meet a set of criteria aimed at avoiding district manipulation by parties. Both BAP and PD are extensively studied in the literature, the first one starting from the seminal paper by Balinski and Demange (1989a,b), the second dating back to 1960’s when the paper by Hess et al. (1965) formulated for the first time the problem as an optimization one. The chapter is organized in two parts, the first related to BAP, the second to PD.