Learning to Elect
Authors: Cem Anil
Xuchan Bao
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural networks
voting rules
social decision making

Abstract: Voting systems have a wide range of applications including recommender systems, web search, product design and elections. Limited by the lack of general-purpose analytical tools, it is difficult to hand-engineer desirable voting rules for each use case. For this reason, it is appealing to automatically discover voting rules geared towards each scenario. In this paper, we show that set-input neural network architectures such as Set Transformers, fully-connected graph networks and DeepSets are both theoretically and empirically well-suited for learning voting rules. In particular, we show that these network models can not only mimic a number of existing voting rules to compelling accuracy --- both position-based (such as Plurality and Borda) and comparison-based (such as Kemeny, Copeland and Maximin) --- but also discover near-optimal voting rules that maximize different social welfare functions. Furthermore, the learned voting rules generalize well to different voter utility distributions and election sizes unseen during training.

Learning to Elect
Cem Anil"
Xuchan Bao"
University Toronto Vector Institute
University of Toronto Vector Institute jennybaolcs toronto.edu
an cecmcss.s........... toronoo. edu
Abstract
Voting systems have wide range of applications including recommender systems, web search, product design and elections. Limited by the lack of general-purpose analytical tools, it is difficult to hand-engineer desirable voting rules for each use case. For this reason, it is appealing to automatically discover voting rules geared towards each scenario. tectures such as Set Transformers, fully-connected graph networks and DeepSets are both theoretically and empirically well-suited for learning voting rules. particular, show that these network models can not only mimic number of ex- isting voting rules to compelling accuracy - both position-basee (such as Plurality and Borda) and comparison-basee -based (such as Kemeny, Copeland and Maximin) but also discover near-optimal voting rules that maximize different social welfare functions. Furthermore, the learned voting rules generalize well to different voter utility distributions and election sizes unseen during training.
this paper, we show that set-input neural network archi-
Introduction
Voting systems are highly prevalent in our daily lives. Examples range from large scale demo- cratic elections company or family-wide decision making, recommender systems and product design [Boutilier et al.) 2015].
As with any social decision-making process, the goal of designing voting rules is reconcile differences and maximize some collective objective. The area of research that studies different voting rules and the approaches designing them is called voting theory.
vast number of voting rules have been proposed over the years. Among them is the widely applied plurality rule. Despite being simple and intuitive, the plurality rule is very limited in that does not consider the strength of voters' preferences. Other examples of voting rules, such as Borda and Copeland, take into consideration the ranked preferences of the voters.
Voting theorists have developed different approaches to designing voting rules. For example, the axiomatic approach constrains the voting rules to satisfy certain desired properties (axioms) such as anonymity (treating all voters equally) and neutrality (treating candidates equally). The utilitarian approach, on the other hand, aims to maximize pre-defined notion of social welfare - a scalar quantity that measures the quality of the elected candidate in the eyes of the electorate.
There are major hurdles to overcome in the traditional way of designing and implementing voting rules. First, the celebrated Arrow's Theorem states the nonexistence of non non-dictatorship voting rules that simultaneously satisfy set of seemingly sensible axioms [Arrow et al. 1951]. Second, for some voting rules such as the ones based on pairwise comparisons. finding the winner can be computationallyy expensive, making them infeasible for large-scale applications. Last but not least, for the utilitarian approach, it not obvious how design voting rules that maximize a given notion
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of social welfare There might be diverse set of social welfare functions of interest, but theory is lacking in finding their corresponding optimal voting rules.
In this paper, we aim to tackle the latter two limitations using neural networks. While doing so, we also seek preserve certain desired properties such voter anonymity. In particular, we identify three cntnuuutttionnnvviiint neural network (PIN) architectures: DeepSet [Zaheer et al. 2017]. Set Transformer [Lee et al. 2019), and Graph Isomorphism Network (GIN) [Xu et al.) 2018 and apply them to learn the voting rules, As compact and universal function approximators, such trained neural networks not only address the computational burden of some voting rules, but also provide flexible approach to maximize diverse set of social welfare functions.
The main contributions of this paper include:
We show that PIN architectures are theoretically and empirically well-suited for learning to represent voting rules. Theoretically, show that the three PIN architectures are universal approximators in the space of permutation-in invirriant functions. This includes a novel proof on the universality of Graph Isomorphism Networks with fully- cullecconneeted graphs (as in learning voting rules).
We apply the aforementioned PIN models to mimic five classical voting rules: plurality, Borda, Copeland, Maximin and Kemeny. We show that they can mimic these voting rules to compelling accuracy and can generalize seamlessly to unseen real datasets and elections with an unseen number of voters.
We train the networks to maximize two different social welfare functions - utilitarian and egalitarian
elections sampled using three different underlying voter utility distributions. We show that the PIN models discover novel voting rules that maximize social welfare better than classical voting rules. In cases where theoretical optimal voting rules are known (i.e. for the utilitarian social welfare function), the PIN models match the optimal performance.
The organization of this paper is follows. Section 2 provides background voting theory. Section describes our method of using PINs to learn voting rules. Specifically, we introduce the permutation-invariae network architectures (Section 3.1 show the universality results (Section 3.2 and describe the proposed the training procedure for learning voting rules in detail. In Section we show comprehensive experiment results on the effectiveness of PIN models learning voting rules. We discuss related works in Section limitations in Section 6 and conclude with Section [7]
2 Background
2.1 Voting theory preliminaries
We adopt the formalism used by Boutilier et al. 2015 Let N = (1,...,n]] n. be a set of voters, A {a...... 3m3 be a set of candidates and .l..... m] be the integer rankings each voter can assign to candidate. Each vote i is represented as bijection from candidates to rankings: o, A + R. The vector of candidate preferences 5 (o,, ......... σn) E (Sm,." is called a preference profile. A voting rule f (S.,)" R + A maps preference profiles to candidates.
The utilitarian approach voting makes the assumption that voters have utility functions (u A H R+) over the alternatives which quantify how much a voter prefers a candidate. Utility functions are consistent with the rankings that is, candidates with higher utilities are ranked higher by voters. The vector of all voters' utility functions रे = (u....., Un) is called a utility profile. The social welfare of an alternative sw(a, 77) A Ra + IR quantifies the "desirability" of candidate under a given preference profile i.. The utilitarian approach posits that the ultimate goal of a voting rule to pick the candidate that maximizes social welfare. Note that since voting rules only have access to rankings and not the utilities, this is often impossible to achieve without further assumptions.
A popular notion of social welfare is the utilitarian social welfare function, which computes the of all the utilities the voters assign a candidate swail (a, iī) = Eien us (a). There exists, however, many different social welfare functions. For example, the Rawlsian social welfare function aims make even the least happy voter as happy as possible: sWmw ū) min, u, (4), and the egalitarian social
We consider average-case social welfare maximization, unlike the worst-case analysis in the distortion literature [Boutilier et al. 2015 Caragiannis al. 2017

---

welfare function aims to maximize the utilitarian welfare, regularized by a penalty term promoting equality: sWegal (a, zi) EieN Uj (a A xEeex(
(u, (Allcott 2011]. It is up to the designer of the voting system to pick a notion of social welfare best suieed for the task at hand.
2.2 Classical voting rules
Most classical voting rules be classified under two groups: score based rules and comparison based rules. Score based rules (also called scoring functions) are defined by score vector 3 = ($1 Sm). Each candidate a A is assigned the score > ieN Soz(a) and the candidate with the largest score is picked as the winner [Boutilier et al., 2015]. Famous examples include Plurality (with a score vector of Spt - (1, 0, ..... OJ) and Borda (with score vector of Sbodda- (m I, m 2,... 0)).
Comparison based rules operate using pairwise comparison matrices R E Rmxm whose entries filled based on how candidates fare against each other in pairwise comparisons. Well-known examples include the Copeland, Maximin and Kemeny rules. The Copeland rule picks the candidate who fares better in pairwise comparisons the largest number of times: arg max, (E, Tij) where Tiy stands for the number times candidate fares better against candidate j in the voter preferences. Maximin, also known as Simpson's rule, picks the candidate for whom the candidate who fares the best against him/her in pairwise comparisons has the least pairwise score: arg min; (max; r33) [Bubboloni et al. 2020). The Kemeny rule [Kemeny 1959 first computes ranking that maximizes the sum of all pairwise wins: o² = arg max, ZivoJ Tijs where > means that candidate is preferred against j according to ranking a. The Kemeny winner is the candidate that ranks the first in a². Note that computing the Kemeny ranking Kemeny winner is NP-hard (Bartholdi et al. 1989
2.3 Average-case optimal voting rules
In cases where the social welfare function takes a very simple algebraic form, it might be possible to derive the voting rule that achieves the largest expected social welfare under given utility distribution Pa. For example, it known that the average-case optimal voting rule for the utilitarian social welfare funtion is score-based voting rule with the score vectors 2t Eu (o (o((u)) (a) A]] (or, the
average utility of the candidates that are ranked at hthh position) [Boutilier al. 2015
3 Permutation-Invarian Networks (PINs) to learn set-input functions
We review the fundamentals of learning set-input functions through the use of permutation-invariant networks (PINs). Learning set-input functions is desirable in the context of learning voting rules: 1) it enables processing elections of varying sizes (i.e. different number of voters) 2) it makes it possible to satisfy desirable properties such as anonymity (invariance to the shuffling of voter identities) through architectural constraints. We review three commutation-invariii fully-connected graph networks and Set Transformers) and show that they' re universal approximators of set-input functions. We also detail the training procedure for learning voting rules.
architectures (DeepSets,
3.1 Constructing peermutationnivvaiiinn architectures
Functions defined on sets are by definition permutation invvaiiann (Zaheer et al. 2017].
Property 1. Let 2 represent the powerset of X. Any senncttu f 2 + y must be invari-
and to the reordering of its inputs by any permutation a: J((EI,..., XM = S [(==o())...xx(()))
Zaheer et al. 2017] showed that one can practically train expressive set-input neural networks by feature extractor (encoder) and a the property that when the inputs of a function are permuted,
chaining together
decoder permutation-cqqivarraan the outputs get permuted the same way:
Property function : MM
Xxdut is permutation-equivariinnt if
((F.(()).... To,s,, = (x).,, Sa (x)]
CComossition of permutation eequivariant and permutation invariant functions results in permutation invariant functions.
3

---

All of the architectures described below follow the central design principle of composing permutation- equivariant building blocks with permutation -ermaataion-invaiiantt invariant ones build expressive set-input networks.
DeepSets [Zaheer et al. 2017] This architecture first encodes each element of the set independently using encoder network (e.g. multilayer perceptron), pools the outputs of the encoder (e.g. using sum, max or mean pooling) and finally passes the result through a decoder network (e.g. another multilayer perceptron). Since the encoder treats the elements of the set independently achieve permutation-equiiiane -equiaaaiiee.iiiiinnnce.e the pooling operation is the only step that can model interactions between the elements in the set.
Fullecconnecttd) graph neural networks (GNNs) Instead of achieving cermmuaation-quivariinn through the independent processing of the set elements, we can instead view the input set fully-connected graph and build a GNN-based [Scarselli et al. 20088 encoder that takes into account all of the interactions between different elements of the set. Each GNN layer transforms the nodes in the graph by concatenating a cermutaaion-invarian and a transformation that produces the next-layer features given the current-layer features and the result of aggregation. A GNN consists of multiple GNN layers, and the graph-level embedding is function. In our experiments,
aggregation of features of the neighbour nodes
obtained by pooling all the node features using permutation-invaricn we use a powerful variant of GNN - the Graph Isomorphism Network (GIN) [Xu et al., 2018 Detailed background on GNNs and GIN can be found in Supplementary Material.
For a fully-connected graph, the graph structure remains unchanged under node permutation. Since both the neighhourhood aggregation and the graph-level pooling operations are permutation-invarian the whole GNN represents a permutation-invarian function.
Set Transformers [Lee et al., 2019] The computational building block of set-transformers is the Query-Key-Valuu Value (QKV) attention [Vaswani et al., 2017]. which can be interpreted as a differentiable dictionary retrieval operation. The neural network controls both the input and output space of the QKV operation using multihead attention, which multiplies all the input and output tensors by learnable weight matrices.
The multihead attention possess desirable permutation-equuiee watpratooonnguivaiiiinneennaaaaa properties for learning set-input functions. Set Transformer builds highly expressive encoder-decoder architecture with multiple multihead attention blocks, resulting in the overall permuaation-invarinnee (Lee et al. 2019]. Detailed background and the full encoder-decoder architecture are found in Supplementary Material.
3.2 Universality results
An important property that we would like these neural network architectures to possess is universal approximation in the space of intuuutationinvvriann functions. Since any anonymous voting rule can be expressed as a permutation-invarian function without the presence of ties, universal approximating network has the maximum representational power over these voting rules.
Throughout this section, we assume that the input feature space X' countable. We also assume that the output space is R. These assumptions are appropriate in the case of approximating voting rules
The universal approximating properties of DeepSets and the Set Transformer have been estab- lished [Zaheer et al., 2017 Lee et al. 2019]. We establish the universal approximating results of GIN in the following subsection.
3.2.1 Universality of GIN
al. 2018 showed that the representational power of GIN is equal to the power of the Weisfeiler- Lehman (WL) graph isomorphism test [Weisteiler and Leman 1968). We extend their result to show that in the case of fully-connected graph structures (as in learning voting rules), GIN has equal representational power as the full graph isomorphism testing. We state this result formally below:
Theorem 1. Let G1, E G be any two non-isomorphic fully-connected coloured graphs Ler Lehman test of isomorphism decides non-isomorphic to different embeddings in Rd. Then A maps G1 and G2 to different embeddings.
A:G- ddd be GNN that maps any two graphs that the Weismeiler-Lehman
'Even though the networks output logits in RT, it is sufficient to show the networks are universal in representing scalar function with a maximum the logits.

---

Maximizing social welfare Under the utilitarian framework, the social welfare is a function of underlying utilities that voters assign to the candidates. In reality, neither the voter utilities nor the social welfare quantity are easily accessible. However, we make assumptions on the distribution generate synthetic training data and get access to Algorithm 1: Supervised Learning of Voting Rules
Inputs
Uttility distribution Pu.
Existing voting rule or oracle f
Initialize the weights of model fw while loss not converged do
Sample voter utilities: iI ~ P.
Compute preference profiles: (
Get target winner y/ f())) (existing rule)
or [(z) (oracle)
Get predicted winner y (=((
Compute prediction loss: ((5,
01 and update weights W Compute gradients aw
end
return Learned rule fw
The proof hinges upon the observation that when applied to callycconnected coloured graphs, the Weisfeiler-Lehmaa iterations do not alter the colouring of nodes. We defer the formal proof to Supplementary Material.
In order to establish universality results from Theorem we refer to Chen et al. (219)) who estab- lished the equivalence between graph isomorphism and the universal approximation of permutation- invariant functions. In particular, Chen et al. [2019) proved that if GNN is graph isomorphism- discriminating, then the GNN with additional two leed-forward layers universal approximating.
3.3 Learning voting rules
We would like to train neural networks to represent voting rules - the network takes in the voter preference profile, and outputs the predicted winner In this paper, we are interested in training networks to perform two tasks: 1) to mimic cxisting voting rules, and 2) to discover novel voting rules that maximize input-label pairs, making it suitable for supervised learning. For the second task, different learning approaches possible.
notion of social welfare. The training data for the first task naturally provides
from which the voter utilities are generated, the utility information.
It is possible to frame the social welfare maximization as reinforcement learning (RL) problem, or more specifically, as a contextual bandits problem. The network would learn to maximize the reward (social welfare) by choosing an action (the winner candidate) from discrete set, given some situation or context (the voter preference profile).
more straightforward alternative is to use supervised learning. Since we have access to the utilities training time, we can define an oracle "voting rule" that takes in the utilities and outputs the winner that maximizes social welfare σ We can then train the networks using supervised learning, with the oracle output as the target. This approach also called behaviour cloning. Compared RL, has the weakness of penalizing all wrong predictions equally. However, it is casier to optimize and empirically yields strong results (Section 4.. We leave the RL approach future work.
Since the training procedure is identical to that of the first task (except that we mimic the oracle instead of an existing voting rule), we summarize the training procedure for both tasks in Algorithm
$ Foor detailed discussion about the input and output representations, see Supplementary Material. 'The oracle not an actual voting rule, uses information (utilities) that is accessible voting rules.
5

---

Architect.
Mimicking Accuracy
Plurality
Borda
Copeland
Maximin
Kemeny
Set Trans.
1.0
0.99
0.82
0.80
0.94
GIN
1.0
0.99
0.81
0.77
0.82
DeepSets
1.0
0.96
0.83
0.78
0.89
MLP
1.0
0.95
0.81
0.75
0.76
Table I: Voting rule mimicking accuracy of learned voting rules. The entries represent the proportion of times the learned voting rule successfully predicts the output of the Plurality, Borda, Copeland, Maximin and Kemeny rules (higher is better). Permutation-invariant architectures achieve near perfect accuracy in approximating score-based voting rules (Plurality and Borda) and compelling accuracy in comparison-base based rules (Copeland, Maximin and Kemeny).
Experiments
In this section, we investigate the effectiveness of PIN models 1) mimicking classical voting rules (Section 4.1) and 2) discovering novel voting rules that maximize social welfare (Section 4.2)
Training data generation We used synthetically generated elections to train the networks. In our experiments, we sampled elections with numbers of voters and candidates ranging between 2 to 99 and 2 to 29 respectively (except for mimicking the Kemeny rule, where we sampled 3 to 10 candidates due solver and computation constraints). We sampled the (normalized) voter utilities from the Dirichlet distribution with concentration parameters E IR" where is the number of candidates. Sampling from the Dirichlet distribution ensures that the sampled utilities are non-negative and sum up to one. Different Dirichlet parameters lead to qualitatively different elections. We consider the following cases where the utility distribution symmetric to each candidate, i.e. a = (ao og] Specifically, we used og = 0.5 and 2 for "polarized" and "indecisive" in our experiments, respectively.
"Polarized" (0 < < 1): each voter likely strongly prefers a candidate.
"Uniform" " (og 1): all utility profiles are assigned equal probability.
"Indecisive" (ao 1): voters likely have strong preference for the candidates.
We then used the generated utilities to compute the voter preference profiles. We also computed the target winner either based on an existing voting rulcd) (Section 4.1 or an oracle that maximizes social welfare based on the utilities (Section 4.2). The neural networks attempt to predict the winner using only the voter preference profiles (pre-processed with the one-hot candidate id function described in Supplementary Material).
To evaluate the diversity of the synthetically generated data, we empirically estimated the probability of pairs of traditional voting rules producing the same winner, using the "uniform" utility distribution (Table 5 in Supplementary Material). We conclude that the synthetically generated elections are diverse, hence can differentiate the voting rules.
Network architecture details We compared the performance of DeepSets [aaheer et al. 2017), Graph Isomorphism Networks [Xu et al.) (2018) and Set Transformers [Lee et al. 2019]. To make the results as comparable as possible, we constructed all architectures to have roughly 10 million parameters and comparable depth. We also used the same normalization layer (LayerNorm (Ba et al., 2016)) in all of the architectures. We additionally trained similar-sized multilayer perceptrons (MLP) as baseline. Further details of the architectures are described in Supplementary Material.
Training setup We used the Lookahead optimizer [Zhang et al. 2019] train the DeepSet models, and the Adam optimizer [Kingma and Ba 2015) to train the other networks. We tuned the learning rate for each architecture. We used the cosine learning rate decay schedule with 160 steps of linear warmup period [Goyal et al.] 2017). We used a sample size of 64 elections per gradient step. We trained each PIN model for 320,000 gradient steps. We trained each MLP model for three times as long (960,000 gradient steps), as MLP models observed to learn more slowly. Additional details for the training setup are included in the Supplementary Material.
The outcomes of these elections are difficult to predict, as no candidate obviously preferred. For the mimicking tasks, we removed elections that have tied winners except for the Kemeny rule, in which case the integer programming solver we used does not efficiently detect the existence of ties.

---

4.1 Mimicking classical voting rules
Are Dermutation-Invarian Networks (PIN) expressive enough to represent number of classical voting rules? How does their performance vary as we move from computationally cheap position-based voting rules, such as Plurality and Borda, to more computationally demanding comparison-based -ased ones, such as Copeland, Maximin and Kemeny? We generated synthetic data with the "uniform" utility distribution, and trained PINs to mimic these aforementioned voting rules. We then tested the robustness of the learned voting rules by computing how their mimicking performance varies on elections with different number of voters and candidates, elections from different data distributions and elections sampled from real world datasets.
Mimicking accuracy The perfor- mance of all architectures on mim- icking the Plurality, Borda, Copeland, Maximin and Kemeny rules are pre- sented in Table I For each value in Table T we sample 16,384 elec- tions from the training distribution. A first observation is that PINs achieve near perfect accuracy in approximat- ing score- voting rules. This is significant result, many theoreti- cally optimal voting rules are known to be score-based (Boutilier et al.) 2015: Young 1975). Secondly, PINs outperform MLP models in all cases (except for Plurality, which all models learned perfectly). We would like to highlight that PINs achieve high accuracy in mimicking the Kemeny rule (significantly better than the MLP baseline), which is ha-hard to compute exactly. This shows that PINs have high potential as efficient approximate solutions for computationally expensive voting rules g
Mimicking Accuracy for
Architect.
Different Number of Voters
(within-domain
2-49
50-99
100-149
150- 199
Set Trans.
0.99
0.99
0.99
0.99
GIN DeepSets MLP
0.99
0.99
0.98
0.98
0.97
0,96
0.95
0.95
0.96
0.93
N/A
N/A
Table 2: The accuracy of permuration-invariant networks on predicting the Borda winner (higher is better). Even though the networks were trained on elections with less than 100 voters, the learned rules generalize seamlessly to unseen num- bers of voters much larger than encountered during training.
Generalization to unseen numbers of voters Can PINs generalize elections with number of voters bigger than that encountered during training? We tested the PIN models on elections with voters between 2 and 199 (the models are trained on maximum 99 voters). We report the results in mimicking Borda in Table 2 Similar results for mimicking Plurality, Copeland, Maximin and Kemeny can be found in Supplementary Material. This confirms that the PIN models have indeed learned proper set-input functions, instead of overfitting to the election sizes observed during training. Note that it is impossible to test the MLP models on elections with more than 99 voters due to the fixed input size. Scaling up an MLP model to fit elections with up to 199 voters would require doubling its input size, increasing that PINs have over MLP models. We leave thorough investigation of PIN models under drastic distribution shifts (such as elections that are orders of magnitude larger) to future work.
number of parameters and retraining. This a major advantage
Generalization to real-world datasets We trained the networks on synthetic data to mimic the classical voting rules, and tested them on three real-world datasets: the Sushi dataset [Kamishima 2003) (10 candidates), the Mechanical Turk Puzzle dataset [Mao et al.] 2013) (4 candidates) and
a subset of the Netflix Prize Data (Bennett et al., 2007] (3-4 candidates). We randomly sampled
elections from these datasets with number of voters from 2 to 99 for testing. Details of the testing
data can be found in Supplementary Material.
The results (Table 4 show that PINs have learned voting rules that generalize well to real datasets, and slightly outperform those learned by the MLP. Interestingly, the mimicking accuracy the real datasets is higher than that on the synthetic training data (Table []. This likely indicates that the winners for synthetic elections generated by the uniform Dirichlet distribution are harder for the networks to determine than most real-world scenarios. While we found that it was not necessary in our experiments, it is also feasible fine-tune synthetically trained networks on real data further adapt to unseen distributions.
'PINs may be more efficient in computing the winner of a single election, and more importantly, batches of elections can be parallelized very efficiently in PINs with GPUs. This is property that traditional solvers lack.
7

---

Arch.
Mimicking Acc. (Netfixx
Mimicking Acc, (Sushi)
Mimicking Acc, (MTP)
P.
B.
C.
M.
K.
P.
B.
C.
K.
B.
C.
M.
K.
Set
1.
1.
1.
1.
99
1.
1.
.98
1.
.98
1.
1.
1.
1.
GIN
1.
1.
.98
.98
.97
1.
1.
.8
.98
.66
1.
1.
.98
.99
.99
DeepS.
1.
1.
1.
1.
.99
1.
1.
.98
.99
.97
1.
1.
1.
1.
MLP
1.
1.
96
.97
.97
1. 1. .98
.98
.96
1.
1.
.98
.98
.99
Table 4: Voting rule mimicking accuracy of networks trained on synthetic elections and tested on three different real-world datasets. Compared to the synthetic data [T the performance of all learned voting rules substantially beller when applied to real data. This compelling zero-shot generalization performance suggests that training on diverse and difficult synthetic datasets is promising approach to overcome the sample inefficiency of training large neural networks.
Architect.
Uniform
Polarized
Indecisive
Apart from real-world datasets, we show in the Supplementary Material @nd 7) that the learned voting rules also generalize well to other syn- thetic data distributions. The strong generalization performance of synthet- ically trained voting rules (including the MI.P baseline) is significant from sample-complexity perspective. Proo caccia et al. 2009 showed that po- sitional scoring rules are efficiently PAC learnable, but learning pairwise comparison based voting rules in gen- eral requires an exponential number of samples. While training neural networks requires large amounts of generaliza- data, our synthetic-to-red
Util.
Egal.
Util.
Egal.
Util.
Egal.
Set Trans,
0.68
0.66
0.67
0.68
0.70
0.54
GIN
0.69
0.65
0.68
0.67
0.70
0.55
DeepSets
0.67
0.65
0.66
0.67
0.68
0.57
MLP
0.67
0.65
0.66
0.67
0.69
0.54
Plurality
0.42
0.40
0.47
0.46
0.39
0.31
Borda
0.56
0.58
0.50
0.51
0.61
0.53
Copeland
0.52
0.53
0.48
0.49
0.56
0.48
Maximin
0.50
0.50
0.46
0.47
0.53
0.45
Optimal 0.65
0.65
0.67
Table 3:
The accuracy by which learned voting rules can predict the candidate that maximizes the utilitarian and egal- itarian social welfare functions on different utility distribu- tions ("uniform". "polarized" and "indecisive") - higher is better. The PIN models slightly outperform, and mostly on par with the MLP ones. All the neural network models outperform classical voting rules.
tion results suggest that training on diverse and difficult synthetic datasets can achieve compelling zero-shot gen- eralization performance. This especially significant for NP-hard voting rules such as Kemeny.
4.2 Maximizing social welfare
In almost all real elections, we only have access to voter preference profiles, but not the underlying utilities. While the theoretically optimal voting rule is known assuming utilitarian social welfare (Section 2.3 no theoretical results are yet established for general social welfare functions.
However, with PINs being general function approximators, we can train them to discover these potentially unknown social celfare--mxiimzzing voting rules. We define an oracle to be the "ideal" voting rule that has access to the underlying utiliiies (possible on synthetic data), and computes the winners that maximize some social welfare function. We then trained the neural networks to mimic the oracles given only the voter preference profiles.
We experimented with two different social welfare functions (utilitarian and egalitarian) and three different utility distributions (uniform, polarized and indecisive). We report the accuracy of the best candidate predictions attained by the learned voting rules in Table 3 We compare these with the performance achieved by classical voting rules (Plurality, Borda, Copeland and Maximin) 10 For the utilitarian social welfare, we report the performance of the theoretically optimal voting rule as well.
Table 3 shows that all the neural network models achieve better accuracy than the classical voting rules. When the theoretical optimal voting rule is known (i.e. with utilitarian social welfare), the
Due to the computational cost of generating training data with large numbers of candidates, we do not report Kemeny results here.
8

---

DeepSeltrriinll Settranaformer MLP
DeepSelDrginal
10a
Settransformer
MLP
10a
10-
Density
plurality
plurality
bonda
bonda
10a
copcland
maximii in
maximin
10-4
10-1
10
10-2
0.7
swidd
sw14,
maxyFwia,
MaK,AWaa, ()
(a) Utilitarian
(b) Egalitarian
Figure 1: Normalized histogram of the ratio between the social welfare following different voting rules and the optimal social welfare, for the utilitarian and egalitarian welial-welfare functions. Data sampled from the "uniform" distribution.
neural networks match the accuracy of the optimal rule This indicates that neural networks are highly effective discovering novel voting rules that maximize general social welfare functions.
Besides the prediction accuracy, we also evaluate the distribution of the resultant social welfare following the baseline and the learned voting rules. Figure shows the normalized histogram of the ratio between the social welfare following a voting rule and the optimal social welfare:
(a 7i)
(ā is the winner chosen by a voting rule).
max,, sw(a 77)
The conclusion from Figure iis consistent with the accuracy results. The neural networks models are better maximizing social welfare than the classical voting rules, in that they achieve higher social welfare values.
Note that although the performance of PINs in Table and Figure T is par with MLP, PINs still have the fundamental advantage of respecting voter anonymity and being able to generalize to arbitrary voter numbers, discussed in Section 4.1
Related works
Procaccia et al. 2009) showed that positional scoring rules are efficiently PAC learnable, but learning pairwise comparison-bart bosee voting rules in general requires exponential number of samples. Boutilier et al. (015) proved that the optimal voting rule that maximizes the average-cass utilitarian social welfare positional voting rule for any neutral utility distributions. Also, the line of work in distortion focuses on developing and analyzing voting rules that are optimal for the worst-case utilities [Boutilier al. 2015 Caragiannis al. 2017). We focus the average-case maximization of social welfare, but without assumptions on the social welfare function any given utility distribution. Xial 20133) proposed a generic workflow towards designing social choice mechanisms using machine learning and outlined approaches could take to incorporate desirable axioms. Armstrong and Larson 2019) and FireFankss--- Queveeoo 2020 proposed using deep learning learn voting rules that satisfy
desirable axioms.
Kujawska et al. (020) and Burka al. 2021 used several classical machine learning methods such as support vector machines, gradient boosted trees and shallow MLPs to mimic existing voting rules (including Borda, Kemeny and Dodgson). Compared the models in Kujawska et al.) [2020) and Burka et al. [202T]. our PIN models have fundamental advantages such as anonymity by construction and generalization unseen numbers of voters.
Note that the theoretically optimal voting rule maximizes expected social welfare, not the accuracy by which the optimal candidate elected, which explains why its accuracy value may trail that of the learned voting rules.

---

Limitations and future directions
Our work currently limited to elections with complete rankings and strict orders, and the single- winner case. Future work should explore generalization to rankings that are incomplete and with ties, and potentially predicting rankings instead of single winner. Moreover, we're interested in architectures that support arbitrary number of candidates at test time by construction (for PIN architectures, number of candidates encountered during test time is limited by the number of candidates the network was trained on.) We would also like to explore the reinforcement learning approach to maximizing social welfare rather than supervised learning (discussed in Section 3.3
Last but not the least, we would like to raise two important points of considerations to the attention of practitioners working on sensitive applications: The neural networks architectures we discuss in the paper are neither interpretable nor transparent by construction, and further effort is needed to understand their inner workings. 2) There are no guarantees as their worst case performance and further empirical (and, is possible, theoretical) analyses is needed. Until the aforementioned points of consideration are addressed, we caution against the direct application of our methods on safety-critical and sensitive settings.
7 Conclusion
We show that PIN architectures are both theoretically and empirically well-suited for learning voting rules. PIN models respect voter anonymity by construction and universal approximators for representing voting rules. After training on synthetic data, PIN models generalize seamlessly to unseen real datasets and an unseen number of voters. They can also be trained to maximize social welfare better than fixed classical voting rules. The flexibility and effectiveness of our approach clears some of the hurdles in the design and implementation voting rules.
Acknowledgement
We are indebted to Nisarg Shah for his close guidance and feedback over the course of this work. We would also like to thank Roger Grosse for his helpful feedback on an early draft of this paper.
CA was supported by the CIFAR Graduate Scholarships Doctorate scholarship. XB was supported by a Natural Sciences and Engineering Research council (NSERC) Discovery Grant. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.
References
H. Allcott. Environmental policy and economics, Spring 2011. URL httpt::///ww..iii edu woterr/aaa----llllooe-aee-e-eeee sppriing-21 Cecture-noteste http:/11111111111111111111111111
courrees/ccooomics//////
B. Armstrong and K. Larson. Machine learning to strengthen democracy. In NewrlPS Joint Workshop Al for Social Good, 2019.
K. J. Arrow et al. An extension of the basic theorems of classical welfare economics. Proceedings of the second Berkeley symposium on mathematical statistics and probubility. The Regents of the University of Californa, 1951.
J. L. Ba, J. R. Kiros, and G. E. Hinton. Layer normalization. arXiv preprint arXiv:1607.06450 2016.
J. Bartholdi, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and welfare, 6(2):157-165, 1989.
J. Bennett, S. Lanning, et al. The netflix prize. In Proceedings of KDD cup and workshop, volume 2007, page 35. Citeseer, 2007.
C. Boutilier, I. Caragiannis, S. Haber, Lu, Procaccia, and O. Sheffet. Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227:190-213, 2015.
10

---

D. Bubboloni, M. Diss, and M. Gori. Extensions of the simpson voting rule to the committee selection setting, Public Choice, 183(1):51-115, 2020.
D. Burka, C. Puppe. L. Szepesváry, and A. Tasnádi. Voting: a machine learning approach. European Journal of Operational Research, 2021.
1. Caragiannis, S. Nath, A. D. Procaccia, and N. Shah. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58:123-1522 2017.
Z. Chen, S. Villar, L. Chen, and J. Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. pages 159922 Curran Associates, Inc.. 2019. https/ss:///poo mew.iinnrs.inipppp neur ips cc/ 1d0444226600444221111111 00000000066611000000111000410010
pdf
D. Firebanks-Quevedo. Machine learning? In my election? It's more likely than you think: Voting rules via neural networks. 2020.
P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He. Accurate, large minibatch sgd: Training imagenet hour. arXiv preprint arXiv: meee:070666500 2017.
S. loffe and C. Szegedy, Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. PMLR, 2015.
T. Kamishima. Nantonac collaborative filtering: recommendation based on order responses. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 583-588, 2003.
J. G. Kemeny. Mathematics without numbers. Daedalus, 88(4):577-591, 1959.
D. Kingma and J. Ba. Adam: method for stochastic optimization. ICLR (Poster), 2015.
H. Kujawska, M. Slavkovik, and J.JJ. Rückmann. Predicting the winners of borda, kemeny and dodgson elections with supervised machine learning. Multi-Agent Systems and Agreement Technologies, pages 440-458. Springer, 2020.
Langley, Crafting papers on machine learning. In P. Langley, editor, Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pages 1207-1216, Stanford, CA. 2000. Morgan Kaufmann.
J. Lee, Y. Lee, J. Kim, A. Kosiorek, S. Choi, and Y. W. Teh. Set transformer: A framework for batedd
neural networks, In International Conference Machine Learning, pages 3744-3753. PMLR, 2019.
A. Leman and B. Weisfeiler. A reduction of graph to canonical form and algebra arising during this reduction. Mauchhoo-Techmicheskayy Informatiiya, 2(9):12-16, 1968.
A. L. Maas, A. Y. Hannun, and A. Y. Ng. Rectifier nonlinearities improve neural network acoustic models. In Proc. icml, volume 30, page Citeseer, 2013.
A. Mao, A. Procaccia, and Y. Chen. Better human computation through principled voting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, 2013.
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. De Z. Lin, A. Desmaison, L. Antiga, and Lerer. Automatic differentiation Pytorch. 2017.
A. D. Procaccia, A. Zohar, Y. Peleg, and J. S. Rosenschein. The Icarnability of voting rules. Artificial 2009.
Intelligence, 173(12-13):1133-
Scarselli, M. Gori, A. C. Tsoi, Hagenbuchner, and Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-80 2008.

---

N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1): 1929-1958, 2014.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, pages 5998 6008, 2017.
M. Wang, L. Yu, D. Zheng, Q. Gan, Y. Gai, Z. Ye, M. Li, J. Zhou, Q. Huang, C. Ma, et al. Deep graph library: Towards efficient and scalable deep learning on graphs. 2019.
B. Weisfeiler and A. Leman. The reduction of graph to canonical form and the algebra which appears therein. Cauchno-Technicheseee Informatsia, 2(9):12-16, 1968.
L. Xia. Designing social choice mechanisms using machine learning. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pages 471 471-474, 2013.
R. Xiong, Y. Yang, D. He, K. Zheng, S. Zheng. C. Xing, H. Zhang, Y. Lan, L. Wang, and T. Liu. On layer normalization in the transformer architecture. In International Conference on Machine Learning, pages 10524-10533. PMLR, 2020.
K. Xu, W. Hu, J. Leskovee, and Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2018.
H. P. Young. Social choice scoring functions. SIAM Journal on Applied Mathematics, 28(4):824-838, 1975.
M. Zaheer, Kottur, S. Ravanbakhsh, Poczos, R. R. Salakhutdinov, and A. Smola. Deep sets. In Advances in neural information processing systems, pages 3391-3401, 2017.
M. Zhang. J. Lucas, J. Ba, and G. E. Hinton. Lookahead optimizer: k steps forward, 1 step back. Advances in Neural Information Processing Systems, 32:9597-9608, 2019.
12


Reviews:
[{"review_id": "nmqjGxQ3B75", "reviewer": "Reviewer_EcCg", "summary": "The authors study the problem of using machine learning techniques to 'automatically' learn voting mechanisms. Specifically, the authors use three permutation-invariant neural network architectures: DeepSet, Set Transformer and Graph Isomorphism Network and show that they can learn voting rules as well as maximize certain social welfare functions.\n\nThe first contribution is to show that these networks are universal function approximators of permutation invariant functions. Voting protocols typically fall within this class, as a permutation of votes should not lead to different outcomes: in other words, the identities of the voters do not matter.\n\nThe second contribution is to develop a learning procedure and evaluate the learned voting rules produced by these three algorithms (as well as a standard multi-layer perceptron, for reference). The way the training worked is to consider a population of voters and candidates such that the utility each voter has for the candidates is sampled from a distribution. Specifically, if there are $n$ voters and $k$ candidates, the utility of each candidate for voter $i$ is sampled by a Dirichlet distributions with all $k$ parameters set to $\\alpha_0$. Different values of $\\alpha_0$ correspond to different voters: some may prefer a single candidate or many of them equally. These values are then converted into an ordering, which the voters submit to the learned mechanism. The mechanisms' output is compared with the voting rule we are trying to learn (or the option which maximizes social welfare) a loss is incurred and a gradient descent step follows. On synthetic data, the learned mechanisms perform very well for all voting protocols tested, which are: Plurality, Borda, Copeland, Maximin and Kemeny.\n\nFinally, the same network architectures perform even better on real data sets, such as the Netflix Prize Data.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The article is very well written, with a clear exposition of the techniques and related work. It is easy to follow and honest: the results claimed in the abstract and introduction are indeed the ones developed later and their analysis is thorough (except possibly for one point).\n\nThe main criticism I have (and the reason I cannot fully recommend the paper) is that I am not totally sure of the following two: 1) why would it be difficult to learn voting rules (or maximize welfare) using off-the-shelf ML techniques? 2) Why would anyone try to re-learn any existing voting rule? \n\nI understand that the answer to the second is that perhaps the network will be able to learn some new voting rules which are not described yet. But how would this scenario appear? We would need some designer of a voting protocol with the capacity to generate hundreds of thousands of votes and outcomes, but without the capacity to formally define their relation. Moreover, the learned voting protocol would be quite difficult to motivate in a real election, since it's internals might be hidden behind the network weights.\n\nFinally, why are the experiments not run for more than 199 voters? I expected the real data sets to run in the hundreds of thousands, but I may have missed something.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately explained the limitations and societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "PuRugPzRBZq", "reviewer": "Reviewer_sGWw", "summary": "The Authors report a set of experiments with using neural networks with a particular architecture to learn optimal voting rules. They provide a concise theoretical description of the problem and prove that the chosen type of NNs are universal approximators of voting rules. They demonstrate experimentally that NNs can be trained using voter's ranked preferences only.\n\nThe experiments are of two kinds:\n\n1. teaching the NN known classical voting rules\n\n2. learning a new rule to maximise a given social welfare function\n\nTheir results show that NNs can learn known voting rules very well and that they can discover new voting rules which select optimal candidates more often than classical voting rules.\n\n--- EDIT ---\n\nIncreased the score to 7 after the clarifications.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The Authors tackle an interesting problem and report encouraging results. The paper is clearly written and the theoretical results are explained well. I liked the fact that the Authors made the effort to provide an introduction to the problem domain for lay readers (like me). However, there are some problems which prevented me from giving a higher score:\n\n1. the notation is not always clear:\n\n- is vec{u} a vector of one voters' utilities per candidate, or a vector of utility functions of all voters? Algorithm 1 suggests the 2nd, but the caption under Figure 1 suggests the 1st. This reviewer is a bit confused.\n\n- what exactly is the prediction loss function l optimised by Algorithm 1?\n\n2. the real-world datasets are not described sufficiently even in the Supplementary Material. Since the synthetic datasets used in the paper contain only uniform distributions of preferences (every candidate is equally likely to win on average), it would be interesting to know if the real-world datasets deviate from that. For example, is there a sushi type which is much more popular than all others? Many real-world situations such as presidential elections contain two or three dominant politicians and a string of niche candidates with little hope of winning.\n\n3. the discussion of the limitations of the method is lacking:\n\n- firstly, usually we deal with more than 99 voters. The Authors do not comment at all on the question how well would their method scale to realistic numbers of voters (i.e. up to millions). \n\n- secondly, since we do not know the actual utility functions of the voters, we probably need voting rules which are robust to perturbations. The Authors did not seem to have tested whether a voting rule learned on one type of utility functions behaves \"decently\" on other utility functions (e.g. train on \"uniform\", test on \"polarized\"). In other words, the network may be overfitting to modelling assumptions.\n\n- thirdly, the Authors do not comment on the question of interpretability of learned voting rules - an important problem if we are to implement such a rule in public life. It would also be fascinating to understand how the learned rules work and how they differ from the classical ones. E.g. how often does a learned rule indicate a different winner than the classical ones?\n\n- finally: as far as I understand, the presented NN architectures do not fulfil the neutrality criterion (as discussed in Appendix C.1 - I think should be moved to the main text). How do we know that, for datasets which have a dominant candidate, the network doesn't simply memorise which candidate should win? Couldn't this be tested by randomly permuting the candidates in the test set? (maybe the Authors have done that? i'm not sure)\n\n4. Figure 1 is hard to understand for me. It seems that the histograms are heavily concentrated in 1, with only the tails differing. Why not also provide the maximised value and compare it with the theoretical maximum? It would be much easier to understand than the histogram. (Especially that the meaning of \\vec{u} is not clear.) The same comment applies to similar Figures in Suppl. Mat.\n\n5. Minor: At least a sketch of the proof of Theorem 1 should be present in the main text.\n\nSome of the above comments are probably impossible to address given the page limits, so the Authors should treat them as my wishlist for their further work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The Authors comment on the societal impact, but the topic needs to be explored further, especially if the learned rules were to be used in a public setting (e.g. political elections).\n\nFor limitations, see pt. 3 above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "60p3Sb80J3", "reviewer": "Reviewer_Sk4S", "summary": "This paper empirically studies the ability of PIN (Set Transformer, GIN, DeepSets and MLP) applied to predicting the (top-1) winner of voting rules (Plurality, Borda, Copeland, Maximin and Kemeny) and predicting the social-welfare-maximizing (utilitarian and egalitarian) candidates. The PINs are trained on synthetic data, agents whose utility over candidates are generated from Dirichlet distributions. The PINs are tested on synthetic data (Table 1 & 3), synthetic data with more voters than in training time (Table 2) and real world data (Table 4). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n - The papers is well written and well motivated. The question of \"why would anyone want to predict the outcome of voting rule\" is addressed out-front on line 38, and the question of \"why not compare the full rankings\" is acknowledged in Section 6.\n - The result is strong and surprising (that training on synthetic data generalizes to real-world data). \n - The code is well organized and easy to follow, although I did not attempt to replicate the results. \n\nCons / questions:\n - Since the voting rules are traditionally assumed to output a ranking (possibly admitted by some scores), I wonder how the PINs do when evaluated in terms of rankings. Strictly speaking, one can use the binary-predicting PINs for n-1 rounds to predict a full ranking, no? \n - On the surprising result that training on synthetic data generalizes to real-world data: does this say anything about the real-world data, that it may follow some Dirichlet distributions?\n\n===============\n\nI acknowledge and appreciate the author response.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hrs"}, "extra_text": {}}, {"review_id": "3vw06YF7zk", "reviewer": "Reviewer_9xsn", "summary": "The paper studies two problems related to using neural networks as single winner voting rules. (1) Training networks to mimic well-known existing rules, and (2) training networks to act as novel rules that select utility-maximizing alternatives.\n\nThe major novel contribution of the paper is in their choice of network architecture. \"Permutation-invariant networks\" are used, which are agnostic to the order of input data, thus ensuring that the resultant voting rules are anonymous by default.\n\nExperiments show that the 3 PIN architectures considered are able to learn the studied voting rules with high accuracy after a large amount of training. These results are shown for testing done on each of real and synthetic data. Similarly, when the networks are trained with an oracle to learn the welfare maximizing alternative they perform quite well.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nOnly a handful of papers have studied the problem of using neural networks as voting rules and have typically focused on relatively basic MLP models. The novel contribution this paper makes is to demonstrate the importance of considering more complex models. This is also (to my knowledge) the first paper to learn voting rules to optimize social welfare.\n\nQuality:\nThe minor theoretical contribution of the paper seems sound.\nThe experimental results make a compelling case for the benefit of their contributions. Some experiments could be more thorough or would benefit from more discussion.\n\nClarity:\nThe paper has only a few minor typos and is clearly written. Most relevant details are included, though I would be surprised if they were enough to replicate the paper (although the included source code would presumably help with that and has a readme file that appears to have good instructions for running the code)\n\nSignificance:\nThe focus on more complex network architecture is very likely to be built upon by other researchers and appears to be an advance in the state of the art. Demonstrating the learnability of social welfare maximizing candidates, while not a particularly surprising result to me, is novel and likely to be replicated by other researchers in the future.\n\nMinor notes for clarification or consideration:\n- explanation of Simpson's rule in 2.2 could be phrased much more clearly\n- 2.3 seems to have limited relevance to the remainder of the paper. Consider making the link more clear or cutting it to expand other sections\n- My preference would be to see the input-output representation very briefly discussed in the text (footnote 4), it has been an important focus of other papers in this area and would be of interest to some readers\n- What is $\\alpha$ in section 4? Is there a reason for not giving the exact value? Is it chosen randomly? (If so, how?)\n- I can't find details on the distribution of numbers of voters and candidates within a training set. I believe a single set contains examples with varying numbers of voters (distributed how?), I'm not sure if the number of candidates varies. If so, that would be worth emphasizing as other work relies on a fixed number of candidates. \n- Is there a reason for training with 2 candidates? All rules will essentially reduce to plurality at that point.\n- Does training with varying numbers of voters help generalization to larger voter populations? ie. Would Table 2 have the same out-of-domain results if the networks were trained on elections with a constant number of voters? The answer might give insight as to whether the training procedure or architecture is responsible for this generalization out of domain.\n- footnote 8: Is there a motivating example for why solving batches of elections is important? That doesn't seem obvious\n- Table 4 is not referenced in the text. Consider doing that\n- Table 4 would be much more compelling if it considered how often all the rules being mimicked found the same winner. Are the networks learning the same thing when mimicking each rule or something different each time?\n- there are a number of very relevant papers that have used neural networks to act as voting rules that you should strongly consider referencing, the mains ones are listed below\n\n\nTypos:\n- end of Sec 1: \"in detail the proposed the training procedure\"\n- 3.2.1 line 3: \"in the case of [a] fully-connected graph structure[s]\" (should add one of [a] or [s])\n- Table 3 caption: \"and [are] mostly on par with,\"\n- 4.2, 2nd last paragraph: \"The neural network models [are] better at\"\n\n\nReferences to add:\n\nXia, Lirong. \"Designing social choice mechanisms using machine learning.\" Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems. 2013.\n\t\n- outlined the general approach most more recent papers have taken to use neural nets as voting rules\n\nArmstrong, Ben, and Kate Larson. \"Machine Learning to Strengthen Democracy.\" NeurIPS Joint Workshop on AI for Social Good. 2019.\n\t\n- describes an approach to generate novel voting rules based on desirable axioms with neural networks\n\nBurka, Dávid, et al. Voting: A machine learning approach. No. 145. KIT Working Paper Series in Economics, 2020.\n\t\n- similar to (Kujawska et al. 2020), describes an approach to mimicking voting rules with neural MLPs\n\nFirebanks-Quevedo, Daniel. \"Machine Learning? In MY Election? It's More Likely Than You Think: Voting Rules via Neural Networks.\" 2020.\n\t\n- similar to (Armstrong and Larson, 2019), generates voting rules automatically based on axioms and other desirable conditions", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors very briefly point out the major limitation of this work: there are no clear worst-case performance guarantees so relying on this in practice may be dangerous.", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2xxm3KS5X2d", "reviewer": "Reviewer_Csu6", "summary": "The authors study how to learn voting rules, both in terms of mimicking existing voting rules and learning new voting rules to (in particular) maximize different versions of social welfare (e.g., egalitarian or utilitarian social welfare). They show that a particular class of neural network architectures (PINs) are well-suited to this task and evaluate their proposed approach experimentally.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors mainly investigate how to mimic different voting rules. Although most of them are relatively straightforward to compute, they do achieve good results mimicking the Kemeny rule, which is a good sign for PINs. \n\nTheir theoretical result also remains a bit weak. If I understand it correctly, it states that different permutations are mapped to different embeddings, and doesn't say anything about the feasibility of learning these embeddings.\n\nOverall, I appreciate the fact that the authors used more datasets and included results about the Kemeny rule, which is considerably more complex than other rules they mimic. I still do not know if I find their results incredibly compelling -- it seems like the bulk of the paper is about mimicking voting rules, and only section 4.2 talks about learning rules in order to maximize social welfare, which seems like a much more interesting objective overall.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Majority of the reviewers are excited about the novel applications of ML techniques to social choice and were impressed by the good performance of the solution proposed in this paper. The paper is well-written and the work is solid. Some concerns were raised about the significance and motivation of the actual technical problem solved in this paper (i.e., learning social welfare maximizers) and technical depth in ML.

The response was generally effective and clarified some points raised by the reviewers. After the discussions, reviewers' opinions did not change much (except the score of one reviewer was raised from 6 to 7). The overall sentiment remained positive.

After all, the novelty and potential to stimulate future work and discussions outweigh the cons, which is the main reason behind the recommendation.
Decision: Accept (Poster)