# proportional_public_decisions__6aa32190.pdf

Proportional Public Decisions

Piotr Skowron, Adrian G orecki

University of Warsaw p.skowron@mimuw.edu.pl, adrian.gorecki.00@gmail.com

We consider a setting where a group of individuals make a number of independent decisions. The decisions should proportionally represent the views of the voters. We formulate new criteria of proportionality and analyse two rules, Proportional Approval Voting and the Metod of Equal Shares, inspired by the corresponding committee election rules. We prove that the two rules provide very strong proportionality guarantees when applied to the setting of public decisions.

Introduction We consider a model where a group of n individuals, hereinafter called voters, needs to collectively make m independent decisions. Each decision is binary it can be either YES or NO. This model describes numerous real scenarios, such as negotiations within a group of people having conflicting interests (in particular, negotiations between senators during talks that precede formations of governing coalitions), or decisions made by housing cooperatives. The same model has been considered by Freeman, Kahng, and Pennock (2020) in the context of selecting a subset of candidates, where for each candidate the voters decide if the candidate should be included in the selected subset. Typically, such decisions are made via majority voting, i.e., for each issue we count the number of YES and NO ballots, and we choose the option that received more votes. This allows even a small majority of voters to decide about all the relevant issues. For example, if 51% of voters would like all m decisions to be YES, and the remaining 49% would have exactly opposite views, making decisions via majority voting would make 51% of voters fully satisfied, and 49% completely ignored. This is unfair and disproportional. Ideally, in this example we would like roughly 51% of the decisions to be YES and 49% to be NO.

Our Contribution In this paper we propose new formal criteria of proportionality that capture the following intuition: an α fraction of voters shall be able to influence at least α fraction of decisions. Thus, our criteria require that a rule used for making decisions should respect minorities of voters to the extent

Copyright c 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

proportional to their size. Similar criteria have been considered in the literature on committee elections (see the recent survey by Lackner and Skowron (2020)). The main difference is that our concepts provide proportionality guarantees for all groups of voters of sufficient size, while the properties formulated for committee elections typically provide guarantees only for groups of voters which have very similar (cohesive) preferences. This difference is very important since empirical studies suggest that groups of voters with cohesive preferences are rare (Bredereck et al. 2019), and thus our axioms provide practically more powerful guarantees. We explain how two rules known in the literature, Proportional Approval Voting (PAV) and the Method of Equal Shares (MES), apply in this setting. We prove they perform very well from the perspective of proportionality.

Related Work

The model of public decisions has been considered by Conitzer, Freeman, and Shah (2017). The authors have also considered criteria of fairness, yet their axioms specify guarantees on satisfaction only for individual voters. Our criteria provide guarantees also for groups of voters. Our model and our criteria are inspired by the literature on approval-based committee elections (Lackner and Skowron 2020). Specifically, the criteria of proportionality that we consider in this paper are closely related to the notions of extended justified representation (EJR) (Aziz et al. 2017) and proportionality degree (S anchez-Fern andez et al. 2017; Aziz et al. 2018; Skowron et al. 2017; Skowron 2021). In committee elections the goal is to select a fixed-size subset of candidates based on the voters preferences. This corresponds to making multiple decisions for each candidate we need to decide whether to include this candidate in the winning committee or not yet, there are additional constraints that specify the total number of yes decisions. This perspective has been noticed by Freeman, Kahng, and Pennock (2020), who refer to the setting of public decisions as to committee elections with variable number of winners (i.e., where the number of winning candidates is not fixed a priori). A number of axioms that specify proportionality guarantees for groups of voters with cohesive preferences have been proposed in the literature on committee elections. In this paper we consider axioms that guarantee fair treetment for all groups of voters, not only the cohesive ones.

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

