One-way flow network formation under constraints

Abstract

We study the effects of institutional constraints on stability and efficiency in the “one-way flow” model of network formation. In this model the information that flows through a link between two players runs only towards the player that initiates and supports the link, so in order for it to flow in both directions, both players must pay whatever the unit cost of a directional link is. We assume that an exogenous “societal cover” consisting of a collection of possibly overlapping subsets covering the set of players specifies the social organization in different groups or “societies,” so that a player may initiate links only with players that belong to at least one society that he/she also belongs to, thus restricting the feasible strategies and networks. In this setting, we examine the impact of such societal constraints on stable/efficient architectures and on dynamics.

Appendix

Proof of Proposition 4

(i) Consider first the case of a linear cover with two societies, $\mathcal{K}= \{ A,B \}$, whose intersection is non-empty. We prove that starting from any $\mathcal{K}$-network g there is a positive probability of transiting to a strict Nash $\mathcal{K}$-network (absorbing state in the Markov process) in finite time. As there is a positive probability at each period that all but one agent will exhibit inertia, it suffices to see that starting from any $\mathcal{K}$-network there is a finite sequence of players’ best responses that leads to a strict Nash $\mathcal{K}$-network. To that end, take a player i ₁ in A∖B, let him/her play a best response and let g ¹ denote the resulting $\mathcal{K}$-network where i ₁ observes at least all players in A.

First step: Form a wheel containing all nodes in A.

Take a player i ₂ furthest away in A from i ₁ in g ¹ (i.e., the/a player in A for which the length of the shortest path $i_{2}\overset{g^{1}}{\rightarrow}i_{1}$ is the greatest). This means that i ₁ observes all players in A without using any of i ₂’s links; otherwise a player other than i ₂ would be furthest away in A from i ₁. There is then a best response of i ₂ where $\overset{\leftarrow}{i_{2}i_{1}}$ is the only link with a player in A (if i ₂∈A∩B such a best response may include some other links with player in B∖A). Let i ₂ play that best response (or “play inertia” if it was his/her current strategy¹⁴), and let g ² denote the resulting $\mathcal{K}$-network. Note that in g ² node i ₁ still observes all nodes in A. Now we describe the induction step from a current network g ^k and a sequence of players in A, i ₁,i ₂,…,i _k , such that each player i _r (r=2,…,k) supports with i _r−1 the only link with players in A, and i ₁ observes all players in A. Let i _k+1 be the player furthest away in A from i _k in g ^k. Again, this means that i _k+1 observes all players in A without using any of i _k ’s links. There is then a best response of i _k+1 in which his/her only link with a node in A is the link with i _k , and i ₁ still observes all nodes in A. Repeat until {i ₀,i ₁,i ₂,…,i _k }=A. At this stage agent i ₁ observes all nodes in A∪B and he/she is the only node in A with possibly more than one link, then a best response of his/her is to form only one link with i _k and delete all others. At the end of this all players in A form a wheel and observe all players in A∪B.

Second step: Form an “8” consisting of this wheel containing all players in A and another one containing all players in B∖A and one player in A∩B.

Take a player j ₁ in A∩B that is linked by a player in A∖B (at least one must exist). Let j ₂ be the player in B∖A furthest away from j ₁. Let j ₂ play the best response consisting of forming a single link with j ₁. By reiterating this process a sequence j ₁,j ₂,…,j _l is formed where {j ₂,…,j _l }⊂B∖A and each node j _r (r=2,…,l) supports the only link with j _r−1, and j ₁ still observes all players in A∪B. Repeat until {j ₂,…,j _l }=B∖A. At this stage player j ₁ is the only one with possibly more than one link with players in B∖A and a best response of his/her is to form a single link in B∖A with j _l and keep the one with a player in A∖B. At the end of this we have a wheel containing all players in B∖A and player j ₁. Therefore this wheel and the one formed in the previous step form the desired “8”. If A∩B={j ₁} the network obtained is a strict Nash $\mathcal{K}$-network, otherwise:

Third step: We show that a sequence of best responses leads to two wheels, one containing all players in A, the other containing all players in B and both sharing a sequence of links containing all those in A∩B.

Remember that j ₁ was followed (i.e., linked) by a player in A∖B. Let i _r be the first player after j ₁ in the sequence in A∩B, and let i _r′ be the first player after i _r in this sequence that is followed (i.e., linked) by a player in A∖B. Now we describe a sequence of best responses: first, j ₂ deletes his/her link with j ₁ and links with i _r′; second, the player in A∖B that links i _r′ deletes this link and links with the player in A∖B that is linked by i _r ; third, let i _r delete his/her link and link j ₁; fourth, let the player linking with j ₁ delete his/her link and link with i _r′. After these four best response movements, the reader may check that we have two wheels, one containing all players in B∖A, the other containing all those in A, and both sharing the sequence j ₁,i _r ,…,i _r′, where each of these nodes links with the preceding one. If this sequence contains all players in A∩B, we have the desired pair of wheels; otherwise, repeat these four steps starting at i _r′ instead of at j ₁. By reiterating this process we obtain a pair of wheels as desired.

Fourth step: Form an all-encompassing wheel.

