# Cosmological black holes: the spherical perfect fluid collapse with pressure
in a FRW background

Rahim Moradi  Department of Physics and ICRA, Sapienza University of Rome,
Aldo Moro Square 5, I-00185 Rome, Italy and
ICRANet, Square of Republic 10, I-65122 Pescara, Italy
<EMAIL_ADDRESS>Javad T. Firouzjaee  School of Astronomy, Institute
for Research in Fundamental Sciences (IPM), P. O. Box 19395-5531, Tehran, Iran
<EMAIL_ADDRESS>Reza Mansouri  Department of Physics, Sharif University
of Technology, Tehran, Iran and
School of Astronomy, Institute for Research in Fundamental Sciences (IPM),
Tehran, Iran<EMAIL_ADDRESS>
###### Abstract

We have constructed a spherically symmetric structure model in a cosmological
background filled with perfect fluid with non-vanishing pressure as an exact
solution of Einstein equations using the Lemaître solution. To study its local
and quasi-local characteristics including the novel features of its central
black hole, we have suggested an algorithm to integrate the equations
numerically. The result shows intriguing effects of the pressure inside the
structure. The evolution of the central black hole within the FRW universe,
its decoupling from the expanding parts of the model, the structure of its
space-like apparent horizon, the limiting case of the dynamical horizon
tending to a slowly evolving horizon, and the decreasing mass in-fall to the
black hole is also studied. The cosmological redshift of a light emitted from
the cosmological structure to an observer in the FRW background is also
calculated. This cosmological redshift includes local and cosmic part which
are explicitly separated. We have also formulated a modified NFW density
profile for a structure to match the exact solution conditions.

###### pacs:

95.30.Sf,98.80.-k, 98.62.Js, 98.65.-r

##  I introduction

The term cosmological black hole (CBH) is used to describe a collapsing
structure within an otherwise expanding universe after the radiation era. This
is different from the term astrophysical black holes (ABHs) coined to use for
the applications of static or stationary asymptotically flat black holes in
astrophysics (see for example recent paper ellis-13 ). CBHs are fundamentally
different from the ABHs in being non-stationary and having a dynamical
horizon, although being as much interesting as ABHs for the astrophysical
applications and well suited to be used as a test arena for fundamental
physics in strong gravity and quasi-local phenomena in weak gravity regimes.
Despite extensive studies in relativistic structure formation and static and
stationary black holes we still have little information based on exact general
relativistic studies regarding the main features of such overdense
cosmological regions including its central black hole.
Since the early beginning of the discovery of the expansion of the universe
people have been looking for models describing an overdense region in a
cosmological background (McVittie , see also cosmological black hole ). In the
matter dominated era the initial expansion of an overdense region within an
expanding universe will finally decouple from the background and collapses to
a dynamical black hole, in contrast to the overdensity regions in the
radiation dominated era in the early universe where the density perturbation
has to be of the order of the horizon to collapse to a primordial black hole
(PBH). In the matter dominated era, we expect a CBH within the resulting
structure and a very weak gravitational field outside it, being different from
the familiar Schwarzschild one in being neither static nor asymptotically flat
man . Therefore, such cosmological structures, if based on exact solutions of
general relativity and not produced by a cut-and-paste technology, are very
interesting laboratories to study not only general relativistic non-linear
structures, their quasi-local features such as mass and horizons man , black
holes thermodynamics and information loss puzzle giddings-12 ; manradiation ,
but the validity of the weak field approximation as well mojahed . After all,
the universe is evolving and asymptotically not Minkowskian. Therefore, one
needs to have a dynamical model for a black hole, to be compared with the
familiar results in the literature on black holes within a static and
asymptotically flat space-time waldbook , where global concepts such as the
event horizon are not defined. Nevertheless, depending on the specific
cosmological model we may be able to define a hypersurface separating the
trapped null outgoing geodesics from those approaching (future-)infinity. This
hypersurface effectively plays the role of the event horizon man .
Numerically, this hypersurface is determined by tracing the outgoing null
geodesics at late times; We will refer to it as the quasi event horizon.

The need for a local definition of black holes and their horizons has led us
to concepts such as Hayward’s trapping horizon Hayward94 , isolated horizon
ashtekar99 , Ashtekar and Krishnan’s dynamical horizon (DH) ashtekar02 , and
Booth and Fairhurst’s slowly evolving horizon booth04 . The CBH we are going
to study is an excellent example of testing these different concepts and their
relationship in addition to understand its difference to an asymptotically
Minkowskian and static black hole. Now, a widely used metric to describe the
gravitational collapse of a spherically symmetric dust cloud is the so-called
Tolman-Bondi-Lemaître(LTB) metric LTB . Exact general relativistic models for
the dynamic of an asymptotically FRW structure leading to a central dynamical
black hole based on a LTB metric with no pressure has been reported in man ;
mangeneral . These models may be extended to a perfect fluid with a non zero
pressure, the so-called Lemaître models hellaby . Our interest is now using
these inhomogeneous cosmological solutions of Einstein equations as a model
for a cosmic structure with non-vanishing internal pressure leading to a
dynamical CBH within a FRW matter dominated expanding universe. We, therefore,
try an ideal fluid with an interpolating pressure function being non-zero
inside the structure and vanishing at infinity where we expect a matter
dominated FRW universe. To achieve this goal, we have to avoid any cut-and-
paste technology of finding the solution. Any internal solution pasted to a
FRW universe does not reflect the dynamics of the inhomogeneous universe due
to the homogeneity of FRW universe outside the structure. In contrast, our
model is just asymptotically FRW reflecting the full relativistic local and
quasi-local effects due to the cosmic fluid. The ideal fluid is modeled such
that the non-vanishing pressure inside the structure goes smoothly to a matter
dominated universe far from the structure. A similar problem studied
extensively in literature in the last 40 years is the issue of primordial
black holes (PBHs). These are structures within the radiation dominated phase
of the universe, usually in the late phase of inflation, due to the
superhorizon perturbations pbh . PBHs are usually based on the same Lemaître
cosmological solutions of Einstein equations which are spherically symmetric
and inhomogeneous. The perturbation is formalized by assuming that the horizon
size $R_{H}$ is smaller than the structure size $R_{S}$, or by assuming
$\epsilon\equiv\frac{R_{H}}{R_{S}}<1$, where the relevant quantities are
expanded in the powers of $\epsilon$. Using the same Lemaître solution
although not in the same coordinates, we are interested in cases where
$\epsilon\gg 1$, i.e. structures are much smaller than the horizon size as
expected for cosmological structures within the matter dominated FRW universe.
Therefore, we expect to recover novel features and we have also to propose a
new algorithm how to solve numerically the field equations. In addition we are
asking different questions such as the kind of black holes we may encounter
and the characteristics of their apparent and event horizons, the effect of
the pressure inside the structure on the collapse behavior and the matter
flux. There are many other questions encountering in black hole literature to
be faced in future studies, such as the definition of a non-rotating
spherically symmetric dynamical black hole within an expanding universe, its
differences to the simple Schwarzschild or Kerr black hole, its event and
apparent horizon and their features, the internal structure of CBH, the rate
of collapse, the effect of pressure inside the structure and its probable non-
Newtonian and non-linear novel effects due to the non-vanishing matter
outside, and the information puzzle. That is why the study of CBHs goes beyond
the study of PBHs and is a new arena for a novel black hole terminology.
Section II is an introduction to the spherically symmetric inhomogeneous
prefect fluid cosmological models. In section III the result of the numerical
integration is reported expressing the main characteristics of our model
assuming different pressure profiles. In the section IV, the redshift of the
light coming from nearby the structure is investigated. In section V we
develop a modified NFW density profile for a cluster of galaxies taking into
account the requirements of our solution and study its evolution. We will then
discuss the result in section VI. Throughout the paper we assume $8\pi G=c=1$.

##  II General spherically symmetric solution

Consider a general inhomogeneous spherically symmetric spacetime hellaby
filled with a perfect fluid and a metric expressed in the comoving
coordinates, $x^{\mu}=(t,\,r,\,\theta,\,\phi)$:

$ds^{2}=-e^{2\sigma}\,dt^{2}+e^{\lambda}\,dr^{2}+R^{2}\,d\Omega^{2}\;,$ (1)

where $\sigma=\sigma(t,r)$, $\lambda=\lambda(t,r)$ are functions to be
determined, $R=R(t,r)$ is the physical radius, and
$d\Omega^{2}=d\theta^{2}+\sin^{2}\theta\,d\phi^{2}$ is the metric of the unit
2-sphere. The energy momentum tensor of the perfect fluid is given by

$T^{\mu\nu}=(\rho+p)\,u^{\mu}\,u^{\nu}+g^{\mu\nu}p\;,$ (2)

where $\rho=\rho(t,r)$ is the mass-energy density, $p=p(t,r)$ is the pressure,
and $u^{\mu}=(e^{-\sigma},0,0,0)$ is the perfect fluid four-velocity.

###  II.1 Field Equations

In addition to the Einstein field equations,
$G^{\mu\nu}=\kappa\,T^{\mu\nu}-g^{\mu\nu}\Lambda$, we will use the
conservation equations in the form

$\frac{2e^{2\sigma}}{(\rho+p)}\,\nabla_{\mu}T^{t\mu}=\dot{\lambda}+\frac{2\dot{\rho}}{(\rho+p)}+\frac{4\dot{R}}{R}\;=0$
(3)
$\frac{e^{\lambda}}{(\rho+p)}\,\nabla_{\mu}T^{r\mu}=\sigma^{\prime}+\frac{p^{\prime}}{p+\rho}=0,$
(4)

where the dot means the derivative with respect to $t$, and the prime means
the derivative with respect to $r$. The Einstein equations lead finally to
following equations

$\frac{\partial}{\partial r}\left[R+R\dot{R}^{2}e^{-2\sigma}-RR^{\prime
2}e^{-\lambda}-\frac{1}{3}\Lambda R^{3}\right]=\kappa\rho R^{2}R^{\prime},\;$
(5)

and

$\frac{\partial}{\partial t}\left[R+R\dot{R}^{2}e^{-2\sigma}-RR^{\prime
2}e^{-\lambda}-\frac{1}{3}\Lambda R^{3}\right]=-\kappa pR^{2}\dot{R}.\;$ (6)

The term in the brackets is related to the Misner-Sharp mass, $M,$ defined by

