Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
111,792 characters · 23 sections · 139 citation commands
An optimal test for strategic interaction in social and economic network formation between heterogeneous agents
JEL Codes: C31, C57
Keywords: Network formation, Locally Best Tests, Similar Tests, Exponential Family, Incomplete Models, Degree Heterogeneity, Homophily, Binary Matrix Simulation, Edge Switching Algorithms
\pagenumbering{arabic} \onehalfspacing
In an economic model of (directed) network formation agents purposefully direct links to one another in order to maximize utility. Specifically, a payoff function maps all possible network configurations into agent utilities. Agents use this payoff function to weigh the benefits of directing any particular link against the costs of doing so. A Nash Equilibrium (NE) network arises when all agents link choices are individually optimal given the choices made by other agents Bala_Goyal_EM00.
Important examples of such processes include firms choosing their suppliers Atalay_et_al_PNAS11, adolescents choosing friends Christakis_et_al_Book2020, banks engaging in interbank lending to meet statutory reserve requirements Boss_et_al_QF2004, and village households choosing partners for risk-sharing deWeerdt_IAP04. Jackson_et_al_JEL17 present many other examples of networks in economics. Such data abound in the other social sciences as well Apicella_et_al_Nat12.
The utility an agent receives when she directs a link to another agent can be usefully divided into two components.\footnote{In digraphs, or directed networks, it is customary to refer to edges as “arcs". Here we use the terms link, edge, arc, friendship, relationship etc. interchangeably.} The first component is “private", or, more precisely, invariant to the presence or absence of other links in the network.\footnote{Note “other links" include those possibility directed by the sending agent to targets other than the one at hand. An alternative to the “private" nomenclature would be “dyadic" or “direct".} The second component is “social", or varying with the presence or absence of other links in the network.
An example of the first component is the payoff associated with a homophilous link McPherson_et_al_ARS01. This payoff component only depends on the attributes of the sending (ego) and receiving (alter) agents. Another example is associated with “degree heterogeneity": agents may vary systematically in their propensity to direct links, or in their attractiveness as link targets for others. Finally we might posit that the payoff from any particular link varies for idiosyncratic reasons, as in other random utility models (RUMs) of discrete choice McFadden_FinE74. Empirical models of network formation with these features were introduced by Charbonneau_EJ17, Graham_EM17, Dzemski_RESTAT18, Jochmans_JBES18 and Yan_et_al_JASA18. These models are fundamentally dyadic: agents' network payoffs are a simple sum of link-specific payoffs and, crucially, invariant to the linking behavior of other agents.
In some settings, however, agents may also value indirect links. For example, an arc from $j$ to $k$ may incidentally reduce the shortest path length from $i$ to $k$, allowing agent $i$ better access to $k$'s information Jackson_Wolinsky_JET96, Bala_Goyal_EM00. While arc $jk$ is valued by $i$, this value is not incorporated into $j$'s decision to direct the arc or not. Preferences of this type mean agents' decisions impose externalities on others. The detection of such externalities is the subject of this paper.
Payoff functions with externalities feature prominently in formal theoretical models of network formation Jackson_NetBook08, Goyal_Book2021. Equilibrium in network formation models with externalities may be analyzed using the tools of game theory. Indeed such models are typically called strategic network formation models. In what follows we say a network formation model is strategic if agents value indirect links or, equivalently, their optimal linking strategy varies with the linking behavior of others.
When links made by one agent alter the incentives for link formation faced by others, equilibrium network configurations may diverge from socially optimal ones Goyal_Book2021. This, in turn, suggests that well-designed interventions might make agents better off. In contrast, without a wedge between the private and social benefits of link formation, equilibrium and socially optimal networks will coincide. This paper introduces a test for whether agents' own incentives to form links vary with the choices of others. A rejection of our test, under the maintained model, indicates the presence of externalities, with their attendant implications for optimal policy design.
Strategic network formation games are complicated. In a directed network with $N$ agents, there are $2^{N(N-1)}$ possible action profiles or network configurations; many of which may be Nash Equilibria (NE). In the seminal model of directed network formation introduced by Bala_Goyal_EM00, for example, with $N=5$ agents there are $1,069$ NE networks. Because of this combinatoric complexity, methods pioneered for the econometric analysis of discrete games with just a few players are not directly applicable -- at least in practice -- to network formation games.
In recent work, Christakis_et_al_Book2020, Mele_EM17, Miyauchi_JOE16, dePaula_et_al_EM18 and Sheng_EM20 each proposed empirical models of strategic network formation.\footnote{dePaula_ARE2020 surveys work in this area and provides additional references.} Each of these models impose particular restrictions on the form of the network payoff function, the nature of any unobserved heterogeneity, and/or make assumptions about equilibrium selection. Even with these restrictions, estimating the identified set for the parameters indexing the network payoff function in these models is challenging, as is conducting inference.\footnote{We wish to emphasize that these “critiques" reflect the inherent difficulty of the problem, not any deficiencies in the above cited papers. Indeed these researchers have shown considerable ingenuity in proposing ways to make methods designed for games with just a few players scale to the considerably more complicated many-player network setting.}
In this paper we introduce an econometric model of strategic network formation which, we believe for the first time, simultaneously allows (i) for agents to value both direct and indirect links, (ii) for the systematic returns to link formation to vary with observed dyad attributes, and (iii) for unobserved agent-specific correlated degree heterogeneity. Our setup maps neatly into the “costs versus benefits" payoff structures emphasized in theoretical models of strategic network formation (see, for example, Jackson_NetBook08 and Goyal_Book2021). Examples of models -- suitably enriched to include covariates, unobserved heterogeneity, and random link utility -- encompassed by our framework include the “connections" model Jackson_Wolinsky_JET96, Bala_Goyal_EM00, “structural hole" or “bridging" models Goyal_Vega-Redondo_JET2007, Kleinberg_et_al_ACM2008 and the favor exchange or “supported links" model of Jackson_et_al_AER12. We can also accommodate tastes for reciprocity, transitivity, network centrality and other forms of indirect link valuation.
We begin with the baseline dyadic logistic regression model for directed networks introduced by Charbonneau_EJ17.\footnote{Although the dissertation from which Charbonneau_EJ17 was drawn appears to be the first formal analysis of the dyadic logit model (especially in terms of exploring the implications of its exponential family structure for estimation), its use in empirical work arose earlier. For example, in the empirical network analysis of deWeerdt_IAP04; see also Holland_Leinhardt_JASA81.} This model is useful for modelling homophily and degree heterogeneity. We then augment this model with a network payoff term which additionally allows agents to value indirect links. The resulting model is quite complicated. Formally it is a very large complete information simultaneous move game. While we assume that the observed network is a NE, we make no auxiliary equilibrium selection assumptions.\footnote{More precisely the observed network is either a pure strategy NE or in the support of a mixed strategy NE (in fact our results hold under an even weaker notion of equilibrium, as explained below).}
Let $K$ be the number of support points in the distribution of observed agent attributes and $N$ the number of agents in the network. Our model includes (i) $K^2$ “homophily" parameters, $\Lambda\overset{def}{\equiv}\left[\lambda_{kl}\right]$ for $k,l=1 \dots K$, capturing how link returns vary systematically with ego and alter attributes, (ii) two $N \times 1$ parameter vectors $\mathbf{A}\overset{def}{\equiv}[A_i]$ and $\mathbf{B}\overset{def}{\equiv}[B_i]$ for $i=1 \dots N$, capturing, respectively, agent-specific out- and in-degree heterogeneity, and (iii) a scalar parameter, $\gamma$, measuring the extent to which agents value indirect links. Our model also includes (iv) an “equilibrium selection" function. Since we are agnostic about which NE is selected in the presence of multiple equilibria, this function is not specified by the analyst, but enters our analysis abstractly (see Theorem (ref) below).
We treat $\delta=(\Lambda',\bf{A}',\bf{B}')'$ as a (high dimensional) nuisance parameter and the equilibrium selection mechanism as a nuisance function.\footnote{This function assigns probabilities to all NE equilibria for every possible realization of the random utility shocks.} This focuses our attention solely on $\gamma$. While, in principle, an analysis of the identified set for $\gamma$ might be possible, we instead focus on the one-sided hypothesis of $H_0:\gamma=0$ versus $H_1:\gamma>0$. Or, put differently, we identify the sign of $\gamma$.\footnote{Our focus on one-sided hypotheses results in a particularly clean exposition and analysis, allows for the statement of some optimality results, and covers our main examples of interest. However, as will be apparent, our basic set-up extends naturally to two-sided hypotheses.}
Our test involves comparing a statistic of the observed network (e.g., its transitivity index) with a critical value derived from a reference distribution. Natural questions are: (i) which reference distribution? (ii) how do I compute the critical value? (iii) which network statistic should I use? We provide answers to all three of these questions.
There is a long tradition in empirical work of using the \"{E}rdos-R\'{e}nyi model to generate the reference distribution. This invariably results in “straw man" tests since few real world networks are well described by the \"{E}rdos-R\'{e}nyi model. To avoid spurious rejection of the null of no strategic interaction ($H_0:\gamma=0$) it is therefore important to have a rich null model; one that might actually describe real world networks. Charbonneau_EJ17 provides an easy to interpret, random utility based, and “credible" null model.\footnote{The Charbonneau_EJ17 model can match any observed in- and out-degree sequence as well as rich patterns of homophilous linking. This is important since heavy-tailed degree distributions characterize many real world networks, as does homophily Barabasi_Book16, McPherson_et_al_ARS01.},\footnote{An analogy: consider the challenge of determining whether persistence in panel data is due to state-dependence or unobserved heterogeneity (or both). Any credible test for state dependence needs to include as part of its null a correct specification of unobserved agent-specific heterogeneity Chamberlain_LALMD85.}
Because $\delta$ may range freely across its parameter space when $\gamma=0$ our null hypothesis is a composite one. Test size equals the supremum of the rejection rate across all data generating processes (DGPs) with $\gamma=0$. Because $\delta$ is high dimensional, the null space is large and constructing a test with good size and power properties is non-trivial Moreira_JOE09. An additional non-standard feature of our testing problem is that the nuisance equilibrium selection function is only present under the alternative Andrews_Ploberger_EM1994.
Under a logistic assumption on the random component of link utility, using a classic exponential family conditioning argument, we introduce a family of similar tests. We provide an exact characterization of the null distributions of the test statistics in this family and, crucially, a feasible Markov Chain Monte Carlo (MCMC) algorithm for simulating from them. Simulating the null distribution requires drawing a binary adjacency matrix uniformly at random from the set of all adjacency matrices satisfying certain constraints. Constrained binary matrix simulation has numerous applications in biology, psychology, ecology and other fields Sinclair_Book1993, Blitzstein_Diaconis_IM11. Unfortunately, extant simulation algorithms cannot be used to simulate the null distribution needed here; our algorithm is therefore novel and of independent interest.
We also derive the form of the locally best test under the alternative $H_1:\gamma>0$. Remarkably we are able to do this while remaining agnostic about equilibrium selection. Finally, because our test is exact, we also side-step difficult issues that arise when undertaking asymptotic analysis in the single network context (see Graham_HBE20 for references and discussion).
Possible use cases for the methods introduced in this paper include:
While our focus is on strategic network formation, it seems likely that the ideas developed below could be adapted to design tests appropriate for other incomplete econometric models. In recent work Chen_et_al_EM2018 and Kaido_Zhang_arXiv2019 introduced likelihood ratio type tests applicable to incomplete models. Our test, in contrast, is a conditional score test. Conditioning, while requiring exponential family structure, is helpful in settings with a high dimensional nuisance parameter Moreira_JOE09. Our score-based approach may also have computational advantages in settings where likelihood evaluation under the alternative is difficult (e.g., when enumeration of all NE is impossible).
Section (ref) presents our model of strategic network formation. We begin by defining agent preferences and characterizing equilibrium networks. With this foundation we are able to write down a likelihood function for the network. Since there may exist multiple equilibrium networks, this likelihood depends on an unknown (and unmodelled) equilibrium selection mechanism. Although well-defined (see Theorem (ref) below), our likelihood function cannot be numerically evaluated in practice.
Section (ref) outlines our approach to testing. We first characterize the exact distribution of any statistic of the adjacency matrix under the null. By conditioning on a sufficient statistic for the parameter of the null model we guarantee similarity of our text. Our test exactly controls size across all null model parameter values. Next we derive the form of the locally best test statistic for specific alternatives.
Although we characterize the exact null distribution of our test statistics, for reasons of practically, we approximate this distribution by simulation. Section (ref) outlines our new Markov Chain Monte Carlo (MCMC) algorithm for generating random draws from the required null distribution.
Section (ref) illustrates our methods in the context of the Nyakatoke risk-sharing network studied by deWeerdt_IAP04 and others. We construct a test with power for an alternative where agents value their ability to broker transactions among otherwise disconnected agents (as in Burt's Burt_StructuralHoles1995 theory of “structural holes"). We formalize this idea using the model of Kleinberg_et_al_ACM2008. This example is interesting because the form of a good test statistic is ex ante non-obvious, but flows naturally from the Kleinberg_et_al_ACM2008 model and our results. The example also illustrates how test statistics need not be simple functions of the adjacency matrix or even exist in closed form. An extensively narrated Python Jupyter Notebook replicating this empirical illustration is available as part of the Supplemental Materials.
Section (ref) finishes with a short discussion of limitations of our methods as well as a few thoughts on possible areas for additional research.
Proofs as well as some Monte Carlo simulation results are collected in a Supplemental Web Appendix. This appendix also includes a discussion of some additional applications of our MCMC simulation algorithm.
Readers interested primarily in applications can read Section (ref), the first part of Section (ref), and the empirical illustration of Section (ref). The balance of the paper can be read later (perhaps after viewing the Python Jupyter Notebook available in the supplemental materials).
A directed graph $G(\mathcal{V},\mathcal{A})$ consists of a set of vertices (agents) $\mathcal{V}=\{ 1,\ldots,N\}$ and a set of ordered pairs of nodes, respectively called egos and alters, $\mathcal{A}=\{( i,j) , (k,l) ,\ldots\}$ for $i\neq j$, $k\neq l$, and $i,j,k,l\in\mathcal{N}$. The elements of $\mathcal{A}$ correspond to those arcs, or directed links, present in $G(\mathcal{V},\mathcal{A})$.
In what follows we typically work with the adjacency matrix $\mathbf{D}=[D_{ij}]$ where
Since we rule out self-links, the diagonal of $\mathbf{D}$ consists of structural zeros.
Let $G-ij$ denote the network obtained by deleting link $ij$ from $G$ (if present), and $G+ij$ the network one gets after adding this link (if absent). Let $\mathbf{D}\pm ij$ denote the adjacency matrix associated with the network obtained by adding/deleting link $ij$ from $G$.
The set of all $2^{N(N-1)}$ possible adjacency matrices is denoted by $\mathbb{D}_{N}$. Hence $\mathbf{d}\in\mathbb{D}_N$ is a feasible network wiring or, equivalently, a pure strategy profile. Let $\mathbf{d}_{i}$ be the $i^{th}$ row of $\mathbf{d}$, or the pure strategy selection of agent $i$ (i.e., a binary vector indicating which edges she chooses to direct). The pure strategy profile for all players other than $i$ is denoted by $\mathbf{d}_{-i}$. We will sometimes refer to “players other than $i$" as $i$'s peers.
For each agent there are $M\overset{def}{\equiv}2^{N-1}$ possible actions, corresponding to all possible configurations of links she may direct towards her peers. A mixed strategy for agent $i$, $\sigma_{i}=\left(\pi_{1i},\pi_{2i},\ldots,\pi_{Mi}\right)'$, is probability distribution on these $M$ pure strategies; $\sigma=\left(\sigma_{1},\sigma_{2},\ldots,\sigma_{N}\right)'$ is a mixed strategy profile for all $N$ agents, while $\sigma_{-i}$ is the strategy profile of agent $i$'s peers.
The utility or payoff agent $i$ gets from network $\mathbf{d}$ is
with $g_{i}\left(\mathbf{d}\right)$ a known, but not necessarily closed-form, function of the network adjacency matrix, normalized such that $g_{i}\left(\mathbf{0}\right)=0$, $\theta=\left(\gamma,\delta'\right)'$, and the link “costs” function taking the form
where $X_{i}$ is a $K \times 1$ vector of mutually exclusive group membership indicators that is observed by the econometrician and $\mathbf{U}_i=\left(U_{i1},\ldots,U_{ii-1},U_{ii+1},\ldots,U_{iN}\right)'$ is agent $i$'s vector of idiosyncratic logistic preference shocks over the $N-1$ possible links she can direct (and $\mathbf{U}=\left(\mathbf{U}_1', \ldots , \mathbf{U}_N'\right)'$).\footnote{More generally $X_{i}$ enumerates the support points of a collection of (observed) discrete agent-specific regressors (or a partition of this support into $K$ regions).} All agents observe their own, as well as their peers', preference shock vectors. As is standard in game theory, we use, in a small abuse of notation, $\nu_{i}\left(\sigma_{i},\sigma_{-i};\theta, \mathbf{U}_i\right)$ to denote agent $i$'s expected utility under the mixed strategy profile $\sigma=\left(\sigma_{i},\sigma_{-i}\right)$.
The first term in (ref) captures how agent $i$'s utility varies with the entire structure of the network; this may include benefits from direct, as well as indirect connections. The second term in (ref) captures the net costs agent $i$ pays in order to maintain those links she chooses to direct.
In theoretical work $g_{i}\left(\mathbf{d}\right)$ is often called the network benefit function, while $c_{ij}\left(X_i,X_j;\delta, U_{ij}\right)$ would be associated with the cost of forming edge $ij$ Jackson_NetBook08, Goyal_Book2021. These costs are generally assumed constant in theory research, while -- as is appropriate given the empirical context -- they are heterogeneous across agents and links here.\footnote{Johnson_Gilles_RED2000 study the implications of cost heterogeneity on equilibrium network structure in the “connections" model.}
While the benefit-cost typology is useful for developing intuitions about the form of NE in this setting, what is essential here is that the first term may vary arbitrarily with $\mathbf{d}$, and hence with peer actions, while the second term is invariant to peers' actions and, furthermore, additively separable in own actions. In some setting the second term in (ref) may be positive, as occurs when links generate intrinsic surplus. It what follows we call the (negative of the) $j^{th}$ summand in the second part of (ref) the baseline utility that $i$ gets from directing edge $ij$. Of course the appropriate nomenclature is context-specific.
Considering baseline utility first, we see it is increasing in the heterogeneity terms, assumed unobserved by the econometrician, $A_{i}$ and $B_{j}$. Agents with high values of out-degree heterogeneity $A_{i}$ get a large amount of baseline utility from any link they send. In a social network context high $A_{i}$ agents are “extroverts". Agents with high in-degree heterogeneity $B_{j}$, in contrast, are especially attractive targets, or alters, for links sent by others. In a social network high $B_{j}$ agents are “prestigious" or “popular".\footnote{Alternatively we can think of high $A_i$ agents as being able to direct links at low cost, and high $B_j$ agents as being low cost alters.}
The $X_{i}'\Lambda_{0} X_{j}\overset{def}{\equiv}W_{ij}'\lambda_{0}$ term allows baseline utility to depend on whether agents assortatively match on their attributes.\footnote{We define $W_{ij}=\left(X_{i}\otimes X_{j}\right)$ and $\lambda=\mathrm{vec}\left(\Lambda'\right)$.} The elements of the $K\times K$ matrix $\Lambda=\left[\lambda_{kl}\right]$ parameterize the systematic utility generated by links, say, from group $k$ to group $l$. For example, in a social network girls might, all things equal, prefer other girls as friends. The $\Lambda_{0}$ matrix parameterizes homophily (or heterophily) of this type.
We leave the joint distribution of $(A_{i},B_{i},X_{i}')'$ unrestricted.\footnote{This distribution does have implications for test power, as will become apparent below. We also comment that $\left\{(A_{i},B_{i},X_{i}')'\right\}_{i=1}^{N}$ need not be i.i.d. There is no requirement, for example, that the agents in the network are a random sample from some population.} This implies that the unobserved degree heterogeneity $(A_{i},B_{i})'$ may be correlated with the observed covariates $X_{i}$, as in fixed effects panel data analyses.
The final component of baseline utility is idiosyncratic; we assume that the $\{ U_{ij}\} _{i\neq j}$ are independent and identically distributed (iid) logistic random variables. The logistic assumption generates exponential family structure which we exploit when forming our test.
Equation (ref) with $\gamma=0$ gives agent preferences under our baseline or null model (essentially the dyadic link formation model introduced by Charbonneau_EJ17. This model, when fitted by maximum likelihood, can successfully match many features of real world networks. Specifically arbitary in- and out-degree sequences and assortative linking patterns on discrete agent attributes Graham_HBE20. Of course, we are especially interested in settings where the Charbonneau_EJ17 model does not provide a good description of the network in hand.
When $\gamma>0$, the first term in (ref) -- the network benefit function $g_{i}(\mathbf{d})$ -- enriches the baseline model to allow agent preferences over links to vary with the presence or absence of links elsewhere in the network. The researcher is free to specify the network benefit function as desired. A few selected examples, drawn from recent theoretical work on strategic network formation, gives a sense of the range of possibilities.
Let, in an abuse of notation, $\nu_{i}\left(\mathbf{d}\right)\equiv\nu_{i}\left(\mathbf{d}_{i},\mathbf{d}_{-i};\theta, \mathbf{U}_i\right)$; the marginal utility of arc $ij$ for agent $i$ equals
Marginal utility measures the utility gain (loss) to agent $i$ from adding (subtracting) link $ij$ holding the structure of all other links in the network constant (including any other links agent $i$ directs). The component of marginal utility associated with the network benefit function $g_{i}\left(\mathbf{d}\right)$ plays an important role in our analysis. Define the marginal network payoff associated with agent $i$ directing a link to $j$ as
Using (ref) and definition (ref) yields a marginal utility for arc $ij$ of
As it features in the computation of the optimal test statistic introduced below, it is helpful to derive the form of $s_{ij}\left(\mathbf{d}\right)$ for the example network benefit functions introduced earlier.
Example (ref). (Connections) In the connections model, when $i$ directs a link to $j$ she weakly reduces her shortest path length to all other agents in the network. In this model $s_{ij}\left(\mathbf{d}\right) \geq 0$ for all $\mathbf{d} \in \mathbb{D}_N$. While there is no closed form expression for $s_{ij}\left(\mathbf{d}\right)$ in the connections model, it is straightforward to compute shortest path lengths between agents numerically (many network manipulation software libraries include routines to do this). If removing (adding) arc $ij$ increases (decreases) $i$'s distance to many other agents in the network, then $s_{ij}\left(\mathbf{d}\right)$ will be large.
Example (ref). (Structural Hole / Bridging) For the bridging network benefit function $s_{ij}\left(\mathbf{d}\right)$ equals
The marginal utility of edge $ij$ is therefore increasing in the number of agents $k$ which direct edges to $i$, but not to $j$. It is decreasing in the number of agents $l$ and $k$ in which edges $kl$ and $lj$ are present (but edge $kj$ is not).
Example (ref). (Supported Links, Transitivity, Reciprocity) In the support model $s_{ij}\left(\mathbf{d}\right)=\sum_{k}d_{ki}d_{kj}$, which is simply a count of how many agents would support edge $ij$ if it were formed. When agents have a taste for transitivity we have instead
which is a count of how many transitive triads (involving agent $i$) would be created if edge $ij$ is added. Finally if agents have a taste for reciprocity we have $s_{ij}\left(\mathbf{d}\right)=d_{ji}$; indicating that the marginal utility of edge $ij$ varies with the presence or absence of the reciprocal edge $ji$.
We assume that the observed network $\mathbf{D}$ coincides with the equilibrium outcome of an $N$-player complete information game. Each agent (i) observes $\left\{(A_{i},B_{i},X_{i}')\right\}_{i=1}^{N}$ and $\left\{U_{ij}\right\}_{i \neq j}$ and then (ii) decides which, out of the $N-1$ other agents, to send links to. Agents may play mixed strategies.
A mixed strategy profile $\sigma^{*}$ is a NE when $\theta = \theta_0$ and $\mathbf{U}=\mathbf{u}$, if for all $i=1,\ldots,N$,
for all possible pure strategy selections $\mathbf{d}_{i}$. We assume that the observed network $\mathbf{D}$ is either a pure strategy NE or in the support of a mixed strategy NE.\footnote{Observe that agent $i$ must consider $2^{N-1}$ different pure strategy deviations in order to verify that their chosen strategy is optimal. This may be unrealistic when $N$ is large. A weaker equilibrium requirement, akin to the notion of pairwise stability introduced by Jackson_Wolinsky_JET96 for undirected networks, is to require agents to only consider the effects of adding or deleting a single link at time on their utility.
Under this weaker stability notion, which we call single deviation stable (SDS), we only require that the marginal utility of any link present in the network is non-negative, while that of any link not present is negative. This implies that the observed network $\mathbf{D}$ satisfies the $N\left(N-1\right)$ non-linear equations
for $i,j=1,\ldots,N$ and $j\neq i$.While we maintain the NE assumption in what follows, it turns out that our test is also valid if, instead, the observed network is only SDS. Although single deviation stability is a natural directed analog of pairwise stability, we are not aware of this equilibrium concept being considered before.}
In the presence of multiple NE, Assumption (ref) imposes no restrictions on which one is actually realized in the observed network. Our strategic network formation model is incomplete. Although we remain agnostic about equilibrium selection, it is nevertheless useful to develop a notation for, and establish some properties of, the unknown equilibrium selection rule. This allows us to write down a (well-defined) likelihood for the network, albeit abstractly.
Let $\mathcal{N}(\mathbf{d},\mathbf{u};\theta)$ be a function which assigns, for $\mathbf{U}=\mathbf{u}$, a probability weight to network $\mathbf{d}$:
In order for $\mathcal{N}(\mathbf{d}, \cdot;\theta)$ to be a valid NE selection function it must satisfy the conditions of Definition (ref).
If $\mathcal{N}(\mathbf{d},\cdot;\theta)$ satisfies the conditions of Definition (ref), then the likelihood of observing network $\mathbf{D}=\mathbf{d}$ is
where $f_{\mathbf{u}}(\mathbf{u})=\prod_{i\neq j}f_{U}(u_{ij})$ with $f_{U}(u)=e^{u}/[1+e^{u}]^{2}.$ Of course, for the likelihood (ref) to be well-defined we require that $\mathcal{N}(\mathbf{d}, \cdot;\theta)$ is measureable.
The proof of Theorem (ref) can be found in Appendix (ref).
The development in this section parallels the first and second use cases outlined in the introduction. We first discuss how to assess the adequacy of the baseline model as a description of the network in hand. Utilizing a conditioning argument we construct an exact test (up to simulation error) of the null of “correct specification". An alternative model is not explicitly formulated in this case, although researcher intuitions about plausible directions of mis-specification typically guides the choice of test statistic. As shown by Lehmann_Romano_TSH05, it is impossible to construct a test with power in all possible directions of mis-specification.
Next we consider applications where the analyst carefully specifies the alternative model (through an explicit choice of the network benefit function, $g_i\left(\mathbf{d}\right)$). Here the researcher believes the true network formation model lies in either the null or the (specified) alternative model space; the purpose of testing is to determine which situation prevails. In this second application we seek to construct a test which rejects with high probability when the alternative is true, while continuing to control size under the null.
Throughout, and crucially, we wish to remain agnostic about the distribution of any degree heterogeneity across agents as well as the form of any homophily and/or heterophily. Let $\Delta$ denote a subset of the $K^{2}+2N$ dimensional Euclidean space in which $\delta_{0}=\left(\lambda_{0},\mathbf{A}_{0},\mathbf{B}_{0}\right)$ is, a priori, known to lie, and
Our null hypothesis is the composite one:
since $\delta$ may range freely over $\Delta\subset\mathbb{R}^{K^{2}+2N}$ under the null.
Under the null the likelihood is $P_{0}(\mathbf{d};\delta)\overset{def}{\equiv}P(\mathbf{d};(0,\delta')',\mathcal{N}_{0})$ with
Under the null the unique “equilibrium” network is the one where all links with positive marginal utility are present and those with negative marginal utility are not. These marginal utilities are invariant to the presence or absence of links elsewhere in the network; $\mathcal{N}_{0}(\mathbf{d},\mathbf{u};\theta)$ places a probability of $1$ on this network. Evaluating the integral (ref) under the null yields
where $R_i$ is the $N\times1$ vector with a $1$ in its $i^{th}$ element and zeros elsewhere.\footnote{Variants of this likelihood are analyzed by Chatterjee_et_al_AAP11, Charbonneau_EJ17, Graham_EM17, Jochmans_JBES18, Dzemski_RESTAT18 and Yan_et_al_JASA18.}
Under the null our likelihood, $P_{0}(\mathbf{d};\delta)$, is a member of the exponential family. To see this it is helpful to establish some additional notation. The out- and in-degree sequences equal:
Here $D_{+i}=\sum_{j}D_{ji}$ and $D_{i+}=\sum_{j}D_{ij}$ equal the in- and out-degree of agents $i=1,\ldots,N$.
The $K\times K$ cross-link matrix equals
This matrix summarizes the inter-group link structure in the network (homophily). The $kl^{th}$ element of $\mathbf{M}$ records the number of links sent by type $k$ agents (e.g., semiconductor manufacturers) to type $l$ agents (e.g., computer manufacturers).
Let $\mathbf{S},\mathbf{M}$ be a degree sequence and cross-link matrix. We say $\mathbf{S},\mathbf{M}$ is graphical if there exists at least one arc set $\mathcal{A}$ such that $G\left(\mathcal{V},\mathcal{A}\right)$ is a simple directed graph with degree sequence $\mathbf{S}$ and cross link matrix $\mathbf{M}$. We call any such network a realization of $\mathbf{S},\mathbf{M}$. The set of all possible realizations of $\mathbf{S},\mathbf{M}$ is denoted by $\mathbb{G}_{\mathbf{S},\mathbf{M}}$ ($\mathbb{D}_{\mathbf{S},\mathbf{M}}$ denotes the associated set of adjacency matrices).
With this notation it is easy to verify that the null model belongs to the exponential family (see Graham_EM17):
with a (minimally) sufficient statistic for $\delta$ of $\mathbf{t}=\left(\mathrm{vec}\left(\mathbf{m}'\right)',\mathbf{s}_{\mathrm{out}}',\mathbf{s}_{\mathrm{in}}'\right)'$. In words, the $K^{2}+N+N$ sufficient statistics are (i) the cross link matrix, (ii) the out-degree sequence and (iii) the in-degree sequence.
Under $H_{0}$ the conditional likelihood of the event $\mathbf{D}=\mathbf{d}$ is
if $\mathbf{d} \in \mathbb{D}_{\mathbf{s},\mathbf{m}}$ and zero otherwise. Under the null of no strategic interaction all networks with the same in- and out-degree sequences and cross link structure are equally likely. Importantly this conditional likelihood is invariant to the actual value of the nuisance parameter $\delta$.
By conditioning on $\mathbf{T}$, which is sufficient for $\delta$, we isolate the information in the data that is relevant for assessing model adequacy Barndorff-Nielsen_Cox_IA1994. This follows because conditional on $\mathbf{T}$, the null model completely specifies the distribution of $\mathbf{D}$. Consequently, the distribution of any statistic of the adjacency matrix, say $R\left(\mathbf{D}\right)$, is also fully specified. Specifically the null distribution $R\left(\mathbf{D}\right)$ is the one induced by a discrete uniform distribution on $\mathbb{D}_{\mathbf{S},\mathbf{M}}$:
To test model goodness-of-fit, we simply check whether the value of $R\left(\mathbf{D}\right)$ in the network in hand is at an extreme quantile of this distribution. If it is, we take this as evidence against the baseline (null) model.
A test with critical function $\phi\left(\mathbf{D}\right)$ will have size $\alpha$ if its null rejection probability (NRP) is less than or equal to $\alpha$ for all values of the nuisance parameter:
Since the nuisance parameter $\delta$ is very high dimensional, size control is a priori non-trivial. For some intuition as to why consider, as an example, the case where $s_{ij}(\mathbf{d})=\sum_{k}d_{ki}d_{kj}$, such that agents' have a taste for supported links when $\gamma_{0}>0$. A natural test statistic in this case would be some function of $\mathbf{D}$ that is increasing in the number of supported links in the network.\footnote{Jackson_et_al_AER12 suggest the fraction of links in the network which are supported.} The researcher would then reject the null of $\gamma_{0}=0$ when this statistic is large enough. Unfortunately, the expected number of supported links varies dramatically under the null depending on the value of $\delta$. Certain configurations of $\mathbf{A}$, $\mathbf{B}$ and/or $\lambda$ may result in a network with substantial link clustering (and hence support) even when agents' have no taste for support per se. If we choose a single critical value for rejection then, depending on the values of $\mathbf{A}$, $\mathbf{B}$ and/or $\lambda$, size may be very poor.
To avoid any size distortion induced by variation in $\delta$ over $\Delta\subset\mathbb{R}^{K^{2}+2N}$ we exploit the exponential family structure of our model (under the null). Let $\mathbb{T}=\left\{ \left(\mathbf{s},\mathbf{m}\right)\thinspace:\thinspace\mathbf{s},\mathbf{m}\text{ is graphical}\right\}$ be the set of possible sufficient statistics $\mathbf{T}$. Instead of choosing a single critical value, which may result in under- or over-rejection, depending on the value of $\delta$, we proceed conditionally on $\mathbf{T} \in \mathbb{T}$, varying our critical value with $\mathbf{T}$. In this way we ensure good size control.
Formally, for each $\mathbf{t}\in\mathbb{T}$ we form a test with the property that, for all $\theta\in\Theta_{0}$,
Such an approach ensures similarity of our test since, by iterated expectations,
for any $\theta\in\Theta_{0}$ Ferguson_MS67. By proceeding conditionally we ensure that the NRP is unaffected by the value of $\delta$.
For any $\mathbf{t}\in\mathbb{T}$ we can construct an exact test, as is required by (ref), because our model completely specifies the distribution of networks conditional on $\mathbf{T}=\mathbf{t}$ under the null. Condition (ref) follows immediately. Using some well-known results from the theory of exponential families, we can make the stronger claim that similarity is only possible by conditioning.
To operationalize, let $R(\mathbf{D})$ be some statistic of the adjacency matrix. For example $R(\mathbf{D})$ might be the network reciprocity index Newman_NetBook10:
where
equals the fraction of dyads which take an unreciprocated or “asymmetric" configuration and
the fraction which take a reciprocated or “mutual" configuration.
A conditional test based upon $R(\mathbf{D})$ will have a critical function of
where the values of $c_{\alpha}\left(\mathbf{t}\right)$ and $g_{\alpha}\left(\mathbf{t}\right)\in\left[0,1\right]$ are chosen to satisfy the requirement that $\mathbb{E}_{\theta}\left[\left.\phi\left(\mathbf{D}\right)\right|\mathbf{T}=\mathbf{t}\right]=\alpha$.
Under the null all adjacency matrices with the $\mathbf{S}=\mathbf{s}$ and $\mathbf{M}=\mathbf{m}$ are equally probable. By enumerating all adjacency matrices in $\mathbb{D}_{\mathbf{s},\mathbf{m}}$ we could exactly compute the null distribution of $R\left(\mathbf{D}\right)$ and hence the critical values $c_{\alpha}\left(\mathbf{t}\right)$ and $g_{\alpha}\left(\mathbf{t}\right)$. In general such a brute force approach will be infeasible.\footnote{In fact very little is known about the set $\mathbb{D}_{\mathbf{s},\mathbf{m}}$; for example we are aware of no method for checking whether a given $\mathbf{s},\mathbf{m}$ pair is graphic. From related settings we believe that the cardinality of $\mathbb{D}_{\mathbf{s},\mathbf{m}}$ will typically be intractably huge even for modestly-sized networks. See Blitzstein_Diaconis_IM11 for discussion of this point and examples from a related setting.} Therefore a method of approximating the exact null distribution is required. The simulation algorithm introduced below provides such a method.
The intuition behind this test is straightforward. If the network in hand has an “unusually" large value of $R(\mathbf{D})$ relative to the set of all networks with same in- and out-degree sequences and cross-link matrices, then we reject the null that the baseline model is correctly specified. A rejection is not interpreted as evidence in favor of a particular alternative model. Relatedly, a feature of goodness-of-fit tests, including this one, is that we have may have low, or even, power equal to size in certain directions Lehmann_Romano_TSH05.
In this section we discuss how to test when the alternative model space is explicitly specified. That is, when the researcher explicitly specifies the network benefit function in (ref) and proceeds under the premise that the true network generating process lies either in the null or the (explicitly specified) alternative model space. In such settings a rejection provides evidence that $\gamma_0>0$ (in the context of a specific network benefit function). Naturally the researcher would like to maximize her power to reject, while continuing to maintain similarity. To accomplish this requires choosing the right test statistic.
Because equilibrium selection is not specified under the alternative, likelihood ratio (LR) testing is not feasible Chen_et_al_EM2018. As an alternative to a LR test, we instead choose, for each $\mathbf{t}\in\mathbb{T}$, the critical function, $\phi\left(\mathbf{D}\right)$ to maximize the derivative of the (conditional) power function $\beta\left(\gamma,\mathbf{t}\right)=\mathbb{E}\left[\left.\phi\left(\mathbf{D}\right)\right|\mathbf{T}=\mathbf{t}\right]$ evaluated at $\gamma=0$ subject to the (conditional) size constraint $\mathbb{E}_{\theta}\left[\left.\phi\left(\mathbf{D}\right)\right|\mathbf{T}=\mathbf{t}\right]=\alpha$. Such a $\phi\left(\mathbf{D}\right)$ is locally best Ferguson_MS67. Remarkably we show that the locally best test does not depend upon the form of the equilibrium selection mechanism $\mathcal{N}(\mathbf{d}, \mathbf{u};\theta)$.
Differentiating the power function we get
with $\mathbb{S}_{\gamma}\left(\left.\mathbf{d}\right|\mathbf{t};\theta\right)$ denoting the conditional score function
and $k\left(\mathbf{t}\right)$ only depending on the data through $\mathbf{T}=\mathbf{t}$ (Here, and in the balance of this section, it is understood that $\delta$ is evaluated at is population value $\delta_0$). By the Neyman-Pearson lemma, the test with the critical function given by equation (ref) above, where the test statistic, $R\left(\mathbf{d}\right)$, is set equal to the log-likelihood gradient, $\frac{1}{P_{0}\left(\mathbf{d};\delta\right)}\left.\frac{\partial P\left(\mathbf{d};\theta\right)}{\partial\gamma}\right|_{\gamma=0}$, will be locally best within the class of similar tests.
The idea behind the locally best test is as follows. If the likelihood increases sharply as we move away from the null in the direction of the alternative of interest, then we take this as evidence against the null. Intuitively if the likelihood gradient in the neighborhood of the null is large, then the likelihood ratio will also be large for simple alternatives close to the null (i.e., when $\gamma \in \left(0,\epsilon\right]$).
Constructing the locally best critical function requires calculating $\frac{1}{P_{0}\left(\mathbf{d};\delta\right)}\left.\frac{\partial P\left(\mathbf{d};\theta\right)}{\partial\gamma}\right|_{\gamma=0}$. This is not straightforward since it depends on properties of the likelihood under the alternative (and consequently the equilibrium selection function). Nevertheless, we are able to derive the form of this derivative.
The proof of Theorem (ref), along with some additional commentary, can be found in Section (ref) of the Supplemental Web Appendix. A key implication of Theorem (ref) is that the form of the locally best test statistics does not depend upon $\mathcal{N}$, the equilibrium selection mechanism. This is essential, since optimal testing would not be feasible otherwise (at least without additional assumptions). One intuition for this finding is that equilibrium is unique with high probability when $\gamma$ is close to zero. This means we can effectively ignore draws of $\mathbf{U}$ which lead to multiple equilibria when differentiating the likelihood.
Indeed, when $\gamma$ is close to zero most players will have a strictly dominant strategy (that is the optimal set of links for them to send will be invariant to the play of their peers). Of course we need more information to recover the gradient with respect to $\gamma$, since this parameter measures the responsiveness of agents to their peers' actions. It turns out that a key scenario used in the derivative calculation involves considering draws of $\mathbf{U}$ where all players except one have strictly dominant strategies. The one player without a strictly dominant strategy provides the needed gradient information.
With a little manipulation we can simplify (ref) to:
where $F_{U}\left(u\right)=e^{u}/\left[1+e^{u}\right]$ is the logistic CDF. This form of the statistic provides insight into how our test accumulates evidence against the null in practice. Consider the case where $s_{ij}\left(\mathbf{d}\right)=d_{ji}$, as would be true in agents' have a taste for reciprocated links. Observe that $F_{U}\left(\mu_{ij}\right)$ corresponds to the probability of the edge $ij$ under the null. Therefore the optimal test statistic is large if we observe that many $ij$ links with low probability under the null are reciprocated. It is not many reciprocated links that drives rejection per se, but the presence of many “unexpected" reciprocated links.
Consider a network of boys and girls with agents exhibiting a strong taste for gender-based homophily. The optimal test statistic in this case is the conditional sample covariance of $D_{ij}$ and $D_{ji}$ given $(A_i, B_i, X_i)$ and $(A_j, B_j, X_j)$. The test based upon the reciprocity index is -- essentially -- based upon the unconditional covariance. The effect of conditioning is to, for example, given more weight to heterophilous reciprocated links than to homophilous ones. Similarly we give more weight to reciprocated links across low degree agents, than to those across high degree agents.
Two practical issues remain. The first, how to simulate the null distribution of the optimal test statistic, is covered in the next section. Second, although the locally best test statistic does not depend on the details of equilibrium selection, it does depend on $\delta_0$. Although the test will remain admissible when $\delta_0$ is replaced by some other, perhaps arbitrary, $\delta$, it will not be locally best.
A practical solution to this problem is to replace $\delta_0$ with its maximum likelihood estimate (MLE) computed under the null. This particular MLE is studied by Yan_et_al_JASA18. In our Monte Carlo experiments, some of which are reported in the Supplemental Web Appendix, we have found that replacing $\delta_0$ with its MLE, results in a test which is nearly as powerful as the infeasibe oracle test based on $\delta_0$, and far more powerful that tests based on ad hoc statistics.
Because a complete enumeration of $\mathbb{D}_{\mathbf{s},\mathbf{m}}$ is not feasible unless $N$ is very small, making our test practical requires a method of constructing uniform random draws from this set. Such draws can be used to simulate the null distribution of any test statistic of interest.
The problem of simulating networks with fixed degree sequences is well-studied; with many domain specific applications Sinclair_Book1993. We add to this problem the additional requirement that the simulated network satisfies the cross-link matrix constraint.
Prior work on network simulation adopts one of two basic approaches. The first approach begins with an empty graph and randomly adds links. Links need to be added such that the end graph satisfies the degree sequence constraint. Blitzstein_Diaconis_IM11 develop an algorithm along these lines. They cleverly use checks for graphicality of a degree sequence, available in the discrete math literature, to add links in a way which constrains the end graph to be in the target set.\footnote{See also Genio2010 and Kim2012. Graham_Pelican_BookCh2020 provide a textbook discussion of the Blitzstein_Diaconis_IM11 algorithm.}
The second approach, to which our new method belongs, uses Markov Chain Monte Carlo (MCMC). Specifically an initial graph, satisfying the target constraints, is randomly rewired many times to create a new graph from the target set. Key to this approach is ensuring that each rewiring is compatible with the target constraints (e.g., maintains the network's degree sequence). The algorithm also needs to be constructed carefully to ensure that the end graph is a uniform random draw from the target set. Sinclair_Book1993, Rao_et_al_Sankhya96, McDonald_et_al_SN07, Berger2010 and Tao_NS16 all developed MCMC methods for simulating graphs (or digraphs) with given degree sequences.
We are aware of no method of generating adjacency matrix draws from $\mathbb{D}_{\mathbf{s},\mathbf{m}}$. The novelty of this problem, relative to the work described above, is the presence of the additional cross link matrix constraint, $\bf{M}$. In the discrete math literature the cross link matrix constraint corresponds to what is called a partition adjacency matrix (PAM) constraint. czabarka2017algebraic conjecture that determining whether a given $\mathbf{s}, \mathbf{m}$ pair is graphical, the PAM realization problem, is NP-complete. If their conjecture is correct (and NP $\neq$ P), using a Blitzstein_Diaconis_IM11 type algorithm to draw from $\mathbb{D}_{\mathbf{s},\mathbf{m}}$ is not feasible.
This leaves MCMC methods. Erdoes2017 showed that naively incorporating a PAM constraint into existing MCMC algorithms destroys their correctness. In this section we introduce a new MCMC algorithm that does generate uniform random draws from $\mathbb{D}_{\mathbf{s},\mathbf{m}}$. This algorithm is of independent interest. Before describing the algorithm we introduce some additional definitions and notation.
We start by defining an alternating walk.
\theoremstyle{definition}
For brevity we will often refer to a walk simply by its node sequence, writing $H:=i_{1}i_{2},\ldots,i_{l}$. To unpack Definition (ref) it is easiest to consider an example. In Figure (ref), Panel B, three altering walks are shown (the links not present are depicted as dotted arrows).
Observe that for $H:=i_{1}i_{2},\ldots,i_{l}$, the adjacency matrix entries $D_{i_{1}i_{2}},D_{i_{3}i_{2}},\ldots,D_{i_{l}i_{l-1}}$ alternate between ones and zeros (or zeros and ones). This observation suggests a method of constructing an alternating walk via a sequence of “hops" across the adjacency matrix: pick row $i_{1}$ of the adjacency matrix and move horizontally to column $i_{2}$, where $i_{2}$ corresponds to one of the agents to which $i_{1}$ directs a link, next move vertically to row $i_{3}$, where $i_{3}$ is an agent which does not direct a link to $i_{2}$, and so on.\footnote{This description is essentially due to Tao_NS16.} We call the horizontal moves active steps and vertical moves passive steps. Figure (ref) provides an example construction. The different cases in Definition (ref) correspond to walks beginning/ending with passive/active steps.
The length of an alternating walk equals the number of ordered dyads used to define it. An important type of alternating walk, which following Tao_NS16, we call an alternating cycle, is central to our algorithm.
The length of an alternating cycle is at least four. Let $D_{i_{1}i_{2}},D_{i_{3}i_{1}},\ldots,D_{i_{l}i_{l-1}}$ be the sequence of adjacency matrix entries associated with alternating cycle $C$ in $D$. These entries necessarily form a sequence of zeros and ones (or ones and zeros).
Consider constructing an alternative digraph, say $\mathbf{D}'$, by replacing all the “ones” in the alternating cycle $C$ with “zeros” and all “zeros” with “ones”. Rewiring $\mathbf{D}$ in this way is degree preserving: $\mathbf{D}'$ has the same in- and out-degree sequence as $\mathbf{D}$. We refer to such operations as switching the cycle (since we switch the zeros and ones).
We use random alternating walks on the network in order to find alternating cycles. We then use these alternating cycles to rewire the network. This motivates the definition of what we call a schlaufe. A schlaufe is either an alternating walk which contains an alternating cycle (as the last part of the walk) or it is an alternating walk which cannot be continued. More precisely
\theoremstyle{definition}
In German schlaufe corresponds to “loop”, “bow” or “ribbon” (its plural is schlaufen); the latter translation is evocative of our meaning here. In the first case the schlaufe will coincide with an alternating walk which includes exactly one alternating cycle.\footnote{The requirement that $i_{k}=i_{l}$ and $\left(k-l\right)\bmod2=0$ ensures that $C=i_{k}i_{k+1}\ldots i_{l}$ is an alternating cycle (imposing even length). The “furthermore...” requirement ensures that if another node is visited multiple times it does not form an alternative cycle (imposing non-even length). See Figure (ref) for an example.} Visually schlaufen of the first type, with the nodes appropriately placed, will look like loops and ribbons. In the second case the schlaufe does not include an alternating cycle.
Associated with a schlaufe, $R$, is a $K\times K$ violation matrix which records the number of extra links from group $k$ to group $l$ generated by switching the alternating cycle in $R$ (if there is one). Consider an alternating rectangle consisting of two boys and two girls. If initially one boy directs a link to the other and one girl directs a link to the other, then after switching the cycle the violation matrix will equal:\\
\\ After switching the cycle there are too few same gender links and too many mixed gender ones.
We call a sequence of schlaufen $\mathcal{R}=\left(R_{1},\ldots,R_{k}\right)$ feasible if (i) the cycles of the schlaufen are link disjoint and (ii) the sum of their violation matrices is zero (and for $i<k$ the sum of their violation matrices is not zero).
Conventional MCMC adjacency matrix re-wiring algorithms work by switching short cycles (e.g., alternating rectangles and compact alternating hexagons as in Rao_et_al_Sankhya96). Switches of this type, while preserving the in- and out-degree sequence of the network will typically generate networks with the wrong inter-group link structure (i.e., non-zero link violation matrices). Our approach to solving this problem involves switching many alternating cycles simultaneously such that their individual link violation matrices sum to zero.
Let $\mathbf{S}=\mathbf{s}$ and $\mathbf{M}=\mathbf{m}$ be the degree sequence and cross link matrix of the network in hand. In order to a draw, say $\mathbf{D}'$, from $\mathbb{D}_{\mathbf{s},\mathbf{m}}$ we (i) start with a realization of $\left(\mathbf{s},\mathbf{m}\right)$, say $\mathbf{D}$, (ii) randomly construct (link disjoint) schlaufen, and (iii) switch any alternating cycles in them. While switching cycles will preserve the degree sequence, it may – as discussed earlier – result in a graph without the appropriate cross link matrix. In order to ensure that $\mathbf{D}'$ has the appropriate cross link matrix, we construct schlaufen until either the sum of their violation matrices equals zero or we stop randomly. If the sum of the schlaufen violation matrices is zero we move to $\mathbf{D}'$ from $\mathbf{D}$ by switching the cycles, otherwise we set $\mathbf{D}'=\mathbf{D}$. Proceeding in this way ensures that $\mathbf{D}'$ is, in fact, a random draw from $\mathbb{D}_{\mathbf{s},\mathbf{m}}$. After sufficiently many iterations of this process we show that a graph constructed in this way corresponds to uniform random draw from $\mathbb{D}_{\mathbf{s},\mathbf{m}}$. A formal statement of the procedure is provided by Algorithm (ref).
Algorithm (ref) uses a subroutine to find schlaufen. This subroutine, described in Algorithm (ref), finds and marks a schlaufe in the graph.
To illustrate our method in more detail consider the network depicted in Panel A of Figure (ref). This network consists of two types of agents: gold (light) and blue (dark). The cross link matrix for the graph is given in Panel D. In Panels B and C a sequence of three schlaufen is shown. The first schlaufen is $R_{1}=jgabcdeca$. It is constructed through a sequence of active and passive steps as described earlier (see also the notes to Figure (ref) above). We begin by choosing agent $j$ randomly with a probability of $\frac{1}{10}$ (since there are ten agents in the network). We then take an active step, randomly choosing one of the two agents to which $j$ directs a link (i.e., either agent $g$ or $i$). Here we choose agent $g$. Next we take a passive step. Specifically we choose an agent at random from the set of agents that do not direct a link to $g$ (the agent chosen in the previous active step). The probability associated with our choice in this passive step is $\frac{1}{7}$; this corresponds to the reciprocal number of agents in the network (i.e., $10$) minus the indegree the current agent (i.e., $2$) minus one (since self-loops are not allowed). We continue taking active and passive steps in this way until we visit $a$ for the second time. At this point we stop since our schlaufe now includes the alternating cycle $C_{1}=abcdeca$. Note that $c$ is also visited twice, but also that $cdec$ is not an alternating cycle since it is not of even length (see Definition (ref)).
As seen in the example we can calculate the probability of a schlaufe $R$ as we go through the algorithm (see Panel E). In Step 1 of Algorithm (ref) an agent is chosen with probability $\frac{1}{N}$. Next let $r_D^a(i)$ be the cardinality of the set of feasible out links in an active step. This set consists of all the out links of node $i$, which are not already marked in $\bf{D}$. Similarly, let $r_D^p(i)$ be the cardinality of the set of feasible outlinks in an passive step. That set consists of all the links $ij$ for which $ji$ is not in $\mathbf{D}$ and which are not already marked. The probability of $R = (i_1,..,i_l)$ can now be written as
In step 2 of Algorithm (ref) we attempt to find a sequence of schlaufen with probability $1-q$ and do not change the adjacency matrix otherwise. In step 3, a schlaufen sequence $\mathcal{R} = (R_1, .. ,R_h)$ is constructed/found. After each detected schlaufe in this sequence, say $R_k$, any cycle in it is marked. Let $\mathbf{D}_k$ be the graph with the cycles of $R_1,..,R_{k-1}$ marked. After each schlaufe added the construction is stopped with probability $\frac{1}{2}$ . The probability of finding a cycle $R_k$ is $p_{\mathbf{D}_k}(R_k)$ as given in equation (ref) above. The total probability of a feasible schlaufen sequence $\mathcal{R}$ is therefore
To show that our algorithm does indeed generate a uniform random draw from the set $\mathbb{D}_{\mathbf{s},\mathbf{m}}$ we use standard Markov chain theory (e.g., Chapters 7 and 10 of Mitzenmacher_Upfal_PC05).
The random rewiring of the network implemented by Algorithm (ref) can be described as a Markov chain. To show that, for $\tau$ large enough, it returns a uniform random draw from $\mathbb{D}_{\mathbf{s},\mathbf{m}}$ we prove that the stationary distribution of the Markov chain generated by Algorithm (ref) is uniform on $\mathbb{D}_{\mathbf{s},\mathbf{m}}$. To show this it is helpful to develop a graphical representation of the Markov chain.
We denote the state graph of the Markov chain by $\Phi = (\mathcal{V}_{\phi} , \mathcal{A}_{\phi})$. Its underlying vertex set $\mathcal{V}_\phi$ is the set of all elements in $\mathbb{D}_{\bf{s},\bf{m}}$. That is each node in our state graph is a network with degree sequence $\bf{S=s}$ and cross link matrix $\bf{M=m}$. For network $\mathbf{D}$ in $\mathbb{D}_{\bf{s},\bf{m}}$, we denote by $v_{\mathbf{D}}$ the corresponding vertex in $\mathcal{V}_\phi$. The arc set $\mathcal{A}_\phi$ is defined as follows.
The probability of any arc $a \in \mathcal{A}_\phi$ is denoted by $p(a)$. Note, by definition, the state graph can have parallel arcs and loops.
With these definitions in place we can prove correctness of the algorithm. First we show that the probability of the algorithm moving from graph $\mathbf{D}$ to $\mathbf{D}'$ coincides with the probability of moving in the reverse direction.
Next we show the state graph is strongly connected. This means our Algorithm moves from any ${\mathbf{D}} \in \mathbb{D}_{\bf{s},\bf{m}}$ to any other ${\mathbf{D}'} \in \mathbb{D}_{\bf{s},\bf{m}}$ with positive probability.
With these two lemmata it is easy to show that the stationary distribution is uniform on $\mathbb{D}_{\bf{s},\bf{m}}$. This gives us the main result of the section.
deWeerdt_IAP04 studied the formation of risk-sharing links across 119 households in the rural village of Nyakatoke (located in Tanzania). He asked all adult individuals in the village who they could rely upon for help and, from their responses, constructed a network of directed links across households.\footnote{The prompt used by deWeerdt_IAP04 is suggestive of both mutuality and directionality, leading to some ambiguity in whether to interpret the collected edges as undirected or directed. Comola_Fafchamps_EJ2014 present evidence suggesting that the links given by households are directed. Specifically that they indicate to which other households they would turn to in the event of need. It is this interpretation that we give the links here.}. The resulting set of risk-sharing links is shown in Figure (ref).
Here we assess whether households value “bridging capital", as suggested by Burt_StructuralHoles1995 and formalized in game-theoretic terms by Kleinberg_et_al_ACM2008 and others. If $k$ directs a link to $i$ but not to $j$, then $i$, by directing a link to $j$, may position herself to serve as a “bridge" or “broker" between $k$ and $j$. See Figure (ref) above.
In the formal model of Kleinberg_et_al_ACM2008 agents gain utility from positioning themselves on length two paths connecting agents not directly connected themselves; however such utility gains are decreasing in the number of “rival” length two paths (i.e., those with other agents in the center). This suggest, for example, a network benefit function of
In this formulation any “bridging" capital is shared equally across all agents $l$ on length two paths from $j$ to $k$ (with arc $jk$ absent). For example, if there are two bridging agents situated between $j$ and $k$, they each get half the benefit and so on. The marginal network benefit of edge $ij$ is thus
from which the form of the locally best test follows.
From deWeerdt_IAP04 we also know that household land and livestock wealth, as well as religion (Catholic, Lutheran or Muslim), are important drivers of link formation in Nyakatoke. We divide households into three wealth bins, which in conjunction with religion, partitions households into nine groups; $X_i$ consists of the nine resulting group membership dummies with the 81 elements of $\Lambda$ parametrizing any homophily/heterophily across these groups. The remaining null model parameters are the $238=119 \times 2$ household-specific in- and out-degree heterogeneity parameters. This gives $\dim(\delta)=2 \times 119 + 9 \times 9$ = 319 null model “nuisance" parameters. It is hard to imagine a testing approach with good properties in this setting which would not involve “conditioning away" the null model parameter.
While the form of the locally best test statistic follows naturally from the form of the Kleinberg_et_al_ACM2008 network benefit function, it is less clear how to form a heuristic test with power to detect the alternative “agents like to bridge disconnected groups". After some experimentation we settled on the difference between the 90th and 50th percentiles of the empirical distribution of betweenness-centrality across agents in the network as a suitable ad hoc test statistic (other measures of dispersion give similar results). The intuition is that acquiring bridging capital is inherently rivalrous; the addition of links by other agents may reduce one's own network benefit. Competition to accumulate bridging capital should lead to more dispersion in betweenness-centrality across agents (than in a reference set of null model graphs). Winners of this competition (the 90th percentile) will have more bridging capital than the typical agent (the 50th percentile) in the network. We wish to emphasize that the “ad hoc" descriptor of this statistic is apt. Indeed, an advantage of the formalism of an explicit network benefit function is that gives precision to the alternative of interest (in turn suggesting a suitable, in fact, optimal test statistic).
The left panel of Figure (ref) plots simulation estimates of the distribution of the $90-50$ betweenness-centrality gap across three reference sets of networks: (i) \"{E}rdos-R\'{e}nyi graphs with the same number of links as observed in Nyakatoke, (ii) the set of all graphs with the same in- and out-degree sequences as observed in Nyakatoke, and (iii) the set of all graphs which additionally constrain the number of cross-group links to be the same as observed in Nyakatoke. The vertical line in the figure marks the value of the actual $90-50$ betweenness-centrality gap in Nyakatoke.
The three reference distributions in Panel A allow us to undertake three model adequacy tests: is Nyakatoke well-described by (i) the \"{E}rdos-R\'{e}nyi model, (ii) a directed $\beta$-model which places equal probability on all networks with the same in- and out-degree sequence as in Nyakatoke, or (iii) by the Charbonneau_EJ17 model described above? In all three cases we reject, but notice that as we enrich the null model the simulated reference distributions shift to the right.\footnote{The incremental effect of additionally controlling for homophily is modest.} Put differently a portion of the dispersion in betweenness-centrality across households observed in Nyakatoke is likely a by-product of degree heterogeneity and homophily. The rightward shifts in the reference distributions as we enrich the null model is indicative of how using a realistic null model may be important for avoiding spurious rejections in practice. That said, our decisive rejection of even the $319$ parameter Charbonneau_EJ17 model indicates that degree heterogeneity and wealth/religion homophily cannot explain all of the inequality in betweenness-centrality we observe across agents in Nyakatoke.
The right panel of Figure (ref) plots the null distribution of the locally best test statistic for the alternative that households gain utility by bridging disconnected pairs of agents (as formalized by Kleinberg_et_al_ACM2008). If we are willing to maintain that the true data generating process is either in the null or specified alternative model space, we can interpret a rejection as evidence for $\gamma_0$ being positive. To implement this test we replace $\delta_0$ with its maximum likelihood estimate (MLE) computed under the null.\footnote{The computation of this MLE is described in detail by Dzemski_RESTAT18 and Yan_et_al_JASA18 and implemented in our Python package ugd for “uniform graph draw".} As is clear from Panel B of Figure (ref), we decisively reject the null.
Panel B is also suggestive of the power gains associated with the locally best test. If we were to standardize each of our test statistics using their respective reference distribution's mean and standard deviation, it is obvious that the locally best test statistic is more extremely positioned in the right tail of its null distribution (the Monte Carlo experiments reported in the Supplemental Web Appendix confirm the power advantages of the locally best test).
Using Algorithm (ref) requires a choice of the mixing time parameter $\tau$. Although the mixing properties of our MCMC procedure are largely unexplored, we have found - by Monte Carlo experimentation -- that choosing $\tau$ such that each edge in the input graph is, on average, swapped at least once before the resulting output is considered a uniform random draw from the target set to yield acceptable results in practice. We use this approach here (also see the Python Juypter Notebook in the Supplemental Materials). The required value for $\tau$ is increasing in the dimension of the nuisance parameter $\delta$ and especially in the dimension of $\Lambda$. Hence the speed of the simulation algorithm declines in both $N$ and $K$.
The analysis in this paper, like much of the wider econometrics literature on games, is likelihood based. Our null model is fully parametric (albeit flexibly-so), while the alternative, due to the unmodeled NE selection function, is semiparametric. Under correct specification -- use case (ii) -- our test reveals whether $\gamma_0=0$ or $\gamma_0>0$ (with a researcher-specified exact Type I error rate, and a locally best Type II error rate). That is, we present a method for detecting whether agents form links “strategically" in the presence of any pattern of homophily and degree heterogeneity allowed by the null.
It would be interesting to know whether detecting strategic interaction in the presence of arbitrary homophily on observables and degree heterogeneity is possible. We know from the panel data literature that detecting state-dependence in the presence of heterogeneity is non-trivial and that modeling details matter Chamberlain_LALMD85. Analogous questions arise here.
Our set-up assumes that researcher is able to a priori partition the support of agents' covariates into $K$ regions along which all homophilous sorting occurs. In practice this is an approximation. Developing data-based discretization rules (e.g., using clustering algorithms) and formalizing the nature of the approximations involved would be useful. It is possible that recent results on randomization inference by Canay_et_al_EM2017 could be useful for such an analysis.
Key to our set-up is the exponential family structure (under the null) induced by the assumption of logistic random link-specific utility. While this is a strong assumption, it comes with considerable pay-off: we are (i) able to exactly control size in (ii) the presence of a high dimensional nuisance parameter while (iii) also making no assumptions about equilibrium selection. Exponential family structures has proved highly fruitful in other areas of econometrics; applications in panel data being most closely connected to the present setting. Our similarity and local optimality results build on classic results in the theory of testing in exponential families (e.g., Ferguson_MS67 and Lehmann_Romano_TSH05).
While obvious, and generic to most testing problems, it is important to understand that our test may have low power in some directions (in extreme cases even power equal to size). As an example imagine agents gain utility from linking with popular agents (as in preferential attachment models), such that $g_{i}\left(\mathbf{d}\right)=\sum_{j\neq i}d_{ij}\left[\sum_{k\neq i}d_{kj}\right]$. This model yields $s_{ij}\left(\mathbf{d}\right)=\sum_{k\neq i}d_{kj}$, which is almost equal to the indegree of agent $j$. Hence the distribution of $s_{ij}\left(\mathbf{D}\right)$ across $\mathbb{D}_{\mathbf{s},\mathbf{m}}$ will be nearly degenerate. Examples of this type are not unique to our setting. See Lehmann_Romano_TSH05 for general impossibility results.
Finally, while we are able to prove that our simulation algorithm works for $\tau$ “large enough", we don't currently have a formal handle on the mixing properties of our procedure. This is not just a limitation of our work, but of much of the related work in the discrete math and computer science literature (e.g., Cooper_Comb_2007 and Erdosr_Comb_2018). Our limited simulation experiments suggest relatively fast mixing. \footnote{A simple heuristic is to increase $\tau$ until one's results are not sensitive to further increases in it.}
These limitations notwithstanding, we nevertheless see potential for the widespread use of the methods presented in this paper in empirical social and economic network research (and, with modification, in other settings where strategic interaction is important). We hope that the ability to easily embed formal game-theoretic models of network formation of the type surveyed by, for example, Jackson_NetBook08 and Goyal_Book2021, into heterogeneity-rich dyadic linking models will be attractive to empirical researchers. While not emphasized here, we also expect our simulation algorithm to find use in other settings where binary matrix simulation is an important part of researchers' toolkits Gotelli_EC2000. Finally our focus on score type tests may represent a fruitful direction for further research on testing in incomplete models Chen_Kaido_WP2021.
The Supplemental Web Appendix shows how to adapt our results to bi-partite networks. There we show how ideas in this paper might be used to, for example, study airline entry into different routes as in Ciliberto_Tamer_EM2009. The set-up allows for complex airline preferences over their own route map as well as how they vary with the route maps chosen by their competitors. We also shows how our simulation algorithm can be used for more traditional conditional likelihood estimation and inference problems. A carefully annotated Python Jupyter, Notebook illustrating how the methods in this paper work in practice, is available in the Supplemental Materials.
\setcounter{page}{0} \pagenumbering{arabic} \setcounter{page}{1}