summaries: The central part of the paper is the design of a learned positional encoding (LPE) that can be used in graph transformers in a similar way the positional encoding is used in text transformers. The authors propose to use eigenvalues and eigenfunctions to encode node positions in a graph, and demonstrate how to incorporate them into a transformer model that achieves high expressivity. The architectural choices are based on the theoretical introduction in which some concepts are borrowed from physics, such as the analogy to electric potential between nodes. The LPE is designed to address five principles that were overlooked by different methods. The authors also implement a new model, Spectral Attention Network (SAN), that utilizes the LPE resulting from the theoretical findings. The experimental results confirm the efficacy of the method.

summaries: This paper presents an interesting idea on designing a novel graph transformer with learning positional encoding by a spectral attention network (SAN) using the full Laplacian spectrum. Three theoretical limitations from previous efforts are overcome by this spectral attention, namely WL test and universality, over-squashing and physical interactions. Experimental results on four standard datasets demonstrate the effectiveness of the proposed SAN.

summaries: This paper proposes a learned position encoding mechanism which can fully make use of the eigenvalues and eigenvectors information from the graph Laplacian. The learned position encoding is then concatenated with the embedded node feature. In addition, the edge feature is also served as an input feature in order to completely leverage the graph structural information. Also, by fully connecting the graph, it helps tackle the common over-squashing problem in many GNNs. The paper also proposes an alternative version of attention so that real edges and added edges are taken into account separately when computing the attention. Eventually, the paper empirically tests the performance of the proposed model on real graph datasets.

summaries: This work proposes a transformer designed for graph structured data. As opposed to GNNs, the transformer allows non-neighboring nodes to communicate. To avoid loosing information on the structure of the graph, the transformer needs some form of structure encoding of the nodes, a non trivial problem for graphs. A common PE scheme consists in using the spectrum of the graphs Laplacian but, as detailed by the authors, this raises some issues. The authors propose an improved positional encoding circumventing these problems and demonstrate that a fully connected transformer is competitive with GNNs on four datasets.

abstractText: In recent years, the Transformer architecture has proven to be very successful in sequence processing, but its application to other data structures, such as graphs, has remained limited due to the difficulty of properly defining positions. Here, we present the Spectral Attention Network (SAN), which uses a learned positional encoding (LPE) that can take advantage of the full Laplacian spectrum to learn the position of each node in a given graph. This LPE is then added to the node features of the graph and passed to a fully-connected Transformer. By leveraging the full spectrum of the Laplacian, our model is theoretically powerful in distinguishing graphs, and can better detect similar sub-structures from their resonance. Further, by fully connecting the graph, the Transformer does not suffer from over-squashing, an information bottleneck of most GNNs, and enables better modeling of physical phenomenons such as heat transfer and electric interaction. When tested empirically on a set of 4 standard datasets, our model performs on par or better than state-of-theart GNNs, and outperforms any attention-based model by a wide margin, becoming the first fully-connected architecture to perform well on graph benchmarks.

authors:
Uri Alon
Eran Yahav

title: On the bottleneck of graph neural networks and its practical implications

authors:
Dominique Beaini
Sofiane Achiche
Alexandre Duperré
Maxime Raison

title: Deep green function convolution for improving saliency in convolutional neural networks

venue: The Visual Computer,

authors:
Dominique Beaini
Saro Passaro
Vincent Létourneau
William L. Hamilton
Gabriele Corso
Pietro Liò

title: Directional graph networks

authors:
Xavier Bresson
Thomas Laurent

title: Residual gated graph convnets

venue: arXiv preprint arXiv:1711.07553,

authors:
Michael M. Bronstein
Joan Bruna
Yann LeCun
Arthur Szlam
Pierre Vandergheynst

title: Geometric deep learning: going beyond euclidean data

venue: IEEE Signal Processing Magazine,

title: A History of Mathematics

venue: AMS Chelsea Publishing Series. AMS Chelsea,

authors:
Heng Chang
Yu Rong
Tingyang Xu
Wenbing Huang
Somayeh Sojoudi
Junzhou Huang
Wenwu Zhu

title: Spectral graph attention

authors:
Fan Chung
S.T. Yau

title: Discrete green’s functions

venue: Journal of Combinatorial Theory, Series A,

authors:
Ronald R. Coifman
Stéphane Lafon

title: Special Issue: Diffusion Maps and Wavelets

venue: Diffusion maps. Applied and Computational Harmonic Analysis,

authors:
Gabriele Corso
Luca Cavalleri
Dominique Beaini
Pietro Liò
Petar

title: Veličković. Principal neighbourhood aggregation for graph nets

venue: arXiv preprint arXiv:2004.05718,

authors:
Luca Cosmo
Mikhail Panine
Arianna Rampini
Maks Ovsjanikov
Michael M. Bronstein
Emanuele Rodola

title: Isospectralization, or how to hear shape, style, and correspondence

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Yushun Dong
Kaize Ding
Brian Jalaian
Shuiwang Ji
Jundong Li

title: Graph neural networks with adaptive frequency response

venue: filter. CoRR,

authors:
Vijay Prakash Dwivedi
Xavier Bresson

title: A generalization of transformer networks to graphs, 2020

authors:
Vijay Prakash Dwivedi
Chaitanya K Joshi
Thomas Laurent
Yoshua Bengio
Xavier Bresson

title: Benchmarking graph neural networks

venue: arXiv preprint arXiv:2003.00982,

authors:
Richard Phillips Feynman
Robert Benjamin Leighton
Matthew Sands

title: The Feynman lectures on physics; New millennium ed

venue: Basic Books,

authors:
Justin Gilmer
Samuel S Schoenholz
Patrick F Riley
Oriol Vinyals
George E Dahl

title: Neural message passing for quantum chemistry

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

title: Graph Representation Learning

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

authors:
Weihua Hu
Matthias Fey
Marinka Zitnik
Yuxiao Dong
Hongyu Ren
Bowen Liu
Michele Catasta
Jure Leskovec

title: Open graph benchmark: Datasets for machine learning on graphs

authors:
Wengong Jin
Regina Barzilay
Tommi Jaakkola

title: Junction tree variational autoencoder for molecular graph generation

title: Can one hear the shape of a drum

venue: The American Mathematical Monthly,

authors:
Anees Kazi
Luca Cosmo
Nassir Navab
Michael Bronstein

title: Differentiable graph module (dgm) graph convolutional networks

venue: arXiv preprint arXiv:2002.04999,

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: arXiv preprint arXiv:1609.02907,

title: Laplace-beltrami eigenfunctions towards an algorithm that "understands" geometry

venue: In IEEE International Conference on Shape Modeling and Applications 2006 (SMI’06),

authors:
Pan Li
Yanbang Wang
Hongwei Wang
Jure Leskovec

title: Distance encoding: Design provably more powerful neural networks for graph representation learning, 2020

authors:
Haggai Maron
Heli Ben-Hamu
Hadar Serviansky
Yaron Lipman

title: Provably powerful graph networks

venue: arXiv preprint arXiv:1905.11136,

authors:
Christopher Morris
Martin Ritzert
Matthias Fey
William L Hamilton
Jan Eric Lenssen
Gaurav Rattan
Martin Grohe

title: Weisfeiler and leman go neural: Higher-order graph neural networks

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in pytorch

title: Can one hear the shape of a molecule (from its coulomb matrix eigenvalues)

venue: Journal of Chemical Information and Modeling,

authors:
Yi Tay
Mostafa Dehghani
Dara Bahri
Donald Metzler

title: Efficient transformers: A survey, 2020

authors:
Edwin R. van Dam
Willem H. Haemers

title: Which graphs are determined by their spectrum

venue: Linear Algebra and its Applications,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N. Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention is all you

venue: need. CoRR,

authors:
Minjie Wang
Da Zheng
Zihao Ye
Quan Gan
Mufei Li
Xiang Song
Jinjing Zhou
Chao Ma
Lingfan Yu
Yu Gai
Tianjun Xiao
Tong He
George Karypis
Jinyang Li
Zheng Zhang

title: Deep graph library: A graph-centric, highly-performant package for graph neural networks

venue: arXiv preprint arXiv:1909.01315,

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

venue: arXiv preprint arXiv:1810.00826,

authors:
Chulhee Yun
Srinadh Bhojanapalli
Ankit Singh Rawat
Sashank J. Reddi
Sanjiv Kumar

title: Are transformers universal approximators of sequence-to-sequence functions

authors:
Chulhee Yun
Yin-Wen Chang
Srinadh Bhojanapalli
Ankit Singh Rawat
Sashank J. Reddi
Sanjiv Kumar

title: $o(n)$ connections are expressive enough: Universal approximability of sparse transformers

heading: 1 Introduction

