Proportionality Guarantees in Elections with Interdependent Issues

1 Introduction

Proportional representation of voters' preferences is an important desideratum in a wide range of social choice settings, including parliamentary elections [Pukelsheim, 2014], approval-based multiwinner voting [Lackner and Skowron, 2022], and participatory budgeting [Peters et al., 2021]. In two recent papers, Freeman et al. [2021] and Skowron and G´orecki [2022] studied a public decision model, where a collective decision needs to be taken on a given set of unrelated binary (yes/no) issues. In real life scenarios, these kinds of situations are often handled via majority rule: an issue is implemented if and only if more than 50% of the voters are in favor of it; and while this might be the most straightforward decision rule, it comes at a disadvantage: It is not proportional. For instance, consider a scenario where three binary decisions need to be taken, and the electorate is split into two groups. The first group of voters, which makes up two thirds of the electorate, votes "yes" on every issue, while the second group votes "no" on all issues. Majority rule would set all issues to "yes," completely ignoring the preferences of one third of the electorate. One might argue that setting two issues to "yes" and one issue to "no" would be a more fair solution. Such considerations led Freeman et al. [2021] and Skowron and G´orecki [2022] to adopt several proportionality notions and proportional voting rules from the setting of approval-based multiwinner voting to their model.

The model studied by the above-mentioned previous works has two important limitations. Firstly, the issues under consideration are only allowed to be binary, which makes it impossible to model scenarios where an issue has more than two possible alternatives. Secondly, their setting does not allow any dependencies between the issues, although in some situations it might be the case that the approval of an issue is dependent on the decision taken for another. The more general setting for proportional decision-making that we study here is based on the conditional approval voting framework introduced by Barrot and Lang [2016]. This setting allows for more than two choices per issue as well as for dependencies between the issues; consequently, it addresses both limitations discussed above. The following example illustrates the type of situations that our model can deal with.

Example 1. Consider a scenario, where a municipality has decided that the following projects will be funded: (1) a public park, (2) a pedestrian infrastructure, and (3) a community center. However, the location of these sites is not fixed yet, and the voters should decide on whether to build each project at the Southside, the Centralside, or the Northside district. Obviously, the domain of each issue here is of size three. Voter 1, a resident of Southside, is voting in favor of building the park in her neighborhood and therefore casts an (unconditional) approval ballot for this option. The preferences of the other voters are more complicated: Voter 2 is concerned about the traffic congestion that a new community center could cause and votes for building a community center at any location only if a pedestrian infrastructure is built at the same location as well. Finally, voter 3 doesn't want any two projects built in the same location. Hence her approval for any project depends on the decisions made for the other two projects.

In this paper, we focus on the proportionality concept that was introduced by Skowron and G´orecki [2022], which provides strong guarantees for all groups of voters of sufficient size. These guarantees are considered as more powerful than other previously studied ones, which were only able to ensure proportional representation to groups of voters that have similar preferences. Such "cohesive" groups are rare to be found in practice in the unconditional setting [Bredereck et al., 2019], let alone when dependencies between issues exist.

Contribution. The main challenge left open by Skowron and G´orecki [2022] lies in incorporating in their model dependencies between issues, which can be seen as a steppingstone to the building of a theory of fairness for general public decision settings. Motivated by this, we first introduce appropriate generalizations of Proportional Approval Voting (PAV) and the Method of Equal Shares (MES), which are two prominent rules with provable guarantees on proportional representation for binary, unrelated issues. We then make progress along two fronts. First, we generalize the known guarantees to elections over issues with non-binary domains. Secondly, and most importantly, we consider elections with dependencies among issues, where we identify sufficient restrictions that lead to analogous results. Our work is the first that provides guarantees of proportionality for elections with conditional ballots. Moreover, for the conditional version of MES, we also study computational aspects. Our results demonstrate that the conditional setting poses additional challenges and differs significantly from the unconditional one, both in terms of proportionality and complexity. As an example, we show that MES is hard to implement in the general conditional case, whereas it has been known to be tractable in unconditional elections. Another highlight of our work is that PAV and MES achieve proportionality bounds under different assumptions (that have some degree of complementarity), and thus, one cannot reach yet an absolute conclusion when compared against each other, under the conditional framework, in contrast to the unconditional setting.

