Proportionality for Constrained Public Decisions
Julian Chingoma Umberto Grandi Arianna Novaro





 
    
            
       
       
      
      

       
       
media/     















same

theoremTheorem
lemma[theorem]Lemma
corollary[theorem]Corollary
proposition[theorem]Proposition
fact[theorem]Fact
definitionDefinition
exampleExample
remarkRemark


 
 
 

























plain


myexExample 
example▵
namedexample[1][][#1]▵

fancy
empty
   


[LO]Proportionality for Constrained Public Decisions




  







Proportionality for Constrained Public Decisions





    
  Julian Chingoma

  ILLC 

  University of Amsterdam 

  Amsterdam, The Netherlands

   Umberto Grandi 

  IRIT 

  Univeristé Toulouse Capitole 

  Toulouse, France

  Arianna Novaro

  CES 

  Université Paris 1 Panthéon-Sorbonne 

  Paris, France


    July 2024
=================================================================================================================================================================================================================================================================




§ ABSTRACT 
We study situations where a group of voters need to take a collective decision over a number of public issues, with the goal of getting a result that reflects the voters’ opinions in a proportional manner. Our focus is on interconnected public decisions, where the decision on one or more issues has repercussions on the acceptance or rejection of other public issues in the agenda. We show that the adaptations of classical justified-representation axioms to this enriched setting are always satisfiable only for restricted classes of public agendas. However, the use of suitably adapted well-known decision rules on a class of quite expressive constraints, yields proportionality guarantees that match these justified-representation properties in an approximate sense. We also identify another path to achieving proportionality via an adaptation of the notion of priceability.






§ INTRODUCTION



In many situations of collective decision-making, a group of voters is presented with a set of issues for which they are expected to make a binary choice: typically, deciding to either accept or reject each issue. 
This setting has recently been studied under the name of public decisions <cit.> and it is of particular interest due to the real-world scenarios captured by it. Notable examples include: instances of multiple referenda where the public vote directly on the resolution of political issues; group activity planning, where a group of individuals are to choose, as a collective, the activities that the entire group shall partake in; and committee elections, where a set of candidates are in the running for multiple positions on a committee and a group of decision-makers must select the committee members <cit.>. 

Given the collective nature of the problem, one of the natural desiderata is that the outcome represents a fair compromise for the participating voters. 
Among the numerous possible interpretations of fairness is the one captured by the notion of proportional representation. Proportionality features prominently in many collective choice settings such as that of apportionment <cit.> and the aforementioned committee elections <cit.> while being introduced to richer social-choice models such as that of participatory budgeting (PB) <cit.>. Indeed, even when zooming in on the public decisions task, the goal of producing collective outcomes that proportionally reflect the opinions of the voter population has been drawing increasing attention in recent years <cit.>. 
However, a component that has so far not received much attention in this growing literature on proportionality

is the presence of constraints that restrict the possible outcomes that can be returned. In this paper, we focus on answering the question of what one may do when outcomes that would satisfy classical proportionality axioms—and thus be considered fair outcomes—are no longer feasible due to the presence of constraints. 

When examining real-world examples of the public-decision model, there are many scenarios where enriching the model with constraints fits naturally: in the case of participatory budgeting, the implementation of one project may be conditional on the acceptance (or rejection) of another; diversity constraints applied to the committee election problem that determine the number of individuals with certain characteristics that may be accepted/rejected; or when selecting the features of some product, only certain feature combinations represent affordable options. 

In tackling our task, we build on existing notions of proportionality that have been posed for less rich models and tailor them for the challenges that comes with the existence of constraints. 
Naturally, this leads us to also consider constrained versions of collective decision rules proposed in the literature and to investigate the extent to which they meet the requirements of our novel constraint-aware notions of proportionality.



Related work.
We begin by noting that our constrained public-decision model closely resembles that of judgment aggregation and it also naturally fits into the area of collective decisions in combinatorial domains (see <cit.> and <cit.> for general introductions to these two topics, respectively). 

Most relevant to our paper is the recent work conducted on fairness in the context of public decisions without constraints <cit.>. <cit.> focused on individually proportional outcomes, thus, our work more closely aligns with that of <cit.> and <cit.> who adapt the notion of justified representation <cit.> from the literature of multiwinner voting (MWV) <cit.>. Moreover, proportionality has also been studied in models of sequential decision-making that are relevant to our own as they can be seen as generalisations of the public-decision model without constraints <cit.>. Amongst these sequential decision-making papers, those of <cit.> and <cit.> relate to our work the most as they also implement justified-representation notions. More recently, <cit.> studied proportionality for a general social-choice model that allows for the modelling of both the unconstrained and constrained versions of the public-decision model. By focusing on the latter, we explore properties that are specifically made for this setting, which in turn allows us to define, and subsequently conduct an analysis of, constrained public-decision rules that are not touched upon by <cit.>. Thus, our results complement their work by showing further possibilities, and also limitations, for proportionality within this constrained public-decision model. We also highlight work by <cit.> who adapted justified representation for the MWV model with arbitrary constraints instead of our focus on the public-decision model. This leads us towards differing approaches in adapting justified representation for constraints and also, analysing quite different rules. 

In related fields, previous work studied proportionality in various models that differ from the constrained public-decision model but features collective choices on interconnected propositions: the belief merging setting <cit.>, interdependent binary issues via conditional ballots <cit.>, and approval-based shortlisting with constraints (presented in a model of judgment aggregation) <cit.>.


Contribution.
We study the extent to which proportionality can be ensured constrained public-decision setting. First, we introduce the notion of feasible group deviations as a building block that allows the translation of existing proportionality axioms—that are based on varying public-decision interpretations of justified representation—for this setting with constraints. 
 
For each of our axioms, we show that although it is challenging to satisfy these properties in general constrained instances, when one hones in on a restricted—yet highly expressive—class of constraints, we can achieve proportionality guarantees that represent approximations of the  desirable justified-representation axioms. 
In doing so, we also define novel adaptations of recently studied decision rules to our public-decision setting with constraints, namely the method of equal shares (MES) and the MeCorA rule. Finally, we adapt the priceability notion from the MWV literature, which provides another promising route to introduce proportionality into public decisions under constraints.


Paper outline. We begin by detailing the constrained public-decision model in Section <ref>. We continue with Section <ref> where we discuss two known ways in which justified representation is formalised for public decisions, and also present the notion of deviating groups. Then each of sections <ref> and <ref> deal with a particular public-decision interpretation of justified representation. Before concluding in Section <ref>, we deal wit our constrained version of the priceability axiom in Section <ref>. Note that all omitted proofs can be found as part of the supplementary material.





§ THE MODEL



A finite set of n voters N = {1,…,n} has to take a collective decision on a finite set of m binary issues = {a_1,…,a_m}. It is typical in the public decisions setting to consider there only being two available decisions per issue but we instead adopt the following, more general setup. 
Each issue a_t∈ is associated with a finite set of alternatives called a domain D_t = {d_t^1,d_t^2,…}⊆ X where |D_t| ≥ 2 holds for all t∈[m]. The design decision of going beyond binary issues is motivated by the wider real-life applicability of this model when more than two alternatives are possible for each issue. 

Each voter i∈ N submits a ballot b⃗_i = (b⃗_i^1,…,b⃗_i^m) ∈ D_1×…× D_m 
where b⃗_i^t = d_t^c indicates that voter i chooses the decision d_t^c for the issue issue a_t. 

A profile B = (b⃗_1,…,b⃗_n) ∈ (D_1×…× D_m)^n is a vector of the n voters' ballots. An outcome w⃗ = (w_1,…,w_m) ∈ D_1×…× D_m is then a vector providing a decision for every issue at stake. 

We focus on situations where some constraints limit the set of possible collective outcomes: we denote by ⊆ D_1×…× D_m the set of feasible outcomes. We write (B, ) to denote an election instance. By a slight abuse of notation we also refer to  as the constraint, and thus, we refer to elections instances where = D_1×…× D_m as unconstrained election instances. [Note that while we work formally with the constraint being an enumeration of all feasible outcomes, in practice, it is often possible to represent the set of feasible outcomes in more concise forms—via the use of formulas of propositional logic, for example—to help with parsing said constraint and/or speed up computation by exploiting the constraint's representation structure.]

Note that voter ballots need not be consistent with the constraints, i.e., for an election instance (B, ), we do not require that b⃗_i∈ for all voters i∈ N.[This assumption takes our model closer to the particular model of judgment aggregation where the constraints on the output may differ from the constraints imposed on the the voters' input judgments <cit.>.] 


     While not common in work done in the related judgment aggregation model, our assumption that voters ballots need not correspond to feasible outcomes is common in other settings of social choice. In multiwinner voting, voters can approve more candidates than the committee target size while in participatory budgeting, the sum of the costs of a voter's approved projects may exceed the instance's budget. For our setting, we argue that this approach helps capture real-world, constrained decision-making scenarios where either the constraint is uncertain when voters submit their ballots, or possibly, the voting process becomes more burdensome for voters as they attempt to create ballots with respect to a (possibly difficult to understand) constraint. For example, consider a group of friends deciding on the travel destinations of their shared holiday across the world, visiting one country in each continent. On a booking platform, there are a certain number of locations that can be selected per continent such as: Amsterdam, Paris and Vienna in Europe; Mexico City and Toronto in North America; Cairo, Nairobi and Cape Town in Africa; and so on. Each friend has a preferred combination of cities and their collective itinerary is subject to factors such as their travel budget or the available flight connections between cities. However, as flight costs and connections may change significantly on a day-to-day basis, it may be unclear which combination of cities are affordable.  Therefore, it is not reasonable to impose the requirement, by default that is, that voter ballots are constraint-consistent.


If needed, we explicitly state when we pivot from this assumption and require that voter ballots be constraint-consistent. At times, we shall restrict ourselves to  election instances where D_t = {0,1} holds for every issue a_t. We refer to such cases as binary election instances. When necessary, we explicitly state whether any result hinges on the restriction to binary instances. Given an outcome w⃗ for a binary instance, the vector w⃗̅⃗ = (w̅_1,…,w̅_m) is such that w̅_t = 1-w_t for all issues a_t∈.

Now, consider an outcome w⃗, a set of issues S⊆ and some vector v⃗ = (1,…,v_m)∈ D_1×…× D_m (that can be interpreted as either an outcome or voter's ballot). We write w⃗Sv⃗ = (w_1',…,w_m') where w_t' = w_t for all issues a_t∈∖S and w_t' = v_t for all issues a_j∈ S. In other words, w⃗Sv⃗ is the resultant vector of updating outcome w⃗'s decisions on the issues in S by fixing them to those of vector v⃗. 
For a given issue a_t ∈ and a decision d∈ D_t, we use N(a_t,d) = {i∈ N |b⃗_i^t = d} to denote the set of voters that agree with decision d on issue a_t. 
Given two vectors v⃗, v⃗' ∈ D_1×…× D_m, we denote the agreement between them by v⃗v⃗' = {a_t∈| v_t = v_t'}. Then, the satisfaction that a voter i obtains from an outcome w⃗ corresponds to iw⃗ = |b⃗_iw⃗|, i.e., the number of decisions on which the voter i is in agreement with outcome w⃗.





§ PROPORTIONALITY VIA JUSTIFIED REPRESENTATION



This section starts with the observation that classical notions of proportionality fall short when considering interconnected decisions (in the upcoming Example <ref>), and then follows with our proposed generalisations of such axioms that deal with constraints.





Ideally, when looking to make a proportional collective choice, we would like to meet the following criteria: a group of similarly-minded voters that is an α fraction of the population should have their opinions reflected in an α fraction of the m issues. We wish to define an axiom for our model that captures this idea within our richer framework. 

In the setting of multiwinner voting, this is formally captured with the justified representation axioms with one of the most widely studied being extended justified representation (EJR) <cit.>. Now, when being studied in the setting of public decisions, there are two different adaptations that have been studied and we shall look at both. One approach intuitively states that `a group of voters that agree on a set of issues T and represent an α fraction of the voter population, should control a α· |T| number of the total issues in ' <cit.>. We refer to it as agreement-EJR.

This approach differs from the following that is a more faithful translation of the EJR from multiwinner voting: `a group of voters that agree on, and represent, an α fraction of the issues, and voter population, respectively, should control α· m of the issues in ' <cit.>. The requirements on the voter groups that is present in the latter approach are captured by the notion of cohesiveness and so we refer to this version of EJR as cohesiveness-EJR. Observe that cohesiveness-EJR is stronger than, and implies, agreement-EJR.

Meeting the ideal outlined by both of these notions is not easy in our setting as the constraint  could rule out a seemingly fair outcome from the onset.


Suppose there are two issues = {a_1, a_2} with constraint = {(1,0),(0,1)}. Then suppose there are two voters N = {1,2} with ballots b⃗_1 = (1,0), and b⃗_2 = (0,1) (note that voters 1 and 2 are both, on their own, cohesive groups). Here, both aforementioned EJR interpretations require each voter to obtain at least 1 in satisfaction, i.e., deciding half of the two issues at hand. However, there exists no feasible outcome that provides agreement-EJR or cohesiveness-EJR as one voter i∈{1,2} will have satisfaction iw⃗ = 0 for any outcome w⃗∈.


Example <ref> makes clear an issue that we must take into account when defining proportionality properties when there are constraints. That is, a voter group that is an α fraction of the population may lay claim to deciding an α fraction of the issues, but in doing so, they may be resolving, or influencing the decision on, a larger portion of the issues than they are entitled to.

In doing so, we look for meaningful ways to identify, given an outcome  w⃗, those voter groups that are underrepresented and can justifiably complain at the selection of outcome w⃗. 

The latter is formalised by the following definition which we use to identify the voter group whose displeasure is justified. Specifically, these are groups that can propose an alternative, feasible outcome w⃗^* that yields greater satisfaction for each group member.


Given election instance (B,) and outcome w⃗∈, a set of voters N'⊆ N has an (S,w⃗)-deviation if ∅≠ S ⊆ is a set of issues such that all of the following hold:
    
        
  * S ⊆b⃗_ib⃗_j for all  i,j∈ N' (the voters agree on the decisions on all issues in S).
        
  * S⊆∖b⃗_iw⃗ for all i∈ N' 
        
        (the voters disagree with outcome w⃗'s decisions on all issues in S).
        
  * w⃗Sb⃗_i∈ for all i∈ N' (fixing outcome w⃗'s decisions on issues in S, so as to agree with the voters in N', induces a feasible outcome).
    


Intuitively, given an outcome w⃗, a voter group having an (S,w⃗)-deviation indicates the presence of another feasible outcome w⃗^*≠w⃗ where every group member would be better off. Thus, our goal in providing a fair outcome reduces to finding an outcome where every group of voters that has an (S,w⃗)-deviation is sufficiently represented.

We shall use this (S,w⃗)-deviation notion to convert proportionality axioms from unconstrained settings to axioms that deal with constraints. But first, we look at the following computational question associated with (S,w⃗)-deviations: given an election instance (B,) and an outcome w⃗∈, the problem is to find all groups of voters with an (S,w⃗)-deviation.


    Given an election instance (B,) and an outcome w⃗∈, there exists an algorithm that finds all groups of voters N' such that there exists an S⊆ with N' having an (S,w⃗)-deviation, that runs in O(||^2mn) time.



    Take (B,) and outcome w⃗∈. Consider the following algorithm that operates in || rounds, assessing an outcome w⃗∈ in each round (with each outcome assessed once throughout): at each round for an outcome w⃗∈, iterate through all other outcomes w⃗^*≠w⃗∈; fix S to be the issues that w⃗ and w⃗^* disagree on; in at most mn steps, it can be checked if there is a set of voters 
    that agree with w⃗^* on all issues in S which verifies the existence of a 
    voter group N' with an (S,w⃗)-deviation; keep track of all such groups N'; if all outcomes have been assessed, terminate, otherwise, move to the next outcome. This algorithm takes O(||^2mn) time to complete in the worst case, which is polynomial in the input size given our assumptions. 


We offer the following remark in regards to the nature of Proposition <ref>.


 Proposition <ref> can be seen as positive whenever the constraint  under consideration is `not too large'. Such an assumption is reasonable for many real-life examples. Consider the quite general, collective task of selecting the features of some product. Our running example of the logo design is an instance of this. Other applicable scenarios include choosing the technical features of a shared computer or the items to be placed in an organisation's common area. In many cases, factors such as a limited budget (or limited space in the case of the common area) may result in very few feature combinations being feasible for said product. These are natural scenarios where we may encounter a `small' constraint (according to our definition) with respect to the number of issues at hand and the size of their domains.   


Our goal is to answer the following question: how much representation can we guarantee from some outcome w⃗, to a group of voters that has an (S,w⃗)-deviation and that qualifies as underrepresented? 





§ JUSTIFIED REPRESENTATION WITH COHESIVENESS



 We now propose the following adaptations of cohesiveness-EJR to public decisions with constraints. To adapt cohesiveness-EJR, we adapt cohesiveness from multiwinner voting in a similar manner as done by <cit.>. We say that a voter group is T-agreeing for some set of issues T⊆ if T ⊆b⃗_ib⃗_j holds for all voters i,j∈ N' and then we define cohesiveness as the following:


For a set of issues T⊆, we say that a set of voters N'⊆ N is T-cohesive if N' is T-agreeing and it holds that |N'| ≥ |T|·n/m.


Using T-cohesiveness, we can define EJR for public decisions with constraints <cit.>.


Given an election (B, ), an outcome w⃗ provides   if for every T-cohesive group of voters N'⊆ N for some T⊆ with an (S,w⃗)-deviation for some S⊆ T, there exists a voter i∈ N' such that iw⃗≥ |T|.


Intuitively,  deems an outcome to be unfair if there exists a T-cohesive voter group with (i) none of its group members having at least |T| in satisfaction, and (ii) `flipping' outcome w⃗'s decisions on some of the issues in T leads to some other feasible outcome.

We have the following result that can be interpreted as positive when the size of  is `not too large'.


 Given an election instance (B,) and an outcome w⃗∈, there exists an algorithm that decides in O((max_t∈[m]|D_t|)^m||^3mn) time whether outcome w⃗ provides . 



        From Proposition <ref> we know that, given an outcome w⃗, we can find all groups with some (S,w⃗)-deviation for some S⊆ in O(||^2mn) time. There can be at most (max_t∈[m]|D_t|)^m(||-1) such groups (recall that max_t∈[m]|D_t| is the maximal size of any issue's domain). Then, for each group N' with an (S,w⃗)-deviation, we can check their size in polynomial time and thus verify whether they are a T-cohesive with S⊆ T, and if so, we can check if there exists any voter i∈ N' with iw⃗ > |T|. 


Now, <cit.> have already shown that, in general, cohesiveness-EJR is not always satisfiable in their sequential decisions model. This negative result carries over to the unconstrained public-decision setting. Although we shall, in the sections to follow, analyse the extent to which we can achieve positive results with cohesiveness-EJR in our constrained setting, this negative result motivates the study of the following weaker axiom—which is an adaptation of the multiwinner JR axiom—that can always be satisfied in the public-decision setting without constraints <cit.>.



    Given an election instance (B, ), an outcome w⃗ provides  if for every T-cohesive group of voters N'⊆ N for some T⊆ with an (S,w⃗)-deviation for some S⊆ T where |S| = |T| = 1, there exists a voter i∈ N' such that iw⃗≥ 1.


Unfortunately, when considering arbitrary constraints, even  cannot always be achieved. Note that this even holds for binary election instances.


There exists an election instance where no outcome provides .




Consider the binary election instance with issues = {a_1,a_2} and a constraint = {(0,1),(0,0)}. Suppose that N = {1,2}, where b⃗_1 = (1,1) and b⃗_2 = (1,0). Note that for both outcomes w⃗∈, one voter will have satisfaction of 0 while being a T-cohesive group with an (S,w⃗)-deviation for |S| = |T| = 1. As each voter is half of the population, they may `flip' issue a_2 to deviate towards the alternative feasible outcome, which provides them greater satisfaction than the current one.


Let us now restrict the constraints that we consider. To do so, we introduce notation for the fixed decisions for a set of outcomes C ⊆, which are the issues in  whose decisions are equivalent across all the outcomes in C. For a set of outcomes C ⊆, we represent this as:

    _fix(C) = {a_t∈|there exists some d∈ D_t such that  w_t = d   for all w⃗∈ C}.




  We say a constraint  has the NFD property if _fix() = ∅ holds for .  



At first glance, this NFD property seems more than a reasonable requirement but rather a property that should be assumed to hold by default. We argue however, that by doing so, we will neglect election instances where decisions that are fixed from the get-go may contribute to the satisfaction of voters and, specifically for our goal, these fixed decisions may aid in giving the voters their fair, proportional representation. It is this reason, why we did not restrict ourselves to election instances where the NFD property holds.
 

Now, we show that with the NFD property, the  axiom can always be provided, albeit only for `small' election instances. We begin with cases where the number of feasible outcomes is limited to two.


For election instances (B, ) with || = 2 where  has the NFD property,  can always be satisfied.



    Take some feasible outcome w⃗∈. Observe that when || = 2, if property NFD holds, then the two feasible outcomes differ on the decisions of all issues. Thus, it is only possible for T-cohesive groups with an (S,w⃗)-deviation for |S| ≤ |T| = m to have an allowable deviation from w⃗ to the only other feasible outcome. This means only the entire voter population have the potential to deviate. And if such deviation to w⃗' exists, then outcome w⃗' sufficiently represents the entire voter population.


Now we ask the following: can we guarantee  when m ≤ 3? We answer in the positive when we restrict ourselves to  binary election instances.


   For  binary election instances (B, ) with m ≤ 3 where the constraint  has the NFD property,  can always be provided.


 The case for m=1 is trivially satisfied so we present the proof as two separate cases where the number of issues is either m=2 or m=3.

Case m = 2:  Observe that for two issues (i.e., m = 2) there are 7 possible constraints  satisfying the NFD property. Take one such  and a feasible outcome w⃗ = (d_x,d_y) ∈ where d_x,d_y∈{0,1}. Let us consider now groups of voters with an (S, w⃗)-deviation over some set of issues S⊆ T who are witness to a violation of . As m = 2, the agreement among voters and the deviation may concern at most two issues, i.e., |S|, |T| ∈{1,2}. 

First, consider |T| = 1. Since |S| ≤ |T| and S ≠∅, we have |S| = 1 for any T-cohesive group (which is thus of size |N'| ≥n/2) wishing to perform a (S, w⃗)-deviation from w⃗ to some other feasible outcome w⃗'∈. If there is a voter i ∈ N' such that iw⃗≥ 1, group N' would be sufficiently satisfied—therefore,  is ensured and we are done. Otherwise, we have that all i ∈ N' are unanimous and that iw⃗ = 0; hence, b⃗_i = (1-d_x, 1-d_y) for all i ∈ N'. There are two possible outcomes (deviations) that differ from w⃗ in only one coordinate. If neither outcome is in , then no feasible deviation is possible for N' and we are done. Otherwise, assume without loss of generality that w⃗' = (1-d_x, d_y) ∈. Now, if there is a voter i ∈ N ∖ N' such that iw⃗≥ 1, then we are done (as the group N ∖ N' would be sufficiently satisfied if it were T-cohesive for |T| = 1). Else, it means that all voters j ∈ N ∖ N' are unanimous on ballot b⃗_j = (d_x, 1-d_y). But then, since  satisfies property NFD, there exists some outcome w⃗”∈ such that w⃗”_2 = 1-d_y. Then, iw⃗”≥ 1 for all i ∈ N and no deviation is possible. 
    
Finally, consider |T| = m = 2. In order for a group N' that is T-cohesive to have a (S,w⃗)-deviation for |S| ≤ |T|, it must be the case that N' = N, and iw⃗ = 0 for all i ∈ N. By property NFD, there must be some outcome w⃗' ≠w⃗∈, and thus iw⃗'≥ 1 for all i ∈ N.


Case m = 3: Let (B, ) be an election instance satisfying the conditions in the statement. We now reason on the existence of possible T-cohesive groups that are a witness to the violation of , for each possible size 1 ≤ |T| ≤ 3 of the set T. 

For |T|=1, suppose by contradiction that for all w⃗∈, there is some voter group N' such that |N'|≥n/3 and each voter in N' has satisfaction of 0. Thus, for all voters i ∈ N' we have b⃗_i= w⃗̅⃗. Moreover, for a T-cohesive group with an (S,w⃗)-deviation for |S| = |T| = 1 to be possible, there has to exist a w⃗'∈ whose decisions differ from w⃗ in exactly one issue, i.e., w⃗w⃗' = 2. To fit all these disjoint T-cohesive groups for |T| = 1, one for each outcome in , it must be that n≥ ||·n/3, hence ||≤ 3 must hold. If || = 1, the NFD property cannot be met. If || = 2, then the two feasible outcomes cannot differ in the decision of only one issue while also satisfying the NFD property. For ||=3, to get a T-cohesive voter group with an (S,w⃗)-deviation for |S| = |T| = 1 at every w⃗∈, the three feasible outcomes must differ by at most one decision, contradicting the NFD property.

For |T| = 2, we only consider (S,w⃗)-deviations from a T-cohesive group N' with |S| ∈{1,2}. Consider the case of |S|=1. W.l.o.g., assume w⃗ = (0,0,0) and assume that there exists a T-cohesive group N' (where |N'| ≥ n·2/3) with every voter having satisfaction < 2, with an (S,w⃗)-deviation towards outcome, e.g., w⃗' = (1,0,0). The case for (0,1,0) is similar. Now one of the N' voters has satisfaction of 2. If n/3 voters now have an allowable deviation (satisfaction of 0 with the current outcome), by NFD one of the outcomes {010, 111, 011, 110} must be in . Observe that any of them provides satisfaction of at least 2 to all cohesive groups of |T| = 2, and at least satisfaction 1 to every cohesive group of |T| =1. Now we look at the case for |S| = 2. W.l.o.g., consider the outcome w⃗ = (0,0,0) and assume that there exists a T-cohesive group N' (where |N'| ≥ n·2/3) with an (S,w⃗)-deviation towards outcome, e.g., w⃗' = (1,1,0). Thus, there is some voter i in N' with satisfaction iw⃗'≥2. At this point, the only possible further (S,w⃗)-deviation could arise for |S| = 1 in case there are n/3 voters in N∖N' each have a satisfaction of 0 for w⃗', i.e., each has the ballot (0,0,1) and either one of the outcomes in {(1,0,0),(0,1,0),(1,1,1)} is in . Now take instead that iw⃗' = 2 and consider two cases where either voter i agrees or disagrees  with the voters in N∖N' on the decision of issue a_3. First, assume that voter i∈ N' agrees with the voters in N∖N' on issue a_3 (so voter i had the ballot b⃗_i = (1,1,1)). Then if either (0,1,1)∈ or (1,1,1)∈ holds, we have that  is provided. And if (0,0,1)∈ holds, then voters in N∖N' are entirely satisfied and the voters in N' may only have an (S,w⃗)-deviation for |S| ≤ |T| = 2 if either (0,1,1)∈ or (1,1,1)∈ holds (as they only `flip' issues they disagree with), which means that  is provided. In the second case, assume that voter i∈ N' disagrees with the voters in N∖N' on issue a_3 and so, voter i had the ballot b⃗_i = (1,1,0). This means that iw⃗' = 3 holds, hence, any outcome that the voters in N∖N' propose given they have an (S,w⃗)-deviation for |S| = 1, would be one that provides . 

Finally, a T-cohesive group for |T| = 3 implies a unanimous profile; if there exists an allowable (S,w⃗)-deviation for |S| ≤ |T| = 3, then the outcome in  maximising the sum of agreement with the profile provides .


We leave it open whether the above result holds if we do not restrict our view to binary election instances. Unfortunately, the good news ends there as we provide a example showing that  cannot be guaranteed when do not have m ≤ 3 (even for binary election instances).


    There exists an election instance (B, ) where m>3 and the constraint  has the NFD property but no  outcome exists.



    Suppose there is a binary election instance with a constraint = {w⃗_1, w⃗_2, w⃗_3, w⃗_4} for m=8 such that w⃗_1 = (0,0,0,…,0), w⃗_2 = (0,0,1,…,1), w⃗_3 = (1,1,1,…,1), w⃗_4 = (1,1,0,…,0). Consider now a profile of four voters where b⃗_i = w⃗_i. Given that m=8, note that for every outcome w⃗∈, there exists some voter that deserves 2 in satisfaction by being T-cohesive for |T| = 2 with an (S,w⃗)-deviation but with zero in satisfaction. And by , such a voter would be entitled to at least 1 in satisfaction, so there is no outcome in  that provides .


We now turn our attention towards a weakening of  that takes inspiration from EJR-1 studied in the context of participatory budgeting.


    Given an election (B, ), an outcome w⃗ provides  -1 if for every T-cohesive group of voters N'⊆ N for some T⊆ with an (S,w⃗)-deviation for some S⊆ T, there exists a voter i∈ N' such that iw⃗≥ |T| -1.


As  implies -1, the results of Propositions <ref> and <ref> immediately apply to -1.


    For binary election instances (B, ) with || = 2 where the constraint  has the NFD property, -1 can always be provided.



    For binary election instances (B, ) with m ≤ 3 where the constraint  has the NFD property, -1 can always be provided.


Note that for the computational result for  in Proposition <ref>, a simple alteration of the proof given for Proposition <ref> (replacing the value |T| with |T|-1 in the final satisfaction check) yields a corresponding computational result for -1. 


 Given an election instance (B,) and an outcome w⃗∈, there exists an algorithm that decides in O((max_t∈[m]|D_t|)^m||^3mn) time whether outcome w⃗ provides -1. 


For the result of stating that  can be provided when m=2 given that NFD holds (see Proposition <ref>), we can show something stronger for -1 by dropping the assumption that the NFD property holds.


        For election instances (B, ) with m = 2, -1 can always be provided.



Consider an election over two issues, where a T-cohesive group of voters has an (S,w⃗)-deviation for some outcome w⃗, as per Definition <ref>. Observe that, when m = 2, (S,w⃗)-deviation are only possible for |S|∈{1,2}. 
Take a T-cohesive group N' for |T| = 1 with an (S,w⃗)-deviation from w⃗ to some other feasible outcome w⃗'∈. Even if iw⃗ = 0 for every voter i ∈ N', we have iw⃗≥ |T| - 1 = 1-1 = 0, and thus -1 is satisfied.
Take now a T-cohesive group N' for |T| = 2: for them to deviate, it must be the case that N' = N, and iw⃗ = 0 for all i ∈ N. If they have an (S,w⃗)-deviation for |S| = |T| = 2, the outcome w⃗'⃗ they wish to deviate to must increase the satisfaction of each voter by at least 1, which thus satisfies iw⃗≥ |T| - 1 = 2-1 = 1, and thus -1.


Can we show that an outcome providing -1 always exists when there are more than three issues, unlike for ? Unfortunately, this is not the case, even assuming property NFD, as the same counterexample used to prove Proposition <ref> yields the following (so also for binary election instances).


     There exists an election instance (B, ) where m > 3 and the constraint  has the NFD property but there exists no outcome that provides -1.




We demonstrate that the challenge of satisfying -1 lies in the constraints. To do so, we show that in the setting without constraints, it is always possible to find an outcome that provides -1. To do so, we define the constrained version of MES that has been studied for the public-decision setting without constraints. Our adaptation allows for the prices associated with fixing the outcome's decisions on issues to vary. This contrasts with the unconstrained MES that fixes the prices of every issue's decision to n from the onset. And this pricing is determined by a particular pricing type λ. 


The rule runs for at most m rounds. Each voter has a budget of m. In every round, for every undecided issue a_t in a partial outcome w⃗^*, we identify those issue-decision pairs (a_t,d) where fixing some decision d∈ D_t on issue a_t allows for a feasible outcome to be returned in future rounds. If no such issue-decision pair exists, then the rule stops. Otherwise, for every such pair (a_t,d), we calculate the minimum value for ρ_(a_t,d)  such that if each voter in N(a_t,d) were to pay either ρ_(a_t,d) or the remainder of their budget, then these voters could afford to pay the price λ(a_t,d) (determined by the pricing type λ). If there exists no such value for ρ_(a_t,d), then we say that the issue-decision pair (a_t,d) is not affordable in round, and if in a round, there are no affordable issue-decision pairs, the rule stops. 
Otherwise, we update w⃗^* by setting decision d on issue a_t for the pair (a_t,d) with a minimal value ρ_(a_t,d) (breaking ties arbitrarily, if necessary) and have each voter in N(a_t,d) either paying ρ_(a_t,d), or the rest of their budget. Note that  may terminate with not all issues being decided and we assume that all undecided issues are decided arbitrarily. 


A natural candidate for a pricing type is the standard pricing of unconstrained MES where the price for every issue-decision pair (a_t,d) is set to λ(a_t,d) = n. And with this pricing, that we refer to as unit pricing λ_unit, we can show that  satisfies -1 for unconstrained, binary elections. 


    For binary election instances, when = {0,1}^m,  with unit pricing λ_unit satisfies -1.



Take an outcome w⃗ returned by  with unit pricing λ_unit and consider a T-cohesive group of voters N'. Let us assume that for every voter i∈ N', it holds that iw⃗ < |T|-1 and then set ℓ = |T|-1. So to conclude the run of , each voter in N' paid for at most ℓ-1 = |T|-2 issues. 

    Now, assume that the voters in N' paid at most m/(ℓ + 1) for any decision on an issue. We know that each voter has at least the following funds remaining at that moment:

    m - (ℓ - 1)m/ℓ + 1  = 2m/ℓ + 1 = 2m/|T|≥2n/|N'|.


 The last step follows from the group N' being . So now we know that the voters in N' hold at least 2n in funds when some at the end of 's run. Thus, we know that at least two issues have not been funded and for at least one of these two issues, at least half of N' agree on the decision of this issue (as the election instance is binary) and they hold enough funds to pay for it, hence, we have a contradiction to  terminating. 

Now, assume that some voter i in N' paid more than m/(ℓ + 1) for a decision on an issue. Since we know that at the end of 's execution, each voter in N' paid for at most ℓ-1 = |T|-2 issues, then at the round r that voter i paid more than m/(ℓ + 1) for an issue's decision, the voters in N' collectively held at least 2n in funds. Since at least two issues in were not funded, there exists some issue that could have been paid for in round r, where voters each pay m/(ℓ + 1), contradicting the fact that voter i paid more than m/(ℓ + 1) in round r. 
So, we have that this group of voters N' cannot exist and that  satisfies -1.


This result provides us with an axiom `close to' EJR that we know is always satisfiable when the issues have size-two domains and there are no constraints.




§ JUSTIFIED REPRESENTATION WITH AGREEMENT


Given the mostly negative results regarding the cohesiveness-EJR notion, we move on to justified representation based on agreement. We justify this move as the notion based on agreement is weaker and yields more positive results in the unconstrained setting. Thus, by assessing it here, we are able to establish a baseline of what can be achieved in terms of EJR-like proportionality guarantees in our constrained model. First, we formalise agreement-based EJR with the following axiom.


    Given an election (B, ), an outcome w⃗ provides  if for every T-agreeing group of voters N'⊆ N for some T⊆ with an (S,w⃗)-deviation for some S⊆ T with |S|≤ |T|·|N'|/n, there exists a voter i∈ N' such that iw⃗≥|N'|/n·|T|.


Now, in more unfortunate news, we find that  is not always satisfiable in general. In fact, the counterexample of Proposition <ref> suffices to show this as each voter requires at least 1 in satisfaction for to  to be satisfied. 


    There exists an election instance where no outcome provides  (even when the NFD property holds for ).


We now focus on a particular class of constraints as we import agreement-EJR into our setting. Specifically, we consider a class that allows us to talk about how restrictive, and thus how costly, the fixing of a particular issue-decision pair is. 

Akin to work by <cit.>, we consider constraints  that can be equivalently expressed as a set of implications Imp_, where each implication in Imp_ is a propositional formula with the following form: ℓ_(a_x,d_x)→ℓ_(a_y,d_y). This class of constraints allows us, for instance, to express simple dependencies and conflicts such as `selecting x means that we must select y' and `selecting x means that y cannot be selected', respectively. These constraints correspond to propositional logic formulas in 2CNF. 


Take a set of issues = {a,b,c,d,e} for a binary election instance. Here is an example of an implication set:

        
  * Imp_ = {(a,1) → (b,1),  (c,1) → (e,0), (d,1) → (e,0)}. Here, accepting a means that b must also be accepted while accepting either c or d requires the rejection of e.



Given a (possibly partial) outcome w⃗∈ and the set Imp_, we construct a directed outcome implication graph G_w⃗ = ⟨ H,E⟩ where H = ⋃_a_t∈{(a_t,d)| d∈ D_t} 
as follows: 

    
  * Add the edge ((a_x,d_x), (a_y,d_y)) to E if ℓ_(a_x,d_x)→ℓ_(a_y,d_y)∈Imp_  and w_y≠ d_y; 
    
  * Add the edge ((a_y,d_y^*), (a_x,d_x^*)) for all d_y^*≠ d_y∈ D_y,d_x^*≠ d_x∈ D_x to E if ℓ_(a_x,d_x)→ℓ_(a_y,d_y)∈Imp_  and w_x = d_x. 

Given such a graph G_w⃗ for an outcome w⃗, we use G_w⃗(a_x,d_x) to denote the set of all vertices that belong to some path in G_w⃗ having vertex (a_x,d_x) as the source (note that G_w⃗(a_x,d_x) excludes (a_x,d_x)).


Consider a binary election instance and take a set of issues = {a_1,a_2,a_3,a_4} and the implication set Imp_ = {(a_1,1) → (a_2,1), (a_1,1) → (a_3,1), (a_2,1) → (a_4,1)} of some constraint . Consider the outcome implication graph for w⃗_1 = (0,0,0,0) (vertices with no adjacent edges are omitted for readability):


		[anchor=center]
			[name = A1] at (-1, 2) (a_1,1);
            [name = C1] at (1, 1) (a_3,1);
            [name = B1] at (1, 2) (a_2,1);
            [name = D1] at (3, 2) (a_4,1);

			[->] (A1) edge (B1);
            [->] (A1) edge (C1);
			[->] (B1) edge (D1);
		



Then, we have G_w⃗(a_1,1) = {(a_2,1), (a_3,1), (a_4,1)} and therefore |G_w⃗(a_1,1)| = 3.


Thus, for an issue-decision pair (a_x, d_x), we can count the number of affected issues in setting a decision d_x for the issue a_x. This leads us to the following class of constraints.



Take some constraint  expressible as a set of implications Imp_. For some positive integer k≥ 2, we say that  is k-restrictive if for every outcome w⃗∈, it holds that:

    max{|G_w⃗(a_x,d_x)| |  (a_x,d_x)∈⋃_a_t∈{(a_t,d)| d∈ D_t}} = k-1

where G_w⃗ is the outcome implication graph constructed for outcome w⃗ and the implication set Imp_.



Intuitively, with a k-restrictive constraint, if one were to fix/change an outcome w⃗'s decision for one issue, this would require fixing/changing w⃗'s decisions on at most k-1 other issues. So intuitively, when dealing with k-restrictive constraints, we can quantify (at least loosely speaking) how `difficult' it is to satisfy a constraint via the use of this value k. Thus, we can use this value k to account for the constraint's difficulty when designing proportionality axioms.

Before assessing how k-restrictive constraints affect our goal of providing proportionality, we touch on the computational complexity of checking, for some constraint , whether there exists a set of implications Imp_ that is equivalent to . For the case of binary elections, this problem been studied under the name of Inverse Satisfiablility and it has been shown that for formulas in 2CNF, the problem is in  <cit.>. So in the remainder of the paper, when we refer to a k-restrictive constraint , we thus assume that  is expressible using an implication set Imp_. 



We now import the agreement-EJR notion and an approximate variant into our framework with constraints.


    Given an election (B, ), some α∈ (0,1] and some positive integer β, an outcome w⃗ provides α--β if for every T-agreeing group of voters N'⊆ N for some T⊆ with an (S,w⃗)-deviation for some S⊆ T with |S|≤ |T|·|N'|/n, there exists a voter i∈ N' such that iw⃗≥α·|N'|/n·|T| - β.


With this axiom, we formalise agreement-EJR to our constrained public-decision model with the presence of the multiplicative and additive factors allowing us to measure how well rules satisfy this notion even if they fall short providing the ideal representation.[Observe that we include the axiom's size requirement on the set S such that a group has an (S,w⃗)-deviation in order to prohibit considering cases such as a single voter only having an (S,w⃗)-deviation for S= while not intuitively being entitled to that much representation.] Note that for the sake of readability, when we have either α = 1 or β = 0, we omit them from the notation when referring to α--β.


 Suppose there are four issues = {a_1, a_2, a_3, a_4} and consider a constraint = {(1,1,0,0),(1,1,1,0)}. Then suppose there are two voters with ballots b⃗_1 = (1,1,1,1) and  b⃗_2 = (0,0,0,0) so each voter deserves at least 2 in satisfaction according to agreement-EJR. See that outcome w⃗ = (1,1,0,0) provides  while the outcome w⃗' = (1,1,1,0) only provides 1/2- as voter 2 only obtains 1 in satisfaction whilst having a sufficiently small (S,w⃗)-deviation for the issue a_3 (deviating to outcome w⃗). 


We now analyse  with respect to this axiom for the class of k-restrictive constraints. We say that for , the price for an issue-decision pair (a_x,d) given a partial outcome w⃗^* is λ(a_x,d) = n· (|G_w⃗^*(a_x,d)|+1) and we refer to this as a fixed pricing λ_fix.  Then we can show the following for binary election instances.


    For binary election instances (B,) where  is k-restrictive for some k,  with fixed pricing λ_fix satisfies 1/k--1.



For a binary election instance (B,) where  is k-restrictive, take an outcome w⃗ returned by  with fixed pricing λ_fix. Consider a T-agreeing voter group N'. Let us assume that for every i∈ N', it holds that iw⃗ < |N'|/nk·|T|-1 and then set ℓ = |N'|/nk·|T|-1. So to conclude , each voter i∈ N' paid for at most ℓ-1 = |N'|/nk·|T|-2 issues. Note that for a k-restrictive constraint , the maximum price  with fixed pricing λ_fix sets for any issue-decision pair is nk (as at most k issues are fixed for a  purchase). Now, assume that the voters in N' paid at most m/(ℓ + 1) for any decision on an issue. We know that each voter has at least the following funds remaining at that moment:

    m - (ℓ - 1)m/ℓ + 1  = 2m/ℓ + 1 = 2m/|N'|/kn·|T| = 2mnk/|N'||T|≥2nk/|N'|.


We now have that voter group N' holds at least 2nk in funds at the rule's end. Thus, we know that at least k issues have not been funded and for at least one of these k issues, at least half of N' agree on the decision for it (as the election is a binary instance) while having enough funds to pay for it. Hence, we have a contradiction to  terminating. 

Now, assume that some voter i∈ N' paid more than m/(ℓ + 1) for fixing an issue's decision. Since we know that at the end of 's run, each voter in N' paid for at most ℓ-1 issues, then at the round r that voter i paid more than m/(ℓ + 1), the voters group N' collectively held at least 2nk in funds. Since at least k issues in were not funded, there exists some issue that could have been paid for in round r, where voters each pay m/(ℓ + 1). This contradicts the fact that voter i paid more than m/(ℓ + 1) in round r. 
So, we have that this group of voters N' cannot exist which concludes the proof.


Towards an even more positive result, and one where we are not limited to binary election instances, we now provide an adaptation of the MeCorA rule <cit.> . In the unconstrained public-decision model, MeCorA is presented by <cit.> as an auction-style variant of MES that allows voter groups to change the decision of an issue all while increasing the price for any further change to this issue's decision. In our constrained model, groups are allowed to pay for changes to the decisions on sets of issues, as long as these changes represent a feasible deviation.
 
Take some constant ϵ > 0. Start by setting λ_t = 0 as the current price of every issue a_t∈, endow each voter i∈ N with a personal budget of m and take some arbitrary, feasible outcome w⃗∈ as the current outcome. A groups of voters can `update' the current outcome w⃗'s decisions on some issues S⊆ if the group:

    
   (i) can propose, for each issue a_t∈ S, a new price λ_t^*≥λ_t+ϵ,
    
   (ii) can afford the sum of new prices for issues in S, and
    
   (iii) has an (S,w⃗)-deviation.

 The rule then works as follows. Given a current outcome w⃗, it computes, for every non-empty S⊆, the smallest possible value ρ_(t,S) for each issue a_t∈ S such that for some N', if voters in N' each pay ρ_S = ∑_a_t∈ Sρ_(t,S) (or their remaining budget), then N' is able to `update' the decisions on every a_t∈ S as per conditions (i)-(iii). If there exists no such voter group for issues S then it sets ρ_S = ∞. 

If ρ_S = ∞ for every S⊆, the process terminates and returns the current outcome w⃗. Otherwise, it selects the set S with the lowest value ρ_S (any ties are broken arbitrarily) and does the following:

    
  * updates the current outcome w⃗'s decisions on issues in S to the decisions agreed upon by the voters with the associated (S,w⃗)-deviation,
    
  * updates the current price of every issue a_t∈ S to λ_t^*,
    
  * returns all previously spent funds to all voters who paid for the now-changed decisions on issues in S,
    
  * and finally, for each voter in N', deduct ∑_a_t∈ Sρ_(t,S) from their personal budget (or the rest of their budget).



Next, we show the representation guarantees can be achieved on instances with k-restrictive constraints via the use of modified version of MeCorA_. Moreover, we can drop the restriction to binary election instances that was key for the result of Theorem <ref>. In this MeCorA_ variant, we first partition the voter population into groups where members of each group agree on some set of issues. Then, for each group, its members may only pay to change some decisions as a collective and only on those issues that they agree on. Contrarily to MeCorA_, voter groups cannot pay to change some decisions if this leads to the group's members gaining `too much' satisfaction from the altered outcome (i.e., a voter group exceeding their proportional share of their agreed-upon issues, up to some additive factor q that parameterises the rule).


The set of the voters N is partitioned into p disjoints sets N(T_1),…,N(T_p) such that:

    
   (i) for every x∈{1,…,p}, a voter group N(T_x)⊆ N is T_x-agreeing for some T_x⊆, and
    
   (ii) for all x∈{1,…,p-1}, it holds that |N(T_x)|· |T_x| ≥ |N(T_x+1)|· |T_x+1|


As with MeCorA_, voter groups shall pay to change the decisions of some issues during the rule's execution. However, given the initial partition, during the run of Greedy MeCorA_-q, the voters in N(T_x) may only change decisions for the issues in T_x.

Moreover, if a voter group N(T_x) for some x∈{1,…,p} wishes to change some decisions at any moment during the process, this change does not lead to any voter in N(T_x) having satisfaction greater than |N(T_x)|/n· |T_x| - q with the updated outcome. Besides these two differences, the rule works exactly as MeCorA_.


Now, we can show the following for Greedy MeCorA_-q working on a k-restrictive constraint. For this result, we require the additional assumption that voter ballots represent feasible outcomes in .


For election instances (B,) where voters' ballots are consistent with the constraint  and  is k-restrictive for some k≥ 2, Greedy MeCorA_-(k-1) satisfies -(k-1).


 
Take an outcome w⃗ returned by Greedy  MeCorA_-(k-1). Assume that w⃗ does not provide -(k-1). Thus, there is a T-agreeing group N' such that iw⃗ < |N'|/n· |T| - k+1 = ℓ holds for every i∈ N'. 

Now, consider the partition of voters N(T_1),…,N(T_p) constructed by Greedy MeCorA_-(k-1) to begin its run. 

Assume first that there is some x∈{1,…,p} such that N' = N(T_x), i.e., voters N' appear in their entirety in said partition. 
We then have T= T_x. Moreover, voters in N' each contribute to at most ℓ decisions at any moment of the run of Greedy MeCorA_-(k-1), as this is the limit the rule imposes on their total satisfaction. We now consider two cases. 

Assume that the voters in N' contributed at most m/(ℓ + k - 1) to change some decisions during the rule's execution. It follows that each voter has at least the following funds remaining: m - (ℓ - 1)·m/(ℓ + k - 1)≥nmk/|N'||T|.

In this case, the voters in N' would have at least nmk/|T| in collective funds, so it follows that each distinct (S,w⃗)-deviation available to N' must cost at least nmk/|T|. As N' is T-agreeing, it must be that N' has at least a (|T| - ℓ + 1)/k many (S,w⃗)-deviations due to  being k-restrictive and as the voters' ballots are consistent with .

Now, consider the case where some voter in N' contributed more than m/(ℓ + k - 1) to change some decisions. The first time that this occurred, the change of decisions did not lead to any voter in N' obtaining a satisfaction greater than ℓ = |N'|/n· |T| - k + 1 (otherwise the rule would not allow these voters to pay for the changes). Thus, each voter in N' must have contributed to at most ℓ -1 issues before this moment. From the reasoning above, it must hold that in this moment, each voter held at least nmk/|N'||T| in funds with there being at least (|T| - ℓ + 1)/k feasible deviations available to N' and each such deviation costing at least nmk/|T|. So in both cases, for the (S,w⃗)-deviations that are present in T that voters in N' wish to make, outcome w⃗'s decisions must have been paid for by voters within the remaining voter population N∖ N'. And so, these decisions must have cost the voters in N∖ N' at least:

    nmk/|T|·(|T| - ℓ + 1/k) = nm/|T|·(|T| - |N'|/n· |T|  + k)


    > nm/|T|·(n|T| - |N'||T|/n) = m(n - |N'|).

However, voters N∖ N' have at most m(n - |N'|) in budget. Thus, the rule cannot have terminated with the voter group N' existing.

Now, assume that the group N' did not appear in their entirety within the partition N(T_1),…,N(T_p) made by Greedy MeCorA_-(k-1). This means that some voter i∈ N' is part of another voter group N(T_x) that is T_x-agreeing such that |N(T_x)|/n· |T_x| ≥N'/n· |T|. Now, recall that for each voter group N(T) in the partition, the voters in N(T) have the same satisfaction to end the rule's execution (as they only pay to flip decisions as a collective). Thus, from the arguments above, it holds for this voter i∈ N'∩ N(T_x) that iw≥|N(T_x)|/n· |T_x| - k +1≥|N'|/n· |T| - k +1, which contradicts the assumption that every voter in N' has satisfaction less than |N'|/n· |T| - k +1. 


We now offer another way towards producing proportional outcomes when using k-restrictive constraints. It is a constrained adaptation of the Local Search Proportional Approval Voting (LS PAV) rule from the MWV literature that is a polynomial-time computable rule that is known to satisfy EJR <cit.>. In the MWV setting, the rule begins with an arbitrary committee of some fixed size k and in iterations, searches for any swaps between committee members and non-selected candidates that brings about an increase of the PAV score by at least n/k^2. In our model, the PAV score of some feasible outcome  w⃗∈ is defined to be PAV(w⃗) = ∑_i∈ N∑_t = 1^iw⃗1/t. We can then lift Local Search PAV to our setting with constraints.


Beginning with an arbitrary outcome w⃗∈ as the current winning outcome, the rule looks for all possible deviations. If there exists an (S,w⃗)-deviation for some voter group to some outcome w⃗'∈ such that PAV(w⃗') - PAV(w⃗)≥n/m^2, i.e., the new outcome w⃗' yields a PAV score that is at least n/m^2 higher than that of w⃗, then the rule sets w⃗' as the current winning outcome. The rule terminates once there exists no deviation that improves on the PAV score of the current winning outcome by at least n/m^2.


As there is a maximum obtainable PAV score, LS PAV_ is guaranteed to terminate. The question is how long this rule takes to return an outcome when we have to take k-restrictive constraints into account. 


    For elections instances where  is k-restrictive (where k is a fixed constant), LS PAV_ terminates in polynomial time. 



We show that given an outcome w⃗, finding all possible deviations can be done in polynomial time for a k-restrictive constraint . This can be done by exploiting the presence of the implication set Imp_. Note that the size of the implication set Imp_ is polynomial in the number of issues. So we can construct the outcome implication graph of Imp_ and the outcome w⃗ in polynomial time. Then for each issue a_t∈, we can find the set G_w⃗(a_t,d) for some d≠ w_t∈ D_t in polynomial time and the issue-decision pairs represent the required additional decisions to be fixed in order to make a deviation from outcome w⃗ by changing the w⃗'s decision on issue a_t to d. Doing this for each issue a_t allows us to find a deviation that can improve the PAV score, if such a deviation exists. With similar reasoning used in other settings <cit.>, we end by noting that since there is a maximum possible PAV score for an outcome, and each improving deviation increases the PAV score by at least n/m^2, the number of improving deviations that LS-PAV_ makes is polynomial in the number of issues m. 


Off the back of this positive computational result, we present the degree to which LS PAV_ provides proportional outcomes with regards to the α--β axiom. 


   For election instances (B,) where the voters' ballots are consistent with the constraint  and  is k-restrictive for some k≥ 2, LS-PAV_ satisfies 2/(k+1)--(k-1).



For an election instance (B,) where  is k-restrictive for k≥ 2, take an outcome w⃗ returned by LS-PAV_ and consider a group of voters N' that agree on some set of issues T. Let us assume that for every voter i∈ N', it holds that iw⃗ < 2/k+1·|N'|/n·|T|-k + 1 and then set ℓ = 2/k+1·|N'|/n·|T|-k + 1. We use r_i to denote the number of outcome w⃗'s decisions that a voter i∈ N agrees with.

For each voter i∈ N∖ N', we calculate the maximal reduction in PAV score that may occur from a possible deviations by LS-PAV_ when  is k-restrictive. This happens when for each of at most r_i/k deviations, we decrease their satisfaction by k and remove ∑_t=0^k-11/(r_i - t) in PAV score. So for these voters in  N∖ N', we deduct at most the following:

    ∑_N∖ N'r_i/k·(∑_t=0^k-11/r_i - t) ≤∑_N∖ N'r_i/k·(∑_t=1^kt/r_i) = k+1/2·(n - |N'|).


Now, so there are |T| - (ℓ - 1) = |T| - ℓ +1 issues that all voters in N' agree on but they disagree with outcome w⃗'s decisions on these issues. Since we assume the constraint is k-restrictive, then for each of these |T| - ℓ +1 issues, they fix at most k-1 other issues and thus, there are at least (|T| - ℓ +1)/k feasible deviations that can be made by LS-PAV_ amongst these issues. For the voters in N', we now consider the minimal increase in PAV score that may occur from these possible deviations by LS-PAV_. For each such deviation, we increase their satisfaction by at least k and thus, for a voter i∈ N', we increase the PAV score by ∑_t=1^k1/(r_i + t). Since for each voter i∈ N' we have r_i≤ℓ - 1, and as there are at least (|T| - ℓ +1)/k feasible deviations in T, it follows that we add at least the following to the PAV score: 


    |T| - ℓ +1/k·(∑_i∈ N'∑_t=1^k1/r_i + t)≥|T| - ℓ +1/k·(∑_i∈ N'∑_t=1^k1/ℓ + t - 1)


Taking into account that k≥ 2 and ℓ = 2|N'||T|/(n(k+1))-k+1, then with further simplification, we find that at least the following is added to the PAV score:

    > n(k+1)/2 - |N'| +  n(k+1)/|T|≥k+1/2·(n - |N'|) +  n(k+1)/|T|.


So the total addition to the PAV score due to satisfying voters in N' is strictly greater than the PAV score removed for the added dissatisfaction of voters in N∖ N' (which is at most (k+1)(n - |N'|)/2). And specifically, this change in score is at least n(k+1)/|T| > n/|T| and thus, at least one of the (|T| - ℓ +1)/k many deviations must increase the PAV score by more than:

    k/|T| - ℓ +1·n/|T|≥1/|T|·n/|T|≥n/|T|^2≥n/m^2.


Thus, LS-PAV_ would not terminate but would instead make this deviation in order to increase the total PAV score. Thus, contradicting that such a group N' cannot exist. 


With this result, we have a rule that when focused on k-restrictive constraints, is both polynomial-time computable and provides substantial proportional representation guarantees (assuming voter ballots are constraint consistent).




§ PROPORTIONALITY VIA PRICEABILITY



With this section, we offer an alternative to the justified-representation-like interpretation of proportional representation, and this is through the notion of priceability <cit.>. Recent work has shown the promise of this market-based approach for a general social choice model <cit.> and the sequential choice model <cit.>. We look to employ it for constrained public decisions (albeit looking at a weaker priceability axiom than the axiom that <cit.> studied).


Each voter has a personal budget of m and they have to collectively fund the decisions on some issues, with each decision coming with some price. A price system ps = ({p_i}_i∈ N,{π_(a_t,d)}_(a_t,d)∈ H) where H = ⋃_a_t∈{(a_t,d)| d∈ D_t} is a pair consisting of (i) a collection of payment functions p_i: ×{0,1}→ [0, b], one for each voter i∈ N, and (ii) a collection of prices π_(a_t,d)∈ℝ_≥ 0, one for each decision pair (a_t,d) for a_t∈ and d∈ D_t. We consider priceability with respect to outcomes w⃗∈ where decisions are made on all issues. 
We say that an outcome w⃗ = (w_1,…,w_m) is priceable if there exists a price system ps such that:
 
 
     
   ( P1): For all a_t∈ and d∈ D_t, it holds that if d ≠b⃗_i^t we have p_i(a_t,d) = 0, for every i∈ N.
     
     
   ( P2): ∑_(a_t,d)∈ H p_i(a_t,d) ≤ m for every i∈ N where it holds that H = ⋃_a_t∈{(a_t,d)| d∈ D_t}.
     
    
   ( P3): ∑_i∈ V p_i(a_t,d) = π_(a_t,w_t) for every a_t∈.
    
    
   ( P4): ∑_i∈ V p_i(a_t,d) = 0 for every a_t∈ and every d≠ w_t∈ D_t.

    
   ( P5): There exists no group of voters N' with an (S,w⃗)-deviation for some S⊆, such that for each a_t∈ S:
    
    ∑_i∈ N'(m-∑_(a_t',d')∈ H p_i(a_t',d')) > π_(a_t,w_t)
 
    where H = ⋃_a_t∈{(a_t,d)| d∈ D_t}.

    


Condition (P1) states that each voter only pays for decisions that she agrees with; (P2) states that a voter does not spend more than her budget m; (P3) states that for every decision in the outcome, the sum of payments for this decision is equal to its price; (P4) states that no payments are made for any decision not in the outcome; and, finally, (P5) states that for every set of issues S, there is no group of voters N' agreeing on all decisions for issues in S, that collectively hold more in unspent budget to `update' outcome w⃗'s decision on every issue a_t∈ S to a decision that they all agree with (where `updating' these issues leads to a feasible outcome). We illustrate priceability in our setting with the following example of a binary election instance.


    Take four issues = {a_1, a_2, a_3, a_4} and a constraint = {(1,1,1,1),(1,1,0,0)}. Suppose there are two voters with ballots b⃗_1 = (1,1,1,1) and  b⃗_2 = (0,0,0,0). Note that outcome w⃗ = (1,1,1,1) is not priceable as any price system where voter 1 does not exceed her budget would have voter 2 having enough in leftover budget to cause a violation of condition ( P5) (with her entire budget being leftover, she can afford more than price of the (S,w⃗)-deviation to outcome w⃗). On the other hand, w⃗' = (1,1,0,0) is priceable where we set the price of this outcome's decisions to 1.


The following result gives some general representation guarantees whenever we have priceable outcomes.


    Consider a priceable outcome w⃗ with price system ps = ({p_i}_i∈ N,{π_(a_t,d)}_(a_t,d)∈ H) where H = ⋃_a_t∈{(a_t,d)| d∈ D_t}. Then, for every T-cohesive group of voters N'⊆ N for some T⊆ with an (S,w⃗)-deviation for some S⊆ T, it holds that:
    
    ∑_i∈ N'iw⃗≥n/q·|T| - |S|

    where q = max{π_(a_t,w_t)}_a_t∈ S.



Take a priceable outcome w⃗ and consider a T-cohesive group of voters N'. Suppose that ∑_i∈ N'iw⃗< n/q·|T| - |S| where q = max{π_(a_t,w_t)}_a_t∈ S. As a group, the voters N' have a budget of m|N'|. Now, the voters in N' collectively contributed to at most n/q·|T| - |S|-1 decisions in outcome w⃗, and for each decision, the price was at most q (as q is the the price system's maximal price). So, we have that voter group N' has at least the following in leftover budget:

    m|N'| - q·(n/q·|T| - |S|-1)≥ m·n|T|/m - n|T| + q|S|+q = q·(|S|+1).

Note we made use of the fact that N' is T-cohesive.
Thus, we know that N' has strictly more than q|S| in funds and for each issue in a_t∈ S, holds more than in funds than q≥π_(a_t,w_t). This presents a violation of condition P5 of priceability. Hence, voter group N' cannot exist.


However, we now must ascertain whether priceable outcomes always exist, regardless of the nature of the constraint. We see that this is possible thanks to the rule we have already defined, namely MeCorA_.

The next result shows that MeCorA_ captures the notion of priceability.


    MeCorA_ always returns priceable outcomes.



Let w⃗ = (w_1,…,w_m) be the outcome returned by MeCorA_. We define the following price system ps: For each issue a_t∈, fix the prices π_(a_t,w_t) = π_(a_t,d) = λ_t for all d≠ w_t∈ D_t where λ_t is issue a_t's last MeCorA_ price (before being set to ∞) prior to the rule's termination. Fix the payment functions p_i for each voter to the money they spent to end the execution of MeCorA_. Observe that the priceability conditions ( P1)-( P4) clearly hold: since we have that, to end MeCorA_'s run, voters do not pay for decisions that (i) they do not agree with (condition ( P1)) and (ii) are not made by outcome w⃗ (condition ( P4)); MeCorA_ limits each voter a budget of m (condition ( P2)) ( P2); and the sum of payments for decisions made by outcome w⃗ will equal exactly π_(a_t,w_t) = λ_t (condition ( P3)). Now, for condition ( P5), note that if such a group of voters N' existed for some set of issues S, then MeCorA_ would not have terminated as this group of voters could have changed the decisions of these issues in S while increasing each issues' prices.


This is a positive result that, combined with that of Proposition <ref>, gives us a rule that always returns us priceable outcomes for any election instance.




§ CONCLUSION



We considered two different interpretations of justified representation from multiwinner voting and adapted them to a public-decision model with constraints. 
In analysing the feasibility of the axioms, we devised restricted classes of constraints (the NFD property and simple implications). 
While we could show mostly negative results for the satisfaction of cohesiveness-EJR under constraints, we were able to adapt successfully three known rules (MES, Local Search PAV and MeCorA) 

to yield positive proportional guarantees that meet, in an approximate sense, the requirements of agreement-EJR. Additionally, we defined a suitable notion of priceability and showed that our adaptation of MeCorA always returns priceable outcomes.

Our work opens up a variety of paths for future research. First, assessing a class of constraints that are more expressive than the simple implications seems a natural starting point in extending our work. Then, on a more technical level, it would be interesting to check if the representation guarantees that are offered by , LS-PAV_ and Greedy MeCorA_-(k-1) still hold for a wider range of election instances. Regarding our adaptation of priceability, the question is open as to whether there are more constrained public-decision that always produce complete priceable outcomes. Given that we opted to represent the constraints as an enumeration of all feasible outcomes, it is natural to ask what occurs to results such as Proposition <ref> when we consider the constraint takes a particular form of representation, e.g.,  is represented as a Boolean formula of propositional logic. We also note some lingering computational questions such as the computational complexity of (i) computing outcomes for rules such as  and Greedy MeCorA_-(k-1) for general constraints, and (ii) of checking whether a given feasible outcome is priceable. Finally, the list of proportionality notions to be tested on the constraints test-bed is not exhausted, with the proportionality degree <cit.> most notably still to be considered. 

abbrvnat
  

