Karlsruhe Institute of Technology, Karslruhe, Germany and
https://scale.iti.kit.edu/people/thomasblaesius<EMAIL_ADDRESS>Hasso
Plattner Institute, University of Potsdam, Potsdam, Germany and
https://hpi.de/friedrich/<EMAIL_ADDRESS>0000-0003-0076-6308 Sorbonne
Université, CNRS, LIP6, France<EMAIL_ADDRESS>0000-0002-1765-1219 This
work was supported by the Paris Île-de-France Region. Hasso Plattner
Institute, University of Potsdam, Potsdam, Germany and
https://hpi.de/friedrich/people/louise-molitor.html<EMAIL_ADDRESS>0000-0002-9166-9927 Thomas Bläsius, Tobias Friedrich, Martin S. Krejca and
Louise Molitor [100]Theory of computation Network formation [300]Theory of
computation Random network models

###### Acknowledgements.

We want to thank Thomas Sauerwald for the discussions on random walks.Nikhil
Bansal and James Worrell 2 48th International Colloquium on Automata,
Languages, and Programming (ICALP 2021) ICALP 2021 ICALP 2021 July 12–16, 2021
Glasgow, United Kingdom

# The Flip Schelling Process on Random Geometric and Erdős–Rényi Graphs

Thomas Bläsius  Tobias Friedrich  Martin S. Krejca  Louise Molitor

###### Abstract

Schelling’s classical segregation model gives a coherent explanation for the
wide-spread phenomenon of residential segregation. We consider an agent-based
saturated open-city variant, the Flip-Schelling-Process (FSP), in which
agents, placed on a graph, have one out of two types and, based on the
predominant type in their neighborhood, decide whether to changes their types;
similar to a new agent arriving as soon as another agent leaves the vertex.

We investigate the probability that an edge $\\{u,v\\}$ is monochrome, i.e.,
that both vertices $u$ and $v$ have the same type in the FSP, and we provide a
general framework for analyzing the influence of the underlying graph topology
on residential segregation. In particular, for two adjacent vertices, we show
that a highly decisive common neighborhood, i.e., a common neighborhood where
the absolute value of the difference between the number of vertices with
different types is high, supports segregation and moreover, that large common
neighborhoods are more decisive.

As an application, we study the expected behavior of the FSP on two common
random graph models with and without geometry: (1) For random geometric
graphs, we show that the existence of an edge $\\{u,v\\}$ makes a highly
decisive common neighborhood for $u$ and $v$ more likely. Based on this, we
prove the existence of a constant $c>0$ such that the expected fraction of
monochrome edges after the FSP is at least $1/2+c$. (2) For Erdős–Rényi graphs
we show that large common neighborhoods are unlikely and that the expected
fraction of monochrome edges after the FSP is at most
$1/2+\mathrm{o}\left({1}\right)$. Our results indicate that the cluster
structure of the underlying graph has a significant impact on the obtained
segregation strength.

###### keywords:

Agent-based Model, Schelling Segregation, Spin System

###### category:

##  1 Introduction

Residential segregation is a well-known sociological phenomenon [43] where
different groups of people tend to separate into largely homogeneous
neighborhoods. Studies, e.g. [16], show that individual preferences are the
driving force behind present residential patterns and bear much to the
explanatory weight. Local choices therefore lead to a global phenomenon [41].
A simple model for analyzing residential segregation was introduced by
Schelling [40, 41] in the 1970s. In his model, two types of agents, placed on
a grid, act according to the following threshold behavior, with $\tau\in(0,1)$
as the _intolerance threshold_ : agents are _content_ with their current
position on the grid if at least a $\tau$-fraction of neighbors is of their
own type. Otherwise they are _discontent_ and want to move, either via
swapping with another random discontent agent or via jumping to a vacant
position. Schelling demonstrated by experiments that, starting from a uniform
random distribution, the described process drifts towards strong segregation,
even if agents are tolerant and agree to live in mixed neighborhoods, i.e., if
$\tau\leq\frac{1}{2}$. Many empirical studies have been conducted to
investigate the influence of various parameters on the obtained segregation,
see [7, 8, 23, 36, 39].

On the theoretical side, Schelling’s model started recently gaining traction
within the algorithmic game theory and artificial intelligence communities [1,
10, 14, 15, 19, 20, 30], with focus on core game theoretic questions, where
agents strategically select locations.

Henry et al. [28] described a simple model of graph clustering motivated by
Schelling where they showed that segregated graphs always emerge. Variants of
the random Schelling segregation process were analyzed by a line of work that
showed that residential segregation occurs with high probability [4, 6, 9, 11,
29, 45].

We consider an agent-based model, called the _Flip-Schelling-Process (FSP)_ ,
which can be understood as the Schelling model in a _saturated open city_. In
contrast to _closed cities_ [6, 11, 29, 45], which require fixed populations,
open cities [3, 4, 9, 25] allow residents to move away. In saturated city
models, also known as voter models [18, 31, 32], vertices are not allowed to
be unoccupied, hence, a new agent enters as soon as one agent vacates a
vertex. In general, in voter models two types of agents are placed on a graph.
An agent examines their neighbors and, if a certain threshold is of another
type, they change their type. Also in this model segregation is visible. There
is a line of work, mainly in physics, that studies the voting dynamics on
several types of graphs [2, 12, 33, 38, 44].

In the FSP, agents have binary types. An agent is content if the fraction of
agents in their neighborhood with the same type is larger $\frac{1}{2}$.
Otherwise, if the fraction is smaller $\frac{1}{2}$, an agent is discontent
and is willing to flip their type to become content. If the fraction of same
type agents in their neighborhood is exactly $\frac{1}{2}$, an agent flips
their type with probability $\frac{1}{2}$. Starting from an initial
configuration where the type of each agent is chosen uniformly at random, we
investigate a simultaneous-move, one-shot process and bound the number of
monochrome edges, which is a popular measurement for segregation strength [17,
24].

Close to our model is the work by Omidvar and Franceschetti [34, 35], who
initiated an analysis of the size of monochrome regions in the so called
_Schelling Spin Systems_. Agents of two different types are placed on a grid
[34] and a geometric graph [35], respectively. Then independent and identical
Poisson clocks are assigned to all agents and, every time a clock rings, the
state of the corresponding agent is flipped if and only if the agent is
discontent w.r.t. a certain intolerance threshold $\tau$ regarding the
neighborhood size. The model corresponds to the Ising model with zero
temperature with Glauber dynamics [13, 42].

The commonly used underlying topology for modeling the residential areas are
(toroidal) grid graphs [10, 29, 34], regular graphs [10, 15, 19], paths [10,
30], cycles [3, 5, 6, 11, 45] and trees [1, 10, 20, 30]. Considering the
influence of the given topology that models the residential area regarding,
e.g., the existence of stable states and convergence behavior leads to
phenomena like non-existence of stable states [19, 20], non-convergence to
stable states [10, 15, 19], and high-mixing times [9, 26].

To avoid such undesirable characteristics, we suggest to investigate _random
geometric graphs_ [37], like in [35]. Random geometric graphs demonstrate, in
contrast to other random graphs without geometry, such as _Erdős–Rényi graphs_
[21, 27], community structures, i.e., densely connected clusters of vertices.
An effect observed by simulating the FSP is that the fraction of monochrome
edges is significantly higher in random geometric graphs compared to
Erdős–Rényi graphs, where the fraction stays almost stable around
$\frac{1}{2}$, cf. Fig 1.

Erdős-Rényi graphsrandom geometric graphs5 k10 k15 k20 k25 k5 k10 k15 k20 k25
k0.500.550.600.650.70number of vertices $n$fraction of monochrome
edgesaveragedegree24816 Figure 1: The fraction of monochrome edges after the
Flip-Schelling-Process (FSP) in Erdős–Rényi graphs and random geometric graphs
for different graph sizes (number of vertices $n$) and different expected
average degrees. Each data point shows the average over 1000 generated graphs
with one simulation of the FSP per graph. The error bars show the
interquartile range, i.e., $50\,\%$ of the measurements lie between the top
and bottom end of the error bar.

We set out for rigorously proving this phenomenon. In particular, we prove for
random geometric graphs that there exists a constant $c$ such that, given an
edge $\\{u,v\\}$, the probability that $\\{u,v\\}$ is monochrome is lower-
bounded by $\frac{1}{2}+c$, cf. Theorem 3.1. In contrast, we show for
Erdős–Rényi graphs that segregation is not likely to occur and the probability
that $\\{u,v\\}$ is monochrome is upper-bounded by
$\frac{1}{2}+\mathrm{o}\left({1}\right)$, cf. Theorem 4.1.

We introduce a general framework to deepen the understanding of the influence
of the underlying given topology on residential segregation. To this end, we
first show that a highly decisive common neighborhood supports segregation,
cf. Section 3.1. In particular, we provide a lower bound that an edge
$\\{u,v\\}$ is monochrome based on the probability that the difference between
the majority and the minority regarding both types in the common neighborhood,
i.e., the number of agents which are adjacent to $u$ and $v$, is larger
compared to their exclusive neighborhoods, i.e., the number of agents which
are adjacent to either $u$ or $v$. Next, we show that large sets are more
decisive, cf. Section 3.2. This implies that a large common neighborhood,
compared to the exclusive neighborhood, is likely to be more decisive, i.e.,
makes it more likely that the absolute value of the difference between the
number of different types in the common neighborhood is larger than in the
exclusive neighborhoods. These considerations hold for arbitrary graphs.
Hence, we reduce the question concerning a lower bound for the fraction of
monochrome edges in the FSP to the probability that, given $\\{u,v\\}$, the
common neighborhood of $u$ and $v$ is larger than the exclusive neighborhoods
of $u$ and $v$, respectively.

For random geometric graphs, we prove that a large geometric region, i.e., the
intersecting region that are formed by intersecting disks, leads to a large
vertex set, cf. Section 3.3, and that random geometric graphs have enough
edges that have sufficiently large intersecting regions, cf. Section 3.4, such
that segregation is likely to occur. In contrast, for Erdős–Rényi graphs, we
show that the common neighborhood between two vertices $u$ and $v$ is with
high probability empty and therefore segregation is not likely to occur, cf.
Section 4.

Overall, we shed light on the influence of the structure of the underlying
graph and discovered the significant impact of the community structure as an
important factor on the obtained segregation strength. We reveal for random
geometric graphs that already after one round a provable tendency is apparent
and a strong segregation occurs.

##  2 Model and Preliminaries

Let $G=(V,E)$ be an unweighted and undirected graph, with vertex set $V$ and
edge set $E$. For any vertex $v\in V$, we denote the _neighborhood_ of $v$ in
$G$ by $N_{v}=\\{u\in V\colon\\{u,v\\}\in E\\}$ and the degree of $v$ in $G$
by $\delta_{v}=|N_{v}|$. We consider _random geometric graphs_ and
_Erdős–Rényi graphs_ with a total of $n\in\mathbf{N}^{+}$ vertices and an
_expected average degree_ $\overline{\delta}>0$.

For a given $r\in\mathbf{R}^{+}$, a random geometric graph
$G\sim\mathcal{G}(n,r)$ is obtained by distributing $n$ vertices uniformly at
random in some geometric ground space and connecting vertices $u$ and $v$ if
and only if $\mathrm{dist}(u,v)\leq r$. We use a two-dimensional toroidal
Euclidean space with total area $1$ as ground space. More formally, each
vertex $v$ is assigned a point $(v_{1},v_{2})\in[0,1]^{2}$ and the distance
between $u=(u_{1},u_{2})$ and $v$ is
$\mathrm{dist}(u,v)=\sqrt{|u_{1}-v_{1}|_{\circ}^{2}+|u_{2}-v_{2}|_{\circ}^{2}}$
for $|u_{i}-v_{i}|_{\circ}=\min\\{|u_{i}-v_{i}|,1-|u_{i}-v_{i}|\\}$. We note
that using a torus instead of, e.g., a unit square, has the advantage that we
do not have to consider edge cases, for vertices that are close to the
boundary. In fact, a disk of radius $r$ around any point has the same area
$\uppi r^{2}$. As every vertex $v$ is connected to all vertices in the disk of
radius $r$ around it, its expected average degree is
$\overline{\delta}=(n-1)\uppi r^{2}$.

For a given $p\in[0,1]$, let $\mathcal{G}(n,p)$ denote an Erdős–Rényi graph.
Each edge $\\{u,v\\}$ is included with probability $p$, independently from
every other edge. It holds that $\overline{\delta}=(n-1)p$.