text:
The prevailing strategy for graph neural networks (GNNs) has been to directly encode graph structure structure through a sparse message-passing process [17, 19]. In this approach, vector messages are iteratively passed between nodes that are connected in the graph. Multiple instantiations of this message-passing paradigm have been proposed, differing in the architectural details of the message-passing apparatus (see [19] for a review).
However, there is a growing recognition that the message-passing paradigm has inherent limitations. The expressive power of message passing appears inexorably bounded by the Weisfeiler-Lehman isomorphism hierarchy [29, 30, 39]. Message-passing GNNs are known to suffer from pathologies, such
∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
as oversmoothing, due to their repeated aggregation of local information [19], and over-squashing, due to the exponential blow-up in computation paths as the model depth increases [1].
As a result, there is a growing interest in deep learning techniques that encode graph structure as a soft inductive bias, rather than as a hard-coded aspect of message passing [14, 24]. A central issue with message-passing paradigm is that input graph structure is encoded by restricting the structure of the model’s computation graph, inherently limiting its flexibility. This reminds us of how early recurrent neural networks (RNNs) encoded sequential structure via their computation graph—a strategy that leads to well-known pathologies such as the inability to model long-range dependencies [20].
There is a growing trend across deep learning towards more flexible architectures, which avoid strict and structural inductive biases. Most notably, the exceptionally successful Transformer architecture removes any structural inductive bias by encoding the structure via soft inductive biases, such as positional encodings [36]. In the context of GNNs, the self-attention mechanism of a Transformer can be viewed as passing messages between all nodes, regardless of the input graph connectivity.
Prior work has proposed to use attention in GNNs in different ways. First, the GAT model [37] proposed local attention on pairs of nodes that allows a learnable convolutional kernel. The GTN work [42] has improved on the GAT for node and link predictions while keeping a similar architecture, while other message-passing approaches have used enhancing spectral features [8, 13] . More recently, the GT model [14] was proposed as a generalization of Transformers to graphs, where they experimented with sparse and full graph attention while providing low-frequency eigenvectors of the Laplacian as positional encodings.
In this work, we offer a principled investigation of how Transformer architectures can be applied in graph representation learning. Our primary contribution is the development of novel and powerful learnable positional encoding methods, which are rooted in spectral graph theory. Our positional encoding technique — and the resulting spectral attention network (SAN) architecture — addresses key theoretical limitations in prior graph Transformer work [14] and provably exceeds the expressive power of standard message-passing GNNs. We show that full Transformer-style attention provides consistent empirical gains compared to an equivalent sparse message-passing model, and we demonstrate that our SAN architecture is competitive with or exceeding the state-of-the-art on several well-known graph benchmarks. An overview of the entire method is presented in Figure 1, with a link to the code here: https://github.com/DevinKreuzer/SAN.

heading: 2 Theoretical Motivations

text: There can be a significant loss in structural information if naively generalizing Transformers to graphs. To preserve this information as well as local connectivity, previous studies [37, 14] have proposed to use the eigenfunctions of their Laplacian as positional encodings. Taking this idea further by using the full expressivity of eigenfunctions as positional encodings, we can propose a principled way of understanding graph structures using their spectra. The advantages of our methods compared to previous studies [37, 14] are shown in Table 1.

heading: 2.1 Absolute and relative positional encoding with eigenfunctions

text: The notion of positional encodings (PEs) in graphs is not a trivial concept, as there exists no canonical way of ordering nodes or defining axes. In this section, we investigate how eigenfunctions of the Laplacian can be used to define absolute and relative PEs in graphs, to measure physical interactions between nodes, and to enable ”hearing” of specific sub-structures - similar to how the sound of a drum can reveal its structure.

heading: 2.1.1 Eigenvectors equate to sine functions over graphs

text:
In the Transformer architecture, a fundamental aspect is the use of sine and cosine functions as PEs for sequences [36]. However, sinusoids cannot be clearly defined for arbitrary graphs, since there is no clear notion of position along an axis. Instead, their equivalent is given by the eigenvectors φ of the graph Laplacian L. Indeed, in a Euclidean space, the Laplacian (or Laplace) operator corresponds to the divergence of the gradient and its eigenfunctions are sine/cosine functions, with the squared frequencies corresponding to the eigenvalues (we sometimes interchange the two notions from here on). Hence, in the graph domain, the eigenvectors of the graph Laplacian are the natural equivalent of sine functions, and this intuition was employed in multiple recent works which use the eigenvectors as PEs for GNNs [15], for directional flows [4] and for Transformers [14].
Being equivalent to sine functions, we naturally find that the Fourier Transform of a function F [f ] applied to a graph gives F [f ](λi) = 〈f,φi〉, where the eigenvalue is considered as a position in the Fourier domain of that graph [6]. Thus, the eigenvectors are best viewed as vectors positioned on the axis of eigenvalues rather than components of a matrix as illustrated in Figure 2.

heading: 2.1.2 What do eigenfunctions tell us about relative positions?

text:
In addition to being the analog of sine functions, the eigenvectors of the Laplacian also hold important information about the physics of a system and can reveal distance metrics. This is not surprising as
the Laplacian is a fundamental operator in physics and is notably used in Maxwell’s equations [16] and the heat diffusion [6].
In electromagnetic theory, the (pseudo)inverse of the Laplacian, known in mathematics as the Green’s function of the Laplacian [9], represents the electrostatic potential of a given charge. In a graph, the same concept uses the pseudo-inverse of the LaplacianG and can be computed by its eigenfunctions. See equation 1 , where G(j1, j2) is the electric potential between nodes j1 and j2, φ̂i and λ̂i are the i-th eigenvectors and eigenvalues of the symmetric LaplacianD −1 2 LD −1 2 , andD is the degree
matrix, and φ̂i,j the j-th row of the vector.
G(j1, j2) = d 1 2 j1 d −1 2 j2 ∑ i>0 (φ̂i,j1φ̂i,j2) 2 λ̂i (1)
Further, the original solution of the heat equation given by Fourier relied on a sum of sines/cosines known as a Fourier series [7]. As eigenvectors of the Laplacian are the analogue of these functions in graphs, we find similar solutions. Knowing that heat kernels are correlated to random walks [6, 4], we use the interaction between two heat kernels to define in equation 2 the diffusion distance dD between nodes j1, j2 [6, 10]. Similarly, the biharmonic distance dB was proposed as a better measure of distances [28]. Here we use the eigenfunctions of the regular Laplacian L.
d2D(j1, j2) = ∑ k>0 e−2tλi(φi,j1 − φi,j2)2 , d2B(j1, j2) = ∑ i>0 (φi,j1 − φi,j2)2 λ2i (2)
There are a few things to note from these equations. Firstly, they highlight the importance of pairing eigenvectors and their corresponding eigenvalues when supplying information about relative positions in a graph. Secondly, we notice that the product of eigenvectors is proportional to the electrostatic interaction, while the subtraction is proportional to the diffusion and biharmonic distances. Lastly, there is a consistent pattern across all 3 equations: smaller frequencies/eigenvalues are more heavily weighted when determining distances between nodes.

heading: 2.1.3 Hearing the shape of a graph and its sub-structures

text:
Another well-known property of eigenvalues is how they can be used to discriminate between different graph structures and sub-structures, as they can be interpreted as the frequencies of resonance of the graph. This led to the famous question about whether we can hear the shape of a drum from its eigenvalues [23], with the same questions also applying to geometric objects [12] and 3D molecules [33]. Various success was found with the eigenfunctions being used for partial functional correspondence [32], algorithmic understanding geometries [26], and style correspondence [12]. Examples of eigenvectors for molecular graphs are presented in Figure 3.
2.2 Laplace Eigenfunctions etiquette
In Euclidean space and sequences, using sinusoids as PEs is trivial: we can simply select a set of frequencies, compute the sinusoids, and add or concatenate them to the input embeddings, as is done in the original Transformer [36]. However, in arbitrary graphs, reproducing these steps is not as simple since each graph has a unique set of eigenfunctions. In the following section, we present key principles from spectral graph theory to consider when constructing PEs for graphs, most of which have been overlooked by prior methods. They include normalization, the importance of the eigenvalues and their multiplicities, the number of eigenvectors being variable, and sign ambiguities. Our LPE architectures, presented in section 3, aim to address them.
Normalization. Given an eigenvalue of the Laplacian, there is an associated eigenspace of dimension greater than 1. To make use of this information in our model, a single eigenvector has to be chosen. In our work, we use the L2 normalization since it is compatible with the definition of the Green’s function (1). Thus, we will always chose eigenvectors φ such that 〈φ,φ〉 = 1. Eigenvalues. Another fundamental aspect is that the eigenvalue associated with each eigenvector supplies valuable information. An ordering of the eigenvectors based on their eigenvalue works in sequences since the frequencies are pre-determined. However, this assumption does not work in graphs since the eigenvalues in their spectrum can vary. For example, in Figure 3, we observe how an ordering would miss the fact that both molecules resonate at λ = 1 in different ways.
Multiplicities. Another important problem with choosing eigenfunctions is the possibility of a high multiplicity of the eigenvalues, i.e. when an eigenvalue appears as a root of the characteristic polynomial more than once. In this case, the associated eigenspace may have dimension 2 or more as we can generate a valid eigenvector from any linear combination of eigenvectors with the same eigenvalue. This further complicates the problem of choosing eigenvectors for algorithmic computations and highlights the importance of having a model that can handle this ambiguity.
Variable number of eigenvectors. A graphGi can have at mostNi linearly independent eigenvectors with Ni being its number of nodes. Most importantly, Ni can vary across all Gi in the dataset. Prior work [14] elected to select a fixed number k eigenvectors for each graph, where k ≤ Ni,∀i. This produces a major bottleneck when the smallest graphs have significantly fewer nodes than the largest graphs in the dataset since a very small proportion of eigenvectors will be used for large graphs. This inevitably causes loss of information and motivates the need for a model which constructs fixed PEs of dimension k, where k does not depend on the number of eigenvectors in the graph.
Sign invariance. As noted earlier, there is a sign ambiguity with the eigenvectors. With the sign of φ being independent of its normalization, we are left with a total of 2k possible combination of signs when choosing k eigenvectors of a graph. Previous work has proposed to do data augmentation by randomly flipping the sign of the eigenvectors [4, 15, 14], and although it can work when k is small, it becomes intractable for large k.

heading: 2.3 Learning with Eigenfunctions

