Algorithmics of Egalitarian versus Equitable Sequences of Committees

1 Prologue

Consider the very basic committee selection scenario where every agent may nominate one candidate for the committee. The only committee that gives certain satisfaction to each agent, which we call egalitarian committee, consist of all nominated candidates. A committee that gives each agent the same satisfaction, which we call equitable committee, would also have to consist of all nominated candidates, or of no candidate at all. Either outcome appears impractical. So, aiming for an equitable or egalitarian committee seems pointless in this setting.

With a small twist, however, it becomes a meaningful yet unstudied case: what happens when the agents can nominate candidates in different levels, or, to put differently, for different points in time? Are there non-trivial egalitarian or equitable committee sequences? Can we simultaneously guarantee a certain minimum number of nominations in each level? And if so, what is the computational complexity we have to face when trying to find such a committee?

What probably appears abstract at first glace is indeed quite natural: when selecting the menu for some event, each participant may nominate a food option (with levels being courses), when organizing a panel, each organizer may nominate a session topic (with levels being days with different topic frames), or when planning activities as sketched next.

Example 1. We want to bring together six agents at some weekend trip. Each one announces what they want to do on each day of the weekend. They will only form a group if each of them is happy with at least one of the chosen activities over all days. Possible activities are: dancing (D), hiking (H), museum (M), restaurant (R), sightseeing (S), and theater (T). The agents' preferences are given in Fig. 1. Assume we can choose two activities per day. To get an overall good satisfaction, we aim to ensure that a strict majority of agents is satisfied each day (in addition to requiring each agent being satisfied at least once). To realize this, we must select {D, S} for day one and {M,H} for day two. While this egalitarian committee sequence indeed maximizes satisfaction per day, the agents might not find this fair, because some are satisfied on two days while others are only satisfied once. We can fix this by aiming to ensure that each agent is satisfied exactly once and only a weak majority of agents is satisfied each day. To realize this, we select {D,M} for day one and {M, T} for day two, which gives an equitable committee sequence.

More formally, we study the following two problems and analyze their (parameterized) complexity with respect to the following parameters and their combinations: number n of agents, number m of candidates, number τ of levels (e.g., time points), size k of each committee, number x of nominations the selected committee shall receive in each level, and number y of successful nominations each agent makes in total. 1

1 In Example 1, we have n = m = 6, τ = k = 2, y = 1, as well as x = 4 in the egalitarian and x = 3 in the equitable case.

EGALITARIAN COMMITTEE SEQUENCE ELECTION (GCSE) a sequence of nomination profiles U = (u1, . . . , uτ)

Input: A set A of n agents, a set C of m candidates, with ut∶ A → C ∪ {∅}, and three integers k, x, y ∈ N0.

Question: Is there a sequence C1, . . . ,Cτ of subsets of C each of size at most k such that

We also refer to the left-hand side of (1) and of (2) as committee and agent score, respectively. EQUITABLE COMMITTEE SEQUENCE ELECTION (QCSE) denotes the variant where we replace "≥" with "=" in (2).

RelatedWork. From themotivations perspective, our model aims to select committees, which is a well-studied core topic of computational social choice. The three main goals of selecting committees discussed in the literature are individual excellence, proportionality, and diversity (cf. Elkind et al. [2017]). The latter is usually reached by egalitarian approaches [Aziz et al., 2018] (on which we also focus), where the quality of a committee is defined by the least satisfied voter.

Our model considers preferences with more than one level. Related, in the multistage setting [Eisenstat et al., 2014; Gupta et al., 2014] one finds committee election problems with multiple preferences for each agent [Kellerhals et al., 2021; Bredereck et al., 2022]. While they also require a minimum satisfaction in each time step, they do not require a minimum satisfaction of agents. Instead, they have explicit constraints on the differences between two successive committees.

Also other aspects of selecting multiple (sub)committees have been studied before. Bredereck et al. [2020b] augment classic multiwinner elections with a time dimension, also selecting a sequence of committees. The crucial differences with our work is that they do not allow agents (voters) to change their ballots over time. While Freeman et al. [2017], Lackner [2020], and Parkes and Procaccia [2013] allow this, they consider online scenarios in contrary to our offline scenario. Moreover, they mostly focus on single-winner decisions and evaluate the quality of solutions quite differently. Bulteau et al. [2021] also consider an offline setting but aim for justified representation, a fairness notion for groups of individuals.