Related Work. On a high level, there are three lines of research that are related to our paper. First, our work is closely related to approval-based multiwinner voting [Lackner and Skowron, 2022]. Starting with [Aziz et al., 2017] and [S´anchez-Fern´andez et al., 2017], a plethora of proportionality notions have been defined and studied. Originally defined for multiwinner voting, proportionality notions have more recently been extended to more general settings such as participatory budgeting [Peters et al., 2021; Brill et al., 2023]. Quantitative proportionality notions have also been studied by Aziz et al. [2018] and Skowron [2021].

Secondly, our work is related to multi-issue decisionmaking and seat-posted elections. With the exception of the aforementioned papers by Skowron and G´orecki [2022] and Freeman et al. [2021], these have not been studied from a proportionality perspective. Instead, the literature has focused on issues such as Anscombe's and Ostrogorski's paradoxes [Anscombe, 1976; Fritsch and Wattenhofer, 2022; Laffond and Lain´e, 2006] or axiomatic comparisons between preferences and decisions over issues and the entire decision space [Dindar and Lain´e, 2022; Aslan et al., 2022].

Third, our work is utilizing a model of conditional approval voting over combinatorial domains. This was introduced by Barrot and Lang [2016], who also proposed three voting rules for incorporating dependencies between issues and studied (mainly axiomatic) properties. Later on, the works by Markakis and Papasotiropoulos [2020; 2021], focused on the algorithmic aspects of the winner determination problem under the conditional analog of the (minisum) approval voting rule and also considered the computational complexity of controlling the election outcome, under the same rule. Apart from approval-based elections, the presence of preferential dependencies remains a major challenge and several frameworks have been considered, as it has been extensively discussed by Lang and Xia [2016] and Chevaleyre et al. [2008].

2 Preliminaries

In this section, we introduce the setting of conditional approval voting, we define the proportionality notion we are interested in, and define the two voting rules that will be the focus of our work.

2.1 Conditional Election Setting

In describing conditional approval elections, we closely follow the notation and terminology of the previous papers on the topic, by Barrot and Lang [2016] and Markakis and Papasotiropoulos [2020; 2021]. We consider a group N = {v1, v2, . . . , vn} of n voters that needs to make a decision over a set of m possibly interdependent issues I = {I1, I2, . . . , Im}. Each issue Ij, is associated with a domain Dj = {a1j , a2j , . . . , adj } that corresponds to the alternatives for this issue. Without loss of generality, we assume that |Dj| = |Dj ′ | ≥ 2, ∀j, j ′ ∈ [m] (if not, one can add dummy alternatives) and we denote the domain size by d.

A conditional approval voting instance, or simply an instance, is determined by a tuple P = (I, N, B), where B denotes the conditional approval ballots of the set of voters N over the issues of I. In what follows, we describe the format of conditional approval ballots.

Each voter vi ∈ N is associated with a directed graph, whose vertex set coincides with the set of issues, referred to as her dependency graph, Gi = (I,Ei). A directed edge (Ik, Ij) ∈ Ei, means that according to voter vi, issue Ij is affected by Ik. We use Γi(Ij) to denote the (possibly empty) set of direct predecessors, i.e., in-neighbors, of issue Ij in Gi and Γ∗i (Ij) = Γi(Ij) ∪ {Ij}. Voters cast conditional approval ballots that are expressed as follows: For an issue Ij with |Γi(Ij)| = 0, voter vi casts a standard (unconditional) approval ballot, stating explicitly all the alternatives of Dj that are approved by her, the number of which varies from 0 to d. For the case that |Γi(Ij)| > 0, voter vi needs to specify all the combinations of alternatives for issues in Γ∗i (Ij) that she approves, i.e., that make her satisfied w.r.t. issue Ij. These combinations are expressed in the form {s : t}, where s ∈ ×Iℓ∈Γi(Ij)Dℓ, and t ⊆ Dj. Such a ballot signifies the satisfaction (i.e., approval) of a voter with respect to issue Ij , when the in-neighbors of Ij in Gi are set to the alternatives specified by s, and the selection for Ij belongs to t. We note that we do not impose that voters submit a ballot for every issue (they can abstain if they are not satisfied with any outcome w.r.t. certain issues). In the case that all voters have the same dependency graph, we let ∆in denote the maximum in-degree of this graph.

Given a conditional approval voting instance, the global dependency graph is the undirected simple graph G that results from ignoring the orientation of edges in the graph (I, ⋃i∈[n] Ei), where Ei is the edge set of vi's dependency graph. We use Γ(Ij) to denote the (possibly empty) set of neighbors of issue Ij in G and Γ∗ (Ij) = Γ(Ij)∪{Ij}. Moreover, ∆ denotes the maximum degree of any vertex in G. Note that if Γ(Ij) = ∅ for all j ∈ [m], then a conditional approval voting election degenerates to a classical approval election over m issues.

