extfieldsofstudy:
Computer Science
Economics
Physics

text:
The Relation Between Global Migration and Trade Networks

In this paper we develop a methodology to analyze and compare multiple global networks. We focus our analysis on the relation between human migration and trade. First, we identify the subset of products for which the presence of a community of migrants significantly increases trade intensity. To assure comparability across networks, we apply a hypergeometric filter to identify links for which migration and trade intensity are both significantly higher than expected. Next we develop an econometric methodology, inspired by spatial econometrics, to measure the effect of migration on international trade while controlling for network interdependencies. Overall, we find that migration significantly boosts trade across sectors and we are able to identify product categories for which this effect is particularly strong.

I. INTRODUCTION
Since the mid 1990s a growing body of research has investigated the relation between global networks of international trade, information flows and migrations. Whereas traditional trade theory (e.g. the standard Heckscher-Ohlin model) suggests that the movement of goods across borders can provide a substitute for the movement of production factors, the bottom line of this branch of research is that the two actually complement each other. This appears to hold for different countries [for the US, Canada and Spain respectively, see 1,2,3] and has recently been confirmed by a meta-analysis covering 48 different studies [4].
Most of the literature referred to above shares a common empirical strategy, based on the estimation of a log-linear gravity model where bilateral trade flows are regressed over standard explanatory variables (economic mass and distance), the stock of immigrants from specific partner countries and other controls aiming at capturing various types of trade costs (common language, colonial relationships and the like). The most influential contributor to the field is probably James Rauch who, in a series of papers with a variety of co-authors, looks at the role of ethnic immigrants networks in facilitating trade. The core of the argument is that formal and informal links among co-ethnic migrants in other countries and at home, the "network" in Rauch's terminology, facilitate trade by providing potential trading partners with easier access to valuable, i.e. qualified, information. The pro-trade effect thus stems from the reduction of the trade barriers and search costs associated with market transactions. Since these costs are likely to be larger for international trade due to distance, language and cultural differences, legal provisions and the like, "networks" end up being especially relevant in facilitating cross-border transactions. Indeed, the central result in Rauch and Trindade [5] is that the positive effect of migration on trade is larger for "differentiated goods", i.e. those items that are not homogeneous and are not traded in organized exchanges therefore rendering that knowledge about counterpart reputation particularly valuable.
Similar results have been replicated by a number of subsequent authors. Peri and Requena-Silvente [3], for instance, analyze the Spanish case and find that doubling the number of immigrants from a given country increases export to the same destination by 10 percent. This effect is higher for firms selling differentiated products and for more distant countries (geographically or culturally). All of these elements are consistent with the notion that networks (in this case the presence of a large community of expatriates and their connections with co-nationals at home and abroad) lower the hurdle in terms of economic interactions, providing better access to information and trade opportunities and reducing the fixed costs associated with entry into a foreign market.
Easier access to information via co-ethnic migrants does not only increase export from the recipient to the home countries, but also facilitates "chain migration": it is typical for communities with a significant presence of migrants to attract more migrants from the same community. This feature is consistent with the preferential attachment mechanism that accurately describes the evolution of many real-world networks (from airline traffic to the World Wide Web, from social ties to financial networks) and makes migration interesting in terms of complex network analysis. Yet, not much has been written on the subject: Slater [6] studies clustering in US internal migration, whereas Simini et al. [7] presents a stochastic radiation model that can be used to predict international migration patterns.
More recently, Fagiolo and Mastrolillo [8] study the topology of the migration network, and its evolution over the period 1960-2000. They find that the network (where links between two countries A and B are given by the stock of migrants originated in country A and living in country B in a given year) is disassortative and highly clustered, and displays a small-world binary pattern. Furthermore, they show that the structural properties of the network are mainly driven by socioeconomic, geographical, and political factors. In a second paper [9] they look at the interplay between trade and migration, finding that the two networks are strongly correlated, and country-pairs that are more central in the migration network tend to trade more.
In this paper we aim at filling this gap by analyzing the relationship between migration and trade through the lens of complex network analysis and spatial econometrics. To do so, we first make the networks comparable, using a hypergeometric benchmark to judge if the link intensity between two countries is significantly higher than expected. Next, we run a set of econometric regressions, checking for network interdependencies: by means of spatial econometric techniques, we check for the presence of network (auto)correlations between trade and migration, disentangling the analysis in different parts, and using the previously defined network matrices as weights in spatial autoregressive models. Our goal is to identify the subset of products whose export/import is the most highly related to the presence of a community of migrants. This paper is structured as follows. In Section II we describe migration and trade data, as well as our methodological approach. In Section III we analyze and compare the migration and trade networks by distinguishing 3 different product types. In Section IV we presents the econometric analysis and discuss the findings. Finally, Section V contains discussions of our main results, further research directions and conclusions.

A. Migration and trade data
In this paper we use data regarding migrants from The World Bank's Global Bilateral Migration dataset In addition, to improve our analysis, we look at the SITC product code traded between each country pair and perform a decomposition of goods following the Rauch classification [5]. We thus distinguish between homogeneous and differentiated goods: the former are those with a reference price, whether it be a result of organized exchanges or simply of price quotations in a specialized journal; while the latter are without such a reference price and can be thought of as 'branded' commodities. An important distinction between these two categories is that homogeneous product prices can be quoted without mentioning the name of the manufacturer, like many chemical compounds for example, letting specialized traders stay informed regarding their prices around the globe and perform international commodity arbitrage by matching distant buyers and sellers much like traders in an organized exchange. In other words for this category of products it is immediately apparent if the differential between the two countries' markets is large enough to cover customs and transportation costs.
On the contrary, differentiated products are such that their commodity categories are usually not well defined (e.g. footwear); they need to be disaggregated into various sub-types, a process that leads to the limit where each category contains only one supplier. These products are, in this respect, 'branded' or differentiated. From this definition one would expect for international trade to be more heavily influenced by migrant networks for this second class of products, as buyers and sellers need to be matched in the product characteristics space. This is indeed the result found by Rauch [5] and one of the aspects we test in this paper.
Our aim is to use the two datasets together. In this respect, we retain only the countries present in both of them to enhance comparability. Doing this we end up with a set of 146 nodes, that populate both the trade and migration networks. 4

B. Methodology
The different nature of the data, both with regards to type and measurement unit, make a direct comparison of the trade and migration networks unreliable. As such what is needed is a tool to make the two datasets comparable. To address this issue, we use a stochastic benchmark for normalization purposes, as recently used in [12] and previously introduced in [13]. This method has been used to identify statistically significant portions of data in fields ranging from genetics to network theory [14,15].
For two countries, A and B, let N A be the value of goods exported by country A and N B the value of goods imported by country B. The total value of traded goods is N k and the observed value of goods exported from A to B is N AB . Under the null hypothesis of random co-occurrence, that is to say, customers in country B who are indifferent to the nationality of the exporter, the probability of observing X thousands US dollars of goods traded is given by the hypergeometric distribution and we can associate a p-value with the observed N AB as Note that the described null hypothesis directly takes into account the heterogeneity of countries with respect to the total value of goods traded (row and column totals). For each pair of countries, we separately evaluate the p-value for each trade relationship and then use a cutoff to select only those links that represent a significant departure from the hypergeometric benchmark (p < .01). The resulting matrices are then dichotomized 1 . Thanks to our stochastic approach we can treat a weighted network as a random graph in which any link has a probability of occurrence. We use this method to filter both trade and migration networks, to make them comparable.
In the next Section we study the structural properties of trade and migration networks. We use then networks as weight matrices in a spatial gravity model of trade flows (Section IV).

III. NETWORK ANALYSIS
We first describe and compare some basic topological properties of the two networks separately (Section III-A); we then to analyze the interconnections and correlations among their links (Section III-B).

