The Social Climbing Game

Abstract

The structure of societies depends, to some extent, on the incentives of the individuals they are composed of. We study a stylized model of this interplay, that suggests that the more individuals aim at climbing the social hierarchy, the more society’s hierarchy gets strong. Such a dependence is sharp, in the sense that a persistent hierarchical order emerges abruptly when the preference for social status gets larger than a threshold. This phase transition has its origin in the fact that the presence of a well defined hierarchy allows agents to climb it, thus reinforcing it, whereas in a “disordered” society it is harder for agents to find out whom they should connect to in order to become more central. Interestingly, a social order emerges when agents strive harder to climb society and it results in a state of reduced social mobility, as a consequence of ergodicity breaking, where climbing is more difficult.

Appendix: Ergodicity of the Dynamics

Let Γ ^C(N,M) be the space of connected graphs with N vertices and M edges. In order to prove ergodicity, we have to show that, with a finite number of basic moves, we can reach any connected graph in Γ ^C(N,M), starting from another arbitrary graph in the same set. Before delving into the technical details, we give a simple intuitive sketch of this proof.

For a finite value of β, the dynamics consists of reversible moves as the one depicted in Fig. 9; such moves can be thought of as a “sliding” of the edge e _ik on the path of length one (k,j) from vertex k to vertex j. The key observation to prove the ergodicity by induction is that, since the graph is finite and connected, there always exists a path of minimum length that connects two arbitrarily chosen vertices in the graph. Then, we can proceed in three steps.

• 1. Let there be two graphs in Γ ^C(N,M) which differ from each other only by an edge incident on the same vertex, v _k . We first prove that by means of basic moves, we can transform one into the other. To do so, it suffices to slide the edge along the path that connects the other end of the edge, which we know to exist because the graph is connected (Proposition 1, Proposition 2).

• 2. Let there be two graphs in Γ ^C(N,M) that differ by an edge with arbitrary ends. By applying the previous step twice, we show that there exists a finite set of moves that allows us to reach one configuration starting from the other (Proposition 3).

• 3. Finally, let there be two arbitrary graphs in Γ ^C(N,M). Moving one edge at time, we show by induction that it is possible to reach one graph starting from the other with a finite number of moves. Thus, the ergodicity is proved (Proposition 4).

Fig. 9

The rewiring move (c-swap) of the dynamics

We now proceed with the detailed proof.

Definition 1

(c-swap)

Let us choose a labeling for the space of vertices V={v ₁,…,v _N } and an induced labeling for the edges E={e _ij } where e _ij =e _ji =(v _i ,v _j ) denotes the undirected edge between v _i and v _j . Let us define a transformation $\sigma_{ij}^{ik}: \varGamma^{C}(N,M) \mapsto\varGamma^{C}(N,M)$, called corner swaps (c-swaps), as following

$$ \sigma_{ij}^{ik}(\mathcal{G})=\mathcal{G}'= \bigl(V,E'\bigr) $$

(8)

such that

$$ E'= \begin{cases} ( E \setminus\{ e_{ik} \} ) \cup\{ e_{ij} \} & \text{if } (e_{kj}, e_{ik}\in E)\wedge( e_{ij} \notin E) \\ E & \text{otherwise}. \end{cases} $$

(9)

Proposition 1

Let $\mathcal{G}=(V,E)$ and $\mathcal{G}'=(V,E')$ be two graphs in Γ ^C(N,M) that differ by an edge incident on the same vertex, i.e. |E|=|E′|=M, |E′∩E|=M−1, E∖E′={e _ik } and E′∖E={e _ij }, and such that the shortest path P from v _k to v _j does not contain neither v _i nor any of its neighbors.

There exists an integer l and a finite sequence of graphs in Γ ^C(N,M), $\mathcal{G}^{n}$ such that:

• (i) $\mathcal{G}=\mathcal{G}^{0}$ and $\mathcal{G}'=\mathcal{G}^{l}$.

• (ii) For all 0≤n<l there exist adjacent vertices $v_{k_{n}}$,$v_{k_{n}+1}$ such that $\mathcal{G}^{n+1}=\sigma_{i k_{n+1}}^{i k_{n} } (\mathcal{G}^{n})$, where k ₀=k and k _l =j.

Proof

Let l be the length of P.

