# approvalbased_voting_with_mixed_goods__d57448b3.pdf

Approval-Based Voting with Mixed Goods

Xinhang Lu1, Jannik Peters2, Haris Aziz1, Xiaohui Bei3, Warut Suksompong4

1School of Computer Science and Engineering, University of New South Wales 2Efficient Algorithms Research Group, Technische Universit at Berlin 3School of Physical and Mathematical Sciences, Nanyang Technological University 4School of Computing, National University of Singapore

We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This setting generalizes both the well-studied model of multiwinner voting and the recently introduced model of cake sharing. Under approval votes, we propose two variants of the extended justified representation (EJR) notion from multiwinner voting, a stronger one called EJR for mixed goods (EJR-M) and a weaker one called EJR up to 1 (EJR-1). We extend three multiwinner voting rules to our setting Greedy EJR, the method of equal shares (MES), and proportional approval voting (PAV) and show that while all three generalizations satisfy EJR-1, only the first one provides EJR-M. In addition, we derive tight bounds on the proportionality degree implied by EJR-M and EJR-1, and investigate the proportionality degree of our proposed rules.

1 Introduction

In multiwinner voting a new challenge for social choice theory , as Faliszewski et al. (2017) put it the goal is to select a subset of candidates of fixed size from a given set based on the voters preferences. The candidates could be politicians vying for seats in the parliament, products to be shown on a company website, or places to visit on a school trip. A common way to elicit preferences from the voters is via the approval model, wherein each voter simply specifies the subset of candidates that he or she approves (Kilgour 2010; Lackner and Skowron 2023). While (approvalbased) multiwinner voting has received substantial attention from computational social choice researchers in the past few years, a divisible analog called cake sharing was recently introduced by Bei, Lu, and Suksompong (2022). In cake sharing, the candidates correspond to a divisible resource such as time periods for using a facility or files to be stored in cache memory. Following the famous resource allocation problem of cake cutting (Robertson and Webb 1998; Procaccia 2016), this divisible resource is referred to as a cake . In this paper, we study a setting that simultaneously generalizes both multiwinner voting and cake sharing, which we call (approval-based) voting with mixed goods. Specifically, in our setting, the resource may consist of both indivis-

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

ible and divisible goods.1 This generality allows our model to capture more features of the resource than either of the previous models. For example, when reserving time slots, it is possible that some hourly slots must be reserved as a whole, while other slots can be booked fractionally. Likewise, in cache memory storage, certain files may need to be stored in their entirety, whereas other files can be broken into smaller portions. Combinations of divisible and indivisible goods have been examined in the context of fair division, where the resource is to be divided among interested agents and the entire resource can be allocated (Bei et al. 2021a,b; Bhaskar, Sricharan, and Vaish 2021). By contrast, we investigate mixed goods in a collective choice context, where only a subset of the resource can be allocated but the allocated resource is collectively shared by all agents.2 There are multiple criteria that one can use to select a collective subset of resource based on the approval votes. For example, one could try to optimize the social welfare the sum of the agents utilities or the coverage the number of agents who receive nonzero utility. A representation criterion that has attracted growing interest is justified representation (JR) (Aziz et al. 2017). In multiwinner voting, if there are n agents and k (indivisible) goods can be chosen, then JR requires that whenever a group of at least n/k agents approve a common good, some agent in that group must have an approved good in the selected set. A wellstudied strengthening of JR is extended justified representation (EJR), which says that for each positive integer t, if a group of at least t n/k agents approve no fewer than t common goods (such a group is said to be t-cohesive), some agent in that group must have no fewer than t approved goods in the selected set. Aziz et al. (2017) showed that the proportional approval voting (PAV) rule always outputs a set of goods that satisfies EJR. In cake sharing, Bei et al. (2022) adapted EJR by imposing the condition for every positive real number t, and proved that the resulting notion is satisfied by the maximum Nash welfare (MNW) rule.3 Can we unify the two versions of EJR for our generalized setting in

1Since a candidate usually refers to an indivisible entity, we use the term good instead from here on. 2We henceforth use the term agent instead of voter . 3See Appendix A in the extended version of their work. They also noted that JR does not admit a natural analog for cake sharing, since there is no discrete unit of cake.

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

such a way that the guaranteed existence is maintained?4