In real life, many decisions happen sequentially. Lackner (2020) initiated the study of models for long-term collective decision making. Our work complements this literature. Alongside studies on the on-line model, it is important to understand what can be achieved in the offline setting. For example, it is typical to compare the qualities of online algorithms to the optimal ones, which have access to the full information at once. Further, we believe that examining our setting can give hints on how to design rules which might work well also in the on-line setting. The literature on propositional belief merging (Konieczny and Pino P erez 2011; Konieczny, Lang, and Marquis 2004) focuses on different aspects than those typically considered in the context of voting. A few notable exceptions include works that study belief merging with strategyproofness (Chopra, Ghose, and Meyer 2006; Everaere, Konieczny, and Marquis 2007; Haret and Wallner 2019) and belief merging with proportionality (Haret et al. 2020). The latter work is the most relevant, yet the proportionality axioms considered there are rather weak and apply only to well-structured voters preferences. We assume that the decisions are made over independent issues. The literature on voting in combinatorial domains deals with the case where relations between the decisions are more complex. For a comprehensive overview of this literature we refer to a book chapter by Lang and Xia (2016). In contrast to the vast literature on fairness in machine learning (Caton and Haas 2020) our work does not concern the problem of reducing existing biases, but rather on designing impartial mechanisms. Our methods treat all groups of voters equally, independently on the societal background.

Preliminaries An election is a pair E = (A, N), where A = {a1, a2, . . . , am} is an agenda of m issues, and N = {1, 2, . . . , n} is a set of voters. For each voter i we given two sets, Ri and Yi, such that Yi Ri A. The set Ri contains issues which are relevant to voter i, i.e., those that the voter is interested in the voter would like the decisions made on issues from Yi to be YES, and the decisions made on issues from Ni = Ri \ Yi to be NO. We say an election has no abstentions if for each voter i N we have Ri = A. An outcome of an election is a set W A; intuitively, W contains issues on which the decision was set to YES. Given an outcome W we define the utility of a voter i as ui(W) = |W Yi| + |(A \ W) Ni|, that is the utility of the voter is measured as the number of decisions that are consistent with the voter s preferences. A decision rule is a function that takes an election as input and returns an outcome. Let us now recall definitions of two decision rules from the literature. Both rules have been initially studied in the context of approval-based committee elections, where they exhibit very good properties pertaining to fairness (Lackner and Skowron 2020), yet their definitions naturally extend to the setting of public decisions.

Proportional Approval Voting (PAV) (Thiele 1895) The rule picks an outcome W maximising P i N H(ui(W)), where H(t) = Pt i=1 1/i for each t N.

Method of Equal Shares (MES) (Peters and Skowron 2020; Peters, Pierczynski, and Skowron 2021) (In the early papers the method was also called Rule X.) We initially assume that each voter is endowed with m dollars, and that buying a candidate costs n dollars. The decisions are made sequentially. At each step we look at issues for which we did not yet make a decision. For each such an issue a and each decision d {YES, NO} we calculate the minimum price ρ(a, d) such that if each voter who wants d paid ρ(a, d) or all the money she has left, then these voters would pay n dollars in total. If such price does not exist (which happens when the voters who want d have not enough money left), we remove the pair (a, d) from further consideration. If all pairs have been removed we finish. Otherwise, we pick the issue and the decision with the minimal value of ρ(a, d), and ask each voter who wants d to pay ρ(a, d) or all the money left. We set the decision on issue a to d, and continue. It might happen that after this procedure there are issues for which the decision has not been set. In the second phase we set the decisions for these issues arbitrarily (for instance, using majority voting).

Proportionality of Aggregation Rules for Elections without Abstentions In this section we consider a model where the voters do not abstain from voting, that is where Ri = A for all i N. This model has been considered by Freeman, Kahng, and Pennock (2020). Below we formally introduce our notions of proportionality, provide their intuitive interpretation and discuss their relation to the notions from the literature.

Definition 1 (Proportionality). A decision rule f is proportional if for each election E = (A, N) and each subset of voters V N there exists a voter v V such that ui(f(E)) > m/2 |V |/n 1.

Our intuitive interpretation of proportionality is the following: we would like each group of voters of size α n, α [0, 1], to be able to decide about α m issues. However, such a requirement would be too strong since the voters within the group might disagree over the issues. Thus, we must relax this condition by a multiplicative factor of 2. The following example shows that any reasonably fair and symmetric rule cannot satisfy a variant of Definition 1 in which the condition ui(f(E)) > m/2 |V |/n 1 is strengthened.

