Collaborative insurance, unfairness and discrimination
Arthur CharpentierWorkshop on decentralized insurance and risk sharing, Chicago, 2024

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

1 / 133

Disclaimer

This is an ongoing project, and, despite my efforts, it might still contain errors.
Some concepts and results presented in those slides are probably either extremely vague, or wrong.
All apologies.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

2 / 133

AgendaPeer-to-peer insurance
Peer-to-peer insurance is a reciprocity insurance contract through the Collaborative consumption concept (...) (It is sometimes paired with the concept of the“sharing economy”) (...) A group can be set up by the policyholders, forming asocial network somewhat like Facebook. ®

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

3 / 133

Agenda“you apply for a loan and your would-be lender somehow examines the credit
ratings of your Facebook friends. If the average credit rating of these members
is at least a minimum credit score, the lender continues to process the loan
application. Otherwise, the loan application is rejected,” Bhattacharya (2015), seealso Meyer (2015)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

4 / 133

AgendaUnfair (algorithmic) decision
Let us define three main criteria to evaluate if a given classifier is fair, that is if its
predictions are not influenced by some of these sensitive variables. For example
gender, ethnicity, sexual orientation or disability. ®
Classical concepts related to (group) fairness are related to (conditional) independence⊥ S, independencem(X, S) ⊥m(X, S) ⊥⊥ S | Y , separation



Y ⊥
⊥ S | m(X, S), sufficiency

or conditional probabilitiesP[m(X, S) > t|S = A] = P[m(X, S) > t|S = B], demographic parity

P[m(X, S) > t|S = A, Y = y ] = P[m(X, S) > t|S = B, Y = y ], ∀y , equalized odds

P[Y = 1|m(X, S) = t, S = A] = P[Y = 1|m(X, S) = t, S = B], ∀t, calibration

or related expected values (weak conditions) for regression problems.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

5 / 133

This course in one slide...
Fairness (machine learning)
An important distinction among fairness definitions is the one between groupand individual notions. Roughly speaking, while group fairness criteria compare
quantities at a group level, typically identified by sensitive attributes (e.g. gender,
ethnicity, age, etc.), individual criteria compare individuals. In words, individual
fairness follow the principle that ”similar individuals should receive similar treatments”, ®
Individual fairness could be related to a “perceptions of unfair treatment,” Brown
et al. (2006), Van Houtven et al. (2005) or Gonzalez et al. (2021)
Can be related to “individual counterfactual explanation,” Rudin (2019), see also
Rudin (2019), Burkart and Huber (2021),Karimi et al. (2020) or Karimi et al. (2021).

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

5 / 133

This course in one slide...
Graph (discrete mathematics)
a graph is a structure amounting to a set of objects in which some pairs of the objects are insome sense ”related” ®
But when observations are individuals in a connected
network, those concepts are harder to quantify (difference local topology, Wu et al. (2017))...
Demographic information (overall) should be studied
from a local perspective, with a network perspective
As a person in group either A or B, I feel discriminated, because among my ”neighbors” (or connections), I have the feeling that I have a higher premium @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

6 / 133

This course in one slide...
Graph (discrete mathematics)
a graph is a structure amounting to a set of objects in which some pairs of the objects are insome sense ”related” ®
But when observations are individuals in a connected
network, those concepts are harder to quantify (difference local topology, Wu et al. (2017))...
Demographic information (overall) should be studied
from a local perspective, with a network perspective
As a person in group either A or B, I feel discriminated, because among my ”neighbors” (or connections), I have the feeling that I have a higher premium @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

7 / 133

Risk Sharing and Convex Order

References: Ohlin (1969); Kaas et al. (1994); Müller and Stoyan (2002); Denuit et al.
(2006); Shaked and Shanthikumar (2007); Kaas et al. (2008); Denuit and Dhaene(2012a); Rüschendorf (2013) (etc.)
In those slides, all random variables are supposed to have a finite expected value.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

8 / 133

Convex Order“The convex ordering approach to solve the optimal insurance decision problem
was first adopted by Ohlin (1969) of minimizing a measure of the dispersion of
the retained and ceded losses. The crucial mathematical tool employed by Ohlin(1969) is the ‘Karlin–Novikoff once-crossing criterion’ by Karlin and Novikoff(1963) for (increasing) convex ordering. Later, Gollier and Schlesinger (1996) used
the same approach to extend the result of Arrow (1974) through maximizing an
increasing convex order preserving objective functional of the terminal wealth.
More recently, this approach was re-exploited to solve various optimal
insurance decision problems,” Cheung et al. (2015)
Mean-preserving spreada mean-preserving spread (MPS)⋆ is a change from one probability distribution
A to another probability distribution B, where B is formed by spreading out one
or more portions of A’s probability density function or probability mass function
while leaving the mean (the expected value) unchanged. ®
⋆ Rothschild and Stiglitz (1978) @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

9 / 133

Majorization and Convex Order
Following Hardy et al. (1929, 1934), and Marshall and Olkin (1979), for random
vectors in Rn+ ,Definition 2.1: Majorization (1)Consider two sorted vectors x and y (x1 ≥ x2 ≥ · · · ≥ xn and y1 ≥ y2 ≥ · · · ≥ yn )such that

n
X

xi =

i=1



1 1
1 1
, ,··· , ,n nn n @freakonometrics § freakonometricsnXyi , then x ⪯M y (majorization order) if

i=1



i=1



≺M

k
X

xi ≤

k
X

yi , ∀k.

i=1

1
1
1
,
,··· ,, 0 ≺M · · · ≺M (1, 0, · · · , 0, 0)n−1 n−1
n−1x ≺M y ↔ x exhibits “less dispersion”“less variability” than yfreakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

10 / 133

Majorization and Convex Order
Definition 2.2: Majorization (2)Consider two vectors x and y such that

n
X

xi =

i=1

eitherkX
i=1

x[i] ≤kX
i=1

y[i] , ∀k ornXyi , then x ⪯M y if

i=1
k
X
i=1

x(i) ≥kX

y(i) , ∀ki=1where x(1) ≤ x(2) ≤ · · · ≤ x(n) (increasing) while x[1] ≥ x[2] ≥ · · · ≥ x[n](decreasing).
If x ∈ Sn , and if ei = (0, · · · , 0, 1, , 0 · · · , 0), then

 @freakonometrics § freakonometrics

1
1 ≺M x ≺M ei , ∀infreakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

11 / 133

Majorization and Convex Order
Proposition 2.1: Majorizationx ⪯M ynn
1X
1X⇐⇒h(xi ) ≤h(yi ) for any convex function h
n i=1
n i=1
⇐⇒

n
n
1X
1X
(xi − d)+ ≤(yi − d)+ for d ∈ R
n i=1
n i=1

⇐⇒ x = Dy for some doubly stochastic matrix D, i.e.
nXDi,k =

k=1

nX

Dk,j = 1, ∀i, j

k=1⇐⇒ x = P1 · · · Pk y for finitely some Pigou-Dalton transfer matrices Pj(Pj = αI + (1 − α)T for some α ∈ (0, 1) and T = 0 except Ti,j = Tj,i = 1)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

12 / 133

Majorization and Convex Order(Muirhead)-Pigou-Dalton transfers are classical notions when studying inequalities(Muirhead (1903); Dalton (1920), see also Atkinson (2015))

(1)

(2)

y (2) ⪯M y (1) ←−

 (2)
(1)

yi = yi , ∀i ̸= j, k where j < k


y

(2)

j


 (2)

yk

 @freakonometrics § freakonometrics(1)= yj +h,(1)= yk −hfreakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

13 / 133

Majorization and Convex Order
Definition 2.3: Convex order
Consider two random variables X and Y , X ⪯CX Y if E[h(X )] ≤ E[h(Y )] forany convex function h.

L⇐⇒ Y is a mean-preserving spread of X , i.e. Y = X + Z , where E[Z |X ] = 0.
⇐⇒ E[(X − d)+ ] ≤ E[(Y − d)+ ] for all d ∈ R.
=⇒ E[X ] = E[Y ] and Var[X ] ⪯ Var[Y ].

X exhibits “less dispersion”“less variability” than Y
X ⪯CX Y
“X is preferred over Y ”

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

14 / 133

Majorization and Convex Order
Proposition 2.2: (Proposition 6 in Kaas et al. (2002))
Let X = (X1 , · · · , Xn ) denote a collection of variables and X + a comonotonic
version, then a ⊤ X ⪯CX a ⊤ X + , a ∈ Rn+ .
Proposition 2.3: (Proposition 3.4.48 in Denuit et al. (2005))
Let X = (X1 , · · · , Xn ) denote a collection of i.i.d. variables, if a ≺ b for the
majorization order, a ⊤ X ⪯CX b ⊤ X.
Proposition 2.4
Let X = (X1 , · · · , Xn ) denote a collection of i.i.d. variables, and p some ndimensional probability vector. Then p ⊤ X ⪯CX Xi for any i.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

15 / 133

