Multi-Winner Reconfiguration
Authors: Jiehua Chen
Christian Hatschka
Sofia Simola
Venue: NeurIPS 2024 poster (2024)
Keywords: computational social choice
computational complexity
algorithmic design
Primary area: algorithmic_game_theory

Abstract: We introduce a multi-winner reconfiguration model to examine how to transition between subsets of alternatives (aka. committees) through a sequence of minor yet impactful modifications, called reconfiguration path. We analyze this model under four approval-based voting rules: Chamberlin-Courant (CC), Proportional Approval Voting (PAV), Approval Voting (AV), and Satisfaction Approval Voting (SAV). The problem exhibits computational intractability for CC and PAV, and polynomial solvability for AV and SAV. We provide a detailed multivariate complexity analysis for CC and PAV, demonstrating that although the problem remains challenging in many scenarios, there are specific cases that allow for efficient parameterized algorithms.

Multi-Winner Reconfiguration
Jiehua Chen
Christian Hatschka
Institute of Logic and Computation TU Wien Austria
Institute Logic and Computation
TU Wien
Austria
jchen@ac. wwwp://..twwiencc.co
chatschka@@a. www.ee..wwwwwiicccmm
Sofia Simola
Institute of Logic and Computation
TU Wien
Austria
ssimol a@ac. www.ew.w..cc.e.mmmm
Abstract
We introduce a multi-winner reconfiguration model to examine how to transition between two subsets of alternatives (aka. committees) through a sequence of minor yet impactful modifications, called reconfiguration path. We analyze this model under four approval-based voting rules: Chamberlin-Coume (CC), Proportional Approval Voting (PAV), Approval Voting (AV), and Satisfaction Approval Voting (SAV). The problem exhibits computational intractability for CC and PAV, and polynomial solvability for AV and SAV. We provide a detailed multivariate com- plexity analysis for CC and PAV, demonstrating that although the problem remains challenging in many scenarios, there are specific cases that allow for efficient parameterized algorithms.
Introduction
In the rapidly evolving landscape of technology, policy, and market dynamics, we need to be able to adapt and reconfigure existing solutions. This necessity spans various domains, such disaster management (Ito et al., 2011; Ju et al., 2017) where one needs to switch, step by step, from an existing power supply distribution another one, while ensuring no blackouts occur in-between and game and puzzle-solving (Nishimura, 2018) where one needs to transfer from one feasible state another via sequence of feasible moves. The crucial idea is employ a systematic approach to transition from one solution to another with minimal disruption. Such concept, known as reconfiguration (Ito al., 2011), omnipresent in areas ranging from everyday life to complex cecision-making processes in computational social choice (COMSOC) such as switching catalogs in streaming services (Prime-Videe 2024; Netflix, 2024) or product displays in department stores.
This paper delves into reconfiguration within COMSOC, using multi-winner elections as a primary example to illustrate its importance and applicability. Our focus is on how find such recon- figuration through incremental yet meaningful changes, adhering to set criterion that quantifies the "closeness" between successive solutions. In multi-winner elections, we are given a preference profile consisting of a finite set of alternatives and a finite set of voters, each with preferences over the alternatives. The objective to select a committee (i.e., a subset of alternatives) of fixed size representing voters' preferences optimally. Briefly put, in multi-winne reconfiguration we need to decide whether there exists a transformation between size-k (not necessarily optimal) committees via sequence of intermediate size-k committees that are "almost" as good as the input committees
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

and close to one another (see Section 2 for the formal definition). Multi Multi-winner reconfiguration can model many real-world applications:
Streaming service providers, such as Prime Video and Netflix, change their catalog fre- quently (Prime-Video, 2024; Netflix, 2024) keep it engaging, while ensuring that popular or critically acclaimed content remains available. Here, customer satisfaction hinges on a balanced mix of fresh and familiar content. The multi-winner reconfiguration model can be used optimize this balance, ensuring the catalog evolves in a way that minimizes disruption to viewer experience. Likewise, for physical or online stores, product displays are crucial in attracting and retaining customers. However, generally shelf or display space is limited. The challenge is to introduce new products or promotions without overshadowing popular or staple items. The reconfiguration model can guide the arrangement of products using fixed capacity in way that maximizes visibility for new items while ensuring customer satisfaction.
An online gaming platform may need to shut down some old games to free up server space to support new games. However, abruptly removing a lot of games could alienate players, and thus the changes should be implemented incrementally in order to ensure player satisfaction throughout the whole exchange process.
In each of the above scenarios, the goal revolves around transitioning from one committee (i.e., a subset of products, movies, games, or routes) to another through minimal, incremental changes, ensuring a balance between introducing new elements and maintaining overall user satisfaction. In other words, we need to ensure that the consecutive committees in the transition are close to each other, both in their content and optimality wrt. the initial committee.
Our contributions. We propose model of multi-winner reconfiguration and study its computational complexity. We focus on four multi winter voting rules for approval preferences: Chamberlin- Courant (CC), Proportional Approval Voting (.AV).Apprae Voting (SAV). We find that while for the first two rules determining whether a reconfiguration path exists is PSPACE-complete, for the latter two reconfiguration path always exists. We further investigate the parameterized complexity for CC and PAV by looking at several canonical parameters: the number m of alternatives, the number of voters, the committee size k, the maximum number b of approved alternatives per voter, and the length E of a shortest reconfiguration path (if it exists). natural input parameters that are already studied in the original
Voting (AV), and Satisfaction Approval
The parameters n. m and multi-winner determination problem. The parameter b can be considered as a structural and distance to tractability parameter: For b- 1, all studied voting rules are equivalent to AV, by Theorem 1, the reconfiguration problem can be solved in polynomial time. Thus, it is natural to ask whether the problem is polynomial-tin time solvable for each constant b. Finally, by our reduction, the PSPACE- hardness arises because shortest reconfiguration path could be of unbounded length. Note that for bounded length the problem is in NP, see Proposition 2. In real-world applications, one may need to reconfigure committees timely, so it is natural to assume that l is small. We summarize our findings as follows (also see Table 1); For brief definition of the relevant parameterized complexity classes see Section 2:
The problem is exed-parameter tractable (FPT) wrt. m. Under CC it is also FPT wrt. n. While the problem is in XP wrt. n (resp. k). it remains NP-hard even for constant value + l. The XP result for is essentially tight since it remains W[2]-hard under CC (resp. W[i]-hard under PAV).
(ii)
(iii)
Combining n with any other single parameter always yields an FPT algorithm.
Due to space constraints, proofs of the results and additional materials marked with (x) are deferred to the appendix.
Related Work. Reconfiguration of puzzles and games has been of interest mathematicians
already since the 19th century (Johnson and Story, 1879). Since the early 2000s, reconfiguration has attracted increasing attention in the fields of computational geometry (Connelly et al., 2003; Aichholzer et al., 2015; Alamdari et al., 2017), graph theory (Ito et al., 2011; Bonsma, 2013), constraint satisfaction (Gopalan et al., 2006), and quantum complexity theory (Gharibian and Sikora, 2018). For graph problems, there are in general three types of reconfigurations between feasible solutions: token addition and removal (TAR; in each step one can either remove or add a vertex), token jumping (TJ; in each step one can replace a vertex with another vertex), and token sliding (TS; in each step one can replace vertex with another adjacent vertex). Our multi-winne reconfiguration problem generalizes the TJ model in the sense that allow replacement of more than one alternative
2

---