Relabel by k ₁,…,k _m , the sequence consisting of all players in A∩B, where each of these players links with the preceding one. Again we give a sequence of best responses. Let j be the player in B∖A who links k _m . Let j replace his/her link with k _m by a link with k ₁. We again have an “8” in which two wheels interconnect at k ₁, but now all players in A∩B are consecutively linked. This allows the following sequence of best responses. Let k ₂ replace his/her link with k ₁ by a link with the player, say j′, in B∖A linked by k ₁. Then k ₁ can delete his/her link with j′. Now, k ₃ replaces his/her link with k ₂ by a link with j′, and subsequently k ₂ can delete his/her link with j′. Reiterate this till k _m replaces the link with k _m−1 by a link with j′, and k _m−1 deletes his/her link with j′. At this stage an all-encompassing wheel is formed.

Now consider a linear societal cover of the form $\mathcal{K}=\{A_{i}\}_{i=1,2,\ldots,m}$, where for all i=1,2,…,m−1, A _i ∩A _i+1≠∅, and in all other cases two societies do not intersect. Then start at A ₁, take a player in A ₁∖A ₂ and form a wheel containing all players in A ₁ proceeding as in the first step. Then, take a player in A ₁∩A ₂ that is linked by a player in A ₁∖A ₂ and, proceeding as in the second step, form an “8” consisting of the wheel containing all players in A ₁ and another containing all players in A ₂∖A ₁ and the player chosen in A ₁∩A ₂. Then, following steps 3 and 4 (unless there is a unique player in A ₁∩A ₂), form a wheel containing all players in A ₁∪A ₂. At this stage all players in this wheel observe at least all players in A ₁∪A ₂∪A ₃. Iterate this process, now taking a player in A ₂∩A ₃, etc., until an all-encompassing wheel is completed (when no hinge-player exists) or a sequence of wheels (in this case contacting at strong hinge-players at the intersection of two consecutive societies) forming a strict Nash $\mathcal{K}$-network. Observe that in both cases a unique strict Nash architecture exists and therefore the dynamic process converges to efficiency.

(ii) Consider a cover in wheel of the form $\mathcal{K}=\{A_{i}\}_{i=1,2,\ldots,m}$ s.t. for all i=1,2,…,m−1, A _i ∩A _i+1≠∅, and A ₁∩A _m ≠∅, and in all other cases two societies do not intersect. Now proceed as in the linear case starting at any society, say A _r . Take a player i ₁ in A _r ∖A _r−1. Let him/her play a best response. Now, i ₁ observes at least all players in A _r . Form a sequence of players in A _r as described inductively. Let i ₁,i ₂,…,i _k (k≥1) be the sequence formed up to step k. Let i _k+1 be the player furthest away in A _r from i _k and let i _k+1 play a best response in which his/her only link in A _r is the link with i _k , if such a best response exists,¹⁵ and reiterate this step as far as such a best response exists until a wheel containing all players in A _r is formed. Otherwise (i.e., if at some point before the wheel is formed i _k+1 has no such best response), let him/her play any best response. This best response should include a link with a player, say $i_{1}^{\prime}$, either in A _r−1∖A _r or A _r+1∖A _r . Now recommence a sequence starting at $i_{1}^{\prime}$ from the current network. It can be seen that by reiterating this process a wheel will be formed including all nodes in a society,¹⁶ unless a strict Nash $\mathcal{K}$-network is formed in the process. Without loss of generality assume that the wheel has been formed in A ₁. Now proceed as in step 2, by picking a player j ₁ in A ₁∩A ₂ linked by a node in A ₁∖A ₂ and forming a sequence of players in A ₂∖A ₁ as described inductively. Let j ₁,j ₂,…,j _k (k≥1) be the sequence formed up to step k. Let j _k+1 be the player furthest away in A ₂∖A ₁ from j _k in the current network and let j _k+1 play a best response where the only link that he/she has in A ₂ is the link with j _k , if such a best response exists, and reiterate this step as far as such a best response exists until a wheel containing all players in A ₂∖A ₁ and node j ₁ is formed. Otherwise, step 2 must be recommenced by picking a player in A ₁∩A _m linked by a player in A ₁∖A _m until a wheel containing all players in A _m ∖A ₁ and the chosen one in A ₁∩A _m is formed. It can be checked that now he formation of this wheel cannot be hindered by the non-existence of the desired best response. Now proceed as in the linear case (steps 3 and 4 apply unchanged) up to the completion of a wheel or a sequence of wheels (in this case contacting at isolated players at the intersection of two consecutive societies) including all players in all societies but one, say A _r . Note that now all players except possibly some in A _r ∖(A _r+1∪A _r−1) observe all players in N. Now proceed once more as in step 2, by picking a player in A _r−1∩A _r linked by a player in A _r−1 and forming a wheel with all players in A _r ∖(A _r+1∪A _r−1) and the chosen one in A _r−1∩A _r . Then, unless A _r−1∩A _r is a singleton, apply steps 3 and 4 to merge this wheel with the one including all players in A _r−1. At this stage, some players at A _r ∩A _r+1 may support some unnecessary links with players in A _r ∖A _r+1. Finally, let these players play best responses and delete these links, then a strict Nash $\mathcal{K}$-network consisting of either an all-encompassing wheel or a sequence of wheels containing all players is formed. Only in the first case the resulting $\mathcal{K}$-network is efficient.

(iii) Finally, if the core of a societal cover $\mathcal{K}$ contains at least as many players as there are societies in $\mathcal{K}$, it is not difficult to adapt the proof, “expanding” an initial wheel containing all players in a society. A sufficient number of players within the core ensures that all such expansions are feasible and necessarily lead to an all-encompassing wheel. Therefore the dynamic process converges to an efficient $\mathcal{K}$-network. □