Our Contributions. Fig. 2 gives a results overview from our parameterized analysis. We highlight the following: Each of GCSE and QCSE is solvable in uniform polynomial time

• for constantly many constant-size committees, but not for constantly many committees where each must have a committee score of at least a given constant (unless P = NP); or
• for a constant number of agents, but not for a constant number of candidates (unless P = NP).

We discovered the following differences between the egalitarian and equitable case:

• For two stages, GCSE is NP-hard while QCSE is polynomial-time solvable (QCSE is NP-hard for three stages);
• For parameter n+y, GCSE admits a polynomial problem kernel while QCSE presumably does not;
• When k = m, GCSE is polynomial-time solvable, while QCSE is still NP-hard in this case. Notably, GCSE is NP-hard even if k = m - 1.

Due to the space constraints, many details, marked by ⭑, can be found in a full version of this paper.

2 Preliminaries and Basic Observations

We use standard notation from parameterized algorithmics [Cygan et al., 2015]. A problem with parameter p is fixed-parameter tractable (in the class FPT), if it can be solved in f(p) ⋅ sc , where s denotes the input size, for some constant c and computational function f only depending on p; i.e., it can be solved in uniform polynomial time O(sc ) for every constant value of p. A (decidable) parameterized problem is fixed-parameter tractable if and only if it admits a problem kernel, that is, a polynomial-time algorithm that maps any instance with parameter p to an equivalent instance of size at most g(p), where g is some function only depending on p. We speak of a polynomial problem kernel if g is a polynomial.

Basic Observations. We first discuss two trivial cases for GCSE and QCSE regarding the value of y and of k.

Observation 1. If y ∈ {0, τ}, then GCSE and QCSE are solvable in linear time.

Note that Observation 1 implies that for τ = 1, each of GCSE and QCSE is linear-time solvable. Another trivial case for GCSE is the following.

Observation 2. GCSE is linear-time solvable if k ≥ m.

We will see that Observation 2 does not transfer to QCSE: QCSE remains NP-hard, even if k ≥ m (Proposition 3).

The following allows us to assume throughout to have at most number of agents many candidates.

Lemma 1 (⭑). Each instance (A,C,U, k, x, y) of GCSE (of QCSE) can be mapped in linear time to an equivalent instance (A, C ′ , U ′ , k, x, y), ∣C ′ ∣ ≤ ∣A∣ of GCSE (of QCSE).

Corollary 1. (i) Each of GCSE and QCSE admits a problem kernel of size O(n2 ⋅ τ). (ii) There are at most (n + 1)n pairwise different nomination profiles.

3 Intractability

We discuss the general intractability of our problems as well as several special cases where they remain hard.

3.1 Dichotomies Regarding the Number of Levels

Both GCSE and QCSE are easy problems if there is only one level. Yet, already for two levels, GCSE becomes NP-hard while QCSE stays efficiently solvable. For three levels, however, also QCSE becomes NP-hard. We have the following.

Theorem 1. We have the following dichotomies for GCSE and QCSE regarding τ :

• (i) If τ = 1, then each of GCSE and QCSE is polynomialtime solvable.
• (ii) If τ = 2, then (a) GCSE is NP-hard and, unless NP ⊆ coNP/poly, admits no problem kernel of size O(m2-ε ) for any ε > 0, and (b) QCSE is polynomial-time solvable.

(iii) If τ ≥ 3, then each of QCSE with k ≥ m and GCSE is NP-hard and, unless the ETH breaks, admits no 2o(n+m) ⋅ poly(n + m)-time algorithm.

We first discuss (iia), then (iib), and finally (iii).

Two Levels Make GCSE Intractable

Proposition 1 (⭑). Even for two levels and x = 0, GCSE is NP-hard and, unless NP ⊆ coNP/poly, admits no problem kernel of size O(m2-ε ) for any ε > 0.

The following problem is NP-hard [Kuo and Fuchs, 1987]. CONSTRAINT BIPARTITE VERTEX COVER (CBVC)

