Facets of proportionality

In this thesis, we study proportional representation in three different collective decision-making settings: voting, budgeting, and clustering. In these settings, we develop new axioms and rules to assess and enable outcomes which proportionally reflect the opinions of all agents taking part in the decision-making. In the first part, we examine proportionality in multiwinner voting. In this setting, voters submit preferences over candidates, based on which we must select a subset of these candidates. We strengthen existing proportionality axioms for a general class of preferences to be efficiently verifiable and hard to achieve. In particular, our axioms are applicable to both approval and ordinal preference models, providing a framework to encompass both settings. We also investigate tradeoffs between individual excellence, diversity, and proportional representation and give rules achieving all three desiderata at the same time. In the second part, we study proportionality in participatory budgeting (PB), where we need to select a subset of costly projects subject to a budget constraint. Specifically, we study PB with approval preferences and generalize existing results to a large class of potential utility functions. We establish novel proportionality guarantees for the Method of Equal Shares, which is currently used in real-life PB elections. Then we consider a generalized setting incorporating both divisible and indivisible projects, and define proportional methods for this domain. In the third part, we focus on proportional representation in metric spaces. This setting subsumes facility location, clustering, and data summarization problems. For this setting, we establish novel connections between prominent fairness concepts like proportional fairness and individual fairness. Further, we relate the clustering setting to the proportionality notions we developed in the first part of the thesis and show that algorithms satisfying these notions provide the best known approximation guarantees. Finally, we analyze sortition, the process of randomly selecting representative panels/committees from a population. We model this setting using metric spaces and show that randomly selected panels according to two particular mechanisms make decisions closely aligned with the will of the underlying population.