# Least Squares Inference for Data with Network Dependency

Jing Lei  Kehui Chen  and Haeun Moon

Abstract

We address the inference problem concerning regression coefficients in a
classical linear regression model using least squares estimates. The analysis
is conducted under circumstances where network dependency exists across units
in the sample. Neglecting the dependency among observations may lead to biased
estimation of the asymptotic variance and often inflates the Type I error in
coefficient inference. In this paper, we first establish a central limit
theorem for the ordinary least squares estimate, with a verifiable dependence
condition alongside corresponding neighborhood growth conditions.
Subsequently, we propose a consistent estimator for the asymptotic variance of
the estimated coefficients, which employs a data-driven method to balance the
bias-variance trade-off. We find that the optimal tuning depends on the linear
hypothesis under consideration and must be chosen adaptively. The presented
theory and methods are illustrated and supported by numerical experiments and
a data example.

Keywords: network dependency, central limit theorem, bias correction, adaptive
estimation

##  1 Introduction

The analysis of dependent data with specific structures such as longitudinal
data, times series data and spatial-temporal data constitutes long-standing
research areas with significant theoretical and practical implications.
Recently, data with complex interpersonal dependency characterized by networks
are becoming increasingly available. For example, in some survey studies of
school students, in addition to traditional variables collected on each unit
such as drug use, smoking and mental health status, a friendship network among
students may also be collected. The response of interest such as drug use is
likely to have dependency across units through friendship networks. In animal
studies, the animal samples in their habitats naturally interact with each
other. In addition to traditional individual data collection, animal
researchers are now able to record a social contacting network through camera
tracking combined with computer software such as idTracker (Pérez-Escudero et
al., 2014). The analysis of this type of data calls for statistical inference
tools and theories that take into account the network dependency. In this
work, we focus on developing methods and theory for the inference of
regression coefficients, when there is network dependency across units of
sample.

We consider a regression setting $Y=X\beta+\epsilon$, where
$Y\in\mathbb{R}^{n}$, $X\in\mathbb{R}^{n\times p}$ and
$\epsilon\in\mathbb{R}^{n}$. Each sample point $1\leq i\leq n$ also
corresponds to a node in a network. Assume that we observe a network adjacency
matrix $A$, where $A_{ij}=1$ means an edge exists between individual $i$ and
$j$ and $A_{ij}=0$ otherwise. We allow the entries of the error vector
$\epsilon$ to be correlated through the network structure $A$. More
specifically, a general dependence structure to consider is that the
dependence between $\epsilon_{i}$ and $\epsilon_{j}$ decays as their graph
distance $d(i,j)$, such as the shortest path distance, increases. Network
auto-regressive error models and network moving-average error models both fall
into this framework, where in the latter case dependency only spans a
neighborhood of finite radius measured in network distance. This
$Y=X\beta+\epsilon$ setting is particularly suitable if the main interest is
in the estimation and inference of $\beta$ instead of modeling social network
effects. For example, researchers in mental health studies are often
interested in identifying biomarkers. A linear regression model with least
squares estimate is arguably the most widely used approach and many of the
tools developed for model interpretation, model selection, and multiple
comparison correction are based on a linear model or a generalized linear
model. Meanwhile, people are aware that neglecting the dependency among
observations may result in an incorrect estimation of standard errors, and
often inflates the Type I error in the inference of $\beta$. This has been
well observed in data with temporal/spatial dependency (Gaetan & Guyon, 2010,
Ch. 5.3), and has recently been shown in data with network dependency (Lee &
Ogburn, 2021). Therefore, in this work we focus on developing valid inference
of $\beta$ based on the ordinary least squares estimate $\hat{\beta}$, where
the estimation of ${\rm var}(\hat{\beta})$ takes into account the network
dependency but does not impose strong or parametric assumptions on the
dependence structure.

While there exists a large body of literature on the analysis and
characterization of the network/graph itself, there is only limited work that
addresses the fundamental normal approximation for the sum of random variables
observed with network/graph dependence. Under the finite range dependence
structure, central limit theorems can be established using tools developed in
Baldi & Rinott (1989); Chen & Shao (2004), and some recent work studied CLT
for infinite range network dependency (Shashkin, 2010; Ogburn et al., 2017;
Kojevnikov et al., 2021). The challenges of dealing with network dependency
are at least twofold. The first challenge is the infinite dimensionality,
which can be understood through the notion of network neighborhood growth.
When the average number of neighbors grows polynomially with the neighborhood
radius measured by a graph distance, the graph can be embedded in a Euclidean
lattice and theories for Euclidean spaces can be borrowed. Time series data
and spatial data can be viewed as data on Euclidean lattices, and are special
cases of low-dimensional embeddable graphs. A general network may have a
faster neighborhood growth beyond the Euclidean lattice case and corresponds
to a much richer and more complex embedding space (Weber, 2020). The second
challenge is the node heterogeneity, which means each node may have its own
neighborhood growth sequence. Such a lack of symmetry makes it hard to carry
over the useful tools developed for Euclidean lattices such as stationarity
and mixing.

In this paper we make three theoretical and methodological contributions to
least squares regression inference with general network dependence. First, we
establish a central limit theorem for the ordinary least squares estimate
$\hat{\beta}$, with a verifiable dependence condition alongside corresponding
neighborhood growth conditions. Second, we propose a consistent estimator for
the asymptotic variance of $\hat{\beta}$. The key quantity to estimate is the
matrix $X^{T}\Sigma X$, where $\Sigma$ denotes the unknown covariance matrix
of the noise vector $\epsilon$. Our estimator $\widehat{X^{T}\Sigma X}$ uses
the pair-wise products of fitted residuals to approximate the entries of
$\Sigma$ and truncates a pair-wise product to $0$ if the graph distance
between the two nodes exceeds a threshold $m$. It can be viewed as an
adaptation of the sandwich estimator (Huber, 1967; White, 1980; Liang & Zeger,
1986) in the network dependency setting. Third, we propose a data-driven
approach to determine the truncation order $m$ in coefficient inferences. We
demonstrate that the optimal truncation order $m$ depends on the linear
hypothesis under consideration, and must be chosen adaptively. In Section 2,
we present the main theoretical results. In Section 3, we describe the data-
driven estimate for the variance components. Numerical experiments and data
examples are presented in Section 4 and 5, followed by a short discussion in
Section 6. Proofs are included in the Appendix.

##  2 Inference of regression coefficients under network dependency

Consider a linear regression model written in matrix form

$Y=X\beta+\epsilon\,,$

where $Y\in\mathbb{R}^{n}=[y_{1},\dots y_{n}]^{T}$, $X\in\mathbb{R}^{n\times
p}=[x_{1\cdot},...,x_{n\cdot}]^{T}=[x_{\cdot 1},...,x_{\cdot p}]$,
$\beta\in\mathbb{R}^{p}$, and $\epsilon\in\mathbb{R}^{n}$ satisfying
$\mathbb{E}(\epsilon|X)=0$.

We are interested in the case where the entries of $\epsilon$ may be
dependent, and the strength of pairwise dependence can be quantified by the
pairwise distances. Our general theory and methods work for all distances
satisfying triangle inequality. In this paper our examples will focus on the
shortest path distance defined on a network. To facilitate discussion, we
assume that each sample point $i$ is a node on a graph denoted by a symmetric
binary adjacency matrix $A$. Let $d(\cdot,\cdot)$ denote the shortest path
distance, or other distance under consideration, between a pair of nodes.

Our goal is to establish asymptotic normality of the least squares estimate of
$\beta$ under suitable conditions of the dependence decay and the network
neighborhood growth. The parameter dimensionality $p$ is assumed fixed. In
order to present the asymptotic theory, we adopt a fixed-design setting and
consider a sequence of data generating models $(X,\Sigma,A)$ indexed by the
sample size $n$, where for each $n$

  * •

$X$ is an $n\times p$ non-random design matrix;

  * •

$A$ is an $n\times n$ symmetric binary adjacency matrix;

  * •

$\Sigma$ is an $n\times n$ covariance matrix such that
$\Sigma=\mathbb{E}\epsilon\epsilon^{T}$.

For notational simplicity, we drop the dependence on $n$ in $(X,A,\Sigma)$ and
other related objects such as $Y$ and $\epsilon$.

We group our technical assumptions into three parts. The first part is some
general boundedness and moment conditions.

######  Assumption 1.

There exists a constant $c$ such that

  1. (a)

$|x_{ij}|\leq c$ for all $i\geq 1$, $1\leq j\leq p$;

  2. (b)

$\sup_{i}\|\epsilon_{i}\|_{4}\leq c$;

  3. (c)

$c^{-1}I\preceq X^{T}\Sigma X/n\preceq cI$.

Assumption 1 part (a) and part (b) are standard boundedness and moment
conditions for the design matrix and noise variable, respectively. The
constant $c$ in these two parts can be relaxed to grow slowly with $n$, as
long as they are dominated by other vanishing terms in the error bound.
Assumption 1 part (c) is much less stringent than requiring
$c_{1}I\preceq\Sigma\preceq c_{2}I$, because it only requires the eigenvalues
of $\Sigma$ after projecting onto the column subspace of $X$ to be bounded
from above and away from zero.

The second part of assumptions is about the dependence decay among coordinates
of $\epsilon$ when the graph distance grows.

######  Assumption 2 (Correlation decay).

The process $(\epsilon_{i}:i\geq 1)$ satisfies an exponential correlation
decay with respect to a distance measure on the index set
$d(\cdot,\cdot):\mathbb{N}^{2}\mapsto\mathbb{R}^{+}\cup\\{0\\}$, such that the
following hold for some constants $\rho\in(0,1)$ and $c>0$

  1. (a)

$|\mathbb{E}(\epsilon_{i}\epsilon_{j}^{\ell})|\leq c\rho^{d(i,j)}$ for
$\ell\in\\{1,2\\}$.

  2. (b)

$|{\rm Cov}(\epsilon_{i}\epsilon_{j},\epsilon_{k}\epsilon_{l})|\leq
c\rho^{d(\\{i,j\\},\\{k,l\\})}$, where for any index set
$U,V\subset\mathbb{N}$ , $d(U,V)=\min_{i\in U,j\in V}d(i,j)$.

  3. (c)

For any $h:\mathbb{R}\mapsto\mathbb{R}$ uniformly bounded with uniformly
bounded derivative, any constant $t$ and any index sets $U$, $|{\rm
Cov}(\epsilon_{i},h(tS_{U}))|\leq c(1+t|U|)\rho^{d(i,U)}$, where
$S_{U}=\sum_{i\in U}\epsilon_{i}$.

The correlation decay conditions listed here are less stringent than similar
“weak dependence” conditions based on pairwise distances (Shashkin, 2010;
Kojevnikov et al., 2021). The exponential decay of correlations resembles the
exponential $\rho$-mixing condition in time-series literature (Bradley, 2005).
After the statement of our main normal approximation result, we present an
example in network auto-regressive model, where Assumption 2 is theoretically
verifiable. Again, the constant $c$ can be relaxed to grow slowly with $n$.

Our final assumption is about the network neighborhood growth. Intuitively,
the network cannot be too densely connected so that the overall dependence is
not too strong.