Consider two different vertices $u$ and $v$. Let $N_{u\cap
v}\coloneqq|N_{u}\cap N_{v}|$ be the number of vertices in the _common
neighborhood_ , let $N_{u\setminus v}\coloneqq|N_{u}\setminus N_{v}|$ be the
number of vertices in the _exclusive neighborhood_ of $u$, and let
$N_{v\setminus u}\coloneqq|N_{v}\setminus N_{u}|$ be the number of vertices in
the exclusive neighborhood of $v$. Furthermore, with $N_{\overline{u\cup
v}}\coloneqq|V\setminus(N_{u}\cup N_{v})|$, we denote the number of vertices
that are neither adjacent to $u$ nor to $v$.

Let $G$ be a graph where each vertex represents an agent of type $t^{+}$ or
$t^{-}$. The type of each agent is chosen independently and uniformly at
random. An edge $\\{u,v\\}$ _monochrome_ if and only if $u$ and $v$ are of the
same type. The _Flip-Schelling-Process_ (FSP) is defined as follows: an agent
$v$ whose type is aligned with the type of more than $\delta_{v}/2$ of their
neighbors keeps their type. If more than $\delta_{v}/2$ neighbors have a
different type, then agent $v$ changes their type. In case of a tie, i.e., if
exactly $\delta_{v}/2$ neighbors have a different type, then $v$ changes their
type with probability $\frac{1}{2}$. FSP is a simultaneous-move, one-shot
process, i.e., all agents make their decision at the same time and, moreover,
only once.

For $x,y\in\mathbf{N}$, we define $[x..y]=[x,y]\cap\mathbf{N}$ and for
$x\in\mathbf{N}$, we define $[x]=[1..x]$.

###  2.1 Useful Technical Lemmas

In this section, we state several lemmas that we will use in order to prove
our results in the next sections.

######  Lemma 2.1.

Let $X\sim\mathrm{Bin}(n,p)$ and $Y\sim\mathrm{Bin}(n,q)$ with $p\geq q$. Then
$\mathrm{Pr}\left[{X\geq Y}\right]\geq\frac{1}{2}$.

######  Proof 2.2.

Let $Y_{1},\dots,Y_{n}$ be the individual Bernoulli trials for $Y$, i.e.,
$Y=\sum_{i\in[n]}Y_{i}$. Define new random variables
$Y_{1}^{\prime},\dots,Y_{n}^{\prime}$ such that $Y_{i}=1$ implies
$Y_{i}^{\prime}=1$ and if $Y_{i}=0$, then $Y_{i}^{\prime}=1$ with probability
$(p-q)/(1-q)$ and $Y_{i}^{\prime}=0$ otherwise. Note that for each individual
$Y_{i}^{\prime}$, we have $Y_{i}^{\prime}=1$ with probability $p$, i.e.,
$Y^{\prime}=\sum_{i\in[n]}Y_{i}^{\prime}\sim\mathrm{Bin}(n,p)$. Moreover, as
$Y^{\prime}\geq Y$ for every outcome, we have $\mathrm{Pr}\left[{X\geq
Y}\right]\geq\mathrm{Pr}\left[{X\geq Y^{\prime}}\right]$. It remains to show
that $\mathrm{Pr}\left[{X\geq Y^{\prime}}\right]\geq\frac{1}{2}$.

As $X$ and $Y^{\prime}$ are equally distributed, we have
$\mathrm{Pr}\left[{X\geq Y^{\prime}}\right]=\mathrm{Pr}\left[{X\leq
Y^{\prime}}\right]$. Moreover, as one of the two inequalities holds in any
event, we get $\mathrm{Pr}\left[{X\geq
Y^{\prime}}\right]+\mathrm{Pr}\left[{X\leq Y^{\prime}}\right]\geq 1$, and thus
equivalently $2\mathrm{Pr}\left[{X\geq Y^{\prime}}\right]\geq 1$, which proves
the claim.

######  Lemma 2.3.

Let $n\in\mathbf{N}^{+}$, $p\in[0,1)$, and let $X\sim\mathrm{Bin}(n,p)$. Then,
for all $i\in[0..n]$, it holds that
$\mathrm{Pr}\left[{X=i}\right]\leq\mathrm{Pr}\left[{X=\lfloor
p(n+1)\rfloor}\right]$.

######  Proof 2.4.

We interpret the distribution of $X$ as a finite series and consider the sign
of the differences of two neighboring terms. A maximum of the distribution of
$X$ is located at the position at which the difference switches from positive
to negative. To this end, let $b\colon[0,n-1]\to[-1,1]$ be defined such that,
for all $i\in[0,n-1]\cap\mathbf{N}$, it holds that

$b(d)=\binom{n}{d+1}p^{d+1}(1-p)^{n-d-1}-\binom{n}{d}p^{d}(1-p)^{n-d}.$

We are interested in the sign of $b$. In more detail, for any
$d\in[0,n-2]\cap\mathbf{N}$, if
$\operatorname{\mathrm{sgn}}\big{(}b(d)\big{)}\geq 0$ and
$\operatorname{\mathrm{sgn}}\big{(}b(d+1)\big{)}\leq 0$, then $d+1$ is a local
maximum. If the sign is always negative, then there is a global maximum in the
distribution of $X$ at position $0$.

In order to determine the sign of $b$, for all $i\in[0..n-1]$, we rewrite

$\displaystyle b(i)$
$\displaystyle=\frac{n!}{i!(n-i-1)!}p^{i}(1-p)^{n-i-1}\frac{p}{i+1}-\frac{n!}{i!(n-i-1)!}p^{d}(1-p)^{n-i-1}\frac{1-p}{n-i}$
$\displaystyle=\frac{n!}{i!(n-i-1)!}p^{i}(1-p)^{n-i-1}\left(\frac{p}{i+1}-\frac{1-p}{n-i}\right).$

Since the term $n!p^{i}(1-p)^{n-i-1}$ is always non-negative, the sign of
$b(i)$ is determined by the sign of $p/(i+1)-(1-p)/(n-i)$. Solving for $i$, we
get that

$\frac{p}{i+1}-\frac{1-p}{n-i}\geq 0\Leftrightarrow i\leq p(n+1)-1.$

Note that $p(n+1)-1$ may not be integer. Further note that the distribution of
$X$ is unimodal, as the sign of $b$ changes at most once. Thus, each local
maximum is also a global maximum. As discussed above, the largest value
$d\in[0,n-2]\cap\mathbf{N}$ such that
$\operatorname{\mathrm{sgn}}\big{(}b(d)\big{)}\geq 0$ and
$\operatorname{\mathrm{sgn}}\big{(}b(d+1)\big{)}\leq 0$ then results in a
global maximum at position $d+1$. Since $d$ needs to be integer, the largest
value that satisfies this constraint is $\lfloor p(n+1)-1\rfloor$. If the sign
of $b$ is always negative ($p\leq 1/(n+1)$), then the distribution of $X$ has
a global maximum at $0$, which is also satisfied by $\lfloor
p(n+1)-1\rfloor+1$, which concludes the proof.

######  Theorem 2.5 (Stirling’s Formula [22, page 54]).

For all $n\in\mathbf{N}^{+}$, it holds that

$\sqrt{2\uppi}n^{n+1/2}\operatorname{\mathrm{e}}^{-n}\cdot\operatorname{\mathrm{e}}^{\left(12n+1\right)^{-1}}<n!<\sqrt{2\uppi}n^{n+1/2}\operatorname{\mathrm{e}}^{-n}\cdot\operatorname{\mathrm{e}}^{\left(12n\right)^{-1}}.$

######  Corollary 2.6.

For all $n\geq 2$ with $n\in\mathbf{N}$, it holds that

$\displaystyle n!$
$\displaystyle>\sqrt{2\uppi}n^{n+1/2}\operatorname{\mathrm{e}}^{-n}\textrm{
and}$ (1) $\displaystyle n!$
$\displaystyle<\operatorname{\mathrm{e}}n^{n+1/2}\operatorname{\mathrm{e}}^{-n}.$
(2)

######  Proof 2.7.

For both inequalities, we aim at using Theorem 2.5.

Equation 1: Note that $\operatorname{\mathrm{e}}^{\left(12n+1\right)^{-1}}>1$,
since $\frac{1}{12n+1}>0$. Hence,

$\sqrt{2\uppi}n^{n+1/2}\operatorname{\mathrm{e}}^{-n}<\sqrt{2\uppi}n^{n+1/2}\operatorname{\mathrm{e}}^{-n}\cdot\operatorname{\mathrm{e}}^{\left(12n+1\right)^{-1}}.$

Equation 2: We prove this case by showing that

$\displaystyle\sqrt{2\uppi}\operatorname{\mathrm{e}}^{\left(12n\right)^{-1}}<\operatorname{\mathrm{e}}.$
(3)

Note, that $\operatorname{\mathrm{e}}^{\left(12n\right)^{-1}}$ is strictly
decreasing. Hence, we only have to check whether Equation 3 holds for $n=2$.

$\sqrt{2\uppi}\operatorname{\mathrm{e}}^{\left(12n\right)^{-1}}\leq\sqrt{2\uppi}\operatorname{\mathrm{e}}^{\frac{1}{24}}<2.7<\operatorname{\mathrm{e}}.$

######  Lemma 2.8.

Let $A$, $B$, and $C$ be random variables such that
$\mathrm{Pr}\left[{A>C\land B>C}\right]>0$ and $\mathrm{Pr}\left[{A>C\land
B\leq C}\right]>0$. Then $\mathrm{Pr}\left[{A>B\land
A>C}\right]\geq\mathrm{Pr}\left[{A>B}\right]\cdot\mathrm{Pr}\left[{A>C}\right]$.

######  Proof 2.9.

Using the definition of conditional probability, we obtain

$\mathrm{Pr}\left[{A>B\land A>C}\right]=\mathrm{Pr}\left[{A>B\ \left|\
\vphantom{A>B}A>C\right.}\right]\cdot\mathrm{Pr}\left[{A>C}\right].$

Hence, we are left with bounding $\mathrm{Pr}\left[{A>B\ \left|\
\vphantom{A>B}A>C\right.}\right]\geq\mathrm{Pr}\left[{A>B}\right]$.
Partitioning the sample space into the two events $B>C$ and $B\leq C$ and
using the law of total probability, we obtain

$\displaystyle\mathrm{Pr}\left[{A>B\mid A>C}\right]=\,$
$\displaystyle\mathrm{Pr}\left[{B>C\ \left|\
\vphantom{B>C}A>C\right.}\right]\cdot\mathrm{Pr}\left[{A>B\mid A>C\wedge
B>C}\right]$ $\displaystyle+\,$ $\displaystyle\mathrm{Pr}\left[{B\leq C\
\left|\ \vphantom{B\leq C}A>C\right.}\right]\cdot\mathrm{Pr}\left[{A>B\mid
A>C\wedge B\leq C}\right].$

Note that the condition $A>C\wedge B\leq C$ already implies $A>B$ and thus the
last probability equals to $1$. Moreover, using the definition of conditional
probability, we obtain

$\displaystyle\mathrm{Pr}\left[{A>B\mid A>C}\right]=\ $
$\displaystyle\mathrm{Pr}\left[{B>C\ \left|\
\vphantom{B>C}A>C\right.}\right]\cdot\frac{\mathrm{Pr}\left[{A>B\wedge
A>C\wedge B>C}\right]missing}{\mathrm{Pr}\left[{A>C\wedge B>C}\right]missing}$
$\displaystyle+\mathrm{Pr}\left[{B\leq C\ \left|\ \vphantom{B\leq
C}A>C\right.}\right].$

Using that $\mathrm{Pr}\left[{B>C\ \left|\
\vphantom{B>C}A>C\right.}\right]\geq\mathrm{Pr}\left[{A>C\wedge B>C}\right]$,
that $A>B\wedge B>C$ already implies $A>C$, that $\mathrm{Pr}\left[{B\leq C\
\left|\ \vphantom{B\leq C}A>C\right.}\right]\geq\mathrm{Pr}\left[{A>B\wedge
B\leq C}\right]$, and finally the law of total probability, we obtain

$\displaystyle\mathrm{Pr}\left[{A>B\mid A>C}\right]$
$\displaystyle\geq\mathrm{Pr}\left[{A>B\wedge A>C\wedge
B>C}\right]+\mathrm{Pr}\left[{B\leq C\ \left|\ \vphantom{B\leq
C}A>C\right.}\right]$ $\displaystyle=\mathrm{Pr}\left[{A>B\wedge
B>C}\right]+\mathrm{Pr}\left[{B\leq C\ \left|\ \vphantom{B\leq
C}A>C\right.}\right]$ $\displaystyle\geq\mathrm{Pr}\left[{A>B\wedge
B>C}\right]+\mathrm{Pr}\left[{A>B\wedge B\leq C}\right]$
$\displaystyle=\mathrm{Pr}\left[{A>B}\right].$

