On Proportionality in Complex Domains
Julian Chingoma

Abstract:
The vast array of collective decision-making scenarios that occur in the real world has provided a wealth of examples for computational social choice researchers to model and analyse. The field of computational social choice has taken the perspective of computer science in studying the methods used to aggregate group opinions towards producing a single collective outcome. The classical social-choice example sees an electorate voting over candidates in some election. Typically, the goal in these elections is to elect a single winning candidate such as a president. However, this thesis goes beyond the case of single-winner elections and focuses on scenarios where multiple candidates are to be selected as winners instead of just one candidate. Real-world applications of this include the apportionment problem where parliamentary seats are to be distributed to political parties, choosing a number of candidates to form a shortlist to attend a job interview, or a local municipality choosing a selection of public projects to implement. This is an area that has garnered plenty of attention from researchers and a significant portion of their work has been dedicated to studying fair aggregation methods, with fairness specifically referring to the notion of proportional representation. In these settings where the goal is to select multiple winners, the ideal of proportionality that we adopt typically requires that a group of voters that has very similar preferences and represents an alpha-fraction of the voting population, should have control over the selection of an alpha-fraction of the winners. This is a notion that we deem to be highly desirable and is one that has received considerable attention within the literature of computational social choice. The thesis will investigate the extent to which proportional representation can be developed for certain complex domains.

What are these complex domains? Take, as a foundation, the standard voting scenario where we are to elect multiple candidates to a committee. What if the seats on the committee are associated with a role and some of the roles are more valuable than others? Or consider that there is a constraint that states that including candidate A means that candidate B cannot be in the committee? We identify scenarios such as these, amongst others, as complex variants of the standard setting where we are to choose more than one winner. Within these more complex settings, we deem it desirable that the notion of proportional representation be suitably adapted. This is then the primary focus of this thesis. Specifically, the thesis' main objective is to determine, when in these complex domains, how to produce outcomes that are proportionally representative of the participating voters. In doing so, we adapt proportionality notions from the standard settings while taking into account the added complexities that come with these domains.

The first part of the thesis consists of two chapters. The first of these chapters deals with the apportionment problem but with the voters considering some parliamentary seats to be more valuable than others. This notion of seats having varying values is then seen again in this part's second chapter where the problem is assigning multiple candidates to some seats in a committee but with committee seats not being treated equally. Within both chapters, the goal is to import proportionality into the complex domains of interest.

The thesis' next part consists of a single chapter and represents a brief deviation from the main objective of the thesis. Here, there is an investigation into the extent that aggregation methods that are used to select multiple winners, can be simulated in the general framework of judgment aggregation. This analysis provides us with insights into the inner workings of these aggregation methods.

The part of the thesis that follows sees a return to the task of adapting proportionality to complex domains. While each of this part's two chapters deals with a particular domain of interest, there is a common thread throughout this part. Specifically, for each domain, there is the presence of a constraint that restricts the outcomes that are feasible. Now, what exactly are these two domains? One scenario concerns a vote over a set of public issues with there being multiple alternatives that can be selected for each issue. The other scenario sees voters working to collectively create a shortlist of candidates. For both of these, we look to ensure proportional outcomes are returned while respecting a constraint.

In the end, the thesis provides an exploration of aggregation methods that aim to choose many winners. And for the most part, this exploration is done through investigating to what extent one can lift proportionality notions from standard multiwinner voting settings to some of their more complex counterparts.