######  Assumption 3 (Network growth).

There exist constants $c_{1},c>0$ such that

$\max\left\\{\left(\frac{1}{n}\sum_{i}N_{m}^{3}(i)\right)^{1/2}\,,~{}~{}\frac{1}{n}\sum_{i}N_{m}^{2}(i)\right\\}\leq
ce^{c_{1}m}\,,$ (1)

where $N_{m}(i)$ is the size of the $m$-step neighborhood set $\\{j:d(i,j)\leq
m\\}$. The neighborhood growth condition is already interpretable in the
current form. But it can be further simplified in special cases. Let
$N_{m}=n^{-1}\sum_{i}N_{m}(i)$ be the average neighborhood size. Eq. (1) can
hold if $N_{m}$ grows exponentially in $m$ with a small constant $c_{1}$ (or
slower), while the $m$-step degree sequence $\vec{N}_{m}=(N_{m}(i):1\leq i\leq
n)$ is not too heavy-tailed for $m\asymp\log n$. Our theory allows for
exponentially growing neighborhood size, which is much faster than Euclidean
embeddable graphs (Weber, 2020).

######  Theorem 2.1.

If the sequence $(X,\epsilon,A)$ satisfies Assumptions 1, 2 and 3 for
constants $(c_{1},\rho)$ such that $2c_{1}<\log(\rho^{-1})$, then following
holds for the least squares estimate $\hat{\beta}$.

  1. (a)

$(X^{T}\Sigma X)^{-1/2}(X^{T}X)(\hat{\beta}-\beta)\rightsquigarrow N(0,I)\,.$

  2. (b)

There exists a positive constant $C$, such that for $m=C\log n$ we have

$\widehat{X^{T}\Sigma X}^{-1/2}(X^{T}X)(\hat{\beta}-\beta)\rightsquigarrow
N(0,I)\,,$

where

$\widehat{X^{T}\Sigma X}_{rs}=\sum_{i=1}^{n}\sum_{j:d(i,j)\leq
m}x_{ir}x_{js}\hat{\epsilon}_{i}\hat{\epsilon}_{j}.$ (2)

with $\hat{\epsilon}_{i}=Y_{i}-x_{i\cdot}^{T}\hat{\beta}$ being the fitted
residual at sample point $i$.

Now assume that the noise vector $\epsilon$ follows an network autoregressive
(NAR) model

$\epsilon_{i}=\sum_{j}w_{ij}\epsilon_{j}+U_{i}\,,~{}~{}1\leq i\leq n\,,$

where $(U_{i}:i\geq 1)$ is a sequence of independent centered random variables
with uniformly bounded $\ell_{4}$ norm.

######  Proposition 2.2.

If the noise vector $\epsilon$ satisfies the NAR model such that

  1. (i)

$\sup_{i}\sum_{j}|w_{ij}|\equiv\tau<1\,;$ (3)

and

  2. (ii)

$A_{ij}=0$ implies $w_{ij}=0$ for all $1\leq i,j\leq n$,

then it satisfies Assumption 2 with $\rho=\tau^{1/2}$.

##  3 Data-driven estimate for the variance components

Now we turn to inference problems related to the regression coefficients
$\beta$. According to Theorem 2.1, the asymptotic variance of the OLS estimate
$\hat{\beta}$ is $n(X^{T}X)^{-1}(X^{T}\Sigma X)(X^{T}X)^{-1}$. Since $X$ is
observed, we only need to estimate the $p\times p$ matrix $X^{T}\Sigma X$,
which can be achieved by a plug-in formula (2). Here we explain the idea
behind the formula (2). For each $(r,s)\in\\{1,...,p\\}^{2}$, the
$(r,s)$-entry of $X^{T}\Sigma X$ is

$\mathbb{E}\sum_{1\leq i,j\leq n}x_{ir}x_{js}\epsilon_{i}\epsilon_{j}\,.$

The correlation decay condition in Assumption 2(a) implies that the
contribution from the $(i,j)$-pair in the above sum will be negligible when
$d(i,j)$ is sufficiently large. Therefore, we may achieve a better bias-
variance trade-off if we truncate the summation based on the distance between
nodes $i$ and $j$. Here the neighborhood range $m$ is a tuning parameter of
the estimation procedure and needs to be chosen in a data-driven manner.
Interestingly, the optimal choice of $m$ indeed depends on the particular
inference we want to make about $\beta$, as we explain next.

Suppose we want to test $H_{0}:a^{T}\beta=0$ for some $a\in\mathbb{R}^{p}$.
Then the CLT result in Theorem 2.1 implies that, under suitable conditions,

$\sqrt{n}a^{T}(\hat{\beta}-\beta)\stackrel{{\scriptstyle
d}}{{\approx}}N(0,\sigma_{a}^{2})$ (4)

with

$\sigma_{a}^{2}=na^{T}(X^{T}X)^{-1}(X^{T}\Sigma X)(X^{T}X)^{-1}a\,.$

Therefore, the network dependence may have different interaction with the
design matrix $X$ and contrast vector $a$. To illustrate this interaction,
consider a simple case where the design matrix $X=(x_{\cdot 1},~{}x_{\cdot
2},~{}x_{\cdot 3})$ consists of three columns:

  1. 1.

the first column is an intercept column $x_{\cdot 1}=(1,...,1)^{T}$;

  2. 2.

the second column $x_{\cdot 2}\sim N(0,\Sigma)$, independent of everything
else;

  3. 3.

the third column $x_{\cdot 3}\sim N(0,I_{n})$, independent of everything else.

Consider three different choices of vector $a$: $a_{1}=(1,0,0)^{T}$,
$a_{2}=(0,1,0)^{T}$, $a_{3}=(0,0,1)^{T}$.

Assume in addition that the diagonal entries of $\Sigma$ are all $1$. If we
replace $X^{T}X/n$ by its expected value $I_{3}$, then for each $a_{k}$
($k=1,2,3$) the asymptotic variance becomes

$\sqrt{n}a_{k}^{T}(\hat{\beta}-\beta)\stackrel{{\scriptstyle
d}}{{\approx}}N(0,x_{\cdot k}^{T}\Sigma x_{\cdot k}/n)$

where $x_{\cdot k}$ is the $k$th column of $X$. We find that

  * •

when $k=1$, the asymptotic variance equals the entry-wise sum of $\Sigma$,
hence the off-diagonal entries of $\Sigma$ matter when their sum is large.

  * •

when $k=2$, the asymptotic variance approximately equals ${\rm
tr}(\Sigma^{2})$, hence the off-diagonal entries of $\Sigma$ matter when their
squared sum is large.

  * •

when $k=3$, the asymptotic variance approximately equals ${\rm tr}(\Sigma)$,
and the off-diagonal entries of $\Sigma$ do not matter.

The approximations claimed for $k=2,3$ in the above statements follow from the
Hansen-Wright inequality (Hanson & Wright, 1971; Rudelson & Vershynin, 2013).
This example illustrates that the dependence between entries of $\epsilon$ may
or may not bias the inference, depending on how the covariance matrix $\Sigma$
is aligned with the matrix $X(X^{T}X)^{-1}aa^{T}(X^{T}X)^{-1}X^{T}$. Thus we
recommend choosing $m$ according to the vector $a$.

Let $\gamma_{a}\in\mathbb{R}^{n}=\sqrt{n}X(X^{T}X)^{-1}a$. Then the asymptotic
variance of $a^{T}(\hat{\beta}-\beta)$ is
$\sigma_{a}^{2}=\gamma_{a}^{T}\Sigma\gamma_{a}$. The truncated plug-in
estimate at radius $m$ is

$\hat{\sigma}_{a}^{2}(m)=\sum_{i}\sum_{j:d(i,j)\leq
m}\gamma_{a,i}\gamma_{a,j}\hat{\epsilon}_{i}\hat{\epsilon}_{j}\,.$

The question reduces to choosing $m$ just enough to achieve a good trade-off
between the bias and variance of $\hat{\sigma}_{a}^{2}(m)$. Define
$\Delta_{a}(m)\equiv\hat{\sigma}^{2}_{a}(m)-\hat{\sigma}^{2}_{a}(0)$. To
calibrate the variability caused by including off-diagonal entries of
$\Sigma$, we adapt the idea of Moran’s I (Moran, 1950; Lee & Ogburn, 2021),
which aims at gauging whether the difference between $\hat{\sigma}_{a}^{2}(m)$
and $\hat{\sigma}^{2}_{a}(0)$ is due to random fluctuation. Let
$\hat{\epsilon}_{1}^{*},...,\hat{\epsilon}_{n}^{*}$ be a permuted version of
the estimated residuals $\hat{\epsilon}_{1},...,\hat{\epsilon}_{n}$. Define
$\hat{\sigma}_{a}^{2*}(m)$ for the permuted residuals accordingly. After
permutation, the adjacency matrix $A$ no longer captures the correct
dependence structure between the residuals, so the contribution from the off-
diagonal terms
$\Delta_{a}^{*}(m)\equiv\hat{\sigma}_{a}^{2*}(m)-\hat{\sigma}_{a}^{2*}(0)$
would be mostly from random fluctuation.

We therefore choose a task-specific $m$ as follows. Let $T$ be the number of
permutations, and for $1\leq t\leq T$, $\Delta_{a}^{*t}(m)$ is the off-
diagonal contributions calculated for the $t$-th permuted data. We choose $m$
by

$\hat{m}_{a}=\min\left\\{m\geq
0:\frac{1}{T}\sum_{t=1}^{T}\mathds{1}\left(|\Delta_{a}(m+1)|\geq|\Delta_{a}^{*t}(m+1)|\right)\leq
1-\alpha\right\\},$ (5)

where $1-\alpha$ is the confidence level. We used $\alpha=0.05$ in all
numerical studies and the data example. In the case that we have a categorical
variable and $a$ is a multiple column contrast matrix, we shall use the
operator norm of $\Delta_{a}(m)$ to replace the absolute value in (5).

##  4 Simulation

In this section, we demonstrate the finite sample performance of the method,
especially in reducing the inflated Type I error that may arise if the
underlying network structure is not appropriately taken into account.

For a given network with adjacency matrix $A$, and it’s degree-normalized
version $A_{n}$ obtained by dividing each entry of $A$ by its row sum, the
dependence among error terms is generated through a matrix $B$, i.e.,
$\epsilon=B\epsilon_{w}$ for an $n$-dimensional white noise vector
$\epsilon_{w}$. We use Gaussian white noise in this simulation. We generate
$B$ based on auto-regressive models (AR), moving average models (MA), and
direct transmission models (DT). For the AR model, $B=(I-\rho A_{n})^{-1}$.
For the MA model, $B=I+\rho A_{n}$, and in the case of DT model, $B=(I+\rho
A_{n})^{2}$. The DT model extends the MA model by considering the influence of
longer ranges, which is a modification of the setting explored in Lee & Ogburn
(2021). The parameter $\rho$ controls the magnitude of dependence, which is
set to either $0.2$ or $0.4$. Three columns of predictor variables are
considered; $x_{\cdot 1}=1$ (intercept), $x_{\cdot 2}=B\epsilon_{x_{2}}$ and
$x_{\cdot 3}=\epsilon_{x_{3}}$, where $\epsilon_{x_{2}}$ and
$\epsilon_{x_{3}}$ are independently generated standard normal vectors of
length $n$. Without loss of generality in assessing Type I error rate, the
true $\beta$ coefficients are set to zero, and we report the empirical Type I
error under the $\alpha=0.05$ nominal level.