##  3 Monochrome Edges in Geometric Random Graphs

In this section, we prove the following main theorem.

######  Theorem 3.1.

Let $G\sim\mathcal{G}(n,r)$ be a random geometric graph with expected average
degree $\overline{\delta}=\mathrm{o}\left({\sqrt{n}}\right)$. The expected
fraction of monochrome edges after the FSP is at least

$\frac{1}{2}+\frac{9}{800}\cdot\left(\frac{1}{2}-\frac{1}{\sqrt{2\pi\lfloor\overline{\delta}/2\rfloor}}\right)^{2}\cdot\left(1-\mathrm{e}^{-\overline{\delta}/2}\left(1+\frac{\overline{\delta}}{2}\right)\right)\cdot(1-\mathrm{o}\left({1}\right)).$

Note that the bound in Theorem 3.1 is bounded away from $\frac{1}{2}$ for all
$\overline{\delta}\geq 2$. Moreover, the two factors depending on
$\overline{\delta}$ go to $\frac{1}{2}$ and $1$, respectively, for a growing
$\overline{\delta}$.

Given an edge $\\{u,v\\}$, we prove the above lower bound on the probability
that $\\{u,v\\}$ is monochrome in the following four steps.  1. For a vertex
set, we introduce the concept of _decisiveness_ that measures how much the
majority is ahead of the minority in the FSP. With this, we give a lower bound
on the probability that $\\{u,v\\}$ is monochrome based on the probability
that the common neighborhood of $u$ and $v$ is more decisive than their
exclusive neighborhoods.  2. We show that large neighborhoods are likely to be
more decisive than small neighborhoods. To achieve this, we give bounds on the
likelihood that two similar random walks behave differently. This step reduces
the question of whether the common neighborhood is more decisive than the
exclusive neighborhoods to whether the former is larger than the latter.  3.
Turning to geometric random graphs, we show that the common neighborhood is
sufficiently likely to be larger than the exclusive neighborhoods if the
geometric region corresponding to the former is sufficiently large. We do this
by first showing that the actual distribution of the neighborhood sizes is
well approximated by independent random variables that follow binomial
distributions. Afterwards, we give the desired bounds for these random
variables.  4. We show that the existence of the edge $\\{u,v\\}$ in the
geometric random graph makes it sufficiently likely that the geometric region
hosting the common neighborhood of $u$ and $v$ is sufficiently large.

###  3.1 Monochrome Edges via Decisive Neighborhoods

Let $\\{u,v\\}$ be an edge of a given graph. To formally define the above
mentioned decisiveness, let $N_{u\cap v}^{+}$ and $N_{u\cap v}^{-}$ be the
number of vertices in the common neighborhood of $u$ and $v$ that are occupied
by agents of type $t^{+}$ and $t^{-}$, respectively. Then $D_{u\cap
v}\coloneqq|N_{u\cap v}^{+}-N_{u\cap v}^{-}|$ is the _decisiveness_ of the
common neighborhood of $u$ and $v$. Analogously, we define $D_{u\setminus v}$
and $D_{v\setminus u}$ for the exclusive neighborhoods of $u$ and $v$,
respectively.

The following theorem bounds the probability for $\\{u,v\\}$ to be monochrome
based on the probability that the common neighborhood is more decisive than
each of the exclusive neighborhoods.

######  Theorem 3.2.

In the FSP, let $\\{u,v\\}\in E$ be an edge and let $D$ be the event
$\\{D_{u\cap v}>D_{u\setminus v}\wedge D_{u\cap v}>D_{v\setminus u}\\}$. Then
$\\{u,v\\}$ is monochrome with probability at least
$1/2+\mathrm{Pr}\left[{D}\right]/2$.

######  Proof 3.3.

If $D$ occurs, then the types of $u$ and $v$ after the FSP coincide with the
predominant type before the FSP in the shared neighborhood. Thus, $\\{u,v\\}$
is monochrome.

Otherwise, assuming $\overline{D}$, w.l.o.g., let $D_{u\cap v}\leq
D_{u\setminus v}$ and assume the type of $v$ has already been determined. If
$D_{u\cap v}=D_{u\setminus v}$, then $u$ chooses a type uniformly at random,
which coincides with the type of $v$ with probability $\frac{1}{2}$.
Otherwise, $D_{u\cap v}<D_{u\setminus v}$ and thus $u$ takes the type that is
predominant in $u$’s exclusive neighborhood, which is $t^{+}$ and $t^{-}$ with
probability $\frac{1}{2}$, each. Moreover, this is independent from the type
of $v$ as $v$’s neighborhood is disjoint to $u$’s exclusive neighborhood.

Thus, for the event $M$ that $\\{u,v\\}$ is monochrome, we get
$\mathrm{Pr}\left[{M\mid D}\right]=1$ and
$\mathrm{Pr}\left[{M\mid\overline{D}}\right]=\frac{1}{2}$. Hence, we get
$\mathrm{Pr}\left[{M}\right]>\mathrm{Pr}\left[{D}\right]+\frac{1}{2}\left(1-\mathrm{Pr}\left[{D}\right]\right)=\frac{1}{2}+\mathrm{Pr}\left[{D}\right]/2$.

###  3.2 Large Neighborhoods are More Decisive

The goal of this section is to reduce the question of how decisive a
neighborhood is to the question of how large it is. To be more precise, assume
we have a set of vertices of size $a$ and give each vertex the type $t^{+}$
and $t^{-}$, each with probability $\frac{1}{2}$. Let $A_{i}$ for $i\in[a]$ be
the random variable that takes the value $+1$ and $-1$ if the $i$-th vertex in
this set has type $t^{+}$ and $t^{-}$, respectively. Then, for
$A=\sum_{i\in[a]}A_{i}$, the decisiveness of the vertex set is $|A|$. In the
following, we study the decisiveness $|A|$ depending on the size $a$ of the
set. Note that this can be viewed as a random walk on the integer line:
Starting at $0$, in each step, it moves one unit either to the left or to the
right with equal probabilities. We are interested in the distance from $0$
after $a$ steps.

Assume for the vertices $u$ and $v$ that we know that $b$ vertices lie in the
common neighborhood and $a$ vertices lie in the exclusive neighborhood of $u$.
Moreover, let $A$ and $B$ be the positions of the above random walk after $a$
and $b$ steps, respectively. Then the event $D_{u\cap v}>D_{u\setminus v}$ is
equivalent to $|B|>|A|$. Motivated by this, we study the probability of
$|B|>|A|$, assuming $b\geq a$. The core difficulty here comes from the fact
that we require $|B|$ to be strictly larger than $|A|$. Also note that $a+b$
corresponds to the degree of $u$ in the graph. Thus, we have to study the
random walks also for small numbers of $a$ and $b$. We note that all results
in this section are independent from the specific application to the FSP, and
thus might be of independent interest.

Before we give a lower bound on the probability that $|B|>|A|$, we need the
following technical lemma. It states that doing more steps in the random walk
only makes it more likely to deviate further from the starting position.

######  Lemma 3.4.

For $i\in[a]$ and $j\in[b]$ with $0\leq a\leq b$, let $A_{i}$ and $B_{j}$ be
independent random variables that are $-1$ and $1$ each with probability
$\frac{1}{2}$. Let $A=\sum_{i\in[a]}A_{i}$ and $B=\sum_{j\in[b]}B_{j}$. Then
$\mathrm{Pr}\left[{|A|<|B|}\right]\geq\mathrm{Pr}\left[{|A|>|B|}\right]$.

######  Proof 3.5.

Let $\Delta_{k}$ be the event that $|B|-|A|=k$. First note that

$\mathrm{Pr}\left[{|A|<|B|}\right]=\sum_{k\in[b]}\mathrm{Pr}\left[{\Delta_{k}}\right]\quad\text{
and
}\quad\mathrm{Pr}\left[{|A|>|B|}\right]=\sum_{k\in[a]}\mathrm{Pr}\left[{\Delta_{-k}}\right].$

To prove the statement of the lemma, it thus suffices to prove the following
claim.

######  Claim 1.

For $k\geq 0$,
$\mathrm{Pr}\left[{\Delta_{k}}\right]\geq\mathrm{Pr}\left[{\Delta_{-k}}\right]$.

We prove this claim via induction on $b-a$. For the base case $a=b$, $A$ and
$B$ are equally distributed and thus Claim 1 clearly holds.

For the induction step, let $B^{+}$ be the random variable that takes the
values $B+1$ and $B-1$ with probability $\frac{1}{2}$ each. Note that $B^{+}$
represents the same type of random walk as $A$ and $B$ but with $b+1$ steps.
Moreover $B^{+}$ is coupled with $B$ to make the same decisions in the first
$b$ steps. Let $\Delta^{+}_{k}$ be the event that $|B^{+}|-|A|=k$. It remains
to show that Claim 1 holds for these $\Delta^{+}_{k}$. For this, first note
that the claim trivially holds for $k=0$. For $k\geq 1$, we can use the
definition of $\Delta^{+}_{k}$ and the induction hypothesis to obtain

$\displaystyle\mathrm{Pr}\left[{\Delta^{+}_{k}}\right]$
$\displaystyle=\frac{\mathrm{Pr}\left[{\Delta_{k-1}}\right]missing}{2}+\frac{\mathrm{Pr}\left[{\Delta_{k+1}}\right]missing}{2}$
$\displaystyle\geq\frac{\mathrm{Pr}\left[{\Delta_{-k+1}}\right]missing}{2}+\frac{\mathrm{Pr}\left[{\Delta_{-k-1}}\right]missing}{2}=\mathrm{Pr}\left[{\Delta^{+}_{-k}}\right].$

Using Lemma 3.4, we can now prove the following general bound for the
probability that $|A|<|B|$, depending on certain probabilities for binomially
distributed variables.

######  Lemma 3.6.

For $i\in[a]$ and $j\in[b]$ with $0\leq a\leq b$, let $A_{i}$ and $B_{j}$ be
independent random variables that are $-1$ and $1$ each with probability
$\frac{1}{2}$. Let $A=\sum_{i\in[a]}A_{i}$ and $B=\sum_{j\in[b]}B_{j}$.
Moreover, let $X\sim\mathrm{Bin}(a,\frac{1}{2})$,
$Y\sim\mathrm{Bin}(b,\frac{1}{2})$, and $Z\sim\mathrm{Bin}(a+b,\frac{1}{2})$.
Then

$\mathrm{Pr}\left[{|A|<|B|}\right]\geq\frac{1}{2}-\mathrm{Pr}\left[{Z=\frac{a+b}{2}}\right]+\frac{\mathrm{Pr}\left[{X=\frac{a}{2}}\right]\cdot\mathrm{Pr}\left[{Y=\frac{b}{2}}\right]missing}{2}.$

######  Proof 3.7.

Using that
$\mathrm{Pr}\left[{|A|<|B|}\right]\geq\mathrm{Pr}\left[{|A|>|B|}\right]$ (see
Lemma 3.4), we obtain

$\displaystyle\mathrm{Pr}\left[{|A|<|B|}\right]+\mathrm{Pr}\left[{|A|>|B|}\right]+\mathrm{Pr}\left[{|A|=|B|}\right]$
$\displaystyle=1$ $\displaystyle\Rightarrow$ $\displaystyle
2\mathrm{Pr}\left[{|A|<|B|}\right]+\mathrm{Pr}\left[{|A|=|B|}\right]$
$\displaystyle\geq 1$ $\displaystyle\Leftrightarrow$
$\displaystyle\mathrm{Pr}\left[{|A|<|B|}\right]$
$\displaystyle\geq\frac{1}{2}-\frac{\mathrm{Pr}\left[{|A|=|B|}\right]missing}{2}.$
(4)

Thus, it remains to give an upper bound for
$\mathrm{Pr}\left[{|A|=|B|}\right]$.

Using the inclusion–exclusion principle and the fact that $B$ is symmetric
around $0$, i.e.,
$\mathrm{Pr}\left[{B=x}\right]=\mathrm{Pr}\left[{B=-x}\right]$ for any $x$, we
obtain

