# explainable_and_efficient_randomized_voting_rules__a9504608.pdf

Explainable and Efﬁcient Randomized Voting Rules

Soroush Ebadian University of Toronto soroush@cs.toronto.edu

Aris Filos-Ratsikas University of Edinburgh Aris.Filos-Ratsikas@ed.ac.uk

Mohamad Latiﬁan University of Toronto latifian@cs.toronto.edu

Nisarg Shah University of Toronto nisarg@cs.toronto.edu

With a rapid growth in the deployment of AI tools for making critical decisions (or aiding humans in doing so), there is a growing demand to be able to explain to the stakeholders how these tools arrive at a decision. Consequently, voting is frequently used to make such decisions due to its inherent explainability. Recent work suggests that using randomized (as opposed to deterministic) voting rules can lead to signiﬁcant efﬁciency gains measured via the distortion framework. However, rules that use intricate randomization can often become too complex to explain to the stakeholders; losing explainability can eliminate the key advantage of voting over black-box AI tools, which may outweigh the efﬁciency gains. We study the efﬁciency gains which can be unlocked by using voting rules that add a simple randomization step to a deterministic rule, thereby retaining explainability. We focus on two such families of rules, randomized positional scoring rules and random committee member rules, and show, theoretically and empirically, that they indeed achieve explainability and efﬁciency simultaneously to some extent.

1 Introduction

In the past decade, AI and machine learning solutions have been deployed ubiquitously to make increasingly critical decisions that affect human lives. Consequently, there is a growing demand for these models and their decisions to be explainable [1, 2]. The literature makes a distinction between two types of explanations: outcome explanations, which explain to the stakeholders why the chosen outcome was selected in a given instance, and procedural explanations, which explain to the stakeholders the procedure of choosing outcomes across all possible instances.Much of the explainable AI (XAI) literature focuses on outcome explanations because many black-box AI solutions used in practice are too complex to admit simple procedural explanations [3].

However, there are several drawbacks of outcome explanations. First, it opens up the possibility of post-hoc explanations for why an outcome was selected. These are susceptible to adversarial reasoning that hides biases [4]. Also, psychological research suggests that people s perception of fairness of an outcome depends not only on the outcome itself, but also on the process by which the outcome is selected [5, 6], and the same outcome may be perceived as fair or unfair depending on the process used [6]. This motivates the need for procedural explanations. Note that an intuitive explanation of the procedure to select outcomes already serves as a rudimentary justiﬁcation for why a given outcome was selected.

To that end, we turn our attention to voting. While explainability is a nascent demand in the AI ecosystem, voting rules, historically deployed for political decision-making, have always battled with the need to be able to explain to the voters how the winner of an election is chosen. Thus,

37th Conference on Neural Information Processing Systems (Neur IPS 2023).

most prominent voting rules admit intuitive procedural explanations. Due to this key advantage over black-box AI solutions, they have been used to automate decision-making in a variety of applications such as designing recommender systems [7, 8], information extraction [9], collaborative ﬁltering [10], ensemble learning [11], and game-playing by AI agents [12]. The advantage is more apparent when the decisions at hand are more signiﬁcant. For example, Noothigattu et al. [13] and Kahng et al. [14] propose the design of a voting-based virtual democracy system that can automate ethical decisionmaking in AI systems. When Lee et al. [15] applied this framework to automate the distribution of food donations, they found that their stakeholders appreciated the fact that voting-based decisionmaking embodied democratic values and being able to provide easy explanations allowed them to understand how algorithmic recommendations were made .

However, most prominent voting rules are deterministic because their primary use case is making infrequent, high-stakes democratic decisions, for which randomization is generally unpalatable [16]. Aside from selected applications such as forming citizens assemblies, juries, and independent redistricting commissions, lottery is seldom used to select representatives [17]. But in AI applications, it is common to make frequent, low-stakes decisions, for which randomization is well-suited.

Research on voting theory suggests that allowing the voting rule to randomize has numerous beneﬁts. It can be essential for avoiding the tyranny of the majority and guarantee minority representation [18, 19]. Randomization also acts as a barrier to manipulations by strategic agents by circumventing the

Gibbard-Satterthwaite impossibility [20, 21]. Most importantly, it can unlock signiﬁcant efﬁciency gains over using deterministic voting rules [22, 23, 19]. Unfortunately, randomized voting rules designed to optimize for efﬁciency can be highly complex and rely on intricate mathematical results such as the minimax theorem [19], making them difﬁcult to explain to the end users.

In view of this, we explore the use of explainable randomized voting rules for improving the efﬁciency of automated decision-making. To ensure explainability, one possibility is to use only extremely simple randomized rules such as random dictatorship, where the most preferred option of a randomly chosen agent is selected. But this may leave signiﬁcant possible efﬁciency gains on the table. Instead, we propose a hybrid approach that adds a simple (and thus, explainable) randomization step to well-understood deterministic decision-making processes. This drives our main research question:

What efﬁciency gains can be unlocked by explainable randomized voting rules which add a simple randomization step to deterministic voting rules?

As a yardstick for efﬁciency, we turn to the distortion framework [24]. Proposed by Procaccia and Rosenschein [25], this framework posits that votes submitted by agents, typically rankings over a set of alternatives, are induced by more expressive preferences underneath, typically cardinal utility functions over the alternatives. In this framework, the goal of a randomized voting rule is to choose a lottery over the alternatives that minimizes distortion, the worst-case ratio between maximum social welfare (total utility to the agents) and that of the chosen lottery.

We study the distortion of two families of randomized voting rules, which we refer to as randomized positional scoring rules and random committee member rules. The former builds on the widelypopular family of (deterministic) positional scoring rules, under which each agent assigns a score to each alternative based on its position in her ranking. But instead of deterministically selecting an alternative with the highest total score, each alternative is selected with probability proportional to its score. In contrast to picking alternatives with varying probabilities, the latter family utilizes the simplicity of uniform randomization by picking, uniformly at random, a member of a subset of alternatives chosen deterministically. Our inspiration for these two families stems from the use of such rules by Boutilier et al. [22] and Ebadian et al. [19].