1.1 Our Contributions In Section 3, we introduce two variants of EJR suitable for the mixed-goods setting. The stronger variant, EJR for mixed goods (EJR-M), imposes the EJR condition for any positive real number t whenever a t-cohesive group commonly approves a resource of size exactly t. The weaker variant, EJR up to 1 (EJR-1), again considers the condition for every positive real number t but only requires that some member of a t-cohesive group receives utility greater than t 1. While EJR-M reduces to the corresponding notion of EJR in both multiwinner voting and cake sharing, and therefore offers a unification of both versions, EJR-1 does so only for multiwinner voting. We then extend three multiwinner voting rules to our setting: Greedy EJR, the method of equal shares (MES), and proportional approval voting (PAV). We show that Greedy EJR-M, our generalization of Greedy EJR, satisfies EJR-M (and therefore EJR-1), which also means that an EJR-M allocation always exists. On the other hand, we prove that our generalizations of the other two methods provide EJR-1 but not EJR-M. Furthermore, while Greedy EJR-M and Generalized MES guarantee the cake version of EJR in cake sharing, Generalized PAV does not. In Section 4, we turn our attention to the concept of proportionality degree, which measures the average utility of the agents in a cohesive group (Skowron 2021). We derive tight bounds on the proportionality degree implied by both EJR-M and EJR-1, with the EJR-M bound being slightly higher. We also investigate the proportionality degree of the three rules from Section 3; in particular, we find that Generalized PAV has a significantly higher proportionality degree than both Greedy EJR-M and Generalized MES. An overview of our results can be found in Table 1.

2 Preliminaries Let N = {1, 2, . . . , n} be the set of agents. In the mixedgoods setting, the resource R consists of a cake C = [0, c] for some real number c 0 and a set of indivisible goods G = {g1, . . . , gm} for some integer m 0. Assume without loss of generality that max(c, m) > 0. A piece of cake is a union of finitely many disjoint (closed) subintervals of C. Denote by ℓ(I) the length of an interval I, that is, ℓ([x, y]) := y x. For a piece of cake C consisting of a set of disjoint intervals IC , we let ℓ(C ) := P I IC ℓ(I). A bundle R consists of a (possibly empty) piece of cake C C and a (possibly empty) set of indivisible goods G G; the size of such a bundle R is s(R ) := ℓ(C )+|G |. We sometimes write R = (C , G ) instead of R = C G . We assume that the agents have approval preferences (also known as dichotomous or binary), i.e., each agent i N approves a bundle Ri = (Ci, Gi) of the resource.5

4As further evidence for the generality of our setting, we remark that, as Bei et al. (2022, Sec. 1.2) pointed out, cake sharing itself generalizes another collective choice setting called fair mixing (Aziz, Bogomolnaia, and Moulin 2020). 5Approval preferences can be given explicitly as part of the input for algorithms, so we do not need the cake-cutting query model

g1 g2 0 0.9 R

Figure 1: A mixed-goods instance with two agents N = {1, 2}, two indivisible goods G = {g1, g2}, a cake C of length 0.9, and α = 2. Agent 1 approves R1 = {g1} C, while agent 2 approves R2 = {g2} C. If the allocation A = {g1, g2} is chosen, both agents receive a utility of 1.

The utility of agent i for a bundle R is given by ui(R ) := s(Ri R ) = ℓ(Ci C )+|Gi G |. Let α (0, c+m] be a given parameter, and assume that a bundle A with s(A) α can be chosen and collectively allocated to the agents;6 we also refer to an allocated bundle as an allocation. An instance consists of the resource R, the agents N and their approved bundles (Ri)i N, and the parameter α. We say that an instance is a cake instance if it does not contain indivisible goods (i.e., m = 0), and an indivisible-goods instance if it does not contain cake (i.e., c = 0). An example instance is shown in Figure 1. A mechanism or rule M maps any instance to an allocation of the resource. For any property P of allocations, we say that a rule M satisfies property P if for every instance, the allocation output by M satisfies P. An example of a rule is the maximum Nash welfare (MNW) rule, which returns an allocation A that maximizes the product Q i N ui(A) of the agents utilities.7

3 EJR Notions and Rules In order to reason about extended justified representation (EJR), an important concept is that of a cohesive group. For any positive real number t, a set of agents N N is said to be t-cohesive if |N | t n/α and s(T i N Ri) t. For an indivisible-goods instance, Aziz et al. (2017) defined EJR as follows: an allocation A satisfies EJR if for every positive integer t and every t-cohesive group of agents N , at least one agent in N receives utility at least t. Bei et al. (2022) adapted this axiom to cake sharing by considering every positive real number t instead of only positive integers.8 To distinguish between these two versions of EJR, as