For any I ′ ⊆ I, any tuple w ∈ ×Ij∈I ′Dj , i.e., that includes an alternative from Dj for every issue Ij ∈ I ′ , is referred to as a suboutcome. If w specifies a value for all issues of an instance P = (I,N,B), we simply call it an outcome of P. A conditional approval voting rule is a function that maps each conditional approval voting instance P to an outcome w. Given an outcome w, we let ui(w) denote the number of issues with respect to which voter vi is satisfied under w. If w is clear from the context, we simply refer to this as ui. The following example illustrates our setting.

The dependency graphs of the voters, namely G1,G2,G3 are depicted in the figure below, together with the global dependency graph G, which has maximum degree ∆ = 2.

2.2 Proportionality Criterion

We now define a (parameterized) notion of proportionality that generalizes the one suggested by Skowron and G´orecki [2022]. The basic rationale behind any proportionality definition is the intuitive idea that any fraction of voters should have the ability to influence a corresponding fraction of decisions:

A group of voters that makes up a β-fraction of the electorate should be able to decide on βm issues.

In particular, such a criterion requires that minority opinions are represented as well (proportionally to their size).

To formalize this notion, an important parameter is the set of issues that a voter can be possibly satisfied with. Namely, for a voter vi ∈ N, we let Ri denote the set of issues Ij ∈ I, for which vi has submitted at least one conditional approval ballot (or unconditional if Γi(Ij) = ∅), i.e., there is at least one selection of alternatives for Γ∗i (Ij) that makes vi satisfied w.r.t. issue Ij. Formally, Ri = {Ij ∈ I : ∃w ∈ ×Iℓ∈Γ∗i (Ij)Dℓ that satisfies vi w.r.t. Ij}. To avoid trivialities, we assume that |Ri| > 0 for all vi ∈ N. By definition, voter vi cannot be satisfied with respect to any issue in I \ Ri, under any outcome. In Example 2, we have R1 = {I1, I2}, R2 = {I2, I3}, R3 = {I1, I2, I3}.

For a group V ⊆ N of voters, we let rV denote the number of issues for which all voters of V approve at least one alternative, i.e., rV = | ∩i∈V Ri|. In Example 2, we have rN = 1, r{v1,v2} = 1 and r{v2,v3} = 2. The role of rV is important in the definition below in which, the proportionality guarantee of a group of voters takes into account the maximal number of issues that all members of the group care about.

Definition 1. A conditional voting rule is α-proportional, for some α ∈ [0, 1], if for every conditional approval voting instance P = (I,N,B) with |N| = n and for every V ⊆ N, there exists a voter vi ∈ V such that if w is the winning outcome under the considered rule, then

The parameter α in the definition represents the degree of proportionality that a voting rule can guarantee. Ideally, we would like to have α-proportional rules for α = 1, as this would mean that the elected outcome aligns with the views of the electorate in a proportional manner. However, as we will soon show, such a rule does not exist and more relaxed values will need to be considered. In the unconditional case, and with a binary domain for each issue, it was shown by Skowron and G´orecki [2022] that α = 12 is achievable. In our more general setting, we will see that the degree of proportionality cannot be expressed by a constant; rather, it will be a function of the input instance, dependent on d and ∆.

2.3 Conditional Voting Rules

We focus on two conditional rules, that constitute natural generalizations of their well-studied unconditional versions.

Conditional Proportional Approval Voting (cPAV)

An outcome w of a conditional approval election in an instance P = (I, N, B) gains a score of ∑ui(w) k=1 1k from every voter vi who is satisfied with w with respect to ui(w) issues. The cPAV score of w is ∑vi∈N ∑ui(w) k=1 1k , or, in words, it is the sum of the scores that it gains from all the voters of the electorate. The outcome that achieves the highest cPAV score is the winning one under cPAV. Note that the only difference between the unconditional definition of PAV [Thiele, 1895; Janson, 2016] and the version we suggest here, comes from the way that a voter's satisfaction w.r.t. an issue is defined.

Conditional Method of Equal Shares (cMES)