Let us illustrate an example rule from each family based on the popular Borda count method, in which scores of m 1, . . . , 0 are assigned to ranks 1, . . . , m respectively. A rule from the ﬁrst family would pick each alternative with probability proportional to its total Borda score, while a rule from the second family may select uniformly at random among the k alternatives with the highest Borda scores, for some ﬁxed k. We select these two families of randomized voting rules because they admit straightforward procedural explanations. For instance, the aforementioned rules based on Borda count can be explained as follows (using version (a) for the former and (b) for the latter using k = 3).

Each user gives zero points to their least preferred option, one point to the next best option, two points to the next best option, and so on. Points are tallied and...

Table 1: Distortion and minimum welfare of common randomized positional scoring rules.

Plurality Borda Harmonic Veto k-Approvals k 2 [1, m1/3]k 2 [m1/3, pm] k 2 [pm, m]

dist (mpm) (m5/4) (pm Hm) (m) ( mpm

m k + 1) min-sw

! n k(m k+1)

(a) the chances of each option being selected are proportional to its total points. (b) the three options with the highest total points are selected with an equal chance.

Unlike prior work on distortion, which is often focused on identifying the most efﬁcient rule, we provide a reﬁned analysis that characterizes the distortion of many interesting rules in these families, allowing the system designer to pick the one most suited to the application at hand.

1.1 Our Results

Randomized positional scoring rules. We develop a whole swathe of novel techniques for analyzing distortion, and use them to obtain tight distortion (dist) bounds for randomized versions of wellknown positional scoring rules such as plurality, Borda count, harmonic, veto, and k-approval, presented in Table 1. For comparison, we remark that the distortion of the best possible deterministic voting rule is (m2) [26, 23] and the best possible randomized voting rule is (pm) [19, 22]. For randomized positional scoring rules, the best bound is (pm log m) due to [22]. En route to the distortion bounds shown in Table 1, we also obtain tight bounds for another useful efﬁciency metric, minimum welfare (min-sw), deﬁned in Section 3.1. In the supplementary material, we apply our novel techniques to analyze the distortion of randomized multi-level approval rules, which are uniform mixtures of different randomized k-approval rules. We demonstrate the strength of this result by using it to derive tight distortion bounds for a recently studied randomized positional scoring rule due to Gkatzelis et al. [27].

Our distortion bound for the randomized plurality rule (better known as random dictatorship) may be of independent interest because it is a widely studied voting rule [28 30]. It is also fascinating that the distortion of randomized k-approval is highly non-monotone: ﬁrst decreasing from (mpm) to (m) when k grows from 1 to m1/3, then staying (m) when k grows further to pm, then increasing again to (mpm) by k = m (m), and ﬁnally decreasing again to (m) by k = m.

Random committee member rules. For the family of random committee member rules, we design a novel voting rule, which selects a random member of a top-biased stable k-committee, and achieves a distortion of O(max{k, m2/(k

k)}). We complement this with a lower bound of (max{k, m2/k2}) on the distortion of any rule in this class.

Experiments. Our experiments with synthetic data indicate that while the (worst-case) distortion of various rules in both families is not signiﬁcantly better than the optimal deterministic distortion of (m2) and often even worse than the (m) distortion of the trivial rule selecting a uniformly random alternative, rules from both families (almost always) signiﬁcantly outperform deterministic voting rules and randomized positional scoring rules (almost always) outperform the uniform-random rule as well. This suggests that one should strongly consider replacing deterministic rules with explainable randomized rules from these two families in order to achieve signiﬁcantly improved efﬁciency.

1.2 Additional Related Work

Outcome explanations in voting. We focus on (randomized) voting rules with procedural explanations because that is, in our view, the key advantage of voting over black-box AI solutions. Nonetheless, there is also compelling literature on producing outcome explanations for voting rules. Classical work that seeks voting rules satisfying qualitative axioms such as Condorcet consistency can be viewed in this light. However, these axioms often provide a justiﬁcation only in limited instances with a special structure. Cailloux and Endriss [31] propose a method for producing a justiﬁcation on any given instance by starting from an axiomatic justiﬁcation on a nearby special instance and using a chain of explanations relating adjacent pairs of instances to arrive at the given instance. Peters et al.

[32] bound the length of such chains, focusing especially on positional scoring rules, while Boixel and Endriss [33] and Boixel et al. [34] study computational aspects of ﬁnding them.

On randomized positional scoring rules. The family of randomized positional scoring rules was ﬁrst proposed by Barbera [35], under the name of point-voting schemes. He establishes several appealing properties of these rules, including strategyproofness (i.e., no agent can ever strictly beneﬁt from misreporting her preferences). Note that the outcome of a randomized positional scoring rule can be computed by ﬁrst selecting an agent uniformly at random, and then, for each k, selecting her k-th most preferred alternative with probability proportional to score assigned to position k. In this sense, implementing a randomized positional scoring rule requires little elicitation.

On distortion. We use the utilitarian distortion framework proposed by Procaccia and Rosenschein [25] and developed by Boutilier et al. [22], where agents have unit-sum utilities over alternatives. This framework has been applied to a broad range of settings such as committee selection [36], participatory budgeting [37], distributed elections [38], elicitation-efﬁciency tradeoff [39 43], and matching [44, 40]. Our methodological novelty is that we are the ﬁrst to provide non-trivial absolute guarantees on the minimum welfare achieved across all instances, which is a reasonable efﬁciency measure in itself, and in turn use them to achieve tight distortion bounds (which compare the welfare achieved on each instance to the optimal welfare in that instance). We also note that there is a related framework of metric distortion [45], which assumes that agents have costs for the alternatives induced by an underlying metric space in which they are both embedded. This framework utilizes the restriction imposed by the triangle inequality instead of a unit-sum normalization. We refer the reader to the survey of Anshelevich et al. [24] for a detailed overview.

