Explainable and Efficient Randomized Voting Rules
Authors: Soroush Ebadian
Aris Filos-Ratsikas
Mohamad Latifian
Nisarg Shah
Venue: NeurIPS 2023 poster (2023)
Keywords: explainability
efficiency
voting
distortion
randomized decision-making
TL;DR: We study the efficiency (measured by distortion) of two families of explainable randomized voting rules and show that they can be significantly more efficient than deterministic voting rules while still being explainable.

Abstract: 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 significant efficiency 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 efficiency gains.

We study the efficiency 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 efficiency simultaneously to some extent.

Explainable and Efficient Randomized Voting Rules
Soroush Ebadian University of Toronto soroush@cs. Coronto.edu
Aris Filos-Ratsikas University of Edinburgh
Aris.Filos wellos-Ratsiin Ratsikaasedd ac uk
Mohamad Latifian University of Toronto latifi an@cs. Coronto.edu
Nisarg Shah University of Toronto
nisargecs.toronto. edu
toronto.
Abstract
With rapid growth in the deployment of AI tools for making critical decisions (or aiding humans in doing so), there is growing demand to be able to explain to the stakcholders how these tools arrive 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 significant efficiency gains measured via the distortion framework. However, rules that use intricate randomization can often become too complex explain to the stakeholders; losing explainability can eliminate the key advantage of voting over black-bor box AI tools, which may outweigh the efficiency gains.
We study the efficiency 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 efficiency simultaneously to some extent.
1 Introduction
In the past decade, Al and machine learning solutions have been deployed ubiquitously to make increasingly critical decisions that affect human lives. Consequently, there is 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 stakcholders the procedure of choosing outcomes across all possible instances. Much of the explainable Al (XAT) literature focuses on outcome explanations because many black-box Al solutions used in practice 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 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 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 justification for why given outcome was selected.
selected. These are susceptible to adversarial
To that end, we turn our attention voting. While explainability ecosystem, voting rules, historically deployed for political decision- makiin, have always battled with the need to be able to explain to the voters how the winner of an election chosen. Thus,
nascent demand in the AI
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

most prominent voting rules admit intuitive procedural explanations. Due to this key advantage over black-box Al solutions, they have been used automate prrisionnmakinng in a variety of applications
such as designing recommender systems [7, 8). information extraction [9], collaborative filtering [10],
ensemble learning [11], and game-playing by Al agents [12]. The advantage more apparent when
the decisions at hand are more significant. 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 decision- making 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 decision- making "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 seldom used to select representatives [17]. But in Al 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 benefits. 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 impossibility [20, 21J. Most importantly, it can unlock significant efficiency gains over using deterministic voting rules [22. 23, 19]. Unfortunately, randomized voting rules designed to optimize for efficiency can be highly complex and rely on intricate mathematical results such as the minimax theorem [19], making them difficult to explain to the end users.
In view of this, we explore the use of explainable randomized voting rules for improving the efficiency 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 significant possible efficiency gains on the table. Instead, we propose hybrid approach that adds a simple (and thus, explainable) randomization step to well-understood deterministic decision maaiiong processes. This drives our main research question:
What efficiency gains can be unlocked by explainable randomized voting rules which add a simple randomization step to deterministic voting rules?
As yardstick for efficiency, 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 this framework, the goal of 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.
functions over the alternatives.
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 widely- popular 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 deterninistically. 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,.... O are assigned to ranks 1,..., m. respectively. A rule from the first 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 fixed 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 = 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...
2

---