of Robertson and Webb (1998). 6Instead of the variable k as in multiwinner voting, we use α, as this variable may not be an integer in our setting. This is consistent with the notation used by Bei et al. (2022) for cake sharing. 7Ties can be broken arbitrarily except when the highest possible product is 0. In this exceptional case, the MNW rule first gives positive utility to a set of agents of maximal size and then maximizes the product of utilities for the agents in this set. 8Note that the indivisible-goods version with positive integers t may be meaningless in the cake setting, e.g., if the entire cake has length less than 1. More generally, the restriction to positive inte-

Greedy EJR-M Generalized MES Generalized PAV

EJR-M EJR-1 Proportionality degree t 1 t +1

2t h t 2+1/t

Indivisible-goods EJR Cake EJR

Polynomial-time computation ?

Table 1: Overview of our results. Entries marked by an asterisk follow from known results in multiwinner voting. We also show that the proportionality degree implied by EJR-M and EJR-1 is t 1 t +1

2t and t 2+1/t

2 , respectively.

well as from versions for mixed goods that we will define next, we refer to the two versions as indivisible-goods EJR and cake EJR, respectively. A first attempt to define EJR for mixed goods is to simply use the cake version. However, as we will see shortly, the resulting notion is too strong. Hence, we relax it by lowering the utility threshold.

Definition 3.1 (EJR-β). Let β 0. Given an instance, an allocation A with s(A) α is said to satisfy extended justified representation up to β (EJR-β) if for every positive real number t and every t-cohesive group of agents N , it holds that uj(A) > t β for some j N .9

Proposition 3.2. For each constant β [0, 1), there exists an indivisible-goods instance in which no allocation satisfies EJR-β. This remains true even if we relax the inequality uj(A) > t β in Definition 3.1 to uj(A) t β.

Proof. We work with the weaker condition uj(A) t β. Fix β [0, 1), and choose a rational constant β (β, 1). Consider an indivisible-goods instance with integers n and α such that α = β n, and assume that all agents approve disjoint nonempty subsets Gi of goods. Each individual agent forms a β -cohesive group, so in an EJR-β allocation, every agent must receive utility at least β β > 0. Hence, any EJR-β allocation necessarily includes at least one good from each approval set Gi, and must therefore contain at least n goods in total. However, since α = β n < n, no allocation can satisfy EJR-β.

Proposition 3.2 raises the question of whether EJR-1 can always be satisfied. We will answer this question in the affirmative in Section 3.1. Before that, we introduce EJR-M, another variant of EJR tailored to mixed goods. The intuition behind EJR-M is that a t-cohesive group of agents should be able to claim a utility of t for some member only when there exists a commonly approved resource of size exactly t. This rules out such cases as in the proof of Proposition 3.2, where a group can effectively claim a utility higher than t due to the indivisibility of the goods.

gers t is unnatural for cake, as there is no discrete unit of cake. 9For β = 1, Peters, Pierczy nski, and Skowron (2021) considered a somewhat similar notion called EJR up to one project in the setting of participatory budgeting with indivisible projects.

Definition 3.3 (EJR-M). Given an instance, an allocation A with s(A) α is said to satisfy extended justified representation for mixed goods (EJR-M) if the following holds: For every positive real number t and every t-cohesive group of agents N for which there exists R R such that s(R ) = t and R Ri for all i N , it holds that uj(A) t for some j N . Note that for indivisible-goods instances, the condition s(R ) = t can only hold for integers t, so EJR-M reduces to indivisible-goods EJR. Likewise, for cake instances, if a group is t-cohesive then a commonly approved subset of size exactly t always exists, so EJR-M reduces to cake EJR. Hence, EJR-M unifies EJR from both settings. Proposition 3.4. Let t be a positive real number. For an EJR-M allocation A and a t-cohesive group of agents N , it holds that uj(A) t for some j N . The proof of Proposition 3.4, along with all other omitted proofs, can be found in the full version of our paper (Lu et al. 2022). Since t > t 1 for every real number t, we have the following corollary. Corollary 3.5. EJR-M implies EJR-1. For indivisible-goods instances, EJR-1 reduces to indivisible-goods EJR, since for every positive integer t, the smallest integer greater than t 1 is t. On the other hand, for cake instances, EJR-1 is weaker than cake EJR. In the cake setting, Bei et al. (2022) proved that the MNW rule satisfies cake EJR. However, in the indivisible-goods setting, the fact that MNW tries to avoid giving utility 0 to any agent at all costs means that it sometimes attempts to help individual agents at the expense of large deserving groups. This is formalized in the following proposition. Proposition 3.6. For any constant β 0, there exists an indivisible-goods instance in which no MNW allocation satisfies EJR-β.