Input: An undirected bipartite graph G = (V, E) with V = V1 ⊎ V2 and k1, k2 ∈ N.

Question: Is there a set X ⊆ V with ∣X ∩ Vi∣ ≤ ki for each i ∈ {1, 2} such that G - X contains no edge?

Note that we can assume that k1 = k2. CBVC is in FPT when parameterized by k1 + k2 [Fernau and Niedermeier, 2001] but, unless NP ⊆ coNP/poly, admits no problem kernel of size O(∣V ∣2-ε ) for any ε > 0 [Jansen, 2016]. The construction behind the proof of Proposition 1 is the following (the correctness proof is deferred to the full version of the paper).

Construction 1. Let I = (G = (V = V1 ⊎ V2,E), k, k) be an instance of CBVC. We construct an instance I ′ ≔ (A,C, (u1, u2), k, x, y) with x = 0 and y = 1 as follows.

For each vertex vi,j with i ∈ {1, 2} and j ∈ {1, . . . , ∣Vi∣}, add a candidate ci,j to C. For each edge {v1,j, v2,j ′}, add agent aj,j ′ to A which nominates c1,j in level 1 and c2,j ′ in level 2. This finishes the construction. ⋄

Two Levels Leave QCSE Tractable

Interestingly, in contrast to GCSE, just one additional level does not change the tractability of QCSE.

Proposition 2. QCSE is polynomial-time solvable if τ = 2.

We provide reduction rules for a generalization of QCSE on two levels, and then reduce it to a special variant of CBVC. The generalization of QCSE with τ = 2 is the following.

X2 EQUITABLE COMMITTEE SEQUENCE ELECTION (X2QCSE)

Input: A set A of agents, a set C of candidates, a two nomination profiles U = (u1, u2) with ut∶ A → C ∪ {∅}, and five integers k1, k2, x1, x2, y ∈ N0.

Question: Is there C1 ⊆ C with ∣C1∣ ≤ k1 and C2 ⊆ C with ∣C2∣ ≤ k2 such that

We know that y ∈ {0, 2} are trivial cases. Thus, we assume that y = 1 is the remainder. Our goal is to reduce X2QCSE to the following problem, which, as we will show subsequently, is polynomial-time solvable.

CONSTRAINT BIPARTITE INDEPENDENT VC W/ SCORE (CBIVCS)

Input: An undirected bipartite graph G = (V, E) with V = V1 ⊎ V2 and k1, k2, x1, x2 ∈ N.

Question: Is there an independent set X ⊆ V with ∣X∩Vi∣ ≤ ki and ∑v∈X∩Vi deg(v) ≥ xi for each i ∈ {1, 2} such that G - X contains no edge?

Lemma 2 (⭑). CBIVCS is polynomial-time solvable.

To reduce X2QCSE to CBIVCS we have to deal with agents nominating none or only one candidate. The first case is immediate.

Data Reduction Rule 1. If there is an agent nominating no candidate, then return no.

If an agent nominates only one candidate in one level and none in the other, we have to pick this nominated candidates.

Data Reduction Rule 2 (⭑). If there is an agent a∗ nominating one candidate c∗ in one level t ∈ {1, 2}, and none in the other level t′ , then do the following: Decrease kt by one, xt by ∣{a ∈ A ∣ ut(a) = c∗ }∣, replace each candidate in {c′ ∈ C ∣ ∃a ∈ A ∶ ut(a) = c∗ ∧ ut′ (a) = c′ } with ∅, and delete all agents from {a ∈ A ∣ ut(a) = c∗ }.

Using Data Reduction Rule 1 and 2 exhaustively, we can finally reduce X2QCSE to CBIVCS, proving Proposition 2.

Observation 3 (⭑). There is a polynomial-time many-one reduction from X2QCSE to CBIVCS.

Three Levels Make QCSE Intractable

We have seen that QCSE is polynomial-time solvable if τ ≤ 2. This changes for τ ≥ 3.

Proposition 3. For at least three levels and x = 0, each of QCSE with k ≥ m and GCSE is NP-hard and, unless the ETH breaks, admits no 2o(n+m) ⋅ poly(n+m)-time algorithm.

