Approval-based voting with mixed goods
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Lu, Xinhang; Peters, Jannik; Aziz, Haris; Bei, Xiaohui; Suksompong, Warut Article — Published Version Approval-based voting with mixed goods Social Choice and Welfare Provided in Cooperation with: Springer Nature Suggested Citation: Lu, Xinhang; Peters, Jannik; Aziz, Haris; Bei, Xiaohui; Suksompong, Warut (2024) : Approval-based voting with mixed goods, Social Choice and Welfare, ISSN 1432-217X, Springer, Berlin, Heidelberg, Vol. 62, Iss. 4, pp. 643-677, https://doi.org/10.1007/s00355-024-01511-8 This Version is available at: https://hdl.handle.net/10419/314984 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/
Social Choice and Welfare (2024) 62:643–677 https://doi.org/10.1007/s00355-024-01511-8 ORIGINAL PAPER Approval-based voting with mixed goods Xinhang Lu1·Jannik Peters2·Haris Aziz1·Xiaohui Bei3· Warut Suksompong4 Received: 21 April 2023 / Accepted: 29 January 2024 / Published online: 27 February 2024 © The Author(s) 2024, corrected publication 2024 Abstract 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—GreedyEJR, 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 A preliminary version of this paper appears in Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023). This version contains additional results on a new notion called “strong EJR-1” (Sect. 3.2), a tight bound on average satisfaction (Theorem B.2), as well as all proofs omitted from the conference version. BWarut Suksompong [email protected] 1University of New South Wales, Sydney, Australia 2Technische Universität Berlin, Berlin, Germany 3Nanyang Technological University, Singapore, Singapore 4National University of Singapore, Singapore, Singapore 123
644 X. Lu et al. 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 et al. (2024). 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”, and cake sharing is the collective choice problem of selecting a subset of this resource. 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 indivisible and divisible goods.1This generality allows our model to capture more scenarios 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 et al. 2021;Kawaseetal.2023; Nishimura and Sumita 2023). 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 nagents and k(indivisible) goods can be chosen, then JR requires that whenever a group of at least n/kagents approve a common good, some agent in that group must have an approved good in the selected set. A well-studied strengthening of JR is extended justified representation (EJR), which says that for each positive integer t,if a group of at least t·n/kagents approve no fewer than tcommon goods (such a group is said to be t-cohesive), some agent in that group must have no fewer than tapproved 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. (2024, Sec. 7) adapted EJR by imposing the condition for every positive real number t,and proved that the resulting notion is satisfied by the maximum Nash 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”. 123
Approval-based voting with mixed goods 645 welfare (MNW) rule.3Can we unify the two versions of EJR for our generalized setting in such a way that the guaranteed existence is maintained?4 1.1 Our contributions In Sect. 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 twhenever 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 tbut 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: GreedyEJR, the method of equal shares (MES), and proportional approval voting (PAV). We show that GreedyEJR-M, our generalization of GreedyEJR, 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 GreedyEJR-M and Generalized MES guarantee the cake version of EJR in cake sharing, Generalized PAV does not. In Sect. 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 Sect. 3; in particular, we find that Generalized PAV has a significantly higher proportionality degree than both GreedyEJR-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 mixed-goods 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.Apiece 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 Cconsisting of a set of disjoint intervals IC,we let (C):=I∈IC(I). Abundle Rconsists of a (possibly empty) piece of cake C⊆Cand a (possibly empty) set of indivisible goods G⊆G;the size of such a 3They also noted that JR does not admit a natural analog for cake sharing, since there is no discrete unit of cake. 4As further evidence for the generality of our setting, we remark that, as Bei et al. (2024, Sec. 1.2) pointed out, cake sharing itself generalizes another collective choice setting called fair mixing (Aziz et al. 2020). 123
646 X. Lu et al. Table 1 Overview of our results. The check mark (✓) indicates that the rule satisfies the property; the cross mark (✗) indicates that it does not GreedyEJR-M Gen. MES Gen. PAV EJR-M ✓✗✗ EJR-1 ✓✓ ✓ Proportionality degree t·1−t+1 2t≈t 2t−2+1/t 2,t+1 2≈t 2>t−1 Indivisible-goods EJR ✓∗✓∗✓∗ Cake EJR ✓✓ ✗ Polynomial-time computation ? ✓✗∗ Entries marked by an asterisk follow from known results in multiwinner voting; the entry on the computation of Generalized PAV relies on the assumption that P = NP. We also show that the proportionality degree implied by EJR-M and EJR-1 is t·1−t+1 2tand t−2+1/t 2,which are both approximately t/2, respectively Fig. 1 A mixed-goods instance with two agents N={1,2},two indivisible goods G={g1,g2}, a cake Cof 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 GC g1g2 00.9 R R1 R2 bundle Ris 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∈Napproves a bundle Ri=(Ci,Gi)of the resource.5 The utility of agent ifor a bundle Ris given by ui(R):=s(Ri∩R)=(Ci∩C)+ |Gi∩G|.Let α∈(0,c+m]be a given parameter, and assume that a bundle Awith s(A)≤αcan be chosen and collectively allocated to the agents6; we also refer to an allocated bundle as an allocation. (Note that we allow s(A)≤αrather than requiring s(A)=α;this is a slight deviation from the standard multiwinner voting model.) An instance consists of the resource R,the agents Nand 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).7An example instance is shown in Fig. 1. Amechanism or rule Mmaps any instance to an allocation of the resource. For any property Pof allocations, we say that a rule Msatisfies property Pif for every 5Approval preferences can be given explicitly as part of the input for algorithms, so we do not need the cake-cutting query model of Robertson and Webb (1998). In particular, the cake preferences can be described by the endpoints of the cake intervals approved by each agent. 6Instead of the variable kas 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. (2024) for cake sharing. 7When c=0 the cake consists of a single point, which yields utility 0 to every agent, so we may ignore it. 123
Approval-based voting with mixed goods 647 instance, the allocation output by Msatisfies P.An example of a rule is the maximum Nash welfare (MNW) rule, which returns an allocation Athat maximizes the product i∈Nui(A)of the agents’ utilities.8 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(i∈N∗Ri)≥t.For an indivisiblegoods instance, Aziz et al. (2017) defined EJR as follows: an allocation Asatisfies EJR if for every positive integer tand every t-cohesive group of agents N∗,at least one agent in N∗receives utility at least t.Bei et al. (2024) adapted this axiom to cake sharing by considering every positive real number tinstead of only positive integers.9 To distinguish between these two versions of EJR, as 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 Awith s(A)≤α is said to satisfy extended justified representation up to β(EJR-β)if for every positive real number tand every t-cohesive group of agents N∗,it holds that uj(A)>t−β for some j∈N∗.10 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 u j(A)>t−βin Definition 3.1 to u j(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 nand αsuch that α=β·n,and assume that all agents approve disjoint nonempty subsets Giof 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 ngoods 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 Sect. 3.1. Before that, we introduce 8Ties 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. 9Note that the indivisible-goods version with positive integers tmay be meaningless in the cake setting, e.g., if the entire cake has length less than 1.More generally, the restriction to positive integers tis unnatural for cake, as there is no discrete unit of cake. 10 For β=1,Peters et al. (2021) considered a somewhat similar notion called “EJR up to one project” in the setting of participatory budgeting with indivisible projects. 123
648 X. Lu et al. 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 tfor 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 utility higher than tdue to the indivisibility of the goods. Definition 3.3 (EJR-M) Given an instance, an allocation Awith s(A)≤αis said to satisfy extended justified representation for mixed goods (EJR-M) if the following holds: For every positive real number tand every t-cohesive group of agents N∗for which there exists R∗⊆Rsuch that s(R∗)=tand R∗⊆Rifor all i∈N∗,it holds that uj(A)≥tfor some j∈N∗. Note that for indivisible-goods instances, the condition s(R∗)=tcan 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 talways 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 u j(A)≥tfor some j ∈N∗. Proof Let R∗=i∈N∗Ri,so s(R∗)≥t,and let m∗be the number of indivisible goods in R∗.If m∗≥t,then by Definition 3.3, there exists j∈N∗such that uj(A)≥t.Else, m∗<t,which means that R∗contains a piece of cake of length at least t−m∗.In this case, by considering the m∗indivisible goods and a piece of cake of length exactly t−m∗commonly approved by all agents in N∗,Definition 3.3 implies the existence of j∈N∗such that uj(A)≥t≥t. 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 real number t,the smallest integer greater than t−1ist.On the other hand, for cake instances, EJR-1 is weaker than cake EJR. In the cake setting, Bei et al. (2024) 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-β. Proof It suffices to prove the statement for every positive integer β. Indeed, once we have this, then for any nonnegative real number β,there exists a positive integer β>β .Since EJR-βimplies EJR-β, in an instance in which no MNW allocation satisfies EJR-β, there also does not exist an MNW allocation satisfying EJR-β. 123
Approval-based voting with mixed goods 649 Fix a positive integer β, and let γ=β+2.Consider an indivisible-goods instance with n=γ2+γagents, m=2γgoods, and α=γ+1.The first γ2agents all approve goods g1,...,gγ,while agent γ2+ionly approves good gγ+ifor 1 ≤i≤γ. Notice that the first γ2agents form a γ-cohesive group, so at least one of them must receive utility no less than γ−β=2inanEJR-βallocation. In particular, at least two goods among g1,...,gγmust be chosen. However, every MNW allocation contains gγ+1,gγ+2,...,g2γalong with exactly one of g1,...,gγ.It follows that no MNW allocation satisfies EJR-β. 3.1 GreedyEJR-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 GreedyEJR rule from the indivisible-goods setting (Bredereck et al. 2019; Peters et al. 2021; Elkind et al. 2022); we therefore call it GreedyEJR-M and describe it below. GreedyEJR-M Step 1: Initialize N=Nand R=∅. Step 2: Let t∗be the largest nonnegative real number for which there exist ∅ = N∗⊆Nand R∗⊆Rsuch that N∗is a t∗-cohesive group, R∗⊆Rifor 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 Rto R. Step 3: If N=∅,return R.Else, go back to Step 2. Example 3.7 Consider the instance in Fig. 1.Wehaven/α =1,and Step 2 of GreedyEJR-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 GreedyEJR-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 nonempty group of agents X⊆N,the set TX:=t≥0|X|≥t·n αand there exists Y⊆ i∈X Riwith s(Y)=t 123
650 X. Lu et al. is a union of a finite number of (possibly degenerate) closed intervals, and is nonempty because 0 ∈TX.Therefore, TXhas a maximum. The value t∗chosen in Step 2 is then the largest among the maxima of TXacross all nonempty 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 Rwith s(R)≤α. Indeed, if an iteration of Step 2 uses value t∗,it removes11 at least t∗·n/α agents from Nand adds a resource of size at most t∗to R.Since only nagents can be removed in total, the added resource has size at most α. •The returned allocation Rsatisfies EJR-M. Assume for contradiction that for some group X,Definition 3.3 fails for Xand parameter t.Consider the moment after the procedure removed the last group with parameter t∗≥t.If no agent in Xhas been removed, the procedure should have removed Xwith parameter t,a contradiction. Else, some agent j∈Xhas been removed. In this case, the procedure guarantees that uj(R)≥t,which means that Xsatisfies Definition 3.3 with parameter t,again a contradiction. 3.2 Generalized Method of Equal Shares Despite the strong representation guarantee provided by GreedyEJR-M, the rule does not admit an obvious polynomial-time implementation.12 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 mixed-goods 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). 11 If t∗=0,the iteration still removes at least one agent from N,but we do not need this fact here. 12 Indeed, determining t∗in Step 2 of GreedyEJR-M potentially requires inspecting an exponential number of subsets N∗⊆N. 123
Approval-based voting with mixed goods 657 = i∈N+1 ui(R)ui(G)+ui(C)≤ i∈N 1=n.(3) Here, we have Cui([x,x+1])dx=ui(C)because C ui([x,x+1])dx=C (Ci∩[x,x+1])dx =Ci∩C ([y−1,y])dy=Ci∩C 1dy=(Ci∩C)=ui(C), where the second equality holds because a point y∈Cibelongs 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 g∈G (H(R)−H(R\{g})) +C (H(R)−H(R\[x,x+1])) dx ≥|G|· n α+c·n α=(α +1)·n α>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 Rwith 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.19 For cake instances, Generalized PAV does not satisfy cake EJR. To prove this statement, we use the following proposition. Proposition 3.20 (Bei et al. 2024)Let f :R≥0→[−∞,∞)be a strictly increasing function which is differentiable in (0,∞). For cake sharing,if a rule that always chooses an allocation Rmaximizing i∈Nf(ui(R)) satisfies cake EJR,then there exists a constant c such that f (x)=c/x for all x ∈(0,∞).16 Proof of Proposition 3.19 For a positive integer r,one can check that the derivative with respect to xof r k=1 x k(x+k)is r k=1 1 (x+k)2,which converges as r→∞.This means that Hx=∞ k=1 x k(x+k)is differentiable as a function of x,and its derivative is ∞ k=1 1 (x+k)2.In particular, there is no constant csuch that H x=c/xfor all x∈(0,∞)—for example, this can be seen by observing that, as xapproaches 0 from above, H xapproaches ∞ k=11/k2=π2/6 rather than ∞.By Proposition 3.20, Generalized PAV does not satisfy cake EJR. 16 This is Theorem 7.8 in their work. Bei et al. normalized the length of the cake to 1,but the same proof works in our setting. 123
658 X. Lu et al. 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 that we studied in Sect. 3. Definition 4.1 (Average satisfaction) Given an instance and an allocation A,the average satisfaction of a group of agents N⊆Nwith respect to Ais 1 |N|·i∈Nui(A). Definition 4.2 (Proportionality degree) Fix a function f:R>0→R≥0.AruleM has a proportionality degree of fif for each instance I,each allocation Athat M outputs on I,and each t-cohesive group of agents N∗,the average satisfaction of N∗ with respect to Ais at least f(t), i.e., 1 |N∗|· i∈N∗ ui(A)≥f(t). For indivisible goods, Sánchez-Fernández et al. (2017) showed that EJR implies a proportionality degree of t−1 2.We will show that in our setting, both EJR-M and EJR-1 imply a proportionality degree of roughly t/2,with the guarantee for EJR-M being slightly higher. In addition, we will establish that both GreedyEJR-M and Generalized MES have a proportionality degree of approximately t/2,while the proportionality degree of Generalized PAV is higher than t−1. 4.1 Proportionality degree implied by EJR-M and EJR-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,at-cohesive group may have an average satisfaction of 0 in an EJR-M or EJR-1 allocation. Indeed, if α=tand the resource consists only of a single indivisible good, which is approved by all nagents, 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∗⊆Nbeatcohesive group and A be an EJR-M allocation. The average satisfaction of N∗with respect to A is at least t·1−t+1 2t. 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 tfraction of the agents in N∗are guaranteed a utility of at least t.The remaining agents can then be partitioned into tdisjoint subsets so that each subset consists of a 1/tfraction of the agents in N∗and the guaranteed utilities for these subsets drop arithmetically from t−1to0. 123
Approval-based voting with mixed goods 659 Proof of Theorem 4.3 For ease of notation, let r:=n/α, and note that |N∗|≥tr. Since N∗is t-cohesive, by Proposition 3.4, some agent i1∈N∗gets utility at least t from the allocation A.If |N∗\{i1}|≥t·r,then since N∗\{i1}is t-cohesive, Proposition 3.4 implies that another agent i2= i1gets utility at least tfrom A. Applying this argument repeatedly, as long as there are at least t·ragents left, Proposition 3.4 implies that one of them gets utility at least t.Let N tconsist of the agents with guaranteed utility tfrom this argument, and note that |N t|= |N∗|−t·r+1≥tr−t·r+1.Let N:=N∗\N t;we have | N|=t·r−1. Denote by Ntan arbitrary subset of N tof size exactly tr−t·r+1. Now, let us consider the agents in N.Applying an argument similar to the one in the previous paragraph but using (t−1)-cohesiveness, we find that Ncontains at least t·r−(t−1)·ragents with a utility of at least t−1 each; let these agents form Nt−1.Continuing inductively, we can partition Ninto tpairwise disjoint sets Nt−1,Nt−2,...,N1,N0such that for each j∈{0,1,...,t−1},every agent in Njgets utility at least jfrom the allocation A. For each j∈{1,2,...,t},it holds that j−1 k=0Nk=jr−1.Furthermore, we have j·tr≥ j·t·r=t·(jr +1)−t≥t·jr−t=t·(jr−1), which implies that j−1 k=0Nk tr=jr−1 tr≤j t. Since t k=0Nk=tr,it follows that t k=jNk tr≥t−j t=t−t t+t− j t=t−t t+ t−1 k=j 1 t.(4) With this relationship in hand, we can bound the average satisfaction of Nt∪ N= t k=0Nkas 1 t k=0Nk · i∈t k=0Nk ui(A)≥1 tr·⎛ ⎝ t k=0 |Nk|·k⎞ ⎠ = t k=0 |Nk| tr·k = t d=1 t k=d |Nk| tr 123
660 X. Lu et al. ≥ t d=1⎛ ⎝t−t t+ t−1 k=d 1 t⎞ ⎠ =t−t t·t+ t d=1 t−1 k=d 1 t =t−t t·t+1 t·t·(t−1) 2 =t t·2t−t−1 2 =t·1−t+1 2t, where the first inequality holds because each agent in Nkgets utility at least kand the second inequality follows from (4). Since every agent in N t\Ntgets utility at least t,the average satisfaction of N t\Ntis at least t≥t·1−t+1 2t.As the average satisfaction of N∗is a convex combination of the corresponding quantities for N t\Ntand Nt∪ N,it is at least t·1−t+1 2t,as desired. We next give a matching upper bound. Theorem 4.4 For any real numbers t ≥1and ε>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 2t+ε. 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 2= (t−1)2 2t,which is slightly lower than that implied by EJR-M for every t>1.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∗⊆Nbeatcohesive group and A be an EJR-1allocation. The average satisfaction of N∗with respect to A is greater than t−2+1/t 2. To prove this theorem, we will use the following claim, which provides a lower bound for the average of a nonincreasing and nonnegative sequence with a particular structure. Claim 1 Let r>0 and t≥1 be real numbers. Consider any nonincreasing and nonnegative sequence t−1,a1,a2,...,atr−r,b1,b2,...,br−1, 123
Approval-based voting with mixed goods 661 in which a1,a2,...,atr−rforms an arithmetic subsequence with common difference −1/r.If t−1−a1≤1/r,then the average of the entire sequence is at least t−2+1/t 2. Proof We start by showing that the average of the subsequence t−1,a1,a2,...,atr−r is at least t−1 2.The bound holds trivially if tr−r=0;we therefore assume that tr−r≥1.Let us continually decrease each of the numbers a1,a2,...,atr−r by the same amount until (at least) one of the following two cases occurs: •Case 1: The difference between t−1 and a1becomes 1/r,i.e., a1=t−1−1/r. Note that atr−ris still nonnegative in this case. •Case 2:atr−rbecomes 0.Note that the difference between t−1 and a1is still at most 1/r. Clearly, the average of the subsequence in question t−1,a1,a2,...,atr−rdoes not increase during this process. Thus, it suffices to show that in each of the above two cases, this average is at least t−1 2after the process. •In Case 1, the subsequence t−1,a1,a2,...,atr−ris now an arithmetic sequence, so its average is (t−1)+atr−r 2≥t−1 2,where the inequality follows from the fact that atr−r≥0 in this case. •In Case 2, consider the arithmetic sequence (dk)tr−r k=0with d0=t−1 and dtr−r=0.Let −βbe its common difference, so βis nonnegative. On the one hand, we have t−1=d0=dtr−r+β·(tr−r)=β·(tr−r). On the other hand, we have t−1=(t−1−a1)+a1 =(t−1−a1)+(tr−r−1)·1/r≤(tr−r)·1/r, where the inequality holds because t−1−a1≤1/rin Case 2. As a result, we have β·(tr−r)≤(tr−r)·1/r,that is, β≤1/r.Hence, each term of the sequence t−1,a1,a2,...,atr−ris at least as large as the corresponding term of the sequence (dk)tr−r k=0.We conclude that the average of t−1,a1,a2,...,atr−ris at least that of (dk)tr−r k=0,which is d0+dtr−r 2= t−1 2. In both cases, we have proven that the average of the sequence t−1,a1,a2,...,atr−r is at least t−1 2. Next, we show that the average of the entire sequence t−1,a1,a2,...,atr−r,b1,b2,...,br−1 123
662 X. Lu et al. is at least t−2+1/t 2.This can be done by taking all bi’s to be 0 and applying the lower bound on the average of t−1,a1,a2,...,atr−rthat we previously computed: 1 1+(tr−r)+(r−1)·t−1 2·(1+(tr−r)) =1+tr−r tr·t−1 2 =1+1−r tr·t−1 2 ≥1+1−(r+1) tr·t−1 2 =1−r tr·t−1 2 ≥1−r tr ·t−1 2 =(t−1)2 2t =t−2+1/t 2. The claim is thus proven. We are now ready to establish Theorem 4.5. Proof of Theorem 4.5 For notational convenience, let r:=n/α. We have |N∗|≥tr, where the inequality holds because N∗is t-cohesive. EJR-1 implies that some agent i1∈N∗gets utility greater than t−1 from the allocation A.If |N∗\{i1}| ≥ tr, then since there still exists a subset of the resource of size at least tcommonly approved by the agents in N∗\{i1},EJR-1 implies that another agent i2= i1gets utility greater than t−1 from A.Applying this argument repeatedly, as long as there are at least t·r agents left, EJR-1 implies that one of them gets utility greater than t−1.Let Nt−1 consist of the agents with guaranteed utility greater than t−1 from this argument. Let N:=N∗\Nt−1and n:=| N|,and note that n=tr−1. Now, let us consider the agents in N.Since | N|=n≥n r·rand si∈ NRi≥t> n r,the agents in Nform an n r-cohesive group. By EJR-1, some agent in Ngets utility greater than n r−1.Continuing inductively, the guaranteed utility drops arithmetically with a common difference of 1/r.Note also that an agent’s actual utility is always nonnegative. To calculate the average satisfaction of the t-cohesive group N∗,we first focus on the agents in Nalong with agent i1discussed earlier in the proof. The average satisfaction of these agents is 1 1+n·⎛ ⎝ui1(A)+ i∈ N ui(A)⎞ ⎠>1 1+n·⎛ ⎝t−1+ i∈ N ui(A)⎞ ⎠ 123
Approval-based voting with mixed goods 663 ≥1 1+n·⎛ ⎝t−1+n j=rj r−1+ r−1 j=1 0⎞ ⎠ ≥t−2+1/t 2. The last inequality is due to Claim 1: We have a nonincreasing and nonnegative sequence with t−1 as the first element, followed by a decreasing arithmetic sequence with tr−rterms whose common difference is −1/rand whose first term, tr−1 r−1,is at most 1/raway from t−1,and then followed by r−1 zeros. The average satisfaction of Nt−1\{i1},if this set is not empty, is greater than t−1.As the average satisfaction of N∗is a convex combination of the corresponding quantities for Nt−1\{i1}and N∪{i1},it is greater than t−2+1/t 2,as desired. We now derive a matching upper bound. Theorem 4.6 For any real numbers t ≥1and ε>0,there exists an instance,a t-cohesive group N∗,and an EJR-1allocation A such that the average satisfaction of N∗with respect to A is at most t−2+1/t 2+ε. 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 0,t+i−n/α n/α +δ, where δ∈(0,1)is sufficiently small (to be specified later). Since all nagents approve the interval [0,t],they form a t-cohesive group N. We claim that allocation A=[t,2t],which has size t=α, satisfies EJR-1. Consider a t-cohesive group for some value of t>0.If t∈(0,1), the requirement of EJR-1 is trivially fulfilled. Since n=t·n/α, we may therefore assume that t∈[1,t]. Consider agent t·n/α∈N,who approves the interval 0,t+t·n/α−n/α n/α +δ; this agent gets utility at least t·n/α−n/α n/α +δ≥t·n/α−n/α n/α +δ>t−1fromthe allocation A.Since every t-cohesive group contains at least t·n/αagents, it must contain an agent who gets utility greater than t−1 from A.This means that Asatisfies EJR-1, as claimed. The average satisfaction of the t-cohesive group Nwith respect to the EJR-1 allocation Ais 1 |N|· i∈N ui(A)=1 n· n i=n/αi−n/α n/α +δ =α n2· n i=n/α (i−n/α) +1 n· n i=n/α δ =α n2·(n/α−n/α) +(n−n/α) 2·(n−n/α+1) 123
664 X. Lu et al. +δ n·(n−n/α+1) ≤α n2·(n−n/α +1)2 2+δ n·(n−n/α +1) =α−2+1/α 2+δ·(α −1) α+α 2n2+α−1+δ n =t−2+1/t 2+δ·(t−1) t+t 2n2+t−1+δ n, where the inequality holds because n/α−n/α ≤1 and −n/α≤−n/α. Finally, we choose a sufficiently large nand a sufficiently small δso that δ·(t−1) t+t 2n2+t−1+δ n≤ ε;this ensures that the average satisfaction of Nis at most t−2+1/t 2+ε, as desired. 4.2 Proportionality degree of specific rules In this subsection, we investigate the proportionality degree of the rules that we studied in Sect. 3. We begin with GreedyEJR-M. Since GreedyEJR-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 GreedyEJR-M is t·1−t+1 2t. Theorem 4.7 For any real numbers t ≥1and ε>0,there exists an instance,atcohesive group N∗,and an allocation A output by GreedyEJR-M such that the average satisfaction of N∗with respect to A is at most t·1−t+1 2t+ε. We first provide an intuition behind the proof of Theorem 4.7. We construct an indivisible-goods instance, make αan integer, and choose nto be a multiple of α. Our goal is to construct a target t-cohesive group of agents N∗with as small utilities as possible. Since GreedyEJR-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∪···∪ Nt,with the agents in Nkreceiving utility exactly kfor 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 GreedyEJR-M execution, the agents in Ntare first satisfied along with some dummy agents via some dummy goods, then those in Nt−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. Proof of Theorem 4.7 Let α=t·(t+1) 2+1=t2+t+2 2,and note that αis an integer. We will construct an indivisible-goods instance with a sufficiently large number of agents n(to be specified later), where nis a multiple of αthat is at least 2α. Observe 123
Approval-based voting with mixed goods 665 that t·n α!= t· n α+(t−t)·n α!=t· n α+ (t−t)·n α!. Since t−t<1,we can choose nlarge enough so that (t−t)·n α≤n α−1. When this holds, we have t·n α≤ t·n α!≤t· n α+n α−1=(t+1)·n α−1.(5) This inequality will help ensure that we can construct a t-cohesive group that is not (t+1)-cohesive. Note that in an indivisible-goods instance, a t-cohesive group must commonly approve at least tindivisible goods. We now describe our instance. Let G={g1,g2,...,gt}∪t k=1DG kbe the set of indivisible goods, where for each k∈{1,2,...,t},DG kcontains exactly k indivisible goods. In particular, the sets {g1,g2,...,gt},DG 1,DG 2,...,DG t are all disjoint. Our specifications for the agents are slightly different depending on whether t≥2ort∈[1,2);we distinguish between the two cases below. Case 1: t≥2 Recalling that n/α is an integer, we partition the set of all agents N into the following pairwise disjoint sets: N0="1,2,..., n α−1#, N1="n α,n α+1,...,2·n α−1#, . . . Nk="k·n α,k·n α+1,...,(k+1)·n α−1#, . . . Nt−1="(t−1)·n α,(t−1)·n α+1,...,t· n α−1#, Nt="t· n α,t· n α+1,..., t·n α!#, D1,D2,...,Dt−1,Dt, where N∗:=t k=0Nk=$1,2,...,t·n α%is our target t-cohesive group and t k=1Dkconsists of “dummy agents”. More specifically: •D1contains a single agent; •For each k∈{2,...,t−1},Dkcontains (k−1)·n αagents; 123
666 X. Lu et al. •Dtcontains t· n α−t·n α−t· n α+1=2t· n α−t·n α−1 agents. Observe that Nt∪Dt=t· n α. Note that D1and Dtare different sets because t≥2.We verify that the total number of agents is indeed n: |N|=⎛ ⎝ t & k=0 Nk⎞ ⎠∪⎛ ⎝ t & k=1 Dk⎞ ⎠ =⎛ ⎝ t−1 & k=0 Nk⎞ ⎠∪D1∪⎛ ⎝ t−1 & k=2 Dk⎞ ⎠∪Nt∪Dt =t· n α−1+1+ t−1 k=2 (k−1)·n α+t· n α =2t· n α+n α·(2−1)+((t−1)−1) 2·((t−1)−2+1) =n α·2t+(t−1)·(t−2) 2 =n α·t2+t+2 2 =n. The agents’ preferences are as follows. •The agents in N0approve the goods in {g1,g2,...,gt}. •For each k∈{1,2,...,t},the agents in Nkapprove the goods in {g1,g2,...,gt}∪DG k,and the agents in Dkapprove the goods in DG k. This completes the description of our instance. Since |N∗|=t·n α,inequality (5) implies that N∗is not (t+1)-cohesive. On the other hand, since the agents in N∗ commonly approve the goods g1,g2,...,gt,N∗is t-cohesive. Also, notice that t∗=tis the largest integer such that a t∗-cohesive group exists in our instance. We now consider the execution of GreedyEJR-M on the above instance. Since our instance consists exclusively of indivisible goods, only integers t∗are relevant for the EJR-M condition in each round of GreedyEJR-M. We claim that GreedyEJR-M can return the allocation A=t k=1DG k,which has size t·(t+1) 2≤α. Given the instance, at the beginning, t∗=tis the largest number such that the EJR-M condition is satisfied: it is satisfied with Nt∪Dt,DG t,because Nt∪Dt=t· n α and the agents in Nt∪Dtcommonly approve all goods in DG t,which has size exactly t.17 GreedyEJR-M removes the agents in Nt∪Dtand adds the goods in DG tto the allocation A.Now, there is no more t-cohesive group, and t∗=t−1 becomes the largest number such that the EJR-M condition is satisfied: it is satisfied 17 At this stage, the EJR-M condition with t∗=talso holds with (N∗,{g1,g2,...,gt}). 123
Approval-based voting with mixed goods 673 Finally, assume that tis irrational. Let t>tand ε<εbe rational numbers such that t=tand t+z(1−z) t+ε<t+z(1−z) t+ε, where z=t−t; the existence of such a pair (t,ε )is guaranteed by the fact that, as we increase tslightly, the value of t+z(1−z) tchanges continuously. From our previous argument, there exists an instance in which no allocation provides an average satisfaction of at least t−1+z(1−z) t+ε to all t-cohesive groups. Suppose for contradiction that there is an allocation that provides an average satisfaction of at least t−1+z(1−z) t+εto all t-cohesive groups in this instance. Because any t-cohesive group is also t-cohesive, this allocation would also provide an average satisfaction of at least t−1+z(1−z) t+ε>t−1+z(1−z) t+ε to all t-cohesive groups, a contradiction. We also show that the bound proved in Theorem B.1 is—perhaps surprisingly— tight. Theorem B.2 For any real number t ≥1,let z =t−tdenote the fractional part of t. Given any instance,there exists an allocation that provides an average satisfaction of at least t −1+z(1−z) tto all t-cohesive groups. Proof Let I=N,R,(Ri)i∈N,αbe an instance, and let k=t(so t=k+z). Let T={T1,T2,...,Tp}be the set of all t-cohesive groups in instance I.By definition, for each i∈{1,2,...,p},it holds that |Ti|≥t·n/α and s(j∈TiRj)≥t. We create another instance I=N, R,( Ri)i∈N,αwith the same set of agents N and a modified resource R=p i=1 RTisuch that •foranypairofdistincti,j∈{1,...,p}, RTi∩ RTj=∅; •for each i∈{1,...,p}, RTiconsists of k indivisible goods that are commonly approved (only) by the agents in Ti. Put differently, the resource RTiin instance Icorresponds to the resource j∈TiRjin instance I,but has a weakly smaller size. The idea here is that we are “worsening” the instance in terms of the average satisfaction for all t-cohesive groups. More specifically, given an allocation Rfor instance I,we can select an allocation Rfor instance I as follows: for each RTi,if ≤k(indivisible) goods from RTiare included in R, then we include a resource of size from j∈TiRjin R.(Even if some resource gets included in Rmultiple times during this process, it is effectively only included once.) Clearly, s(R)≤s( R)≤α. Moreover, it can be seen that for each i∈{1,...,p}, 1 |Ti|· j∈Ti uj(R)≥1 |Ti|· j∈Ti uj( R). It is worth noting that in instance I,each agent group Timay no longer be a t-cohesive group, because their set of commonly approved goods is now RTi,whose size is only k=t.Nevertheless, our goal is to find an allocation Rfor instance Isuch that for every i∈{1,...,p},the average satisfaction of Tiwith respect to Rin instance Iis at least t−1+z(1−z) t,even if Tiis not a t-cohesive group in instance I.As a result, as we argued above, there exists a corresponding allocation Rfor instance Ithat has the same or better average satisfaction for all t-cohesive groups in instance I. 123
674 X. Lu et al. We apply the classic PAV rule to find the allocation Rfor instance I(which is an indivisible-goods instance). That is, we choose Rthat maximizes H( R)= i∈NHui( R),where Hx:=1+1 2+ ··· + 1 xis the x-th harmonic number. The following analysis is similar to that of Theorem 3.18, but more refined. By adding an indivisible good approved by no agent to the resource Ras well as Rif necessary, we may assume without loss of generality that s( R)=α. To show that Rsatisfies the target average satisfaction value for each Ti∈T,we assume for contradiction that there exists T∗∈Tsuch that 1 |T∗|· i∈T∗ ui( R)<t−1+z(1−z) t =t−z−1+z(t−z+1) t=k−1+(k+1)z t.(6) Since (k+1)z t<k+z t=1,we have k−1≤k−1+(k+1)z t<k,(7) which means that there exists a good g∗∈ RT∗that is not selected in R.Let R := R∪{g∗}; so | R|=α+1.We have H( R)−H( R)≥ i∈T∗Hui( R)+1−Hui( R)= i∈T∗ 1 ui( R)+1. In what follows, we provide a lower bound on i∈T∗ 1 ui( R)+1.First, for each i∈T∗, let yi=ui( R). We thus have i∈T∗ 1 ui( R)+1=i∈T∗ 1 yi+1.If there exists a pair i,j∈T∗with yi≥yj+2,let y i=yi−1 and y j=yj+1.It is easy to verify that 1 yi+1+1 yj+1>1 y i+1+1 y j+1. By replacing yi(resp., yj) with y i(resp., y j), we decrease b∈T∗ 1 yb+1.Repeat this process until, for every pair i,j∈T∗,it holds that |yi−yj|≤1.We now have i∈T∗ 1 ui( R)+1≥ i∈T∗ 1 yi+1. Note that all yi’s are integers and the following equation still holds: i∈T∗ ui( R)= i∈T∗ yi.(8) 123
Approval-based voting with mixed goods 675 Together with (6) and (7), we have that yi≤k−1forsomei∈T∗,and therefore yi≤kfor all i∈T∗. If i∈T∗yi≤|T∗|·(k−1), then i∈T∗ 1 yi+1≥|T∗|2 i∈T∗(yi+1) =|T∗|2 i∈T∗yi+|T∗|≥|T∗|2 |T∗|·(k−1)+|T∗|≥|T∗| t≥n α, where the first transition follows from the inequality of arithmetic and harmonic means and the second-to-last transition from the fact that t≥k. Else, i∈T∗yi>|T∗|·(k−1). This means that there exists i∈T∗such that yi=k. Let ' T∗:={i∈T∗|yi=k}; we have |' T∗|>0.As argued earlier, for all i∈T∗\' T∗, it holds that yi=k−1.Recall from (6) and (8) that |' T∗|·k+(|T∗|−| ' T∗|)·(k−1)= i∈' T∗ k+ i∈T∗\' T∗ (k−1) = i∈T∗ yi = i∈T∗ ui( R)<|T∗|·k−1+(k+1)z t, which implies that |' T∗|<|T∗|·(k+1)z t.As a result, we have i∈T∗ 1 yi+1= i∈' T∗ 1 k+1+ i∈T∗\' T∗ 1 k=|' T∗| k+1+|T∗|−| ' T∗| k=(k+1)·|T∗|−| ' T∗| k(k+1) >(k+1)·|T∗|−|T∗|·(k+1)z t k(k+1) =|T∗|·1−z t k=|T∗| t≥n α. Therefore, in either case, adding g∗increases the PAV-score of Rby at least n/α. Finally, the rest of the proof proceeds in the same way as that of Theorem 3.18 when arguing about the marginal contribution of an indivisible good in R (which corresponds to R in our proof here). For each good g∈ R,denote by Ng⊆Nthe set of agents who approve it. For each g∈ R,we have H( R)−H( R\{g})= i∈NgHui( R)−Hui( R)−1= i∈Ng 1 ui( R). 123
676 X. Lu et al. Letting N+consist of the agents i∈Nwith ui( R)>0,we get g∈ R (H( R)−H( R\{g})) = g∈ R i∈Ng 1 ui( R)= i∈N+ g∈ R∩ Ri 1 ui( R)=|N+|≤n. If there is a good g∈ R such that H( R)−H( R\{g})<n/α (clearly, g= g∗), we can replace gwith g∗in Rand obtain a higher PAV-score, contradicting the definition of R.Hence, we may assume that H( R)−H( R\{g})≥n/α for every g∈ R.It follows that n≥ g∈ R (H( R)−H( R\{g})) ≥| R|· n α. Therefore, we have that | R|≤α, contradicting the fact that | R|=α+1.This completes the proof. The proof of Theorem B.2, however, does not show that there exists an allocation with the claimed average satisfaction guarantee for all t simultaneously, as the creation of the new instance Idepends on t.While it is conceivable that Generalized PAV achieves this simultaneous guarantee, proving (or disproving) this seems to be a challenging task. Acknowledgements This work was supported by ARC Laureate Project FL200100204 on “Trustworthy AI”, by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, 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 would like to thank the anonymous reviewers for their valuable comments. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Abramowitz M, Stegun IA (eds) (1972) Handbook of mathematical functions with formulas, graphs, and mathematical tables, 10th edn. National Bureau of Standards, Washington D.C. Aziz H, Brill M, Conitzer V, Elkind E, Freeman R, Walsh T (2017) Justified representation in approval-based committee voting. Soc Choice Welf 48(2):461–485 Aziz H, Elkind E, Huang S, Lackner M, Sánchez-Fernández L, Skowron P (2018) On the complexity of extended and proportional justified representation. In: Proceedings of the 32nd AAAI conference on artificial intelligence (AAAI), pp 902–909 123
Approval-based voting with mixed goods 677 Aziz H, Bogomolnaia A, Moulin H (2020) Fair mixing: the case of dichotomous preferences. ACM Trans Econ Comput 8(4):18:1-18:27 Bei X, Li Z, Liu J, Liu S, Lu X (2021a) Fair division of mixed divisible and indivisible goods. Artif Intell 293:103436 Bei X, Liu S, Lu X, Wang H (2021b) Maximin fairness with mixed divisible and indivisible goods. Auton Agents Multi-Agent Syst 35(2):34:1–34:21 Bei X, Lu X, Suksompong W (2024) Truthful cake sharing. Soc Choice Welf (forthcoming) Bhaskar U, Sricharan AR, 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), pp 1:1–1:23 Bredereck R, Faliszewski P, Kaczmarczyk A, Niedermeier R (2019) An experimental view on committees providing justified representation. In: Proceedings of the 28th international joint conference on artificial intelligence (IJCAI), pp 109–115 Elkind E, Faliszewski P, Igarashi A, Manurangsi P, Schmidt-Kraepelin U, Suksompong W (2022) The price of justified representation. In: Proceedings of the 36th AAAI conference on artificial intelligence (AAAI), pp 4983–4990 Faliszewski P, Skowron P, Slinko A, Talmon N (2017) Multiwinner voting: a new challenge for social choice theory. In: Endriss U (ed) Trends in computational social choice, chapter 2. AI Access, pp 27–47 Kawase Y, Nishimura K, Sumita H (2023) Fair allocation with binary valuations for mixed divisible and indivisible goods. arXiv preprint. arXiv:2306.05986 Kilgour DM (2010) Approval balloting for multi-winner elections. In: Laslier J-F, Sanver MR (eds) Handbook on approval voting. Springer, Berlin, pp 105–124 Lackner M, Skowron P (2023) Multi-winner voting with approval preferences. Springer, Berlin Nishimura K, Sumita H (2023) Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods. arXiv preprint. arXiv:2302.13342 Peters D, Skowron P (2020) Proportionality and the limits of welfarism. In: Proceedings of the 21st ACM conference on economics and computation (EC), pp 793–794. Extended version available at arXiv:1911.11747v2 Peters D, Pierczy´nski G, Skowron P (2021) Proportional participatory budgeting with additive utilities. In: Proceedings of the 35th conference on neural information processing systems (NeurIPS), pp 12726– 12737 Procaccia AD (2016) Cake cutting algorithms. In: Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (eds) Handbook of computational social choice, chapter 13. Cambridge University Press, Cambridge, pp 311–329 Robertson J, Webb W (1998) Cake-cutting algorithms: be fair if you can. Peters/CRC Press, Natick Sánchez-Fernández L, Elkind E, Lackner M, Fernández N, Fisteus JA, Basanta-Val P, Skowron P (2017) Proportional justified representation. In: Proceedings of the 31st AAAI conference on artificial intelligence (AAAI), pp 670–676 Skowron P (2021) Proportionality degree of multiwinner rules. In: Proceedings of the 22nd ACM conference on economics and computation (EC), pp 820–840 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123