$\displaystyle\mathrm{Pr}\left[{|A|=|B|}\right]$
$\displaystyle=\mathrm{Pr}\left[{A=B\vee A=-B}\right]$
$\displaystyle=\mathrm{Pr}\left[{A=B}\right]+\mathrm{Pr}\left[{A=-B}\right]-\mathrm{Pr}\left[{A=B=0}\right]$
$\displaystyle=2\mathrm{Pr}\left[{A=-B}\right]-\mathrm{Pr}\left[{A=B=0}\right].$
(5)

We estimate $\mathrm{Pr}\left[{A=-B}\right]$ and
$\mathrm{Pr}\left[{A=B=0}\right]$ using bounds for binomially distributed
variables. To this end, define new random variables $X_{i}=\frac{A_{i}+1}{2}$
for $i\in[a]$ and let $X=\sum_{i\in[a]}X_{i}$. Note that the $X_{i}$ are
independent and take values $0$ and $1$, each with probability $\frac{1}{2}$.
Thus, $X\sim\mathrm{Bin}(a,\frac{1}{2})$. Moreover, $A=2X-a$. Analogously, we
define $Y$ with $Y\sim\mathrm{Bin}(b,\frac{1}{2})$ and $B=2Y-b$. Note that $X$
and $Y$ are independent and thus $Z=X+Y\sim\mathrm{Bin}(a+b,\frac{1}{2})$.
With this, we get

$\displaystyle\mathrm{Pr}\left[{A=-B}\right]$
$\displaystyle=\mathrm{Pr}\left[{2X-a=-2Y+b}\right]=\mathrm{Pr}\left[{Z=\frac{a+b}{2}}\right]\text{,
and}$ $\displaystyle\mathrm{Pr}\left[{A=B=0}\right]$
$\displaystyle=\mathrm{Pr}\left[{A=0}\right]\cdot\mathrm{Pr}\left[{B=0}\right]=\mathrm{Pr}\left[{X=\frac{a}{2}}\right]\cdot\mathrm{Pr}\left[{Y=\frac{b}{2}}\right].$

This, together with Equations 4 and 5 yield the claim.

The bound in Lemma 3.6 becomes worse for smaller values of $a$ and $b$.
Considering this worst case, we obtain the following specific bound.

######  Theorem 3.8.

For $i\in[a]$ and $j\in[b]$ with $0\leq a\leq b$, let $A_{i}$ and $B_{j}$ be
independent random variables that are $-1$ and $1$ each with probability
$\frac{1}{2}$. Let $A=\sum_{i\in[a]}A_{i}$ and $B=\sum_{j\in[b]}B_{j}$. If
$a=b=0$ or $a=b=1$, then $\mathrm{Pr}\left[{|A|<|B|}\right]=0$. Otherwise
$\mathrm{Pr}\left[{|A|<|B|}\right]\geq\frac{3}{16}$.

######  Proof 3.9.

Clearly, if $a=b=0$, then $A=B=0$ and thus
$\mathrm{Pr}\left[{|A|<|B|}\right]=0$. Similarly, if $a=b=1$, then $|A|=|B|=1$
and thus $\mathrm{Pr}\left[{|A|<|B|}\right]=0$. For the remainder, assume that
neither $a=b=0$ nor $a=b=1$, and let $X$, $Y$, and $Z$ be defined as in Lemma
3.6, i.e., $X\sim\mathrm{Bin}(a,\frac{1}{2})$,
$Y\sim\mathrm{Bin}(b,\frac{1}{2})$, and $Z\sim\mathrm{Bin}(a+b,\frac{1}{2})$.

If $a+b$ is odd, then $\mathrm{Pr}\left[{Z=\frac{a+b}{2}}\right]=0$. Thus, by
Lemma 3.6, we have $\mathrm{Pr}\left[{|A|<|B|}\right]\geq\frac{1}{2}$. If
$a+b$ is even and $a+b\geq 6$, then

$\mathrm{Pr}\left[{Z=\frac{a+b}{2}}\right]={a+b\choose\frac{a+b}{2}}\left(\frac{1}{2}\right)^{a+b}\leq{6\choose
3}\left(\frac{1}{2}\right)^{6}=\frac{5}{16}.$

Hence, by Lemma 3.6, we have
$\mathrm{Pr}\left[{|A|<|B|}\right]\geq\frac{1}{2}-\frac{5}{16}=\frac{3}{16}$.

If $a+b<6$ (and $a+b$ even), there are four cases: $a=0,b=2$; $a=0,b=4$;
$a=1,b=3$; $a=2,b=2$. If $a=0$ and $b=2$, then $A=0$ with probability $1$ and
$|B|=2$ with probability $\frac{1}{2}$. Thus,
$\mathrm{Pr}\left[{|A|<|B|}\right]=\frac{1}{2}$. If $a=0$ and $b=4$, then
$|A|<|B|$ unless $B=0$. As $\mathrm{Pr}\left[{B=0}\right]={4\choose
2}\cdot(\frac{1}{2})^{4}=\frac{3}{8}$, we get
$\mathrm{Pr}\left[{|A|<|B|}\right]=1-\frac{3}{8}=\frac{5}{8}$. If $a=1$ and
$b=3$, then $|A|=1$ with probability $1$ and $|B|=3$ with probability
$\frac{1}{4}$ (either $B_{1}=B_{2}=B_{3}=1$ or $B_{1}=B_{2}=B_{3}=-1$). Thus,
$\mathrm{Pr}\left[{|A|<|B|}\right]=\frac{1}{4}$. If $a=b=2$, then $|A|=0$ with
probability $\frac{1}{2}$ and $|B|=2$ with probability $\frac{1}{2}$. Thus
$\mathrm{Pr}\left[{|A|<|B|}\right]=\frac{1}{4}$.

We note that the bound of $\mathrm{Pr}\left[{|A|<|B|}\right]=\frac{3}{16}$ is
tight for $a=b=3$.

###  3.3 Large Common Regions Yield Large Common Neighborhoods

To be able to apply Theorem 3.8 to an edge $\\{u,v\\}$, we need to make sure
that the size of their common neighborhood (corresponding to $b$ in the
corollary) is at least the size of the exclusive neighborhoods (corresponding
to $a$ in the corollary). In the following, we give bounds for the probability
that this happens. Note that this is the first time we actually take the graph
into account. Thus, all above considerations hold for arbitrary graphs.

Recall that we consider random geometric graphs $\mathcal{G}(n,r)$ and $u$ and
$v$ are each connected to all vertices that lie within a disk of radius $r$
around them. As $u$ and $v$ are adjacent, their disks intersect, which
separates the ground space into four regions; cf. Fig 2(a). Let $R_{u\cap v}$
be the intersection of the two disks. Let $R_{u\setminus v}$ be the set of
points that lie in the disk of $u$ but not in the disk of $v$, and
analogously, let $R_{v\setminus u}$ be the disk of $v$ minus the disk of $u$.
Finally, let $R_{\overline{u\cup v}}$ the set of points outside both disks.
Then, each of the $n-2$ remaining vertices ends up in exactly one of these
regions with a probability equal to the corresponding measure. Let
$p=\mu(R_{u\cap v})$ and $q=\mu(R_{u\setminus v})=\mu(R_{v\setminus u})$ be
the probabilities for the common and exclusive regions, respectively. The
probability for $R_{\overline{u\cup v}}$ is then $1-p-2q$.

We are now interested in the sizes $N_{u\cap v}$, $N_{u\setminus v}$, and
$N_{v\setminus u}$ of the common and the exclusive neighborhoods,
respectively. As each of the $n-2$ remaining vertices ends up in $R_{u\cap v}$
with probability $p$, we have $R_{u\cap v}\sim\mathrm{Bin}(n-2,p)$. For
$N_{u\setminus v}$ and $N_{v\setminus u}$, we already know that $v$ is a
neighbor of $u$ and vice versa. Thus, $(N_{u\setminus
v}-1)\sim\mathrm{Bin}(n-2,q)$ and $(N_{v\setminus
u}-1)\sim\mathrm{Bin}(n-2,q)$. Moreover, the three random variables are not
independent, as each vertex lies in only exactly one of the four regions,
i.e., $N_{u\cap v}$, $(N_{u\setminus v}-1)$, $(N_{v\setminus u}-1)$, and the
number of vertices in neither neighborhood together follow a multinomial
distribution $\mathrm{Multi}(n-2,\bm{p})$ with
$\bm{p}=\left(p,q,q,1-p-2q\right)$.

The following lemma shows that these dependencies are small if $p$ and $q$ are
sufficiently small. This lets us assume that $N_{u\cap v}$, $(N_{u\setminus
v}-1)$, $(N_{v\setminus u}-1)$ are independent random variables following
binomial distributions if the expected average degree is not too large.

######  Lemma 3.10.

Let
$X=\left(X_{1},X_{2},X_{3},X_{4}\right)\sim\mathrm{Multi}\left(n,\bm{p}\right)$
with $\bm{p}=\left(p,q,q,1-p-2q\right)$. Then there exist independent random
variables $Y_{1}\sim\mathrm{Bin}\left(n,p\right)$,
$Y_{2}\sim\mathrm{Bin}\left(n,q\right)$ and
$Y_{3}\sim\mathrm{Bin}\left(n,q\right)$ such that
$\mathrm{Pr}\left[{\left(X_{1},X_{2},X_{3}\right)=\left(Y_{1},Y_{2},Y_{3}\right)}\right]\geq
1-3n\cdot\max(p,q)^{2}$.

######  Proof 3.11.

Let $Y_{1}\sim\mathrm{Bin}\left(n,p\right)$, and
$Y_{2},Y_{3}\sim\mathrm{Bin}\left(n,q\right)$ be independent random variables.
We define the event $B$ to hold, if each of the $n$ individual trials
increments at most one of the random variables $Y_{1}$, $Y_{2}$, or $Y_{3}$.
More formally, for $i\in[3]$ and $j\in[n]$, let $Y_{i,j}$ be the individual
Bernoulli trials of $Y_{i}$, i.e., $Y_{i}=\sum_{j\in[n]}Y_{i,j}$. For
$j\in[n]$, we define the event $B_{j}$ to be $Y_{1,j}+Y_{2,j}+Y_{3,j}\leq 1$,
and the event $B=\bigcap_{j\in[n]}B_{j}$.

Based on this, we now define the random variables $X_{1}$, $X_{2}$, $X_{3}$,
and $X_{4}$ as follows. If $B$ holds, we set $X_{i}=Y_{i}$ for $i\in[3]$ and
$X_{4}=n-X_{1}-X_{2}-X_{3}$. Otherwise, if $\overline{B}$, we draw
$X=(X_{1},X_{2},X_{3},X_{4})\sim\mathrm{Multi}\left(n,\bm{p}\right)$
independently from $Y_{1}$, $Y_{2}$, and $Y_{3}$ with $\bm{p}=(p,q,q,1-p-2q)$.
Note that $X$ clearly follows $\mathrm{Multi}\left(n,\bm{p}\right)$ if
$\overline{B}$. Moreover, conditioned on $B$, each individual trial increments
exactly one of the variables $X_{1}$, $X_{2}$, $X_{3}$, or $X_{4}$ with
probabilities $p$, $q$, $q$, and $1-p-2q$, respectively, i.e.,
$X\sim\mathrm{Multi}\left(n,\bm{p}\right)$.

Thus, we end up with $X\sim\mathrm{Multi}\left(n,\bm{p}\right)$. Additionally,
we have three independent random variables
$Y_{1}\sim\mathrm{Bin}\left(n,p\right)$, and
$Y_{2},Y_{3}\sim\mathrm{Bin}\left(n,q\right)$ with
$(X_{1},X_{2},X_{3})=(Y_{1},Y_{2},Y_{3})$ if $B$ holds. Thus, to prove the
lemma, it remains to show that $\mathrm{Pr}\left[{B}\right]\geq
1-3n\max(p,q)^{2}$. For $j\in[n]$, the probability that the $j$th trial goes
wrong is

$\displaystyle\mathrm{Pr}\left[{\overline{B}_{j}}\right]$
$\displaystyle=1-\left((1-p)(1-q)^{2}\right)-\left(p(1-q)^{2}\right)-2\left(q(1-p)(1-q)\right)$
$\displaystyle=2pq-2pq^{2}+q^{2}\leq 2pq+q^{2}\leq 3\cdot\max(p,q)^{2}.$

Using the union bound it follows that
$\mathrm{Pr}\left[{\overline{B}}\right]\leq\sum_{j\in[n]}\mathrm{Pr}\left[{\overline{B}_{j}}\right]\leq
3n\cdot\max(p,q)^{2}$.

