{'fraction_non_alphanumeric': 0.031410801378137725, 'fraction_numerical': 0.008680477873730368, 'mean_word_length': 4.3803562831006255, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Network Games: Condensation of the Graph as a Hierarchical interpretation of the Game

Abstract In this paper we investigate the problem of optimal games played over networks and focus our attention on the importance of the topology of communication between the agents. We consider a set of agents which are connected via a directed communication graph: each agent in the network has to optimize a local cost function which depends on the agent’s decision and on the decision taken by the set of its neighbors, giving rise to a Network Game. We show that, by condensing the strongly connected components of the control graph into super-nodes, it is possible to give a hierarchical interpretation to the Network Game. Then we apply the proposed architecture to the case of a large scale network which takes inspiration by traffic networks application.


INTRODUCTION
Control and optimization over large population networks have become a popular topic within the control community. The main reason is that modern applications require multiple systems to communicate and interact with each other to fulfill the desired task. For instance power networks, sensor networks and social networks are solid examples in which is fundamental to control different parts of the network to achieve a global desired behavior.
In the recent years, the control community has largely focused on cooperative approaches to networks. In this framework the agents in the network are willing to collaborate and find an agreement between each other in such a way that they coordinate their motion. This approach is represented by the huge literature of consensus/synchronization problems (Isidori et al. (2014), Arcak (2007)) and its application to robot-swarm coordination (Sepulchre et al. (2008), Olfati-Saber (2006)), power networks (Dhople et al. (2014), Xiang and Hill (2014)) and social networks (Mirtabatabaei and Bullo (2012), Blondel et al. (2010)). However, not in all the frameworks and not in all the situations, it is possible to consider a cooperative approach. In several scenarios, the nodes are selfish and in competition with the others to pursue their goal. This leads to a non-cooperative interaction between the agents and thus to games played over networks. Notable examples of this scenario can be found in traffic networks and more in general in network congestion control (Pisarski and Canudas de Wit (2015), Barrera and Garcia (2015)) The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement N • 694209).
The authors would like to thank Rémi Piotaix for the help and support. and smart grids (Ma et al. (2014), Mohsenian-Rad et al. (2010)).
When the number of nodes in the network is large, it becomes analytically impossible to use conventional game theoretic tools to find a solution to the problem. This motivated researchers to define a new type of games, named aggregative, where the response of an agent depends, rather than on each other players decision, on the aggregation of all the other agents action (see Jensen (2006), Jensen (2010)). The problem of games over networks can be seen as an extension of aggregative game, where the aggregation map depends indeed on the topology of a communication graph. In other words the payoff of each players depends only on the set of neighbors (see Jackson and Zenous (2014) for an overview on the topic). In Parise et al. (2015), the authors considered a refined typology of networks games in which the aggregate information is depending on a directed communication graph and showed that under a certain number of conditions the players reach a Nash Equilibrium. In this paper we consider a similar game setting, where a certain number of nodes representing physical systems are influencing each other through a graph. First, we study the influence of this graph topology on the structure of the game and show that the condensation of the graph leads to a hierarchical interpretation of the game and thus to a quasi-sequential architecture of optimization. Then, we introduce the concept of physical graph and control graph in flow networks, and show that the condensation of the control graph helps in determining the equilibrium the agents will reach. The paper is organized as follows. In Section 2, we present the theoretical problem we aim to solve. In Section 3, we analyze the graph topology and provide a level-of-priority interpretation of the game. Then, in Section 4 we specify the problem to a generic large scale flow networks and introduce the notion of control graph. In Section 5 we present some interesting simulation results.

Notation and basic concept on Graph Theory
Denoting by V = {v 1 , v 2 , . . . , v N } the set of N nodes of the network, a topology is described by a directed communication graph given by the following objects: • E ⊂ V × V is a set of edges that models the interconnection between nodes, according to the following convention: (v k , v j ) belongs to E if there is a flow of information from node j to node k. It is assumed that there are no self-loops, i.e. that (v k , v k ) / ∈ E. • for each (v k , v j ) ∈ E the flow of information from node j to node k in the i-th topology is weighted by the (k, j)-th entry a kj ≥ 0 of the so-called adjacency matrix A ∈ R N ×N .
The set of neighbors of node v k is the set The property of connectedness just introduced can be formulated also for portion of the graph, namely subgraphs. Definition 1. A strongly connected component (SCC) of a di-graph G = {V, E, A} is a maximal subgraph G = {Ṽ,Ẽ,Ã} subject to being strongly connected.