Example 1. Consider an election where the population of voters is divided into two equal-size disjoint groups, N = N1 N2. For each voter i N1 we set Yi = A and Ni = , and for each i N2 we set the opposite preferences, Yi = and Ni = A. A symmetric rule should treat the voters from N1 and N2 equally, and thus half of the decisions should be set to YES and half to NO. Then, the utility of each voter would equal to m/2, and so in the group of all voters (α = 1) there would be no voter with utility greater than m/2 |N|/n.

Freeman, Kahng, and Pennock (2020) considered a related axiom, called extended justified representation (EJR), which requires that in each group of voters V N with | T i V Yi| + | T i V Ni| m |V |/n there exists a voter i with ui(f(E)) m/2 |V |/n . The requirement that

| T i V Yi| + | T i V Ni| m |V |/n is often called cohesiveness. In words, EJR says that a group should be guaranteed the right to decide about a certain number of issues only if they full agree on that many decisions. The requirement of cohesiveness is very strong and in practice very few groups of voters are cohesive (Bredereck et al. 2019). To the best of our knowledge, we provide the first definition of proportionality that ensures guarantees to all groups of voters. Definition 1 requires that in each group of voters of sufficient size there must be at least one voter with sufficiently high utility. Below we provide a related definition which focuses on the average utility within the group.

Definition 2 (Proportional Average Representation). Consider a function d: [0, 1] N. We say that a decision rule f guarantees proportional average representation of d if for each election E = (A, N), each α [0, 1], and each subset of voters V N with |V | αn we have:

i V ui(f(E)) > d(α).

We allow the proportional average representation to depend on the number of issues, or the number of voters, but for simplicity, we explicitly state only α as an argument of d. There is a relation between the two properties. It is instructive to observe that Definition 1 applies (to some extent) to all the voters from the group V . If we fix V , Definition 1 directly implies that there exists a voter i V with sufficiently high satisfaction. Yet, it also applies to V \ {i}, and ensures that there exists a voter j V \ {i} who is wellrepresented. Then, we can apply Definition 1 to V \ {i, j}, etc. Consequently, this implies that, on average, the satisfaction of the voters from V is high.

Proposition 1. Every decision rule with proportional average representation of d(α) = α/2 m 1 is proportional. Every proportional decision rule has the proportional average representation of d(α) = α/4 m 1.

We show that PAV has optimal proportionality guarantees.

Theorem 1. In the model with no abstentions PAV has proportional average representation of d(α) = α/2 m 1.

Corollary 1. With no abstentions PAV is proportional.

We omit the proof of Theorem 1, as it follows from a more general result that we present in the subsequent section. Let us now move to the analysis of the Method of Equal Shares (MES). First we show that if there are no abstentions, then MES in the first phase will not set the decision for at most one issue. Thus, all but one decisions will be made in a proportional fashion. This is different to the setting of committee elections, where MES might select significantly fewer candidates than required.

Proposition 2. In the model with no abstentions MES in the first phase will not set the decision for at most one issue.

Proof. For the sake of contradiction assume that the rule did not set the decision for at least two issues, a and a . Then the total amount of money left in the voters pockets equals at least to 2n. Consider issue a and let us look at two groups

of voters: those who want a to be set YES and those who want it to be set to NO. At least one of this groups has at least n dollars left. Thus, the rule would set the issue to the respective decision before moving to the second phase.

Theorem 2. With no abstentions MES is proportional.

Proof. Consider an election E = (A, N), and a group of voters V ; we set n = |V |. Let ri denote the number of issues that voter i agrees on with the outcome f MES(E). Towards a contradiction assume that there does not exist a voter i V for which ri m

2 n /n. Then for all voters i V we have ri m

2 n /n 1. Now let us prove that there is no issue for which a voter in V spent more than 2n/n dollars. For the sake of contradiction let us assume that this is not true and that such issues exist. Let a and d be the first such issue and the corresponding decision that has been bought. There must exist a set of voters V V of size at least n /2 in which all voters support YES or NO on a. Each voter in V paid for at most m

2 n /n 1 decisions, thus before d has been bought she spend at most: m

