Consider the decision-making setting where agents elect a panel by expressing both positive and negative preferences. Prominently, in constitutional AI, citizens democratically select a slate of ethical preferences on which a foundation model is to be trained. There, in practice, agents may both approve and disapprove of different ethical principles. Proportionality has been well-studied in computational social choice for approval ballots, but its meaning remains unclear when negative sentiments are also considered. In this work, we propose two conceptually distinct approaches to interpret proportionality in the presence of up and down votes. The first approach treats the satisfaction from electing candidates and the impact of vetoing them as comparable, leading to combined proportionality guarantees. The second approach considers veto power separately, introducing guarantees distinct from traditional proportionality. We formalize axioms for each perspective and examine their satisfiability by suitable adaptations of Phragm\'en's rule, Proportional Approval Voting rule and the Method of Equal Shares.

Consider the problem of selecting a fixed number of k nodes from a network. Our goal is twofold: to identify the most influential nodes, and to ensure that the selection proportionally represents the diversity within the network. For instance, consider a network composed of three groups of densely connected nodes. Assume the groups contain 50%, 30%, and 20% of all nodes, respectively, and connections between groups are relatively sparse. If the objective is to select k = 10 nodes, a proportional approach would involve selecting five most influential nodes from the first group, three from the second, and two from the third group.

In participatory budgeting (PB), voters decide through voting which subset of projects to fund within a given budget. Proportionality in the context of PB is crucial to ensure equal treatment of all groups of voters. However, pure proportional rules can sometimes lead to suboptimal outcomes. We introduce the Method of Equal Shares with Bounded Overspending (BOS Equal Shares), a robust variant of Equal Shares that balances proportionality and efficiency. BOS Equal Shares addresses inefficiencies inherent in strict proportionality guarantees yet still provides good proportionality similar to the original Method of Equal Shares. In the course of the analysis, we also discuss a fractional variant of the method which allows for partial funding of projects.

We consider a voting model, where a number of candidates need to be selected subject to certain feasibility constraints. The model generalises committee elections (where there is a single constraint on the number of candidates that need to be selected), various elections with diversity constraints, the model of public decisions (where decisions needs to be taken on a number of independent issues), and the model of collective scheduling. A critical property of voting is that it should be fair -- not only to individuals but also to groups of voters with similar opinions on the subject of the vote; in other words, the outcome of an election should proportionally reflect the voters' preferences. We formulate axioms of proportionality in this general model. Our axioms do not require predefining groups of voters; to the contrary, we ensure that the opinion of every subset of voters whose preferences are cohesive-enough are taken into account to the extent that is proportional to the size of the subset. Our axioms generalise the strongest known satisfiable axioms for the more specific models. We explain how to adapt two prominent committee election rules, Proportional Approval Voting (PAV) and Phragm\'{e}n Sequential Rule, as well as the concept of stable-priceability to our general model. The two rules satisfy our proportionality axioms if and only if the feasibility constraints are matroids.

We study the setting of committee elections, where a group of individuals needs to collectively select a given size subset of available objects. This model is relevant for a number of real-life scenarios including political elections, participatory budgeting, and facility-location. We focus on the core -- the classic notion of proportionality, stability and fairness. We show that for a number of restricted domains including voter-interval, candidate-interval, single-peaked, and single-crossing preferences the core is non-empty and can be found in polynomial time. We show that the core might be empty for strict top-monotonic preferences, yet we introduce a relaxation of this class, which guarantees non-emptiness of the core. Our algorithms work both in the randomized and discrete models. We also show that the classic known proportional rules do not return committees from the core even for the most restrictive domains among those we consider (in particular for 1D-Euclidean preferences). We additionally prove a number of structural results that give better insights into the nature of some of the restricted domains, and which in particular give a better intuitive understanding of the class of top-monotonic preferences.

We establish a link between multiwinner elections and apportionment problems by showing how approval-based multiwinner election rules can be interpreted as methods of apportionment. We consider several multiwinner rules and observe that they induce apportionment methods that are well-established in the literature on proportional representation. For instance, we show that Proportional Approval Voting induces the D'Hondt method and that Monroe's rule induces the largest reminder method. We also consider properties of apportionment methods and exhibit multiwinner rules that induce apportionment methods satisfying these properties.

We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) and the bribery actions are limited to: adding an approval to a vote, deleting an approval from a vote, or moving an approval within a vote from one candidate to the other. We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV). We find the landscape of complexity results quite rich, going from polynomial-time algorithms through NP-hardness with constant-factor approximations, to outright inapproximability. Moreover, in general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee (i.e., adding approvals only for this preferred candidate, or moving approvals only to him or her). We also study parameterized complexity of our problems, with a focus on parameterizations by the numbers of voters or candidates.

We consider the following problem in which a given number of items has to be chosen from a predefined set. Each item is described by a vector of attributes and for each attribute there is a desired distribution that the selected set should have. We look for a set that fits as much as possible the desired distributions on all attributes. Examples of applications include choosing members of a representative committee, where candidates are described by attributes such as sex, age and profession, and where we look for a committee that for each attribute offers a certain representation, i.e., a single committee that contains a certain number of young and old people, certain number of men and women, certain number of people with different professions, etc. With a single attribute the problem collapses to the apportionment problem for party-list proportional representation systems (in such case the value of the single attribute would be a political affiliation of a candidate). We study the properties of the associated subset selection rules, as well as their computation complexity.

To choose a suitable multi-winner rule, i.e., a voting rule for selecting a subset of $k$ alternatives based on a collection of preferences, is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an "optimal" subset. In this paper, we offer a new perspective to measure the quality of such subsets and---consequently---multi-winner rules. We provide a quantitative analysis using methods from the theory of approximation algorithms and estimate how well multi-winner rules approximate two extreme objectives: diversity as captured by the (Approval) Chamberlin--Courant rule and individual excellence as captured by Multi-winner Approval Voting. With both theoretical and experimental methods we classify multi-winner rules in terms of their quantitative alignment with these two opposing objectives.

We consider the problem of selecting a fixed-size committee based on approval ballots. It is desirable to have a committee in which all voters are fairly represented. Aziz et al. (2015a; 2017) proposed an axiom called extended justified representation (EJR), which aims to capture this intuition; subsequently, Sanchez-Fernandez et al. (2017) proposed a weaker variant of this axiom called proportional justified representation (PJR). It was shown that it is coNP-complete to check whether a given committee provides EJR, and it was conjectured that it is hard to find a committee that provides EJR. In contrast, there are polynomial-time computable voting rules that output committees providing PJR, but the complexity of checking whether a given committee provides PJR was an open problem. In this paper, we answer open questions from prior work by showing that EJR and PJR have the same worst-case complexity: we provide two polynomial-time algorithms that output committees providing EJR, yet we show that it is coNP-complete to decide whether a given committee provides PJR. We complement the latter result by fixed-parameter tractability results.