Majorization and Convex Order
Definition 2.4: Risk-sharing scheme
Consider two random vectors ξ = (ξ1 , . . . , ξn ) and X = (X1 , · · · , Xn ) on Rn+ . ξ
is a risk-sharing scheme of X if X ⊤ 1 = ξ ⊤ 1, i.e. X1 + · · · + Xn = ξ1 + · · · + ξnalmost surely.
Definition 2.5: Componentwise Convex, Denuit and Dhaene (2012b), Carlier et al. (2012)
Consider two random vectors ξ = (ξ1 , . . . , ξn ) and X = (X1 , · · · , Xn ) on Rn+ .
ξ ⪯CCX X if ξi ⪯CX Xi .
Definition 2.6: Desirable Risk Sharing Scheme
A risk sharing scheme ξ of X is desirable if ξ ⪯CCX X.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

16 / 133

Majorization and Convex Order

For example, ξj = X =n1X
Xi , ∀jn i=1

it is a risk sharing since ξ1 + · · · + ξn = X1 + · · · + Xn
it is desirable (componentwise convex-order) : ξj ⪯CX Xj , ∀j
Definition 2.7: Linear risk-sharing scheme
Consider two random vectors ξ = (ξ1 , . . . , ξn ) and X = (X1 , · · · , Xn ) on Rn+ . ξ
is a linear risk-sharing scheme of X if X ⊤ 1 = ξ ⊤ 1 almost surely, and ξ = RXfor some matrix R n × n with positive entries.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

17 / 133

Majorization and Convex Order
Definition 2.8: Row-stochastic matrix
A row-stochastic matrix (or left-stochastic matrix) R has positive entries, and
R1 = 1, i.e.,R = [Ri,j ] where Ri,j ≥ 0, andnX

Ri,j = 1 ∀j.

i=1Definition 2.9: Column-stochastic matrix
A column-stochastic matrix (or left-stochastic matrix) C has positive entries, and1⊤ C = 1⊤ , i.e.,C = [Ci,j ] where Ci,j ≥ 0, andnX

Ci,j = 1 ∀i.

j=1

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

18 / 133

Majorization and Convex Order
Definition 2.10: (Doubly) Stochastic matrix
A double-stochastic matrix D has positive entries, and D1 = 1 and 1⊤ D = 1⊤ ,i.e.,
D = [Di,j ] where Di,j ≥ 0, and

n
X
i=1

Di,j =nX

Di,j = 1 ∀i, j.

j=1

This corresponds to the “zero-balance conservation” property in Feng et al. (2023).
Proposition 2.5: Birkhoff–von Neumann theorem,
Any doubly stochastic matrix can be expressed as a barycenter of permutation
matrices P 1 , · · · , P m .

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

19 / 133

Majorization and Convex OrderIf D be some n × n doubly-stochastic matrix, ξ = DX is a linear risk sharing of X thatsatisfies the “zero-balance conservation” property.
Proposition 2.6: Comparing Linear Risk Sharing
Consider two linear risk sharing schemes ξ 1 and ξ 2 of X, such that there is adoubly stochastic matrix D, n × n such that ξ 2 = Dξ 1 . Then ξ 2 ⪯CCX ξ 1 .

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

20 / 133

Majorization and Convex Order
Proposition 2.7: Linear Risk Sharing
Let R be some n × n row-stochastic matrix, and given X, a positive vector in
R+ , define ξ = RX. Then ξ is a linear risk sharing of X.
Following Martı́nez Perı́a et al. (2005), we can define an ordering based thoserow-stochastic matrices
Definition 2.11
Consider two linear risk sharing schemes ξ 1 and ξ 2 of X. ξ 1 weakly dominatesξ 2 , denoted ξ 2 ⪯wCX ξ 1 if and only if there is a column-stochastic matrix R,n × n such that ξ 2 = Rξ 1 .

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

21 / 133

Networks

References: Gibbons (1985); Trudeau (1993); Barabási (2002); Diestel (2006); Harris(2008); Easley et al. (2010); Evans (2017); Hougaard and Moulin (2018); Pass (2019)(etc.)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

22 / 133

Networks
Definition 3.1: Network
A (directed) network G = (V , E ), where, as a convention, V = {1, · · · , n} denoteeither nodes, or vertices, and E ∈ {0, 1}n×n represents the relationships.
Definition 3.2: Adjacency Matrix
Aij ∈ {0, 1}, and Aij = 1 if and only if i and j are linked,
(

Aij =

1 if (i, j) ∈ E
0 otherwise

There are no self-loops, i.e. Ai,i = 0. If the matrix is symmetric (Aij = Aji ), thenetwork is undirected.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

23 / 133

Networks> library ( igraph )> g
3 IGRAPH 8 d07103 U - - - 26 61 -4 + attr : gender ( v / c )5 + edges from 99 d7971 :6[1] 1 - -12 1 - - 3 1 - - 9 1 - - 67[6] 2 - - 8 2 - -10 2 - -18 2 - - 7
8 [11] 2 - - 9 3 - -12 3 - - 9 3 - - 6
9 [16] 4 - -18 4 - -10 4 - - 8 4 - -23
10 [21] 4 - -14 5 - -14 5 - -25 5 - -16
11 [26] 6 - -21 6 - -12 6 - - 9 6 - -15
12 [31] 7 - - 9 7 - -12 7 - -10 8 - -12
13 [36] 8 - -10 8 - - 9 8 - -18 9 - -12
14 + ... omitted several edges
1
2

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

2-- 3
2 - -15
3-- 7
4 - -13
6 - -116 - -24
8 - -23
9 - -15

24 / 133

Networks
Definition 3.3: Neighbors(immediate) neighbors of node i are

Ni = j ∈ V : (i, j) ∈ E .
Proposition 3.1: Neighbors
Ni = {j ∈ V : Ai,j > 0}.
Definition 3.4: Extended Neighborhood(immediate) extended neighbors of node i are
N i = Ni ∪ {i} @freakonometrics § freakonometrics> neighbors (g , 4)
+ 6/26 vertices
3 [1]
8 10 13 14 18 23
1
2

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

25 / 133

Networks
Definition 3.5: Neighbors of neighbors
Neighbors of neighbors of node i are(2)

Ni= {j ∈ V : (A2 )i,j > 0}.

where classically, (A2 )i,j =nXAi,k Ak,j

k=1

Definition 3.6: 2-Neighbors
Neighbors of order 2 of node i are
N 2 (i) = {j ∈ V : ∃k ≤ 2, (Ak )i,j > 0}.
(2)

Note that N 2 (i) = Ni ∪ Ni .
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

26 / 133

Networks

Definition 3.7: Subgraph of G
Given two networks G = (E , V ) and G ′ = (E ′ , V ′ ),G ′ is a subgraph of G (denoted G ′ ⊂ G) if E ′ ⊂ E
and V ′ ⊂ V .

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

27 / 133

Networks
Induced subgraphan induced subgraph of a graph is another graph, formed from a subset of thevertices of the graph and all of the edges, from the original graph, connecting
pairs of vertices in that subset ®
Definition 3.8: Induced subgraph of G
Given a network G = (V , E ) and a subset of vertices V ′ ⊂ V . The induced
subgraph GV ′ = (V ′ , E ′ ) is the graph whose vertex set is V ′ and whose edge set
consists of all of the edges in E that have both endpoints in V ′ (denoted E ′ ).

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

28 / 133

Networks

Set Ei = N i and
Vi = {(i, j) ∈ E , where j ∈ Ni }.
Definition 3.9: Induced subgraph of neighbors
Given a node i in a network (E , V ), the induced
subgraph of node i is GN i , also denoted Gi =(Ei , Vi ).
E.g. G4 = (E4 , V4 )

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

29 / 133

Networks
Definition 3.10: Degrees
Row i contains list of vertices connected to vertex i,
di =

n
X

Ai,j = A⊤i,· 1 = #Ni .

j=1

Let d = (di ) denote the vector of degrees, and D = diag(d ).
Definition 3.11: Normalized Adjacency Matrix
A0 = D −1 A = D −1/2 AD −1/2 is the normalized adjacency matrix.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

30 / 133

Networks(for directed networks, this corresponds to “out degrees”)
Definition 3.12: Walk
A walk from node i to node j is a sequence of edges, (i, v1 ), (v1 , v2 ), (v2 , v3 ),· · · , (vk−1 , vk ), (vk , j)
Definition 3.13: Path
A walk where all the vertices are distinct is a path.
Definition 3.14: Connected graph
There exists a path that connects very pair of nodes in the network.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

31 / 133

Networks

Definition 3.15: Shortest path
A geodesic between nodes i and j is a “shortest path” (i.e., with minimum numberof edges) between these nodes. dsp (i, j) is the distance between nodes i and j.

Conveniently suppose that the set of vertices V is In = {1, 2, · · · , n}.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

32 / 133

Networks
Exemples of (shortest) paths.

> shortest_paths (g , from =11 , to =26)
$vpath
3 $vpath [[1]]4 + 6/26 vertices ,5 [1] 11
9 2 18 13 26> shortest_paths (g , from =20 , to =16)
$vpath
3 $vpath [[1]]4 + 8/26 vertices ,5 [1] 20 22 12
8 4 14 5 16

1

1

2

2

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

33 / 133

Networks
Definition 3.16: Random walkRandom walk with transition matrix P = diag(d )−1 A.
Let xt denote the node reached at time t, and p(t) ∈ Sn ⊂ Rn+ the probability vector
associated with {xt = i}. Thenp t+1 = diag(d )−1 Ap t .
The stationary distribution is π = lim p t .
t→∞Proposition 3.2: Unique Stationnary Distribution
π exists and is unique if the network is connected and aperiodic.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

34 / 133

Random Graphs: Regular Graph (Dirac)

Definition 3.17: Complete graph
A complete graph is a simple undirected graph inwhich every pair of distinct vertices is connected
Here di = (n − 1), ∀i ∈ {1, · · · , n}

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

35 / 133

Random Graphs: Regular Graph (Dirac)

Definition 3.18: (r ) Regular grapha regular graph is a graph where each vertex has
the same number of neighbors; i.e. every vertex
has the same degree.
Here di = r , ∀i ∈ {1, · · · , n}

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

36 / 133

Random Graphs: Regular Graph (Dirac)

Definition 3.19: (r ) Regular grapha regular graph is a graph where each vertex has
the same number of neighbors; i.e. every vertex
has the same degree.
Here di = r , ∀i ∈ {1, · · · , n}
See Bollobás (1998) for regular random graphs

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

37 / 133

Random Graphs: Erdös-Rényi (Binomial-Poisson)
From Gilbert (1959), di ← Di ∼ B(n − 1, p)
Definition 3.20: Erdös-Rényi graphAi,j = Aj,i ← Xi,j where Xi,j are i.i.d. B(p) random variables (each edge has a fixed probabilityof being present or absent, independently of theother edges).

!

P(Di = k) =P(Di = k) →n−1 kp (1 − p)n−1−k ,k(np)k e−npk!

 @freakonometrics § freakonometrics

as n → ∞ and np = constant.

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

38 / 133

Random Graphs: Barabási–Albert, preferential attachment (Power law)

From Barabási and Albert (1999),
Definition 3.21: Barabási–Albert
Let m ≥ 1. The network initializes with a networkof m0 ≥ m nodes. At each step, add 1 new node,
then sample m existing vertices from the network,with a probability that is proportional to the number of links that the existing nodes already have.
(heavily linked nodes (“hubs”) tend to quickly accumulateeven more links)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

39 / 133

Networks Generation
Havel–Hakimi algorithm
The Havel–Hakimi algorithm is an algorithm in graph theory solving the graphrealization problem. That is, it answers the following question: Given a finite listof nonnegative integers in non-increasing order, is there a simple graph such thatits degree sequence is exactly this list? A simple graph contains no double edges
or loops. ®
Suppose that the sum of degrees is even, random networks can then be generated withthe algorithm of Havel (1955) and Hakimi (1962) (see also Viger and Latapy (2005)).
>
>
3 +
4 +
5 >
1
2

degs = sort ( round (1+ rexp (100 , 1/10) ) , decreasing = TRUE )if ( sum ( degs ) %% 2 != 0) {degs [1] <- degs [1] + 1}
g = realize_degseq ( degs , allowed . edge . types = " all ") @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

40 / 133

Majorization on networks

From Marshall and Olkin (1979),

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

41 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

42 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

Find largest j such that

j
X
(1)

yi

i=1
 @freakonometrics § freakonometrics

<

j
X
(2)

yi

i=1

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

43 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

(2)

Find largest k< j such that yk

 @freakonometrics § freakonometrics

(1)

> yk

(2)

(1)

> yj+1 > yj+1

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

44 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

−1

+1

(1)
1

2

3

4

5

1

2

3

4

5

(2)

To get a transfer, we need to select ℓ @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

45 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

Remove edge (ℓ,j) and create (ℓ,k)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

46 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

... we’re back at stage 1...

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

47 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

Find largest j such that

j
X
(1)

yi

i=1
 @freakonometrics § freakonometrics

<

j
X
(2)

yi

i=1

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

48 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

(2)

Find largest k< j such that yk

 @freakonometrics § freakonometrics

(1)

> yk

(2)

(1)

> yj+1 > yj+1

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

49 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)
−1
+1