Table 1: Distortion and minimum welfare of common randomized positional scoring rules.
A-Approvals
Plurality
Borda
Harmonic
Veto
[1,
//////// E 1/3,
E [ ml
dist
(mmmm)
+ (m
mm
(m)
m kv/
(mm)
@ m - ++
min-sw
(
mk
m
R(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 equal chance."
Unlike prior work distortion, which is often focused identifying the most efficient rule, provide a refined 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 whole swathe of novel techniques for analyzing distortion, and use them obtain tight distortion (dist) bounds for randomized versions of well- known positional scoring rules such as plurality, Borda count, harmonic, veto, and k-approval, presented Table 1. For comparison, we remark that the distortion of the best possible deterministic voting rule is (m²² ) [26, 23] and the best possible randomized voting rule is O v m) [19, 22]. For randomized positional scoring rules, the best bound @(vm log m) due to [22]. En route to the distortion bounds shown in Table 1, we also obtain tight bounds for another useful efficiency metric, minimum welfare (min-sw), defined Section 3.1. 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 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 widely studied voting rule [28-30]. also fascinating that the distortion of randomized k-approval is highly non-monotone: first decreasing from (m) 1/3 then staying ((m) when i grows further to y /m, then
to (mm) when l grows from increasing again to 0(mym)) by & = m (m)) and finally decreasing again to (m)) by k = m.
Random committee member rules. For the family of random committee member rules, design a novel voting rule, which selects a random member of a top-biased stable k-commiltee, and achieves a distortion of (mmxx(K (k: (l:///(k//r) /k))). We complement this with a lower bound of ((max(k m² /k?]) on the distortion of any rule this class.
Experiments. Our experiments with synthetic data indicate that while the (worst-case) distortion of various rules in both families is not significantly better than the optimal deterministic distortion of O(m²) and often even worse than the (m) distortion of the trivial rule selecting a uniformly random alternative, rules from both families (almost always) significantly outperform deterministic voting rules and randomized positional scoring rules (almost always) outperform the mniform-randon 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 significantly improved efficiency.
1.2 Additional Related Work
Outcome explanations in voting. We focus on (randomized) voting rules with procedural ex- planations because that is, in our view, the key advantage of voting over black-box Al 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 this light. However, these axioms often provide a justification only in limited instances with special structure. Cailloux and Endriss [31] propose a method for producing justification on any given instance by starting from an axiomatic justification on a nearby special instance and using chain of explanations relating adjacent pairs of instances 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 al. [34] study computational aspects of finding them.
On randomized positional scoring rules. The family of randomized positional scoring rules was first proposed by Barbera [35], under the name of point-voting schemes. He establishes several appealing properties of these rules, including strategyproofness (i.c., no agent can ever strietly benefit from misreporting her preferences). Note that the outcome of randomized positional scoring rule can be computed by first selecting an agent uniformly at random, and then, for each k, selecting her k-th most preferred alternative with probability proportional score assigned to position k. In this sense, implementing 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 broad range of settings such committee selection [36], participatory budgeting [37]. distributed elections [38], elicitation-efficiengg tradeoff [39-43], and matching [44, 40J. Our methodological novelty is that we are the first to provide non-trivial absolute guarantees on the minimum welfare achieved across all instances, which is reasonable efficiency 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 unit-sum normalization. We refer the reader to the survey of Anshelevich et al. [24] for detailed overview.
2 The Setting
Let us formally introduce our setting and define the notion of distortion. We will define 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 conflicting preferences or opinions.
Basic notation. Let [t] {1, 21,2...... .t} for t E N. and define (SS) to be the probability simplex over the finite set S. For a vector 3 = (s1,...,&)) st), denote its -nom by || = Σie(t) $i.
Utilitarian voting. A (single-winner election consists of sets N = [n] of n agents and A = [m] of alternatives. Each agent E N has personal cardinal utility function u, A Ezo. where (,(a) is the value associated by agent i to alternative a. Following the convention in the literature (e.g., see [22, 191), we adopt the unit-sum normalization of utility functions: for every i N, let EacA (4(() (a) = 1. Aziz [46] provides several compelling justifications for using unit-sum utility functions. For a utility profile ū = (wI... : un.) and a subset of agents T C N, define the social welfare of alternative
A with respect to T as (a ū)) Eier uz(a). We write swN simply as sw, and drop i when it is clear from the context. As an extension, for distribution p E (AA) over the alternatives, define uz (p) = Rpg-p [u; (a)) and its social welfare as sw(p, i7) EVEn (p()) Our goal is to find distribution over alternatives with high social welfare. We will sometimes construct and analyze a partial utility profile, 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 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 N submits preference ranking a; : [m]] + A of the alternatives. We use rank;()) (a) to denote the rank of alternative in agent i's preference ranking (the most preferred alternative has rank 1), and a > a' to denote that agent i prefers a to a' (i.e., rank; (a) < (an); We assume that d; is consistent with agent i's utility function u, i.e., >-3 a' implies ua(a) ua(aa) for all a, a' E A; ties can be broken arbitrarily without affecting our distortion upper bounds.
Let = (ax)ieN be preference profile and C(ō) denote the set of utility profiles Tī such that o; is consistent with u; for each agent i E N. A voting rule f takes a preference profile o as input and returns a distribution p over alternatives.
4

---

Distortion. The distortion of distribution p E ((A) over alternatives with respect to utility profile is defined
dist(p, ū) m sw(a, 2))
sw(p, a7)
The distortion of a voting rule f is defined as its worst-case distortion over all instances: distm(() (eC() dist(f(ā), if), where the supremum is taken over all instances with m alternatives and any number of agents. For simplicity, we drop and write dist()).
3 Distortion of Randomized Positional Scoring Rules
The first class of explainable randomized voting rules we study is randomized positional scoring rules, or point- voting schemes [35]. This builds the popular class of (deterministic) positional scoring rules, which assign scores to alternatives based on their positions in agents' preference rankings, and adds 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 ø ($1,.... 88)) assigns a score 8, to each position r E [m]] and satisfies 51 3 52 3 ... e 8m 2 0. For an alternative a E A, let (a, 3) = Srank: (a) be the score a obtains from agent i, and for N' S N, scorey- (a, 5) = EieN' score, (a, $). Note that
EnEA scorey 8) = n || We drop 5 when it is clear from the context. For a scoring vector 5, we can define the following rules.
The deterministic positional scoring rule f selects the top scored alternative (breaking ties arbitrarilyy), i.e., (d) arg max, score, (a, 5).
The randomized positional scoring rule fran selects every alteraative A with probability proportional to its score, i.e., Pr(jfand(o)) a) scorex 8) / (n (|s]]1).
The deterministic rules introduced above include several well-known voting rules such as plurality, Borda, k-approval, velo, and harmonic defined, by the following scoring vectors, respectively:
Aplu = (1, 0, (1,)0)..))) 0),
0), Eveto = (1, 1, ................................ 1, 1,0), hharmonic (1, 2/2, 1/s...,, ..... 1/m)
Borda = (m - 1, 2, ,,...,0),
approvvl
1.0. 0).
ones
We refer to the randomized versions of these rules as "randomized f", where f e {plurality, Borda, harmonic, veto). and extend this terminoloyy to any positional scoring rule fz. Note that "randomized plurality" is more widely known as random dictatorship (see, e.g., 29)).
3.1 High-Level Distortion Analysis and Novel Insights
Logarithmic rounding of the scores. Our first useful insight is that we can reduce the number of distinct scores by rounding any score down to the nearest power of + fo a constant a >> 0, and this only changes the distortion of the rule by factor of at most +
Lemma 1 (Rounding Down Scores). Let a 2 O, and ā, 5 be scoring vectors such that 8' < 83 & (1 + s) for all j E [m]. Then, for every preference profile ā and consistent utility profile it E C(d),
1
sw(s (ō), it) & sw(J Frand (ō). 17) < (1 + ax) sw[sfand (ō), i7),
I+a
and consequently, Ita dist(I & dist(J!and) < (1 a) dist(s
By applying this transformation, scores in the range | || [] can be reduced to O(log m) distinct values, which we will find helpful in the subsequent sections. In the supplementary material, we show that by ignoring the remaining scores by reducing any 8, & [lál)/(4mm² to 0 changes the distortion further by another factor of at most two. Hence, we can limit our focus to scoring vectors that contain (log m) distinct scores, resulting in only a constant factor loss in the distortion analysis.
/(1mm),
High-level distortion analysis. After reducing the scoring vector to O(log distinct scores, we partition the agents into Olog 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
5

---

0= 6o < <.... < < m be the indices where the score changes in the reduced scoring vector, where, for each r E [4]. we have s; sr, for all i [e,-1 +1, 1,1,,,,,, f,l,
and St .... St, Furthermore,
let N, be the set of agents who rank a" among positions [6,-1 1,4..
Next, borrowing an insight from the prior distortion literature 42, 43), we round the agent utilities to the nearest power of two and ignore utilities below 1/m=², reducing the number of distinct utility values to (log m) while losing at most a constant factor in the analysis. This allows us to subdivide voters in each group N, into Ollog m) subgroups such that every agent in 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 Ollog² m) distortion bounds across all subgroups of all the N, groups.
Strategy 1 (Welfare above a"). Voters in subgroup of N, who have utility t for a" also have utility at least for their top 4-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 always upper bounded by the inverse of the probability of selecting a².
Strategy (Absolute Welfare Lower Bounds). Another novel insight from our work is that proving an absolute lower bound on the welfare achieved by 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 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 first to successfully apply it to distortion analysis.
Definition 1 (Minimum Welfare). Define the minimum welfare of a distribution over alternatives E (AA) on a preference profile ō as min-sw(p, ō) = ae(a) sw(p, ūī), which is the minimum social welfare of p across all consistent utility profiles. The minimum welfare of a voting rule f is the minimum welfare of its output, minimized over all preference profiles: min-swn.m (f) ming min-sw(f(i) (f()).))) o). where the minimum is taken over all preference profiles with n agents and m alternatives. We drop and m when clear from the context.
Due C(ō) being compact, the infimum in the min-sw(p, σ) definition is indeed attained. In the supplementary material, we make an structural observation that for any preference profile and distribution p (A4), the minimum welfare is at most '/m, attained a dichotomous utility profile. Furthermore, every randomized positional scoring rule f satisfies min-sw( (ffand) [r/((m²)), 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 generic welfare lower bound, which use to apply Strategies and 3. Instead of focusing only on Pr(ffan(d)) at), it bounds the overall welfare expression Eae Pr[ffand (ō) a] swr(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-K Karush-Kuhn-1 Kuhn-Tucker (KKT) conditions.
Lemma 2. Fix any scoring vector 8, preference profile o, subset of agents T C N, threshold + 3 O, and rank & [m]. For a partial utility profile in which every agent in T' has utility at least T for each of her top alternatives and all other utilities are O, we have:
h.
min he(m] 1 [2sc (2ss - (T > Eom-stt).
swr frand (ō), J. 2 T 2n||3||1
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 I E (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 (a) - score(a, BB First, we need the following lower bound on its minimum welfare. Lemma 3. The minimum welfare of the randomized Borda rule min-sw( (
frand Q my/m
Proof. Fix any preference profile and consistent utility profile i E C(Ø). Our goal is show that sw(stand agans (ō), i)) 52 my my/m First, we make few modifications to the scoring vector and the preference profile that are guaranteed to not increase the welfare, and then invoke Lemma 2.
Simplify the scores. Let consider the scoring vector 3" which is equal to šBorda except the top m/2 scores are all equal to m/2. Note that s', & (SBorda)y & 28/ for all j E [m]. Hence, invoking Lemma I with a 1 yields [[ (σ). i > 1/2 sw(s]?nd (ā), (d).
Simplify the preference and uilltty profiles. Next, let us lower bound sw(Sgand grand (ō), ū). For each agent i, let A, be the set top m/2 alternatives in o; and ag E arg ei score(a, s") be the alternative in A, with the lowest score (equivalently, probability of selection under (ō)). Now,
score(a, 5") n 3
(a)a) (1) score(ar,s") >
(2) score 5") 1
ug Frand (T))
Σ ue(a) AEEA;
n2 n2
1113% 2
aEA:
where (1) follows from the definition of a, and (2) the fact that each agent has total utility of at least 1/2 for her top m/2 alternatives (due to the pigeonhole principle).
be written as u. (F"))) where 5' is preference profile in which each agent i ranks a; first, and τº is a partial utility profile in which each agent has utility 1/2 for her top alternative and 0 for the rest. Summing the above for all agents, have sw( frand (Ø) ii) > sw(ffardd (Ø', t² Thus, lower bound it, we invoke Lemma with 5 + 5", σ + 0¹, T being an arbitrary subset of n1/2 agents, T t 1/2, and & + 1. Using
Invoking Lemma 2. The final expression above
||"
(m/2) m m33 (2n 21 this gives
2
(1) 1
1
n h(h 1)
sw( frand (o'). x
2
min AE|m/22
2
2
2n
ml (3m 21
2 h
2
2 2
n
min AE[m/2]
2m
h
+ h
2 n (2v2m)
(3)
n
4mm 2)
h
4m 13m - 2)
6m/
where the restriction to h E [m/2] in (1) is based on the fact that the bound would be ((n/m)) when > m/2, (2) is due to the AM-GM inequality, and (3) uses m 3 2. Connecting the dots, we have
sw(J
Sw([fand
prand Fourda
(d), TT)
sw( sw( prand (7). 1 > 2 sw( pland (o',a²))
V
2
12m m
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 altemnatve and its social welfare.
Lemma 4. For any preference profile d. consistent utility profile 7 C(Ø), and alternative a E A, we have sw(a) < (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 0(m5/4).
Proof. Fix any preference profile Ø and consistent utility profile ū E C(T). Let a" E arg max,e4 sw(a, i) be an optimal alternative. By Strategy 2 from Section 3.1, we know that the distortion is at most Borda(a")
aea Following Strategy 3 from Section 3.1 and the minimum wel-
sw(a") fare analysis in Lemma 3, we have that distortion is at most m/(2mmmm) which, using Lemma 4, is at

---

most 1 B/odala")/n 1). Putting everything together, and using the fact that min min(a, b) < vb for all a, b Ezo. the distortion is upper bounded by
n |ll 1
Borda(a") -12mmm +12mm
min
(orda(a"))
m(m 1)/2 Borda(a*) 12ym Borda(a*)
< 12 +
<8ym %/ = O(m²/4).
n
Random Committee Member Rules
Next, we focus uniformly at random from a shortlisted committee of size & E [m]] We call them random k-committee member rules. For l 1, we left with deterministic rules, among which plurality achieves the optimal distortion of (mm²). 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 ((y)), 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 (mm2/3).
second class of explainable randomized voting rules that select alternative
Theorem 3. For k E [m]) any random k-committee member rule incurs (max((k, m² m(21)))) distor- tion. This lower bound is at least (/m2/3) ) for all k.
As 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 benefit 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 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 O(m(m k 1)) distortion. While it nicely interpolates between the extremes of O(m²) at k = 1 and (m)) at = m, it fails to achieve sublinear distortion, which we prove to be achievable. What about other scoring vectors? Unfortunately. is relatively easy 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 polynomial-time computable random k-committee member rule with distortion (max (k. m² [kv/)))) This is minimized at k mm43, where the bound becomes (m//)
To achieve the above, we concoct a three-way mixture of an approximately stable commitlee [48], 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 sufficiently many agents. We refer 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 random committee member rule, sandwiching this value between O(m4/5) and ((m 2/3). ). It also interesting to wonder which value of k is optimal. Our upper bound is optimized at m and our lower bound implies that the optimal must be in [ 4/5 as the distortion outside of that range is 2(m+/5). See Section for empirical evaluation of the optimal k.
5 Experiments
Next, we empirically evaluate the efficiency 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 & alternatives with the highest scores (henceforth, uniform random k-positionall scoring rules).
8

---

10
10
B Bonch
Aveuge distortion
8-
Avenug distortion
8-
Mlrrlity
R Harmonic
R 3-Appessal
Bonds
10
20
30
40
50
10
20
30
40
50
Pluraiity
+ D Hamnotic
(a) Average distortion with Φ = 0.1.
(b) Average distortion with Φ = 0.5.
D. Approval
10
UR: Boeda
UR, Boeda
Average distortion
20
UR, Pluraliy
UR: Pluralit
UR, Harmanic
for URR Harmonic
Best.K
UR) Apgroval
10-
UKs
Opeimal
10
20
30
40
50
0-
0.0
0.2
0.4
0.6
0.8
1.0
(c) Average distortion with Φ
(d) Best value of based on d, for m = 25.
Figure All figures show results averaged over 150 runs along with the standard eτror. Figures la to Ic share the legend on the left.
We consider four representative scoring vectors f E (Plurality, Borda, Harmonic, 3-Approval), and denote the corresponding rules in the three classes by 'D f" 'R f", and 'UR, respectively. Thus, overall, we test 12 voting rules. 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 profile. Boutilier et al. [22] show how to use lincar programming compute the latter in polynomial time.
Data Generation. We generate preference profiles by sampling 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 6 E [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 o² is sampled with probability 1, so all the agents have the same preference ranking in the sampled profile. For precise definition the model an efficient algorithm to sample from it (which we in experiments), see the work of Lu and Boutilier [50]. For each combination of n 100 agents, m E (5, .o....... 50} alternatives, and dispersion parameter & E {0, o.,,....., 1}. we sample 150 instances, and report averages along with the standard error. In the supplementary material, report the results for two other statistical models namely the folyb-eggen urn model [51 and the Plackett-Luce model [52, 53].
Evaluation. For each rule f under consideration and each instance o. we evaluate the efficiency of the output ((ō) by measuring its instance-specific distortion dist( σ). Note that this still takes worst case over the utility profiles consistent with o, but unlike in Sections 3 and 4 where we also take worst case over o. here we compute the expected distortion over Ø drawn from the Mallows model. Again, we compute dā), σ) using the La-based approach Boutilier et al. [22].
Results. Figures Ia to Ic show the average distortion of different rules for ø E {0.1, 0.5, 1}. respectively, fixing m 25. For large & (impartial culture), the alternatives are spread 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 this case, randomized positional scoring rules outperform deterministic and random committee member rules as well as the uniform benchmark since it is more efficient to give 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
agents'

---

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 6 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 efficiency 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 (specifically, the uniform random k-positional scoring rules), we use a committee size of 3. Figure 1 shows the best value of (one that yields the minimum distortion) for different scoring vectors as a function of Φ. It turns out that the best l is indeed very small (< 5) unless Φ is really close to 1. Thus, choice that helps our random committee member rules achieve high efficiency. Still, it is possible to further optimize the efficiency of these rules by pairing them with their corresponding optimal value of k; the resulting average distortion is presented in the supplementary material.
is a reasonable
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 find these explanations reasonable and satisfactory in the context of 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 be tackled.
Efficiency. Our work uses distortion as a yardstick for efficiency, 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 to be between (m/2/3) and (m+/5)). Taking a step back, while distortion is a reasonable theoretical measure for efficiency, it remains be seen whether it is also correlated for other measures of efficiency 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 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 travel to deliver donations, and whether organizations with higher poverty rates, lower median incomes, and worse food access are receiving sufficient donations. An important next step would be to measure the efficiency of explainable randomized voting rules in real-life applications such as food donation.
10

---

References
[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 artificial intelligence (xai). IEEE access, 6:52138-52164 2018.
[4] Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks 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 social relationships" " in Gergen, KJ-MS Greenberg HJJ 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 recommender system. In Proceedings of the third annual conference 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 filtering. AAAI/IAA,, 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 filtering. In 2016 IEFF/ACIS 15th International Conference on Computer and Information Science (ICIS), pages 1-6. IEEE, 2016.
[11] David M Pennock, Pedrito Maynard-Reid II, Lee Giles, and Eric Horvitz. A normative examination of ensemble learning algorithms. In ICMI,, 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 Artificial Intelligence, pages 1587-1594, 2018.
[14] Anson Kahng. Min Kyung Lee, Ritesh Noothigattu, Ariel Procaccia, and Christos-Alexandme Psomas. Statistical foundations of virtual democracy. In International Conference 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, al. Webuildai: Participatory frame- work for algorithmic governance. Proceedings of the ACM on Human CommannCommuter Interaction, (3SC 2019.
[16] Jason Brennan. The ethics of voting. Princeton University Press, 2012.
[17] David O'Brien and Pam Keller. American democracy in the 21 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-satterthwaitte? In Proceedings of the 24th AAAI Conference on Artificial Intelligence, pages 836-841, 2010.
[22] Craig Boutilier, loannis Caragiannis, Simi Haber, Tyler Lu, Ariel D Procaccia, and Or Sheffet. Optimal social choice functions. Artificial Intelligence, 227(C):1900211 2015.
[23] Ioannis Caragiannis, Swaprava Nath, Ariel D Procaccia, and Nisarg Shah. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58:123-152, 2017.
[24] Elliot Anshelevich, Aris Mloos-Rassikas, Nisarg Shah, and Alexandros A Voudouris. Distortion in social choice problems: The first 15 years and beyond. In Proceedings of the 13th International Joint Conference Artificial 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, S 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. Artificial Intelligence, 17500110::655-11671, 2011.
[27] Vasilis Gkatzelis, Mohamad Latifian, and Nisarg Shah. Best of both distortion worlds. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), 2023. Forth- coming.
[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-94) 1973.
[30] Elliot Anshelevich and John Postl. Randomized social choice functions under metric preferences. Journal of Artificial Intelligncce Research, 58:797-827, 2017.
[31] Olivier Cailloux and Ulle Endriss. Arguing about voting rules. In International Conference on Autonomous Agents and Mulliagent Systems (AAMAS 2016), pages 287-295, 2016.
[32] Dominik Peters, Ariel D Procaceia, Alexandros Psomas, and Zixin Zhou. Explainable voting. Advances in Neural Information Processing Systems, 33:1525-1533 2020.
[33] Arthur Boixel and Ulle Endriss. Automated justification of collective decisions via constraint solving. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages (66-176.7 2020.
[34] Arthur Boixel, Ulle Endriss, and Ronald de Haan. A calculus for computing structured jus- tifications for election outcomes. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, pages 4866, 2022.
[35] Salvador Barbera. Nice decision schemes. Decision theory and social ethics, pages 101-117. 1978.
[36] Allan Borodin, Daniel Halpern, Mohamad Latifian, and Nisarg Shah. Distortion in voting with top-t preferences. In Proceedings of the 31 International Joint Conference on Artificial Intelligence (IJCAI), page 4, 2022.
12

---

[37] Gerdus Benade, Swaprava Nath, Ariel D Procaccia, and Nisarg Shah. Preference elicitation for participatory budgeting. Management Science, 67(5):2813-227) 2021.
[38] Aris Ailos-Ratsikas. Evi Micha, and Alexandros A Voudouris. The distortion of distributed voting. Arlificial Intelligence, 286: 103343, 2020.
[39] Georgios Amanatidis, Georgios Birmpas, Aris Ratss-aa and Alexandros A Voudouris. Peeking behind the ordinal curtain: Improving distortion via cardinal queries. Artificial Intelli- gence, 296:103488, 2021.
[40] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A Voudouris. few queries go a long way: iifommatioondistottiin tradeoff's in matching, Journal of Artificial Intelligence Research, 74:227-261, 2022.
[41] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsike and Alexandros Voudouris. Don't roll the dice, ask twice: The two-query distortion of matching problems and beyond. In Advances Neural Information Processing Systems, 2022.
[42] Debmalya Mandal, Ariel Procaccia, Nisarg Shah, and David Woodruff. Efficient and thrifty voting by any means necessary. Advances in Neural Information Processing Systems, 32, 2019.
[43] Debmalya Mandal, Nisarg Shah, and David Woodruff. Optimal communication-disooniie tradeoff in voting. In Proceedings of the 21 ACM Conference on Economics and Computation, pages 795-813, 2020.
[44] Aris sided matchings: Random priority and beyond. In Proceedings of the 7th Symposium on Algorithmic Game Theory, pages 1-12, 2014.
Srøen Kristoffer Stiil Frederiksen, and Jie Zhang. Social welfare in one-
[45] Elliot Anshelevich, Onkar Bhardwaj. Edith Elkind, John Postl, and Piotr Skowron. Approx- imating optimal social choice under metric preferences. Artificial Intelligence, 264:27-51, 2018.
[46] Haris Aziz. Justifications of welfare guarantees under normalized utilities. ACM SIGecom Exchanges, 17(2):71-75, 2020.
[47] Siddharth Barman, Umang Bhaskar, and Nisarg Shah. Optimal bounds 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 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-388 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, (42)):13-2022 1975.
[53] Dunean Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2012.
[54] Nicholas Mattei and Toby Walsh. Preflib: A library for preferences http://www. preflib. org. In Algorithmic Decision Theory: Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 2013, Proceedings 3, pages 259-270. Springer, 2013.
13


Reviews:
[{"review_id": "kH1eCXSJX2", "reviewer": "Reviewer_Ypnk", "summary": "This paper provides a discussion of and bounds for distortion (distance) and minimum social welfare of randomized additions to several voting rules. The main body of the paper introduces two versions of randomization for positional scoring rules (either using scores as the distribution or selecting a top-k and then using a distribution). The main technical results of the paper are bounds on the distortion of these randomized voting rules and some empirical simulations that point in the direction that single level randomized voting rules may be better in practice.", "questions": "? After Theorem 3 there is a discussion of non-worst case results, is there any hope for average case or distributional results that would improve the worst-case bounds for the random k-committee results?\n\n? The empirical results are nice, though I was hoping for a bit more discussion of why, e.g., UR does so well at lower and so bad at higher distortions. There doesn't seem to be a clear winner across all the experiments except maybe R 3-Approval... any more comments here?\n\n? Why don't we just use the optimal voting rule? Is it because you claim it's not explainable? but from the Boutillier framework it's just a weighted rule that one could explain (as easily as any positional scoring rule) -- so I wonder why one doesn't just use the optimal rule framework?\n\n------- \nAfter Rebuttal:\n\nSee my comments below, I think this is a good paper and liked the answers given by the reveiwers.", "limitations": "Good discussion. Though I wonder if distortion is the right framework here, a more concrete application (e.g., aggregating classifiers or something) and argument as to why distortion is the right measure would strengthen the fit for NeruIPS.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ The proofs and the methodology of the proofs are very nice and are likely of independent interest to the distortion community. \n\n+ The paper is very well written overall and easy to follow.\n\n+ The results are very nice and the simulations give a nice indication that even though the worst case results are significantly better, that in practice there could be a lot here.", "weaknesses": "- The positioning of the paper in terms of \"explainable\" is a bit weak, to say the least. The limitations address this but the main \"explainable\" part is basically the tautology that \"voting rules are explainable\" which, I guess? There are quite a few poly sci and sociology papers that deal with understanding and explainable voting rules, you could have cited at least one of those papers. Likewise there are a number of papers on models for explain-ability that one could tie into.\n\n- Likewise, how is this machine learning? I don't really understand the vague statement \"critical decisions\" -- there is plenty of literature, new and old, that argues for using voting rules for concrete examples (aggregating classifiers (Cornelio, C., Donini, M., Loreggia, A., Pini, M.S. and Rossi, F., 2021. Voting with random classifiers (VORACE): theoretical and experimental analysis. Autonomous Agents and Multi-Agent Systems, 35(2), p.22.) or making recommendations (Aird, A., Farastu, P., Sun, J., Voida, A., Mattei, N. and Burke, R., 2023. Dynamic fairness-aware recommendation through multi-agent social choice. arXiv preprint arXiv:2303.00968.)) that would maybe ground the paper better in the ML community than the social choice one.\n\n### Minor Issues:\n\n* Footnote one without any citations is really just random and unnecessary, either substantiate it or delete.\n\n* \" explain-ability and efficiency simultaneously to some extent.\" while I'm all for not overstating results this is a bit informal.. maybe \"indicate that in some cases...\" \n\n* \"explainable voting rules in the section in which\" --> this just feels like buzzword bingo, you assert all voting rules are explainable so the extra explainable here is not needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and the time you took to provide such helpful feedback. In response to your questions:\n\n> ? After Theorem 3 there is a discussion of non-worst case results, is there any hope for average case or distributional results that would improve the worst-case bounds for the random k-committee results?\n\nStudying the average-case distortion of rules, e.g., under distributional assumptions, is certainly a very important and interesting problem. While it was briefly studied in the original paper of Boutilier et al. [22], it remains largely unexplored. Even for the vanilla version (without explainability), the state-of-the-art is very recent, from two working papers from 2023, see [A] and [B] below. Future work could certainly build on the models of those papers and study the average-case distortion of random k-committee rules, as the reviewer suggests.  \n\n[A] Caragiannis, Ioannis, and Karl Fehrs. \"Beyond the worst case: Distortion in impartial culture electorate.\" arXiv preprint arXiv:2307.07350 (2023).\nhttps://arxiv.org/pdf/2307.07350.pdf\n\n[B] Gonczarowski, Y. A., Kehne, G., Procaccia, A. D., Schiffer, B., & Zhang, S. (2023). The Distortion of Binomial Voting Defies Expectation. arXiv preprint arXiv:2306.15657.\nhttp://procaccia.info/wp-content/uploads/2023/05/expdistortion.pdf\n\n\n> ? The empirical results are nice, though I was hoping for a bit more discussion of why, e.g., UR does so well at lower and so bad at higher distortions. There doesn't seem to be a clear winner across all the experiments except maybe R 3-Approval... any more comments here?\n\nWe believe you mean \"higher values of $\\phi$\" rather than \"higher distortions\". \n\nWhen $\\phi$ is small, the rankings produced via Mallows' model are highly correlated. Thus, just the $3$ alternatives that $\\text{UR}_3$ randomizes over (for the four scoring vectors) likely cover the top choices of most agents, leading $\\text{UR}_3$ to achieve low distortion. \n\nIn contrast, when $\\phi$ is large, the alternatives are spread out in agents' preference rankings. Thus, it becomes likely that some alternative is ranked slightly lower by many agents, has a low enough score to not be in the top $3$, but has much higher social welfare than the top $3$ alternatives over which $\\text{UR}_3$ randomizes. \n\nThis is also why deterministic rules perform reasonably well at low $\\phi$, but randomization (over many alternatives, not just $3$) becomes important at high $\\phi$. \n\nOther than these, R Plurality and R 3-Approval performing reasonably well, and R Plurality outperforming all four deterministic rules across almost all values of $m$ and $\\phi$ (see also the figures in the appendix) are the main takeaways of our experiments, as stated in the paper. \n\nWe will explain these more thoroughly in our revision. \n\n\n> Why don't we just use the optimal voting rule? Is it because you claim it's not explainable? but from the Boutillier framework it's just a weighted rule that one could explain (as easily as any positional scoring rule) -- so I wonder why one doesn't just use the optimal rule framework?\n\n\nWe believe you're referring to the rule of Boutilier et al. [22], which chooses alternatives proportional to harmonic scores with probability $1/2$ and a uniformly random alternative with probability $1/2$, achieving distortion $\\Theta(\\sqrt{m \\cdot \\log m})$, only slightly worse than the optimal of $\\Theta(\\sqrt{m})$. Note that this is not just a weighted rule. As we state in the paper, it can also be viewed as a randomized positional scoring rule, with the score associated with each position $k$ being $\\frac{1}{k}+\\frac{1}{m}$. As such, it is indeed explainable by our own criterion.\n\nThat being said, its scoring vector is not one of the widely recognized ones, such as Borda, approval, or (regular) harmonic. Hence, people may be less willing to adopt it in practice. This is why we focus on providing an in-depth analysis of the distortion of many explainable rules, including the aformentioned recognized ones, so that the designer can choose depending on the application.\n\nHaving said that, the worst-case optimal rule within a given family of rules certainly deserves attention. While this is a solved question for randomized positional scoring rules, we propose this as an interesting open question for random committee member rules and provide bounds towards answering it.\n"}, {"review_id": "BWOIACX2j6", "reviewer": "Reviewer_VN7K", "summary": "This paper studies distortions of two family of \"explainable\" randomized voting rules  -- randomized positional scoring rules and random committee member rules. In the literature of explainable voting rules, various deterministic voting rules have been widely studied and believed to be explainable to some extent. However, recent studies showed that randomized voting rules have efficiency advantages under the measure of distortion. This work aims to combine the best of both worlds -- adding one simple randomization step to explainable deterministic voting rules in order to improve its efficiency. Specifically, randomized positional scoring rules select each alternative with a probability proportional to their scores, and random committee member rules select an alternative uniformly at random among top $k$ candidates with the highest scores.\n\nIn this paper, efficiency of certain voting rules is measured by distortion, which assumes each voter has a utility to each agent(normalized to $1$) and reports an ordinal preference that is consistent with her utility. The distortion is then defined as the ratio between expected total utility of the winner and the total utility of the optimal alternative in the worst case.\n\nThe paper prove tight distortion bounds for a number of randomized positional scoring rules including Plurality, Borda. Under random committee rules, the authors propose a novel voting rule that achieves sublinear distortion.\n\nFinally, the paper also includes a numerical simulation that demonstrates distortion performance of these two classes of randomized voting rules on synthetic data.", "questions": "- Line 297 mentions \"worse than the optimal $\\sqrt{m}$\". I might be missing something but where does this $O(\\sqrt{m})$ bound comes from and what do you mean by \"optimal\"?\n\n- Could the authors compare randomized propositional voting rules with other randomized voting rules that may be more efficient but less explainable?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The distortion analyses of randomized positional scoring rules are fairly complete that include asympototically tight bounds.\n- The main technical lemma (lemma 2) is novel and mathematically non-trivial that surprisingly tightly captures the lower bounds of the minimal social welfare of a wide range of randomized positional scoring rules. \n- It is nice to have some numerical simulations to demonstrate the advantages of randomized voting rules compared to their deterministic counterparts.", "weaknesses": "- The introduction tries hard to draw connections between its actual technical contributions (i.e. distortions of randomized voting rules) with literature of explainable AI. However I feel the story a bit disconnected. I understand that certain families of deterministic voting rules have been studied in the context of explainable voting rules. Nevertheless, it is not clear to me why adding one more randomization step won't jeopardize the explainability. For instance, some explainability are based on aximatization, but adding randomization might be incompatible with the original aximatization. I encourage the authors to at least elaborate more and make more convincing arguments on the explainability issue.\n\n- Authors should include more related works about distortions of voting rules and compare their results with other distortion results of different voting rules (deterministic or randomized) in the literature. \n\n- The paper is generally well written, however, to me the main technical lemma (lemma 2) lacks intuition. I think it might be helpful if the authors could expressly explain the quadratic programming for a simple example in the body of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper. Here are our ansewers to your questions:\n\n> Explainable AI...Nevertheless, it is not clear to me why adding one more randomization step won't jeopardize the explainability....I encourage the authors to at least elaborate more and make more convincing arguments on the explainability issue.\n\nYou are absolutely correct that when adding randomization, we inevitably lose some explainability. However, our argument, as laid out in the paper, is that in some contexts it may be important to add randomization in order to achieve the significant efficiency gains it provides over deterministic rules. Our point is that instead of adding arbitrary or complex randomization, it may be possible to add simpler and structured randomization, which can retain explainability to some degree while still providing significant efficiency gains. We will clarify this further in our revision.\n\n\n> Line 297 mentions \"worse than the optimal \". I might be missing something but where does this bound comes from and what do you mean by \"optimal\"?\n\nFrom Ebadian et al. [19], we know that the lowest possible (across all instances with $m$ candidates) distortion achievable by randomized rules is $\\Theta(\\sqrt{m})$ --- this is what we mean by \"optimal\" here. In contrast, we know that the best distortion achievable by randomized positional scoring rules is $\\Theta(\\sqrt{m \\log m})$, which is only a sublogarithmic factor worse than $\\Theta(\\sqrt{m})$. The question we propose in this line, which we resolve negatively later, is whether random committee member rules can also achieve distortion that is only slightly worse than $\\Theta(\\sqrt{m})$, perhaps even just $O(\\sqrt{m} \\operatorname{polylog}(m))$.\n\n> Could the authors compare randomized propositional voting rules with other randomized voting rules that may be more efficient but less explainable?\n\n\nTheoretically, the worst-case optimal rule of Ebadian et al. achieves the optimal $\\Theta(\\sqrt{m})$ distortion, but it uses advanced machinery (e.g., von Neumann's minimax theorem) and is not very explainable. Further, its distortion is only slightly better than the best $\\Theta(\\sqrt{m \\log m})$ distortion that randomized positional scoring rules can achieve (Boutilier et al. [22]). Thus, no other rule (explainable or not) can be significantly better in the worst case. This includes another rule of Boutilier et al. [22] that achieves a distortion of $O(\\sqrt{m}\\log^{\\*} m)$ (where $\\log^{\\*} m$ is the iterated logarithm), which is even less explainable due to use of advanced LP-duality techniques. \n\nEmpirically, we show that some of the explainable rules (e.g., R Plurality) actually achieve distortion that is, on average, very close to the distortion achieved by even the instance-optimal rule. Thus, once again, no rule (explainable or not) can be significantly better on average. When $\\phi=1$, all four common randomized positional scoring rules are close to this benchmark of the instance-optimal rule. \n"}, {"review_id": "lStj8EV2Vq", "reviewer": "Reviewer_uYtf", "summary": "The paper studies two types of simple (or in their words *explainable*) randomized voting rules with respect to their (utilitarian) distortion. These are, (1) randomized positional scoring rules where every agent gives a certain number of points to their first ranked, second ranked, etc. alternative and a winning alternative is chosen with probability proportional to the received scores, and (2) random uniform committee member rules, where the rule first selects a committee and then choses a winning alternative uniformly at random from this committee. \n\nThe story of the paper is that decision making within AI tools should be both *explainable* and *efficient*. For the sake of explainability, the paper focuses on voting methods and suggests that the above mentioned methods offer a particularly explainable procedure. For measuring efficiency, the paper utilizes the commonly studied distortion framework. \n\nThe paper then provides tight bounds on the distortion of members of these families of randomized voting rules. While these bounds show that some of these simple randomized rules do not even reach the same worst-case guarantee as a trivial benchmark (the rule selecting a candidate uniformly at random), the paper presents computational experiments in which the studied rules outperform the benchline (in some cases) as well as deterministic rules. ", "questions": "- Have you studied the natural combination of your two (family of) rules? That is, for some scoring vector and some $k$, consider the $k$ alternatives with highest score and then randomize over these with probability proportional to their score. I was wondering whether this rule might be able to inherit the advantages of proportional scoring rules, while reducing the size of the support. Do you know anything about this rule? \n- If I understand correctly, in your experiments, you omit the $k$-committee rule from Theorem 4, which was proven to have bounded distortion in the worst case. Why did you decide to do so? \n- Why did you decide to focus on Mallow's model in the experiments? Do you have any reason to believe that results for other random models would be similar? \n", "limitations": "While I do think that the authors do a good job in pointing to the limitations of their work within Section 6, I think that the introduction of the paper is in parts misleading and should be tailored more closely to the main part of the paper. Also, the limitations of the experiments could be addressed more transparently. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is certainly well written, and easy to follow. Especially, I appreciated that the papers gives insights into the developed techniques, albeit that most of the proofs had to be deferred to the appendix. \n- I see the main strength of the paper in its technical contribution, especially the new technique of deriving distortion bounds via a global lower bound on the social welfare. I am optimistic that these will be helpful for future research on utilitarian distortion. \n- I appreciate the breadth of the results, since many of the results hold for entire classes of voting rules. \n- The literature on distortion of voting rules has been very active in recent years in social choice, hence I am optimistic that the paper will receive significant attention within the community. ", "weaknesses": " I find the story in the introduction more distracting and unfitting than helpful. In particular, the following questions are completely left open: (1) In which AI applications can voting actually serve as a reasonable alternative? (2) In which AI application are we in the situation that a set of agents have cardinal utilities but they can only report *ordinal* preferences? In particular, if the *agents* in the AI application are actually AI systems themselves, the argument that cardinal preferences require too much cognitive effort is not very convincing. (3) If there are AI tools that satisfy the above criteria, which objectives are important in these contexts? (Why is it small distortion?) Personally, I think it would be much more helpful for the reader to shift the focus of the introduction much more towards the content of the paper, e.g., (a) How can we measure explainability in randomized rules and do there exist other rules (besides the two groups) that are explainable? (b) What is the status quo on utilitarian distortion among deterministic and randomized voting rules? \n- I am not convinced that the experimental results are very meaningful since the experiments consider only one specific random model (i.e., Mallows Model) which has been shown to be able to produce only a small fraction of all possible types elections (see, e.g., \"Putting a Compass on the Map of Elections\", Boehmer et al, IJCAI 2021). While this is a general issue in social choice theory, this is particularly relevant for this paper, since the main positive results seem to stem from the fact that the studied voting rules behave well \"in practice\" (evaluated as their behavior on Mallows) and even within the space of Mallows elections, there is no randomized voting rule which dominates the benchmarks for all Mallows elections. Hence, I think that extending the experimental evaluation to more models would significantly increase the relevance of the experimental part of the paper. \n\n**Minor Comments**\n- Related Work section: For the sake of comparison it would have been nice to provide an overview of the best distortion guarantees that can be achieved by deterministic and randomized rules. \n- Line 179: sc(a,s) instead of sc(c,s)? \n- Line 194: \\alpha instead of \\epsilon? \n- Line 212: \"This allows us to we subdivide\"\n- Line 221: I was missing some context here: Does this hold for every distribution of alternatives? \n- Theorem 2 seems unusual. I understand that this was done to save space. \n- If I understand correctly, $k$-committee member rules define a family of randomized voting rules. However, Theorem 3 makes it sound as if this would be one specified rule. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and helpful comments. Regarding your questions:\n\n> Have you studied the natural combination of your two (family of) rules? \n\nThis is a nice idea, which we did not consider. These rules are only slightly less explainable than UR$_k$ rules, so if they lead to significant efficiency gain, it may be worth considering them. \n\nTheoretically, it is not hard to show that most of them also have infinite distortion, just like most UR$_k$ rules, because it is possible for none of the $k$ alternatives in the support to be the top choice of any agent.  \n\nEmpirically, we ran further experiments to compare these rules (coined PR$_3$) against UR$_3$ rules under Mallows' model; please see Figure 2 in the PDF attached to the common response. \n\nFor low $\\phi=0.1$, when the rankings are highly correlated, PR$_3$ indeed generally perform better than UR$_3$, which is expected because here the best alternative is often obvious and PR$_3$ can place a higher probability on it. The effect is more pronounced when the best alternative has a much higher score (so, most under plurality, less under Borda/harmonic, almost negligible under 3-approval). However, PR$_3$ Plurality does get worse with large $m$, mimicking D Plurality. Thus, if $\\phi$ is low, it may make sense to prefer PR$_3$ Borda/harmonic, and also PR$_3$ Plurality if further $m$ is small. \n\nHowever, this seems to be the extent of their helpfulness. For the intermediate $\\phi=0.5$, all PR$_3$ and UR$_3$ rules have similar performance, and for the impartial culture with $\\phi=1$, each PR$_3$ rule coincides with its corresponding UR$_3$ rule as the top 3 alternatives likely have very similar scores (leading PR$_3$ to also pick from them almost uniformly at random).\n\nBy the way, once we allow non-uniform randomization, it leads us to the family of randomized rules with support of size $k$; this generalizes both PR$_k$ rules and random committee member rules. Interestingly, our proof of the $m^2/k^2$ lower bound from Theorem 3 actually holds for this broader family, but not the proof of the $k$ lower bound. This leads to the interesting open question whether a randomized rule with support size $k = o(m)$ can achieve near-optimal distortion of $O(\\sqrt{m} \\operatorname{polylog}(m))$. For random committee member rules, we proved the answer is no (Theorem 3). \n\nWe will be happy to add these discussions and experimental results to the appendix of our paper with a reference in the discussion section. \n\n> in your experiments, you omit the $k$-committee rule from Theorem 4...Why did you decide to do so?\n\nThat is a good question. We omitted this rule from the experiments for two main reasons. \n\nFirst, it involves computing an approximately stable committee, which is a computationally difficult task. There is a polynomial time algorithm of Jiang et al. [40], but we suspect it would take long in practice since it relies on using multiplicative weights update to solve a zero-sum game followed by a complicated iterative rounding procedure. One can instead write an integer linear program (ILP), which has bad worst case but perhaps works better in practice. \n\nSecond, even if we implemented it, we did not believe that it would perform any better on average than the best of the UR$_3$ rules we already use in our experiments, being a rule designed specifically to get good *worst-case* distortion. \n\nThat said, we ran further experiments implementing this rule using the aforementioned ILP to compute approximately stable committees, and compared it in the same Figure 2 of the attached PDF mentioned above. As expected, this rule generally does worse (e.g., markedly so for $\\phi=0.5$), although it is interesting that at the extremes of $\\phi=0.1$ and $\\phi=1$, its performance is similar to the UR$_3$ rules (though never better than the best of the UR$_3$ rules).\n\n> Why did you decide to focus on Mallow's model in the experiments? Do you have any reason to believe that results for other random models would be similar?\n\nWe elected to limit the scale of our experiments because we view our extensive theoretical results to be our primary contribution. We chose Mallows' model because it is one of the most popular random ranking models in the computational social choice literature. \n\nThat said, we agree that apriori there is no strong reason to believe that results on other random models would be similar. While detailed experiments with more models is an avenue for future work, we ran preliminary experiments with the Polya-Eggenberger Urn Model (from the Map of Elections paper you mentioned) and the Plackett-Luce model, another popular random ranking model. Note that the urn model experiments are limited to $m \\le 18$ because sampling from this model is computationally expensive for large $m$ (https://github.com/PrefLib/preflibtools/blob/main/preflibtools/instances/sampling.py).\n\nFigure 1 in the attached PDF shows the results. \n\nResults for the Plackett-Luce model and the urn model with $\\alpha=0.01$ are very similar to those for impartial culture from our submission (Mallows' model with $\\phi=1$), where randomized positional scoring rules perform better than UR$_3$ rules, which in turn perform better than deterministic rules. Note that the urn model with $\\alpha=0$ would be exactly the impartial culture, so this is not very surprising. \n\nResults for the urn model with higher values of $\\alpha$ are more interesting. They share some similarities with the Mallows results, such as the order among the three families mentioned above and R Plurality generally performing very well. But there are also crucial differences: for example, in the Mallows experiments, there are no significant differences between the different deterministic rules or between the different UR$_3$ rules, but clear differences show up in the urn experiments, with plurality-based rules performing better.\n\nWe will be happy to add these additional plots to the appendix of our paper."}, {"review_id": "cQOF7dvDfc", "reviewer": "Reviewer_c5N6", "summary": "This paper is concerned with introducing a simple randomization \"step\" to deterministic voting rules so as to increase efficiency, as measured through the distortion framework (and also min-sw). The goal is to retain both the explainability of deterministic voting rules while increasing efficiency.", "questions": "Please see above.", "limitations": "Seems fine.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an interesting tension between explainability and efficiency. I commend the author for this well-motivated problem. I think formalizing the tradeoff is definitely an important question. ", "weaknesses": "Let me preface by saying that voting is not my primary research area, and so, it is not entirely clear to me the extent of the innovation and if the number and quality of the results/techniques are significant for the community.\n\nWith that said, some questions come to mind when reading:\n\n1. The fundamental premise of the paper is that deterministic => explainable.\nIs this a well-established fact in the voting community (besides appealing to [16] as in L46)? If not, then the whole investigation seems less well-founded.\n\n2. To me, it seems natural to have a knob for introduce the amount of randomization, which can also serve as a measure of how ``simple'' the randomization step is.\n\nFor instance, what about a ``soft'' notion of randomization? There is a tunable parameter that introduces a measured amount of randomization. Have the authors considered this and bounding distortion and min-sw as a function of this parameter?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are sincerely grateful for your time and energy reviewing the paper. To answer your questions:\n\n> The fundamental premise of the paper is that deterministic => explainable. Is this a well-established fact in the voting community (besides appealing to [16] as in L46)? If not, then the whole investigation seems less well-founded.\n\nWe would say that in general, yes, most deterministic rules are viewed as more explainable than most randomized rules. Besides [16], we have cited the work of Lee et al. [15], who used deterministic rules in the context of food donations and explained them to the stakeholders. These were deemed understandable by the stakeholders and thus adopted. \n\nAdditionally, political elections are almost always deterministic. Indeed, even significantly complicated deterministic rules such as the Schulze method are widely deployed in the real world (see https://en.wikipedia.org/wiki/Schulze_method#Usage). In contrast, even simple randomized rules have no known uses in real-world elections (see https://en.wikipedia.org/wiki/Random_ballot#Prevalence). \n\nAt least part of the resistance to using randomized rules comes from a lack of explainability. This is related to the inability to convincingly explain precisely why a decision was taken due to chance being involved; see [C, p107] below. However, when the randomization step is simple, it may be possible to explain why a certain alternative had high score under a randomized positional scoring rule or was chosen to be in the support under a random committee member rule along with the final randomization step.\n\nTherefore, although some deterministic rules can be more explainable than others, we believe that the deterministic-randomized divide in terms of explainability is viewed as more significant. \n\n[C] Duxbury, Neil. Random justice: On lotteries and legal decision-making. Oxford University Press, USA, 2002.\n\n\n> To me, it seems natural to have a knob for introduce the amount of randomization, which can also serve as a measure of how \"simple\" the randomization step is. For instance, what about a \"soft\" notion of randomization? There is a tunable parameter that introduces a measured amount of randomization. Have the authors considered this and bounding distortion and min-sw as a function of this parameter?\n\nThat sounds like an interesting line of investigation, which we have not pursued. This would require finding an appropriate measure for the \"amount of randomization\". One could look into entropy or the size of the support; our random committee member rules can be viewed as an example of the latter. Although, such simple measures would likely fail to accurately capture what makes randomization less appealing to humans. Ultimately, we believe that user studies may be needed to come up with the right measures.\n"}]

Author rebuttal:
We thank all the reviewers for their detailed and helpful reviews. In response to some of the comments, we ran further experiments and included the results in the PDF attached to this common response. We will be happy to incorporate these results as well as the suggestions of the reviewers when we revise the paper.

Meta-review: The reviewers are all positive and acknowledged the neat results and interesting message, while they all raised questions about the high-level approach and arguments on explainability. Eventually, results in paper seems to be interesting in its own right to at least the AGT community, which makes it a good candidate for poster presentation.

We hope the authors can find the reviews helpful. Thanks for submitting to NeurIPS!
Decision: Accept (poster)