$\frac{2M}{R}=\dot{R}^{2}e^{-2\sigma}-R^{\prime
2}e^{-\lambda}+1-\frac{1}{3}\Lambda R^{2}\;.$ (7)

Eqs (5) and (6) may now be written as

$\kappa\rho=\frac{2M^{\prime}}{R^{2}R^{\prime}}~{},\kappa
p=-\frac{2\dot{M}}{R^{2}\dot{R}}~{}.$ (8)

We may write Eq (7) in the form of an evolution equation of the model:

$\dot{R}=\pm e^{\sigma}\sqrt{\frac{2M}{R}+f+\frac{\Lambda R^{2}}{3}}~{},\\\ $
(9)

where

$f(t,r)=R^{\prime 2}e^{-\lambda}-1~{}$ (10)

is the curvature term, or twice the total energy of test particle at $r$
(analogous to $f(r)$ in the LTB model). In this paper we have set $\Lambda$=0.
Note that $R(t,r)$ can not be directly obtained from this equation because of
the unknown functions $\lambda$, $\sigma$, and $M$.

The metric functions $g_{tt}$ and $g_{rr}$ may be obtained by integrating (4)
and (3):

$\sigma=\ c(t)-\int_{r_{0}}^{r}\frac{p^{\prime}\,\
dr}{(\rho+p)}|_{t=const}=\sigma_{0}-\int_{\rho_{0}}^{\rho}\frac{(\frac{\partial
p}{\partial\rho})}{(\rho+p(\rho))}\,d\rho~{}|_{t=const},$ (11)

and

$\lambda=\lambda_{0}(r)-2\int_{\rho_{0}}^{\rho}\frac{d\rho}{(\rho+p(\rho))}-4\ln\left(\frac{R}{R_{0}}\right)~{}|_{t=const},$
(12)

where $c(t)$ and $\lambda_{0}(r)$ are arbitrary functions of integration (see
hellaby  for more details). In the case of $c(t)$ it is easily seen that
requiring our coordinates to lead to the LTB synchronous ones for $p=0$ leads
to $c(t)=0$. We notice also that according to (10) and the LTB coordinate
conditions, the choice of $\lambda_{0}(r)$ is equivalent to the choice of
$f(t_{0},r)=f_{0}(r)$. One may prefer to choose $f_{0}(r)$ and then calculate
$\lambda_{0}(r)$ from $e^{\lambda_{0}}=R_{0}^{\prime 2}/(1+f_{0})$.
We have therefore 5 unknowns $p,\rho,\sigma,\lambda$, and $R$, four dynamical
equations $\dot{\rho}$, $\dot{M}$, $\dot{\lambda}$, and $\dot{R},$ in addition
to an equation of state $p=p(\rho)$, and the definition of the mass $M$ (7).
This defines a numerical algorithm to find solutions for the dynamics of our
spherical structure after assuming the initial conditions. The algorithm for
solving the coupled PDEs can be found in mine

##  III equation of state and the results

We are now ready to specify the equation of state and integrate the model to
see its characteristics. To have a comparative discussion of the results we
consider two types of equation of state: a perfect fluid with a constant state
function, $p=w\rho$, and a more general case with the equation of state
$p=ws(r)\rho$ matching our needs for a structure with pressure inside the
structure and a pressure-less matter dominated universe far from the
structure. We may then choose the function $s(r)$ in a way that the pressure
becomes zero at infinity, i.e. at $r>>r_{0}$. A suitable choice is
$s(r)=e^{-\frac{r}{r_{0}}}$ where $r_{0}$ is the distance of the void
(boundary of expanding and collapsing phase) from the center of the structure.
This is a more realistic model to describe a black hole collapse within the
FRW universe and to see the effect of the inside pressure while the universe
outside is matter dominated with no pressure.

The model we envisage starts from a small inhomogeneity within a FRW universe.
The density profile should be such that the metric outside the structure tends
to FRW independent of the time while the central overdensity region undergoes
a collapse after some initial expansion. At the initial conditions, where the
density contrast of the overdensity region is still too small, we may assume
that the metric is almost FRW or LTB; the density contrast and the pressure
does not play a significant role. The dynamics of Lemaître universe will give
us anyhow the expected structure at late times. To choose the initial
conditions at the time $t_{0}$, we will therefore use a LTB solution with a
negative curvature function. We have in fact tried both examples of LTB or FRW
initial data and received no significant difference between the final Lemaître
solutions.
Now, let us choose the the two initial functions $f(r)=f(t_{0},r)$ and
$M(r)=M(t_{0},r)$ in the following way to achieve an asymptotically FRW final
solution:

$f(r)=-\frac{1}{b}re^{-r},$ (13) $M(r)=\frac{1}{a}r^{3/2}(1+r^{3/2}).$ (14)

Far from the central overdensity region we have

$lim_{r\rightarrow\infty}f(r)=0,$ (15)
$lim_{r\rightarrow\infty}M(r)=\frac{r^{3}}{a},$ (16)

showing the asymptotically FRW behavior of the initial conditions. The
corresponding LTB solution of Einstein equations now gives us $R(r)=R_{0}(r)$
at the initial time $t_{0}$. By choosing suitable a and b the ”reality
condition”Joshi

$\frac{2M}{R}+f+\frac{\Lambda R^{2}}{3}>0,$ (17)

will be satisfied. This condition can be obtained from Eq (9). In addition to
”reality condition”, the ”weak energy condition” Joshi  must be satisfied at
every r and t:

$\rho(r,t)\geq 0,\quad\rho(r,t)+p(r,t)\geq 0,$ (18)

It can be seen from Fig.(1) that our initial conditions give rise to
$\rho(r,t)\geq 0$ at every t and r.

Assuming an equation of state to satisfy weak energy condition, $p(r,t)\geq
0$, is now enough to numerically calculate the necessary dynamical functions
of the model. Specifically, by looking at $\dot{R}(t,r)$ and $\rho(t,r)$ we
may extract informations of how the central region starts collapsing after the
initial expansion and how a black hole with distinct apparent and event
horizons develops while the outer region expands as a familiar FRW universe.
We may also find out the difference to the case of the pressure-less model. It
will also show if and how the very weak gravity outside the collapsed
structure affects the dynamic of the central structure in comparison to the
familiar Schwarzschild model. The results of the numerical calculation for
both equation of states are given in the following sections.

###  III.1 The density behavior

The density profiles for both equation of states as a function or $t$ and $r$
are given in Fig.(1). A comparison of these figures shows the effect of the
pressure on the development of the central black hole. Obviously in case of
non-vanishing pressure outside the structure the collapse is more highlighted
with a more steep density profile. The over-density region in the collapsing
phase is always separated from the expanding under-density region through a
void not expressible in these figures. We will consider the deepest place of
the void as the boundary of the structure. This boundary is always near by the
boundary of the contracting and the expanding region of the model structure.

(a) Density evolution of our cosmological black hole for the perfect fluid
with the equation of state $p=w\rho$. (b) Density evolution of our
cosmological black hole for the perfect fluid with the equation of state
$p=w\rho s(r)$. Note the less significant central density and the more flat
density profile near the center of the structure.

Figure 1: Density evolution of our cosmological black hole.

In the numerical calculation at late times the density near the center of the
black hole approaches infinity leading to numerical errors and crashing of the
algorithm. We refer to this effect as the black hole singularity, as discussed
in man ; mine . The cosmological singularities (big bang and big crunch) are
not included in our numerical simulation due to the initial conditions being
fixed at a time much later than the big bang in the matter dominated era.
Assuming the background to be the standard flat FLRW metric, there is no big
crunch singularity in our model. By selecting other backgrounds such as the
closed FLRW model, the big crunch singularity will play a crucial role in the
development of singularities man .

###  III.2  The pressure effect

Figs.(2(a)) and (3(a)) show the behavior of the collapsing and the expanding
regions for the equation of state $p=w\rho$ by depicting the corresponding
Lemaître Hubble parameter $\dot{R}/R$ versus the physical radius $R$. Figs.
(2(b)) and (3(b)) show similar data for the equation of state $p=ws(r)\rho$.
Note that the function $s(r)$, as defined to get matter dominated FRW universe
at far distances, has no significant effect, and the qualitative behavior of
the dynamics of the physical radius is independent of it. Therefore, as far as
we are interested in the qualitative features of the model, we will just use
the simple equation of state with $s(r)=1$.
The place of separation between the expanding and collapsing region defined by
$\dot{R}>0$ and $\dot{R}<0$ is almost coincident with the place of the void
where we have defined as the boundary of the structure. Now, from the figures
we realize that the effect of the pressure in different regions of the model
and its comparison to the homogeneous FRW model is an intriguing one. As we
know already from the Friedman equations in FRW models, the pressure adds up
to the density and has an attractive effect slowing down the expansion leading
to a more negative acceleration ($\frac{\ddot{a}}{a}=-\frac{1}{6}(\rho+3p)$).
This is evident from the figures at distances far from the center where our
model tends to an FRW one. Whereas within the structure where we have a
contracting overdensity region the behavior is counter-intuitive. Except for
the case of vanishing pressure, in all the other cases the pressure begins
somewhere to act classically like a repulsive force opposing the collapse of
the structure. To see this more clearly, we have also depicted the
acceleration in Fig.(4). As we approach distances near to the center, the
negative acceleration in the FRW limit and even inside the void, gradually
increases to positive values, meaning that somewhere within the structure the
contraction of the structure slows down due to the pressure like a classical
fluid. Therefore, the pressure effect begins somewhere within the structure to
act like a repulsive force in contrast to the outer regions where its
attractive nature dominates. Note that the central black hole and its horizon
has a much smaller radius than the region of the repulsive pressure effect we
are discussing.

(a) The overall scheme: $\dot{R}>0$ and $\dot{R}<0$ show the expanding and
collapsing regions, respectively. (b) A magnified scheme related to the
regions near to the center

Figure 2: The behavior of the Hubble parameter $\dot{R}/R$ in the case of
$p=w\rho$. Evidently the pressure slows down the collapse velocity near the
center of the structure

(a) The overall scheme: $\dot{R}>0$ and $\dot{R}<0$ show the expanding and
collapsing regions, respectively.  (b) A magnified scheme related to the
regions near to the center.

Figure 3: The behavior of the Hubble parameter $\dot{R}/R$ in the case of
$p=w\rho s(r)$. The features are qualitatively as in Fig (2).