For GCSE, the proof is via a polynomial-time manyone reduction from the famous NP-complete problem 3SATISFIABILITY (3-SAT), which transfers the well-known ETH lower bound [Impagliazzo et al., 2001] as well as NPhardness [Garey and Johnson, 1979]. Given a set X of N variables and a 3-CNF formula ϕ = ⋀Mi=1 Ki over X, 3-SAT asks whether there is a truth assignment f∶X → {⊥,⊤} satisfying ϕ.

Construction 2. Let I = (X, ϕ) be an instance of 3SAT with N variables and M clauses. We construct an instance I ′ ≔ (A,C,U, k, x, y) of GCSE as follows (see Fig. 3 for an illustration). Let C ≔ {ci, ci ∣ xi ∈ X}. Let Ai ≔ ⋃3j=1 {ai,j , ai,j} for each i ∈ {1, . . . , N}. and A ≔ A1∪⋅ ⋅ ⋅∪AN∪{a1, . . . , aM}. See Fig. 3 for the nominations. Let k ≔ N, x ≔ 0, and y ≔ 1. ⋄

The construction provides the following key property when I ′ is a yes-instance: for every variable, exactly one of the two corresponding candidates must be in the committee.

Lemma 3 (⭑). If I ′ is a yes-instance, then for every solution (C1,C2,C3) it holds true that ∣Cj ∩ {ci, ci}∣ = 1 and Cj ∩ {ci, ci} = Cj ′ ∩ {ci, ci} for all j, j ′ ∈ {1, 2, 3} and i ∈ {1, . . . , N}.

Proof of Proposition 3 (GCSE). (⇒) Let f be a satisfying truth assignment. We claim that (C ′ , C ′ , C ′ ) with C ′ = {ci ∈ C ∣ f(xi) = ⊤} ∪ {ci ∈ C ∣ f(xi) = ⊥} is a solution to I ′ . Clearly, ∣C ′ ∣ = N. Moreover, if f(xi) = ⊤, then ai,j is satisfied in level j, and ai,1 is satisfied in level 3 and ai,j with j ∈ {2, 3} is satisfied in level j - 1. If f(xi) = ⊥, then ai,j is satisfied in level j, and ai,1 is satisfied in level 3 and ai,j with j ∈ {2, 3} is satisfied in level j - 1. Since f is satisfying, there is exactly one level t with ar being satisfied. (⇐) Let (C1,C2,C3) be a solution to I ′ . From Lemma 3 we know that C ′ = C1 = C2 = C3 and that C ′ ∩ {ci, ci} = 1 for all i ∈ {1, . . . ,N}. Let f(xi) = ⊤ if ci ∈ C ′ , and f(xi) = ⊥ otherwise. Clearly, f is a truth assignment. Suppose it is not satisfying, i.e., there is a clause Kr with no literal evaluated to true. Then, agent ar is satisfied in no level, contradicting that (C1,C2,C3) is a

solution to I ′ .

For QCSE, yet using again Construction 2, we instead reduce from the NP-hard problem EXACTLY 1-IN-3 SAT (X1-3SAT) [Schaefer, 1978], where, given a boolean 3-CNF formula ϕ over a set X of variables, the question is whether there is a truth assignment f ∶ X → {⊥, ⊤} such that for every clause, there is exactly one literal evaluated to true?

Notably, Lemma 3 also holds true here. In fact, we can even allow k = 2N, since for each variable only one candidate is chosen, as otherwise there is an agent scoring more than once.

3.2 FewCandidates Are of No Help

One could conjecture that it should be possible to guess the committees, and hence get some, possibly non-uniformly polynomial running time when the number of candidates is constant. In this section, we will show that this conjecture is wrong unless P = NP: each of GCSE and QCSE are NP-hard even for two candidates.

Theorem 2 (⭑). Even for x = 0, k = 1, and y = 1, each of GCSE with two candidates and QCSE with one candidate is NP-hard. Moreover, unless the SETH breaks, GCSE admits no (2 - ε)τ ⋅ poly(τ + n)-algorithm.

