How to Sample Approval Elections?

1 Introduction

In an approval election [Brams and Fishburn, 1983], each voter indicates which candidates he or she finds acceptable for a certain task (e.g., to be a president, to join the parliament, or to enter the final round of a competition) and a voting rule aggregates this data into the final outcome. In the single-winner setting (e.g., when choosing the president), the most popular rule is to pick the candidate with the highest number of approvals. In the multiwinner setting (e.g., in parliamentary elections or when choosing finalists in a competition) there is a rich spectrum of rules to choose from, each with different properties and advantages. Approval voting is particularly attractive due to its simplicity and low cognitive load imposed on the voters. Indeed, its practical applicability has already been tested in a number of field experiments, including those in France [Laslier and der Straeten, 2008; Baujard and Igersheim, 2011; Bouveret et al., 2019] and Germany [Al´os-Ferrer and Grani´c, 2012]. Over the recent years there was also tremendous progress regarding its theoretical properties (see, e.g., the overviews of Laslier and Sanver [2010] and Lackner and Skowron [2021]).

In spite of all these achievements, numerical experiments regarding approval voting are still challenging to design. One of the main difficulties is caused by the lack of consensus on which statistical election models to use. Below we list a few models (i.e., statistical cultures) that were recently used:

1. In the impartial culture setting, we assume that each vote is equally likely. Taken literally, this means that each voter approves each candidate with probability 1/2 [Barrot et al., 2017]. As this is quite unrealistic, several authors treat the approval probability as a parameter [Bredereck et al., 2019; Faliszewski et al., 2020] or require that all voters approve the same (small) number of can-
2. didates [Lackner and Skowron, 2020]. A further refinement is to choose an individual approval probability for each candidate [Lackner and Maly, 2021].
3. In Euclidean models, each candidate and voter is a point in Rd , where d is a parameter, and a voter approves a candidate if they are sufficiently near. Such models are used, e.g., by Bredereck et al. [2019] and Godziszewski et al. [2021]. Naturally, the distribution of the candidate and voter points strongly affects the outcomes.
4. Some authors consider statistical cultures designed for the ordinal setting (where the voters rank the candidates from the most to the least desirable one) and let the voters approve some top-ranked candidates (e.g., a fixed number of them). This approach is taken, e.g., by Lackner and Skowron [2020] on top of the ordinal Mallows model (later on, Caragiannis et al. [2022] provided approval-based analogues of the Mallows model).

Furthermore, even if two papers use the same model, they often choose its parameters differently. Since it is not clear how the parameters affect the models, comparing the results from different papers is not easy. Our goal is to initiate a systematic study of approval-based statistical cultures and attempt to rectify at least some of these issues. We do so by extending the map-of-elections framework of Szufa et al. [2020] and Boehmer et al. [2021] to the approval setting.

Briefly put, a map-of-elections is a set of elections with a distance between each pair. We embed these elections in a plane, by representing each election as a point, so that the Euclidean distances between these points are similar to the original distances between the respective elections. Such maps help in obtaining insights about the elections they contain.

To create a map-of-elections for approval elections, we start by identifying two metrics between approval elections, the isomorphic Hamming distance and the approvalwise distance. The first one is accurate, but difficult to compute, whereas the second one is less precise, but easily computable. Fortunately, in our datasets the two metrics are strongly correlated, so we use the latter one.

Next, we analyze the space of approval elections with a given number of candidates and voters. For each p ∈ [0, 1], by p-identity (p-ID) elections we mean those where all the votes are identical and approve the same p-fraction of candidates. By p-impartial culture (p-IC) elections we mean those where each voter chooses to approve each candidate with probability p. We view p-ID and p-IC elections as two extremes on the spectrum of agreement between the voters and, intuitively, we expect that every election (where each voter approves on average a p fraction of candidates) is located somewhere between these two. In particular, for p, φ ∈ [0, 1], we introduce the (p, φ)-resampling model, which generates elections whose expected approvalwise distance from p-ID is exactly the φ fraction of the distance between p-ID and p-IC.