2 The Setting

Let us formally introduce our setting and deﬁne the notion of distortion. We will deﬁne each class of explainable voting rules in the section in which we will study it. We use the terminology of elections for consistency with the literature, but our setting captures a general decision-making scenario in which one of several alternatives must be chosen by aggregating conﬂicting preferences or opinions.

Basic notation. Let [t] = {1, 2, . . . , t} for t 2 N, and deﬁne (S) to be the probability simplex over the ﬁnite set S. For a vector ~s = (s1, . . . , st), denote its 1-norm by k~sk1 = P

Utilitarian voting. A (single-winner) election consists of sets N = [n] of n agents and A = [m] of m alternatives. Each agent i 2 N has a personal cardinal utility function ui : A 7! R>0, where ui(a) is the value associated by agent i to alternative a. Following the convention in the literature (e.g., see [22, 19]), we adopt the unit-sum normalization of utility functions: for every i 2 N, let P

a2A ui(a) = 1. Aziz [46] provides several compelling justiﬁcations for using unit-sum utility functions. For a utility proﬁle ~u = (u1, . . . , un) and a subset of agents T N, deﬁne the social welfare of an alternative a 2 A with respect to T as sw T (a, ~u) = P

i2T ui(a). We write sw N simply as sw, and drop ~u when it is clear from the context. As an extension, for a distribution p 2 (A) over the alternatives, deﬁne ui(p) = Ea p[ui(a)] and its social welfare as sw(p, ~u) = P

i2N ui(p). Our goal is to ﬁnd a distribution over alternatives with high social welfare. We will sometimes construct and analyze a partial utility proﬁle, where the utilities of each agent sum to at most 1.

Ordinal preferences and voting rules. We consider voting rules that have access only to the ordinal preferences induced by the utilities. This is because a ranking of alternatives can often be elicited with less cognitive burden or estimated more accurately than exact numerical utilities for each alternative.

Each agent i 2 N submits a preference ranking σi : [m] 7! A of the alternatives. We use ranki(a) = σ 1

i (a) to denote the rank of alternative a in agent i s preference ranking (the most preferred alternative has rank 1), and a i a0 to denote that agent i prefers a to a0 (i.e., ranki(a) < ranki(a0)). We assume that σi is consistent with agent i s utility function ui, i.e., a i a0 implies ui(a) > ui(a0) for all a, a0 2 A; ties can be broken arbitrarily without affecting our distortion upper bounds.

Let ~σ = (σi)i2N be a preference proﬁle and C(~σ) denote the set of utility proﬁles ~u such that σi is consistent with ui for each agent i 2 N. A voting rule f takes a preference proﬁle ~σ as input and returns a distribution p over alternatives.

Distortion. The distortion of a distribution p 2 (A) over alternatives with respect to a utility proﬁle ~u is deﬁned as

dist(p, ~u) = maxa2A sw(a, ~u)

sw(p, ~u) .

The distortion of a voting rule f is deﬁned as its worst-case distortion over all instances: distm(f) = sup~σ,~u2C(~σ) dist(f(~σ), ~u), where the supremum is taken over all instances with m alternatives and any number of agents. For simplicity, we drop m and write dist(f).

3 Distortion of Randomized Positional Scoring Rules

The ﬁrst class of explainable randomized voting rules we study is randomized positional scoring rules, or point-voting schemes [35]. This builds on the popular class of (deterministic) positional scoring rules, which assign scores to alternatives based on their positions in agents preference rankings, and adds an easy-to-explain randomization step where each alternative is chosen with probability proportional to its score instead of deterministically choosing the one with the highest score.

Positional scoring rules. A scoring vector ~s = (s1, . . . , sm) assigns a score sr to each position r 2 [m] and satisﬁes s1 > s2 > . . . > sm > 0. For an alternative a 2 A, let scorei(a,~s) = sranki(a) be the score a obtains from agent i, and for N 0 N, score N 0(a,~s) = P

i2N 0 scorei(a,~s). Note that P

a2A score N(a,~s) = n k~sk1. We drop ~s when it is clear from the context. For a scoring vector ~s, we can deﬁne the following rules.

- The deterministic positional scoring rule f det

~s selects the top scored alternative (breaking ties arbitrarily), i.e., f det

~s (~σ) = arg maxa2A score N(a,~s). - The randomized positional scoring rule f rand

~s selects every alternative a 2 A with probability proportional to its score, i.e., Pr[f rand

~s (~σ) = a] = score N(a,~s) / (n k~sk1).

The deterministic rules introduced above include several well-known voting rules such as plurality, Borda, k-approval, veto, and harmonic deﬁned, by the following scoring vectors, respectively:

~splu = (1, 0, . . . , 0), ~s Borda = (m 1, m 2, . . . , 0), ~sk-approval = (1, . . . , 1 | {z }

, 0, . . . , 0),

~sveto = (1, 1, . . . , 1, 0), ~sharmonic = (1, 1/2, 1/3, . . . , 1/m).

We refer to the randomized versions of these rules as randomized f , where f 2 {plurality, Borda, harmonic, veto}, and extend this terminology to any positional scoring rule f~s. Note that randomized plurality is more widely known as random dictatorship (see, e.g., [28, 29]).

3.1 High-Level Distortion Analysis and Novel Insights

Logarithmic rounding of the scores. Our ﬁrst useful insight is that we can reduce the number of distinct scores by rounding any score down to the nearest power of 1 + ,for a constant > 0, and this only changes the distortion of the rule by a factor of at most 1 + .

Lemma 1 (Rounding Down Scores). Let > 0, and ~s, ~s0 be scoring vectors such that s0

j 6 sj 6 (1 + )s0