As mentioned before, we are interested in the event $N_{u\cap v}\geq
N_{u\setminus v}$ (and likewise $N_{u\cap v}\geq N_{v\setminus u}$), in order
to apply Theorem 3.8. Moreover, due to Lemma 3.10, we know that $N_{u\cap v}$
and $(N_{u\setminus v}-1)$ almost behave like independent random variables
that follow $\mathrm{Bin}(n-2,p)$ and $\mathrm{Bin}(n-2,q)$, respectively. The
following lemma helps to bound the probability for $N_{u\cap v}\geq
N_{u\setminus v}$. Note that it gives a bound for the probability of achieving
strict inequality (instead of just $\geq$), which accounts for the fact that
$(N_{u\setminus v}-1)$ and not $N_{u\setminus v}$ itself follows a binomial
distribution.

######  Lemma 3.12.

Let $n\in\mathbf{N}$ with $n\geq 2$, and let $p,q\in(0,\frac{1}{2}]$ with
$p\geq q$. Further, let $X\sim\mathrm{Bin}(n,p)$ and $Y\sim\mathrm{Bin}(n,q)$
be independent, let $d=\lfloor p(n+1)\rfloor$, and let
$d=\mathrm{o}\left({\sqrt{n}}\right)$, then
$\mathrm{Pr}\left[{X>Y}\right]\geq\big{(}\frac{1}{2}-1/\sqrt{2\uppi
d}\big{)}(1-\mathrm{o}\left({1}\right))$.

######  Proof 3.13.

By Lemma 2.1, we get $\mathrm{Pr}\left[{X\geq Y}\right]\geq\frac{1}{2}$, and
we bound

$\mathrm{Pr}\left[{X>Y}\right]=\mathrm{Pr}\left[{X\geq
Y}\right]-\mathrm{Pr}\left[{X=Y}\right]\geq\frac{1}{2}-\mathrm{Pr}\left[{X=Y}\right],$

leaving us to bound $\mathrm{Pr}\left[{X=Y}\right]$ from above. By
independence of $X$ and $Y$, we get

$\displaystyle\mathrm{Pr}\left[{X=Y}\right]=\sum_{i\in[n]}\mathrm{Pr}\left[{X=i}\right]\cdot\mathrm{Pr}\left[{Y=i}\right].$
(6)

Note that, by Lemma 2.3, for all $i\in[0..n]$, it holds that
$\mathrm{Pr}\left[{X=i}\right]\leq\mathrm{Pr}\left[{X=d}\right]$. Assume that
we have a bound $B$ such that $\mathrm{Pr}\left[{X=d}\right]\leq B$.
Substituting this into Equation 6 yields

$\mathrm{Pr}\left[{X=Y}\right]\leq
B\sum_{i\in[n]}\mathrm{Pr}\left[{Y=i}\right]=B,$

resulting in $\mathrm{Pr}\left[{X>Y}\right]\geq\frac{1}{2}-B$. Thus, we now
derive such a bound for $B$ and apply the inequality that for all
$x\in\mathbf{R}$, it holds that $1+x\leq\mathrm{e}^{x}$, as well as Equation
1. We get

$\displaystyle\binom{n}{d}p^{d}(1-p)^{n-d}$
$\displaystyle\leq\frac{n^{d}}{d!}\left(\frac{d}{n}\right)^{d}\left(1-\frac{d}{n}\right)^{n}\left(1-\frac{d}{n}\right)^{-d}$
$\displaystyle\leq\frac{d^{d}}{d!}\mathrm{e}^{-d}\left(1-\frac{d}{n}\right)^{-d}$
$\displaystyle\leq\frac{d^{d}}{\sqrt{2\uppi}d^{d+1/2}\mathrm{e}^{-d}}\mathrm{e}^{-d}\left(1-\frac{d}{n}\right)^{-d}$
$\displaystyle=\frac{1}{\sqrt{2\uppi d}}\frac{1}{(1-d/n)^{d}}.$ (7)

By Bernoulli’s inequality, we bound $(1-d/n)^{d}\geq
1-d^{2}/n=1-\mathrm{o}\left({1}\right)$ by the assumption
$d=\mathrm{o}\left({\sqrt{n}}\right)$. Substituting this back into Equation 7
concludes the proof.

Finally, in order to apply Theorem 3.8, we have to make sure not to end up in
the special case where $a=b\leq 1$, i.e., we have to make sure that the common
neighborhood includes at least two vertices. The probability for this to
happen is given by the following lemma.

######  Lemma 3.14.

Let $X\sim\mathrm{Bin}(n,p)$ and let $c=pn\in\mathrm{o}\left({n}\right)$. Then
it holds that
$\mathrm{Pr}\left[{X>1}\right]\geq\left(1-\mathrm{e}^{-c}\left(1+c\right)\right)\left(1-\mathrm{o}\left({1}\right)\right)$.

######  Proof 3.15.

As $X>1$ holds if and only if $X\not=0$ and $X\not=1$, we get

$\displaystyle\mathrm{Pr}\left[{X>1}\right]$
$\displaystyle=1-\mathrm{Pr}\left[{X=0}\right]-\mathrm{Pr}\left[{X=1}\right]=1-(1-p)^{n}-n\cdot
p\cdot(1-p)^{n-1}.$ Using that for all $x\in\mathbf{R}$ it holds that
$1-x\leq\operatorname{\mathrm{e}}^{-x}$, we get
$\displaystyle\mathrm{Pr}\left[{X>1}\right]$ $\displaystyle\geq
1-\mathrm{e}^{-pn}-n\cdot p\cdot\mathrm{e}^{-p(n-1)}$
$\displaystyle=1-\mathrm{e}^{-c}-c\cdot\mathrm{e}^{c/n}\cdot\mathrm{e}^{-c}$
$\displaystyle=1-\mathrm{e}^{-c}\left(1+c\cdot\mathrm{e}^{c/n}\right).$

As $\mathrm{e}^{c/n}$ goes to $1$ for $n\to\infty$, we get the claimed bound.

###  3.4 Many Edges Have Large Common Regions

In Section 3.3, we derived a lower bound on the probability that $N_{u\cap
v}\geq N_{u\setminus v}$ provided that the probability for a vertex to end up
in the shared region $R_{u\cap v}$ is sufficiently large compared to
$R_{u\setminus v}$. In the following, we estimate the measures of these
regions depending on the distance between $u$ and $v$. Then, we give a lower
bound on the probability that $\mu(R_{u\cap v})\geq\mu(R_{u\setminus v})$.

######  Lemma 3.16.

Let $G\sim\mathcal{G}(n,r)$ be a random geometric graph with expected average
degree $\overline{\delta}$, let $\\{u,v\\}\in E$ be an edge, and let
$\tau\coloneqq\frac{\mathrm{dist}(u,v)}{r}$. Then,

$\displaystyle\mu(R_{u\cap v})$
$\displaystyle=\frac{\overline{\delta}}{(n-1)\uppi}\left(2\arccos\left(\frac{\tau}{2}\right)-\sin\left(2\arccos\left(\frac{\tau}{2}\right)\right)\right)\textrm{
and}$ (8) $\displaystyle\mu(R_{u\setminus v})=\mu(R_{v\setminus u})$
$\displaystyle=\frac{\overline{\delta}}{n-1}-\mu(R_{u\cap v}).$ (9)

(a) The geometric regions corresponding to the common and exclusive
neighborhoods, respectively, with yellow illustrating $R_{u\cap v}$ and blue
illustrating $R_{u\setminus v}$ and $R_{v\setminus u}$.

(b) Let $\alpha$ be the central angle determined by the intersection points
$i$ and $j$, and let $x$ be the corresponding circular sector (illustrated in
yellow).

(c) Let $y$ be a triangle in the intersection (illustrated in green)
determined by the radical axis $\ell$ and the central angle $\alpha$, cf. Fig
2(b).

(d) The height $h$ divides the area $\mu(y)$ (illustrated in green) of the
triangle $y$, cf. Fig 2(c), into two subareas of equal size, since adjacent
and opposite legs have the same length $r$.

Figure 2: The neighborhood of two adjacent vertices $u$ and $v$ in a random
geometric graph.

######  Proof 3.17.

We start with proving Equation 8. Let $i$ and $j$ be the two intersection
points of the disks of $u$ and $v$, let $\alpha$ be the central angle enclosed
by $i$ and $j$, and let $x$ be the corresponding circular sector, cf. Fig
2(b). Moreover, let the triangle $y$ be a subarea of $x$ determined by
$\alpha$ and the radical axis $\ell$, cf. Fig 2(c). Let $h$ denote the height
of the triangle $y$, cf. Fig 2(d). For our calculations, we restrict the
length of $\ell$ by the intersection points $i$ and $j$. Since we consider the
intersection between disks and thus $\ell$ divides the area $\mu(R_{u\cap v})$
into two subareas of equal sizes, it holds that $\mu(R_{u\cap
v})=2\left(\mu(x)-\mu(y)\right)$. Considering the two areas $\mu(x)$ and
$\mu(y)$, it holds that

$\displaystyle\mu(x)=\frac{\alpha}{2}r^{2}\quad\text{ and
}\quad\mu(y)=h\cdot\frac{\ell}{2}=\cos\left(\frac{\alpha}{2}\right)r\cdot\sin\left(\frac{\alpha}{2}\right)r=\frac{\sin(\alpha)}{2}r^{2}.$
(10)

For the central angle $\alpha$ we know $\cos\left(\alpha/2\right)=h/r=\tau/2$
and therefore $\alpha=2\arccos\left(\frac{\tau}{2}\right)$. Together with
Equation 10, we obtain

$\displaystyle\mu(R_{u\cap v})=2\left(\mu(x)-\mu(y)\right)=2\
\left(\frac{2\arccos\left(\frac{\tau}{2}\right)}{2}r^{2}-\frac{\sin\left(2\arccos\left(\frac{\tau}{2}\right)\right)}{2}r^{2}\right).$
(11)

The area of a general circle is equal to $\uppi r^{2}$, the area of one disk
in the random geometric graph equals $\frac{\overline{\delta}}{n-1}$, i.e.,
$r^{2}=\frac{\overline{\delta}}{(n-1)\uppi}$. Together with Equation 11, we
obtain Equation 8.

Equation 9: We get the claimed equality by noting that $\mu(R_{u\cap
v})+\mu(R_{u\setminus v})=\uppi r^{2}$.

######  Lemma 3.18.

Let $G\sim\mathcal{G}(n,r)$ be a random geometric graph, and let $\\{u,v\\}\in
E$ be an edge. Then $\mathrm{Pr}\left[{\mu(R_{u\cap v})\geq\mu(R_{u\setminus
v})}\right]\geq\left(\frac{4}{5}\right)^{2}$.

######  Proof 3.19.

Let $\tau=\frac{\mathrm{dist}(u,v)}{r}$. By Lemma 3.16 with $\mu(R_{u\cap
v})\geq\mu(R_{v\setminus u})$, we get

$\left(2\arccos\left(\frac{\tau}{2}\right)-\sin\left(2\arccos\left(\frac{\tau}{2}\right)\right)\right)\geq\frac{\uppi}{2},$

which is true for $\tau\geq\frac{4}{5}$. The area of a disk of radius
$\frac{4}{5}r$ is $\left(\uppi(\frac{4}{5}r)^{2}\right)/\left(\uppi
r^{2}\right)=\left(\frac{4}{5}\right)^{2}$ times the area of a disk of radius
$r$. Hence, the fraction of edges with distance at most $\frac{4}{5}r$ is at
least $\left(\frac{4}{5}\right)^{2}$, concluding the proof.

###  3.5 Proof of Theorem 3.1

By Theorem 3.2, the probability that a random edge $\\{u,v\\}$ is monochrome
is at least $\frac{1}{2}+\mathrm{Pr}\left[{D}\right]/2$, where $D$ is the
event that the common neighborhood of $u$ and $v$ is more decisive than each
exclusive neighborhood. It remains to bound $\mathrm{Pr}\left[{D}\right]$.

#### Existence of an edge yields a large shared region.

Let $R$ be the event that $\mu(R_{u\cap v})\geq\mu(R_{u\setminus v})$. Note
that this also implies $\mu(R_{u\cap v})\geq\mu(R_{v\setminus u})$ as
$\mu(R_{u\setminus v})=\mu(R_{v\setminus u})$. Due to the law of total
probability, we have

$\mathrm{Pr}\left[{D}\right]\geq\mathrm{Pr}\left[{R}\right]\cdot\mathrm{Pr}\left[{D\mid
R}\right].$