(a) The overall scheme: $\dot{R}>0$ and $\dot{R}<0$ show the expanding and
collapsing regions, respectively.  (b) The overall scheme of the acceleration.

Figure 4: The behavior of the Hubble parameter $\dot{R}/R$ and the
acceleration $\ddot{R}/R$ in the case of $p=w\rho$.

###  III.3 The Apparent and Quasi Event Horizon

The boundary of a dynamical black hole, where the area law and the black hole
temperature are defined, is a non-trivial concept (see for example man ,
Faraoni  and manradiation ). Our model is again a concrete example to see the
behavior of both apparent and quasi event horizon of a dynamical structure
within an expanding universe. It is easily seen that the apparent horizon of
our cosmological black hole is located at $R=2M$ mangeneral . We note that
after the formation of an apparent horizon the central density goes to
infinity indicating the formation of the singularity at the center. Therefore,
the singularity is covered by the dynamical horizon and is not naked!

This apparent horizon is calculated in $t,r$ coordinates numerically. It is
always space-like tending to be light-like at late times. This can best be
seen by comparing the slope of the apparent horizon relative to the light cone
at every coordinate point of it. This is in contrast to the Schwarzschild
black hole horizon where it is always light-like. At the late times, however,
we expect the apparent horizon to become approximately light-like and
approaching the event horizon. This is reflected in the Fig.(5). It is evident
that $\frac{dt}{dr}|_{AH}<\frac{dt}{dr}|_{null}$ at all times on the apparent
horizon, the difference tending to zero at late times. Therefore, the apparent
horizon is always a space-like _dynamical horizon_ leading to a _slowly
varying horizon_ at late times ashtekar02 ; man . Note that the qualitative
result is independent of the equation of state.

(a) The $p=w\rho$ case: $\frac{dt}{dr}|_{AH}<\frac{dt}{dr}|_{null}$ on the
apparent horizon. Therefore, the apparent horizon is always a space-like
dynamical horizon leading to a slowly varying horizon at late times.  (b) The
$p=ws(r)\rho$ case: $\frac{dt}{dr}|_{AH}<\frac{dt}{dr}|_{null}$ on the
apparent horizon. Qualitatively, there is no difference to the Fig.(a).

Figure 5:  $\frac{dt}{dr}|_{AH}<\frac{dt}{dr}|_{null}$ on the apparent
horizon. Qualitatively, there is no difference between two equation of states.

We now show how the dynamical horizon of our cosmological black hole becomes a
_slowly evolving horizon_ at late times. Let’s first define the evolution
parameter $c$ such that the tangent vector to the dynamical horizon, $V$, is
given by

$V^{\mu}=\ell^{\mu}-cn^{\mu},$ (19)

where the two vectors $\ell^{a}$ and $n^{a}$ are normal null vectors on a
space-like two surface $S$ in $(t,r)$ plane (see ashtekar02 ). We expect $c$
to go to zero at late times in order for our dynamical horizon to become a
_slowly evolving horizon_. In the case of our Lemaître model $c$ is calculated
to be

$\displaystyle
c=2\frac{M^{\prime}+wM^{\prime}}{M^{\prime}-wM^{\prime}-R^{\prime}}|_{AH}.$
(20)

The result of the numerical calculation for different equation of states and
different state functions is given in Fig.(6). The decreasing behavior of the
function $c$ in the course of time independent of the equation of state is
evident. We may then conclude that the dynamical horizon of the cosmological
black hole tends to a slowly evolving horizon.

(a) The $p=w\rho$ case: the more the pressure the sooner the dynamical horizon
becomes a slowly evolving horizon.  (b) The $p=w\rho s(r)$ case:
qualitatively, the same behavior as in Fig.(a).

Figure 6:  Dynamical horizon becomes a slowly evolving horizon.

###  III.4 The Effect of $\Lambda$ on the Formation of the Apparent Horizon

Let us now explore how the addition of a cosmological term $\Lambda$ to the
Einstein equations may influence the formation of the apparent horizon. The
location of the apparent horizon is now defined by mangeneral

$2M=R-\frac{\Lambda}{3}R^{3}~{}.$ (21)

Now, for a typical structure like a galaxy or a cluster of galaxies we have
$\frac{\Lambda}{3}R^{2}\ll\frac{2M}{R}$. Therefore, the location of the
apparent horizon is almost the same as in the case of vanishing cosmological
constant, i.e. $2M\approx R$. We may then refer to Fig(7) for the behavior of
the apparent horizon.

(a) The $p=w\rho$ case.  (b) The $p=ws(r)\rho$ case.

Figure 7: Adding $\Lambda$ to the Einstein equations does not have any
observable effect on the formation of the apparent horizon.

###  III.5  Mass and matter flux

Due to the expanding background we expect the matter flux into the dynamical
black hole to be decreasing and the dynamical horizon to become a slowly
evolving horizon in the course of timemangeneral . We know already that there
is no unique concept of mass in general relativity corresponding to the
Newtonian concept. The question of what does general relativity tell us about
the mass of a cosmological structure in a dynamical setting was discussed
recently manmass . It was shown razbin  that The Misner-Sharp quasi-local
mass, $M$, is very close to the Newtonian mass.

Let us then take the Misner-Sharp mass for this black hole and calculate the
corresponding matter flux into the black hole. In the case of Lemaîtremodel,
the matter flux is given by

$\displaystyle\frac{dM(r,t)}{dt}|_{AH}=\frac{\partial{M(r,t)}}{\partial{t}}|_{AH}+\frac{\partial{M(r,t)}}{\partial{r}}\frac{\partial{r}}{\partial{t}}|_{AH}=\dot{M}|_{AH}+M^{\prime}\frac{\partial{r}}{\partial{t}}|_{AH}$
(22)

The result of the numerical calculation is depicted in Fig.(8). Note how the
pressure decreases the rate of matter flux into the black hole at the late
time.

(a) The $p=w\rho$ case: the rate of matter flux into the black hole decreases
with the pressure.  (b) The $p=ws(r)\rho$ case: qualitatively the same
behavior as in Fig.(a).

Figure 8:  The rate of matter flux into the cosmological black hole.

##  IV Measuring the redshift in the Lemaître metric

In cosmology we are used to interpret the cosmological redshift according to
the homogeneous FRW model. What if the universe is inhomogeneous? In the
simplest case we are ready to model a source, a cosmological structure, within
an otherwise homogeneous FRW model using our Lemaître model. We assume now an
observer far from the source of light near the structure. What is then the
redshift measured by this observer? Given that the metric is an exact solution
of the Einstein equations, we expect the redshift to include all gravitational
effects including not only the cosmological redshift but also the
gravitational redshift due to the overdensity of the source.
The redshift in our model can be obtained as follows. Assume the light ray
coming from a source S located near to the structure in the center of our
inhomogeneous Lemaître model, and the observer O somewhere within the FRW
background having the corresponding 4-velocities $u^{\mu}_{(s)}$ and
$u^{\mu}_{(o)}$. Let $k^{\mu}\equiv dx^{\mu}/d\beta$ be the tangent vector to
the null geodesic connecting the source to the observer. The corresponding
redshift $z$, i.e. frequency shift, is then defined asDwivedi

$1+z={[k_{\mu}u^{\mu}_{(s)}]_{P_{1}}\over[k_{\mu}u^{\mu}_{(o)}]_{P_{2}}},$
(23)

where $[k_{\mu}u^{\mu}_{(s)}]_{P_{1}}$ and $[k_{\mu}u^{\mu}_{(o)}]_{P_{2}}$
are evaluated at the source and observer events. Let us assume the null
geodesics to be radial, i.e. $k^{\mu}k_{\mu}=0=k^{\mu}_{;\nu}k^{\nu}$. For the
metric in equation (1) we then have

$k^{r}={e^{\sigma}\over e^{\frac{\lambda}{2}}}k^{t}\Rightarrow{dt\over
dr}={e^{\frac{\lambda}{2}}\over e^{\sigma}}.$ (24)

Using now the geodesic equation, it is straightforward to show that

${dk^{t}\over d\beta}=-[{\sigma^{\prime}+(-\dot{\sigma}+\dot{\lambda\over
2}){e^{\frac{\lambda}{2}}\over e^{\sigma}}}]k^{t}k^{r},$ (25)

where $\beta$ is an affine parameter. Therefore,

${dk^{t}\over k^{t}}=-[{\sigma^{\prime}+(-\dot{\sigma}+\dot{\lambda\over
2}){e^{\frac{\lambda}{2}}\over e^{\sigma}}}]d\beta
k^{r}=-[{\sigma^{\prime}+(-\dot{\sigma}+\dot{\lambda\over
2}){e^{\frac{\lambda}{2}}\over e^{\sigma}}}]dr.$ (26)

Integrating the Eq.(26) we obtain

$k^{t}=c_{o}\exp{(-\int{[{\sigma^{\prime}+(-\dot{\sigma}+\dot{\lambda\over
2}){e^{\frac{\lambda}{2}}\over e^{\sigma}}}]dr})},$ (27)

where $c_{o}$ is a constant.
Now, the 4-velocities are given by

$u^{\mu}_{(s)}=\delta^{\mu}_{t}e^{-\sigma(r_{s},t_{s})},$ (28)
$u^{\mu}_{(o)}=\delta^{\mu}_{t}e^{-\sigma(r_{o},t_{o})}.$ (29)

Using equations (23), (28), (29), and (27) we obtain the cosmological redshift
in the presence of a structure ($z_{CBH}$):

$1+z_{CBH}=\exp[{(\int_{r_{o}}^{r_{1}}[{\sigma^{\prime}+(-\dot{\sigma}+\dot{\lambda\over
2}){e^{\frac{\lambda}{2}}\over
e^{\sigma}}}]dr)}]\frac{e^{\sigma_{r_{o}}}}{e^{\sigma_{r_{1}}}}.$ (30)
$1+z_{CBH}=\exp[{(\int_{r_{o}}^{r_{1}}[{(-\dot{\sigma}+\dot{\lambda\over
2}){e^{\frac{\lambda}{2}}\over
e^{\sigma}}}]dr)}]=\exp[{(\int_{r_{o}}^{r_{1}}[\frac{\partial}{\partial
t}{({e^{\frac{\lambda}{2}}\over e^{\sigma}}})]dr)}].$ (31)