3.1 Greedy EJR-M Proposition 3.6 implies that the MNW rule cannot guarantee EJR-M or EJR-1 in the indivisible-goods setting, let alone in the mixed-goods setting. We show next that a greedy approach can be used to achieve these guarantees. The rule that we use is an adaptation of the Greedy EJR rule from the indivisible-goods setting (Bredereck et al. 2019; Peters,

Pierczy nski, and Skowron 2021; Elkind et al. 2022); we therefore call it Greedy EJR-M and describe it below.

Greedy EJR-M

Step 1: Initialize N = N and R = .

Step 2: Let t be the largest nonnegative real number for which there exist = N N and R R such that N is a t -cohesive group, R Ri for all i N , and s(R ) = t . Consider any such pair (N , R ). Remove N from N and add the part of R that is not already in R to R .

Step 3: If N = , return R . Else, go back to Step 2.

Example 3.7. Consider the instance in Figure 1. We have n/α = 1, and Step 2 of Greedy EJR-M chooses t = 1, along with (as one possibility) N = {1} and R = {g1}. We are left with N = {2}, and the next iteration of Step 2 chooses t = 1, N = {2}, and R = {g2}. Finally, the rule returns R = {g1, g2}. Theorem 3.8. The Greedy EJR-M rule satisfies EJR-M (and therefore EJR-1).

Proof. By Corollary 3.5, it suffices to prove the claim for EJR-M. We break the proof into the following four parts.

The procedure is well-defined. To this end, we must show that the largest nonnegative real number t in Step 2 always exists. Observe that for each group of agents X N , the set

TX := t 0 |X| t n

α and there exists

i X Ri with s(Y ) = t

is a union of a finite number of (possibly degenerate) closed intervals, and is nonempty because 0 TX. Therefore, TX has a maximum. The value t chosen in Step 2 is then the largest among the maxima of TX across all X N . The procedure always terminates. This is because each iteration of Step 2 removes at least one agent from N . The procedure returns an allocation R with s(R ) α. Indeed, if an iteration of Step 2 uses value t , it removes at least t n/α agents from N and adds a resource of size at most t to R . Since only n agents can be removed in total, the added resource has size at most α. The returned allocation R satisfies EJR-M. Assume for contradiction that for some group X, Definition 3.3 fails for X and parameter t. Consider the moment after the procedure removed the last group with parameter t t. If no agent in X has been removed, the procedure should have removed X with parameter t, a contradiction. Else, some agent j X has been removed. In this case, the procedure guarantees that uj(R ) t, which means that X satisfies Definition 3.3 with parameter t, again a contradiction.

3.2 Generalized Method of Equal Shares Despite the strong representation guarantee provided by Greedy EJR-M, the rule does not admit an obvious polynomial-time implementation. In the indivisible-goods setting, Peters and Skowron (2020) introduced the Method of Equal Shares (MES), originally known as Rule X, and showed that it satisfies indivisible-goods EJR and runs in polynomial time. We now extend their rule to our mixedgoods setting. At a high level, in Generalized MES, each agent is given a budget of α/n, which can be spent on buying the resource each piece of cake has cost equal to its length whereas each indivisible good costs 1. In each step, a piece of cake or an indivisible good that incurs the smallest cost per utility for agents who approve it is chosen, and these agents pay as equally as possible to cover the cost of the chosen resource. The rule stops once no more cake or indivisible good is affordable. Note that when the resource consists only of indivisible goods, Generalized MES is equivalent to the original MES of Peters and Skowron (2020).

Generalized MES

Step 1: Initialize R = (C , G ) = ( , ) and bi = α/n for each i N.

Step 2: Divide the remaining cake C into intervals I1, . . . , Ik so that each agent approves each interval either entirely or not at all. For each interval Ij = [x0, x1], x (x0, x1], and ρ 0, we say that Ij is (x, ρ)-affordable if X

i NIj min(bi, (x x0) ρ) = x x0,

where NIj N denotes the set of remaining agents who approve Ij. Similarly, for each remaining good g G and ρ 0, we say that g is ρ-affordable if X