Due to Lemma 3.18, we have
$\mathrm{Pr}\left[{R}\right]\geq\left(\frac{4}{5}\right)^{2}$. By conditioning
on $R$ in the following, we can assume that $\mu(R_{u\cap
v})\geq\frac{\overline{\delta}}{2n}\geq\mu(R_{u\setminus v})=\mu(R_{v\setminus
u})$, where $\overline{\delta}$ is the expected average degree.

#### Neighborhood sizes are roughly binomially distributed.

The next step is to go from the size of the regions to the number of vertices
in these regions. Each of the remaining $n^{\prime}=n-2$ vertices is sampled
independently to lie in one of the regions $R_{u\cap v}$, $R_{u\setminus v}$,
$R_{v\setminus u}$, or $R_{\overline{u\cup v}}$. Denote the resulting numbers
of vertices with $X_{1}$, $X_{2}$, $X_{3}$, and $X_{4}$, respectively. Then
$(X_{1},X_{2},X_{3},X_{4})$ follows a multinomial distribution with parameter
$\bm{p}=\left(p,q,q,1-p-2q\right)$ for $p=\mu(R_{u\cap v})$ and
$q=\mu(R_{u\setminus v})=\mu(R_{v\setminus u})$. Note that $N_{u\cap
v}=X_{1}$, $N_{u\setminus v}=X_{2}+1$, and $N_{v\setminus u}=X_{3}+1$ holds
for the sizes of the common and exclusive neighborhoods, where the $+1$ comes
from the fact that $v$ is always a neighbor of $u$ and vice versa.

We apply Lemma 3.10 to obtain independent binomially distributed random
variables $Y_{1}$, $Y_{2}$, and $Y_{3}$ that are likely to coincide with
$X_{1}=N_{u\cap v}$, $X_{2}=N_{u\setminus v}-1$, and $X_{3}=N_{v\setminus
u}-1$, respectively. Let $B$ denote the event that $(N_{u\cap v},N_{u\setminus
v}-1,N_{v\setminus u}-1)=(Y_{1},Y_{2},Y_{3})$. Again, using the law of total
probabilities and due to the fact that $R$ and $B$ are independent, we get

$\mathrm{Pr}\left[{D\mid R}\right]\geq\mathrm{Pr}\left[{B\mid
R}\right]\cdot\mathrm{Pr}\left[{D\mid R\cap
B}\right]=\mathrm{Pr}\left[{B}\right]\cdot\mathrm{Pr}\left[{D\mid R\cap
B}\right].$

Note that $p,q\leq\frac{\overline{\delta}}{n}$ for the expected average degree
$\overline{\delta}$. Thus, Lemma 3.10 implies that
$\mathrm{Pr}\left[{B}\right]\geq\left(1-3\overline{\delta}^{2}/n\right)$.
Conditioning on $B$ makes it correct to assume that $N_{u\cap
v}\sim\mathrm{Bin}(n^{\prime},p)$, $(N_{u\setminus
v}-1)\sim\mathrm{Bin}(n^{\prime},q)$, $(N_{v\setminus
u}-1)\sim\mathrm{Bin}(n^{\prime},q)$ are independently distributed.
Additionally conditioning on $R$ gives us
$p\geq\frac{\overline{\delta}}{2n}\geq q$.

#### A large shared region yields a large shared neighborhood.

In the next step, we consider an event that makes sure that the number
$N_{u\cap v}$ of vertices in the shared neighborhood is sufficiently large.
Let $N_{1}$, $N_{2}$, and $N_{3}$ be the events that $N_{u\cap v}\geq
N_{u\setminus v}$, $N_{u\cap v}\geq N_{v\setminus u}$, and $N_{u\cap v}>1$,
respectively. Let $N$ be the intersection of $N_{1}$, $N_{2}$, and $N_{3}$. We
obtain

$\displaystyle\mathrm{Pr}\left[{D\mid R\cap B}\right]$
$\displaystyle\geq\mathrm{Pr}\left[{N\mid R\cap
B}\right]\cdot\mathrm{Pr}\left[{D\mid R\cap B\cap N}\right]$
$\displaystyle\geq\mathrm{Pr}\left[{N_{1}\mid R\cap
B}\right]\cdot\mathrm{Pr}\left[{N_{2}\mid R\cap
B}\right]\cdot\mathrm{Pr}\left[{N_{3}\mid R\cap
B}\right]\cdot\mathrm{Pr}\left[{D\mid R\cap B\cap N}\right],$

where the last step follows from Lemma 2.8 as the inequalities in $N_{1}$,
$N_{2}$, and $N_{3}$ all go in the same direction. Note that $N_{u\cap v}\geq
N_{u\setminus v}$ is equivalent to $N_{u\cap v}>N_{u\setminus v}-1$. Due to
the condition on $B$, $N_{u\cap v}$ and $N_{u\setminus v}-1$ are independent
random variables following $\mathrm{Bin}(n^{\prime},p)$ and
$\mathrm{Bin}(n^{\prime},q)$, respectively, with $p\geq q$ due to the
condition on $R$. Thus, we can apply Lemma 3.12, to obtain

$\mathrm{Pr}\left[{N_{1}\mid R\cap B}\right]=\mathrm{Pr}\left[{N_{2}\mid R\cap
B}\right]\geq\frac{1}{2}-\frac{1}{\sqrt{2\pi\lfloor\overline{\delta}/2\rfloor}(1-\mathrm{o}\left({1}\right))},$

and Lemma 3.14 gives the bound

$\mathrm{Pr}\left[{N_{3}\mid R\cap B}\right]\geq
1-\mathrm{e}^{-\overline{\delta}/2}\left(1+\frac{\overline{\delta}}{2}\cdot(1+\mathrm{o}\left({1}\right))\right).$

Note that both of these probabilities are bounded away from $0$ for
$\overline{\delta}\geq 2$. Conditioning on $N$ lets us assume that the shared
neighborhood of $u$ and $v$ contains at least two vertices and that it is at
least as big as each of the exclusive neighborhoods.

#### A large shared neighborhood yields high decisiveness.

The last step is to actually bound the remaining probability
$\mathrm{Pr}\left[{D\mid R\cap B\cap N}\right]$. Note that, once we know the
number of vertices in the shared and exclusive neighborhoods, the decisiveness
no longer depends on $R$ or $B$, i.e., we can bound $\mathrm{Pr}\left[{D\mid
N}\right]$ instead. For this, let $D_{1}$ and $D_{2}$ be the events that
$D_{u\cap v}>D_{u\setminus v}$ and $D_{u\cap v}>D_{v\setminus u}$,
respectively. Note that $D$ is their intersection. Moreover, due to Lemma 2.8,
we have $\mathrm{Pr}\left[{D\mid N}\right]\geq\mathrm{Pr}\left[{D_{1}\mid
N}\right]\cdot\mathrm{Pr}\left[{D_{2}\mid N}\right]$. To bound
$\mathrm{Pr}\left[{D_{1}\mid N}\right]=\mathrm{Pr}\left[{D_{2}\mid N}\right]$,
we use Theorem 3.8. Note that the $b$ and $a$ in Theorem 3.8 correspond to
$N_{u\cap v}$ and $N_{u\setminus v}+1$ (the $+1$ coming from the fact that
$N_{u\setminus v}$ does not count the vertex $v$). Moreover conditioning on
$N$ implies that $a\leq b$ and $b>1$. Thus, Theorem 3.8 implies
$\mathrm{Pr}\left[{D_{1}\mid N}\right]\geq\frac{3}{16}$.

#### Conclusion.

The above arguments gives us that the fraction of monochrome edges is

$\frac{1}{2}+\frac{\mathrm{Pr}\left[{D}\right]missing}{2}\geq\frac{1}{2}+\frac{1}{2}\cdot\underbrace{\mathrm{Pr}\left[{R}\right]missing}_{\geq\left(\frac{4}{5}\right)^{2}}\cdot\underbrace{\mathrm{Pr}\left[{B}\right]missing}_{1-\mathrm{o}\left({1}\right)}\cdot\big{(}\underbrace{\mathrm{Pr}\left[{N_{1}\mid
R\cap
B}\right]missing}_{\geq\frac{1}{2}-\frac{1}{\sqrt{2\pi\lfloor\overline{\delta}/2\rfloor}}}\big{)}^{2}\cdot\underbrace{\mathrm{Pr}\left[{N_{3}\mid
R\cap B}\right]missing}_{\geq
1-\operatorname{\mathrm{e}}^{-\overline{\delta}/2}\left(1+\frac{\overline{\delta}}{2}\right)}\cdot\big{(}\underbrace{\mathrm{Pr}\left[{D_{1}\mid
N}\right]missing}_{\geq\frac{3}{16}}\big{)}^{2},$

where we omitted the $\mathrm{o}\left({1}\right)$ terms for
$\mathrm{Pr}\left[{N_{1}\mid R\cap B}\right]$ and $\mathrm{Pr}\left[{N_{3}\mid
R\cap B}\right]$, as they are already covered by the
$1+\mathrm{o}\left({1}\right)$ coming from $\mathrm{Pr}\left[{B}\right]$. This
yields the bound stated in Theorem 3.1:

$\frac{1}{2}+\frac{9}{800}\cdot\left(\frac{1}{2}-\frac{1}{\sqrt{2\pi\lfloor\overline{\delta}/2\rfloor}}\right)^{2}\cdot\left(1-\mathrm{e}^{-\overline{\delta}/2}\left(1+\frac{\overline{\delta}}{2}\right)\right)\cdot(1-\mathrm{o}\left({1}\right)).$

##  4 Erdős–Rényi Graphs

In the following, we are interested in the probability that an edge
$\\{u,v\\}$ is monochrome after the FSP on Erdős–Rényi graphs. In contrast to
geometric random graphs, we prove an upper bound. To this end, we show that it
is likely that the common neighborhood is empty and therefore $u$ and $v$
choose their types to be the predominant type in their exclusive neighborhood,
which is $t^{+}$ and $t^{-}$ with probability $\frac{1}{2}$, each.

######  Theorem 4.1.

Let $G\sim\mathcal{G}(n,p)$ be an Erdős–Rényi graph with expected average
degree $\overline{\delta}=\mathrm{o}\left({\sqrt{n}}\right)$. The expected
fraction of monochrome edges after the FSP is at most
$\frac{1}{2}+\mathrm{o}\left({1}\right)$.

######  Proof 4.2.

Given an edge $\\{u,v\\}$, let $M$ be the event that $\\{u,v\\}$ is
monochrome. We first split $M$ into disjoint sets with respect to the size of
the common neighborhood and apply the law of total probability and get

$\displaystyle\mathrm{Pr}\left[{M}\right]=\ $
$\displaystyle\mathrm{Pr}\left[{M\ \left|\ \vphantom{M}N_{u\cap
v}=0\right.}\right]\cdot\mathrm{Pr}\left[{N_{u\cap
v}=0}\right]+\mathrm{Pr}\left[{M\ \left|\ \vphantom{M}N_{u\cap
v}>0\right.}\right]\cdot\mathrm{Pr}\left[{N_{u\cap v}>0}\right]$
$\displaystyle\leq\ $ $\displaystyle\mathrm{Pr}\left[{M\ \left|\
\vphantom{M}N_{u\cap v}=0\right.}\right]\cdot
1+1\cdot\mathrm{Pr}\left[{N_{u\cap v}>0}\right].$

We bound each of the summands separately. For estimating $\mathrm{Pr}\left[{M\
\left|\ \vphantom{M}N_{u\cap v}=0\right.}\right]$, we note that the types of
$u$ and $v$ are determined by the predominant type in disjoint vertex sets. By
definition of the FSP this implies that the probability of an monochrome edge
is equal to $\frac{1}{2}$.

We are left with bounding $\mathrm{Pr}\left[{N_{u\cap v}>0}\right]$. Note that
$N_{u\cap v}\sim\mathrm{Bin}\left(n,p^{2}\right)$. Thus, by Bernoulli’s
inequality we get $\mathrm{Pr}\left[{N_{u\cap
v}>0}\right]=1-\mathrm{Pr}\left[{N_{u\cap
v}=0}\right]=1-\left(1-p^{2}\right)^{n}\leq np^{2}$. Noting that
$np^{2}=\mathrm{o}\left({1}\right)$ holds due to our assumption on
$\overline{\delta}$, concludes the proof.