A. Topological properties
In this section we introduce and analyze some topological indicators of the migration and trade (both total and separated in differentiated and homogeneous products) networks for the year 2000.
One of the most important topological properties of a network is the degree distribution, P (k). This quantity measures the probability of a randomly chosen vertex to have k neighbors. Figure 1 (main) shows the undirected cumulative distribution of trade and migration networks, defined as P c (k) ≡ k >k P (k ). In all cases the cumulative distributions show a flat approach from the origin, similar to the Erdös-Rényi (ER) network; but then, at about k = 10, the distributions follow a power law decay, with a strong deviation from the exponential 1 The hypergeometric multi-urn benchmark is equivalent to the Monte Carlo degree-preserving network rewiring procedure [16] 5 tail predicted by the classical random graph theory. This is especially true for the trade networks' cumulative distribution, whereas the migration case has a less evident power law behavior and deviation from the ER case. Table I presents a selection of well-known statistics for these networks. We can observe that the trade networks share, in general, very similar properties, although they are always slightly different for the migration case. In particular, while the migration network has a lower connectivity, as indicated by the nodes' average degree and density, its links are more reciprocal, meaning that a bilateral bond is more common than in commercial trades. Another important aspect is the hierarchical structure of the networks, which is usually analyzed by means of the clustering coefficient and degree-degree correlation. The clustering coefficient of vertex i is defined as  17], indicating that the hypergeometric filtering we used in our work to dilute it resulted in the loss of the clustered structure of the network. Hierarchy is also reflected in the degree-degree correlation through the conditional probability P (k|k ), i.e. the probability that a vertex of degree k is linked to a vertex of degree k. This function is difficult to measure, due to statistical fluctuations, and it is usually substituted by the average nearest neighbors degree (ANND), defined as k nn (k) = k k P (k |k) [18]. For independent networks this quantity would result independent of k. Figure 1 (inset) reports the ANND for the migration and trade networks, showing a dependency on the vertex's degree and indicating that in all the networks highly connected vertices tend to connect to poorly connected vertices (which is usually called dissortative behavior).
It is clear how this phenomenon is much more pronounced in trade than in migration, as can also be seen by the assortativity coefficient 2 in Table I.

B. The Relation between migration and trade
A first approach to analyzing the interplay between international trade and human migration is to observe whether, for a pair of countries, a strong bond in one aspect is related to a strong tie in anther. To do this we make use of the Jaccard index [19] that, given two sets of events, is defined as J = |A ∩ B| / |A ∪ B|, therefore representing the ratio between the number of events shared between the two sets, over the number of events in at least one of them. In our case the events will represent that the link between two countries is significant 3 both in the trade and the migration networks.
In Figure 2  In Tables II and III we also list the top and bottom countries and products, respectively, that appear in the distributions.
To verify the validity of the Rauch classification [5] we repeated the same analysis separating differentiated and homogeneous goods: in the main panel of Fig. 3 we plot the distribution of the Jaccard index for individual products while in the inset we show the Jaccard index for the entire networks in the years 1970-2000. As one can observe, in this first analysis the Rauch classification seems to be verified by our results, with values for the differentiated products generally higher for both individual SITC codes and the whole networks.
To further investigate this point, in Section IV we compare the results for the classification proposed by Rauch and the that emerges from the overlapping of the trade and migration networks (see Table III). In particular, we take the top-N products 4 from our ranking and compare them with Rauch's differentiated ones, and do the 7 same for the bottom ranked with homogeneous commodities. We call these two new categories overlapping and non-overlapping 5 .

IV. ECONOMETRIC APPROACH
Gravity models have often been used to explain Origin-Destination (OD) flows that arise in fields such as trade, transportation and migration. The term spatial interaction models has been used in the literature to label models that focused on flow between origins and destinations [20]. A great deal of literature on theoretical foundations for this model exists [21,22], as well as literature focused on empirical studies [21,22,23,24].
These models rely on a function of the distance between an origin and destination in addition to explanatory variables pertaining to characteristics of both origin and destination regions. Spatial interaction models assume that using distance as a variable will eradicate the spatial dependence among the OD pairs. However, the notion that using of distance functions in conventional interaction models effectively captures spatial dependence in interregional flows has long been challenged.
It has been recently fully recognized that a spatial interaction effect exists [25,26,27,28], essentially due to the spatial spillover and the third country effect. This motivates the introduction of the spatial autoregressive Other formulations are also proposed based on an inverse distance approach, as well as on the similarity of technologies in the pair or regions. It is important to underline that the neighboring regions of OD flows include neighbors of the origin location, neighbors of the destination location, and perhaps a link between neighbors of the origin and neighbors of the destination regions. To account for this, the matrix dimension that suits in this case is n 2 × n 2 , and it is generally constructed (as LeSage and Pace proposed [29]) as the Kronecker product of the W matrix with itself.
Network theory and spatial econometrics are intimately connected. Leenders [30] proposed using SAR models employing an ad-hoc W matrix based on the network relations (in terms of social influences and communication); Farber et al. [31] analyzed the relationship between the topology property of networks and the properties of spatial models, performing some simulation tests. Mansky's paper [32] is seminal, as it laid the foundation for analyzing the exogenous, endogenous and correlated effects that researchers encounter both in network and econometric theory. Lee, Liu and Lin [33], following Mansky's work, proposed a specification and estimation of network econometric models, in the presence of exogenous, endogenous and correlated effects.
Furthermore, the discussion on the specification and estimation of the network econometric models has become quite widespread as of late [34,35]. To control for network effects, here we use a similar approach and replace the spatial weight the network of trade weight matrix. 10 The specification of the W matrix becomes the following: W : w i,j =1 if i has a significant trade relationship with j (p < 0.1), w i,j = 0 otherwise.

A. Model specification
Le Sage and Pace [29] proposed to revise spatial specification for OD relationships based on two classes of models: Spatial autoregressive models (SAR) and Spatial Durbin / Spatial error models (SDM/SEM). The former is motivated by a time relationship describing a diffusion process over space; the latter by the omitted variables argument. We can think of the omitted variable as an unobserved tendency of trade due to network interdependencies.
The econometric representation of the models can be illustrated as: SAR: SDM: which becomes the SEM model in the event that included and excluded variables are not correlated (Common factor test can be performed [29]). SEM:

B. Estimation methods
The concentrated maximum likelihood estimated proposed by Anselin [36] and revised by LeSage and Pace [29] generally fits the spatial gravity model of trade. This methods is based on the computation of the logdeterminant, which is quite time-consuming. Fortunately, new technical results regarding the calculation of the log determinant have recently come to light, which facilitates estimations [37,38,39]. One caveat for this method is that for cases in which a large number of zero flows exists, the method is not appropriate.
Maximum likelihood (ML) estimation requires that the dependent variable vector follow a normal distribution, or that it is able to be suitably transformed to achieve normality. A partial solution is generally the logarithmic transformation. Another solution is to consider trade as count data using the Poisson model [40].