Consequently, each voter from V has at least 2n/n dollars left. As a result, there exists a group of voters who could buy a decision by paying at most 2n/n dollars, each. MES would first make such a purchase, a contradiction. Since for all voters in V we have that ri m

2 n /n 1 and no voter spent more than 2n/n dollars on any decision, each voter in V has at least 2n/n dollars left at the end of execution of the first phase of MES. In total, these voters have at least 2n dollars left, so at least 2 issues are left without a decision. For each of these issues at least half of V will support or oppose them and will have enough dollars to buy one more decision, which contradicts the fact that the rule has stopped, and completes the proof.

Proposition 1 implies that MES has also the proportional average representation of d(α) = α/4 m 1. However, below we will prove a stronger guarantee, which is the core technical contribution of our work. Theorem 3. With no abstentions MES has the proportional average representation of d MES(α) > α (m+1)

Proof. Consider an election E = (A, N), a value α [0, 1], and a group of voters V with |V | α n. We set n = |V |. Let us arrange the voters in V in the order v1, v2, . . . , vn such that v1 is the first voter in V that paid more than m 2n

n dollars for the purchases, v2 is the first from the remaining voters that paid more than m 2n n 1 dollars for the purchases, . . ., vi is the first from the remaining voters that paid more than m 2n n i+1 dollars for the purchases, etc. The main strategy of the proof is as follows. Consider purchases made by a voter vi until she spent more than m 2n n i+1 dollars. We will show that for such purchases, on average for each c dollars that voter vi spends the sum of utilities of voters in group V increases by at least:

c 2(n i) + 1

Consider a single such a purchase. Then, at least n i+1 voters have at least 2n n i+1 dollars left this follows from how we arranged the voters in the order. Let us consider a purchase of a decision in which x of those n i + 1 voters participate. There are 2 possibilities: x n i+1

2 or x > n i+1

2 . We start by considering the case where x n i+1

2 . At least n i+1 x voters will vote for the opposite decisions to the one that is currently being purchased. Thus, the price for the decision cannot be larger than n n i+1 x. According to our invariant, the total utility of the voters should increase at least by

n n i + 1 x 2(n j) + 1

The utility increased by at least x, thus, in order to show our invariant it suffices to prove that:

n n i + 1 x 2(n j) + 1

This is equivalent to:

j=i (2(n j) + 1) 3x(n i + 1 x)

2n x + x x(2i + x 1) 3x(n i + 1 x)

2n 2i x 3n 3i 3x + 3

2x n i + 3.

Thus, in case where x n i+1

2 the invariant is preserved. Now, let us move to the second case. The price cannot be higher than n/x. By analogous reasoning, we see that it is sufficient to prove that:

n x 2(n j) + 1

This is equivalent to:

j=i (2(n j) + 1) 3(x + 1)x

2n (x + 1) + (x + 1) (x + 1)(2i + x) 3(x + 1)x

2n + 1 2i x 3x

4x 2n 2i 1.

Which follows from the assumption that x > n i+1

2 . Using our invariant, we get that the average utility of the voters from V equals at least:

m 2n n i + 1

i=1 (2(n i) + 1) 1

3n m(n + 1)

This completes the proof.

We conclude this section by looking at proportionality for cohesive groups, as studied by Freeman, Kahng, and Pennock (2020), and by improving upon their results. Definition 3 (Proportional Average Representation for Cohesive Groups). We say that a group of voters V N is ℓ-cohesive if |V | n ℓ

m and | T i V Yi| + | T i V Ni| ℓ. Consider a function d: N N. We say that a decision rule f gives proportional average representation for cohesive groups of d if for each election E = (A, N), each ℓ [m], and each ℓ-cohesive group of voters V N we have: 1 |V |

i V ui(f(E)) > d(ℓ).

Freeman, Kahng, and Pennock (2020) have shown that PAV does not have the proportional average representation for cohesive groups of d(ℓ) > ℓ

2. This result is however misleading, since it may suggest that the guarantee of PAV is worse than the expected optimum by a multiplicative factor of 1/2. We show, that if we admit an additive factor of one (which commonly appears in the literature on committee elections), then the multiplicative factor improves to 3/4. Theorem 4. With no abstentions PAV has proportional average representation for cohesive groups of d(ℓ) > 3ℓ