Table 1: (Parameterized) complexity results obtained in our paper. We omit the results for AV and SAV as reconfiguration under both rules polynomial-tmme solvable (see Theorem 1). Both PSPACE-hardness and W[I]-hardness hold even if each voter approves of at most two alternatvees, i.e., b = 2. Except for the NP hardnesddsss for constant b+ f. all hardness results hold even if (6e, 6.) = (1.0).
Parameter
CC
PAV
In general
PSPACE-C
[T2]
PSPACE-C
[T2]
m
FPT
[P3]
FPT
[P3]
n
FPT
[T4]
2, XP
[[[4]
k
W[2]-h, XP
[T5]. [P3]
W[1]-h, XP
[T2], [P3]
b +
NP-h
[P2]
NP-h
[P2]
k +
W[2]-h, XP
[T5]. [P3] W[I]-h, XP
[T2), [P3]
b + k +
W[1]-h
[T2]
W[1]-h
[T2]
+ b
FPT
[T4]
FPT
[P5]
n + k
FPT
[T4]
FPT
[P4]
T + &
FPT
[T4]
FPT
[T3]
in each step. For a general introduction to reconfiguration and how differs from various similar problems such local search (Ahuja al., 2002), reoptimization (Schieber et al., 2018), and increeental problems (Bredereck et al., 2020a), we refer to the surveys by van den Heuvel (2013) and Nishimura (2018). Ito et al. (2014), Mouawad al.. (2016), and Bodlaender et al. (2021) studied the parameterized complexity of various reconfiguration problems such as independent set and dominating set reconfiguration. They considered the length of the path well as bound on the size of the solutions as parameters. Notably, Bodlaender et al. claimed that dominating set reconfiguration via TJ is W[2]-hard wrt. the solution size and the reconfiguration path by wrongly referring to the TAR model. This is in general not correct as the two models are not equivalent. We correct this by providing a direct parameterized reduction from the dominating problem (see Proposition 6).
Reconfiguration in computational social choice as a topic has recently gained traction, with Igarashi et al. (2024) introducing the concept of reconfiguration to fair division. Ito et al. (2022) introduced a similar framework to reconfiguration to fair matchings.
Multi-winnes elections are topic of great interest in computational decision theory. For general introduction to multi-winner elections, see for example the work of Faliszewski et al. (2017). For further methods and topics on muiti-winnerr elections with approval preferences we refer to a recent book by Lackner and Skowron (2023). In this work, we will only consider approval preferences.
Reconfiguration is related to the model of "one problem, successive solutions" by Boehmer and Niedermeier (2021) where the goal is to select a sequence of desirable solutions. Bredereck et al. (2020c) introduced and studied this model for multi-winner election where each alternative in the committee must remain in office consecutive amount of times. Our reconfiguration problem is different from theirs two ways: First, we aim sequence of committees starting from an initial committee and ending at a target committee such that the intermediate committees are "close" to each other. Second, we do not require that an alternative appears for limited number of times.
2 Preliminaries
Given non-negative integer E N, let [t] denote the set (1....,()
!). Given two subsets X and Y, we use XAY to denote the symmetric difference between X and Y. ie.. XAY = (X (Y \ X).
Parameterized Complexity. Let II denote a decision problem and & a parameter. We say that II is fixed-parameter tractable (FPT) wrt. & if there exists an algorithm that decides every instance 7 of II in fkk ((1) time (we say the algorithm runs in FPT time), where f is computable function that solely depends on k. We say that 1I in XP wrt. k there exists an algorithm that decides every instance / of in (k))()) time, where / a computable function that solely depends on In the same way NP-hard problems are unlikely to be in P. problems which are W//J- or W/2/-hard wrt. k are unlikely to be FPT wrt. Similarly to showing NP-hardness, we show W[1]- and hr2)-hardness through FPT time reductions, where the new parameter must be function of the original one.

---

As examples, INDEPENDENT SET wrt. solution size and DOMINATING SET wrt. solution size are W[1]-hard and W[2]-hard, respectively. For more details we refer to Cygan et al. (2015).
Approval profiles and types. An approval preference profile (profile for short) is a triple P (C, V, Rt,, where C' denotes set of m alternatives, V a set of n voters with V = {VI,.... ), and R a collection R = (A1,.... ..,) of non-emply subsets of such that A, consists of all alternatives that voter 22 approves of, i E [n]. Unless stated otherwise, we use P to denote profile of the form (C, V, R). We say that two alternatives a and are of the same rype if they are approved by the same voters. We call any subset of alternatives a committee.
Score-based multi-winner voting rules. A score-based (multi-winner)) voling rule À (voting rule for short) takes as input a profile P and a number k, and assigns to each size-k commit- tee W score SC₂(P, W) The committees with maximum score winning committees. The score SCx (P, W) measures the satisfaction of the voters towards committee W. Note that we will omit the profile P and the subscript À if clear from the context. We say that a voting rule is neutral if the outcome does not depend on the names of the alternatives. This implies that if two alternatives are of the same type, then replacing one alternative with the other does not change the outcome. We consider four score-based voting rules, all of which are neutral:
The Chamberlin-Couren (CC) rule selects size-k committee that maximizes the number of voters who approve of at least one alternative in the committee. Formally, W is winning under CC if it maximizes (C) (v; V A; n W + 0}}.
The Proportional Approval Voting (PAV) rule uses h(x) = Σÿ= to denote the partial sum of the first x elements of the harmonic sequence. A size-k committee W is winning under PAV if it maximizes SCPAv En,ev h([A, n WI).
The Approval Voting (AV) (resp. Satisfaction Approval Voting (SAV)) rule selects a size-k com- mittee that maximizes the sum of approving voters (resp. the weighted sum of approving voters). Formally, the score of altemaatie a is defined as (C)v(a)
He, V | a A (resp. 1 Committee W is winning under AV (resp. SAV) if it maximizes SCSAv = En,ev st aeA; [A.] SCAv(W)= Enew SCAv(() (a) (resp. SC) = Enew (C)av
Reconfiguration of committees. Let P be profile and À a voting rule. Given number d, we say that two committees W and W are d-adjacent if |W \ W'| s and |W' \ W| I d. For two numbers & 2 1 and &g 0, we call sequence of committees Wo.... We a (6c, reoofoooooinr path (reconfiguration path for short) for (P,A) if for all i E [4] the following holds:
(C1) Wi-1l= |W5]:
(C2) W and W; are adjaceeen
(C3) The score difference of Wo and W; is bounded by 6g, i.e., SCx(W)) (Mo)) S
Remark 1. Note that the reconfiguration path requires closeness (C2-C3) between committees of the same size (CI). This is essential, as closeness captures the incremental yet necessary changes necessary in various applications, like evolving content in streaming services or adjusting product line-ups in retail stores, while fixing the committee size (C1) mirrors practical limitations like pre-set numbers of movie slots streaming catalogs or specific shelf capacities in retail stores.
By convention, the length of a reconfiguration path is defined as the number of committees on the path minus one.
Example 1. Let C' = [4] and V [U1, U2. U3, v1} with approval preferences A [1,2), = (2.3), A3 {3, 4} and A = [1,4). Let k = 2. Under both CC and PAV we have two size-2 committees with maximum score 4: 4: W = [1,3} and W' = {2, 4). For de = 6g = 1 and under CC, there is a (de, recoonofiiinn path between W and W" of length two, e.g. (W, (1,2), W"). The same path is also a (1, 2) reconfiguration path under PAV since SCrAv (1,2 3
Problem definition. Now, we define our reconfiguration problem.
A-MULTI-WII RECONFIGURATION (A-MR)
Input: A profile P, a committee size k, two numbers 8, 2 and 8 2 0, and two size-k committees W & W' with SC) - SCx(W') (WW)WWs)WW" < dg.
Question: Does there exist a sequence (Wo, (W....., Wt) of committees which is a (6., 0z)- reconfiguration path for (P, A) such that Wú = W and W. = W'?

---

((14))
(11.2)
(22.4) *
(1.33
((2.4)
({1.3)
(3344
(2.3)
Figure 1: Reconfiguration graphs for Example 2 with d 0 (Left), and with 6, under CC or ó, = 2 under
PAV (Right).
S 5, as otherwise either there is always a reconfiguration path (when W =W' or none (when 6, < 1 and W * W SC>(W)- SCx(W") committees to be optimal (i.e., winning). This choice allows for a more realistic representation of scenarios where optimal solutions are immediate feasible, thereby enhancing the practical relevance of our study.
Remark 2. Note that we require that the input satisfies d, 2 1, W + W and (W)
62). Moreover, we intentionally do not restrict the
For the restricted variant where the committees on the reconfiguration path must be optimal (i.e., W and W are winning and 8 0) and de 1. we write A-MRO. We will see that all intractability results except Proposition 2 already hold for the restricted case while all algorithmic results hold for the general case.
Reconfiguration graphs. Let = (P, 8c, 6z, W, W be instance of X-MR with P= (C (m], V, .R being a profile and a score- basee- voting rule. We construct a reconfiguration graph GR (VR, FR) for / as follows. Let /R = {uc- C' S C s.t. |C'| k and SCx (P, W) SCA C") < 6.} be the vertex set of GR such that each vertex corresponds whose score is at most & lower than the score of W. For each pair uw, uw, of vertices, we create an edge {uw, uw,] if the corresponding two committees W1 and W2 are de-adjacent.
size-k committee
Remark Note that | S (W) since only committees of size are relevant. We can compute VR in time (TT T(P,,) A), where T(P, A) denotes the time to compute the score of a committee under rule X. The number of edges of GR is bounded above by ( so the reconfiguration graph can be 2
constructed time O((T)² + (*r) T(P, ((). By construction, if 6- = O, and both W and W' are winning committee, then for each pair of connected vertices uw, and uw.,, there exists a onc-to-one correspondence between all (uw,, "w,) )-pahhs in GR and all (6e, 6. -reconffiiurationnn paths for W1 and W2.
Example 2. Let us consider the instance given in Example 1. If 6 = O, then the vertex set of the reconfiguration graph R is R {u(I,a): 4(2,4) 43 since {1.3} and {2, 4} are the only two winning committess. Because
if de = there no path between uw and uw and hence no reconfiguration from W to W exists. See the LHS of Figure for an illustration.
4]|
6 (under CC) or 8 1/2 (under PAV), then VR contains vertices for all size-2 committees C. There are four possible length-2 paths between ((13)) and (2.4), for example (u(113), ((122), "(2.4)). See the RHS of Figure I for illustration. Note that the length of shortest path between any two [WWW"
committees W, W' is at least
any edge on the reconfiguration will remove (resp. add) at
26.
most &e alternatives from W
W (resp. W W).
3 Complexity Results
In this section, we consider the computational and parameterized complexity of X-MR.
Computational Complexity. It is straightforward that A-MR is in PSPACE due to an observation by Ito et al. (2011).
Proposition 1. For each X of the four considered voting rule, X-MR is in PSPACE.
Proof. It suffices to show that X-MR is contained in NPSPACE since PSPACE = NPSPACE (Savitch, 1970). Moreover, as observed by Ito et al. (2011), to show that the reconfiguration version of problem is in NPSPACE, one only needs to show that the underlying problem is in NP. In our case, need to show that the following two problems can be verified in polynomial time: (1) Does
5

---

given committee satisfy given score-bound? (2) Are two given committees ò--adjacent? For the sake of completeness, we provide detailed proof for X-MR. We first define decision variant of the multi-winner determination problem. In S.MULTI-WINNER SCORE, we are given profile P. a committee size k, and a number 8, and ask whether there exists size-k committee W such that (C) 2 8.
Note that since the score of a committee under each considered rule À can be computed in polynomial time, X-MULTI-WINNG WINNER SCORE is in NP. Since NP C PSPACE, given an instance (P, W. W 6., 6,) of X-MR we can enumerate all size-k committees U with SCx(P, W) SCx(P, U) S 6, in PSPACE. Then, we can iteratively non denettemmnnistiallly choose a size-k committee W that is 6 adjacent to the current committee and has SCx (P, W) SCx(P, W < 6g. The problem is thus in NPSPACE. O
The following result implies that AV- and SAV-MR are easy. This is because both rules are based on additive scoring functions, so we can greedily exchange alternatives from the symmetric difference between the initial and target committees.
Theorem 1. Every instance of AV-MR (resp. SAV-MR) admits a reconfiguration path. Moreover, a shortest one can be computed in polynomial time and has length
[W.W
WAW"
6.
26
Proof. Let A E IAV,SAV and = (P, 5g, Sc, X, W, W*) denote an instance of A-MR. As already discussed, we will greedily exchange alternatives from W WWW. The correctness is based on the following claims:
Claim 1.1. Let W1 and W2 be two size-k committees, and arg mag.axxwwww scx(c) and b = arg min SCx(e). Then, scx( J (a}) \ {b)) 2 (w.
Proof. We distinguish between two cases. Case (1) (ax(a) 2 (C)( Case (2) SCx(a) (a) < (C).
For Case (1), due to the additivity of the voting rule the statement follows: SCy (W1 U {a} \ {b})
SCx (W1) + SCx(a) - SCx(b) 2 (C1) 2 (C))
For Case (2), by the choice of a and b, we infer that SCx(c) < (d) for all c C W2 \ W1 and all d W, \ W2. We now enumerate the elements in W₂ Wi in the order a1.... .....-.-. G4 so that 0; a;+1 holds for all E [t - 1). Similarly, we enumerate W1 \ W2 in the order bi...., by so that b; 2 b;+1 holds for all
[t - 1]. Note that in these orderings we have a a₁ and b b. Using this enumeration we can now show the statement:
SCx(W1 U {a} \ {b}) = scx (W1) + (C) sC)
SCx n W2) +
kej SCx (bx) + SC)(a) SCx(b)
SCx(W1 n W2)
+
ij SCx (b:) (C)(a)
SCx(W1 n W2)
ij SC2 (0.) + (a)
SCx n W2) Liely (C,) SC, (W2)
(of Claim 1.1)
By Claim I.I, we can iteratively replace the lowest scoring alternative in W \ W' with the highest scoring alternative in W" \ W. while ensuring the overall score is at least min (W), SCx SCx"))) Since SCx SCx(W) < SCx (W") + ô, per definition, we obtain valid reconfiguration path in polynomial time. For 5. 1, such a path has a shortest possible length IW \ W For 5. > 1, we can take the same path, but skip & 1 many committees in each step. This leads to path of length WW''' Note that a shorter path cannot exist.
&
Example 3. We illustrate the greedy approach behind the proof of Theorem I on the following example under AV: Let C = [6] and V = {U1..... U11} with approval preferences A =... As- 2,, 3, 4), Ag = A7 Ag = (3, 4, 6), Ag A = 52, and A
A1i (1, 63. We have the following scores for each of the alternatives: SC(1) 11- = 9, SC(() = SC(3) = SC((4= 8, 6, 5, W (1,3, 4}, and W' = (2, (2,5,63, 6). Note that W is a winning committee with Sc(W)= = 25 and Sc(W") = 20.
SC(5) 6 and SC(6)= = 7. Let k = 3, d
We now proceed with generating the reconffiguration path. We start with Wa = W. Alternative 6 is the highest scoring ulternative in W" Wo. while alternative (or 3) the lowest scoring alternative in Wo W'. Therefore, we generate W1 = {1,3,6) 6) by exchanging 4 with 6. Using the same procedure, we compute W2 = (1,2,6), 6), and finally W, = (2.5.6) W" It is struightforward to check that (Wo- = W, W1, W2, W3- = W') is (1, recoonnnacconnnnititoonn path.

---

In contrast to AV and SAV, the next theorem shows that CC- and PAV-MR are computationally difficult. The idea to reduce from the PSPpCE-complete and W[1]-hard problem INDEPENDENT VIA TOKEN JUMPING (ISR-TJ) (Ito et al., 2014), by adapting from the reduction of Aziz et al. (2015) for CC and PAV.
SET RECONFIGUR
Theorem (+). For all X {CC, PAV), A-MRO (and hence X-MR) are PSPACE-comples More- over, they are PSPACE-hard and W| W-I]-hard wrt. k + l, even if (6c, 8,, b) = (1, 1,0.2 2).
We observe that the reduction of Ito et al. (2011) can be used to show that a generalized variant of ISR-TJ where in each step more than one vertex can be exchanged is NP-hard for constant path length. Hence, we obtain the following hardness for our problem as well.
Proposition (+). For all {CC, PAV), X-MR remains NP-hard even if = l = 2, and for constant E, it is in NP.
Parameterized Complexity. Next, we focus on the parameterized complexity for CC and PAV wrt. a few selected parameters. The most intuitive ones are the number m of alternatives, the number n of voters, and the committee size k.
Proposition 3. For all score-based multi-winner voting rules À such that the score of a committee can be computed in polynomial time, X-MR is solvable in m (n + m))(1) time, and hence FPT wrt. m and in XP wrt. k. Furthermore a shortest path can be computed in the same time.
Proof. Let 1 = (P,k, 8c, 8z, W, W') be an instance of X-MR. We operate on the reconfiguration graph GR of I. As noted in Remark 3, the number of edges in GR is bounded above by (T)) S
m2k 2m and hence GR can be constructed in (w² 2
(n + m) time. Since determining shortest path between two vertices can be done in time linear in the number of edges of the graph, we
can determine a shortest-length (uw, )-att in GR in m2 (n + (m)+ m))(1) time, which is FPT wrt.
m and in XP wrt. k, as desired.
D
Yang and Wang (2023) show that PAV-MULTI- SOY-MULT--WINERR SCORE can be solved in FPT time wrt. via a specific integer linear programming (ILP) formulation called Integer Programming With Simple Piecewise Linear Transformation (IPWSPLT) that can encode convex constraints." It not clear how to extend their approach to the reconfiguration variant because the length E of a shortest reconfiguration path may be unbounded. However, we can extend their approach to obtain an FPT result wrt. n + f.
Theorem (*). PAV-MR is FPT wrt. n +
Proof sketch. As said, we extend the IPWSPLT by Yang and Wang (2023). Briefly put, IPWSPLT is an ILP extension that allows for piecewise concave or convex functions to be used (Bredereck er al., 2020b). We construct many copies of the IPWSPLT formulation and combine them with additional constraints to model the exchanges. Similarly to their approach, we utilize the fact that alternatives of the same type are interchangeable when considering the score of committee. We then split the alternatives of each type into 4 groups: Alternatives that are in W n WW, W \ W', W \ W. and CX (W U W'). We add variables that keep track of the number alternatives of each group from each type. By keeping track of these numbers along the steps of the reconfiguration path ensure that the symmetric difference between two intermediate committees is at most 2 &6 and that the final committee in the reconfiguration path is the target committee. We ensure that the total number of variables and constraints are in 0(2"... -). This yields an FPT algorithm wrt. n + since an IPWSPLT instance can be solved in time (n 2.56-o((()) ([Z] + Pmax)) (Bredereck et al., 2020b), where á is the number of integer variables, [Z] is the size of the encoding of the instance, and Pmax is the maximum number of pieces of a piecewise-linee the number ň of variables and the size of the encoding |7| are in 0(2 l), the FPT result follows. The precise formulation and the proof are deferred to Appendix B.3.
convex/concave function. Since in our IPWSPLT formulation
The next results are based on either brute-force searching all possible reconfiguration paths or bounding the size of the reconfiguration graph.
'ILP with convex constraints was shown to be FPT wrt. before the introduction of IPWSPLT by Grötschel al. (1988), but IPWSPLT to keep the terminology consistent with Yang and Wang.
7

---

B
W1
B
A
A
W
W
B
737
(B W) Bi
X
W
X
W
W
Figure 2: Illustration for the proof of Lemma 1. Left: Case 1; Right: Case 2.
Proposition (+). For all score-based voting rules À such that the score of a committee can be computed in polynomial time, the following holds:
(i) X-MR is solvable in m2 (n + m) m)))1)))))))))))))))) time, and hence in XP wrt. E for constant de.
(ii) If X is additionally neutral, then X-MR is solvable in k2k (2 + 2)2k (n + m))(1) time and (k + 1)4 (n + m) m))(1) time and shortest reconfiguration path can be found in the same time. Thus, it is FPT wrt. n + k and in XP wrt. n.
For CC, the following lemma shows that for a large enough committee size k there is always reconfiguration path: The score of each committee is determined by at most relevant alternatives since each voter contributes a score of at most one. Due this, we can find a shortest path the symmetric difference between W and W is very large (Case (i)). by only exchanging the alternatives in the symmetric difference. Otherwise (Case (i)), we can still find a path in polynomial time by also exchanging alternatives that are shared by both W and W
Lemma 1. For every instance of CC-MR with k 2 2n there exists a reconfiguration path between W and W'. Moreover,
(i) If ( \ W 2 2n, then we can find a shortest one in polynomial time.
(ii) W W < 2n, then can find one with length at most
2n in polynomial time.
8g
Proof. Let 1 = (e, W") denote an instance of CC-MR. We first consider the case when d 1 and show how to adapt the proof for & 2 at the end. First, observe that we can always find a size-n committee of W (resp. W') with score at least SC(W) (resp. SC(W')). Hence, the idea is to find size-n committee S W (resp. S W') such that sc(A) Sc(W) (resp. SC(B) sc(W')) and perform exchanges to obtain a committee that contains A U B, and then switch out alternatives that are not contained in W'. Note that A and B can be found polynomial time by iteratively deleting "redundant" alternatives from W and W'. respectively. To show the statement, we distinguish between two cases. Figure illustrates the constructions used in the proofs.
Case 1: W w'| 2 2n or WW \ (W' U A) 2 JB \ W/. Note that the first condition implies the second condition since |A| = n [B). To implement the exchange idea, let X S W \ (W' U A) be an arbitrary committee of [B \ W| alternatives. We divide the exchanges into two parts. In the first part, we step-by-ster exchange all alternatives from X with all alternatives from B W. It is straightforward to verify that every committee obtained until now has score at least Sc(W) because always contains A, and the last committee obtained has score at least Sc(W') since contains B. In the second part, we step-by-stey step exchange the remaining alternatives from W \ (W' U UX) with the remaining alternatives from W" \ (W B). is straightforward to verify that every committee obtained in the second part has score at least Sc(W") 2 Sc(W)- - 8, since it contains B.The exchange sequence yields a reconfiguration path of shortest length [[ A/ If 6, 2 2, then we take every de-th element the path, including W and W', All these committees have score least SC(W) d by construction and the path is of the shortest possible length [| (WWWW (/2///(2a)) (2))
Case 2: W \ W' < 2n and W (W' U A) < BB \ W|. We proceed in three parts. For the sake of brevity, let W; = W (W'LA) and let B, S B\W denote committee of [W alternatives arbitrarily chosen from B W. First, we step-by-step exchange the alternatives in Wi with the alternatives in B Afterwards, we select a committee X C (Wnn W') \ (AUB) of [ W - |W]] arbitrary alternatives, and step-by-step exchange the alternatives in X with the remaining alternatives in (B W) B, Note
that this possible since (W n nW) (A B) Z W n W' - A| + |4 W - [B] + \ W
Wi-116 W W'I
A||
W'I
- B B W| - WW + B W the last inequality holds since
8

---

Wi = W (W UA) W - W and [W] 2 2n 2 |A|+ + [B]. So far, we perform B WWW S a exchanges, where all intermediate committees contain and the final committee additionally contains B. Thus, they all have score at least SC(W). The only alternatives from W W" that remain in the most recently obtained committee are those alternatives in \ W Thus, in the third part, we step-by-step exchange all alternatives in A \ W' with the alternatives in W that are not yet in the most recent committee; they are precisely in X U (W") (W U BB). Since all committees obtained in the third part contain B, each of them has score SC(W") 2 SC(W)- 6g. The number of exchanges in the last part is |A| \ W & n, and overall we have performed at most 2n exchanges. Similarly to the first case, if 6e 2 2, then the number of exchanges reduces to [2n/ dcl.
Combining Lemma 1 with Proposition 4(ii) yields FPT result (wrt. n) for CC. Theorem 4 (x). CC-MR is FPT wrt. and shortest reconfiguration path can be found in FPT time wrt. n.
Proof. We distinguish between two cases. If < 2n, then we use Proposition 4(ii) to solve CC-MR and find shortest path in FPT-time wrt. n. Otherwise, by Lemma 1, we can in polynomial time find a reconfiguration path that either has minimum length (when [W \ W'| 2 2n) or has length at most [2a (when WW WII 2n). This proves the first part of the statement.
To show the second part of the statement we only need to consider the case when k 2 2n and IW \ (W' < 2n as the other cases are already covered by the above reasoning and by Lemma 1(). In the case of k 2 2n and [W\ \ WII < 2m, by Lemma ((i),, there is always reconfiguration path of length at most [ 2 1. This implies that a shortest path can exchange at most 4n many altermatives. Since CC is neutral, any two alternatives of the same type are "interchangcable" on the path. Hence, only need to keep track of at most 4n alternatives for each type of alternative. Note that all alternatives in the symmetric difference W W'W' must be among these tracked alternatives. There in total most 4n 2n many alternatives that are relevant for the exchanges. Thus, we can a simple branching algorithm to search for a shortest reconfiguration path by branching over all possibilities of selecting 2 6g alternatives from at most 4n2" relevant ones to exchange in each step.
remains to analyze the running time. In the case where k < 2n, the time needed to compute a shortest path is still 4n (2" + +2)4n. (n + m)(() per Proposition 4(i).. For k 2 22 and [W W'| 2 2n shortest path can be found in polynomial time per Lemma 1()).
We now consider the case of k 2 2n and W WI| < 2n. Before looking the running time, we describe the branching algorithm more precisely. We note that we can assume 6g < 2n, as otherwise there is a path of length one that is obviously a shortest path. Recall that due to CC being neutral, it suffices to keep track of 4n alternatives of each type since by Lemma I (ii) the maximum number of alternatives that are exchanged on a shortest path is 4n. Let X denote a set consisting of min (4n. /Cl) alternatives of each type t E T, including all alternatives from W WAW' This implies that X S 4n2". As we know that the reconfiguration path has length at most E [2n/ 8c we can solve this problem by branching over all possible exchanges using alternatives in X with depth l. For each step i [é], we branch over all pairs of two sets X! X? C X with XX!| I 6, and |X?| < & that shall correspond to the set of alternatives in W,- W; and W; W,-1, respectively. Then, using these exchanges, we can compute all committees on each branch and check whether they yield a desired reconfiguration path. By checking all branches we can then find shortest path.
Finally, we compute the running time of the branching algorithm. A single step has |X| |X| [X]26 many branches and there are at most 22 steps. That means the branching algorithm has
running time of |X 2 < 2 1 < [x de < (4n 28
By observing that there are not too many different alternatives (wit. n + b), we obtain the following FPT result.
Proposition 5 (x). For all neutral and score-based mulli-winner voling rules À such that the score of a committee can be computed in polynomial time, X-MR is solvable in 22b (n + o(1 time, and hence FPT wrt. n + b.
Finally, we prove that the committee size combined with the path length l is unlikely to yield FPT-algorithms by showing W[2]-hardness, We reduce from the problem of DOMINATING SET
9

---

RECONFIGURATION VIA TOKEN JUMPING (DSR-TJ) In DSR-TJ, TJ, we are given a graph G = (V. E), two non-negative integers h and é, and two size-h dominating sets V, and V; of G. and we ask whether there exists a sequence Vo, ..... Vi of size-h dominating set such that Vo = v. V = V, and [VAV++1 < 2 for all 0 < i < - 1. Recall that a dominating set of a graph is subset V of vertices whose neighborhood covers the whole vertex set of the graph, i.e., each vertex not from V is adjacent to at least one vertex in V'. Bodlaender et al. (2021) claimed that Mouawad et al. (2016) showed that DSR-TT TJ is W[2]-hard wrt. (h. f), where h denotes the size of any dominating set (DS for short) on the path and é the length of shortest DS reconfiguration path (if exists). The reduction given by Mouawad et al., however, only works for the TAR but not the TJ variant. The reason is that in their created instance, the size h of the initial DS is smaller than h, so the size of any intermediate dominating set could be larger than h' while this is not possible for the TJ variant. Below, we modify their reduction and show hardness for the TJ variant.
Proposition 6 (+). DSR-TJ is Wh2r-hard wrt. h +
We obtain the same hardness for the CC rule by adapting the reduction by Betzler et al. (2013). Theorem 5. CC-MR" (and hence CC-MR) are W[2]-hard wrt. k k+
Proof. It suffices show W[2]-hardness for CC-MR To achieve this, we provide a parameterized reduction from the W[2]-hard DSR-TJ problem (see Proposition 6) to CC-MR", i.e., CC-MR where 5, 0 and 6e- 1.
Let (G,h, ê, V.. Vi) be an instance of DSR-TJ, where G is an undirected graph, V, and V2 are the initial and target dominating sets, respectively, h |Val |Vi], and é denotes the length bound on the reconfiguration path (if it exists).
We define k = h and create preference profile as follows. For each vertex v; E V(G), create
one vertex-alternative Ca. and one vertex-voter that approves of e; and the alternatives corresponding to the neighbors of uz in G. Formally, the approval set of voter u; is A, {c:} U {ey {or Uj} E E(G)).
Let P = (C, V. R) denote the created profile. The total number of voters in this instance is [V(G)) To complete the construction, let the initial and target committees be W {c; vi E V.) and W' = {c i E Vi). Note that the score of W (resp. W') is V(G) since Vg (resp. Vi) is a dominating set. It is straightforward to see that every size-h dominating set of G' corresponds to size- k committee with score at least [. The correctness of the construction follows immediately. Li
4 Conclusion
We introduced a framework for reconfiguring committees in multi- winner elections for four prominent committee election rules: CC, PAV, AV, and SAV, and systematically studied the (parameterized) complexity of the problem. We left open whether our reconfiguration problem under PAV is FPT wrt. the number n of voters.
Our framework can be directly applied to other score-based rules, such as the Monroe rule (Monroe, 1995), even for linear preferences. For non-score-base rules, we may adapt by either restricting the reconfiguration path winning committees or introducing measure that captures closeness to optimality.
Our preliminary experimental investigations (see Appendix C) indicate that for most randomly gener- ated committees, reconfiguration path not only exists but can also be efficiently determined using a straightforward heuristic. This finding opens promising avenue for future research: determining the specific structures within the data that ensure the existence of a reconfiguration path, and whether it is possible to develop FPT algorithms leveraging these structures.
The concept of reconfiguration extends beyond the the fair division setting explored by Igarashi et al. (2024). Many other social choice frameworks remain unexplored in this context, such as stable matching (Gale and Shapley, 1962) or coalition formation (Drèze and Greenberg, 1980). Investigating these could provide useful insights into the algorithmic principles of varied decision -mainn processes.
election settings explored here or
10

---

Acknowledgments
The authors are supported by the Vienna Science and Technology Fund (WWTF) [10.47379/ VRG18012]. We would like to thank the reviewers for their helpful comments. We acknowl- edge the support of the NeurlPS 2024 Financial Assistance grant, which helped the authors attend the conference.
References
Ravindra K. Ahuja, Özlem Ergun, James B. Orlin, and Abraham P. Punnen. A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123(1-3):75-102, 2002.
Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz. Flip distance between triangulations of simple polygon np-complete. Discrete and Computational Geometry. 54(2):368-385 -398, 2015.
Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz, Timothy M. Chan, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Penny Haxell, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, and Bryan T. Wilkinson. How morph planar graph drawings. SIAM Journal on Computing, 46(2):824-852, 2017.
Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. Computational aspects of multi-winner approval voting. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS 2015), pages 107-115, 2015.
Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 47:475-519, 2013.
Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis. Parameterized complexities of dominating and independent set reconfiguration. In Proceedings of the 16th International Symposium on Parameterized and Exact Computation, (IPEC 2021), pages 9:1-9:16, 2021.
Niclas Boehmer and Rolf Niedermeier. Broadening the research agenda for computational social choice: Multiple preference profiles and multiple solutions. In Proceedingy of the 20th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS 2021), pages 1-5, 2021.
Paul Bonsma. The complexity of rerouting shortest paths. Theoretical Computer Science, 510:1-12, 2013.
Robert Bredereck, Jiehua Chen, Dušan Knop, Junjie Luo, and Rolf Niedermeier. Adapting stable matchings evolving preferences. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pages 1830-1837, 2020.
Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon. Mixed
integer programming with convex/concave constraints: Fixed-parameter tractability and applica- tions to multicovering and voting. Theoretical Computer Science, 814:86-105, 2020.
Robert Bredereck, Andrzej Kaczmarczyk, and Rolf Niedermeier. Electing successive committees: Complexity and algorithms. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pages 1846-1853, 2020.
Robert Connelly, Erik D. Demaine, and Günter Rote. Blowing up polygonal linkages. Discrete & Computational Geometry, 30(2):205-239) 2003.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipezuk, Michal Pilipezuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013.
J. H. Drèze and Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4):987- 1003, 1980.
Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. Trends in computational social choice, 74:27-47, 2017.
David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 12065):386-391, 1962.

---

Sevag Gharibian and Jamie Sikora. Ground state connectivity of local hamiltonians. ACM Transaction on Computation Theory, 10 2018.
Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, and Christos H. Papadimitriou. The connectivity of boolean satisfiability: Computational and structural dichotomies. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), pages 346-357, 2006.
Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988.
Ayumi Igarashi, Naoyuki Kamiyama, Warut Suksompong, and Sheung Man Yuen. Reachability of fair allocations via sequential exchanges. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024). pages 9773-9780, 2024.
Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412((1-14)): 1054-11550 2011.
Takehiro Ito, Marcin Kaminski, Hirotaka Ono, Akira Suzuki, Ryuhei Uchara, and Katsuhisa Ya- manaka. On the parameterized complexity for token jumping on graphs. In 11th International Conference Theory and Applications of Models of Computation (TAMC 2022), pages 341-351, 2014.
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Reforming an envy-free matching. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), pages 5084-5091, 2022.
William W. Johnson and William E. Story. Notes on the "15" puzzle. American Journal of Mathe- matics, 2(4):397-404, 1879.
Chengquan Ju, Shuhan Yao, and Peng Wang. Resilient post-disaster system reconfiguration for multiple energy service restoration. In Proceedings of the 1st IEEE Conference Energy Internet and Energy System Integration (E12 2017), pages 1-6, 2017.
Martin Lackner and Piotr Skowron. Multi- Winner Voting with Approval Preferences-Arriffiaal Intelligence, Multiagent Systems, and Cognitive Roboties. Springer Briefs in Intelligent Systems. Springer, 2023.
Martin Lackner, Peter Regner, and Benjamin Krenn. abcvoting: A Python package for approval-based voting rules. Journal of Open Source Software, 8(81):4880, 2023.
Burt Monroe. Fully proportional representationn. American Political Science Review, 89(4):925-940 1995.
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki. On the parameterized complexity of reconfiguration problems. Algorithmmica, 78(1):274-297, may 2016.
Netflix. Netflix prize. https: /www. kaggle e com/ http//datttttt/eelliii.// innc
netflix-pris data, 2006. Accessed 2023-7-7, Version 2.
Netflix. Don't Miss Your Chance to Watch These Movies and Shows Leaving in December. https: / www. netflix wttpttwum////ecctttc//ctttttwttt bawddd///arrices//htttett Leettt--eeeiin 2024. [Accessed 17-01-2024].
Naomi Nishimura.
Prime-Vides Introduction to reconfiguration. Algorithms, (1))))222208)
Prime video: leaving soon. ht http::/wwwwwww//cc.o.o.o uk/ SeppriingPrringg Next 30- -a00-ays--- Piays-Viinn Videos/s http:://s22hhnn11999777766338332 soyss_to_watchee 327448344448888 wtw.:///aaacca14444400000000
2024. [Accessed 17-01-2024).
Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities.
Journal of Computer System Science, 4(2):177-19,, 1970.
Baruch Schieber, Hadas Shachnai, Gal Tamir, and Tami Tamir. A theory and algorithms for combina- torial reoptimization. Algorithmica, 80(2):576-60) 2018.
Stanislaw Szufa, Piotr Faliszewski, Eukasz Janeczko, Martin Lackner, Arkadii Slinko, Krzysztof Sornat, and Nimrod Talmon. How to sample approval elections? Proceedings of the 31 International Joint Conference Artificial Intelligence (IJCAI 2022), pages 496-502, 2022.
12