We consider two types of network structure. In Simulation I, the network is
generated from a 4-block Stochastic Block Model with a sample size of $n=300$
and an equal proportion of nodes in each block. The connection probabilities
within and between these groups are represented by a symmetric matrix $\gamma
P\in[0,1]^{4\times 4}$. The parameter $\gamma$ adjusts the overall density of
the network and is set to $0.5,1,$ or $1.5$. The off-diagonal values of $P$ is
set to be 0.005 and the diagonal values are set to be (0.005, 0.010, 0.015,
0.020). Nodes without any connections are removed afterwards. Once $A$ is
generated, it remains fixed throughout the simulation repetitions.

In Simulation II, we utilize the network data and the seven covariates from
our student data example, the details of which are presented in the next
section. The sample size is 244 and all nodes are initially connected to at
least one other node.

| $\rho$ | $m$ |  $\gamma$=0.5 |  $\gamma$=1 |  $\gamma$=1.5
---|---|---|---|---|---
| $x_{\cdot 1}$ | $x_{\cdot 2}$ | $x_{\cdot 3}$ | $x_{\cdot 1}$ | $x_{\cdot 2}$ | $x_{\cdot 3}$ | $x_{\cdot 1}$ | $x_{\cdot 2}$ | $x_{\cdot 3}$
AR | 0.2 | $m=0$ | 0.11 | 0.06 | 0.06 | 0.11 | 0.06 | 0.06 | 0.11 | 0.07 | 0.05
$\hat{m}_{a}$ | 0.07 | 0.06 | 0.06 | 0.07 | 0.05 | 0.06 | 0.06 | 0.07 | 0.05
0.4 | $m=0$ | 0.16 | 0.11 | 0.06 | 0.21 | 0.1 | 0.06 | 0.21 | 0.08 | 0.06
$\hat{m}_{a}$ | 0.05 | 0.08 | 0.06 | 0.07 | 0.07 | 0.06 | 0.08 | 0.07 | 0.06
MA | 0.2 | $m=0$ | 0.11 | 0.07 | 0.06 | 0.12 | 0.07 | 0.07 | 0.12 | 0.06 | 0.05
$\hat{m}_{a}$ | 0.05 | 0.07 | 0.06 | 0.06 | 0.07 | 0.07 | 0.06 | 0.06 | 0.05
0.4 | $m=0$ | 0.15 | 0.09 | 0.06 | 0.17 | 0.07 | 0.07 | 0.17 | 0.06 | 0.07
$\hat{m}_{a}$ | 0.07 | 0.06 | 0.06 | 0.06 | 0.05 | 0.06 | 0.06 | 0.05 | 0.07
DT | 0.2 | $m=0$ | 0.15 | 0.09 | 0.06 | 0.15 | 0.09 | 0.06 | 0.17 | 0.09 | 0.07
$\hat{m}_{a}$ | 0.07 | 0.07 | 0.06 | 0.06 | 0.08 | 0.06 | 0.07 | 0.08 | 0.07
0.4 | $m=0$ | 0.22 | 0.16 | 0.04 | 0.25 | 0.14 | 0.06 | 0.26 | 0.13 | 0.07
$\hat{m}_{a}$ | 0.07 | 0.07 | 0.04 | 0.08 | 0.05 | 0.06 | 0.09 | 0.06 | 0.07
Table 1: Type I error of $\beta$ coefficients in Simulation I. | $\rho$ | m | Intercept | hh.size | age | sex | play | homework | bio.parents
---|---|---|---|---|---|---|---|---|---
AR | 0.2 | m=0 | 0.05 | 0.06 | 0.05 | 0.1 | 0.06 | 0.05 | 0.07
$\hat{m}_{a}$ | 0.05 | 0.06 | 0.05 | 0.08 | 0.06 | 0.05 | 0.07
0.4 | m=0 | 0.06 | 0.06 | 0.06 | 0.2 | 0.06 | 0.06 | 0.09
$\hat{m}_{a}$ | 0.06 | 0.06 | 0.05 | 0.09 | 0.06 | 0.05 | 0.09
MA | 0.2 | m=0 | 0.07 | 0.06 | 0.06 | 0.08 | 0.06 | 0.05 | 0.08
$\hat{m}_{a}$ | 0.06 | 0.06 | 0.06 | 0.07 | 0.06 | 0.05 | 0.09
0.4 | m=0 | 0.06 | 0.06 | 0.05 | 0.16 | 0.05 | 0.06 | 0.09
$\hat{m}_{a}$ | 0.06 | 0.06 | 0.05 | 0.07 | 0.05 | 0.06 | 0.09
DT | 0.2 | m=0 | 0.05 | 0.06 | 0.04 | 0.15 | 0.04 | 0.04 | 0.09
$\hat{m}_{a}$ | 0.05 | 0.06 | 0.04 | 0.07 | 0.04 | 0.04 | 0.09
0.4 | m=0 | 0.07 | 0.09 | 0.06 | 0.24 | 0.05 | 0.06 | 0.08
$\hat{m}_{a}$ | 0.06 | 0.08 | 0.06 | 0.09 | 0.05 | 0.06 | 0.08
Table 2: Type I error of $\beta$ coefficients for Simulation II.

The results of the first simulation are presented in Table 1. The table
consists of nine columns representing the outcomes for testing $\beta_{j}=0$
for three predictive variables ($j=1,2,3$) under three values of the network
density parameter ($\gamma$). The rows correspond to the results obtained from
three different models (AR, MA, DT) and two different values of $\rho$. We
examine type I errors at nominal level $0.05$ under two schemes: no adjustment
($m=0$) and the task-specific selection as described in Section 3
($\hat{m}_{a}$). The maximum $m$ in the search range is set to be 6.
Neglecting the potential dependency due to networks, the type I errors for
$x_{\cdot 1}$ and $x_{\cdot 2}$ are found to be inflated across nearly all of
the settings. The inflation is particularly severe when the network dependence
is strong ($\rho=0.4$) or the network dependency is long range (DT model). The
type I errors for $x_{\cdot 3}$ remain close to the nominal level. This result
is consistent with the phenomenon described in Section 3. The dependence
between entries of $\epsilon$ may or may not bias the inference, depending on
how network dependency is aligned with the matrix
$X(X^{T}X)^{-1}aa^{T}(X^{T}X)^{-1}X^{T}$, where $X$ is the design matrix and
$a$ is the contrast vector corresponding to the hypothesis of interest. In
cases where the Type I error is inflated, applying adjustments using the
recommended selection scheme proves effective in reducing the type I error.
The findings are similar across different levels of network density.

The results for Simulation II are presented in Table 2. The table displays
seven columns representing the Type I errors of testing the coefficients for
each of the seven predictor variables. Among the variables examined, the “sex”
variable consistently exhibits inflated Type I errors across different
settings. As explained in the data analysis section, the “sex” variable has an
obvious alignment with the network structure and therefore the design column
is likely to be aligned with the dependence structure. Adjusting $m$ is shown
to be helpful in reducing the Type I errors.

##  5 Student Data Example

To further illustrate the method, we apply the proposed method to a student
data set with a known network structure. The data consist of survey responses
collected in 2018 from three public primary schools in Tanzania (Schürz et
al., 2020). These responses include students’ school grade scores and their
background characteristics. Additionally, students were asked to provide
information on up to three of their closest friends, including their
interaction patterns such as how often they play or do homework together.

After removing observations with missing data, the size of the three schools
are as follows: 244, 161, and 225. We primarily focus on the largest school,
while considering the other schools as additional data sets to enhance the
interpretation of our findings. Table 3 provides a summary of the data. We
treat the “sex” and “bio.parents” variables as categorical variables. Two
students (nodes) are considered to have an edge in the network if at least one
of them reported the other as a close friend. We note that the data also
contain religious information and the majority are Muslim. Controlling this
variable in the regression model would slightly alter the fitted coefficients
of other variables but not change any of the significant/non-significant
conclusions or the signs of the fitted coefficients. For the purpose of
illustrating the proposed method, all results and discussions for this data
analysis and Simulation II remain the same regardless of whether the religious
variable is controlled or not. The data also contain a variable indicating the
number of children in the household, which is not included in the regression
due to its high collinearity with the household size variable.

Variable | Mean/frequency | sd | Definition
---|---|---|---
School grade score ($Y$) | 451.5 | 112.4 |
Household size | 5.27 | 2.2 | Number of people living in the household
Age | 12.6 | 1.0 |
Sex |  |  |
1: female | 0.52 |  |
0: male | 0.48 |  |
How often play with friends | 2.35 | 0.9 | 0= never, 1=once a week, 2=two or three
How often do homework with friends | 1.47 | 1.2 | times a week, 3=everyday
Living with biological parents |  |  |
0: both | 0.47 |  |
1 : only mother / only father | 0.44 |  |
2 : none | 0.09 |  |
In-network friends | 4.5 | 1.7 | Degree of nodes in friendship network
Table 3: A summary of the variables and the network characteristics.

Figure 1:  Left: Network structure with females represented in gray and males
in orange. Right: Scatter plot between the school grade score of students and
the average score of their friends (Pearson’s correlation coefficient =0.28.)

We consider the student’s school grade score as the response variable and
include other covariates as predictor variables. The authors of the paper
Schürz et al. (2020), where the data set was first released, discovered a
positive correlation between the school grade score of students and those of
their friends. Additionally, the authors emphasized the significant presence
of gender-based segregation within these social networks; see Figure 1. These
findings collectively suggest the need of dealing with the network dependency,
especially for the inference of the “sex” variable. We therefore apply the
proposed method to adjust the network dependency in the inference of
regression coefficients.

| $m=0$ | $\hat{m}_{a}$
---|---|---
(Intercept) | 0.00* | 0.00*
hh.size | 0.09 | 0.35
age | 0.19 | 0.19
sex | 0.02* | 0.16
play | 0.62 | 0.62
homework | 0.03* | 0.03*
bio.parents | 0.21 | 0.21
Table 4: P-values of each covariate with different $m$ selection for the
largest school.

Table 4 shows the p-values for each covariate with and without network
adjustment. When no adjustment is applied, the variables “homework” and “sex”
exhibit statistical significance at the 0.05 level. However, after network
adjustment, the “sex” variable is not statistically significant anymore.

| main school | test school 1 | test school 2
---|---|---|---
(Intercept) | 670.4 | 581.8 | 363.1
hh.size | -5.5 | 3.8 | 7.2
age | -10.0 | -12.7 | 10.9
sex (female) | -33.7 | 7.2 | 10.2
play | -4.0 | -2.8 | -5.7
homework | -13.6 | -2.6 | -4.0
bio.parents1 (only father/mother) | -27.3 | 0.55 | -40.8
bio.parents2 (none) | -31.5 | -24.5 | -48.0
Table 5: Regression coefficients for three schools.