text:
Learning generalizable information from eigenfunctions is fundamental to their succesful usage. Here we detail important points that support it is possible to do so if done correctly.
Similar graphs have similar spectra. Thus, we can expect the network to transfer patterns across graphs through the similarity of their spectra. In fact, spectral graph theory tells us that the lowest and largest non-zero eigenvalues are both linked to the geometry of the graph (algebraic connectivity and spectral radius).
Eigenspaces contain geometric information. Spectral graph theory has studied the geometric and physical properties of graphs from their Laplacian eigenfunctions in depth. Developing a method that can use the full spectrum of a graph makes it theoretically possible capture this information. It us thus important to capture differences between the full eigenspaces instead of minor differences between specific eigenvalues or eigenvectors from graph to graph.
Learned positions are relative within graphs. Eigenspaces are used to understand the relationship between nodes within graphs, not across them. Proposed models should therefore only compare the eigenfunctions of nodes within graphs.

heading: 3 Model Architecture

text:
In this section, we propose an elegant architecture that can use the eigenfunctions as PEs while addressing the concerns raised in section 2.2. Our Spectral Attention Network (SAN) model inputs eigenfunctions of a graph and projects them into a learned positional encoding (LPE) of fixed size. The LPE allows the network to use up to the entire Laplace spectrum of each graph, learn how the frequencies interact, and decide which are most important for the given task.
We propose a two-step learning process summarized earlier in Figure 1. The first step, depicted by blocks (c-d-e) in the figure, applies a Transformer over the eigenfunctions of each node to generate an LPE matrix for each graph. The LPE is then concatenated to the node embeddings (blocks g-h), before being passed to the Graph Transformer (block i). If the task involves graph classification or regression, the final node embeddings are subsequently passed to a final pooling layer.

heading: 3.1 LPE Transformer Over Nodes

text:
Using Laplace encodings as node features is ubiquitous in the literature concerning the topic. Here, we propose a method for learning node PEs motivated by the principles from section 2.2. The idea of our LPE is inspired by Figure 2, where the eigenvectors φ are represented as a non-uniform sequence with the eigenvalue λ being the position on the frequency axis. With this representation, Transformers are a natural choice for processing them and generating a fixed-size PE.
The proposed LPE architecture is presented in Figure 4. First, we create an embedding matrix of size 2 × m for each node j by concatenating the m-lowest eigenvalues with their associated eigenvectors. Here, m is a hyper-parameter for the maximum number of eigenvectors to compute and is analog to the variable-length sequence for a standard Transformer. For graphs where m > N , a masked-padding is simply added. Note that to capture the entire spectrum of all graphs, one can simply select m such that it is equal to the maximum number of nodes a graph has in the dataset. A linear layer is then applied on the dimension of size 2 to generate new embeddings of size k. A Transformer Encoder then computes self-attention on the sequence of length m and hidden dimension k. Finally, a sum pooling reduces the sequence into a fixed k-dimensional node embedding.
The LPE model addresses key limitations of previous graph Transformers and is aligned with the first four etiquettes presented in section 2.2. By concatenating the eigenvalues with the normalized eigenvector, this model directly addresses the first three etiquettes. Namely, it normalizes the eigenvectors, pairs eigenvectors with their eigenvalues and treats the number of eigenvectors as a variable. Furthermore, the model is aware of multiplicities and has the potential to linearly combine or ignore some of the repeated eigenvalues.
However, this method still does not address the limitation that the sign of the pre-computed eigenvectors is arbitrary. To combat this issue, we randomly flip the sign of the pre-computed eigenvectors during training as employed by previous work [15, 14], to promote invariance to the sign ambiguity.

heading: 3.2 LPE Transformer Over Edges

text:
Here we present an alternative formulation for Laplace encodings. This method addresses the same issues as the LPE over nodes, but also resolves the eigenvector sign ambiguity. Instead of encoding absolute positions as node features, the idea is to consider relative positions encoded as edge features.
Inspired by the physical interactions introduced in 1 and 2, we can take a pair of nodes (j1, j2) and obtain sign-invariant operators using the absolute subtraction |φi,j1 − φi,j2 | and the product φi,j1φi,j2 . These operators acknowledge that the sign of φi,j1 at a given node j1 is not important, but that the relative sign between nodes j1 and j2 is important. One might argue that we could directly compute the deterministic values from equations (1, 2) as edge features instead. However, our goal is to construct models that can learn which frequencies to emphasize and are not biased towards the lower frequencies — despite lower frequencies being useful in many tasks.
This approach is only presented thoroughly in appendix A, since it suffers from a major computational bottleneck compared to the LPE over nodes. In fact, for a fully-connected graph, there are N times more edges than nodes, thus the computation complexity is O(m2N2), or O(N4) considering all eigenfunctions. The same limitation also affects memory and prevents the use of large batch sizes.

heading: 3.3 Main Graph Transformer

text:
Our attention mechanism in the main Transformer is based on previous work [14], which attempts to repurpose the original Transformer to graphs by considering the graph structure and improving attention estimates with edge feature embeddings.
In the following, note that hli is the i-th node’s features at the l-th layer, and eij is the edge feature embedding between nodes i and j. Our model employs multi-head attention over all nodes:
ĥl+1i = O l h
Hn
k=1 ( ∑ j∈V wk,lij V k,lhlj) (3)
where Olh ∈ Rd×d, V k,l ∈ Rdk×d, H denotes the number of heads, L the number of layers, and f concatenation. Note that d is the hidden dimension, while dk is the dimension of a head ( dH = dk).
A key addition from our work is the design of an architecture that performs full-graph attention while preserving local connectivity with edge features via two sets of attention mechanisms: one for nodes connected by real edges in the sparse graph and one for nodes connected by added edges in the fully-connected graph. The attention weights wk,lij in equation 3 at layer l and head k are given by:
ŵk,lij =  Q1,k,lhli◦K 1,k,lhlj◦E 1,k,leij√ dk if i and j are connected in sparse graph Q2,k,lhli◦K 2,k,lhlj◦E
2,k,leij√ dk
otherwise
 (4)
wk,lij =  1 1+γ · softmax( ∑ dk ŵk,lij ) if i and j are connected in sparse graph
γ 1+γ · softmax( ∑ dk ŵk,lij ) otherwise  (5) where ◦ denotes element-wise multiplication and Q1,k,l, Q2,k,l, K1,k,l, K2,k,l, E1,k,l, E2,k,l ∈ Rdk×d. γ ∈ R+ is a hyperparameter which tunes the amount of bias towards full-graph attention, allowing flexibility of the model to different datasets and tasks where the necessity to capture longrange dependencies may vary. Note that softmax outputs are clamped between−5 and 5 for numerical stability and that the keys, queries and edge projections are different for pairs of connected nodes (Q1,K1,E1) and disconnected nodes (Q2,K2,E2).
A multi-layer perceptron (MLP) with residual connections and normalization layers are then applied to update representations, in the same fashion as the GT method [14]. ˆ̂ hl+1 = Norm(hli + ĥ l+1 i ), ˆ̂ ĥl+1i =W l 2ReLU(W l 1 ˆ̂ hl+1i ), h l+1 i = Norm( ˆ̂ hl+1 + ˆ̂ ĥl+1i ) (6)
with the weight matrices W l1 ∈ R2d×d, W l2 ∈ Rd×2d. Edge representations are not updated as it adds complexity with little to no performance gain. Bias terms are omitted for presentation.

heading: 3.4 Limitations

text:
The first limitation of the node-wise LPE, and noted in Table 1 is the lack of sign invariance of the model. A random sign-flip of an eigenvector can produce different outputs for the LPE, meaning
that the model needs to learn a representation invariant to these flips. We resolve this issue with the edge-wise LPE proposed in 3.2, but it comes at a computational cost.
Another limitation of the approach is the computational complexity of the LPE being O(m2N), or O(N3) if considering all eigenfunctions. Further, as nodes are batched in the LPE, the total memory on the GPU will be num_params * num_nodes_in_batch instead of num_params * batch_size. Although this is limiting, the LPE is not parameter hungry, with k usually kept around 16. Most of the model’s parameters are in the Main Graph Transformer of complexity O(N2).
Despite Transformers having increased complexity, they managed to revolutionalize the NLP community. We argue that to shift away from the message-passing paradigm and generalize Transformers to graphs, it is natural to expect higher computational complexities. This is exacerbated by sequences being much simpler to understand than graphs due to their linear structure. Future work could overcome this by using variations of Transformers that scale linearly or logarithmically [34].

heading: 3.5 Theoretical properties of the architecture

text:
Due to the full connectivity, it is trivial that our model does not suffer from the same limitations in expressivity as its convolutional/message-passing counterpart.
WL test and universality. The DGN paper [4] showed that using the eigenvector φ1 is enough to distinguish some non-isomorphic graphs indistinguishable by the 1-WL test.
Given that our model uses the full set of eigenfunctions, and given enough parameters, our model can distinguish any pair of non-isomorphic graphs and is more powerful than any WL test in that regard. However, this does not solve the graph isomorphism problem in polynomial time; it only approximates a solution, and the number of parameters required is unknown and possibly non-polynomial. In appendix C, we present a proof of our statement, and discuss why the WL test is not well suited to study the expressivity of graph Transformers due to their universality.
Reduced over-squashing. Over-squashing represents the difficulty of a graph neural network to pass information to distant neighbours due to the exponential blow-up in computational paths [1].
For the fully-connected network, it is trivial to see that over-squashing is non-existent since there are direct paths between distant nodes.
Physical interactions. Another point to consider is the ability of the network to learn physical interactions between nodes. This is especially important when the graph models physical, chemical, or biological structures, but can also help understanding pixel interaction in images [2, 3]. Here, we argue that our SAN model, which uses the Laplace spectrum more effectively, can learn to mimic the physical interactions presented in section 2.1.2. This contrasts with the convolutional approach that requires deep layers for the receptive field to capture long-distance interactions. It also contrasts with the GT model [14], which does not use eigenvalues or enough eigenfunctions to properly model physical interactions in early layers. However, due to the lack of sign-invariance in the proposed node-wise LPE, it is difficult to learn these interactions accurately. The edge-wise LPE (section 3.2) could be better suited for the problem, but it suffers from higher computational complexity.