Proof. Consider an election E = (A, N) and an ℓ-cohesive group of voters V . Let W be an outcome returned by PAV, W = f PAV(E), and let ri = ui(W). For the sake of contradiction assume that 1 |V | P i V ui(W) 3ℓ

4 1. From the inequality between the harmonic and arithmetic mean, we get that: X

1 ri + 1 |V |2 P i V (1 + ri) = |V |2 P i V ri + |V |

4 1) + |V | = |V |

Let swap(W, a) denote the change of the PAV score of W due to changing the decision for issue a to the opposite one. Observe that voter i agrees with W on ri issues. For each such an issue the change of the decision will cause the decrease of the PAV score by 1/ri. For the other issues changing the decision will increase the score by 1/ri+1. Thus: X

a A swap(W, a) = X

(m ri) 1 ri + 1

Note that since W is the winning outcome, for each a A it must hold that swap(W, a) 0. Consequently:

m + 1 ri + 1 2n.

Also, since the average utility of the group is lower than ℓ, there must exist an issue a such that the voters in V agree on it, yet the decision on this issue is opposite to their views. Since swap(W, a) 0, we get that:

We continue our estimations:

m + 1 ri + 1 = X

m + 1 ri + 1 + X

m + 1 ri + 1

m + 1 ri + 1 + 4n

(m + 1) 2(ri + 1) + 4n

This give a contradiction and completes the proof.

Proportionality in the Model with Abstentions

In this section we analyse the properties of decision rules in the model, where the voters are allowed to abstain from voting, i.e., we assume that the sets Ri can be strict subsets of A. In this case our criteria of proportionality need adjustment. Indeed, we cannot guarantee good satisfaction for the groups irrespectively of their preferences. As an example, consider an election where all voters abstain from voting for all issues. Then, for any decision rule the utility of each voter will equal to zero. Consequently, we formulate the following axioms.

Definition 4 (Proportionality). A decision rule f is ϵproportional if for each election E = (A, N) and each subset of voters V N there exists a voter v V such that

ui(f(E)) > r

(1 ϵ) 1 where r = | \

If a rule is 0-proportional we simply say that it is proportional.

In words Definition 4 provides similar guarantees to Definition 1 capped to the extent to which the voters in a group decide to participate in voting. We adjust the definition of proportional average representation accordingly.

Definition 5 (Proportional Average Representation). Consider a function d: [0, 1] N N. We say that a decision rule f guarantees proportional average representation of d if for each election E = (A, N), each α [0, 1], and each subset of voters V N with |V | αn we have:

i V ui(f(E)) > d

Below we prove that our strong guarantees for proportionality of PAV still hold in the model with abstentions.

Theorem 5. PAV has proportional average representation of d PAV(α, r) > α (r+1)

2 1 ϵ for each ϵ > 0.

Proof. Let us fix α [0, 1], an election E = (A, N), and a group of voters V with |V | α n. Let W be an outcome returned by PAV, W = f PAV(E), and let ri denote the number of issues on which voter i agrees with W. For each issue a A by swap(W, a) we denote the change of the PAV score of W due to changing the decision for a to the opposite one. Observe that voter i agrees with W on ri issues; changing the decision for each such an issue makes the voter decrease the score she assigns to W by 1/ri. On the other hand, for each issue a for which i disagrees with W (there are |Ri| ri such issues), changing the decision on a makes voter i increase the score she assigns to W by 1/ri+1. Consequently:

a A swap(W, a) = X

ri + |Ri| ri

(|Ri| ri) 1 ri + 1

By the fact that the PAV score of W is optimal, we get that swap(W, a) 0 for each a A. As a result, we infer that: X

Let r = | T

i V Ri|. Because |Ri| r for all i V :

1 ri + 1 2n r + 1 and so X

1 ri + 1 2n r + 1

From the inequality between the harmonic and arithmetic mean, we get that:

1 ri + 1 |V |2 P i V (1 + ri) = |V |2 P i V ri + |V |

By combining the two inequalities, we get that:

2n r + 1 |V |2 P i V ri + |V |

After reformulation:

i V ri |V |(r + 1)