(1)
1

2

3

4

5

1

2

3

4

5

(2)

To get a transfer, we need to select ℓ @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

50 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

To get a transfer, we need to select ℓ @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

51 / 133

Majorization on networks
y (1) = (5, 4, 4, 4, 3, 3, 2, 1) → (4, 4, 4, 3, 3, 3, 3, 2) = y (2)

(1)
1

2

3

4

5

1

2

3

4

5

(2)

Remove edge (ℓ,j) and create (ℓ,k)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

52 / 133

Majorization on networks

djacency matrix A1degree vector d 1


 



. . 1 1 1 . 1 1
5. . . 1
 . . . . . 1 . .  1
. . . .
  




  
1 . . 1 1 . . .  3
. . . 1  
1 . 1 . . . 1 1 4 ,   , A2 = 1 . 1 .
A1 = 
1 . 1 . . 1 . 1 4
. 1 1 .


  


  
 . 1 . . 1 . . 1 3
. 1 . .
  
1 . . 1 . . . .  2
1 . 1 1
1 . . 1 1 1 . .
4
1 . . 1  

. . 1 13 
1 1 . .
 2
  
1 . 1 .  3
  
 
. . 1 1 , 4
. 1 . 1 
4
  
1 . . 1 3  . . . .  3
1 1 . .
4Note that d 2 = y (2) ⪯ y (1) = d 1 and A2 ⪯ A1 .

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

53 / 133

Risk Sharing on Networks

References: Gibbons (1985); Trudeau (1993); Barabási (2002); Diestel (2006); Harris(2008); Easley et al. (2010); Evans (2017); Hougaard and Moulin (2018); Pass (2019)(etc.)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

54 / 133

Risk sharing on cliques
Definition 3.22: Cliques
A clique of a graph G = (V , E ) is an induced subgraph of G that is complete. Formally, a clique C
is a subset of the vertices, C ⊂ V , such that every
two distinct vertices are adjacent.
With disconnected cliques, A is a diagonal block matrix