Note that there was no need to calculate the $k^{r}$ due to $k_{r}u^{r}=0$.
Now, the Eq.(31) may be integrated numericaly using the equations for
$\dot{\sigma}$, $\sigma^{\prime}$, and $\dot{\lambda}$ from mine  for any
collapsing structure in an expanding FRW universe. The necessary initial
condition may be chosen along the line discussed in mine .
This redshift includes the familiar cosmological FRW part, $z_{C}$, as well as
the gravitational redshift, $z_{G}$ due to the overdensity of the structure
(the cosmological black hole). In general, we then expect it to be different
from that of the corresponding homogeneous FRW model. In the special case of a
homogeneous universe without a structure it reduces obviously to the familiar
FRW cosmological redshift $z_{C}=\frac{a(t_{o})}{a(t_{s})}-1$, lacking the
contribution from the local gravitational redshift of the overdensity,
$z_{G}$. To see the difference between the exact inhomogeneous cosmological
redshift according to our model and the sum $z_{G}+z_{C}$, let’s look at some
specific models.
Take a CBH model with the mass $10^{6}M_{\odot}$ at a distance corresponding
to $z_{C}=0.005$ from the observer. The gravitational redshift according to
the Schwarzschild metric is given by

$z_{G}\simeq={1\over(1-\frac{2M(r,t)}{R_{s}})}-1.$ (32)

Adding to it the FRW cosmological redshift

$z_{C}=\frac{a(t_{o})}{a(t_{s})}-1,$ (33)

should give us the CBH redshift we have already calculated, i.e.

$z_{CBH}\simeq z_{G}+z_{C}$ (34)

The result of the numerical calculation is given in Fig.(9). We see that the
exact $z_{C}BH$ is always larger that the sum of FRW cosmological redshift and
the local Schwarzschild gravitational redshift, although the difference is
smaller than the observational limit of accuracy. The difference $z_{C}BH-
z_{C}$ is shown in Fig.(10). The difference goes to zero for the source being
at distances far from the apparent horizon. There may be, however, cases that
this difference is not to be ignored. We leave it to a more detail study in
future to see where this difference may be of any cosmological significance.

Figure 9:  Difference of gravitational redshift and CBH redshift for the some
source near the CBH ($R_{ah}=R_{apparent-horizon}$). The observer place is
fixed.

$R/R_{ah}$ | $z_{G}$ | $z_{CBH}$ | $[z_{CBH}-(z_{G}+z_{C})]/(z_{CBH})$
---|---|---|---
30 | 0.01709 | 0.022173 | 0.00374
50 | 0.01015 | 0.015211 | 0.00401
70 | 0.00722 | 0.012263 | 0.00350
100 | 0.00458 | 0.00959 | 0.00101

Table 1: Numerical values of Fig.(9)

.

Figure 10:  The difference between cosmological and CBH redshift for several
observers located at different physical distances, the source of photon is
fixed for all observers.

##  V Modeling the evolution of a cluster of galaxies using the Lemaître
metric: Case of A2061

Now we are ready to use our exact solution and the corresponding algorithm to
study the collapse of a real galaxy cluster within an otherwise expanding
universe using a fluid model. Clusters of galaxies are modeled by a
spherically symmetric (isotropic) dark matter halo assumed to dominate the
dynamics of the system. The density profile of such a halo is often described
by the Navarro-Frenk-White (NFW) profile NFW :

$\rho_{NFW}(r)=\frac{\delta_{c}\rho_{c}}{\frac{r}{r_{s}}(1+\frac{r}{r_{s}})^{2}},$
(35)

where $r_{s}$ is a scale radius, $\rho_{c}$ is the critical density, and the
characteristic overdensity $\delta_{c}$ being a function of cluster
concentration $c=r_{200}/r_{s}$ given by

$\delta_{c}=\frac{200}{3}\frac{c^{3}}{\ln(1+c)-\frac{c}{1+c}}.$ (36)

The parameter $r_{200}$ is the radius at which the average interior density is
$200~{}\rho_{c}$ being approximately equal to the virialized overdensity,
$\rho_{virial}=178~{}\rho_{c}$. The NFW profile in Eq.(35) has three
undesirable features to be applied to our case of a cosmological structure:
1) The density tends to infinity at small r.
2) The NFW mass diverges at large r and can not be matched to the with FRW
mass;
3) Due to the lack of a void it doesn’t represent a density profile for a
structure within an expanding universe.
We have then to modify it to remedy these deficiencies. To resolve the first
problem, we introduce a maximum density at very small r:

$\rho_{1~{}NFW}(r)=\frac{\delta_{c}\rho_{c}}{(\epsilon_{c}+\frac{r}{r_{s}})(1+\frac{r}{r_{s}})^{2}}.$
(37)

The second problem will be resolved by introducing the truncation radius
$r_{t}$:

$\rho_{2~{}NFW}(r)=\frac{\delta_{c}\rho_{c}}{(\epsilon_{c}+\frac{r}{r_{s}})(1+\frac{r}{r_{s}})^{2}}{(\frac{r^{2}_{t}}{r^{2}+r^{2}_{t}})^{2}}.$
(38)

In order to resolve the third problem, we add a Gaussian density profile to
match the overdensity region through a void to the cosmological background as
is necessary for any exact solution of Einstein equations (see mansouri-
khakshournia  and mojahed ):

$\rho_{G}(r)=a\exp(-\frac{(r-r_{1})^{2}}{r_{0}}).$ (39)

The parameters $r_{0}$ and $r_{1}$ give us the freedom to adjust the location
of the void as desired. For our model cluster, A2061 Yoon , we choose $c=3$,
$a=1$Mpc, and $\epsilon_{c}=0.1$ to have $r_{200}=1.723$Mpc . Our metric
solution has to approach FRW at large r outside the cluster. Therefore, we add
a homogeneous background density such that the final density profile at
$t_{0}$ becomes

$\rho_{cluster}(r)=\rho_{2~{}NFW}(r)-\rho_{G}(r)+\rho_{c}.$ (40)

Note that the Gaussian profile must be added in such a way that

$\int_{0}^{r_{1}}r^{2}\rho_{G}dr=\int_{0}^{r_{1}}r^{2}\rho_{2}(r)dr,$ (41)

where $r_{1}$ is the distance at which the density approaches the background
critical density. It guaranties that the mass due to the overdensity in the
structure is compensated by the underdensity region within the void (See Fig.
(11)).
Now, by choosing $R(t_{0},r)=r$ and integrating Eq. (8) to determine
$M(t_{0},r)$ as well as having the equation of state, we can solve the coupled
evolution PDEs numerically. To have zero pressure at FRW background, a good
choice for the equation of state is $p(t,r)=w(\rho(t,r)-\rho_{c})$, in which
$\rho_{c}$ is just a function of time. The other initial functions are as
before. Fig.(11) shows the evolution of the galaxy cluster. By modifying the
NFW density profile to match the exact general relativistic requirements we
have therefore arrived at a model cluster based on the exact solution. We may
even go further and see how good we may rely on the observation of the red
shift of such a cluster and compare it to the model reflected in Eq.(31).
Based on the redshift of clusters estimated with spectroscopic data and the
redshift of the brightest cluster galaxies (BCGs) Yoon  we may take the
cosmological redshift of the galaxy cluster A2061 to be $z=0.07845$, being
located at a distance around 330 Mpc. We may therefore model our galaxy
cluster such that its cosmological redshift is $z_{c}=0.07845$; The Eq.(31)
will then tell us if we need to add the gravitational redshift as part of the
cosmological one.
Fixing the observer distance at 330Mpc, and solving the Eq.(31) we see that
the gravitational redshift is about two orders of magnitude smaller than the
cosmological redshift. Therefore, we have a well defined dynamical model of
the structure including a modified density profile fitted well with
observation. The effect of gravitational redshift may be much bigger for
supermassive blackholes Pollack:2014rja . Any other density profile may also
be modified and adapted to requirements as indicated in this section.

Figure 11:  Density evolution of the galaxy cluster.

##  VI DISCUSSION

We have studied the evolution of a structure made of perfect fluid with non-
vanishing pressure as an exact solution of Einstein equations within an
otherwise expanding FRW universe. The structure boundary is separated by a
void from the expanding part of the model which is very much like a FRW
universe already near by the void. We have noticed a counter-intuitive
pressure effect somewhere inside the structure where the existence of the
pressure slows down the collapse like a classical fluid in contrast to
distances far from the structure. The collapsed region develops to a dynamical
black hole with a space-like apparent horizon, in contrast to the
Schwarzschild black hole. This apparent horizon tends to a slowly evolving
horizon becoming light-like at late times with a decreasing mater flux into
the black hole. We have, therefore, to conclude that the mere existence of a
cosmological matter, even dust, may have significant effect on the central
black hole differentiating it from a Schwarzschild one irrespective of how
small the density outside the structure is.
The light properties of these cosmological black holes can be interesting
because most of the information about the black holes, galaxies and clusters
are coming from their lights. We have investigated the redshift of a light
emitted near by a cosmological structure to a distant observer. It was shown
that the exact CBH redshift of light includes both local gravitational and
cosmological redshift of the structure. Therefore, in the era of precision
cosmology we may be forced to consider the effects of inhomogeneities as seen
in the CBH cosmological model for high redshift surveys.
We have also seen how to generalize the existing models of density profile for
cold dark matter within large structures using the results of our structure
model. Although the gravity may be too weak near a large cosmological
structure, we can not use the Newtonian approximation due to the non-local or
quasi-local cosmological effects.