The unconditional version of cMES was introduced by Peters and Skowron [2020] (and was originally being referred to as "Rule X"). In our more general setting, the rule consists of two phases, and the first one works in rounds. Initially, each voter is given a budget m, equal to the number of issues and all issues are being considered as unfixed. Fixing an issue will cost a price of n. Unlike in the unconditional version of the rule, we also allow that several issues are fixed at the same time, in which case the price to be paid is n times the number of issues to be fixed. For any round t of the first phase and an issue Ij ∈ I that has not been fixed yet, denote by Γu (Ij) the set of all issues in ∪vi∈NΓ∗i (Ij) that remain unfixed until round t. For every such issue Ij, for every set I ′ ⊆ Γu (Ij), and for every possible (sub)outcome w on the issues of I ′ , we perform the following: First, we identify the set of voters S(w) who have a positive remaining budget and are satisfied with respect to Ij under w; second, we calculate 1 the price p(w), which is such that if each voter in S(w) paid p(w) or all the money she has left, then the voters from S(w) would altogether pay n · |I ′ |. Finally, among the above, we determine the set of issues I ′ and the suboutcome w with a minimal value for p(w); we reduce the budget of every voter in S(w) by p(w) (or to 0 if their current budget is less than p(w)); we set the decision on the issues of I ′ to w, and we continue with the next round, until no further purchase can be made. It might happen that after this procedure, there are issues for which the decision has not been set. For these, in the second phase, we select an alternative arbitrarily.

A natural case for elections with conditional ballots, that we pay special attention to, is when all the voters agree on the dependencies among issues, i.e., when they have the same dependency graph. In some scenarios, this may even be enforced by the election organizer, either for uniformity reasons or when there are obvious enough dependencies among issues that apply to all voters. With a common graph, the execution of cMES becomes a bit simpler. In particular, for a yet unfixed issue Ij ∈ I, we only look at the single subset of the in-neighborhood of Ij, say I ′ , that has not been fixed in the previous rounds. For this set I ′ , we check all possible suboutcomes w to identify the voters who can get satisfied with respect to Ij, and continue in the same manner as in the description of cMES above.

3 Conditional PAV

We begin our study by examining cPAV, the conditional version of Proportional Approval Voting; a voting rule that exhibits significant proportionality guarantees in the binary and unconditional case [Skowron and G´orecki, 2022]. The main result of this section is the identification of a proportionality guarantee under a certain assumption (Theorem 1). Before delving into this, we present an example that establishes that, as in the unconditional setting, we should not have too high expectations in terms of the α-value that is achievable.

Example 3. Consider an instance P = (I,N,B), with m issues, such that m is a multiple of d∆+1 and furthermore, suppose that m can be written as m = k(∆ + 1), for an integer k. Assume also that the issues of I can be partitioned in k sets, namely M1,M2, . . . ,Mk, of size (∆+ 1) each, so that issues fromMi are not dependent on issues fromMj for any voter, and for any i ̸= j. Let there also be d∆+1 voters. We fix an i ∈ [k] and we focus on a single set of issues Mi. We will make each issue of Mi dependent on all the remaining ∆ issues of the group Mi, for all voters. This means that the global dependency graph is a disjoint union of cliques.

1 The calculation of p(w) for a given w can be done easily, see e.g. the proof of Theorem 4.

To describe the voters' preferences, note that there are exactly d∆+1 possible outcomes for the issues of any single clique. We define the preferences so that for every possible outcome in each clique, there is exactly one voter who is satisfied with that outcome, with respect to all the ∆+ 1 issues. Furthermore this voter is dissatisfied in any other outcome with respect to all these issues. For instance, say we fix a suboutcome x = (x1, . . . , x∆+1) for a particular clique. Then, we will have exactly one voter whose ballot is {x-1 : x1, x-2 : x2, . . . , x-(∆+1) : x(∆+1)}, where x-i denotes the tuple (x1, . . . , xi-1, xi+1, . . . x∆+1). Thus, observe that if x is indeed the final selection for the clique under consideration, the satisfaction of the corresponding voter, with respect to these issues, equals exactly ∆+1. We use the same construction of preferences for the issues of the remaining cliques. Hence, for every V ⊆ N, it holds that rV =m.

Observation 1. There does not exist a voting rule that is αproportional for α = 1.

Proof. Consider the instance P of Example 3, pick an arbitrary voting rule and let w be its winning outcome in P. Since the voters do not agree on any issue under any outcome, there exists at least one voter vi satisfied with at most mn issues. If vi is satisfied with strictly less than m d∆+1 issues, then consider the set V = {vi}. Proportionality requires that ui(w) ≥ m |V | n = m d∆+1 , which is a contradiction. Hence, it must be that all voters are satisfied with exactly m d∆+1 issues. If we focus now on V = N, it should hold that ui(w) > m-1 for all vi ∈ N, which is not the case.