C. Data, application and econometric results
We conduct a cross-section on two different years, 1970 and 2000, on a sample of 146 world countries. For each year we test a cross section using three different dependent variables: (i) total trade; (ii) differentiated goods; (iii) non-differentiated goods. This allows us to test the Rauch theory, in addition to commenting on the relations between trade of differentiated goods and migration.
The gravity model is a benchmark in international trade and seems to be the best choice for our aims. For the gravity model the trade flow depends on the economic dimension of both the origin and the destination country, 11 and on the distance between the couple. Following this approach, we use the gross domestic product (per capita) and the population as control variables. Furthermore, we control for contiguity, for free trade agreements and for common language and currency, much like what is done in many empirical applications regarding the gravity model of trade. We found all of these variables within the CEPII dataset [41,42]. However, the control variable we are most interested in are the migrants stocks: we collected this data from the World Bank dataset [10].
Appending the spatial autoregressive components in the econometric formula of the gravity model seems to be fundamental in order to grasp the potential contributions of the networks of trade and migration. The concentrated maximum likelihood estimation is the most frequently used estimation method in spatial econometrics because it overcomes issues related to the intrinsic endogeneity in the spatial models. However, the ML estimates require normal distribution, which rarely happens when zero flows are present. We resolve this issue by performing a logarithmic transformation of the dependent and the control variables.
We did a likelihood ratio (LR) and common factor test to choose from different specifications of spatial econometric models, and the results of these tests point in favor of the Durbin model with both the autoregressive component in the dependent variable (trade) and in the control variables (including stock of migration).
In the previous section, we computed four 146 × 146 matrices for two distinct time periods (the years 1970 and 2000), representing the (i) network of country to country migration; (ii) network of country to country total trades; (iii) network of country to country differentiated goods; (iv) network of country to country nondifferentiated goods. We use these matrices as weight matrices in the spatial econometric model, which can be basically represented in this fashion: where with tr we represent the total trade between pair of countries, dtr the amount for the differentiated goods and ndtr the non-differentiated goods. 1970 and 2000 remain the time periods. ρ is the coefficient of the lagged trade term, β 1 the coefficients of the benchmark control variables like GDP and population, β 2 is the migration coefficient and γ is the lagged migration coefficient. Moreover, m stay for stock of migration.
To conclude, W t is the n 2 × n 2 network of total trade Kronecker matrix, W tf is the n 2 × n 2 network of differentiated trade, W tn is the n 2 × n 2 network of non-differentiated trade and W m is the n 2 × n 2 network of migration.
We also perform the baseline gravity model using a new dependent variable representing a novel version of differentiated products that we call overlapping (see Section III-B).
We computed these models in R with the spdep package. Results are shown in Tables IV, VI   can see a more substantial effect of migration on the differentiated ones (see Table IV); 13  • the lagged stock of migration (γ) also has a positive impact of trade. This means that, if country i trades with country j, and the country j has an high stock of migrants, the trade from i to a third country k will also increase; • using the Rauch classification, this phenomenon is stronger for non-differentiated goods in 1970, while for differentiated goods in 2000. Using our classification, this phenomenon is still not strongly significative for differentiated goods (see Table V); • ρ has negative sign for all the models used in Rauch classification. It means that, if a country i imports from country j, and the country j has a high level of trade, imports of i from a third country k will decrease (substitution effect). Using the Rauch classification, these coefficients are still negative, altough they are not significative; cascading failures and the transmission of shocks across multiple and heterogeneous network structures. In this paper we contribute to this emerging field of research by analyzing the relationship between the network of human migration and the world trade web. To make different networks comparable, we apply a hypergeometric benchmark to identify significant cross-country relationships. We find that the presence of a stock of migrants in a foreign country has a positive impact on trade. This is particularly true for a subset of products that we identify in Section III. However, when we move to test a gravity model of trade controlling for network interdependencies, we do not find any significant difference between the trade of differentiated and homogeneous goods. Since multiple communities of migrants are simultaneously present in developed countries, when we move to consider competition among them and network substitution effects we do not find any particular information advantage for differentiated goods. However, our results in this paper must be considered as preliminary. Spatial econometrics techniques have a huge potential to include network effects in traditional gravity models. In future work we plan to accommodate multiple and different network effects in this setting. Moreover, since the traditional distinction between differentiated and homogeneous goods does not seem to be particularly informative, we plan to investigate the changing role that migrants play in favoring the trade of specific commodities.


extfieldsofstudy:
Computer Science
Mathematics

text:
Dynamic Coalitional TU Games: Distributed Bargaining among Players' Neighbors

We consider a sequence of transferable utility (TU) games where, at each time, the characteristic function is a random vector with realizations restricted to some set of values. The game differs from other ones in the literature on dynamic, stochastic or interval valued TU games as it combines dynamics of the game with an allocation protocol for the players that dynamically interact with each other. The protocol is an iterative and decentralized algorithm that offers a paradigmatic mathematical description of negotiation and bargaining processes. The first part of the paper contributes to the definition of a robust (coalitional) TU game and the development of a distributed bargaining protocol. We prove the convergence with probability 1 of the bargaining process to a random allocation that lies in the core of the robust game under some mild conditions on the underlying communication graphs. The second part of the paper addresses the more general case where the robust game may have empty core. In this case, with the dynamic game we associate a dynamic average game by averaging over time the sequence of characteristic functions. Then, we consider an accordingly modified bargaining protocol. Assuming that the sequence of characteristic functions is ergodic and the core of the average game has a nonempty relative interior, we show that the modified bargaining protocol converges with probability 1 to a random allocation that lies in the core of the average game.