In order to gain a better understanding of this result, we conduct separate
linear regression analyses for each of the other two schools, which have sizes
of 161 and 225, respectively. The regression coefficients are summarized in
Table 5. We observe that the regression coefficients of the “homework”
variable have the same sign across all three schools. However, the signs of
the regression coefficient of the “sex” variable are positive in the main
school and negative in the other schools. Recall that in Simulation II the
“sex” variable had an inflated Type I error rate when data were generated from
a model without the “sex” predictor. These observations indicate that the
significant result for the “sex” variable using regular OLS method ($m=0$)
could be a spurious finding due to the network dependency.

##  6 Discussion

As long as the decay of correlations is exponential as the distance increases,
we show that the ordinary least squares estimate remains consistent and
asymptotically normal even when the neighborhood sizes grow exponentially.
While this result extends the applicability of the popular OLS-based inference
under network dependency, it calls for further investigation and innovation on
adaptive inference, especially in estimating the asymptotic variance. In
practice, the network is given but the decay speed of the correlations is
unknown, making the choice of truncation radius $m$ a challenging task. An
adaptive choice of bias-variance trade-off, contingent upon an unknown
regularity parameter, resembles the model selection problem in non-parametric
and high-dimensional inferences akin to methods like Lepskii’s method and
cross-validation (see Heidenreich et al., 2013; Wu & Wang, 2020, and
references therein). It would be interesting to further develop and study
these methods under the network dependence context.

The Gaussian comparison results for general dependent data beyond Euclidean
embeddable cases are another useful probability tools for statistical
inference, and can potentially be extended in several directions, including
generalized linear models (Bonney, 1987; Daskalakis et al., 2019),
semiparametric models (Bravo, 2022), and high-dimensional data (Kurisu et al.,
2023; Chang et al., 2024).

## Acknowledgements

Jing Lei’s research is partially supported by NSF grants DMS-2015492 and
DMS-2310764. Kehui Chen’s research is partially supported by NSF grant
DMS-2210402.

## References

  * Baldi & Rinott (1989) Baldi, P., & Rinott, Y. (1989).  On normal approximations of distributions in terms of dependency graphs.  The Annals of Probability, (pp. 1646–1650).
  * Bonney (1987) Bonney, G. E. (1987).  Logistic regression for dependent binary observations.  Biometrics, (pp. 951–973).
  * Bradley (2005) Bradley, R. C. (2005).  Basic properties of strong mixing conditions. a survey and some open questions.  Probability Surveys, 2, 107–144.
  * Bravo (2022) Bravo, F. (2022).  Misspecified semiparametric model selection with weakly dependent observations.  Journal of Time Series Analysis, 43(4), 558–586.
  * Chang et al. (2024) Chang, J., Chen, X., & Wu, M. (2024).  Central limit theorems for high dimensional dependent data.  Bernoulli, 30(1), 712–742.
  * Chen & Shao (2004) Chen, L. H., & Shao, Q.-M. (2004).  Normal approximation under local dependence.  The Annals of Probability, 32(3), 1985–2028.
  * Daskalakis et al. (2019) Daskalakis, C., Dikkala, N., & Panageas, I. (2019).  Regression from dependent observations.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, (pp. 881–889).
  * Gaetan & Guyon (2010) Gaetan, C., & Guyon, X. (2010).  Spatial Statistics and Modeling, vol. 90.  Springer.
  * Hanson & Wright (1971) Hanson, D. L., & Wright, F. T. (1971).  A bound on tail probabilities for quadratic forms in independent random variables.  The Annals of Mathematical Statistics, 42(3), 1079–1083.
  * Heidenreich et al. (2013) Heidenreich, N.-B., Schindler, A., & Sperlich, S. (2013).  Bandwidth selection for kernel density estimation: a review of fully automatic selectors.  AStA Advances in Statistical Analysis, 97, 403–433.
  * Huber (1967) Huber, P. J. (1967).  Under nonstandard conditions.  In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability: Weather modification, vol. 5, (p. 221). Univ of California Press.
  * Kojevnikov et al. (2021) Kojevnikov, D., Marmer, V., & Song, K. (2021).  Limit theorems for network dependent random variables.  Journal of Econometrics, 222(2), 882–908.
  * Kurisu et al. (2023) Kurisu, D., Kato, K., & Shao, X. (2023).  Gaussian approximation and spatially dependent wild bootstrap for high-dimensional spatial data.  Journal of the American Statistical Association, (pp. 1–13).
  * Lee & Ogburn (2021) Lee, Y., & Ogburn, E. L. (2021).  Network dependence can lead to spurious associations and invalid inference.  Journal of the American Statistical Association, 116(535), 1060–1074.
  * Liang & Zeger (1986) Liang, K.-Y., & Zeger, S. L. (1986).  Longitudinal data analysis using generalized linear models.  Biometrika, 73(1), 13–22.
  * Moran (1950) Moran, P. A. (1950).  Notes on continuous stochastic phenomena.  Biometrika, 37(1/2), 17–23.
  * Ogburn et al. (2017) Ogburn, E. L., Sofrygin, O., van der Laan, M., & Diaz, I. (2017).  Causal inference for social network data with contagion.  ArXiv e-prints.
  * Pérez-Escudero et al. (2014) Pérez-Escudero, A., Vicente-Page, J., Hinz, R. C., Arganda, S., & De Polavieja, G. G. (2014).  idtracker: tracking individuals in a group by automatic identification of unmarked animals.  Nature methods, 11(7), 743–748.
  * Rudelson & Vershynin (2013) Rudelson, M., & Vershynin, R. (2013).  Hanson-wright inequality and sub-gaussian concentration.  Electronic Communications In Probability, 18, 1–9.
  * Schürz et al. (2020) Schürz, S., Alem, Y., Kocher, M., Carlsson, F., & Lindahl, M. (2020).  Distributional preferences in adolescent peer networks.  Tech. rep., IHS Working Paper.
  * Shashkin (2010) Shashkin, A. (2010).  A berry–esseen type estimate for dependent systems on transitive graphs.  In Advances in Data Analysis, (pp. 151–156). Springer.
  * Weber (2020) Weber, M. (2020).  Neighborhood growth determines geometric priors for relational representation learning.  In International Conference on Artificial Intelligence and Statistics, (pp. 266–276). PMLR.
  * White (1980) White, H. (1980).  A heteroskedasticity-consistent covariance matrix estimator and a direct test for heteroskedasticity.  Econometrica: journal of the Econometric Society, (pp. 817–838).
  * Wu & Wang (2020) Wu, Y., & Wang, L. (2020).  A survey of tuning parameter selection for high-dimensional regression.  Annual review of statistics and its application, 7, 209–226.

##  Appendix A Proof of main results

###  A.1 Proof of Theorem 2.1 part (a):

Since $\hat{\beta}-\beta=(X^{T}X)^{-1}X^{T}\epsilon$, it suffices to prove
that for any $\alpha\in\mathbb{R}^{p}$, $\|\alpha\|_{2}=1$ we have

$\alpha^{T}(X^{T}\Sigma X)^{-1/2}X^{T}\epsilon\rightsquigarrow N(0,1)\,.$

Let $z=\sqrt{n}X(X^{T}\Sigma X)^{-1/2}\alpha$, then $|z_{i}|\leq
c^{3/2}\sqrt{p}=O(1)$ by Assumption 1, and we can write, letting
$\xi_{i}=z_{i}\epsilon_{i}$

$\alpha^{T}(X^{T}\Sigma
X)^{-1/2}X^{T}\epsilon=\frac{\sum_{i=1}^{n}z_{i}\epsilon_{i}}{\sqrt{n}}=\frac{\sum_{i=1}^{n}\xi_{i}}{\sqrt{n}}$

Define $S=\sum_{i}\xi_{i}$ and $S_{i}(m)=\sum_{j:d(i,j)\leq m}\xi_{j}$. Notice
that we often omit $m$ in the parenthesis in these notations whenever its
clear in the context. Let $\sigma^{2}={\rm Var}(S)\equiv n$.

Let $h\in\mathbb{C}_{b}^{3}(\mathbb{R}\mapsto\mathbb{R})$. According to
Stein’s method, we only need to show

$\mathbb{E}\left[\frac{S}{\sigma}h\left(\frac{S}{\sigma}\right)-h^{\prime}\left(\frac{S}{\sigma}\right)\right]\rightarrow
0\,.$

For any $m$,

$\displaystyle(S/\sigma)h(S/\sigma)-h^{\prime}(S/\sigma)$ $\displaystyle=$
$\displaystyle\sum_{i}(\xi_{i}/\sigma)\left[h((S-S_{i})/\sigma)+h(S/\sigma)-h((S-S_{i})/\sigma)\right]-h^{\prime}(S/\sigma)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\sum_{i}\frac{\xi_{i}}{\sigma}h\left(\frac{S-S_{i}}{\sigma}\right)$
$\displaystyle+\sum_{i}\frac{\xi_{i}}{\sigma}\frac{S_{i}}{\sigma}h^{\prime}\left(\frac{S}{\sigma}\right)$
$\displaystyle-\sum_{i}\frac{\xi_{i}}{\sigma}\left(\frac{S_{i}}{\sigma}\right)^{2}\int_{0}^{1}uh^{\prime\prime}\left(\frac{S-S_{i}}{\sigma}+u\frac{S_{i}}{\sigma}\right)du$
$\displaystyle-h^{\prime}\left(\frac{S}{\sigma}\right)$ $\displaystyle=$
$\displaystyle\sum_{i}\frac{\xi_{i}}{\sigma}\frac{S_{i}}{\sigma}h^{\prime}\left(\frac{S}{\sigma}\right)-h^{\prime}\left(\frac{S}{\sigma}\right)$
$\displaystyle+\sum_{i}\frac{\xi_{i}}{\sigma}h\left(\frac{S-S_{i}}{\sigma}\right)$
$\displaystyle-\sum_{i}\frac{\xi_{i}}{\sigma}\left(\frac{S_{i}}{\sigma}\right)^{2}\int_{0}^{1}uh^{\prime\prime}\left(\frac{S-S_{i}}{\sigma}+u\frac{S_{i}}{\sigma}\right)du$

where step $(a)$ follows from the standard first order expansion of
$h(S/\sigma)-h((S-S_{i})/\sigma)$.

We need to show the expectation of each term is small.

#### First term.

The first term equals

$h^{\prime}\left(\frac{S}{\sigma}\right)\left[\frac{\sum_{i}\xi_{i}S_{i}}{\sigma^{2}}-1\right]\,,$

whose expectation is bounded by, letting
$\hat{\sigma}^{2}=\sum_{i}\xi_{i}S_{i}$,

$\displaystyle\|h^{\prime}\|_{\infty}\mathbb{E}\left|\frac{\hat{\sigma}^{2}}{\sigma^{2}}-1\right|$
$\displaystyle\lesssim$ $\displaystyle
n^{-1}\mathbb{E}|\hat{\sigma}^{2}-\sigma^{2}|$ $\displaystyle\lesssim$
$\displaystyle
n^{-1}\left(\mathbb{E}|\hat{\sigma}^{2}-\sigma_{0}^{2}|+|\sigma_{0}^{2}+\sigma^{2}|\right)\,.$