Armed with these tools, we proceed to draw maps of elections. First, we consider p-ID, p-IC, and (p, φ)-resampling elections, where the p and φ values are chosen to form a grid, and compute the approvalwise distances between them. We find that, for a fixed value of p, the (p, φ)-resampling elections indeed form lines between the p-ID and p-IC ones, whereas for fixed φ values they form lines between 0-ID and 1-ID ones (which we refer to as the empty and full elections). We obtain more maps by adding elections generated according to other statistical cultures; the presence of the (p, φ)- resampling grid helps in understanding the locations of these new elections. For each of our elections we compute several parameters, such as, e.g, the highest number of approvals that a candidate receives, the time required to compute the results of a certain multiwinner voting rule, or the cohesiveness level (see Section 2 for a definition). For each of the statistical cultures, we present maps where we color the elections according to these values. This gives further insight into the nature of the elections they generate. Finally, we compare the results for randomly generated elections with those appearing in real-life, in the context of participatory budgeting.

2 Preliminaries

For a given positive integer t, we write [t] to denote the set {1, 2, . . . , t}, and [t]0 as an abbreviation for [t] ∪ {0}.

Elections. A (simple) approval election E = (C, V ) consists of a set of candidates C = {c1, . . . , cm} and a collection of voters V = (v1, . . . , vn). Each voter v ∈ V casts an approval ballot, i.e., he or she selects a subset of candidates that he or she approves. Given a voter v, we denote this subset by A(v). Occasionally, we refer to the voters or their approval ballots as votes; the exact meaning will always be clear from the context. An approval-based committee election (an ABC election) is a triple (C, V, k), where (C, V ) is a simple approval election and k is the size of the desired committee. We use simple elections when the goal is to choose a single individual, and ABC elections in the multiwinner setting. Given an approval election E (be it a simple election or an ABC election) and a candidate c, we write scoreav (c) to denote the number of voters that approve c. We refer to this value as the approval score of c. The single-winner approval rule (called AV) returns the candidate with the highest approval score (or the set of such candidates, in case of a tie).

Distances Between Votes. For two voters v and u, their Hamming distance is ham(v, u) = |A(v)△A(u)|, i.e., the number of candidates approved by exactly one of them. Other distances include, e.g., the Jaccard one, defined as jac(v, u) = ham(v,u) |A(v)∪A(u)| . For other examples of such distances, we point to the work of Caragiannis et al. [2022].

Approval-Based Committee Voting Rules. An approvalbased committee voting rule (an ABC rule) is a function that maps an ABC election (C, V, k) to a nonempty set of committees of size k. If an ABC rule returns more than one committee, then we consider them tied.

We introduce two prominent ABC rules. Multiwinner Approval Voting (AV) selects the k candidates with the highest approval scores. Given a committee W, its approval score is the sum of the scores of its members; scoreav(W) = ∑w∈W scoreav (w). If there is more than one committee that achieves a maximum score, AV returns all tied committees. The second rule is Proportional Approval Voting (PAV). PAV outputs all committees with maximum PAV-score:

where h(x) = ∑xj=1 1/j is the harmonic function. Intuitively, AV selects committees that contain the "best" candidates (in the sense of most approvals) and PAV selects committees that are in a strong sense proportional [Aziz et al., 2017]. In contrast to AV, which is polynomial-time computable, PAV is NP-hard to compute [Aziz et al., 2015; Skowron et al., 2016]. In practice, PAV can be computed by solving an integer linear program [Peters and Lackner, 2020] or by an approximation algorithm [Dudycz et al., 2020].

Cohesive Groups. Intuitively, a proportional committee should represent all groups of voters in a way that (roughly) corresponds to their size. To speak of proportional committees in ABC elections, Aziz et al. [2017] introduced the concept of cohesive groups.

Definition 1. Consider an ABC election (C, V, k) with n voters and some non-negative integer ℓ. A group of voters V ′ ⊆ V is ℓ-cohesive if (i) |V ′ | ≥ ℓ · nk and (ii) ∣∣⋂v∈V ′ A(v)∣∣ ≥ ℓ.