## References

  * (1) G. F. R. Ellis, arXiv:1310.4771 [gr-qc]; E. Berti, Braz. J. Phys. 43, 341 (2013) [arXiv:1302.5702 [gr-qc]].
  * (2) G.C. McVittie, Mon. Not. R. Astr. Soc. 93, 325 (1933); A. Einstein and E.G. Straus, Rev. Mod. Phys. 17, 120 (1945); 18, 148.
  * (3) Wessel Valkenburg, Gen.Rel.Grav. 44 (2012) 2449-2476; Xuelei Chen, You-Gen Shen and Valerio Faraoni, Phys.Rev. D84 (2011) 104047; Krzysztof Bolejko, Marie-Noelle Celerier and Andrzej Krasinski, Class.Quant.Grav. 28 (2011) 164002; E. Abdalla, N. Afshordi, M. Fontanini, D. C. Guariento and E. Papantonopoulos, Phys. Rev. D 89, no. 10, 104018 (2014).
  * (4) J. T. Firouzjaee, Reza Mansouri, Gen. Relativity Gravitation. 42, 2431 (2010) [arXiv:0812.5108].
  * (5) S. B. Giddings, Phys. Rev. D 85, 124063 (2012) [arXiv:1201.1037 [hep-th]].
  * (6) S. Khakshournia and R. Mansouri, Phys. Rev. D 65, 027302 (2002).
  * (7) M. P. Mood, J. T. Firouzjaee and R. Mansouri, arXiv:1304.5062 [astro-ph.CO]; M. P. Mood, J. T. Firouzjaee and R. Mansouri, Phys. Rev. D 88, 083011 (2013).
  * (8) Robert M. Wald, _General Relativity_ (University of Chicago Press, Chicago, 1984).
  * (9) S. A. Hayward, Phys. Rev. D 49, 6467 (1994).
  * (10) A. Ashtekar, C. Beetle, O. Dreyer, S. Fairhurst, B. Krishnan, J. Lewandowski and J. Wisniewski, Phys. Rev. Lett. 85, 3564-3567 (2000).
  * (11) A. Ashtekar and B. Krishnan, Phys. Rev. Lett. 89, 261101 (2002); A. Ashtekar and B. Krishnan, Phys. Rev. D 68, 104030 (2003).
  * (12) Booth I. and Fairhurst S., Phys. Rev. Lett. 92, 011102 (2004).
  * (13) R. C. Tolman, Proc. Natl. Acad. Sci. U.S.A. 20, 410 (1934); G. Lemaître, Ann. Soc. Sci. Bruxelles I A53, 51 (1933); H. Bondi, Mon. Not. R. Astron. Soc. 107, 343 (1947).
  * (14) J. T. Firouzjaee, Int. J. Mod. Phys. D, 21, 1250039 (2012) [arXiv:1102.1062].
  * (15) M. Razbin, J. T. Firouzjaee and R. Mansouri, Int. J. Mod. Phys. D 23, no. 9, 450074 (2014).
  * (16) J. T. Firouzjaee, M. Parsi Mood and Reza Mansouri, Gen. Relativ. Gravit. 44, 639 (2012) [arXiv:1010.3971].
  * (17) Alnadhief A. H. Alfedeel, Charles Hellaby, Gen.Rel.Grav. 42, 1935 (2010) [arXiv:0906.2343].
  * (18) B. J. Carr, Astrophys.J. 201, 1 (1975); M. Shibata and M. Sasaki, Phys. Rev. D 60, 084002 (1999); A. G. Polnarev, T. Nakama and J. ’i. Yokoyama, JCAP 1209, 027 (2012).
  * (19) Valerio Faraoni, arXiv:1309.4915v1 [gr-qc]
  * (20) J. T. Firouzjaee and Reza Mansouri, Europhys. Lett. 97, 29002 (2012) [arXiv:1104.0530]; Javad T. Firouzjaee and G. F. R. Ellis, Gen. Rel. Grav. 47, no. 2, 6 (2015) [arXiv:1408.0778 [gr-qc]]; Javad T. Firouzjaee and G. F. R. Ellis, Phys. Rev. D 91, no. 10, 103002 (2015) [arXiv:1503.05020 [gr-qc]].
  * (21) Pankaj S. Joshi and Daniele Malafarina. Int.J.Mod.Phys. D20 (2011) 2641-2729.
  * (22) I. H. Dwivedi, Phys. Rev. D 58, 064004 (1998).
  * (23) R. Moradi, J. T. Firouzjaee and R. Mansouri, arXiv:1301.1480 [gr-qc].
  * (24) J. F. Navarro, C. S. Frenk and S. D. M. White, Mon. Not. Roy. Astron. Soc. 275, 720 (1995) [astro-ph/9408069].
  * (25) J. Pollack, D. N. Spergel and P. J. Steinhardt, arXiv:1501.00017 [astro-ph.CO].
  * (26) Joo H. Yoon et al. 2008 ApJS 176 414 doi:10.1086/528958


cube that is not $\gamma$-good, and hence not contained in $U$, is at least
$R$-distant from each small cube contained in $W\left(U_{\gamma},R\right)$.
Finally, because $R<\frac{b_{m}}{m}\left(\frac{1}{10}k_{m}-1\right)$, if
$C_{0}\in U_{\gamma}$ is an extraordinary large cube, then
$W\left(C_{0},R\right)$ is non-empty and it contains a small cube $c_{0}\in
W\left(C_{0},R\right)\subseteq W\left(U_{\gamma},R\right)$ such that for any
$c$, if $d\left(c,c_{0}\right)\leq R$, then $c\in C_{0}$ and $c$ is
extraordinary. Therefore set $W\left(U_{\gamma},R\right)$ is
$\left(\gamma,R\right)$-good.

###  D.6. Proof of Theorem

Fix $\eta>0$. We are going to show that, for each $\eta>0$, there exist
constants $A,m_{0}>0$ such that, if $m\geq m_{0}$ and $M\geq A^{m^{6}}$, and
$G$ is $\left(M,m\right)$-lattice, then the probability that there is an
equilibrium $a$ on the $\left(M,m\right)$-lattice such that
$\text{Av}\left(a\right)=\frac{1}{M^{2}}\sum a\geq x^{*}+\eta$ is smaller than
$\eta$. The argument for the lack of equilibria with average action below
$x^{*}-\eta$ is analogous (and it follows from exchanging the roles for binary
actions 0 and 1). Combining the two bounds (and taking maximum of respective
constants $A$ and $m_{0}$) delivers the result.

Apply Lemma 12 to $\frac{1}{2}\eta$ and find $\delta>0$,
$a^{*}<x+\frac{1}{2}\eta$, $L<\infty$, and a $\delta$-contagion wave $\sigma$
for $P$.

Let $D\geq 1$ be a constant that is larger than the sum of constants from
Lemmas 15 and 16. Choose $\rho\leq\frac{1}{D}\delta$ and
$\gamma\leq\min\left(\delta,\frac{1}{4}\eta\right).$ Let $R_{\rho}$ be the
constant from Lemma 13. Let $R=R_{\rho}+L$. Let $m_{0}=m_{\gamma,\rho,R}$ and
$A=A_{\gamma,\rho,R}$. Choose $m\geq m_{0}$, $M\geq A^{m^{6}}$, and $b$ be as
in Lemma 17.

Let $W$ denote a $\left(\gamma,R\right)$-good set of cubes in the network of
small cubes $\mathcal{G}^{b}$ if such a set exists. Let $c_{0}\in W$ be the
cube such that for each $c$, if $d\left(c,c_{0}\right)\leq R$, then $c$ is
extraordinary.

Let $a$ be any equilibrium on the lattice. Let $W_{d}\subseteq W$ be a maximal
subset of small cubes such that the equilibrium $a$ is
$\left(W_{d},\gamma,R_{\rho}\right)$-dominated by $\sigma$. If $W$ exists,
then $c_{0}\in W_{d}$ and $W_{d}$ is non-empty. (To see why, notice that
$a\left(c\right)=0\leq\sigma\left(d\left(c,c_{0}\right)-R_{\rho}\right)$ for
each extraordinary cube, including all cubes $c$ st.
$d\left(c,c_{0}\right)\leq R$. Additionally,
$\sigma\left(d\left(c,c_{0}\right)-R_{\rho}\right)\geq\sigma\left(L\right)=1\geq
a\left(c\right)$ for each cube $c$ such that $d\left(c,c_{0}\right)>R$.) By
Lemmas 15 and 16, for each $\gamma$-good small cube $c$,

$\displaystyle a\left(c\right)$
$\displaystyle\leq\gamma+P\left(a^{*}+\sum_{a\in\sigma\left(\operatorname{\mathbb{R}}\right)}\left(1-f\left(\sigma^{-1}\left(a\right)+R_{\rho}-d\left(c,W_{d}\right)\right)\right)\left(a-a_{-}\right)+D\rho\right)$
$\displaystyle\leq\delta+P\left(a^{*}+\sum_{a\in\sigma\left(\operatorname{\mathbb{R}}\right)}\left(1-f\left(\sigma^{-1}\left(a\right)+R_{\rho}-d\left(c,W_{d}\right)\right)\right)\left(a-a_{-}\right)+\delta\right).$

Because $\sigma$ is a $\delta$-contagion wave (see Lemma 12), the above is no
larger than

$\leq\sigma\left(d\left(c,W_{d}\right)-R_{\rho}-\delta\right).$

Suppose that $W_{d}\neq W$. Because $W$ is connected, there is a cube
$c_{d}\in W\backslash W_{d}$ such that $c_{d}$ is a neighbor of
$c_{d}^{\prime}\in W_{d}$ in the network of small cubes. Then,
$d\left(c_{d},c_{d}^{\prime}\right)\leq\rho$, and, by the triangle inequality,
$d\left(c,W_{d}\cup\left\\{c_{d}\right\\}\right)\geq
d\left(c,W_{d}\right)-\rho$ for any cube $c$. We have:

  * •

for each $\gamma$-good cube $c$, because $\rho\leq\delta$,

$a\left(c\right)\leq\sigma\left(d\left(c,W_{d}\right)-R-\delta\right)\leq\sigma\left(d\left(c,W_{d}\cup\left\\{c_{d}\right\\}\right)-R\right).$

  * •

for each cube $c$ that is not $\gamma$-good, we have
$d\left(c,W_{d}\cup\left\\{c_{d}\right\\}\right)\geq R\geq R_{\rho}+L$ due to
$W_{d}\cup\left\\{c_{d}\right\\}\subseteq W$. But then, $a\left(c\right)\leq
1=\sigma\left(L\right)=\sigma\left(d\left(c,W_{d}\cup\left\\{c_{d}\right\\}\right)-R\right)$.

It follows that equilibrium $a$ is
$\left(W_{d}\cup\left\\{c_{d}\right\\},\gamma,R_{\rho}\right)$-dominated by
$\sigma$. But this is a contradiction with the choice of $W_{d}$ as a maximal
set.

Therefore, $W_{d}=W$, $a$ is $\left(W,\gamma,R_{\rho}\right)$-dominated by
$\sigma$, and for each $c\in W$,

$a\left(c\right)\leq\sigma\left(d\left(c,W\right)-R\right)+\rho=\sigma\left(-R\right)+\rho\leq
a^{*}+\frac{1}{4}\eta.$

Hence