A1 0 · · · 0 ( 0 A2 · · · 0 
Ak : nk × nk matrix
A= .
.. . .
.. 
,
.
. . 
Ak = (1k 1⊤.
 .
k − Ik )00 · · · Ak
(up to some rearrangement of indices) @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

55 / 133

Risk sharing on cliques
Let G be a collection of disconnected cliques (partition of cliques), set
M1 0 · · · 0  0 M2 · · · 0  Mk : nk × nk matrix
M=
1
1
..
.. 
..
 ..
,
Mk =
(1k 1⊤.
 Mk =.
.   .
k − Ik )nk − 1nk − 100 · · · Mk

(up to some rearrangement of indices).
Proposition 3.3: Risk Sharing on Cliques
M is a doubly-stochastic matrix, and ξ = MX is a linear risk sharing of X,(strictly) preferable in the sense that ξ ≺CCX X.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

56 / 133

Risk sharing on networks
With our disconnected cliques, if Ank = 1nk 1⊤
nk − Ink ,

(n1 − 1)In1

0

M=
..

.

0

0
(n2 − 1)In2
..
.
0

···
···
..
.

−1 

0
0
..
.

· · · (nk − 1)Ink







An1

 0
 .
 .
 .
0

0
An2
..
.

···
···
..
.

0

· · · Ank



0
0 

.. 

. 

i.e. M is the normalized adjacency matrix of A, D −1 A, where D = diag(d ).








0 1 0
0 1 0




For example, if A = 1 0 1, then M = D −1 A = 1/2 0 1/2.
0 1 0
0 1 0
Note that here M is a row stochastic matrix, but not doubly stochastic.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

57 / 133

Risk sharing on networks
Definition 3.23: Linear Sharing Risks with ‘Friends’ on a Network
Given a network G = (V , E ) with adjacency matrix A, the Linear Sharing Risks
with ‘Friends’ is
1 X
ξ A = (D −1 A)X, i.e. ξA,j =Xi
dj j∈Ni(

G1 = (In , E1 ), with adjacency matrix A1 , with degree vectors d 1
G2 = (In , E2 ), with adjacency matrix A2 , with degree vectors d 2

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

58 / 133

Risk sharing on networks
Definition 3.24: Network Ordering based on dConsider G1 = (In , E1 ) and G2 = (In , E2 ), write G1 ⪯D G2 if d 1 ⪯M d 2
Definition 3.25: Network Ordering based on A
Consider G1 = (In , E1 ) and G2 = (In , E2 ), write G1 ⪯A G2 if A1 ⪯M A2
Proposition 3.4: Risk Sharing on Networks
If G1 ⪯A G2 , then ξ A1 ⪯ ξ A2 ⪯ x

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

59 / 133

Risk sharing on networks
As mentioned in Charpentier et al. (2021), there are several problems,
1. suppose that A is a permutation matrix, then M = A is doubly stochastic








0 1 0
0 1 0




A = 0 0 1 then M = A = 0 0 1.
1 0 0
1 0 0
Related to the anonymicity principle in Pigou Dalton transfer(and law based properties).
2. such risk sharing schemes are not, per se, reciprocal.








0 1 0
0 1 0




A = 1 0 1 then M = D −1 A = 1/2 0 1/2.
0 1 0
0 1 0
3. diag(M) = 0 is problematic...
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

60 / 133

Centrality and Algebra of Networks

References: Gibbons (1985); Trudeau (1993); Barabási (2002); Diestel (2006); Harris(2008); Easley et al. (2010); Evans (2017); Hougaard and Moulin (2018); Pass (2019)(etc.)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

61 / 133

Networks Centrality
Definition 3.26: Degree Centrality
Degree centrality of node i is cd (i) = di , and c d = d .
Definition 3.27: Eigenvector Centralityn
1X
Ai,j ce (j), or
Eigenvector centrality of node i is solution of ce (i) =λ j=1
1c e = A⊤ c e , for some fixed constant λ > 0.
λEquation A⊤ c e = λc e means that c e is some eigenvector associates with A⊤ (or A if
G is undirected).
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

62 / 133

Networks Centrality
Definition 3.28: PageRank Centrality
PageRank centrality of node i is solution of cp (i) = α

n
X
j=1

⊤

c p = αA D

−1

cp (j)+ β, ordj

c p + β1, for some fixed constant α and β.

> eigen_centrality ( g )[1] 0.527 0.821 0.732 0.544 0.060
3[6] 0.702 0.671 0.833 1.000 0.788
4 [11] 0.310 0.864 0.286 0.298 0.458
5 [16] 0.019 0.075 0.657 0.030 0.030
6 [21] 0.162 0.160 0.544 0.345 0.060
7 [26] 0.046
8 > eigen ( t ( get . adjacency ( g1 ) ) )$vectors [ ,1]> page_rank ( g )[1] 0.030 0.049
3[6] 0.060 0.036
4 [11] 0.036 0.058
5 [16] 0.024 0.023
6 [21] 0.020 0.044
7 [26] 0.014
8 >
9 >

1

1

2

2

 @freakonometrics § freakonometrics

Ai,jfreakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

0.043
0.049
0.036
0.052
0.045

0.045
0.070
0.044
0.026
0.025

0.033
0.049
0.031
0.026
0.033

63 / 133

Networks Centrality
Definition 3.29: Closeness Centrality
Closeness centrality of node i is cc (i) =

n
n
X

.

dsp (i, j)

j=1> closeness ( g1 )[1] 0.014 0.018
3[6] 0.016 0.017
4 [11] 0.014 0.019
5 [16] 0.009 0.012
6 [21] 0.012 0.014
7 [26] 0.010
1
2

0.017
0.019
0.013
0.018
0.017

0.017
0.019
0.014
0.011
0.014

0.011
0.019
0.015
0.011
0.011

1

>

See Freeman et al. (1979)
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

64 / 133

Networks Centrality
Definition 3.30: LaplacianL = diag(d ) − A,

Li,j :=




di

−1



0

1

if i = jif i ̸= j and (i, j) ∈ E
otherwise,> L = laplacian_matrix ( g ) @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

65 / 133

Networks Centrality
Proposition 3.5: Alternative expression for Lℓi,j

Let ei = (0, · · · , 0, 1, , 0 · · · , 0) ∈ {0, 1}n ,L=X(ei − ej )(ei − ej )⊤(i,j)∈E

i
..
.

j

.
(0) .. (0)1 · · · −1 · · ·  iℓi,j n × n matrix, ℓi,j = ..
..
. (0) . (0)
(0)



 · · · −1 · · · 1 · · ·  j.
.
(0) .. (0) .. (0)(0)· · ·
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)



66 / 133

Sidenote on quadratic forms
Definition 3.31: Normalized Laplacian Matrix
L0 = D −1/2 LD −1/2 = I − A0 is the normalized adjacency matrix.
L and L0 are symmetric positive semidefinite matrices.
Proposition 3.6: Laplacian and quadratic form
L = diag(d ) − A,x ⊤ Lx = @freakonometrics § freakonometrics

n
1 X
1 X
(xi − xj )2 =Ai,j (xi − xj )22 (i,j)∈E
2 i,j=1

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

67 / 133

Sidenote on quadratic forms
Proof.
Ai,· =nX

2

Ai,j (xi − xj ) =

i,j=1

n
X


Ai,j xi2 − 2xi xj + xj2 =

i=1

i,j=1

n
X

Ai,j (xi − xj )2 = 2

i,j=1

n
X

n
X
i=1

di xi2 + 2nXAi,· xi2 −

n
X

n
X

Ai,j = dij=1

2Ai,j xi xj +

i,j=1

n
X

A·,j xj2

j=1

Ai,j xi xj = 2x ⊤ D − A x = 2x ⊤ Lx


i,j=1

x ⊤ Dxx ⊤ AxSince x ⊤ Lx ≥ 0 for all x, L is symmetric positive semidefinite matrices.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

68 / 133

Sidenote on quadratic forms
Let λn ≥ λn−1 ≥ · · · ≥ λ2 ≥ λ1 ≥ 0 denote L’s eigenvalues.
Proposition 3.7: Spectrum of L and λ1
The n-vector of one’s, 1, is an eigenvector of L associated with eigenvalue λ1 = 0.

Proof.
L1 =X(1i − 1j ) (1i − 1j )⊤ 1 =(i,j)∈E

0X(1i − 1j )0 = 0.

(i,j)∈E

Proposition 3.8: Spectrum of L and λ2
Network G = (E , V ) is disconnected in two groups if and only if λ2 = 0.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

69 / 133

Sidenote on quadratic forms
Proposition 3.9: Spectrum of L and λ2
Network G = (E , V ) is disconnected in at least k groups if and only if λk = 0.
Proposition 3.10: Laplacian and quadratic form
L0 = D −1/2 LD −1/2 ,1 X
x L0 x =2 (i,j)∈E⊤

 @freakonometrics § freakonometrics

xi
xj
−
di
dj

!2

n
1 X
=
Ai,j
2 i,j=1

xi
xj
−
di
dj

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)!2

70 / 133

Networks Homophily and Assortative Mixing

Reference: Shrum et al. (1988); Yamaguchi (1990); McPherson et al. (2001); Jackson(2008); Newman (2018) (etc.)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

71 / 133