An ℓ-cohesive group is large enough to deserve ℓ representatives in the committee and is cohesive in the sense that there are ℓ candidates that can represent it. A number of proportionality notions have been proposed based on cohesive groups, such as (extended) justified representation [Aziz et al., 2017], proportional justified representation [S´anchez-Fern´andez et al., 2017], proportionality degree [Skowron, 2021], and others. All these notions make certain proportionality guarantees for the cohesive groups (see also the survey of [Lackner and Skowron, 2021] for a comprehensive overview).

3 Statistical Cultures for Approval Elections

In the following, we present several statistical cultures (probabilistic models) for generating approval elections. Our input consists of the desired number of voters n and a set of candidates C = {c1, . . . , cm}. For models that already exist in the literature, we provide examples of papers that use them.

Resampling, IC, and IDModels. Let p and φ be two numbers in [0, 1]. In the (p, φ)-resampling model, we first draw a central ballot u, by choosing ⌊p·m⌋ approved candidates uniformly at random; then, we generate each new vote v by initially setting A(v) = A(u) and executing the following procedure for every candidate ci ∈ C: With probability 1-φ, we leave ci's approval intact and with probability φ we resample its value (i.e., we let ci be approved with probability p). The resampling model is due to this paper and is one of our basic tools for analyzing approval elections. By fixing φ = 1, we get the p-impartial culture model (p-IC) where each candidate in each vote is approved with probability p; it was used, e.g., by Bredereck et al. [2019] and Faliszewski et al. [2020]. By fixing φ = 0, we ensure that all votes in an election are identical (i.e., approve the same p fraction of the candidates). We refer to this model as p-identity (p-ID).

Disjoint Model. The (p, φ, g)-disjoint model, where p and φ are numbers in [0, 1] and g is a non-negative integer, works as follows: We draw a random partition of C into g sets, C1, . . . ,Cg, and, to generate a vote, we choose i ∈ [g] uniformly at random and sample the vote from a (p, φ)-resampling model with the central vote that approves exactly the candidates fromCi (while the central votes are independent of p, we still need this parameter for resampling).

Noise Models. Let p and φ be two numbers from [0, 1] and let d be a distance between approval votes. We require that d is polynomial-time computable and, for each two approval votes u and v, d(u, v) depends only on |A(u)|, |A(v)|, and |A(u) ∩ A(v)|; both distances from Section 2 have this property. In the (p, φ, d)-Noise model we first generate a central vote u as in the resampling model and, then, each new vote v is generated with probability proportional to φd(u,v) . Such noise models are analogous to the Mallows model for ordinal elections and were studied, e.g., by Caragiannis et al. [2022]. In particular, they gave a sampling procedure for the case of the Hamming distance. We extend it to arbitrary distances.

Proposition 1. There is a polynomial-time sampling procedure for the (p, φ, d)-noise models (as defined above).

In the reminder, we only use the noise model with the Hamming distance and we refer to it as the (p, φ)-noise model. Note that the roles of p and φ in this model are similar, but not the same, as in the resampling one (for example, for φ = 0 we get the p-ID model, but for φ = 1 get the 0.5-IC one).

Euclidean Models. In the t-dimensional Euclidean model, each candidate and each voter is a point from Rt and a voter v approves candidate c if the distance between their points is at most r (this value is called the radius); such models were discussed, e.g., in the classical works of Enelow and Hinich [1984,1990], and more recently by Elkind and Lackner [2015], Elkind et al. [2017], Bredereck et al. [2019], and Godziszewski et al. [2021]. We consider t-dimensional models for t ∈ {1, 2}, where the agents' points are distributed uniformly at random on [0, 1]t . We refer to them as 1DUniform and 2D-Square models (note that to fully specify each of them, we also need to indicate the radius value).

