Complex Network Formation as Antagonistic Game: Numerical Modeling

Complex Networks: the Interplay between Design and Functions

In recent years, a large volume of research has been dedicated to the structural and functional connectivity patterns in complex brain networks, and concepts of emergent functions in networks that combine network segregation and integration have been proposed. These concepts are based on different mathematical approaches: network science, graph theory, statistical mechanics and dynamical systems theory structure. The structure of logical and neural networks is in fact a graph model (nodes and connections between nodes), which is a mathematical tool used to present some events or processes, including transportation systems of roads between towns, chemical bonds between atoms and automaton for Boolean function computation. In these cases, nodes and the connections between them define the function of the network completely. The first mathematical results to shed light on the structural and functional connectivity of logical networks appeared in computer science more than fifty years ago. In these works, it was suggested that there is a connection between the optimal complexity of the network (number of logical elements) and the network geometry. Roughly speaking, one cannot obtain minimally complex networks (e.g., the Shannon function L(n) where n is the number of arguments in the logical function) if the geometrical network parameters, e.g., the density in 2-dimensional Euclidean space, length of connections, and element degree, do not grow with n.

For quantifying dynamic functional connectivity (DFC), static models areevidentlyinsufficientwhenstudyingbiologicalnetworks. The new experimental models, which include both network elements and the dynamics of their behavior, must be considered and evaluated [1] because a large body of neurophysiological studies demonstrates that new, appropriate DFC metrics are vitally necessary for studying changes in macroscopic neural activity patterns and, consequently, important aspects of cognition and behavior. Determining the behavior dynamics of complex networks and the exact results used in understanding large-scale network activity are the most challenging tasks in computational biology and modeling. The main goal of an experimental study of the brain is to clarify “the intrinsic properties and functional repertoire of the brain” [1]. This is similar to estimating the behavior of automata transition graphs, in which the input signals (the “questions”) are entered and then the “answers” can be observed. Brain network experimental research has focused on similar problems, such as deciphering fMRI1 pictures.

The problem of decoding absolute black boxes is algorithmically unsolved [2]. For traditional automata model, one can avoid insolvability by using a “reset button”, which restores the initial state between each pair of states. It is evidently that for living entities this method unacceptable. However, since ancient times, people have been learning to predict the behavior of living entities without exact knowledge of their inner structure. Domestication is the best example of successful behavioral studies. Careful observation the behavior (the mammals and invertebrates) provides a rich source of behavioral information. The most striking discovery of recent times is that complex behavior and even the ability to communicate is possible with a relatively simple structure of the nervous system, such as in bees or ants [3]. Modeling the simplest automaton games could be one method for decoding automata structures. In other words, the challenge is to clarify how automata behavior could be changed by changing its structures.

Here, we study two different approaches of game theory to network formations: Nash equilibrium game modelling and Neumann equilibrium for antagonistic two-player zero-sum games with mixed strategies. Game theory provided a natural framework for modeling of the trade-off between efficiency and stability for economical systems models (see [4] and references herein). However, such approach became very popular later for the formation of the architecture that connects the relay stations (RS) and their serving base station. Here each RS aims to maximize of utility function that include the benefit from cooperative transmission due of reduced bit error rate, and decrease of the delays. The results (see [5,6] and references in [5]) attest that network formation games is a promising line of investigations for optimal networks design field including wireless sensor networks, cognitive radio and distributed detection.

In this work we discuss the case in which the network “structure” is defined by the topological properties of the partition graphs [7] of two players, GA(N, E) and GB(N, E), with a special labeling of nodes and a prearranged metric space. For Nash equilibrium model of network formation from [8] we analyzed by numeric modelling the optimal result depends from the players’ skills or resources when game is perturbed, i.e. randomizing strategies are using. For case of Neumann antagonistic games with zero sum we hypothesized that there is a tight connection between the suboptimal solution of the associated antagonistic game Ξ(A, B) and the topological properties of the graphs GA(N, E) and GB(N, E). The results that have been derived from numerical modelling are used to verify this hypothesis.

Partition Networks Game for Nash Equilibrium Model of Network Formation

Game theory is concerned with the decision-making process in situations where outcomes depend upon choices made by one or more players. To apply game theory, certain assumptions are necessary. The first assumption is that each player is rational and acting in his or her own self-interest. The players’ choices determine the outcome of the game, but each player has only partial control over the outcome. Other important assumption is the structure of game strategies that can be determined or randomized. For example, when the players are intelligent creatures it can be hypotheses that strategies are determined but for game with nature the strategies are randomized because nature is unpredictable. For game with nature, two alternative models can be using: nondeterministic and probabilistic. For nondeterministic case, a player have no idea what nature will do and for randomized case a player decide observing nature and gathering statistics.

Authors of the first works on network formation games (see [8] and references herein) consider a game with N players, where each player is identified by a graph node, and uses the Nash equilibrium model. In this game, each player tries to form links to other players unilaterally. Node u may choose to build edges from u to v from any subset of nodes. Players (nodes) have two opposite goals: to build and pay for as few edges as possible, i.e. to form a network that minimizes the distance from their own node u to all other nodes. The quality of such a network is the sum of the distances to all other nodes. The players aim to minimize a cost function that combines both the network building costs and the distances to all other players. The set of edges S in the union of all players’ strategies forms a network G(S) on the player nodes. Let dist S(u, v) be the shortest path (minimum number of edges) between u and v; the cost of building an edge is specified by a single parameter, α. The social cost of network G(S) is

SC(G)= ∑dist(u, v)+ α|Ed| (1)

were u and v are nodes (u ≠ v), the sum of the player’s costs dist(u, v) is the shortest path between u and v in G(S) and α is the cost of building an edge. |Ed| is the total number of edges. Network G(S) is the optimal solution if it minimizes the social cost. The optimal solution can be reached for the Nash equilibrium graph. In [8], it was proven that if α ≥ 2, then any star is an optimal solution, and if α ≤ 2, then the complete graph (clique) is the optimal solution. The social cost of a star with N nodes equals α(2N − 1), and for a clique, the social cost equals (1 + α)(N − 1)N/2. (Both estimates are proportional of total number of edges for according graphs). These results attest that the social cost of the Nash equilibrium graph is a special case. Such approach doesn’t allow to estimate of the network design when

• the goals of the players are opposite (in particular for antagonistic games with zero sum);

• the players’ skills or resources are different (it is most common situation because inequality is a basic moving force in both human games and games in communities of simpler life forms, such as virus and microbial communities);

• for cases of randomized player strategies (i.e. the perturbed games for example, playing with nature or competition with an intelligent adversary).

Therefore, basic assumptions in [8] breaks down in most networks’ formation games.

One way around these problems is using of partition graphs model [7,9] where each node is labelled. Below we demonstrate (Example 1) that label value of the nodes (i.e. players) have a drastic effect on optimal cost solution.

Example 1. Two graphs for TPF(16, 4) with 5 nodes are depicted on Fig. 1: a star and a perfect graph. Fig. 1a shows the partition graph which contains the internal node, (7, 5, 3, 1) ≡ α, and four leaves, (6, 6, 4, 0), (6, 4, 4, 2), (8, 4, 2, 2), (8, 6, 2, 0). Any star have minimized the social cost G(S) when cost of edge equals 3 [8]. Suppose that for some reasons the label of the internal node is changed to (6, 6, 2, 2) ≡ β. Note that ρ(α, β) = 1 and total resource of these nodes doesn’t change, i.e. it makes sense to consider this change insignificant. However, the star in Fig. 1a turns into four isolated nodes (for formation game it can be treated as if the players preferred not to cooperate)2. If partitions at all leaves of the star could be change in a different, but also insignificant way (see Fig. 1b), the star graph would be transformed into a complete graph, i.e. another optimal social cost decision although cost of edge doesn’t change. This example demonstrates that labels of graph nodes define the topological structure of a network graph in first place.

To demonstrate the influence of randomized strategies of a player in a network formation game, it is necessary to define the distance between network partition nodes in a more general way than in [7]. Firstly, let’s remind some definitions from [7].

Figure 1: The optimal social solution (the star) can be transformed into the opposite optimal social solution (the clique) by changing strategies (nodes labels) of the players, i.e. different behaviors of the players. The star graph (a) has a diameter of 2, density of 0.4, characteristic path length of 1.6, and graph energy of 4.0. The complete graph (b) has a diameter of 1, density of 1.0, characteristic path length of 1.0 and graph energy of 8.0.

Table 1: Topological metrics for the 5-clique and the 5-star in the case of randomized strategies of a player. Total number of random experiments is 20. Denote the share of the ”ideal“ results (i.e. without randomization) as True; AD is an average diameter of networks and ADen is an average density of networks for all random experiments. Red color for the 5-star is the share of disconnected networks.

An (n, m)-partition of n into no more than m parts is defined as a sequence of nonnegative integers a1 ≥ a2 ≥ ... ≥ ak ≥ 0, such that n = a1 + a2 + ... + am. The set of all feasible (n, m)-partitions is denoted by P(n, m).

Let for any partition α = (a1, . . . , am), a random partition α∗(n, m, s2) = (a (s2), . . . , a (s2)), be given where a (s2) is normally distributed variable with mean ai and variance s². The distance between partitions a∗(n, m, s²) and b∗(n, m, s²) will be defined as P(n, m), i.e. as the maximum of modules of coordinate differences a∗(n, m, s2) and b∗(n, m, s2). Let value η be the threshold distance. The nodes are labelling as random partitions be connected iff distance between these nodes is less or equal η.

We will illustrate the influence of randomized strategies of a player on topological metric for the star and the perfect graphs shown on Fig. 1 using the collection of programs [11].

There are two intriguing experimental observations related to behavior of partition graphs when using randomizing strategies.

1. The reliability of the 5-clique decreases monotonically with 1 m i perturbations, whereas the structure of 5-star is left without changing as long as σ² is small enough (0.05, 0.1). However, when noise is increasing, the isolated nodes in network are appearing, i.e. the structure of such network is broken down.

2. Provisional results of numerical modelling showed that for trinomial partition family TPF(m) [9] the reliability of the networks G(TPF(m)) under perturbations is distinctly increased as m increases. In particular, for TPF(5), where the number of network nodes equals to 18, the share of the ”ideal“ results, when σ² = 0.25, are about 70%. It is much higher than modelling results for 5-clique (see Table 1). It seems plausible that the reason is in the connectivity strength (network density) and small K-complexity of the networks for G(TPF(m)).

Zero-Sum Games with Mixed Strategies

The model of partitioned network games is based on the specific models of two-player zero-sum antagonistic games with mixed strategies. Let Ξ be a two-player game. Each player has a set of N strategies in addition to SA and SB, and M = N × N is the game playoff matrix. Let players A and B be represented by partitions of graphs GA(N, E) and GB(N, E), where each node of GA and GB is labeled by one of the strategies from sets SA and SB, respectively. A zero-sum game is one in which no wealth is created or destroyed. Therefore, in a two-player zero-sum game, whatever one player wins, the other loses, and the players share no common interests. The concept of a mixed strategy and the minimax solution for two- player games were developed originally by Emile Borel with an example of a game in which the players strategically distribute a fixed amount of resources n over a finite number of m battlefields. Minimax is a strategy that minimizes the maximum possible loss, which can result from a choice that a player makes. If the game has no saddle point, the players have to choose their strategies with a degree of randomness. In this case, the game is called a “game with mixed strategies”. Next, we will discuss the antagonistic zero-sum games on the Borel model using the names “Blotto game” and “Lotto game” [12-14]. The player who assigns more resources to a battlefield will win. The objective of the players is to maximize the number of battlefields won. The application of the games approach is possible if players have a tractable (with polynomial computation complexity) optimal (or “almost optimal”) algorithm to obtain the game solution, i.e., can obtain the set of profitable game strategies. The more possible strategies players have, the more difficult it is to find the optimal game solution. This scenario is clearest in Blotto (Lotto) games, where the strategies are m nonnegative integers ai, and ∑ ai = n, where n is the total number of resources (number of warriors) and m is the number of battlefields. In [13], it was shown that a Blotto game has a mixed-strategy equilibrium in which the marginal distributions are uniform on [0, 2n/m] along all battlefields. For Blotto game (120, 6), the support set should contain more than 108 strategies with equal probabilities. From the theorem of Caratheodory, games such as Blotto (Lotto) allow mixed equilibrium strategies involving no more than (n + 1)m + 1 pure strategies [15]. However, the Caratheodory theorem is an existence theorem. In the past, it was common to believe that solving a minimax problem for antagonistic matrix games with constant sum is intractable because the number of pure strategies grows exponentially with the game parameters. Therefore, it is not surprising that traditional optimization techniques fail to find optimal solutions for Colonel Blotto games. Recently, in [16], in, LMO-based decomposition techniques were proposed. These techniques allow a large but well-organized matrix game to be reduced to a small saddle point optimization problem. In Blotto (Lotto) games, the matrices for each player are well organized. Specifically, in the game “attacker vs defender”,which is a general version of the Blotto game, was considered [16]. The method in [16] was applied to the “attacker vs defender” game and allows the game to be solved in polynomial time. In fact, the method is capable of obtaining, in a reasonable amount of time, near-optimal solutions to rather large (e.g., m = 10 and n = 100) games with accurate payoff values, such as 0.02. in [16] addition, this method provides a support set with few pure strategies (significantly below the Caratheodory bound). The results in allowed for essential progress in general optimization theory and minimax games specifically. However, we have concentrated on finding the simplest procedure by choosing effective strategies that are easily accessible for living entities. There are some different artificial methods used to organize the process of choosing strategies for the support set (in addition to minimax solution algorithms). The first is based on modeling the contest between different classes of partitions [17]. The second method, which is discussed below, analyzes topology graphs with node labeling by applying different strategies.

Efficiency of the Selection Mechanisms: Numerical Modeling

As shown computing experiments the key features to define of partitions “strength” as game strategies (i.e. support set members) are diversity and permutation balance.

The value PB is used to estimate the maximal deviation of the composition’s center mass from the middle. The algorithmic complexity of PB computation does not exceed Θ(m2 log n).

Importantly, the partition’s features used in the selection mechanism should be easily computed (the time complexity should be no more than quadratic in the resource value). Attempts to estimate the efficiency of the selection mechanisms in Blotto (Lotto) games were made in and [17, 18]. In [17] the strategy efficiency is defined as the result of some kind of evolutionary game. The numerical simulation demonstrated that the class with strategies containing a large diversity and a large permutation balance is certain to be an “absolute evolution winner”, i.e., the strategies from this class are winners in all evolutionary experiments. Now, we will study the topological structure graphs that are used in the Blotto game. Let P∗(n, m) ∈ P(n, m) be the set of suboptimal strategies in Blotto (n, m)-partition games [18], and Prand(n, m) ∈ P(n, m) be a set of random strategies with |Prand(n, m)| = |P∗(n, m)|. It is found that the topological properties of the graphs with nodes labeled with P∗(n, m) and Prand(n, m) are essentially different. Almost all graphs that are designed from random strategies have small densities and energy values. As a result, a graph with small energy (density) essentially does not have a chance to win against a graph with more energy (density). Therefore, game equilibrium assumes that the graphs of the playing strategies of both players are strongly connected. This is circumstantial (but encouraging) evidence that within the network design and its behavior (functionalities) are deep and insufficiently studied relationships. Although this fact may seem selfevident from a commonsense point of view, to the best of our knowledge, this study is the first to provide a set of detailed experimental results. am) is

Experimental Observations

For numerical modeling, the program tool [11] was used. For the sake of simplicity, Appendix displays the data from only one numerical experiment. Here, two players, A and B, are playing a Blotto game (100, 10). Each player has 50 strategies, i.e. partitions from partition set P(100, 10). Strategies for A were taken from set ∗ (100, 10), which was obtained by the selection mechanisms described above, or from set P∗ (100, 10) as suboptimal decisions in attacker-defender games [18]. Fifty strategies for B were taken (randomly and evenly) from the set of all possible partitions, P(100, 10). The graphs GA(N, EA) and GB(N, EB) are graphs whose nodes are labeled of the strategies from P∗(100, 10) and P(100, 10), respectively, and given a distance value of ρ. The results (see Appendix) provide a convincing demonstration of the advantage of player A in the game. To confirm the empirical observation results, which show that player A is “stronger” than player B, we calculate the game price and support sets for players A and B (see Table A1 in Appendix) with the help of the computer tool CVX [19].

Conclusion

For all modern complex technological networks, indeterminism of real world is the primary source of trouble. The cost of solutions to reach necessary robustness level can be extremely high. However during evolution process Nature found not only robust solutions but the methods in harnessing the random events for facilitate of survival living entities from as mammals till the simplest creatures. So main challenge is to clarify how the simplest natural or artificial creatures could make decisions in survival problems. In studying model, each vertex has an individual label that determines its connections with other vertices, i.e., vertex “abilities”. During dynamic partition games, the vertex resource can vary. As a result, the game price and equilibrium level are also changed. In this way,partition games have the ability to react not only to the behavior of other players but also to outside forces (e.g., temperature, pressure and energy). Indeed, the appearance of H2O molecules is not the result of optimal strategies for chemical element behavior (hydrogen and oxygen atoms) but is a consequence of quantum mechanical laws and the availability of outside physical conditions. Aspects of mutual perception and joint problem solving might be more important than individual optimization [4]. Partition games may be the model best suited to focus on the “physical” aspects of network design [20] and the interplay between the functional and structural properties of living or artificial. It worth noting that In our model we studying the version of the classical zero-sum matrix game with unknown payoff matrix , where the players only observe each other’s actions and a noisy payoff. Such generalizations of the usual matrix game, where the payoff matrix is known to the players became very popular in recent years in particular for deep learning algorithms. See for example [21,22].

In the last years, experimental researches appeared in the computational neuroscience field with intriguing results about the topology and functionality of human brain networks. Roughly speaking, it was experimentally found that the structure of a network (more specifically, the connections between specially selected areas of a brain) clearly depends on the reward or punishment of players during gambling. What is more, were found key regions that convey loss and win information across the network [23].

Author Contributions

Conceptualization, A.G. and P.B.; methodology, A.G.; software, P.B.; validation, A.G., P.B.; formal analysis, A.G.; investigation, A.G.; resources, P.B.; data curation, P.B.; writing—original draft preparation, A.G, P.B.; writing— review and editing, A.G., P.B.; visualization, P.B.; supervision, A.G.

Conflicts of Interest

The authors declare no conflict of interest.

References

1. Hutchison, R. M., Womelsdorf, T., Allen, E. A., Bandettini,P. A., Calhoun, V. D., Corbetta, M., ... & Chang, C. (2013). Dynamic functional connectivity: promise, issues, and interpretations. Neuroimage, 80, 360-378.
2. Trakhtenbrot, B. A., & Barzdin, Y. M. (1973). Finite automata: Behavior and synthesis. Elsevier.
3. Reznikova, Z. (2017). Studying animal languages without translation: An insight from ants. Berlin: Springer International Publishing.
4. Schelling, T.C. The strategy of conflict; Harvard University Press: Cambridge, MA, 1960.
5. Cavaliere, M., Jordan, F., Csikasz-Nagy, A., & Moscon, R. (2008). Graph transformations and game theory: A generative mechanism for network formation.
6. Saad, W., Han, Z., Basar, T., Debbah, M., & Hjorungnes, A. (2011). Network formation games among relay stations in next generation wireless networks. IEEE Transactions on Communications, 59(9), 2528-2542.
7. Goryashko, A., Samokhine, L., & Bocharov, P. (2018,December). New Deterministic Model of Evolving Trinomial Networks. In International Conference on Complex Networks and their Applications (pp. 553-564). Cham: Springer International Publishing.
8. Tardos, E., & Wexler, T. (2007). Network formation games and the potential function method. Algorithmic Game Theory, 487-516.
9. Goryashko, A., Samokhine, L., & Bocharov, P. (2019). About complexity of complex networks. Applied Network Science, 4, 1-21.
10. Pagan, N., & Dörfler, F. (2019). Game theoretical inference of human behavior in social networks. Nature communications, 10(1), 5507.
11. Samokhine, L. Trinomial Family Research Toolbox, 2017.
12. Borel, E. (1921). La théorie du jeu et les équations intégralesa noyau symétrique. Comptes rendus de l’Académie des Sciences, 173(1304-1308), 58.
13. Golman, R., & Page, S. E. (2009). General Blotto: games of allocative strategic mismatch. Public Choice, 138, 279-299.
14. Hart, S. (2008). Discrete colonel blotto and general lotto games. International Journal of Game Theory, 36(3-4), 441- 460.
15. Eckhoff, J. (1993). Helly, Radon, and Carathéodory type theorems. In Handbook of convex geometry (pp. 389-448). North-Holland.
16. Cox, B., Juditsky, A., & Nemirovski, A. (2017). Decomposition techniques for bilinear saddle point problems and variationainequalities with affine monotone operators. Journal ofOptimization Theory and Applications, 172, 402-435.
17. Bocharov, P., & Goryashko, A. (2017). New approach to solving partition games. Applied Mathematical Sciences, 11(15), 739-750.
18. Bocharov, P. S., & Goryashko, A. P. (2017). Suboptimal solutions of antagonistic partition games. Upravlenie Bol'shimi Sistemami, 70, 6-24.
19. Diamond, S., & Boyd, S. (2016). CVXPY: A Python- embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83), 1-5.
20. Bassett, D. S., Greenfield, D. L., Meyer-Lindenberg, A., Weinberger, D. R., Moore, S. W., & Bullmore, E. T. (2010). Efficient physical embedding of topologically complex information processing networks in brains and computer circuits. PLoS computational biology, 6(4), e1000748.
21. O’Donoghue, B.; Lattimore, T.; Osband, I. Stochastic matrix games with bandit feedback. arXiv preprint arXiv:2006.05145 2020.
22. Blum, A., & Monsour, Y. (2007). Learning, regret minimization, and equilibria.
23. Van De Steen, F.; Krebs, R.; Marinazzo, D. 2017. Effective connectivity modulations of win-and loss feedback: A dynamic causal modeling study of the human connectome gambling task. Frontiers in Neuroscience.
24. Gutman, I. Hyperenergetic and hypoenergetic graphs. Selected Topics on Applications of Graph Spectra 2011.

Foot notes

¹fMRI — functional magnetic resonance imaging measures brain activity by detecting changes associated with blood flow.

²In theory of communication systems, the problems of myopic fashion of network nodes, i.e. without anticipating others’ potential reaction (it is malicious or selfish nodes), are being studying [10].

³A pure strategy is in support of a mixed strategy if that pure strategy is played with positive probability according to the mixed strategy.

Appendix A. Experimental Results

The results of the game between graph A (where nodes are labeled with the suboptimal strategies) and graph B (where nodes are labeled with random strategies) and the graph metric measure distance ρ = 3 are depicted here. The number of iterations in the experiment is 10. In addition to the topological parameters in Fig. A1, we obtain the diameter, efficiency, and average degree of the graph.

Through our research, we establish that a sample size of 10 (the number of iterations in the experiment) is sufficient to obtain statistically stable results for the A vs B graph game.