heading: 4 Experimental Results

text:
The model is implemented in PyTorch [31] and DGL [38] and tested on established benchmarks from [15] and [21] provided under MIT license. Specifically, we applied our method on ZINC, PATTERN, CLUSTER, MolHIV and MolPCBA, while following their respective training protocols with minor changes, as detailed in the appendix B.1. The computation time and hardware is provided in appendix B.4.
We first conducted an ablation study to fairly compare the benefits of using full attention and/or the node LPE. We then took the best-performing model, tuned some of its hyperparameters, and matched it up against the current state-of-the-art methods. Since we use a similar attention mechanism, our code was developed on top of the code from the GT paper [14], provided under the MIT license.

heading: 4.1 Sparse vs. Full Attention

text:
To study the effect of incorporating full attention, we present an ablation study of the γ parameter in Figure 5. We remind readers that γ is used in equation 5 to balance between sparse and full attention. Setting γ = 0 strictly enables sparse attention, while γ = 1 does not bias the model in any direction.
It is apparent that molecular datasets, namely ZINC and MOLHIV, benefit less from full attention, with the best parameter being log γ ∈ (−7,−5). On the other hand, the larger SBM datasets (PATTERN and CLUSTER) benefit from a higher γ value. This can be explained by the fact that molecular graphs rely more on understanding local structures such as the presence of rings and specific bonds, especially in the artificial task from ZINC which relies on counting these specific patterns [15]. Furthermore, molecules are generally smaller than SBMs. As a result, we would expect less need for full attention, as information between distant nodes can be propagated with few iterations of even sparse attention. We also expect molecules to have fewer multiplicities, thus reducing the space of eigenvectors. Lastly, the performance gains in using full attention on the CLUSTER dataset can be attributed to it being a semi-supervised task, where some nodes within each graph are assigned their true labels. With full attention, every node receives information from the labeled nodes at each iteration, reinforcing confidence about the community they belong to.
In Figure 6, we present another ablation study to measure the impact of the node LPE in both the sparse and full architectures. We observe that the proposed node-wise LPE contributes significantly to the performance for molecular tasks (ZINC and MOLHIV), and believe that it can be attributed to the detection of substructures (see Figure 3). For PATTERN and CLUSTER, the improvement is modest as the tasks are simple clustering [15]. Previous work even found that the optimal number of eigenvectors to construct PE for PATTERN is only 2 [14].

heading: 4.2 Comparison to the state-of-the-art

text:
When comparing to the state-of-the-art (SOTA) models in the literature in Figure 7, we observe that our SAN model consistently performs better on all synthetic datasets from [15], highlighting the strong expressive power of the model. On the MolHIV dataset, the performance on the test set is slightly lower than the SOTA. However, the model performs better on the validation set (85.30%) in comparison to PNA (84.25%) and DGN (84.70%). This can be attributed to a well-known issue with this dataset: the validation and test metrics have low correlation. In our experiments, we found higher test results with lower validation scores when restricting the number of epochs. Here, we also included results on the MolPCBA dataset, where we witnessed competitive results as well.
Other top-performing models, namely PNA [11] and DGN [4], use a message-passing approach [17] with multiple aggregators. When compared to attention-based models, SAN consistently outperforms the SOTA by a wide margin. To the best of our knowledge, SAN is the first fully-connected model to perform well on graph tasks, as is evident by the poor performance of the GT (full) model.

heading: 5 Conclusion

text:
In summary, we presented the SAN model for graph neural networks, a new Transformer-based architecture that is aware of the Laplace spectrum of a given graph from the learned positional encodings. The model was shown to perform on par or better than the SOTA on multiple benchmarks and outperforms other Attention-based models by a large margin. As is often the case with Transformers, the current model suffers from a computational bottleneck, and we leave it for future work to implement variations of Transformers that scale linearly or logarithmically. This will enable the edge-wise LPE presented in appendix A, a theoretically more powerful version of the SAN model.
Societal Impact. The presented work is focused on theoretical and methodological improvements to graph neural networks, so there are limited direct societal impacts. However, indirect negative impacts could be caused by malicious applications developed using the algorithm. One such example is the tracking of people on social media by representing their interaction as graphs, thus predicting and influencing their behavior towards an external goal. It also has an environmental impact due to the greater energy use that arises from the computational cost O(m2N +N2) being larger than standard message passing or convolutional approaches of O(E).
Funding Disclosure.
Devin Kreuzer is supported by an NSERC grant.

title: Rethinking Graph Transformers with Spectral Attention


summaries: This paper studies a setting that combines social choice and information aggregation.  As in a classic social choice problem, individuals with preferences want to choose between two options, but as in an information aggregation setting they do not have the knowledge to know exactly what their preferences are, instead having only a signal correlated with the true state of the world.  The paper introduces a “Wisdom-of-the-Crowd-Voting” Mechanism, which implements the majority wish in an (approximate) strong Bayes Nash equilibrium.

summaries: The authors consider elections that have two alternatives and three distinct classes of voters: candidate-friendly, candidate-unfriendly, and contingent agents. Candidate-friendly and candidate-unfriendly agents have made up their minds before the election, but each contingent voter's opinion depends on an unobservable state variable; they each receive a private signal about this state variable. The authors present a mechanism that elicits private signals from voters and which outputs the correct answer based on the state of the world. This mechanism is also strategyproof against even coalitions in the sense that truthful reporting is a strong Bayes Nash equilibrium. The mechanism draws on the "surprisingly popular" method of Prelec et al.

summaries: The paper considers two alternative elections in which the voters are imperfectly informed. There is an unobservable state that may affect some voters’ preferences. Each voter receives a signal correlated with the state. The voter’s signals are conditionally independent and follow the same publicly known distribution. The designer’s goal is to elicit truthful information and aggregate the information to find the alternative that is preferred by the majority. The paper proposes a mechanism that guarantees truthful reporting is an approximate strong BNE and outputs the right alternative with high probability.

summaries: This paper considers the two-alternative voting problem with imperfectly informed voters. In this setting, each voter receives a signal which is positively correlated to voter's true preferences (over two alternatives). The goal is to aggregate these signals to find out the majority voting winner w.h.p. Specifically, the paper gives a mechanism such that  1) the mechanism will output the majority voting winner under the true preferences w.h.p.  2) the mechanism incentives every voter to truthfully report the signal they received.  The main technical contribution of this work is that their mechanism uses the idea of "surprisingly popular" approach (Prelec et al., 2017)  from the information aggregation literature. They show that "surprisingly popular" approach can be well adapted to two-alternative social choice setting and can incentivize voters to report truthfully (for two-alternative). In addition, they show their mechanism is user-friendly, and does not require voters to understand deep mathematics.

abstractText: We consider two-alternative elections where voters’ preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. Voters may be “contingent" with different preferences in different states; or predetermined with the same preference in every state. In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased. We present an easy-to-deploy mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome).

authors:
David Austen-Smith
Jeffrey S. Banks

title: Information aggregation, rationality, and the condorcet jury theorem

venue: American political science review,

title: On the Rationale of Group Decision-making

venue: Journal of political economy,

authors:
Kay-Yut Chen
Leslie R Fine
Bernardo A Huberman

title: Eliminating public knowledge biases in information-aggregation mechanisms

venue: Management Science,

authors:
Yiling Chen
Chara Podimata
Ariel D Procaccia
Nisarg Shah

title: Strategyproof linear regression in high dimensions

venue: In Proceedings of the 2018 ACM Conference on Economics and Computation,

authors:
Anirban Dasgupta
Arpita Ghosh

title: Crowdsourced judgement elicitation with endogenous proficiency

venue: In Proceedings of the 22nd international conference on World Wide Web,

authors:
Ofer Dekel
Felix Fischer
Ariel D Procaccia

title: Incentive compatible regression learning

venue: Journal of Computer and System Sciences,

authors:
Boi Faltings
Goran Radanovic

title: Game theory for data science: Eliciting truthful information

venue: Synthesis Lectures on Artificial Intelligence and Machine Learning,

authors:
Timothy Feddersen
Wolfgang Pesendorfer

title: Voting behavior and information aggregation in elections with private information

authors:
A. Gao
J.R. Wright
K. Leyton-Brown

title: Incentivizing Evaluation via Limited Access to Ground Truth: Peer-Prediction Makes Things Worse

title: Tapping into the wisdom of the crowd—with

venue: confidence. Science,

authors:
Hadi Hosseini
Debmalya Mandal
Nisarg Shah
Kevin Shi

title: Surprisingly popular voting recovers rankings, surprisingly

venue: In Proceedings of the International Joint Conference on Artificial Intelligence (forthcoming),

title: Stability in Competition

venue: The Economic Journal,

authors:
Leslie K John
George Loewenstein
Drazen Prelec

title: Measuring the prevalence of questionable research practices with incentives for truth telling

venue: Psychological science,

title: Dominantly truthful multi-task peer prediction with a constant number of tasks

venue: In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA),

authors:
Yuqing Kong
Grant Schoenebeck

title: Equilibrium selection in information elicitation without verification via information monotonicity