j for all j 2 [m]. Then, for every preference proﬁle ~σ and consistent utility proﬁle ~u 2 C(~σ),

1 1 + sw(f rand

~s 0 (~σ), ~u) 6 sw(f rand

~s (~σ), ~u) 6 (1 + ) sw(f rand

~s 0 (~σ), ~u),

and consequently, 1 1+ dist(f rand

~s0 ) 6 dist(f rand

~s ) 6 (1 + ) dist(f rand

By applying this transformation, scores in the range [k~sk1/(4m2), k~sk1] can be reduced to O(log m) distinct values, which we will ﬁnd helpful in the subsequent sections. In the supplementary material, we show that by ignoring the remaining scores by reducing any sj 6 k~sk1/(4m2) to 0 changes the distortion further by another factor of at most two. Hence, we can limit our focus to scoring vectors that contain O(log m) distinct scores, resulting in only a constant factor loss in the distortion analysis.

High-level distortion analysis. After reducing the scoring vector to O(log m) distinct scores, we partition the agents into O(log m) groups based on where they rank the optimal alternative a . This is only for the analysis; the voting rule does not know the optimal alternative. More formally, let

0 = 0 < 1 < . . . < q = m be the indices where the score changes in the reduced scoring vector, where, for each r 2 [q], we have si = s r for all i 2 [ r 1 +1, r], and s 1 > . . . > s q. Furthermore, let Nr be the set of agents who rank a among positions [ r 1 + 1, r].

Next, borrowing an insight from the prior distortion literature [37, 42, 43], we round the agent utilities to the nearest power of two and ignore utilities below 1/m2, reducing the number of distinct utility values to O(log m) while losing at most a constant factor in the analysis. This allows us to subdivide voters in each group Nr into O(log m) subgroups such that every agent in a subgroup with the same utility, say , for a . We then employ three strategies to bound the distortion within each subgroup. Finally, we show that the overall distortion can be upper bounded, up to logarithmic factors, by the worst of these O(log2 m) distortion bounds across all subgroups of all the Nr groups.

Strategy 1 (Welfare above a ). Voters in a subgroup of Nr who have utility for a also have utility at least for their top r 1 alternatives. This helps us derive social welfare guarantees for the randomized positional scoring rule.

Strategy 2 (Probability of a ). We use the well-known observation (see, e.g., [22]) that the distortion is always upper bounded by the inverse of the probability of selecting a .

Strategy 3 (Absolute Welfare Lower Bounds). Another novel insight from our work is that proving an absolute lower bound on the welfare achieved by a rule across all instances can be useful in bounding the distortion, even though the latter needs to compare the welfare achieved in each instance to the optimum welfare in that instance. We carefully analyze and approximate, up to logarithmic factors, the minimum welfare achieved by the randomized positional scoring rules we study, and use it to bound its distortion. A similar idea has been used in other domains (see, e.g. [47]), but to the best of our knowledge, we are the ﬁrst to successfully apply it to distortion analysis. Deﬁnition 1 (Minimum Welfare). Deﬁne the minimum welfare of a distribution over alternatives p 2 (A) on a preference proﬁle ~σ as min-sw(p,~σ) = inf~u2C(~σ) sw(p, ~u), which is the minimum social welfare of p across all consistent utility proﬁles. The minimum welfare of a voting rule f is the minimum welfare of its output, minimized over all preference proﬁles: min-swn,m(f) = min~σ min-sw(f(~σ),~σ), where the minimum is taken over all preference proﬁles with n agents and m alternatives. We drop n and m when clear from the context.

Due to C(~σ) being compact, the inﬁmum in the min-sw(p,~σ) deﬁnition is indeed attained. In the supplementary material, we make an structural observation that for any preference proﬁle and distribution p 2 (A), the minimum welfare is at most n/m, attained at a dichotomous utility proﬁle. Furthermore, every randomized positional scoring rule f rand

~s satisﬁes min-sw(f rand

~s ) 2 [n/(4m2), n/m]. We also show how to approximate minimum welfare better (up to constants or logarithmic terms); see Table 1 for tight bounds for the rules induced by common scoring vectors.

To this end, we present our most intricate technical lemma to derive a generic welfare lower bound, which we use to apply Strategies 1 and 3. Instead of focusing only on Pr[f rand

~s (~σ) = a ], it bounds the overall welfare expression P

a2A Pr[f rand

~s (~σ) = a] sw T (a); the product of probability of selection and welfare of an alternative leads to a quadratic program, where the variables encode the worst case, and this is analytically solved using the Karush-Kuhn-Tucker (KKT) conditions. Lemma 2. Fix any scoring vector ~s, preference proﬁle ~σ, subset of agents T N, threshold > 0, and rank 2 [m]. For a partial utility proﬁle ~u in which every agent in T has utility at least for each of her top alternatives and all other utilities are 0, we have:

sw T (f rand

~s (~σ), ~u) > |T| 2nk~sk1

2s |T| + (n |T|)

Instead of tediously explaining the lemma, we will later show how its straightforward application wondrously gives us the desired welfare lower bound for the example of randomized Borda rule.

3.2 Analyzing Common Rules

We are ready to present our main result, which uses the aforementioned insights to pinpoint the asymptotic distortion of common randomized positional scoring rules. Theorem 2. For f 2 {plurality, Borda, harmonic, veto, k-approvals}, the minimum welfare (min-sw) and the distortion (dist) of the randomized f rule are as shown in Table 1.

Due to space limitations, we only provide a proof for the distortion upper bound of the randomized Borda rule, and defer the rest to the supplementary material. For conciseness, we use the notation Borda(a) , score(a,~s Borda). First, we need the following lower bound on its minimum welfare.

Lemma 3. The minimum welfare of the randomized Borda rule is min-sw(f rand

~s Borda) = ( n mpm).

Proof. Fix any preference proﬁle ~σ and consistent utility proﬁle ~u 2 C(~σ). Our goal is to show that sw(f rand

~s Borda(~σ), ~u) = ( n mpm). First, we make a few modiﬁcations to the scoring vector and the preference proﬁle that are guaranteed to not increase the welfare, and then invoke Lemma 2.

Simplify the scores. Let us consider the scoring vector ~s 0 which is equal to ~s Borda except the top m/2 scores are all equal to m/2. Note that s0

j 6 (s Borda)j 6 2s0

j for all j 2 [m]. Hence, invoking Lemma 1 with = 1 yields sw(f rand

~s Borda(~σ), ~u) > 1/2 sw(f rand

~s 0 (~σ), ~u).

Simplify the preference and utility proﬁles. Next, let us lower bound sw(f rand

~s 0 (~σ), ~u). For each agent i, let Ai be the set of top m/2 alternatives in σi and ai 2 arg mina2Ai score(a,~s 0) be the alternative in Ai with the lowest score (equivalently, probability of selection under f rand

~s 0 (~σ)). Now,

~s 0 (~σ)) >