Using the same argument as the variance estimation part, in particular (6) and
(8) we have

  * •

$|\sigma^{2}-\sigma_{0}^{2}|\lesssim n^{2}\rho^{m}$;

  * •

$\mathbb{E}(\hat{\sigma}^{2}-\sigma_{0}^{2})^{2}\lesssim\sum_{i}N_{m}^{3}(i)+n^{2}\rho^{m}\bar{N}_{m}^{2}$
.

So the total contribution of the first term is at most, recall that
$\sigma^{2}=n$, ignoring constant factors,

$\displaystyle
n\theta_{m}+\frac{\left(n^{-1}\sum_{i}N_{m}^{3}(i)\right)^{1/2}}{n^{1/2}}+\theta_{m}^{1/2}\bar{N}_{m}$
$\displaystyle\lesssim$ $\displaystyle
n\rho^{m}+n^{-1/2}e^{c_{1}m}+\rho^{m/2}e^{c_{1}m/2}\,,$

where the inequality follows from Assumption 3. Thus the first term is $o(1)$
when

$\min\left(\frac{m}{\log
n}-\frac{1}{\log(\rho^{-1})}\,,~{}\frac{1}{2c_{1}}-\frac{m}{\log n}\right)$

is positive and bounded away from $0$.

#### Second term.

$\displaystyle\mathbb{E}\xi_{i}h\left(\frac{S_{-i}}{\sigma}\right)$
$\displaystyle=$ $\displaystyle{\rm
Cov}\left(\xi_{i},h\left(\frac{S_{-i}}{\sigma}\right)\right)$
$\displaystyle\leq$
$\displaystyle\|h^{\prime}\|_{\infty}\frac{n}{\sigma}\theta_{m}$

by Assumption 2(c).

The total contribution of the second term is at most

$\frac{n^{2}}{\sigma^{2}}\theta_{m}\lesssim n\theta_{m}=o(1)$

whenver $m/\log n-1/\log(\rho^{-1})$ is bounded away from $0$.

#### Third term.

Since $\|\xi_{i}\|_{3}$ is uniformly bounded by a constant for all $i$, we
have $\|S_{i}\|_{3}\leq N_{m}(i)$. By Hölder inequality, the third term is at
most

$\sum_{i}\frac{N_{m}^{2}(i)}{\sigma^{3}}=\frac{n^{-1}\sum_{i}N_{m}^{2}(i)}{n^{1/2}}\leq
cn^{-1/2}e^{c_{1}m}$

which is $o(1)$ if $\frac{1}{2c_{1}}-\frac{m}{\log n}$ is positive and bounded
away from 0.

###  A.2 Proof of Theorem 2.1 part (b):

Now our goal is to establish

$\widehat{X^{T}\Sigma X}^{-1/2}(X^{T}X)(\hat{\beta}-\beta)\rightsquigarrow
N(0,I)\,.$

for the estimate $\widehat{X^{T}\Sigma X}^{-1/2}$ given in (2) with a suitably
chosen $m$.

We will achieve this by upper bounding the entry-wise estimation error with an
$o(n)$ rate. An $o(n)$ error rate is sufficient because by assumption
$X^{T}\Sigma X$ has minimum and maximum eigenvalues at the order $n$. The
desired result follows by combining part (a) with Slutsky’s theorem.

To simply notation, let $x=x_{\cdot r}$ and $y=x_{\cdot s}$ for $1\leq r<s\leq
p$ be two columns of $X$. We want to approximate

$\Gamma_{rs}=(X^{T}\Sigma X)_{rs}=\sum_{1\leq i,j\leq
n}x_{i}y_{j}\Sigma_{ij}=\mathbb{E}\sum_{i,j}x_{i}y_{j}\epsilon_{i}\epsilon_{j}$

For a given truncation radius $m$, define

$\Gamma_{rs,0}=\sum_{i}\sum_{j:d(i,j)\leq m}x_{i}y_{j}\Sigma_{ij}$

We have, by Assumption 2(a) which simplies $\Sigma_{ij}\leq c\rho^{d(i,j)}$

$\displaystyle\Gamma_{rs,0}-\Gamma_{rs}=$
$\displaystyle\sum_{i}\sum_{j:d(i,j)>m}x_{i}y_{j}\Sigma_{ij}$
$\displaystyle\leq$ $\displaystyle c^{3}n^{2}\rho^{m}$ (6) $\displaystyle=$
$\displaystyle o(n)\,.$

as long as $n\rho^{m}=o(1)$ which is satisfied when $m/\log
n-1/\log(\rho^{-1})$ is positive and bounded away from $0$.

Let $\tilde{\Gamma}_{rs}=\sum_{i}\sum_{j:d(i,j)\leq
m}\epsilon_{i}\epsilon_{j}x_{i}y_{j}$.

Then, using the fact that
$\hat{\epsilon}_{i}-\epsilon_{i}=x_{i\cdot}^{T}(\beta-\hat{\beta})$

$\displaystyle|\hat{\Gamma}_{rs}-\tilde{\Gamma}_{rs}|=$
$\displaystyle\left|\sum_{i}\sum_{j:d(i,j)\leq
m}\left[(\hat{\epsilon}_{i}-\epsilon_{i})(\hat{\epsilon}_{j}-\epsilon_{j})+(\hat{\epsilon}_{i}-\epsilon_{i})\epsilon_{j}+(\hat{\epsilon}_{j}-\epsilon_{j})\epsilon_{i}\right]x_{i}y_{j}\right|$
$\displaystyle\leq$
$\displaystyle\sum_{i}N_{m}(i)\left(c^{4}p\|\hat{\beta}-\beta\|^{2}+2c^{3}\sqrt{p}\|\hat{\beta}-\beta\|\right)$
$\displaystyle\lesssim$ $\displaystyle
ne^{c_{1}m/2}\|\hat{\beta}-\beta\|=o_{P}(n)$

whenever $1/c_{1}-m/\log n$ is positive and bounded away from $0$, because we
have already established in part(a) of Theorem 2.1 that
$\hat{\beta}-\beta=O_{P}(1/\sqrt{n})$.

The last step is to bound $\tilde{\Gamma}_{rs}-\Gamma_{rs,0}$. For
$u=(i,j)\in[n]^{2}$, let
$W_{u}=(\epsilon_{i}\epsilon_{j}-\Sigma_{ij})x_{i}y_{j}$. Let
$\mathcal{U}=\\{(i,j)\in[n]^{2}:d(i,j)\leq m\\}$.

$\displaystyle\mathbb{E}\left(\tilde{\Gamma}_{rs}-\Gamma_{rs,0}\right)^{2}=$
$\displaystyle\mathbb{E}\left(\sum_{u\in\mathcal{U}}W_{u}\right)^{2}$
$\displaystyle=$ $\displaystyle\mathbb{E}\sum_{u,v\in\mathcal{U}}W_{u}W_{v}$
$\displaystyle=$
$\displaystyle\mathbb{E}\sum_{u\in\mathcal{U}}\sum_{v:v\in\mathcal{U},~{}d(u,v)\leq
m}W_{u}W_{v}+\mathbb{E}\sum_{u\in\mathcal{U}}\sum_{v:v\in\mathcal{U},~{}d(u,v)>m}W_{u}W_{v}\,.$
(7)

In the first term, $\mathbb{E}W_{u}W_{v}\leq\|W_{u}\|_{2}\|W_{v}\|_{2}=O(1)$
by Assumption 1. Each $(u,v)$ pair in this sum corresponds to a quadruplet
$(i,j,k,l)$ such that $d(j,i)\leq m$, $d(k,j)\leq m$, $d(k,l)\leq m$. So the
first term is bounded by, up to a constant factor,

$\displaystyle\sum_{i}\sum_{j:d(i,j)\leq m}\sum_{k:d(k,j)\leq
m}\sum_{l:d(k,l)\leq m}1$ $\displaystyle=$
$\displaystyle\sum_{i}\sum_{j:d(i,j)\leq m}\sum_{k:d(k,j)\leq m}N_{m}(k)$
$\displaystyle=$ $\displaystyle\sum_{k}N_{m}(k)\sum_{j:d_{k,j}\leq
m}\sum_{i:d(i,j)\leq m}1$ $\displaystyle=$
$\displaystyle\sum_{k}N_{m}(k)\sum_{j:d_{k,j}\leq m}N_{m}(j)$
$\displaystyle\leq$ $\displaystyle 2\sum_{k}\sum_{j:d(k,j)\leq
m}(N_{m}^{2}(j)+N_{m}^{2}(k))$ $\displaystyle=$ $\displaystyle
4\sum_{j}N_{m}^{3}(j)\,.$

The second term in (7) is bounded by, up to constant factor,
$\rho^{m}|\mathcal{U}|^{2}\lesssim\rho^{m}(\sum_{i}N_{m}(i))^{2}$.

So that, by Assumption 1,

$\displaystyle\mathbb{E}(\tilde{\Gamma}_{rs}-\Gamma_{rs,0})^{2}$
$\displaystyle\lesssim\sum_{j}N_{m}^{3}(j)+\rho^{m}\left[\sum_{j}N_{m}(j)\right]^{2}$
$\displaystyle\lesssim ne^{2c_{1}m}+\rho^{m}n^{2}e^{c_{1}m}\,,$ (8)

which implies that $\tilde{\Gamma}_{rs}-\Gamma_{rs,0}=o(n)$ if
$1/(2c_{1})-m/\log n$ is positive and bounded away from $0$, and
$c_{1}<\log(\rho^{-1})$.∎

Proof of Proposition 2.2

Let $B=W/\tau$, then each row of $B$ has $\ell_{1}$ norm at most $1$.

Now

$\epsilon=(I-\tau B)^{-1}U=\left(\sum_{k=0}^{\infty}\tau^{k}B^{k}\right)U$

Now suppose $i$ and $j$ are two distinct nodes such that $d(i,j)=m$.

Define

$\tilde{\epsilon}_{i}=e_{i}^{T}(I-\tau B)^{-1}U^{(i)}$

where

$U^{(i)}_{j}=U_{j}\mathds{1}_{d(i,j)\leq(m-1)/2}.$

By construction, $\tilde{\epsilon}_{i}$ and $\tilde{\epsilon}_{j}$ are
independent if $d(i,j)\geq m$.

It remains to control $\tilde{\epsilon}_{i}-\epsilon_{i}$. First by definition

$\displaystyle\tilde{\epsilon}_{i}-\epsilon_{i}=\sum_{k=0}^{\infty}\tau^{k}(B^{k})_{i\cdot}(U^{(i)}-U)\,,$

where $(B^{k})_{i\cdot}$ is the $i$th row of $B^{k}$. Because the support of
$B$ is contained in the support of $A$, thus the support of $(B^{k})_{i\cdot}$
is contained in the $k$-step neighborhood of node $i$, therefore we have
$(B^{k})_{i\cdot}(U^{(i)}-U)=0$ whenever $k\leq(m-1)/2$. Thus we have, for
$q\geq 1$

