# verifying_proportionality_in_temporal_voting__8e2875db.pdf

Verifying Proportionality in Temporal Voting

Edith Elkind1, Svetlana Obraztsova2, Jannik Peters3, Nicholas Teh4

1Northwestern University, USA 2Carleton University, Canada 3National University of Singapore, Singapore 4University of Oxford, UK edith.elkind@northwestern.edu, svetlanaobraztsova@cunet.carleton.ca, peters@nus.edu.sg, nicholas.teh@cs.ox.ac.uk

We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms.

1 Introduction

Consider a large corporation that has decided to improve its public image and to give back to the society by engaging in corporate philanthropy over the next decade. They will commit a small fraction of their profits towards supporting the efforts of a single charitable organization, to be selected on an annual basis. The management of this corporation decides to ask its customers, staff, and shareholders for input as to which charity organization it should select each year. Furthermore, the charity selected is of strategic importance it would directly impact the company s corporate image and hence profitability. As such, it is important for the company to ensure that the selection is representative of what its customers, staff, and shareholders care about and that it would create maximum impact for the charity organization they choose to support. It is natural to view this problem through the lens of multiwinner voting (Faliszewski et al. 2017; Elkind et al. 2017; Lackner and Skowron 2023): indeed, the corporation s goal is to select a fixed-size subset of candidates (in this case, charities) while respecting the preferences of agents (in this case, the customers, staff, and shareholders). In this context, several notions of representation and fairness have been proposed over the past decade, spanning across proportional representation (Elkind et al. 2017; Aziz and Lee 2020), diversity (Bredereck et al. 2018; Celis, Huang, and Vishnoi 2018), and excellence, amongst others (Lackner and Skowron 2023). Perhaps the most prominent among these is

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

the concept of justified representation (JR) and its variants (such as proportional justified representation (PJR) and extended justified representation (EJR)), which aim to capture the idea that large cohesive groups of voters should be fairly represented in the final outcome (Aziz et al. 2017; S anchez Fern andez et al. 2017; Aziz et al. 2018; Peters, Pierczy nski, and Skowron 2021; Brill and Peters 2023). However, the existing notions of fairness do not fully capture the complexity of our setting: traditional multiwinner voting models consider decisions made in a single round, with the entire set of candidates to fund (or candidates) being chosen simultaneously. In contrast, in our model the decisions are made over time, voters preferences may evolve, and a candidate may be chosen multiple times. This calls for adapting the JR axioms to the temporal setting. Temporal considerations in the multiwinner voting setting have been studied recently, most notably in the line of work known as perpetual voting (Lackner 2020; Lackner and Maly 2023) or temporal voting (Elkind, Neoh, and Teh 2024; Zech et al. 2024), and have broad real-world applications (see the recent survey by Elkind et al. (2024)). In particular, Bulteau et al. (2021) and, subsequently, Chandak et al. (2024) defined temporal analogues of the justified representation axioms and investigated whether existing multiwinner rules with strong axiomatic properties can be adapted to the temporal setting so as to satisfy the new axioms.

1.1 Our Contributions

We build upon the works of Bulteau et al. (2021) and Chandak et al. (2024), and focus on the complexity of verifying whether a given solution satisfies justified representation axioms. This task is important if, e.g., the outcome is fully or partially determined by external considerations, so explicitly using an algorithm to obtain an outcome with strong representation guarantees is not feasible, but representation remains an important concern. In multiwinner voting setting, the verification problem is known to be co NP-hard for PJR and EJR, but polynomial-time solvable for JR. We argue that the existing complexity results do not automatically transfer from the multiwinner setting to the temporal setting. However, we develop new proofs specifically tailored to the temporal setting, and show that in temporal elections all three properties are co NP-hard to verify, even under strong constraints on the structure of the input instance. Our complex-

The Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25)

ity result for JR shows that the temporal setting is strictly harder than the multiwinner setting. We complement our hardness results by fixed parameter tractability results as well as a polynomial-time algorithm for a natural special case of our model where candidates may join the election over time, but never leave, and voters preferences over available candidates do not change. We also develop an integer linear programming formulation for the problem of selecting an outcome that provides EJR and satisfies additional linear constraints on voters utilities, thereby establishing that this problem is fixed-parameter tractable with respect to the number of voters n. Finally, we (partially) answer an open question of Chandak et al. (2024), by showing that the prominent Greedy Cohesive Rule (Bredereck et al. 2019; Peters, Pierczy nski, and Skowron 2021) can be adapted to the temporal setting.

1.2 Related Work Our work belongs to the stream of research on perpetual, or temporal voting (Lackner 2020; Lackner and Maly 2023; Elkind, Neoh, and Teh 2024). This line of work started by considering temporal extensions of popular multiwinner voting rules and simple axiomatic properties. Bulteau et al. (2021) were the first to adapt notions of proportional representation to the temporal setting. They consider several temporal variants of JR and PJR, and show that a JR outcome can be computed in polynomial time even for the most demanding notion of JR among the ones they consider; for PJR, they prove the existence of an outcome satisfying the axiom, but their proof, while constructive, is based on an exponential-time algorithm. Page et al. (2022) proposed very similar concepts in the context of electing the executive branch. This work is extended by Chandak et al. (2024), who also propose a temporal variant of EJR, and show that several multiwinner voting rules that satisfy PJR/EJR in the standard model can be extended to the temporal setting so as to satisfy temporal variants of PJR/EJR. Bredereck et al. (2020; 2022) look at sequential committee elections whereby an entire committee is elected in each round, and impose constraints on the extent a committee can change, whilst ensuring that the candidates retain sufficient support from the electorate. Zech et al. (2024) study a similar model, but focus on the class of Thiele rules. Elkind et al. (2024) offer a systematic review of recent work on temporal voting. The temporal voting model captures apportionment with approval preferences (Brill et al. 2024; Delemazure et al. 2023), by endowing the voters with preferences that do not change over time. Other models in the social choice literature that include temporal elements include public decision-making (Alouf-Heffetz et al. 2022; Conitzer, Freeman, and Shah 2017; Fain, Munagala, and Shah 2018; Skowron and G orecki 2022; Lackner, Maly, and Nardi 2023; Masaˇr ık, Pierczy nski, and Skowron 2024), scheduling (Elkind, Kraiczy, and Teh 2022; Patro et al. 2022), resource allocation over time (Bampis, Escoffier, and Mladenovic 2018; Allouah et al. 2023; Elkind et al. 2024), online committee selection (Do et al. 2022), and dynamic social choice (Parkes and Procaccia 2013; Freeman, Zahedi, and Conitzer 2017).