score(a,~s 0)

> score(ai,~s 0)

> score(ai,~s 0)

where (1) follows from the deﬁnition of ai and (2) uses the fact that each agent has a total utility of at least 1/2 for her top m/2 alternatives (due to the pigeonhole principle).

Invoking Lemma 2. The ﬁnal expression above can be written as u0

~s 0 (~σ0)), where ~σ0 is a preference proﬁle in which each agent i ranks ai ﬁrst, and ~u0 is a partial utility proﬁle in which each agent i has utility 1/2 for her top alternative and 0 for the rest. Summing the above for all agents, we have sw(f rand

~s 0 (~σ), ~u) > sw(f rand

~s 0 (~σ0, ~u0)). Thus, to lower bound it, we invoke Lemma 2 with ~s ~s 0, ~σ ~σ0, T being an arbitrary subset of n/2 agents, 1/2, and 1. Using k~s 0k1 = m

8 , this gives us

~s 0 (~σ0), ~u0)

min h2[m/2]

= n 4m(3m 2) min h2[m/2]

2m 1) 4m(3m 2)

where the restriction to h 2 [m/2] in (1) is based on the fact that the bound would be (n/m) when h > m/2, (2) is due to the AM-GM inequality, and (3) uses m > 2. Connecting the dots, we have

~s Borda(~σ), ~u) > 1

2 sw(f rand

~s 0 (~σ), ~u) > 1

2 sw(f rand

~s 0 (~σ0), ~u0) > n 12mpm.

To translate the welfare lower bound from Lemma 3 into a distortion upper bound, we need the following relation between the Borda score of an alternative and its social welfare.

Lemma 4. For any preference proﬁle ~σ, consistent utility proﬁle ~u 2 C(~σ), and alternative a 2 A, we have sw(a) 6 (Borda(a) + n)/m.

The desired distortion upper bound can now be derived using a standard analysis. The crux of our proof for the randomized Borda rule lies in our intricate derivation of its minimum welfare in Lemma 3, for which Lemma 2 does the heavy lifting.

Lemma 5. The distortion of the randomized Borda rule is O(m5/4).

Proof. Fix any preference proﬁle ~σ and consistent utility proﬁle ~u 2 C(~σ). Let a 2 arg maxa2A sw(a, ~u) be an optimal alternative. By Strategy 2 from Section 3.1, we know that the distortion is at most nk~s Bordak1

Borda(a ) . Following Strategy 3 from Section 3.1 and the minimum wel-

fare analysis in Lemma 3, we have that distortion is at most sw(a ) n/(12mpm), which, using Lemma 4, is at

Borda(a )/n + 1

. Putting everything together, and using the fact that min{a, b} 6

ab for all a, b 2 R>0, the distortion is upper bounded by

nk~s Bordak1

Borda(a ) , Borda(a ) 12pm

Borda(a ) Borda(a ) 12pm

6m5/4 = O(m5/4).

4 Random Committee Member Rules

Next, we focus on our second class of explainable randomized voting rules that select an alternative uniformly at random from a shortlisted committee of size k 2 [m]. We call them random k-committee member rules. For k = 1, we are left with deterministic rules, among which plurality achieves the optimal distortion of (m2). For k = m, we are left with uniform selection among all alternatives, which has distortion (m). Is it possible that, for some intermediate value of k, we in fact achieve sublinear distortion? Could we achieve distortion at most logarithmic factors worse than the optimal (pm), like with randomized positional scoring rules? We answer the former positively but the latter negatively. First, we present a lower bound proving that any random k-committee member rule, for any value of k, incurs a distortion of at least (m2/3). Theorem 3. For k 2 [m], any random k-committee member rule incurs (max(k, m2/k2)) distortion. This lower bound is at least (m2/3) for all k.

As a result, this class of rules is less powerful than the class of randomized positional scoring rules, and thus, the class of all randomized rules. However, especially for small values of k, we gain the beneﬁt of randomizing over a small support, which could translate to greater explainability.

To derive upper bounds, one might be tempted to turn again to positional scoring rules, and consider selecting uniformly at random from the k alternatives with the highest score according to some scoring vector. In the supplementary material, we show that using plurality scoring vector yields (m(m k + 1)) distortion. While it nicely interpolates between the extremes of (m2) at k = 1 and (m) at k = m, it fails to achieve sublinear distortion, which we prove to be achievable. What about other scoring vectors? Unfortunately, it is relatively easy to see that using scoring vectors such as Borda, harmonic, or veto results in unbounded distortion. Despite the disappointing worst-case performance, we show in Section 5 that these rules perform relatively well empirically.

Next, we design a novel random k-committee member rule, which, with the right value of k, allows us to achieve sublinear distortion. Theorem 4. There is a polynomial-time computable random k-committee member rule with distortion O(max{k, m2/(k

k)}). This is minimized at k = m4/5, where the bound becomes O(m4/5).