For GCSE, we reduce from the well-known NP-complete problem SATISFIABILITY (SAT), which transfers the wellknown SETH lower bound [Impagliazzo and Paturi, 2001] as well as NP-hardness [Garey and Johnson, 1979]. Given a set X of N variables and a CNF formula ϕ = ⋀Mi=1 Ki over X, SAT asks whether there is a truth assignment f∶ X → {⊥, ⊤} satisfying ϕ.

The construction is quite intuitive: Each level corresponds to a variable, and each agent corresponds to a clause. In each level, if the corresponding variable appears as a literal in the agent's corresponding clause, then the agent nominates a candidate regarding whether it appears negated or unnegated.

Construction 3. Let I = (X, ϕ) be an instance of SAT. Construct an instance I ′ ≔ (A,C,U, k, x, y) as follows. Let A ≔ {a1, . . . , aM}, C ≔ {c⊤, c⊥}, τ ≔ N, x ≔ 0, k ≔ 1, and y ≔ 1. In level i, agent aj nominates

⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩ c⊤, if xi appears unnegated in Kj, c⊥, if xi appears negated in Kj, and ∅, otherwise.

This finishes the construction.

⋄

Remark 1. For QCSE, we reduce from X1-3SAT (see previous section) where no variable appears negated [Schmidt, 2010], where the construction is very similar to Construction 3 (yet c⊥ can be dropped). Hence, a lower bound based on the SETH as for GCSE remains open for QCSE. ◁

4 Tractability

In this section, we discuss non-trivial tractable cases of GCSE and QCSE. It turns out that fixed-parameter tractability starts with the number n of agents or the solution size k ⋅ τ, i.e., with the combination of the size k of each committee and the number τ of levels. As to the latter, recall that each of GCSE and QCSE is NP-hard if either k is constant or τ is constant. Finally, we discuss efficient and effective data reduction regarding n and n + y.

4.1 Few Small Committees May be Tractable

We show that each of GCSE and QCSE when parameterized by the solution size k ⋅ τ is in FPT. That is, we can deal with many agents and candidates, as long as we are asked to elect few small committees. We also show that GCSE admits presumably no problem kernel of size polynomial in m ⋅ τ .

Theorem 3. Each of GCSE and QCSE is solvable in 2k⋅τ 2 ⋅ poly(n +m+ τ) time, and hence fixed-parameter tractable when parameterized by k + τ .

We introduce generalized versions of GCSE and QCSE. Intuitively, they allow to fix certain parts of the solution. Moreover, one may request level-individual committee sizes, levelindividual numbers of nomination the committees shall receive, and agent-individual numbers of successful nominations the agents still have to make.

Algorithm 1: FPT-algorithm for PE-GCSE parameterized by k + τ on input (A, C, U, (kt)t, (xt)t, (ya)a). 1 main((A,C,U, (kt)t, (xt)t, (ya)a)); 2 return no; 3 function main((A,C,U, (kt)t, (xt)t, (ya)a)): 4 if kt < 0 for some t ∈ {1, . . . , τ} then break 5 if ∀a ∈ A ∶ ya ≤ 0 then 6 foreach t ∈ {1, . . . , τ} do 7 if xt > 0 then 8 if any level-t committee of kt most nominated candidates in C w. r. t. ut scores less than xt then break 9 return yes 10 if ∃a ∈ A with ya > 0 but no fingerpint with at least ya non-empty entries then break 11 Let a ∈ A be such that ya > 0 with at least one fingerpint with at least ya non-empty entries 12 foreach X ∈ {u1(a), ∅} × ⋅ ⋅ ⋅ × {uτ (a), ∅} with at least ya non-empty entries do // ≤ 2τ many 13 foreach t ∈ {1, . . . , τ} do 14 Set x′t ← xt - ∣{a′ ∈ A ∣ ut(a′ ) = Xt ∧ Xt ≠ ∅}∣, u′t ← ut - ut(a), and k′t ← kt - ∣Xt∣ 15 foreach a′ ∈ A′ ← A \ {a} do 16 Set y′a′ ← ya′ -∑t ∣ut(a′ ) ∩Xt∣ 17 main((A′ , C, U ′ , (k′t)t, (x′t)t, (y′a)a))