Lackner et al. (2021) propose a framework for studying long-term participatory budgeting, and study fairness considerations in that setting.

2 Preliminaries

We start by introducing the basic model of multiwinner voting with approval ballots. A multiwinner approval election is given by a set of candidates P, a set of voters N, a list of approval sets (si)i2N, where si P for each i 2 N, and an integer k; the goal is to select a committee, i.e., a size-k subset of P. There is a large body of research on axioms and voting rules for this model (Lackner and Skowron 2023). In this work, we consider temporal voting with approval ballots, as defined by Bulteau et al. (2021) and Chandak et al. (2024). A temporal election is a tuple (P, N, , (si)i2N), where N = {1, . . . , n} is a set of voters, P = {p1, . . . , pm} is a set of m candidates, is the number of rounds, and, for each i 2 N, si = (si,1, si,2, . . . , si, ), where si,t P is the approval set of voter i in round t, which consists of candidates that i approves in round t. We refer to si as i s temporal preference; for brevity, we will sometimes omit the term temporal . An outcome of a temporal election (P, N, , (si)i2N) is a sequence o = (o1, . . . , o ) of candidates such that for every t 2 [ ] candidate ot 2 P is chosen in round t. A candidate may be selected multiple times, i.e., it may be the case that ot = ot0 for t 6= t0. A voter i s satisfaction from an outcome o is computed as sati(o) = |{t 2 [ ] : ot 2 si,t}|. An important concern in the multiwinner setting is group fairness, i.e., making sure that large groups of voters with similar preferences are represented by the selected committee. The most well-studied group fairness axioms are (in increasing order of strength) justified representation (JR) (Aziz et al. 2017), proportional justified representation (PJR) (S anchez-Fern andez et al. 2017), and extended justified representation (EJR) (Aziz et al. 2017). We will now formulate these axioms, as well as their extensions to the temporal setting; for the latter, we follow the terminology of Chandak et al. (2024). Definition 2.1 may appear syntactically different from the standard definitions of these notions, but it can easily be shown to be equivalent to them; further, it has the advantage of being easily extensible to the temporal setting.

Definition 2.1. For a multiwinner election (P, N, (si)i2N, k) and a group of voters N 0 N, we define the demand of N 0 as

mw(N 0) = min{βmw(N 0), γmw(N 0)}, where

βmw(N 0) = | \i2N 0 si| and γmw(N 0) = ! k |N 0|