Introduction
Coalitional games with transferable utilities (TU) have been introduced by von Neumann and Morgenstern [27]. A coalitional TU game constitutes of a set of players, who can form coalitions, and a characteristic function that provides a value for each coalition. The value of a coalition can be thought of as a monetary value that can be divided among the members of the coalition according to some appropriate fairness allocation rule.
Coalitional TU games have been used to model cooperation in supply chain or inventory management applications [6,10], as well as in network flow applications to coordinate flows of goods, materials, or resources between different production/distribution sites [2]. Recently, coalitional games have also sparked much interest in communication networks. We refer an interested reader to tutorial [23] for an in-depth discussion on potential applications in this field.
In this paper, we consider a sequence of coalitional TU games for a finite set of players. We assume that the game is played repeatedly over time thus generating a sequence of time varying characteristic functions. We refer to such a repeated game as dynamic coalitional TU game. In addition, we assume that a player need not necessarily observe the allocations of all the other players, but he can only observe the allocations of his neighbors, where the neighbors may change in time.
In this setting, we consider robust and average TU games, and for each of these games we propose an allocation process to reach a solution of the dynamic game. More specifically, we formulate a dynamic bargaining process as a dynamically changing constrained problem. Iterations are simply bargaining steps free of any concrete reward allocation. We assume that the reward allocation occurs only once at the end of the bargaining process, when the players have agreed on how to allocate rewards among themselves. Our main objective is to explore distributed agreement on solutions in the core of the game, where the players interact only with their neighbors.
In particular, we consider bargaining protocols assuming that each player i obeys rationality and efficiency by deciding on an allocation vector which satisfies the value constraints of all the coalitions that include player i. This set is termed bounding set of player i. At every iteration, a player i observes the allocations of some of his neighbors. This is modeled using a directed graph with the set of players as the vertex set and a time-varying edge set composed of directed links (i, j) whenever player i observes the allocation vector proposed by player j at time t. We refer to this directed graph as players' neighbor-graph. Given a player's neighbor-graph, each player i negotiates allocations by adjusting the allocations he received from his neighbors through weight assignments. As the balanced allocation may violate his rationality constraints (it lies outside player i's bounding set), the player selects a new allocation by projecting the balanced allocation on his bounding set. We propose such bargaining protocols for solving both the robust and the average TU game. For each of these games, we use some mild assumptions on the connectivity of the players' neighbor-graph and the weights that the players use when balancing their own allocations with the neighbors' allocations. Assuming that the core of the robust game is nonempty, we show that our bargaining protocol converges with probability 1 to a common (random) allocation in the core. In the case when the core of the robust game is empty, we consider an average game that can provide a meaningful solution under some conditions on the sequence of the characteristic functions. Specifically, in this case, we consider a dynamic average game by averaging over time the sequence of characteristic functions. We then modify accordingly the bounding set and the associated bargaining process by using the dynamic average game. This means that the value constraints are defined by using the time-averaged sequence rather than the sequence of random characteristic functions. Under the assumptions that the time-averaged sequence is ergodic and that the core of the average game has a nonempty relative interior, we show that the players' allocations generated by our bargaining protocol converge with probability 1 to a common (random) allocation in the core of the average game.
The main contributions of this paper are in the two-fold dynamic aspect of the games, and in the development and the analysis of distributed bargaining process among the players. The novelty in the dynamic aspect is in the consideration of games with timevarying characteristic functions and the use of time-varying local players interactions.
The work in this paper is related to stochastic cooperative games [9,24,25]. However, we deviate from this stochastic framework in a number of aspects among which are the existence of a local players interactions captured by players' neighbor-graph and the presence of multiple iterations in the bargaining process, and the consideration of robust game. Bringing dynamical aspects into the framework of coalitional TU games is an element in common with papers [8,11]. However, unlike [8,11], the values of the coalitions in this paper are realized exogenously and no relation is assumed between consecutive samples. Dynamic robust TU games have been considered in [3] and [4] but for a continuous time setting in the former work and for a centralized allocation process in the latter one. Convergence of allocation processes is a main topic in [5,13]. There, rewards are allocated by a game designer repeatedly in a centralized manner and based on the current excess rewards of the coalitions (accumulated reward up to current time minus the value of the coalition). Our approach, however, differs from that of [5,13] as we resort to a decentralized scheme where the allocation process is the result of a bargaining process among the players with local interactions. Convergence of bargaining processes has also been explored under dynamic coalition formation [1] for a different dynamic model, where players decide both on which coalition to address and what payoff to announce. Coalitions form when announced payoffs are all met for all players in the coalition. Our bargaining procedure is different as it produces an agreement resulting in the formation of grand coalition, which is stable with respect to any sub-coalitions.
The work in this paper is also related to the literature on agreement among multiple agents, where an underlying communication graph for the agents and balancing weights have been used with some variations [26,15] to reach an agreement on common decision variable, as well as in [16,17,20,19] for distributed multi-agent optimization.
This paper is organized as follows. In Section 2, we introduce the dynamic TU game, the robust game and the bargaining protocol for this game. We then motivate the game and give some preliminary results. In Section 3, we prove the convergence of the bargaining protocol to a point in the core of the robust game with probability 1. In Section 4, we introduce the dynamic average game and the modified bargaining protocol. We also prove the convergence of this protocol to an allocation in the core of the average game with probability 1. In Section 5, we report some numerical simulations to illustrate our theoretical study, and we conclude in Section 6. Notation. We view vectors as columns. For a vector x, we use x i or [x] i to denote its ith coordinate component. For two vectors x and y, we use x < y (x ≤ y) to denote x i < y i (x i ≤ y i ) for all coordinate indices i. We let x denote the transpose of a vector x, and x denote its Euclidean norm. An n × n matrix A is row-stochastic if the matrix has nonnegative entries a ij and n j=1 a ij = 1 for all i = 1, . . . , n. For a matrix A, we use a ij or [A] ij to denote its ijth entry. A matrix A is doubly stochastic if both A and its transpose A are row-stochastic. Given two sets U and S, we write U ⊂ S to denote that U is a proper subset of S. We use |S| for the cardinality of a given finite set S.
We write P X [x] to denote the projection of a vector x on a set X, and we write dist(x, X) for the distance from x to X, i.e., P X [x] = arg min y∈X x − y and dist(x, X) = x − P X [x] , respectively. Given a set X and a scalar λ ∈ R, the set λX is defined by λX {λx | x ∈ X}. Given two sets X, Y ⊆ R n , the set sum X + Y is defined by Given a set N of players and a function η : S → R defined for each nonempty coalition S ⊆ N , we write < N, η > to denote the transferable utility (TU) game with the players' set N and the characteristic function η. We let η S be the value η(S) of the characteristic function η associated with a nonempty coalition S ⊆ N . Given a TU game < N, η >, we use C(η) to denote the core of the game,

Dynamic TU Game and Robust Game
In this section, we discuss the main components of a dynamic TU game and a robust game. We state some basic assumptions on these games and introduce a bargaining process conducted by the players to reach an agreement on their allocations. We also provide some examples of the TU games motivating our development and establish some basic results that we use later on in the convergence analysis of the bargaining process.

Problem Formulation and Bargaining Process
Consider a set of players N = {1, . . . , n} and the set of all (nonempty) coalitions S ⊆ N arising among these players. Let m = 2 n − 1 be the number of possible coalitions. We assume that the time is discrete and use t = 0, 1, 2, . . . to index the time slots. We consider a dynamic TU game, denoted < N, {v(t)} >, where {v(t)} is a sequence of characteristic functions. Thus, in the dynamic TU game < N, {v(t)} >, the players are involved in a sequence of instantaneous TU games whereby, at each time t, the instantaneous TU game is < N, v(t) > with v(t) ∈ R m for all t ≥ 0. Further, we let v S (t) denote the value assigned to a nonempty coalition S ⊆ N in the instantaneous game < N, v(t) >.
In what follows, we deal with dynamic TU games where each characteristic function v(t) is a random vector with realizations restricted to some set of values. We will consider the robust TU game in this section and Section 3, while in Section 4 we deal with the average TU game.
In our development of robust TU game, we impose restrictions on each realization of v(t) for every t ≥ 0. Specifically, we assume that the grand coalition value v N (t) is deterministic for every t ≥ 0, while the values v S (t) of the other coalitions S ⊂ N have a common upper bound. These conditions are formally stated in the following assumption.
for all nonempty coalitions S ⊂ N.
We refer to the game < N, v max > as robust game. In the first part of this paper, we rely on the assumption that the robust game has a nonempty core.

Assumption 2
The core C(v max ) of the robust game is not empty.
An immediate consequence of Assumptions 1 and 2 is that the core C(v(t)) of the instantaneous game is always not empty. This follows from the fact that C(v max ) ⊆ C(η) for any η satisfying η N = v max N and η S ≤ v max S for S ⊂ N , and the assumption that the core C(v max ) is not empty.
Throughout the paper, we assume that each player i is rational and efficient. This translates to each player i ∈ N choosing his allocation vector within the set of allocations satisfying value constraints of all the coalitions that include player i. This set is referred to as the bounding set of player i and, for a generic game < N, η >, it is given by In what follows, we find it suitable to represent the bounding sets and the core in alternative equivalent forms. For each nonempty coalition S ⊆ N , let e S ∈ R n be the incidence vector for the coalition S, i.e., the vector with the coordinates given by Then, the bounding sets and the core can be represented as follows: Furthermore, observe that the core C(η) of the game coincides with the intersection of the bounding sets X i (η) of all players i ∈ N = {1, . . . , n}, i.e., We now discuss the bargaining protocol where repeatedly over time each player i ∈ N submits an allocation vector that the player would agree on. The allocation vector proposed by player i at time t is denoted by x i (t) ∈ R n , where the jth component x i j (t) represents the amount that player i would assign to player j. To simplify the notation in the dynamic game < N, {v(t)} >, we let X i (t) denote the bounding set of player i for the instantaneous game < N, v(t) >, i.e., for all i ∈ N and t ≥ 0, We assume that each player may observe the allocations of a subset of the other players at any time, which are termed as the neighbors of the player. The players and their neighbors at time t can be represented by a directed graph G(t) = (N, E(t)), with the vertex set N and the set E(t) of directed links. A link (i, j) ∈ E(t) exists if player j is a neighbor of player i at time t. We always assume that (i, i) ∈ E(t) for all t, which is natural since every player i can always access its own allocation vector. We refer to graph G(t) as a neighbor-graph at time t. In the graph G(t), a player j is a neighbor of player i (i.e., (i, j) ∈ E(t)) only if player i can observe the allocation vector of player j at time t. Figure 1 illustrates how the players' neighbor-graph may look at two time instances.
Given the players' neighbor-graph G(t), each player i negotiates allocations by averaging his allocation and the allocations he received from his neighbors. More precisely, at time t, the bargaining process for each player i involves the player's individual bounding set X i (t), its own allocation x i (t) and the observed allocations x j (t) of some of his neighbors j. Formally, we let N i (t) be the set of neighbors of player i at time t (including himself), i.e., N i (t) = {j ∈ N | (i, j) ∈ E(t)}.
With this notation, the bargaining process is given by: where a ij (t) ≥ 0 is a scalar weight that player i assigns to the proposed allocation x j (t) of player j and P X i (t) [·] is the projection onto the player i bounding set X i (t). The initial allocations x i (0), i = 1, . . . , n, are selected randomly and independently of {v(t)}. The bargaining process in (5) can be written more compactly by introducing zero weights for players j whose allocations are not available to player i at time t. Specifically by defining a ij (t) = 0 for all j ∈ N i (t) and all t ≥ 0, we have the following equivalent representation of the bargaining process: for all i ∈ N and t ≥ 0.
Here, a ij (t) = 0 for all j ∈ N i (t) while a ij (t) ≥ 0 for j ∈ N i (t).
We now discuss the specific assumptions on the weights a ij (t) and the players' neighborgraph that we will rely on. We let A(t) be the weight matrix with entries a ij (t). We will use the following assumption for the weight matrices.
Assumption 3 Each matrix A(t) is doubly stochastic with positive diagonal. Furthermore, there exists a scalar α > 0 such that In view of the construction of matrices A(t), we see that a ij (t) ≥ α for j = i and perhaps for some players j that are neighbors of player i. The requirement that the positive weights are uniformly bounded away from zero is imposed to ensure that the information from each player diffuses to his neighbors in the network persistently in time. The requirement on the doubly stochasticity of the weights is used to ensure that in a long run each player has equal influence on the limiting allocation vector.
It is natural to expect that the connectivity of the players' neighbor-graphs G(t) = (N, E(t)) impacts the bargaining process. At any time, the instantaneous graph G(t) need not be connected. However, for the proper behavior of the bargaining process, the union of the graphs G(t) over a period of time is assumed to be connected, as given in the following assumption.
Assumption 4 There is an integer Q ≥ 1 such that the graph N, Assumptions 3 and 4 together guarantee that the players communicate sufficiently often to ensure that the information of each player is persistently diffused over the network in time to reach every other player. Under these assumptions, we will study the dynamic bargaining process in (6). We want to provide conditions under which the process converges to an allocation in the core of the robust game. Before this, we provide some motivating examples in the following section.

Motivations
Dynamic coalitional games capture coordination in a number of network flow applications. Network flows model flow of goods, materials, or other resources between different production/distribution sites [2]. We next provide two examples. The first one is more practically oriented and describes a supply chain application [6]. The second one is more theoretical and re-casts the problem at hand in terms of controlled flows over hyper-graphs.

Supply chain
A single warehouse v 0 serves a number of retailers v i , i = 1, . . . , n, each one facing a demand d i (t) unknown but bounded by pre assigned values d min i ∈ R and d max i ∈ R at any time period t ≥ 0. After demand d i (t) has been realized, retailer v i must choose to either fulfill the demand or not. The retailers do not hold any private inventory and, therefore, if they wish to fulfill their demands, they must reorder goods from the central warehouse.
Retailers benefit from joint reorders as they may share the total transportation cost K (this cost could also be time and/or players dependent). In particular, if retailer v i "plays" individually, the cost of reordering coincides with the full transportation cost K. Actually, when necessary a single truck will serve only him and get back to the warehouse. This is illustrated by the dashed path (v 0 , v 1 , v 0 ) in the network of Figure 2(a). The cost of not reordering is the cost of the unfulfilled demand  If two or more retailers "play" in a coalition, they agree on a joint decision ("everyone reorders" or "no one reorders"). The cost of reordering for the coalition also equals the total transportation cost that must be shared among the retailers. In this case, when necessary a single truck will serve all retailers in the coalition and get back to the warehouse. This is illustrated, with reference to coalition {v 1 , v 2 } by the dashed path Figure 2 Figure 2(c). The cost of not reordering is the sum of the unfulfilled demands of all retailers. How the players will share the cost is a part of the solution generated by the bargaining process.
The cost scheme can be captured by a game with the set N = {v 1 , . . . , v n } of players where the cost of a nonempty coalition S ⊆ N is given by Note that the bounds on the demand d i (t) reflect into the bounds on the cost as follows: for all nonempty S ⊆ N and t ≥ 0, To complete the derivation of the coalitions' values we need to compute the cost savings v S (t) of a coalition S as the difference between the sum of the costs of the coalitions of the individual players in S and the cost of the coalition itself, namely, Table 1: Vertex-coalition correspondence for a 3-player coalitional game.
Given the bound for c S (t) in (7), the value v S (t) is also bounded, as given: for any Thus, the cost savings (value) of each coalition is bounded uniformly by a maximum value.

Network controlled flows
Here, we provide a more theoretical example where the bargaining process provides a way for the nodes of a hyper-graph to agree on the edge controlled flows [2]. Consider the hyper-graph H = {V, E} with the vertex set V = {v 1 , . . . , v m } and the edge-set E = {e 1 , . . . , e n }. The vertex set V has one vertex per each coalition, while the edge-set E has one edge per each player. An edge e i is incident to a vertex v j if the player i is in the coalition associated with v j . For a 3-player coalitional game, the vertex-coalition correspondence is shown in Table 1. The corresponding hyper-graph is shown in Figure 3. The incidence relations are described by a matrix B H = [e S ] S⊆N ∈ R m×n whose rows are the characteristic vectors of all coalitions S ⊆ N . The flow control reformulation arises naturally by viewing an allocation valueã i (t) of player i as the flow on the edge e i associated with player i. The demand d j (t) at a vertex v j is the value v S (t) of the coalition S associated with the vertex v j . In view of this, an allocation in the core translates into satisfying in excess the demand at the vertices, or formally: In this case, the efficiency condition i∈Nã i (t) = v N (t) corresponds to the equality constraint i∈Nã i (t) = d m (t). When d m (t) is a constant, say d m (t) = f for an f > 0, the resulting constraint i∈Nã i (t) = f can be interpreted as a total flow constraint, stating that the total flow in the network has to be equal to the given value f .
In this framework, the bargaining process is an algorithmic and distributed mechanism that ensures the players reach an agreement on controlled flows satisfying uncertain demand at the nodes.

Preliminary Results
In this section we derive some preliminary results pertinent to the core of the robust game and some error bounds for polyhedral sets applicable to the players' bounding sets X i (t). We later use these results to establish the convergence of the bargaining process in (6).
In our analysis we often use the following relation that is valid for the projection operation on a closed convex set X ⊆ R n : for any w ∈ R n and any x ∈ X, This property of the projection operation is known as a strictly non-expansive projection property (see [7], volume II, 12.1.13 Lemma on page 1120). We next prove a result that relates the distance dist(x, C(η)) between a point x and the core C(η) with the distances dist(x, X i (η)) between x and the bounding sets X i (η). This result will be crucial in our later development. The result relies on the polyhedrality of the bounding sets X i (η) and the core C(η), as given in (1) and (2) respectively, and a special relation for polyhedral sets. This special relation states that for a nonempty polyhedral set P = {x ∈ R n | a x ≤ b , = 1, . . . , r}, there exists a scalar c > 0 such that where H = {x ∈ R n | a x ≤ b } and the scalar c depends on the vectors a , = 1, . . . , r only. Relation (9) has been established by Hoffman [12] and is known as Hoffman bound. Aside from the Hoffman bound, in establishing the forthcoming Lemma 1, we also use the fact that the square distance from a point x to a closed convex set X contained in an affine set H is given by which is illustrated in Figure 4. Now, we are ready to present the result relating the values dist 2 (x, C(η)) and dist 2 (x, X i (η)).
Lemma 1 Let < N, η > be a TU game with a nonempty core C(η). Then, there is a constant µ > 0 such that  Proof. Since the hyperplane H contains the core C(η) (see (2)), by relation (10) we have The point P H [x] and the core C(η) lie in the n − 1-dimensional affine set H. By applying the Hoffman bound relative to the affine set H (cf. Eq. (9)), we obtain where the summation is over nonempty subsets S, where m is the number of nonempty subsets of N and the last inequality follows by ( j=1 a j ) 2 ≤ j=1 a 2 j , which is valid for any finite collection of scalars a j , j = 1, . . . , with ≥ 1. Combining Eq. (12) with equality (11), we obtain for any x ∈ R n , From the preceding relation, it follows for any x ∈ R n , where |S| denotes the cardinality of the coalition S. Note that We also note that X i (η) ⊂ H ∩ H S for each nonempty S ⊂ N and i ∈ S, which follows by the definition of H S and relation (1).
for any x ∈ R n and for any two closed convex sets X, By combining relations (13)-(15), we obtain where κ is the number of coalitions S that contain player i, which is the same number for every player (κ does not depend on i). The desired relation follows by letting µ = c 1 κ, and by recalling that c 1 = max{1, c 2 (m − 1)} and that c depends on the projectionsẽ S of vectors e S , S ⊂ N , on the hyperplane H. Note that the scalar µ in Lemma 1 does not depend on the coalitions' values η S for S = N . It depends only on the vectors e S , S ⊆ N , and the grand coalition value η N .
As a direct consequence of Lemma 1, we have the following result for the instantaneous game < N, v(t) > under the assumptions of Section 2.1.
Lemma 2 Let Assumptions 1 and 2 hold. We then have for all t ≥ 0, for all x ∈ R n , where C(v(t)) is the core of the game < N, v(t) >, X i (t) is the bounding set of player i, and µ is the constant from Lemma 1.
Proof. By Assumption 2, we have that the core C(v max ) is nonempty. Furthermore, under Assumption 1, we have C(v max ) ⊆ C(v(t)) for all t ≥ 0, implying that the core C(v(t)) is nonempty for all t ≥ 0. Under Assumption 1, each core C(v(t)) is defined by the same affine equality corresponding to the grand coalition value, e N x = v max N . Moreover, each core C(v(t)) is defined through the set of hyperplanes H S (t) = {x ∈ R n | e S x ≥ v S (t)}, S ⊂ N , which have time invariant normal vectors e S , S ⊆ N . Thus, the result follows from Lemma 1.

Convergence to Core of Robust Game
In this section, we prove convergence of the bargaining process in (6) to a random allocation that lies in the core of the robust game with probability 1. We find it convenient to re-write the bargaining protocol (6) by isolating a linear and a non-linear term. The linear term is the vector w i (t) defined as: for all i ∈ N and t ≥ 0.
Note that w i (t) is linear in players' allocations x j (t). The non-linear term is the error Now, using (16) and (17), we can rewrite protocol (6) as follows: Recall that the weights a ij (t) are nonnegative and such that a ij (t) = 0 for all j ∈ N i (t). Also, recall that A(t) is the matrix with entries a ij (t), which governs the construction of the vectors w i (t) in (16).
The main result of this section shows that, with probability 1, the bargaining protocol (16)- (18) converges to the core C(v max ) of the robust game < N, v max >, provided that v(t) = v max happens infinitely often in time with probability 1. To establish this we use some auxiliary results, which we develop in the next two lemmas.
The following lemma provides a result on the sequences x i (t) and shows that the errors e i (t) are diminishing. Proof. By x i (t+1) = P X i (t) [w i (t)] and by strictly non-expansive property of the Euclidean projection on a closed convex set X i (t) (see (8)), we have for any i ∈ N , t ≥ 0 and x ∈ X i (t), Under Assumptions 1 and 2, the core C(v max ) is contained in the core C(v(t)) for all t ≥ 0, implying that C(v max ) ⊆ C(v(t)) for all t ≥ 0. Furthermore, since C(v(t)) = ∩ n i=1 X i (t), it follows that C(v max ) ⊆ X i (t) for all i ∈ N and t ≥ 0. Therefore, relation (19) holds for all x ∈ C(v max ). Thus, by summing the relations in (19) over i ∈ N , we obtain for all t ≥ 0 and x ∈ C(v max ), By the definition of w i (t) in (16), using the stochasticity of A(t) and the convexity of the squared norm, we obtain By the doubly stochasticity of A(t), we have n i=1 a ij (t) = 1 for every j, implying By substituting this relation in (20), we arrive at The preceding relation shows that the scalar sequence { n i=1 x i (t + 1) − x 2 } is nonincreasing for any given x ∈ C(v max ). Therefore, the sequence must be convergent since it is nonnegative. Moreover, by summing the relations in (21) over t = 0, . . . , s and taking the limit as s → ∞, we obtain which implies that lim t→∞ e i (t) = 0 for all i ∈ N .
In our next result, we will use the instantaneous average of players allocations, defined as follows: The result shows that the difference between the bargaining payoff vector x i (t) for any player i and the average y(t) of these payoffs converges to 0 as time goes to infinity. The proof essentially uses the line of analysis that has been employed in [17], where the sets X i (t) are static in time, i.e., X i (t) = X i for all t. In addition, we also use the rate result for doubly stochastic matrices that has been established in [15]. Then, for every player i ∈ N we have Proof. For any t ≥ s ≥ 0, define matrices with Φ(t, t) = A(t). Using the matrices Φ(t, s) and the expression for x i (t) in (18), we can relate the vectors x i (t) with the vectors x i (s) at a time s for 0 ≤ s ≤ t − 1, as follows: [Φ(t − 1, r)] ij e j (r − 1) + e i (t − 1). (22) Under the doubly stochasticity of the matrices A(t), using y(t) = 1 n n j=1 x j (t) and relation (22), we obtain By our assumption, we have lim t→∞ e i (t) = 0 for all i. Thus, for any > 0, there is an integerŝ ≥ 0 such that e i (t) ≤ for all t ≥ŝ and all i. Using relations (22) and (23) with s =ŝ, we obtain for all i and t ≥ŝ + 1, Since e i (t) ≤ for all t ≥ŝ and all i, it follows that Under Assumptions 3 and 4, the following result holds for the matrices Φ(t, s), as shown in [14] (see there Corollary 1): Substituting the preceding estimate in the estimate for x i (t) − y(t) , we obtain Letting t → ∞, we see that Note that ∞ r=ŝ+1 1 − α 4n 2 t−r Q −2 < ∞, which by the arbitrary choice of yields Now, we focus on n i=1 w i (t) − y(t) . Since w i (t) = n j=1 a ij (t)x j (t) and since A(t) is stochastic, it follows Exchanging the order of the summations over, and then using the doubly stochasticity of Note that Lemma 4 captures the effects of the matrices A(t) that represent players' neighbor-graphs. At the same time, Lemma 3 is basically a consequence of the projection property only. So far, the polyhedrality of the sets X i (t) has not been used at all. We now put all pieces together, namely Lemma 2 that exploits the polyhedrality of the bounding sets X i (t), Lemma 3 and Lemma 4. This brings us to the following convergence result for the robust game < N, v max >. where i.o. stands for infinitely often. Then, the players allocations x i (t) generated by bargaining protocol (16)-(18) converge with probability 1 to an allocation in the core C(v max ), i.e., there is a random vectorx ∈ C(v max ) such that with probability 1, Proof. By Lemma 3, for each player i ∈ N , the sequence { n i=1 x i (t)−x 2 } is convergent for every x ∈ C(v max ) and the errors e i (t) are diminishing, i.e., e i (t) → 0. Then, by Lemma 4 we have x i (t) − y(t) → 0 for every i. Hence, We want to show that {y(t)} is convergent and that its limit is in the core C(v max ) with probability 1. For this, we note that since x i (t + 1) ∈ X i (t), it holds The preceding relation and x i (t) − y(t) → 0 for all i ∈ N (cf. Lemma 4) imply lim t→∞ n i=1 dist 2 (y(t + 1), X i (t)) = 0.
By our assumption, the event {v(t) = v max infinitely often} happens with probability 1. We now fix a realization {v ω (t)} of the sequence {v(t)} such that v ω (t) = v max holds infinitely often (for infinitely many t's). Let {t k } be a sequence such that v ω (t k ) = v max for all k.
All the variables corresponding to the realization {v ω (t)} are denoted by a subscript ω. By relation (24) the sequence {y ω (t)} is bounded, therefore {y ω (t k )} is bounded. Without loss of generality (by passing to a subsequence of {t k } if necessary), we assume that {y ω (t k )} converges to some vectorỹ ω , i.e., lim k→∞ y ω (t k ) =ỹ ω .
This and the assumption Prob {v(t) = v max i.o.} = 1, imply that the sequence {y(t)} converges with probability 1 to a random pointỹ ∈ C(v max ). Since by Lemma 4 we have x i (t) − y(t) → 0 for every i, it follows that the sequences {x i (t)}, i = 1, . . . , n, converge with probability 1 to a common random point in the core C(v max ).

Dynamic Average Game
When the core of the robust game is empty, the core of the instantaneous average game can provide a meaningful solution under some conditions on the distribution of the functions v(t). In what follows, we focus on the instantaneous average game associated with the dynamic TU game < N, {v(t)} >. In the next sections, we define the instantaneous average game, we introduce a bargaining protocol for the game and investigate the convergence properties of the bargaining protocol.

Average Game and Bargaining Protocol
Consider a dynamic TU game < N, {v(t)} > with each v(t) being a random characteristic function. With the dynamic game we associate a dynamic average game < N, {v(t)} >, wherev(t) is the average of the characteristic functions v(0), . . . , v(t), i.e., for all t ≥ 0.
An instantaneous average game at time t ≥ 0 is the game < N,v(t) >. We let C(v(t)) denote the core of the instantaneous average game at time t and letX i (t) denote the bounding set of player i for the instantaneous game < N,v(t) >, i.e., for all i ∈ N and t ≥ 0, In what follows, we assume that X i (t) are nonempty for all i ∈ N and all t ≥ 0. In this setting, the bargaining process for the players is given by where a ij (t) ≥ 0 is a scalar weight that player i assigns to the proposed allocation x j (t) received from player j at time t. The initial allocations x i (0), i ∈ N , are selected randomly and independently of {v(t)}. Regarding the weights a ij (t), recall that these weights are reflective of the players' neighbor-graph: a ij (t) = 0 for all j ∈ N i (t), where N i (t) is the set of neighbors of player i (including himself) at time t, while we may have a ij (t) ≥ 0 only for j ∈ N i (t).

Assumptions and Preliminaries
In this section, we provide our assumptions for the average game, and discuss some auxiliary results that we need later on in the convergence analysis of the bargaining protocol.
Regarding the random characteristic functions v(t) we use the following assumption.

Assumption 5
The sequence {v(t)} is ergodic, i.e., with probability 1, we have Furthermore, v N (t) = v mean for all t with probability 1.
Assumption 5 basically says that the grand coalition value v N (t) is constant with probability 1. Note that Assumption 5 is satisfied, for example, when {v S (t)} is an independent identically distributed sequence with a finite expectation E[v S (t)] for all S ⊂ N . We refer to the TU game < N, v mean > as average game, which is well defined under Assumption 5. We let C(v mean ) be the core of the average game andX i be the bounding set for player i in the game, i.e., (28) Note that the average core C(v mean ) lies in the hyperplane H = {x ∈ R n | e N x = v mean N }. Hence, the dimension of the core is at most n − 1. We will in fact assume that the dimension of the average core C(v mean ) is n − 1, by requiring the existence of a point z in the core such that all other inequalities defining the core are satisfied as strict inequalities.
Specifically, we make use of the following assumption.
Assumption 6 There exists a vectorẑ ∈ C(v mean ) such that e Sẑ > v mean S for all nonempty S ⊂ N.
Assumption 6 basically says thatẑ is in the relative interior of the core C(v mean ) of the average game and that the core C(v mean ) has dimension n − 1. This assumption will be important in establishing the convergence of the bargaining protocol (27). In particular, the following result will be important, which is an immediate consequence of Assumption 6 and the polyhedrality of the cores C(v(t)).
Lemma 5 Let Assumptions 5 and 6 hold. Then, with probability 1, for every z in relative interior of C(v mean ) there exists t z large enough such that z is in the relative interior of C(v(t)) for all t ≥ t z with probability 1.
Proof. Let z be in the relative interior of C(v mean ) which exists by Assumption 6. Thus, e N z = v mean N and e S z > v mean S for all S ⊂ N . By Assumption 5, with probability 1 we havev ) z for all t with probability 1. Furthermore, there exists a random time t z large enough so that with probability 1, e S z >v S (t) for all S ⊂ N and all t ≥ t z , implying that z is in the relative interior of C(v(t)) for all t ≥ t z with probability 1. Lemma 5 shows that the sets C(v(t)) and C(v mean ) have the same dimension for large enough t with probability 1. In particular, this lemma implies that the cores C(v(t)) are nonempty with probability 1 for all t sufficiently large. Aside from Lemma 5, in our convergence analysis of the bargaining protocol, we make use of two additional well-known results. One of them is the super-martingale convergence theorem due to Robbins and Siegmund [21] (it can also be found in [18], Chapter 2.2, Lemma 11).
Theorem 2 Let {V k }, {g k }, and {h k } be non-negative random scalar sequences. Let F k be the σ-algebra generated by V 1 , . . . , V k , g 1 , . . . g k , h 1 , . . . h k . Suppose that almost surely, and k h k < ∞ almost surely. Then, almost surely both the sequence {V k } converges to a non-negative random variable and k g k < ∞.
The other well-known result that we use is pertinent to two nonempty polyhedral sets whose description differs only in the right-hand side vector. The result can be found in [7], 3.2.5 Corollary, pages 258-259.

Lemma 6
Let P b and Pb be two polyhedral sets given by where B is an m × n matrix and b,b ∈ R m . Then, there is a scalar L > 0 such that for every b,b ∈ R m for which P b = ∅ and Pb = ∅, we have where the constant L depends on the matrix B.
For two polyhedral sets P b and Pb as in Lemma 6 we also have (see Rockafellar [22], 4.34 Lemma on page 132).

Convergence to Core of Average Game
Here, we show the convergence of the bargaining protocol to the core of the average game. In our analysis, we find it convenient to re-write the bargaining protocol (27) in an equivalent form by separating a linear and a non-linear term. The linear term is the vectorw i (t) given byw a ij (t)x j (t) for all i ∈ N and t.
The non-linear term is expressed by the error Now, using relations (30) and (31), we can rewrite (27) as follows: We first show some basic properties of the players' allocations by using the preceding equivalent description of the bargaining protocol (27). These properties hold under the doubly stochasticity of the weights a ij (t) that comprise the matrix A(t).
Lemma 7 Let Assumptions 5 and 6 hold. Also, let the matrices A(t) be doubly stochastic. Then, for bargaining protocol (30)-(32), we have with probability 1: (a) The sequence { n i=1 x i (t + 1) − z 2 } converges for every z in the relative interior of C(v mean ). Proof. Let rintY denote the relative interior of a set Y . Let z ∈ rintC(v mean ) be arbitrary and fixed for the rest of the proof. By Lemma 5, there exists t z large enough such that z ∈ rintC(v(t)) for all t ≥ t z with probability 1. Since C(v(t)) = ∩ n i=1 X i (t), it follows that z ∈X i (t) for all i ∈ N and t ≥ t z with probability 1.
From cf. (32)), the definition ofē i (t) in (31), and the projection property given in Eq. (8), we have with probability 1, for i ∈ N and all t ≥ t z , Summing these relations over i ∈ N , and usingw i (t) = n j=1 a ij x i (t), the convexity of the norm and the stochasticity of A(t), we obtain Exchanging the order of summation in n i=1 n j=1 a ij (t) x j (t) − z 2 and using the doubly stochasticity of A(t), we have for all t ≥ t z with probability 1, Applying the super-martingale converge theorem (Theorem 2) (with an index shift), we see that the sequence { n i=1 x i (t + 1) − z 2 } is convergent and ∞ t=tz n j=1 ē i (t) 2 < ∞ with probability 1. Hence, the result in part (b) follows.
We observe that Lemma 4 applies to protocol (30)-(32) in view of the analogy of the description of the protocol in (16)- (18) and the protocol in (30)-(32). We will re-state this lemma for an easier reference, but without the proof since it is almost the same as that of Lemma 4 (the proof in essence depends mainly on the matrices A(k)).  Then, for every player i ∈ N we have with probability 1, where y(t) = 1 n n j=1 x j (t). We are now ready to show the convergence of the bargaining protocol. We show this in the following theorem by combining the basic properties of the protocol established in Lemma 7 and using Lemma 8.
Theorem 3 Let Assumptions 3-6 hold. Then, the bargaining protocol (30)-(32) converges to a random allocation that lies in the core C(v mean ) of the average game with probability 1, i.e., there is a random vectorz ∈ C(v mean ) such that with probability 1, Proof. By Lemma 7, with probability 1, the sequence { n i=1 x i (t) − z 2 } is convergent for every z in the relative interior of C(v mean ) and e i (t) → 0 for each player i ∈ N . By Lemma 8, with probability 1 we have Hence, with probability 1, We next show that {y(t)} has accumulation points in the core C(v mean ) with probability 1. Since Relations (35) and (33) imply Let i ∈ N be arbitrary but fixed and let x ∈X i be arbitrary. Note that we can write By taking the minimum over x ∈X i and using y(t + 1) − PX i (t) [y(t + 1)] = dist(y(t + 1),X i (t)), we obtain for all i ∈ N and t ≥ 0, dist(y(t + 1),X i ) ≤ dist(y(t + 1),X i (t)) + dist PX i (t) [y(t + 1)],X i .
The bounding setsX i are nonempty by Assumption 6 and the fact C(v mean ) ⊂X i for all i, whileX i (t) are assumed nonempty (see the discussion after relation (26)). Furthermore, sinceX i andX i (t) are polyhedral sets, by Lemma 6 it follows that for a scalar L i > 0 and all Therefore, for all i ∈ N and all t ≥ 0, By letting t → ∞ and using relations (36) andv(t) → v mean (Assumption 5), we see that for all i ∈ N with probability 1, lim t→∞ dist(y(t + 1),X i ) = 0.
In view of relation (34), the sequence {y(t)} is bounded with probability 1, so it has accumulation points with probability 1. By relation (37), all accumulation points of {y(t+1)} lie in the setX i for every i ∈ N with probability 1. Therefore, the accumulation points of {y(t)} must lie in the intersection ∩ i∈NXi with probability 1. Since ∩ i∈NXi = C(v mean ), we conclude that all accumulation points of {y(t)} lie in the core C(v mean ) with probability 1. Furthermore, according to relation (34) we have that, for any point z ∈ rintC(v mean ), the accumulation points of the sequences {y(t)} are at the same (random) distance from z with probability 1. Since the accumulation points are in the set C(v mean ), it follows that {y(k)} is convergent with probability 1 and its limit point is in the core C(v mean ) with probability 1. Now, since x i (t) − y(t) → 0 with probability 1 for all i (see (33)), the sequences {x i (t)}, i ∈ N , have the same limit point as the sequence {y(t)}. Thus, the sequences {x i (t)}, i ∈ N , converge to a common (random) point in C(v mean ) with probability 1.
Theorem 3 shows the convergence of the allocations generated by the bargaining protocol in (30)-(32). The convergence relies on the properties of the matrices and the connectivity of the players' neighbor graphs, as reflected in Assumptions 3 and 4. It also critically depends on the fact that the core of the average game C(v mean ) has dimension n − 1 and that all bounding setsX i (t) and, hence the cores C(v(t)), lie in the same hyperplane with probability 1, the hyperplane defined through the constant value of the grand coalition.