To achieve the above, we concoct a three-way mixture of an approximately stable committee [48], a powerful notion which has been used to derive optimal randomized rules [19], alternatives with high plurality scores, and alternatives picked carefully to guarantee high minimum welfare from sufﬁciently many agents. We refer to the committee thus formed as a top-biased stable k-committee. The rule that returns this committee is presented as Algorithm 1 in the supplementary material.

Theorems 3 and 4 leave open the question of the optimal distortion that can be achieved by a random committee member rule, sandwiching this value between O(m4/5) and (m2/3). It is also interesting to wonder which value of k is optimal. Our upper bound is optimized at k = m4/5, and our lower bound implies that the optimal k must be in [m3/5, m4/5] as the distortion outside of that range is (m4/5). See Section 5 for an empirical evaluation of the optimal k.

5 Experiments

Next, we empirically evaluate the efﬁciency of explainable rules studied in the previous sections.

Rules. We consider three classes of rules: deterministic positional scoring rules, randomized positional scoring rules from Section 3, and, from Section 4, rules that select uniformly at random from the k alternatives with the highest scores (henceforth, uniform random k-positional scoring rules).

R Plurality

R 3-Approval

D Plurality

D 3-Approval

UR3 Plurality

UR3 Harmonic

UR3 3-Approval

10 20 30 40 50 m

Average distortion

(a) Average distortion with φ = 0.1.

10 20 30 40 50 m

Average distortion

(b) Average distortion with φ = 0.5.

10 20 30 40 50 m

Average distortion

(c) Average distortion with φ = 1.

0.0 0.2 0.4 0.6 0.8 1.0 f

URk Borda URk Plurality URk Harmonic URk 3-Approval

(d) Best value of k based on φ, for m = 25.

Figure 1: All ﬁgures show results averaged over 150 runs along with the standard error. Figures 1a to 1c share the legend on the left.

We consider four representative scoring vectors f 2 {Plurality, Borda, Harmonic, 3-Approval}, and denote the corresponding rules in the three classes by D f , R f , and URkf , respectively. Thus, overall, we test 12 voting rules. As benchmarks, we also add the Uniform rule, which selects an alternative uniformly at random from the set of all alternatives, and the Instance Optimal rule, which selects the lottery over alternatives minimizing distortion on the preference proﬁle. Boutilier et al. [22] show how to use linear programming to compute the latter in polynomial time.

Data Generation. We generate preference proﬁles by sampling n rankings over m alternatives iid from the Mallows model [49], which is widely used in machine learning and statistics. The model takes as input an underlying reference ranking σ (which can be set arbitrarily) and a dispersion parameter φ 2 [0, 1]. When φ = 1, the model converges to a uniform distribution over all m! rankings (also known as impartial culture), whereas φ ! 0 converges to the point distribution where σ is sampled with probability 1, so all the agents have the same preference ranking in the sampled proﬁle. For a precise deﬁnition of the model and an efﬁcient algorithm to sample from it (which we use in our experiments), see the work of Lu and Boutilier [50]. For each combination of n = 100 agents, m 2 {5, 10, . . . , 50} alternatives, and dispersion parameter φ 2 {0, 0.1, . . . , 1}, we sample 150 instances, and report averages along with the standard error. In the supplementary material, we report the results for two other statistical models namely the Polya-Eggenberger urn model [51] and the Plackett-Luce model [52, 53].

Evaluation. For each rule f under consideration and each instance ~σ, we evaluate the efﬁciency of the output f(~σ) by measuring its instance-speciﬁc distortion dist(f(~σ),~σ). Note that this still takes a worst case over the utility proﬁles consistent with ~σ, but unlike in Sections 3 and 4 where we also take a worst case over ~σ, here we compute the expected distortion over ~σ drawn from the Mallows model. Again, we compute dist(f(~σ),~σ) using the LP-based approach of Boutilier et al. [22].

Results. Figures 1a to 1c show the average distortion of different rules for φ 2 {0.1, 0.5, 1}, respectively, ﬁxing m = 25. For large φ (impartial culture), the alternatives are spread out in agents preference rankings. Thus, it becomes likely that some alternative is ranked slightly lower than another alternative by many agents, but has much higher social welfare in total. We see that in this case, randomized positional scoring rules outperform deterministic and random committee member rules as well as the uniform benchmark since it is more efﬁcient to give a chance of winning to each alternative. As φ decreases to 0.5 and agent rankings become somewhat correlated, random committee member rules start to outperform some of the randomized positional scoring rules (though randomized plurality and randomized 3-approval still perform quite well). But crucially, both families

of rules still outperform deterministic rules and the improved performance of random committee member rules now allows them to outperform the uniform benchmark as well. At φ = 0.1, when agent preferences are highly correlated, deterministic rules gain some traction. Nonetheless, at least one rule from one of the two randomized classes still outperforms all deterministic rules (randomized plurality for low m and any random committee member rule for high m). Overall, randomized plurality and randomized 3-approval perform reasonably well, and randomized plurality outperforms all four deterministic rules across almost all values of m and φ. The evidence suggests that one can almost always choose an explainable randomized rule that achieves better efﬁciency than deterministic rules, though the choice of the rule may have to depend on the setting at hand. A detailed comparison of rules in each class can be found in the supplementary material.

In the above experiments, for random committee member rules (speciﬁcally, the uniform random k-positional scoring rules), we use a committee size of k = 3. Figure 1d shows the best value of k (one that yields the minimum distortion) for different scoring vectors as a function of φ. It turns out that the best k is indeed very small (6 5) unless φ is really close to 1. Thus, k = 3 is a reasonable choice that helps our random committee member rules achieve high efﬁciency. Still, it is possible to further optimize the efﬁciency of these rules by pairing them with their corresponding optimal value of k; the resulting average distortion is presented in the supplementary material.

6 Limitations and Future Work

