# when_votes_change_and_committees_should_not__27cd6fa9.pdf When Votes Change and Committees Should (Not) Robert Bredereck 1,2 , Till Fluschnik3 and Andrzej Kaczmarczyk3,4 1 Institut für Informatik, TU Clausthal, Germany 2 Humboldt-Universität zu Berlin, Berlin, Germany 3 Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Germany 4 AGH University, Kraków, Poland robert.bredereck@tu-clausthal.de, till.fluschnik@tu-berlin.de, andrzej.kaczmarczyk@agh.edu.pl Electing a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce two time-dependent multistage models based on simple scoring-based voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, and our task is to find a small committee for each stage of high score. In the conservative model we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. We prove both models to be NP-hard even for a constant number of agents, and, based on this, initiate a parameterized complexity analysis for the most natural parameters and combinations thereof. Among other results, we prove both models to be in XP yet W[1]-hard regarding the number of stages, and that being revolutionary seems to be easier than being conservative. 1 Introduction In well-studied classical committee election scenarios, given a set of candidates, we aim at selecting a small committee that is, in a certain sense, most suitable for a given collection of preferences over the candidates [Brandt et al., 2016; Faliszewski et al., 2017; Rothe, 2016]. However, typically these scenarios concentrate solely on electing a committee in a single election to the neglect of a time dimension. This neglect results in serious limitations of the model. For instance, it is not possible to ensure a relationship (e.g., a small number of changes) between any two consecutive committees. We tackle this issue by introducing a multistage [Gupta et al., 2014] variant of the problem. In this variant, a sequence of voting profiles is given, and we seek a sequence of small committees, each collecting a reasonable number of approvals, such that the difference between consecutive committees is upper-bounded. For instance, assume a research community to seek organizers of a series of events (say those scheduled for next year). Contact Author The organizers must be fixed in advance to allow preparation time. Since events may differ in location and type, not every candidate fits equally well to every event. Thus, each member (agent) of the community is asked to name one suitable organizer for each event and, based on this, the goal is to determine a sequence of organizing committees (one for each event). Naturally, there are three constraints: (i) each committee is bounded in size, (ii) each committee has enough support from the agents, and (iii) at least a certain number of candidates in consecutive committees overlap to avoid a lack of knowledge transfer jeopardizing effectiveness. Initiating a study of so far overlooked multistage variant of multiwinner elections, we aim at understanding the computational complexity of the related computational problems. In particular we want to detect computationally tractable cases. Notably, our multistage setting introduces two new dimensions to the standard model of multiwinner elections: the relation between consecutive committees and the time. Thus, our second goal is to observe how these two dimensions affect the computational complexity of the introduced model. 1.1 Model and Examples We denote by N and N0 the natural numbers excluding and including zero, respectively. For a function f : A B, let f 1(B ) = {a A | f(a) B } for every B B. We use basic notation from graph theory [Diestel, 2010] and parameterized algorithmics [Cygan et al., 2015]. The main problem of this work is as follows. MULTISTAGE SNTV (MSNTV) Input: A set of agents A = {a1, . . . , an}, a set of candidates C = {c1, . . . , cm}, a sequence U = (u1, . . . , uτ) of τ voting profiles with ut : A C { }, t {1, . . . , τ}, and three integers k N, ℓ N0, and x N. Question: Is there a sequence (C1, . . . , Cτ) of committees Ct C such that for all t {1, . . . , τ} it holds true that |Ct| k and scoret(Ct) := |u 1 t (Ct)| x, and |Ct Ct+1| ℓ (1) holds true for all t {1, . . . , τ 1}? One may wonder why we chose an upper bound on k in the problem definition instead of specifying an exact constant committee size. While most natural instances will have solutions with committees of size exactly k, requiring them rules Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) FPT(Co. 1) FPT(Co. 1) MSNTV RMSNTV XP, W[2]-h.a FPT MSNTV RMSNTV p-NP-h(Th. 1) FPT MSNTV RMSNTV p-NP-h(Th. 1) p-NP-h(Th. 1) MSNTV RMSNTV p-NP-h(Th. 1) p-NP-h(Th. 1) MSNTV RMSNTV XP, W[1]-h.b XP, W[1]-hc MSNTV RMSNTV XP, W[1]-h.b FPT MSNTV RMSNTV XP, W[1]-h.b FPT MSNTV RMSNTV x + τ FPT( ) XP or FPT? MSNTV RMSNTV MSNTV RMSNTV m + τ FPT(Th. 7) FPT(Th. 7) MSNTV RMSNTV n + τ FPT(Th. 8) FPT(Th. 8) MSNTV RMSNTV k m n m + n x + τ n + τ ℓ ℓ+ n Figure 1: Overview of results for MSNTV and RMSNTV. Abbreviations p-NP-h and W[1]-h stand for, respectively, para-NP-hard and W[1]-hard. An arrow from one parameter p to another parameter p indicates that p can be upper bounded by some function in p (e.g., ℓ 2k, k m, or x n). The spiderweb diagram depicts further results being not displayed for readability (solid: conservative; dashed: revolutionary). a (Th. 2 & 4) b (Th. 2 & 5) c (Th. 3 & 5) [Kellerhals et al., 2021] out odd symmetric differences, e.g., ℓ= 1. All but one of our results easily translate to the setting with size k committees in each stage so that this decision is mainly a technical simplification. See a full version of the paper [Bredereck et al., 2020a] for a detailed discussion. SNTV comes from single non-transferable vote , to which our model boils down for a single stage. While most of our results transfer to the setting of general approval profiles (see Section 5), we use Plurality profiles, where each agent approves exactly one candidate, for four reasons. (I) Aiming for positive algorithmic results and for recognizing the influence of the basic model properties, it is most natural to start with the simplest relevant scenario. Even though SNTV is simple, (II) it is the only committee scoring rule serving finding representationand excellence-focused committees [Faliszewski et al., 2019]. Hence, it forms a good basis for a further exploration of our model for another rules reaching these two goals. (III) Plurality profiles are widely accepted in practice and form complex voting procedures (e.g., STV, the two-vote or two-stage voting systems used for the German or French parliament). (IV) Selecting a single candidate is only a weak (cognitive) barrier for human agents increasing the applicability of the model. In fact, our definition can be easily extended to more expressive scoring-based voting profiles. Motivated by respective requirements in many applications, Boehmer and Niedermeier [2021] propose a systematic study of (multiwinner) voting models that handle multiple preference profiles at once (e.g., when incorporating changes over time). Following their work, our paper provides one of the first models opening the field for new potential applications. Indeed, MSNTV models various possible practical scenarios, two of which we briefly sketch below. Buffet Selection. Suppose we are asked to organize the venue s breakfast buffet of a multiday event (like a workshop seminar). We offer different disjoint food bundles (candi- dates) for breakfast and ask the participants of the event to share their preferences of which bundle is their favorite for which day. Due to limited space, we can offer only at most some number of bundles in the buffet (committee) simultaneously. Moreover, to stay at low cost and to avoid food waste, we want that few bundles change from one day to the next. Clearly, given these constraints and the collected preferences (voting profiles), we want at all days to have a high number of participants whose voted bundle made it into the buffet. Exhibition Composition. When planning a multiday exhibition of sculptures (candidates) in a lobby of a hotel where we are enabled neither to show at once all the sculptures that we want to exhibit, nor to exchange arbitrarily many sculptures between consecutive exhibitions days (due to, e.g., limited capacity of transporting sculptures between some depot and the hotel). To nevertheless offer an enjoyable experience for numerous visitors, we ask the visitors to vote for each day they plan to visit for their favorite sculpture to be exhibited (to keep the poll simple and robust). Note that if we drop condition (1) (or, equivalently, set ℓ= 2k), then on the one hand, we have no control over changes between consecutive committees, yet on the other hand, we obtain a linear-time solvable problem. Thus, control comes with a computational cost, bound in the value of ℓ. To proceed with our second goal in particular, better understanding of condition (1), we additionally study a problem variant of MSNTV. We obtain this variant, referred to as REVOLUTIONARY MULTISTAGE SNTV (RMSNTV), by replacing (1) by |Ct Ct+1| ℓ. In words, in RMSNTV we request a change of size at least ℓbetween consecutive committees. By this, while we complemented the meaning of ℓ, it still expresses a control over the changes, and hence comes possibly again with a computational cost. We investigate whether the conservative (MSNTV) and the revolutionary (RMSNTV) variant differ, and if so, then how and why. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) 1.2 State of the Art and Our Contributions Our model follows the recently proposed multistage model [Eisenstat et al., 2014; Gupta et al., 2014], that led to several multistage problems [Bampis et al., 2018a; Bampis et al., 2019b; Fluschnik et al., 2019; Fluschnik et al., 2020; Chimani et al., 2021; Heeger et al., 2021; Bampis et al., 2019a; Bampis et al., 2018b; Kellerhals et al., 2021; Fluschnik, 2021] next to ours. Graph problems considered in the multistage model often study classic problems on temporal graphs (a sequence of graphs over the same vertices). While all the multistage problems known from literature cover the variant we call conservative, our revolutionary variant forms a novel submodel herein. Although, to the best of our knowledge our model is novel, other aspects of selecting multiple (sub)committees have been studied in (computational) social choice theory. The closest is a recent work of Bredereck et al. [2020b], who augment classic multiwinner elections with a time dimension. Accordingly, they consider selecting a sequence of committees. However, the major differences with our work are, first, that they do not allow agents (voters) to change their ballots over time and, second, that there are no explicit constraints on the differences between two successive committees. Freeman et al. [2017], Lackner [2020], and Parkes and Procaccia [2013] allow this but they consider an online scenario (in contrary to our problem that is offline). Finally, Aziz and Lee [2018] study a so-called subcommittee voting, where a final committee is a collection of several subcommittees. Their model, however, does not take time into account and requires that all subcommittees are mutually disjoint. Our Contributions. We present the first work in the multistage model that studies a problem from computational social choice and that compares the two cases that we call conservative and revolutionary. We prove MSNTV and RMSNTV to be NP-complete, even for two agents. We present a full parameterized complexity analysis of the two problems (see Figure 1 for an overview of our results; refer to a full version [Bredereck et al., 2020a] for a more detailed overview). Herein, the central tractability concept is fixed-parameter tractability: Given some parameter ρ, a problem is called fixed-parameter tractable (FPT) when it can be solved in f(ρ)|I|c time, where f is a computable function only depending on ρ, |I| is the instance size, and c is some constant. Less positively, we can sometimes only show XP-membership parameterized by ρ, which means that the problem can be solved in polynomial time when ρ is constant (but the degree of the polynomial may depend on ρ). Fixed-parameter tractability can often be excluded (under standard parameterized complexity assumptions) showing W[1]- or W[2]-hardness (using parameterized reductions which are similar to standard polynomial-time many-one reductions). MSNTV and RMSNTV are almost indistinguishable regarding their parameterized complexity, but when parameterized by ℓ, MSNTV is NP-hard and RMSNTV is contained in XP. Moreover, both problems are contained in XP and W[1]-hard regarding the parameter number τ of stages; Note that for many natural multistage problems (and even temporal graph problems), such a classification is unknown τ usually leads to para-NP-hardness. Our results further indicate that efficient data reductions (see Section 4 for the definition) in terms of polynomial-size problem kernelizations require a combination with τ: While combining the number of agents with the number of candidates allows for no polynomial-size problem kernel (unless NP co NP / poly), combining any of the two with τ yields kernels of polynomial size. Due to the space constraints, many details, marked by , can be found in a full version [Bredereck et al., 2020a] 2 Limits of Efficient Computation To prepare the ground for our algorithmic investigations of the introduced problems, we first settle the computational complexity lower bounds of MSNTV and RMSNTV. We begin with NP-hardness for quite restricted cases. Theorem 1 ( ). (i) MSNTV is NP-hard even for two agents, ℓ= 0, x = 1, and k = |C|/2. (ii) RMSNTV is NP-hard even for two agents, ℓ= 2k, x = 1, and k = |C|/2. Herein, Theorem 1(ii) follows from Theorem 1(i) due to the following result (which we also use later in this section). Lemma 1 ( ). There is an algorithm that, on every instance (A, C, U, k, ℓ, x) with ℓ= 0 and k = |C|/2 of MSNTV, computes an equivalent instance (A, C , U , k , ℓ , x) of RMSNTV with k = |C |/2, ℓ = 2k , and |U | = 2|U| + 1 in polynomial time. We point out that ℓ= 0 (MSNTV) and ℓ= 2k (RMSNTV) are not the only intractable cases ( ). Theorem 1 shows that MSNTV and RMSNTV remain NP-hard even for very specific scenarios. However, the restrictions in Theorem 1 do not deal with the size k of committee and the number τ of stages. This gives hope that instances in which these numbers are small could be solved more effectively. However, as we show in the remainder of this section, regarding parameters k and τ (and their combination) for MSNTV and parameter τ for RMSNTV we (presumably) cannot obtain running times for which the exponential blow-up is only depending on values of the parameters. Theorem 2 ( ). MSNTV is (i) W[1]-hard when parameterized by k + τ, even if ℓ= 0; (ii) W[2]-hard when parameterized by k, even if x = 1 and ℓ= 0. For Theorem 2(ii), we reduce from the W[2]-complete DOMINATING SET problem ( ).In the reduction behind the proof of Theorem 2(i), we employ Sidon sets defined subsequently. A Sidon set is a set S = {s1, s2, . . . , sb} of b natural numbers such that every pairwise sum of the elements in S is different. Sidon sets can be computed efficiently. Lemma 2. A Sidon set of size b can be computed in O(b) time if b is encoded in unary. Proof. Suppose we aim at obtaining a Sidon set S = {s1, . . . , sb}. For every i {1, . . . , b}, we compute si := 2ˆbi + (i2 mod ˆb), where ˆb is the smallest prime number greater than b [Erdös and Turán, 1941]. Thus, given ˆb, one can compute S in linear time. It remains to show how to find ˆb in linear time. Due to the Bertrand-Chebyshev [Tchebichef, 1852] theorem, we have Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) that ˆb < 2b. Searching all prime numbers smaller than 2b is doable in O(b) time (see, for example, an intuitive algorithm by Gries and Misra [1978]). Proof of Theorem 2(i). We reduce from MULTICOLORED CLIQUE that is W[1]-complete when parameterized by the solution size [Pietrzak, 2003; Fellows et al., 2009]. An instance ˆI of MULTICOLORED CLIQUE consists of a q-partite graph G = (V1 V2 Vq, E) and the task is to decide whether there is a set K of q pairwise connected vertices, each from a distinct part. For brevity, for some i, j {1, . . . , q}, i < j, let Ej i be a set of edges connecting vertices from parts Vi and Vj; thus, E = S i,j {1,...,q},i nτ, delete a candidate which is never approved. Intuitively, Reduction Rule 1 is correct because selecting a candidate which is never approved into a committee at some stage is not beneficial: it only increases the symmetric difference at the respective stage but not the committee s score. For RMSNTV, a similar approach applies. Reduction Rule 2. If m > max{n, k} τ, then delete a candidate that is never approved. It is not so clear that deleting an unapproved candidate is safe. Indeed, this can decrease the symmetric difference between some consecutive committees in a potential solution below ℓ. Still, assuming that m > nτ (otherwise, we simply output the original instance as the kernel), one can show that there must exist a candidate y that can replace the deleted candidate z = y in every committee that z was previously a member of. In the case of k n, applying Reduction Rule 2 exhaustively already yields the result from Theorem 8. Yet, the case of k > n and other details of the reduction rules require a more complex analysis ( ). Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) Theorems 7 & 8 emphasize the role of a short time-horizon in our problems as they both deal with instances with few stages. In passing, we point out that the above theorems also imply that the corresponding parameterized problems are in FPT. This is due to a well-known fact that a kernelization implies fixed-parameter tractability for the same parameter. 5 Conclusion and Discussion While our multivariate analysis revealed several intractability results, we emphasize that we also identified quite practically relevant tractable cases. In natural applications, such as electing committees serving for only few days/events, the number τ of stages is usually small. Even more, since planning too far in advance usually increases uncertainty. Furthermore, usually either the number n of voters or the number m of candidates is expected to be small (as suggested by quite a significant number of small-sized election in the preflib database). Additionally, in many elections the committee size k is not very large. Hence, our results for τ and for k (polynomial-time solvability for constant values) as well as for τ +n, for τ +m, or for m alone (fixed-parameter tractability) form a very positive message. Our results also underline the importance of the time aspect for preprocessing. For both MSNTV and RMSNTV, we show that efficient data reduction to size polynomial in the number of agents and the number of candidates is unlikely [Bredereck et al., 2020a]. Yet, combining any of the two parameters with the number of stages (see Theorems 7 & 8) allows for efficient (polynomial) data reduction. Moreover, the tractability result for τ seems generally insightful for the multistage community where problems usually remain computationally hard even a for constant number of stages. Additionally, the revolutionary multistage model may be relevant on its own and may pave the way for studying more new models where consecutive changes are both lowerand upper-bounded. This is already underlined by the study of Kellerhals et al. [2021] on several further problems like matching or s-t path taking up our revolutionary setup. Representation. Although it is naturally justified to start with the simplest meaningful model variant, our focus on SNTV might look restrictive. We stress that most results transfer easily to general Approval profiles (see WMSNTV): Replace each voter approving multiple candidates by multiple voters, each approving one candidate. Also basic scoring rules can be modeled: Create for each candidate c that receives score s(c) exactly s(c) votes for c. The main drawback is that now the parameter number n of voters corresponds to the total number of approvals or the total score sum, respectively; yet, most positive results still hold. It remains open whether a direct modeling of more complex preferences instead of blowing up in the number of voters can avoid blowing up the running time as well. Recently, it was shown that many of our results transfer to more complex voting rules.1 Deeper comparison of our models. As opposed to the single-stage case, both conservative and revolutionary com- 1Burak Arinalp. Multistage committee elections: Beyond plurality voting, March, 2021. Bachelor thesis. TU Berlin. mittee election over multiple stages are NP-complete, even for a constant number of agents. From a parameterized algorithmic point of view, computing a revolutionary committee is easier than a conservative one: When asking for committees to change for all but constantly many candidates, RMSNTV is polynomial time solvable, yet when asking for committees to change for only constant many candidates, MSNTV remains NP-hard. Finally, we wonder if RMSNTV parameterized by k + τ or ℓ+ τ admits a polynomial problem kernel, and whether RMSNTV parameterized by x + τ is in FPT. Future work. Further future work may include studying approximate or randomized algorithms for MSNTV and RMSNTV as well as experimentally testing our results. Moreover, further concepts and problems (e.g., bribery and manipulation) from computational social choice may be studied in the (conservative and revolutionary) multistage model. Note that, for instance, 2-Approval (each agent approves up to two candidates) in the conservative multistage setup is already NP-hard for one agent (similar to the proof of Theorem 1(i)). As a concrete future work, we want to prove that MSNTV is W[1]-hard when parameterized by k+n (inspired by a proof of Fluschnik et al. [2019]). Offline versus online. Importantly, our model is applicable for offline scenarios, in which preferences are collected in advance (e.g., by social media polls, Internet profiling, customer targeting). However, online scenarios also offer an interesting research direction, yet requiring significant changes in our original models. To observe this, consider an online scenario of selecting two committees such that in the first profile all committees are scoring equally high and in the second profile there is exactly one such a committee. In the worst case, every algorithm returns a solution requiring exchanging all candidates between the two selected committees; thus, no reasonable guarantee concerning the number of changes is achievable. To avoid such trivial cases, when studying the online setting, one needs to carry out significant model modifications. One way to proceed (following the multistage literature [Bampis et al., 2019a; Bampis et al., 2018b; Gupta et al., 2014]) is to introduce a goal function and consider the quality of the selected committees and the symmetric difference as soft constraints. Another way is to restrict the differences of consecutive profiles (analogously to Parkes and Procaccia [2013]). Such a correlation between consecutive profiles (greatly restricting the model) provides enough information to achieve some guarantees on the solution. Acknowledgements We thank the IJCAI 22 reviewers for their helpful comments. This work was started when all authors were with TU Berlin. TF was supported by the DFG, projects TORE (NI 369/18) and MATE (NI 369/17). AK was supported by the DFG, project AFFA (BR 5207/1 and NI 369/15), and by the European Research Council (ERC). This project has received funding from the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation programme (grant agreement No 101002854). Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) References [Aziz and Lee, 2018] H. Aziz and B. E. Lee. Sub-committee approval voting and generalized justified representation axioms. In Proc. of 1st AIES, pages 3 9, 2018. [Bampis et al., 2018a] E. Bampis, B. Escoffier, M. Lampis, and V. Th. Paschos. Multistage matchings. In Proc. of 16th SWAT, pages 7:1 7:13, 2018. [Bampis et al., 2018b] E. Bampis, B. Escoffier, and S. Mladenovic. Fair resource allocation over time. In Proc. of 17th AAMAS, pages 766 773, 2018. [Bampis et al., 2019a] E. Bampis, B. Escoffier, K. Schewior, and A. Teiller. Online multistage subset maximization problems. In Proc. of 27th ESA, pages 11:1 11:14, 2019. [Bampis et al., 2019b] E. Bampis, B. Escoffier, and A. Teiller. Multistage knapsack. In Proc. of 44th MFCS, pages 22:1 22:14, 2019. [Boehmer and Niedermeier, 2021] N. Boehmer and R. Niedermeier. Broadening the research agenda for computational social choice: Multiple preference profiles and multiple solutions. In Proc. of 20th AAMAS, pages 1 5, 2021. [Brandt et al., 2016] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016. [Bredereck et al., 2020a] R. Bredereck, T. Fluschnik, and A. Kaczmarczyk. Multistage committee election. Co RR, abs/2111.09049, 2020. [Bredereck et al., 2020b] R. Bredereck, A. Kaczmarczyk, and R. Niedermeier. Electing successive committees: Complexity and algorithms. In Proc. of 34th AAAI, pages 1846 1853, 2020. [Chimani et al., 2021] M. Chimani, N. Troost, and T. Wiedera. Approximating multistage matching problems. In Proc. of 32nd IWOCA, pages 558 570, 2021. [Cygan et al., 2015] M. Cygan, F. V Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. [Diestel, 2010] R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 2010. [Eisenstat et al., 2014] D. Eisenstat, C. Mathieu, and N. Schabanel. Facility location in evolving metrics. In Proc. of 41st ICALP, pages 459 470, 2014. [Erdös and Turán, 1941] P. Erdös and P. Turán. On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc., s1 16(4):212 215, 1941. [Faliszewski et al., 2017] P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon. Multiwinner voting: A new challenge for social choice theory. In U. Endriss, editor, Trends in Computational Social Choice. AI Access, 2017. [Faliszewski et al., 2019] P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon. Committee scoring rules: Axiomatic characterization and hierarchy. ACM Trans. Econ. Comput., 7(1):Article 3, 1 39, 2019. [Fellows et al., 2009] M. R. Fellows, D. Hermelin, F. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53 61, 2009. [Fluschnik et al., 2019] T. Fluschnik, R. Niedermeier, V. Rohm, and P. Zschoche. Multistage vertex cover. In Proc. of 14th IPEC, pages 14:1 14:14, 2019. [Fluschnik et al., 2020] T. Fluschnik, R. Niedermeier, C. Schubert, and P. Zschoche. Multistage s-t path: Confronting similarity with dissimilarity in temporal graphs. In Proc. of 31st ISAAC, pages 43:1 43:16, 2020. [Fluschnik, 2021] T. Fluschnik. A multistage view on 2satisfiability. In Proc. of 12th CIAC, pages 231 244, 2021. [Frank and Tardos, 1987] A. Frank and É. Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49 65, 1987. [Freeman et al., 2017] R. Freeman, S. M. Zahedi, and V. Conitzer. Fair and efficient social choice in dynamic settings. In Proc. of 26th IJCAI, pages 4580 4587, 2017. [Gries and Misra, 1978] D. Gries and J. Misra. A linear sieve algorithm for finding prime numbers. Commun. ACM, 21(12):999 1003, 1978. [Gupta et al., 2014] A. Gupta, K. Talwar, and U. Wieder. Changing bases: Multistage optimization for matroids and matchings. In Proc. of 41st ICALP, pages 563 575, 2014. [Heeger et al., 2021] K. Heeger, A. Himmel, F. Kammer, R. Niedermeier, M. Renken, and A. Sajenko. Multistage graph problems on a global budget. Theor. Comput. Sci., 868:46 64, 2021. [Kellerhals et al., 2021] L. Kellerhals, M. Renken, and P. Zschoche. Parameterized algorithms for diverse multistage problems. In Proc. of 29th ESA, pages 55:1 55:17, 2021. [Lackner, 2020] M. Lackner. Perpetual voting: Fairness in long-term decision making. In Proc. of 34th AAAI, pages 2103 2110, 2020. [Mattei and Walsh, 2017] N. Mattei and T. Walsh. A preflib.org retrospective: Lessons learned and new directions. In Ulle Endriss, editor, Trends in Computational Social Choice. AI Access, 2017. [Parkes and Procaccia, 2013] D. C. Parkes and A. D. Procaccia. Dynamic social choice with evolving preferences. In Proc. of 27th AAAI, page 767 773, 2013. [Pietrzak, 2003] K. Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci., 67(4):757 771, 2003. [Rothe, 2016] J. Rothe, editor. Economics and Computation. Springer, 2016. [Tchebichef, 1852] P. Tchebichef. Mémoire sur les nombres premiers. J. Math. Pures. Appl., 1(17):366 390, 1852. [Weihe, 1998] K. Weihe. Covering trains by stations or the power of data reduction. Proc. of 1st ALEX, pages 1 8, 1998. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)