Numerical Illustrations
In this section, we report some numerical simulations. We consider coalitional TU games with 3 players, so the number of possible nonempty coalitions is m = 7. We consider two different scenarios as shown respectively in rows I and II in Table 2. The columns of Table 2 enumerate the coalitions. In each scenario, the characteristic functions v S (t) are generated independently with identical uniform distribution over an interval. Specifically, we suppose that the values of single player coalitions {1} and {2} are uncertain within the given interval. All the other coalitions' values are fixed and equal to zero except for the grand coalition, which has value 10 in both scenarios I and II.
The two scenarios differ in that the core C(v max ) of the robust game is nonempty in scenario I and empty in scenario II. For scenario I, we simulate the convergence behavior of the bargaining protocol (16)- (18) for the robust game, while for scenario II, we simulate bargaining protocol (30)-(32) for the average game.
For each scenario, we run 50 different Monte Carlo trajectories each one having 100 iterations. The number of iterations is chosen long enough to show the convergence of the protocols. All plots include the sampled average and sampled variance for the 50 different trajectories that were simulated. Each trajectory in each scenario is generated by starting with the same initial allocations, which are given by  [4,7] [0, 3] 0 0 0 0 10 II [4,9] [0, 5] 0 0 0 0 10 Regarding the players' neighbor-graphs, we assume that the graphs are deterministic but time-varying. The graphs for the times t = 0, 1, 2 are as follows: player 2 and 3 connected at time t = 0 (see Figure 5(a)), then player 3 and 1 connected at time t = 1 ( Figure 5(b)), and finally player 1 and 2 connected at time t = 3 ( Figure 5(c)). These graphs are then repeated consecutively in the same order. In this way, the players' neighbor-graph is connected every 3 time units (Assumption 4 is satisfied with Q = 2).
The matrices that we associate with these three graphs, are respectively given by: These matrices are also repeated in the same order for the rest of the time. Thus, at any time t, the matrix A(t) is doubly stochastic, with positive diagonal, and every positive entry bounded below by 1 2 , so Assumption 3 is satisfied with α = 1 2 . All simulations are carried out with MATLAB on an Intel(R) Core(TM)2 Duo, CPU P8400 at 2.27 GHz and a 3GB of RAM. The run time of each simulation is around 90 seconds.

