font=footnotesize capbtabboxtable[][0.9]

# A NOVEL SOFT-AIDED BIT-MARKING DECODER FOR PRODUCT CODES

Gabriele Liga1  Alireza Sheikh1  and Alex Alvarado1<EMAIL_ADDRESS>1Department
of Electrical Engineering, Eindhoven University of Technology, Eindhoven, The
Netherlands

###### Abstract

We introduce a novel soft-aided hard-decision decoder for product codes
adopting bit marking via updated reliabilities at each decoding iteration.
Gains up to 0.8 dB vs. standard iterative bounded distance decoding and up to
0.3 dB vs. our previously proposed bit-marking decoder are demonstrated.

###### keywords:

HARD DECISION DECODING, FORWARD-ERROR CORRECTION, PRODUCT CODES, BOUNDED
DISTANCE DECODING, SOFT-AIDED BIT MARKING, SCALED RELIABILITIES.

##  1 Introduction

As optical line rates are quickly shifting towards 400 Gbit/s and beyond,
implementing soft-decision forward-error correction (SD-FEC) decoders becomes
increasingly challenging due to their high decoding complexity and internal
data-flow. For this reason, lately, considerable attention has been devoted to
hard-decision FEC (HD-FEC) schemes whose decoding complexity and data-flow can
be order of magnitudes less than SD-FEC.

In the context of HD-FEC, product codes (PCs) Elias1954 (and generalisation
thereof, such as staircase codes Smith2012 ) offer at least at high coding
rates a very good compromise between complexity and performance. This is due
to the use of iterative algebraic decoding which is well known to be capacity-
approaching at high rates in a binary-symmetric channel. A product code
constructed on a $(n,k)$ component code is a set of square arrays of size
$n\times n$ where any row and column of each array is a valid codeword in the
component code. Typically, Bose-Chaudhuri-Hocquenghem (BCH) or Reed-Solomon
codes are used as a component code.

PCs based on BCH codes are typically decoded using iterative bounded distance
decoding (iBDD) which can lead to substantial coding gains. However, the main
performance limitation of BDD is due to so-called decoding _failures_ and
_miscorrections_. A decoding failure is declared when the received vector of
bits is not within the correction capability of the component code. A
miscorrection instead occurs when the received vector is succesfully decoded,
but it is mapped into a codeword different from the transmitted one.

A number of new decoding strategies have recently been proposed to tackle both
failures and miscorrections, and thus, improve the performance of iBDD
decoders whilst preserving an iterative algebraic decoding structure Hager2017
; Sheikh2018ECOC ; Sheikh2019 ; Lei2018ISTC ; Sheikh2018ISTC ;
FougstedtOFC2018 . Except from Hager2017 , all these strategies somehow
require the use of soft information from the channel. For instance in
Sheikh2018ECOC ; Sheikh2019 , the channel bit reliabilities are updated at
each iteration based on the previous BDD output and are used to produce new
hard decisions for the next BDD decoding stage.

In our previous work Lei2018ISTC ; Lei2019arXiv , we showed how marking the
input bits using the log-likelihood ratios (LLRs) can effectively prevent
failures and miscorrections resulting in a significant improvement of the iBDD
performance. We referred to this approach as _soft-aided bit-marking_ (SABM).
SABM was first introduced in Lei2018ISTC for staircase codes, and later also
applied to PCs Lei2019arXiv .

In this contribution, we extend the SABM algorithm to include scaled
reliabilities (SRs) in the decoding process. Differently from Sheikh2018ECOC ;
Sheikh2019 , the SRs are used to update the bit-marking process at each
decoding iteration. The proposed design efficiently merges SABM and SRs to
optimise the decoding of PCs. By doing that, we achieve up to 0.8 dB gain
compared to standard iBDD and 0.3 dB compared to the previous implementation
of SABM.

##  2 Soft-aided bit marking decoder

The SABM algorithm was shown to be an effective way to mitigate failures and
miscorrections in iBDD Lei2019arXiv . The algorithm workflow is illustrated in
Fig. 1. In the standard BDD (top part of Fig. 1), the received codeword $r$ is
succesfully decoded if there exists a codeword $\hat{c}$ that differs by at
most $t$ positions from $r$, where $t$ is the correction power of the
component code. Alternatively, a failure is declared and the decoder simply
outputs $c^{\prime}=r$. A successful BDD decoding does not always guarantee
that the transmitted codeword is correctly recovered. If more than $t$ errors
are introduced by the channel, and $r$ is within $t$ positions from a codeword
$c^{\prime}\neq c$, the decoder will select $c^{\prime}$ as opposed to $c$,
resulting in a so called _miscorrection_. Miscorrections often result in the
decoder adding more errors than the ones introduced by the channel, thus
leading to a deterioration of the iBDD performance.

SABM tackles both failures and miscorrections via a twofold action:
_miscorrection detection_ and _bit flipping_. This approach is enabled by the
use of _soft quantities_ or _reliabilities_ extracted from the channel. In
SABM, LLRs are used as a bit reliability measure. By setting a threshold in
the LLR magnitude, bits are marked as highly reliable bits (HRBs) when they
fall above such a threshold. Alternatively, they are labelled as highly
unreliable bits. Two rules are adopted to prevent a miscorrection: i) the BDD
decoder can never flip a bit from a previously succesfully decoded codeword;
ii) HRBs can never be flipped. When either a failure occurs or a miscorrection
is detected (red area in Fig. 1) a new decoding attempt is performed after
_bit flipping_.

Figure 1: Workflow of the SABM algorithm presented in Lei2018ISTC .

Bit flipping is used to facilitate the success of an additional decoding
attempt. The LLRs are ordered based on their magnitude and the least reliable
bit is flipped in the case of failure. In the case of a detected
miscorrection, the least $d_{min}-t-w_{H}(e)$ bits are flipped, where
$d_{min}$ and $w_{H}(e)$ are the minimum Hamming distance of the component
code and the Hamming weight of the error vector $e$, respectively. If after an
additional decoding attempt on the flipped received vector $r^{\prime}$ a
further failure or miscorrection is detected, the output is set to
$c^{\prime}=r$ and passed to the next BDD decoding stage. This process is
performed for a few iterations. For PCs the number of these iterations is
lower than the number of total iBDD iterations and can be optimised in terms
of post-FEC bit-error rate (BER) performance (see Sec. 4).

##  3 SABM with scaled reliabilities

In SABM the bit marking occurs only once (based on the channel LLRs) and is
then used over a certain number of iterations. This approach is, however, sub-
optimal as the marking mask loses its validity after bits are updated at every
iteration by the BDD decoders. This problem can be solved by re-marking the
output bits at each BDD iteration by defining a reliability measure for the
outbound BDD decisions. The SR measure proposed in Sheikh2018ECOC ; Sheikh2019
linearly combines the BDD decisions with the channels LLRs. We call this new
approach SABM-SR.

The SABM-SR algorithm is illustrated in Fig. 2. The BDD output can provide at
each iteration quantised information by assigning values -1 and +1 to
successfully decoded bits 0 and 1, respectively. When a failure occurs the BDD
output will instead be identically set to 0. The green blocks in Fig. 2 show
how the reliabilities are updated at each iteration for both row and column
decoding. Let $u^{\text{r}}_{i,j}\in\\{-1,0,+1\\}$ be the quantised
reliability information provided by the row BDD decoder for the bit in row $i$
and column $j$. The SR after row decoding at each iteration is defined as
Sheikh2019

$\phi_{i,j}=w^{\text{r}}u^{\text{r}}_{i,j}+l_{i,j}\quad\forall\;i,j=1,2,...n$
(1)

where $w^{\text{r}}\in\mathbb{R}^{+}$ are optimised weights and $l_{i,j}$ are
the LLRs.

As illustrated in Fig. 2 (yellow blocks), the SRs $\phi_{i,j}$ can be used to
update the SABM marking stage. The bit-marking block takes as an input the SRs
from the previous (column) decoding iteration and yields a new set of marked
bits $\psi^{\text{r}}_{i,j}$. The new marked bits are then passed to the SABM
row decoder which produces a block of output bits $\hat{b}_{i,j}$ and a
corresponding block $u^{\text{r}}_{i,j}$. This information is used to update
again the reliabilities $\phi_{i,j}$ according to (1). A marking update is
then performed via the $\phi_{i,j}$ for the SABM column decoder.

SABM row decoderSABM column decoderBit MarkingBit
Marking$\times$$+$$\scaleto{u^{\text{r}}_{i,j}}{8pt}$$\scaleto{\psi^{\text{r}}_{i,j}}{8pt}$$\scaleto{\psi^{\text{c}}_{i,j}}{8pt}$$\scaleto{l_{i,j}}{8pt}$$\scaleto{w^{\text{r}}}{5pt}$$\scaleto{\hat{b}_{i,j}}{8pt}$$\scaleto{\phi_{i,j}}{8pt}$$\times$$+$$\scaleto{u^{\text{c}}_{i,j}}{8pt}$$\scaleto{l_{i,j}}{8pt}$$\scaleto{w^{\text{c}}}{5pt}$

Figure 2: Schematic diagram of one iteration of the proposed SABM-SR
algorithm.

Differently from Sheikh2018ECOC ; Sheikh2019 , here the reliability
information at each iteration is used merely to re-mark the bits at the input
of the next BDD decoder, and the BDD output $\hat{b}_{i,j}$ is still used as
the input of the next BDD decoder.

##  4 Results and Discussion

The two decoders described in this paper were numerically assessed in an
additive white Gaussian noise channel with binary antipodal modulation (2PAM)
and noise power spectral density $N_{0}/2$. Ten decoding iterations were used
for all the implemented decoders. For SABM, and SABM-SR, the reliability
threshold and the number of iterations where miscorrection detection (and bit
flipping) is performed was optimised and set to 5 and 5 (out of 10)
iterations, respectively. The SR weights were numerically optimised and it was
found $w^{\text{r}}\approx w^{\text{c}}$. The optimised vector
$\boldsymbol{w}\triangleq[w_{1},w_{2},...,w_{N}]$, where $w_{k}$ is the SR
weight at iteration $k$ and $N$ is the number of marking iterations, was found
to be $\boldsymbol{w}=[3.42,3.87,4.08,4.27,4.49]$.

$3$$3.25$$3.5$$3.75$$4$$4.25$$4.5$$4.75$$5$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$0.6
dB2320 km0.3 dB0.5 dB1440 kmTPDideal iBDD$E_{b}/N_{0}$ [dB]Post-PC
BERiBDDSABMSABM-SR960 km1280014000152001656018000Optical reach [km] Figure 3:
BER vs. $E_{b}/N_{0}$ for the decoding schemes analysed and for a code rate
$R$=0.78.

Fig. 3 shows the post-PC bit-error rate (BER) as a function of $E_{b}/N_{0}$,
where $E_{b}$ is the energy per information bit. The component code is in this
case a BCH (7,2,1)111We use the common notation ($\nu$,$t$,$e$) for BCH codes,
where $\nu$ is the order of the extended Galois field and $e$ number of bits
of extension., yielding a PC rate $R=0.78$. Other than the decoding algorithms
described in Secs. 2, 3, the performance of an ideal (miscorrection-free) iBDD
(dash-dotted curve) and a _fully-fledged_ SD decoder such as the turbo product
decoder (TPD) based on the Chase-Pyndiah algorithm Pyndiah1998 , are also
shown as a reference.

Table 1: Optical system paramaters. Parameter Name | Value
---|---
Modulation Format | PM-QPSK
Symbol rate | 33 GBaud
Channel Spacing | 33 GHz
No. of Channels | 295
Roll-off factor | 0
Fibre Type | Standard single-mode fibre
Span Length | 80 km
EDFA noise figure | 4.5 dB

The SABM decoder (red curve) shows a 0.5 dB coding gain compared to iBDD (blue
line) at a BER of $10^{-7}$. SABM also outperforms ideal iBDD (dashed-dotted
black line), due to its capability to also mitigate failures. SABM-SR gains
0.3 dB over SABM and an overall 0.8 dB compared to iBDD. This substantial
coding gain comes at expense of some additional decoding complexity, due to
the SR calculation and the repeated marking operation. However, as noted in
Sheikh2019 and also illustrated in Fig. 2, the SRs are not passed between the
SABM decoding stages and can be calculated and stored in place, considerably
reducing the decoder data flow. The only messages passed to the decoders are a
mask of marked bits and the previous decoder output (hard bits). Finally, TPD
(dashed black line) gains 0.6 dB over SABM-SR. Thus, SABM-SR performance is
closer to an SD decoder than to conventional HD decoding for PCs (iBDD).

Fig. 3 also shows the performance in terms of achievable optical reach ($x$
axis at the top). In order to link $E_{b}/N_{0}$ to a given transmission
distance, a closed-form for the enhanced Gaussian noise model proposed in
Poggiolini2015 was used. For our analysis, we assumed a long-haul optical
transmission system (parameters in Table 1) using polarisation-multiplexed
quadrature phase-shift keying (PM-QPSK) and Erbium-doped fibre amplifiers
(EDFAs). SABM yields a 1440 km reach increase, whilst SABM-SR gains an
additional 960 km and an overall 2400 km compared to iBDD. Using an SD decoder
(TPD) increases the reach by 2320 km compared to SABM-SR.

$3.8$$4$$4.2$$4.4$$4.6$$4.8$$5$$5.2$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$0.45
dB1340 km0.23 dB640 km0.4 dB960 kmTPDideal iBDD$E_{b}/N_{0}$ [dB]Post-PC
BERiBDDSABMSABM-SR1080011520123201280013120Optical reach [km] Figure 4: BER
vs. $E_{b}/N_{0}$ for the decoding schemes analysed and for a code rate
$R$=0.87.

Fig. 4 shows the performance of a PC using a BCH (8,2,1) with rate $R=0.87$.
It can be observed that the gains are slightly reduced compared to Fig. 3, due
to the increased code rate. SABM (red line) gain over iBDD (blue line) is now
reduced to 0.4 dB, equivalent to a 960 km reach increase. SABM-SR gains 0.23
dB over SABM and 0.63 dB compared to iBDD, equivalent to a 640 km and 1600 km
reach extension, respectively. Despite being a _full_ SD decoder, TPD shows
_only_ a 0.45 dB improvement over SABM-SR, which translates to a 1340 km reach
increase.

##  5 Conclusions

We presented a novel soft-aided hard-decision decoder for product codes based
on the principle of marking bits using soft information from the channel.
Updating the bit marking at each iteration via scaled reliabilities yields up
to 0.3 dB gain (or 960 km reach increase) compared to the standard SABM
algorithm. SABM-SR outperforms iBDD by up to 0.8 dB (2400 km reach increase)
while preserving its core algebraic structure. We believe this new scheme is a
strong candidate for 400G and beyond optical transponders.

Acknowledgements: This work has received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No 757791). G. Liga also gratefully acknowledges
the NWO Visitors Travel Grant 040.11.659/6291.

## References

## References

  * [1] P. Elias: ‘Error-Free Coding’, Trans. IRE Professional Group on Information Theory, 1954, 4, (4), pp 29–37
  * [2] B. P. Smith, A. Farhood, A. Hunt, et al.: ‘Staircase Codes: FEC for 100 Gb/s OTN’, IEEE Journal of Lightwave Technology, 2012, 30, (1), pp 110–117
  * [3] C. Häger, and H. D. Pfister: ‘Approaching Miscorrection-Free Performance of Product Codes With Anchor Decoding’, IEEE Transactions on Communications, 2017, 66, (7), pp 2797–2808
  * [4] A. Sheikh, A. G. i Amat, and G. Liva: ‘Binary Message Passing Decoding of Product Codes Based on Generalized Minimum Distance Decoding’, 2019, available online: http://arxiv.org/abs/1901.02914
  * [5] Y. Lei, A. Alvarado, B. Chen, et al.: ‘Decoding Staircase Codes with Marked Bits,’ Proc. International Symposium on Turbo Codes and Iterative Information Processing (ISTC), Hong Kong, China, 2018
  * [6] A. Sheikh, A. G. i. Amat, G. Liva: ‘Iterative Bounded Distance Decoding of Product Codes with Scaled Reliability’, Proc. European Conference on Optical Communications, Rome, Italy, 2018
  * [7] A. Sheikh, A. G. i. Amat, G. Liva, et al.: ‘On Low-complexity Decoding of Product Codes for High-throughput Fiber Optic Systems’, Proc. IEEE 10th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), Hong Kong, China, 2018
  * [8] C. Fougstedt, A. Sheikh, A. Graell i Amat, et al.: ‘Energy-efficient soft-assisted product decoders’, Proc. Optical Fiber Communciations Conference and Exposition (OFC), San Diego, USA, 2019
  * [9] Y. Lei, B. Chen, G. Liga, et al.: ‘Improved Decoding of Staircase Codes: The Soft-aided Bit-marking (SABM) Algorithm’, 2019, available online: http://www.arxiv.org/abs/1902.01178
  * [10] R. M. Pyndiah: ‘Near–Optimum Decoding of Product Codes: Block Turbo Codes’, IEEE Transactions on Communications, 1998, 46, (8), 1003–1010
  * [11] P. Poggiolini, G. Bosco, A. Carena, et al.: ‘A Simple and Effective Closed-form GN Model Correction Formula Accounting for Signal Non-Gaussian Distribution’, Journal of Lightwave Technology, 2015, 33, (2), 459–473


11institutetext: Department of Computing
Imperial College London
11email: {dz819<EMAIL_ADDRESS>
# The Impact of Incomplete Information on Network Formation with Heterogeneous
Agents

D. Kai Zhang  0000-0001-5770-0903 Alexander Carver  0000-0003-3151-6563

###### Abstract

We propose an agent-based network formation model under uncertainty with the
objective of relaxing the common assumption of complete information, calling
attention to the role beliefs may play in segregation. We demonstrate that our
model is capable of generating a set of networks that encompasses those of a
complete information model. Further, we show that by allowing agents to be
biased toward each other based on observable attributes, our model is able to
generate homophilous equilibria with preferences that are indifferent to these
attributes. We accompany our theoretical results with a simulation-based
investigation of the relationship between beliefs and segregation and show
that biased beliefs are an important driver of segregation under incomplete
information.

###### Keywords:

Social Networks Segregation Incomplete Information Heterogeneous Agents.

##  1 Introduction

Frequently, members of the same group exhibit similar outward appearances – a
phenomenon referred to as homophily. This paper aims to provide an approach to
studying this feature of social networks under uncertainty. We specifically
build on an agent-based network formation model first proposed by Jackson and
Wolinsky (1996) [14].

A number of extensions have been made to study segregation from a network
formation perspective. These extensions have in common that agents belong to
different types, where a type denotes shared attributes. Further, agents may
exhibit heterogeneity in either benefits or costs when connecting to other
agents. Specifically, forming a link with someone of the same type is usually
assumed to either offer greater benefits or come at a lower cost than forming
a link when types differ. By way of illustration, these models imply that a
person finds it easier to form friendships with other people of the same
ethnicity. These models show that segregation equilibria exist when agents
exhibit even small preferences for homophily.

###  1.1 Our Contribution

The key shortcoming in most of the existing literature is the strong
assumption that agents have complete information about each other’s types or,
equivalently, utilities depend only on observable attributes. This paper
departs from this assumption by introducing a distinction between overt social
groups, which subsume all publicly observable attributes, and covert types,
denoting private attributes. Agents are assumed to prefer connecting to other
agents of the same type which, however, is ex-ante unobservable. Agents are
thus indifferent over observable attributes. Instead, agents use a heuristic
device and rely on social group memberships to gauge someone’s hidden type.
This, in turn, allows for “errors” in people’s judgement of each other’s
types.

We present a model designed to give us the ability to investigate if
segregation between social groups can simply occur when people are
sufficiently prejudiced, i.e., exhibit beliefs that are detached from the true
distribution of covert types. We introduce the concept not just of hidden
types, but also of agents’ beliefs to intuit these types from observable
attributes and form connections based on these beliefs.

Finally we implement various simulated experiments in order to provide
comparisons to complete information networks and incomplete information
networks with rational beliefs. We demonstrate that even mildly biased beliefs
are an important driver of segregation under incomplete information.

###  1.2 Related Literature

Since Schelling’s (1969, 1971) [25, 26] landmark segregation models, numerous
studies of homophily in heterogeneous networks have been undertaken in recent
years. Jackson and Xing (2014) [15] argue that homophily reflects how norms
could help members of a group predict each other’s behaviour and thus
facilitate cooperative play in coordination games. McPherson, Smith-Lovin and
Cook (2001) [22] show that having similar attributes is a strong predictor
that two individuals maintain social ties along a variety of dimensions.

Aits, Carver and Turrini (2019) [1] demonstrate how tolerance can result in
complex intra-group segregation. De Martí and Zenou (2017) [21] determine that
segregation can be the socially optimal outcome when agents are not
sufficiently exposed to each other’s groups as to reduce inter-group linking
costs. Centola, Gonzalez-Avella, Eguiluz and San Miguel (2007) [4] show how
homophily can lead to the formation of distinct cultural groups that persist
even when random shocks variously bring groups closer together. Within this
divergence, group membership can have profound effects on the individuals.
This has been examined, amongst others, in the context of migration and
assimilation decisions [2, 5, 24, 30], occupation and employment [9, 23, 31],
and even marriage [27].

However, to date, only a relatively small body of literature exists which has
investigated the role of incomplete information in networks. Jackson and Yariv
(2007) [16] investigate incomplete information pertaining to the structure of
the network. They present a model in which agents are uncertain over how well
connected other agents are. Since an agent’s payoffs depend in part on the
indirect connections gained through her direct connections, her actions will
be a response to her _beliefs_ of the structure of those connections.

De Martí and Zenou (2015) [20] assume that there is a shared state of the
world which determines the return individuals receive from expending private
effort to interact with each other. Since this state is further assumed to be
unknown, players use signals to partially infer the true state.

This type of model arguably forms the main stream within this literature and
generally focuses on network _games_. That is, the objective is to understand
better how games are played when the players are already connected in a
network in some fashion and, as such, these models differ significantly from
network _formation_ models.

The work of Song and van der Schaar (2015) [28] is a notable exception that
parallels the approach of this paper. They consider not only a network
formation model but also a heterogeneous agent setting in which agents have
incomplete information about each others’ types. Their model, however, assumes
that heterogeneity is expressed in benefits and that beliefs are shared across
agents.

Galeotti, Goyal and Kamphorst (2006) [7] note that heterogeneity in cost
shapes both the level of connectedness as well as the general structure of a
network, whereas heterogeneity in benefits appears to have much less of an
influence on the latter.

##  2 The Incomplete Information Model

###  2.1 Design

In order to allow for homophily to be the result rather than the entry point
of a model, we introduce the idea that agents belong to distinct _social
groups_ which share observable characteristics but also have a hidden _type_
which can be revealed by forming a link.

#### Agents

Let every agent $i\in N=\\{1,...,n\\}$ belong to one of $K$ social groups so
that $s_{i}=k\in K$ denotes $i$’s membership of group $k$. We define
$N^{k}\subset N$ to be the set of all agents from group $k$.

Let each agent also have a hidden type $t_{i}\in T$, where $T$ is the set of
all possible types. Agents are assumed to _memorise_ the types of all agents
whose type they learn by forming a link. Let the $n\times n$ matrix $M$
contain the memory of all agents, where $M_{ij}=1$ if agent $i$ knows the type
of agent $j$ and $M_{ij}=0$ otherwise.

#### Networks

To encompass the information present within the network, we represent networks
as $(N,M,g)$, where $g$ is an undirected graph.

#### Dynamic Network Formation

We follow Jackson and Watts (2002) [13] and explicitly define network
formation as a stochastic dynamic process in which at every time step a random
pair $\\{i,j\\}$ is selected with uniform probability. This pair is evaluated
for pairwise stability and, should their relationship be unstable, a link is
then either added or removed.

#### Actual Utility

Agents are assumed to receive utility from their location within the network
as follows:

$u_{i}(g)=\sum_{j\neq i}\delta^{d_{ij}}-\sum_{j:\ ij\ \in\ g}c_{ij}$ (1)

where we assume that benefits decay with the geodesic distance, $d_{ij}$,
given the decay factor, $0<\delta<1$. Further, we assume the cost of a direct
connection, $c_{ij}$, depends on the agents’ types, specifically:

$c_{ij}=c(t_{i},t_{j})$ (2)

#### Expected Utility

For prospective links, agents are required to consider _expected utility_ when
contemplating a link with someone they do not yet know.

This paper contributes a _specific_ formulation for the expected utility.
First note that since agents have met everyone they are presently in a direct
connection with, the uncertain component is expressed only when the
incremental change from a link _addition_ is considered. The utility an agent
expects to enjoy if the link is added can then be expressed as:

$\begin{split}E_{i}[u_{i}(g+ij)]&=[\delta-\sum_{t\in T}\pi_{i}(t|s_{j})\
c(t_{i},t)]\\\ &+[\sum_{k\notin\\{i,j\\}}\delta^{d_{ik}}-\sum_{k:\ ik\ \in\
g\setminus ij}c_{ik}]\end{split}$ (3)

The first bracketed term on the right-hand side corresponds to the benefit of
becoming neighbours with $j$ less the expected cost of doing so. The expected
cost is an average of the costs to connect with each type $t\in T$ weighted by
agent $i$’s belief – $\pi_{i}(t|s_{j})$ – that agent $j$ is of type $t$ given
their social group. The second bracketed term describes the net utility from
the remainder of the network defined by $g+ij$.

Note that we can thus decompose the above expression into (i) the expected
incremental change in utility from adding a link to agent $j$,
$E_{i}[u_{ij}]$, and (ii) the utility she starts off with, giving the
following expression:

$E_{i}[u_{i}(g+ij)]=E_{i}[u_{ij}]+u_{i}(g)$ (4)

#### Beliefs

To complete our definition of expected utilities, agent $i$’s belief that
agent $j$ is of type $t\in T$ given $j$’s group membership, $s_{j}$, is
defined as follows:

$\pi_{i}(t|s_{j})\in\begin{cases}[0,1]&\text{if $i$ and $j$ do not know each
other}\\\ \\{0,1\\}&\text{otherwise}\end{cases}$ (5)

This definition captures how beliefs are uncertain if agents are unacquainted
but update to reflect certainty once they meet and reveal each other’s types.

#### Stability

We can now state a refinement of the pairwise stability conditions of Jackson
and Wolinsky (1996) [14] which reflects that agents do not know each other’s
types ex-ante:

$\begin{split}\mbox{(i)\ \ \ }&\forall ij\in g,\ u_{i}(g)\geq
u_{i}(g-ij)\mbox{\ and\ }u_{j}(g)\geq u_{j}(g-ij),\mbox{\ and}\\\ \mbox{(ii)\
\ \ }&\forall ij\notin g,\mbox{\ if\ }E_{i}[u_{ij}]\geq 0\mbox{\ then\
}E_{j}[u_{ji}]<0\end{split}$ (6)

Note that we assume that links only require non-negative instead of strictly
positive utilities to cover cases where both agents are indifferent and which
are otherwise indeterminate.

#### Further Assumptions

Having set up the general model, it is useful to follow the cost assumption of
the insider-outsider model of Galeotti et al. (2006) [7] and simplify costs
to:

$c(t_{i},t_{j})=\begin{cases}c_{L}&\text{if $t_{i}=t_{j}$}\\\
c_{H}&\text{otherwise}\end{cases}$ (7)

where $0<c_{L}<c_{H}$. This allows us to simplify expected costs to:

$\begin{split}\sum_{t\in T}\pi_{i}(t|s_{j})\ c(t_{i},t)&=\pi_{i}(t_{i}|s_{j})\
c_{L}+(1-\pi_{i}(t_{i}|s_{j}))\ c_{H}\\\ &=\pi_{i}(s_{j})\
c_{L}+(1-\pi_{i}(s_{j}))\ c_{H}\end{split}$ (8)

where $\pi_{i}(s_{j})$ is shorthand for $\pi_{i}(t_{i}|s_{j})$.

This simplification implies that the cost of forming inter-type links only
depends on the fact that types differ rather than by how much. This allows us
to hone in on the relationship between beliefs and network outcomes.

#### Complete Information

One observation to make is that our model nests the complete information case.
In particular, if agents are assumed to know each other, then their beliefs
are updated to $\pi_{i}(s_{j})\in\\{0,1\\}$ for all $i,j\in N$ prior to the
start of the game. Expected utilities then collapse to actual utilities.
Further, our stability conditions will effectively coincide with those of
other complete information models, such as Jackson and Wolinsky (1996) [14] or
Jackson and Rogers (2005) [12], save for our inclusion of an explicit
definition for previously indeterminate links.

We can further observe that the model of Jackson and Rogers (2005) [12] (with
their truncation parameter set to infinity) is a special case of our model
with complete information where hidden types and social groups coincide.

###  2.2 The Role of Beliefs

Our first set of propositions revolves around the role of beliefs in the
decision of when to make connections, particularly for low intra-type costs.
Note that the relationship between beliefs and networks is, in general, quite
complex when costs are entirely unrestricted. Given our objective of studying
social networks, it seems reasonable, however, to assume that like-minded
individuals would want to meet. We thus focus our attention on the low intra-
type cost case.

These propositions demonstrate that in many cases, beliefs are sufficient for
links to initially form or not form, irrespective of gains in actual utility.
This further has implications on the information agents will acquire over each
other’s types.

Note that all proofs are given in Appendix 0.B.

###### Proposition 1

Let $c_{L}\leq\delta-\delta^{2}$. Any two agents $i$ and $j$ must know each
other in a pairwise stable equilibrium, if

  1. (i)

$min\\{\pi_{i}(s_{j}),\pi_{j}(s_{i})\\}\geq\tfrac{c_{H}-(\delta-\delta^{2})}{c_{H}-c_{L}}$,
provided $c_{H}>\delta-\delta^{2}$, or

  2. (ii)

for any $\pi_{i}(s_{j}),\pi_{j}(s_{i})\in[0,1]$, provided
$c_{H}\leq\delta-\delta^{2}$.

This proposition has an intuitive interpretation. If inter-type costs are low,
then agents will always want to meet regardless of their beliefs. If inter-
type costs are high, then both agents need to be sufficiently optimistic about
compatibility before agreeing to meet.

###### Corollary 1

Let $c_{L}\leq\delta-\delta^{2}<c_{H}$. There exist
$\pi_{i}(s_{j}),\pi_{j}(s_{i})\in[0,1]$ so that agents $i$ and $j$ must know
each other’s types in a pairwise stable equilibrium.

This corollary is useful, as it implies that for inter-type costs that are
arbitrarily high, there are beliefs that are able to persuade the agents to
still meet.

###### Proposition 2

Consider the empty network with agents that have never met. This network
cannot be pairwise stable if and only if

  1. (i)

for some $i,j\in N$,
$min\\{\pi_{i}(s_{j}),\pi_{j}(s_{i})\\}\geq\tfrac{c_{H}-\delta}{c_{H}-c_{L}}$
when $c_{H}>\delta$, or

  2. (ii)

$c_{H}\leq\delta$.

###### Corollary 2

Consider a network that is initially empty with agents that have never met and
let $c_{L}\leq\delta-\delta^{2}<\delta<c_{H}$. Then a pairwise stable network
must have:

  1. (i)

no one knowing each other if for any $i,j\in
N,\pi_{i}(s_{j})<\tfrac{c_{H}-\delta}{c_{H}-c_{L}}$

  2. (ii)

some agents $i,j$ that have discovered each other’s types if
$min\\{\pi_{i}(s_{j}),\pi_{j}(s_{i})\\}\geq\tfrac{c_{H}-\delta}{c_{H}-c_{L}}$

  3. (iii)

everyone knowing each other if for any $i,j\in N,\\\
min\\{\pi_{i}(s_{j}),\pi_{j}(s_{i})\\}\geq\tfrac{c_{H}-(\delta-\delta^{2})}{c_{H}-c_{L}}$

This proposition and corollary are useful for simulations where the network
may be initially instantiated as the empty network with agents that do not yet
know each other. The proposition provides parameterisation that ensures agents
will start revealing to each other their types, while the corollary provides
some additional predictions about the extent to which discovery occurs. Note
that they do not imply that the empty network cannot be pairwise stable, as
agents may decide to terminate their links once they know their neighbours’
types.

###### Lemma 1

Consider an agent $i$ who belongs to a component $C_{i}$ and who is not
connected to and does not know agent $j$ who belongs to a separate component
$C_{j}$. Let $c_{H}>\delta+(|C_{j}|-1)\ \delta^{2}$. In a pairwise stable
equilibrium, agent $i$ will refuse to become acquainted with $j$ if:

$\pi_{i}(s_{j})<\dfrac{c_{H}-(\delta+(|C_{j}|-1)\ \delta^{2})}{c_{H}-c_{L}}$

This lemma shows that our model is also able to support pairwise stable
equilibria in which components coexist. Note that this nests the special case
of a singleton refusing to connect to any component. The interpretation is, in
addition, intuitive. An agent $i$ will refuse to branch out of his group, even
to the best connected individual of another group, if he is sufficiently
pessimistic about compatibility.

###  2.3 Comparison with Complete Information Networks

Song and van der Schaar (2015) [28] derive a theorem that includes a useful
relationship between incomplete and complete information networks, showing
that the set of networks that can be generated and the set of networks that
are stable under complete information are, respectively, subsets of those
under incomplete information. While their model assumes heterogeneity in
benefits, the proof of their theorem does not depend on this fact and can thus
be applied to our model. We therefore restate a generalised excerpt of their
theorem without proof.

First, denote the set of all networks generated under complete information as
$G^{C}(N)$ and those under incomplete information as $G^{IC}(N)$. Let the
networks that are pairwise stable under complete and incomplete information
respectively be denoted as $G^{C}_{S}(N)$ and $G^{IC}_{S}(N)$.

###### Theorem 2.1

If $E_{i}[u_{ij}]\geq 0$ for all $i,j\in N$, then $G^{C}(N)\subset G^{IC}(N)$
and $G^{C}_{S}(N)\subset G^{IC}_{S}(N)$.

This allows us to derive the following proposition characterising the
relationship between incomplete and complete information networks in
dependence of beliefs.

###### Proposition 3

Let $c_{L}\leq\delta-\delta^{2}$ and
$min\\{\pi_{i}(s_{j}),\pi_{j}(s_{i})\\}\geq\tfrac{c_{H}-(\delta-\delta^{2})}{c_{H}-c_{L}}$
for all $i,j\in N$. Then

  1. (i)

$G^{C}(N)\subset G^{IC}(N)$ and $G^{C}_{S}(N)\subset G^{IC}_{S}(N)$, but

  2. (ii)

$G^{IC}_{S}(N)\not\subset G^{C}_{S}(N)$.

Proposition 3 proves that for low intra-type costs our model is both capable
of generating any network that can be generated under complete information as
well as supporting all pairwise stable networks. Further, it shows that the
set of pairwise stable networks under complete information constitutes a
strict subset.

This is a significant result, as it implies that some links are formed and
_kept_ under incomplete information that would otherwise never have survived
if agents knew who they were about to connect with.

###  2.4 Application to Segregation in Social Networks

One of our key objections to the existing literature relate to an implicit
assumption that homophily is an inherent preference over observable
attributes. This assumption appears to suggest that segregative patterns in
society which are most vividly based on outward traits – such as ethnicity,
gender or class – are the socially optimal result of our supposed preference
to be with people of similar such traits.

A more nuanced argument could be made which points out that the groups in de
Martí and Zenou (2017) [21] or the islands in Jackson and Rogers (2005) [12]
do not need to correspond to social groups defined by their outward
appearance. Segregative patterns could be the result of people forming
relationships based on preferences for some underlying trait which happens to
correlate with the outward traits we observe. Homophily could, in that case,
be interpreted as a resulting phenomenon rather than an inherent preference.
This line of reasoning, however, does not fully convince, as the underlying
traits are then necessarily assumed to be observable by everyone.

We have therefore proposed a model of a heterogeneous agent-based network
formation model under uncertainty to relax this assumption and, instead, allow
for people to look for hidden traits in each other based on expectations
formed from their outward appearances. If these expectations are biased, as
this paper contends, then social group homophily could be interpreted as a
reflection of these biases rather than an inherent preference.

The introduction of a distinction between hidden types and overt social groups
provides an additional advantage in that the characterisation of efficient
networks carries over from complete information models. The analysis of
Jackson and Rogers (2005) [12], for instance, can be applied to our model by
assuming that their islands are defined based on our hidden types rather than
social groups.

We demonstrate in Appendix 0.A that we are easily able to generate a
segregative equilibrium which is not socially optimal.

##  3 Simulation Setup

To complement the static perspective taken thus far, we will now turn to the
numerical investigation of the role of beliefs in dynamic network formation
under incomplete information. We specifically focus on the properties of the
networks after they have converged to a steady state.

In the following we discuss specifics of the design of our simulation and the
key metrics that we are measuring.

###  3.1 Initial Conditions

From our theoretical results, it is clear that given the initial state of the
system, different pairwise stable networks will form.

The objective of this paper is to investigate the effect of incomplete
information on the formation of networks. As such, the focus is not on the
analysis of any particular architectures which may require specific
initialisation of the network. We will therefore initialise the network as the
empty network.

###  3.2 Dynamic Process

Our simulation will closely follow the definition of dynamic network formation
due to Jackson and Watts (2002) [13] – as we did in our theoretical framework.

Recall that network formation is thus described as a stochastic dynamic
process in which a pair of agents, $\\{i,j\\}$, is randomly selected in every
period. This pair is then evaluated for pairwise stability.

Instead of ending the period when a stable pairing has been encountered, we
instead randomly select another pair of agents until an unstable pair has been
identified or until no pairs remain. We make this change to enable faster
detection of a network’s pairwise stability.

Once the relationship between one pair of agents has been modified, we
subsequently move on to the next period, in which a new pair of agents,
$\\{k,l\\}$, is selected. The process converges when no unstable pairs remain.

###  3.3 Terminating Conditions

Given that dynamic processes may either converge to a steady state or diverge,
we turn to the definition of the conditions under which our system comes to a
halt.

We follow Jackson and Watts (2002) [13] and make use of what they call
“improving paths”.

Jackson and Watts (2002) [13] show that given a finite number of network
states, any improving path must either terminate in a pairwise stable network
or result in a cycle, which repeatedly visits the same set of networks.

In order to capture the role of information, we will add to the original
definition of improving paths and reflect that the state of the network not
only includes a description of the relationship between all agents but also
the information that each agent holds. Recall that we represent this
information with an $n\times n$ matrix $M$, giving us networks represented as
$(N,M,g)$.

In the spirit of Jackson and Watts (2002) [13], we define an improving path
from a network $(M,g)$ to a network $(M^{\prime},g^{\prime})$ – where we
suppress the constant set of agents $N$ for ease of notation – as a finite
sequence of adjacent networks $(M_{1},g_{1}),(M_{2},g_{2}),...,(M_{K},g_{K})$
with $(M_{1},g_{1})=(M,g)$ and $(M_{K},g_{K})=(M^{\prime},g^{\prime})$ so that
for any $k\in\\{1,...,K-1\\}$:

$\begin{split}\mbox{(i)\ \ }&g_{k+1}=g_{k}-ij\mbox{\ for some\ }ij\mbox{\
s.t.\ }u_{i}(g_{k}-ij)>u_{i}(g_{k}),\mbox{\ or}\\\ \mbox{(ii)\ \
}&g_{k+1}=g_{k}+ij\mbox{\ for some\ }ij\mbox{\ s.t.\ }E_{i}[u_{ij}]\geq
0\mbox{\ and\ }E_{j}[u_{ji}]\geq 0,\mbox{\ or}\\\ \mbox{(iii)\ \
}&\mathds{1}(M_{k+1})>\mathds{1}(M_{k}).\end{split}$ (9)

where the function $\mathds{1}$ returns the number of ones in matrix $M$.

Following Jackson and Watts (2002) [13], we similarly define cycles as a set
of networks $C$ so that for any of its networks,
$(M,g),(M^{\prime},g^{\prime})\in C$, there exists an improving path from
$(M,g)$ to $(M^{\prime},g^{\prime})$. A _closed_ cycle is then a cycle $C$
that does not contain any network which lies on an improving path to a network
outside of $C$.

If the improving path terminates, we can thus terminate the simulation as
convergence to a pairwise stable solution has been achieved. If the improving
path has a closed cycle, then our simulation will never converge and we thus
also terminate.

###  3.4 Belief Mechanism

One of the key features of our network formation model is a flexible
specification of agent beliefs. This is motivated by substantial evidence that
people exercise heuristic thinking in many aspects of their lives [6, 8, 10,
18, 19, 29] so that beliefs may be biased and thus differ from rational
expectations. While we draw inspiration from that body of literature, our
theoretical framework, however, does not assume any particular belief
mechanism.

We therefore use a simulation-based approach to investigate the role of biased
beliefs in generating segregation. To do so, we consider a mechanism based on
heuristic thinking whereby agents judge each other’s compatibility based on
similarity. We specifically assume that agents possess base beliefs that are
rationally anchored but tend to be more optimistic when judging people of
their own social group and less so for any other social group. We express this
formally as follows:

$\pi_{i}(s_{j})=\begin{cases}\dfrac{n_{s_{j}t_{j}}}{n_{s_{j}+}}+(1-\dfrac{n_{s_{j}t_{j}}}{n_{s_{j}+}})\gamma&\text{if
$s_{i}=s_{j}$}\\\
\dfrac{n_{s_{j}t_{j}}}{n_{s_{j}+}}-\dfrac{n_{s_{j}t_{j}}}{n_{s_{j}+}}\gamma&\text{otherwise}\end{cases}$
(10)

where $n_{s_{j}t_{j}}$ is the cardinality of the set of agents from group
$s_{j}$ and of type $t_{j}$ and $n_{s_{j}+}$ is the cardinality of the set of
agents from group $s_{j}$. Their ratio corresponds to the true probability
that an agent belongs to type $t_{j}$ in group $s_{j}$ and therefore equals
the beliefs an agent under rational expectations would hold. The bias enters
via an adjustment factor $\gamma\in[0,1]$ moving beliefs upward for agents of
the same group and downward otherwise. The adjustment is normalised to ensure
beliefs remain in the unit interval.

For our base case, we assume $\gamma$ is drawn from a positively skewed beta
distribution:

$\gamma\sim Beta(\alpha,\beta)\ \text{with}\ \alpha=1,\beta>1$ (11)

Note that the shape parameter $\beta$ controls the degree of bias, i.e., the
extent to which agent beliefs deviate from rational beliefs. In our proposed
base case parameterisation we choose $\beta=7$ which implies that c.52% of
agents do not deviate more than 10% and c.79% do not deviate more than 20%
from rational beliefs. We show an illustration of the proposed belief
distribution in Appx. 0.D.

###  3.5 Metrics

#### Segregation Indices

We make use of the generalised Freeman’s segregation index as derived in
Bojanowski and Corten (2014) [3] which is given by:

$S_{F}=1-\dfrac{pn(n-1)}{(\Sigma_{k}n_{+k})^{2}-\Sigma_{k}n^{2}_{+k}}$ (12)

where $n$ and $n_{+k}$ denote the cardinality of the set of all agents and the
set of agents of type $k$ respectively. Further, $p$ denotes the proportion of
inter-group links, which is given by the following expression:

$p=\dfrac{\Sigma_{g,h;g\neq h}m_{gh1}}{m_{++1}}$ (13)

where $m_{gh1}=|\\{ij\in g|i\in N^{g};j\in N^{h}\\}|$ and
$m_{++1}=\Sigma_{g}\Sigma_{h}m_{gh1}$ are, respectively, the number of inter-
group links and the number of all links.

Given the random graph benchmark used in Freeman’s segregation index, it can
be interpreted as a measure of the segregation introduced by agent preferences
guiding link formation. Our model of agent-based network formation under
incomplete information, however, introduces an additional information effect,
which would be confounded in Freeman’s segregation index.

In order to disentangle information effects from agent preferences we are
therefore proposing additional _incremental segregation indices_ defined as
follows:

$S_{IS}=\dfrac{p_{base}-p_{biased}}{p_{base}}$ (14)

where $p_{biased}$ denotes the proportion of inter-group links under our
network with biased beliefs and where $p_{base}$ represents the proportion of
such links in a baseline network. We use a network under complete information
and a network under rational expectations for our baselines. The incremental
segregation indices with these baselines serve as a gauge of how much of
Freeman’s segregation index is attributable to biased beliefs, incomplete
information and agent preferences.

To enhance comparability between the networks, we hold the random seed
constant for each biased belief network and its baseline networks.

#### Degree Centrality

In order to measure how well-connected the graph is, we make use of the notion
of _degree centrality_. Since we wish to focus on the macro-characteristics of
the network as a whole, we will specifically report the average of the degree
centrality across all agents.

#### Discovery

A distinguishing feature of our model lies in the information matrix capturing
varying degrees of information present in the system. As agents become less
likely to form links when the expected costs of doing so increase, the amount
of information they will discover will suffer as a result. We therefore report
on the proportion of discovery, which is calculated as the following ratio:

$discovery(g)=\dfrac{\Sigma_{i}\Sigma_{j}M_{ij}}{n^{2}}$ (15)

which corresponds to the sum of the number of agents each person knows,
normalised by the maximum possible such sum given a population of $n$ agents.

##  4 Simulation Results

We present our results, which were generated with the parameterisation
summarised in Table 1. We choose a network size for which convergence can
still be reasonably expected in a real life setting, considering that all
pairs of agents need to have interacted a potentially large number of times.

We focus in the main body on networks with two social groups which are each
equally divided between two hidden types. In Apps. 0.C.2 and 0.C.3 we compare
and discuss results from compositional changes to the network using different
distributions of social groups and hidden types. In general, these additional
results indicate that segregation dynamics are not significantly influenced by
social groups but do depend on the composition of hidden types. We, however,
show that the case of two hidden types has the advantage of incentivising
network formation and thus serves as a useful counterpoint to the distortive
and segregative influence of biased beliefs.

We focus on the network dynamics by varying one type of cost at a time to
investigate their independent effects. In addition, we are holding the decay
factor, $\delta$, constant in all cases, as results mainly depend on the
relative magnitude of benefits and costs.

All simulations were repeated 30 times. Specimen networks are illustrated in
Appx. 0.D. Averaged results are reported below.

Table 1: Simulation parameters. Parameter |  Value
---|---
Number of nodes |  48
Social groups |  2 of size 24
Hidden types |  2 of size 12 per group
Decay factor $\delta$ |  0.7
Intra-type cost $c_{L}$ (base case) |  0.2
Inter-type cost $c_{H}$ (base case) |  1.0

###  4.1 Segregation under uncertainty

In Fig. 1 we compare the network dynamics under biased beliefs with those
under rational expectations and complete information.

The segregation indices in the top panels confirm our hypothesis that biased
beliefs play an important role in segregation under uncertainty. Freeman’s
segregation index remains distinctly positive as intra-type and inter-type
costs change. Moreover, as both the incremental segregation indices with
respect to rational expectations and complete information closely track
Freeman’s index, this suggests that the segregation is not a result of
uncertainty alone or agent preferences respectively.

The middle panels provide a comparison of how much agents are willing to link
up and reveal each other’s types under biased beliefs and rational
expectations. This in itself does not imply that the links that are initially
formed survive once types are revealed. We observe that biased beliefs sustain
connection-forming between agents for both higher intra-type and inter-type
costs compared to the case under rational expectations.

Intuitively, biased beliefs imply that agents may hold different beliefs,
specifically there will exist both more and less optimistic agents in a
network under beliefs following a distribution than in one under rational
expectations where all agents share the same rational beliefs. The existence
of more optimistic agents is significant, as they are the ones that will still
be willing to risk forming a link under higher costs. As such, biased beliefs
induce connections to form in higher cost ranges whereas they wouldn’t under
rational expectations.

The lower panels show how well connected the network is, that is, how many
connections between agents survive in equilibrium. Firstly, we can observe
that networks under biased beliefs and rational expectations appear to have a
similar degree of connectedness for the lower part of the cost ranges. Given
the evolution of the segregation indices, this suggests that biased networks
support as many links as networks with rational expectations, but with a
greater number of links between agents of the same social group.

Secondly, we can observe that the greater willingness to connect at higher
costs under biased beliefs compared to under rational expectations also
results in a correspondingly later collapse of the biased network.

Lastly, networks under complete information are better connected in
equilibrium. This is intuitive, as unconnected agents of the same type will
always form and maintain a link as long as the intra-type cost lies below the
decay factor – a decision that is independent of inter-type costs as indicated
by the flat degree centrality curve on the right-hand side of the panel.

Figure 1: Biased beliefs sustain segregation as each cost is varied. Note that
incremental segregation cannot be computed where the baseline network has
collapsed to singletons (i.e., $p_{base}=0$). Freeman’s segregation index
approaches 1 when the biased network collapses to singletons.

In Fig. 2 we vary the degree of bias by changing the $\beta$ shape parameter
of the beta distribution seeding our beliefs where a lower $\beta$-value
corresponds to a greater degree of bias. We observe that while increasing the
bias is clearly associated with a step-up in the segregation index, a
reduction in the bias still yields distinctly segregative results. A full
comparison of network dynamics is shown in Appx. 0.C.1.

Figure 2: An increase in bias (a reduction in the $\beta$ shape parameter)
leads to greater segregation. Freeman’s segregation index approaches 1 when
the network collapses to singletons.

##  5 Conclusion

We have contributed an agent-based network formation model for the study of
group segregation relaxing the common assumption of complete information. We
have done so by introducing notions of expectations and beliefs that are
allowed to be heterogeneous across agents, drawing inspiration from the field
of psychology. We have shown that our model is rich enough to not only
generate those networks that a complete information equivalent could support
but indeed is capable of generating an even more diverse set of networks.
Beyond this, we have demonstrated that segregative equilibria can be supported
in our model when agents are sufficiently biased. We have proceeded to a
simulation-based approach to investigate the dynamics of segregation and found
clear evidence pointing to the role of biased beliefs in generating
segregation under incomplete information.

This has not been an exhaustive study of beliefs. The belief mechanisms we
have assumed throughout have been static to enable our focus on the presence
and absence of complete information. A promising avenue of further research
would be to imbue our mechanisms with greater realism. A first step could be
to assume that beliefs gradually update as agents meet each other. Similarly,
agents may not have perfect memory and forget each other if enough time has
passed. A second line of extensions could emanate from incorporating more
complex relationships between social groups and beliefs, where a spatial cost
topology, such as in Johnson and Gilles [17], could be applied to expected
costs. This could be useful in moving the focus from overall segregative
patterns as in this paper to studying segregation between specific groups. A
third topic of future research could revolve around the stability conditions
underlying our model. While pairwise stability offers some attractive
properties, it would be worthwhile investigating the effect of coalitional
stability concepts such as that proposed by Jackson and van den Nouweland
(2005) [11].

## References

  * [1] Aits, D., Carver, A., Turrini, P.: Group segregation in social networks. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019. pp. 1524–1532. International Foundation for Autonomous Agents and Multiagent Systems (2019)
  * [2] Blumenstock, J.E., Chi, G., Tan, X.: Migration and the value of social networks. CEPR Discussion Paper p. No. DP13611 (2019)
  * [3] Bojanowski, M., Corten, R.: Measuring segregation in social networks. Social Networks 39(1), 14–32 (2014)
  * [4] Centola, D., Gonzlez-Avella, J.C., Eguíluz, V.M., San Miguel, M.: Homophily, cultural drift, and the co-evolution of cultural groups. Journal of Conflict Resolution 51(6), 905–929 (2007)
  * [5] Chay, K., Munshi, K.: Black Networks After Emancipation: Evidence from Reconstruction and the Great Migration. Working Paper (2013)
  * [6] Chen, G., Kim, K.A., Nofsinger, J.R., Rui, O.M.: Degrees of Uncertainty: An Overview and Framework for Future Research on Experience-Based Choice. Journal of Behavioral Decision Making (20), 425–451 (2007)
  * [7] Galeotti, A., Goyal, S., Kamphorst, J.: Network formation with heterogeneous players. Games and Economic Behavior 54(2), 353–372 (2006)
  * [8] Gant, M.M., Davis, D.F.: Mental Economy and Voter Rationality: The Informed Citizen Problem in Voting Research. The Journal of Politics 46(1), 132–153 (1984)
  * [9] Granovetter, M.: The Strength of Weak Ties: A Network Theory Revisited. Sociological Theory 1, 201–233 (1983)
  * [10] Grether, D.M.: Bayes Rule as a Descriptive Model: The Representativeness Heuristic. The Quarterly Journal of Economics 95(3), 537 (1980)
  * [11] Jackson, M.O., van den Nouweland, A.: Strongly stable networks. Games and Economic Behavior 51(2 SPEC. ISS.), 420–444 (2005)
  * [12] Jackson, M.O., Rogers, B.W.: The Economics of Small Worlds. The Economic Journal 3(2-3), 617–627 (2005)
  * [13] Jackson, M.O., Watts, A.: The evolution of social and economic networks. Journal of Economic Theory 106(2), 265–295 (2002)
  * [14] Jackson, M.O., Wolinsky, A.: A strategic model of social and economic networks. Journal of Economic Theory 71(1), 44–74 (1996)
  * [15] Jackson, M.O., Xing, Y.: Culture-dependent strategies in coordination games. Proceedings of the National Academy of Sciences of the United States of America 111(SUPPL.3), 10889–10896 (2014)
  * [16] Jackson, M.O., Yariv, L.: Diffusion of behavior and equilibrium properties in network games. American Economic Review 97(2), 92–98 (2007)
  * [17] Johnson, C., Gilles, R.P.: Spatial social networks. Review of Economic Design 5(3), 273–299 (2000)
  * [18] Kahneman, D., Tversky, A.: On the psychology of prediction. Psychological Review 80(4), 237–251 (1973)
  * [19] Krawczyk, M.W., Rachubik, J.: The representativeness heuristic and the choice of lottery tickets: A field experiment. Judgment and Decision Making 14(1), 51–57 (2019)
  * [20] de Martí, J., Zenou, Y.: Network games with incomplete information. Journal of Mathematical Economics 61, 221–240 (2015)
  * [21] de Martí, J., Zenou, Y.: Segregation in Friendship Networks. Scandinavian Journal of Economics 119(3), 656–708 (2017)
  * [22] McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology 27, 415–444 (2001)
  * [23] Munshi, K.: Strength in numbers: Networks as a solution to occupational traps. Review of Economic Studies 78(3), 1069–1101 (2011)
  * [24] Munshi, K., Rosenzweig, M.: Networks and Misallocation: Insurance, Migration, and the Rural-Urban Wage Gap. American Economic Review 106(1), 46–98 (2016)
  * [25] Schelling, T.C.: Models of Segregation. The American Economic Review 59(2), 488–493 (1969)
  * [26] Schelling, T.C.: Dynamic Models of Segregation. Journal of Mathematical Sociology 1, 143–186 (1971)
  * [27] Skopek, J., Schulz, F., Blossfeld, H.P.: Who contacts whom? Educational homophily in online mate selection. European Sociological Review 27(2), 180–195 (2011)
  * [28] Song, Y., van der Schaar, M.: Dynamic network formation with incomplete information. Economic Theory 59(2), 301–331 (2015)
  * [29] Tversky, A., Kahneman, D.: Judgment under Uncertainty : Heuristics and Biases. Science 185, 1124–1131 (1974)
  * [30] Verdier, T., Zenou, Y.: The role of social networks in cultural assimilation. Journal of Urban Economics 97, 15–39 (2017)
  * [31] Zenou, Y.: A dynamic model of weak and strong ties in the labor market. Journal of Labor Economics 33(4), 891–932 (2015)

##  Appendix 0.A Non-optimal Segregative Equilibrium

In this appendix, we show that our model supports segregative equilibria that
are not socially optimal.

###### Proposition 4

Let all agents be of the same hidden type but belong to K separate social
groups, $N^{1},N^{2},...,N^{K}\subset N$ and let $c_{L}\leq\delta-\delta^{2}$.

Assume that beliefs are such that:

  1. (i)

for $i,j\in N^{k},\
\pi_{i}(s_{j})\geq\tfrac{c_{H}-(\delta-\delta^{2})}{c_{H}-c_{L}}$

  2. (ii)

for $i\in N^{k},j\in N^{s},k\neq s,\
\pi_{i}(s_{j})<\tfrac{c_{H}-(\delta+(n_{s}-1)\ \delta^{2})}{c_{H}-c_{L}}$

Starting a new network from the empty network, agents will be perfectly
segregated in a pairwise stable equilibrium that is not socially optimal.

###### Proof

Start with the empty network and take any agent $i$ belonging to some social
group $k$.

Given that $i$’s beliefs comply with the first condition for any $j\in N^{k}$,
Prop. 1 implies that agent $i$ will meet all such agents $j$, that is, he will
want to meet everyone from his social group. Since all agents are of the same
hidden type and $c_{L}\leq\delta-\delta^{2}$, all such meetings result in
lasting connections.

Given that $i$’s beliefs comply with the second condition for any $j\in
N^{s},k\neq s$, Lemma 1 implies that $i$ will refuse to meet $j$ no matter how
well-connected she is within her group.

Given $c_{L}\leq\delta-\delta^{2}$, the efficient network must be fully
connected amongst agents of the same type, as the incremental utility of
forming a link will be at least $u_{ij}\geq\delta-\delta^{2}-c_{L}\geq 0$. Yet
we have just shown that agents stay within their social groups, giving the
proposition.

##  Appendix 0.B Proofs

This appendix contains the proofs for the statements in the main body of the
paper.

###  0.B.1 Proof of Proposition 1

###### Proof

To prove this by contradiction, suppose there is a pairwise stable equilibrium
in which agents $i$ and $j$ have not met.

W.l.o.g, the least amount of utility agent $i$ expects to gain from meeting
$j$ corresponds to the case when $i$ and $j$ are already as closely connected
as possible without being neighbours, i.e., $d_{ij}=2$. The expected gain is
therefore non-negative if:

$\delta-[\pi_{i}(s_{j})\ c_{L}+(1-\pi_{i}(s_{j}))\ c_{H}]-\delta^{2}\geq 0$

where the first two terms are the benefit of becoming neighbours less the
expected cost of doing so, and where the last term is the lost benefit of
being closely but indirectly connected.

This expression can be rewritten as:

$\pi_{i}(s_{j})\geq\dfrac{c_{H}-(\delta-\delta^{2})}{c_{H}-c_{L}}$

which gives us a contradiction, as agents $i$ and $j$ must therefore have met.
Statements 1 and 2 then follow directly.

###  0.B.2 Proof of Corollary 1

###### Proof

This follows from Prop. 1, as
$\tfrac{c_{H}-(\delta-\delta^{2})}{c_{H}-c_{L}}\leq 1$.

###  0.B.3 Proof of Proposition 2

###### Proof

To prove this by contradiction, suppose the empty network with entirely
ignorant agents was pairwise stable. Take any agents $i$ and $j$, who must be
unacquainted with one another, so that the expected utility of forming a link
for agent $i$ is therefore always non-negative if:

$\delta-\pi_{i}(s_{j})\ c_{L}-(1-\pi_{i}(s_{j}))\ c_{H}\geq 0$

This is equivalent to:

$\pi_{i}(s_{j})\geq\dfrac{c_{H}-\delta}{c_{H}-c_{L}}$

This results in a contradiction and a link will then be formed if agent $j$’s
expected utility is also non-negative. The proposition thus follows by
symmetry.

###  0.B.4 Proof of Corollary 2

###### Proof

This corollary follows from Prop. 1 and Prop. 2.

###  0.B.5 Proof of Lemma 1

###### Proof

Suppose agent $i$ contemplates a link with agent $j$. The highest net utility
agent $i$ can receive from becoming connected to $j$ occurs when $j$ is
himself directly connected to all individuals in his component $C_{j}$, so
that $i$ could become indirectly connected to everyone in $C_{j}$. The
expected incremental gain of connecting is therefore negative if:

$\delta+(|C_{j}|-1)\ \delta^{2}-\pi_{i}(s_{j})\ c_{L}-(1-\pi_{i}(s_{j}))\
c_{H}<0$

which shows the lemma.

###  0.B.6 Proof of Proposition 3

###### Proof

Statement 1 – Note that Prop. 1 implies that it must be the case that
$E_{i}[u_{ij}]\geq 0$ for all $i,j\in N$. Thm. 2.1 thus gives us the first
statement.

Statement 2 – We show this by contradiction. Suppose it was the case that
$G^{IC}_{S}(N)\subset G^{C}_{S}(N)$.

Lemma 1 shows that under incomplete information some agents would stay
singletons for inter-type costs that are high enough and pessimistic enough
beliefs. Let this network be denoted $g^{o}\in G^{IC}_{S}(N)$.

Under complete information, agents would always connect with anyone from their
own type, as the least amount of utility they would receive is:

$u_{ij}\geq\delta-\delta^{2}-c_{L}\geq 0$

Singletons, therefore, do not survive under complete information, that is,
$g^{o}\notin G^{C}_{S}(N)$. Hence $G^{IC}_{S}(N)\not\subset G^{C}_{S}(N)$.

##  Appendix 0.C Additional Simulations

We discuss a number of ancillary simulations in this appendix.

###  0.C.1 Varying the Degree of Bias

In Fig. 3 we show a full comparison of network dynamics under different levels
of bias induced by changes to the $\beta$ shape parameter. We can observe that
the networks with more biased agents reflect a step-up in segregation.
Interestingly, such networks tend to collapse at a slightly later point when
intra-type costs are increased. Intuitively, more biased agents are more
willing to form connections with peers from the same social group, as they are
more optimistic that such agents would also have the same hidden type.

Figure 3: Increasing bias results in greater segregation. Freeman’s
segregation index approaches 1 when the biased network collapses to
singletons.

###  0.C.2 Compositional Changes: Social Groups

In this section, we compare network dynamics under different social groupings
of the network. An overview of the network compositions is shown in Table 2.

Table 2: Network compositions. Entries of arrays indicate size of a particular social group. Parameter |  Base |  4 Groups |  Imbalanced
---|---|---|---
Social group size |  [24, 24] |  [12, 12, 12, 12] |  [12, 36]
Hidden type distribution | Even split within each group

In Fig. 4 we can observe that changes to the social groups do not seem to have
a significant impact on segregative dynamics, as they closely align to our
base case results.

Note that Freeman’s segregation index is calculated with respect to the number
of inter-group links expected in a randomly formed network. An increase in the
number of social groups or a re-balancing to create majority and minority
groups result in adjustments to the expected number of random inter-group
links. The absolute number of inter-group link will therefore have changed
between the different compositions of the network, yet the relative proportion
to the respective random networks must have largely remained constant.

Figure 4: Segregative network dynamics under different social groupings of the
network. Freeman’s segregation index approaches 1 when the network collapses
to singletons.

###  0.C.3 Compositional Changes: Hidden Types

In this section, we compare network dynamics under different distributions of
hidden types. An overview of the network compositions is shown in Table 3.

Table 3: Network compositions. Array entries in the first row indicate size of a particular social group. Array entries in the second row indicate size of a particular hidden type _given_ a social group. Parameter |  Base |  4 Types |  Imbalanced |  Correlated
---|---|---|---|---
Social group size | [24, 24]
Hidden type distribution |  [12, 12] per group |  [6, 6, 6, 6] per group |  [18, 6] per group |  Group 1: [18, 6] Group 2: [6, 18]

In Fig. 5 we observe that network dynamics are sensitive to the distribution
of hidden types. This is expected given their direct relationship to agent
preferences.

Figure 5: Segregative network dynamics under different hidden type
distributions. Freeman’s segregation index approaches 1 when the network
collapses to singletons.

The results indicate that increasing the number of types appears to have a
disincentivising effect on network formation. Intuitively, a larger number of
rival types dilutes incentives to form connections, as all connections with
agents of a different type are penalised. Networks with 4 hidden types thus
show a rapid rise in the segregation index as costs increase and collapse to
singletons comparatively early.

Initialising the network with a type that represents the majority in each
social group (the imbalanced case) appears to not impact the dynamics
significantly. We can observe that these networks tend to be slightly better
connected and collapse to singletons at slightly higher intra-type costs
compared to the base case.

In contrast, in the correlated case in which each social group is dominated by
a different hidden type, the corresponding results reflect a marked increase
in segregation at a comparable level of connectedness. This is not surprising,
as this case naturally encourages segregation given that agents of the
majority type in a given social group would _rationally_ prefer connections to
the same social group, all things being equal.

##  Appendix 0.D Additional Figures

Figure 6: Probability density functions underlying the biased belief mechanism
anchored by different rational expectations with the adjustment factor
$\gamma\sim Beta(1,7)$. Beliefs are drawn from the right-hand side of the peak
for agents of the same social group and from the left-hand side of the peak
otherwise. Figure 7: Example networks generated with the baseline
parameterisation in Table 1 using (a) biased beliefs and (b) complete
information. Colours (green vs red) indicate social groups, tones (light vs
dark) denote hidden types.