i Ng min(bi, ρ) = 1,

where Ng N denotes the set of remaining agents who approve g.

Step 3: If for every ρ, no ρ-affordable good or (x, ρ)- affordable piece of cake exists, return R . Else, take either an interval Ij with the smallest ρ along with the largest x such that Ij is (x, ρ)-affordable, or a good g with the smallest ρ such that g is ρaffordable, depending on which ρ is smaller. In the former case, deduct min(bi, (x x0) ρ) from bi for each i NIj, and set C = C \[x0, x] and C = C [x0, x]. In the latter case, deduct min(bi, ρ) from bi for each i Ng, and set G = G \ {g} and G = G {g}. Remove all agents who have run out of budget from N, and go back to Step 2.

Example 3.9. For the instance in Figure 1, each agent starts with a budget of α/n = 1. The first iteration of Step 2 selects

the entire cake (with ρ = 1/2), and each agent pays 0.9/2 = 0.45 for this cake. Since neither agent has enough budget left to buy the indivisible good that she approves (which costs 1), the procedure terminates with only the cake. In the instance above, each agent on her own is 1-cohesive and approves a subset of the resource of size exactly 1, so the only EJR-M allocation is {g1, g2}. In particular, the allocation chosen by Generalized MES is not EJR-M. Proposition 3.10. Generalized MES doesn t satisfy EJR-M. Nevertheless, we prove that Generalized MES satisfies EJR-1 and, moreover, can be implemented efficiently. Theorem 3.11. Generalized MES satisfies EJR-1 and can be implemented in polynomial time. For indivisible-goods instances, Generalized MES reduces to the original MES of Peters and Skowron (2020), which satisfies indivisible-goods EJR. We prove that the analog holds for cake instances. Proposition 3.12. For cake instances, Generalized MES satisfies cake EJR.

3.3 Generalized PAV In the indivisible-goods setting, a well-studied rule is proportional approval voting (PAV), which chooses an allocation R that maximizes P i N Hui(R ), where Hx := 1 + 1 2 + + 1

x is the x-th harmonic number. We now show how to generalize PAV to the mixed-goods setting. To this end, we will use a continuous extension of harmonic numbers due to Hintze (2019), defined as

x k(x + k) =

for each real number x 0; in particular, these infinite sums converge. It is clear from the definition that the generalized harmonic numbers indeed extend the original harmonic numbers, and that Hx > Hy for all x > y 0. Moreover, Hx+1 Hx = 1 x+1 for all x 0.

Definition 3.13 (Generalized PAV). The Generalized PAV rule selects an allocation R with s(R ) α that maximizes P i N Hui(R ).

For ease of notation, we let H(R ) := P i N Hui(R ) for any allocation R , and call H(R ) the GPAV-score of R . Given the instance in Figure 1, since H1.9 + H0.9 > 1.45 + 0.93 > 1+1 = H1+H1, Generalized PAV selects the entire cake together with one of the indivisible goods. As the only EJR-M allocation in this instance is {g1, g2}, the allocation selected by Generalized PAV is not EJR-M. Proposition 3.14. Generalized PAV does not satisfy EJR-M. To show that Generalized PAV satisfies EJR-1, we establish a useful lemma on the growth rate of the generalized harmonic numbers. Lemma 3.15. For any x (0, ) and y [0, 1], it holds that Hx+y Hx y x+y.

Theorem 3.16. Generalized PAV satisfies EJR-1.

Proof. Let R = (C , G ) be a Generalized PAV allocation. By adding a piece of cake approved by no agent to the resource R as well as R if necessary, we may assume without loss of generality that s(R ) = α. Assume also that the cake C is represented by the interval [0, c ]. Whenever x + y > c , the interval [x, x + y] refers to [x, c ] [0, x + y c ], i.e., we cyclically wrap around the cake C . Suppose for contradiction that for some t > 0, there exists a t-cohesive group N with ui(R ) t 1 for all i N . Hence, there exists either a piece of cake of size 1 that is approved by all agents in N but not contained in R , or an indivisible good with the same property. We assume the latter case; the proof proceeds similarly in the former case. Denote this good by g , and let G := G {g } and R := (C , G ). We have

H(R ) H(R ) X

Hui(R )+1 Hui(R )

1 ui(R ) + 1

|N |2 P i N (ui(R ) + 1)

|N | (t 1) + |N | = |N |