In fact, Example 3 has further negative implications.

Remark 1. Consider a rule that is reasonably fair to the voters, in the sense that it does not treat any voter in a significantly different manner. Then in Example 3, every voter would have to be satisfied with respect to exactly m d∆+1 issues. But then, looking at V = N would imply that the rule cannot be α-proportional, for any α > 1 d∆+1 .

The previous discussion highlights that most probably, the best we could expect is a proportionality guarantee of α = 1 d∆+1 . We have not yet been able to obtain such a general result for all instances. The main technical difficulty with conditional elections is the analysis of the PAV score. This is more challenging to handle now because the satisfaction of a voter can change more abruptly when we alter the value of a single issue, due to the effect this may have on other issues. On the positive side, we can prove a guarantee by restricting the voters' preferences. It remains an open problem to determine whether such restrictions could be relaxed or removed.

Assumption 1. For every voter vi ∈ N, any two issues in Ri are either located in different components or are at a distance of at least 4 from each other in the global dependency graph.

In other words, the assumption states that if a voter can be satisfied w.r.t. some issue, she cannot be satisfied w.r.t. to any other "nearby" issue in the global dependency graph. Hence it intends to capture voters who express preferences for a rather limited number of issues per component, which allows us to control the total satisfaction achieved by the voters.

Theorem 1. Under Assumption 1, cPAV is α-proportional for α = 1 (1+∆2 )d∆+1 .

Proof. Consider a conditional election instance (I,N,B) in which Assumption 1 holds, let G be its global dependency graph, and w its cPAV winning outcome. For any fixed issue Ij, our proof will be based on a counting argument, where we will examine all possible ways of changing the alternatives chosen for Ij and its neighbors in w. Let sj be a (sub)outcome that specifies an alternative for every issue in Γ∗ (Ij). Let δw(sj), be the difference of the cPAV score if we change every issue of Γ∗ (Ij) from its value in w to the value indicated by sj, minus the cPAV score of w. We denote by Fj the set of all possible suboutcomes sj such that sj(I ′ ) ̸= w(I ′ ), for at least one issue I ′ ∈ Γ∗ (Ij), so that sj does impose an outcome different from w. Given that |Γ∗ (Ij)| ≤∆+1, it holds that |Fj| ≤ d∆+1 -1.

The main component of the proof is the estimation of the expression ∑Ij∈I ∑sj∈Fj δw(sj), denoted by Sw for simplicity. Before we proceed, recall also that if ui is the number of issues that vi is satisfied with under w, the voter contributes to the cPAV score the quantity 1 + 12 + · · · + 1 ui . At what follows we will use Γ(Γ(Ij)) to denote the set of issues that are at distance 2 from Ij in G. We consider now two cases.

First, we consider an issue Ik with respect to which voter vi is satisfied under w. We will take into account all possible tuples sj in the expression Sw, that may affect the satisfaction of vi for this issue. These are precisely the suboutcomes sk ∈ Fk, the suboutcomes sℓ ∈ Fℓ that correspond to any issue Iℓ ∈ Γ(Ik), and also the suboutcomes sℓ ∈ Fℓ for any issue Iℓ ∈ Γ(Γ(Ik)). Let us denote by F ′k the set of all these suboutcomes. In worst case, any change of w by the values indicated by some s ∈ F ′k may cause voter vi to become dissatisfied with respect to issue Ik. Observe also that by Assumption 1, the suboutcomes from F ′k cannot affect any other issues that voter vi is satisfied with under w, in other words, vi will remain satisfied with all the other ui - 1 issues that she was satisfied with under w. Therefore, when we change w according to a suboutcome s ∈ F ′k , either the voter vi does not contribute anything to Sw, or her contribution will be negative, and equal to -1/ui due to the definition of cPAV. To bound the number of tuples that can create this negative contribution, we need to estimate |F ′k |. To do this, note that the set Γ∗ (Ik) ∪Γ(Γ(Ik)) contains exactly Ik itself, its neighbors, and its neighbors of neighbors which altogether correspond to at most (1+∆+∆(∆-1)) = 1+∆2 issues. Given also that for every such issue Ij, the number of different tuples sj ∈ Fj to consider is d∆+1 - 1, it is true that |F ′k | ≤ (1 +∆2 )(d∆+1 - 1). Thus, the total contribution of voter vi is in worst case at least - (1+∆2 )(d∆+1-1) ui . Since we know that under w, there are exactly ui issues that vi is satisfied with, we conclude that for every i ∈ [n] the contribution of vi to Sw is at most - ui(1+∆2 )(d∆+1-1) ui .