## References

  * [1] Aishwarya Agarwal, Edith Elkind, Jiarui Gan, and Alexandros A. Voudouris.  Swap stability in Schelling games on graphs.  In AAAI’20, pages 1758–1765, 2020.
  * [2] Paul Balister, Béla Bollobás, J. Robert Johnson, and Mark Walters.  Random majority percolation.  Random Structures & Algorithms, 36(3):315–340, 2010.
  * [3] George Barmpalias, Richard Elwes, and Andrew Lewis-Pye.  Tipping points in 1-dimensional Schelling models with switching agents.  Journal of Statistical Physics, 158(4):1572–9613, 2015.
  * [4] George Barmpalias, Richard Elwes, and Andrew Lewis-Pye.  Unperturbed Schelling segregation in two or three dimensions.  Journal of Statistical Physics, 164(6):1460–1487, 2016.
  * [5] George Barmpalias, Richard Elwes, and Andrew Lewis-Pye.  Minority population in the one-dimensional Schelling model of segregation.  Journal of Statistical Physics, 173(5):1572–9613, 2018.
  * [6] George Barmpalias, Richard Elwes, and Andy Lewis-Pye.  Digital morphogenesis via Schelling segregation.  In FOCS’14, pages 156–165, 2014.
  * [7] Stephen Benard and Robb Willer.  A wealth and status-based model of residential segregation.  Journal of Mathematical Sociology, 31(2):149–174, 2007.
  * [8] Itzhak Benenson, Erez Hatna, and Ehud Or.  From Schelling to spatially explicit modeling of urban ethnic and economic residential dynamics.  Sociological Methods and Research, 37(4):463–497, 2009.
  * [9] Prateek Bhakta, Sarah Miracle, and Dana Randall.  Clustering and mixing times for segregation models on $\mathbb{Z}^{2}$.  In SODA’14, pages 327–340, 2014.
  * [10] Davide Bilò, Vittorio Bilò, Pascal Lenzner, and Louise Molitor.  Topological influence and locality in swap Schelling games.  In MFCS’20, pages 15:1–15:15, 2020.
  * [11] Christina Brandt, Nicole Immorlica, Gautam Kamath, and Robert Kleinberg.  An analysis of one-dimensional Schelling segregation.  In STOC’12, pages 789–804, 2012.
  * [12] Paulo R. A. Campos, Viviane M. de Oliveira, and F. G. Brady Moreira.  Small-world effects in the majority-vote model.  Physical Review E, 67:026104, Feb 2003.
  * [13] Claudio Castellano, Santo Fortunato, and Vittorio Loreto.  Statistical physics of social dynamics.  Review of Modern Physics, 81:591–646, 2009.
  * [14] Hau Chan, Mohammad T. Irfan, and Cuong Viet Than.  Schelling models with localized social influence: A game-theoretic framework.  In AAMAS’20, pages 240–248, 2020.
  * [15] Ankit Chauhan, Pascal Lenzner, and Louise Molitor.  Schelling segregation with strategic agents.  In SAGT’18, pages 137–149. Springer, 2018.
  * [16] William A. V. Clark.  Residential segregation in american cities: A review and interpretation.  Population Research and Policy Review, 5(2):95–127, 1986.
  * [17] Vasco Cortez and Sergio Rica.  Dynamics of the Schelling social segregation model in networks.  Procedia Computer Science, 61:60 – 65, 2015.
  * [18] Richard Durrett and Jeffrey E. Steif.  Fixation results for threshold voter systems.  Annals of Probability, 21(1):232–247, 1993.
  * [19] Hagen Echzell, Tobias Friedrich, Pascal Lenzner, Louise Molitor, Marcus Pappik, Friedrich Schöne, Fabian Sommer, and David Stangl.  Convergence and hardness of strategic Schelling segregation.  In WINE’19, pages 156–170, 2019.
  * [20] Edith Elkind, Jiarui Gan, Atushi Igarashi, Warut Suksompong, and Alexandros A. Voudouris.  Schelling games on graphs.  In IJCAI’19, pages 266–272, 2019.
  * [21] Paul Erdős and Alfréd Rényi.  On random graphs I.  Publicationes Mathematicae Debrecen, 6:290–297, 1959.
  * [22] William Feller.  An Introduction to Probability Theory and Its Applications, volume 1.  John Wiley & Sons, 3rd edition, 1968.
  * [23] Mark A Fossett.  Simseg–a computer program to simulate the dynamics of residential segregation by social and ethnic status.  Race and Ethnic Studies Institute Technical Report and Program, Texas A&M University, 1998.
  * [24] Linton C. Freeman.  Segregation in social networks.  Sociological Methods & Research, 6(4):411–429, 1978.
  * [25] Laetitia Gauvin, Jean-Pierre Nadal, and Jean Vannimenus.  Schelling segregation in an open city: A kinetically constrained blume-emery-griffiths spin-1 system.  Physical Review E, 81:066120, 2010.
  * [26] Stefan Gerhold, Lev Glebsky, Carsten Schneider, Howard Weiss, and Burkhard Zimmermann.  Computing the complexity for Schelling segregation models.  Communications in Nonlinear Science and Numerical Simulation, (13):2236–2245, 2008.
  * [27] Edgar N. Gilbert.  Random graphs.  Annals of Mathematical Statistics, 30(4):1141–1144, 1959.
  * [28] Adam Douglas Henry, Paweł Prałat, and Cun-Quan Zhang.  Emergence of segregation in evolving social networks.  Proceedings of the National Academy of Sciences, 108(21):8605–8610, 2011.
  * [29] Nicole Immorlica, Robert Kleinberg, Brendan Lucier, and Morteza Zadomighaddam.  Exponential segregation in a two-dimensional Schelling model with tolerant individuals.  In SODA’17, pages 984–993, 2017.
  * [30] Panagiotis Kanellopoulos, Maria Kyropoulou, and Alexandros A. Voudouris.  Modified Schelling games.  In SAGT’20, pages 241–256, 2020.
  * [31] Thomas M. Liggett.  Coexistence in threshold voter models.  The Annals of Probability, 22(2):764–802, 1994.
  * [32] Thomas M. Liggett.  Voter Models, pages 139–208.  Springer, 1999.
  * [33] Francisco W.S. Lima, Alexandre O. Sousa, and Muneer A. Sumuor.  Majority-vote on directed Erdős–Rényi random graphs.  Physica A: Statistical Mechanics and its Applications, 387(14):3503–3510, 2008.
  * [34] Hamed Omidvar and Massimo Franceschetti.  Self-organized segregation on the grid.  Journal of Statistical Physics, 170(4):1572–9613, 2018.
  * [35] Hamed Omidvar and Massimo Franceschetti.  Shape of diffusion and size of monochromatic region of a two-dimensional spin system.  In STOC’18, page 100–113, 2018.
  * [36] Romans Pancs and Nicolaas J. Vriend.  Schelling’s spatial proximity model of segregation revisited.  Journal of Public Economics, 91(1):1–24, 2007.
  * [37] Mathew Penrose.  Random Geometric Graphs.  Oxford University Press, 1st edition, 2003.
  * [38] Luiz F. C. Pereira and F. G. Brady Moreira.  Majority-vote model on random graphs.  Physical Review E, 71:016123, 2005.
  * [39] Tim Rogers and Alan J McKane.  A unified framework for Schelling’s model of segregation.  Journal of Statistical Mechanics: Theory and Experiment, 2011(07):P07006, 2011.
  * [40] Thomas C. Schelling.  Models of segregation.  American Economic Review, 59(2):488–93, 1969.
  * [41] Thomas C Schelling.  Micromotives and Macrobehavior.  WW Norton & Company, 2006.
  * [42] Sorin Solomon and Dietrich Stauffer.  Ising, Schelling and self-organising segregation.  The European Physical Journal B, 57(4):473–479, 2007.
  * [43] Miehelle J. White.  Segregation and diversity measures in population distribution.  Population index, 52 2:198–221, 1986.
  * [44] Zhi-Xi Wu and Petter Holme.  Majority-vote model on hyperbolic lattices.  Physical Review E, 81:011133, 2010.
  * [45] H. Peyton Young.  Individual strategy and social structure: An evolutionary theory of institutions.  Princeton University Press Princeton, N.J, 1998.


# On the Computational Complexity of Determining Value

Tiasa Mondol, MMath
<EMAIL_ADDRESS>
###### Abstract

> We look at an algorithmic information theory based definition of value of a
> creative artifact and discuss the computational difficulty associated with
> the creation or determination of value. We look at the computational
> resources required to create a valuable product and discuss how likely an
> observer is to verify a claim that an object required significant effort on
> the creator’s part.

##  1 Introduction

We start by building an algorithmic information theory based definition of
value of a creative artifact. An artifact can be described concisely by an
algorithm that generates a binary description of it on a computer (such
formulation may seem reductive but it makes analysis of its complexity, the
creative process and effort that went behind it much easier). We fix this
particular computer $C$ as the only way to generate a description of an
artifact which upon receiving some program $p$ (a set of instructions) halts
after outputting only our desired object $x$ and nothing else. Algorithmic
information theory says, in this settings, the length of shortest program is
the object’s Kolmogorov complexity [1] which is its absolute information
content (a concise set of instructions for composing Bach’s Cello Suites may
be more economical and certainly more informative than the verbatim
compositions themselves).

$K_{C}(x)=\min_{p}\\{|p|:C(p)=x\\}$

If the input programs are binary and we generate them via coin tosses, then
the probability that $x$ will be the output on any given input is
$Q_{C}(x)=\sum_{p:C(p)=x}2^{-|p|}$. This is remarkable as it is also the
algorithmic probability of $x$’s existence on $C$. For the sum to be a proper
probability distribution such that $Q_{C}(x)\leq 1$, it is however required
that $C$ knows when to stop reading the input (due to Kraft inequality [1])
and such property is known as prefix-free where no program is a prefix of
another valid program. Then the shortest program $p$ contributes the most to
$x$’s probability and it is $p$’s computational effort to create $x$ that will
determine $x$’s value.

##  2 Value as Computational Effort

Note that this “effort” can measured be in required time, space or energy; all
of which are resources that we may have restricted access to and thus will
naturally value an object to create which an extraordinary amount of these
resources was needed. However, we continue our discussion focusing only on
time as the other resources increase proportionally with it after a certain
threshold (a computer which embarks on a long computation generates heat when
it manipulates or erases information [2]; to cool it down we need to spend
energy still. The discussion on assigning value to space is rather tricky;
because space can be reused and even the polynomial space complexity class
$PSPACE$ contains some of the most difficult problems, it is more interesting
to discuss problems with bounded time). We define here a time-bounded version
$K^{t}_{C}(x)$ which is the length of shortest program $p$ that outputs $x$
within a computable time bound $t(|x|)$.

$\displaystyle K^{t}_{C}(x)=\min_{p}\\{$ $\displaystyle|p|:C(p)\texttt{ halts
with }x$ $\displaystyle\texttt{ in time }t(|x|)\\}$

Intuitively, as $t(|x|)$ becomes larger the length of the program that needs
this time becomes shorter; as it takes more time for them to create a large
artifact than it takes an already larger program (we do not take into account
the inner mechanisms of the programs which can be regarded as a shortcoming of
this formulation). But is it always economical to sacrifice in time for a
small gain in space? In Conway’s game of life, a simple initial configuration
can give rise to non-trivial organized complexity after running for
exponential time which may lead us to think that this final configuration is
valuable: it is attainable from its initial simplicity but only with much
endeavours. However, if it can be reached from another slightly more complex
initial settings within polynomial time, then it no longer seems as valuable
as it did before. Therefore, a more error-free way of defining value is: an
object is valuable only if all of its short programs are slow-running; in
other words almost all of its algorithmic probability comes from slow and
short programs. This is captured succinctly by the Logical depth
$depth_{c}(x)$ [3] which we adopt as a formal measure of $x$’s value.

$depth_{s}(x)=\min_{p}\\{time(p):C(p)=x,\;|p|\leq K_{C}(x)+s\\}$

Here $s$ denotes the significance of the witness program $p$ in terms of its
contribution to $x$’s existence: the less $s$ is, the more probable it is for
$p$ to be $x$’s actual source on $C$; thus $p$’s computational effort is also
the most probable way in which $x$ was created.

###  2.1 Compressibility$\not=$Value

Note that such definition of value also protects us from certain pitfalls;
like claims that highly compressible and regular objects are valuable; rather
we seem to attach value to objects that are meaningful and often such meaning
is acquired over time. In Colton’s Art exhibit example [4] a similar scenario
is described where an art enthusiast deems a painting of random dots more
valuable than another similar painting as it had a meaning attached to it
provided by the painter: the random dots depicted his personal relationships
and how he felt about them.