2n 1 α (r + 1)

This completes the proof.

Corollary 2. PAV is proportional.

Unfortunately, MES in its naive implementation is not proportional in the model with abstentions, which is illustrated in the following example.

Example 2. Consider an election E = (A, N) and two disjoint non-empty groups of voters, V1 and V2 such that V1 S V2 = N and |V1| > |V2|. Voters have following preferences:

1. For each voter i N we have Ri = {a1, a2, . . . , am/2}. 2. For each voter i V1 we have Ni = Ri, Yi = . 3. For each voter i V2 we have Yi = Ri, Ni = .

Because V1 is the larger group, voters in V1 will pay lower price for making decisions on issues, so their purchases will be made first. Group V1 also consist of majority of voters, so they can afford to buy decisions for all issues they are interested in. Consequently, MES will choose NO for all issues a1, a2, . . . , am/2 and the utility of all voters in V2 will be equal 0, making MES not proportional.

We will now describe a new variant of MES which satisfies proportionality. The main idea is that we do not set the prices of decisions to a fixed value but allow groups of voters to bid for the decisions.

Definition 6 (Method of Coordinated Auctions with Equal Shares (Me Cor A)). Fix a constant ϵ > 0. At the beginning the price of each issue is set to 0, and we fix the decisions to arbitrary values. Each voter is given m dollars. We assume that each decision can be changed to the opposite one, but for that the voters need to propose a price that is higher by at least ϵ from the current price of the issue. In such a case, the price of the issue is raised to the new value. We run the process of bidding as follows. At each step, for each decision d which is not set (that is, the opposite decision is set) we compute the smallest possible value ρd such that if all voters who support d pay ρd or the whole money left, then they will collect the value required for changing the decision. If such value does not exist we set ρd = . If for all decisions d we have ρd = , then we stop, and return the current decisions. Otherwise, we pick the decision d with the lowest value ρd, set it, update the price of the corresponding issue, and return the money that was paid for the decision opposite to d to the voters who paid for it.

Before we formally prove that Me Cor A is proportional, let us illustrate the difference in how proportionality is understood by Me Cor A and PAV.

Example 3. Let us fix t N, and consider an election E = (A, N), where A = {a1, a2, . . . , a4t} and N = V1 V2 with V1 V2 = and |V1| = |V2| = t. For each i V1 we set Ri = Ni = {a1, a2, . . . , a4t} and for each i V2 we set Ri = Yi = {a1, a2 . . . a2t}.

YES a1, . . . at

NO (at+1, . . . a2t)

NO (a2t+1, . . . a4t)

YES a1, . . . at

YES (at+1, . . . a2t)

NO (a2t+1, . . . a4t)

Figure 1: Comparison of the behaviour of PAV and Me Cor A based on the instance from Example 3. The green colour represents that the group of voters is satisfied with the decision, red that is not satisfied, and grey illustrates that the decision is irrelevant for the group.

Let us first consider the behaviour of Me Cor A. At first, all issues could be set by voters from V1 to NO for the price of ϵ dollars each. After that the voters from V2 will swap a1, a2, . . . a2t to YES for 2ϵ dollars each. As a result, the voters from V1 will gain their money back and will swap those 2t issues back to NO for 3ϵ dollars each. The process will repeat to a point where the total price of these issues exceeds tm ϵ, at which the swapping group of voters will be able to afford to swap only 2t 1 issues. Yet, still the prices of all issues will be gradually increasing. At the time when the total price of these issues will be roughly equal to 2mt the process will stop. Then one group will control half of the decisions, paying for them roughly mt and the other group will control the other half. The result will be that 75% of issues will be set to NO, and 25% will be set to YES. On the other hand, PAV will set decisions a1, a2 . . . a2t to YES, and the decisions a2t+1, . . . a4t to NO. This behaviour is illustrated in Figure 1.

Example 3 shows different behaviours of PAV and Me Cor A. PAV equalises the utility of the two groups of voters. Me Cor A notices that half of the issues are relevant only to one group of voters, so it sets the decisions on them according to the will of those voters. The decisions on the remaining issues which are relevant to all the voters are spilt proportionally among the two groups of voters.