venue: In Proceedings of the 9th Innovations in Theoretical Computer Science (ITCS

title: Eliciting expertise without verification

venue: In Proceedings of the 2018 ACM Conference on Economics and Computation (EC),

title: A Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling

venue: ACM Transactions on Economics and Computation (TEAC),

authors:
Yuqing Kong
Grant Schoenebeck
Biaoshuai Tao
Fang-Yi Yu

title: Information elicitation mechanisms for statistical estimation

title: The Condorcet Jury Theorem, Free Speech, and Correlated Votes

venue: American Journal of Political Science,

title: Information, Electorates, and Democracy: some Extensions and Interpretations of the Condorcet Jury Theorem

venue: Information Pooling and Group Decision Making,

authors:
N. Miller
P. Resnick
R. Zeckhauser

title: Eliciting informative feedback: The peer-prediction method

authors:
Shmuel Nitzan
Jacob Paroush

title: Collective decision making and jury theorems

venue: The Oxford Handbook of Law and Economics,

authors:
Javier Perote
Juan Perote-Pena

title: Strategy-proof estimators for simple regression

venue: Mathematical Social Sciences,

title: A Bayesian Truth Serum for subjective data

authors:
Dražen Prelec
H Sebastian Seung
John McCoy

title: A solution to the single-question crowd wisdom

venue: problem. Nature,

authors:
Grant Schoenebeck
Fang-Yi Yu

title: Two strongly truthful mechanisms for three heterogeneous agents answering one question

venue: In Web and Internet Economics,

title: Learning and strongly truthful multi-task setting peer prediction: A variational approach

venue: In Proceedings of the 12th Innovations in Theoretical Computer Science (ITCS

authors:
Victor Shnayder
Arpit Agarwal
Rafael Frongillo
David C Parkes

title: Informed truthfulness in multi-task peer prediction

venue: In Proceedings of the 2016 ACM Conference on Economics and Computation,

authors:
Joseph P Simmons
Leif D Nelson
Jeff Galak
Shane Frederick

title: Intuitive biases in choice versus estimation: Implications for the wisdom of crowds

venue: Journal of Consumer Research,

title: Condorcet’s Theory of Voting

venue: American Political Science,

authors:
Peter Zhang
Yiling Chen

title: Elicitability and knowledge-free elicitation with peer prediction

venue: In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems,

heading: 1 Introduction

text:
Social choice theory studies how to aggregate participants’ heterogeneous opinions/preferences and output a collective decision from a set of alternatives. Typically, though not always, it is assumed that each participant has a clear preference over the alternatives, e.g., a preference order over all the alternatives, a valuation for each alternative, etc. However, even with only two alternatives, this is not the typical case for all participants. In addition to the participants who have clear, predetermined preferences for one alternative over the other, typically there are also contingent participants who only have partial information on which alternative is “preferable for them” and yet would like to select the alternative that is “preferable for them.”
A standard example would be an election with two candidates a and b coming from political parties A and B respectively. Voters are normally partitioned into three types: some partisans for Party A prefer candidate a based on his support for the platform of party A; other partisans for Party B prefer candidate b based on her support for the platform of party B; finally, there are swing voters who are largely indifferent between the parties’ platforms and would like to elect whichever candidate can make more progress on non-partisan issues. However, swing voters do not have perfect information about which candidate is better suited for addressing the non-partisan needs of the community. Instead, each voter has a hunch of which candidate will perform better on the non-partisan problems facing the community based on both public information and their private experiences and beliefs.
Additional examples where participants have preferences, but may or may not know what is “preferable for them”, abound. In votes for corporate strategies, for hiring decisions, and for policy decisions typically some participants would like to select according to some truth they are collectively trying to
A full version of this paper is available at https://arxiv.org/abs/2108.03749. This material is based upon work supported by the National Science Foundation under Grant No. 2007256.
∗corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
discern (e.g., impact on future profits, suitability for the position, efficacy of policy, etc.) while others may have predetermined preferences, for example, because of the way they are uniquely affected (e.g., prominence of their position in future corporate strategy, vision/skills of the job candidate, who in particular the policy benefits/harms).

heading: 1.1 Informal Setting

text:
In this paper, we consider a two-alternative social choice setting where voters’ preferences may depend on a state variable. In the above example, the state is which candidate will make more progress on non-partisan issues.
We consider binary state variables in the main body of this paper. In general, the state need not be binary. For example, we could generalize the above example so which candidate would preform better on non-partisan issues is on a scale of 1 to 10 (where 1 indicates candidate a is much better and 10 indicates candidate b is much better). Predetermined voters’ preferences would still not depend on the state. However, contingent voters’ may have different thresholds on the state where they would transfer their support from candidate a to candidate b. In Appendix E, we discuss the non-binary setting and extend our results to this setting.
The state variable is not directly observable in the election phase, as the performance of a new government official, a new hired employee, a new policy, etc., may not be revealed until many years after the vote. Instead, each voter receives a signal that is correlated to the hidden state which models the information voters received from difference sources.
Our goal is to select the majority wish, the alternative that would be preferred by the majority if they knew the state of the world. If some type of predetermined voters forms a majority, this is rather easy. However, in the case where the predetermined voters of neither alternative forms a majority, the mechanism needs to aggregate the information and preferences of the contingent voters and selects the alternative which, for a majority of voters, is “preferable for them”.

heading: 1.2 Imperfectly Informed Voters

text:
Social Choice Social choice theory with imperfectly informed voters dates back to Condorcet’s jury theorem in 1785 [De Condorcet, 1785], and has also been widely studied [Miller, 1986, Young, 1988, Ladha, 1992, Nitzan and Paroush, 2017]. In Condorcet’s setting, there are two alternatives, one of which is “correct”, and each voter votes for the correct alternative with probability p. Condorcet’s jury theorem states that the probability that the majority voting scheme outputs the correct alternative goes to 1 as the number of voters increases when p > 0.5, and, conversely, this probability goes to 0 when p < 0.5.
Two unfortunate limitations for Condorcet’s jury theorem are 1) It fails to output the correct alternative in the case voters’ beliefs are aligned to the incorrect alternative (i.e., p < 0.5), and 2) It assumes voters vote truthfully and disregards voters’ potential strategic behaviors. However, even in the case all voters have the same preference for the correct alternative, voting truthfully still may not be a Nash equilibrium [Austen-Smith and Banks, 1996].
To circumvent the first limitation, Feddersen and Pesendorfer [1997] consider the scenario where voters play a Nash equilibrium strategy profile, while the voting rule is still the majority scheme. Feddersen and Pesendorfer [1997] show that when the number of voters tends to infinity, the probability that a majority voting scheme outputs the correct alternative approaches to 1 if voters play the equilibrium strategy profile, while this probability is bounded away from 1 if voters play the truthful strategy profile instead. Feddersen and Pesendorfer’s model assigns each voter a preference parameter x ∈ [−1, 1] describing his/her alignment to the two alternatives. In their model, the unique (Bayes) Nash equilibrium is characterized by two thresholds x0, x1 ∈ [−1, 1] with x0 < x1 such that voters with preferences below x0 always vote for one alternative, voters with preferences above x1 always vote for the other, and voters with preferences between x0 and x1 vote truthfully. Although Feddersen and Pesendorfer’s solution guarantees that the correct alternative is output with high probability, it requires sophisticated voters. The voters need to calculate the values of x0 and x1 to decide their actions. The values x0 and x1 are each the zero point of a continuous monotone function involving a complicated Riemann integral. This is usually too demanding for voters in practice,
especially those who do not have a mathematical background. Moreover, it needs to be common knowledge that all agents can and will perform this computation.
In this paper, we take a different approach. Instead of asking voters to play the Nash equilibrium for majority voting, we seek to design a more sophisticated voting scheme, or a mechanism, than the majority voting scheme, such that voters are incentivized to vote truthfully under the mechanism, while guaranteeing the correct alternative is output with high probability. Our social choice mechanism thus elicits truthful information from the voters and then aggregates it.
Information Aggregation The information aggregation literature considers how to obtain a “correct answer” by aggregating individuals’ partial information—the crowd’s wisdom. The straightforward procedure of outputting the answer that is believed to be correct by the majority does not always work [Chen et al., 2004, Simmons et al., 2011]. An example where this fails is when the crowd has a strong prior belief for the incorrect answer while novel specialized knowledge is only shared among a minority of the agents. It is also known that further calibration based on collecting participants’ confidences (the posterior of their beliefs) does not always solve this problem [Hertwig, 2012, Prelec et al., 2017]. In a seminal work by Prelec et al. [2017], a new “surprisingly popular” approach was proposed: the participants’ predictions over the other remaining participants’ reported answers are collected, and the answer that is reported by more participants than predicted is output (we will review this in Section 3.1). They justified this approach both theoretically and through experimentation. In particular, they demonstrate the viability of approaches that require agents to predict reports of the other agents. Hosseini et al. [2021] empirically extend the surprisingly popular approach to the non-binary setting, where the goal is to learn the correct ranking over many options instead of the correct answer in two options.
The work by Prelec et al. [2017] and Hosseini et al. [2021] does not fit into the social choice context in two aspects. Firstly, the objective for an information aggregation mechanism is to output the correct answer. Participants who collaboratively contribute their knowledge/information do not have preferences on which answer is finally selected. This is fundamentally different from the social choice setting where the whole point of a social choice mechanism is to select an alternative favored by the majority. Secondly, as agents care about the outcome, agents may be strategic and manipulate their reports in order to make their preferred alternatives win, while Prelec et al. [2017] and Hosseini et al. [2021] do not put the problem in a game theory setting.

heading: 1.3 Our Results