where the second inequality follows from the inequality of arithmetic and harmonic means and the last inequality from the definition of a t-cohesive group. In other words, adding g increases the GPAV-score of R by at least n/α. For each good g G, denote by Ng N the set of agents who approve it. For each g G , we have

H(R ) H(R \ {g}) = X

Hui(R ) Hui(R ) 1

Letting N+ consist of the agents i with ui(R ) > 0, we get X

g G (H(R ) H(R \ {g})) = X

ui(G ) ui(R ) (1)

If there is a good g G such that H(R ) H(R \{g}) < n/α (clearly, g = g ), we can replace g with g in R and obtain a higher GPAV-score, contradicting the definition of R . Hence, we may assume that H(R ) H(R \{g}) n/α for every good g G . It follows that

g G (H(R ) H(R \ {g})) |G | n

Therefore, we have that |G | α, and so c 1. Now, for any x C , it holds that

H(R ) H(R \ [x, x + 1])

Hui(R ) Hui(R ) ui([x,x+1])

ui([x, x + 1])

ui(R ) , (2)

where the inequality follows from Lemma 3.15. Using (1) and (2), we get X

g G (H(R ) H(R \ {g}))

C (H(R ) H(R \ [x, x + 1])) dx

ui(G ) ui(R ) + Z

ui([x, x + 1])

ui(G ) ui(R ) + X

C ui([x, x + 1])

C ui([x, x + 1]) dx

1 ui(R ) (ui(G ) + ui(C )) X

i N 1 = n. (3)

Here, we have R

C ui([x, x + 1]) dx = ui(C ) because Z

C ui([x, x + 1]) dx = Z

C ℓ(Ci [x, x + 1]) dx

Ci C ℓ([y 1, y]) dy

= ℓ(Ci C ) = ui(C ),

where the second equality holds because a point y Ci belongs to the interval [x, x+1] if and only if x [y 1, y]. If it were the case that H(R ) H(R \[x, x+1]) n/α for every x C , we would have X

g G (H(R ) H(R \ {g}))

C (H(R ) H(R \ [x, x + 1])) dx

α = (α + 1) n

a contradiction with (3). Thus, it must be that H(R ) H(R \ [x, x + 1]) < n/α for some x C . By replacing the cake [x, x + 1] in R with the good g , we therefore obtain a higher GPAV-score than that of R . This yields the final contradiction and completes the proof.

In contrast to Generalized MES, Generalized PAV does not satisfy EJR in cake sharing.

Proposition 3.17. For cake instances, Generalized PAV does not satisfy cake EJR.

4 Proportionality Degree

In addition to the axiomatic study of representation in terms of criteria like EJR-M and EJR-1, another relevant concept for cohesive groups is the proportionality degree, which measures the average utility of the agents in each such group (Skowron 2021). In this section, we first derive tight bounds on the proportionality degree implied by EJR-M and EJR-1, and then investigate the proportionality degree of the rules we studied in Section 3.

Definition 4.1 (Average satisfaction). Given an instance and an allocation A, the average satisfaction of a group of agents N N with respect to A is 1 |N | P i N ui(A).

Definition 4.2 (Proportionality degree). Fix a function f : R>0 R 0. A rule M has a proportionality degree of f if for each instance I, each allocation A that M outputs on I, and each t-cohesive group of agents N , the average satisfaction of N with respect to A is at least f(t), i.e.,

i N ui(A) f(t).

For indivisible goods, S anchez-Fern andez et al. (2017) showed that EJR implies a proportionality degree of t 1

4.1 Proportionality Degree Implied by EJR-M/1

Our focus in this subsection is to establish tight bounds on the proportionality degree implied by EJR-M and EJR-1. Observe that for t < 1, a t-cohesive group may have an average satisfaction of 0 in an EJR-M or EJR-1 allocation. Indeed, if α = t and the resource consists only of a single indivisible good, which is approved by all n agents, then the set of all agents is t-cohesive, but the empty allocation is EJR-M and EJR-1. We therefore assume t 1 for our results from here on. We first show that the proportionality degree implied by EJR-M is t 1 t +1

2t , beginning with the lower bound.

Note that this quantity is roughly t/2.

Theorem 4.3. Given any instance and any real number t 1, let N N be a t-cohesive group and A be an EJR-M allocation. The average satisfaction of N with respect to A is at least t 1 t +1

The high-level idea behind the proof of Theorem 4.3 is that, given a t-cohesive group N and an EJR-M allocation, a t t