$\displaystyle\text{Av}\left(a\right)$ $\displaystyle=\frac{1}{M^{2}}\sum
a_{i}=a^{*}+\frac{1}{\left|\mathcal{G}^{b}\right|}\sum_{c\in
W}\left(a\left(c\right)-a^{*}\right)+\frac{\left|I_{M}\backslash\bigcup
W\right|}{M^{2}}\sum_{i\notin\bigcup W}\left(a_{i}-a^{*}\right)$
$\displaystyle\leq a^{*}+\frac{1}{4}\eta+\gamma\leq x^{*}+\eta.$

Because the probability that $\left(\gamma,R\right)$-good set of small cubes
exists is at least $1-\gamma\geq 1-\eta$, the above inequality demonstrates
our claim.

##  Appendix E Proof of Theorem 4

###  E.1. Proof overview

We formally describe the best response dynamics: initial profile and the
updating process. Next, we compute capacity-type bounds on the dynamics, i.e.,
calculations (9) from the main body of the paper. We show that the reminder
terms are small. We use this to show that the average payoffs at the end of
the dynamics cannot be significantly different from $x^{*}$ and conclude the
proof of the theorem.

###  E.2. Initial profile

In this part of the Appendix, we define the initial profile for the dynamics
and its properties. Let $x^{*}$ be the RU-dominant outcome. For each relation
$r\in\left\\{=,<,>\right\\}$, let
$E_{r}=\left\\{\varepsilon_{i}:u\left(0,x^{*},\varepsilon{}_{i}\right)\text{
}r\text{ }u\left(1,x^{*},\varepsilon{}_{i}\right)\right\\}$. Then, $E_{=}$ is
the set of payoff shocks that make player indifferent if exactly fraction
$x^{*}$of their neighbors plays action $1$. Then, because $x^{*}$ is an RU-
dominant outcome, $F\left(E_{<}\right)\leq x^{*}\leq
F\left(E_{<}\right)+F\left(E_{=}\right)$. If $F\left(E_{=}\right)\neq 0$,
define
$p=\frac{F\left(E_{<}\right)+F\left(E_{=}\right)-x^{*}}{F\left(E_{=}\right)}$.
For each player $i$, let $Y_{i}$ be the binomial i.i.d. variable equal to 1
with probability $p$ and equal to 0 otherwise.

Define an initial strategy profile as a function of the payoff shocks:

$a_{i}^{0}=\begin{cases}BR_{i}\left(a_{-i};\varepsilon_{i}\right)&\text{if
}\left|BR_{i}\left(a_{-i};\varepsilon_{i}\right)\right|=1\\\
Y_{i}&\text{otherwise.}\end{cases}$ (20)

For each player $i$, let $\beta_{i}^{0}=\frac{1}{g_{i}}\sum g_{ij}a_{j}^{0}$
be the fraction of neighbors of agent $i$ who play action 1 under profile
$a_{i}^{0}$. The next result derives a probabilistic bound on the average
distance of neighborhood behaviors from the RU-dominant outcome.

######  Lemma 26.

For each $\eta>0$, there exists $d>0$ such that if $d\left(g\right)\leq d$,
then

$\operatorname{\mathbb{P}}\left(\sum
g_{i}\left|\beta_{i}^{0}-x^{*}\right|>\eta\left(\sum
g_{i}\right)\right)<\eta.$

###### Proof.

Variables $a_{j}^{0}$ are independent of each other and
$\operatorname{\mathbb{E}}a_{j}^{0}=x^{*}$. Hence, for each $i$,

$\operatorname{\mathbb{E}}\left(\beta_{i}^{0}-x^{*}\right)^{2}=\sum_{j}\frac{g_{ij}^{2}}{g_{i}^{2}}\operatorname{\mathbb{E}}\left(a_{j}^{0}-x^{*}\right)^{2}\leq\sum_{j}d\left(g\right)\frac{g_{ij}}{g_{i}}=d\left(g\right).$

By the Cauchy-Schwartz inequality, we get
$\operatorname{\mathbb{E}}\left|\beta_{i}^{0}-x^{*}\right|\leq
2\sqrt{d\left(g\right)}.$ Let $d\left(g\right)\leq d=\frac{1}{4}\eta^{4}$.
Then, by the Markov’s equality, for each $\eta$,

$\operatorname{\mathbb{P}}\left(\sum
g_{i}\left|\beta_{i}^{0}-x^{*}\right|>\eta\left(\sum
g_{i}\right)\right)\leq\frac{\operatorname{\mathbb{E}}\left(\sum
g_{i}\left|\beta_{i}^{0}-x^{*}\right|\right)}{\eta\left(\sum
g_{i}\right)}\leq\frac{2\sqrt{d\left(g\right)}}{\eta}\leq\eta.$

∎

###  E.3. Best response process

In this subsection, we formally define best response dynamics: starting from
the initial profile $a^{0}$, agents who play 0 but have 1 as a best response
revise their actions to 1, in an arbitrary (but fixed) order. Assume that all
players are labeled with numbers $i\in\left\\{1,...,N\right\\}$. For all
$t\geq 0$, and for each $i$, let

$\displaystyle\beta_{i}^{t}$ $\displaystyle=\frac{1}{g_{i}}\sum
g_{ij}a_{j}^{t},$ (21) $\displaystyle p_{i}^{t}$
$\displaystyle=P\left(\beta_{i}^{t}\right),$ $\displaystyle i_{t}$
$\displaystyle=\min\left\\{i:a_{i}^{t}=0\text{ and
}u\left(1,\beta_{i}^{t},\varepsilon{}_{i}\right)\geq
u\left(0,\beta_{i}^{t},\varepsilon{}_{i}\right)\right\\},$ $\displaystyle
a_{i}^{t+1}$ $\displaystyle=\begin{cases}1&\text{if }i=i_{t}\\\
a_{i}^{t}&\text{otherwise}.\end{cases}$

We refer to $p_{i}^{t}$ as the expected action of agent $i$ in period $t$.
Because at most one player changes actions at each step, we have
$\left|\beta_{i}^{t}-\beta_{i}^{t+1}\right|\leq d\left(g\right)$ for each $i$.
The stochastic process $\left(a^{t},\beta^{t},p^{t}\right)_{t}$ depends on the
realization of payoff shocks $\varepsilon$.

If the set in the third line is empty, the process stops. Because there are
finitely many players, the dynamics must stop in a finite time. We denote the
final outcome of the process as
$\left(a_{i}^{U},\beta_{i}^{U},p_{i}^{U}\right)$.

###  E.4. Main step

For each profile of expected actions $p$, define the functional

$\mathcal{F}\left(p\right)=\frac{1}{2}\sum_{i,j}g_{ij}\left(p_{i}-p_{j}\right)^{2}.$

Clearly, $\mathcal{F}\left(p^{t}\right)\geq 0$ for each $t$. Also, define
function

$L\left(x\right)=\intop_{x^{*}}^{x}\left(P^{-1}\left(y\right)-y\right)dy.$

Because $x^{*}$ is RU-dominant, it is the unique minimizer of
$L\left(x\right)$. Hence $L\left(x^{*}\right)=0$ and $L\left(x\right)>0$ for
each $x\neq x^{*}$.

The next lemma fills calculations behind formula (9) in the main body of the
paper.

######  Lemma 27.

For each $t$,

$\displaystyle 2\sum_{i}g_{i}L\left(p_{i}^{T+1}\right)\leq$
$\displaystyle\mathcal{F}\left(p^{0}\right)+A+2\sum_{i}g_{i}\left|\beta_{i}^{0}-x^{*}\right|+2d\left(g\right)\sum
g_{i},$ (22)

where $A$ is defined as

$\displaystyle A=$ $\displaystyle\sum_{t\leq
T}\sum_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{j}g_{ij}\sum_{s=t,t+1}\left(a_{j}^{s}-p_{j}^{s}\right).$

###### Proof.

Observe that for each $t$,

$\displaystyle\mathcal{F}\left(p^{t+1}\right)-\mathcal{F}\left(p^{t}\right)$
$\displaystyle=$
$\displaystyle\sum_{i}g_{i}\left(p_{i}^{t+1}\right)^{2}-\sum_{i}g_{i}\left(p_{i}^{t}\right)^{2}-\sum_{i,j}g_{ij}\left(p_{i}^{t+1}p_{j}^{t+1}-p_{i}^{t}p_{j}^{t}\right)$
$\displaystyle=$
$\displaystyle\sum_{i}g_{i}\left(p_{i}^{t+1}\right)^{2}-\sum_{i}g_{i}\left(p_{i}^{t}\right)^{2}-\sum_{i,j}g_{ij}\left(\left(p_{i}^{t+1}-p_{i}^{t}\right)p_{j}^{t+1}+p_{i}^{t}\left(p_{j}^{t+1}-p_{j}^{t}\right)\right)$
$\displaystyle=$
$\displaystyle\sum_{i}g_{i}\left(p_{i}^{t+1}\right)^{2}-\sum_{i}g_{i}\left(p_{i}^{t}\right)^{2}-\sum_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{j}g_{ij}\sum_{s=t,t+1}p_{j}^{s}$
$\displaystyle=$
$\displaystyle\sum_{i}g_{i}\left(p_{i}^{t+1}\right)^{2}-\sum_{i}g_{i}\left(p_{i}^{t}\right)^{2}-\sum_{i}g_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{s=t,t+1}\beta_{i}^{s}+\sum_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{j}g_{ij}\sum_{s=t,t+1}\left(a_{j}^{s}-p_{j}^{s}\right),$

where, in the last line, we used $g_{i}\beta_{i}^{s}=\sum_{j}g_{ij}a_{j}^{s}$.
Summing up across $t\leq T$, we obtain

$\displaystyle\mathcal{F}\left(p^{T+1}\right)-\mathcal{F}\left(p^{0}\right)=\sum_{t\leq
T}\left(\mathcal{F}\left(p^{t+1}\right)-\mathcal{F}\left(p^{t}\right)\right)$
$\displaystyle=$
$\displaystyle\sum_{i}g_{i}\left(p_{i}^{T+1}\right)^{2}-\sum_{i}g_{i}\left(p_{i}^{0}\right)^{2}-\sum_{t\leq
T}\sum_{i}g_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{s=t,t+1}\beta_{i}^{s}+A$
$\displaystyle=$ $\displaystyle
A+\sum_{i}g_{i}\left[\left(p_{i}^{T+1}\right)^{2}-\left(p_{i}^{0}\right)^{2}-2\intop_{p_{i}^{0}}^{p_{i}^{T+1}}P^{-1}\left(y\right)dy\right]$
$\displaystyle+\sum_{t\leq
T}\left[2\intop_{p_{i}^{t}}^{p_{i}^{t+1}}P^{-1}\left(y\right)dy-\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{s=t,t+1}\beta_{i}^{s}\right].$