Networks Homophily and Assortative Mixing
Definition 4.1: Homophily
Homophily is the tendency of individuals to form relations with others similar tothem.
Definition 4.2: Community, Newman and Girvan (2004), Newman (2018)
Communities are partitions of nodes.
The total number of edges that run between nodes of the same type is
1X
δ(ci , cj ) =Ai,j δ(ci , cj ) where δ(ci , cj ) =2 i,j(i,j)∈EX

 @freakonometrics § freakonometrics(

1 if ci = cj
0 otherwise.

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

72 / 133

Networks Homophily and Assortative Mixing

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

73 / 133

Networks Homophily and Assortative Mixing
The expected number of edges between nodes if edges are placed at random is
1 X di dj
δ(ci , cj )2 i,j 2m
and the difference between the actual and expected number of edges in the networkthat join nodes of the same type is mQ where Q is the modularity measure,
Definition 4.3: Modularity measure, Newman (2003)
The modularity measure of a partition (c) of a network (E , V ) isQ=

1 X
2m i,jAi,j −

di dj
2m

Bi,j



δ(ci , cj )where m is the total number of links. B is coined “modularity matrix”.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

74 / 133

Networks Homophily and Assortative Mixing
A network is said to be assortative if a significant portion of its links are between nodes
that belong to the same community
B =A−

>
>
3 >
4 >
1
2

A
m
d
B

=
=
=
=

d ⊤d
di dj
, i.e. Bi,j = Ai,j −,2m2m

get . adjacency ( g )sum ( A ) /2
apply (A ,1 , sum )A - d %*% t ( d ) /(2* m ) @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

75 / 133

Networks Homophily and Assortative Mixing
Since Bi,j = Ai,j −

di dj
, and
2m

n
X

Bi,j =

i=1
n
X

2m

dj
n
X

Ai,j −ndj X
dj2m = 0di = dj −2m i=12m

Ai,j −ndi X
di2m = 0
dj = di −2m j=12m

i=1Bi,j =

j=1

n
X
j=1

di
2m
In the case where were two communities, A and B, set(siA = @freakonometrics § freakonometrics+1 if i ∈ A−1 if i ∈ B(

and siB = −siA =+1 if i ∈ B−1 if i ∈ A

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop).

76 / 133

Networks Homophily and Assortative Mixingthenδ(ci , cj ) =1
si sj + 1
2

so that
Q=


1 X
1 X
1 X
1 ⊤
Bi,j δ(ci , cj ) =Bi,j si sj + 1 =Bi,j si sj =s Bs,
2m i,j4m i,j4m i,j4m(whatever the reference group).
Proposition 4.1
The modularity measure can be written
1 ⊤s Bs, where s = 1A − 1B , i.e. siA =Q=
4m
 @freakonometrics § freakonometrics(+1 if i ∈ A−1 if i ∈ B

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

77 / 133

Networks Homophily and Assortative Mixing
When is Q maximal (in s) ? see “modularity maximization,” in Newman (2012)
Recall that s ∈ {±1}n , so that s ⊤ s = n. Our problem ismax n s ⊤ Bs , subject to s ⊤ s = n.
s∈{±1}

Using the Legrangian, our optimization problem has the following first order condition∂ ⊤s Bs + λ(n − s ⊤ s) = 0
∂s

i.e.

n

X  X∂ X
Bi,j si sj + λ n −sj2 =Bi,k si − λsk = 0, ∀k∂sk i,jji=1

or, with matrix notations, Bs ⋆ = λs ⋆ , i.e. s ⋆ is an eigenvector of B. ThusQ⋆ =
 @freakonometrics § freakonometrics

1 ⊤
1 ⊤
n
s ⋆ Bs ⋆ =s ⋆ λs ⋆ =
λ.
4m
4m
4m

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

78 / 133

Networks Homophily and Assortative Mixing

1
2> modularity ( g1 , 1+( V ( g1 ) $gender ==" female ") )[1] 0.3078474

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

79 / 133

Networks, without networks
Following Morris (1995), from AMEN (AIDS in Multi-Ethnic Neighborhoods) Study @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

80 / 133

Networks, without networks
Here we have 4 sensitive groups, on a bipartite network (heterosexual relationships)
Consider a discrete copula representation
ei,j
Black
Hispanic
White
Other
bj
ai =

Black
0.258
0.012
0.013
0.005
0.289
K
X

Hispanic
0.016
0.157
0.023
0.007
0.204

White
0.035
0.058
0.306
0.024
0.423

ei,j = E ⊤i,· 1 and bj =

j=1

K
X

Other
0.013
0.019
0.035
0.016
0.084

ai
0.323
0.247
0.377
0.053

ei,j = E ⊤
·,j 1

i=1

Further
a⊤b =

K
X
k=1

 @freakonometrics § freakonometrics

ak bk =

K X
K
X
k=1

i=1

ei,k

K
 X
j=1



ek,j =

X(E 2 )i,j = ∥E 2 ∥i,jfreakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

81 / 133

Networks, without networks
Thus, we recover the coefficient introduced in Gupta et al. (1989),
Definition 4.4: Assortativity coefficient, Gupta et al. (1989)
With K communities
K
X

r=

K
X

ek,k −

k=1

1−

ak bk

k=1
K
X

ak bk

=

trace[E ] − ∥E 2 ∥1 − ∥E 2 ∥k=1

More generally, when dealing with data with a network topology, we should be careful...

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

82 / 133

Statistics with a Network Topology

References: Peel et al. (2022)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

83 / 133

Statistics with a Network Topology
sample data (y, X, S)

network data (V , E , y, X, S)
for a node i ∈ V ,

y=

n
1X
1⊤ y
yj = ⊤
n j=1
1 1→ sample version of E[Y ].
ys =

n
1 X
1⊤ y
1(sj = s)yj = s⊤ns j=11s 1→ sample version of E[Y |S = s].

 @freakonometrics § freakonometrics

n
1 X
A⊤ y
1 X
yj =
Ai,j yj = i·⊤y (i) =di j∈Ndi i=1Ai· 1
i→ sample version of Ei [Y ].
y s (i) =1 X(Ai· · 1s )⊤ y1(sj = s)yj =di:s j∈N(Ai· · 1s )⊤ 1i

→ sample version of Ei [Y |S = s].
where a · b is the element-wise product.

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

84 / 133

Statistics with a Network Topology
Given sample {x1 , · · · , xn }, the empirical variance,
σ2 =

n
n
1X
1X
(xi − x )2 , where x =
xi
n i=1
n i=1

could be written as a U-stat, Lee (2019)
σ2 =

n
1 X
(xi − xj )2 .
2n2 i,j=1

On a network, with adjacency matrix A,
σG2 =

n
n
X
1 X
Ai,j (xi − xj )2 , where 2e =Ai,j
4e i,j=1
i,j=1

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

85 / 133

Statistics with a Network Topology

Given sample {(x1 , y1 ), · · · , (xn , yn )}, the empirical covariance could be written as a U-stat,
cv =

n
1 X
(xi − xj ) (yi − yj )2n2 i,j=1

and if observations are nodes on a network
cvG =

n
1 X
Ai,j (xi − xj ) (yi − yj )4e i,j=1

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

86 / 133

Statistics with a Network Topology
If x is independent of the topology of the network (summarized by A),
σ2 =

n
n
1 X
1 X
2
≈
Ai,j (xi − xj )2 = σG2
(x
−
x
)
i
j
2n2 i,j=1
4e i,j=1

otherwise, the topology of the network is not neutral...

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

87 / 133

Statistics with a Network Topology
σG2 ≈ σ 2“cor(A, x ) ≈ 0”

σG2 ≥ σ 2“cor(A, x ) ≥ 0”

σG2 ≤ σ 2“cor(A, x ) ≤ 0”

Erdös-Rényi network with n = 100 nodes, probability p (drawn randomly in [0, 1])
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

88 / 133

Statistics with a Network Topology
Following Hall (1970), write
s2 =

n
n
1 X
1 X
(xi − x̄ )2 =( xi − xj + xj − x̄ )2
n − 1 i=1
n − 1 i=1=⇒ (n − 1)s 2 ==⇒ n(n − 1)s 2 =nX(xi − xj )2 + 2nX(xi − xj )(xj − X̄ ) +

i=1
n
n
XX

i=1
n
n X
X

j=1 i=1j=1 i=1(xi − xj )2 + 2(xi − xj )(xj − x̄ ) +n XnX

i=1 j=1i=1 j=1i=1 j=1(xi − xj )(xj − x̄ ) = 2

n X
n
X

n X
n
X

n
X

i=1 j=1i=1 j=1i=1(xi − xj )2 = 2(xj − x̄ )2 + 2(xj − x̄ )2 .

(xj − x̄ + x̄ − xi )(xj − x̄ )(x̄ − xi )nX

(xj − x̄ ) = 2n(n − 1)s 2 .

j=1|
 @freakonometrics § freakonometricsnn X
X
j=1 i=1

n X
n
X

=⇒

(xj − x̄ )2 .

i=1

n X
n
X

(xi − xj )2 = −2

n
X

{z
0

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)}

89 / 133

Statistics with a Network Topology
Thus, for any m, writenX2n(n − 1)s 2 =(xi − xj )2 =

i,j=1

n
X

xi − m − xj − m )i,j=1 | {z }
ui

|

{z
uj

2

=

n
X

ui2 + uj2 + 2ui uj

i,j=1

}

If m = x ,nXui2 = n

i,j=1

n
X
i=1

ui2 = n(n − 1)S 2 and thereforenXui uj = 0.

i,j=1Hence,
n
n
1 X
1 X
(x
−
x
)(x
−
x
)
=
0
but
possibly
Ai,j (xi − x )(xj − x ) ̸= 0.
i
j2n2 i,j=1
4e i,j=1

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

90 / 133

Paradoxes in Networks“on average your friends have more friends than you do.”
Proposition 4.2: Friendship Paradox
The average number of friends of the collection of friends of individuals in a social
network will be higher than the average number of friends of the collection of theindividuals themselves. More formally
n
n
1X
1 X
Aij djn i=1 di j=1





≥

n
1X
di .
n i=1

Define differences ∆i ’s between the average of its neighbours’ degrees and its own
degree, in the sense that
n
1 X
∆i =
Aij dj − di .
di j=1
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

91 / 133

Paradoxes in Networks
Write the average as
n
n
n
1X
1 X
1X
∆i =
Aij dj − din i=1
n i=1 di j=1





n
dj
1X
Aij − Aij ,=n ij=1dithat yields
n
n
1X
dj
1X
−1
∆i =
Aij
n i=1
n ij=1
di





n
1X
di
−1 ,
Aij
n ij=1dj

but also

by exchanging the summation indices, and because A is a symmetric matrix. By
adding the two, we can write
n
2X

n i=1

∆i =

1X
n

ij



Aij

dj
di
+ −2 =
di
dj
2n


1 X
ij

s

Aij 

dj
−
di

s

2

di 
≥ 0.
dj

(the exact equality holds only when di = dj for all pairs of neighbors)
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

92 / 133

Attributed Networks
Definition 4.5: Attributed Network
An attributed (directed) network Gx = (V , E , X) is a network (V , E ) where X
is a node attributes matrix, n × k, where each row is a feature vectors, for eachnode in V = In .
If X = (x1 , · · · , xn ), the classical average isµ(x) = x =

n
1X
xi .
n i=1

Given an attributed (directed) network Gx = (V , E , X), where X = (x1 , · · · , xn ),
n
1 X
1 X
di xi
Ai,j xi =µG (x) = X
2m i=1
Ai,j i,j
i,j @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

93 / 133

Attributed Networks
Similarly, the variance of X = (x1 , · · · , xn ) isVar(x) =−1 X(xi − µ(x))(xj − µ(x))
n − 1 i̸=jwhile variance over edges
1 X
di dj
Ai,j (xi − µG (x))(xj − µG (x)) =Ai,j −
2m
2m
Ai,j i,ji,j1

VarG (x) = X



X



xi xj .

i,jThis leads to an other modularity measure, after anoter renormalization, so that it
takes the value 1 in a network with perfect assortative mixing—one in which all edges
fall between nodes with precisely equal values of xi ,
1 X
di dj
Q=
Ai,j xi2 −xi xj
2m i,j2m

 @freakonometrics § freakonometrics



1 X
di dj
=
di 1i=j −2m i,j2m
freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)



xi xj

94 / 133

Attributed Networks
Definition 4.6: Modularity measure for attributed networks
For some categorical variable x , the modularity measure is
1 X
di dj
Ai,j −
2m i,j2mQ=δ(xi , xj ).

If x is a numerical variable, a different normalization is considered
1X
di dj
Q=
Ai,j −
κ i,j
2m




xi xj , where κ =dk dl
dk 1k=l −
2m

X
k,l



xk xl

also coined “assortativity coefficient”.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

95 / 133