t fraction of the agents in N are guaranteed a utility of at least t . The remaining agents can then be partitioned into t disjoint subsets so that each subset consists of a 1/t fraction of the agents in N and the guaranteed utilities for these subsets drop arithmetically from t 1 to 0. We next give a matching upper bound.

Theorem 4.4. For any real numbers t 1 and ε > 0, there exists an instance, a t-cohesive group N , and an EJR-M allocation A such that the average satisfaction of N with respect to A is at most t 1 t +1

We do not prove Theorem 4.4 directly, as we will establish a stronger statement later in Theorem 4.7. Next, we show that the proportionality degree implied by EJR-1 is t 2+1/t

2t , which is slightly lower than that implied by EJR-M for every t. For the lower bound, we use a similar idea as in Theorem 4.3, but we need to be more careful about agents with low utility guarantees. In particular, even when the guarantee provided by the EJR-1 condition is negative, the actual utility is always nonnegative, so we need to round up the EJR-1 guarantee appropriately.

Theorem 4.5. Given any instance and any real number t 1, let N N be a t-cohesive group and A be an EJR-1 allocation. The average satisfaction of N with respect to A is greater than t 2+1/t

We now derive a matching upper bound.

Theorem 4.6. For any real numbers t 1 and ε > 0, there exists an instance, a t-cohesive group N , and an EJR-1 allocation A such that the average satisfaction of N with respect to A is at most t 2+1/t

Proof. Consider a cake instance with a sufficiently large number of agents n (to be specified later). Let α = t. Thus, we have |N| = t n/t t n/α. The cake is given by the interval [0, 2t], and the agents preferences are as follows.

Each agent i {1, 2, . . . , n/α 1} approves the interval [0, t]. Each agent i { n/α , n/α + 1, . . . , n} approves the interval h 0, t + i n/α

n/α + δ i , where δ (0, 1) is sufficiently small (to be specified later).

Since all n agents approve the interval [0, t], they form a tcohesive group N. We claim that allocation A = [t, 2t], which has size t = α, satisfies EJR-1, and that the average satisfaction of the N with respect to A is at most t 2+1/t

2 + ε when n and δ are suitably chosen. Details can be found in the full version of our paper (Lu et al. 2022).

4.2 Proportionality Degree of Specific Rules In this subsection, we investigate the proportionality degree of the rules that we studied in Section 3. We begin with Greedy EJR-M. Since Greedy EJR-M satisfies EJR-M, Theorem 4.3 immediately yields a lower bound. We derive a matching upper bound, which implies that the proportionality degree of Greedy EJR-M is t 1 t +1

Theorem 4.7. For any real numbers t 1 and ε > 0, there exists an instance, a t-cohesive group N , and an allocation A output by Greedy EJR-M such that the average satisfaction of N with respect to A is at most t 1 t +1

We provide here an intuition behind the proof of Theorem 4.7. We construct an indivisible-goods instance, make α an integer, and choose n to be a multiple of α. Our goal is to construct a target t-cohesive group of agents N with as small utilities as possible. Since Greedy EJR-M outputs an EJR-M allocation, the largest number of agents in N that receive utility 0 denote the set of these agents by N0 is n/α 1; otherwise, these agents would form a 1-cohesive group and cannot all receive utility 0. Similarly, among the agents in N \ N0, the largest number of agents that receive utility 1 denote the set of these agents by N1 is n/α, as we do not want N0 N1 to form a 2-cohesive group. Continuing inductively, we want to partition N into N0 N1 N t , with the agents in Nk receiving utility exactly k for each k. We add dummy agents and goods in order to make sure that, instead of all agents in N being satisfied at once by the Greedy EJR-M execution, the agents in N t are first satisfied along with some dummy agents via some dummy goods, then those in N t 1 are satisfied along with other dummy agents via other dummy goods, and so on. The dummy agents and goods need to be carefully constructed to make this argument work. In the indivisible-goods setting, Lackner and Skowron (2023, Prop. A.10) showed that for integers t, the proportionality degree of MES is between t 1

2 . Since Generalized MES satisfies EJR-1, Theorem 4.5 implies a lower bound of t 2+1/t

2 on its proportionality degree. On the other hand, since any t -cohesive group is also t-cohesive for t t , Lackner and Skowron s result implies an upper bound of t +1