$\displaystyle\|\tilde{\epsilon}_{i}-\epsilon_{i}\|_{q}=$
$\displaystyle\left\|\sum_{k>\frac{m-1}{2}}\tau^{k}(B^{k})_{i\cdot}(U^{(i)}-U)\right\|_{q}$
$\displaystyle\leq$
$\displaystyle\sup_{j}\|U_{j}\|_{q}\sum_{k>(m-1)/2}\tau^{k}\|B^{(k)}_{i\cdot}\|_{1}$
$\displaystyle\lesssim$ $\displaystyle\tau^{(m-1)/2}\,.$

Now we are ready to establish the dependence condition with $\rho=\tau^{1/2}$.

First, if $d(i,j)=m$,

$\displaystyle|\mathbb{E}(\epsilon_{i}\epsilon_{j})|\leq$
$\displaystyle|\mathbb{E}(\tilde{\epsilon}_{i}\tilde{\epsilon}_{j})|+|\mathbb{E}(\epsilon_{i}-\tilde{\epsilon}_{i},\epsilon_{j})|+|\mathbb{E}(\tilde{\epsilon}_{i},\epsilon_{j}-\tilde{\epsilon}_{j})|$
$\displaystyle\leq$ $\displaystyle
0+\|\epsilon_{i}-\tilde{\epsilon}_{i}\|_{2}\|\epsilon_{j}\|_{2}+\|\tilde{\epsilon}_{i}\|_{2}\|\epsilon_{j}-\tilde{\epsilon}_{j}\|_{2}$
$\displaystyle\lesssim$ $\displaystyle\tau^{(m-1)/2}$

and similarly,

$\displaystyle|\mathbb{E}(\epsilon_{i}\epsilon_{j}^{2})|\leq$
$\displaystyle|\mathbb{E}(\tilde{\epsilon}\tilde{\epsilon}_{j}^{2})|+|\mathbb{E}(\epsilon_{i}-\tilde{\epsilon}_{i})\epsilon_{j}^{2}|+|\mathbb{E}\tilde{\epsilon}_{i}(\epsilon_{j}^{2}-\tilde{\epsilon}_{j}^{2})|$
$\displaystyle\leq$ $\displaystyle
0+\|\tilde{\epsilon}_{i}-\epsilon_{i}\|_{3}\|\epsilon_{j}\|_{3}^{2}+\|\tilde{\epsilon}_{i}\|_{3}\|(\epsilon_{j}\|_{3}+\|\tilde{\epsilon}_{j}\|_{3})\|\epsilon_{j}-\tilde{\epsilon}_{j}\|_{3}$
$\displaystyle\lesssim$ $\displaystyle\tau^{(m-1)/2}$

And if $d(\\{i,j\\},\\{k,l\\})=m$,

$\displaystyle|{\rm
Cov}(\epsilon_{i}\epsilon_{j},\epsilon_{k}\epsilon_{l})|\leq$
$\displaystyle|{\rm
Cov}(\tilde{\epsilon}_{i}\tilde{\epsilon}_{j},\tilde{\epsilon}_{k}\tilde{\epsilon}_{l})|+|{\rm
Cov}(\epsilon_{i}\epsilon_{j}-\tilde{\epsilon}_{i}\tilde{\epsilon}_{j},\epsilon_{k}\epsilon_{l})|+|{\rm
Cov}(\tilde{\epsilon}_{i}\tilde{\epsilon}_{j},\epsilon_{k}\epsilon_{l}-\tilde{\epsilon}_{k}\tilde{\epsilon}_{l})|$
$\displaystyle\lesssim$ $\displaystyle\tau^{(m-1)/2}$

Let $\tilde{S}_{A}=\sum_{j\in A}\tilde{\xi}_{j}$. When $d(i,A)=m$,