---

Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics 2013, volume 409 of London Mathematical Society Lecture Note Series, pages 127-160. Cambridge University Press, 2013.
Yongjie Yang and Jianxin Wang. Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability. Autonomous Agents and Mulli-Agent Systems, 37(2):28, 2023.
13

---

Supplementary Material for the Paper "Multi-Winner Reconfiguration"
A Additional Material for Section 2
Parameters. In this work we additionally look at the problems through the lens of parameterized complexity using the following parameters: the number of alternatives, the number of voters, the committee size k, the maximum number b of approved alternatives per voter and the length & of a shortest reconfiguration path (if it exists).
B Additional Material for Section
Independent Set Reconfiguration Definition
Ito et al. (2014) show that the following reconfiguration is W[I]-hard wrt. the number of tokens (i.e., the size of any independent set the path).
INDEPENDENT SET RECONFIGURATION VIA TOKEN JUmPING (ISR-TJ)
Input: A graph G. two non-negative integers h and f, and two independent sets L. Le of size h. Question: Does there exist a sequence 1o..... 1 of size-h independent sets of such that
lo 1, 1 4t, and 1,4++1 2 holds for all 0 s i < - 1?
An independent set graph is subset of vertices such that no two of them are adjacent.
B.1 Proof of Theorem 2
Theorem (+). For all X {CC, PAV], X-MRO (and hence X-MR) are PSPACE-complets More- over, they are PSPACE-hard and W-1ard wrt. k + l, even if (ōe, 8,, b) = 01,
Proof. Since PSPACE--membership follows from Proposition 1, we only need to focus on the hardness hardness by reducing from ISR-T TJ (see above for
results. We show W[L]-hardness and the definition). Ito et al. (2014) show that ISR- TJ is both PSPACE-compler and W[I]-hard wrt. to h. We observe that the reduction is simultancously a polynomial and [[]]-hardsess reduction wrt. + ? because a shortest reconfiguration path has length 2h in their construction. Hence, we can provide polynomial-tine
reduction for CC-MR" and PAV-MR such that the committee size and the path length are h and i, respectivelyy then we obtain W[L]-hardness in the statement.
Let (G, h, Is, It) be an instance of ISR-TJ. We create an instance of CC-MR and PAV-MR with committee size k h. For each vertex e; (G),, let deg(u;) denote the degree of vertex U; in G. Further let deg((G (G) = max,, (V(G) deg(v; U;) denote the maximum degree of graph G.
For each vertex 1 E (G), we create vertex- alteraaveeeeeeeive c; and (deg(G) df pleg(G) (dgg(G)-dg(en) ddeg(e)) that only approve c;-
deg(e:)) (ee))
many private
dummy voters {d] .....
For each edge {v,, 0z} E(G), we create one edge-voter "(..j) that approves only c and cj.
Let ' denote the created profile with C {a v2 E V(G)) and V {dj e E V(G), Ideg(( G)) deg(v;)) U {urss {u,, v, E E(G)). The total number of voters created is V deg G) (V To complete the construction, let the initial and target committees be W {c; Vs E [.} and W' = {c, v, E lt). the size of the independent set h k, and the length reconfiguration path l = 2h 2k.
For the sake of brevity, define a bijection f: 2V()) - 2c with S(V") = fcr | m E V' between the vertex subsets and the committees. We present one-to-one correspondence between the size-h independent sets in G' and size-h committees with score of at least deg G)- in the created PAV-MR and CC-MR"-instances innstacce.
Claim 5.1. V a size-h independent set if and only if J(V') a size-h committee of score least deg(G) under CC as well as PAV.
14

---

Proof. The "only if"" part is straightforward: For each size-h independent set V we have that the alternatives in fV*) are approved by deg(G) k voters. Among them deg(G) (G) -> deg(e;) voters are private voters and EV,,/(V)) dog(v:) voters are the edge-voters of the edges incident to V' Each of these deg(G)- - edge-voters approves exactly one alternative in S(V") since V is an independent set. Thus SCPAv (W) = SCcc(W) = deg(G)
For the "if" part, let W" denote a size-h committee with score 2 deg(G)- k. We claim that f (w") a size-h independent set. Clearly [W") h, so we only need to show that no edge incident to more than one vertex in (W Let E (( E E(G): Ke, 2j} n ff-((""")
}} and Eg = ((v, 1y) E ([G):Ku; ) f (W")) = 2} denote the set of edges that are incident to exactly one vertex in f fWW")) and the set of edges that are incident to two vertices in f (W"). respectively. Then, by the handshaking lemma, we have that
(
E + 2 = E deg(u;).
(1)
GEW!
For CC, we have that deg(G) k = SCcc(W") E (deg(G) - deg(v:) (s)) F + [22). which implies that |Ei| + [B = Ene deg(v) since k = h. Together with (1), we obtain that
[Ea meaning that edge is incident more than vertex in f f""( ); desired.
-deg() + we infer that [E + (1 + 1/2)|Ez| = Ew. deg(v). Similarly to the previous case, by (1), we obtain that |A = 0, meaning that no edge is incident to more than one vertex in f-")"",, as desired.
As for PAV, since (eg(G))-k SCrAv E
(of Claim 5.1)
By Claim 5.1, it is straightforward to verify that sequence (Ig...., 4) of vertex subsets is size-h independent set reconfiguration path if and only if (W = f(.)).... W = f(4)) is a (1, reconfiguration for CC-MR and PA. This concludes the proof for the PSPACE-hardnes. since the reduction is a polynomial time reduction.
Note that in our construction each voter approved of at most alternatives. This means the PSPACE- hardness remains even the ballot size is bounded by 2.
It remains to show the W[I -harddesss wrt. the committee size k and the path length As the committee size k is equal the size h of the independent set, each committee on the reconfiguration path directly corresponds to an independent set on the reconfiguration path of the independent sets of size h and the shortest path of length at most 2h (Ito et al., 2014), it follows that both PAV-MR and CC-MR" are W[r]-hard wrt. the path length l and the committee size k. This concludes the proof.
B.2 Proof of Proposition 2
Proposition 2 (+). For all E (CC, X-MR remains NP-hard even if = = 2, and for constant E, is in NP.
Proof. As already mentioned, the reduction of Ito et al. (2011) can be used to show NP-hardness for the case when may allow for more than token to be moved at once. In other words, it NP-hard to decide whether one can reconfigure from one independent set I, of size to another independent set I, of / via an intermediate step. Hence, by using the same reduction as for Theorem 2, we obtain the result from the statement.
As for constant path length f, we can guess sequence of constantly many committees which in total has polynomial size and check in polynomial time whether it valid reconfiguration path. This proves containment in NP.
B.3 Continuation of the proof of Theorem
Theorem (*). PAV-MR is FPT wrt. n + f.
We first introduce some notations and concepts that are useful for the IPWSPIT formulation. For each type t of alternative, let C, denote the set consisting of all alternatives with type Let T denote
15

---

the set of types of alternatives that exist in a given preference profile P. Further, let A(t) denote the set of voters that approve of alternatives of type t. We say that two committees C₁ and C2 are in the same equivalence class (class for short) if for each type i, the number of alternatives with type in C1 the same as that in Cz. We partition the set C, of alternatives of type 1 into four subsets as follows: X C n (W) W X? C C nW", X² C, n (W") W), and X; = CC UW))) In other words, X X X and X denote the set consisting of all alternatives of type that are from the set W W the intersection W n W', the other set W \ W, and not in W U W respectively.
We now describe the variables and constraints used in the IPWSPLT. We use IPWSPLT rather than a regular ILP because it is not clear how to compute the scores under PAV with just ILP.
Variables. The following variables will be used:
An integer variable æ for each / T and each j E (.....,e). .). This variable stores the number of alternatives in X in the j-th committee of the reconfiguration graph.
An integer variable =?., for each & T and each j {0, .......,. ...,,..... {). This variable stores the number of alternatives in X? in the j-th committee of the reconfiguration graph.
An integer variable oi2 for each / E T and each j E {0...... .0,....,3 .). This variable stores the number of alternatives in X3 in the j-th committee of the reconfiguration graph.
An integer variable vi, for each / E T and each j E {o...., This variable stores the number of alternatives in X in the j-th committee of the reconfiguration graph.
x.2' An integer variable ((t.j-1),(0 for each 2, =' E [4]. E [f] and 1, E T. This variable stores the number of alternatives that were part of the group represented by -i-ー that were replaced by
alternatives in the group u in the step from W to W
An integer variable žejj for each voter E V and each step j E (o....,e) how many alternatives voter approves of in committee W..
.]. This variable stores
We use the same piecewise linear concave function f: R2o Rxo Yang and Wang. We set f() 0 and for every positive integer x we set f(z) Σ5 ii=1 I. Then for each real positive non-integer a we choose y E N such that = [æ] and set f(x) = f() + (x v) (f(++) f())).
Constraints. We add the following constraints:
(1) For each z [4], we fix æī,0 and o to be the correct values for W and W i.c., 21,0 [X]]] 2i,0 = 2²,, = X =²,00 = zτ.0 = _1, = =t, = 0, and iie = |
(2) For each j E [4]. we add constraint E (1) S d.. These constraints ensure that
E'ET
the symmetric difference between concurrent committees in the reconfiguration path observes the bound.
(3) For each (j, 2) E () x T x [4), we add constraint oi, S ensure that the class of committee used in an intermediary result exists, i.e., we do not use more alternatives of type in committee than possible.
|x+1- These constraints
(4) For each t, 2) E [C] x T x [4]. we add a constraint - 2 EET V Theses
a' 2'E[4]
constraints are added so that it is not possible to switch out alternatives that are not in the committee.
(5) For each (j.t,2) E [[]x x [4], we add a constraint æं,j = z Exee,, Vir
EveRA 2,2" is as described after the exchanges.
(I These constraints ensure that the number of alternatives in each group
(6) For each j E {O..... f). we add constraint EIET, vig = k. This constraint ensures that each committees of the reconfiguration path has size k. (7) For each v e V and i E [C] we add a constraint Ty,t = Et: ve ACA()), zī.-- These constraints link the number of alternatives of each type with the number of alternatives each voter approves of.
(8) For every j E [e] we add a constraint Evev f(z,.)) 2 SCPAv (P. W) - 6.. These constraints ensure that each committee in the reconfiguration has high enough score.
The number of variables and constraints are both 0(2". E) and the function f consists of at linear parts and hence this IPWSPLT can be solved in FPT time wrt. + E. Note that the constraints (3)-(8)
16

---

are the constraints used by Yang and Wang for the committees on the reconfiguration graph.
We now show that the constructed IPWSPLT feasibility instance is a yes-instance if and only if there exists reconfiguration path of at most length & between the given committees W and W
The if part is straightforward: Let Wo.... We be a (6e, recofooofiinr path for (P, X). For every t E T.J E {O..... e), we set the variable xi, to be the number of alternatives in W; that are also in the set represented by Xū, i... [W; n X We additionally set for every 2' E [4] the variable (())))))(())) to be the number of alternatives of type that were replaced by alternatives of type between the committees W and W,. Constraint (5) is thus satisfied by construction. As these variables describe valid committee, the constraints (6)-(8) are satisfied, as shown by Wang and Yang. Constraint (1) is satisfied, as Wo- = W and W2 = W' Constraint (2) is satisfied because the symmetric difference upper bounded by 26, &g. Constraint (3) must satisfied, as it is not possible to have more alternatives of any type in the solution then there are in total. Similarly constraint (4) must be satisfied, as we can only switch out alternatives from groups that were previously in the solution.
The only-if part follows similarly: We iteratively create the committees Wj for every E [e]. Note that Wo = W and W = w" are already fixed. Suppose the committees W,,... W have been created and fulfill our conditions. We then create W For each variable ((,.)) 3+1)" we replace that many alternatives that are in Wj and belong to the group [X] with alternatives that are not in Wj and belong to |X After this process, have replaced at most de many alternatives with 8e many other alternatives due to Constraint (2), and therefore the symmetric difference is upper bounded by 2 2 The resulting committee must exist because Constraint (3) ensures that each group in each type of alternatives does not appear more often in a committee then possible and Constraint (4) ensures that only existing alternatives were switched out. Constraint (6) ensures that the committee has size k. Constraint (7) counts the number of alternatives voters approve and with Constraint (8) ensures that the score is sufficiently high. As this reasoning holds for every j E [d]. the generated Wo..., Wy is a (de, 6z 6-J-reconfigurationn path from W to W", as required.
Therefore it is possible to find path between two committees using the IPWSPLT feasibility formulation.
B.4 Proof of Proposition
Proposition 4 (+). For all score-based voting rules X such that the score of committee can be computed in polynomial time, the following holds:
(i) X-MR is solvable in m2 -2_ (n + m) time, and hence in XP wrt. & for constant é--
(ii) If X is additionally neutral, then X-MR is solvable in k2k (2" + 2)2* (n + m))(1) time and (k + 1)4-2" (n + m)0() time and shortest reconfiguration path can be found in the same time. Thus, is FPT wrt. n + k and in XP wrt. n.
Proof. For Statement (i), we observe that in each reconfiguration step we exchange at most & alternatives with at most & other alternatives. This gives us (*)) 2 possible different exchanges. Since
for a yes-instance we have at most é steps in the reconfiguration path, we have ((*) 2 = m possible different reconfiguration sequences. Since the score of a committee can be computed in polynomial time, can check for every sequence whether it is (8e, 6,) recoofiiiginn path from W to W" in 26 (n + m))(1) time.
The proof idea for Statement (ii) is to group alternatives of the same type, keep only a bounded number of alternatives for each type and then generate reconfiguration graph of bounded size. To Let 'T denote the set of types of alternatives that exist in given preference profile P. We define C, be the set consisting of all alternatives with type for t E T. We will analyze the running times one by one: Generally, let P = (C, V. R) be a preference profile and I (P, de, &,, W, W") an instance of X-MR.
this end, we enumerate the types as 1,.....7 2n.
For the first part of Statement (ii), we observe that every committee on a reconfiguration path contains at most k alternatives of each type. Therefore, apart from the alternatives that appear in W U W', we
17

---

may remove all but k many alternatives of each type from the instance. Let us call the set of kept alternatives V. This means that we only need to keep at most 2k + k-2" = k(2 + 2) alternatives. We can construct a restricted reconfiguration graph of the remaining alternatives and determine a shortest path between uy and uw, in time (( ((k(2)+)))
k 22))) )² (n + m))() = (k(2" + 2)) (n + +))00)
A uw-lww" path of length l' in the restricted reconfiguration graph corresponds to (ō,, 62)- reconfiguration path of length f", as the committees corresponding to the vertices on the path form a (de, d&) -reconfiiuuaatonn path in /. Next assume we have a (6c, 0g) de-oooonfiiirnaonnnn path (Wo.... We) W)), where W Wo and W = We,, of length '' in I. We will show that there is uw-uww path of length at most e' in the restricted reconfiguration graph. Let us iteratively construct the path "w, ".,"
We show that in each step the following two conditions hold for j E "0....,(?)
(CI) We n (W U w = We n (W U W"), i..., an alternative from W U W' is in We if and only if it is in We, and
(C2) for every alternative type E T, it holds that (WFU")) = (W nC, (WWU")) i.e, for every type, the number of alternatives of that type is the same in both W and W", discounting the alternatives in the initial and goal committees.
From these two conditions it follows clearly that sc(W)) = sc(,,) for every j E to......t.. Since all alternatives in W U W' are retained, the first vertex in the path is uw and the last uwr Assume we have created vertices uW...... ,w so that Wo... W, satisfy the conditions. We construct the committee W from W, as follows:
We remove the alternatives in (W, W (1+1) (WO'")
We add the alternatives in (W 3+1 W, n (WOW).
(iii) For every type t E T such that d == [W; \ (W (WW") - [W (WOW)) > O, we remove
arbitrary d alternatives of type t from W, \ (WUW".
(iv) For every type E T such that == [Wi+1 \ (WUW") [W, \ (W W'I > 0, we add arbitrary d alternatives of type t from (V (W)) \. (W (WOW).
We show that these exchanges, if possible to perform, enforce that W,+1 satisfies the two conditions (C1) and (C2) we set prove. The first two exchanges guarantee (C1), they remove and add the corresponding alternatives to Wj+1. The last two guarantee (C2), as they remove and add alternatives of the same type as are removed and from W, to W It is obvious that Exchanges (i) and (ii) can be performed. Similarly, Exchange (iii) is clearly possible as we remove alternatives that are necessarily in the committee. To see that we can always perform Exchange (iv), recall that V contains d, == min(k, [c, C (WUWW) U W')! alternatives of type I. No committee may contain more than d, many alternatives of C, (W W"), so this exchange is also safe. It is also clear we will always add at most IW, \ Wj+1l alternatives and remove at most [W j+1 W, alternatives, W,, and W are dd-adjacent, and thus uw, and uW;; are adjacent. This concludes the proof of the first part of Statement (ii).
For the second part of Statement (ii), we observe that there can be at most k alternatives of each type in committee, so we can upper-bound the number of committees need to track to (k + 1)2-2"; We associate each size-k committee U C C, with two length 2an vectors with non-negative entries such that for all U C C,, E T.
[(U)(( = (U) \ WII and g(U)({ =
The vector ((U){t) is the number of alternatives of type t in the committee without W', and {U)[ is the number of alternatives of type in the committee that are also in W'. For these pairs of vectors we define -d-ajaacey in the following way: Let (f(W)) g(W)) ((W)..(W1) the pairs of vectors representing two committees W and W We say that (f(W)). ((W) and (f(W)). () are -ddaaeenntt if EiET [[W))[ - f(W2) + 19( [[t - [[t]) < 2dc-
and ((W2).gWW)) be
It is clear there are at most (k + 1)2-2" possible ordered pairs of vectors f and g. For each such ordered pair of vectors we consider it relevant there a corresponding size-k committee, i.e., there are enough alternatives of each type in both W" and C' W' and the score of such a committee at least Sc(W)- - &.- Note that the scores of any two committees with the same corresponding ordered pairs of vectors must be equal because we are considering neutral voting rule. Let
18

---

V=[(((() U S c,sc 2 Sc(U),IU] kj be the set of ordered pairs of vectors that are relevant. We construct a restricted reconfiguration graph & whose vertices are V. where there is an edge between two pairs of vectors if and only if they are de-adjacent. Such a graph takes (k + 1)4-2 (n + m))(1) time to construct.
We proceed to show that there is a (&e, 4.) reeoooooniinn path of length E between W and W if and only if there is a path in & between (f(W), ((W) and (f(W"), ((W")) of length at most e".
Assume there is (ōe, -eeoroooniinronaooonn path (Wo.... We:), where W W and Wr W of length E' For every Wi. E {o....,E') we construct (f(W)), ((W)) as previously described. g( (W)) )) must be contained in V by construction. It is casy to observe that if AWW J+1| I 2 c, then E1ET (f(W)) f(W,+ + (W) - ((W)+1) - 2 de and the two vectors are -c-adjacent.
We know that (f(W)), ). g)gg)))(
Assume there is path in & between (S(W), g (W)) and ([(W"),9WW) of length at most E. We construct a reconfiguration path (W....... We) such that Wo W. Wer = W and for every j E (0, ( () E 'T, it holds that [(W))(4 = (C,)W)) \ W and (WW)) (C,
We set Wo- W. Assuming we have constructed committees Wo.... W for some j E {o....,. C 1} so that the above conditions are satisfied, we construct the next committee Wj+1 as follows:
(i) For every type E T. if (W)++){ft f(W,) > 0, then add arbitrary f(W
f(W many alternatives from (C, W,) W to W,.
(ii) For every type t T, if f(W,) [[]] - ff(W [+] 0, then we remove arbitrary f(W
J(W,-1 [4] many alternatives from (W WWW from Wj-
(iii) For every type 1 T, if o(W5+1) -g(W;)(( > 0, then add arbitrary (WW+1))[(]
[W] many alternatives from (C, W3) n W to W,.
(iv) For every type E T, if g(W, g( 4+1 [t] > 0, then we remove arbitrary g (()) ((5++1][ many alternatives from (W, n C,) n W" from Wj.
It is easy to see that if these exchanges can be performed, then fW = I(C. n (1) W and 9 [[t] = [CC, n W5+1) n W'| must hold. We can perform Exchanges (i) and (ii), as per construction, there must be enough alternatives of the selected type in (W, n C,) \ W and (W,nG))nW'. Similarly Exchanges (ii) and (iv) can be performed, because there must be sufficiently many alternatives in (C, (") \ W, and (C, (W) Wj. because otherwise W W could not exist in the reconfiguration path. Additionally, because W3 and W are do-adjacent, the committees W, and Wi+1 must also be d.-adeac,nt, as the number of additions and removals in (i)-(iv) is upper-bounded by EIST (f [t]] - f(W + (g( [[ - g -WW-))) < 2 8g. The score of W,+1 must be sufficient because otherwise (f(W,+1), (WW+)))WWW)))) would not be on the path.
To see that We = W', is enough to observe that W is the only committee U S C such that f(U)[{] = [C,, n W' \ W'| and (() = ICC W W = |C, W"| for every & T. Thus we have that We = W".
The FPT (resp. XP) statement follows directly from the time of constructing & and searching for shortest path.
B.5 Proof of Proposition 5
Proposition (x). For all neutral and score-based multi-winner voling rules À such that the score of committee can be computed in polynomial time, X-MR is solvable in 22bn (n + m() time, and hence FPT wrt. n + b.
= (C [m], V. R) be a preference profile and /= (P, k, dc, d=, W, W') an instance of X-MR. As every voter approves at most b alternatives, the number of alternatives that are approved by at least one voter is at most br. Let Ö' = UieVA; denote the set of alternatives that are approved by least one voter. Then CC] < bn We call these alternatives relevant and the rest of the alternatives irrelevant.
Proof. P
For every two size-k committees W,, W2 such that W1 n = W2 n é there is a reconfiguration path from W1 to W2 by swapping the irrelevant alternatives one by one. This is true because the irrelevant alternatives are not approved by any voter and X is neutral, so their identity does not affect
19

---

the score of the committee. We can use this observation to create modified reconfiguration graph where we disregard the information concerning the identity of irrelevant alternatives.
We create a modified reconfiguration graph GR, The vertices are all at most size-k committees of C' such that, possibly together with some irrelevant alternatives, they could committees on a reconfiguration path. Formally, the set of vertices of GR is
V(GR) =[ucr | S C s.t. |C S k SC) Scy (C' U W) s 6, for some W CC) C with [W| = k ICI)-
Since IC] S bn, we have that [V(GR)] S 2bn, There is an edge between two vertices uw; and uw, there are two committees containing W1 and W2 as their relevant alternatives, which are ddaadeecent. Formally uw, and uw; are adjacent if [W] \ W2| S 6e and [ \ Wil S dg. The number of edges ) is bounded above by (2bx)² ) Similarly the proof of Proposition 3, we can of GR, i.e. ..e.. search for a path from "wrc to "w'nn in 22bm (n+ m))()) time.
Finally, we show that there exists a path from uwnc to "grnn in the modified reconfiguration graph if and only if there exists a (ōe, 6.)-reconffguration path for T.
For the if direction, let .o...., W. with Wo = W and W. = W be reconfiguration path. For each committee W; on the path there must exist vertex Ww.nc- Since IW; WW+1l S 6 and [W++1 \ Wi| S 6. it follows that [W;+1 O Õ) \ (W, (C)) I 6c and (W; \ (W+inn)) s &c. Therefore it follows that "wind -.... "w,n is path in the modified reconfiguration graph.
For the only-if direction, we first note that irrelevant alternatives can be exchanged with other irrelevant alternatives without changing the score. We order the irrelevant alternatives an arbitrary but fixed way such that the irrelevant alternatives in W are before all other irrelevant alternatives. Let MV....., uy, be a path in the reconfiguration graph such that Vi Wnd NC and V = W' w'nc. We will now iteratively build a reconfiguration path. We set Wo = W. Let Wo...., W be the committees corresponding to the first i vertices on the path. We create W in the following way:
If [ V++1l. then we set W++1 W \ (V, \ Vi+1) U (Ve41 \ Vi). In this case |W++1| [W,. [W++1 Wal |i+1 \ Vil S 6e, and [W; W = VV, \ Vi+1l S &c. Therefore this is a valid reconfiguration step.
[V > |V+1 then let be the V/ - --V many irrelevant alternatives with the lowest index which not in W. We then set W W, \ (V, UV++1 \ Vi) U J. In this case WH+1 |W, and due to this [W++1 W = W; Wi+1 As W, \ Waal = VV/ Veaal < 6c, this is also a valid reconfiguration step.
In the last case that V/| < |V++1. |. let be the |V4+1 - [V| many irrelevant alternatives with the highest index which are in W. We then set W = (W, \ 7) (V, U V.). In this case [Wi+1|= = [Wa and due to this [W++1| \ Wal = [W; \ W As [W, \ W = [V+1 \ Vil < de. this is also valid reconfiguration step.
It is easy to see that the obtained UV44 is in the reconfiguration graph, SC(V++1 U (W; \ \c) = sc(W++1) 2 SC(W)- 5..
By repeating this process, we get a reconfiguration path from W to committee W, which satisfies We W C = W" n Ć. Therefore the alternatives in W,AW' are only irrelevant alternatives. We can greedily exchange these alternatives obtain reconfiguration path from W. W', thereby completing our proof.
B.6 Proof of Proposition 6
Proposition 6 (x). DSR-TJ is W/2]-hard wrt. h + l.
Proof. We provide a parameterized reduction from the W[2]-complete DOMINATING SET prob- lem (Downey and Fellows, 2013) which is adapted from the one of Mouawad et al. (2016). We will point out the differences in the reduction.
20

---

DOMINATING SET (DS)
Input: A graph G and a non-nege non-negative integer h.
Question: Does G admit dominating set of size h??
We first show the construction and then the correctness. Note that in our construction. the size of the dominating set as well as the length of a shortest reconfiguration path in the reduced instance will be linearly bounded by h.
Construction. Let (G, h) be a DS instance with V = fu1..... Un ) being the vertex set of G. The graph G of the created instance of DJ consists of two independent graphs H₃ and H2.
The first graph H1 consists of h + 4 cliques (i.e., complete subgraphs), each of size h h 3 (rather than h + 2-cliques consisting of h 1 vertices in the original reduction of Mouawad al.). We refer to these cliques as Co...., Ch+3. We furthermore label the vertices in each clique C₁ as -i,,,-.., +3,++3- Finally, we add to H2 the following edges E" (1 U,,a} A i, E [h + 3|.. In other words, we make each vertex in Co adjacent to the vertex in each other clique C₂ (z E [h + 3) that have the same second index. Therefore, each vertex in each of the cliques C1..... Ch+3 is adjacent to vertex in Co, with no two vertices from the same clique C- being adjacent to the same vertex in Co.
The second graph H2 is the same the one in the original reduction. It consists of h + 2 copies of the original graph G' which we label Gn (V1, F1): :....... GR++1 (V++1, FR+1). For each (0...., h 13, }. let W2,1,--- | denote the vertices in G,. We add to H2 the following edges F" = H Wz,} } i, E [m], E [h + 1] s.t. {u,,uz) E(C) i j]. In other words, make
each vertex Wo,s E Go adjacent to the copies of its neighbors in Go and to its copies w1, wp...,,,,11 in GR+1.
Finally, we add to H2 a set D of h + dummy vertices do...., dh+1 and edges that connect the copied graphs, one for each copy. For every 2 E {0, ........ h + 1), make d2 adjacent all vertices in G2 and all vertices in Gu-
We define the initial and target dominating sets as V, = V(C,) U (wi.I..... w and V = (vi, i E [h- + }] UUDU (wi,I... Wi,A respectively. Note that the set [wi,,..... Wi,. is not necessary to dominate the vertices in the created graph, but is needed to maintain the size bound; can be replaced with an arbitrary but fixed vertex subset of (Go) of size h. We use this subset for ease of reasoning.
To complete the construction, we define the size bound h = 3h + 5 and E = 4h + 5. Clearly, the construction can be done in polynomial time and [V |V, h.
Correctness. We show that (G, h) admits a size-h dominating set if and only if the constructed instance has length-l reconfiguration path between V, and Vg. For the "only if" part, let U" denote a size-h dominating set of G. We first exchange the vertices W1, z E [h). one-by-one with the U'.. Afterwards, we exchange each dummy vertex from D with a distinct vertex U2,., 2 E [/ + 2]. Next, we exchange one vertex from ((C)) with vertex 3/43334- Note that now the remaining vertices from the clique Co are not necessary to dominate the vertices in the created graph anymore. Thus, we can exchange the remaining h + 2 vertices from the clique Co with the / + 2 dummics from D. one-by-one, reaching the target dominating set. The length of the reconfiguration path is h + h + + h + = 3h + = l.
vertices from the copies corresponding to V', i.e., {wi,5
For the "if" part, assume that the constructed instance admits a length-E reconfiguration path be- tween V, and Vi, We aim to show that on the reconfiguration path there must be a dominating set of H1 U H2 containing a size-h subset which corresponds to a dominating set of G. We recall an observation by Mouawad et al. that for f + 4 cliques, each of size h + 3, and connected as described in their construction, they need + 3 additional vertices on that graph in order to be able to switch from the dominating set consisting of V (C₂) to the dominating set { i [h + 2]} via TAR, as one needs to dominate all vertices from C., 2 E [/- + 3], before removing any vertex from Co-
We show similarly that for the TJ variant we can only afford to have h vertices to dominate all vertices from H2 in order to "save up" + to exchange for the vertices from {Uz.e E [ 2]]- To achieve this, we claim that for each dominating set X on the reconfiguration path which does not contain all vertices from the clique Co, i.e. |X n (Ca)) * [V(Co)). must hold that (V(C.) E X| 2 1 for every 2 [ 2). Let U be vertex that is not included in X. Then, in order to dominate all vertices
21

---

k
12
k:
Running time (s)
k:
Ruie: CC
Rule: CC
Rule: PAV
Rule:
Running time
2-
0
0002
0009
0003
00n8
00001
0006
0000
00003
00081
00000
666
6882
6689
6669
6688
66801
58881
0.3
0.4
Radius
Figure 3: Left: The dependency the median to find reconfiguration path the number voters n on Netflix data. Right: The dependency of the median time to find reconfiguration path to the radius of Manhattan data.
1.2
k:
3:
k
k:
k
1.0
0.25
$ 0.25
Running time (s)
0.8
0.75
0.5
Rurning time
$: 0.75
$: 0.5
#:
0.6
0.0
0.75
0.05
0.75
P
Figure 4: Left: CC, Right: PAV. dependency median time find reconfiguration path p under (p-6)-Rees Resampiiaa data, measured in seconds.
from {Uz,i + 3]}. need vertex from each clique Cz, claimed. Since no vertex in Co is contained in V₁, in order to reconfigure from V, to V,, there must be an intermediate dominating set X' where one vertex from VCC) is missing and least
vertex from each clique C₂ is present. This means that X' contains /t + 3 - + 2 = 2h + 5 vertices from the first graph H₃- By the size bound = 3h + 5, we need h vertices to dominate the second graph Hz. By construction, this is possible only if it corresponds to size-h dominating set of the input graph G. This concludes the "if" part and the correctness proof.
C Experimental Research
In this section, present preliminary research how easy reconfiguration paths find practice. We discover that reconfiguration paths almost always exist and can be found quite efficiently. We both real-life (Netflix Prize data (Netflix, 2006)) and synthetic data (geometric and (p-a)-iesa
C.1 Setup and Heuristic
We perform the experiments for both CC and PAV and committee sizes k (3, 4, 5).
For each then pick and pair the 20 best ones. This way obtain random but still reasonably well-scoring
we create 100 random committees. We order them by score,
22

---

Table 2: Netflix data: Median, average, and variance of the running time, and the number of committee pairs. The data is only taken on the committee pairs that did not time out, except the total number of committee pairs. The proportion of timeouts is in Table 3. Timeout 60s.
k
k
5
Rule
Med.
Avg.
o²
#
Med.
Avg.
Pairs
Med.
Avg.
a²
Pairs
0-999
0.01
0.02
0.00
9020
0.07
0.07
0.00
9020
0.40
0.41
0.04
9020
1000 1999
0.02
0.03
0.00
2650
0.10
0.10
0.00
26500
0.51
0.50
0.05
2650
2000-2999 2999
0.03
0.03
0.00
980
0.11
0.11
0.00
980
0.54
0.52
0.05
980
3000-3999 3939
0.13
0.14
1190
0.07
4000 4999
0.04
0.04
0.00
1170
0.15
0.16
0.00
1170
0.69
0.72
0.09
1170
5599
0.00
720
0.19
0.20
720
0.88
0.94
0.16
720
6000 6999
0.05
0.06
0.00
680
0.21
0.23
0.01
680
0.95
1.04
0.24
680
7000-7999
0.06
0.08
0.00
830
0.25
0.28
0.02
830
1.15
1.31
1.01
830
8000 8999
0.07
0.08
0.00
860
0.26
0.29
0.02
860
1.22
1.40
0.61
860
9000 9900-9999
0.08
0.09
0.00
590
0.29
0.31
0.02
600
1.31
1.52
1.70
600
CC
10000 10999
0.04
0.33
0.42
9.34
560
11000 11999
0.09
0.11
0.01
430
0.36
0.40
0.04
430
1.63
1.80
0.86
430
12000 12999
0.18
0.21
430
0.42
0.56
1.04
430
1.94
2.34
7.09
430
13000 13999
0.12
0.14
0,01
340
0.45
0.49
0.05
350
2.09
2.18
1.18
350
14000 14999
0.13
0.15
0.01
220
0.52
0.57
0.07
220
2.22
2.34
1.42
220
15000 15999
0.13
0.16
0.01
300
0.55
0.60
0.08
300
2.75
2.76
2.05
300
16000 16999
0.13
0.14
0.00
190
0.47
0.51
0.06
190
2.26
2.37
1.45
190
17000 17999
1.50
0.51
0.99
220
18000 18999
0.13
0.21
0.11
100
0.47
0.53
0.09
100
2.05
2:27
1.02
100
19000- 19999
0.14
0.16
0.01
0.47
0.49
0.02
20
2.76
2.96
0.91
20000
0.25
0.32
0.06
0.70
1.21
2.44
30
3.42
5.31
23.19
30
0-999
0.02
0.02
0.00
9020
0.07
0.08
0.00
9020
0.31
0.41
0.12
9020
1000 1000-1999
0.03
0.05
0.00
2650
0.12
0.13
0.02
2650
0.46
0.57
0.41
2650
2999
0.00
0.14
0.14
0.10
980
3000 3999
0.04
0.05
0.00
1190
0.16
0,18
0.01
1190
0.76
0.83
0.23
1190
4009
0.05
0,06
0.00
1170
0.19
0.21
0.01
1170
0,90
0.99
0.37
1170
5000 5999
0.06
0.07
0.00
720
0.24
0.27
0.02
720
1,21
1.39
0.66
720
6000 (000-6999
0.07
0.08
0.00
680
0.29
0.33
0.03
680
1.43
1.63
0.89
680
7000 7999
0.00
830
0.35
0.43
1.70
2.24
830
8000 8999
0.10
0,12
0.01
860
0.40
0.48
0.12
860
1.93
2.39
3.19
860
9999
0.02
0.44
0.53
4.40
600
PAV
10000 10999
0.12
0.17
0,05
560
0.50
0,71
2.01
560
2.33
3.07
17.26
560
11000
11999
0.13
0.16
0.02
430
0.52
0.63
0.15
430
2.72
3.16
3.64
430
12000
12999
0.16
0.26
0.22
430
0.68
1.05
6.15
430
3.09
3.77
9.49
430
13000 13999
0.17
0.20
0.02
340
0.71
0.84
0.27
350
3,51
4.02
6.83
350
14000 14499
0.03
220
0.81
220
15000 15999
0.19
0,24
0.03
300
0.86
1.02
0.37
300
4.86
5.59
13.46
300
16000 16999
0.02
190
0.77
0.90
190
4.12
4.71
190
17000 1799U
0.20
0.64
8.75
220
0.79
1.59
36.48
220
3.88
5.41
38.97
220
18000 18999
0.18
0.28
0.07
100
0.69
0.86
0.32
100
3.68
4.10
7.14
100
19000 19999
0.20
0.21
0.01
0.94
1.00
0.20
20
3.97
4.31
6.65
20
20000
0.28
0.39
0.08
30
1.31
2.65
7.23
30
6.21
10.69
102.87
30
committees. If the number of alternatives is too small obtain 100 random committees. we skip the instance. For each pair, we choose the lower scoring committee as the starting committee W, the higher scoring as the goal committee W", and set 6g and 8
To find a reconfiguration path, we create an initial set S = W U W'. We create the reconfiguration graph that only uses the alternatives in S. We use Python and our modification of the abevoting library (Lackner el al., 2023) to find all the committees that use alternatives in S and whose score is at least SC(W). If there no W-W" path in this graph, we add the alternative with the highest number of approvals outside of S to S, and add the sufficiently high-scoring committees within S that contain this alternative to the reconfiguration graph. We repeat this until we either find a reconfiguration path, show there is no path, or time out.
The experiments are run on Python 3.. Additionally we use for example the following Python libraries: abcvoting version 2.8.0, Gurobipy version 10.0.2 and Networkx version 3. A complete list of all the dependencies is in the supplementary material. We modify the abcvoting library to be able to compute all committees whose score is at least some percentage of the optimal score. The experiments are run on Ubuntu 22.04.2 with 3.8 GB of RAM, CPU of the virtual machine "Intel Xeon (Cascadelake),, 2x 1-Core", on a host with "Intel Xeon Gold 5215, 2x 10-Core".
We set the timeout for finding the reconfiguration path to 60 seconds.
23

---

Table 3: Netflix data: The proportion of timcout pairs. Timcout 60s.
k 3
k CC
5
76
PAV
PAV
CC
PAV
09999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
1000 1999
%
0.0
%
0.0
2000 2999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
3000 3999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
4000 4999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
5000 5999
0.0 %
0.0
%
0.0
6000 6999
%
0.0
%
0.0
7000 7999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
8000 8999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
9000 9999
0.0 %
0.0 %
0.0 %
0.0
0.0 %
0.0 %
10000 10999
%
0.0
%
0.2
11000 11999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0
12000 12999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.2 %
13000 13999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
14000 14999
0.0
0.0 %
0.0
0.0
%
0.0
15000 15999
%
0.0
%
0.0
16000 16999
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
17000 17999
0.0 %
0.0 %
0.0 %
0.5 %
1.4 %
1.8 %
18000 18999
0.0 %
0.0 %
0.0 %
0.0
0.0 %
0.0 %
19000 19999
%
0.0
%
0.0
20000
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
Table 4: Manhattan data: Median, average, and variance of the running time. The data is only taken on committee pairs not time out. The proportion of timeouts is Table 5. Timcout 60s. There are 100 instances for each radius.
3
k
k 5
Rule
Radius
Med.
Avg.
d²
Med.
Avg.
a²
Med.
Avg.
0²
0.1
0.01
0.00
0.04
0.03
0.00
0.14
0.14
0.01
0,2
0.01
0.02
0.02
0.06
0.08
0.15
0.23
0.27
0.03
0.3
0.02
0.04
0.04
0.09
0.11
0.01
0.35
0.40
0.07
CC
0.4
0.03
0.16
0.77
0.13
0.22
1.05
0.43
0.51
1.19
0.5
0.32
2.02
0.15
0.31
2.74
0.44
0.50
0.6
0.03
0.32
4.80
0.12
0.18
1.88
0.34
0.40
0.07
0.7
0.02
0.14
2.27
0.10
0.10
0.00
0.54
0.52
0.06
0.1
0.01
0.01
0.00
0.04
0.04
0.00
0.17
0.16
0.01
0.2
0.02
0.03
0.00
0.11
0.11
0.00
0.45
0.52
0.14
0.3
0.06
0.06
0.00
0.31
0.35
0.22
1.73
1.92
1.61
PAV
0.4
0.12
0.05
0.78
0.79
0.18
4.54
4.89
8.87
0.5
0.17
0.20
0.14
1.28
1.26
0.36
7.64
7.86
19.70
0.6
0.26
0.30
1.65
1.85
1.78
0.63
12.44
11.73
33.98
0.7
0.27
0.28
0.02
2.04
1.98
0.68
13.38
12.12
34.25
Table 5: Manhattan data: The proportion of timeout pairs. Timeout 60s.
k
Radius
CC
PAV
CC
PAV
CC
PAV
0.1
0.0
0,0
0.0
%
0.2
0.0 %
0.0
0.2 %
0.0 %
0.0 %
0.0 %
0.3
0.0 %
0.0 %
0.2 %
0.0 %
0.0 %
0.0 %
0.4
0.0 %
0.0 %
0.0 %
0.1 %
0.1 %
0.0 %
0.5
0.0 %
0.0
0.1 %
0.1 %
0.1
0.0 %
0.6
0.2 %
%
0.0
0.7
0.0 %
0.0
0.0 %
0.0 %
0.0 %
0.0 %

---

Table 6: Resampling data: Median, average, and variance of the running time. The data is only taken the committee pairs that did not time out. The proportion of timeouts is in Table 7. Timeout 60s. There 100 instances each (p-o)-pait)
k 3
4
k 5
Rule
P
Med.
Avg.
a²
Med.
Avg.
Med.
Avg.
0.25
0.01
0.02
0.00
0.02
0.09
0.01
0.23
0.42
0.18
0,5
0.01
0.02
0.00
0.05
0.07
0.00
0.37
0.42
0.13
0.05
0.75
0.01
0.02
0.00
0.07
0.06
0.00
0.37
0.34
0.06
0.01
0.02
0.00
0.06
0.06
0.00
0.28
0.30
0.03
0.25
0.05
0.06
0.00
0.21
0.21
0.01
0.89
0.95
0.40
0.08
0.08
0.25
0.24
0.01
0.97
0.98
0.30
0.25
0.75
0.08
0.07
0.00
0.23
0.22
0.01
1.01
0.98
0.25
0.07
0.23
2.59
0.23
0.28
0.67
0.98
0.98
0.30
CC
0.25
0.03
0.03
0.00
0.14
0.14
0.00
0.70
0.81
0.22
0.5
0.06
0.13
0.62
0.18
0.22
0.02
0.63
0.74
0.18
0.5
0.75
0.11
0.20
0.72
0.26
0.44
5.82
0.64
0.77
0.28
0.10
1.15
22.22
0.26
1.06
24.11
0.60
0.79
5.25
0.25
0.04
0.03
0.00
0.18
0.15
0.00
0.56
0.82
0.20
0.5
0.03
0.03
0.00
0.20
0.17
0.01
1.07
0.94
0.23
0.75
0.75
0.03
0.09
1.47
0.19
0.17
1.24
0.22
0.02
0.14
0.31
0.19
0.18
0.01
1.15
0.96
0.20
0.25
0.01
0.04
0.00
0.07
0.17
0.08
0.48
0.92
0.5
0.02
0.03
0.00
0.08
0.10
0.01
0.42
0.55
0.31
0.05
0.75
0.02
0.02
0.00
0.09
0.08
0.00
0.32
0.32
0.06
0.02
0.02
0.00
0.07
0.07
0.00
0.25
0.25
0.02
0.25
0.34
0.39
0.10
2.09
9.45
9.34
28.37
0.5
0.24
0.27
0.04
1.66
1.71
1.05
9.25
10.37
43.26
0.25
0.75
0.17
0.18
0.01
1.02
1.07
0.39
7.64
7.60
22.35
0.16
0.16
0.01
0.97
0.96
0.55
6.43
5.99
9.71
PAV
0.25
0.27
0.35
0.07
2.45
2.34
1.42
11.92
10.62
24.53
0.45
0.43
3.26
3.00
17.87
15.87
44.97
0.5
0.75
0.45
0.44
0.05
3.26
3.02
1.41
18.95
16.69
46.51
0.39
0.39
0.16
3.25
2.99
1.57
17.20
15.72
58.93
0.25
0.10
0.10
0.00
0.57
0.56
0.05
3.57
3,56
5.53
0.5
0.21
0.20
0.01
1.39
1.30
0.24
8.55
7.61
10.59
0.75
0.75
0.29
0.29
0.02
1.97
1.83
0.49
11.68
10.33
19.17
0.36
0.34
0.03
2.50
2.30
0.85
13.80
12.06
26.80
Table Resampling data: The proportion timeout pairs. Timeout 60s.
k
3
k CC
5
p
CC
PAV
PAV
CC
PAV
0.25
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.5
0.0
0.0
0.0 %
0.0
0.05
0.75
0.0 %
0.0
%
0.0
1
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.25
0.0 %
0.0
%
0.0 %
0.0
0.5
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.75
0.0 %
0.0 %
0.0
0.0 %
0.0 %
0.0 %
0.1 %
0.0 %
0.4
0.0 %
0.4 %
0.0
0.25
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.5
%
0.0 %
0.0
0.0 %
0.0
0.5
0.75
0.0 %
0.8
0.1 %
0.0
0.3 %
0.1 %
1.6 %
0.1 %
0.8 %
0.0 %
0.25
0.0 %
0.0 %
0.0
0.0 %
0.0 %
0.0
0.5
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.75
0.75
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.0 %
0.1 %
0.0
0.0 %
0.0 %
0.0
25

---

C.1.1 Data Preprocessing
Netflix data. Netflix data contains ratings for 17770 movies from 480189 users. The ratings contain the date of the rating and an integer score from the range [1. To create approval preferences, we interpret rating lower than 2 or lack of rating as disapproval, and a rating of at least 3 as approval. To make multiple elections, we divide the ratings by date. There are in total 2180 days.
We turn the ratings into approval votes and divide them by dates. To make the instances smaller, for each day, we remove all the movies that got fewer than 5% of the number of approvals of the most popular movie of the day. We also ignore each day with fewer than 10 voters (i.c., users) or 5 alternatives (i.e., movies). In the end 2162 instances remain.
Synthetic data. In all synthetic instances, we have n = 100 voters and m = 100 alternativss. However, if either voter does not approve of any alternatives or an alternative is approved by no voter, then it is removed from the instance. As a result, some instances have fewer voters or alternatives. We create two different types of data sets.
The first type uses geometric (Manhattan) preferences: We choose the locations of both voters and alternatives uniformly at random in [0, 1] x [o, 1]. We fix radius r, and each voter approves the alternatives that are within distance from him according to the metric given by the & -norm. We use the values (0.1, 0.2..... 0.7} for and create 100 instances for every value of r.
The second type uses (p-ø)-reewt resampling model (Szufa et al., 2022). In this model the variable p is the probability that a voter approves of an alternative, and ø E [0, 1] controls how dissimilar the voters are to each other; the higher Φ the less similar the voters are. We use values (p, Φ) E {0.05, 0.25, 0.5, 0.75) x (0.25, 0.5, 0.75, }). and create 100 instances for every combination.
More formally, we first create central vote that consists of [p- p-m] randomly selected alternatives. The central vote disapproves all other alternatives. For every voter-alternative pair (Ui, c:), the voter v; takes his opinion on & from the central vote with probability 1-d e and with probability & "resamples" his opinion on e; He approves e; with probability p.
C.2 Evaluation
The median running times of the instances that did not time out presented in Figure 3 and Figure 4. More detailed data is presented in Tables 2 to 7.
Overall we discover that finding reconfiguration path is relatively fast in practice, and CC is noticeably faster than PAV. Despite our timeout being only 60 seconds, less than 0.03% of the committee pairs time out. More detailed breakdown of timeouts can be found in Tables 3, 5 and 7.
Of the pairs that did not time out, all but three pairs of committees admit reconfiguration path. The three pairs in question were all from Manhattan data with radius 0.6 and k = 3. We must however note that it rather difficult show non-existence of reconfiguration path, because it requires in theory creating the whole reconfiguration graph, whose size is in ((m)).
Median running times for Netflix data, divided by the number of voters, are presented in Figure [[Left]. More detailed information is available in Tables 2 and 3. The effect of the number of voters is surprisingly small.
Median running times of Manhattan data, divided by different values of p and Φ. are presented in Figure ][Right], and more detailed information in Tables 4 and 5. The larger the radius, i.c., the more alternatives the voters approve, the harder PAV appears to be.
Median rumning times of (p-o)-resampling data, divided by different values of p and c. are presented in Figure 4, and more detailed information in Tables and 7. The effect of 6 to the rumning time appear to be rather moderate, although we can see from Table 7 that the timeouts are most frequent when Φ high, i.e., the votes are dissimilar. We see from Figure 4[Right] that under PAV the approval probability p has a clear effect the running time: p- = 0.5 has the highest running time, with the times decreasing further away. The problem appears easier when the alternatives either approve a few or almost all alternatives.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All computational complexity claims made the abstract and introduction are backed up by the main body of the paper. To the best of our knowledge the first to introduce the framework presented in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We make clear that our experimental research only preliminary, and should be only used as suggestion of interesting future research directions. Otherwise, our work is only theoretical.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All of our results have complete proofs either in the main paper or the appendix. The guidelines are followed.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The setup is described in detail in Appendix C. The dependencies are described. All the code is included the code appendix. The datasets are either provided by us. or in the case of Netflix data, can be derived from publicly available data using our code or description. The appendix contains also a description of the hardware we use.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
28

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code and the synthetic data are included in the supplementary material. The raw Netflix data, which is not ours, is available Netflix (2006). Code and description the preprocessing are included in the supplementary material and Appendix C.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: /ett::::/nippt cc/ public /guidess / SCodeSubeei ss ssionPolllloooossssossooo olicy) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. wttp:stccpcppcccccctcccccccccccc htt.ubliccggideaaseeeeee guides/ Cooee Submis ss oonooliio oollyyly) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The parameters for the creation of the synthetic data described, the parameters of the reconfiguration path we are looking for (committee size, 6g, 8.). This information is not included in the main paper, because the experiments are only preliminary, and we do not make wide claims based on them.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
29

---

Justification:
We do not make claims of the significance of our results, as the research is only expressed preliminary observation that requires further research. However, do report the variance in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eτror rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The resources are provided in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttpprss/////rss..... http:////...p...ttttttcccteeeeea
Answer: [Yes]
Justification: Our research has societal or human impact. All datasets and code are credited and their licenses described.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
30

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is such risk. All data is either synthetic derived from public dataset.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: abcvoting library and the Netflix data are cited, and their licenses are available there. abevoting library uses MIT license and Netflix data own license, which described in its references Netlix (2006).
31

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papersw wwrrewwii thcode. com/ da catasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We include documentation of the synthetic instances we created in the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
There is no crowdsourcing or human experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
32

---

Answer:
[NA]
Justification:
There is no crowdsourcing or research on human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
33


Reviews:
[{"review_id": "eX2UPF8TCh", "reviewer": "Reviewer_q2Mc", "summary": "The paper studies an attractive reconfiguration problem in the context of multi-winner elections. Suppose we have an n-voter m-candidate approval election and work with a committee-scoring voting rule outputting size-k committees. Fix such a rule r (in the paper, this is either approval voting, proportional approval voting, satisfaction approval voting, or Chamberlin-Courant). The goal is, given two committees W != W’ such that their score under r differs by at most some number x, and given a number y, to compute (or decide the existence of) a chain of committees W = W_0, W_1, …, W_t = W’ such that any two consecutive committees’ scores differ by at most x under r and the symmetric difference between them has size at most 2y (more precisely, the number of added and removed elements between any two consecutive committees are both at most y). The authors study the classical and parameterized complexity of this problem, almost tracing the complete landscape of its complexity with respect to a large number of natural parameters and combinations thereof. The paper also provides an experimental appendix on computing such chains in practice.", "questions": "1. Please clarify (*) above.\n\n2. Would any of your results still apply to the alternative setting described in (**) above?\n\n3. You mention that your hardness results apply even to the setting of working exclusively with optimal committees, which I personally find very attractive (and maybe it should even be somehow mentioned in the technical statements, similar to a point I made earlier). However, both PAV and CC are hard to compute, so it could be unrealistic to assume that access to optimal committees is available. Would any of your findings translate to assuming that the starting committee is the output of some approximation of PAV or CC?", "limitations": "In general, the paper is honest about the quality of the work and where the unknown starts. I have no complaints in this regard.\n\nNo potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is quite well-written and motivated. I enjoyed reading it. The parameterized complexity analysis is carefully executed, with well-chosen parameters and interesting findings. The paper’s initial segment introduces concepts at an appropriate pace, giving examples where they are due. I was particularly happy with the existence of this sentence: “We will see that all intractability results already hold for the restricted case (x = 0, y = 1), while all algorithmic results hold for the general case.” I think a paper like this could be a nice read for a general AI/ML audience (which is relatively rare for parameterized complexity papers). Moreover, I think the findings will be interesting to the specialized audience interested in multi-winner elections and/or voting in general. The experiments in the appendix clearly add a bit more color to the paper, which would otherwise be a pure complexity paper (I believe these should be more prominently featured earlier in the paper, even if just for a few sentences).", "weaknesses": "- One could argue that such “heavy” parameterized complexity papers shouldn’t appear in AI venues. While I tend to agree with this statement in general, as I already said, this paper could be a welcome exception.\n- The model permits chains of committees where a certain alternative is included/excluded multiple times throughout the chain. In clearer terms: it would be strange if, say, Netflix repeatedly added and removed a certain movie throughout the course of 1 month (extreme example: the movie is available only every second day). I’d say it’s more realistic to ask that once a certain alternative in W \\setminus W’ is removed, it should never be added back. (**)\n- L131-138: {I am familiar with these definitions and I understand what you meant to write.} The way you work here with multi-winner rules implicitly assumes that they are irresolute (i.e., nondeterministic = return a set of solutions), since otherwise neutrality is almost meaningless; e.g., say m = 2 and k = 1 and we have two identical candidates, which one would a neutral resolute rule choose? This makes me also wonder about anonimity as well (outcome does not depend on the name of the voters). What do you actually assume here? (*) I am positive none of these omissions break your results in any way, but I think this should be clarified and revised in the paper.\n- L190-191: I think the correspondence only holds for paths that start at W (the vertex set of the graph is defined in terms of the score of W, so the made statement can’t be true). I understand the idea you wanted to convey though, i.e., we care about subpaths that are to be used in a longer path that starts at W.\n- I had great difficulty understandign the first half of the proof of Proposition 1 (the one making appeal to previous work). This is not because the rough idea is unclear to me, but because of the details; e.g., “determining whether a committee is on a reconfiguration path” seems as hard as answering the whole question. Instead you might have meant “whether it’s in the vertex set of the graph”. I would advise to revise this part.\n\nMinor:\n- You should highlight more in the first few pages that the path need not necessarily be a shortest path. In hindsight, it’s never stated otherwise, and there is no reason why one would believe that, but I still somehow managed to think it’s shortest for a few minutes (maybe because one of the parameters you introduce early on is the length of the shortest one!).\n- L56: It can’t be PSPACE-complete because it’s not a decision problem. I assume you wanted to say PSPACE-hard.\n- L39: The “But…” sentence reads a bit strange. Consider adding a comma or combining with the previous sentence.\n- Abstract: “minor yet impactful modifications” sounds a bit weird in this context. Instead of helping me, the addition of the word “impactful” made me start pondering what would “impactless” changes even mean in this model. The “meaningful” you use on L24 is a bit better, but really I wonder whether an adjective is even needed here.\n- L128: “If not” -> “Unless”\n- L129: Maybe use \\emph{} over the word “type” to show that this is a definition.\n- L165: “Let” -> “Assume”\n- L178: “we use” -> “we write”\n- L194: Remove “the”.\n- L195: “there is no” -> “hence no”\n- I understand the need for them, but LaTeX is just not very appropriate for imbricated proofs (i.e., Claim 1.1 inside the proof of Theorem 1). The \\qed symbol above L234 looks slightly strange if the reader is not accustomed to it.\n- L245: “remains” seems inappropriate here since the former part of the statement doesn’t concern W[1]-hardness. Another comment I will make here, but more generally applicable: it might be worth saying that the proof uses an optimal committee in the statement of the theorem (this is announced earlier in the paper, so it would be nice to have this clearly mentioned also in the theorem statements). I understand that this might have the side-effect of overburdening some statements, but I would ask that you consider clarifying this when revising the paper.\n- L267: “approach [to] the reconfiguration”\n- L294: some early intuition as to why this distinction will be needed would be nice to have.\n- Footnote on page 7: “is” -> “was”\n- In general: I would vote to use the same counter for Theorems, Lemmas and Propositions (it looks a bit strange at times, like on page 7).\n- L390: Remove “as to”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed and helpful feedback.\n\nQ1: \"Please clarify (*) above. What do you actually assume here?\"\n\nWe assume that the voting rules are irresolute, as we look into the case where there are multiple optimal committees and we consider score-based voting rules without tie breakers. Our considered score-based voting rules are neutral. We will make this more clear in our final revision. Although we didn’t discuss anonymity, our algorithmic results for the score-based voting rules (i.e., Propositions 3-5) do work for anonymous and non-anonymous voting rules. \n\nThe remaining algorithmic results are for CC, PAV, AV, and SAV, which are known to be anonymous. \n\nQ2: “Would any of your results still apply to the alternative setting described in (**) above?\"\n\nYes, Proposition 3, Proposition 4(i), and Lemma 1(i) would still hold. Note that for Proposition 3, the running time would be longer; however, it would still be FPT wrt. m and XP wrt. k. For the hardness, we would lose PSPACE-hardness as by adding this restriction because the length of a valid reconfiguration path would be polynomially bounded in m. Due to this, a polynomial-size certificate would exist to verify a solution, meaning that the problem would be contained in NP. \n\nQ3: “Would any of your findings translate to assuming that the starting committee is the output of some approximation of PAV and CC\". \n\nAll algorithmic results should still hold. We conjecture that the hardness results should also hold.\n\nSecond weakness: \"The model permits chains of committees,....\"\n\nWe chose to allow removing an alternative and adding it back to a committee because it may be necessary to do so in order to obtain a reconfiguration path. For example, consider a profile with six voters, called v1 to v6, and five alternatives, called a to e. The alternatives are approved as follows: A(a)={v1,v2,v3}, A(b)={v4,v5,v6}, A(c)={v1,v2,v6}, A(d)={v3,v4,v5}, A(e)={v1}. Suppose we use the CC rule. If we set \\delta_s=0 and \\delta_c=1, then there is a reconfiguration path between the committees {a,b,e} and {c,d,e} only if we are allowed to switch out e and switch it back in afterwards. This means that a store that tries to keep an optimal set of items on display may want to use such a solution.\n\nFourth weakness: \"L190-191:...\" \n\nYou are correct; this is a typo and will be fixed.\n\nFifth weakness: \"I had great difficulty understanding the first half of the proof of Proposition 1...\"\n\nThanks for the comment. We will improve the first half of the proof in our final revision by describing Ito et al.’s general PSPACE-membership more clearly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "8Gijcoeu0C", "reviewer": "Reviewer_wJyv", "summary": "The paper studies the multiwinner setting with approval preferences. The authors propose a new framework of multi-winner reconfiguration, where the goal is to select a sequence of committees such that (1) the subsequent pairs of committees do not differ too much from one another, (2) the final committee is better or, at least, not \"too much worse\", from the initial one. The quality of a committee in the second part is measured using either Chamberlin-Courant scores, Proportional Approval Voting scores, Approval Voting scores or Satisfaction Approval Voting scores.\n\nThe paper solves the following computational problem: having two committees W and W', and having fixed bounds on the maximal number of candidates that could be changed between committees and on the maximal score loss in comparison to the initial committee, decide whether it is possible to reconfigure W into W'. The question is polynomial for AV and SAV scores. For CC and PAV scores it is PSPACE-complete, while the authors propose several FPT algorithms and other complexity results for special cases where certain parameters of the model are constant.", "questions": "You can respond to my doubts in the \"Weaknesses\" section -- in particular, do you have an idea how this setting can be generalized to the rules not based on maximizing committee score?", "limitations": "The limitations are adequately addressed and there is no potential negative societal impact of the work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well-written, its structure and motivation are clear. I especially appreciate the real-world examples presented in the Introduction. The obtained results are technically challenging - as far as I checked, they are sound to me.", "weaknesses": "The only weakness that came to my mind is that the current definition of the multi-winner reconfiguration path is somewhat limiting --- for now it is impossible to apply it for other multiwinner rules that are not based on maximizing some kind of score (like the Method of Equal Shares, or the Phragmen's method), which otherwise would be a natural follow-up question of the paper. Hence, if anyone would like to further analyze different rules in this context, there would still be a need to reinvent the whole reconfiguration setup (and potentially, analyze all the four rules studied by the authors again, under the reinvented definition). This could limit the significance of the contribution, but it does not change my overall positive opinion about the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and an interesting question.\n\nQ: “do you have an idea how this setting can be generalized to the rules not based on maximizing committee score?”\n\nThere are two ways to extend our model to other voting rules.\n\n- We could just follow the graph reconfiguration model and restrict the reconfiguration paths to winning (optimal) committees only. This does not require us to introduce any distance measure to an optimal committee. Hence, it works for all voting rules. \n\n- To allow for nearly optimal committees, we only need to define a distance measure from each committee to an optimal one. For example, Phragmén’s rule can be seen as a greedy approach to the leximax-Phragmén-rule, that is, minimizing the maximum voter load and subject to that, the second highest voter load, and so on. (See Rule 10 in the book “Multi-Winner Voting with Approval Preferences” by Lackner and Skowron.) We could set the loads of the voters under the selected starting committee as the initial “score”, define \\delta_s as a vector as well, and only accept committees W’’ whose loads are lexicographically smaller than or equal to that of our starting committee W + \\delta_s; that is, there is an integer i \\in {0,...,n}, where n is the number of voters, such that the i - 1 highest loads of W’’ are equal to the i - 1 highest loads of W + \\delta_s, and the i^th highest load of W’’ is smaller than the i^th highest load of W + \\delta_s. These vector comparisons can also be translated to number comparisons, if so desired. \n\nThis allows us to compare Phragmén to the four voting rules studied in our paper without reinventing the whole setup.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "seQZ6DEeyC", "reviewer": "Reviewer_tnVW", "summary": "The paper studies the multi-winner reconfiguration problem. The goal is to find a transferring path between two winner committees and not change/decrease the score too much in the path. An example of this problem is switching products for streaming providers. This paper study this problem under for voting rule, CC, PAV, AV, and SAV. They show that this problem is solvable under AV and SAV, and do detailed complexity analysis for CC and PAV on multiple groups of parameters.", "questions": "1. What is the most important difference between your modeling of multi-winner reconfiguration and the reconfiguration problem in the previous work? \n2. I'm a bit confused about the parameter of the complexity analysis. For example, $\\ell$ is not an input in the problem definition, but your results contain $\\ell$, and the proof of Proposition 4 says the path contains at most $\\ell$ steps. Could you explain the relation ship between inputs of the computation problems, the parameter of the complexity analysis, and the constrains of the steps?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ Novelty: Firstly propose reconfiguration problem into a social choice setting. \n+ Well-motivated with real-world examples. I am persuaded by the streaming provider case. \n+ Thorough and solid complexity analysis.", "weaknesses": "- Section 3 is not well-organized. It's almost a list of theorems and proof without any high-level implications. \n- I can't follow Proposition 4's proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the helpful feedback.\n\nQ1: \"What is the most important difference between your modeling of multi-winner reconfiguration and the reconfiguration problems in the previous work?\".\n\nWe’re not quite sure what reconfiguration problems in the previous work you would like us to discuss more, but we would like to emphasize that we’ve discussed differences to the graph reconfiguration problems and to the sequential multi-winner problem by Bredereck et al. in lines 86-87 and 106-111, respectively. In the following, we summarize the most relevant differences:\n\n- Graph reconfiguration problems have in general three types of modifications: token jumping, token addition, and token removal (token referring to the vertices). Our model generalizes token jumping. The crucial difference to the graph reconfiguration problems in the literature lies in the definition of closeness between two committees that may be on the reconfiguration path. We use two aspects: the score and the symmetric difference. In the literature, usually only symmetric difference of size 2 is allowed, and all the solutions on the path must be valid solutions (e.g., it must be a vertex cover). We generalize both of these settings. \n\n- Our reconfiguration is also fundamentally different from the one introduced by Bredereck et al. First, the input is different. In our model, a starting and end committee are additionally given, while in theirs no such committees are given. Second, our objective is to look for a path of committees that are close to each other, closeness being defined by the score and symmetric difference, whereas they look for a sequence of committees that satisfy additional constraints, such as requiring that alternatives remain in a number of consecutive committees. Third, their problem is NP-hard while our problem may be PSPACE-complete in general.\n\n\nIgaraishi et al. study reachability problem in fair division context. The underlying problem is different from ours and the reconfiguration step is more restricted.\n\nIto et al. study how to reform envy-free matching by swapping an assigned item with an unassigned item. The setting is different from ours and the underlying studied problem as well. \n\nQ2: \"I'm a bit confused about the parameter of the complexity analysis...\".\n\nOur problem is in general PSPACE-complete, which implies that even a shortest reconfiguration path can be of exponential length wrt. m and n. Having the parameter \\ell restricts the search space to paths of length at most \\ell. This may help to design algorithms that scale well with \\ell. For instance, Proposition 4(i) tells us that determining the existence of a reconfiguration path of length at most \\ell can be done in polynomial time if both \\ell and \\delta_c have constant values. However, \\ell does not always help. For instance, Proposition 2 implies that the problem remains NP-hard even if every voter approves only two alternatives, and we are looking for a reconfiguration path of length two.\n\nWe will improve upon Proposition 4's readability.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "USChSAmzS6", "reviewer": "Reviewer_go2g", "summary": "The authors study the multi-winner reconfiguration model in the approval setup. They focus on the following rules: AV, SAV, PAV, and CC. While AV and SAV can be solved in polynomial time, CC and PAV cannot. Therefore, the authors provide a more refined analysis of these latter two methods using the FPT approach.", "questions": ".", "limitations": ".", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The first contribution of this paper is the introduction of the new model. The second important contribution is a detailed study of four voting rules, particularly CC and PAV, since they cannot be computed in polynomial time.\nBesides, the paper is overall clearly written (although a bit dry).", "weaknesses": "It is a bit worrisome that there are side comments from the authors in the appendix.\nI also find one sentence in the “Conclusion” section a bit unusual. The authors wrote, “Our preliminary experimental investigations (see Appendix C) indicate that for most randomly generated committees, a reconfiguration path not only exists but can also be efficiently determined using a straightforward heuristic.” There is quite a large section regarding the experiments in the appendix. I think either this experimental part should be completely removed, or there should be a section (or subsection) about it in the main body. It is not a big issue, but it is a bit strange. To be sincere, I don’t know if in such a case I should comment and review these experiments or not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the helpful feedback. We wish to apologize for forgetting to remove the two resolved to-do notes in the appendix.\n\nWeakness: “I also find one sentence in the ‘Conclusion’ section a bit unusual...”\n\nWe believe the experimental section is of interest to anyone who wishes to know some preliminary results on how long the reconfiguration paths are in practice and how easy they are to find. However, our paper’s main contribution is the model and the complexity results, and we did not wish to distract the readers from that. Also due to space constraints, we decided to put the description and analysis of the experimental study into the appendix.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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: All the reviewers like the paper. The paper has clear motivation, shows work of high quality, and is well-written. One of the reviewers points out that while parameterized complexity papers are rare at NeurIPS, this particular paper is a particularly good candidate for inclusion in the conference.
Decision: Accept (poster)