PROBLEM FORMULATION
In this paper we investigate the problem of games over networks. Our main goal is to give an immediate understanding of the hierarchical dependency between different parts of the network.
A N -player game is defined as Γ = (J i , U i ) with U i ⊆ R n the finite dimensional convex strategy set of player i, U = i U i the joint strategy set and J i : S → R the upper semi-continuous utility function of player i. Given a strategy profile u −i ∈ U −i for all agents except agent i, the best-response correspondence for agent i is In the aggregative games scenario, the utility function of each agent can be written as The aggregate function is in general defined as so as the sum of all other players decision. In our setting, we are interested in considering a different class of aggregative games in which the interaction term depends only on the set of neighbors: in particular, given a graph G = {V, E, A}, we define σ i : U Ni → R, with N i the set of neighbors of agent i, as where a ij are the elements of the adjacency matrix A ∈ R N ×N describing the communication between the players. In accordance with the definition of σ i in (1), we consider a set of local utility functions defined as with Q i , R i ∈ R n×n matrices of weights. The cost function is indeed composed by two terms: the first is a quadratic term in u i while the second term penalizes the interaction with the neighbors through σ i . The local optimization problem is formulated as One of the most important concepts in games is the Nash equilibrium. A Nash equilibrium is a strategy set in which no agent has any advantage in deviating from its own strategy given the other players'. In this framework, the aggregative Nash equilibrium can be formulated as follows.

CONDENSATION OF THE GRAPH: A SEQUENTIAL ARCHITECTURE
In general, solving an optimization problem over a complex graph is a really difficult task. In case of loops, for instance, a trade between the various agents has to take place. Furthermore, the agents might take decisions in different moments (i.e not being synchronous). One could wonder if there are nodes with high priority from which to start the computation and then propagate the result to the others.
In this section we introduce a methodology to interpret the network and obtain a hierarchical representation of the graph. Through this hierarchy, it will be possible to understand clearly the inter-dependence of the nodes and to set a sequential procedure of optimization. First, we introduce the concept of condensation of a graph. Definition 3. The condensation G of a graph G is a reduced graph in which: • strongly connected components (SCC) of G are contracted to a single node is and edge in G Furthermore, we recall a fundamental result about directed graphs. Theorem 2. (Th. 3.6, Harary et al. (1965)). For any directed graph G, the condensation G of G is a directed acyclic graph (DAG).
As a matter of fact G can be seen as hierarchical representation of the optimization problem over the original graph G. In graph theory, a level assignment is a procedure in which for every node v i , we define an integer n i : a level ordering is a level assignment in which for every edge connecting v i to v j , either we have n i < n j or n i > n j (ascending and descending level assignment respectively).
In the following, we consider only ascending level assignment without loss of generality.
The definition of the DAG G allows us to describe the optimization over the original network G as a sequential procedure by sorting the nodes into levels. Hence, we define a quasi-level assignment (in which nodes belonging to a strongly connected component have the same level) based on the longest path to reach a node: given node v i , its level n i is equal to the length of the the longest path from any root of G plus 1. Then, the level assignment n i ∈ [1, + 1] where is the length of the longest path in G . Based on this level assignment, we define a sequential procedure for solving the optimization process on the graph, in which nodes with the smallest level compute first and then propagate their decision to the higher levels in a cascade-fashion. This recursive procedure is illustrated in Table 1.
Algorithm for the DAG Initialize set k = 1 Iterate all nodes v j ∈ level k, compute their optimum value based on the result of the previous level • if v j ∈ lev k belongs to a super node, iterate u j = arg min uj ∈Uj J j u j , σ j Then u k (k) = col{u j } for all j : v j ∈ lev k If k = + 1 stop Table 1. Sequential procedere of optimization: a hierarchical stracture.
In order to solve the problem of optimization inside the super-nodes we make use of game-theory tools and show that, given the information from the father-nodes (namely the nodes belonging to a previous level, if present), each super-node eventually reaches a Nash-equilibrium.
Suppose that the condensation procedure results in c super nodes. Then, for each node v i belonging to SN j (j = 1, . . . , c), it is possible to split the aggregate information σ i in two parts: σ f i that comes from the upper levels and thus is a constant, and σ sn i that is the aggregate information from the nodes that belongs to the super-node. In other words, we write 5) Suppose that the super-node has a level assignment n j and that the nodes belonging to SN j are v h , . . . , v k . Given a set of of initial strategies {u i } k i=h for the nodes belonging to SN j and the aggregate information from the fathernodes (i.e. the nodes with a level assignment n f < n j ), it is possible to define the super-node best response as which collects the strategies computed by each node belonging to SN j . To describe the aggregate information available at the nodes in SN j after each round of optimization, we introduce the aggregation mapping U j : Proposition 1. The aggregation mapping (7) admits at least one fixed point. For each fixed pointσ, the set of strategies {u i (σ f i ,σ sn i )} k i=h is a Nash equilibrium for the game in SN j .
Proof: The mapping U j (σ j ) is continuous and compact valued, so it possesses at least one fixed point. The fact that this point is a Nash equilibrium is a direct consequence of the definition of a Nash equilibrium in aggregative games in Definition 2 (see Smart (1974)).
Proposition 1 is valid for all c super-nodes SN j in the network. To guarantee convergence to a Nash equilibrium one might consider an iterative myopic best response policy, in which each agent plays its best response to the neighbors aggregate information at each round. More in general, every strategy that is a contraction and a non-expansive mapping guarantees that the agents reach a Nash equilibrium (a detailed analysis of the conditions and the techniques to ensure that the Nash equilibrium or a near-Nash equilibrium is reached can be found in Jensen (2006), Jensen (2010), Voorneveld and Norde (1997), Kukushkin (2004)).
As far as the full game is concerned, we replicate the result in Proposition 1. We reorder the nodes and super-nodes belonging to the same level so that they are consecutive and define u i = col{u j } for j : v j ∈ lev i Accordingly, the adjacency matrix A reads as Then, we can write the aggregate information by levels as and define the best response mapping u(σ) = col u 1 , u 2 (σ 2 ), . . . , u (σ ) As a consequence, the aggregation mapping for the entire game U : R N n → R N n as Corollary 1. The aggregation mapping (8) admits at lest one fixed point. For each fixed pointσ, the set of strategies {u i (σ i )} i=1 is a Nash equilibrium for the entire game.
The proof is an straightforward consequence of Proposition 1. After each iteration of the algorithm in Table 1, we can express the update of the aggregate information as which, through the junction matrix A junc , clearly shows the cascade propagation of decision between nodes with higher priority to nodes with lower priority in the structure of the equilibrium.