PRE-ELECTED GCSE (PE-GCSE)

Input: A set A of agents, a set C of candidates, a sequence of nomination profiles U = (u1, . . . , uτ) with ut∶A → C ∪ {∅}, integers xt, kt ∈ N0 for each t ∈ {1, . . . , τ} and integers ya ∈ N0 for each a ∈ A.

Question: Is there a sequence C1, . . . , Cτ ⊆ C with ∣Ct∣ ≤ kt for every t ∈ {1, . . . , τ} such that

PRE-ELECTED QCSE (PE-QCSE) denotes the variant when replacing "≥" with "=" in (3).

Each of PE-GCSE and PE-QCSE use slightly different approaches. However, the core idea is the same: in any solution, each agent has a fingerprint over all levels regarding whether or not her candidate is elected into the respective committee. Note that there are at most 2τ fingerprints. Hence, we can guess such a fingerprint for any unsatisfied agent and branch. Together with the fact that the sum of the committee sizes in the sequence is at most k ⋅ τ, the result follows.

Throughout, we use the following. Fix any agent a ∈ A. We define for A′ ≔ A \ {a} the utility function

We first show the following Turing-reduction for PEGCSE. The idea of this reduction is then used to obtain fixedparameter tractability through Algorithm 1.

Lemma 4 (⭑). Let I ≔ (A, C, U, (kt)t, (xt)t, (ya)a∈A) be an instance with at least one agent a ∈ A with ya > 0 and at least one fingerprint with at least ya non-empty entries. Then, I is a yes-instance of PE-GCSE if and only if for any agent a ∈ A with ya > 0 and at least one fingerprint with at least ya non-empty entries, one of the instances I 1 , . . . , I p is a yes-instance, where X1 , . . . ,X p ∈ {u1(a), ∅} × ⋅ ⋅ ⋅ × {uτ (a), ∅} are the fingerprints with at least ya non-empty entries and for each q ∈ {1, . . . , p}, I q = (A′ , C, U ′ , (kq t )t, (xqt )t, (yqa)a∈A′ ), where A′ ≔ A\{a}, and

• for each t ∈ {1, . . . , τ}, x′t ≔ xt - ∣{a′ ∈ A ∣ ut(a′ ) = Xq t ∧Xq t ≠ ∅}∣, u′t ≔ ut -ut(a), k′t ≔ kt -∣Xq t ∣, and
• for each a′ ∈ A′ , y′a′ ≔ ya′ -∑τt=1 ∣ut(a′ ) ∩Xq t ∣.

Proposition 4 (⭑). Algorithm 1 is correct and runs in FPTtime regarding k + τ .

The proof for PE-QCSE works very similarly and is hence deferred to the full version of the paper.

In terms of kernelization, we cannot improve much further: Presumably, there is no problem kernel of size polynomial in k + τ . In fact, we have the following stronger result.

Theorem 4 (⭑). Unless NP ⊆ coNP/poly, GCSE admits no problem kernel of size polynomial in τ, even if m = 2 and x = 0.

Remark 2. We leave open whether the composition can be adapted for QCSE. For this, the last q levels forming the selection gadget must be changed or extended such that each agent gets the same score over the selection. ◁

4.2 Tractability Borders Regarding n

We first show that both problems become fixed-parameter tractable when parameterized by the number n of agents.

Theorem 5. Each of GCSE and QCSE is fixed-parameter tractable when parameterized by n.

Proof. Due to Lemma 1, we know that there are at most n candidates, and at most ν ≔ (n + 1)n pairwise different nomination profiles. That is, we have at most ν types, each having at most (nk) committees of size k and score of at least x (we call such a committee valid subsequently; note that we can check whether a committee is valid in linear time).

Let xt,ϕ denote the variable for type t and valid committee ϕ. Let nt denote the number of type-t profiles. For an agent a ∈ A, let Xa denote the set of tuples (t, ϕ) where valid committee ϕ respects a's nomination in level t. We then have the following integer programming constraints for GCSE:

As to Lenstra Jr. [1983], having 2O(nlog(n)) variables and constraints, and numbers upper bounded by τ , the result follows. For QCSE, we replace "≥" with "=" in (4).