Attributed Networks“you apply for a loan and your would-be lender somehow examines the credit
ratings of your Facebook friends. If the average credit rating of these members
is at least a minimum credit score, the lender continues to process the loan
application. Otherwise, the loan application is rejected,” Bhattacharya (2015)“il ne faut jamais juger les gens sur leurs fréquentations. Tenez, Judas, parexemple, il avait des amis irréprochables,” Paul Verlaine
For the generalized friendship paradox, which considers attributes other than degree, as(x )in Cantwell et al. (2021), one can define an analogous quantity, ∆i , for some
attribute x (such as the wealth) is defined as
(x )

∆i

 @freakonometrics § freakonometrics=

1 X
Aij xj − xi ,di jfreakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

96 / 133

Attributed Networks
which measures the difference between the average of the attribute for node i’sneighbours and the value for i itself. When the average of this quantity over all nodes
is positive one may say that the generalized friendship paradox holds. In contrast to(x )the case of degree, this is not always true – the value of ∆i can be zero or negative –but we can write the average as
1 X (x )1X 1 X∆i =Aij xj − xin i
n i di j


X Aij
1X
xi
− xi ,
n i
dj
j




=



where the second line again follows from interchanging summation indices. Defining
the new quantity
X Aij
δi =
,
dj
j
and noting that
1X
1 X Aij
1X 1 Xδi ==Aij = 1,n i
n ij djn j dj i @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

97 / 133

Attributed Networks
we can then write
1 X (x )
1X
1X 1X
∆i =
xi δi −xi
δ i = Cov(x, δ).
n i
n i
n i
n i
Thus, we will have a generalized friendship paradox in the sense defined here if (andonly if) x and δ are positively correlated. But this is not always the case)

Cov(d , δ) ≥ 0
Cov(x, δ) ≥ 0

 @freakonometrics § freakonometrics

̸=⇒ Cov(d , x) ≥ 0.

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

98 / 133

Group Fairness

References: Kearns and Roth (2019); Barocas et al. (2023); Charpentier (2024) (etc.)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

99 / 133

Group Fairness
Fairness (machine learning)
Fairness in machine learning refers to the various attempts at correcting algorithmic bias in automated decision processes based on machine learning models.
Decisions made by computers after a machine-learning process may be considered
unfair if they were based on variables considered sensitive. For example gender,
ethnicity, sexual orientation or disability ®
x ∈ X ⊂ Rd : ‘explanatory’ variabless ∈ {A, B} : (binary) ”sensitive variable”
class ∈ {0, 1}
y ∈ {0, 1} : classification problem
yb ∈ {0, 1} : prediction, classically yb = 1( m(x, s) > t)score ∈ [0, 1] ⊂ R⊥SIndependence (Definition 5.1) : m(Z ) ⊥Separation (Definition 5.2) : m(Z ) ⊥⊥ S | YSufficiency (Definition 5.6) : Y ⊥⊥ S | m( Z ) @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)z = (x, s)

100 / 133

Group Fairness

Definition 5.1: Independence, Barocas et al. (2017)
A model m satisfies the independence property if m(Z ) ⊥⊥ S, with respect to the
distribution P of the triplet (X, S, Y ).
Definition 5.2: Separation, Barocas et al. (2017)
A model m : Z → Y satisfies the separation property if m(Z ) ⊥⊥ S | Y , withrespect to the distribution P of the triplet (X, S, Y ).

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

101 / 133

