# Locally Fair Partitioning

Pankaj K. Agarwal  Shao-Heng Ko  Kamesh Munagala  Erin Taylor  Department of
Computer Science, Duke University
{pankaj, sk684, kamesh<EMAIL_ADDRESS>
###### Abstract

We model the societal task of redistricting political districts as a
partitioning problem: Given a set of $n$ points in the plane, each belonging
to one of two parties, and a parameter $k$, our goal is to compute a partition
$\Pi$ of the plane into regions so that each region contains roughly
$\sigma=n/k$ points. $\Pi$ should satisfy a notion of “local” fairness, which
is related to the notion of core, a well-studied concept in cooperative game
theory. A region is associated with the majority party in that region, and a
point is unhappy in $\Pi$ if it belongs to the minority party. A group $D$ of
roughly $\sigma$ contiguous points is called a deviating group with respect to
$\Pi$ if majority of points in $D$ are unhappy in $\Pi$. The partition $\Pi$
is locally fair if there is no deviating group with respect to $\Pi$.

This paper focuses on a restricted case when points lie in $1$D. The problem
is non-trivial even in this case. We consider both adversarial and “beyond
worst-case” settings for this problem. For the former, we characterize the
input parameters for which a locally fair partition always exists; we also
show that a locally fair partition may not exist for certain parameters. We
then consider input models where there are “runs” of red and blue points. For
such clustered inputs, we show that a locally fair partition may not exist for
certain values of $\sigma$, but an approximate locally fair partition exists
if we allow some regions to have smaller sizes. We finally present a
polynomial-time algorithm for computing a locally fair partition if one
exists.

##  1 Introduction

Redistricting is a common societal decision making problem. In its basic form,
there are two parties, say red and blue, and a parliament with some $k$
representatives. Each individual (or voter) in the geographic region is
aligned with one of the two parties. The goal is to divide the region into $k$
parts – called districts – so that each part elects one representative to the
parliament. It is typically assumed that each district does majority voting,
so that if a district has more red voters than blue voters, then the chosen
representative will be red.

The societal question then is how should these districts be drawn? One natural
constraint is that the district is a connected region and, more preferably,
has a compact shape. Another consideration is that each district is population
balanced, i.e., has roughly the same number of individuals.111US courts have
ruled that districts be population balanced, compact, and contiguous; see,
e.g., https://en.wikisource.org/wiki/Reynolds_v._Sims. A final consideration,
and one that will be the focus of this paper, is fairness. If society has a
large fraction of blue voters, the districts should not be drawn so that most
representatives end up being red.

In this paper, we consider a local and strong notion of fairness. Let us say
that a voter is unhappy if she is in a majority blue (resp. red) district, but
her party is red (resp. blue). We say that a given set of districts is locally
fair if no subset of unhappy voters of the same party can deviate and form a
feasible district (nicely shaped and balanced) so that they are the majority
in that district. In other words, these deviating voters have a justified
complaint – there was a different hypothetical district where they could have
been happy. This notion is akin to that of the core from cooperative game
theory [26]. As such, if a partition is locally fair, then it is as fair as
possible to the relevant parties – there are no groups could potentially form
a region and do better.

There are examples in which a group of voters have argued they have a
justified complaint regarding the redistricting. In the 2012 election in North
Carolina, $13$ House seats were allocated, $4$ to Democrats and $9$ to
Republicans. In contrast, the percentage of voters who voted for a Democrat
candidate was $50.60\%$. The U.S. Court of Appeals ruled that two of the
districts’ boundaries in this map were unconstitutional due to gerrymandering
and required new maps to be drawn. Considering this map, it is clear there
exist compact potential districts which could be considered a deviating group
with respect to the districting. This case (Cooper v. Harris (2017)) is just
one in a long line of judgements on the fairness of districting plans in the
U.S.222See also, Benisek v. Lamone (2018), Gill v. Whitford (2018), Rucho v.
Common Cause (2019), etc. The exhibition of deviating groups may help a
political group or group of voters justify their complaint that a
redistricting is unfair, and it may be effectively used in auditing proposed
plans.

In contrast, some input instances may exhibit “natural gerrymandering”, when
the distribution of the population prevents redistricting plans from being
representative to all groups [6]. For example, if the minority party had
$40\%$ of the vote in total but the voters are uniformly distributed, it is
unlikely that any deviating groups with a justified complaint would exist. In
this case, one could argue no reasonable redistricting could ensure the
minority group elects its fair share of the representatives. Thus, the notion
of local fairness introduced in the paper allows us to distinguish between
natural and artificial gerrymandering. In contrast, when a redistricting plan
is not globally fair (proportionally representative), it is not clear whether
any group has a justified complaint regarding the redistricting, or if it is
an unavoidable consequence of the geometry of the map.

###  1.1 Our Results

In this paper, we study the existence and computation of a locally fair
partition in the one-dimensional case, where we assume the $n$ voters lie on a
line or a circle. A _feasible_ district or region is now an interval
containing $\sigma=n/k$ voters. The “niceness” aspect is captured by the
region being an interval, and the “balance” aspect is captured by the number
of points in each interval being $n/k$. Even in this setting, we show that
locally fair partitioning is surprisingly non-trivial, and leads to a rich
space of algorithmic questions.

#### Relaxed local fairness notions.

In the 1D case, regulating each interval to be containing exactly $\sigma$
voters is extremely restrictive, and it is relatively easy to show that even a
balanced (not necessarily fair) partition need not exist. We will therefore
allow ourselves to relax the interval size. We parameterize this by
$\varepsilon$, so that the number of voters in any allowable interval lies in
$\left[(1-\varepsilon)\sigma,(1+\varepsilon)\sigma\right]$. This also relaxes
the number of intervals to be some number in
$[\frac{k}{1+\varepsilon},\frac{k}{1-\varepsilon}]$.333Many of our results
extend to the setting in which the number of intervals must be exactly $k$.
Further, we also relax the notion of _deviation_ , so that if a subset of
voters deviate, they need to become “really happy” – they need to be a strict
majority in the interval to which they deviate. We call this parameter
$\beta\in[1/2,1]$, so that unhappy points only deviate to a new allowable
interval if their population size is at least $\beta\sigma$. If a fair
partition exists under such relaxations, we term it _$(\varepsilon,\beta)$
-fair_.

Under these relaxations, our first set of results in Section 3 characterizes
the $(\varepsilon,\beta)$ values for which a fair partition exists, and those
where it may not. For $\varepsilon\leq 1/5$, we show a sharp threshold at
$\beta=1-\varepsilon$: When $\beta<1-\varepsilon$, for large enough values of
$n$, there is an instance with no $(\varepsilon,\beta)$-fair partition, while
when $\beta\geq 1-\varepsilon$, the simple strategy of creating uniform
intervals is $(\varepsilon,\beta)$-fair. If we restrict points to deviate only
when the interval they create has exactly $\sigma$ points, this sharp
threshold holds for all $\varepsilon\leq 1/3$. To interpret this result, when
$\varepsilon=1/3$, this means there is a fair partition where all intervals
have size in the range $\left[\frac{2}{3}\sigma,\frac{4}{3}\sigma\right]$, and
no subset of unhappy points can create an interval with $\sigma$ points, where
they form $2/3$-majority. Furthermore, there is an instance where the bound of
$2/3$ on the majority cannot be reduced any further.

#### Beyond worst-case.

The negative results above are adversarial: they need careful constructions of
sequences of runs of red and blue points with precise lengths, so that any
partitioning scheme that needs intervals of certain size to eventually
straddle both red and blue points in a way that allows a deviating interval to
take shape. However, this is an artifact of the intervals needing almost
precise balance, i.e., their lengths being approximately $\sigma$. The next
question we ask is: suppose we are allowed to place a small fraction $\alpha$
of points in intervals whose sizes can be smaller than
$(1-\varepsilon)\sigma$. In particular, we could construct intervals for these
points so that they are all happy, preventing them from deviating; or we could
think of it as eliminating these points. Then is it possible to circumvent
these lower bounds?

In Section 4, we show that the above is indeed the case when the input
sequences are reasonably benign. By “benign”, we mean that the input is
clustered, i.e., composed of runs of red and blue points of arbitrary lengths,
as long as these lengths are lower bounded by some value $\ell$. This models
phenomena like Schelling segregation [27, 32, 20], where individuals have a
slight preference for like-minded neighbors and relocate to meet this
constraint, which leads to “runs” of like-minded individuals.

For such input sequences, we show that as long as all runs are of length at
least $\ell=2\sigma$, once we allow a small fraction $\alpha=O(\frac{1}{k})$
of the points to be placed in unbalanced regions, there is a locally fair
partition even for the strictest setting $(\varepsilon,\beta)=(0,1/2)$: the
remaining points are placed in intervals of size exactly $\sigma$, and no
deviating interval of size $\sigma$ has a simple majority of unhappy points.

##### Efficient partitioning.

In Section 5, we finally study the algorithmic question: given parameters
$(\varepsilon,\beta)$, decide whether a given input of length $n$ admits a
$(\varepsilon,\beta)$-fair partition. Note that the results so far have been
worst-case existential results, and it is possible that even when
$\beta<1-\varepsilon$, many inputs would have an $(\varepsilon,\beta)$-fair
partition. The challenge in designing an algorithm is that a deviating
interval could involve points from more than one interval in the partition. We
resolve this via a dynamic programming algorithm whose running time is
polynomial in $n$ for any $\varepsilon\in[0,1/2]$.

###  1.2 Related Work

#### Fairness notions.

Proportionality is a classic approach to achieving fairness in social choice.
In a proportional solution, different demographic slices of voters feel they
have been represented fairly. This general idea dates back more than a century
[14], and has recently received significant attention [8, 23, 7, 2, 25, 3]. In
fact, there are several elections, both at a group level and a national level,
that attempt to find committees (or parliaments) that provide approximately
proportional representation.

The notion of core from cooperative game theory [26] represents the ultimate
form of proportionality: every demographic slice of voters feel that they have
been fairly represented and do not have incentive to deviate and choose their
own solution which gives all of them higher utility. In the typical setting
where these demographic slices are not known upfront, the notion of core
attempts to be fair to all subsets of voters. Though the core has been
traditionally considered in the context of resource allocation problems [21,
16, 15, 28], one of our main contributions is to adapt this notion in a non-
trivial way to the redistricting problem.

#### Redistricting vs. clustering.

The redistricting problem is closely related to the clustering problem. In a
line of recent work, various models of fairness have been proposed for center-
based clustering. One popular approach to fairness ensures that each cluster
contains groups in (roughly) the same proportion in which they exist in the
population [11, 31]. The redistricting problem we consider may take the
opposite view – we effectively want the regions or clusters to be as close to
monochromatic as possible to minimize the number of unhappy points in each
region.

Chen et al. studied a variant of fair clustering problem where any large
enough group of points with respect to the number of clusters are entitled to
their own cluster center, if it is closer in distance to all of them [10].
This extends the notion of the core in a natural way to clustering. However,
this work defines happiness of a point in terms of its distance, while in the
redistricting problem, the happiness is in terms of the color of the majority
within that region. The latter leads to fundamentally different algorithmic
questions.

#### Redistricting Algorithms.

There has been extensive work on redistricting algorithms, going back to 1960s
[19], for constructing contiguous, compact, and balanced districts. Many
different approaches, including integer programming [17], simulated annealing
[1], evolutionary algorithms [22], Voronoi diagram based methods [29, 12],
MCMC methods [4, 13], have been proposed; see [5] for a recent survey. A line
of work on redistricting algorithms focuses on combating manipulation such as
gerrymandering: when district plans have been engineered to provide advantage
to individual candidates or to parties [6]. For example, Cohen-Addad et al.
propose a districting strategy with desirable geometric properties such as
each district being a convex polygon with a small number of sides on average
[12]. Using similar methods, Wheeler and Klein argue that the political
advantage of urban or rural voters tends to be dramatically less than that
afforded by district plans used in the real world [30]. In fact, Chen et al.
show that district plans can also have unintentional bias arising from
differences in geographic distribution of two parties [9].

#### Auditing.

Another line of work in redistricting focuses on developing statistical tools
to detect gerrymandering given a districting plan [18]. In many redistricting
algorithms, existing methods generate maps without explicitly incorporating
notions of fairness, but instead focusing on compactness. Popular methods
generate an ensemble of plans and compare the number of representatives each
party gets in the generated maps with the number received under the actual
proposed maps [5]. In practice, political groups use many justifications for
whether a plan is fair, and our paper offers a new formal model which may be
used for auditing– arguing that various plans satisfy properties of fairness
[24, 13]. Our work in contrast takes a more algorithmic approach – given a
natural definition of what a fair redistricting should look like, we show
existence and computational results.

##  2 Preliminaries

Let $X$ be a set of $n$ points in $\mathbb{R}^{1}$, each colored red or blue,
and let $\sigma\in[n]$ be a parameter called ideal population size.444We
assume points lie on a line for simplicity; our results extend to the case of
a ring in a straightforward manner. We wish to construct a locally fair
partition of $X$ into intervals so that all intervals have roughly $\sigma$
points. Only ordering of points in $X$ really matters, so we describe the
input as a (binary) sequence $X=x_{1},\dots,x_{n}$, where
$x_{i}\in\\{\mathsf{R},\mathsf{B}\\}$ represents the color of the $i$-th point
on the line.

Define $R\coloneqq\\{i\in[n]\mid x_{i}=\mathsf{R}\\}$ and
$B\coloneqq\\{i\in[n]\mid x_{i}=\mathsf{B}\\}$ to be the subset of all red
points and blue points, respectively. An _interval_ is a contiguous sequence,
defined by a pair of integers $i,j\in[n]$ and denoted as either $[i,j]$ (where
both points $i$ and $j$ are included) or $(i,j]$ (where only $j$ is included).
For an interval $I\subset[n]$, let $\left|I\right|$ denote its size, i.e.,
$\left|[i,j]\right|=j-i+1,\left|(i,j]\right|=j-i$.

#### An alternative way to describe the input.

Sometimes it is useful to re-describe the input as a series of alternating
maximal monochromatic intervals. When appropriate, we denote the input as
$X=R_{1},B_{1},R_{2},\ldots,R_{\eta},B_{\eta}$, where each $R_{j}\subseteq R$
(resp. $B_{j}\subseteq B)$ is a maximal sequence of red (resp. blue) points,
$R_{j}\neq\varnothing$ for $j>1$, and $B\neq\varnothing$ for $j<\eta$. For
each $R_{j},B_{j}$, it suffices to specify its size.

#### Balanced Partition.

We are interested in partitioning $[n]$ into pairwise-disjoint intervals,
i.e., computing a partition $\Pi=\langle\pi_{1},\dots,\pi_{T}\rangle$, where
$T=\left|\Pi\right|$, $\pi_{t}=(i_{t-1},i_{t}]$ for all $t\in[T]$, and
$0=i_{0}<i_{1}<\ldots<i_{T}=n$.

We parameterize the population deviation in an interval using an input
parameter $\varepsilon$: For $\varepsilon\in[0,1/2]$, an interval
$\pi_{t}\in\Pi$ is called $\varepsilon$-allowable (or allowable for brevity)
if it satisfies
$(1-\varepsilon)\sigma\leq\left|\pi_{t}\right|\leq(1+\varepsilon)\sigma.$ The
partition $\Pi$ is balanced if each of its interval is allowable. Note that a
balanced partition may not always exist (take $n=100$, $\varepsilon=.01$, and
$\sigma=40$). In the remainder of the paper, we assume that $\sigma$ is chosen
such that a balanced partition exists.

For $\varepsilon=0$, each interval has exactly $\sigma$ points; and for
$\varepsilon=1/2$, each interval contains between $\frac{\sigma}{2}$ and
$\frac{3\sigma}{2}$ points. In principle, we can choose $\varepsilon$ to be
any value in $[0,1]$; but as the value of $\varepsilon$ increases, the sizes
of intervals in the partition become increasingly unbalanced. At an extreme,
when $\varepsilon=1$, every point could form its allowable interval. Thus, we
only consider the setting of $\varepsilon\in[0,1/2]$, though most of our
results extend to settings of larger $\varepsilon$.

For an interval $I\subseteq[n]$, it is sometimes more convenient to work with
the ratio $\left|I\right|/\sigma$, which is $1$ for an interval of $\sigma$
points. We define the measure of $I$, denoted by $\left\lVert I\right\rVert$,
as $\left\lVert I\right\rVert=\left|I\right|/\sigma.$

#### Locally fair partition.

Next, we turn our focus to defining the notion of local fairness. For an
interval $I$, let $\chi(I)$ represent its majority color. Formally,
$\chi(I)=\mathsf{R}$ if the interval $I$ has red majority, i.e. $\left|R\cap
I\right|>\left|B\cap I\right|$. Similarly, set $\chi(I)=\mathsf{B}$ if
$\left|R\cap I\right|<\left|B\cap I\right|$. Without loss of generality, if
$\left|R\cap I\right|=\left|B\cap I\right|$, i.e., there is no majority in
$I$, we define $\chi(I)=\mathsf{B}$.

A point $i$ is happy in $\Pi$ if it is assigned to an interval matching its
color, i.e., $\chi(\pi_{t})=x_{i}$, where $\pi_{t}\in\Pi$ is the interval
containing $i$; otherwise $i$ is unhappy in $\Pi$. For an interval
$I\subseteq[n]$, let $\text{uhp}({I,\Pi})\coloneqq\\{i\in I\mid i\text{ is
unhappy in }\Pi\\}$ denote the subset of unhappy points in $I$ in partition
$\Pi$. Note that here $I$ can be any interval and is not necessarily a part in
$\Pi$. If $\Pi$ is fixed or clear from the context, we write
$\text{uhp}({I})\coloneqq\text{uhp}({I,\Pi})$.

Intuitively, a partition $\Pi$ is locally fair if there is no large set of
unhappy points which could form an allowable interval in which they would be
the majority. We make this concept more precise below:

######  Definition 1.

Given an input instance $(X,\sigma)$ and a parameter
$\beta\in\left[\frac{1}{2},1\right]$, a $\beta$-deviating group with respect
to a partition $\Pi$ is an allowable interval $D$ with more than
$\max\left\\{\frac{|D|}{2},\beta\sigma\right\\}$ unhappy monochromatic points,
or equivalently, $\max\left\\{\left\lVert\text{uhp}({D})\cap
R\right\rVert,\left\lVert\text{uhp}({D})\cap
B\right\rVert\right\\}>\max\left\\{\frac{\left\lVert
D\right\rVert}{2},\beta\right\\}.$ Note that we do not require the existence
of a balanced partition with $D$ being one of its intervals.

$D$ is called a $\beta$-deviating group because $D$ may deviate from $\Pi$
such that at least $\beta\sigma$ points that were unhappy in $\Pi$ become
happy if $D$ was made a standalone part in another partition. We sometimes
omit $\beta$ and use the term “deviating group” when the context is clear.
Intuitively, $\beta$ controls how difficult it is for a set of unhappy points
to deviate and form an interval in which they are happy. As $\beta$ grows, the
set of unhappy points that may form a deviating group must grow larger with
respect to the desired interval size $\sigma$; to deviate when $\beta=1/2$, a
set of more than $\sigma/2$ unhappy points must lie in an allowable interval
in which they are the majority. At $\beta=1$, the number of unhappy points
required to form a deviating group increases to $\sigma$. See Figure 1 for an
example.

######  Definition 2.

Given $(X,\sigma)$, $\varepsilon\in[0,1/2]$, and $\beta\in[1/2,1]$, we call a
balanced partition $\Pi$ $(\varepsilon,\beta)$-locally fair if there is no
$\beta$-deviating group with respect to $\Pi$.

Figure 1: An with $n=15$ points, $\sigma=4$, $\varepsilon=1/2$, and
$\beta=2/3$. The top partition $\\{\pi_{1},\dots,\pi_{5}\\}$ admits a blue
deviating group $D$, whereas the bottom partition
$\\{\pi^{\prime}_{1},\dots,\pi^{\prime}_{4}\\}$ is $(1/2,2/3)$-locally fair.

#### Remark.

While we focus on $\beta\in[1/2,1]$, the largest possible range to consider is
$\beta\in\left[(1-\varepsilon)/2,(1+\varepsilon)\right]$. For applications of
our model, we would expect the requirement on $\beta$ to be stronger than a
simple majority, so that we bias towards solutions (partitions) which are
presumably fair to the rest of the points.

##  3 Existence of Locally Fair Partitions

In this section, we present our results on the existence of locally fair
partitions. We first give characterizations of parameters $\varepsilon$ and
$\beta$ for which a locally fair solution is guaranteed to exist. We show that
for every $\varepsilon\in[0,1/2]$, there is a threshold
$\bar{\beta}(\varepsilon)$ such that if $\beta$ is above this threshold, a
simple partitioning strategy into small intervals results in a
$(\varepsilon,\beta)$-fair partition.

######  Theorem 3.

Let $(X,\sigma)$ be an input instance as defined above. For any
$\varepsilon\in[0,1/2]$, there is a value $\bar{\beta}(\varepsilon)$ such that
for any $\beta>\bar{\beta}(\varepsilon)$, there exists an
$(\varepsilon,\beta)$-fair partition, where

$\bar{\beta}(\varepsilon)=\begin{cases}\max\left\\{1-\varepsilon,\frac{1+3\varepsilon}{2}\right\\}+O(\delta)\text{
for }\varepsilon\in[0,1/3],\\\ \max\left\\{\frac{3(1-\varepsilon)}{2},\
2\varepsilon\right\\}+O(\delta)\text{ for
}\varepsilon\in[1/3,1/2],\end{cases}$

and $\delta\leq\frac{1}{\frac{n}{\sigma}-1}+\frac{1}{\sigma}$.

aaai

#### Proof sketch.

(See the full version for a detailed proof.) We construct a partition $\Pi$
that uses as small as possible intervals (the length of each interval takes
the form $(1-\varepsilon+\delta)\sigma$). For $\varepsilon\leq 1/3$, an
allowable deviating group $D$ could intersect at most $3$ intervals. We show
if $D$ intersects only $2$ intervals, a simple calculation shows there are
less than $\beta\sigma$ unhappy points and such a $D$ cannot exist. On the
other hand, if $D$ intersects $3$ intervals $\pi_{i},\pi_{i+1},\pi_{i+2}$, it
must completely contain $\pi_{i+1}$. We can bound the number of points $D$ can
pull from $\left|\pi_{i}\cup\pi_{i+2}\right|$ as
$(1+\varepsilon)\sigma-\left|\pi_{i+1}\right|$, all of which could be unhappy.
Additionally, it must be
$\left|\text{uhp}({\pi_{i+1}})\right|\leq\left|\pi_{i+1}/2\right|$. Combining
the two above observations shows the total number of unhappy points is less
than $\beta\sigma$, and so no deviating group exists. A similar proof holds
for $\varepsilon\in[1/3,1/2]$ by increasing the number of intervals the
deviating group could intersect to $4$.

arxiv

###### Proof.

We first consider the case of $\varepsilon\in[0,1/3]$. We call a partition
$\Pi$ of $[n]$ almost-uniform if there is some
$q\in[1-\varepsilon,1+\varepsilon]$ such that $\sigma^{\prime}=q\sigma$ is an
integer, and $\left|\pi_{t}\right|\in\\{\sigma^{\prime}-1,\sigma^{\prime}\\}$
for all $t=1,\ldots,\left|\Pi\right|$. Consider the following partition:
construct $\lfloor\frac{n}{(1-\varepsilon)\sigma}\rfloor$ intervals of
$(1-\varepsilon)\sigma$ points each. Then, uniformly distribute the remaining
points (less than $(1-\varepsilon)\sigma$ of them) across the intervals. Every
interval then gets at most
$\lceil\frac{(1-\varepsilon)\sigma}{\lfloor\frac{n}{(1-\varepsilon)\sigma}\rfloor}\rceil$
additional points. Therefore, the total number of points in the largest
interval is given by

$\displaystyle\sigma^{\prime}=q\sigma=(1-\varepsilon)\sigma+\lceil\frac{(1-\varepsilon)\sigma}{\lfloor\frac{n}{(1-\varepsilon)\sigma}\rfloor}\rceil\leq(1-\varepsilon)\sigma+\frac{(1-\varepsilon)\sigma}{\frac{n}{(1-\varepsilon)\sigma}-1}+1\leq(1-\varepsilon)\sigma+\frac{(1-\varepsilon)^{2}\sigma^{2}}{n-(1-\varepsilon)\sigma}+1.$

Hence we have

$\displaystyle\delta=q-(1-\varepsilon)\leq\frac{(1-\varepsilon)^{2}\sigma}{n-(1-\varepsilon)\sigma}+\frac{1}{\sigma}\leq\frac{\sigma}{n-\sigma}+\frac{1}{\sigma}=\frac{1}{\frac{n}{\sigma}-1}+\frac{1}{\sigma},$

when $n\gg\sigma$.

Hence take the almost-uniform partition $\Pi$ with this value of $q$. Consider
any potential deviating group $D$ of $\Pi$. First, suppose $D$ intersects at
least four contiguous intervals of $\Pi$. Then it must contain at least two
intervals in the middle, and therefore
$\left|D\right|>2(1-\varepsilon)\sigma\geq(1+\varepsilon)\sigma$ for
$\varepsilon\in[0,1/3]$, which violates the requirement that $D$ must be
allowable. Hence, $D$ can intersect at most three (contiguous) intervals of
$\Pi$. If $D$ intersects one or two intervals of $\Pi$, then

$\displaystyle\left|\text{uhp}({D,\Pi})\right|$ $\displaystyle\leq
2\cdot\frac{\sigma^{\prime}}{2}\leq\sigma^{\prime}=q\sigma\leq\bar{\beta}(\varepsilon)\sigma<\beta\sigma,$

which implies $D$ cannot be a deviating group itself. Hence, no deviating
group intersects at most $2$ intervals. Finally, if $D$ intersects $3$
intervals, $\\{\pi_{t},\pi_{t+1},\pi_{t+2}\\}$, then it completely contains
the middle interval $\pi_{t+1}$, which has size at most $\sigma^{\prime}$.
Since at most half of the points in $\pi_{t+1}$ are unhappy, we have
$\left|\text{uhp}({\pi_{t+1}})\right|\leq\frac{\sigma^{\prime}}{2}.$ On the
other hand, we have

$\displaystyle\left|D\cap(\pi_{t}\cup\pi_{t+2})\right|\leq(1+\varepsilon)\sigma-\left|\pi_{t+1}\right|\leq(1+\varepsilon)\sigma-\left(\sigma^{\prime}-1\right).$

Thus we have

$\displaystyle\left|\text{uhp}({D,\Pi})\right|=\sum_{j=t}^{t+2}\left|\text{uhp}({D\cap\pi_{j}})\right|$
$\displaystyle\leq\left|D\cap(\pi_{i}\cup\pi_{t+2})\right|+\left|\text{uhp}({\pi_{t+1}})\right|$
$\displaystyle\leq(1+\varepsilon)\sigma-\sigma^{\prime}+1+\frac{\sigma^{\prime}}{2}$
$\displaystyle\leq\left(1+\varepsilon-\frac{q}{2}+\frac{1}{\sigma}\right)\sigma$
$\displaystyle\leq\left(\frac{1+3\varepsilon}{2}-\frac{\delta}{2}+\frac{1}{\sigma}\right)\sigma$
$\displaystyle\leq\bar{\beta}(\varepsilon)\sigma<\beta\sigma,$

which again implies $D$ cannot be a deviating group. Hence $D$ does not exist,
and the proposed almost-uniform partition $\Pi$ is
$(\varepsilon,\beta)$-locally fair for $\varepsilon\in[0,1/3]$. The proof for
$\varepsilon\in[1/3,1/2]$ follows analogously by increasing the largest number
of intervals the deviating group can intersect by one, from three to four. ∎

arxiv

#### Remark.

When $n=c(1-\varepsilon)\sigma$ for some integer $c$, the partition proposed
in the proof of Theorem 3 becomes a uniform partition with interval size
$(1-\varepsilon)\sigma$, and thus $\delta=0$. Otherwise, we try to create an
almost-uniform partition such that the intervals are as small as possible. For
Theorem 3 to give a $\bar{\beta}(\varepsilon)$ bound below $1$, we need
$\delta$ to be roughly $O(\varepsilon)$, or $\varepsilon>\sigma/n$. If
$\sigma/n=c$ for a constant $c$, the desired interval size is $\Theta(n)$, and
the number of intervals in a balanced partition will only be $O(1)$. In this
setting, it is likely that any fair partitioning scheme must take into account
the coloring of the input.

Theorem 3 can be extended for any $\varepsilon\in[0,1]$. Following the same
proof approach gives the general form of
$\bar{\beta}(\varepsilon)=\max\left\\{\frac{t(1-\varepsilon)}{2},\frac{(3-t)+(t+1)\varepsilon}{2}\right\\}+O(t\sigma)$,
where $t$ is an integer such that
$\varepsilon\in\left[\frac{t-2}{t},\frac{t-1}{t+1}\right]$, or in other words,
$(t+1)$ is the largest number of intervals a deviating group can intersect.

Next, we show that for smaller values of $\beta$, a locally fair partition may
not exist.

######  Theorem 4.

Let $\varepsilon\in[0,1/2)$ and $\beta\in[1/2,1-\varepsilon)$. For any
$\sigma\geq 1$, there exists an input instance $(X,\sigma)$ with
$|X|=O\left(\frac{\beta\sigma}{1-\varepsilon-\beta}\right)$ for which no
$(\varepsilon,\beta)$-locally fair partition exists.

aaai,arxiv

###### Proof.

We construct an instance for which there is always a deviating group. For
simplicity, assume $\beta\sigma$ is an integer; we will relax this assumption
later. Specifying the input using the runs of monochromatic intervals, let
$X=R_{1},B_{1},R_{2},B_{2},\dots,R_{\eta},B_{\eta}$ for
$\eta=\left\lceil\frac{n}{2\beta\sigma}\right\rceil$. Set
$\left|R_{j}\right|=\beta\sigma$ for $j=1,\dots,\eta$ and
$\left|B_{j}\right|=\beta\sigma$ for $j=1,\dots,\eta-1$, and
$\left|B_{\eta}\right|=n-(2\eta-1)\beta\sigma\leq\beta\sigma.$

In any fair partition $\Pi$, each $R_{j}$ (resp. $B_{j}$) must intersect a red
(resp. blue) interval of $\Pi$; if there exists an entire $R_{j}$ (resp.
$B_{j}$) contained in a blue (resp. red) interval of $\Pi$, $R_{j}$ (resp.
$B_{j}$) could form a deviating group with its own $\beta\sigma$ unhappy
points, and $(1-\varepsilon-\beta)\sigma$ points from a neighboring $B_{j}$
(resp. $R_{j}$). Since $\beta\geq 1/2$, these unhappy red (resp. blue) points
are the majority in the deviating group. As a consequence, in any fair
partition $\Pi$, there exists no red (resp. blue) interval $\pi_{t}$ that
intersects multiple monochromatic red intervals $R_{j}$, $R_{j^{\prime}}$
(resp. blue intervals $B_{j}$, $B_{j^{\prime}}$) in $X$.

Suppose there exists a fair partition $\Pi$ for $(X,\sigma)$, and let let
$\pi_{1}$ be a red interval of $\Pi$ that intersects $R_{1}$. Since
$\beta<1-\varepsilon$, $\pi_{1}$ must include points from a neighboring blue
monochromatic interval; without loss of generality, let it intersect with
$B_{1}$.555We assume the input lies on a circle. Since $\pi_{1}$ must
intersect at least one of the two blue monochromatic intervals neighboring
$R_{1}$, we can order the input so that the intersected interval is $B_{1}$.
Then $\pi_{1}$ cannot intersect $R_{2}$; otherwise $B_{1}$ would deviate.
Therefore, $\pi_{1}$ includes at most $\beta\sigma$ points from $R_{1}$ and
some points from $B_{1}$. Now, consider interval $\pi_{2}$ of $\Pi$ which is
blue and intersects $B_{1}$ (but not $B_{2}$). By size constraints,
$\left\lVert\pi_{2}\right\rVert\geq(1-\varepsilon)$, and
$\left\lVert\pi_{2}\cap B_{1}\right\rVert<\beta$, since $\pi_{1}\cap
B_{1}\neq\emptyset$. This implies $\left\lVert\pi_{2}\cap
R_{2}\right\rVert>(1-\varepsilon-\beta)$. Next, interval $\pi_{3}$ is red-
majority and intersects $R_{2}$ (but not $R_{3}$); moreover, we have
$\left\lVert\pi_{3}\cap R_{2}\right\rVert\leq\left\lVert
R_{2}\right\rVert-\left\lVert\pi_{2}\cap
R_{2}\right\rVert<\beta-(1-\varepsilon-\beta)$. This then implies
$\left\lVert\pi_{3}\cap
B_{2}\right\rVert\geq\left\lVert\pi_{3}\right\rVert-\left\lVert\pi_{3}\cap
R_{2}\right\rVert>(1-\varepsilon)-\left(\beta-(1-\varepsilon-\beta)\right)=2(1-\varepsilon-\beta)$.

Continuing this argument, it can be shown that (i) every $R_{j}$ must
intersect a red interval in $\Pi$ that also intersects with $B_{j}$; and (ii)
every $B_{j}$ must intersect a blue interval in $\Pi$ that also intersects
with $R_{j+1}$. Combined with the fact that each red- (resp. blue-) majority
$\pi_{t}$ cannot intersect multiple monochromatic red (resp. blue) intervals
of $X$, for every $j$ it must hold that:

  * •

$\pi_{2j-1}$ is red-majority and intersects $R_{j}$;

  * •

$\pi_{2j}$ is blue-majority and intersects $B_{j}$;

  * •

$\left\lVert\pi_{2j-1}\cap
R_{j}\right\rVert<\beta-(2j-3)\cdot(1-\varepsilon-\beta)$;

  * •

$\left\lVert\pi_{2j-1}\cap
B_{j}\right\rVert>(2j-2)\cdot(1-\varepsilon-\beta)$;

  * •

$\left\lVert\pi_{2j}\cap
B_{j}\right\rVert<\beta-(2j-2)\cdot(1-\varepsilon-\beta)$;

  * •

$\left\lVert\pi_{2j}\cap
R_{j+1}\right\rVert>(2j-1)\cdot(1-\varepsilon-\beta)$.

Denote
$j^{\prime}=\left\lceil\frac{3-3\varepsilon-2\beta}{4(1-\varepsilon-\beta)}\right\rceil$,
and assume $\eta\geq j^{\prime}$. By the above, $\pi_{2j^{\prime}}$ is blue-
majority, and we have $\left\lVert\pi_{2j^{\prime}}\cap
B_{j^{\prime}}\right\rVert<\beta-(2{j^{\prime}}-2)\cdot(1-\varepsilon-\beta)<\frac{1-\varepsilon}{2}$,
which implies $\pi_{2j^{\prime}}$ cannot be blue-majority, a contradiction. In
other words, there are not enough points in $\pi_{2j^{\prime}}$ to create a
majority matching its color. Since
$\eta=\left\lceil\frac{n}{2\beta\sigma}\right\rceil$, the above holds for
$\frac{n}{2\beta\sigma}>\frac{3-3\varepsilon-2\beta}{4(1-\varepsilon-\beta)}$,
or
$n>\frac{(3-3\varepsilon-2\beta)\beta\sigma}{2(1-\varepsilon-\beta)}=O\left(\frac{\beta\sigma}{1-\varepsilon-\beta}\right)$.
Finally, if $\beta\sigma$ is not an integer, let
$\beta^{\prime}=\frac{\left\lceil\beta\sigma\right\rceil}{\sigma}$. Then the
above argument still holds for
$n>\frac{(3-3\varepsilon-2\beta^{\prime})\beta^{\prime}\sigma}{2(1-\varepsilon-\beta^{\prime})}$.
∎

$\pi_{1}$$\pi_{2}$$\pi_{3}$$\pi_{4}$$\cdots$$B_{\textsl{{d}}}$$\frac{5}{8}\sigma$
Figure 2: An instance so that each monochromatic interval has length
$5\sigma/8$, which does not admit a $(\frac{1}{4},\frac{5}{8})$-fair
partition. For example, partition $\Pi$ is made of intervals of length
$(1-\varepsilon)\sigma=3\sigma/4$; however, $B_{\textsl{{d}}}$ forms a
deviating group by pulling in points from neighboring intervals.

See Figure 2 for an example of the construction. For $\varepsilon\in[0,1/5]$,
Theorem 3 and Theorem 4 provide an almost sharp threshold: if
$\beta>1-\varepsilon+O(\delta)$ (for $\delta$ defined in Theorem 3), a locally
fair partition always exists, but for $\beta<1-\varepsilon$ there are
instances that do not admit fair partitions. In fact, if we enforce the
deviating group to have exactly $\sigma$ points, Theorems 3 and 4 become
almost tight for all $\varepsilon\in[0,1/3]$. We next extend Theorem 4 so that
a single instance $X$ has no locally fair partition for a wide range of
$\sigma$ values.

######  Corollary 5.

Let $\varepsilon\in[0,1/2)$, $\beta\in[1/2,1-\varepsilon)$, and let
$\mathcal{S}=\\{\sigma_{1},\sigma_{2},\dots,\sigma_{M}\\}$ be the set of
desired interval sizes. If
$\frac{n}{M\sigma_{m}}>\left\lceil\frac{1}{1-\varepsilon-\beta}\right\rceil$
holds for all $m\in[M]$, there exists an input $X$ such that (i)
$\left|X\right|=n$; (ii) for all $m=1,\dots,M$, the instance $(X,\sigma_{m})$
has no $(\varepsilon,\beta)$-locally fair partition.

arxiv

###### Proof.

We construct $X$ as follows. Let $X_{1},\dots,X_{M}\subseteq X$ be
subintervals of $X$, each of size $n/M$. For each part $X_{m}$, we apply
Theorem 4 with $(X_{m},\sigma_{m})$. For each $\sigma_{m}$, a deviating group
exists in $X_{m}$. ∎

#### Remark.

(i) In light of Theorem 4, we observe that if we are given a periodic
instance, it is always possible to define a $\tilde{\sigma}$ for which the
instance has a locally fair solution, even if the instance had no locally fair
solution for the given $\sigma$. Specifically,
$\tilde{\sigma}=\Theta(\sigma)$. In the next section, we define an approximate
version of the problem, in which we allow some fraction of points to lie
outside of allowable regions. We focus on “periodic-like” instances, when the
input consists of monochromatic intervals of size $\Omega(\sigma)$.

(ii) In some applications, it may be desirable to ensure there is a fixed
number of intervals in a partition. Given a desired number of intervals $k$,
the negative results of Theorem 4 extend to this setting, i.e., we can
construct periodic instances similar to those in Theorem 4 in which no locally
fair solutions exist, for even larger ranges of $(\varepsilon,\beta)$
parameters.

##  4 Clustered Instances

As manifested in the previous section, under many specific parameters
$\varepsilon,\beta$, there exist adversarial input instances $(X,\sigma)$ that
rule out the existence of any locally fair partition. However, such negative
instances often seem artificial, and are not robust to perturbation. In this
section, we turn our attention to a category of interesting inputs, when
points are “clustered” into large monochromatic intervals. Such instances
arise in applications in which we expect points of the same color to gather
together. We show that fair partitions exist when the input instance is
comprised of large monochromatic intervals, while incurring a small
approximation on the balancedness of the fair partition.

For a constant $\alpha\in[0,1)$, we say a partition $\Pi$ of $X$ is
$\alpha$-balanced if the union of all its allowable intervals make up at least
a $(1-\alpha)$-fraction of the total input. Formally, let
$\tilde{\Pi}\coloneqq\\{\pi_{t}\in\Pi\mid\left|\pi_{t}\right|\in[(1-\varepsilon)\sigma,(1+\varepsilon)\sigma]\\}$
be the set of allowable intervals in $\Pi$. Then $\Pi$ is $\alpha$-balanced if
$\left|\bigcup_{\pi_{t}}\\{\pi_{t}\in\tilde{\Pi}\\}\right|\geq(1-\alpha)n$.

In fact, in this section our results hold for any $\beta\in[1/2,1]$, so we
omit $\beta$ as a parameter, and instead refer to a fair partition as
$\varepsilon$-locally fair.

First, we show that if the size of each monochromatic interval in $X$ is at
least $2\sigma$, we can compute a fair partition by letting allowable
intervals not contain a small fraction of the population.

######  Theorem 6.

Given instance $\left(X=R_{1},B_{1},R_{2},\dots,\sigma\right)$ with
$\left\lVert R_{j}\right\rVert,\left\lVert B_{j}\right\rVert\geq 2,$ for all
$j$ and parameter $\varepsilon\in[0,1/2]$, there is a
$\left(\frac{(1-\varepsilon)\sigma}{n}\right)$-balanced, $\varepsilon$-locally
fair partition $\Pi$.

###### Proof.

We assume that the first monochromatic interval $R_{1}$ is red and the last
monochromatic interval $B_{\eta}$ is blue. The other cases follow analogously.
Consider an arbitrary maximal monochromatic red interval $R_{j}$ with measure
$\left\lVert R_{j}\right\rVert\geq 2$. We divide $R_{j}$ into allowable
intervals such that the residual interval $R^{\prime}_{j}$ (points of $R_{j}$
not assigned to an allowable interval) is as small as possible. Note that
$\left\lVert R^{\prime}_{j}\right\rVert\in[0,1-\varepsilon)$. We assign the
points of $R^{\prime}_{j}$ to a size $\lceil(1-\varepsilon)\sigma\rceil$
interval using $\lceil\left((1-\varepsilon)-\left\lVert
R^{\prime}_{j}\right\rVert\right)\sigma\rceil$ points from the next interval,
$B_{j}$. Partition the entire instance in this manner and let $\Pi$ be the
resulting partition. All intervals of $\Pi$ are allowable except for the
residual interval $B^{\prime}_{\eta}$ from the last monochromatic interval
$B_{\eta}$. Since $|B^{\prime}_{\eta}|<(1-\varepsilon)\sigma$, $\Pi$ is
$\left(\frac{(1-\varepsilon)\sigma}{n}\right)$-balanced.

We next show $\Pi$ is locally fair regardless of the value of $\varepsilon$.
Suppose there exists a deviating group $D$. Without loss of generality, assume
$D$ is red-majority and $D$ intersects two consecutive red intervals $R_{j}$
and $R_{j+1}$ of $X$. Then we have $B_{j+1}\subset D$. Since $\left\lVert
B_{j+1}\right\rVert\geq 2$, we have $\left\lVert
D\right\rVert>2>(1+\varepsilon)$, a violation of the size constraint. Hence,
$D$ can only intersect one monochromatic red interval $R_{j}$ for some $j$.

Define $R^{\prime\prime}_{j}\subseteq R_{j}$ (resp. $R^{\prime}_{j}\subseteq
R_{j}$) to be the (not necessarily non-empty) set of red points assigned to
the same interval, denoted by $\pi^{\prime\prime}$ (resp. $\pi^{\prime}$) as a
subset $B^{\prime}_{j}$ of $B_{j}$ (resp. $B^{\prime}_{j+1}$ of $B_{j+1})$
(See Figure 3). If $\pi^{\prime}$ is blue majority, then $\left\lVert
R^{\prime\prime}_{j}\right\rVert<\frac{1-\varepsilon}{2}$, by construction.
Similarly, if $\pi^{\prime}$ is blue majority, then $\left\lVert
R^{\prime}_{j}\right\rVert<\frac{1-\varepsilon}{2}$. Assume $D$ intersects
both $R^{\prime}_{j}$ and $R^{\prime\prime}_{j}$. Then both $\pi^{\prime}$ and
$\pi^{\prime\prime}$ need to be blue-majority, and we have
$R\setminus\left(R^{\prime}_{j}\cup R^{\prime\prime}_{j}\right)\subset D$. But
this implies $\left\lVert R\setminus\left(R^{\prime}_{j}\cup
R^{\prime\prime}_{j}\right)\right\rVert>2-\frac{1-\varepsilon}{2}-\frac{1-\varepsilon}{2}=1+\varepsilon$
and thus $\left\lVert D\right\rVert>1+\varepsilon$, a contradiction.

Hence, $D$ can only intersect either $R^{\prime}_{j}$ or
$R^{\prime\prime}_{j}$. In both cases,
$\left\lVert\text{uhp}({D})\right\rVert<\frac{1-\varepsilon}{2}$, implying $D$
does not have sufficient points to form a deviating group. Therefore, no
deviating group exists in $\Pi$. ∎

$R_{j}^{\prime\prime}$$R_{j}^{\prime}$$\cdots$$\cdots$$R_{j}$$D$

Figure 3: No deviating group $D$ intersects $R^{\prime\prime}_{j}$ and
$R^{\prime}_{j}$.

In fact, we can use the same partitioning strategy to find balanced fair
partitions (i.e., every point belongs to an allowable interval $\pi_{t}$) if
each monochromatic interval of an instance has size at least
$\left\lceil\frac{(1-\varepsilon)^{2}}{2\varepsilon}\right\rceil$.

######  Corollary 7.

For an instance $(X,\sigma)$ and parameter $\varepsilon$, such that for all
$j$: $\left\lVert R_{j}\right\rVert,\left\lVert
B_{j}\right\rVert\geq\left\lceil\frac{(1-\varepsilon)^{2}}{2\varepsilon}\right\rceil,$
there is always a balanced $\varepsilon$-locally fair partition $\Pi$ of $X$.

arxiv

###### Proof.

Observe that the residual interval for each $R_{j},B_{j}$ defined in Theorem 6
has length zero. Accordingly, by uniformly partitioning each $R_{j},B_{j}$
into equally-sized monochromatic intervals, we have a locally fair partition
of $X$ in which no points are unhappy. ∎

arxiv

#### Remark.

For all $\varepsilon\geq 3-2\sqrt{2}\approx.17$, Corollary 7 requires
monochromatic intervals to have size at most that of Theorem 6, but achieves
exact balancedness. However, the threshold
$\left\lceil\frac{(1-\varepsilon)^{2}}{2\varepsilon}\right\rceil$ is non-
increasing in $\varepsilon$: when $\varepsilon\rightarrow 0$,
$\left\lceil\frac{(1-\varepsilon)^{2}}{2\varepsilon}\right\rceil\rightarrow\infty$,
while when $\varepsilon\geq 1/2$,
$\left\lceil\frac{(1-\varepsilon)^{2}}{2\varepsilon}\right\rceil=1$. Thus, for
small values of $\varepsilon$, it is preferable to apply Theorem 6.

Next, we relax the requirement that every monochromatic interval is long and
consider “mostly” clustered instances. Specifically, assume that at most
$\gamma n$ points of $X$ lie in monochromatic intervals smaller than size
$2\sigma$. Applying Theorem 6 to this setting, we can construct an
$\alpha$-balanced fair partition with $\alpha$ depending on $\gamma$.

######  Theorem 8.

Given $(X,\sigma)$ and parameter $\varepsilon\in[0,1/2]$, where
$X=R_{1},B_{1},\dots,R_{\eta},B_{\eta}$, let $Y$ denote the set of
monochromatic intervals of $X$ of length smaller than $2\sigma$:
$Y\coloneqq\\{I\in\\{R_{1},\ldots,R_{\eta},B_{1},\ldots,B_{\eta}\\}\mid\left\lVert
I\right\rVert<2\\}.$

If $\left|\bigcup_{I\in Y}I\right|\leq\gamma n$, then there is a
$\left(\frac{(1-\varepsilon)\sigma}{n}+\gamma\right)$-balanced,
$\varepsilon$-locally fair partition.

arxiv

###### Proof.

We partition $X$ into two parts: the bad part $Y$ and the good part
$Z=X\setminus Y$. $X$ can be regarded as an alternating sequence of $Z_{i}$s
and $Y_{j}$s.

Apply Theorem 6 to each good part $Z_{i}$. For each $Z_{i}$, the residual
points $Z^{\prime}_{i}$ of the last monochromatic interval in $Z_{i}$
satisfies $\left\lVert Z^{\prime}_{i}\right\rVert<(1-\varepsilon)$. Then we
consider two cases:

  * •

$\left\lVert Z^{\prime}_{i}\right\rVert+\left\lVert Y_{i}\right\rVert\geq
1-\varepsilon$. We define an interval $I_{i}$ containing $Z^{\prime}_{i}$ and
$(1-\varepsilon-\left\lVert Z^{\prime}_{p}\right\rVert)\sigma$ points of
$Y_{i}$, and add $I_{i}$ to the partition. For each remaining monochromatic
interval $R_{j}$ (or $B_{j}$) in $Y_{i}$, we create a (not necessarily
allowable) standalone interval in our partition, so that all points are happy
and do not contribute to any potential deviating groups.

  * •

$\left\lVert Z^{\prime}_{i}\right\rVert+\left\lVert
Y_{i}\right\rVert<1-\varepsilon$. In this case, we apply the partitioning
scheme in the proof of Theorem 6 on $Z_{i},Y_{i},Z_{i+1}$, namely, there is an
interval $\pi_{i}$ containing $Z^{\prime}_{i},Y_{i}$ and
$\lceil\left(1-\varepsilon-\left|Z_{i}\right|-\left|Y_{i}\right|\right)\sigma\rceil$
points of the first monochromatic interval of $Z_{i+1}$.

In both cases, no deviating group exists since the interval containing
$Z^{\prime}_{i}$ and points of $Y_{i}$ are adjacent to intervals with no
unhappy points, although there may be a total of $\gamma n$ points lying in
non-allowable intervals $\pi_{i}\in\Pi$ with
$\left|\pi_{i}\right|<(1-\varepsilon)\sigma$. Additionally, for the last good
part $Z_{i}$, there may be an additional
$\left(\frac{(1-\varepsilon)\sigma}{n}\right)$ points lying in non-allowable
intervals, as a direct consequence of applying Theorem 6. (Note that its
counterparts in $Z_{1},\ldots,Z_{i-1}$ are handled in the above process.)
Thus, there is a
$\left(\frac{(1-\varepsilon)\sigma}{n}+\gamma\right)$-balanced,
$\varepsilon$-locally fair partition. ∎

For all $\varepsilon$, $\alpha$ improves (i.e., decreases) as $\gamma$
decreases, as more of the input lies in larger monochromatic intervals.
Similar to Corollary 7, if $\varepsilon\geq 3-2\sqrt{2}$, we can prove the
above process gives a $\gamma$-balanced, $\varepsilon$-locally fair partition.

arxiv

#### Remark.

Here we defined the approximation concept in terms of the balancedness of fair
partitions. If we want to ensure the partition is strictly balanced, we can
instead define the approximation concept in terms of the total number of
points in the union of deviating groups, i.e., we allow a maximum of
$\alpha$-fraction of the points to deviate (participate in some deviating
group). Still assuming that at most $\gamma n$ points in the input lie in
monochromatic intervals smaller than size $2\sigma$, if $\varepsilon\geq
3-2\sqrt{2}$, we can get an exactly balanced partition which is
$\left(\frac{\gamma}{2}+\frac{1-\varepsilon}{4}\right)$-approximately fair.
For smaller $\varepsilon$, we still require a non-zero $\alpha$, but the
$\gamma$ parameter could be moved into the fairness approximation.

##  5 Partitioning Algorithm

Finally, we shift our focus to following algorithmic question: Given an
instance $(X,\sigma)$ and parameters $\varepsilon\in[0,1/2],\beta\in[1/2,1]$,
does a $(\varepsilon,\beta)$-locally fair solution exist for $(X,\sigma)$?

In this section, we focus on a fixed input instance, so throughout this
section, treat $X,\sigma,\varepsilon$, and $\beta$ as fixed, and describe an
algorithm that determines whether an $(\varepsilon,\beta)$-locally fair
balanced partition, possibly with additional constraints, exists, for an
interval $I\subseteq[n]$ of the input, where $|X|=n$.

$\ \ \pi_{1}\cdots\pi_{\textsl{{t}}-3}\ \ $ $\ \pi_{\textsl{{t}}-2}\ $ $\
\pi_{\textsl{{t}}-1}\ $ $\ \pi_{\textsl{{t}}}\ $ $i$$j$$i_{3}$$i_{2}$$i_{1}$
Figure 4: $\Pi$ is a partition of interval $(i,j]$, where $i_{1},i_{2}$, and
$i_{3}$ are the last three boundaries.

We now define the recursive subproblems. For any interval $I=(i,j]\in[n]$ and
for $i\leq i_{3}\leq i_{2}\leq i_{1}<j$, define
$\mathsf{LF}(I,i_{1},i_{2},i_{3})=\mathsf{True}$ if and only if there exists
at least one fair partition $\Pi=\\{\pi_{1},\ldots,\pi_{T}\\}$ of $I$ that
satisfies the following conditions:

$\displaystyle i_{1}=i_{2}=i_{3}=i,\quad\Pi=\\{(i,j]\\},\quad\text{for }T=1;$
$\displaystyle
i_{1}>i_{2}=i_{3}=i,\quad\Pi=\\{(i,i_{1}],(i_{1},j]\\},\quad\text{for }T=2;$
$\displaystyle
i_{1}>i_{2}>i_{3}=i,\quad\Pi=\\{(i,i_{2}],(i_{2},i_{1}],(i_{1},j]\\},\quad\text{for
}T=3;$ $\displaystyle
i_{1}>i_{2}>i_{3}>i,\quad\Pi=\\{\pi_{1},\ldots,(i_{3},i_{2}],(i_{2},i_{1}],(i_{1},j]\\},\,\text{o/w.}$

In other words, $i_{1},i_{2}$, and $i_{3}$ are the last three “interval
boundaries” in $\Pi$; see Figure 4.

We first define the base cases of our algorithm. Consider every interval
$I=(i,j]$ that is allowable, i.e.,
$(1-\varepsilon)\sigma\leq\left|I\right|\leq(1+\varepsilon)\sigma$. Without
loss of generality, let $\chi(I)=\mathsf{B}$. We consider letting
$\Pi=\\{(i,j]\\}$ be the trivial partition for $I$. This is locally fair if
and only if no deviating group can form within $I$, i.e., there exists no
$(i^{\prime},j^{\prime}]\subset(i,j]$ such that (i)
$(1-\varepsilon)\sigma\leq(j^{\prime}-i^{\prime})$ (so that
$(i^{\prime},j^{\prime}]$ is allowable), and (ii)
$\left|\text{uhp}({(i^{\prime},j^{\prime}]\cap
R})\right|\geq\max\\{\frac{\beta\sigma}{2},\frac{j^{\prime}-i^{\prime}}{2}\\}$
(so that $(i^{\prime},j^{\prime}]$ is deviating). If the above holds, we have
$\mathsf{LF}(I,i,i,i)=\mathsf{True}$, and
$\mathsf{LF}(I,i_{1},i_{2},i_{3})=\mathsf{False}$ for any other values of
$i_{1},i_{2},$ and $i_{3}$.

Intuitively, if an interval $I=(i,j]\subseteq[n]$ has a fair partition, either
$I$ is a standalone fair allowable interval (i.e.,
$\mathsf{LF}((i,j],i,i,i)=\mathsf{True}$), or there must exist a point
$j^{\prime}\in[j-(1+\varepsilon)\sigma,j-(1-\varepsilon)\sigma)$ such that

(i)

there is a fair partition for $(i,j^{\prime}]$;

(ii)

$(j^{\prime},j]$ is a fair unpartitioned standalone interval;

(iii)

no deviating group is formed by the last 3 intervals of fair partition of
$(i,j^{\prime}]$ and the interval $(j^{\prime},j]$.

arxiv To see this, simply observe that any fair partition of $(i,j]$ that
contains at least two intervals has at least one interval boundary
$j^{\prime}$ between $(j-(1+\varepsilon)\sigma)$ and
$(j-(1-\varepsilon)\sigma)$ (so that the last interval $(j^{\prime},j]$ is
allowable). There is no deviating group formed within interval
$(i,j^{\prime}]$, $(j^{\prime},j]$ or straddling $j^{\prime}$ (such a
deviating group cannot span more than three intervals of a balanced partition
of $(i,j^{\prime}]$). Accordingly, we have the following lemma:

######  Lemma 9.

$\mathsf{LF}((i,j],i_{1},i_{2},i_{3})=\mathsf{True}$ if and only if there
exists a point $i_{4}\in[\max\\{i,i_{3}-(1+\varepsilon)\sigma\\},i_{1}]$ such
that

  * •

$\mathsf{LF}((i_{1},j],i_{1},i_{1},i_{1})=\mathsf{True}$, and

  * •

$\mathsf{LF}((i,i_{1}],i_{2},i_{3},i_{4})=\mathsf{True}$, and

  * •

There is no deviating group forming within $(i_{4},j]$ with the partition
$\\{(i_{4},i_{3}],(i_{3},i_{2}],(i_{2},i_{1}],(i_{1},j]\\}$.

arxiv

###### Proof.

Recall that $\varepsilon\leq\frac{1}{2}$. Thus, every allowable interval, as
well as a potential deviating group, has size between $\frac{\sigma}{2}$ and
$\frac{3\sigma}{2}$. Suppose there exists a deviating group $D$ for a
partition $\Pi$ of $(i,j]$ intersecting more than four contiguous intervals in
$\Pi$. Then $D$ must strictly contain at least three intervals
$\pi_{i},\pi_{i+1},\pi_{i+2}$, and thus we have
$\left|D\right|>3\cdot\frac{\sigma}{2}$, a contradiction. Hence $D$ can
intersect at most four contiguous intervals in any partition $\Pi$ for $X$.
Suppose
$\mathsf{LF}((i_{1},j],i_{1},i_{1},i_{1})=\mathsf{LF}((i,i_{1}],i_{2},i_{3},i_{4})=\mathsf{True}$
for some $i_{4}$. This means (i) interval $(i_{1},j]$ is fair as a standalone
interval; (ii) there is a fair partition $\Pi^{\prime}$ of interval
$(i,i_{1}]$, with the last three interval boundaries being $i_{2}$, $i_{3}$,
and $i_{4}$. Concatentate $\Pi^{\prime}$ with $(i_{1},j]$ as $\Pi$. By the
discussion above, any deviating group $D$ for $\Pi$ intersects at most four
contiguous intervals in $\Pi$. Suppose a such $D$ intersects $(i,i_{4}]$. Then
it must not intersect $(i_{1},j]$ as a consequence, which implies $D$ is also
a deviating group for $\Pi^{\prime}$, a contradiction. Hence $D$ must be
contained in $(i_{4},j]$. However, by the third criteria, there is no
deviating group in $(i_{4},j]$ either. Therefore, no deviating group exists in
$D$, which means $\Pi$ is a fair partition for $(i,j]$. ∎

arxiv In other words, for $i_{1},i_{2}$, and $i_{3}$ to be the last three
interval boundaries in a fair partition for $(i,j]$, the last interval
$(i_{1},j]$ must be fair itself, and there must exist a point $i_{4}$ as the
next (fourth last) interval boundary. Note that it is possible that
$i_{4}=i_{3}$ in the degenerate case when $(i,j]$ is partitioned into less
than 4 intervals. Accordingly, we know that $(i,i_{1}]$ must also be fair with
last three interval boundaries being $i_{2},i_{3}$, and $i_{4}$, as well as
$(i_{4},j]$ must be fair with the interval boundaries being $i_{1},i_{2}$, and
$i_{3}$.

For $\varepsilon\leq 1/3$, as $(i_{4},i_{3}]$ cannot be further separated into
multiple allowable intervals, Lemma 9 can be simplified as follows:

######  Corollary 10.

For $\varepsilon\leq 1/3$,
$\mathsf{LF}((i,j],i_{1},i_{2},i_{3})=\mathsf{True}$ if and only if there
exists a point $i_{4}\in[\max\\{i,i_{3}-(1+\varepsilon)\sigma\\},i_{1}]$ such
that

  * •

$\mathsf{LF}((i_{1},j],i_{1},i_{1},i_{1})=\mathsf{True}$, and

  * •

$\mathsf{LF}((i,i_{1}],i_{2},i_{3},i_{4})=\mathsf{True}$, and

  * •

$\mathsf{LF}((i_{4},j],i_{1},i_{2},i_{3})=\mathsf{True}$.

###### Proof.

The proof follows from Lemma 9. Since
$\mathsf{LF}((i_{4},j],i_{1},i_{2},i_{3})=\mathsf{True}$, there must exist a
fair partition for $(i_{4},j]$ with the last three intervals being
$\\{(i_{3},i_{2}],(i_{2},i_{1}],(i_{1},j]\\}$. By the fact that
$\mathsf{LF}((i,i_{1}],i_{2},i_{3},i_{4})=\mathsf{True}$, we know
$(i_{4},i_{3}]$ is an allowable region. For $\varepsilon\in[0,1/3)$, this
implies
$\left|(i_{4},i_{3}]\right|\leq(1+\varepsilon)\sigma<\frac{2\sigma}{3}<\frac{2(1-\varepsilon)\sigma}{3}$,
i.e., there is no other way to partition $(i_{4},i_{3}]$ in a balanced fashion
other than making it a standalone part. Hence, the partition
$\\{(i_{4},i_{3}],(i_{3},i_{2}],(i_{2},i_{1}],(i_{1},j]\\}$ must be the only
fair partition for $(i_{4},j]$ with the last three intervals being
$\\{(i_{3},i_{2}],(i_{2},i_{1}],(i_{1},j]\\}$, which implies the third
criterion in Lemma 9 is met. ∎

Hence, for a general interval $(i,j]$, to compute
$\mathsf{LF}((i,j],i_{1},i_{2},i_{3})$, it suffices to check for all possible
values of $i_{4}$, each incurring two lookups of previously computed subquery
results and one check of fairness in a partition for an interval of length at
most $4(1+\varepsilon)\sigma$. arxivFor $\varepsilon\in[0,1/3)$, it can be
simplified to three lookups of previously computed subquery results.

#### Algorithm.

arxivWe use Corollary 10 and dynamic programming to compute $\bigvee_{1\leq
i_{1}\leq i_{2}\leq i_{3}\leq
n}\mathsf{LF}\left([0,n],i_{1},i_{2},i_{3}\right)$, as follows. aaaiWe use
Lemma 9 and dynamic programming to compute $\bigvee_{1\leq i_{1}\leq i_{2}\leq
i_{3}\leq n}\mathsf{LF}\left([0,n],i_{1},i_{2},i_{3}\right)$, as follows. Our
algorithm first enumerates all possible allowable intervals $(i,j]$ as base
cases (i.e., $(1-\varepsilon)\sigma\leq j-i\leq(1+\varepsilon)\sigma$), and
computes $\mathsf{LF}((i,j],i,i,i)$ for each such $(i,j]$. Then, for general
$(i,j]$, the algorithm computes $\mathsf{LF}((i,j],i_{1},i_{2},i_{3})$ for all
possible values of $i_{1},i_{2}$, and $i_{3}$ given $i$ and $j$, in increasing
order of $(i+j)$; this ensures all the intermediate subqueries are already
computed before $\mathsf{LF}((i,j],i_{1},i_{2},i_{3})$ is evaluated. After it
computes $\mathsf{LF}((i,j],i_{1},i_{2},i_{3})$ for all possible values of
$i,j,i_{1},i_{2},i_{3}$, it examines whether
$\mathsf{LF}((0,n],i_{1},i_{2},i_{3})=\mathsf{True}$ for some
$i_{1},i_{2},i_{3}$; any such true entry implies a fair partition of $[n]$,
i.e., the original input. Note that $(0,n]=[1,n]$ is the complete set of
points.

#### Running time and Enhancements.

aaaiRefer to the full version for a detailed analysis of the algorithm, as
well as two enhancement strategies that exploit precomputation to avoid
redundant computations. We present the final result:

arxivFor interval $(i,j]$ to belong to the base cases, it must hold that
$j\in[i+(1-\varepsilon)\sigma,i+(1+\varepsilon)\sigma]$, for which
$i\in[0,n-(1-\varepsilon)\sigma]$. Hence, there are $O(n\sigma)$ such pairs.
For each such interval $(i,j]$, whether or not it contains a deviating group
as a standalone interval can be checked naively in $O(\sigma^{3})$-time. Hence
all base cases can be computed within $O(n\sigma^{4})$-time.

For every general interval $(i,j]$, the algorithm needs to enumerate all
possible values of $i_{1},i_{2},$ and $i_{3}$. Note that the ranges for all
possible values of $i_{1}$, $i_{2}$, and $i_{3}$ are exactly
$2\varepsilon\sigma$, $4\varepsilon\sigma$, and $6\varepsilon\sigma$; hence
the number of such 3-tuples are bounded by $O(\varepsilon^{3}\sigma^{3})$. For
each subquery $\mathsf{LF}((i,j],i_{1},i_{2},i_{3})$, the algorithm needs to
enumerate all $O(\varepsilon\sigma)$ possible values of $i_{4}$; for each
$i_{4}$, the lookups of previously computed subqueries incur $O(1)$
computation, whereas the check for fairness for $(i_{4},j]$ can be done
naively in $O(\sigma^{2})$-time. Hence the algorithm computes the values of
all subqueries in $O(\varepsilon^{4}\sigma^{4})$-time for
$\varepsilon\in[0,1/3)$ and $O(\varepsilon^{4}\sigma^{6})$-time for
$\varepsilon\geq 1/3$.

For the last step, the algorithm linear scans
$\mathsf{LF}((0,n],i_{1},i_{2},i_{3})$ for all $O(\varepsilon^{3}\sigma^{3})$
possible values of $(i_{1},i_{2},i_{3})$, which is
$O(\varepsilon^{3}\sigma^{3})$-time. Therefore, the total time complexity of
the algorithm is given by

$O(n\sigma^{4})+O(\varepsilon^{4}\sigma^{6})+O(\varepsilon^{3}\sigma^{3})=O(n\sigma^{5}),$

as $\sigma=O(n)$ and $\varepsilon=O(1)$. For $\varepsilon\in[0,1/3)$, it is
$O(n\sigma^{4})$ with the second term being $O(\varepsilon^{4}\sigma^{4})$.

#### Running time enhancement with precomputation.

In the algorithm above, the naive check for deviating group within a
standalone interval for base cases incurs redundant computations. Instead,
with standard dynamic programming techniques, one can precompute in
$O(n\sigma)$-time for each allowable region $(i,j]$: (i) the number of blue
points and the number of red points in $(i,j]$, i.e., $\left|(i,j]\cap
B\right|$ and $\left|(i,j]\cap R\right|$; and thus (ii) the number of unhappy
points in $(i,j]$ if $(i,j]$ is contained in a blue-majority (resp. red-
majority) interval. These values can be stored using $O(n\sigma)$-memory. When
checking if a deviating group $(i^{\prime},j^{\prime}]$ exists within $(i,j]$,
note that both $(i^{\prime},j^{\prime}]$ and $(i,j]$ need to be standalone
allowable intervals; this gives $i^{\prime}\in(i,i+2\varepsilon\sigma]$ and
$j^{\prime}\in(j-2\varepsilon\sigma,j]$. Therefore, the check can be done in
$O(\varepsilon^{2}\sigma^{2})$ constant-time lookups.

This idea is also useful for speeding up the step of checking whether the
partition $\\{(i_{4},i_{3}],(i_{3},i_{2}],(i_{2},i_{1}],(i_{1},j]\\}$ is a
fair partition of $(i_{4},j]$. Again using standard dynamic programming
techniques, similar to the above, one can precompute in
$O(n\varepsilon^{4}\sigma^{4})$-time for each $(i_{1},i_{2},i_{3},i_{4},j)$
whether the above partition is fair (observe that there are $O(n)$
possibilities for $j$, then at most $2\varepsilon\sigma$ possibilities for
$i_{1}$, then at most $4\varepsilon\sigma$ possibilities for $i_{2}$, and so
on), such that the check can be replaced by $O(1)$-time lookups when
evaluating each $\mathsf{LF}((i,j],i_{1},i_{2},i_{3})$.

For $\varepsilon\in[0,1/3)$, only the first enhancement is needed, for which
the total time complexity of the algorithm is improved to

$O(n\sigma)+O(n\varepsilon^{2}\sigma^{3})+O(\varepsilon^{4}\sigma^{4})+O(\varepsilon^{3}\sigma^{3})=O(n\sigma^{3});$

for $\varepsilon\in[1/3,1/2]$, with both enhancements, the total time
complexity of the algorithm is improved to

$O(n\sigma)+O(n\varepsilon^{4}\sigma^{4})+O(n\varepsilon^{2}\sigma^{3})+O(\varepsilon^{4}\sigma^{4})+O(\varepsilon^{3}\sigma^{3})=O(n\sigma^{4}),$

as $\sigma=O(n)$ and $\varepsilon=O(1)$.

######  Theorem 11.

Given an instance $(X,\sigma)$ with $|X|=n$ and $\sigma\in[n]$, and parameters
$\varepsilon\in[0,1/2]$ and $\beta\in[1/2,1]$, a $(\varepsilon,\beta)$-locally
fair partition of $[n]$ can be computed, or report that none exists, in time
$O(n\sigma^{3})$ for $\varepsilon\in[0,1/3)$ and $O(n\sigma^{4})$ for
$\varepsilon\in[1/3,1/2]$.

##  6 Conclusion

arxivWe note that many of our results do extend to the fixed $k$ version. The
existence results in Section 3 extend to the fixed-$k$ case naturally. The
dynamic program of Section 5 can be extended to handle a fixed $k$ in a
straightforward manner.

The main open question is extending the model to two dimensions, which poses
several challenges: how to define feasible regions, how these regions tile the
plane, how a deviating group/region is defined. Part of the difficulty stems
from the fact that points are no longer linearly ordered. arxivAlthough
Voronoi region based methods have been proposed to construct compact regions,
incorporating fairness seems very hard, and none of the existing algorithms
extend to this case even to construct an approximate solution for clustered
inputs. Currently, no polynomial-time algorithm is known even if each region
of the partition is restricted to be an axis-aligned rectangle. In contrast,
the additional freedom when defining two dimensional regions suggests a fair
partition exists for a larger value of parameters assuming the input points
are not concentrated along a $1$D curve. Despite the challenges, the lower
bounds presented in the paper directly extend to two dimensions. Additionally,
the algorithm described in Section 5 may extend to $2$D when when the
partitions considered have sufficient structure, such as when we restrict to a
hierarchical partition of simple shapes, and the deviating region spans $O(1)$
regions of the partition.

## Acknowledgments

The authors would like to thank Hsien-Chih Chang, Brandon Fain, and anonymous
reviewers for helpful discussions and feedback. This work is supported by NSF
grants CCF-2113798, IIS-18-14493, and CCF-20-07556 and ONR award
N00014-19-1-2268.

## References

  * [1] Micah Altman and Michael McDonald.  The promise and perils of computers in redistricting.  Duke Journal of Constitutional Law & Public Policy, 5:69, 2010\.
  * [2] H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh.  Justified representation in approval-based committee voting.  Social Choice and Welfare, 48(2):461–485, 2017.
  * [3] Haris Aziz, Edith Elkind, Shenwei Huang, Martin Lackner, Luis Sánchez Fernández, and Piotr Skowron.  On the complexity of extended and proportional justified representation.  In AAAI, pages 902–909, 2018.
  * [4] Sachet Bangia, Christy Vaughn Graves, Gregory Herschlag, Han Sung Kang, Justin Luo, Jonathan C Mattingly, and Robert Ravier.  Redistricting: Drawing the line, 2017.  arXiv:1704.03360.
  * [5] Amariah Becker and Justin Solomon.  Redistricting algorithms, 2020.  arXiv:2011.09504.
  * [6] Allan Borodin, Omer Lev, Nisarg Shah, and Tyrone Strangway.  Big city vs. the great outdoors: voter distribution and how it affects gerrymandering.  In IJCAI, pages 98–104, 2018.
  * [7] Steven J. Brams, D. Marc Kilgour, and M. Remzi Sanver.  A minimax procedure for electing committees.  Public Choice, 132(3):401–420, 2007.
  * [8] John R. Chamberlin and Paul N. Courant.  Representative deliberations and representative decisions: Proportional representation and the borda rule.  The American Political Science Review, 77(3):718–733, 1983.
  * [9] Jowei Chen and Jonathan Rodden.  Unintentional gerrymandering: Political geography and electoral bias in legislatures.  Quarterly Journal of Political Science, 8(3):239–269, 2013.
  * [10] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala.  Proportionally fair clustering.  In ICML, pages 1032–1041, 2019.
  * [11] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii.  Fair clustering through fairlets.  In NeurIPS, pages 5029–5037, 2017.
  * [12] Vincent Cohen-Addad, Philip N Klein, and Neal E Young.  Balanced centroidal power diagrams for redistricting.  In ACM SIGSPATIAL, pages 389–396, 2018.
  * [13] Daryl DeFord, Moon Duchin, and Justin Solomon.  Recombination: a family of markov chains for redistricting.  Harvard Data Science Review, 2021.
  * [14] H. R. Droop.  On methods of electing representatives.  Journal of the Statistical Society of London, 44(2):141–202, 1881\.
  * [15] Duncan K Foley.  Lindahl’s solution and the core of an economy with public goods.  Econometrica, pages 66–72, 1970.
  * [16] D. Gale and L. S. Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [17] Sebastian Goderbauer.  Political districting for elections to the german bundestag: an optimization-based multi-stage heuristic respecting administrative boundaries.  In Operations Research, pages 181–187, 2014.
  * [18] Gregory Herschlag, Han Sung Kang, Justin Luo, Christy Vaughn Graves, Sachet Bangia, Robert Ravier, and Jonathan C Mattingly.  Quantifying gerrymandering in North Carolina.  Statistics and Public Policy, 7(1):30–38, 2020.
  * [19] Sidney Wayne Hess, JB Weaver, HJ Siegfeldt, JN Whelan, and PA Zitlau.  Nonpartisan political redistricting by computer.  Operations Research, 13(6):998–1006, 1965.
  * [20] Nicole Immorlica, Robert Kleinberg, Brendan Lucier, and Morteza Zadomighaddam.  Exponential segregation in a two-dimensional schelling model with tolerant individuals.  In ACM-SIAM SODA, pages 984–993, 2017.
  * [21] Erik Lindahl.  Just taxation—a positive solution.  In Classics in the Theory of Public Finance, pages 168–176. Springer, 1958.
  * [22] Yan Y. Liu, Wendy K. Tam Cho, and Shaowen Wang.  PEAR: a massively parallel evolutionary computation approach for political redistricting optimization and analysis.  Swarm and Evolutionary Computation, 30:78–92, 2016.
  * [23] Burt L. Monroe.  Fully proportional representation.  The American Political Science Review, 89(4):925–940, 1995.
  * [24] Ariel D. Procaccia and Jamie Tucker-Foltz.  Compact redistricting plans have many spanning trees, 2021.  arXiv:2109.13394.
  * [25] L. Sánchez-Fernández, E. Elkind, M. Lackner, N. Fernández, J. A. Fisteus, P. Basanta Val, and P. Skowron.  Proportional justified representation.  In AAAI, pages 670–676, 2017.
  * [26] Herbert E Scarf.  The core of an n person game.  Econometrica: Journal of the Econometric Society, pages 50–69, 1967\.
  * [27] Thomas C. Schelling.  Dynamic models of segregation.  The Journal of Mathematical Sociology, 1(2):143–186, 1971.
  * [28] L. Shapley and H. Scarf.  On cores and indivisibility.  Journal of Mathematical Economics, 1(1):23–37, 1974.
  * [29] Lukas Svec, Sam Burden, and Aaron Dilley.  Applying voronoi diagrams to the redistricting problem.  The UMAP journal, 28(3):313–329, 2007.
  * [30] Archer Wheeler and Philip N Klein.  The impact of highly compact algorithmic redistricting on the rural-versus-urban balance.  In ACM SIGSPATIAL, pages 397–400, 2020.
  * [31] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi.  Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment.  In ACM WWW, pages 1171–1180, 2017.
  * [32] Junfu Zhang.  Tipping and residential segregation: a unified schelling model.  Journal of Regional Science, 51(1):167–193, 2011.


# Phonon Boltzmann equation non-local in space and time: the partial failure
of the generalized Fourier law

Philip B. Allen<EMAIL_ADDRESS>Department of Physics and
Astronomy, Stony Brook University, Stony Brook, New York 11794-3800, USA

###### Abstract

The purpose of this note is to clarify the solution of the non-local Peierls
Boltzmann equation found by Hua and Lindsay (Phys. Rev. B 102, 104310 (2020)).
They used methods of Cepellotti and Marzari. The response function “thermal
distributor” is discussed. The new, “non-Fourier” term $\vec{B}$
[$\vec{J}_{\rm th}=-\kappa\vec{\nabla}T+\vec{B}]$ that occurs in non-local
situations, gives rise also to a new term in the thermal distributor.

##  I Fourier law and nonlocal correction

Transport in bulk systems, with currents small enough to linearize, is given
by simple linear response functions, such as the Fourier law for thermal
conductivity, $\vec{J}_{\rm th}=-\kappa\vec{\nabla}T$, where the temperature
is close to a background temperature $T_{0}$, deviating by a small correction
$\vec{r}\cdot\vec{\nabla}T$, with $\vec{\nabla}T$ uniform in space. However,
in small systems, the current and temperature need to be studied on distance
scales less than the mean free paths of heat carriers. A sensible assumption
is that a non-local Fourier law, $\vec{J}_{\rm F}(\vec{r})=-\int d\vec{r}^{\
\prime}\kappa(\vec{r},\vec{r}^{\ \prime})\vec{\nabla}T(\vec{r}^{\ \prime})$
should describe the linear response. However, for non-uniform heat driving, a
correction has been noticed recently. An additional, non-Fourier term
$\vec{J}_{\rm non-F}(\vec{r})$ appears. This was found recently by Hua and
Lindsay Hua  _et al._ (2019); Hua and Lindsay (2020). Hints of this can be
found in earlier literature. Boltzmann theory shows how this happens. The
derivation given below assumes heat carried by phonons in insulators. Similar
results are expected for heat carried by electrons in metals, and also for
electrical conduction. The derivation includes time-dependent driving of
phonon heat.

##  II Non-local Peierls Boltzmann equation

The phonon, or Peierls, Boltzmann equation Peierls (1929); Ziman (1960) (PBE),
linearized for small deviations from equilibrium, says that the phonon
distribution $N_{Q}(\vec{r},t)$ evolves according to

$\displaystyle\frac{dN_{Q}}{dt}$ $\displaystyle=$
$\displaystyle\left(\frac{dN_{Q}}{dt}\right)_{\rm
drift}+\left(\frac{dN_{Q}}{dt}\right)_{\rm
coll}+\left(\frac{dN_{Q}}{dt}\right)_{\rm ext},$ $\displaystyle{\rm where}\
\left(\frac{dN_{Q}}{dt}\right)_{\rm
drift}=-\vec{v}_{Q}\cdot\vec{\nabla}_{\vec{r}}N_{Q},$ $\displaystyle{\rm and}\
\left(\frac{dN_{Q}}{dt}\right)_{\rm
coll}=-\sum_{Q^{\prime}}R_{QQ^{\prime}}\Delta N_{Q^{\prime}}(\vec{r},t),$
$\displaystyle{\rm and}\ \left(\frac{dN_{Q}}{dt}\right)_{\rm
ext}=\frac{1}{C(T_{0})}\left(\frac{dn_{Q}}{dT}\right)_{T_{0}}P_{Q}(\vec{r},t).$
(1)

The symbol $Q=(\vec{q},j)$ enumerates the $N=3nN_{\rm cell}$ eigenstates of
the harmonic vibrational sustem. The scattering operator $R_{QQ^{\prime}}$ is
linearized for small deviations $\Delta N_{Q}$ from the local equilibrium
distribution, a Bose-Einstein distribution $n_{Q}$ at the local temperature
$T(\vec{r},t)$; $P_{Q}(\vec{r},t)$ is the rate per unit volume of energy input
into mode $Q$, and $T_{0}$ is the background temperature. The specific heat
$C(T_{0})$ has units energy divided by temperature$\times$volume, and $P_{Q}$
has units power per volume. The external power input $P_{Q}$ causes mode $Q$
to increase in energy per unit time by an amount which would increase its
effective temperature by $d\Delta T_{Q}(\vec{r},t)/dt=P_{Q}(\vec{r},t)/C$. For
simple driving, with $P_{Q}$ independent of $Q$, the modal temperature
increase $\Delta T_{Q}$ is the same for all modes $Q$.

Non-local Boltzmann theories require a definition of local temperature; the
one that works in Boltzmann theory is that the local energy density
$u(\vec{r},t)$ is $(1/V)\sum_{Q}\hbar\omega_{Q}n_{Q}(T(\vec{r},t))$. This
means that there is no energy in the deviation $\Delta N_{Q}\equiv
N_{Q}(\vec{r},t)-n_{Q}(T(\vec{r},t))$. The sum
$(1/V)\sum_{Q}\hbar\omega_{Q}\Delta N_{Q}=0$ defines $T(\vec{r},t)$.

##  III Scattering and Temperature

Each scattering event conserves phonon energy:
$\sum_{Q}\hbar\omega_{Q}(d\Delta N_{Q}/dt)_{\rm scatt}=0$, whether linearized
in $\Delta N_{Q}$ or not. In linear approximation, this is equivalent to the
sum rule $\sum_{Q}\hbar\omega_{Q}R_{QQ^{\prime}}=0$. The operator $\hat{R}$
(where $R_{QQ^{\prime}}=\langle Q|\hat{R}|Q^{\prime}\rangle$) has a left null
eigenvector $\langle\hbar\omega|\hat{R}=0$, where
$\hbar\omega_{Q}=\langle\hbar\omega|Q\rangle$. The vector $|\cdot\rangle$ lies
in the space of harmonic eigenstates. The states $|Q\rangle$ are a complete
orthonormal basis. In the coordinate space enumerated by unit cell $\ell$ at
$\vec{R}_{\ell}$, and atom number $n$, and Cartesian coordinate $i$,

$\langle\ell ni|Q\rangle=\frac{1}{\sqrt{N_{\rm
cells}}}e^{i\vec{q}\cdot\vec{R}_{\ell}}\epsilon_{Q}(n,i),$ (2)

where the polarization vector $\hat{\epsilon}_{Q}$ is normalized,
$\sum_{n,i}|\epsilon_{Q}(n,i)|^{2}=1$. But $\hat{R}$ is not symmetric. The
corresponding null right eigenvector is $|n(n+1)\hbar\omega\rangle$. This is
equivalent to the statement that if the distribution
$N_{Q}=n_{Q}(T(\vec{r},t))+\Delta N_{Q}(\vec{r},t)$ consists of shifting the
occupancy of every mode $Q$ away from local equilbrium $T(\vec{r},t)$ by
$\Delta N_{Q}=(dn_{Q}/dT)\Delta T(\vec{r},t)$ with the same $\Delta
T(\vec{r},t)$ for each mode, the shifted distribution is already locally
thermalized and doesn’t experience net scattering.

A symmetrized scattering operator $\hat{\Omega}$ is Simons (1960); Krumhansl
(1965)

$\displaystyle\hat{\Omega}$ $\displaystyle=$
$\displaystyle[\hat{n}(\hat{n}+1)]^{-1/2}\hat{R}[\hat{n}(\hat{n}+1)]^{1/2}$
$\displaystyle\Omega_{QQ^{\prime}}$ $\displaystyle=$
$\displaystyle[n_{Q}(n_{Q}+1)]^{-1/2}R_{QQ^{\prime}}[n_{Q^{\prime}}(n_{Q^{\prime}}+1)]^{1/2}.$
(3)

The operator $\hat{n}$ is defined as $\langle
Q|n|Q^{\prime}\rangle=n_{Q}\delta_{QQ^{\prime}}$. The Bose factors $n_{Q}$ in
Eq. 3 are taken at the background temperature $T_{0}$, not the local
equilibrium temperature $T(\vec{r},t)$. Similarly the operator $\hat{n}$ is
defined at $T=T_{0}$ unless explicitly written as $\hat{n}(\vec{r},t)$. The
Boltzmann Eq. 1 is now

$\displaystyle\frac{dN(\vec{r},t)\rangle}{dt}$ $\displaystyle=$
$\displaystyle-\hat{\vec{v}}\cdot\vec{\nabla}_{\vec{r}}|N(\vec{r},t)\rangle$
(4) $\displaystyle-$
$\displaystyle\sqrt{\hat{n}(\hat{n}+1)}\hat{\Omega}\frac{1}{\sqrt{\hat{n}(\hat{n}+1)}}|\Delta
N(\vec{r},t)\rangle$ $\displaystyle+$
$\displaystyle\hat{n}(\hat{n}+1)\frac{\hbar\hat{\omega}}{Ck_{B}T^{2}}|P(\vec{r},t)\rangle,$

where $\langle Q|P\rangle=P_{Q}$ The operators $\hat{\vec{v}}$ and
$\hat{\omega}$ are diagonal in $Q$-representation, $\langle
Q|\hat{\vec{v}}|Q^{\prime}\rangle=\vec{v}_{Q}\delta_{QQ^{\prime}}$ and
$\langle Q|\hat{\omega}|Q^{\prime}\rangle=\omega_{Q}\delta_{QQ^{\prime}}$.

Now define from $\Delta N_{Q}$ a deviation function $\Phi_{Q}$,

$\displaystyle\Delta N_{Q}$ $\displaystyle=$ $\displaystyle
N_{Q}-n_{Q}(\vec{r},t)\equiv\sqrt{n_{Q}(n_{Q}+1)}\Phi_{Q}(\vec{r},t)$
$\displaystyle|\Delta N\rangle$ $\displaystyle=$
$\displaystyle|N\rangle-|n(\vec{r},t)\rangle\equiv\sqrt{\hat{n}(\hat{n}+1)}|\Phi(\vec{r},t)\rangle$
(5)

Then Eq. 4 becomes

$\frac{\partial|\Phi(\vec{r},t)\rangle}{\partial
t}+\hat{\vec{v}}\cdot\vec{\nabla}_{\vec{r}}|\Phi(\vec{r},t)\rangle+\hat{\Omega}|\Phi(\vec{r},t)\rangle=|A(\vec{r},t)\rangle,$
(6) $\displaystyle|A(\vec{r},t)\rangle$ $\displaystyle=$
$\displaystyle-[\hat{n}(\hat{n}+1)]^{-1/2}\left[\left(\frac{\partial}{\partial
t}+\hat{\vec{v}}\cdot\vec{\nabla}_{\vec{r}}\right)\Delta
T(\vec{r},t)\right]\left|\frac{dn}{dT}\right\rangle$ (7) $\displaystyle+$
$\displaystyle[\hat{n}(\hat{n}+1)]^{1/2}\frac{\hbar\hat{\omega}}{Ck_{B}T^{2}}|P(\vec{r},t)\rangle,$

The inhomogeneous part $|A\rangle$ has been separated. It drives the deviation
$|\Phi\rangle$ from local equilibrium, $|\Phi\rangle=0$. Because of
linearization, the equation is simplified by a Fourier transform,

$\displaystyle|X(\vec{k},\omega)\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{V}\int^{V}d\vec{r}\int_{-\infty}^{\infty}dt|X(\vec{r},t)\rangle\exp[-i(\vec{k}\cdot\vec{r}-\omega
t)]$ $\displaystyle|X(\vec{r},t)\rangle$ $\displaystyle=$
$\displaystyle\sum_{\vec{k}}\int_{-\infty}^{\infty}d\omega|X(\vec{k},\omega)\rangle\exp[i(\vec{k}\cdot\vec{r}-\omega
t)]$ (8)

The different Fourier components are not coupled, and are treated one at a
time, as if
$|X(\vec{r},t)\rangle=|X(\vec{k},\omega)\rangle\exp[i(\vec{k}\cdot\vec{r}-\omega
t)]$. The symbol $\omega$ is the external frequency, not to be confused with
$\hat{\omega}$ which is the operator version of the phonon frequency
$\omega_{Q}$. Equations 6 and 7 become

$\left[\hat{\Omega}+i(\vec{k}\cdot\hat{\vec{v}}-\omega\hat{1})\right]|\Phi\rangle=|A(\vec{k},\omega)\rangle$
(9)
$|A\rangle=\frac{\sqrt{\hat{n}(\hat{n}+1)}}{k_{B}T^{2}}\left[-i(\vec{k}\cdot\hat{\vec{v}}-\omega\hat{1})\Delta
T|\hbar\omega\rangle+\frac{\hbar\hat{\omega}}{C}|P\rangle\right]$ (10)

Mode space has so far been described in $Q$-representation by harmonic
eigenstates $|Q\rangle$. It is convenient to also use the
“relaxon”-representation $|\alpha\rangle$ of eigenstates Guyer and Krumhansl
(1966); Maris (1969); Cepellotti and Marzari (2016) of $\hat{\Omega}$.

$\hat{\Omega}|\alpha\rangle=\gamma_{\alpha}|\alpha\rangle$ (11)

where

$\langle\alpha|\beta\rangle=\delta_{\alpha\beta}\ \ {\rm and}\ \
\sum_{\alpha}|\alpha\rangle\langle\alpha|=\hat{1}.$ (12)

The eigenvalues $\gamma_{\alpha}$ are relaxation rates,
$\gamma_{\alpha}=1/\tau_{\alpha}$. In this basis, Eq. 9 has the form

$\sum_{\beta}\left[\gamma_{\alpha}\delta_{\alpha\beta}+i(\vec{k}\cdot\vec{v}_{\alpha\beta}-\omega\delta_{\alpha\beta})\right]\Phi_{\beta}=A_{\alpha},$
(13)

where $\Phi_{\beta}=\langle\beta|\Phi\rangle$ and
$A_{\alpha}=\langle\alpha|A\rangle$. There are $N$ modes $Q$ ($N=3N_{\rm
cells}n_{\rm at}$ where $n_{\rm at}$ is the number of atoms in the unit cell),
and Eq. 13 gives $N$ equations for the $N$ unknown components $\Phi_{\alpha}$
of the deviation function. But there are two fields ($|\Delta T\rangle$ and
$|P\rangle$) driving the distribution out of equilibrium, of which one
(typically $|\Delta T\rangle$) is unknown. An extra equation is needed. That
equation is the definition of local temperature.

There is one null eigenvector, $|\alpha=0\rangle\equiv|0\rangle$ with
eigenvalue $\gamma_{0}=0$. The vectors $\langle 0|$ and $|0\rangle$ deviate
only by factors $[\hat{n}(\hat{n}+1)]^{\pm 1/2}$ from the null left
$(\langle\hbar\omega|)$ and right $|dn/dT\rangle$ eigenvectors of $\hat{R}$.
In $Q$-representation, the null eigenvector is

$\langle
Q|0\rangle=\sqrt{n_{Q}(n_{Q}+1)}\frac{\hbar\omega_{Q}}{\sqrt{CVk_{B}T^{2}}}$
(14)

The factor $1/\sqrt{VCk_{B}T^{2}}$ normalizes the state, $\langle
0|0\rangle=1$. The definition of temperature takes the form

$\displaystyle\frac{1}{V}\sum_{Q}$ $\displaystyle\hbar\omega_{Q}\Delta
N_{Q}=0=\frac{1}{V}\sum_{Q}\hbar\omega_{Q}\sqrt{n_{Q}(n_{Q}+1)}\Phi_{Q}$ (15)
$\displaystyle=\sqrt{\frac{Ck_{B}T^{2}}{V}}\langle
0|\Phi\rangle=\sqrt{\frac{Ck_{B}T^{2}}{V}}\Phi_{0}=0.$

This shows that there are actually only $N-1$ unknown parts of $|\Phi\rangle$,
because the $\alpha=0$ component, $\langle 0|\Phi\rangle=\Phi_{0}$ must be
zero by the definition of local temperature.

Now we can rewrite the formula for $|A\rangle$ using Eqs. 10 and 14,

$|A\rangle=\sqrt{\frac{V}{Ck_{B}T^{2}}}\left[-i(\vec{k}\cdot\hat{\vec{v}}-\omega\hat{1})C\Delta
T(\vec{k},\omega)+\hat{P}(\vec{k},\omega)\right]|0\rangle$ (16)

where $\langle Q|\hat{P}|Q^{\prime}\rangle=P_{Q}\delta_{QQ^{\prime}}$. Now
look at the $\alpha=0$ component of Eq. 13,

$i\vec{k}\cdot\sum_{\beta}^{\neq 0}\vec{v}_{0\beta}\Phi_{\beta}=A_{0}$ (17)

The left hand side of Eq. 17 is

$\langle
0|i\vec{k}\cdot\vec{v}|\Phi\rangle=\sqrt{\frac{V}{Ck_{B}T^{2}}}i\vec{k}\cdot\vec{J}$
(18)

where $\vec{J}(\vec{k},\omega)$ is the energy (or heat) current density,
$(1/V)\sum_{Q}\hbar\omega_{Q}\vec{v}_{Q}[N_{Q}(\vec{k},\omega)-n_{Q}(\vec{k},\omega)]$.
The right hand side of Eq. 17 is

$\langle 0|A\rangle=\sqrt{\frac{V}{Ck_{B}T^{2}}}\left(i\omega C\Delta
T+\bar{P}\right),$ (19)

where $\bar{P}=\langle 0|\hat{P}|0\rangle$, or

$\bar{P}\equiv\sum_{Q}\frac{C_{Q}}{C}P_{Q}\ \ {\rm and}\ \
C_{Q}=\frac{1}{V}\hbar\omega_{Q}\frac{dn_{Q}}{dT},$ (20)

and $C=\sum_{Q}C_{Q}$ is the total specific heat. If $P_{Q}$ is independent of
$Q$, then $P_{Q}=\bar{P}$ for all modes $Q$. Thus the $\alpha=0$ part of the
Boltzmann equation expresses energy conservation. In $(\vec{r},t)$
representation,

$\vec{\nabla}_{\vec{r}}\cdot\vec{J}=-\frac{\partial u}{\partial t}+\bar{P}.$
(21)

where $\partial u/\partial t=C\partial\Delta T/\partial t\rightarrow-i\omega
C\Delta T$.

We can now “reinterpret” Eq. 13 as a system of $N-1$ linear equations (the sum
over $\beta$ does not include $\beta=0$ because $\Phi_{0}=0$). The
$(N-1)\times(N-1)$ matrix
$\Omega_{\alpha\beta}=\gamma_{\alpha}\delta_{\alpha\beta}$ is now positive-
definite. We still need to invert the non-Hermitean matrix on the left side of
Eq. 13 in order to solve for $|\Phi\rangle$.

##  IV The Solution

The method of solution is given by Hua and Lindsay Hua and Lindsay (2020). A
earlier version is in a paper by Cepellotti and Marzari Cepellotti and Marzari
(2017). Rewrite Eq. 13 by rescaling the distribution function $\Phi_{\alpha}$
and driving term $A_{\alpha}$:

$\Psi_{\beta}\equiv\gamma_{\beta}^{1/2}\Phi_{\beta}\ {\rm and}\
B_{\alpha}\equiv\gamma_{\alpha}^{-1/2}A_{\alpha}.$ (22)

Equation 13 then becomes $[\hat{1}+i\hat{\Gamma}]|\Psi\rangle=|B\rangle$, or

$\displaystyle\sum_{\beta}\left[\delta_{\alpha\beta}+i\Gamma_{\alpha\beta}\right]\Psi_{\beta}=B_{\alpha}$
$\displaystyle\Gamma_{\alpha\beta}$ $\displaystyle=$
$\displaystyle\vec{k}\cdot\left(\gamma_{\alpha}^{-1/2}\vec{v}_{\alpha\beta}\gamma_{\beta}^{-1/2}\right)-\gamma_{\alpha}^{-1}\omega\delta_{\alpha\beta}$
(23)

The matrix $\hat{\Gamma}$ is real-symmetric, so it has real eigenvalues,
$\lambda_{m}$:

$\hat{\Gamma}(\vec{k},\omega)|m\rangle=\lambda_{m}(\vec{k},\omega)|m\rangle.$
(24)

In this basis, Eq. 23 is $(1+i\lambda_{m})\Psi_{m}=B_{m}$, where
$\Psi_{m}=\langle m|\Psi\rangle$, etc. Then the distribution function in the
relaxon basis (the eigenbasis of $\hat{\Omega}$) is

$\displaystyle\Psi_{\alpha}=\sum_{\beta}S_{\alpha\beta}B_{\beta},\ {\rm or}\ \
\Phi_{\alpha}=\sum_{\beta}\left(\gamma_{\alpha}^{-1/2}S_{\alpha\beta}\gamma_{\beta}^{-1/2}\right)A_{\beta},$
$\displaystyle{\rm where}\ \
\langle\alpha|\hat{S}|\beta\rangle=S_{\alpha\beta}=\sum_{m}\langle\alpha|m\rangle\frac{1}{1+i\lambda_{m}(\vec{k},\omega)}\langle
m|\beta\rangle.$ (25)

This is the desired solution. In the spatially homogeneous ($\vec{k}=0$) and
static ($\omega=0$) case, $\hat{\Gamma}=0$ and $\lambda_{m}=0$, so
$S_{\alpha\beta}=\delta_{\alpha\beta}$ and the bulk solution
$\Phi_{\alpha}=\gamma_{\alpha}^{-1}A_{\alpha}$ is recovered.

##  V Heat current

The operator $\hat{\Omega}$ is positive if we exclude the null space. The
operator $\hat{S}=(\hat{1}+i\hat{\Gamma})^{-1}$ is defined in this “positive”
or $p$-space. It is convenient to define another operator in the same
$p$-space,

$\displaystyle\hat{W}$ $\displaystyle\equiv$
$\displaystyle\hat{\Omega}^{-1/2}\hat{S}\hat{\Omega}^{-1/2}$ $\displaystyle
W_{\alpha\beta}$ $\displaystyle=$
$\displaystyle\gamma_{\alpha}^{-1/2}S_{\alpha\beta}\gamma_{\beta}^{-1/2}$ (26)

The solution of the Boltzmann equation is then

$|\Phi\rangle=\hat{W}|A\rangle_{p}$ (27)

where $|A\rangle_{p}$ is the part of the driving term that is orthogonal to
$|0\rangle$ (and thus lies in $p$-space),

$|A\rangle_{p}=\sqrt{\frac{V}{Ck_{B}T^{2}}}\left[-i\vec{k}\cdot\hat{\vec{v}}C\Delta
T+(\hat{P}-\bar{P}\hat{1})\right]|0\rangle.$ (28)

As required, the inner product $\langle 0|A\rangle_{p}$ vanishes, because it
has a term proportional to $\langle 0|\hat{\vec{v}}|0\rangle$ which is zero
because $\hat{\vec{v}}$ is an odd operator, and a term proportional to
$\langle 0|(\hat{P}-\bar{P}\hat{1})|0\rangle$ that is zero because $\langle
0|\hat{P}|0\rangle\equiv\bar{P}$. From $|\Phi\rangle$ we get the heat current
density $\vec{J}$,

$\vec{J}=\sqrt{\frac{Ck_{B}T^{2}}{V}}\langle
0|\hat{\vec{v}}|\Phi\rangle=\vec{J}_{\rm F}+\vec{J}_{\rm non-F}.$ (29)

The “generalized Fourier” component $\vec{J}_{\rm F}$ is

$\vec{J}_{\rm F}(\vec{k},\omega)=-\kappa(\vec{k},\omega)\cdot(i\vec{k})\Delta
T(\vec{k},\omega),$ (30) $\kappa(\vec{k},\omega)=C\ \langle 0|\hat{\vec{v}}\
\hat{W}(\vec{k},\omega)\ \hat{\vec{v}}|0\rangle.$ (31)

The “non-Fourier” term is

$\vec{J}_{\rm non-F}(\vec{k},\omega)=\langle
0|\vec{\hat{v}}\hat{W}[\hat{P}(\vec{k},\omega)-\bar{P}(\vec{k},\omega)\hat{1}]|0\rangle.$
(32)

This extra, non-Fourier, component of the current was found by Hua et al. Hua
_et al._ (2019) in an RTA treatment. A version is in the paper by Mahan and
Claro Mahan and Claro (1988). In their version, there was no external
insertion $P$ except via boundary conditions. It was rederived by Hua and
Lindsay Hua and Lindsay (2020) in a more complete treatment (not using RTA).
Reference Hua  _et al._ , 2019 gives additional parts of the non-Fourier term
that arise from boundary conditions, but solved only in RTA. Boundary terms do
not appear here; the present derivation, like ref. Hua and Lindsay, 2020,
assumes an infinite homogeneous sample.

In a d.c. situation ($\omega=0$), the insertion term $\hat{P}(\vec{r})$ should
have a zero spatial average: $P(\vec{k}=0,\omega=0)=0$. Otherwise, the sample
experiences net heating or cooling. The spatially homogeneous ($\vec{k}=0$)
part of the “non-Fourier” current is zero. Also, when $\vec{k}=0$ and
$\omega=0$, $\hat{W}(0,0)=\hat{\Omega}^{-1}$ and the bulk static thermal
conductivity is recovered,

$\kappa(\vec{k}=0,\omega=0)=C\ \langle 0|\hat{\vec{v}}\ \hat{\Omega}^{-1}\
\hat{\vec{v}}|0\rangle.$ (33)

##  VI Thermal distributor

The local temperature distribution $T(\vec{r},t)$ can be found from energy
conservation (Eq. 21),

$\Delta T(\vec{k},\omega)=\frac{1}{i\omega
C}\left[i\vec{k}\cdot\left(\vec{J}_{\rm F}(\vec{k},\omega)+\vec{J}_{\rm
non-F}(\vec{k},\omega)\right)-\bar{P}(\vec{k},\omega)\right].$ (34)

If $P_{Q}(\vec{k},\omega)$ is independent of $Q$ (i.e. $\hat{P}=\bar{P}$), the
non-Fourier current is zero, and the local temperature variation is given by a
simple nonlocal response function, the “thermal distributor”
$\Theta(\vec{k},\omega)$,

$\Delta T(\vec{k},\omega)=\Theta(\vec{k},\omega)\bar{P}(\vec{k},\omega)$ (35)

where

$\Theta(\vec{k},\omega)=\frac{1}{\vec{k}\cdot\kappa(\vec{k},\omega)\cdot\vec{k}-i\omega
C}$ (36)

This is Eq. 38 of ref. Hua and Lindsay, 2020. The function $\Theta$ was
defined in ref. Allen and Perebeinos, 2018. The name “thermal distributor,”
has been changed from the previous name “thermal susceptibility,” and a factor
of C has been removed from the definition. When $\hat{P}\neq\bar{P}$, there is
another term,

$\Delta
T(\vec{k},\omega)=\Theta(\vec{k},\omega)\bar{P}(\vec{k},\omega)-\frac{i\vec{k}\cdot\vec{J}_{\rm
non-F}(\vec{k},\omega)}{\vec{k}\cdot\kappa(\vec{k},\omega)\cdot\vec{k}-i\omega
C}$ (37)

Griffin Griffin (1965) makes an interesting argument that may be related to
thermal distributors. Guyer and Krumhansl Guyer and Krumhansl (1966) noticed
that Griffin’s argument is related to the mean-field method relating non-
interacting to interacting electrical susceptibility.

##  VII appendix: terminology

Various names are given to the operator
$-\vec{v}_{Q}\cdot\vec{\nabla}_{\vec{r}}$: (a) “drift operator”, (b)
“advection operator”, (c) “convection operator”, or (d) “diffusion operator”.
Sometimes the combination $\partial/\partial
t+\vec{v}_{Q}\cdot\vec{\nabla}_{\vec{r}}$ is called the “drifting operator” .
The process these words are describing is that the occupancy
$N_{Q}(\vec{r},t+\Delta t)$, in a completely ballistic system, is the same as
$N_{Q}(\vec{r}-\vec{v}_{Q}\Delta t,t)$, so that

$\displaystyle\left(\frac{dN_{Q}}{dt}\right)_{\rm drift}$ $\displaystyle=$
$\displaystyle\lim_{\Delta t\rightarrow 0}\left[\frac{N_{Q}(\vec{r},t+\Delta
t)-N_{Q}(\vec{r},t)}{\Delta t}\right]_{\rm ballistic}$ $\displaystyle=$
$\displaystyle-\vec{v}_{Q}\cdot\vec{\nabla}_{\vec{r}}N_{Q}.$

The term I use, “drift operator”, makes sense; “diffusion operator” does not.

## References

  * Hua  _et al._ (2019) Chengyun Hua, L. Lindsay, Xiangwen Chen, and A. J. Minnich, “Generalized Fourier’s law for nondiffusive thermal transport: Theory and experiment,” Phys. Rev. B 100, 085203 (2019).
  * Hua and Lindsay (2020) Chengyun Hua and Lucas Lindsay, “Space-time dependent thermal conductivity in nonlocal thermal transport,” Phys. Rev. B 102, 104310 (2020).
  * Peierls (1929) R. E. Peierls, “Zur kinetischen Theorie der Wärmeleitung in Kristallen,” Ann. Phys. 395, 1055–1101 (1929).
  * Ziman (1960) J. M. Ziman,  _Electrons and Phonons_ (Oxford, London, 1960).
  * Simons (1960) S. Simons, “The Boltzmann equation for a bounded medium I. General theory,” Phil. Trans. Roy. Soc. London, Series A, Math. Phys. Sci. 253, 137–184 (1960).
  * Krumhansl (1965) J A Krumhansl, “Thermal conductivity of insulating crystals in the presence of normal processes,” Proc. Phys. Soc. London 85, 921 (1965).
  * Guyer and Krumhansl (1966) R. A. Guyer and J. A. Krumhansl, “Solution of the linearized phonon Boltzmann equation,” Phys. Rev. 148, 766–778 (1966).
  * Maris (1969) H. J. Maris, “Phonon viscosity,” Phys. Rev. 188, 1303–1307 (1969).
  * Cepellotti and Marzari (2016) A. Cepellotti and N. Marzari, “Thermal transport in crystals as a kinetic theory of relaxons,” Phys. Rev. X 6, 041013 (2016).
  * Cepellotti and Marzari (2017) A. Cepellotti and N. Marzari, “Boltzmann transport in nanostructures as a friction effect,” Nano Letters 17, 4675–4682 (2017).
  * Mahan and Claro (1988) G. D. Mahan and F. Claro, “Nonlocal theory of thermal conductivity,” Phys. Rev. B 38, 1963–1969 (1988).
  * Allen and Perebeinos (2018) P. B. Allen and V. Perebeinos, “Temperature in a Peierls-Boltzmann treatment of nonlocal phonon heat transport,” Phys. Rev. B 98, 085427 (2018).
  * Griffin (1965) A. Griffin, “On the detection of second sound in crystals by light scattering,” Physics Letters 17, 208–210 (1965).