Theorem 6. Me Cor A is ϵ-proportional.

Proof. Consider an election E = (A, N) and a group of voters V N. Let R = T

i V Ri and r = |R|. For the sake of contradiction, assume that each voter in V has utility equal to at most ℓ= ( r

n )(1 ϵ) 1. For each issue from R we pick the decision that is preferred by a majority of the voters from V . Let us call the set of such decisions D. In this set of decisions let us pick those that have been set according to the will of majority. Since the utility of each voter is at

most ℓ, we know there are at most 2ℓsuch decisions. Let us call the set of the remaining decisions D , |D | r ℓ. We will show that for the decisions in D the prices of the corresponding issues need to be equal to at least m|V |

ℓ+2 ϵ. Indeed, let use consider two cases. First, assume that the highest price a voter from V pays for a decision is at most m ℓ+2. This means that each voter still has at least the following amount of money left:

m ℓ m ℓ+ 2 = 2m

That is, for each decision from D the voters supporting this decision would have at least m|V |

ℓ+2 money left. Since no such decision from D is affordable, it means each such a decision must cost at least m|V |

ℓ+2 ϵ. Now, let us consider the second case, where some voter from V paid for some candidate more than m|V |

ℓ+2 . Let us consider the first moment when such a purchase occurred. In that moment each voter from V had at least 2m

ℓ+2 money left, so the price of all issues corresponding to the decisions from D must have been at least equal to m|V |

ℓ+2 ϵ. Consequently, the total price of all issues corresponding to the decisions from D must equal to at least: m|V |

ℓ+ 2 ϵ (r ℓ).

Since 2ℓ+ 2 r we have: m|V |

ℓ+ 2 ϵ (r ℓ) > m|V |

ℓ+ 1 ϵ (r ℓ 1)

= m (2n |V |) mn.

Yet, the voters have in total mn dollars, a contradiction.

Finally, we introduce one more axiom of proportionality. Definition 7 (Proportionality for cohesive groups). A decision rule f is proportional if for each election E = (A, N) and each subset of voters V N there exists a voter v V such that

ui(f(E)) > r |V |

n 1 where r = | \

i V Yi| + | \

Note that there are two differences between Definition 4 and Definition 7. In Definition 7 the group needs a stronger cohesion in order to be guaranteed high utility. It must agree not only on the issues on which they do not abstain, but also on preferred decisions for those issues. Second, since Definition 7 excludes certain disagreement within the group of voters, we can provide a stronger guarantee of r |V |/n 1 instead of r/2 |V |/n 1. Theorem 7. For a sufficiently small ϵ Me Cor A satisfies proportionality for cohesive groups.

Proof. Consider an election E = (A, N) and a group of voters V N. Let r = | T i V Yi| + | T i V Ni|. Towards a contradiction, assume that each voter in V has utility equal to at most ℓ= r |V |

n 1. Thus, there are at least r r |V |

n +1 decisions on which the voters from V agree, but they do not have money to change them according to their will. For each such a decision the price of the corresponding issue must be equal to at least m|V |

ℓ+1 . Indeed, let use consider two cases. First, assume that the highest price a voter from V pays for a decision is at most m ℓ+1. This means that each voter still has at least the following amount of money left:

m ℓ m ℓ+ 1 = m ℓ+ 1.

The voters from V would have in total m|V |

ℓ+1 money left. Since they cannot afford any decision it means each such a decision must cost at least m|V |

ℓ+1 . Now, let us consider the second case, where some voter from V paid for some candidate more than m|V |

ℓ+1 . Let us consider the first moment when such a purchase occurred. In that moment the voters from V had at least m|V |

ℓ+1 money left, so the price of all the consid-

ered issues must have been at least equal to m|V |

ℓ+1 . The total price of all these issues must equal to at least:

m|V | ℓ+ 1 (r r |V |

n + 1) > mn