Let $v_{k_{1}}$ be the unique neighbor of v _k that lies in P. If we set $\mathcal{G}^{1}=\sigma_{i k_{1}}^{i k} ( \mathcal{G})$, the c-swap reduces the distance between v _i and v _j , since the neighbor of v _k that lies in P must have a distance l−1 from v _j . We reiterate the procedure on $\mathcal{G}^{1}$ and obtain in such a way a sequence of graphs that satisfies property (ii). Now, since at any step the length of P diminishes by 1, after the l-th step, in the graph $\mathcal{G}^{l}$ v _i and v _j will be neighbors. Thus, since no other edge was changed by applying c-swaps, $\mathcal {G}^{l}=\mathcal{G}'$ proving property (i). □

Proposition 2

Let $\mathcal{G}=(V,E)$ and $\mathcal{G}'=(V,E')$ be two graphs in Γ ^C(N,M) which differ by an edge incident on the same vertex, i.e. |E|=|E′|=M, |E′∩E|=M−1, E∖E′={e _ik } and E′∖E={e _ij }.

There exist an integer l and a finite sequence of graphs in Γ ^C(N,M), $\mathcal{G}^{n}$ such that:

• (i) $\mathcal{G}=\mathcal{G}^{0}$ and $\mathcal{G}'=\mathcal{G}^{l}$.

• (ii) For all 0≤n≤l there exist adjacent vertices $v_{k_{n}}$,$v_{k_{n}+1}$ such that $\mathcal{G}^{n+1}=\sigma_{i k_{n+1}}^{i k_{n}} (\mathcal{G}^{n})$.

Proof

Let P be the shortest path in $\mathcal{G}$ from v _k to v _j that does not contain (v _k ,v _i ).

There are four possible cases:

• (i) P does not contain neither v _i nor any of its neighbors other than v _k . The thesis is proven applying Proposition 1 directly to P.

• (ii) P contains v _i . Let P ₁ be the shortest path from v _k to v _i that does not contain the edge (v _k ,v _i ). Let P ₂ be the shortest path from v _i to v _j , clearly P=P ₁⊕P ₂, where ⊕ is the path concatenation. Since by construction there are no neighbors of v _k in P ₂ (otherwise P would not contain v _i ) we can apply Proposition 1 and reach $\mathcal {G}''=(V,(E\setminus \{e_{ki}\})\cup\{e_{kj}\})$; on the other hand there cannot be neighbors of v _j in P ₁ (otherwise there would be a shortest path not containing v _i ) and thus applying again Proposition 1 along P ₁ we reach $\mathcal{G}'$ proving the thesis.

• (iii) P does not contain v _i but two of its neighbors, c and f such that c≠v _k , f≠v _k and |c,v _k |<|f,v _k |, where |⋅,⋅| represents the graph distance between two vertices. We first note that c and f must be neighbors, otherwise P should include v _i . Then, as in case (ii), by minimality we can write P=P ₁⊕(c,f)⊕P ₂ where P ₁ is the shortest path from v _k to c and P ₂ is the shortest path from f to v _j . It is easy to see that Q ₂=(v _i ,f)⊕P ₂ is a shortest path from v _i to v _j : if it were not so, there would exist a path $Q_{2}'$ from v _i to v _j strictly shorter than Q ₂, but in that case $P_{1}\oplus(c,v_{i})\oplus Q_{2}'$ would be a shortest path from v _k to v _j containing v _i , in contradiction with our hypotheses. A similar argument holds for Q ₁. As before, since, by minimality, there cannot be neighbors of v _k in P ₂, it is possible to reach the graph $\mathcal{G}''=(V,(E\setminus\{e_{ki}\})\cup\{e_{kj}\})$ by applying Proposition 1 to Q ₂; since by minimality there cannot be neighbors of v _j in P ₁, we can apply Proposition 1 to $\mathcal{G}''$ along Q ₂ and reach $\mathcal{G}'$ proving the thesis.

• (iv) The shortest path P contains only one neighbor of v _i other than v _k , let us call it m. As before, P=P ₁⊕P ₂ where P ₁ is the shortest path from v _k to m and P ₂ is the shortest path from m to v _j . Since by construction there cannot be other neighbors of i in P ₂, we can apply Proposition 1 to P ₂ and reach the graph $\mathcal{G}^{*}=(V,(E\setminus\{e_{im}\})\cup\{e_{ij}\})$. On the other hand, by construction there cannot be neighbors of v _i in P ₁ other than v _k and thus we can apply Proposition 1 to P ₂ and reach $\mathcal{G}'$ proving the thesis.

 □

Proposition 3