The second term of the above is equal to

$\displaystyle\sum_{i}g_{i}\left[\left(p_{i}^{T+1}\right)^{2}-\left(p_{i}^{0}\right)^{2}-2\intop_{p_{i}^{0}}^{p_{i}^{T+1}}P^{-1}\left(y\right)dy\right]$
$\displaystyle=$ $\displaystyle
2\sum_{i}g_{i}\left[\intop_{p_{i}^{0}}^{p_{i}^{T+1}}ydy-\intop_{p_{i}^{0}}^{p_{i}^{T+1}}P^{-1}\left(y\right)dy\right]=2\sum_{i}g_{i}\left(L\left(p_{i}^{0}\right)-L\left(p_{i}^{T+1}\right)\right).$

Notice that $L\left(x^{*}\right)=L\left(P\left(x^{*}\right)\right)=0$ and
$L\left(P\left(\beta_{i}^{0}\right)\right)$ is Lipschitz with constant 1.
Hence the above is no larger than

$\leq-2\sum_{i}g_{i}L\left(p_{i}^{T+1}\right)+\sum
g_{i}\left|\beta_{i}^{0}-x^{*}\right|.$

Recall that $\sup_{t\leq T}\left(\beta_{i}^{t+1}-\beta_{i}^{t}\right)\leq
d\left(g\right)$. By definition of the Lebesgue integral,

$\displaystyle\sum_{t\leq T}\beta_{i}^{t}\lambda\left(y:\beta_{i}^{t}\leq
P^{-1}\left(y\right)<\beta_{i}^{t+1}\right)$
$\displaystyle\leq\intop_{p_{i}^{0}}^{p_{i}^{T+1}}P^{-1}\left(y\right)dy$
$\displaystyle\leq\sum_{t\leq
T}\left(\beta_{i}^{t}+d\left(g\right)\right)\lambda\left(y:\beta_{i}^{t}\leq
P^{-1}\left(y\right)<\beta_{i}^{t+1}\right),$

where $\lambda$ is the Lebesgue measure on the interval $\left[0,1\right]$.
The definition of inverse function $P^{-1}$ as well as
$p_{i}^{t}=P\left(\beta_{i}^{t}\right)$ for each $t$ imply that

$\lambda\left(y:\beta_{i}^{t}\leq
P^{-1}\left(y\right)<\beta_{i}^{t+1}\right)=p_{i}^{t+1}-p_{i}^{t}.$

Hence

$\sum_{i}g_{i}\sum_{t\leq
T}\left[2\intop_{p_{i}^{t}}^{p_{i}^{t+1}}P^{-1}\left(y\right)dy-\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{s=t,t+1}\beta_{i}^{s}\right]\leq
2d\left(g\right)\sum g_{i}.$

The result follows from putting the estimates together and the fact that
$\mathcal{F}\left(p_{i}^{T+1}\right)\geq 0$. ∎

###  E.5. Estimates

In this section, we provide estimates of the terms on the right-hand side of
(22).

######  Lemma 28.

For each $\eta>0$, there exists $d_{\eta}^{F}>0$ such that, if
$d\left(g\right)\leq d_{\eta}^{F}$, then

$\operatorname{\mathbb{P}}\left(\mathcal{F}\left(p^{0}\right)>\eta\left(\sum
g_{i}\right)\right)<\eta.$

###### Proof.

Note that

$\mathcal{F}\left(p^{0}\right)\leq\sum_{i}g_{i}\left(p_{i}-x^{*}\right)^{2}\leq\sum_{i}g_{i}\delta\left(\beta_{i}^{0}\right),$

where $\delta\left(x\right)=\left(P\left(x\right)-x^{*}\right)^{2}$. Note that
$\delta\left(x^{*}\right)=0$. Choose $\xi>0$ such that
$\delta\left(\sqrt{\xi}\right)+\sqrt{\xi}<\frac{1}{2}\eta$. Let $d<\eta$ be
small enough so that Lemma 26 holds for $\xi$. Then,

$\operatorname{\mathbb{P}}\left(\sum_{i:\beta_{i}^{0}\geq\sqrt{\xi}}g_{i}>\sqrt{\xi}\sum
g_{i}\right)\leq\xi,$

and, if the event in the brackets does not hold, we have

$\sum_{i}g_{i}\delta\left(\beta_{i}^{0}\right)\leq\sum_{i}g_{i}\left(\delta\left(\sqrt{\xi}\right)+\sqrt{\xi}\right)\leq\eta\left(\sum_{i}g_{i}\right).$

∎

To gain estimates on term $A$, we need a preliminary lemma:

######  Lemma 29.

For each $j$ and $s$,

$\operatorname{\mathbb{E}}\left(a_{j}^{s}-\max\left(x^{*},p_{j}^{s}\right)|\varepsilon{}_{-j}\right)\leq
0.$

###### Proof.

Fix player $j$. The stochastic process
$\left(a^{t},\beta^{t},p^{t}\right)_{t}$ can be defined on the probability
space $\Omega=E^{N}$ composed of the realizations of the payoff shock for each
individual. Consider an auxiliary stochastic processes $\left(a^{\prime
t},\beta^{\prime t},p^{\prime t}\right)_{t}$ defined on the same probability
space with the same equations (20)-(21) as the original process, but with
setting $a_{j}^{\prime t}\equiv a_{j}^{0}$ for each $t$. Additionally, define

$a_{j}^{*t+1}=1\text{ iff }u\left(1,\max\left(x^{*},\beta_{j}^{\prime
t}\right),\varepsilon{}_{j}\right)\geq
u\left(0,\max\left(x^{*},\beta_{j}^{\prime
t}\right),\varepsilon{}_{j}\right).$

So defined $a_{j}^{*t}$ depends on $\varepsilon_{-j}$ only through process
$\beta^{\prime}$. Hence, for each $\varepsilon_{-j}$,

$\displaystyle\operatorname{\mathbb{P}}\left(a_{j}^{*t+1}=1|\varepsilon{}_{-j}\right)$
$\displaystyle=\operatorname{\mathbb{P}}\left(u\left(1,\max\left(x^{*},\beta_{j}^{\prime
t}\right),\varepsilon_{j}\right)\geq
u\left(0,\max\left(x^{*},\beta_{j}^{\prime
t}\right),\varepsilon_{j}\right)|\varepsilon{}_{-j}\right)$
$\displaystyle=P\left(\max\left(x^{*},\beta_{j}^{\prime t}\right)\right).$

Notice that $a_{j}^{*t}\geq a_{j}^{t}$ for each $t$. Indeed, let
$t_{0}=\inf\left\\{t:a_{j}^{t}=1\right\\}$ and equal $\infty$ if the set is
empty. Then, $\beta_{i}^{t}=\beta_{i}^{\prime t}$ for each $i$ and $t<t_{0}$ .
Moreover, $a_{j}^{t_{0}}=1$ implies
$u\left(1,\beta_{j}^{t_{0}-1},\varepsilon{}_{j}\right)\geq
u\left(0,\beta_{j}^{t_{0}-1},\varepsilon{}_{j}\right)$ , which implies that
$a_{j}^{*t_{0}}=1$.

Further, payoff complementarities imply that, for each $s$, $\beta^{\prime
s}\leq\beta^{s}$, and hence $p^{\prime s}\leq p^{s}$. Additionally, $p^{\prime
s-1}\leq p^{\prime s}$. Thus,

$\displaystyle\operatorname{\mathbb{E}}\left(a_{j}^{s}-\max\left(x^{*},p_{j}^{s}\right)|\varepsilon_{-j}\right)$
$\displaystyle=\operatorname{\mathbb{P}}\left(a_{j}^{s}=1|\varepsilon{}_{-j}\right)-\max\left(x^{*},p_{j}^{\prime
s}\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}\left(a_{j}^{*s}=1|\varepsilon{}_{-j}\right)-\max\left(x^{*},p_{j}^{\prime
s}\right)$ $\displaystyle=P\left(\max\left(x^{*},\beta_{j}^{\prime
s-1}\right)\right)-\max\left(x^{*},p_{j}^{\prime s}\right)$
$\displaystyle=\max\left(x^{*},p_{j}^{\prime
s-1}\right)-\max\left(x^{*},p_{j}^{\prime s}\right)\leq 0,$

where the first equality is due to the fact that $p_{j}^{\prime s-1}$ and
$\beta_{j}^{\prime s-1}$ are measurable wrt. $\varepsilon{}_{-i}$. ∎

######  Lemma 30.

For each $\eta>0$, there exists $d_{\eta}>0$ such that, if
$d\left(g\right)\leq d_{\eta}^{1}$, then

$\operatorname{\mathbb{P}}\left(\frac{1}{g_{i}}\sum
g_{ij}\left(a_{j}^{s}-\max\left(x^{*},p_{j}^{s}\right)\right)\geq\eta\right)\leq\eta.$

###### Proof.

By Lemma 29, finite stochastic process
$X_{j}=\frac{1}{g_{i}}\sum_{j^{\prime}\leq
j}g_{ij^{\prime}}a_{j^{\prime}}^{s}$ is a supermartingale. Take
$d_{\eta}=-\frac{\eta}{\ln\eta}$. Then, the Azuma-Hoeffding’s Inequality
implies that

$\operatorname{\mathbb{P}}\left(\frac{1}{g_{i}}\sum
g_{ij}a_{j}^{s}-p_{j}^{s}\geq\eta\right)\leq\exp\left(-\frac{\eta}{\sum\frac{g_{ij}^{2}}{g_{i}^{2}}}\right)\leq\exp\left(-\frac{1}{d\left(g\right)}\eta\right)\leq\exp\left(\text{ln}\eta\right)=\eta.$

∎

######  Lemma 31.

For each $\eta>0$, there exists $d_{\eta}^{A}>0$ such that if
$d\left(g\right)\leq d_{\eta}^{A}$, then for each $i$ and $s$,

$\operatorname{\mathbb{P}}\left(A\geq\eta\sum_{i}g_{i}\right)\leq\eta.$

###### Proof.

Because $p_{i}^{t+1}>p_{i}^{t}$ for each $i$,

$\displaystyle A=$ $\displaystyle\sum_{t\leq
T}\sum_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{j}g_{ij}\sum_{s=t,t+1}\left(a_{j}^{s}-\max\left(x^{*},p_{j}^{s}\right)\right)$
$\displaystyle+\sum_{t\leq
T}\sum_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{j}g_{ij}\sum_{s=t,t+1}\left(\max\left(x^{*},p_{j}^{s}\right)-p_{j}^{s}\right)$
$\displaystyle\leq$ $\displaystyle\sum_{t\leq
T}\sum_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{j}g_{ij}\sum_{s=t,t+1}\left(a_{j}^{s}-\max\left(x^{*},p_{j}^{s}\right)\right)+2\sum_{j}g_{j}\left|p_{j}^{0}-x^{*}\right|$
$\displaystyle=$ $\displaystyle A_{1}+A_{2}.$

We are going to bound each of the two terms separately.

Let $d_{\eta}^{2}$ be the constant from Lemma 31. Then, if
$d\left(g\right)\leq d_{\eta}^{A1}=d_{\frac{1}{8}\sqrt{\eta}}^{2}$,

$\operatorname{\mathbb{E}}\left(\sum_{t\leq
T}\sum_{i}\left(p_{i}^{t+1}-p_{i}^{t}\right)\sum_{j}g_{ij}\sum_{s=t,t+1}\left(a_{j}^{s}-\max\left(x^{*},p_{j}^{s}\right)\right)\right)\leq\frac{1}{4}\sqrt{\eta}\sum_{i}g_{i}.$

By Markov’s inequality,

$\operatorname{\mathbb{P}}\left(A_{1}\geq\frac{1}{2}\eta\sum
g_{i}\right)\leq\frac{\frac{1}{4}\sqrt{\eta}\sum_{i}g_{i}}{\frac{1}{2}\eta\sum
g_{i}}\leq\frac{1}{2}\eta.$

Take $\delta\left(x\right)=\left|P\left(x\right)-x^{*}\right|$. Note that
$\delta\left(x^{*}\right)=0$. Choose $\xi>0$ such that
$\max\left(\xi,4\left(\delta\left(\sqrt{\xi}\right)+\sqrt{\xi}\right)\right)<\frac{1}{2}\eta$.
Let $d_{\eta}^{A2}<\eta$ be sufficiently small so that Lemma 26 holds for
$\xi$. Then,

$\operatorname{\mathbb{P}}\left(\sum_{i:\beta_{i}^{0}\geq\sqrt{\xi}}g_{i}>\sqrt{\xi}\sum
g_{i}\right)\leq\xi,$

and, if the event in the brackets does not hold, we have

$2\sum_{j}g_{j}\left|P\left(\beta_{j}^{0}\right)-x^{*}\right|\leq
2\left(\delta\left(\sqrt{\xi}\right)+\sqrt{\xi}\right)\sum_{i}g_{i}\leq\frac{1}{2}\eta\left(\sum_{i}g_{i}\right).$

Take $d_{\eta}^{A}=\min\left(d_{\eta}^{A1},d_{\eta}^{A2}\right)$. Then,

$\operatorname{\mathbb{P}}\left(A\geq\eta\sum_{i}g_{i}\right)\leq\operatorname{\mathbb{P}}\left(A_{1}\geq\frac{1}{2}\eta\sum_{i}g_{i}\right)+\operatorname{\mathbb{P}}\left(A_{2}\geq\frac{1}{2}\eta\sum_{i}g_{i}\right)\geq\eta.$

∎

###  E.6. Average payoffs at the end of dynamics

We show that the average payoffs when the upper best response dynamics stop
are not much higher than $x^{*}$.

######  Lemma 32.

For each $\eta>0$, there exists $d_{\eta}^{U}>0$ such that, if
$d\left(g\right)\leq d_{\eta}^{U}$, then

$\operatorname{\mathbb{P}}\left(\text{Av}\left(a^{U}\right)\geq\left(\eta+x^{*}\right)\sum_{i}g_{i}\right)\leq\eta.$

###### Proof.

By definition, $x^{*}$ is the unique maximizer of $L\left(x\right)$. Fix
$\eta>0$ and find $\xi>0$ such that $\sqrt{\xi}\leq\eta$ and if
$L\left(x\right)\leq\sqrt{\xi}$, then $x\leq x^{*}+\frac{1}{2}\eta$.

Let$\left(a^{t},\beta^{t},p^{t}\right)_{t}$ be the upper best response
dynamics defined in Section E.3. By Lemmas 22, 28, and 31, if $d\leq
d_{\xi}^{U}=\max\left(d_{\xi}^{F},d_{\xi}^{A}\right)$, then

$\sum_{i}g_{i}L\left(p_{i}^{U}\right)\leq\xi\sum_{i}g_{i}$

with a probability of at least $1-\xi$. It follows that
$\sum_{i:L\left(p_{i}^{U}\right)\geq\sqrt{\xi}}g_{i}\leq\sqrt{\xi},$ which
implies that $\sum_{i:\beta_{i}^{U}\geq
x^{*}+\frac{1}{2}\eta}g_{i}\leq\sqrt{\xi}$. Hence,

$\sum g_{i}\beta_{i}^{U}\leq\sum_{i:\beta_{i}^{U}\leq
x^{*}+\frac{1}{2}\eta}g_{i}\left(x^{*}+\frac{1}{2}\eta\right)+\sqrt{\xi}\sum
g_{i}\leq\left(x^{*}+\eta\right)\sum_{i}g_{i}.$

Finally, notice that

$\text{Av}\left(a^{U}\right)=\sum_{i}g_{i}a_{i}^{U}=\sum_{i}\sum_{j}g_{ij}a_{i}^{U}=\sum_{i}\sum_{j}g_{ij}a_{i}^{U}=\sum_{i}g_{i}\beta_{i}^{U}.$

The result follows from the above inequality. ∎

###  E.7. Proof of Theorem 4

Lemma 32 shows that the best response dynamics, where players only revise
their actions upwards, stop with a profile $a^{U}$ with average payoffs close
to $x^{*}$. An analoguous result shows that a lower version of the best
response dynamics, initiated from the same profile $a^{0}$ and where players
only revise their actions downwards, stop with a profile $a^{L}$ with average
payoffs also close to $x^{*}.$

Due to payoff complementarities, the lower best response dynamics initiated
from profile $a^{U}$ will stop at equilibrium profile $a^{UL}$ that lies in
between $a^{U}$ and $a^{L}$. The latter implies that the average payoffs must
lie in between the average payoffs $\text{Av}\left(a^{U}\right)$ and
$\text{Av}\left(a^{L}\right)$. The claim follows.

###  E.8. Extension to unweighted average

The argument remains identical except for the following modification of Lemma
32: For each $\eta>0$ and $w<\infty$, there exists $d_{\eta}^{U}>0$ such that,
if $d\left(g\right)\leq d_{\eta}^{U}$, and $w\left(g\right)\leq w$ then

$\operatorname{\mathbb{P}}\left(\text{Av}_{\text{unweighted}}\left(Ua^{0}\right)\geq\left(\eta+x^{*}\right)\right)\leq\eta.$

To see the above claim, recall that $a_{i}^{U}\geq a_{i}^{0}$ . Hence

$\displaystyle\text{Av}_{\text{unweighted}}\left(a^{U}\right)-\text{Av}_{\text{unweighted}}\left(a\right)$
$\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{i}\left(a_{i}^{U}-a_{i}^{0}\right)=\frac{1}{\min_{i}g_{i}}\frac{1}{N}\sum_{i}\left(\min_{j}g_{j}\right)\left(a_{i}^{U}-a_{i}^{0}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{\min_{i}g_{i}}\frac{1}{N}\sum_{i}g_{i}\left(a_{i}^{U}-a_{i}^{0}\right)\leq\frac{1}{\min_{i}g_{i}}\frac{\sum
g_{i}}{N}\frac{1}{\sum g_{i}}\sum_{i}g_{i}\left(a_{i}^{U}-a_{i}^{0}\right)$
$\displaystyle\leq$
$\displaystyle\frac{\max_{i}g_{i}}{\min_{i}g_{i}}\left(\text{Av}\left(Ua\right)-\text{Av}\left(a^{0}\right)\right)=w\left(g\right)\left(\text{Av}\left(Ua\right)-\text{Av}\left(a^{0}\right)\right).$

An application of Lemma 32 established the claim.

## References

  * [Blume(1993)] Blume, L. E. (1993). The statistical mechanics of strategic interaction. Games and economic behavior, 5 (3), 387–424, publisher: Elsevier.
  * [Bollobás et al.(2006)Bollobás, Riordan and Riordan] Bollobás, B., Riordan, O. and Riordan, O. (2006). Percolation. Cambridge University Press.
  * [Ellison(1993)] Ellison, G. (1993). Learning, local interaction, and coordination. Econometrica: Journal of the Econometric Society, pp. 1047–1071, publisher: JSTOR.
  * [Ellison(2000)] — (2000). Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution. The Review of Economic Studies, 67 (1), 17–45, publisher: Wiley-Blackwell.
  * [Harsanyi and Selten(1988)] Harsanyi, J. C. and Selten, R. (1988). A general theory of equilibrium selection in games. MIT Press Books, 1, publisher: The MIT Press.
  * [Jackson and Zenou(2015)] Jackson, M. O. and Zenou, Y. (2015). Games on networks. In Handbook of game theory with economic applications, vol. 4, Elsevier, pp. 95–163.
  * [Kandori et al.(1993)Kandori, Mailath and Rob] Kandori, M., Mailath, G. J. and Rob, R. (1993). Learning, mutation, and long run equilibria in games. Econometrica: Journal of the Econometric Society, pp. 29–56, publisher: JSTOR.
  * [Morris(2000)] Morris, S. (2000). Contagion. The Review of Economic Studies, 67 (1), 57–78, publisher: Wiley-Blackwell.
  * [Newton(2021)] Newton, J. (2021). Conventions under heterogeneous behavioural rules. The Review of Economic Studies, 88 (4), 2094–2118.
  * [Peski(2010)] Peski, M. (2010). Generalized risk-dominance and asymmetric dynamics. Journal of Economic Theory, 145 (1), 216–248, publisher: Elsevier.
  * [Vershynin(2018)] Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge: Cambridge University Press.
  * [Young(1993)] Young, H. P. (1993). The evolution of conventions. Econometrica: Journal of the Econometric Society, pp. 57–84, publisher: JSTOR.