Second, consider the |Ri| -ui issues that vi is dissatisfied under w, but for which we know that there exists an assignment of values that satisfy vi (by definition of Ri). Fix any such issue, say Ik. We know that in Fk there exists at least one suboutcome, say sk, that can make vi satisfied with respect to Ik. By Assumption 1, we know that changing w according to sk cannot affect the remaining issues that vi is satisfied with under w. Hence, there is at least one suboutcome, sk, for which voter vi contributes a positive value to Sw, which equals 1 ui+1 . Therefore, for every i ∈ [n] the contribution of vi to Sw is at least |Ri|-ui ui+1 .

The optimality of w implies that δw(sj) ≤ 0, for every sj ∈ Fj and for every j ∈ [m]. Furthermore, -(d∆+1 -1) ≤ 0 and hence the following hold:

Equivalently, ∑vi∈N |Ri |+1 ui+1 ≤ (1 + ∆2 )d∆+1n, and if we fix any set V ⊆ N, the following hold:

Using the fact that |Ri| ≥ rV , and by a rearrangement of the terms, we also have that

Due to the harmonic and arithmetic mean inequality, n ∑i∈[n] 1 xi ≤ 1n ∑i∈[n] xi, and by fixing xi to 1 ui+1 we get

Combining the relations (1) and (2) gives (after reordering)

Consequently, for every V ⊆ N, there exists a voter vi ∈ V , for which ui(w) > 1 (1+∆2 )d∆+1 |V | n rV -1.

Despite the negative results indicated by Example 3, Theorem 1 provides the first guarantee of proportionality for conditional approval elections. On the downside, even in the unconditional setting, determining the winning outcome for PAV is NP-hard.

Implications for the Unconditional Case. Assumption 1 trivially holds if all voters submit unconditional ballots since then, any two issues belong to different components in the global dependency graph (which does not have any edges). For this case, ∆ = 0 and the α-value achieved by Theorem 1 is 1d . This strictly generalizes the result of Skowron and G´orecki [2022], that deals only with the case of d = 2, and had left as an open problem the cases with higher values of d. Note also that Example 3 still works for ∆ = 0, which makes the result of Theorem 1 tight in the unconditional case, for any domain size, generalizing once again the analogous result.

4 Conditional MES

The computational intractability of PAV in the unconditional setting motivated the study of other rules, such as the Method of Equal Shares (MES), that overcome computational barriers and at the same time have desirable characteristics from the perspective of proportional representation. In this section, we extend this line of work to conditional elections, by focusing on the conditional version of MES as defined in Section 2.3. We start with studying algorithmic properties of cMES, and then proceed to proportionality guarantees.

4.1 Computational Complexity of cMES

The main result of this subsection is that Conditional MES is not, in general, computable in polynomial time, which is a noteworthy characteristic that differentiates it from its unconditional variant. This holds even for binary domains and rather simple dependency graphs, when either the maximum in-degree is large (Theorem 2) or the dependency graphs of the voters do not coincide (Theorem 3). Despite these negative results, there are well-motivated restricted families of instances for which we can compute cMES in polynomial time. In particular, when neither of the aforementioned conditions hold, a winning outcome can be computed efficiently (Theorem 4). Finally, for the case of different dependency graphs, we have also identified a restriction that implies polynomialtime computability (Theorem 5).

Theorem 2. The winning outcome under cMES cannot be computed in polynomial time, unless P=NP, even when the voters have a common dependency graph.

In the proof of Theorem 2, we have used in an essential way the fact that the maximum in-degree of the common dependency graph is large enough, and certainly non-constant. However, we expect that this represents rather extreme cases, and that in practical scenarios for conditional voting, it is more important to focus on the case of bounded in-degree, which has also been the focus of previous works on computational aspects of such elections, see e.g. [Markakis and Papasotiropoulos, 2021]. Even in this case, the NP-hardness remains, when the voters have different dependency graphs.

Theorem 3. Assuming ties are broken in favor of the largest set of buyers, the winning outcome under cMES cannot be computed in polynomial time, unless P=NP, even with a constant maximum in-degree in each voter's dependency graph.

Proof. To prove the statement, we reduce from 3SAT. Given a 3SAT instance, Π, on q variables, namely x1, x2, . . . , xq, and r clauses, namely c1, c2, . . . , cr, we create a conditional election instance P = (I, N, B) of |I| = q +r+1 issues and |N| = q + r + 1 voters, as follows:

• We create a binary issue I0 of domain {z1, z2} and we add a voter voting unconditionally for z1.
• For every j ∈ [q], i.e. for every variable xj of Π, we add a binary issue Ij of domain {tj, fj}. We refer to these issues as variable-issues. Furthermore, we add a variable-voter for every j ∈ [q], who is only voting for {tj : z1, fj : z1} and is dissatisfied with any other issue.
• For every clause cj of Π, j ∈ [r], we add a binary issue I ′j of domain {posj , negj}. We refer to these as clauseissues. Furthermore, we add a clause-voter who only cares to be satisfied w.r.t. I0, and is voting for {cj ∧ posj : z1}, where cj contains at most 3 variable-issues.

Observe that the maximum in-degree in every voter's dependency graph is at most 4. Furthermore, every voter is only interested in getting satisfied w.r.t. a single issue I0.

Lemma 1. The instance Π is a YES-instance if and only if there exists an outcome that satisfies all voters w.r.t. I0.

In the remaining proof we will show that one cannot efficiently determine the set of voters who should pay for the first purchase in a run of cMES, unless P=NP. To do this, we establish the following claim: the set of all voters N, is the largest in cardinality set of voters that can jointly buy a set of alternatives at a minimum per voter cost in the first iteration if and only if the 3SAT formula is satisfiable.

For the forward direction, suppose that the formula is satisfiable. Then by Lemma 1, there is an outcome that satisfies all voters. This implies that the voters can buy an outcome of all the q + r + 1 issues, and the per voter cost would be p(w) = q + r + 1. If this was not the minimum possible per voter cost in the first iteration of cMES, then there was a different purchase, say for a suboutcome w′ , with p(w) < q + r + 1, due to the tie-breaking rule. We need to check whether there exists such a set of κ voters, that are willing to buy a suboutcome w′ on λ issues, where κ < q+r+1, and such that p(w′ ) < q + r + 1. But then, with λ issues, we have p(w′ ) = λ(q+r+1) κ and λ(q+r+1) κ < q + r +1 if and only if λ < κ. However, it must be the case that λ ≥ κ. To see why, consider an arbitrary set of voters S that includes a variable-voters, b clause-voters and possibly the voter who votes for I0 unconditionally. In order for such a set of voters to buy a suboutcome, note that the issue I0 has to be included, and furthermore, each variable-voter requires her own variable issue to be included as well. For every clause-voter, we also have to include the corresponding clause issue, hence in total the set of issues that will be fixed is at least a + b + 1.

Thus, it is impossible that some set of κ voters can decide to buy together a suboutcome on less than κ issues.

For the reverse direction, suppose that in the first iteration of cMES, the set selected to buy alternatives is the set of all voters. Since, the ballot of every voter contains a distinct issue, this means that the voters have bought an alternative for all the issues in order to be concurrently satisfied with I0. Then, by Lemma 1, the SAT formula is satisfiable. Hence, we have shown that we can run efficiently the first iteration of cMES in the instance we constructed, if and only if we can decide if the SAT formula is satisfiable.

Moving to positive results, we demonstrate below that when we have a common dependency graph and the in-degree is bounded, cMES can be implemented efficiently. We find this to be a natural case (which complements the tractability landscape for cMES with Theorems 2 and 3), since there are numerous scenarios where the voters are likely to have the same perception on the dependence structure among issues. Recall that in these instances, ∆in is the maximum in-degree.

Theorem 4. If all the voters have the same dependency graph, and ∆in is bounded by a constant, then the winning outcome of cMES can be computed in polynomial time.

We conclude the computational analysis of cMES with one more positive result, applicable to the more general setting where voters can have different dependency graphs.

Theorem 5. If each connected component of the global dependency graph has no more than a constant number of vertices, then the winning outcome under cMES can be computed in polynomial time.

4.2 Proportionality Considerations of cMES

We first prove that in the conditional case, there is a family of instances for which cMES is strictly worse in terms of proportionality than cPAV.

Proposition 1. If ∆ ≥ 1, for any ρ ∈ R≥1, cMES is not 1ρ -proportional, even for instances that satisfy Assumption 1.

