Maintaining Proportional Committees with Dynamic Candidate Sets
Authors: Chris Dong
Jannik Peters
Venue: ICML 2025 poster (2025)
Keywords: computational social choice
multiwinner voting
algorithmic game theory
online algorithms
clustering
committee selection
proportionality
Primary area: theory->game_theory
TL;DR: We study whether proportional committees can be maintained when candidates can join or leave the instance.

Abstract: Multiwinner voting is the study of electing a fixed-size committee given individual agents' preferences over candidates. Most research in this field has been limited to a static setting, with only one election over a fixed set of candidates. However, this approach overlooks the dynamic nature of applications, where candidate sets are subject to change.
We extend the study of proportionality in multiwinner voting to dynamic settings, allowing candidates to join or leave the election and demanding that each chosen committee satisfies proportionality without differing too much from the previously selected committee. We consider approval preferences, ranked preferences, and the proportional clustering setting. In these settings, we either give algorithms making few changes or show that such algorithms cannot exist for various proportionality axioms. In particular, we show that such algorithms cannot exist for ranked preferences and provide amortized and exact algorithms for several proportionality notions in the other two settings.

Maintaining Proportional Committees with Dynamic Candidate Sets
Chris Dong' Jannik Peters? 2
Abstract
of multiwinner voting: voters submit preferences over a subset of candidates, from which & need to be selected. For instance, in the classical centroid clustering problem, the voters correspond to the points to be clustered, the candi- dates are the possible cluster centers, is the number of cluster centers to be selected, and the preferences are de- rived from the distances between the points and the cluster centers.
Multiwinner voting is the study of electing fixed- size committee given individual agents' prefer- ences over candidates. Most research in this field has been limited to a static setting, with only one election over a fixed set of candidates. However, this approach overlooks the dynamic nature of applications, where candidate sets are subject change. We extend the study of proportionality in multiwinner voting to dynamic settings, allow- ing candidates to join or leave the election and demanding that each chosen committee satisfies proportionality without differing too much from the previously selected committee. We consider approval preferences, ranked preferences, and the proportional clustering setting. In these settings, we either provide algorithms making few changes or show that such algorithms cannot exist for var- ious proportionality axioms. In particular, we show that such algorithms cannot exist for ranked preferences and provide amortized and exact al- gorithms for several proportionality notions in the other two settings.
In the vast majority of settings studied so far, multiwinner voting is "one-shot": voters and candidates are given, and the task is to make one selection only. However, assuming such a static setting might be too restrictive for real-world applications (a concern raised, for instance, by Boehmer and Niedermeier, 2021; Elkind al., 2024). In election settings, candidates might concede their seat and then need to be replaced (Gallagher, 1996); in hiring settings, candidates could apply for the job or decline offers at any time during a hiring procedure (Brill et al., 2023); and in facility location problems, new possible locations might open up.
As a possible application, consider the setting of civic partic- ipation platforms (Halpern al., 2023; Fish al., 2024). A website (such as https: / /pol. iss, studied by Halpern et al.) wants to curate slate of representative new ments on its homepage. In this setting, the comments corre- spond to candidates, and the voters correspond to the users of the website. The voters express which comments they like, for instance, by up- or down-voting them. Such a set- ting, however, is inherently "online", as new comments get posted, and old comments get removed when they become out-of-date. Our work studies if it is possible to maintain slate of representative comments, while only making a small amount of changes with each update.
1. Dynamic Committee Selection
Given diverse preferences of agents, a central subject of re- search in artificial intelligence, collective meakin, and social choice theory is the task of choosing subset of possible candidate items that proportionally represents the agents' preferences. Applications include clustering (Caragiannis et al., 2024; Kellerhals and Peters, 2024), fa- cility location (Jung et al., 2020), query answering, and top-k selection protocols (Behar and Cohen, 2022; Islam al.. 2024), or democratic innovations like participatory budgeting (Peters et al., 2021) or civic participation plat- forms (Fish et al., 2024). Most of the previously mentioned papers derive their models from the basic social choice task
We follow in the footsteps of recent work in the match- ing (Matuschke et al., 2019; Bernstein et al., 2019), and clustering (Bhattacharya et al., 2024: Lącki et al., 2024) lit- erature and study dynamic multiwinner voting. In particular, we study low recourse dynamic proportional multiwinner voting and answer the following question: can we select proportional committees such that after the candidate set changes, we can restore proportionality by altering the orig- inal committee slightly?
Equual contribution 'TU Munich National University of Sin- gapore. Correspondence to: Chris Dong <chris.dong tum.de>, Jannik Peters cesters@nu..cdu..s.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In a recent paper Chen, Hatschka, and Simola (2024) exam- ined a highly related problem: given two different commit-

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
tees, can we transform one of the committees into the other by swapping candidates in and out of the committee. How- ever, their study focuses only on committess elected by spe- cific scoring rules in an approval-based setting, and provides results exclusively limited to computational intractability and fixed parameter tractability. Crucially, while some scor- ing rules always select proportional committees, Chen et al. (2024) only require that the in-between committees have bounded score differences. However, simply bounding the differences in scores does not guarantee that the committees selected in-between are actually proportional. In contrast, our work focuses on guaranteeing proportionality itself.
is related to Do et al. (2022). In their approval- setting, candidates appear in an online manner and have be irre- vocably chosen or rejected at each time-step. The difference is that in our model (i) the committee needs to satisfy the proportionality notion at every step of the online process and (ii) chosen candidates can be taken off the committee or even off the feasible set again. Further, Brill et al. (2023) consider model in which they assume that the set of can- didates is known in advance, but the actual availability of the candidates is unclear and needs to be requested via an invitation to the committee. Similarly to Do et al. (2022), candidates are added irrevocably. Further, the preferences over all candidates are known in advance. In a series of works Deltl et al. (2023): Bredereck et al. (2022; 2020) con- sidered the complexity of the sequential committee selection problem. In their model, the rules select one committee per time-step, while constantly satisfying requirements such as optimizing egalitarian welfare or scores, subject to the com- mittees not changing drastically over time. Most problems studied in these works are computationally intractable and thus the authors instead study the parameterized complexity of several related problems.
Our Results We study the dynamic preservation of pro- portionality in three common settings, where preferences are modeled via linear orders, approval ballots, and distances in metric space. We further distinguish between the three classical dynamic frameworks where the candidate set can iteratively grow, decrease, or both. For linear orders, we show that the popular axiom of proportionality for solid coalitions (PSC) (Dummett, 1984) can be maintained in the incremental framework, but not in the decremental or fully- dully-dynamic framework, where the number of required replacements after a single deletion may be arbitrarily large. For approval ballots, we provide fully-dynamic algorithms that satisfy the notions of PJR+ and (llog(k)) and Peters, 2023) while requiring, on average, two changes per sime Additionally, we show that in the incremental setting a-EJR+ can be satisfied for constant a > 1 with the average number of swaps per time-step being constant and independent of k. For proportional clustering, we obtain a fully- dally-dynamic algorithm that achieves a p.o-proopll fair outcome and a 5 approximation to the q-core (Kellerhals and Peters, 2024; Ebadian and Micha, 2025). Surprisingly, this meets the currently best known upper bound on the q- core of non-dynamic algorithms. Hence, we achieve results that are more positive than one might anticipate based on Chen et al. (2024), especially in proportional clustering and for the incremental setting.
2. Model and Notation
In this section, we first introduce general static framework, then expand it to be dynamic. Setting-specific definitions are in the corresponding sections.
(Brill
Static Framework Throughout the paper, we denote by N = [n] the set of voters and by C = {c: i E N} the set of candidates. A preference profile P contains the voters' preferences over the candidates in C. Further, when given some C C C*, we denote the restriction of tto C by Plc- The exact form of P and Plc depends on the setting and we provide according definitions in each corresponding section. Roughly speaking.
(i) with ordinal preferences, each voter i E N has a linear order over C":
Further Related Work Proportionality in the static mul- tiwinner voting setting is well studied. In detail, we refer to Lackner and Skowron (2023) for recent book on approval- based multiwinner voting and to the works of Aziz and Lee (2020; 2021; 2022), Brill and Peters (2023), and Bardal et al. (2025) for proportionality with ranked preferences. Further, we refer to Chen al. (2019) for the introduction of propor- tional faimess in clustering; to (Micha and Shah, 2020; Li et al., 2021; Kalayci et al., 2024) for follow-up work; and to (Aziz et al., 2024; Kellerhals and Peters, 2024) for relating it to multiwinner voting and the problem of individual fair clustering (Jung et al., 2020; Mahabadi and Vakilian, 2020).
(ii) with proportional clustering, preferences are given via distances in a pseudometric space (N U C*, .d); and
(iii) with approval preferences, each voter i e N has an approval set A, C
Given a target size a profile P. and a finite set C' C C* of size least the goal is to select a committee W C C of size k. For each k E N, C C C* with |C| k, and preference profile P. the tuple I = (C, Plc, constitutes an (approval/ordinal/llsset rule f takes instances I as input and outputs a committee f(C, k) C C of size k. Throughout the paper we write that a group N' C N of voters is lllarge, if N'| 2 k.
instance. A static voting
As for other online models of multiwinner voting, our work
2

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
Intuitively, for an outcome be proportional, every &-large group of voters should be represented with & ccandidates in the outcome.
the dynamic problems add layer of depth that has yet to be accounted for. Their definitions and all missing proofs and examples are in the appendix.
Online Algorithms We introduce three settings for dy- namic algorithms. In each of these, a sequence of instances with varying candidate sets is given, and the algorithm is only allowed to use information up the current time-step.
3. Ordinal Preferences
In this section, we first introduce ordinal preferences. Then, we show that the axiom of proportionality for solid coali- tions can be satisfied robustly in the incremental setting, but not in the decremental setting. We further give asymptotic lower bounds for the number of replacements that are re- quired to restore proportionality after a single deletion, and present negative results for a notion called "rank justified representation".
First, in the incremental setting, we are given set Co of m 2 ht candidates together with stream of candidates e1, .2,..., appearing over time. Accordingly, the voters' preferences are revealed incrementally. For this purpose, let t E N denote time-step and C.- = CoU fei,...,ce) be the set of available candidates at this time-step. Formally, an incremental algorithm f takes as input (Ct; Plc, k () and outputs a committee f(C,, Plc,, t) C C2 of target size k.
An ordinal preference profile p = (>))iEN is a collection of complete, strict orders >; over C*. We hence write > instead of P in this section. We define Plc lc as the restriction of each >; to C. Given a profile > and a set C C C*, we say that set of voters N' S N is a solid coalition over a set S S C of candidates if for any E N' it holds that S >; C' \ S, i.e., S forms a prefix of that voter's preferences. A committee W satisfies Proportionality for Solid Coalitions (PSC) (Dummett, 1984) if for every Ê-large group of voters N' that is solid coalition over some S S C, it holds that IW S| 2 min([S), f). If W violates PSC due to an E-large solid coalition N' over S with IW nnn < min(e, (S)), we say that (N', S, (or N') is a witness for the violation. PSC is a thoroughly studied axiom and, e.g., is satisfied by the popular and widely used single transferable vote (STV). The eminent social choice theorist Tideman argued for PSC as the reason for STV being proportional: "It is the fact that STV satisfies PSC that justifies describing STV as system of proportional representation." " (Tideman, 1995, page 28)
Next, in the decremental setting, we start with some set of candidates Co = fct,....,mll m 2 k and the vot- ers reveal their preferences over Cu immediately. How- ever, the order in which candidates drop out of the elec- tion is not known to f in advance. Formally, any sequence (C+)t=o.....mbb k. with [C,] = m mn and C2 C C--1 is admis- sible and a decremental algorithm f takes as input instances of the form ((Cs)ast. Plc., k. () and outputs a committee (lc,, k. t) S C2 of target size k:
In the fully-dynamic setting, the candidates can both join and leave. As in the decremental setting, we start with Co = fci...,,Coo .. for some m 2 k. However, the only requirement on the sequence (Cz)t2a. apart from |Cyl 2 k; is that C++1 is obtained from C. by adding or removing one candidate for all E N. A fully-dynamic algorithm takes as input ((C.)agt, Plu,ee Ca k,t) t) and outputs a committee (((C.)ss) Plu.s. C,, kt 1) C, of target size k.
As an illustration of PSC consider the following example with n voters and k- 3:
Let a hitlyyyyyaaniidddeeeeeen//nneeee
algorithm ff be given. Once a sequence (C+); is fixed, the complete input of f can be derived from the tuple (P, k, t), and for brevity we hence write f(P, k, t) in all three frameworks. Note that, despite this shorthand notation, can only use information that is available up to time-step and has finite input. Often, even P and & will be clear from the context, in which case we abbreviate ft).
C1 1 02
C4 > c5 6
C3
>
C3 >
9 8
>
05 >2 C4 3
C4
6
c3 > C2
C3 -
02
C5.
Here, the committee W = (c2, ct} satisfies PSC. How- ever, W' = {cz, C4, { violates PSC due to the witness [11,2,4, (21,02, c22 o,),,,)))))) as W' n (c1. call < 2.
Let X be any proportionality axiom. An algorithm f satis- fies X if [(P, k, 1) satisfies X for all k, I, and P. A (fully dyamiclecremental/nceeeeee for all (fully dyamic/derremenaal/cceeeeee
As our first main result, we give a polynomial time incremen- tal rule satisfying PSC. Our proof entails an even stronger statement: for each committee W satisfying PSC and each newly added candidate e that causes a violation, there is always a single candidate c' E W who can be swapped with e to restore PSC Therefore, it is possible to, for instance, initialize the committee by running STV and then fix PSC violations whenever they appear.
algorithm f is robust, if instances we have (S k. !) n S(P, k. ( + 1)1 > k- - Finally, we say that an algorithm makes amortized E changes if after rounds ok - [f k, (') [(P, k, + 1)1) < t.
Throughout the paper, we will reference well- well-known rules from the static multiwinner voting setting to illustrate that
3

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
Theorem 3.1. There exists a robust incremental algorithm satisfying PSC.
not satisfy PSC. Fix any c W. Then, there exist witnesses e) of W-c violating PSC and we can exhaustively list all of them. Consider only the witnesses for W-c with maximal candidate set size [S], and among these choose a witness that maximizes the size of the solid coalition [ For each c E W, we denote this "maximal" witness via (No, Se, fo). We will now arrive at a contradiction by iteratively assigning a } t-ffaction of the voters to each in W. For this, enumerate W {di,...., dx+1), ) For d1, we can assign it to any & E-fraction of the voters that is contained in Na, which must exist since Na, must be at least 1-large to be a witness. For j 2 2, let injective voter assignments be made for all candidates with smaller index, i.e., de with S x < j. To prove that there is still at least &-fraction of the voters from Na, unassigned, we use the following claim to count the number of de with assignments in Na,,
Proof. Fix an ordinal profile > and target size k. Let C,- Co U (cI,...,(.) (t) denote the set of candidates that joined until time-step t. We will denote by f(t) the committee selected at this time. For t = O, let f(t be any committee satisfying PSC.
For > O, let f(t - 1) satisfy PSC with regard to C--1- We will show that f(t - 1) still satisfies PSC at step or that by adding < to J(L - 1) and removing another candidate, PSC can be restored. To this end, we consider the set W = f(tt - 1) J { and the resulting committees W-c = W {c} for e E W. Rephrased, our goal is to show that W-c still satisfies PSC at time ć for some e E W. Note that c here can also be the newly added candidate cs.
Claim 3: For all x < j with Nd. n Na, A 0. we have Na, -Na, and Sa, = Sa,-
To reach this goal, we conduct counting argument: for each W with W_ violating PSC, "reserve" unique i. -frrccioo of the voters. As there are k + candidates in W. there hence exists at least one candidate for which we could not have reserved such a + --fraction and thus no PSC violation occurs when we remove this candidate from W.
Let i E Na, n Na, be given. Since Sa. and Sd, are both prefixes of the relation > one must be a subset of the other. Without loss of generality, assume Sd, S Sdy. We first show that the voter set Na, is not only a witness for a PSC violation of W-d,- but also for violation of W-d-. Applying Claim 1, we obtain dz E Sa. S SSd, and d3 E Sa, Combining this fact with (Na,. Sa,, la,) being a witness yields
To show this, we need the two following claims about poten- tial PSC witnesses. Let c W be such that W-o violates PSC at time & due some witness (Ne, E).
Claim 1: e E S. i.e., all voters in No rank e above C. \ S.
min(ISa,l,ea)) > [Sa, O NW nWaa,l -Sa, n -W-l---
To prove the claim, we consider a case distinction:
Hence. (Nay, Say: ka,) is also a witness for the PSC vio- lation of W-d.. Since we chose St, to be maximal, it must be that Sd, = Sd, and the prefixes coincide. Thus, (Na, U No,, Sa, la.) also witness for the PSC viola- tion of -- Since we chose Na. to be inclusion maximal among witnesses, it must be that Na, NN,, U UN,, imply- ing Na. 2 NN,, Applying the same argument to W W-d,, we obtain Na, 2 Na, which concludes the proof of Claim 3.
Case is that c & S. which implics that the voter set No is a solid coalition for the candidate set S S Ct-1 in time-step t 1. Further, of course, No is &-large independent of the time-step. Since [(t 1) satisfies PSC at time / 1, we have ()(t1))n S| > min( e). By choice of the witness S. we have W-c n Si < miin(S)),2 This implies [W-nns < [s(L- (), which is only possible if e E S, showing our claim in this case.
Each de with < j that is assigned some voters in Na satisfies No. N.Na, * 0. By Claim I and 3, it follows that d, E Sa, 0 W. However, by Claim 2, IW n Sa, S lay- Since dj itself is contained in W n Sa,, at most La, - different de with x < j can have been assigned to some voters in Na,- Since each of these dy is assigned to & voters and N&,, 2 Ea, F. there still at least a j -fraccioon of the voters unassigned, which we can assign dj. This proves that we can assign each c E W to some & fraction of N. Since W contains k++1 candidates, this implies that there are k+1 .n > n voters in total, the desired contradiction. Hence, there exists a e E W such that W., satisfies PSC.
Case 2 is that e E S, which implies that the voter set No is solid coalition for the candidate set S {(e) C C-11 in time-step --1 1 (and still is É-large). Since f(t 1) satisfies PSC at time i - 1, we have |W nnnsss1 1 [s(t- ( \ {c)))] 2 min([S] - 1, f). where the equal sign follows from & E W n S and e & f(t - 1). This implies [Wns] 2 min([S] 1, +1 2 min((S), > [S] which is only possible if E
Claim 2: |Wns|
By choice of the witness (Ne, S, f), we have [W < min( (S) e) < f. This directly implies W S| < [W-n S|+1 < L, proving Claim 2.
The approach of Theorem 3.1 does not work for deleting a candidate- if we choose poorly, we may need to replace the entire committee after a single deletion.
Now we are ready for the main argument. Assume for contradiction that for all e E W, the committee W_, does
4

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
A size & committee satisfying PSC may require l additions to restore PSC after a single deletion. For this, consider the following profile with n = k.
Example 1.
Proportional faimess, however, only looks at deviations to single candidates. This prompted several strengthenings (Ebadian and Micha, 2025; Kalayci et al., 2024; Aziz et al., 2024) dealing with deviations to multiple candidates instead. As it is closest in spirit to proportional fairness, we focus here on the q-core as introduced by Ebadian and Micha (2025). Given an instance over some candidate set C' C C", a committee W is said to be in the a-q-core for some q E [A] and 2 if for all other candidate subsets C' C C the following holds: there are strictly less than IC'I n voters &
a 1 b 11 02 1 >1 ag >11
a >2 b2 2 2 >2 as >2
01 x bk > 02 > b ak > *
The committee W {ai,..., } satisfies PSC. However, after removing 01, all candidates b; would need to be added.
N for which their q-th closest candidate in W is times farther away than their q-th closest candidate in C". For y 1 this is equivalent to proportional faimess.
Similarly, commonly used rules that satisfy PSC fail to distinguish between robust and non-robust committees. We provide an example in the appendix.
Unlike for the ordinal and approval settings, in the clustering setting proportionality can only be approximated, not per- fectly satisfied. Several existing algorithms, such as Greedy Capture (Chen al., 2019) or the Spatial Expanding Ap- provals Rule (Aziz et al., 2024), achieve constant factor approximation to proportional faireess the core. How- ever, these algorithms rely on generalization of rank-JR of which we have shown that it does not admit a robust algorithm- - to proportional clustering (Kellerhals and Pe- ters, 2024). We circumvent this and design a fully-dynamic algorithm achieving a constant factor approximation to pro- portional fairness. In essence, proportional clustering is easier than proportional multiwinner voting, as voters share metric space with the candidates. By clustering similar voters into groups, we preempl the clustering of candidates. Using this, we obtain a fully-dynamic algorithm that is 4.24- proportionally fair and in the 5-q-core. Surprisingly enough, the 5-q-core bound is equal to the current best bound in the offline setting (Kellerhals and Peters, 2024).
Observation 1. The single transferable vote (STV) and the expanding approvals rule (EAR) of Aziz and Lee (2020) can select committees that are not robust to single deletion for PSC, even when such committees exist.
While in Observation 1 robust committee exists, there are instances where any algorithm satisfying PSC is not robust and requires at least ((log(lo((k)) changes to restore PSC. This precludes the existence of a robust decremental- let alone dolly-dynamic PSC algorithm.
Proposition 3.2. There does not exist a robust decremenial PSC algorithm. After single deletion, any algorithm may require ((og(log(k))) replacements to restore PSC.
Finally, in the appendix, we also show that for the "rank- based" axioms recently introduced by Brill and Peters (2023) an even stronger lower bound of 92( (VVK) holds and that this lower bound also extends to incremental setting.
Theorem 3.3. There is no incremental or decremental al- gorithm satisfying the rank-JR axiom of Brill and Peters (2023) and making of o(yk) changes amortized per round.
Theorem 4.1. There exists a robust fobustfully fully-dynamic algorithm achieving a 2 + v5 ~ 4.24-proportional fair outcome and satisfying the 5-q-core for any q E [Mc]
4. Proportional Clustering
Proof. We begin with a pre-clustering phase similar to the spatial expanding approvals rule (Aziz al., 2024). We assign each voter E N budget b, = _ and initialize counter = 1. Then we continuously increase real parameter 5 from 0 on. Whenever there is set of voters N' C N of diameter at most ö such that N' has a total budget of at least 1, we create a cluster N₂ = N' for these voters, decrease their budgets by a total of 1, and increase the counter x by 1. multiple clusters could be created for the same but compete with each other for the budget, we break ties arbitrarily. This leads to clusters NN...., No (with clusters potentially overlapping). To focus on the vot- ers that positively contributed to the clusters, we denote by px(x) Z 0 the contribution of voter i to the cluster N,
Secondly, we turn to proportional clustering. Here, candi- dates and voters are situated in space (N U C*, d) with d being a pseudometric. Hence, the distance function d: N U C* x NUC - I2 satisfies symmetry: d(x, y) = d(y,a)) and the triangle inequality: d(x,, y) < d(x, z) + x)) for all voters and candidates z. y, 2 E NNUC. For finite C C C* we denote by dlc the natural restriction of d to the finite subdomain NUC x NUC. In proportional clus- tering, the most prominent proportionality notion is that of proportional fairness (Chen et al., 2019). An outcome (or clustering committee) W is said to be 7-proportionally fair for some 7 2 1 and some instance (C, dic, k), if there is no unselected candidate e E C W and l-large group N' C N of voters such that
n.
'This algorithm for "pre-clustering" the voters can additionally be seen a generalization of the recently proposed algorithm for finding a proportional non-centroid clustering by Caragiannis et al.
min d(i,e') c') > 7 yd(i,) c) for all i E N'. e'ew
5

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
For a given cluster of voters N₂ and any candidate we let c( min(d(i, c): E N and pc(x:) > 0}. To initialize a committee, we consider the clusters ,,....,N. Nu in order. For each cluster N₂ we pick among the so far unchosen candidates some Cz minimizing d(Na.Ga) To dynamically determine whether we need to modify the com- mittee at each time step, we say that a cluster N₂ envies another cluster N₂ if d(Na. Cy) < d(N,,, 2 By our enu- meration, it is clear that for the initial assignment and all r, S cluster N₂ can only envy N₂ if x < y. Further, the selected committee contains the distance minimizers for all clusters N1....Ny Ng. We will in each step ensure that this invariant remains true.
we know that at least one of the agents in N' pays for a preprocessed cluster N of diameter at most 6. Let i be this agent and let j be the agent furthest away from c in N" (note that this might be i again). Since N" did not pick e, c is not a (unique) minimizer of d(N" ..). We know that there must be an agent h E N" with d(h, W) S d(N"". .) S d(i, c). Further, by the triangle inequality we can bound the distance between any two elements of N' by their respective distances to c, so it must hold that 8 I 2d c). Thus, we get that
d(i,W) d(i,W)
S min
d(i,c) d(j,c)
d(i,h) + -dh,, W) d(j,0) + d(i,W)
When we delete a candidate e we either do (i) nothing if c not picked by any cluster or (ii) if is picked by cluster N₂ we let N₂ repick the closest current unchosen candi- date d. Since every cluster Ny with y * x prefers their current candidate to d, we re-enumerate them with N₂ is renamed to N₂ and the former Na+1,..., Nu renamed to . Still, for æ, y S n, N₂ can only envy N₂ if x < y.
S min
c(i,c)
d(j,c)
8 8 c(i,c) d(i,c) + d(j.c) + d(i, W)
S min
d(i.c)
d(j,c)
2d(j, c) + d(t,c) 3d(j. c) + 2d(i, c)
< min
d(i,c)
d(j,c)
2x + 1,3 + 2 x
S min =20
= 2 V3.
If candidate gets added, we first check if there is any cluster N₂ for which c)) < d(Na,, Ca), i.e., c is closer than the picked candidate for this cluster. If there is not, we do not add c. If there is, however, such a cluster Nz, we assign e to such a cluster N₂- with the smallest index x² and store Cz. as the interim candidate. As long as the set of N, with y > i* are assigned their current choices or ca-, N2- only envies clusters with y' < i. Now, in ascending order, every N₂ with y > gets to choose between keeping their current candidate Cy or exchanging it for the current interim candidate, thus making cy the new interim candidate. If Ny keeps cy. then it will not envy any N₂ with = > y after the process since they will be assigned to some d2g or the interim candidate that N, prefers less to cy. If N₂ swaps by for the interim candidate, then still will not envy any N> after the process because each will obtain some Czy After N& made their choice, we discard the current interim candidate and obtain a new committee containing e with just one swap on the currently selected set, but up to k re- re-assignments of clusters to selected candidates. Still, this time without re-enumeration, for x, y S n, Ny can only envy N₂ if a < y.
and therefore the improvement through is bounded by 2 v5.
For the a-q-core, let N' S N be an f-large deviating coali- tion and C" C of size |C'| = f be the set of candidates the coalition deviates to. For a given agent i E N we de- fine di, C*) to be the distance of the agent to their g-th closest member of C². Following Kellerhals and Peters (2024, Lemma 9) there is candidate E C' and subset N" C N such that is in the top-q choices among C' of everyone in N" with N" being of size at least g Let E N be the agent among N with the largest di C"). Since the agents in N" have a total budget of & there must at least exist q clusters bought partially by agents from N Similar to the first part of this proof, the diameter of at least q of these clusters is smaller than the diameter of N We know that these clusters must have chosen q of the cluster centers in W. Since the diameter of N is at most d(i,, 12) < d(ir, c) + d(c, i2) I di,,,, C²) + (iz, C') < (d, C") the diameter of each of these clusters is also at most Ci. Since each agent in N" is also at most (i, C") away from an unselected cluster center, the cluster center selected must also be at most di, C) away from someone in the group and thus at most (i, C') away from the member of N However, since the diameter of N" is at most 2d C") this implies that agent i is at most a distance of (i C") away from q cluster centers in W, therefore showing that W is in the 5-q-core.
Now we are ready to show that this procedure is always p-proportional fair. Let W be any committee throughout the online process, be any unselected candidate, and N' be group of voters deviating to e of size at least x Let 5 be the diameter of N'. Then, in the first step of the procedure,
(2024) to also handle groups larger sizes than X- We now perform procedure similar to the envy-cycle elimi- nation from fair division, see, e.g., the survey of Amanatidis et al. (2023).
While the initial pre-clustering is not tractable, it is possible to adapt this step to obtain a polynomial time constant factor approximation with slightly larger constant.
6

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
5. Approval Preferences
C3 EiExPi(e) = 1 for all W
In this section, we assume that we are given an appreval profile A = (A.).e. and we call A, S C* the approval ballots. We define Alc (A, n C)NEN. Throughout this section, refer to subsets W S C of size [W] < k as subcommittees. For approval preferences, we call set NN " N of voters f-cohesive if ( NEN A, 2 L. Since the original paper of Aziz et al. (2017) defining the axiom of justified representation, a plethora of works have focused on defining new possible axioms or extending the original ones of Aziz et al. (see for instance the recent book of Lackner and Skowron, 2023). We focus here two natural variants introduced by Brill and Peters (2023). We say that a committee W satisfies
C4 EiEn Pc(c) = for all c & W
C5 EiEN: (# Edec < for all e & W.
Maximally affordable subcommittees always exist, as e.g. the non-exhaustive output of the MES rule is maximally affordable. Further, is easy to see that any committee W that contains a maximally affordable subcommittee W S W" satisfies PJR+ (Brill and Peters, 2023, Proposition 10).
Corollary 5.1. Every completion of a maximally affordable subcommittee satisfies PJR+.
Our goal is maintain supersets of maximally affordable subcommittees dynamically. First, we use this approach to provide robust incremental PJR+ algorithm, which, in essence, works the same way as the algorithm of Do et al. (2022), who show that PJR+ is satisfiable in their online committee selection setting.
proportional justified representation+ (PJR+) if for every l E [k] and 1-cohesive and é-large group N' it holds that NiEN. A; S.W W or (UEN A; n W| 2 L.
extended justiffied representation+ (EJR+) if for every e E [k] and 1-cohesive and f-large group N' it holds that DiEN. A, S W or [4,W]] 2 & for some E N'.
Theorem 5.2. There exists a robust incremental PJR+ al- gorithm.
The proof also shows that once a maximally affordable committee of size & has been instantiated, no further modifi- cations are required maintain PJR+ in all time steps.
Further, a-EJR+ with a > 1 requires that for every E E [k] and 1-cohesive and a E-large group N' there exists an E N' with |A, n W| 2 é or it holds that CIEN' A, S W. Example 2. First, we give an example of committee sat- isfying EJR+, for which removing any candidate from the committee, forces at least two changes, even for PJR+ to be satisfied. For this, consider the following simple instance with h: = 2, two voters, and respective approval sets {a, b} and {b.c]. Further, there is a candidate d approved by no one. The committee {b, d) satisfies EJR+, but after the removal of 6, only the committee {a, e} satisfies PJR+.
Using affordability, however, does not yield robust decre- mental PJR+ algorithm. In fact, no such algorithm exists.
Theorem 5.3. There does not exist robust decremental PJR+ algorithm.
Nonetheless, we can utilize maximally affordable commit- tees to construct a fully-dynamic PJR+ algorithm making two changes per iteration amortized, meaning that the total number of changes up to any time-step is at most 2t.
A similar incremental example can also be created. Consider an instance with h = 3 and six voters having approval sets {a, 6), {a, c), {a, d), {a, (S) {.}. Consider the com- mittee (b, c, d) before f becomes feasible. After the addi- tion of f to the instance, we would need to remove one of b, c, d, for whom the voter approving it, together with the voter approving {a, e) would witness a PJR+ violation.
Theorem 5.4. There exists a robust fully-dynamic PJR+ algorithu making amortized 2 changes per iteration.
EJR+ While our previous result shows that one can nearly achieve PJR+ in fully-dynamic manner, PJR+ in itself is quite a weak axiom for approval-based multiwinner voting (see for instance Peters and Skowron, 2020, Example 6). The strongest alternative to PJR+ which is still achievable in polynomial time is EJR+. However, EJR+ is not nearly as well understood as PJR+, which is significantly easier to achieve. Consequentially, fewer rules are known to satisfy EJR+ As any committee satisfying EJR+ also satisfies PJR+, our impossibility result in Theorem 5.3 also applies to EJR+.
PJR+ Nonetheless, we now construct robust incremental and almost robust fully dynamic PJR+ algorithms. We
require the following notion by Brill and Peters (2024), which is related to priceability (Peters and Skowron, 2020).
A subcommittee W S C of size at most i is maximally affordable if there exists payment system (pi)ien: C R20 satisfying the following constraints
As our first positive result we build upon an approximation result from Do et al. (2022) and show that a (log(k)) approximation of EJR+ is possible in a fully-dynamic setting
C1 (:(c) of E A, for all c E C and N
C2 E.ECP((O) s for all i N
7

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
making amortized two change per iteration. This in essence works similar to Theorem 5.4.
exist a filly-dynamic algorithm satisfying ((1)-EJR+ mak- ing amortized (1) changes per round?
Theorem 5.5. There exists fully-dynamic (log(()))-
EJR+ algorithm making amortized two changes per iter- ation.
6. Conclusion and Open Questions
We study proportionality in multiwinner voting for dynamic candidate sets, with voter preferences given via linear orders, distances in metric space, or approval ballots. Depending the setting and whether new candidates join, old candi- dates drop out, or both, we provide algorithms that make small amounts of changes while upholding proportionality or show that no such algorithm can exists by providing a lower bound on the changes necessary. An overview of our results can be seen in Table 1.
While Theorem 5.5 considers fully dynamic algorithms, it only provides an approximation factor depending on k. If we turn to the incremental setting, we can obtain + bounds for constant a > 1. Especially, the following result implies an incremental algorithm satisfying 2-EJR+ making amortized 2 changes per iteration.
Theorem 5.6. For any > 1 there exists an incremental a-EJR+ algorithm making amortized o-1 changes.
Our work leaves open several questions and possible future research directions. As "meta" future research direction, we highlight that the understanding of EJR and EJR+ as axioms is still quite narrow. For instance, despite extensive research, it is still an open question whether there always exists a ranking satisfying EJR for every prefix of the rank- ing (Skowron et al., 2017: Chandak et al., 2024) or whether there is safe querying procedure for EJR (Brill et al., 2023). Furthering the understanding of EJR and EJR+, e.g., by developing different rules characterizations of rules satis- fying EJR+ might shed further light on it and help to resolve the open questions regarding EJR and EJR+.
While achieving a robust algorithm satisfying exact EJR+ seems difficult, we are able to provide a committee that is robust with respect to a single added candidate. That is, for any committee W selected by the rule, and any added candidate e' there exists candidate W U {d} such that (W U (c')) \ {c) satisfies EJR+. This rules out strong negative results for incremental algorithms, akin to Proposi- tion 3.2 for PSC in the decremental setting. We achieve this by modifying the greedy justified candidate rule (GJCR) of Brill and Peters (2023) to be "locally stable"..
Theorem 5.7. There exists an incremental EJR+ algorithm that is robust with respect to single addition.
As a further point, we restrict ourselves to dynamic candi- date sets. A natural extension would be a setting in which not only the candidates, but also the voters are dynamic. This gives some additional difficulties. For instance, adding or deleting voters, changes the quota ğ throughout the pro- cess. Deciding whether it is feasible to deal with this, is an interesting possibility for future work.
The modification necessary even for this single step, as we give examples in the appendix that all known rules satisfying EJR+ are not robust with respect to single addition. This leads us to the open question whether there is an incremental algorithm for EJR+ that remains robust beyond the first step.
Open Question 1. Is there a robust (amortized) incremental algorithm satisfying EJR+?
A Acknowledgements
We further remark that all commonly considered rules satis- fying EJR+ fail to distinguish between decrementally robust and unrobust committees.
Chris Dong was supported by the Deutsche Forschungsge- meinschaft under grants BR 2312/11-2 and BR 2312/12-1. Jannik Peters was supported by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001.
Example 3. Consider the profile with 2 x {ai,.... a5 ,. 2 x {a),............... ag: y). 1 x (a.....,(0) as).2 2 (b]...., b,, x), 2 (b) (b...... by. y). 1 x {ci...., C4, c4, 3). x fci...., Ca. y). 2 x fet,..., } and fix known to satisfy EJR+ (MES, GJCR, and PAV) can choose the committee (ai..... as) U (b....., ba) U (et......u, )a). However, after the deletion of some a, we would need to add both x and to the committee to restore EJR+.
n = 13. Then, all rules
Impact Statement
Our paper is a theoretical work dealing with online algo- rithms ensuring "proportionality" and tries to enhance the understanding of proportional outcomes and the algorithms achieving them. While the goal of proportionality is to ensure that large groups of the affected population are ad- equately represented, naturally, this does not rule out that there are other potential outcomes that are more beneficial to society or "fairer" in some other aspects. In particular, is very much unclear whether the algorithms designed here should or could ethically be used for real-worke elections.
It remains unknown whether we can select an EJR+ com- mittee that is robust to a single deletion, and whether there is fully-dynamic or decremental algorithm satisfying a constant approximation to EJR+
Open Question 2. Is there an algorithm satisfying EJR+ that robust with respect to a single deletion? Does there
8

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
Axiom
Incremental
Decremental and Fully-Dynamic
PSC
X xs((log(lo(())) lower
rank-JR
x 12((k) lower b.
x xs((k) lower b.
Proportional Fairness
/ 44.24-approx
/ /4.24-approx
q-Core
/ 5-approx
5-approx
PJR+
(amort. 2-changes)
EJR+
/ 22aaproxx (amort. 2-changes)
/ (((oo()))--appox (amort. 2-changes)
Table 1. An overview of our results. indicates that a robust (amporizee/aappoxiiatelly optimal) dynamic algorithm exists for the respective problem and input type. An indicates that fully-dynamic algorithm can exist.
References
S. Bhattacharya, M. Costa, N. Garg, S. Lattanzi, and N. Parotsidis. Fully dynamic k-clustering with fast up- date time and small recourse. In Proceedings of the 65th Symposium Foundations of Computer Science (FOCS), 2024. Forthcoming.
G. Amanatidis, H. Aziz, G. Birmpas, A.
B. Li. H. Moulin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:103963 2023.
N. Boehmer and R. Niedermeier. Broadening the research agenda for computational social choice: Multiple prefer- ence profiles and multiple solutions. Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2021.
H. Aziz and B. E. Lee. The expanding approvals rule: improving proportional representation and monotonicity. Social Choice and Welfare, 54:1-45 2020.
H. Aziz and B. E. Lee. Proportionally representative par- ticipatory budgeting with ordinal preferences. In Pro- ceedings of the 35th AAAI Conference on Artificial Intel- ligence (AAAI), pages 5100-5118. AAAI Press, 2021.
R. Bredereck, A. Kaczmarezyk, and R. Niedermeier. Elect- ing successive committees: Complexity and algorithms. Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAT), pages 1846-1853, 2020.
H. Aziz and B. E. Lee. A characterization of proportion- ally representative committees. Games and Economic Behavior, 133:248-222 255, 2022.
R. Bredereck, T. Fluschnik, and Kaczmarezyk. When votes change and committees should (not). In Proceed- ings of the 31st International Joint Conference on Artifi- cial Intelligence (ICCAI), pages 144-150, 2022.
H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and Walsh. Justified representation in approval-based com- mittee voting. Social Choice and Welfare, 48(2):461 -455, 2017.
M. Brill and J. Peters. Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the
H. Aziz, Lee, Morota Chu, and J. Vollen. Pro- portionally representative clustering. In Proceedings of the 20th International Conference on Web and Internet Economics (WINE), 2024. Forthcoming.
24th ACM Conference on Economics and Computation (ACM-ECC page 301, ACM Press, 2023. Full version arXiv:2302.01989 [cs.GT].
M. Brill and J. Peters. Completing priceable committees: Utilitarian and representation guarantees for proportional multiwinner voting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9528- 9536. AAAI Press, 2024.
T. Bardal, M. Brill, D. McCune, and Peters. Proportional representation in practice: Quantifying proportionality in ordinal elections. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), 2025. Forth- coming-
R. Behar and S. Cohen. Representative query results by vot- ing, In Proceedings of the 48th International Conference on Management of Data (SIGMOD), pages 1741-1754, 2022.
M. Brill, H. Dindar, J. Israel, LLng, Peters, and U. Schmidt -eamiddtKrreeelin. Multiwinner voting with pos- sibly unavailable candidates. In Proceedings of the 37th AAAI Conference Artificial Intelligence (AAAI), pages 5532-5539. AAAI Press, 2023.
A. Bernstein, Holm, and E. Rotenberg. Online bipartite matching with amortized o(log?n) replacements. Journal of the ACM, 66(5):37:11377222 2019.
Caragiannis, E. Micha, and N. Shah. Proportional fairness in non-centroid clustering. In Proceedings of the 38th

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
Conference on Neural Information Processing Systems (NeurlPS), 2024. Forthcoming.
M. M. Islam, S. Vahidi, B. Schieber, and S. Basu Roy. Promoting faimess and priority in k-winners selection using IRV. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 24), pages 1199-1210, 2024.
N. Chandak, S. Goel, and D. Peters. Proportional aggrega- tion of preferences for sequential decision making. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9573-9581, 2024.
C. Jung, S. Kannan, and N. Lutz. Service in your neighbor- hood: Fairness in center location. In Proceedings of the 1st Symposium on Foundations of Responsible Computing (FORC), pages 5:1 5:15, 2020.
J. Chen, C. Hatschka, and S. Simola. Multi-winner recon- figuration. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS), 2024. Forthcoming.
Y. H. Kalayci, D. Kempe, and V. Kher. Proportional repre- sentation in metric spaces and low-distortion committee selection. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9815-9823, AAAI Press, 2024.
X. Chen, B. Fain, L. Lyu, and K. Munagala. Proportionally fair clustering. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 1032- 1041, 2019.
L. Kellerhals and J. Peters. Proportional fairness in clus- tering: A social choice perspective. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS), 2024. Forthcoming.
E. M. Delti, T. Fluschnik, and R. Bredereck. Algorithmics of egalitarian versus equitable sequences of committees. In Proceedings of the 32nd International Joint Confer- ence on Artificial Intelligence (IJCAI), pages 2651-2658. 2023.
J. Lacki, B. Haeupler, C. Grunau, V. Rozhoñ, and R. Ja- yaram. Fully dynamic consistent k-center clustering. In Proceedings of the 35th Annual ACM-SIAM Sympo- sium Discrete Algorithums (SODA), pages 1463-3484. SIAM, 2024.
V. Do, M. Hervouin, J. Lang, and P. Skowron. Online approval committee elections. In Proceedings of the 31 International Joint Conference on Artificial Intelligence (IJCAI), pages 251 251- 2022.
M. Lackner and P. Skowron. Multi-winner voting with approval preferences. Springer Nature, 2023.
M. Dummett. Voting Procedures. Oxford University Press, 1984.
B. Li, L. Li, A. Sun, C. Wang, and Y. Wang. Approximate group fairness for clustering. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages
S. Ebadian and E. Micha. Boosting sortition via proportional representation. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Sys- tems (AAMAS), 2025. Forthcoming.
2021.
S. Mahabadi and A. Vakilian. Individual fairness for k- clustering. In Proceedings of the 37th International Con- ference on Machine Learning (ICML), pages 6586-6596. 2020.
E. Elkind, S. Obraztsova, and N. Teh. Temporal fairness in multiwinner voting. In Proceedings the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 22633 -22640, 2024.
J. Matuschke, U. Schmidt-Kraepelin, and Ver- schae. Maintaining perfect matchings low cost. In Proceedings of the 46th International Collo- quium on Automula, Lunguages, and Programming (ICALP), 2019. URL https: //tp:://///ppp dagstuhl. de
S. Fish, Gölz, D. C. Parkes, A. D. Procaccia, G. Rusak, I. Shapira, and M. Wüthrich. Generative social choice. In Proceedings of the 25th ACM Conference Eco- nomics and Computation (ACM-EC), page 985. ACM Press. 2024.
201/20099910021 /df// LIPIcS- ICALP-ICALP--- 1AALLP-21190 221--22001122200 pdf.
E. Micha and N. Shah. Proportionally fair clustering revis- ited. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), pages 85:1-85:16, 2020.
M. Gallagher. By-elections to dáil éireann 1923-96 96: The anomaly that conforms. Irish Political Studies, 11(I): 33-60, 1996.
D. Halpern, G. Kehne, A. D. Procaccia, J. Tucker-Foltz, and M. Wüthrich. Representation with incomplete votes. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5657-5664, 2023.
D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of the 2 ACM Conference on Economics and Computation (ACM-EC), pages 793 794. ACM, 2020.
10

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
D. Peters, G. Pierczyáski, and P. Skowron. Proportional par- ticipatory budgeting with additive utilities. In Advances in Neural Information Processing Systems (NeurIPS), vol- ume 34, pages 12726-12731 2021.
Skowron, M. Lackner, M. Brill, D. Peters, and E. Elkind. Proportional rankings. In Proceedings of the 26th Interna- tional Joint Conference on Artificial Intelligence (IJCAI), pages 409 415. IJCAL, 2017.
N. Tideman. The single transferable vote. Journal of Eco- nomic Perspectives, 9(1):27-38, 1995.

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
Algorithm 1 Greedy Justified Candidate Rule (GJCR) (Brill
B.I. Rank Justified Representation
and Peters, 2023)
A voter has rank rank(i, c) for candidate if this candi- date is the rank(i, c)th closest candidate to this voter. An outcome W satisfies rank justified representation (rank- JR), if there is no rank r S m, no 1-large set of vot- ers N' C N and set of candidates C' S C such that rank(i, c) I r for all i E N' and с E C as well as He E W rank(i, c) S r for some E N n W = 0. In the following example with n = 4 voters and k: = 2, all committees satisfy PSC, but due r = 2, only committees containing b satisfy rank-JR (Brill and Peters, 2023).
W + 0 for l in 1,...,1 do while there is c & W: Hi E No: |I < <01 2 in do
Add candidate maximizing f No: |4, <
{ to W
end
end return W
A. Appendix: Multiwinner Voting Rules
In this section, we provide brief definitions of the mentioned rules.
a> b ed d > 0-
c> b 1 0 d>
Rules for approval ballots. Proportional approval voting (PAV) the rule that assigns a score of ([A, n WI) to each ballot A, and committee W, where HJ) is the j- th harmonic number. It then chooses the committees that maximize the sum of scores over the entire profile A.
e bx bb>d>>>0
For rank-JR, we show that neither incremental nor decre- mental rules can be robust.
The method of equal shares (MES) assigns each voter bud- get of &. Each candidate can be bought into the committee a for a cost of 1. MES proceeds iteratively and selects the next candidate by maximizing the minimal budget over the buyers after the purchase.
Theorem B.1. There is no robust incremental or decremen- tal JRR algorithm.
Proof. We give the following example with n = 12 voters,
m 13 candidates C = {ci,.... CB. cj, ......, cg. c}. and k 6. We show that the removal of 01 from C is incompat- ible with decremental rank-JR and the addition of c₁ oj to C (cr, ( is incompatible with incremental rank-JR:
The greedy justified candidate rule (GICR) also proceeds iteratively, by choosing the candidate currently causing the largest violation of EJR+. See Algorithm 1.
Rules for ranked ballots. Single transferable vote (STV) selects the candidates iteratively. Fixing n as the initial number of voters and starting with an empty committee, it adds any candidate e that is top ranked at least & times. (It does not matter which one if there are multiple such candidates.) STV then deletes this share of supporters of c and itself from the profile. In case that no candidate is top ranked sufficiently many times, instead candidate with the lowest amount of supporters is eliminated from the profile.
c > 02
1'. d > de x
2. > 03
2. d > d
3. 02 > 6 7...
3' 4 + 2
4. 0g > 4 > C...
4. d > 4 > c...
5. 0 > 68 C...
5' dg > 4 x c...
6. ca > C6 > C...
6. 4 > 4 > c
The Expanding approvals rule (EAR) also assembles the committee step by step. It assigns each voter a budget of 1 and proceeds rank by rank. If there is a candidate, for whom the voters giving it at most that rank have a budget of at least F. that candidate is added to the commitiee and the budget of these voters is decreased by g. Otherwise, the rank gets increased by 1.
Note that this instance is symmetric with regard to ramking candidates e; and df. We first show the following claim, which is crucial for both proofs:
Claim 1: If committee W satisfies rank-JR on C, then | n (c2, ca, c2, caH s 1. To show this claim, first let a committee W be given with {c2,cy)
W. Since ci are top ranked twice, c1 éf E W. Further, voters 5, 6 share candidate Gs at position r = 2 and thus one of {ca, cs, ca} must be contained in W. Since |W| = 6, W can only contain one of the candidates [ch...., d. Thus, there are always (i', C (3',...,6') obtaining none of their three
B. Missing Proofs for Section 3
We examine the notion of rank-JR and present the missing proofs for PSC.
12

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
most preferred candidates, leading the desired violation of rank-JR for W with 3. Now, let committee W be given with |W n {e2, ca = and |W n (ce, dgH = 1. We have to show that W violates rank-JR. Again, c1,c| E W. Further, voters 5,6 6 share candidate ca at position r = 2 and thus one of {Ca, Cs2 ) must be contained in W. Since the same argument holds for voters 5', 6', the committee W already contains 6 candidates and & W. Note however, no matter how we choose the candidates, there will be one voter i E {3, 4, 5, 6} not obtaining any of their top three ranked candidates: If we choose 05 (c4), voter 6 (voter 5) is unhappy. If we choose co. voter 3 or voter 4 will be unhappy as we can only choose one of {c2.3 }. By applying the same argument, we obtain j E {3', 4', 6') for which W does not contain any of their top three candidates. Since j both have 7 as their third most-preferred candidate, { induces rank-JR violation for W and r 3. This concludes the proof of the claim.
(1 - 1) x of
0j c x ...
1 x os 2 c - d - -
1 x u
of > dj > ~
We set k = t(t + 1) and thus " = t. For now, consider a fixed block B, E [4] First, we notice that a, needs to be included to satisfy rank-JR, as there are & voters top ranking it. To not need additions after the deletion of a, we include some b,((9) with z(i) S t for each i. Further, we claim that ट cannot be chosen: for each i E [t].j e [t] (a(i)) to satisfy the (t 1) voters uf of and the voter b. 2 we need to include one of b/, ce de to satisfy rank-JR. All additions so far considered for B, this enforces + I candidates. Iterating over all blocks, we overall enforce (tt + 1) candidates, filling the committee and leaving c unchosen. But then the set of voters (vg (02+))())))) )ige witness a rank-JR violation, as they all rank candidate 7 on rank 3.
k
The following is clearly true: Claim: If a committee 2 on C (ci,d) satisfies rank-JR, then {c2, c3, 222 d3} C W
For the incremental case consider the same profile before the addition of (ai)ist
For the incremental rank-JR violation, we see the following: Any rule / satisfying rank-JR on C = fei, 4 } must
return 2 containing {c2, C3, c2. c3J. For C² = C² {c]} thus [W1 n [fe2, C3, c2) 2 3 and thus for C = C
1 of: b >...
we have w n ffee, C3. c2 H 2 2. This implies that f fails rank-JR by our Claim 1.
1 x of by
(t - 1) x oft1
b1 > c x
For decremental rank-JR, apply Claim to obtain that wlog W n {e2, c3} = 0. Deleting e1 now requires the addition of both (2, Cg, as desired.
(t- x vttt
b > d 7 ci > d x ē
1 1 1xx2tt1 2+11
We generalize this approach to show that for any / there is an instance in which at least changes must be made after deleting a single candidate. This provides steeper lower bounds than for PSC.
1x u
o > d
27
Theorem 3.3. There is no incremental or decremental al- gorithm satisfying the rank-JR axiom of Brill and Peters (2023) and making ok) changes amortized per round.
Clearly, we must choose all bj for j,j for However, after adding .,,..., a2, we can similarly to the decremental case prove that at most < t candidates of the
S t,, i.e., t2 candidates.
Proof. We now create a profile in which each committee satisfying rJnk-JR must add t candidates b'....8 b' after the deletion of some candidate a to maintain rank-JR. Consider the following instance consisting of t blocks (B,)ss,, each B, consisting of t(t + 1) voters with the following 38 voter types (w ssss:
form b) can be contained in a committee satisfying rank-
JR. This constitutes > t² - replacements in rounds, hence in some round there must have been f - = ((Vk) replacements.
This further raises the question whether the bound is tight.
Open Question 3. Is there an incremental or decremen- tal algorithm satisfying rank-JR making at most O(Vk) changes amortized per round?
x of a > b) ....
1 1x uff ai > b >
B.2. PSC
(t (t- 1) x x : b) > ot
Observation 1. The single transferable vote (STV) and the expanding approvals rule (EAR) of Aziz and Lee (2020) can
13

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
select committees that not robust to single deletion for PSC, even when such committees exist.
further (1 1)s voters. Whenever is a multiple of I, we can set h r t-1s. Thus, a set of voters is 1-large if it has cardinality 2 t. PSC now implies that ai..... Or must all be chosen. Further, if in the next time step a; is deleted, then PSC enforces that all candidates in the subset (i) C B are chosen. Since any a, could be deleted, this means that for the committee to guarantee PSC after one deletion, s candidates from B must already be chosen in this round. Clearly, 1 + >> (-1 r k. Choose = 12, Then, 8 + - k = fs 1- -t 6- candidates 6; remain unchosen. If the corresponding (j gets deleted, at least t - 2 additions are necessary to restore PSC. For the asymptotic bound, observe & E ((r) = O(s"). Thus, there is a constant E R20 with k S cl2,, which implies V S l' and thus log( / S (log((), and finally
Proof. For an example of STV failing this, consider the following instance
0 b
>
1. So at least
b > a > x
x> >
C> 2->> y x >
Here, with = 3 STV could first select a and delete the first two voters who top-rank a from the profile. Then delete select x, and delete voters three and four who at this time rank on top. Finally, delete e and choose y. Now if a withdraws, both b and need to be added. We note that the same committee could also be selected by EAR. This instance, however, admits a robust committee, for instance M
W (log( / () S for the product log function W. Thus, the number of additions necessary to restore PSC have lower bound of ((lo((og(()))).
C. Missing Proofs for Section 5
We first remark that the modification to GJCR truly nec- essary to obtain committee that is robust with respect to a single addition.
{a, 6, x is robust to a single deletion.
There does not exist robust decremental PSC algorithm. After single deletion, any algorithm may require (log(lg(())) replacements to restore PSC.
Proposition 3.2.
Proposition C.1. GJCR, MES, and PAV can elect commit- tees that are not robust with respect to single addition.
Proof. Let t < E N with = (i) Consider the fol- lowing instance over the candidate set C = {a1..... a, U (b,...., b..::
Proof. Consider the following approval profile with ap- proval sets x {ui,..., as 3 x {ai,..... a4 x),2 x (b....., b5, x3.3 x {b 65 1 (c....., c1 {c (c....,,44: 2), 2 x (dl...., dg. y). {d) ( dg) with = = k. Here possible MES committee is all candi- dates except for x and y. However, now adding a candidate approved by the three voters voting for only b candidates and the three voters only voting for d candidates, would require one other candidate to be removed. If an a or c candidate is removed that candidate witnesses an EJR+ violation. b or d candidate gets removed, the corresponding voters approving y witness an EJR+ violation, consist of 5 voters, but only approve 4 candidates in the outcome.
> bj
d1 > b
a2 > b2
22 > bit1
Or > b--e41 >
To extend this to PAV consider the same instance, consisting of copies of 3 x {aI..... ).). 1 x {a)..... 04 2), 4 x {b..... b,, x}. 1 x (bi...., by} with n = 54 = k Here, a optimal PAV committee would choose the copies of the a and b candidates, as adding the x candidate for an a candi- date would decrease the PAV score by - - + < 0 while adding the x candidate for a b candidate would leave the PAV score unchanged. However, adding a candidate ap- proved exactly by the (b,,..., b5) voters, would need this candidate to be included, leading to the same contradiction as in the first case.
0r > b, x
(t (t-1) 1) x bi
(t - 1) x b.
To be more precise, for each subset of t candidates from B, i.e., each B' E (B). we add one voter ranking (:(B)) first and b E B' second. This yields tr voters. Then, for each i S 8 we add voters ranking b, first. This adds
Corollary 5.1. Every completion of a maximally affordable
14

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
subcommittee satisfies PJR++
Proof. Consider an instance with set of 12 voters N {1,..., 12.. target size k = 6, and set of (22) candi- dates C' = {eigi i,j E NN, < j}. one candidate for each pair of voters. First, assume that the chosen com- mittee is (c1,2, C5,4, 27,8, C9,10, (11,2) (or equivalently any other committee covering all voters). Now let the first deleted candidate be C122. Let e' be the replacement candi- date. We distinguish two cases, Firstly, if c' is not approved by or 2, we can assume without loss of generality that it is C6.7. Then after deleting candidate c3,4, in order to restore PJR+ one would need to cover at least three of 1, 2, 3, 4 as otherwise one of 1, together with one of 3, 4 would wit- ness a PJR+ violation. This is impossible with just a single candidate. Therefore, e' has to be approved by either or 2. Without loss of generality, we can assume that it is C2,3.
Proof. Let W = fc...... ct) J be maximally affordable w.r.t some (p:)s. Then clearly, 8 I k as the voters only have budget & in total. Assume for contradiction there is a viola- tion of PJR+ for W based on size-k largeness, i.e., some CE C.C W with some N' S N such that E NIEN A, and UUSN A, n W| < l despite |N'] 2 gg for some f E N. The total amount of budget spent by N' is thus at most f - 1
with their starting budget being at least e l = f. This is the desired contradiction as C5< is violated.
Theorem 5.2. There exists robust incremental PJR+ al- gorithm.
Next, we delete c2 In order for C1,5 C1,6 to not witness PJR+ violation, we need to cover voter 1. If we include nei- ther C1,5 nor C1,6, this leaves 5 and 6 uncovered. Therefore, after deleting for instance 09 in the last step, we would again need to cover at least of the uncovered voters, which is impossible with a single candidate. Hence, without loss of generality, we added C1,5, We will immediately delete this candidate again, leaving all three of 5, 6 uncovered. In order, for and 6 not to witness PJR+ violation, we need to cover at least one of them. If we add C1,6 we immedi- ately delete it again. Now dependent on which candidate we add, we can either delete 67,8, Co or C11,12 and again get four uncovered voters, witnessing a PJR+ violation, which cannot be repaired with a single candidate. If we did not add C1,6 two of 1, 5, are again uncovered and dependent which candidate we added deleting C7,8, C9,10, or 111,12 gets us four uncovered voters leading to a PJR+ violation.
Proof. The first & candidates that arrive we take into our committee T0 = -C. We create a partition of W = X U y into a maximally affordable committee X and disposable part y For this, initialize both sets empty and assign total budget of k equally among all voters, i.e., & to every voter. They will proceed to buy candidates, each for the price of 1, into X as follows: As long as there is a candidate e such that N₂ has a total budget of 2 to afford it, add e to Xº, and subtract the budget of 1 off any of these voters in any way such that the budgets are not exceeded. Store this subtracted amount as (c). By finiteness of the budget, this process must terminate after finite number of steps. Clearly, C1 to C4 are satisfied for X Further, C5< is satisfied as else the candidate violating the inequality would be bought into the committee and the process cannot have already terminated. Clearly, | S k as the voters only have budget i in total. Now, set Y = Co XO. This concludes the induction start.
Similarly, if we started with a committee leaving one voter uncovered, for instance {ci,2, C3,4, C5,6: C7,8, C9,10- C10,11 } after deleting c1,2 2 we need to cover voter 12. we do with 01,12, we can delete this candidate again immediately. If we then add 22 and delete it immediately, we are left with four uncovered voters in any case, thus witnessing PJR+ violation. If we do not add 02,12 both 0122 are uncovered leading to a PJR+ violation after deleting C3,4. Similarly, if we did not add C1,12 in the first place, the voters 1 and are uncovered. Thus, after deleting an appropriate next candidate, PJR+ cannot be restored.
For the induction step, let two disjoint sets X Y C O" given such that their union is of size l and X is maximally affordable in Ct with cost function p' (and thus satisfies PJR++ with respect to size A largeness). Let now a new candidate e* be added, i.e., C++1 = Uc").. J. X still maximally affordable, we can set X = XX, y Y". and p²+1 = p'. Else, there must be E C++1 such that one of the conditions is violated. Since C1 to C4 did not change, it must be C5< and c = c² Thus, No- can afford to buy c* into the committee. Set X = X U' Uc') }. Clearly, since there was budget left to buy c", we have X < le and thus |Y'| >>>00 0. Thus, remove an arbitrary element y E y i... set y++
Theorem 5.4. There exists a robust fully-dynamic PJR+ algorithm making amortized 2 changes per iteration.
y \ {v}. Set pi(c") as the amount of budget that was taken from voter i finance c". It easy to check that W satisfies all 5 axioms and thus is maximally affordable. This concludes the induction step.
Proof. Our goal is to maintain maximally affordable sub- committee throughout the process. Let Co be the initial candidate set. We compute an affordable subcommittee Mo of maximum size for Co and fill the remaining seats arbitrar- ily to initialize some committee W,, = Mo U Do with Do consisting of discardable candidates and initialize i tokens.
Theorem 5.3. There does not exist a robust decremental PJR+ algorithm.
15

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
For 1 2 O, at the start of the next time step ( + we add two tokens. When some candidate E C2 is deleted from C there are three cases. If e & W5, we set D1+1 = Dr and M++1 = M,; if c E De, we refill D(+1 by replacing with an arbitrary candidate d E C++1 \ W2 and remove a token; and if É M, we first refund the budgets spent on c. Then, iteratively, we refill M starting from M, by adding affordable candidates and dispose any candidate from De, as well as one token, until no candidate is affordable. If we do not add any candidate this way, we instead add d & W, to Dr to obtain D remove a token, and set M,+1 = M, \ {e). Whenever some candidate & Ct gets added to C++1, we check whether this candidate is affordable. If it is. we add it
total budget was k, we have a committee of size k. We fill up the remaining places with placeholders. Now, if can- didate is added and creates a violation of H (K)-EUR++ w.r.t. some & S k. then each voter that is part of this violation can have spent at most Ejst njH[(K) To buy this candi- & date into the committee, they spend at most S ned[( and thus no one overdraws their budget. Especially, since the budget was not fully used before, there are placeholders in the committee. Replace one of them with the newly added candidate. then H (k))-JJR++ is restored. Conversely, if candidate e is deleted and this creates violations of H (A:) EJR+, we can reimburse the voters who previously bought the candidate into the committee. With the same argument as in the instantiation and the addition of a candidate, we obtain that each voter has sufficient budget to buy the can- didates causing the violations into the committee. There can be multiple of these changes to the committee after a single deletion. However, note that for E S l changes to be made, there must have been & total budget that was not used or freed beforehand. If the budget was freed, at most corresponding dummy candidates have been added to W before. Together, these are at most 26 changes, preceeded by l rounds in which the budget was freed or not used. L
to W/ to obtain Mo+1 and remove any d E W, \ Mr A 0, as well as a token.
Clearly, Mj is maximally affordable and hence Wt satisfies PJR+ in each time step I. To see that we need at most 2 changes per round amortized, note that in each round we add two 2 tokens. Hence, it suffices to show that the token count is always non non- non-neeaaive. Let K' = |Moo be the size of the initial committee and 1' be the number of added candidates. We claim that at each time-step 1, there are at least k' + L' Mr] tokens left. At time-step 0 this is clearly true, as we have not added any candidates tokens yet. Thus, assume that it holds at time-step t. If we add candidate I,+1, we increase the number of tokens by at least one. Thus, the invariant still holds. If we delete a candidate not in the committee, the invariant is also still true, as we have just added two tokens. Similarly, if we delete from Dr we add two tokens and remove one. Thus, finally, if we delete candidate from D, we add new candidates until we reach a final maximally affordable subcommittee M++1. As the size of the original maximally affordable subcommittec was k and as we just added 1' candidates, we know that D++1 < k' + Therefore, the invariant still holds, even after deleting a candidate from D,.
Theorem 5.6. For any a > there exists an incremental a-EJR+ algorithm making amortized a a-1 changes.
Proof. Let a > 1 be given. For small k with k < a we can replace the entire committee in each step and triv- ially obtain the result. Else, we have > a a-I implying A[1 - a) < aa and thus < k - 1, which finally leads to the desired _ k. Begin by running any EJR+ rule for the committee size [ and select - _ other can- didates arbitrarily. For the next k - = steps, while there is a candidate arriving who witnesses an a-EJR+ violation, include them in exchange for one of the arbitrarily added candidates. Afterwards, recompute committee of size 1 satisfying EJR+ and add them into the committee by ex- cluding arbitrary candidates. After k - [ + 1 steps, we thus have made at most k: replacements. This leads to amor- 4
Theorem 5.5. There exists a fully-dynamic ((log(k))- EJR+ algorithm making amortized two changes per iter- ation.
tized K-1 --([---1 replacements per round which concludes the proof.
k --
Proof. Let (n) denote the n-th harmonic number. Con- sider for the start a modified GJCR that considers groups of size 2 (K)ee instead of 2 e Again, this rule can be modeled via a budget of & for each voter, which the " voters then all uniformly spend when they can buy a candi- date, which all have unit cost. To show that on Co GJCR computes at most h candidates, observe that each voter can buy at most 1 candidate for violations with é = 1, 2 for violations with e < 2 and so on. For a violation w.r.t. f, the price the voter pays it at most .. In total, this yields & k. So, no voter overspends, and since the Lesk (K) n.
Theorem 5.7. There exists an incremental EJR+ algorithm that is robust with respect to a single addition.
Proof. To show this theorem, we use Algorithm 2. In essence, Algorithm 2 runs the GJCR with an additional local swapping step at the end. This local swapping step tries to maximize the number of voters covered in each it- eration. As Algorithm 2 produces one possible outcome of GJCR, it satisfies EIR+.
16

---

Proportional Multiwinner Voting with Dynamic Candidate Sets
Algorithm 2 Locally Stable GJCR
GJCR, one of these "buyers" must pay less than A. leading to contradiction that selected k candidates (see Brill and Peters (2023, Proposition 8) for full proof). Therefore, we could have swapped c" with c' increasing the number of covered voters in iteration & by at least 1, as there is no voter who go down to approvals after the removal of c. (The implicit assumption here that & at least which must true, as otherwise j approves nothing, and would not have selected & candidates.)
W +- 0 Nactive + 0 for E in .....,, do
We = 9 do
while there e & W: 1 No: | <01
fm do
Choose e maximizing li No: |4, M W| <
2) Naetiivll We < Wc) W < (c)cc Nactive t- Nactive U e No: | l). end
while there was a change in the last iteration;
for C We & W do
l[ Ne:: |A W \ [cH < <0)> in
and i No: [Ag W
{c}l tHl li
No: {4,n n W! {c) = =] then
We + We [c [c) W + wufc) \ (c)
N Nactive + {i N::N:: =
end
end
end
return W
If Algorithm outputs less than candidates, the theorem follows, as we can simply include the new candidate in the committee with single swap, swapping out an irrelevant candidate. Thus, assume it outputs & candidates and let be the newly added candidate witnessing EJR+ violation. Let N' C No be the set of voters witnessing the violation with [N'| 2 8 and |A, n W| < l for all i E N'. If [A; n W = 0 it is easy to see that the committee could not have been size k. Therefore, every voter in N' approves least one candidate. Let E N' be any such voter and let = AA: n W Let c' be any arbitrary candidate in A W and consider the committee W = W \ {d'} U {c}. Further, assume that W does not satisfy EJR+ with its violation being witnessed by candidate c" for threshold t and set N" C Nor. We distinguish two cases:
Case (" > l, Then, iteration E" some voter in N" must approve at least &" candidates, one of which must be d' Therefore, c' got bought in iteration before f, contradiction.restttbbl
Case 2: 8" < E,. Then, someone in N" must approve of c'. Since 8" e, this voter must approve less than l candidates in iteration E; and must therefore have contributed to buying 4. Thus, this voter approves least l, - 1 candidates in W' contradicting !" l,
Case 3: !" = 4. Let NY {j N" N" E Ay). I N" this set must necessarily include who still approves (" candidates in the outcome, contradiction. Therefore, there is j E N NY. However, since for GJCR to select candidates, every "buyer" of must approve exactly & candidates. Otherwise, the price-system constructed by
17


Reviews:
[{"review_id": "Pb9SWESQTv", "reviewer": "Reviewer_ut2U", "summary": "The paper considers multiwinner voting rules when the candidate sets are dynamic in one of 3 ways - candidates arrive one at a time, leave one at a time, or a mix of both. They consider 3 different types of preference classes - ordinal, distance-based, and approval based. They show that in some settings, there exist voting rules that achieve proportionality (which is defined differently depending for each preference class) whereas in others, there cannot exist any such rule.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and suggestions. We implemented the changes (for the next version).", "claims_and_evidence": "Yes, the claims are appropriately cited or proven.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "As far as I can tell, the proofs in the main body of the paper are correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "There appear to be several related works in related online settings, but none in their specific models.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The online models they consider are reasonable, and their results in these models appear promising. They also study several preference models. I also particularly like all the negative results they have, especially for existing voting rules.\n\nMy only (minor) complaint would be that the proofs don't seem very technically novel, or at least it is unclear to me what the novel parts are. If there are any new ideas, it would be better if the authors could highlight them more.", "other_comments_or_suggestions": "Page 4, Near Line 184 \".As there are ..\" missing a space after the period.\n\nPage 5, proof of Theorem 4.1, I got briefly confused because $i$ is used for both the voters and the index of the clusters $N_i$ which have no relation to the individual voters. I would suggest a different indexing variable.\n\nPage 13, Proof of Proposition 3.2. It should say $t<s$, not $s<t$.\n\nPage 14, Proof of Theorem 5.3, the target size should be $k=6$, not $k=4$.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hkmOeK8IB4", "reviewer": "Reviewer_gYxQ", "summary": "This paper introduces a temporal element to multi-winner voting by studying a model wherein the set of candidates changes over time. This is separated into three settings: incremental (candidates are added over time), decremental (candidates are removed over time), and fully dynamic (candidates can be added or removed over time). These settings are each studied under three different paradigms of multi-winner voting: ranking-based, approval-based, and clustering.\n\nWithin each paradigm two proportionality axioms are studied. The paper shows that, across paradigms, proportionality can typically be achieved or approximated when candidates are added over time. When candidates are removed or in the fully dynamic setting proportionality can sometimes be approximated.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the kind review! \n\n- I would be interested to hear your perspective on the informativeness of any experiments that might be done on this setting.\n\nAnswer: \nWe have thought about this for a bit. There are a few possible experiments we could see. Firstly, we already did a bit of experimentation using preference sampling, namely, we tried to find simple examples akin to Observation 1 or Example 3 in sampled data (e.g., we used some preference distributions for approval preferences, ran common voting rules such as MES or PAV and tried to see if the committees selected by them are not robust to a single deletion). However, we were not able to find any such violations in the short experiments we conducted. \n\nSecondly, what might be a bit more interesting would be to experiment on real-world data. Namely, there are two recently \"uncovered\" large datasets from last year, one being a dataset of approval-based multiwinner voting elections for so-called proof-of-stake elections by Boehmer et al. [1] and the other one being a dataset of over 1000 multiwinner ordinal preference elections from local Scottish government elections by McCune and Graham-Squire [2]. In particular, we would find it quite interesting to evaluate the effect of so-called \"by-elections\", i.e., elections to replace a candidate who dropped out of the parliament. In particular, these by-elections are not done using a proportional voting method, but by employing the singlewinner instant runoff voting rule. It would be interesting to see, if somehow one can measure the impact of this on the proportionality of the outcome.\n\nInterestingly enough, the data provided by Boehmer et al., is actually temporal. Namely, in these blockchain elections, there is one election per day. We would find it interesting to see, if one can perhaps use this data to evaluate our findings and to actually check whether dynamic multiwinner voting is hard. (We note that their data comes with the added difficulty that it allows voters to change their preferences)\nReferences: \n\n[1] Boehmer, Brill, Cevallos, Gehrlein, Sánchez-Fernández, Schmidt-Kraepelin, 2024, AAAI, Approval-based committee voting in practice: a case study of (over-) representation in the Polkadot blockchain\n\n[2] McCune and Graham-Squire, 2024, Social Choice and Welfare, Monotonicity anomalies in Scottish local government elections", "claims_and_evidence": "The claims in the paper are described quite clearly. Some theorems are supported by a proof in the main text (while other proofs are relegated to an appendix) and the claims all seem to be quite reasonable and attached to some evidence.", "methods_and_evaluation_criteria": "The paper is entirely theoretical and conceptual. The proofs that I considered were well-written and are the suitable method for supporting a theorem.", "theoretical_claims": "I lightly reviewed the proofs that are included in the main text and found no issues.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper builds upon three existing paradigms of multi-winner voting and a specific priority (proportionality) which is popular within the multi-winner setting. Much work has been done on these topics; this paper adds what seems to be a fairly novel -- but quite natural -- component of dynamicity. The paper fits quite neatly into contemporary work on multi-winner elections within computational social choice.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "In general I find the paper to be quite well written. Put bluntly, I typically find purely theoretical papers to be quite a slog and this was much easier to read than I had anticipated. In considering three paradigms of multi-winner voting and three types of dynamic candidates the paper manages to quite naturally fit in an impressive amount of content while remaining fairly readable.\n\nMany temporal settings have been studied in the single winner setting (e.g. in iterative voting settings) but I have not previously seen work on this dynamic candidates in multi-winner settings. The motivation is quite natural and makes understanding the task seem a useful step towards approaching real-world applications.\n\nPersonally, I would consider the paper to be more useful in a setting where page limits are not an issue. This might be better as a journal paper but I recognize that in our current time a conference is the expected venue for publication. \n\nRelatedly: while the paper fits in quite a bit already and is focused on establishing early theoretical results I can easily imagine some experiments being informative. In particular, I would be interested in understanding how often the various axioms you study are violated by various voting rules under different parameters (e.g. number of voters, number of candidates, preference distributions).", "other_comments_or_suggestions": "Tiny issues to adjust:\n\n- missing a space on line 3 of section 3\n- line 336 should probably include W: \"a committee $W$ satisfies\"", "questions_for_authors": "I am unlikely to update my evaluation based on your response. Feel free to respond, or not, to any portion of my review. I would be interested to hear your perspective on the informativeness of any experiments that might be done on this setting.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ye4reEMyUD", "reviewer": "Reviewer_hSUk", "summary": "This paper consider a series of problems about modifying the winner set of a multi-winner election when there are changes on candidates. The paper investigate three types of voter preferences: rankings, metric-space, and approval (0-1). Both positive (algorithms satisfying certain fairness axioms) and negative (some fairness axioms cannot even be approximated) theoretical results are given.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Explain your contradiction for Theorem 3.1\n\nAnswer: We are given a profile with $n$ voters and a committee $f(t-1)$ that previously satisfied PSC. At time $t$, a new candidate $c_t$ becomes feasible, and $f(t-1)$ may now fail to satisfy PSC -- we would like to fix that with a single swap involving $c_t$. Assume that we cannot do so, then $f(t-1)\\cup \\{c_t\\}\\setminus \\{b\\}$ violates PSC for all $b\\in f(t-1)$.\nIn total, this yields $k+1$ committees that violate PSC. For each of these committees, we prove that we can reserve $\\frac nk$ voters. Thus, in total there are $(k+1)\\frac nk$ voters -- more than $n$, a contradiction.\n\n- Explain your proof for Theorem 4.1.\n\nAnswer: We apologize for the confusion created here, we agree that we were a bit sloppy in writing the proof. We are sorry for this. \nOn a high level our proof works as follows: we start off with a pre-clustering phase, leading to $k$ groups of agents $N_1$ to $N_k$. In particular, in the way we define it an agent can be part of multiple groups. To construct these groups, we use a common technique from other papers, namely, we give each of the $n$ agents a budget of $k/n$. With $k$ groups to be opened at cost of $1$ each. this intuitively means that each agent can open their \"proportional share\" of a group. We now open these groups by letting the agents buy groups using their share of the budget, and we assign each agent to a group they paid for. Now, after creating these groups, we go one-by-one and let them pick the cluster center that is closest to them. When a point is added, we update these picked cluster centers and potentially swap cluster centers between these groups (that is the invariant envy relation). In the end, we use this fact that every group has their \"favourite\" cluster center to bound the factor by which any set of n/k agents can improve.\n\n- The proof is extremely confusing as many steps are unexplained. The proof starts with creating clusters, while many details are omitted (such as what are the p_j(i)\n\nAnswer: In general, we will make sure to mark clearly the properties that are important for the high level idea of the proof, and state which arguments are only required to prove these important properties. \nE.g., it does not really matter how the prices are chosen and we agree that we should explain that. To show that it is possible to define prices, one way to do so is: (1) check for the first voter in $N'$, i.e., $i_1 = \\min\\{i\\in N': b_i > 0\\}$ whether she has a budget of $1$ on her own. If yes, we reduce her budget by $1$ and only let her pay for the cluster. (2) If no, voter $1$ pays all she has and we set her remaining budget to zero. Consider the next voter in $N'$ with positive budget. If $i_2$ can pay for the remaining cost, she does so and we reduce her budget accordingly. (3) Otherwise, she contributes all of her remaining budget, we set her budget to zero and continue.\n\n- and what if two clusters with same diameters comes together).\n\nAnswer: If there are ties any of them can be chosen, i.e., we assume some arbitrary tie-breaking. We will note this in the paper.\n\n- Then it goes into show the envy relations keeps invariant in the modifications, but I don't see this is applied anywhere in the proof.\n\nAnswer: The envy relation is just technical and guarantees us something important: the chosen committee contains the closest candidate to each cluster $N_i$. We apply this in line 320. Here, $i$ belongs to a cluster $N''$, and hence we can assume that cluster member is closer to the chosen committee than i is to c.  \nWe will state our goals more clearly in the proof.\n\n- Finally, the real part for the axioms seems have nothing to do with the dynamic changes.\n\nAnswer: Indeed, the guarantee holds at every time step. Note that the tricky, dynamic part of the algorithm is described within the envy cycle procedure -- here, when candidates join or leave the election, we determine, depending on how the envy of the clusters, whether we need to modify the committee for this time step.\n\n- For Right Column of Line 277-286, the formula, rho is undefined. I doubt it is the approximation ratio Gamma for proportionally fairness.\n\nAnswer: Sorry about this, indeed rho is supposed to be gamma, i.e., the improvement factor or approximation ratio. We will declare more clearly where the variable comes from.", "claims_and_evidence": "Yes, the claims are supported by the Theorems and proofs.", "methods_and_evaluation_criteria": "Yes (once the proofs are correct).", "theoretical_claims": "I checked Theorem 3.1 and Theorem 4.1 \n\nI think Theorem 3.1 is correct. \n\nFor Theorem 4.1, I would be careful to draw the same conclusion. The proof is extremely confusing as many steps are unexplained. The proof starts with creating clusters, while many details are omitted (such as what are the $p_j(i)$, and what if two clusters with same diameters comes together). Then it goes into show the envy relations keeps invariant in the modifications, but I don't see this is applied anywhere in the proof. Finally, the real part for the axioms seems have nothing to do with the dynamic changes. For Right Column of Line 277-286, the formula, \\rho$ is undefined. I doubt it is the approximation ratio Gamma for proportionally fairness.\n\n--------------\n\nAfter rebuttal: theorem 4.1 is further explained and looks better. I encourage the authors to improve the presentation of the proof.", "experimental_designs_or_analyses": "This paper have no experiments.", "relation_to_broader_scientific_literature": "This paper expands the discovery of multi-winner election to the scenario where the candidates may change. The potential significance of the problem is illustrated in the introduction of this paper, where a series of scenarios with changeable candidates are given.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength: The paper studies an interesting and well-motivated extension of multi-winner voting. The authors study the problem under three different preferences models and prove a bunch of non-trivial theoretical results, giving a somewhat thorough characterization. The paper also well placed itself in the previous literature. \n\nWeaknesses: There can be a large improvements on the presentation of the paper, especially the proof. The proofs lack intuition, intention, and explanations on each step, making it non-trivial to understand what each step is doing. This applies to the contradiction method in Theorem 3.1 (what makes a contradiction? specify it) and almost everything in Theorem 4.1. The paper will largely benefit from adding intuitive proof sketch, running examples, and more discussions. \n\nFor now I will give a negative score. If the authors could persuade me that their Theorem 4.1 is correct, I am happy to raise my score.\n\n------\nScore updated.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. Explain you proof for Theorem 4.1 and the contradiction for Theorem 3.1. Address my questions in the ''correctness' part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In the end, all the reviewers viewed the paper positively. The idea of dynamically changing the candidate set is novel and is certainly worth presenting. The paper is well written, especially given its theoretical nature.
Decision: Accept (poster)