2 for Generalized MES. Finally, we prove that Generalized PAV has a significantly higher proportionality degree than the other two rules that we study. In doing so, we extend a result of Aziz et al. (2018) from the indivisible-goods setting. Theorem 4.8. For any real number t 1, the average satisfaction of a t-cohesive group with respect to a Generalized PAV allocation is greater than t 1. We also demonstrate in the full version of our paper (Lu et al. 2022) that the bound t 1 is almost tight.

5 Conclusion and Future Work In this work, we have initiated the study of approval-based voting with mixed divisible and indivisible goods, which allows us to unify both the well-studied setting of multiwinner voting and the recently introduced setting of cake sharing. We generalized three important rules from multiwinner voting to our setting, determined their relations to our proposed extensions of the EJR axiom, and investigated their proportionality degree. While the Generalized MES and Generalized PAV rules only satisfy the weaker axiom of EJR-1, Greedy EJR-M satisfies the stronger axiom of EJR-M, thereby showing that an allocation fulfilling both axioms can be found in every instance. Nevertheless, an interesting open question is whether there exists a polynomial-time algorithm for computing such an allocation. Further directions for future work include exploring other axioms such as proportional justified representation (PJR) (S anchez-Fern andez et al. 2017) and the core.

Acknowledgments

This work was partially supported by ARC Laureate Project FL200100204 on Trustworthy AI , by the Singapore Ministry of Education under grant number MOE-T2EP202210001, by the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1 and the Graduiertenkolleg Facets of Complexity (GRK 2434), and by an NUS Start-up Grant. We thank the anonymous reviewers for their valuable feedback.

Aziz, H.; Bogomolnaia, A.; and Moulin, H. 2020. Fair mixing: the case of dichotomous preferences. ACM Transactions on Economics and Computation, 8(4): 18:1 18:27. Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justified representation in approvalbased 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 AAAI Conference on Artificial Intelligence (AAAI), 902 909. Bei, X.; Li, Z.; Liu, J.; Liu, S.; and Lu, X. 2021a. Fair division of mixed divisible and indivisible goods. Artificial Intelligence, 293: 103436. Bei, X.; Liu, S.; Lu, X.; and Wang, H. 2021b. Maximin fairness with mixed divisible and indivisible goods. Autonomous Agents and Multi-Agent Systems, 35(2): 34:1 34:21. Bei, X.; Lu, X.; and Suksompong, W. 2022. Truthful cake sharing. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 4809 4817. Extended version available at ar Xiv:2112.05632v3. Bhaskar, U.; Sricharan, A. R.; and Vaish, R. 2021. On approximate envy-freeness for indivisible chores and mixed resources. In Proceedings of the 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 1:1 1:23. Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; and Niedermeier, R. 2019. An experimental view on committees providing justified representation. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 109 115. Elkind, E.; Faliszewski, P.; Igarashi, A.; Manurangsi, P.; Schmidt-Kraepelin, U.; and Suksompong, W. 2022. The price of justified representation. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 4983 4990. Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017. Multiwinner voting: a new challenge for social choice theory. In Endriss, U., ed., Trends in Computational Social Choice, chapter 2, 27 47. AI Access. Hintze, W. 2019. Analytic continuation of harmonic series. http://math.stackexchange.com/a/3058569. Accessed 202207-07.

Kilgour, D. M. 2010. Approval balloting for multi-winner elections. In Laslier, J.-F.; and Sanver, M. R., eds., Handbook on Approval Voting, 105 124. Springer. Lackner, M.; and Skowron, P. 2023. Multi-Winner Voting with Approval Preferences. Springer. Lu, X.; Peters, J.; Aziz, H.; Bei, X.; and Suksompong, W. 2022. Approval-based voting with mixed goods. Co RR, abs/2211.12647. Peters, D.; Pierczy nski, G.; and Skowron, P. 2021. Proportional participatory budgeting with additive utilities. In Proceedings of the 35th Conference on Neural Information Processing Systems (Neur IPS), 12726 12737. Peters, D.; and Skowron, P. 2020. Proportionality and the limits of welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), 793 794. Extended version available at ar Xiv:1911.11747v2. Procaccia, A. D. 2016. Cake cutting algorithms. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, chapter 13, 311 329. Cambridge University Press. Robertson, J.; and Webb, W. 1998. Cake-Cutting Algorithms: Be Fair if You Can. Peters/CRC Press. 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 AAAI Conference on Artificial Intelligence (AAAI), 670 676. Skowron, P. 2021. Proportionality degree of multiwinner rules. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), 820 840.