Therefore, restrictions of a different flavor than Assumption 1 are necessary in order to end up with a bounded proportionality guarantee for cMES. To understand when to expect a good behavior from cMES, it is important to revisit first the unconditional case, where an assumption was also needed to achieve any proportionality bound. More precisely, the guarantee for MES by Skowron and G´orecki [2022] was established under the assumption that there are no abstainers, i.e., every voter approves at least one alternative from every issue, hence rV = m. In the conditional setting, we will use a generalization of this statement, in the following form: no matter how the in-neighbors of an issue are set, a voter can still be satisfied with at least one alternative of that issue.

Assumption 2. For every issue Ij and for every voter vi, we assume that for every combination of values for the issues in Γi(Ij), there is a choice for Ij that satisfies vi with respect to Ij. When Γi(Ij) = ∅, we simply assume that vi approves at least one alternative from the domain of Ij.

We note that Assumption 2 is incomparable to the assumptions needed for the polynomial algorithms of Section 4.1 and also that it implies rV = m for any set of voters V .

Theorem 6. Under Assumption 2, cMES is α-proportional for α = 1 (∆+1)d∆+1 . When all voters have the same dependency graph, then the same bound holds with ∆ replaced by ∆in, the maximum in-degree over all issues.

For the case of a common dependency graph for all voters, we show that we can also go a small step further by slightly relaxing Assumption 2, in a way that Theorem 6 still holds and at the same time no significant improvements on the proportionality bound would be possible. Before that, we give the following notation: consider an instance P = (I, V,B), the voters of which have the same dependency graph. Then for every issue Ij ∈ I, let Γin(Ij) be the set of in-neighbors of issue Ij in the dependency graph and let Z(Ij) = {Ik ∈ I such that Ik ∈ Γin(Ij) ∧ Ij ∈ Γin(Ik)}.

Assumption 3. For every issue Ij and for every voter vi, we assume that for every combination of values for the issues in Γin(Ij) \ Z(Ij), there is a choice of values for the issues in Z(Ij) ∪ {Ij} that satisfies vi with respect to Ij. When Γin(Ij) = ∅, we simply assume that vi approves at least one value from the domain of Ij .

It is easy to verify that, for the case of a common dependency graph, Theorem 6 still works under this weaker assumption. The reason is that the issues in Z(Ij) cannot be fixed before the round where Ij gets fixed, as they depend on it. Hence, in the proof of Theorem 6, we only need to impose the condition of Assumption 2 for the issues in Γin(Ij) \ Z(Ij). Furthermore, we exhibit below that under Assumption 3, a proportionality guarantee that is significantly better than the result of Theorem 6 is impossible.

Observation 2. For ∆in ≥ 1 and d ≥ 2, cMES is not 1 d∆in+1 -proportional, even for instances that satisfy Assumption 3 and even if all voters have the same dependency graph.

Implications for the Unconditional Case. A corollary of Theorem 6 that concerns the unconditional case is the generalization of the proportionality guarantee for MES from the case of binary decisions to any domain size d (which was left as an open question by Skowron and G´orecki [2022]), while meeting the lower bound of 1d from Example 3.

5 Conclusions

Our main results establish that both cPAV and cMES can achieve proportionality bounds, under different assumptions. PAV seems to favor situations where the satisfaction score of a voter is somewhat restricted, whereas MES has a better behavior when voters are "easier" to please for every issue.

Concerning potential future work, we first note that we do not have yet a complete picture about the tightness of our bounds. Also it has been challenging to understand whether the assumptions used can be relaxed, and to what extent. The assumption on MES seems to be quite critical even in its unconditional variant; as for PAV, we are optimistic that relaxations might be possible. One can also study the behavior of other rules under the conditional setting, or think of further ways to generalize MES, based on how a purchase is made and who participates in each purchase. In general, we believe that proportional representation in combinatorial domains is a fascinating area, worth further exploration.

Acknowledgments

The work of MB and JP was supported by the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1 and the Graduiertenkolleg "Facets of Complexity" (GRK 2434). The work of GP was supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the "3rd Call for H.F.R.I. PhD Fellowships" (Fellowship Number: 5163). The work of EM has been supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the "First Call for H.F.R.I. Research Projects to support faculty members and researchers and the procurement of high-cost research equipment" grant (Project Number: HFRI-FM17-3512). The authors would like to thank J´erˆome Lang for graciously hosting MB, GP, and JP concurrently at Paris Dauphine University, where this work was initiated. The visit of MB has been supported by a visiting professorship from Paris Dauphine University and the visit of GP has been supported by COST Action CA16228 - GAMENET. GP is also grateful to the Hellenic Artificial Intelligence Society (EETN) for their support.