Simulation Scenario I
In this scenario, the coalitions' values are generated as given in row I of Table 2. In particular, at each time t, the value v {1} (t) is chosen randomly in the interval [4,7] with uniform probability independently of the other times. Similarly, the values v {2} (t) are generated in the interval [0, 3]. The grand coalition value is fixed to 10 at all times, and the other coalition values are 0. With this data, we consider the allocations as generated by players i = 1, 2, 3 according to the bargaining protocol in (16)- (18) for the robust game as reported in Subsection 5.1.1. We then consider the bargaining protocol in (30)-(32) for the average game in Subsection 5.1.2.

Robust game
For this specific example, the characteristic function v max for the robust game is obtained by considering the highest possible coalition values (see the data in row I of Table 2), which results in v max = [7 3 0 0 0 0 10] . The resulting core of the robust game is given by Figure 5: Topology of players' neighbor-graph at three distinct times t = 0, 1 and 2.
We note that this core contains a single point, namely [7 3 0] . To ensure that v(t) = v max infinitely often, as required by Theorem 1 for the convergence of the protocol, we adopt the following randomization mechanism. At each time t = 1, . . . , 100, we flip a coin and if the outcome is "head" (probability 1/2), the coalitions' values v {1} (t) and v {2} (t) are extracted from the intervals [4,7] and [0, 3], respectively, with uniform probability independently of the other times. If the outcome of the coin flip is "tail", then we assume that the robust game realizes and take v(t) = v max .
We next present the results obtained by the Monte Carlo runs for the bargaining protocol in (16)- (18). An illustration of a typical run with the allocations generated in periods t = 0, 1, 2, 3 is shown below: In Figures 6 and 7, we report our simulation results for the average of the sample trajectories obtained by Monte Carlo runs. Figure 6 shows the sampled average and variance of the allocations x i (t), i = 1, 2, 3 per iteration t. In accordance with the convergence result of Theorem 1, the sampled averages of the players' allocations x i (t) converge to the same point, namely x = [7 3 0] which is in the core of the robust game C(v max ). Figure 7 shows that the sample average and sampled variance of the errors e i (t) converge to 0, as expected in view of Lemma 3(b).