Truncated Urn Models. Let p be a number in [0, 1] and let α be a non-negative real number (the parameter of contagion). In the truncated P´olya-Eggenberger Urn Model [Berg, 1985] we start with an urn that contains all m! possible linear orders over the candidate set. To generate a vote, we (1) draw a random order r from the urn, (2) produce an approval vote that consists of ⌈p · m⌉ top candidates according to r (this is the generated vote), and (3) return αm! copies of r to the urn. For α = 0, all votes with ⌈p · m⌉ approved candidates are equally likely, whereas for large values of α all votes are likely to be identical (so the model becomes similar to p-ID).

4 Metrics

Next we describe two (pseudo)metrics used to measure distances between approval elections. Since we are interested in distances between randomly generated elections, our metrics are independent of renaming the candidates and voters.

Consider two equally-sized candidate sets C and D, and a voter v with a ballot over C. For a bijection σ: C → D, by σ(v) we mean a voter with an approval ballot A(σ(v)) = {σ(c) | c ∈ C}. In other words, σ(v) is the same as v, but with the candidates renamed by σ. We write Π(C,D) to denote the set of all bijections from C to D. For a positive integer n, by Sn we mean the set of all permutations over [n]. Next, we define the isomorphic Hamming distance (inspired by the metrics of Faliszewski et al. [2019]).

Definition 2. Let E = (C, V ) and F = (D,U) be two elections, where |C| = |D|, V = (v1, . . . , vn) and U = (u1, . . . , un). The isomorphic Hamming distance between E and F , denoted dham(E, F), is defined as:

Intuitively, under the isomorphic Hamming distance we unify the names of the candidates in both elections and match their voters to minimize the sum of the resulting Hamming distances. We call this distance isomorphic because its value is zero exactly if the two elections are identical, up to renaming the candidates and voters. Computing this distance is NP-hard (see also the related results for approximate graph isomorphism [Arvind et al., 2012; Grohe et al., 2018]).

Proposition 2. Computing the isomorphic Hamming distance between two approval elections is NP-hard.

Thus we compute this distance using a brute-force algorithm (which is faster than using, e.g., ILP formulations). Since this limits the size of elections we can deal with, we also introduce a simple, polynomial-time computable metric.

Definition 3. Let E be an election with candidate set {c1, . . . , cm} and n voters. Its approvalwise vector, denoted av(E), is obtained by sorting the vector (scoreav(c1)/n, . . . , scoreav (cm)/n) in non-increasing order.

Definition 4. The approvalwise distance between elections E and F with approvalwise vectors av(E) = (x1, . . . , xm) and av(F) = (y1, . . . , ym) is defined as:

In other words, the approvalwise vector of an election is a sorted vector of the normalized approval scores of its candidates, and an approvalwise distance between two elections is the ℓ1 distance between their approvalwise vectors. We sort the vectors to avoid the explicit use of a candidate matching, as is needed in the Hamming distance. Occasionally we will speak of approvalwise distances between approvalwise vectors, without referring to the elections that provide them.

It is clear that the approvalwise distance is computable in polynomial time. Yet, it is not as clear that its values are

Figure 2: Correlation between Hamming and approvalwise metrics.

actually meaningful. In Section 6.3 we will show that in our datasets it is strongly correlated with the Hamming distance and, so, in the following, we focus on approvalwise distances.

5 AGrid of Approval Elections

To better understand the approvalwise metric space of elections, next we analyze expected distances between elections generated according to the (p, φ)-resampling model.

Fix some number m of candidates and parameters p, φ ∈ [0, 1], such that pm is an integer, and consider the process of generating votes from the (p, φ)-resampling model. In the limit, the approvalwise vector of the resulting election is:

Indeed, each of the pm candidates approved in the central ballot either stays approved (with probability 1 - φ) or is resampled (with probability φ, and then gets an approval with probability p). Analogous reasoning applies to the remaining (1 - p)m candidates. With a slight abuse of notation, we call the above vector av(p, φ). Furthermore, we refer to av(p, 0) as the p-ID vector, to av(p, 1) as the p-IC vector, and to 0ID and 1-ID vectors as the empty and full ones, respectively (note that 0-ID = 0-IC and 1-ID = 1-IC).

Now, consider two additional numbers, p′ , φ′ ∈ [0, 1], such that p′m is an integer. Simple calculations show that:

Thus dapp(av(p, φ), empty) = mp is a p fraction of the distance between empty and full, and dapp(av(p, φ), p-ID) = 2mp(1-p)φ is a φ fraction of the distance between p-IC and p-ID (see also Figure 1). Furthermore, dapp(empty, full) = m is the largest possible approvalwise distance.

Intuitively, (p, φ)-resampling elections form a grid that spans the space between extreme points of our election space; the larger the φ parameter, the more "chaotic" an election becomes (formally, the closer it is to the p-IC elections), and the larger the p parameter, the more approvals it contains (the closer it is to the full election). We use (p, φ)-resampling elections as a background dataset, which consists of 241 elections with 100 candidates and 1000 voters each, with the following p and φ parameters:

1. p is chosen from{0, 0.1, 0.2, . . . , 0.9, 1} and φ is chosen from the interval (0, 1), 1 or
2. φ is chosen from {0, 0.25, 0.5, 0.75, 1} and p is chosen from the interval (0, 1).

For each of these elections we compute a point in R2 , so that the Euclidean distances between these points are as similar to the approvalwise distances between the respective elections as possible. For this purpose, similarly to Szufa et al. [2020], we use the Fruchterman-Reingold force-directed algorithm [Fruchterman and Reingold, 1991]. For the resulting map, see the clear grid-like shape at the left side of Figure 3. Whenever we present maps of elections later in the paper, we compute them in the same way (but for datasets that include other elections in addition to the background ones).

6 Experiments

In this section, we use the map-of-elections approach to analyze quantitative properties of approval elections generated according to our models. In particular, we will see how an election's position in the grid influences each of the properties, and what parameters to use to generate elections with the quantitative property in a desired range.

6.1 Experimental Design

Concretely, we consider the following four statistics:

Max. Approval Score. The highest approval score among all candidates in a given election, normalized by the maximum possible score, i.e., the number of voters.

Cohesiveness Level. The largest integer ℓ such that there exists an ℓ-cohesive group (for committee size 10).

Voters in Cohesive Groups. Fraction of voters that belong to at least one 1-cohesive group (for committee size 10).

PAVRuntime. Runtime (in seconds) required to compute a winning committee under the PAV rule, by solving an integer linear program provided by the abcvoting library [Lackner et al., 2021], using the Gurobi ILP solver.

We use six datasets. Five of them are generated using our statistical cultures and consist of 100 candidates and 1000

1 By generating t elections with a parameter from interval (a, b), we mean generating one election for each value a+i b-a t+1 , for i ∈ [t].

voters (except for the experiments related to the cohesiveness level, where we have 50 candidates and 100 voters, due to computation time). We have: 250 elections from the Disjoint Model (50 for each g ∈ {2, 3, 4, 5, 6} with φ ∈ (0.05, 1/g)); 225 elections from the Noise Model with Hamming distance (25 for each p ∈ {0.1, 0.2, . . . , 0.9} with φ ∈ (0, 1)); 225 elections from the Truncated Urn Model (25 for each p ∈ {0.1, 0.2, . . . , 0.9} with α ∈ (0, 1)); 200 elections from Euclidean Model (100 for 1D-Uniform, with radius in (0.0025, 0.25), and 100 for 2D-Square, with radius in (0.005, 0.5)); these parameters are as used by Bredereck et al. [2019]. The sixth dataset uses real-life participatory budgeting data and contains 44 elections from Pabulib [Stolicki et al., 2020], where for each (large enough) election we randomly selected a subset of 50 candidates and 1000 voters.

6.2 Experimental Results

Our visualizations are shown in Figures 3 and 4. We use the grid structure of the background dataset for comparison. with other datasets. Notably, some of them do not fill this grid. This is most striking for the real-world dataset, Pabulib (Figure 4d), which is placed very distinctly in the bottom left part.

To get an intuitive understanding of the four statistics, let us consider the background dataset in Figure 3a. We see that the highest approval score is lowest in the lower left side and increases towards up and right. This is sensible: If the average number of approved candidates increases, so does this statistic; also, if voters become more homogeneous, high-scoring candidates are likely to exist. Regarding voters in cohesive groups, it turns out that in most elections almost all voters belong to a 1-cohesive group, with the left lower part as an exception (where there are not enough approvals to form 1cohesive groups). The time needed to find a winning committee under PAV is correlated with the distance from 0.5-IC. Similar to the highest approval score, the cohesiveness level increases when moving up or right in the diagram. Cohesive groups with levels close to the committee size only exist in very homogeneous elections (rightmost path) and elections with many approvals (top part).

We move on to the results for the five other datasets. Note that each figure also contains the background dataset (gray dots) for reference. These results help to understand the differences between our statistical cultures.

The maximum approval score statistic provides an insight into whether there is a candidate that is universally supported. Instances with a value close to 1 possess such a candidate. In a single-winner election, this candidate is likely to be a clear winner. This is undesirable when simulating contested elections or shortlisting. Also note that in the real-world data set (Pabulib) we do not observe the existence of such a candidate.

When looking at the PAV runtime, we find some statistical cultures that generate computationally difficult elections, e.g., the (p, φ)-resampling model with parameter values close to p = 0.5 and φ = 1 (0.5-IC), the noise model with parameters p ∈ [0.5, 0.9] and φ > 0.5, and the disjoint model with g = 2. Yet, instances from the real-world dataset, as well as from the Euclidean and urn ones, can be computed very quickly. 2

Concerning voters in cohesive groups, whenever this statistic is close to 1, it is easy to provide most voters with at least one approved candidate in the committee; such committees are easy to find [Aziz et al., 2017]. Since many proportional rules take special care of voters that belong to cohesive groups, in such elections there are no voters that are at a systematic disadvantage. In many of our generated elections (almost) all voters belong to 1-cohesive groups, but this is not the case for the real-world, Pabulib data and it would be interesting to find statistical model that would behave similarly. For the cohesiveness level, we see that all models generate a full spectrum (i.e., [0, 10]) of cohesiveness levels. That said, we expect realistic elections to appear in the "lower left" part of our grid (with few approvals), and such elections tend to have low cohesiveness levels. Indeed, this is the case for Pabulib elections. Thus it is important how proportional rules treat ℓ-cohesive groups with small ℓ.

2 Less than 1 second on a single core (Intel Xeon Platinum 8280 CPU @ 2.70GH) of a 224 core machine with 6TB RAM. In contrast, the worst-case instance (0.3-IC) required 25 minutes on 13 cores.

6.3 Correlation

Figures 3 and 4 are based on the approvalwise distance, but they would not change much if we used the (computationally intractable) isomorphic Hamming distance. To verify this claim, we generated 363 elections with 10 candidates and 50 voters from the statistical cultures used in the previous experiment and compared Hamming and approvalwise distances between them: The results are in Figure 2, where each dot represents a pair of elections, and its coordinates are the respective distances between them. The Pearson Correlation Coefficient is 0.989, and for 67% pairs of elections the distances (after normalization) are identical.

This last observation requires comments. On the one hand, we observe that the two distances often coincide when the distances are large. This happens, e.g., if one election is dense (i.e., each voter approves many candidates) and the other one is sparse (i.e., each voter approves few candidates). In such cases, it is likely that every ballot A(vi) from the sparse election can be mapped to some ballot B(uj ) in the dense election such that A(i) ⊆ B(j). If this is the case, then both distances coincide. On the other hand, equality of the distances is unlikely, e.g., for elections generated from 0.5-IC.

7 Conclusions and FutureWork

We propose to use the resampling model as a baseline in numerical experiments on approval voting. An important task for future work is to broadly study real-world datasets with the methods proposed in this paper. It would also be interesting to consider further statistics than the ones we used.

Acknowledgements

Martin Lackner was supported by the Austrian Science Fund (FWF), project P31890. Nimrod Talmon was supported by the Israel Science Foundation (ISF; GrantNo.630/19). This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 101002854).