In an interesting study [5], the authors showed that complex but non-random
images that we would normally assign value to takes more time to generate from
their lossless PNG (Portable network graphics) compression (Figure 1).

(a)

(b)

Figure 1: The mono-coloured image on the left is more compressible than the
complex one on the right; yet the latter takes more decompression time from
its short program. Image Courtesy: [5]

On the other end of the spectrum, highly random objects which are not
compressible and are often of little value to us, can be generated quickly
from their similar-length programs (Figure 2).

(a)

(b)

Figure 2: The image on the left is purely random noise. Hence a suitable
program that generates it will contain a lot of verbatim description taking
little time to reproduce the image. The image on the right by the virtue of
being highly compressible takes more decompression time from its short
program. Image Courtesy: [5]

It is important to note here that this object-dependent notion of value does
not consider the cultural context in which it was was conceived nor the
observer’s perspective which may differ from person to person. Instead, what
it correctly predicts is that valuable objects are extremely rare: there are
far more random objects in the universe than there are highly regular
compressible ones; even less are among those which are programs and go through
a long evolution (computation) to create something meaningful. This catapults
us to the discussion of the computational complexity associated with value.

##  3 Complexity of Creating Value

Consider creating an artifact $x$ with value $T$ (some large number) using the
following diagonalization procedure [3]: we enumerate all programs $p:|p|\leq
T$, run each of them for time $T$, check whether the cumulative probability
$\sum_{p:C(p)=x}2^{-|p|}$ of programs that halt with output $x$ is significant
or larger than $2^{-|x|}$ (which means $x$ is compressible and has a more
probable source than a verbatim description). If we do find an object $x$ that
is less probable to be created by these $T$-fast programs, then we can say
with high probability that $x$ has value at least $T$ (as programs taking more
time than $T$ may be able to produce $x$; the algorithm we just described is
certainly one among them) This is a very slow process taking more than $2^{T}$
to create an object with value $T$. However, this process can not be sped up
due to the slow-growth law which states that a fast deterministic process can
not turn a shallow or valueless object into a deep and valuable one. If it did
then this process along with the shallow object (can be an empty string) could
be encoded as a program that generates the valuable object quickly
contradicting the fact that the object is valuable. This phenomenon is best
illustrated by a great work of autobiography: the existence of such a
literature would be impossible without the meaningfully lived life of the
author.

Given an artifact $x$ it is natural to think that starting from some initial
long program (“print $x$”) we can incrementally update it by exploring shorter
programs by running them until termination and check whether they output $x$.
Unfortunately, since halting of a program is undecidable, even if we encounter
a short program that eventually outputs $x$, without a preconceived idea of
the object’s value we would not know how long we should keep the program
running. A halting sequence $H$ however, whose $i$th bit is 1 iff the $i$th
program halts (we enumerate all possible programs with lexicographically
increasing length) has the ability to speed up this process: with the
knowledge that a particular program halts with certainty the only thing that
remains to check is whether the program outputs $x$ [3]. By the slow growth
law $H$ itself is logically deep and useful (in fact the time needed to
generate this sequence from a small program as described above is unbounded)
as it aids the creation of all other valuable objects. An art appraiser with a
vast knowledge of what constitutes valuable works, enjoys such efficiency when
it comes to evaluating a new artwork; here we say their collective knowledge
is useful which possibly took a long time to build.

Another natural question to ask is: whether there are ways of generating depth
more closely approximating the maximum allowed by the slow growth law: depth
$T$ in time $T$. One way of doing so would be simply to generate a string of
$T$ zeros. Then this string is valuable whenever $T$ itself is deep [3]. Time
$O(T)$ is clearly both necessary and sufficient to generate this string, but a
string of zeroes is not useful and it would be more satisfying to find an
example of an efficiently generated object deeper than its own bulk. It turns
out this can only be possible if the creator has access to a random oracle
with the help of which they can convert a simple string like $O^{n}$ to a deep
string that takes polynomial time $O(kn)$ to be generated for some constant
$k$; but it will take any normal observer proportional to $O(kn^{2})$ time to
generate the object from the same simple source [3]. The paintings of Jackson
Pollock has such quality: at a first glance they seem random and producible by
a trivial highly complex program. However, Pollock’s drip paintings have been
clearly identified as masterpieces which means they have overwhelming
probability to be generated by very slow-running short programs [6, 7]
regardless of the time taken by its creator.

##  4 Complexity of Verifying Value

Consider Colton’s art exhibition example again: the painter supplies the
observer with a short program that simulates the events and relationships of
the painter’s life up to the point of creating the random dots painting after
which the program terminates. If the program takes exponential time
$O(2^{|x|})$ in the painting’s length $|x|$ and the observer only has
polynomial time, is it possible for a sceptical observer to be convinced of
the meaning or value in the painting? Due to the deterministic nature of our
setup, the answer points towards the negative: the provided program has to be
run in order to see whether it outputs $x$ in the end. The exponential time-
bound here is not too ambitious as typically, the most valuable or useful
strings (like the Halting sequence $H$) take more than recursively bounded
time to be generated [3].

Note that this problem gets much more difficult if the painter instead claimed
the following: $p$ outputs $x$ in $O(2^{|x|})$ time and no other shorter
program does so more efficiently. Now, the observer additionally has to
enumerate all programs up-to length $|p|$, run them for $O(2^{|x|})$ and
reject the claim if any of the programs halts within the time with output $x$.
More difficult still is the claim that $x$ is logically deep with exponential
time bound with significance at least $|p|-K_{C}(x)$ as it would require the
observer to also generate all $|p|$ length programs to check whether
$O(2^{|x|})$ is the minimum time taken by the programs to generate $|x|$. In
general, the more valuable the object is, the harder it gets to detect such
value.

Because of the interactive nature of the value-verification problems let us
see what an interactive proof (IP) system [8] might look like. To determine
the value of $x$ we must first select a threshold runtime which can be
$O(2^{|x|})$ as before. An all-powerful prover can find the shortest program
$p$ that outputs $x$ in the designated time and to convince the verifier that
no other same length or shorter program can output $x$ faster, they can
provide a proof as following: the prover can run all programs with length
$\leq|p|$ for $O(2^{|x|})$ time, collect the outputs of the halting programs
and send it to the verifier. The problem then reduces to finding $x$ in this
string. Note that, since the programs are allowed to run for $O(2^{|x|})$ time
the largest output can have length at-most $O(2^{|x|})$ and in the worst case,
the proof can have length $O(2^{|p|+|x|+O(1)})$. If the communication overhead
between the two parties is allowed to be exponential then an exponential
verifier can easily with high probability accept or reject the proof (each
message from the prover contains a $O(2^{|x|})$ length output which the
verifier compares with $|x|$ and there are at most $O(2^{|p|})$ messages).
However, it is not clear whether a polynomial time-bounded verifier can accept
or reject such proofs with high probability and if they have access to a
random oracle (which is a standard addendum to a verifier in IP) what must its
purpose or computational complexity be.

Note that such austere difficulty in assessing value comes from the fact that
compression is generally a more difficult task that decompression [9]. To find
a non-trivial compression $q(x):C(q(x))=x\texttt{ and }q(x)<|x|$ the search
space becomes exponential to find some encoding which decompressed to $|x|$.
Besides some objects are cryptographically pseudo-random [3, 10], meaning it
is extremely difficult to pin-point a non-random source for them (highly
sophisticated and complex artworks are good examples of this). While this
maybe unsatisfactory, it might still be possible to efficiently detect a
logically shallow or valueless artifact. A dishonest prover may claim that a
shallow object is valuable but being shallow it is guaranteed to have at least
one fast short program that generates the object. A clever observer after some
bounded time analysis (or compression) of the object can detect such short
program and refute the claim with high probability [9].

##  5 Conclusion and Future Direction

We presented an object-dependent analysis of value rooting it in Algorithmic
Information Theory and discussed the computational difficulty associated with
determining and creating such value. Although such formulation does not take
into account the object’s cultural significance, its ability to be understood
by viewers, or any other social properties, various authors [11, 12] have made
similar connections between an object’s value and its buried computational
effort. This is also related to a notion of “organized complexity” found in
nature: a priori the most probable explanation for the sequence of bases in a
biological object like a DNA molecule is that it is the product of an
extremely long evolutionary process [1].

We presented a time-dependent discussion but analogous results can be shown
for space-bounded computation which illustrates the difficulty a mechanism
with limited-memory faces when critiquing or evaluating a valuable object.
Moreover, space-bounded computation sheds light on another exciting research
direction: an object which stores information about its own creation. This is
formalized with reversible computation where a computer along with the output
supplies all the discarded information that can be used to trace back to the
original program that is the source of the object. Then storing information
from a long computation quickly becomes intractable, specially for one-way
naturally occurring processes: a bottle of sterile nutrient solution has low
complexity, but if inoculated with a single bacterium it can quickly turn into
a bacterial culture. The rapid growth of bacteria following introduction of a
seed bacterium is a irreversible process and even without the seed the forward
process is vastly more probable than its reverse: transformation of bacteria
into low-complexity energy nutrient. Complexity thus not to increase quickly,
except with low probability, but can increase slowly over geological time,
which makes taking snapshots of such progress extremely space-inefficient.

Another future direction for research will be to situate the intractable
problems in value-determination within appropriate complexity classes. As we
noted in the previous sections, it is not possible to reliably verify the
value of an object in a classical settings within reasonable time-bound,
however the quantum realm can lend a hand. One way to approach this is the
observation that a valuable or logically deep object is one that is not in the
set of shallow or valueless objects (our example of diagonal creation of value
made use of this principle) and shallow or even weekly deep objects [3] are
abundant in nature. This problem is remarkably similar to the Group non-
membership problem [13] which belongs to the Quantum Merlin-Arthur (QMA) [14]
complexity class. We do not go into details but including or excluding the
value problems from such classes will give a good idea about their true
complexities and whether quantum techniques like entanglement and super-dense
coding plays any role in efficient verification of value.

##  6 Acknowledgement

I would like to thank Prof. Daniel Brown for his valuable comments and
suggestions on the topics of this short paper.

## References

  * [1] Ming Li and Paul M.B. Vitányi.  An Introduction to Kolmogorov Complexity and Its Applications.  Springer Publishing Company, Incorporated, 4th edition, 2019.
  * [2] R. Landauer.  Irreversibility and heat generation in the computing process.  IBM Journal of Research and Development, 5(3):183–191, 1961.
  * [3] C. H. Bennett.  Logical depth and physical complexity.  In A Half-Century Survey on The Universal Turing Machine, page 227–257, USA, 1988. Oxford University Press, Inc.
  * [4] Simon Colton.  Creativity versus the perception of creativity in computational systems.  In AAAI Spring Symposium: Creative Intelligent Systems, pages 14–20. AAAI, 2008.
  * [5] Hector Zenil, Delahaye Jean-Paul, and Cédric Gaucherel.  Image characterization and classification by physical complexity.  Complexity, 17:26 – 42, 01 2012.
  * [6] Luís Antunes and Lance Fortnow.  Sophistication revisited.  Theor. Comp. Sys., 45(1):150–161, April 2009.
  * [7] Tiasa Mondol and Daniel G. Brown.  To Appear in the Proceedings of the Twelfth International Conference on Computational Creativity, Mexico Virtual, September 14-18, 2021, 2021.
  * [8] S Goldwasser, S Micali, and C Rackoff.  The knowledge complexity of interactive proof-systems.  In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC ’85, page 291–304, New York, NY, USA, 1985. Association for Computing Machinery.
  * [9] Stephen Fenner and Lance Fortnow.  Compression complexity, 2017.
  * [10] Y. Liu and R. Pass.  On one-way functions and kolmogorov complexity.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1243–1254, Los Alamitos, CA, USA, nov 2020. IEEE Computer Society.
  * [11] Clément Vidal and Jean-Paul Delahaye.  Universal ethics: Organized complexity as an intrinsic value.  In Georgi Yordanov Georgiev, John M. Smart, Claudio L. Flores Martinez, and Michael E. Price, editors, Evolution, Development and Complexity, pages 135–154, Cham, 2019. Springer International Publishing.
  * [12] Seth Lloyd and Heinz Pagels.  Complexity as thermodynamic depth.  Annals of Physics, 188(1):186–213, 1988.
  * [13] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery.
  * [14] C. Marriott and J. Watrous.  Quantum arthur-merlin games.  In Proceedings. 19th IEEE Annual Conference on Computational Complexity, pages 275–285, Los Alamitos, CA, USA, jun 2004. IEEE Computer Society.