r (r n |V |

= m(n |V |).

These issues must have been paid only by voters from N \V who had in total m(n |V |) dollars, a contradiction.

Conclusion In this paper we have considered a setting, where a group of individuals makes simultaneously a number of decisions. We propose a number of axioms that capture the intuitive idea of proportionality. Our results suggest that the two rules that we analyse, Proportional Approval Voting and MES, provide strong guarantees of proportionality. We have also introduced a new variant of MES, Me Cor A, which is implemented through an auction. This new variant extends to (and preserves good proportionality guarantees in) a more general model, where the voters can abstain from voting. We explain that while the two rules offer good proportionality guarantees, they interpret proportionality differently. There are a number of challenging open questions. We do not know whether our bounds in Theorem 4 and Theorem 3 are tight. We do not know what is the proportional average representation for cohesive groups for MES, nor what is the proportional average representation of Me Cor A in the model with abstentions. Yet, in our opinion the main challenge lies in incorporating additional constraints (dependencies between issues) to the model and building a theory of fairness that would apply to such more general settings.

Acknowledgments Piotr Skowron was supported by Poland s National Science Center grant UMO-2019/35/B/ST6/02215.

Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justified Representation in Approval Based Committee Voting. Social Choice and Welfare, 48(2): 461 485. Aziz, H.; Elkind, E.; Huang, S.; Lackner, M.; S anchez Fern andez, L.; and Skowron, P. 2018. On the Complexity of Extended and Proportional Justified Representation. In Proceedings of the 32nd Conference on Artificial Intelligence (AAAI-2018). Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; and Niedermeier, R. 2019. An Experimental View on Committees Providing Justified Representation. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2019), 109 115. Caton, S.; and Haas, C. 2020. Fairness in Machine Learning: A Survey. Technical Report ar Xiv:2010.04053 [cs.LG], ar Xiv.org. Chopra, S.; Ghose, A.; and Meyer, T. 2006. Social choice theory, belief merging, and strategy-proofness. Information Fusion, 7(1): 61 79. Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair public decision making. In Proceedings of the 2017 ACM Conference on Economics and Computation, 629 646. Everaere, P.; Konieczny, S.; and Marquis, P. 2007. The strategy-proofness landscape of merging. Journal of Artificial Intelligence Research, 28: 49 105. Freeman, R.; Kahng, A.; and Pennock, D. M. 2020. Proportionality in Approval-Based Elections With a Variable Number of Winners. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI2020), 132 138. Haret, A.; Lackner, M.; Pfandler, A.; and Wallner, J. P. 2020. Proportional Belief Merging. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020). AAAI Press. Haret, A.; and Wallner, J. P. 2019. Manipulating skeptical and credulous consequences when merging beliefs. In European Conference on Logics in Artificial Intelligence (JELIA2019), 133 150.

Konieczny, S.; Lang, J.; and Marquis, P. 2004. DA2 merging operators. Artificial Intelligence, 157(1-2): 49 79. Konieczny, S.; and Pino P erez, R. 2011. Logic Based Merging. Journal of Philosophical Logic, 40(2): 239 270. Lackner, M. 2020. Perpetual Voting: Fairness in Long-Term Decision Making. In Proceedings of the 34th Conference on Artificial Intelligence (AAAI-2020), 2103 2110. Lackner, M.; and Skowron, P. 2020. Approval-Based Committee Voting. Technical Report ar Xiv:2007.01795 [cs.GT], ar Xiv.org. Lang, J.; and Xia, L. 2016. Voting in Combinatorial Domains. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice. Cambridge University Press.

Peters, D.; Pierczynski, G.; and Skowron, P. 2021. Proportional Participatory Budgeting with Additive Utilities. In Proceedings of the Thirty-fifth Conference on Neural Information Processing Systems (Neur IPS-2021). To Appear. Peters, D.; and Skowron, P. 2020. Proportionality and the Limits of Welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (EC-2020), 793 794. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Basanta Val, P.; and Skowron, P. 2017. Proportional justified representation. In Proceedings of the 31st Conference on Artificial Intelligence (AAAI-2017), 670 676. Skowron, P. 2021. Proportionality Degree of Multiwinner Rules. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC-2021), 820 840. Skowron, P.; Lackner, M.; Brill, M.; Peters, D.; and Elkind, E. 2017. Proportional Rankings. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI-2017), 409 415. Thiele, T. N. 1895. Om Flerfoldsvalg. In Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, 415 441.