A committee W P provides justified representation (JR) if for every N 0 N with mw(N 0) > 0 there is an i 2 N 0 such that |si \ W| > 0; it provides proportional justified representation (PJR) if for every N 0 N we have |([i2N 0si) \ W| mw(N 0), and it provides extended justified representation (EJR) if for every N 0 N there is an i 2 N 0 such that |si \ W| mw(N 0).

When extending these notions to the temporal setting, Bulteau et al. (2021) consider JR and PJR (but not EJR), each with three variants prefixed with static , dynamic all-periods-intersection , and dynamic someperiods-intersection ; where dynamic some-periods intersection is the most demanding of these. Chandak et al. (2024) extend this analysis to EJR, and focus on two variants of the axioms: dynamic all-period intersection , which they call weak JR/PJR/EJR, and dynamic some-period intersection , which they call JR/PJR/EJR1. In what follows, we use the terminology of Chandak et al. (2024). Just as in the multiwinner setting, for each group of voters N 0 we determine its demand (N 0), which depends both on the size of N 0 and on the degree of agreement among the group members. The axioms then require that the collective satisfaction of group members is commensurate with the group s demand. Definition 2.2. Given an election E = (P, N, , (si)i2N) and a group of voters N 0 N, we define the agreement of N 0 as the number of rounds in which all members of N 0 approve a common candidate:

β(N 0) = |{t 2 [ ] : \

i2N 0 si,t 6= ?}|.

We define the demand of a group of voters N 0 as

(N 0) = ! β(N 0) |N 0|

That is, if voters in N 0 agree in β rounds, they can demand a fraction of these rounds that is proportional to |N 0|. We now proceed to define temporal extensions of JR, PJR, and EJR, starting with their stronger versions Definition 2.3 (Justified Representation). An outcome o provides justified representation (JR) for a temporal election E = (P, N, , (si)i2N) if for every group of voters N 0 N with (N 0) > 0 we have sati(o) > 0 for some i 2 N 0. Definition 2.4 (Proportional Justified Representation). An outcome o provides proportional justified representation (PJR) for a temporal election E = (P, N, , (si)i2N) if for every group of voters N 0 N it holds that |{t 2 [ ] : ot 2 S i2N 0 si,t}| (N 0). Definition 2.5 (Extended Justified Representation). An outcome o provides extended justified representation (s-EJR) for a temporal election E = (P, N, , (si)i2N) if for every group of voters N 0 N there exists a voter i 2 N 0 with sati(o) (N 0). Note that EJR implies PJR, and PJR implies JR. It is instructive to compare Definitions 2.3 2.5 to Definition 2.1. In particular, one may wonder why we did not define the demand of a group N 0 in the temporal setting as (N 0) = min{β(N 0), |N 0|

n }, thereby decoupling the constraints on the size of the group and the level of agreement. Note that β(N 0) for all N 0 N and hence

1The conference version of their paper uses JR/PJR/EJR for the weaker version and strong JR/PJR/EJR for the stronger version; we use the terminology from the ar Xiv version of their paper.

(N 0) (N 0) for all N 0. However, the following example shows that if we were to use this definition of demand, even the JR axiom would be impossible to satisfy (whereas Chandak et al. (2024) show that every temporal election admits an outcome that provides EJR); see also the discussion in Section 5 of the paper by Chandak et al. (2024). Example 2.6. Let N = {1, . . . , 6}, and let T be the set of all size-2 subsets of N (so |T | = 15). Consider an election with voter set N, P = {x T }T 2T [ {yj}j=1,...,6, and = 3, where the voters approval sets have the following structure:

si,1 = {x T : i 2 T}, si,2 = si,3 = {yi} for all i 2 N.

For each group of voters N 0 with |N 0| = 2 we have β(N 0) = 1, as both voters in N 0 approve x N 0 in the first round. Moreover, |N 0|

n = 1, so (N 0) = 1. Hence, if we were to replace (N 0) with (N 0) in the definition of JR, we would have to ensure that for every pair of voters N 0 at least one voter in N 0 obtains positive satisfaction. However, there is no outcome o that accomplishes this: o1 is approved by at most two voters, and o2 and o3 are approved by at most one voter each, so for every outcome o there are two voters whose satisfaction is 0. That is, the modified definition of JR (and hence PJR and EJR) is unsatisfiable. On the other hand, we have β(N 0) = 3 if |N 0| = 1, β(N 0) = 1 if |N 0| = 2 and β(N 0) = 0 if |N 0| 3, and hence (N 0) = 0 for all N 0 N. Thus, every outcome o provides EJR (and hence PJR and JR). The axioms introduced so far apply to groups of voters with positive agreement. Bulteau et al. (2021) and Chandak et al. (2024) also consider weaker axioms, which only apply to groups of voters that agree in all rounds. Definition 2.7 (Weak Justified Representation/Proportional Justified Representation/Extended Justified Representation). Consider an outcome o for a temporal election E = (P, N, , (si)i2N). We say that o provides: weak justified representation (w-JR) if for every group of voters N 0 N with β(N 0) = , (N 0) > 0 it holds that sati(o) > 0 for some i 2 N 0. weak proportional justified representation (w-PJR) if for every group of voters N 0 N with β(N 0) = it holds that |{t 2 [ ] : ot 2 S

i2N 0 si,t}| (N 0). weak extended justified representation (w-EJR) if for every group of voters N 0 N with β(N 0) = there exists a voter i 2 N 0 with sati(o) (N 0). By construction, the weak JR/PJR/EJR axioms are less demanding than their regular counterparts: e.g., if = 10 and all voters agree on a candidate in each of the first 9 rounds, but each voter approves a different candidate in the last round, these axioms are not binding. Indeed, they are somewhat easier to satisfy: e.g., Chandak et al. (2024) show that a natural adaptation of the Method of Equal Shares (Peters and Skowron 2020) satisfies w-EJR, but not EJR. Therefore, in our work we consider both families of axioms.

3 Hardness Proofs In multiwinner elections, outcomes that provide EJR (and thus JR and PJR) can be computed in polynomial time (Aziz

et al. 2018; Peters and Skowron 2020). In contrast, the problem of verifying if a given outcome provides JR/PJR/EJR is considerably more challenging: while this problem is polynomial-time solvable for JR, it is co NP-hard for PJR and EJR (Aziz et al. 2017, 2018). In this section, we show that in the temporal setting the verification problem is co NP-hard even for (w-)JR. These results extend to (w-)PJR and (w-)EJR. We note that the hardness results for PJR and EJR in the multiwinner setting do not transfer immediately to the temporal setting. This is because the notion of agreement in our model is fundamentally different from the one in the multiwinner model: we focus on the number of rounds in which a group of voters agrees on a candidate, whereas in the multiwinner model the cohesiveness of a group is determined by the number of candidates the group members agree on. Suppose that we naively transform a multiwinner instance (P, N, (si)i2N, k), where k is the number of candidates to be elected, into a temporal instance with k rounds where voters approvals in each round are given by (si)i2N. Consider a group of voters N 0 that only agrees on a single candidate in the original instance (and therefore can demand at most one spot in the elected committee). In the temporal setting, voters in N 0 will agree on that candidate in all rounds, and therefore if N 0 is large, its demand can be substantial. Thus, we have to prove hardness of verifying PJR and EJR from scratch. Fortunately, the proofs of Theorems 3.1 and 3.2 apply to all three representation concepts that we consider.

Theorem 3.1. For each of X 2 {w-JR, w-PJR, w-EJR}, verifying whether an outcome provides X is co NP-complete. The hardness result holds for w-JR and w-PJR even if |P| = 3, and for w-EJR even if |P| = 2.

Proof. If an outcome o does not provide w-JR, this can be witnessed by a group of voters N 0 N with β(N 0) = , (N 0) > 0 such that sati(o) = 0 for all i 2 N 0. Hence, our problem is in co NP. Similarly, for w-PJR (respectively, w-EJR) it suffices to exhibit a group of voters N 0 such that β(N 0) = and |{t 2 [ ] : ot 2 [i2N 0si,t}| < (N 0) (respectively, β(N 0) = , sati(o) < (N 0) for all i 2 N 0). To prove co NP-hardness for w-JR, we reduce from the NP-hard problem CLIQUE. An instance of CLIQUE is given by a graph G = (V, E) with vertex set V and edge set E, together with a parameter ; it is a yes -instance if there exists a subset of vertices V 0 V of size that forms a clique, i.e., for all v, v0 2 V 0 we have {v, v0} 2 E. Given an instance (G, ) of CLIQUE with G = (V, E), where V = {v1, . . . , v }, we construct an election with a set of voters N = {1, . . . , } [ N0, where |N0| = ( 1) , a set of candidates P = {p1, p2, p3}, and = rounds. For each i 2 [ ], the preferences of voter i are given by:

{p2} if t = i; {p1, p2} if {vi, vt} 2 E; {p1} otherwise.

For each i 2 N0 and each t 2 [ ] we set si,t = {p3}. We claim that a set of voters N 0 [ ] satisfies β(N 0) = if and only if the set V 0 = {vi : i 2 N 0} forms a clique in G.

Indeed, let V 0 be a clique in G, and consider a round t 2 [ ]. If t 2 N 0, we have st,t = {p2}, si,t = {p1, p2} for all i 2 N 0 \ {t}, i.e., p2 2 \i2N 0si,t. On the other hand, if t 62 N 0, for each i 2 N 0 we have si,t = {p1, p2} if {vi, vt} 2 E and si,t = {p1} otherwise, so p1 2 \i2N 0si,t. Thus, for each t 2 [ ] the set \i2N 0si,t is non-empty. Conversely, if {vi, vj} 62 E for some i, j 2 N 0, i 6= j, then si,j = {p1}, whereas sj,j = {p2}, i.e., \i02N 0si0,j = ? and hence β(N 0) < . We claim that an outcome o = (p3, . . . , p3) fails to provide w-JR if and only if G contains a clique of size . Indeed, let V 0 be a sizeclique in G, and let N 0 = {i : vi 2 V 0}. We have argued that β(N 0) = and hence (V 0) = = 1 > 0; however, sati(o) = 0 for each i 2 N 0. For the converse direction, suppose there exists a subset of voters N 0 witnessing that o fails to provide w-JR. As sati(o) = 0 for each i 2 N 0, we have N 0 \ N0 = ?, i.e., N 0 [ ]. Moreover, β(N 0) = and hence the set V 0 = {vi : i 2 N 0} forms a clique in G. Then (N 0) > 0 can be re-written as |N 0|

1, i.e., |N 0| . As |V 0| = |N 0|, the set V 0 is a clique of size at least in G. The argument extends easily to w-PJR/w-EJR: if G contains a clique of size , then, as argued above, o fails to provide w-JR (and hence it fails to provide w-PJR/w-EJR), whereas if there are no cliques of size in G, there is no group of voters N 0 N with β(N 0) = , (N 0) > 0, so w-PJR/w-EJR is trivially satisfied. In the full version of the paper we provide a different proof for w-EJR, which applies even if |P| = 2.

For stronger versions of our axioms, we obtain a hardness result even for |P| = 2.

Theorem 3.2. For each of X 2 {JR, PJR, EJR}, verifying whether an outcome provides X is co NP-complete. The hardness result holds even if |P| = 2.

4 Tractability Results for |P | = 2

The hardness results in Theorems 3.1 and 3.2 hold even if the number of candidates |P| is small (3 for w-JR/w-PJR and 2 for w-EJR/JR/PJR/EJR). Now, for |P| = 1 verification is clearly easy: there is only one possible outcome, and for any group of voters N 0 this outcome provides satisfaction of at least β(N 0) (N 0) to all voters in N 0. To complete the complexity classification with respect to |P|, it remains to consider the complexity of verifying w-JR/w-PJR when |P| = 2.

Proposition 4.1. Given an election (P, N, , (si)i2N) with |P| = 2 and an outcome o, we can check in polynomial time whether o provides w-JR.

Proof. Assume that P = {p, q}. Suppose that a group of voters N 0 witnesses that o fails to provide w-JR. Then sati(o) = 0 for each i 2 N 0, but β(N 0) = . We say that a voter i is grumpy if in each round t she approves a single candidate, and this candidate is not ot, i.e., |si,t| = 1 and ot 62 si,t for all t 2 [ ]. Let G be the set of all grumpy voters, and note that β(G) = : in each round t, all grumpy voters approve the (unique) candidate in P \ {ot}.

Note that N 0 G: indeed, if a voter i is not grumpy, either she approves ot for some t 2 [ ], so sati(o) > 0, or she has si,t = ? for some t 2 [ ], which is not compatible with β(N 0) = . Hence, to check whether o provides w-JR it suffices to verify whether (G) = b |G|

It is not clear if Proposition 4.1 can be extended to w PJR: to verify w-PJR, it is no longer sufficient to focus on grumpy voters. We conjecture that verifying w-PJR remains hard even for |P| = 2 (recall that, by Theorem 3.1, this is the case for w-EJR). Observe that for the election constructed in the proof of Theorem 3.1 we have si,t 6= ? for all i 2 N, t 2 [ ]. In contrast, in the election constructed in the proof of Theorem 3.2 the approval sets si,t may be empty. It turns out that if we require that si,t 6= ? for all i 2 N, t 2 [ ] then for |P| = 2 the problem of verifying JR becomes easy; under this assumption, if sati(o) = 0 for all i 2 N 0 then all voters in N 0 are grumpy, so it suffices to check if (G) = 0.

Proposition 4.2. Given an election (P, N, , (si)i2N) with |P| = 2 and si,t 6= ? for all i 2 N, t 2 [ ] and an outcome o, we can check in polynomial time whether o provides JR.

Again, it is not clear if Proposition 4.2 extends to (w-)PJR and (w-)EJR; we conjecture that the answer is no .

Remark 4.3. The proofs of Propositions 4.1 and 4.2 go through if, instead of requiring |P| = 2, we require that in each round there are at most two candidates that receive approvals from the voters, i.e., | [i si,t| 2 for each t 2 [ ].

Proposition 4.2 shows that, for |P| = 2, requiring each voter to approve at least one candidate in each round reduces the complexity of checking JR considerably. However, this requirement only helps if |P| is bounded. Indeed, we can modify the construction in the proof of Theorem 3.2 by creating a set of additional candidates P N = {pi}i2N and modifying the preferences so that whenever si,t = ? in the original construction, we set si,t = {pi}. The new candidates do not change the agreement of any voter group, so the rest of the proof goes through unchanged.

Proposition 4.4. For each of X 2 {JR, PJR, EJR}, verifying whether an outcome provides X is co NP-complete, even if si,t 6= ? for all voters i 2 N and all rounds t 2 [ ].

It remains an open question whether verifying that a given outcome provides JR/PJR/EJR remains co NP-complete if all approval sets are non-empty and the size of the set P is a fixed constant greater than 2; we conjecture that this is indeed the case, but we were unable to prove this.

5 Parameterized Complexity We have seen that the verification problem becomes easier if the size of the candidate set m = |P| is very small. We will now consider other natural parameters of our problem, such as the number of voters n and the number of rounds , and explore the complexity of the verification problem with respect to there parameters.

Proposition 5.1. For each X 2 {(w-)JR, (w-)PJR, (w-)EJR}, checking if an outcome provides X is FPT with respect to n.

The proof of the following proposition, as well as the results in Section 6, make use of the following observation.

Observation 5.2. Let X be a multiset of real numbers, and let r |X| be a positive integer. Let Y and Z be two subsets of X with |Y | = |Z| = r such that Z consists of the r smallest elements of X (for some way of breaking ties). Then for each z 2 Z we have z maxy2Y y.

Proposition 5.3. For each X 2 {(w-)JR, (w-)PJR, (w-)EJR}, checking if an outcome provides X is FPT with respect to the combined parameter (m, ) and XP with respect to .

Proof. Given an outcome o, we proceed as follows. For each possible outcome o0 and each subset T [ ], compute the set No0,T = {i 2 N : o0 t 2 si,t for all t 2 T}; this set consists of all voters who approve the outcome o0 in each of the rounds in T. We then sort the voters in No0,T according to their satisfaction under o in non-decreasing order, breaking ties lexicographically; for each r = 1, . . . , |No0,T |, let N r o0,T denote the set that consists of the first r voters in this order. To verify EJR, for each r = 1, . . . , |No0,T | we determine whether there is an i 2 N r o0,T such that sati(o) b r

n |T|c. We claim that o provides EJR if and only if it passes these checks for all possible choices of o0, T and r. Indeed, suppose o fails this check for some o0, T and r, and let N 0 = N r o0,T . By construction, β(N 0) |T| and |N 0| = r, so (N 0) b r

n |T|c, i.e., N 0 is a witness that EJR is violated. Conversely, suppose that o fails EJR. Then there is a set of voters N 0 such that maxi2N 0 sati(o) < (N 0). By definition of β(N 0), there exists a set T 0 [ ], |T 0| = β(N 0), and an outcome o0 such that for each t 2 T 0 and each i 2 N 0 it holds that o0 t 2 si,t; note that this implies N 0 No0,T 0. Let r = |N 0|, and consider the set N r o0,T 0. Observe that β(N r o0,T 0) |T 0| = β(N 0) and |N r o0,T 0| = |N 0| = r, so (N r o0,T 0) (N 0). On the other hand, by applying Observation 5.2 to the multisets {sati(o) : i 2 N 0} and {sati(o) : i 2 N r o0,T 0}, we conclude that for each i 2 N r o0,T 0 it holds that sati(o) maxi2N 0 sati(o) < (N 0) (N r o0,T 0). That is, N r o0,T 0 is also a witness that o fails to provide EJR. As our algorithm checks N r o0,T 0, it will be able to detect that o fails to provide EJR. For PJR, instead of checking whether sati(o) b r

n |T|c for some i 2 N r o0,T , we check that |{t 2 [ ] : ot 2 [i2N r o0,T si,t}| b r

n |T|c, and for JR we check whether b r

n |T|c 1 implies that sati(o) 1 for some i 2 N r o0,T . For w-JR, w-PJR and w-EJR, the algorithm can be simplified: instead of iterating through all T [ ], it suffices to consider T = [ ]. The rest of the argument goes through without change. The bound on the runtime follows, as we have m possibilities for o0 and 2 possibilities for T, and we process each pair (o0, T) in polynomial time.

Our XP result with respect to is tight, at least for weak versions of the axioms: our next theorem shows that checking whether an outcome provides w-JR, w-PJR, or w-EJR is W[1]-hard with respect to . This indicates that an FPT (in ) algorithm does not exist unless FPT = W[1].

Theorem 5.4. For each of X 2 {w-JR, w-PJR, w-EJR}, verifying whether an outcome provides X is W[1]-hard with respect to .

6 Monotonic Preferences Since the problem of checking whether an outcome provides (w-)JR, (w-)PJR, or (w-)EJR is intractable in general, it is natural to seek a restriction on voters preferences that may yield positive results. In particular, a natural restriction in this context is monotonicity: once a voter approves a candidate, she continues to approve it in subsequent rounds. Formally, we will say that an election (P, N, , (si)i2N) is monotonic if for any two rounds t, t0 2 [ ] with t < t0, each p 2 P and each i 2 N it holds that p 2 si,t implies p 2 si,t0. Monotonic elections occur if, e.g., candidates join the candidate pool over time, but never leave, and the voters preferences over the available candidates do not change. Such preferences can also arise in settings where the candidates improve over time: e.g., job candidates become more experienced. By reversing the time line, this can also model candidates that deteriorate over time (e.g., planning family meals from available ingredients). We first note that verifying weak JR/PJR/EJR in monotonic elections is easy. Theorem 6.1. Given a monotonic election (P, N, , (si)i2N) togther with an outcome o, for each of X 2 {w-JR, w-PJR, w-EJR} we can decide in polynomial time whether o provides X. For strong notions of justified representation, we also obtain easiness-of-verification results, though the proof requires an additional level of complexity. Theorem 6.2. Given a monotonic election (P, N, , (si)i2N) together with an outcome o, for each of X 2 {JR, PJR, EJR} we can decide in polynomial time whether o provides X.

7 Finding EJR Outcomes So far, we focused on checking whether an outcome provides a representation guarantee. We will now switch gears, and explore the problem of finding a fair outcome.

7.1 Greedy Cohesive Rule Provides EJR Chandak et al. (2024) show that every temporal election admits an outcome that provides EJR, by adapting the PAV rule (Thiele 1895) and its local search variant ls-PAV (Aziz et al. 2018) from the multiwinner setting to the temporal setting; the local search-based approach results in a rule that is polynomial-time computable. However, they leave it as an open question whether another prominent voting rule, namely, the Greedy Cohesive Rule (GCR) (Bredereck et al. 2019; Peters, Pierczy nski, and Skowron 2021) can be adapted to the temporal setting so as to provide EJR. Bulteau et al. (2021) describe an algorithm that is similar in spirit to GCR and constructs a PJR outcome; however, unlike GCR, the algorithm of Bulteau et al. (2021) proceeds in two stages. We will now describe a two-stage procedure that is inspired by the algorithm of Bulteau et al. (but differs from it) and always finds EJR outcomes.

Algorithm 1: 2-Stage Greedy Cohesive Rule.

1 Input: Set of voters N = {1, . . . , n}, set of candidates P = {p1, . . . , pm}, number of rounds , voters approval sets (s1, . . . , sn);

2 o (p1, . . . , p1);

4 V := {V N : β(V ) > 0};

6 while V 6= ? do

7 Select a set V 2 arg max V 2V (V ) with ties broken arbitrarily;

8 V+ V+ [ {V };

9 for V 0 2 V do

10 if V \ V 0 6= ? then

11 V V \ {V 0};

12 Sort V+ as V1, . . . , Vq so that β(V1) β(Vq);

13 for k = 1, . . . , q do

14 Let T 0 be a subset of {t 2 T : \i2Vksi,t 6= ?} of size (Vk);

15 T T \ T 0;

16 for t 2 T 0 do

17 Pick p 2 \i2Vksi,t and set ot p;

18 return outcome o;

Theorem 7.1. Algorithm 1 always outputs an outcome that provides EJR, and runs in time O(2n poly(n, m, )).

Proof. The bound on the running time of the algorithm follows from the fact that the size of V is O(2n), and the amount of computation performed for each subset in V is polynomial in the input size. We now focus on correctness. Note that all sets in V+ are pairwise disjoint: for each k 2 [q], when we place Vk in V+, we remove all sets that intersect Vk from V, and therefore no such set can be added to V+ at a future iteration. We will use this observation to argue that, while processing the sets in V+, for each set Vk we consider there exist (Vk) rounds in which all members of Vk agree on at least one candidate. Suppose for a contradiction that this is not the case, and let k 2 [q] be the first index such that there are fewer than (Vk) slots available out of the β(Vk) rounds voters in Vk agree on. This means that strictly more than β(Vk) (Vk) of these slots have been taken up in previous iterations, and hence Pk r=1 (Vr) > β(Vk). Since β(Vk) β(Vr) for all r k, the inequality implies

r=1 (Vr) > β(Vk),

(1) and hence Pk r=1 |Vr| > n, a contradiction with the fact the groups V1, . . . , Vk 1, Vk are pairwise disjoint, and |V | = n. We conclude that for each V 2 V+ it holds that sati(o) (V ) for each i 2 V . Hence, no set in V+ can be a witness that EJR is violated. Further, each set V 2 2N \ V has β(V ) = 0 and hence (V ) = 0, so it cannot witness that EJR is violated either. It remains to consider sets in V \ V+.

Fix a set V 0 2 V \ V+, and suppose that it was deleted from V when some V was placed in V+ (and hence (V 0) (V )). Moreover, when processing V+, the algorithm ensured that the satisfaction of each voter i 2 V is at least (V ) = b β(V ) |V |

n c. As V \ V 0 6= ?, this means that the satisfaction of some voter i 2 V 0 is at least (V ) (V 0). Thus, V 0 cannot be a witness that EJR is violated.

We note that for monotonic elections Algorithm 1 can be modified to run in polynomial time. Indeed, the proof of Theorem 6.2 shows that, when verifying representation axioms, it suffices to consider sets of the form N z p,t (defined in the proof; see the full version of the paper for details). If we modify Algorithm 1 so that initially it only places sets of this form in V, it will only have to consider O(m n) sets, each of them in polynomial time; on the other hand, by Theorem 6.2 its output would still provide EJR. While GCR runs in exponential time, it is a simple rule that can often be used to prove existence of fair outcomes; e.g., in the multiwinner setting, its outputs satisfy the stronger FJR axiom (Peters, Pierczy nski, and Skowron 2021), which is not satisfied by PAV or the Method of Equal Shares (MES). While FJR seems difficult to define for the temporal setting, this remains an interesting direction for future work, and GCR may prove to be a relevant tool. Moreover, one may want to combine JR-like guarantees with additional welfare, coverage, or diversity guarantees; the associated problems are likely to be NP-hard, so GCR may be a useful starting point for an approximation or a fixedparameter algorithm (that may be more practical than the ILP approach). Finally, compared to PAV and MES, GCR may be easier to adapt to general monotone valuations (this is indeed the case in the multiwinner setting).

7.2 An ILP For Finding EJR Outcomes We will now describe an algorithm for finding EJR outcomes that is based on integer linear programming (ILP). While this algorithm does not run in polynomial time, it is very flexible: e.g., we can easily modify it so as to find an EJR outcome that maximizes the utilitarian social welfare, or provides satisfaction guarantees to individual voters.

Theorem 7.2. There exists an integer linear program (ILP) whose solutions correspond to outcomes that provide EJR; the number of variables and the number of constraints of this ILP are bounded by a function of the number of voters n.

The following corollary illustrates the power of the ILPbased approach.

Corollary 7.3. There is an FPT algorithm with respect to the number of voters that, given an election E = (P, N, , (si)i2N) and a set of integers δ1, . . . , δn, decides whether there exists an EJR outcome of E that guarantees satisfaction δi to voter i for each i 2 N, and, if yes, finds an outcome that maximizes the utilitarian social welfare among all outcomes with this property.

Proof. The ILP in the proof of Theorem 7.2 contains an expression encoding each voter s satisfaction. We can modify

this ILP by adding constraints saying that the satisfaction of voter i is at least δi, and adding a goal function that maximizes the sum of voters satisfactions. The resulting ILP admits an algorithm that is FPT with respect to n by the classic result of Lenstra (1983).

We note that, while Chandak et al. (2024) show that ls PAV rule can find EJR outcomes in polynomial time, their approach cannot handle additional constraints on voters welfare; hence Corollary 7.3 is not implied by their result.

7.3 An Impossibility Result for EJR in the (Semi-)Online Setting In their analysis, Chandak et al. (2024) distinguish among (1) the online setting, where the number of rounds is not known, voters preferences are revealed round-by-round, and ot is selected as soon as all (si,t)i2N are revealed, (2) the semi-online setting, where is known, but preferences are revealed round-by-round and an outcome for a round needs to be chosen as soon as the preferences for that round have been revealed, and (3) the offline setting, where we select the entire outcome o given full access to (si)i2N. The PAV rule and its local search variant, the GCR rule and the ILP approach only work in the offline setting. In contrast, Chandak et al. (2024) show that a variant of MES satisfies w-EJR in the semi-online setting, but not in the online setting. They left open the existence of rules satisfying EJR in the semionline setting. Here, we resolve this open question and show that no rule can satisfy EJR in the semi-online setting (and hence in the online setting).

Proposition 7.4. No rule satisfies EJR in the semi-online setting.

8 Conclusion We have explored the complexity of verifying whether a given outcome of a temporal election satisfies one of the six representation axioms considered by Chandak et al. (2024). We have obtained co NP-hardness results even for very restricted special cases of this problem: e.g., for strong versions of the axioms verification remains hard even if there are just two candidates. We complement these hardness results with parameterized complexity results and a positive result for a structured setting, where candidates join the pool over time and never leave. We also describe an ILP that can be used to find outcomes that provide EJR and satisfy additional constraints. Finally, we answer an open question of Chandak et al. (2024), by showing that a variant of the Greedy Cohesive Rule provides EJR. Possible directions for future work (in addition to open problems listed in Section 4) include considering stronger variants of proportionality, such as FJR (Peters, Pierczy nski, and Skowron 2021) or core stability (Aziz et al. 2017), exploring other domain restrictions, and extending the temporal framework to the broader setting of participatory budgeting (Aziz and Lee 2021; Lackner, Maly, and Rey 2021; Peters, Pierczy nski, and Skowron 2021).

Acknowledgments Edith Elkind was supported by the AI Programme of The Alan Turing Institute and an EPSRC Grant EP/X038548/1. Jannik Peters was supported by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001.

References Allouah, A.; Kroer, C.; Zhang, X.; Avadhanula, V.; Bohanon, N.; Dania, A.; Gocmen, C.; Pupyrev, S.; Shah, P.; Stier-Moses, N.; and Taarup, K. R. 2023. Fair Allocation Over Time, with Applications to Content Moderation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 25 35. Alouf-Heffetz, S.; Bulteau, L.; Elkind, E.; Talmon, N.; and Teh, N. 2022. Better Collective Decisions via Uncertainty Reduction. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 24 30. Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justified Representation in Approval Based Committee Voting. Social Choice and Welfare, 48: 461 485. Aziz, H.; Elkind, E.; Huang, S.; Lackner, M.; S anchez Fern andez, L.; and Skowron, P. 2018. On the Complexity of Extended and Proportional Justified Representation. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), 902 909. Aziz, H.; and Lee, B. 2021. Proportionally Representative Participatory Budgeting with Ordinal Preferences. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 5110 5118. Aziz, H.; and Lee, B. E. 2020. The expanding approvals rule: Improving proportional representation and monotonicity. Social Choice and Welfare, 54(1): 1 45. Bampis, E.; Escoffier, B.; and Mladenovic, S. 2018. Fair Resource Allocation Over Time. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 766 773. Bredereck, R.; Faliszewski, P.; Igarashi, A.; Lackner, M.; and Skowron, P. 2018. Multiwinner Elections with Diversity Constraints. In Proceedings of the 32th AAAI Conference on Artificial Intelligence (AAAI), 933 940. Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; and Niedermeier, R. 2019. An Experimental View on Committees Providing Justified Representation. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 109 115. Bredereck, R.; Fluschnik, T.; and Kaczmarczyk, A. 2022. When Votes Change and Committees Should (Not). In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 144 150. Bredereck, R.; Kaczmarczyk, A.; and Niedermeier, R. 2020. Electing Successive Committees: Complexity and Algorithms. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 1846 1853. Brill, M.; G olz, P.; Peters, D.; Schmidt-Kraepelin, U.; and Wilker, K. 2024. Approval-based apportionment. Mathematical Programming, 203: 77 105.

Brill, M.; and Peters, J. 2023. Robust and Verifiable Proportionality Axioms for Multiwinner Voting. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), 301.

Bulteau, L.; Hazon, N.; Page, R.; Rosenfeld, A.; and Talmon, N. 2021. Justified Representation for Perpetual Voting. IEEE Access, 9: 96598 96612.

Celis, L. E.; Huang, L.; and Vishnoi, N. K. 2018. Multiwinner Voting with Fairness Constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 144 151.

Chandak, N.; Goel, S.; and Peters, D. 2024. Proportional Aggregation of Preferences for Sequential Decision Making. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), 9573 9581.

Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair Public Decision Making. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), 629 646.

Cygan, M.; Fomin, F. V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; and Saurabh, S. 2015. Parameterized algorithms, volume 5. Springer.

Delemazure, T.; Demeulemeester, T.; Eberl, M.; Israel, J.; and Lederer, P. 2023. Strategyproofness and Proportionality in Party-Approval Multiwinner Elections. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), 5591 5599.

Do, V.; Hervouin, M.; Lang, J.; and Skowron, P. 2022. Online Approval Committee Elections. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 251 257.

Elkind, E.; Faliszewski, P.; Skowron, P.; and Slinko, A. 2017. Properties of multiwinner voting rules. Social Choice and Welfare, 48: 599 632.

Elkind, E.; Kraiczy, S.; and Teh, N. 2022. Fairness in Temporal Slot Assignment. In Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT), 490 507.

Elkind, E.; Lam, A.; Latifian, M.; Neoh, T. Y.; and Teh, N. 2024. Temporal Fair Division of Indivisible Items. ar Xiv preprint ar Xiv:2410.14593.

Elkind, E.; Neoh, T. Y.; and Teh, N. 2024. Temporal Elections: Welfare, Strategyproofness, and Proportionality. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), 3292 3299.