APPLICATION TO LARGE SCALE FLOW NETWORKS
In this section we apply the analysis presented in Section 3 to the case of large scale flow networks. Flow networks are of particular interest because they represent several field of application, such as pipe networks, power networks and traffic networks. A fundamental aspect about flow networks is to distinguish between two possible interpretation of the network itself: • on one hand, the physical representation stands for the real connection between the nodes of the network in terms of flow • on the other, the control representation stands for the dependence of the nodes on the others from the control point of view The two representation do not necessarily coincide in the sense that the control directionality might not be the same as the physical directionality of the network. With P-Graph G P = {V, E, A} we represent the physical interconnection between the N nodes in the network and thus the physical flow of information. Traffic networks can be seen as flow networks where the goal is to control the density of cars and avoid congestion. In this framework, when the density of vehicles is low, a certain section is considered in free flow, while when the density is high, the same section is in congestion. By partitioning the road into sections, the state of each section has two admissible configuration, namely: • F (green): representing a free evolution of the section • C (red): representing a congested evolution of the section Based on the P-Graph G P , we also define a some limitation on the nodes state evolution. First, the nodes are allowed to change at discrete time instants T 1 , T 2 , . . ., with periodicity T . Furthermore, given a certain configuration of free and congested nodes, the nodes are allowed to change configuration according to the following Assumption. Assumption 1. Given a P-Graph G P , we assume that: i) nodes which are free and have no outgoing edge towards congested node cannot change ii) nodes which are congested and have no incoming edge from free nodes are not allowed to change To each node v i which is allowed to change, we associate a probability which is associated to the result of the optimization problem with P i (u i ) to be specified later.
As mentioned before, the control graph is an abstraction of the control dirctions and its derived from the physical graph, based on the state of each node in the network. As pointed out in Pisarski and Canudas de Wit (2015), traffic networks control is highly influenced by the congested/free configuration of the road. Based on the configuration of each section, namely congested/free, the congestion waves can propagate upstream or downstream. When a certain section is congested, in order to control the downstream propagation of the traffic wave, we have to act in the upstream direction: on the other hand, when a section is in free-flow, the control is applied following the downstream flow of the physical graph. The rules to determine the C-Graph G C in case of traffic networks (note that they are equivalent to the case of pipe networks) are summarized in Tab 2. In our framework, nodes can be seen as sections of roads which can be controlled. As a consequence, the local optimization problem (3) is formulated according to the control graph, as