Group Fairness
Definition 5.3: True positive equality, (Weak) Equal Opportunity, Hardt
et al. (2016)
A decision function yb – or a classifier mt (·), taking values in {0, 1} – satisfies
equal opportunity, with respect to some sensitive attribute S if(

b = 1|S = A, Y = 1] = P[Yb = 1|S = B, Y = 1] = P[Yb = 1|Y = 1]
P[YP[mt (Z ) = 1|S = A, Y = 1] = P[mt (Z ) = 1|S = B, Y = 1] = P[mt (Z ) = 1|Y = 1],

which corresponds to parity of true positives, in the two groups, {A, B}.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

102 / 133

Group Fairness

Definition 5.4: False positive equality, Hardt et al. (2016)
A decision function yb – or a classifier mt (·), taking values in {0, 1} – satisfies
parity of false positives, with respect to some sensitive attribute s, if(

b = 1|S = A, Y = 0] = P[Yb = 1|S = B, Y = 0] = P[Yb = 1|Y = 0]
P[YP[mt (Z ) = 1|S = A, Y = 0] = P[mt (Z ) = 1|S = B, Y = 0] = P[mt (Z ) = 1|Y = 0].

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

103 / 133

Group Fairness
Definition 5.5: Equalized Odds, Hardt et al. (2016)
A decision function yb – or a classifier mt (·) taking values in {0, 1} – satisfies
equal odds constraint, with respect to some sensitive attribute S, if(

b = 1|S = A, Y = y ] = P[Yb = 1|S = B, Y = y ] = P[Yb = 1|Y = y ], ∀y ∈ {0, 1}
P[YP[mt (Z ) = 1|S = A, Y = y ] = P[mt (Z ) = 1|S = B, Y = y ], ∀y ∈ {0, 1},,

which corresponds to parity of true positive and false positive, in the two groups.
Definition 5.6: Sufficiency, Barocas et al. (2017)
A model m : Z → Y satisfies the sufficiency property if Y ⊥⊥ S | m(Z ), withrespect to the distribution P of the triplet (X, S, Y ).

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

104 / 133

Individual Fairness

References: Dwork et al. (2012); Kusner et al. (2017); Charpentier (2024) (etc.)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

105 / 133

Individual Fairness“We capture fairness by the principle that any two individuals who are similar
with respect to a particular task should be classified similarly,” Dwork et al.
(2012)
Definition 5.7: Similarity Fairness, Dwork et al. (2012)
We have similarity fairness if for all i ̸= j such that x i = x j , and si ̸= sj , thenm(x i , si = A) = m(x j , sj = B).
“In order to accomplish this individual- based fairness, we assume a distancemetric that defines the similarity between the individuals,” Dwork et al. (2012)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

106 / 133

Individual Fairness
Definition 5.8: Similarity Fairness, Luong et al. (2011), Dwork et al.
(2012)
Consider two metrics, one on Y (for a classifier [0, 1]2 and not {0, 1}2 ) noted Dy ,and one on X noted Dx . We will have similarity fairness on a database of size n
if we have the following property (called Lipschitz property)
Dy (m(x i , si ), m(x j , sj )) ≤ L · Dx (x i , x j ), ∀i, j = 1, · · · , n,for some L < ∞.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

107 / 133

Individual Fairness

1
2
3
4

Gender

Name

H
F
F
H

Alex
Betty
Beatrix
Ahmad

Treatment
ti
A
B
B
A

yi
75
52
57
78

Outcome (Weight)
⋆
⋆
yi,T
yi,T
TE
←A
←B
75
64
11
67
52
15
71
57
14
78
61
17

Height
xi
172
161
163
183

···
···
···
···
···
···

Different notations are used y (1) and y (0) in Imbens and Rubin (2015), y 1 and y 0 in
Cunningham (2021), or yt=1 and yt=0 in Pearl and Mackenzie (2018)⋆⋆
Define potential outcomes to quantify the treatment effect, TE = yi,T
←B − yi,T ←A(⋆
observation : yi,T
←B when ti = B is observed, and x i⋆counterfactual : yi,T ←A when ti = B is observed, and x i

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

108 / 133

Individual Fairness
Definition 5.9: Fairness on Average Treatment Effect, Kusner et al. (2017)
We achieve counterfactual fairness on average if⋆⋆
ATE = E YS←A− YS←B= 0.



A decision satisfies counterfactual fairness if “had the protected attributes (e.g.,race) of the individual been different, other things being equal, the decision
would have remained the same” Kusner et al. (2017)
Definition 5.10: Counterfactual Fairness, Kusner et al. (2017)
We achieve counterfactual fairness for an individual with characteristics x if⋆⋆
CATE(x) = E YS←A− YS←BX = x = 0.



 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

109 / 133

Individual Fairness
If we get back to the “similarity approach”, Zemel et al. (2013) suggested to use aconsistency indexn
1X
1 X
m(x i , si ) −m(x j , sj )
n i=1
k j∈N
i:k

where Nk (i) at the k closest neighbor of x i in X . Why not considern
1 X
1Xm(x i , si ) −m(x j , sj )n i=1
ni j∈N(i)

or
n
1X
1
n i=1 niAX
j∈N A (i)m(x j , sj ) −1 X
m(x j , sj )niB j∈N B (i)corresponding to some network centric approach (perceived discrimination Pascoe andRichman (2009), Schmitt et al. (2014)).
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

110 / 133

Fairness Perception on Networks“Network and data analyses compound and reflect discrimination embedded
within society,” Bernstein (2007)
References: Shalmani (2021)

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

111 / 133

Network Centric Fairness Perception
Definition 5.11: d-Neighbors
Given d ∈ N⋆ , let Nd : V → P(V ) defined as N d (i) = {j ∈ V : ∃k ≤d, (Ak )i,j > 0}. N1 (i) = Ni corresponds to (standard) neighbors of node i.
Definition 5.12: d-centered subgraph
Given d ∈ N⋆ , and a node i, the subgraph centered on node i (of order d) is
Gid = (N d (i), Ed (i)) where Ed (i) = {(j, j ′ ) ∈ E : j, j ′ ∈ N d (i)}.
Suppose that y is binary, yi ∈ {0, 1}.
Instead of a “model” m : X → [0, 1], consider a decision function h : V → [0, 1]
decision function.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

112 / 133

Network Centric Fairness Perception

Definition 5.13: Isomorphic Networks
Two subgraphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) of G are isomorphic with respect
to h : V → R if there exists a one-to-one mapping ψ : V1 → V2 such that- ∀(k, l) ∈ E1 , (ψ(k), ψ(l)) ∈ E2 ,- ∀k ∈ V1 , h(k) = h(ψ(k)).

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

113 / 133

Network Centric Fairness Perception

Definition 5.14: Isomorphic Attributed Networks
Two attributed subgraphs G1 = (V1 , E1 , X 1 ) and G2 = (V2 , E2 , X 2 ) of G are
isomorphic with respect to h : V → R if there exists a one-to-one mappingψ : V1 → V2 such that- ∀(k, l) ∈ E1 , (ψ(k), ψ(l)) ∈ E2 ,- ∀k ∈ V1 , h(k) = h(ψ(k)),and x k = 1, x 2,ψ(k) .

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

114 / 133

Network Centric Fairness Perception
Definition 5.15: Fairness Perception Function
F(i, h) associate with decision h, for some node i (on a given network G), “fairness
perception function” iflocal axiom, if h(i) = h′ (i) and ∀j ∈ N(i), h(j) = h′ (j), thenF(i, h) = F(i, h′ ),monotonicty axiom, if h(i) < h′ (i) and ∀j ∈ N(i), h(j) = h′ (j), thenF(i, h) ≤ F(i, h′ ),neighborhood expectation axiom, if h(i) = h′ (i) and ∀j ∈ N(i),h(j) ≤ h′ (j), then F(i, h) ≥ F(i, h′ ),homogeneity axiom, let Gi = (Ei , Vi ) and Gj = (Ej , Vj ) be two subgraphs, if
Gi and Gj are isomorphic with decision function h, then F(i, h) = F(j, h) @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

115 / 133

Network Centric Fairness Perception
Definition 5.16: Neighborhood Peer Expectation
Given an network G, a decision function h : V → [0, 1], and a node iyi
Ei [h] = X

1 − yi X
yj h(j) + X(1 − yj )h(j)yj j∈Ni
1 − yj j∈Ni
X

j∈Ni

j∈Ni

1
where actually, if yi = 1, Ei [h] = XXyj j∈Niyj h(j),j∈Niwhile if yi = 0, Ei [h] = X

1X

1 − yj j∈Ni

(1 − yj )h(j).

j∈Ni @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

116 / 133

Network Centric Fairness Perception
The Neighborhood Peer Expectation considers the average decision of all neighborswith the same output y .
yiEi [h] = X

1 − yi X
yj h(j) + X(1 − yj )h(j)yj j∈Ni
1 − yj j∈Ni
X

j∈Ni

j∈Ni

can we extended when considered larger networks, with d ≥ 1,
Ei,d [h] =yiXX
1 − yiyj h(j) + X(1 − yj )h(j)yj j∈N (i)1 − yj j∈N (i)Xdj∈N d (i) @freakonometrics § freakonometricsdj∈N d (i)freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

117 / 133

Network Centric Fairness Perception
Proposition 5.1: Network-Centric Fairness Perception
Given a network G = (V , E ), and a decision function h, the network-centric
fairness perception function is defined as(

F(i, h) =1 if Ei [h] ≤ h(i)0 otherwise

satisfies the locality, monotonicity, neighborhood expectation, and homogeneity
axioms, i.e. it is a fairness perception function.
More generally, function Ei [h] should satisfy
if ∀j ∈ Ni , such that h(j) = h′ (j), then Ej [h] = Ej [h′ ],if ∀j ∈ Ni , such that h(j) ≤ h′ (j), then Ej [h] ≤ Ej [h′ ],if Gi and Gj are isomorphic, with respect to h, Ei [h] = Ej [h] @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

118 / 133

Network Centric Fairness Perception
Consider an attributed network Gs = (V , E , S)
Definition 5.17: Fairness Visibility
Let Vs = {i ∈ V : S i = s}, then fairness visibility of h for group s is
F d (s, h) =1 X
Fd (i, h)#Vs i∈Vs

Definition 5.18: Fairness Visibility Parity
h satisfies fairness visibility parity, with respect to S, if
F d (s, h) = F d (s ′ , h).

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

119 / 133

Network Centric Fairness Perception
Consider some binary decision rule h : V → {0, 1},
Proposition 5.2: Asymptotic Fairness Visibility
Assuming the network graph is connected, and the decision function h has nonzero true positive and false positive rates, the fairness visibility of group Vs , basedon the neighborhood peer expectation, converges to the acceptance probability
for Vs as the d-neighborhood size increases,
F d (s, h) =1 X
F(i, h) → P[h(i) = 1|i ∈ Vs ), as d → ∞.
#Vs i∈Vs(d)Heuristically, since the graph is connected, Ni → V as d increases.
(
Fd (i, h) = 1 if h(i) = 1
For any i, ultimately,, thus consider only i ∈ Vs
Fd (i, h) = 0 if h(i) = 0
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

120 / 133

Network Centric Fairness Perception

For non-relational data, standard definition of demographic parity is
Definition 5.19: Demographic Parity
Decision function h satisfies demographic parity if
P[h(i) = 1|i ∈ Vs ) = P[h(i) = 1|i ∈ Vs ′ ).
acceptance probability for group s
Again, this definition ignores the neighborhood structure of a node.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

121 / 133

Network Centric Fairness Perception

Proposition 5.3: Local vs. Asymptotic Fairness Visibility
Even if decision function h satisfies demographic parity,
P[h(i) = 1|i ∈ Vs ) = P[h(i) = 1|i ∈ Vs ′ ),there can still be non-parity w.r.t. fairness visibility, for some d,
F d (s, h) ̸= F d (s ′ , h).

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

122 / 133

Wrap-up (?)

Group fairness is interesting, but only “distribution based”, with distributions ofm(X, S) conditional on S
Individual fairness is more interesting, by comparing outcomes from model m withcounterfactuals version of (x i , si )Perceived discrimination is more complex to analyze, individual (x i , si ) comparing
with neighbors on some attributed network (In , E , X, S)
It becomes even more complex without centralized insurance, in collaborative
insurance schemes, with peer-to-peer risk sharing

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

123 / 133

Warsaw Actuarial School 2024
The Polish Society of Actuaries
and University of Warsaw, Faculty of Economic Sciences
invite to the course

Insurance, biases, discrimination and fairness
by Prof. Arthur Charpentier (UQAM, Montréal, Canada)
Warsaw, 18-19 September 2024••

Registration will start in the middle of August• You can participate on-line or on-site• The number of on-site participants is limited to those who register first
For more information visit the site of the Polish Society of Actuaries: https://actuary.org.pl/References
Arrow, K. J. (1974). Optimal insurance and generalized deductibles. Scandinavian Actuarial Journal,
1974(1):1–42.
Atkinson, A. B. (2015). Inequality. Harvard University Press.
Barabási, A.-L. (2002). The new science of networks. Cambridge University Press.
Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. science,
286(5439):509–512.
Barocas, S., Hardt, M., and Narayanan, A. (2017). Fairness in machine learning. Nips tutorial, 1:2017.
Barocas, S., Hardt, M., and Narayanan, A. (2023). Fairness and machine learning: Limitations andopportunities. MIT press.
Bernstein, E. (2007). Temporarily Yours: Intimacy, Authenticity, and the Commerce of Sex. Universityof Chicago Press.
Bhattacharya, A. (2015). Facebook patent: Your friends could help you get a loan - or not. CNN
Business, 2015/08/04.
Bollobás, B. (1998). Random graphs. Springer.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

124 / 133References
Brown, C., Matthews, K. A., Bromberger, J. T., and Chang, Y. (2006). The relation between
perceived unfair treatment and blood pressure in a racially/ethnically diverse sample of women.
American Journal of Epidemiology, 164(3):257–262.
Burkart, N. and Huber, M. F. (2021). A survey on the explainability of supervised machine learning.
Journal of Artificial Intelligence Research, 70:245–317.
Cantwell, G. T., Kirkley, A., and Newman, M. E. (2021). The friendship paradox in real and model
networks. Journal of Complex Networks, 9(2):cnab011.
Carlier, G., Dana, R.-A., and Galichon, A. (2012). Pareto efficiency for the concave order andmultivariate comonotonicity. Journal of Economic Theory, 147(1):207–229.
Charpentier, A. (2024). Insurance: biases, discrimination and fairness. Springer Verlag.
Charpentier, A., Kouakou, L., Löwe, M., Ratz, P., and Vermet, F. (2021). Collaborative insurance
sustainability and network structure. arXiv, 2107.02764.
Cheung, K. C., Chong, W. F., and Yam, S. C. P. (2015). Convex ordering for insurance preferences.
Insurance: Mathematics and Economics, 64:409–416.
Cunningham, S. (2021). Causal inference. Yale University Press.
Dalton, H. (1920). The measurement of the inequality of incomes. The Economic Journal,30(119):348–361.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

125 / 133References
Denuit, M. and Dhaene, J. (2012a). Convex order and comonotonic conditional mean risk sharing.
Insurance: Mathematics and Economics, 51(2):265–270.
Denuit, M. and Dhaene, J. (2012b). Convex order and comonotonic conditional mean risk sharing.
Insurance: Mathematics and Economics, 51(2):265–270.
Denuit, M., Dhaene, J., Goovaerts, M., and Kaas, R. (2005). Actuarial Theory for Dependent Risks:
Measures, Orders and Models. Wiley.
Denuit, M., Dhaene, J., Goovaerts, M., and Kaas, R. (2006). Actuarial theory for dependent risks:measures, orders and models. John Wiley & Sons.
Diestel, R. (2006). Graph Theory. Springer Verlag.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012). Fairness through awareness. In
Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226.
Easley, D., Kleinberg, J., et al. (2010). Networks, crowds, and markets: Reasoning about a highly
connected world, volume 1. Cambridge University Press.
Evans, J. (2017). Optimization algorithms for networks and graphs. CRC Press.
Feng, R., Liu, C., and Taylor, S. (2023). Peer-to-peer risk sharing with an application to flood risk
pooling. Annals of Operations Research, 321(1):813–842.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

126 / 133References
Freeman, L. C. et al. (1979). Centrality in social networks: Conceptual clarification. Social network:
critical concepts in sociology. Londres: Routledge, 1:238–263.
Gibbons, A. (1985). Algorithmic graph theory. Cambridge university press.
Gilbert, E. N. (1959). Random graphs. The Annals of Mathematical Statistics, 30(4):1141–1144.
Gollier, C. and Schlesinger, H. (1996). Arrow’s theorem on the optimality of deductibles: a stochastic
dominance approach. Economic Theory, 7:359–363.
Gonzalez, D., McDaniel, M., Kenney, G. M., and Skopec, L. (2021). Perceptions of unfair treatment or
judgment due to race or ethnicity in five settings. Washington, DC: Urban Institute.
Gupta, S., Anderson, R. M., and May, R. M. (1989). Networks of sexual contacts: implications for thepattern of spread of hiv. Aids, 3(12):807–818.
Hakimi, S. L. (1962). On realizability of a set of integers as degrees of the vertices of a linear graph. i.
Journal of the Society for Industrial and Applied Mathematics, 10(3):496–506.
Hall, K. M. (1970). An r-dimensional quadratic placement algorithm. Management science,17(3):219–229.
Hardt, M., Price, E., and Srebro, N. (2016). Equality of opportunity in supervised learning. Advancesin neural information processing systems, 29:3315–3323.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

127 / 133References
Hardy, G., Littlewood, J., and G. Polya, . (1929). Some simple inequalities satisfied by convex
functions. British Mathematics Journal, 38:145–152.
Hardy, G., Littlewood, J., and Polya, G. (1934). Inequalities. Cambridge University Press.
Harris, J. M. (2008). Combinatorics and graph theory. Springer.
Havel, V. (1955). A remark on the existence of finite graphs. Časopis pro pěstovánı́’ matematiky,
80:477–480.
Hougaard, J. L. and Moulin, H. (2018). Allocation in networks. MIT Press.
Imbens, G. W. and Rubin, D. B. (2015). Causal inference in statistics, social, and biomedical sciences.
Cambridge University Press.
Jackson, M. O. (2008). Social and Economic Networks. Princeton University Press.
Kaas, R., Dhaene, J., Vyncke, D., Goovaerts, M., and Denuit, M. (2002). A simple geometric proof
that comonotonic risks have the convex-largest sum. ASTIN Bulletin, 32(1):71–80.
Kaas, R., Goovaerts, M., and Dhaene, J. (2008). Modern actuarial risk theory. Springer Science &Business Media.
Kaas, R., van Heerwaarden, A. E., Goovaerts, M. J., et al. (1994). Ordering of actuarial risks. Kluwer.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

128 / 133References
Karimi, A.-H., Barthe, G., Balle, B., and Valera, I. (2020). Model-agnostic counterfactual explanations
for consequential decisions. In International conference on artificial intelligence and statistics, pages
895–905. PMLR.
Karimi, A.-H., Schölkopf, B., and Valera, I. (2021). Algorithmic recourse: from counterfactual
explanations to interventions. In Proceedings of the 2021 ACM conference on fairness,accountability, and transparency, pages 353–362.
Karlin, S. and Novikoff, A. (1963). Generalized convex inequalities. Pacific Journal of Mathematics,
13:1251–1279.
Kearns, M. and Roth, A. (2019). The ethical algorithm: The science of socially aware algorithm
design. Oxford University Press.
Kusner, M. J., Loftus, J., Russell, C., and Silva, R. (2017). Counterfactual fairness. In Advances in
Neural Information Processing Systems, pages 4066–4076.
Lee, A. J. (2019). U-statistics: Theory and Practice. CRC Press.
Luong, B. T., Ruggieri, S., and Turini, F. (2011). k-nn as an implementation of situation testing fordiscrimination discovery and prevention. In Proceedings of the 17th ACM SIGKDD international
conference on Knowledge discovery and data mining, pages 502–510.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

129 / 133References
Marshall, A. W. and Olkin, I. (1979). Inequalities: Theory of Majorization and its Applications, volume143. Academic Press.
Martı́nez Perı́a, F. D., Massey, P. G., and Silvestre, L. E. (2005). Weak matrix majorization. Linear
Algebra and its Applications, 403:343–368.
McPherson, M., Smith-Lovin, L., and Cook, J. M. (2001). Birds of a feather: Homophily in social
networks. Annual review of sociology, 27(1):415–444.
Meyer, R. (2015). Could a bank deny your loan based on your facebook friends? The Atlantic,
2015/09/25.
Morris, M. (1995). Data driven network models for the spread of infectious disease. Epidemic models:
their structure and relation to data, 5:302–22.
Muirhead, R. F. (1903). Some methods applicable to identities and inequalities of symmetric algebraic
functions of n letters. Proceedings of the Edinburgh Mathematical Society, 21:144–162.
Müller, A. and Stoyan, D. (2002). Comparison methods for stochastic models and risks.
Newman, M. (2018). Networks. Oxford university press.
Newman, M. E. (2003). Mixing patterns in networks. Physical review E, 67(2):026126.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

130 / 133References
Newman, M. E. (2012). Communities, modules and large-scale structure in networks. Nature physics,
8(1):25–31.
Newman, M. E. and Girvan, M. (2004). Finding and evaluating community structure in networks.
Physical review E, 69(2):026113.
Ohlin, J. (1969). On a class of measures of dispersion with application to optimal reinsurance. ASTIN
Bulletin: The Journal of the IAA, 5(2):249–266.
Pascoe, E. A. and Richman, L. S. (2009). Perceived discrimination and health: a meta-analytic review.
Psychological Bulletin, 135(4):531.
Pass, R. (2019). A Course in Networks and Markets: Game-theoretic Models and Reasoning. MIT
Press.
Pearl, J. and Mackenzie, D. (2018). The book of why: the new science of cause and effect. Basic
books.
Peel, L., Peixoto, T. P., and De Domenico, M. (2022). Statistical inference links data and theory in
network science. Nature Communications, 13(1):6794.
Rothschild, M. and Stiglitz, J. E. (1978). Increasing risk: I. a definition. In Uncertainty in economics,
pages 99–121. Elsevier.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

131 / 133References
Rudin, C. (2019). Stop explaining black box machine learning models for high stakes decisions and use
interpretable models instead. Nature machine intelligence, 1(5):206–215.
Rüschendorf, L. (2013). Mathematical risk analysis. Springer.
Schmitt, M. T., Branscombe, N. R., Postmes, T., and Garcia, A. (2014). The consequences ofperceived discrimination for psychological well-being: a meta-analytic review. Psychological bulletin,
140(4):921.
Shaked, M. and Shanthikumar, J. G. (2007). Stochastic orders. Springer.
Shalmani, F. M. (2021). Fairness in Social Network Analysis: Measures and Algorithms. Michigan
State University PhD Thesis.
Shrum, W., Cheek Jr, N. H., and MacD, S. (1988). Friendship in school: Gender and racial homophily.
Sociology of Education, pages 227–239.
Trudeau, R. J. (1993). Introduction to graph theory. Dover Publications.
Van Houtven, C. H., Voils, C. I., Oddone, E. Z., Weinfurt, K. P., Friedman, J. Y., Schulman, K. A.,
and Bosworth, H. B. (2005). Perceived discrimination and reported delay of pharmacy prescriptions
and medical tests. Journal of general internal medicine, 20:578–583.
Viger, F. and Latapy, M. (2005). Fast generation of random connected graphs with prescribed degrees.
arXiv, 0502085.
 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

132 / 133References

Wu, X.-Z., Percus, A. G., and Lerman, K. (2017). Neighbor-neighbor correlations explain measurement
bias in networks. Scientific Reports, 7(1):5576.
Yamaguchi, K. (1990). Homophily and social distance in the choice of multiple friends an analysis
based on conditionally symmetric log-bilinear association models. Journal of the American
Statistical Association, 85(410):356–366.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. (2013). Learning fair representations. In
International Conference on Machine Learning, pages 325–333.

 @freakonometrics § freakonometrics

freakonometrics.hypotheses.org – Arthur Charpentier, 2024 (IME Workshop)

133 / 133