Elkind, E.; Obraztsova, S.; and Teh, N. 2024. Temporal Fairness in Multiwinner Voting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), 22633 22640.

Fain, B.; Munagala, K.; and Shah, N. 2018. Fair Allocation of Indivisible Public Goods. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), 575 592.

Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017. Multiwinner Voting: A New Challenge for Social Choice Theory. In Trends in Computational Social Choice, chapter 2, 27 47.

Freeman, R.; Zahedi, S. M.; and Conitzer, V. 2017. Fair and Efficient Social Choice in Dynamic Settings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 4580 4587. Garey, M. R.; Johnson, D. S.; and Stockmeyer, L. J. 1976. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3): 237 267. Lackner, M. 2020. Perpetual Voting: Fairness in Long-Term Decision Making. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2103 2110. Lackner, M.; and Maly, J. 2023. Proportional Decisions in Perpetual Voting. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), 5722 5729. Lackner, M.; Maly, J.; and Nardi, O. 2023. Free-Riding in Multi-Issue Decisions. In Proceedings of the 22nd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2040 2048. Lackner, M.; Maly, J.; and Rey, S. 2021. Fairness in Long Term Participatory Budgeting. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 299 305. Lackner, M.; and Skowron, P. 2023. Multi-Winner Voting with Approval Preferences. Springer. Lenstra Jr, H. W. 1983. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4): 538 548. Masaˇr ık, T.; Pierczy nski, G.; and Skowron, P. 2024. A Generalised Theory of Proportionality in Collective Decision Making. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), 734 754. Page, R.; Shapiro, E.; and Talmon, N. 2022. Electing the Executive Branch. ar Xiv preprint ar Xiv:2009.09734. Parkes, D.; and Procaccia, A. 2013. Dynamic Social Choice with Evolving Preferences. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), 767 773. Patro, G. K.; Jana, P.; Chakraborty, A.; Gummadi, K. P.; and Ganguly, N. 2022. Scheduling Virtual Conferences Fairly: Achieving Equitable Participant and Speaker Satisfaction. In Proceedings of the ACM Web Conference (WWW) 2022, 2646 2656. Peeters, R. 2003. The maximum edge biclique problem is NP-complete. Discrete Applied Mathematics, 131(3): 651 654. Peters, D.; Pierczy nski, G.; and Skowron, P. 2021. Proportional Participatory Budgeting with Additive Utilities. In Advances in Neural Information Processing Systems (Neur IPS), volume 34, 12726 12737. Peters, D.; and Skowron, P. 2020. Proportionality and the limits of welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), 793 794. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J.; Basanta Val, P.; and Skowron, P. 2017. Proportional Justified Representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 670 676.

Skowron, P.; and G orecki, A. 2022. Proportional Public Decisions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 5191 5198. Thiele, T. 1895. Om Flerfoldsvalg. Oversigt Over Det Kongelige Danske Videnskabernes Selskabs Forhandlinger, 415 441. Zech, V.; Boehmer, N.; Elkind, E.; and Teh, N. 2024. Multiwinner Temporal Voting with Aversion to Change. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), 3236 3243.