text:
In this paper, we study the social choice problem in a game theory setting with the existence of imperfectly informed voters who only have partial information regarding which alternative is more favorable. For various settings with two alternatives, we propose a mechanism that aggregates participants’ private information and outputs the alternative favored by more than half of the participants—the majority wish. Our mechanisms are truthful, in the sense that the truthful strategy profile forms a strong Bayes Nash Equilibrium.
Our main wisdom-of-the-crowd-voting mechanism, presented in the paper, applies to the case of two worlds/states, where each agent receives a binary signal. We show it has strong truthfulness and aggregation properties, even for relatively small numbers of agents (Section 3). This result requires that the distribution of agents is a common knowledge. In the full version, we show several additional results. First, the common knowledge assumption is necessary to attain a strongly truthful mechanism that outputs the majority wish with high probability (Appendix D). Additionally, we extend our results to the setting of more than two worlds (Appendix E.2). Finally, we show how to extend our results to the case of more than two signals (Appendix E.3).
Our mechanism can easily be implemented using a simple questionnaire that elicits voters’ information and preferences. The questions in the questionnaire are friendly to those voters who do not have relevant backgrounds in mathematics, game theory, etc., and they require participants to predict the responses of other agents, which is empirically validated by the surprisingly popular method from Prelec et al. [2017].
We ensure our mechanisms have a group truthfulness property by employing a “median trick.” Intuitively, by the Median Voter Theorem [Black, 1948, Hotelling, 1929], the median voter’s vote (in a binary choice) is favored by the majority. By a careful design, our mechanism ensures that
the voters who are “below” the median have a conflict of interest to the voters who are “above” the median, which makes sure less than half of the voters have an incentive to deviate and those voters can only change the outcome in the unfavorable direction by the property of median.
From a high level, our work can be understood as a revelation principal applied to plurality voting.4 However this view is not entirely accurate. First, our equilibrium concept is strong Bayes Nash equilibrium while we only know that plurality voting implements the majority wish outcome in (Bayesian) Nash equilibrium [Feddersen and Pesendorfer, 1997]. Second, the revelation principal requires that agents report all their knowledge. In our case, this would include the entire prior, which is not realistic. In contrast, our mechanisms only require that agents report a preference and a prediction of other agents’ preferences. Such reporting requirements have previously been shown to be pragmatic [John et al., 2012, Prelec et al., 2017, Hosseini et al., 2021]. Third, our setting is different than prior work [Feddersen and Pesendorfer, 1997], and this makes our results incomparable. In particular, we deal with a discrete state space. This difference also allows us to achieve some of our results not just in the limit, but for finite sets of agents.
Appendix A contains an additional comparison of our work with Feddersen and Pesendorfer [1997]’s.

heading: 1.4 Additional Related Work

text:
Our work is additionally related to the recent work on incentive compatible machine learning [Perote and Perote-Pena, 2004, Dekel et al., 2010, Chen et al., 2018]. In these settings, the “social choice" being made is a machine learning predictor where agents benefit from their point having small error with respect to the chosen predictor. As in our setting, the information of the optimal model is distributed among the agents. Unlike our model, the private information and the preferences of the agents essentially coincide.
Information elicitation without verification, sometimes call peer prediction, is another very related line of research which shares some of the intuitions and techniques from information aggregation. The information elicitation literature has been well established in the past decades, starting from Prelec [2004]’s Baysian Truth Serum and Miller et al. [2005]’s peer-prediction method. These mechanisms cleverly design payments to the agents to guarantee that the truthful reporting of received information forms a Nash equilibrium.
A mass of recent work (see Faltings and Radanovic [2017] for a survey) is dedicated to designing information elicitation mechanisms that work in more general settings (such as, supporting a small number of agents [Dasgupta and Ghosh, 2013, Zhang and Chen, 2014, Schoenebeck and Yu, 2020], allowing agents having information with different levels of sophistication [Gao et al., 2016, Kong and Schoenebeck, 2018b]), or achieving better truthful guarantees (such as, strict Nash equilibrium [Schoenebeck and Yu, 2021], informed Nash equilibrium [Shnayder et al., 2016], or even dominant strategy equilibrium [Kong and Schoenebeck, 2019, Kong, 2020]) sometimes by studying more restrictive settings (e.g. multiple similar questions being asked simultaneously [Dasgupta and Ghosh, 2013]). Indeed, following Bayesian Truth Serum, many of these mechanism require the agents to predict other agents’ reports [Zhang and Chen, 2014, Kong and Schoenebeck, 2018a,b, 2019, Kong et al., 2020, Schoenebeck and Yu, 2020].
However, all these mechanisms rely on payments to the agents to incentivize truth-telling. In our social choice setting, on the other hand, we need to incentivize truth-telling solely based on choosing the winning alternative.

heading: 2 Model and Preliminaries