Theorem 5 is in fact tight in the following sense: decreasing n by x gives a useless parameter (presumably).

Theorem 6 (⭑). GCSE is NP-hard even if n-x = 2 and m = 3, and QCSE is NP-hard even if n - x = 3 and m = 2.

The construction behind the proof of Theorem 6 is very similar to Construction 3 but with no empty nominations (we hence defer also the construction to the full version of the paper).

The FPT-algorithm behind Theorem 5 is not running in single-exponential time. Combining n with y gives singleexponential running time.

Proof. We give the proof for QCSE, and it is not hard to adapt it for GCSE. We use dynamic programming, where table

D[t, y] is true if and only if there are committees C1, . . . , Ct each with committee size at most k and a score of at least x such that the score of each agent ai at time t sums up to exactly yi, where y = (y1, . . . , yn).

Set D[t, y], where t > 1 and each entry of y is at most y, to true if and only if there is a set-to-true D[t - 1, y′ ] and a size-at-most k score-at-least x committee C ′ ⊆ C with respect to ut such that y′ + ⃗ c = y, where ⃗ c = (c1, . . . , cn) ∈ {0, 1}n with ci = 0 ⟺ ut(ai) ∩ C ′ = ∅ is called the fingerprint of C ′ regarding level t. Set

Return yes if the entry D[τ, (y1, . . . , yn)] is set to true, where y1 = y2 = ⋅ ⋅ ⋅ = yn = y, and no otherwise.

The running time of filling the table is clear: We have at most τ ⋅ (y + 1)n entries and at most 2n different committees per level. We defer the correctness proof to the full version of paper.

4.3 Efficient and Effective Data Reduction Regarding n and y

While GCSE admits a problem kernel of size polynomial in n + y, QCSE does not presumably. Moreover, for GCSE, dropping y also leads to kernelization lower bounds. We have the following.

Theorem 8 (⭑). Unless NP ⊆ coNP/poly, (i) GCSE admits no problem kernel of size polynomial in n, even if m = 2 and k = 1, and (ii) QCSE admits no problem kernel of size polynomial in n, even if m = 2, k = 1, and y = 1. (iii) GCSE admits a problem kernel of size polynomial in n + y.

We only discuss (iii) briefly (refer to the full version of the paper for the remaining details).

Proposition 5. GCSE admits a problem kernel of size polynomial in n+ y.

In the following, we (again) call a committee valid if its size is at most k and its score is at least x. For an agent a, we denote by Z(a) the set of all levels where there is a valid committee containing a's nominated candidate. We call an agent a non-critical if ∣Z(a)∣ > n ⋅ y, and critical otherwise. We have the followings.

Data Reduction Rule 3 (⭑). If every agent a is non-critical, then return a trivial yes-instance.

Thus, if we have a non-trivial instance, then there must be a critical agent. We will see that the number of critical agents can upper bound the number of levels. To this end, we first delete levels which are irrelevant to critical agents as follows.

Data Reduction Rule 4. If there is a level t∗ such that there is at least one valid committee and every valid committee only includes candidates nominated by non-critical agents, then delete this level.

Proof. Let I = (A,C,U, k, x, y) be the input instance and I ′ ≔ (A, C, U ′ , k, x, y) be the instance obtained by the reduction rule. Clearly, if I ′ is a yes-instance, then I is a yes-instance. Hence, we show the converse next.

Assume towards a contradiction that for every solution C ≔ (C1, . . . ,Ct∗, . . . ,Cτ) it holds true that C ′ ≔ (C1, . . . ,Ct∗-1,Ct∗+1, . . . ,Cτ) is no solution to I ′ , i.e., there is a maximal set A∗ ⊆ A of agents which is not satisfied when Ct∗ is dropped. Let q ≔ ∣A∗ ∣. Recall that A∗ consists of only non-critical agents. Let T ⊆ {1, . . . , τ} \ {t∗ } be a minimum-size set of levels such that all agents of A \ A∗ are satisfied (which exists since C ′ satisfies all agents except for those in A∗ ). Note that ∣T∣ ≤ (n - q) ⋅ y. Let T ≔ {1, . . . , τ} \ (T ∪ {t∗ }). Hence, for all a ∈ A∗ , we have that ∣Z(a) ∩ T ∣ ≥ ∣Z(a)∣ - ∣T ∪ {t∗ }∣ ≥ n ⋅ y + 1 - ((n - q) ⋅ y + 1) ≥ q ⋅ y. Thus, there is a solution to I ′ , yielding a contradiction.

It follows that in every level, there must be a valid committee for any of the at most n critical agents, each of which has at most n ⋅ y levels of this kind. This leads to the following.

Lemma 5 (⭑). If each of Data Reduction Rule 3 and 4 is inapplicable, then there are at most n2 ⋅ y levels.

To conclude, GCSE admits presumably no problem kernel of size polynomial in n, but one of size polynomial in n + y. Interestingly, for QCSE the latter is presumably impossible.

Proposition 6 (⭑). Unless NP ⊆ coNP/poly, QCSE admits no problem kernel of size polynomial in n, even if m = 2, k = 1, and y = 1.

5 Epilogue

We settled the parameterized complexity for both GCSE and QCSE for several natural parameters and their combinations. We found that both problems become tractable only if either the number of agents or the solution size is lower bounding the parameter. Hence, short trips with few per-day activities like in our introductory example can be tractable even if many agents participate and if there are many activities available. Also the practically relevant setting where few agents have to select from many options, where egalitarian or even equitable solutions appear particularly relevant, can be solved efficiently.

Our two problems have a very similar complexity fingerprint, yet, they distinguish through the lens of efficient and effective data reduction: While GCSE admits a problem kernel of size polynomial in n + y, QCSE presumably does not. In other words, it appears unlikely that we can efficiently and effectively shrink the number of levels for QCSE.

Other Variants. Looking at the constraints in GCSE and QCSE, one quickly arrives at the following general problem. Herein, we generalize to preference functions, where each agent assigns some utility value to each candidate. Moreover, we use generalized OWA-based aggregation, e.g., allowing max(⋅) and thus modeling rules such as Chamberlin-Courant. Let ∼∈ {≤, =, ≥}, Λ = {Λk ∈ Rk ∣ k ∈ N} be a family of (OWA) vectors, and U be a class of preference functions. We write ⃗u(C ′ ) for the vector of utilities that u assigns to the candidates from C ′ sorted in nonincreasing order. See Bredereck et al. [2020a] for details.

Input: A set A of agents, a set C of candidates, a sequential profile of preference functions U = (ua,t ∶ C → N0 ∣ a ∈ A, t ∈ {1, . . . , τ}) each from U, and three integers k, x, y ∈ N0.

Question: Is there a sequence C1, . . . , Cτ ⊆ C such that

Let SUM denote the family of OWA-vectors containing only 1-entries, and NOM be the class of preference functions that contain only 0-entries except for at most one 1-entry. We have that GCSE is (≤∣≥,≥)-BICMCE[SUM,NOM] and QCSE is (≤∣≥,=)-BICMCE[SUM,NOM]. It turns out that all variants except for (≤∣≤,≤)-BICMCE[SUM,NOM] and (≥∣≥,≥)-BICMCE[SUM,NOM] are NP-hard. In fact, most of the variants (including GCSE and QCSE) are NP-hard even if every voter does not change their vote over the levels. We defer the details to the full version of the paper.

Outlook. Since our model is novel, also several future research directions come to mind. A parameterized analysis of the variants of (∼k ∣ ∼x,∼y)-BICMCE[Λ, U] next to GCSE and QCSE could reveal where these variants differ from each other. One could consider a global budget instead of a budget for each level, that is, variants where ∣⋃τt=1 Ct∣ ≤ k or ∑τt=1 ∣Ct∣ ≤ k. Speaking of variants, another modification could be where the score of any two agents must not differ by more than some given γ. Finally, as a concrete question: does GCSE or QCSE admit a problem kernel of size polynomial in k if τ is constant? (Recall that due to Theorem 4, we know that there is presumably no problem kernel for GCSE of size polynomial in τ if k is constant.)

Acknowledgements

We thank the IJCAI'23 reviewers for their helpful comments. TF was supported by the DFG, project AFFA (BR 5207/1 and NI 369/15).