$\displaystyle|{\rm Cov}(\epsilon_{i},h(tS_{A}))|\leq$ $\displaystyle|{\rm
Cov}(\tilde{\epsilon}_{i},h(t\tilde{S}_{A})|+|{\rm
Cov}(\epsilon_{i}-\tilde{\epsilon}_{i},h(tS_{A}))|+|{\rm
Cov}(\tilde{\epsilon}_{i},h(tS_{A})-h(t\tilde{S}_{A}))|$ $\displaystyle\leq$
$\displaystyle
0+\|\epsilon_{i}-\tilde{\epsilon}_{i}\|_{1}\|h\|_{\infty}+\|\tilde{\epsilon}\|_{2}t\|S_{A}-\tilde{S}_{A}\|_{2}\|h^{\prime}\|_{\infty}$
$\displaystyle\lesssim$ $\displaystyle\tau^{(m-1)/2}(1+t|A|)\,.$


# A Note on Rules Achieving Optimal Metric Distortion

Jannik Peters<EMAIL_ADDRESS>
###### Abstract

In this note, we uncover three connections between the metric distortion
problem and voting methods and axioms from the social choice literature.

##  1 Introduction

The distortion of voting rules was introduced by Procaccia and Rosenschein
(2006) as a way to implicitly measure the utilitarian performance of a voting
rule. The distortion of a voting rule given some ordinal preference profile,
is the worst-case approximation factor to the social welfare this voting rule
can achieve, among all utility profiles consistent with the ordinal
preferences. Without any additional assumptions on these utility profiles, no
voting rule can achieve any constant factor guarantees. This motivated
Anshelevich et al. (2018) to study the special case of metric utility
profiles, i.e., utility profiles for which a metric space exists, in which the
voters and candidates lie, such that the utility of a voter for a candidate is
precisely the distance between them. For such utility profiles, a lower bound
of $3$ on the distortion of any rule was quickly established, while it was
also shown that the Copeland rule (in fact, any rule selecting from the
uncovered set) achieves a distortion of $5$. This upper bound of $5$ was
subsequently lowered by Kempe (2020) and Munagala and Wang (2019), until
finally Gkatzelis et al. (2020) achieved an upper bound of $3$ through a
rather “complex” rule dubbed Plurality Matching. This rule was subsequently
simplified by Kızılkaya and Kempe (2022) to the so-called Plurality Veto rule.

In this paper, we show that the Plurality Matching and Plurality Veto rules
are related closely to three different settings in social choice: (i) The
Proportional Veto Core by Moulin (1981), (ii) the concept of Proportionality
for Solid Coalitions from multiwinner voting (see, for instance, Aziz and Lee
(2020) or Brill and Peters (2023)), and (iii) the Matching under Preferences
setting (Bogomolnaia and Moulin, 2001). In fact, we give an equivalent
formulation of the Plurality Matching concept in all three settings. Using
this equivalence, the Plurality Veto rule, the Vote-by-Veto rule (Moulin,
1981), and the Serial Dictatorship rule (Abdulkadiroğlu and Sönmez, 1998) are
instantiations of the same rule. Further, Phragmén’s Ordered Rule (Janson,
2016), Probabilistic Serial (Bogomolnaia and Moulin, 2001), and the “Veto by
consumption” rule (Ianovski and Kondratev, 2021) can also be treated as
instantiations of the same rule and thus lead to a new rule with an optimal
metric distortion of $3$.

##  2 Notation

Throughout the paper, we assume that we are given a set $N=[n]$ of voters and
a set $C=\\{c_{1},\dots,c_{m}\\}$ of candidates. Further, each voter $i\in N$
has a strict and complete _preference list_ $\succ_{i}\subseteq C\times C$
with $\succ=(\succ_{i})_{i\in N}$ forming the preference profile. Together,
$(N,C,\succ)$ form our election instance. For a given profile $\succ$, we let
$\succ^{R}$ be the preference profile such that $c\;\succ^{R}_{i}\;c^{\prime}$
if and only if $c^{\prime}\succ_{i}c$, i.e., the reversed preference profile.
Further, we write $c_{i}\succeq c_{j}$ if and only if $c_{i}\succ c_{j}$ or
$c_{i}=c_{j}$. For a set $N^{\prime}\subseteq N$ of voters and sets
$C^{\prime},C^{\prime\prime}\subseteq C$ of candidates we write that
$C^{\prime}\succ_{N^{\prime}}C^{\prime\prime}$ if and only if
$c^{\prime}\succ_{i}c^{\prime\prime}$ for all $i\in N^{\prime}$,
$c^{\prime}\in C^{\prime}$, and $c^{\prime\prime}\in C^{\prime\prime}$.

Additionally, we need the notion of cloned candidates. For a given frequency
function $f\colon C\to\mathbb{N}_{0}$, the instance $(N,C^{f},\succ^{f})$ is
the instance in which every candidate $c$ is replaced by $f(c)$ clones in
every preference list. The ranking between the clones is arbitrary but fixed
across voters, and candidates with $f(c)=0$ are deleted. We denote by
$\operatorname{plu}(c)$ the plurality score of candidate $c$, by
$\operatorname{bot}_{i}(C^{\prime})$ the worst ranked candidate $c\in
C^{\prime}$ by voter $i$. Hence, the instance
$(N,C^{\operatorname{plu}},\succ^{\operatorname{plu}})$ denotes the instance
in which every candidate is cloned as many times as they appear first in any
preference profile. We not that for this special instance $n=m$ holds.

For any $c\in C$ and $N^{\prime}\subseteq N$ we define

$D_{c}(N^{\prime})\coloneqq\\{c^{\prime}\in C\colon
c\succeq_{i}c^{\prime}\text{ for some }i\in N^{\prime}\\}$

as the set of all candidates which are not ranked better than $c$ by at least
one voter in $N^{\prime}$. Note that, by definition, $c\in D_{c}(N^{\prime})$
for all $c\in C$ and non-empty $N^{\prime}\subseteq N$.

We say that a utility function $u\colon C\to\mathbb{R}^{+}$ is consistent with
a preference list $\succ$ if $c_{i}\succ c_{j}$ implies $u(c_{i})\leq
u(c_{j})$, i.e., the goal is to select the candidate with the lowest social
cost. A utility profile $U=(u_{i})_{i\in N}$ is a collection of utility
functions such that $u_{i}$ is consistent with $\succ_{i}$. For a given
utility profile $U$ and candidate $c$ the _social welfare_ of $c$ is
$\operatorname{sw}(c,U)\coloneqq\sum_{i\in N}u_{i}(c)$.

We call a utility profile _metric_ if there exists a metric space $(N\cup
C,d)$ with $u_{i}(c)=d(i,c)$, i.e., if there is a function $d\colon(N\cup
C)^{2}\to\mathbb{R}^{+}$ such that for any $i,j,k\in N\cup C$ it holds that
(i) $d(i,j)=0$ if and only if $i=j$, (ii) $d(i,j)=d(j,i)$, and (iii)
$d(i,k)\leq d(i,j)+d(j,k)$.

Given a preference profile $\succ$, let $\mathcal{U}(\succ)$ be the set of all
metric utility profiles consistent with the preference profile. The _metric
distortion_ of a given candidate is now the worst-case social welfare ratio of
this candidate compared to the social welfare winner, over all consistent
metric utility profiles, that is

$\operatorname{dist}(c,\succ)=\sup_{U\in\mathcal{U}(\succ)}\frac{\operatorname{sw}(c,U)}{\min_{c^{\prime}\in
C}\operatorname{sw}(c^{\prime},U)}.$

The metric distortion of a voting rule is the worst-case distortion of any
candidate the rule selects over all possible preference profiles.

##  3 Plurality Matching and Domination Graphs

To tackle the problem of designing a voting rule achieving a metric distortion
of exactly $3$, Gkatzelis, Halpern, and Shah (2020) introduced the Plurality
Matching rule, based on the so-called domination graph.

######  Definition 1.

Given a candidate $c$, the domination graph $G(c)=(V\cup C,E_{c})$ is the
bipartite graph consisting of the set of voters on the one side, the set of
candidates on the other side, with an edge between voter $i$ and candidate
$c^{\prime}$ if and only if $c\succeq_{i}c^{\prime}$.

A _fractional perfect matching_ is a function $M\colon
E_{c}\to\mathbb{R}_{\geq 0}$ with $\sum_{e\in\delta(i)}M(e)=1$ for all $i\in
V$ and $\sum_{e\in\delta(c)}M(e)=\frac{n}{m}$ for all $c\in C$. As one of
their main contributions, Gkatzelis et al. (2020) were able to show that there
is always a candidate $c$ whose domination graph has a fractional perfect
matching.

######  Theorem 1 ((Gkatzelis et al., 2020)).

For any election, there is a candidate $c$ such that $G(c)$ admits a
fractional perfect matching. Such a candidate can be found in polynomial time.

Whether $G(c)$ admits a fractional perfect matching can be verified in
polynomial time using a generalization of Hall’s Theorem.

######  Lemma 2 ((Gkatzelis et al., 2020)).

Given a candidate $c$, the domination graph $G(c)$ admits a fractional perfect
matching if and only if for any $N^{\prime}\subseteq N$, it holds that $\lvert
D_{c}(N^{\prime})\rvert\geq\frac{m\lvert N^{\prime}\rvert}{n}$.

To relate this to the distortion problem, Gkatzelis et al. (2020) further
showed that for the special case in which candidates are cloned according to
their plurality score, any candidate admitting such a fractional perfect
matching has metric distortion of at most $3$.

######  Theorem 3 ((Gkatzelis et al., 2020)).

Given an instance $(N,C,\succ)$, consider the instance
$(N,C^{\operatorname{plu}},\succ^{\operatorname{plu}})$ in which every
candidate $c$ appears as many times as they are ranked first by a voter. Any
candidate $c$ whose domination graph $G(c)$ admits a fractional perfect
matching in the instance
$(N,C^{\operatorname{plu}},\succ^{\operatorname{plu}})$, has metric distortion
of at most $3$ in $(N,C,\succ)$.

We call such a candidate a _plurality matching winner_. As such a candidate
always exists according to Theorem 1, there is also always a candidate with
metric distortion of at most $3$. However, while this candidate always exists,
selecting it via simply iterating over all candidates and checking whether
their domination graph admits such a matching, is somewhat unsatisfying and
unnatural when comparing it to other voting rules, especially as it is not
obvious (without the involved proof of Gkatzelis et al. (2020)), that such a
candidate exists.

This motivated Kızılkaya and Kempe (2022) to introduce a simple rule which can
always select a plurality matching winner: The plurality veto rule.

1 Create instance $(N,C^{\operatorname{plu}},\succ^{\operatorname{plu}})$;

2 for  _$i\in[n-1]$_ do

3 $C^{\operatorname{plu}}\leftarrow
C^{\operatorname{plu}}\setminus\operatorname{bot}_{i}(C^{\operatorname{plu}})$

4 end for

5return last remaining candidate in $C^{\operatorname{plu}}$;

ALGORITHM 1 Plurality Veto Rule

We state the rule in Algorithm 1 for the special case of $n=m$ in the instance
$(N,C^{\operatorname{plu}},\succ^{\operatorname{plu}})$. For the general
version, called fractional veto rule, which can also be used to show Theorem
1, see the paper by Kızılkaya and Kempe (2022).

##  4 The Proportional Veto Core

Unrelated to the previous distortion considerations, Moulin (1981, 1982)
introduced the proportional veto core, which we present here in the
formulation of Ianovski and Kondratev (2021). The goal of the proportional
veto core is to give groups of voters the right to veto candidates they do not
like. The power to veto should be distributed in a proportional fashion: an
$\alpha$-fraction of the voters should be able to veto an $\alpha$-fraction of
the candidates. To formalize this, for any group of voters
$N^{\prime}\subseteq N$, we say that the _veto power_ of $N^{\prime}$ is
$v(N^{\prime})=\lceil\frac{m\lvert N^{\prime}\rvert}{n}\rceil-1$. A candidate
$c$ is now considered to be vetoed, if there is some group $N^{\prime}$ of
voters which rank at least $m-v(N^{\prime})$ candidates all better than $c$,
that is, they could veto $v(N^{\prime})$ candidates together with $c$.

######  Definition 2.

A candidate $c$ is _vetoed_ if there is some set $N^{\prime}\subseteq N$ of
voters and set $C^{\prime}\subseteq C$ of candidates with $c\notin C^{\prime}$
such that $\lvert C^{\prime}\rvert\geq m-v(N^{\prime})$ and
$C^{\prime}\succ_{N^{\prime}}C\setminus C^{\prime}$. The _proportional veto
core_ consists of all alternatives which are not vetoed.

The proportional veto core is non-empty (Moulin, 1981, 1982) and can be
computed using the voting by veto tokens rule introduced by Moulin (1981) and
further analyzed by Ianovski and Kondratev (2021). This rule works exactly the
same as the fractional veto rule of Kızılkaya and Kempe (2022) and can be
computed in polynomial time (Ianovski and Kondratev, 2021). Additionally, both
Moulin (1983) and Ianovski and Kondratev (2021, Proposition 21) showed that a
candidate is in the proportional veto core if and only if it can be computed
by the voting by veto tokens rule.

Further, Ianovski and Kondratev (2021) introduced the “Vote by consumption”
rule, which also selects from the proportional veto core. Intuitively, their
rule works as follows: all voters simultaneously and with the same speed give
score to their lowest ranked candidate. Once a candidate reaches a score of
$1$ this candidate is eliminated and the voters move on to their next worst
candidate. The last candidate remaining wins. As pointed out by Ianovski and
Kondratev (2021), this rule is anonymous and can be computed in polynomial
time as well.

##  5 Proportionality for Solid Coalitions

Next, we turn to another equivalent formulation of the proportional veto core.
For this, we use the well-known notion of _proportionality for solid
coalitions (PSC)_ (Dummett, 1984). It was introduced in the context of
proportional committee selection with ranked preferences, as a way to
axiomatically measure whether a committee is proportional. In the committee
selection problem, instead of selecting a single winner, a set of $k$ winners
is selected. Sets $W\subseteq C$ are referred to as committees.

######  Definition 3.

A committee $W$ of size $k$ satisfies weak Droop proportionality for solid
coalitions (weak-PSC) if there is no group $N^{\prime}$ of voters and set
$C^{\prime}$ of candidates with $\lvert N^{\prime}\rvert>\frac{\lvert
C^{\prime}\rvert n}{k+1}$ such that $C^{\prime}\setminus W\neq\emptyset$ and
$C^{\prime}\succ_{N^{\prime}}C\setminus C^{\prime}$.

In a nutshell, if a group of voters agrees on a prefix in their rankings and
could afford this prefix, the candidates in the prefix need to be included in
the committee. Rules satisfying this notion include Phragmén’s sequential rule
for ordinal ballots (Janson, 2016), the Droop variants of the expanding
approvals rule (Aziz and Lee, 2020), and the well-studied Single Transferable
Vote (STV) (Tideman, 1995).

Interestingly enough, Phragmén’s sequential rule for ordinal ballots behaves
equivalently to veto-by-consumption run on the reversed preferences profile:
the first $k$ candidates discarded by veto-by-consumption on profile
$\succ^{R}$, are exactly the $k$ candidates elected by Phragmén’s sequential
rule.

This is no coincidence, however, as we show in the next section.

##  6 Equivalence Result

Here we show our main result: For a candidate $c$ it is equivalent that $c$ is
selected by the plurality matching rule, is in the proportional veto core, and
that the committee $C\setminus\\{c\\}$ of size $m-1$ satisfies weak-PSC in the
reversed preference profile.

######  Theorem 4.

Given an election instance $(N,C,\succ)$ and candidate $c\in C$, the following
three statements are equivalent.

  * (i)

The domination graph $G(c)$ of candidate $c$ admits a fractional perfect
matching.

  * (ii)

Candidate $c$ is in the proportional veto core.

  * (iii)

The committee $C\setminus\\{c\\}$ satisfies weak-PSC in the instance
$(N,C,\succ^{R})$.

###### Proof.

(i) $\Rightarrow$ (ii): First, assume that $c$ is not in the proportional veto
core. Then there is a group $N^{\prime}\subseteq N$ of voters and set
$C^{\prime}\subseteq C$ of candidates with $c\notin C^{\prime}$, $\lvert
C^{\prime}\rvert\geq m-\lceil\frac{m\lvert N^{\prime}\rvert}{n}\rceil+1$, and
$C^{\prime}\succ_{N^{\prime}}\\{c\\}$. Thus, we know that $\lvert
D_{c}(N^{\prime})\rvert\leq\lceil\frac{m\lvert
N^{\prime}\rvert}{n}\rceil-1<\frac{m\lvert N^{\prime}\rvert}{n}$ and by Lemma
2 the domination graph $G(c)$ does not admit a perfect fractional matching.

(ii) $\Rightarrow$ (iii): Next, assume that the committee $C\setminus\\{c\\}$
does not satisfy weak-PSC in the instance $(N,C,\succ^{R})$. Thus, there is a
set $N^{\prime}$ of voters and a set $C^{\prime}$ of candidates with $c\in
C^{\prime}$ such that $C^{\prime}\succ_{N^{\prime}}C\setminus C^{\prime}$ and
$\lvert C^{\prime}\rvert<\frac{\lvert N^{\prime}\rvert(k+1)}{n}=\frac{\lvert
N^{\prime}\rvert m}{n}$. Since, $\lvert C^{\prime}\rvert$ is integral, we also
get that $\lvert C\setminus C^{\prime}\rvert=m-\lvert C^{\prime}\rvert\geq
m-\lceil\frac{m\lvert N^{\prime}\rvert}{n}\rceil+1$ and hence, the set
$C\setminus C^{\prime}$ together with $N^{\prime}$ blocks $c$.

(iii) $\Rightarrow$ (i): Finally, we assume that the domination graph of $c$
does not admit a fractional perfect matching. Then by Lemma 2 there is some
group $N^{\prime}$ of voters with $\lvert
D_{c}(N^{\prime})\rvert<\frac{m\lvert N^{\prime}\rvert}{n}$, and therefore the
candidate set $\\{c^{\prime}\in C\colon
c\succ_{N^{\prime}}c^{\prime}\\}=\\{c^{\prime}\in C\colon
c^{\prime}\;\succ^{R}_{N^{\prime}}\;c\\}$ together with $N^{\prime}$ witnesses
a weak-PSC violation. ∎

Thus, all rules for either selecting from the proportional veto core or
selecting committees satisfying weak-PSC can also be turned into rules
achieving a metric distortion of $3$ by applying them to the instance
$(N,C^{\operatorname{plu}},\succ^{\operatorname{plu}})$. These include the
anonymous veto-by-consumption rule (or Phragmén’s sequential rule for ordinal
ballots), but also committee selection rules such as STV or EAR, which satisfy
weak-PSC (Aziz and Lee, 2020).

##  7 Matching under Preferences

Finally, we turn to our fourth setting: Matching under Preferences. More
specifically, we investigate the random assignment problem of Bogomolnaia and
Moulin (2001). Like Ianovski and Kondratev (2021), we observe that the
Probabilistic Serial rule of Bogomolnaia and Moulin (2001) can be seen as
running Phragmén’s sequential rule for $k=m$ (or the veto-by-consumption rule
for the reversed preference profile) and interpreting the “eaten part” as the
probabilities.

To stay consistent with the notation, we also assume that we are given a set
$N$ of voters, $C$ of candidates and a preference profile $\succ$. Further, we
assume that we are given a restriction $k$ on the number of candidates
matched. Now, a random assignment $\mu\colon N\times C\to\mathbb{R}_{\geq 0}$
is a function assigning each voter-candidate pair a probability to be matched.
That is, $\sum_{i\in N}\mu(i,c)\leq 1$ for each $c\in C$. Further, to
implement the constraint of at most $k$ candidates being matched, we assume
that $\sum_{c\in C}\mu(i,c)=\frac{k}{n}$ for each $i\in N$, that is, each
voter is matched with the same probability. We note that this is the same as a
price system in the committee selection literature, (Peters and Skowron, 2020;
Brill and Peters, 2023).

Such a random assignment can also be seen as a lottery over matchings. Given a
set of matchings $M_{1},\dots,M_{\ell}$ and probabilities
$p_{1},\dots,p_{\ell}\in(0,1]$ with $\sum_{i\in[\ell]}p_{i}=1$, we say that
this set implements $\mu$ if $\mu(i,c)=\sum_{j\in[\ell]\colon M(i)=c}p_{j}$.
The support of $\mu$ are now all matchings $M$ is of size $k$ that are in some
set implementing $\mu$.

Finally, we note that the two popular assignment mechanisms, Random Priority
and Probabilistic Serial, can easily be adapted to this setting of matching at
most $k$ items: Random Priority by ending the process after $k$ items have
been picked, and Probabilistic Serial by only running it for a time of
$\frac{k}{n}$.

Random Priority and Probabilistic Serial are both known to satisfy ex-post
efficiency, i.e., the actual allocations they randomize over are Pareto
efficient. We formalize this as follows.

######  Definition 4.

A matching $M$ of size $k$ is _Pareto efficient_ , if there is no matching
$M^{\prime}$ of size $k$ such that $M^{\prime}(i)\succeq_{i}M(i)$ for every
$i\in N$ and $M^{\prime}(i)\succ_{i}M(i)$ for some $i\in N$.

Further, we say that a random assignment is _ex-post efficient_ if every
matching in its support is Pareto efficient.

We can show that Pareto optimality gives us another equivalent formulation of
the proportional veto core, at least in the case $n=m$. Thus, any ex-post
Pareto optimal mechanism can also be used to select from the proportional veto
core in this special case.

######  Theorem 5.

Given a voting instance $(N,C,\succ)$ with $\lvert N\rvert=\lvert C\rvert$, a
candidate $c$ is in the proportional veto core if and only if in the instance
$(N,C,\succ^{R})$ there is a Pareto optimal matching of size $m-1$ matching
every candidate in $C\setminus\\{c\\}$.

###### Proof.

First, if $c$ is not in the proportional veto core, there is a group
$N^{\prime}$ of voters and $C^{\prime}$ of candidates with $\lvert
C^{\prime}\rvert\geq m-\lceil\frac{m\lvert
N^{\prime}\rvert}{n}\rceil+1=n-\lvert N^{\prime}\rvert+1$ and
$C^{\prime}\succ_{N^{\prime}}\\{c\\}$ and therefore
$\\{c\\}\succ^{R}C^{\prime}$. Since the members of $N^{\prime}$ are matched to
at least $\lvert N^{\prime}\rvert-1$ items, there must be one voter in
$N^{\prime}$ matched to someone worse than $c$. Hence, this matching was not
Pareto optimal, since this voter could have been matched to $c$ instead.

On the other hand, assume that there is no Pareto optimal matching of size
$m-1$ matching every candidate in $C\setminus\\{c\\}$. It is easy to see that
this is equivalent to there not being any matching of size $m-1$ which only
matches voters to candidates they prefer to $c$ (for a proof see (Hosseini et
al., 2021, Theorem 2)). Thus, by Hall’s Theorem, there must be a set
$N^{\prime}\subseteq N$ of voters with $C^{\prime}\coloneqq\\{c^{\prime}\in
C\colon c^{\prime}\succ_{i}c\text{ for some }i\in N^{\prime}\\}$ such that
$\lvert C^{\prime}\rvert\leq\lvert N^{\prime}\rvert-2$. However, then
$C^{\prime}$ and $N^{\prime}$ witness a violation of $c$ being in the
proportional veto core. ∎

While this applies to the special case relevant for distortion (in which
$n=m$) it does not do so in general. For example, consider an instance with
$4$ voters and $3$ candidates. Two of the voters have the ranking $c_{1}\succ
c_{2}\succ c_{3}$ while two other ones have the ranking $c_{3}\succ c_{2}\succ
c_{1}$. Here, two voters have a veto power of $3-\lceil\frac{3\cdot
2}{4}\rceil+1=2$. Thus, neither $c_{1}$ nor $c_{3}$ is in the proportional
veto core of this instance. However, the matching which matches the first two
voters to $c_{3}$ and $c_{2}$ is Pareto optimal in the instance $\succ^{R}$.
Hence, we leave a generalization beyond the case of $n=m$ for future work.

Further, we note that by the equivalence between Pareto optimality and the
serial dictatorship mechanism (Abdulkadiroğlu and Sönmez, 1998), the existence
of a Pareto optimal matching of size $m-1$ matching every candidate in
$C\setminus\\{c\\}$ is equivalent to there being a permutation
$\sigma(1),\dots,\sigma(n)$ of the voters, such that the last voter
$\sigma(n)$ picks candidate $c$ in the serial dictatorship mechanism, thus
also drawing the connection to matchings of size $m$.

##  8 Conclusion and Outlook

We have shown that the domination graph concept of Gkatzelis et al. (2020) and
the plurality veto rule of Kızılkaya and Kempe (2022) are inherently related
to three concepts from social choice: The proportional veto core,
proportionality for solid coalitions, and Pareto optimal matchings. This gives
rise to several more possible algorithms achieving an optimal metric
distortion of $3$. Most prominently, Phragmén’s ordinal method (or,
equivalently, veto-by-consumption or probabilistic serial) can be turned into
such a rule, by cloning each candidate according to their plurality score and
then picking the last candidate elected by Phragmén’s ordinal method for $k=n$
(or, equivalently, the only remaining one for $k=n-1$).

So far, all methods known to achieve a metric distortion of $3$ rely on this
cloning step. Thus, it would be an interesting direction for future research
to explore whether there is a voting rule with distortion $3$ which works
without this step.

### Acknowledgments

I thank Markus Brill, David Kempe, Fatih Kızılkaya, Dominik Peters, and
Alexandros Voudouris for helpful discussions. This research is supported by
the Deutsche Forschungsgemeinschaft (DFG) under the grant BR 4744/2-1 and the
Graduiertenkolleg “Facets of Complexity” (GRK 2434).

## References

  * Abdulkadiroğlu and Sönmez [1998] A. Abdulkadiroğlu and T. Sönmez.  Random serial dictatorship and the core from random endowments in house allocation problems.  _Econometrica_ , 66(3):689–701, 1998.
  * Anshelevich et al. [2018] E. Anshelevich, O. Bhardwaj, E. Elkind, J. Postl, and P. Skowron.  Approximating optimal social choice under metric preferences.  _Artificial Intelligence_ , 264:27–51, 2018.
  * Aziz and Lee [2020] H. Aziz and B. E. Lee.  The expanding approvals rule: improving proportional representation and monotonicity.  _Social Choice and Welfare_ , 54:1–45, 2020.
  * Bogomolnaia and Moulin [2001] A. Bogomolnaia and H. Moulin.  A new solution to the random assignment problem.  _Journal of Economic Theory_ , 100(2):295–328, 2001.
  * Brill and Peters [2023] M. Brill and J. Peters.  Robust and verifiable proportionality axioms for multiwinner voting.  In _Proceedings of the 24th ACM Conference on Economics and Computation (ACM-EC)_ , 2023.  Forthcoming.
  * Dummett [1984] M. Dummett.  _Voting Procedures_.  Oxford University Press, 1984.
  * Gkatzelis et al. [2020] V. Gkatzelis, D. Halpern, and N. Shah.  Resolving the optimal metric distortion conjecture.  In _Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS)_ , pages 1427–1438, 2020.
  * Hosseini et al. [2021] H. Hosseini, V. Menon, N. Shah, and S. Sikdar.  Necessarily optimal one-sided matchings.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 5481–5488, 2021.
  * Ianovski and Kondratev [2021] E. Ianovski and A. Kondratev.  Computing the proportional veto core.  In _Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 5489 – 5496, 2021.
  * Janson [2016] S. Janson.  Phragmén’s and Thiele’s election methods.  Technical report, arXiv:1611.08826 [math.HO], 2016.
  * Kempe [2020] D. Kempe.  An analysis framework for metric voting based on lp duality.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 2079–2086, 2020.
  * Kızılkaya and Kempe [2022] F. E. Kızılkaya and D. Kempe.  Pluralityveto: A simple voting rule achieving optimal metric distortion.  In _Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 349 – 355, 2022.
  * Moulin [1981] H. Moulin.  The proportional veto principle.  _Review of Economic Studies_ , 48(3), 1981.
  * Moulin [1982] H. Moulin.  Voting with proportional veto power.  _Econometrica_ , 50(1):145–162, 1982.
  * Moulin [1983] H. Moulin.  _The Strategy of Social Choice_.  North-Holland, 1983.
  * Munagala and Wang [2019] K. Munagala and K. Wang.  Improved metric distortion for deterministic social choice rules.  In _Proceedings of the 20th ACM Conference on Economics and Computation (ACM-EC)_ , pages 245–262, 2019.
  * Peters and Skowron [2020] D. Peters and P. Skowron.  Proportionality and the limits of welfarism.  In _Proceedings of the 21st ACM Conference on Economics and Computation (ACM-EC)_ , pages 793–794. ACM Press, 2020.
  * Procaccia and Rosenschein [2006] A. Procaccia and J. Rosenschein.  The distortion of cardinal preferences in voting.  In _International Workshop on Cooperative Information Agents (CIA)_ , pages 317—331, 2006.
  * Tideman [1995] N. Tideman.  The single transferable vote.  _Journal of Economic Perspectives_ , 9(1):27–38, 1995.