Explainability. We focus on the families of randomized positional scoring rules and random committee member rules as two examples of explainable randomized voting rules. While we argue in the introduction that these families admit intuitive procedural explanations and provide example explanations, checking whether stakeholders ﬁnd these explanations reasonable and satisfactory in the context of a real-life application requires an in-depth investigation, possibly via user studies. Our work also treats explainability as a qualitative attribute, but different rules even within the same family may differ in the degree to which they are explainable. Quantifying the degree of explainability, both theoretically and empirically, remains to be tackled.

Efﬁciency. Our work uses distortion as a yardstick for efﬁciency, leaving open exciting technical questions. While our analysis of randomized multi-level approval rules in the supplementary material takes a step towards characterizing the distortion of all randomized positional scoring rules, it still remains an unresolved challenge. For random committee member rules, even the more basic question of identifying the optimal distortion they can achieve remains open, though we are able to pinpoint it to be between (m2/3) and O(m4/5). Taking a step back, while distortion is a reasonable theoretical measure for efﬁciency, it remains to be seen whether it is also correlated for other measures of efﬁciency one may care about in practice. For example, in the context of food donations, Lee et al. [15], who use the deterministic Borda rule to make decisions, suggest a number of important decision factors other than the social welfare of the stakeholders, such as whether the donations are distributed equitably, how long the drivers have to travel to deliver donations, and whether organizations with higher poverty rates, lower median incomes, and worse food access are receiving sufﬁcient donations. An important next step would be to measure the efﬁciency of explainable randomized voting rules in real-life applications such as food donation.

[1] Pantelis Linardatos, Vasilis Papastefanopoulos, and Sotiris Kotsiantis. Explainable ai: A review

of machine learning interpretability methods. Entropy, 23(1):18, 2020.

[2] Sharadhi Alape Suryanarayana, David Sarne, and Sarit Kraus. Explainability in mechanism

design: recent advances and the road ahead. In Multi-Agent Systems: 19th European Conference, EUMAS 2022, Düsseldorf, Germany, September 14 16, 2022, Proceedings, pages 364 382. Springer, 2022.

[3] Amina Adadi and Mohammed Berrada. Peeking inside the black-box: a survey on explainable

artiﬁcial intelligence (xai). IEEE access, 6:52138 52160, 2018.

[4] Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling

lime and shap: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 180 186, 2020.

[5] Gerald Leventhal. What should be one with equity theory. New approaches to the study

of fairness in social relationships in Gergen, KJ MS Greenberg HJ Willis (szerk.): Social Exchange: Advances in Theory and Research, 1980.

[6] J.W. Thibaut and L. Walker. Procedural Justice: A Psychological Analysis. L. Erlbaum

Associates, 1975.

[7] Sumit Ghosh, Manisha Mundhe, Karina Hernandez, and Sandip Sen. Voting for movies:

the anatomy of a recommender system. In Proceedings of the third annual conference on Autonomous Agents, pages 434 435, 1999.

[8] David M Pennock, Eric Horvitz, C Lee Giles, et al. Social choice theory and recommender

systems: Analysis of the axiomatic foundations of collaborative ﬁltering. AAAI/IAAI, 30: 729 734, 2000.

[9] Georgios Sigletos, Georgios Paliouras, Constantine D Spyropoulos, Michalis Hatzopoulos,

and William Cohen. Combining information extraction systems using voting and stacked generalization. Journal of Machine Learning Research, 6(11), 2005.

[10] Yeming Tang and Qiuli Tong. Bordarank: A ranking aggregation based approach to collaborative

ﬁltering. In 2016 IEEE/ACIS 15th International Conference on Computer and Information Science (ICIS), pages 1 6. IEEE, 2016.

[11] David M Pennock, Pedrito Maynard-Reid II, C Lee Giles, and Eric Horvitz. A normative

examination of ensemble learning algorithms. In ICML, pages 735 742, 2000.

[12] Albert Jiang, Leandro Soriano Marcolino, Ariel D Procaccia, Tuomas Sandholm, Nisarg Shah,

and Milind Tambe. Diverse randomized agents vote to win. Advances in Neural Information Processing Systems, 27, 2014.

[13] Ritesh Noothigattu, Snehalkumar Gaikwad, Edmond Awad, Sohan Dsouza, Iyad Rahwan,

Pradeep Ravikumar, and Ariel Procaccia. A voting-based system for ethical decision making. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence, pages 1587 1594, 2018.

[14] Anson Kahng, Min Kyung Lee, Ritesh Noothigattu, Ariel Procaccia, and Christos-Alexandros

Psomas. Statistical foundations of virtual democracy. In International Conference on Machine Learning, pages 3173 3182. PMLR, 2019.

[15] Min Kyung Lee, Daniel Kusbit, Anson Kahng, Ji Tae Kim, Xinran Yuan, Allissa Chan, Daniel

See, Ritesh Noothigattu, Siheon Lee, Alexandros Psomas, et al. Webuildai: Participatory framework for algorithmic governance. Proceedings of the ACM on Human-Computer Interaction, 3 (CSCW):1 35, 2019.

[16] Jason Brennan. The ethics of voting. Princeton University Press, 2012.

[17] David O Brien and Pam Keller. American democracy in the 21st century: A retrospective.

Idaho Law Review, 56(2):9, 2021.

[18] Haris Aziz, Anna Bogomolnaia, and Hervé Moulin. Fair mixing: the case of dichotomous

preferences. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 753 781, 2019.

[19] Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah. Optimized distortion and

proportional fairness in voting. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 563 600, 2022.

[20] Allan Gibbard. Manipulation of schemes that mix voting with chance. Econometrica: Journal

of the Econometric Society, pages 665 681, 1977.

[21] Ariel Procaccia. Can approximation circumvent gibbard-satterthwaite? In Proceedings of the

24th AAAI Conference on Artiﬁcial Intelligence, pages 836 841, 2010.

[22] Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D Procaccia, and Or Sheffet.