Let $\mathcal{G}=(V,E)$ and $\mathcal{G}'=(V,E')$ be two graphs in Γ ^C(N,M) such that |E|=|E′|=M and |E∩E′|=M−1. Let us assume that, in particular, E={e _ij }∪(E∩E′) and E′={e _hk }∪(E∩E′).

Thus there exists an integer l and a finite sequence of graphs in Γ ^C(N,M), $\mathcal{G}^{n}$ such that:

• (i) $\mathcal{G}=\mathcal{G}^{0}$ and $\mathcal{G}'=\mathcal{G}^{l}$.

• (ii) For all 0≤n<l there exist adjacent vertices $v_{k_{n}}$,$v_{k_{n}+1}$ such that $\mathcal{G}^{n+1}=\sigma_{i k_{n+1}}^{i k_{n}} (\mathcal{G}^{n})$.

Proof

Let us define the graph $\mathcal{G}''=(V,E'')$ such that E″=(E∖{e _ij })∪{e _ih }. Applying Proposition 2 first to graphs $\mathcal{G}$ and $\mathcal{G}''$ and then to graph $\mathcal{G}''$ and $\mathcal{G}'$ proves the thesis. □

Definition 2

(g-swap)

Let $\mathcal{G}=(V,E)$ and $\mathcal{G}'=(V,E')$ be two graphs in Γ ^C(N,M) which differ at most by an edge, that is such that |E|=|E′|=M and |E∩E′|=M−1. Let us assume that, in particular, E={e _ij }∪(E∩E′) and E′={e _hk }∪(E∩E′).

We define a global swap or g-swap of the edge e _ij to the edge e _hk a transformation such that:

$$ \mathcal{G}'=\varSigma_{ij}^{hk}(\mathcal{G}). $$

(10)

Proposition 3 simply states that any global swap can be obtained as the composition of a minimal set of corner swaps between adjacent vertices.

Proposition 4

Let $\mathcal{G}=(V,E)$ and $\mathcal{G}=(V,E')$ be two graphs in Γ ^C(N,M). There exists an integer d and a sequence of graphs $\mathcal{G}^{n}(V, E_{n})$ in Γ ^C(N,M) such that:

• (i) $\mathcal{G}=\mathcal{G}^{0}$ and $\mathcal{G}'=\mathcal{G}^{d}$.

• (ii) For all 0≤n<d there exist four vertices v _i , v _j ,v _h and v _k such that $\mathcal{G}^{n+1}=\varSigma _{ij}^{hk}(\mathcal{G}^{n})$.

Proof

Let $\mathcal{Z}=(V,Z=E\cap E')$, and let us define δ=|Z|. We proceed by induction on the number δ.

Base case :

If δ=M−1, the Thesis is trivially true because of Proposition 3.

Inductive step :

Let us assume that the Thesis holds for δ=M−d, we want to show that this implies that it also holds for δ=M−d−1, with d<M−1. Let us assume that $\mathcal {G}= (V,E)$ and $\mathcal{G}' = (V,E')$ are such that |E′∩E|=M−d−1. Let e _ij ∈E∖(E∩E′) and e _hk ∈E′∖(E∩E′). Moreover, let E″=(E∖{e _ij })∪{e _hk }. By construction, |E∩E″|=M−1 and |E′∩E″|=M−d. Finally, let $\mathcal{G}''= (V,E'')$. Since $\mathcal{G}''$ and $\mathcal{G}'$ differ by M−d edges, by inductive assumption there exists a sequence $\mathcal{G}^{i}$, with i∈[0,d], such that $\mathcal{G}^{0} = \mathcal{G}'$ and $\mathcal{G}^{d} = \mathcal{G}''$, that satisfies the Thesis. Moreover, by Proposition 3, there exists a g-swap such that $\mathcal{G}= \varSigma _{hk}^{ij}(\mathcal{G}'')$. Thus, the complete sequence $\mathcal {G}'=\mathcal{G}^{0},\mathcal{G}^{1},\ldots,\mathcal{G}''=\mathcal {G}^{d},\mathcal{G}=\mathcal{G}^{d+1}$ satisfies the Thesis.

 □

Proposition 4 and Proposition 3 state simply that any two connected graphs with the same number of edges can be obtained one from the other applying a finite sequence of c-swaps. Moreover, since the number of edges is finite, then there must be a minimal sequence of c-swaps that connects any two of such graphs. Since, for finite β, all c-swaps are allowed with nonzero probability, this proves the ergodicity.