IMPLEMENTATION OF THE PROPOSED ARCHITECTURE AND SIMULATION RESULTS
Following the probelm setting introduced in Section 4, we now display the fundamental steps to implement the approach presented in Section 3. The first step to be performed is the condensation of the graph described in Section 3. For large scale networks, one may think that the computation of the condensation G C can be critical: however, it is important to stress that such a task can be computed in linear time. Several algorithms have been proposed in literature, for instance the Tarjan's strongly connected components algorithm, whose complexity is indeed proportional to the number of nodes and  Figure 1. Example of the evolution of the graph with 100 nodes: from the control graph we obtain the direct acyclic graph determining the structure of the game and the associated Nash equilibrium. edges, i.e. O(|V|, |E|) 1 (see Tarjan (1972)). On the other hand, the computation payload substantially consists in the sequential optimization/game described in Table 1. In our framework, the optimization problem is decomposed into a sequential father-to-son best-response architecture: in other words, the optimization is a sequence of + 1 optimization problems in which, the agents belonging to a certain level i compute in parallel their best response to level i − 1 and then pass their result to level i + 1.
We consider a network composed by 100 nodes. The physical network is randomly generated and the initial congested/free configuration is assigned arbitrarily to each nodes. The cost function at each node is defined according to (2) as whereū i ∈ R is a local target value and ij are elements of the Laplacian matrix associated to the control graph G C . In other words, (10) is composed by a term which penalizes the displacement with respect to the local target valuē u i and by another term which penalizes the displacement with respect to the aggregate information σ i . The N local target values are chosen such thatū i ∈ [0, 1] according to a pseudo-normal distribution with mean µ = 0.5 and standard deviation ε = 0.2. Then, the probability to switch between the two configurations P i (u i ) in (9) is defined as P i = |u i −ū i |, namely the distance between the local target valueū i and the result of the optimization u i . This implies that the agents who are capable of getting closer to their target are more likely to become free. In Figure 1, 1 Here |A| stands for the cardinality of the set A.
three possible configurations of the network are considered and the relative condensation is shown. Starting from the control graph configuration 1(a), we derive the corresponding condensed graph: then, at T = 5 sec, the nodes evolves according to the result of the optimization. We obtain the control graph in 1(b) and its associated DAG, and in a similar fashion 1(c). Videos of various examples of the evolution of the nodes and of the optimization procedure is available at the following link: http://scalefreeback.eu/wp-content/uploads/2017/04/videos.zip.
We also compare the case in which agents are sorted by levels and the case in which the agents computes in parallel. With parallel we mean the case in which the agents are thought to be synchronous and thus compute their optimum all at the same time, without being reorganized: nevertheless, for computational constraints the computation is not fully decentralized, in the sense that there is not a separate computational facility for each node. We stress however that, for a large scale network, it is unfeasible to think that all the agents are synchronous.
In order to compare the two results, in the implementation of our architecture, we take into account the time necessary to perform the condensation of the graph and the level assignment. Despite the necessary delay to perform this computation, the architecture takes advantage of this reordering to compute in a hierarchical sequence the optimal solution to the local problems. Simulation results are shown in Figure 2(a) and 2(b), for a network of 100 and 10000 nodes respectively. The two procedure converge indeed to the same equilibrium, but with rather different computation times. For our architecture, it is possible to see the level-by-level decrements of the cost functions while in the case the of the parallel computation the decrements are relative to a full round of optimization over all the nodes.

CONCLUSION
In this paper we considered a class of network games and studied the influence of the networks topology in the equilibrium the nodes reach. Based on the topology, we defined a hierarchical architecture which solves the optimization problem in a cascade fashion. The approach has been tested on a simplified scenario mimicking flow networks. The first natural extension of this paper is to apply the proposed architecture to a real case scenario, in particular for controlling complex traffic networks. The idea of clusterizing certain parts of the networks has promising perspective in this direction. Furthermore, the analysis of the topology in network games allows also to consider different aspects to the problem: for instance one could think to treat the super-nodes problem with a different approach than simple nodes, or to consider the condensation of the graph as a controllability property of the game .