Optimal social choice functions. Artiﬁcial Intelligence, 227(C):190 213, 2015.

[23] Ioannis Caragiannis, Swaprava Nath, Ariel D Procaccia, and Nisarg Shah. Subset selection via

implicit utilitarian voting. Journal of Artiﬁcial Intelligence Research, 58:123 152, 2017.

[24] Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A Voudouris. Distortion in

social choice problems: The ﬁrst 15 years and beyond. In Proceedings of the 13th International Joint Conference on Artiﬁcial Intelligence Survey Track, pages 4294 4301, 2021.

[25] Ariel D Procaccia and Jeffrey S Rosenschein. The distortion of cardinal preferences in voting.

In Cooperative Information Agents X: 10th International Workshop, CIA 2006 Edinburgh, UK, September 11-13, 2006 Proceedings 10, pages 317 331. Springer, 2006.

[26] Ioannis Caragiannis and Ariel D Procaccia. Voting almost maximizes social welfare despite

limited communication. Artiﬁcial Intelligence, 175(9-10):1655 1671, 2011.

[27] Vasilis Gkatzelis, Mohamad Latiﬁan, and Nisarg Shah. Best of both distortion worlds. In

Proceedings of the 24th ACM Conference on Economics and Computation (EC), 2023. Forthcoming.

[28] Allan Gibbard. Manipulation of voting schemes: a general result. Econometrica: journal of the

Econometric Society, pages 587 601, 1973.

[29] Richard Zeckhauser. Voting systems, honest preferences and pareto optimality. American

Political Science Review, 67(3):934 946, 1973.

[30] Elliot Anshelevich and John Postl. Randomized social choice functions under metric preferences.

Journal of Artiﬁcial Intelligence Research, 58:797 827, 2017.

[31] Olivier Cailloux and Ulle Endriss. Arguing about voting rules. In International Conference on

Autonomous Agents and Multiagent Systems (AAMAS 2016), pages 287 295, 2016.

[32] Dominik Peters, Ariel D Procaccia, Alexandros Psomas, and Zixin Zhou. Explainable voting.

Advances in Neural Information Processing Systems, 33:1525 1534, 2020.

[33] Arthur Boixel and Ulle Endriss. Automated justiﬁcation of collective decisions via constraint

solving. In Proceedings of the 19th International Conference on Autonomous Agents and Multi Agent Systems, pages 168 176, 2020.

[34] Arthur Boixel, Ulle Endriss, and Ronald de Haan. A calculus for computing structured jus-

tiﬁcations for election outcomes. In Proceedings of the 36th AAAI Conference on Artiﬁcial Intelligence, pages 4859 4866, 2022.

[35] Salvador Barbera. Nice decision schemes. Decision theory and social ethics, pages 101 117,

[36] Allan Borodin, Daniel Halpern, Mohamad Latiﬁan, and Nisarg Shah. Distortion in voting

with top-t preferences. In Proceedings of the 31st International Joint Conference on Artiﬁcial Intelligence (IJCAI), page 4, 2022.

[37] Gerdus Benade, Swaprava Nath, Ariel D Procaccia, and Nisarg Shah. Preference elicitation for

participatory budgeting. Management Science, 67(5):2813 2827, 2021.

[38] Aris Filos-Ratsikas, Evi Micha, and Alexandros A Voudouris. The distortion of distributed

voting. Artiﬁcial Intelligence, 286:103343, 2020.

[39] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris.

Peeking behind the ordinal curtain: Improving distortion via cardinal queries. Artiﬁcial Intelligence, 296:103488, 2021.

[40] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris. A

few queries go a long way: Information-distortion tradeoffs in matching. Journal of Artiﬁcial Intelligence Research, 74:227 261, 2022.

[41] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris.

Don t roll the dice, ask twice: The two-query distortion of matching problems and beyond. In Advances in Neural Information Processing Systems, 2022.

[42] Debmalya Mandal, Ariel D Procaccia, Nisarg Shah, and David Woodruff. Efﬁcient and thrifty

voting by any means necessary. Advances in Neural Information Processing Systems, 32, 2019.

[43] Debmalya Mandal, Nisarg Shah, and David P Woodruff. Optimal communication-distortion

tradeoff in voting. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 795 813, 2020.

[44] Aris Filos-Ratsikas, Srøen Kristoffer Stiil Frederiksen, and Jie Zhang. Social welfare in one-

sided matchings: Random priority and beyond. In Proceedings of the 7th Symposium on Algorithmic Game Theory, pages 1 12, 2014.

[45] Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approx-

imating optimal social choice under metric preferences. Artiﬁcial Intelligence, 264:27 51, 2018.

[46] Haris Aziz. Justiﬁcations of welfare guarantees under normalized utilities. ACM SIGecom

Exchanges, 17(2):71 75, 2020.

[47] Siddharth Barman, Umang Bhaskar, and Nisarg Shah. Optimal bounds on the price of fairness

for indivisible goods. In Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7 11, 2020, Proceedings, pages 356 369. Springer, 2020.

[48] Zhihao Jiang, Kamesh Munagala, and Kangning Wang. Approximately stable committee

selection. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 463 472, 2020.

[49] Colin L Mallows. Non-null ranking models. i. Biometrika, 44(1/2):114 130, 1957.

[50] Tyler Lu and Craig Boutilier. Effective sampling and learning for mallows models with pairwise-

preference data. J. Mach. Learn. Res., 15(1):3783 3829, 2014.

[51] Sven Berg. Paradox of voting under an urn model: The effect of homogeneity. Public Choice,

47(2):377 387, 1985.

[52] Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series

C: Applied Statistics, 24(2):193 202, 1975.

[53] R Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2012.

[54] Nicholas Mattei and Toby Walsh. Preﬂib: A library for preferences http://www. preﬂib. org. In

Algorithmic Decision Theory: Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 2013, Proceedings 3, pages 259 270. Springer, 2013.