Average game
In this numerical example, for scenario I data as given in row I of Table 2, we consider the average TU game and its corresponding bargaining protocol (30)-(32). We at first provide a sample example and report the outcomes for the first three steps of the algorithm, as reported below:    For the average game associated with the data in row I of Table 2, we have v mean = [5.5 1.5 0 0 0 0 10] and the core C(v mean ) given by In Figures 8 and 9, we depict our simulation results generated by bargaining protocol (30)-(32) for the average game. Figure 8 shows that the sampled average of the allocations x i (t), i = 1, 2, 3 converge to a common pointx = [5.6 2.2 2.2] which belongs to the core C(v mean ) of the average game, as guaranteed by Theorem 3. The sampled variance does not converge to zero as the common limit point of the allocations x i (t) can be different for different runs. Figure 9 demonstrates that the sampled average and variance of the errorsē i (t), i = 1, 2, 3, converge to zero, as predicted by Lemma 7(b). Figure 9: Plots of the sampled average (left) and variance (right) of the errorsē i (t), i = 1, 2, 3, for bargaining protocol (30)-(32) and the average game associated with the data in row I of Table 2. The sampled average and variance of the errorsē i (t) goes to 0.

Simulation Scenario II
Here, we report the simulation results obtained by the bargaining protocol (30)-(32) for the average game corresponding to the data in row II of Table 2. In this case the core of the robust game is empty, so we do not consider the robust game. The average game has characteristic function v mean = [6.5 2.5 0 0 0 0 10] and its core is C(v mean ) = {x ∈ R 3 : x 1 ≥ 6.5, x 2 ≥ 2.5, x 3 ≥ 0, x 1 + x 2 ≥ 0, x 1 + x 3 ≥ 0, x 2 + x 3 ≥ 0, x 1 + x 2 + x 3 = 10}. Figures 10 and 11 show the results for the average game obtained in our simulations. In Figure 10, we report the sampled averages of the players' allocations x i (t), i = 1, 2, 3, obtained by bargaining protocol (30)-(32). In accordance with Theorem 3, the players' allocations converge to an allocation that lies in the core of the average game C(v mean ), precisely to the pointx = [6.6 2.6 0.8] ∈ C(v mean ). Here, again, the sampled variance of the allocations does not converge to zero as their common limit point is different for different runs. Figure 11 shows that the sampled average and variance of the errorsē i (t), i = 1, 2, 3, converge to zero.

Conclusions
This article deals with dynamics and robustness within the framework of coalitional TU games. With respect to a sequence of TU games, each with a random characteristic  Table 2. Sampled averages converge to point x = [6.6 2.6 0.8] ∈ C(v mean ), which is the average of the limit points of the 50-sample trajectories.
function, the novelty of the work lies in the design of a decentralized allocation process defined over a communication graph of players. The allocation process captures the main features of bargaining in a realistic scenario. The proposed bargaining scheme is proven to converge, with probability 1, in either a robust game setting or an average game setting, under mild assumptions on the communication topology among the players and the stochastic properties of the random characteristic function. The key properties that distinguish this work from the existing work on dynamic games are: (1) the introduction of a time-varying communication graph, termed players' neighbor-graph, over which the bargaining protocol takes place; and (2) the distributed bargaining protocol for players' allocations updates subject to local information exchange with neighboring players.