text:
In this paper, we will define our model and present our main result with two states and two signals. The extension to general numbers of states and signals is discussed in Appendix E. We use the standard signal structure that is commonly used in the peer prediction (e.g., the work in Sect. 1.4), information aggregation (e.g., [Prelec et al., 2017]), and social choice literature (e.g., [Feddersen and Pesendorfer, 1997]).
4Loosely speaking, the revelation principal states that any outcome that can be implemented in equilibrium can also be truthfully implemented in equilibrium by having the mechanism play the equilibrium strategy on behalf of the truthful agents.
Suppose a department of T faculty members, or agents, need to decide whether or not to hire a new faculty candidate. In our model, those T agents are voting for two alternatives, A and R (corresponding to “accept” and “reject”). There is a set of 2 possible worlds (or states)W = {L,H}, which describes the underlying quality of the candidate. Here, L stands for “low quality”, and H stands for “high quality”. Agents do not know which world is the actual world that they are in. They have a common prior belief on the likelihood of each world. In the candidate hiring example, the CV of the candidate is given to those T faculty members before any individual interviews, and a prior belief is formed. Let W be the actual world which is viewed as a random variable. We use W = L and W = H to denote the events that the actual world is L and H respectively. Let (PL, PH) = (Pr(W = L),Pr(W = H)) be the prior over worlds. Each agent knows the values of PL and PH as prior beliefs. We further assume PL, PH > 0.
An individual interview for this candidate is held for each of the T agents. Each agent t receives a signal, represented by the random variable St, from the set S = {`, h}. Given W = L or W = H , the signals agents receive have the same distribution and are conditionally independent. Let P`L = Pr(St = ` | W = L) be the probability that signal ` will be received (by an arbitrary agent t) if the actual world is L. Let PhL, P`H and PhH have similar meanings. The set of values {P`L, P`H , PhL, PhH} is known by all the agents, but not the mechanism (such mechanisms are called detail-free in the peer prediction literature). Naturally, signals are positively correlated to the worlds:
P`L > P`H and PhH > PhL. (1)
Different agents may have different bars on the quality of the candidate. For example, if a theory candidate is interviewed in a computer science department, the theory faculty members may want to accept this candidate at a lower quality compared with the AI, software and hardware faculty members. To capture this, each agent t is assigned a utility function vt :W×{A,R} → {0, 1, . . . , B}. Naturally, voters receive higher utilities for A in world H and for R in world L:
vt(H,A) > vt(L,A) and vt(H,R) < vt(L,R). (2) Since we can always rescale agents’ utilities, for simplicity, we assume without loss of generality that agents’ utilities are integers and bounded by B ∈ Z+. Endowed with their prior beliefs, upon receiving their signals, agents will have posterior beliefs about the distribution of W and react to the mechanism in a way maximizing their expected utilities accordingly.
We assume vt(L,A) 6= vt(L,R) and vt(H,A) 6= vt(H,R) for each agent t, so that agents always strictly prefer one alternative over the other. Let F be the set of the candidate-friendly agents t who always prefer A: vt(H,A) > vt(L,A) > vt(L,R) > vt(H,R). Let U be the set of the candidateunfriendly agents t who always prefer R: vt(L,R) > vt(H,R) > vt(H,A) > vt(L,A). Let C be the set of the contingent agents t whose preference depends on the actual world: vt(L,R) > vt(L,A) and vt(H,A) > vt(H,R).
Let αF = |F | |T | , αU = |U | |T | and αC = |C| |T | be the fractions of the three types of agents. Since the numbers of theory, AI, software, hardware faculty members are known to everyone, we assume that the values of αF , αU and αC are common knowledge. Admittedly, this assumption may not apply to some specific scenarios. In Appendix D, we discuss the model where agents have only partial information on αF , αU and αC , and present a strong impossibility result for this model.
The goal is to output the majority wish, the alternative that is preferred by at least half of the agents conditioned on the true state. We assume T is an odd number to avoid ties. Clearly, A should be output if αF > 12 , R should be output if αU > 1 2 . In the case αF , αU < 1 2 , A should be output if the actual world is H and R should be output if the actual world is L.
Our results will sometimes require T , the number of agents, to be sufficiently large, and it may be helpful to think of T →∞. However, we will always assume that the parameters of the model: B, {PL, PH}, {P`L, P`H , PhL, PhH}, and {αF , αU , αC}, do not depend on T in any way. The traditional social choice setting with agents having predetermined preferences can be viewed as a special case of our model, by setting |C| = 0 (i.e., there is no contingent agent). For the ease of comprehension, we have used the faculty candidate hiring as a running example for this paper. This can be replaced by any example from most practical scenarios where different types of imperfectly informed voters are voting between two alternatives, including all the examples we mentioned in Section 1.
In our election example in the second paragraph of Section 1, A and R can represent candidates a and b respectively. Correspondingly, for this example, L and H can represent “a is better suited” and “b is better suited” respectively. F and U represent voters aligned to party A and B respectively, while C represents those swing voters whose preferences depend on the signals (in this case, the signals correspond to their private experiences and beliefs, which may be based on information they obtained from their favorite TV programs, newspapers, etc).

heading: 2.1 Strategy and ε-strong Bayes Nash equilibrium

text:
A mechanism collects a report from each agent, and then outputs an alternative which is either A or R. The mechanism specifies the content of the report by specifying questions for the agents. Examples of those questions include asking each agent for the signal he/she receives, asking each agent to predict the other agents’ reports, etc.
LetR be the space of all possible reports, which depends on the design of the mechanism. A pure strategy of an agent is given by a function σ : S → R that maps a signal received by this agent to a report. In a mixed strategy, σ can be a random function.
An agent’s strategy is truthful if it always specifies the correct answer to each question in the report, to the best of the agent’s knowledge after receiving the signal. For example, if the mechanism asks for the agent’s signal, an agent playing the truthful strategy should report the signal he/she receives; if the mechanism asks the agents to predict the fraction of agents who will receive signal m, an agent playing the truthful strategy should report his/her posterior belief on this computed by the Bayes rule (Section 2.2 discusses the computation of posterior beliefs).
Given a strategy profile Σ = (σ1, . . . , σT ), let ut(Σ) be the expected utility of agent t, where the expectation is taken over the sampling of agents’ signals. Notice that we use ut to denote the ex-ante utility (as defined just now) and we have used vt to denote the ex-post utility (see the fourth paragraph in Section 2). Most parts of this paper will focus on the ex-ante utility, especially when we are talking about any equilibrium solution concept.5
Since we are in a social choice setting with a potentially large number of agents, a single agent’s behavior may not have much effect. Thus, instead of the typical Bayes Nash Equilibrium, we consider a much stronger goal—the strong Bayes Nash equilibrium.
Definition 2.1. A strategy profile (σ1, . . . , σT ) is an ε-strong Bayes Nash equilibrium if there does not exist a subset of agents D and a strategy profile (σ′1, . . . , σ ′ T ) such that
1. σt = σ′t for each t /∈ D,
2. ut(σ′1, . . . , σ ′ T ) ≥ ut(σ1, . . . , σT ) for each t ∈ D, and
3. there exist t ∈ D such that ut(σ′1, . . . , σ′T ) > ut(σ1, . . . , σT ) + ε.
When a strategy profile (σ1, . . . , σn) is not an ε-strong Bayes Nash equilibrium, we will call the subset of the agents D in Definition 2.1 the deviating agents or the deviating coalition. By Definition 2.1, every agent of the deviating coalition must be at least as well off, and some must be strictly better off by at least . Notice that a 0-strong Bayes Nash equilibrium is the conventional strong Bayes Nash equilibrium. The larger ε is, the harder it is to find a deviating coalition, and so the larger the set of ε-strong Bayes Nash equilibria.

heading: 2.2 Posterior Update by Bayes Rule

text:
Upon receiving a signal St ∈ {`, h}, agent t updates his/her posterior beliefs (about the probability that (s)he is in world L or H , the fraction of agents that will receive signal ` or h, etc.) based on
5However, the goal of the mechanism is to output the majority preferred alternative based on agents’ ex-post utilities. Our choice of discussing ex-ante utilities in solution concept and ex-post utilities in the goal is motivated by practical applications. The underlying better alternative is unknown in the election phrase, so ex-ante utilities are considered for the solution concept. On the other hand, the ultimate goal is to select the alternative that turns out to be better after a certain period of time when the underlying better alternative is revealed (e.g., the performance of a selected president or the effect of a new policy in the next few years after the election), and in this case the ex-post utilities are considered.
Bayes rule. Let Tm′m be the probability that an agent who receives signal m ∈ {`, h} believes that another agent will receive signal m′ ∈ {`, h}. Straightforward calculations by Bayes rule (available in Appendix B.1) reveals
Tm′m = PLPmL
PLPmL + PHPmH · Pm′L + PHPmH PLPmL + PHPmH · Pm′H . (3)
Given a strategy profile Σ = {σ1, . . . , σT } and a mechanismM, let λA,Mn (Σ) be the probability that alternative A is announced as the winner given the actual world is n, then λR,Mn (Σ) = 1− λA,Mn (Σ) is the probability that alternative R wins given the actual world is n. We will omit the superscriptM when it is clear what mechanism we are discussing.
All the agents’ ex-ante utilities depend exclusively on λAL(Σ), λ A H(Σ) (or λ R L(Σ), λ R H(Σ)), and each agent t’s utility is given by
ut(Σ) = PL ( λAL(Σ)vt(L,A) + λ R L(Σ)vt(L,R) ) +PH ( λAH(Σ)vt(H,A) + λ R H(Σ)vt(H,R) ) , (4)
which can also be rewritten as (by noticing λAL(Σ) + λ R L(Σ) = 1 and λ A H(Σ) + λ R H(Σ) = 1)
ut(Σ) = PLvt(L,R) + PHvt(H,R) + PLλAL(Σ)(vt(L,A)− vt(L,R)) +PHλ A H(Σ)(vt(H,A)− vt(H,R)).
(5)
We will always use Σ∗ = {σ∗1 , . . . , σ∗T } to denote the truthful strategy profile.

heading: 3 The Wisdom-of-the-Crowd-Voting Mechanism

text: We will first review Prelec et al.’s Surprisingly Popular algorithm [Prelec et al., 2017], which works under a setting similar to ours but with non-strategic agents. Some part of the intuition behind our mechanism is based on Prelec et al.’s work.

heading: 3.1 Prelec et al.’s Surprisingly Popular Algorithm

text:
For the purpose of this paper, we will describe the algorithm with two worlds and two signals. The algorithm asks each agent t the signal (s)he receives, and his/her belief on the fraction of agents who have received signal ` (or signal h). In our notation, each agent reports the realization of St and, assuming St = m ∈ {`, h}, the value of T`m (or Thm, which equals to 1− T`m). Since agents are assumed to be non-strategic, those who receive signal ` will report (`, T``) and those who receive signal h will report (h, T`h). The algorithm then computes the fraction of agents who report signal `, and the average value of all the reported T`m’s. If the former is greater than the latter, ` is considered as being “surprisingly popular” and the algorithm will conclude that L is the actual world. Otherwise, h will be considered as being “surprisingly popular” and H will be concluded as being the actual world.
The correctness of this algorithm is based on the following simple yet important observation in Theorem 3.1. In particular, the average of agents’ reported predictions (those T`m’s) will be between T`h and T``. When the number of agents T is sufficiently large, the actual fraction of agents who receive signal ` will be either approximately P`L (if L is the actual world) or approximately P`H (if H is the actual world). Theorem 3.1 then implies the correctness of the Surprisingly Popular algorithm. Theorem 3.1. P`H < T`h < T`` < P`L and PhH > Thh > Th` > PhL
For completeness, the full proof is appears in Appendix B.2, but the intuition is straightforward. The inequality P`H < P`L is by the positive correlation (1). The inequality T`h < T`` is also intuitive: the positive correlation between the signals and worlds implies the positive correlation between two agents’ received signals. Finally, (3) implies each of T`h and T`` is a weighted average of P`H and P`L, so the value is between P`H and P`L. This concludes the first inequality chain, and the second can be shown similarly.
Throughout this section, we use c to denote the following constant, which is used in the Chernoff bounds in our proofs.
c = 1
3 min {T`h − P`H , T`` − T`h, P`L − T``, PhH − Thh, Thh − T`h, T`h − P`H} (6)

heading: 3.2 The Wisdom-of-the-Crowd-Voting Mechanism

text:
Mechanism 1 The Wisdom-of-the-Crowd-Voting Mechanism 1: Each agent t reports his/her type (F , U or C) to the mechanism, and if he/she is of type C, the
signal (s)he receives (either ` or h), denoted by s̄i ∈ {`, h}. 2: If agent t reports type F , his reported signal will be automatically treated as s̄t = h; if agent t
reports type U , his reported signal will be automatically treated as s̄t = `. 3: For each agent t of type C, ask him/her to predict the fraction of agents who will report signal h.
Let δ̄t be t’s prediction. The prediction δ̄t should be made with the type F and type C agents’ predictions defined in the previous step being considered, and the mechanism makes this clear to the agents. For each agent t of type F , δ̄t is set to 0, and for each agent t of type U , δ̄t is set to 1. 4: Compute the median of those δ̄t, denoted by δ̄. 5: If more than half of the agents report type F , announce A being the winning alternative; if more
than half of the agents reports type U , announce R being the winning alternative. 6: If the fraction of the agents reporting s̄t = h is more than the median δ̄, announce A being the
winning alternative; otherwise, announce R being the winning alternative.
At Step 3 of the mechanism, we only elicit predictions from those contingent agents, and those candidate-friendly (candidate-unfriendly resp.) agents’ predictions are treated as 0 (1 resp.). In Appendix C, we discuss an alternative mechanism where we elicit all the predictions and then take the median. The alternative mechanism shares the same theoretical properties, and we discuss the advantages and disadvantages of this alternative.
Mechanism 1 may look too obscure to be implemented in practice. However, very simple and understandable questionnaires implementing the mechanism can be designed. In our running example of faculty candidate hiring, the questionnaire corresponding to our mechanism could look like:
1. Choose one of the followings: (a) I definitely want to accept this candidate, regardless of my colleagues’ inputs. (b) I definitely want to reject this candidate, regardless of my colleagues’ inputs. (c) After talking to the candidate, I am more inclined to accept him/her than before. (d) After talking to the candidate, I am more inclined to reject him/her than before.
2. If your answer is (c) or (d) in the first question, what percentage of the faculty members do you believe will choose (a) or (c) in the first question?
In the first question above, faculty members of type F (type U resp.) will choose (a) ((b) resp.). Faculty members of type C will choose either (c) or (d) depending on the signals they have received. If a faculty member receives signal h, (s)he believes world H is more likely than before. Notice that, it is still possible that (s)he believes the probability of world H being the actual world is less than 50% and (s)he still prefers rejecting the candidate based on his/her private information (for example, his/her prior belief may be only 10% for world H , and his/her posterior belief for this increases to 30% upon receiving a signal h), so the description that (s)he is “more inclined to accept the candidate than before” accurately implements Mechanism 1. The same holds for those receiving signal `.

heading: 3.3 Main Theoretical Results for Our Mechanism

text:
We first show that our mechanism indeed achieves (with an exponentially small failure probability) the goal of outputting the alternative favored by the majority, assuming agents are truth-telling. Theorem 3.2. If all the agents play the truthful strategy Σ∗, then, with probability at least 1 − 2 exp(−2c2αCT ) (where c is the constant defined in Eqn. (6)), our mechanism outputs an alternative that is favored by more than half of the agents.
Proof. Suppose all the agents report truthfully. Step 5 of the mechanism guarantees that the majority wish will be announced with probability 1 if either αF > 0.5 or αU > 0.5. It remains to consider the case where we have both αF < 0.5 and αU < 0.5.6 In this case, A is favored by the majority if the actual world is H , and R is favored by the majority if the actual world is L.
6Recall that we have assume T is an odd number, so we cannot have αF = 0.5 or αU = 0.5.
If a contingent agent t receives signal h, (s)he will believe that a Thh fraction of agents receive h (before the treatment at Step 2), and (s)he will report δ̄t = αCThh + αF (after considering the treatment at Step 2). Similarly, a contingent agent receiving signal `will report δ̄t = αCTh`+αF . We have δ̄t = 0 for each candidate-friendly agent and δ̄t = 1 for each candidate-unfriendly agent. Since we are considering the case αF , αU < 0.5, the median δ̄ is in the interval [αCTh`+αF , αCThh+αF ] (note that Th` < Thh by Theorem 3.1).
Suppose the actual world is L. The expected fraction of the agents receiving signal h would be PhL, and the expected fraction of the agents reporting signal h (after the treatment at Step 2) would be αC · PhL + αF . By a Chernoff bound, with probability at least 1− 2 exp(−2c2αCT ), the fraction of agents reporting signal h is in the interval [αC · (PhL − c) + αF , αC · (PhL + c) + αF ], which is less than αC · Th` + αF ≤ δ̄ by Theorem 3.1 and (6). Step 6 of the mechanism indicates that R will be announced. The analysis for the case where H is the actual world is similar.
Next, we show that the truthful strategy profile is an ε-strong Bayes Nash equilibrium of our mechanism for some exponentially small ε. Theorem 3.3. The truthful strategy profile is an ε-strong Bayes Nash equilibrium, where ε = (2B2 + 4B) exp(−2c2αCT ).

heading: 3.4 Proof Theorem 3.3 with T →∞

text:
We defer the full proof of Theorem 3.3 to Appendix B.3. Here we prove the following limit version, where T →∞, which illustrates the key features while eliminating the need for both Chernoff bound analyses and for some additional subtle corner cases. Theorem 3.4. For T →∞, the truthful strategy profile is a strong Bayes Nash equilibrium.
We consider three cases: 1) αF > 0.5, 2) αU > 0.5 and 3) αF < 0.5 and αU < 0.5.
In the first case, more than half of the agents are candidate-friendly, and A will be announced according to Step 5 of the mechanism if these agents report truthfully. The truthful strategy profile forms a strong Bayes Nash equilibrium, as those candidate-friendly agents receive their maximum utilities by truth-telling and the remaining agents are not able to stop the mechanism from outputting A regardless of what they report. The analysis for the second case is the analogous to the first case. It remains to consider the third case.
Under the third case, A is favored by the majority if the actual world is H , and R is favored by the majority if the actual world is L. By the same analysis as in the proof of Theorem 3.2, supposing agents report truthfully, we know that A will be output with probability 1 (by taking the limit T →∞) if the actual world isH , and R will be output if the actual world is L. Therefore, the contingent agents (type C) receive their maximum utilities, and thus have no incentive to deviate from the truthful strategy.
To conclude that truth-telling is a strong Bayes Nash equilibrium, we will show that there is no coalition of deviating agents D (see the paragraph following Definition 2.1). Let Σ′ be the strategy profile after D’s deviation.
Next, we show that D cannot contain both a type F agent and a type U agent. The following lemma shows that an increase in a type F agent’s (ex-ante) utility always results a decrease in a type U agent’s (ex-ante) utility, and vice versa. This is obvious if we are dealing with ex-post utilities, as a candidate-friendly agent and a candidate-unfriendly agent always want the opposite alternatives. However, this becomes less obvious for ex-ante utilities. Lemma 3.5. Suppose αF < 0.5 and αU < 0.5. Let Σ∗ be the truthful strategy profile and Σ′ be an arbitrary strategy profile. Let t1 be an arbitrary candidate-friendly agent and t2 be an arbitrary candidate-unfriendly agent. We have
(i) If ut1(Σ′)− ut1(Σ∗) > 0, then ut2(Σ′)− ut2(Σ∗) < 0.
(ii) If ut2(Σ′)− ut2(Σ∗) > 0, then ut1(Σ′)− ut1(Σ∗) < 0.
Proof. By (5), we have
ut(Σ ′)− ut(Σ∗) = ΓL(vt(L,A)− vt(L,R))− ΓH(vt(H,A)− vt(H,R)),
where ΓL = PL(λAL(Σ ′) − λAL(Σ∗)) and ΓH = PH(λAH(Σ∗) − λAH(Σ′)). Theorem 3.2 implies λAL(Σ ∗) = 0 and λAH(Σ
∗) = 1 (with T → ∞), which implies ΓL,ΓH ≥ 0. By (2), we have vt(L,A) − vt(H,A) < 0 < vt(L,R) − vt(H,R), which further implies vt(L,A) − vt(L,R) < vt(H,A)− vt(H,R). Since a type F agent always prefers A and a type U agent always prefers R,
0 < vt1(L,A)− vt1(L,R) < vt1(H,A)− vt1(H,R), and vt2(L,A)− vt2(L,R) < vt2(H,A)− vt2(H,R) < 0.
Intuitively, this means ut1(Σ ′) − ut1(Σ∗) is more sensitive to ΓH and ut2(Σ′) − ut2(Σ∗) is more sensitively to ΓL. Formally, ut1(Σ ′)− ut1(Σ∗) > 0 implies ΓL > ΓH
vt1 (H,A)−vt1 (H,R) vt1 (L,A)−vt1 (L,R) ≥ ΓH , and
ut2(Σ ′) − ut2(Σ∗) ≥ 0 implies ΓL ≤ ΓH vt2 (H,A)−vt2 (H,R) vt2 (L,A)−vt2 (L,R) ≤ ΓH . Thus, ut1(Σ′) − ut1(Σ∗) > 0 and ut2(Σ ′)− ut2(Σ∗) ≥ 0 cannot be both true. The proof for (ii) is similar.
We have seen that the deviating coalition D cannot contain any contingent agents (since their ex-ante utilities have already been maximized). Thus, Lemma 3.5 implies D can only be comprised of either candidate-friendly agents or candidate-unfriendly agents. Finally, we show that a minority coalition comprised of only candidate-friendly agents or only candidate-unfriendly agents cannot change the outcome by misreporting. We consider candidate-friendly agents without loss of generality.
Suppose D contains only candidate-friendly agents. Those agents cannot make the mechanism output A at Step 5, because fewer than 1/2 of the agents report type F no matter how agents in D deviate. To maximize the chance for the mechanism to output A at Step 6, those candidate-friendly agents would like to maximize the fraction of agents reporting h and minimize the median of the prediction δ̄. However, the mechanism already does this when those candidate-friendly agents play the truthful strategy: their signals are treated as h at Step 2, and their predictions are treated as 0 at Step 3. The same analysis works when D contains only candidate-unfriendly agents. This concludes the proof for Theorem 3.4.
In fact, the arguments in the previous paragraph show that: truth-telling is a dominant strategy for each candidate-friendly agent and each candidate-unfriendly agent.

heading: 4 Remarks, Limitations and Future Work

text:
We have assumed agents are Bayesian. Although this assumption may not be completely realistic in practice, we believe the theoretical properties of our mechanism still hold to a certain extent. For example, agents may not exactly predict αCThh +αF or αCTh` +αF in practice, but it is reasonable to assume that their predictions are roughly around these two numbers, or in between. If so, all the theoretical properties will still hold. Prelec et al. [2017] also assume Bayesian agents in the theoretical analysis of the surprisingly popular method, but their empirical experiments with human subjects suggest the method still works in practice.
Our mechanism can be extended to the setting where a fixed fraction τ of acceptance votes is required to adopt a policy. For example, in many countries, constitutional amendments requires a 2/3 majority to pass. To do this, we only need to change Step 4 of Mechanism 1 such that δ̄ is the prediction with rank τT , and change Step 5 such that A is announced if more than τ fraction of agents report type F and R is announced if more than 1− τ fraction of agents report type U . One limitation is that our mechanism only deals with two alternatives. While this is natural in many scenarios (accept/reject, election with two candidates), extending our results to more than two alternatives is an interesting future direction, but faces a multitude of hurdles: the median technique will not straightforwardly work, the “surprisingly popular" formalism faces impossibility results [Prelec et al., 2017], and Gibbard-Satterthwaite social choice impossibility results apply.
Another interesting future direction is deployment. Our Wisdom-of-the-Crowd-Voting mechanism could be used in any place that currently uses majority voting to better aggregate information. Of course, it would suffer from some of the same drawbacks of majority voting: that the majority can impose their will on the minority. It is not clear if either one of these enjoys fairness properties not included by the other, but that would be another direction of future inquiry. It would be interesting to test this mechanism in the real world, and then test to see if participants are, in aggregate, more pleased with the alternatives selected by this mechanism as compared with those selected by a majority vote.

heading: Acknowledgement

text:
We gratefully thank Noah Burrell and the anonymous reviewers for the helpful comments and suggestions for improving this paper.
Funding Transparency Statement
All the funding support related to this paper has been declared at the bottom of Page 1.

title: Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences