\section{Conclusion}

We propose a probabilistic model for diffeomorphic image registration and derive a learning algorithm that makes use of a convolutional neural network and an intuitive resulting loss function. To achieve unsupervised, end-to-end learning for diffeomorphic registrations, we introduce novel \textit{scaling and squaring} differentiable layers. Our derivation is generalizable. For example,~$\bz$ can be a low dimensional embedding representation of a deformation field, or the displacement field itself.
Our algorithm can infer the registration of new image pairs in under a second. Compared to traditional methods, our method is significantly faster, and compared to recent learning based methods, our method offers diffeomorphic guarantees, and provides natural uncertainty estimates for resulting registrations.

\section{Acknowledgments}
This research was funded, in part, by NIH grants R01LM012719, R01AG053949, and 1R21AG050122, and NSF grant 1707312, the Cornell NeuroNex Hub.
\section{Introduction}
\label{sec:introduction}
\vspace{-0.3cm}

Deformable registration computes a dense correspondence between two images, and is fundamental to many medical image analysis tasks.

Traditional methods  solve an optimization over the space of deformations, such as elastic-type models~\cite{bajcsy1989,shen2002}, B splines~\cite{rueckert1999}, dense vector fields~\cite{thirion1998}, or discrete methods~\cite{dalca2016,glocker2008}. Constraining the allowable transformations to diffeomorphisms ensures certain desirable properties, such as preservation of topology. Diffeomorphic transforms have seen extensive methodological development, yielding state-of-the-art tools, such as LDDMM~\cite{beg2005,zhang2017}, DARTEL~\cite{Ashburner07}, and SyN~\cite{Avants08}. Unfortunately, these methods often demand substantial time and computational resources to run for a given image pair.

Recent methods have proposed to train neural networks that map a pair of input images to an output deformation. These approaches usually require ground truth registration fields, often derived via more conventional registration tools, which can introduce a bias and necessitate significant preprocessing~\cite{rohe2017,sokooti2017,yang2017}. Some preliminary papers~\cite{devos2017,li2017} explore unsupervised strategies that build on the spatial transformer network~\cite{jaderberg2015}, but are only demonstrated with constrained deformation models such as affine or small displacement fields. Furthermore, they have only been validated on limited volumes, such as 3D patches or 2D slices.
A recent paper avoids these pitfalls, but still does not provide topology-preserving guarantees or probabilistic uncertainty estimates, which yield meaningful information for downstream image analysis~\cite{balakrishnan2018}.

In this paper we present a formulation for registration as conducting variational inference on a probabilistic generative model. This framework naturally results in a learning algorithm that uses a convolutional neural network with an intuitive cost function.  We introduce novel
\textit{diffeomorphic integration} layers combined with a transform layer to enable unsupervised end-to-end learning for diffeomorphic registration. We present extensive experiments, demonstrating that our algorithm achieves state of the art registration accuracy while providing diffeomorphic deformations, fast runtime and estimates of registration uncertainty.

\subsection{Diffeomorphic Registration}

Although the method presented in this paper applies to a multitude of deformable representations, we choose to work with diffeomorphisms, and in particular with a stationary velocity field representation~\cite{Ashburner07}.  Diffeomorphic deformations are differentiable and invertible, and thus preserve topology. Let $\bphi: R^3 \rightarrow R^3$ represent the deformation that maps the coordinates from one image to coordinates in another image.
In our implementation,  the deformation field is defined through the following ordinary differential equation (ODE):
\begin{equation}
\frac{\partial\bphi^{(t)}}{\partial t} = \bv(\bphi^{(t)})
\label{eq:ode}
\end{equation}
where $\bphi^{(0)} = Id$ is the identity transformation and~$t$ is time. We integrate  the stationary velocity field $\bv$ over $t=[0,1]$ to obtain the final registration field $\bphi^{(1)}$.

We compute the integration numerically using \emph{scaling and squaring}~\cite{arsigny2006}, which we briefly review here.
The integration of a stationary ODE represents a one-parameter subgroup of diffeomorphisms.  In group theory, $\bv$ is a member of the Lie algebra and is exponentiated to produce $\bphi^{(1)}$, which is a member of the Lie group: $\bphi^{(1)} =\text{exp}(\bv)$.
  From the properties of one-parameter subgroups, for any scalars $t$ and $t'$, \mbox{$\exp((t+t')\bv) = \exp(t\bv) \circ \exp(t'\bv)$}, where $\circ$ is a composition map associated with the Lie group.
Starting from~$\bphi^{(1/2^T)} =\bp + \bv(\bp)$ where~$\bp$ is a map of spatial locations, we use the recurrence~$\bphi^{(1/2^{t-1})} = \bphi^{(1/2^t)} \circ \bphi^{(1/2^t)}$ to obtain~$\bphi^{(1)} = \bphi^{(1/2)} \circ \bphi^{(1/2)}$. $T$ is chosen so that $\bv \approx 0$.

\section{Methods}
\label{sec:model}

Let~$\bmoving$ and~$\bfixed$ be 3D images, such as MRI volumes,
and let~$\bz$ be a latent variable that parametrizes a transformation function~$\bphi_{\bz}: R^3 \rightarrow R^3$. We use a generative model to describe the formation of~$\bmoving$ by warping~$\bfixed$ into~$\bfixed \circ \bphi_{\bz}$.
We propose a variational inference method that uses a neural network of convolutions, diffeomorphic integration, and spatial transform layers. We learn the network parameters in an unsupervised fashion, i.e., without access to ground truth registrations. We describe how the network yields fast diffeomorphic registration of a new image pair~$\bmoving$ and~$\bfixed$, while providing uncertainty estimates.

\vspace{-0.1cm}
\subsection{Generative Model}

We model the prior probability of~$\bz$ as:
\begin{align}
p(\bz) = \mathcal{N}(\bz; \boldsymbol{0}, \bSigma_z),
\end{align}
where~$\mathcal{N}(\cdot;\bmu,\bSigma)$ is the multivariate normal distribution with mean~$\bmu$ and covariance~$\bSigma$.
Our work applies to a wide range of representations~$\bz$. For example,~$\bz$ could be a low-dimensional embedding of a dense displacement field, or even the displacement field itself. In this paper, we let~$\bz$ be a stationary velocity field that specifies a diffeomorphism through the ODE~\eqref{eq:ode}. We let~$\bL = \bD - \bA$ be the Laplacian of a neighborhood graph defined on a voxel grid, where~$\bD$ is the graph degree matrix, and~$\bA$ is a voxel neighbourhood adjacency matrix. We encourage spatial smoothness of~$\bz$ by letting~$\bSigma_z^{-1} = \bLambda_z = \lambda \bL$, where~$\bLambda_z$ is a precision matrix and~$\lambda$ denotes a parameter controlling the scale of the velocity field~$\bz$.

We let~$\bmoving$ be a noisy observation of warped image~$\bfixed$:
\begin{align}
	p(\bmoving | \bz ; \bfixed) &= \mathcal{N}(\bmoving ; \bfixed \circ \bphi_{\bz}, \sigma^2\boldsymbol{\mathbbm{I}}),
	\label{eq:likelihood}
\end{align}
where~$\sigma^2$ reflects the variance of additive image noise.

We aim to estimate the posterior registration probability~$p(\bz|\bmoving;\bfixed)$. Using this, we can obtain the most likely registration field~$\bphi_{\bz}$ for a new image pair~$(\bmoving, \bfixed)$ via MAP estimation, along with an estimate of uncertainty for this registration.

\vspace{-0.1cm}
\subsection{Learning}

With our assumptions, computing the posterior probability~$p(\bz|\bmoving; \bfixed)$ is intractable. We use a variational approach, and introduce an approximate posterior probability~$q_{\bpsi}(\bz|\bmoving; \bfixed)$ parametrized by~$\bpsi$. We minimize the KL divergence
\begin{align}
\min_{\psi} \KL &\left[q_{\bpsi}(\bz|\bmoving ; \bfixed) || p(\bz|\bmoving ; \bfixed)  \right] \nonumber \\
&= \min_{\psi} \Expect_{q} \left[ \log q_{\bpsi}(\bz|\bmoving ; \bfixed) - \log p(\bz|\bmoving ; \bfixed) \right] \nonumber \\
&= \min_{\psi} \Expect_{q} \left[ \log q_{\bpsi}(\bz|\bmoving ; \bfixed) - \log p(\bz, \bmoving, \bfixed) \right] + \log p(\bmoving ; \bfixed) \nonumber \\
&= \min_{\psi} \KL \left[  q_{\bpsi}(\bz|\bmoving; \bfixed) ||  p(\bz)  \right] - \Expect_{q} \left[ \log p(\bmoving | \bz ; \bfixed) \right],
\label{eq:VLB}
\end{align}
which is the negative of the \textit{variational lower bound} of the model evidence~\cite{kingma2013}.
We model the approximate posterior~$q_{\bpsi}(\bz | \bmoving ; \bfixed)$ as a multivariate normal:
\begin{align}
q_{\bpsi}(\bz | \bmoving ; \bfixed) = \mathcal{N}(\bz ; \bmu_{z | \moving, \fixed}, \bSigma_{z |\moving, \fixed}),
\end{align}
where~$\bSigma_{z | \moving, \fixed}$ is diagonal.

We estimate~$\bmu_{z | \moving, \fixed}$, and~$\bSigma_{z | \moving, \fixed}$ using a convolutional neural network~$\text{def}_{\bpsi}(\bmoving,\bfixed)$ parameterized by~$\bpsi$, as described below.
We can therefore learn the parameters~$\bpsi$ by optimizing the variational lower bound~\eqref{eq:VLB} using stochastic gradient methods. Specifically, for each image pair~$\{\bmoving, \bfixed\}$ and samples~$\bz_k\sim q_{\psi}(\bz|\bmoving; \bfixed)$, we can compute~$\bfixed \circ \bphi_{z_k}$,
with the resulting loss:
\begin{align}
&\mathcal{L}(\bpsi; \bmoving, \bfixed) \nonumber\\
 &= - \Expect_{q} \left[ \log p(\bmoving | \bz ; \bfixed) \right] + \KL \left[  q_{\bpsi}(\bz|\bmoving; \bfixed) ||  p(\bz)  \right]  \label{eq:main_loss}\\
&= \frac{1}{2\sigma^2K} \sum_k ||\bmoving - \bfixed \circ \bphi_{z_k}||^2  + \frac{1}{2} \left[ \text{tr}(\lambda\bD \bSigma_{z|x;y} - \log|\bSigma_{z|x;y}|) + \bmu_{z | \moving, \fixed}^T \bLambda_z \bmu_{z | \moving, \fixed} \right] + \text{const}, \nonumber
\end{align}
where~$K$ is the number of samples used. In our experiments, we use~$K=1$.
The first term encourages the warped image~$\bfixed \circ \bphi_{z_k}$ to be similar to~$\bmoving$. The second term encourages the posterior to be close to the prior~$p(\bz)$. Although the variational covariance~$\bSigma_{z|\moving,\fixed}$ is diagonal, the last term spatially smoothes the mean:~$\bmu_{z | \moving, \fixed}^T \bLambda_z \bmu_{z | \moving, \fixed} = \frac{\lambda}{2} \sum \sum_{j\in N(I)} (\bmu[i] - \bmu[j])^2$, where
$N(i)$ are the neighbors of voxel~$i$.
We treat~$\sigma^2$ and~$\lambda$ as fixed hyper-parameters.

\vspace{-0.2cm}
\subsection{Neural Network Framework}
\vspace{-0.1cm}

\begin{figure}[t]
	\centering
	\begin{minipage}[t]{1\linewidth}
		\includegraphics[width=1\linewidth]{./figures/overview}
	\end{minipage}
	\hfill
	%
	\begin{minipage}[b]{1\linewidth}
		\caption{Overview of end-to-end unsupervised architecture. The first part of the network,~$\text{def}_{\psi}(\bmoving, \bfixed)$ takes the input images and outputs the approximate posterior probability parameters representing the velocity field mean,~$\bmu_{z|\moving;\fixed}$, and variance,~$\bSigma_{z|\moving;\fixed}$. A velocity field~$\bz$ is sampled and transformed to a diffeomorphic deformation field~$\bphi_z$ using novel differentiable \textit{squaring and scaling} layers. Finally, a spatial transform warps~$\bfixed$ to obtain~$\bfixed \circ \bphi_z$.
			}
		\label{fig:network_overview_simple}
	\end{minipage}
\end{figure}

We design the network~~$\text{def}_{\bpsi}(\bmoving,\bfixed)$ that takes as input~$\bmoving$ and~$\bfixed$ and outputs~$\bmu_{z|\moving,\fixed}$ and~$\bSigma_{z|\moving,\fixed}$, based on a 3D UNet-style architecture~\cite{ronneberger2015}.
The network includes a convolutional layer with 16 filters, four downsampling layers with 32 convolutional filters and a stride of two, and finally three upsampling convolutional layers with 32 filters. All convolutional layers use LeakyReLu activations and a 3x3 kernel.

To enable unsupervised learning of parameters~$\bpsi$ using~\eqref{eq:main_loss}, we must form~\mbox{$\by \circ \bphi_z$} to compute the data term. We first implement a layer that samples a new \mbox{$\bz_k \sim \mathcal{N}(\bmu_{z|\moving,\fixed}, \bSigma_{z|\moving,\fixed})$} using the ``re-parameterization trick"~\cite{kingma2013}.

We propose novel \emph{scaling and squaring} network layers to compute~\mbox{$\bphi_{z_k} = \exp(\bz_k)$}.

Specifically, these involve compositions within the neural network architecture using a differentiable spatial transformation operation. Given two 3D vector fields $\ba$ and $\bb$, for each voxel $p$ such a layer computes $(\ba \circ \bb)(p) = \ba(\bb(p))$, a non-integer voxel location $\bb(\bp)$ in $\ba$, using linear interpolation. Starting with~$\bv^{(1/2^T)} = \bz_k$, we compute~\mbox{$\bv^{(1/2^{t+1})} = \bv^{(1/2^t)} \circ \bv^{(1/2^t)}$} recursively using these layers, leading to~$\bv^{(1)} \triangleq \bphi_{z_k} = \exp(\bz_k)$. In our experiments, we use~$T=7$.

Finally, we use a spatial transform layer to warp volume~$\bfixed$ according to the computed diffeomorphic field~$\bphi_{z_k}$. This network results in three outputs,~$\bmu_{z|\moving,\fixed}, \bSigma_{z|\moving,\fixed}$ and~~$\by \circ \bphi_{z_k}$, which are used in the model loss~\eqref{eq:main_loss}.

In summary, the neural network takes as input~$\bmoving$ and~$\bfixed$, computes~$\bmu_{z|\moving,\fixed}$ and~$\bSigma_{z|\moving,\fixed}$, samples a new~$\bz_k \sim \mathcal{N}(\bmu_k, \bSigma_k)$, computes a diffeomorphic~$\bphi_{z_k}$ and applies it to~$\bfixed$. Since all the steps are designed to be differentiable, we  learn the network parameters using stochastic gradient descent based methods on the loss~\eqref{eq:main_loss}. The framework is summarized in Figure~\ref{fig:network_overview_simple}.

Our implementation uses Keras~\cite{chollet2015}
 with a Tensorflow backend~\cite{abadi2016}
 and the ADAM optimizer~\cite{kingma2014}.
 We implement our method as part of the VoxelMorph package, with both implementations available online at \url{https://github.com/voxelmorph/voxelmorph}.

\subsection{Registration and Uncertainty}

Given learned parameters, we approximate registration of a new scan pair~$(\bmoving, \bfixed)$ using~$\bphi_{\hat{z}_k}$. We first obtain~$\hat{\bz}_k$ using
\begin{align}
\hat{\bz}_k &= \arg \max_{\bz_k} p(\bz_k | \bmoving; \bfixed) = \bmu_{z|\moving;\fixed},
\label{eq:MAP1}
\end{align}
by evaluating the neural network~$\text{def}_\psi(\bmoving, \bfixed)$ on the two input images. We then compute~$\bphi_{\hat{z}_k}$ using the \textit{scaling and squaring} network layers.
We also obtain~$\bSigma_{z|\moving,\fixed}$, enabling an estimation of the uncertainty of the velocity field $\bz$ at each voxel~$j$:
\begin{align}
H(\bz[j]) &\approx \Expect \left[ -\log q_{\bpsi}(\bz|\bmoving,\bfixed) \right] = \frac{1}{2} \log 2 \pi \bSigma_{z|\moving;\fixed}[j,j].
\label{eq:uncertainty_z}
\end{align}
We also estimate uncertainty in the deformation field~$\bphi_z$ empirically. We sample several representations~$\bz_{k'} \sim q_{\psi}(\bz | \bmoving; \bfixed)$, propagate them through the diffeomorphic layers to compute~$\bphi_{z_k'}$, and compute the empirical diagonal covariance~$\hat{\bSigma}_{\bphi_z}[j,j]$ across samples. The uncertainty is then~$H(\bphi[j]) \approx \frac{1}{2} \log 2 \pi \hat{\bSigma}_{\phi_z}[j,j]$.

\section{Experiments}
\label{sec:results}

\begin{figure}[b!]
	\begin{center}
		\includegraphics[width=\linewidth]{figures/example.pdf}
	\end{center}
	\vspace{-0.5cm}
	\caption{ Example MR slices of input moving image, atlas, and resulting warped image for our method and ANTs, with overlaid boundaries of ventricles, thalami and hippocampi. Our resulting registration field is shown as a warped grid and RGB image, with each channel representing dimension. Due to space constraints, we omit VoxelMorph examples, which are \textit{visually} similar to our results and ANTs.}
	\label{fig:reg_examples}
\end{figure}

We focus on 3D atlas-based registration, a common task in population analysis. Specifically, we register each scan to an atlas computed using external data~\cite{fischl2012}.

\vspace{0.3cm}
\noindent \textbf{Data and Preprocessing.} We use a large-scale, multi-site dataset of 7829 T1-weighted brain MRI scans from eight publicly available datasets: ADNI~\cite{mueller2005ways}, OASIS~\cite{marcus2007open}, ABIDE~\cite{di2014autism}, ADHD200~\cite{milham2012adhd}, MCIC~\cite{gollub2013mcic}, PPMI~\cite{marek2011parkinson}, HABS~\cite{dagley2015harvard}, and Harvard GSP~\cite{holmes2015brain}. Acquisition details, subject age ranges and health conditions are different for each dataset. We performed standard pre-processing steps on all scans, including resampling to~$1$mm isotropic voxels, affine spatial normalization and brain extraction for each scan using FreeSurfer~\cite{fischl2012}. We crop the final images to $160\times 192 \times 224$. Segmentation maps including 29 anatomical structures, obtained using FreeSurfer for each scan, are used in evaluating registration results. We split the dataset into 7329, 250, and 250 volumes for train, validation, and test sets respectively, although we underscore that the training is unsupervised.

\begin{table}[t!]
	\small
	\centering
	\begin{tabular}{c c c c c c}
		Method&Avg. Dice&GPU sec&CPU sec & $|J_\Phi| \le 0$ & Uncertainty   \\
		\hline
		Affine only&0.567 (0.157)&0 &0  & 0 & No \\
		ANTs (SyN) &0.750 (0.135)&-&9059 (2023) & 6505 (3024) & No \\
		VoxelMorph & 0.750 (0.137)&0.554 (0.017) & 144 (1) & 18096 (4230) & No   \\
		\textbf{Ours} & \textbf{0.753} (0.137) & \textbf{0.451} (0.011)& \textbf{51} (0.2) & \textbf{0.7} (2.0) & \textbf{Yes}  \\
		\hline
	\end{tabular}
	\vspace{+0.2cm}

	\caption{ Summary of results: mean Dice scores over all anatomical structures and subjects (higher is better), mean runtime; and mean number of locations with a non-positive Jacobian of each registration field (lower is better). All methods have comparable Dice scores, while our method and the original VoxelMorph are orders of magnitude faster than ANTs. Only our method

		achieves both high accuracy and fast runtime while also having nearly zero non-negative Jacobian locations and providing uncertainty prediction.
		 	\vspace{-0.5cm}
		 	}
	\label{tbl:results}
\end{table}
\normalsize

	\vspace{0.1cm}\noindent \textbf{Evaluation Metric.}  To evaluate a registration algorithm, we register each subject to an atlas, propagate the segmentation map using the resulting warp, and measure volume overlap using the Dice metric. We also evaluate the diffeomorphic property, a focus of our model. Specifically, the Jacobian matrix \mbox{$J_{\phi}(p) = \nabla \bphi (p) \in \mathcal{R}^{3\times 3}$} captures the local properties of $\bphi$ around voxel $p$. The local deformation is diffeomorphic, both invertible and orientation-preserving, only at locations for which $|J_{\phi}(p)| > 0$~\cite{Ashburner07}.
	We count all other voxels, where~$|J_{\phi}(p)| \le 0$.

	\begin{figure*}[b!]
		\begin{center}
			\includegraphics[width=\linewidth]{figures/boxplots_ANTs_VoxelMorph_Ours.pdf}
		\end{center}
		\vspace{-0.4cm}
		\caption{Boxplots indicating Dice scores for anatomical structures for ANTs, VoxelMorph, and our algorithm.
	 Left and right hemisphere structures are merged for visualization, and ordered by average ANTs Dice score. We include the brain stem (BS), thalamus (Th), cerebellum cortex (CblmC), lateral ventricle (LV), cerebellum white matter (CblmWM), putamen (Pu), cerebral white matter (CeblWM), ventral DC (VDC), caudate (Ca), pallidum (Pa), hippocampus (Hi), 3rd ventricle (3V), 4th ventricle (4V), amygdala (Am), CSF (CSF), cerebral cortex (CeblC), and choroid plexus~(CP).
		}
		\label{fig:boxplot}
	\end{figure*}

	\vspace{0.2cm}\noindent \textbf{Baseline Methods.} We compare our approach with the popular ANTs software package using Symmetric Normalization (SyN)~\cite{Avants08}, a top-performing algorithm~\cite{klein2009}.  We found that the default ANTs settings were sub-optimal for our task, so we performed a wide parameter and similarity metric search across a multitude of datasets. We identified top performing parameter values on the Dice metric and used cross-correlation as the ANTs similarity measure. We also test our recent CNN-based method, VoxelMorph, which aims to produce fast registration but does not yield diffeomorphic results or uncertainty estimates~\cite{balakrishnan2018}. We sweep the regularization parameter using our validation set, and use the optimal parameters in our results.

	\vspace{0.2cm}\noindent \textbf{Results on Test set:} Figure~\ref{fig:reg_examples} shows  representative results.  Figure~\ref{fig:boxplot} illustrates Dice results on a range of anatomical structures, and Table~\ref{tbl:results} gives a summary of the results.  Not only does our algorithm achieve state of the art Dice results and the fastest runtimes, but it also produces diffeomorphic registration fields (having nearly no non-negative Jacobian voxels per scan) and yields uncertainty estimates.

	Specifically, all methods achieve comparable Dice results on each structure and overall. Our method and VoxelMorph require a fraction of the ANTs runtime to register two images: less than a second on a GPU, and less than a minute on a CPU (for our method). To the best of our knowledge, ANTs does not have a GPU implementation. Algorithm runtimes were computed for an NVIDIA TitanX GPU and a Intel Xeon (E5-2680) CPU, and exclude preprocessing common to all methods. Importantly, while our method achieves positive Jacobians at nearly all voxels, the flow fields resulting from the baseline methods contain a few thousand locations of non-positive Jacobians. This can be alleviated with increased spatial regularization, but this in turn leads to a drop in performance on the Dice metric.

\vspace{0.2cm}\noindent \textbf{Uncertainty.}	Figure~\ref{fig:uncertainty} shows representative uncertainty maps, unique to our model. The velocity field is more certain near anatomical structure edges, and less confident in homogenous scan regions, such as the white matter or ventricle interior.

\vspace{0.2cm}\noindent \textbf{Parameter Analysis.} We perform a grid search for the two fixed hyper-parameters~$\lambda$ and~$\sigma^2$. We train a model for each parameter pair and evaluate Dice on the validation set. We search 30 values within two orders of magnitude around meaningful initial values for both parameters:~$\sigma^2 \sim (0.07)^2$, the variance of the intensity difference between an \textit{affinely} aligned image and the atlas, and~$\lambda = 10000$, equivalent to a diagonal standard deviation of 1 voxel for~$\bphi_z$. We found~$\sigma^2 \sim (0.035)^2$ and~$\lambda \in (20000, 100000)$ to perform well, and set~$\lambda=70,000$.

\begin{figure}[t]
	\centering
	\includegraphics[width=1\linewidth]{./figures/entropy}
	%
		\caption{\scriptsize Example velocity field uncertainty~$H(\bz)$ (left) indicates low uncertainty near structure boundaries, as seen in the line graph (middle).
		This correlation is less obvious in the final registration field uncertainty~$H(\bphi_z)$ (right).

		}
		\label{fig:uncertainty}
\end{figure}


\section*{Introduction}

The spread of COVID-19, a respiratory disease responsible for the emerging pandemic observed in early 2020 to date~\cite{hoehl2020evidence,kraemer2020effect,aleta2020modelling}, has led to an increase in misinformation and disinformation about a broad range of topics, from health to technology~\cite{roozenbeek2020susceptibility}. However, due to the unprecedented global health crisis we are facing, the rise of fake news has become a global concern, with the potential to affect public health policy and public order~\cite{rapp_cant_2018,earnshaw2020covid}. The World Health Organization has recognized this phenomenon and has referred to as ``infodemic''~\cite{who2020}, a massive volume of news and narratives not necessarily reliable, including a variety of false rumors and unreliable news appearing during a disease outbreak \cite{organization_managing_2018}, identifying in artificial intelligence an invaluable tool to support the global response against it~\cite{luengo2020artificial}. In fact, coupling misinformation spreading with an ongoing pandemic might be particularly dangerous for public health~\cite{tangcharoensathien2020framework,calleja2021public}, as it erodes trust institutions~\cite{pummerer2020conspiracy} and can lead people to turn to ineffective -- and potentially harmful -- remedies, as well as to engage in risky behavior for them and for the collectivity (e.g., refusing vaccines or not adopting non-pharmaceutical interventions, such as wearing masks and physical distancing)~\cite{van2020using} that substantially increase epidemic spread~\cite{organization_managing_2018,waszak_spread_2018,gallotti_assessing_2020}. \\
Over the past years, social media platforms have become the preferred arena for public debates. Notwithstanding, they also represent some of the most vulnerable hotspots for infodemics to occur~\cite{frenkel_surge_2020,russonello_afraid_2020,loomba2021measuring}. For instance, on social media platforms, false information is typically shared by more users, and travels far more rapidly than reliable information \cite{vosoughi_spread_2018}. This condition is further exacerbated by the presence of social bots~\cite{Ferrara2016,cresci2021coming} -- i.e., automated accounts impersonating humans -- that act as magnifiers of noise, conflicts and (mis)information spread~\cite{shao2018spread,Stella2018,ross_are_2019,stella2019influence,chen2021neutral,gonzalez2021bots,caldarelli2021flow}. Fed by users' preferences and attitudes, social media algorithms increase the selectivity of the contents to which users are exposed, further limiting content verifiability \cite{ciampaglia_how_2018}. All this has been shown to provide a fertile ground for the emergence of echo chambers and epistemic bubbles \cite{nguyen_2020}, well-formed and highly segregated communities where unsubstantiated rumors can gain increased exposure and become highly resistant to correction \cite{Garrett2013ThePA}. \\

\begin{figure*}[t]
    \centering
    \includegraphics[width=\textwidth]{Lorentz1.png}
    \caption{\textbf{Characterizing the share of contents with respect to the share of users who produce them.} The $x$-axis indicates the share of users appearing more frequently in our data set, while the $y$-axis displays the share of the overall content (tweets and retweets) that those users are responsible for. Different content types are encoded by distinct colours: note the red one, corresponding to content identified as fake news. Black dashed lines correspond to the distribution one would observe if all users were responsible for the same fraction of total content, to highlight the highly heterogeneous activity of content production from different users, regardless of content type.

    }
    \label{fig:quantile}
\end{figure*}

In this paper, we investigate factors that may facilitate the share of misinformation in online settings, and we focus our attention on the role of social influence.
Social psychology has shown that beliefs and actions of individuals are heavily affected by what they perceive the majority of their peers thinks or does \cite{Cialdini1999}. Yet this perception does not need to be necessarily correct to be effective. A wrong perception of what the majority opinions and actions leads to what in social psychology is known as “pluralistic ignorance'' \cite{katz_students_1931}, a situation in which the majority of members of a group privately disagree with a certain opinion or social norm, yet (incorrectly) believe that the other group members accept it. Under this situation, individuals believe that they will lose social reputation or will receive negative reactions from other members of their group if they behave how they wish. Therefore, people are likely to act in accordance with the perceived majority even if they privately disapprove of the behavior. Consequently, public behaviors of groups as a whole do not coincide with the majority of group members' private preferences under circumstances of pluralistic ignorance. Previous research has examined the role of pluralistic ignorance across many topics, including heavy drinking \cite{prentice_pluralistic_1993}, racial segregation \cite{fields_public_1976}, casual sex \cite{lambert_pluralistic_2003}, bullying \cite{sandstrom_social_2013}, adolescent delinquency \cite{young_delinquency_2013}, stigmatization at work \cite{munsch_pluralistic_2014}, providing evidence for its effect in supporting the persistence of unpopular attitudes and behavior.
Despite its potential role in favouring the spread of misinformation, evidences of pluralistic ignorance in social media require still to be directly addressed. We thus contribute to this line of research by investigating whether online communication network features -- e.g., those based on content sharing-- play a role in developing a misperception about the opinion of the majority. Specifically, we suggest that a mismatch -- e.g., both in terms of size and in terms of segmentation -- between users responsible for producing unreliable contents and those that mainly share unreliable contents may represent a structural basis on which pluralistic ignorance can naturally emerge.
To this aim, we provide a quantitative analysis of empirical human activities gathered from Twitter, a popular micro blogging platform, on unreliable contents --such as fake news and conspiracy theories -- in the context of COVID-19.
For this purpose we collected and analysed 7.7 million retweets belonging to 1.6 million users and we introduce a criterion for characterizing the users responsible for spreading fake news by means of two groups that we name 'creators' and 'consumers'.
Our choice is supported by empirical evidence provided in first section of this work. We show that the size of the two groups differs significantly: the creators are almost 15k while the consumers are 93k, amounting to the 14\% and 86\% of the fake news spreaders population, respectively.
In the second section we prove that such a definition is solid and suitable even when the underlying socio-technical system is analyzed from a dynamic perspective, showing that users tend to mostly remain in the same group and that inter-group switches are mostly temporary. Finally, we analyse the causality relation between the overall volume of fake news and the size of the groups of creators and consumers, finding the latter to be, in fact, a good control parameter to describe the behavior of spread dynamics of unreliable content.

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.8\textwidth]{schema3.png}
    \caption{\textbf{Schematic illustration of the separation between creators and consumers}. The arrows represent the endorsements (i.e., retweets in Twitter) and go from the retweeting to the retweeted individuals. Values indicates the ratio between the observed number of links and the number one would expect if the links were randomly assigned. Note that the illustration is not at scale with numbers. }

    \label{fig:schema}
\end{figure*}

\section*{Results}

\heading{Characterizing the separation between creators and consumers} We analyzed the interaction networks involving users posting messages related to the COVID-19 on a period of time spanning from January the 22nd to May the 22nd 2020. We focused our attention on the U.S., which is a geographic area particularly active on Twitter, where we have passively collected 7.7 million retweets that allowed us to reconstruct the communication flow network between 1.6 million user accounts.

Users' social behavior, measured in terms of volumes of activities, is not uniformly distributed: instead, it exhibits a heavy-tail distribution, where a minority of individuals is responsible for the great majority of content, as shown in Fig.~\ref{fig:quantile}. Furthermore, this result is confirmed even after stratifying for the type of content: In fact, a minority of users is actively involved in the production of false or misleading content in the context of COVID-19, contributing in a major way to the overall volume of fake news and to the possible over-representation of ideas that would be otherwise be minor. Other users, instead, are characterized by a 'bot-like' behaviour, i.e., the tendency to passively retweet something without commenting on it or appending any original content, thus contributing nonetheless to its diffusion. Users within the platform may assume such misleading information as being representative of what the majority of users believes, which is the basis on which pluralistic ignorance can naturally emerge. Although these two qualitatively different types of users are both ``fake news spreaders'' -- which is the word that we will use to identify them throughout this work -- it is safe to assume that they will have different roles in the misinformation ecosystem.
Users belonging to the first, active, group are highly motivated users, prepared to spend energy and time to craft messages (i.e., tweets) to spread them further. We call a user in this first group as a ``creator''. The second, passive, group contains those users who are more likely to engage in low-cost behaviours, such as retweeting. We will refer to a user in this group as a ``consumer''.The latter user is the one that we suggest may be vulnerable to pluralistic ignorance, namely acting in accordance with the perceived majority, even if he/she privately disapprove of the behavior. Finally, outside of these two groups remains the rest of the online population, consisting of those user accounts that have never shared unreliable content but that, nonetheless, interact with creator and consumer through other kinds of retweets. \\

In order to talk more quantitatively about these two groups, it is useful to define them in terms of the fraction of fake retweets per user in a given time window. Specifically, we defined as being creators all those users whose retweeted content in a given time interval, at least 20\% fake. For more details about this choice see Methods. Furthermore, see SI for an analysis of the difference in number of followers between creators and consumers that further supports our intuition behind the definition of the two groups.

\heading{Fluid transitions between creator and consumer groups} One of the consequences of defining both creators and consumers in terms of user activity is that when the underlying behaviour changes, the composition of the corresponding groups changes accordingly. Operationally, this dynamical behavior over time leads to users going from being active spreaders to being silent, or viceversa, as well as anything in between. In practice, the groups of creators and consumers are fluid constructs that exist at every time step but are also continuously mutating and experiencing inward and outward user flows. \\
It is natural to wonder if the classification provided in the previous section -- that of creators and consumers of fake news -- still holds when such concepts are defined taking short time steps, e.g. one day, while allowing users to switch between groups. We find that only a small minority -- specifically, the 4.67\% -- of all fake news spreaders go from being creators to being consumers or viceversa. Moreover the majority of fake news spreader tends to keep a similar spreading behavior, even after a long period of inactivity (see Table \ref{tab:table}).

Fig.~\ref{fig:flow} shows how a user belonging to the creators (or consumers) group is more likely to behave next, and after how much time. The analysis is restricted only to those users for which such a time can be unambiguously identified, meaning that we only consider those users that return to one of the two fake news groups within the time span of our temporal data. Our analysis shows two facts: first, the probability of returning to either one of the two fake news groups decreases with time; second, it is always more likely to return to the same group that a user left than in the other one. In practice, this means that creators are more likely to go back being creators, no matter how much time they spent being silent, and the same hold for consumers. While these features are the same whether we consider creators or consumers, these two groups also display some notable differences. For instance users leaving the creator group are more likely to come back to it within 0--2 days, although in the same time span they can change group with 10\% probability. Conversely, if a user starts from the consumer group it is much more likely to go back to it even after quite long time, while the probability to change group in the same period is much lower, going down to 24 times less likely in the 18-45 days range. This makes this group more stable in terms of user dynamics and, consequently, more suitable to be considered for potential interventions.
This finding supports our interpretation of consumers as those users who are not very committed to fake news spreading, since the inter-time between consecutive fake news sharing is longer, on average, than that measured for the creators.

\begin{figure*}[t]
    \centering
    \includegraphics[width=\textwidth]{flow2.png}
    \caption{\textbf{Fluid transitions between creator and consumer groups.} Let us consider first-return times: $a)$ schematic example of the behaviour of a user (the circle), who might change his/her group at every time step (e.g., 1 day). Red, blue and black circles represent creators, consumers and non-spreaders, respectively. The return times are the number of black circles that separate colored circles from one another, so in this example they are 3, 0, 1 and 0 days, in chronological order from left-hand to right-hand side. We also report the probability of returning to a skeptic (i.e., non-spreader) group for a user that has just left the creators $b)$ or the consumers $c)$. }
    \label{fig:flow}
\end{figure*}

\begin{table}[ht]
    \centering
    \small
    \begin{tabular}{ l|c|c }
        \textbf{Behaviour} & \textbf{Users} & \textbf{Only once}  \\
        \hline
        Only creators & 13848 (12.91\%) & 9804 (9.14\%) \\
        Only consumers & 88400 (82.42\%) & 58328 (54.38\%) \\
        Mixed & 5005 (4.67\%) & {/}
    \end{tabular}
    \caption{\textbf{User behavior in spreading fake news.} Number of users classified according to their behaviour towards the spread of unreliable content: the majority of them tends to spread fake news only once and, consequently, they were not taken into account in the analysis shown in Fig. \ref{fig:flow}. }

    \label{tab:table}
\end{table}

\heading{Unraveling causality between creators' dynamics and fake news volume} It is plausible to ask whether the overall volume of fake news increases in response to an increase in the number of fake news spreaders or if it is the other way around. To inspect the existence of a causal relation between the size of the two communities of fake news spreaders and the overall volume of fake news circulating in the network, we consider temporal snapshots of 1 day for the analysis. For each time slice, we count how many creators and consumers there are and how many fake news are being shared, building the three time series showed in Fig.~\ref{fig:causation}a which appear to be at least correlated with each other. First, we quantify such correlations: The cross-correlation between the fraction of creators and the fraction of fake content is 0.7; this value goes to 0.69 when we consider the fraction of creators and consumers and reaches 0.97 when we consider the last pair of time series, i.e., fraction consumers and fraction of fake content. \\
Moving beyond simple correlations, we identify what is the cause-effect relation between the number of consumers and fake news spreading by means of the Convergent Cross Mapping (CCM) algorithm (see Methods). To investigate all the possible cases we look for both short-time and long-time effects by varying the time-delay parameter that the method allows one to tune. Our results are shown in Fig.~\ref{fig:causation}b, where the null hypothesis is obtained by performing the same causal test over different surrogates of our original time-series, obtained by randomly permuting empirical observations while destroying any temporal correlation.  \\
As shown in Fig. \ref{fig:causation}b, the cross map causality, i.e. the quantity that indicates how strongly two time series are causally linked, is the highest when the time delay is 0 days, and above the 95\% CL only for 0 and 1 days for both the causality directions (consumers cause a higher volume of fake news and such a volume, in turn, cause a growth in consumers size). An analogous result is obtained when, instead of the consumers' dynamics, creators' dynamics is considered. Although a causal relation between the time course of the two empirical dynamics has been found, it is not possible to conclude which of the two quantities is responsible for the variation of the other, either because 1) there is a very strong feedback loop that propagates causal effects over fast time scales; or 2) the two variables are driven by a third, external or hidden, common cause. In either case this proves that the creators-consumers separation that we introduced to explain the fake news spreading is such a fundamental features that it is practically indistinguishable from the fake news themselves.

\begin{figure*}[ht]
    \centering
    \includegraphics[width = \textwidth]{causation1.png}
    \caption{\textbf{Unraveling causal relationships between group dynamics and fake news volume.}
        $a)$ Comparison between time series of the fraction of fake retweets (black line), the fraction of consumers (blue line) and the fraction of creators (red line). The latters were rescaled to ease the comparison between trends. The time step is of one day while the lines are obtained through a ten days moving average.
        $b)$ Cross map signal computed for different time-delays with the Convergent Cross Mapping algorithm (see Methods). For the null hypothesis we used surrogates obtained by randomly reshuffling empirical observations. The null hypothesis is rejected at 95\% CL, equivalent to an \emph{a priori} test size of 5\%, only at time delay equal to 0 and 1 day, with the strongest signal at the former.
     }
    \label{fig:causation}
\end{figure*}

\begin{figure*}[t]
    \centering
    \includegraphics[width=\textwidth]{sensitivity1.png}
    \caption{\textbf{Analysis of the separation between creators and consumers for different definitions of these groups.} The height of the bars indicate the ratio between the observed number of links between two groups and the number we would expect if the links were randomly distributed among the network. The dashed horizontal line corresponds to the case where the number of observed links is compatible with those of a random network ($y=1$). The red and blue colors indicate if the tweet was originally from the creators or from the consumers, respectively. The figures differ because of the threshold in the percentage of most active fake news spreaders used to define creators and consumers. However, it can be seen that the densities of the connections between these groups do not depend strongly on such a threshold.  }

    \label{fig:density}
\end{figure*}

\section*{Discussion}

Overall, from our analysis, a consistent picture arises. First of all, we were able to separate fake news spreaders in two groups: a small one (14\%) of active and motivated users (creators) and larger one (86\%) of users who instead prefer to repeat what other people say without creating content on their own (consumers). We did so by putting together an information coming from the structural network such as the in-degree of each node with the information coming from the metadata on the retweets nature, namely the subject of the message. Furthermore the criterion that we chose proved to be robust against the variation of the only arbitrary parameter that it takes as input. \\
As a result we were able to classify all users in the network based on their group's belonging. This allows us to quantify their role in the spreading of fake news and to understand how much they are susceptible to developing a wrong representation of the opinions and beliefs of their community. In particular, the creators strongly interact among themselves, so it is reasonable to think that they have a correct estimate of the opinions of the other members of their group.
By contrast, the consumers are users who read and retweet contents coming from the creators. Since creators are only a minor fraction of the twitter landscape, such an over exposure to their tweets may lead consumers to believe that the opinions of the creators are representative of those held by the majority of users. This may generate a pressure to act accordingly to the (mis)perceived majority, even if this is not in line with their own private opinions. Our study thus suggest that, on a global level, this condition can favour the spread of COVID-19 infodemics.
One may ask if such interpretation is specific to fake news or, alternatively, if it can apply also to other types of news (e.g., Mainstream Media, Science) shared on  social media. While a similar group segmentation (namely, a small number of creators and a large number of consumers) is likely to occur  regardless of the content expressed (e.g., see Fig. \ref{fig:quantile}), we expect pluralistic ignorance to emerge especially with "unpopular" behaviours, such as when individuals publicly express approval for something questionable (such as sharing blatantly false content) while privately disapproving it, and do so under the false perception of a general acceptance of that behavior. Such a misalignment between public action and private preference is unlikely to occur for less questionable behaviours (e.g., sharing Mainstream Media contents). \\
One of the benefit of our distinction between creators and consumers is the possibility of doing a temporal analysis and therefore to judge how user behaviour and fake news circulation relate to each other. In our analysis we found that it is impossible (at least with the time resolution available to us) to understand if fake news cause a growth in the number of highly active fake news spreaders or vice versa or, again, if they simply are the effect of a third, external event. Our results suggest that the number of consumers is probably the best indicator of fake news trend, since these two quantities show a stunning cross-correlation of 0.97. This confirms the idea that it is on consumers, those more susceptible to a possible ``illusion of majority'', that one should focus in order to control and, hopefully, reduce the incidence of fake content online. In off-line contexts, the effect of pluralistic ignorance can be alleviated by informing people about the real beliefs and expectations of others \cite{berkowitz_overview_2005}. Similar kinds of ``bottom-up" interventions could be designed to prevent users to share unreliable contents in online settings. Specifically, by unveiling the collective misunderstanding on which users behaviour is based may reduce the pressure to act as the perceived majority does not let users behave according to their (potentially disagreeing) private preferences.  Such interventions may encounter less resistance and lead to less backfiring effects (e.g., increasing polarization and resistance to opinion change) compared to debunking information ``inoculated" by external authorities or fact-checkers \cite{lewandowsky_misinformation_2012, chan_debunking_2017}.
Our study makes several important contributions to the current literature addressing the expression of opinions in social media. We provide insights on what drives individuals to share unreliable contents in online settings, complementing a growing body of interdisciplinary work exploring the social motives and the psychology that underpins the dynamics of social media sharing \cite{ren_social_2021, pennycook_psychology_2021}.
Misinformation  spreading can  be  particularly  dangerous in the context of the current COVID-19 pandemic as it may decrease people willingness to comply with preventive behaviours  (e.g., taking vaccines,  wearing   masks  and adopting physical distancing) \cite{van2020using}. Although more evidence is needed to assess that on-line undesirable behavior may spill-over in off-line behavior (see also \cite{valensise2021lack}), shading light on the role of social factors in the context of fake news spread may offer a novel approach for fighting misinformation and it is an attempt to respond to the current call from the research community for a better integration of the social sciences to support COVID-19 pandemic response \cite{van2020using}.

\section*{Methods}
\heading{Dataset origin and description} The datasets that we used in this come from the Covid19 Infodemics Observatory \cite{gallotti_assessing_2020, covid_observatory}.
Twitter associated with the COVID-19 pandemics (coronavirus, ncov, \#Wuhan, covid19, COVID-19, sarscov2, covid) have been automatically collected using the Twitter Filter API.

The fraction of tweets included in our filter is limited by Twitter to 1\% of the total, which instead provided us with a random sub-sample of all interactions. Nevertheless,  recall of approximately 40\% of all tweets associated with Coronavirus is estimated during these months. To reconstruct the communication network from the messages, we aggregate the information from two
the three
types of public pairwise interactions between
users: retweets and replie

In order to identify misinformative contents we used a database of web-domains we constructed joining together multiple publicly available data sources \cite{gallotti_assessing_2020}. This allowed us to to classify the URLs, that are included in about 20\% of tweets
as one of seven categories: Science, Mainstream Media, Satire, Clickbait, Political, Fake/Hoax, Conspiracy/Junk Science. A fraction of about 14\% of URLs were successfully classified in this sense (about 25\% in the case of Italy).
In this analysis, we considered as ``fake'' messages associated with domains marked as Clickbait, Fake/Hoax, Conspiracy/Junk Science. We also restricted our analysis to those users classified as real people, and not bots, using the machine learning methodology described in \cite{stella2019influence}.

Lastly, our analysis is focused on three countries: Italy, the United States, and the United Kingdom. To select accounts associated with a particular country, our data infrastructure is based on the geo-coding of the accounts' textual self-declared location, which we are able to successfully map to a country of the world in the 50\% of cases. Finally in the case of the US and the UK the data spanned from January 22 and May 22, 2020; for Italy the period was instead between January 22  and December 2, 2020.

\heading{Definition of Creator and Consumer groups} The definition of the concept of creators and consumers is based on a criterion applied to each user individually. This criterion is based on the fraction of fake news produced: if among all the tweets that an account has produced 20\% or more is fake, then that user is considered to be part of the creators. On the other hand, if this fraction is between 0\% and 20\%, the account is considered to be part of the consumers.\\
In order to verify that this method is actually effective in identifying two separate groups we compared our network against a null model with randomly distributed links (see Fig. \ref{fig:density}). In this way, we were able to
highlight
a clear separation between creators and consumers given by the fact that the former group is much more likely to be retweeted than the latter.
Furthermore, this methodology allows carrying out a sensitivity analysis to investigate the dependence of the behaviour of these systems on the threshold to be considered a creator (that we fixed to 20\%). The result of such analysis shows that no matter what threshold we choose, this criterion is effective in separating fake news spreaders responsible for producing a large part of fake news, and those responsible for retweeting them, as shown in Fig. \ref{fig:density}. Finally in the Supplementary Information we show that the creators-consumers structure is not unique to the data from the US but can be found in the data from Italy and the UK as well.

\heading{Causality detection via Convergent Cross Mapping} The algorithm that we use to infer the causal relation between the two time series in Fig. \ref{fig:causation} is called Convergent Cross Mapping. Given two time series it makes use of Taken's theorem to reconstruct the dynamical attractor that produces the first of the two and from that uses it to estimate the other. The cross correlation between the second time series and its reconstructed version is the indicator of how strongly the second is caused by the first. More information on the exact algorithm that we used can be found at \cite{rEDM}.

\heading{ACKNOWLEDGMENTS}The research reported in this work was partially supported by the EU H2020 ICT48 project ``Humane AI Net" under contract \#952026.


\section{Introduction}

In a recent paper, \citet{freedman2020adapting} remark that
``efficient and fair allocation of limited resources is a classical
problem in economics and computer science.'' Their specific
application is to kidney exchange, a central example of the kinds of
domains we are concerned with in this paper, but it also captures many
important issues in the development of how we think about the problem
today. Computer Science has been concerned for a long time with
algorithms that allow for efficient and fair allocation of limited
resources (learning about job allocation in time-sharing computers is
a long-time staple of operating systems courses, for
example). Economics is sometimes defined as precisely the study of
the allocation of scarce resources. As a result, most of our ideas for
AI-enabled allocation of scarce resources
have been driven by the histories of these two fields. This has
significant consequences, because it means the measures we develop
algorithms to optimize are those that have a pride of place in
economics -- most of the time utilitarian (or additive) social
welfare, but in other cases Rawlsian (max-min) or Nash
(multiplicative) social welfare.

However, we have also been building real social and political
institutions to allocate scarce resources for centuries, and a central
insight is that they often prioritize in ways that do not correspond
directly with any of these measures of social welfare. For example,
triage in battlefield medicine or rationing of healthcare in
emergencies prioritizes greedily by predicted improvement, which can
have consequences different from either efficient allocation or
max-min allocation.
While economics may be the study of
the allocation of scarce resources, in the words of
Harold Lasswell, politics is ``who gets what, when, and how.''
Thus it is appropriate to turn to political science. The political
philosophy of allocation of scarce resources is studied under the
moniker of \emph{local justice} \cite{elster1992local}, which
systematically considers the question of how institutions allocate
scarce resources and necessary burdens (for example, through
lotteries, principles of greatest need, best outcome, or most ``value
added'').

While there has been burgeoning interest in defining the objectives of
AI systems by taking multiple stakeholders into account
\cite{freedman2020adapting,lee2019webuildai}, the main theme of this paper is
that analyzing AI systems that endeavor to fairly and efficiently
allocate scarce resources through the lens of local justice can
greatly clarify both the objectives of system design and the parts of
the pipeline where algorithmic and data-driven techniques can be
particularly helpful. I start by introducing the setting and
describing four big questions that should be answered by any allocation
system. After providing background on related research in machine
learning and fair division, I introduce a formalization of some of the
principles of local justice, and then discuss how the four questions
can be thought of in that framework, and the roles that AI can play in
helping to better assess and design these allocation systems.

\section{Setting}

For the purposes of this paper, the problems we are interested in involve the allocation of resources that are
(1) controlled or regulated by society; and (2) scarce; we focus on
settings where data-driven or algorithmic decision-making is
feasible. For various reasons, we have decided that market mechanisms
are inappropriate for these settings \cite{elster1992local,roth2007repugnance,currie2008transfers}. Examples include organs for transplantation,
resources for homeless populations, and spaces in elite public
schools, among others. Note that decisions about the appropriateness
of market mechanisms can vary across settings -- for example,
markets for kidneys exist in Iran. A few other notes: settings can be
dynamic (e.g. organ transplantation) or static (e.g. batch matchings
of students to schools), and it could be possible to assign different
individuals to different types of resources (for example, the level of
services provided by homelessness service providers can vary in
intensity).

I will argue, through the rest of this paper, that in order to design
systems that are improved by the use of AI (and more generally, to
consider the benefits and harms of using AI in these domains), we need
to think clearly and specifically about a set of related questions.
(1) How do we define and quantify desirable outcomes, in terms of
efficiency, equity, justice, or fairness? (2) How do we predict outcomes for
heterogeneous individuals and households under different feasible
allocations? (3) How do we optimize allocation of scarce resources
to achieve the best population-level outcomes under constraints
defined by our notions of justice or fairness?
(4) What can we say about the incentives created by the overall
system, and the potential for manipulation or negative long-term
outcomes of deployment, considering the preferences of participants?

By specifically engaging elements of each of these questions, we can better consider the ramifications of our technologies --
how, precisely, do they help or hurt compared with current practice?
-- rather than being seen as technological solutionists by the
stakeholders we must engage.

\section{Background}

It is certainly not a novel observation that we need to think
carefully about what it is that we are trying to optimize. Just to
give a couple of recent examples, \citet{conitzer2019designing} discusses the
importance of appropriately designing preferences and optimization
goals for AI agents, while a core argument of \citet{o2020near} is that many of the problems of ``near-term AI'' (defined as
expert systems that replace human decision-makers) are driven by a
mismatch between the performance metrics of the AI (constructed by the
algorithm designers) and the true objectives of
stakeholders. Nevertheless, it is useful to get a sense of where the
academic community has gone in response to these concerns.

\subsection{Fairness in machine learning}

A common trope is that the first objective of the engineer is simply
to optimize a given objective function. Indeed, standard metrics, for
example, accuracy, area under the ROC curve, or return on investment,
still drive much research, so the first instinct in many applications
of machine learning in society has been to define societal problems in
a manner amenable to analysis through the lens of metrics like these.
In the recent past, we have learned how machine learning systems that
are ``in the loop'' of human decision-making can have significant
unintended consequences. Examples abound: in some cases, instead of
reducing crime rates, predictive policing results in more false
arrests as police misinterpret algorithmic predictions of suspects as
evidence \cite{saunders2016predictions}. In a number of situations,
data-driven allocations have unintentionally introduced systematic
biases that perpetuate inequities, such as racial disparities in
credit lending, hotspot policing, and crime sentencing
\cite{ensign2017runaway,pleiss2017fairness,corbett2017algorithmic}.

The response of the ML community, while not entirely uniform, has
largely revolved around a call for algorithms to satisfy various
fairness metrics
\cite{dwork2012fairness,kusner2017counterfactual,hardt2016equality}. However,
there has been pushback against this from various
perspectives. Notably there have been some impossibility results,
showing that several different fairness criteria that all seem
intuitively reasonable cannot be satisfied simultaneously
\cite{kleinberg2016inherent,pleiss2017fairness,feller2016computer}. \citet{corbett2018measure} discuss the statistical limitations of various fairness
criteria, and argue that formal fairness criteria may ``harm the very
groups they are meant to protect'' and advocate instead for treating
similarly risky individuals similarly, based on the best risk metrics
available. \citet{green2018myth} say that the
methodological reliance of machine learning on standard techniques,
metrics, and datasets makes it ill-suited to address political and
ethical considerations in the deployment of algorithms in socially
important contexts. They go on to call for the
process of democratic deliberation as much as technical analysis in
such deployments.

There is also a rich literature on \emph{fair division} \cite[e.g.]{bouveret2008efficiency,chen2013truth}
that is related, but the connections are, somewhat surprisingly, only
beginning to be explored. In typical fair division problems, the
analysis is from the perspective of treating all agents as equal
priority and focusing on the efficiency and fairness guarantees that
can be made with respect to agent preferences. In the types of domains
we are looking at, the questions of who receives priority and why are
much more central.

\section{Social policy and local justice}
In the domain of allocation of scarce resources to individuals (and
households, etc.) in need, we do not have to reinvent the wheel
in order to examine the effects of different ways of setting social
optimization goals. Institutions such as organ donation policy-making
bodies and draft boards (among many others) have long grappled with
the question of how best to allocate scarce resources (or necessary
burdens). Political philosophers have discerned from these cases a set
of useful underlying principles of what they call local justice. Our
discussion here largely follows that of \citet{elster1992local}.

\paragraph{Local vs.\ global justice}
To make one distinction clear, local justice is
distinguished from theories of global justice and individual rights
(notably utilitarianism, Rawl's theory, and Nozick's libertarian
theory) by the local nature of decision-making. The ethics of deciding
how to allocate scarce resources in one setting does not carry over to
others necessarily, and a series of decisions deemed to be locally
just may lead to global problems for a particular group. Our concern
here is with considerations of ethical decision-making by local
institutions.

\subsection{Principles of local justice}

Elster categorizes the principles of local justice in several ways. Let us briefly discuss principles for
allocation of scarce resources that have been used in society that
will not be our focus. These include allocation based on status (quota
systems in general), age and gender (women and children first on the
lifeboats), waiting time (queueing systems), power and influence
(legacy admissions), or lotteries.

If we restrict ourselves to settings in which AI or data-driven
decision-making can have most impact, we are most interested in
principles that take into account specific properties of individuals,
and also the interaction between the individual and the allocated
resource. Three types of local decision-making based on the welfare of
individuals are prevalent in institutions that allocate scarce
resources. In order to present these, first let us assume that
individual welfare levels can be reduced to a single-dimension, call
it $w$.

\noindent (1) Minimum pre-allocation $w$: This is the principle of allocating
  to those with the greatest need. The homelessness system in most of the United States is a good example of
  a system that mostly works on this principle, with explicit
  determination and prioritization of the most vulnerable, sometimes
  based on a score, and sometimes on individual discretion of the case
  officer. Another example is in cadaveric organ transplantation,
  where the sickest patients get highest priority, often based on a
  complex scoring mechanism.

\noindent (2) Maximum post-allocation $w$: This principle allocates
  resources to those who will be best off after allocation. For
  example, some elite public magnet schools may select those
  who are already extremely gifted and would have the
  highest post-schooling quality (even if the school does not
  end up contributing much to that final quality itself).

  \noindent (3) Greatest increase in $w$: This is the principle of
  allocating to those who would get the greatest ``value added'' from
  the resource, measured by the difference in post- and pre-allocation
  levels of $w$ (note that this difference could be stochastic rather
  than deterministic). An example is in emergency medical triage in
  wars, or when there are insufficient ICU beds or ventilators
  available in hospitals and care must be rationed. In these settings,
  those who receive treatment and attention are typically those in the
  middle-range (leaving aside those who will recover well without
  attention and those who are too critical to be saved).

It is certainly not the case that one of these is better than the
others as a criterion in all situations. Indeed it is worth thinking
about societal objectives again, with the example of patients on wait
lists for organs from deceased donors. It is common practice to
prioritize sicker patients (corresponding to the first principle
above) even though overall outcomes may be better if one were to
transplant less sick patients earlier in their time on the wait
list. However, this creates the societal feeling that one could be
abandoned, which is considered harmful to social
well-being and cohesion.

\section{Roles for AI}

Using the framework of local justice, and in particular of allocation
systems based on properties of individuals, we can articulate possible
roles for AI by going back to the four defining questions for an
allocation system posed above.

\subsection{Defining and quantifying desirable outcomes}

While most of the literature examines the ``traditional'' utilitarian
or Rawlsian notions of welfare, there has been increasing interest in
considering different possibilities. The ``moral machines'' project
was among the first to crowdsource moral judgments about algorithmic
decisions in the context of ethical dilemmas that could be faced by
autonomous vehicles \cite{awad2020crowdsourcing}. There has been
recent work on turning such judgments, from experts or from the
general public, into objective functions. Notably, \citet{lee2019webuildai}
describe a system that allows stakeholders to construct computational
models representing their views, and the models then vote in order to
create what the authors call ``algorithmic policy.'' One of the
benefits, compared to objective functions designed by the algorithm
designers, is that this engages stakeholders and increases
buy-in. \citet{freedman2020adapting} propose a principled methodology
for eliciting stakeholder preferences for which attributes of
individuals should be considered for prioritization of kidney
transplant recipients, and propose a method for estimating weights
using these preferences. Interestingly, in both of these cases, there
is a combination of machine learning for preference learning, and some
form of social choice for preference aggregation. These types of
ideas highlight the promise of AI to go beyond what we have been able
to do societally and come up with methods that could lead to
greater social acceptance and more participatory decision-making in
these spheres.

Another area where AI has been valuable is in understanding the
overall effects of optimizing different welfare criteria through ideas
like the price of fairness, which examines the efficiency loss due to
implementation of a fairness criterion in allocation \cite{bertsimas2011price,caragiannis2012efficiency}.  For example, \citet{nguyen2021scarce} consider a
prioritization method that implements the triage principle
of greatest increase in $w$. They study the price of fairness and show
that its price of fairness is often lower than that of the
most-vulnerable-first principle. They argue that this could partly
explain situations in which society has agreed that the triage
principle should be used, e.g. short-term emergency medical situations
like those that could occur in a pandemic, in spite of the problem of
abandonment.  In this type of work, computing acts, in the words of \citet{abebe2020roles} ``as a formalizer, [shaping] how social problems are explicitly defined --- changing how those problems, and possible responses to them, are understood.''

There are many risks and caveats to remain aware of. While some may be
unanticipated, a few can be seen from the start, and we discuss two
here. First: some of the major problems in bias of machine learning
systems have arisen as a result of them replicating human biases that
we do not want to sustain. Does learning preferences from stakeholders
and humans potentially perpetuate injustices? This can vary between
contexts, but the famous case of the Seattle ``God committee''
which decided who would have access to dialysis treatments in the
1960s is a classic cautionary tale. As \citet{levine2009seattle} says ``the
committee relied heavily on criteria of social worth heavily weighted
toward economic status, reflecting their own values and biases.''
One of the potential \emph{benefits} of AI
is in the potential objectivity of its goals, but nevertheless, this must
be in consultation with stakeholders (the veneer of objectivity can
also encode biases, of course).

Second, we need to be careful in translating between social objectives
and mathematical formalizations. We often benchmark to efficient, or
utility maximizing allocations, whether in terms of the price of
fairness or not. However, even in some social allocation problems
where the goal at first appears to be utilitarian efficiency, it may not be. For
example, prioritization by maximum post-allocation welfare is not the
same thing as the utilitarian assignment in a system with multiple
interventions.

\subsection{Predicting outcomes under different allocations}

A second part of the local justice framework in which AI, and in
particular, machine learning (ML), has potential is in measuring and
predicting the welfare level $w$. While an
impossible task in general, in many real-world cases we do use
proxies for $w$. For example, in medical interventions we may use
Quality Adjusted Life Years (QALY) as a
measure, in homelessness services the VI-SPDAT score (note concerns
about validity) has been used to measure vulnerability, and in liver
transplantation the MELD score is used to measure severity of liver
disease. In the latter two cases, the score is considered inversely
related to welfare.

One interesting use of ML is to better capture
what such scores seek to measure. In homelessness services, for
example, the vulnerability score is often intended to measure how
well an individual or household would do without receiving support. In
child welfare, one may want to measure any number of negative outcomes
(inability to make progress in school, interactions with
the criminal justice system or need for emergency medical care). By using ML methods on administrative data,
one could predict the probability of successfully remaining housed, or
graduating school on time, and these measures
may be more directly related to the outcomes we care about
than the scores we currently construct.

The prediction problem is in some ways even more interesting, because
it asks the question of how well individual $A$ (defined by some
characteristics that we can think of as a feature vector) would do
when given interventions $\alpha, \beta, \gamma, \ldots$. This is more
complex because it asks about the interaction of an individual (or
household) with an intervention. While there is much to be done in
this area, recently different approaches to this have been taken. In
the domain of matching refugees to cities in which they are likely to
do well (so $A$ is a refugee family and the Greek letters are
different cities), \citet{bansak2018improving} take advantage of prior random allocation
to learn good models, while \citet{kube_allocating_2019} estimate
counterfactual probabilities using BART in the case of allocation of
homelessness services.

Many of the usual concerns with ML surface when it is
used in these domains. Are we learning the right model, and making
predictions in ways that are fair to different subgroups, for example
\cite{kearns2018preventing}? This could be compounded in two separate ways. First,
there are many domains where human behavior is fundamentally not very
predictable compared with other ML tasks, with low AUC
values the norm. Second, the counterfactual problem is particularly difficult. There may be a paucity of data on
individuals or households of certain types receiving certain services
in the past (whether because of biases or other reasons), making
models less valid for those populations.

\subsection{Optimization with fairness constraints}

The third question raises interesting algorithmic challenges. Given a plausible, but perhaps ``soft'' notion of fairness that
does not yield a strict priority ordering that must be respected, and
also a social goal, how can we optimize towards both objectives? This
is a fascinating, and methodologically challenging, problem with
a strong practical basis. For example, those fleeing domestic violence
are prioritized for spaces in homeless shelters and the
immunosuppressed for vaccines. There is exciting work in this
space. For example \citet{mcelfresh2018balancing} design a rule for balancing a utilitarian
objective with preferences for one group over another in kidney exchange, while \citet{azizi2018designing} consider a
formulation that optimizes efficiency while satisfying fairness
constraints specified by a policy-maker in the context of providing
resources to homeless youth. There is plenty to be done in this area,
where exact solutions that can be computed efficiently are typically hard to find.

\subsection{Preferences and incentives}

Thus far we have elided the question
of preferences. The implicit assumption is that the decision-maker
knows, or can acquire, sufficient information about each individual in
order to make decisions, and that individuals do not really have the
power to affect allocations, and would prefer some allocation to none
at all. However, we should also consider the incentives created by
such systems, as suggested by \citet{roth1993local} in a review of Elster's book
\emph{Local Justice}. Recent work in algorithmic game theory
and matching has begun to do so. Two examples are
illustrative. \citet{estornell2021incentivizing} look at a problem
motivated by people lying about self-reported attributes in order to
receive a more favorable score (as has been reported, for example, in
the context of homelessness services in LA). They show how one
can use audits of self-reported features after-the-fact in order to
incentivize truthful behavior, and also demonstrate that the scarce
resource setting poses fundamentally different challenges than the
setting where resources are not scarce but the institution would
benefit from setting some score threshold. \citet{aziz2021efficient}
consider the problem of allocating scarce healthcare resources when
individuals may have different eligibilities for the resources. For
example, individuals may become eligible for Covid-19 vaccination
under different eligibility categories. They design a mechanism for
efficient allocation that complies with eligibility requirements,
respects priorities within eligibility categories, and incentivizes
truthfulness in the sense that individuals never underreport
eligibility categories.

These examples are on the spectrum of the many interesting and
challenging problems that arise on the mechanism design side when
thinking about how to design end-to-end systems for allocation of
scarce societal resources. In addition to the other categories above,
this provides a set of possible ideas, and a personal sense of
priorities, for future research in the use of AI for such allocation
problems.

\section{Acknowledgments}

I am grateful to Frank Lovett for pointing me to Jon Elster's work, and to Veena Das, Jennifer Dlugosz, Patrick Fowler and Eugene Vorobeychik for many conversations that have helped frame my thinking on these topics. I also thank the AAAI Blue Sky track reviewers for various helpful suggestions. All errors and opinions are, of course, my own. This work has been supported in part by NSF awards 2127752, 2127754, and 1939677 and by Amazon through an NSF-Amazon FAI award.