Microeconomics-based resource allocation in overlay networks by using non-strategic behavior modeling

Behavior modeling has recently been investigated for designing self-organizing mechanisms in the context of communication networks in order to exploit the natural selfishness of the users with the goal of maximizing the overall utility. In strategic behavior modeling, the users of the network are assumed to be game players who seek to maximize their utility with taking into account the decisions that the other players might make. The essential difference between the aforementioned researches and this work is that it incorporates the non-strategic decisions in order to design the mechanism for the overlay network. In this solution concept, the decisions that a peer might make does not affect the actions of the other peers at all. The theory of consumer-firm developed in microeconomics is a model of the non-strategic behavior that we have adopted in our research. Based on it, we have presented distributed algorithms for peers’ “joining” and “leaving” operations. We have modeled the overlay network as a competitive economy in which the content provided by an origin server can be viewed as commodity and the origin server and the peers who multicast the content to their downside are considered as the firms. On the other hand, due to the dual role of the peers in the overlay network, they can be considered as the consumers as well. On joining to the overlay economy, each peer is provided with an income and tries to get hold of the service regardless to the behavior of the other peers. We have designed the scalable algorithms in such a way that the existence of equilibrium price (known as Walrasian equilibrium price) is guaranteed.     

Bounded invariant verification for time-delayed nonlinear networked dynamical systems

We present a technique for bounded invariant verification of nonlinear networked dynamical systems with delayed interconnections. The underlying problem in precise bounded-time verification lies with computing bounds on the sensitivity of trajectories (or solutions) to changes in initial states and inputs of the system. For large networks, computing this sensitivity with precision guarantees is challenging. We introduce the notion of input-to-state (IS) discrepancy of each module or subsystem in a larger nonlinear networked dynamical system. The IS discrepancy bounds the distance between two solutions or trajectories of a module in terms of their initial states and their inputs. Given the IS discrepancy functions of the modules, we show that it is possible to effectively construct a reduced (low dimensional) time-delayed dynamical system, such that the trajectory of this reduced model precisely bounds the distance between the trajectories of the complete network with changed initial states. Using the above results we develop a sound and relatively complete algorithm for bounded invariant verification of networked dynamical systems consisting of nonlinear modules interacting through possibly delayed signals. Finally, we introduce a local version of IS discrepancy and show that it is possible to compute them using only the Lipschitz constant and the Jacobian of the dynamic function of the modules.     

An extended TODIM method for multiple attribute group decision‐making based on 2‐dimension uncertain linguistic Variable

The significant characteristic of the TODIM (an acronym in Portuguese of Interactive and Multiple Attribute Decision Making) method is that it can consider the bounded rationality of the decision makers. However, in the classical TODIM method, the rating of the attributes only can be used in the form of crisp numbers. Because 2‐dimension uncertain linguistic variables can easily express the fuzzy information, in this article, we extend the TODIM method to 2‐dimension uncertain linguistic information. First of all, the definition, characteristics, expectation, comparative method and distance of 2‐dimension uncertain linguistic information are introduced, and the steps of the classical TODIM method for Multiple attribute decision making (MADM) problems are presented. Second, on the basis of the classical TODIM method, the extended TODIM method is proposed to deal with MADM problems in which the attribute values are in the form of 2‐dimension uncertain linguistic variables, and detailed decision steps are given. Its significant characteristic is that it can fully consider the bounded rationality of the decision makers, which is a real action in real decision making. Finally, a numerical example is provided to verify the developed approach and its practicality and effectiveness. © 2014 Wiley Periodicals, Inc. Complexity 21: 20–30, 2016     

Evaluating the robustness of temporal networks considering spatiality of connections

Network robustness has been a hot research area of studies on complex networks. Finding out the explanations behind the phenomena that networked systems can still function efficiently after some structural damages or the malfunction of certain nodes is meaningful to both the design of solid systems and the defend against failures. It is still indistinct what kind of resilience networked systems which change their topological structures incessantly over time might have. Nevertheless, earlier studies have frequently overlooked to consider the temporal characteristics which in many real scenarios are of great concern, or have considered only the temporality without spatiality which is not reasonable in the real world case. In this paper, we first take the spatiality of connections and communications between nodes, except for the temporal ordering of connection events which has solely been noticed by previous studies, into consideration for measuring and assessing the robustness of the temporal network. We propose a novel temporal efficiency metric, and correspondingly, develop a new temporal robustness evaluation method for temporal network models. The proposed metric and method show their validity through numerical simulations of three temporal network models and we give our evaluations and discussions.     

Forecasting macroeconomic fundamentals in economic crises

The goal of this paper is to introduce bounded rational behaviors in a competitive queuing system. Furthermore, we propose a realistic queuing model for two last-mile delivery services in which consumers are in competition. This work is derived from a real-world e-commerce application. We study the problem using a game theoretical point of view: the e-consumers are interacting through the last-mile delivery service system creating congestion for each other. Specifically, we focus our analysis on several equilibrium concepts from congestion/routing games: Wardrop and Logit equilibria. The difference in these equilibrium concepts is on the rationality level of players in the game. We are able to prove the existence and uniqueness of both equilibria. We compare them through a new metric called the Price of Rationality and we also compare each one to the social optimum solution through the Price of Anarchy. Some numerical results are presented in order to illustrate the theoretical results obtained.     

Robust delay-constrained routing in telecommunications

In telecommunications, operators usually use market surveys and statistical models to estimate traffic evolution in networks or to approximate queuing delay functions in routing strategies. Many research activities concentrated on handling traffic uncertainty in network design. Measurements on real world networks have shown significant errors in delay approximations, leading to weak management decisions in network planning. In this work, we introduce elements of robust optimization theory for delay modeling in routing problems. Different types of data uncertainty are considered and linked to corresponding robust models. We study a special case of constraints featuring separable additive functions. Specifically, we consider that each term of the sum is disturbed by a random parameter. These constraints are frequent in network based problems, where functions reflecting real world measurements on links are summed up over end-to-end paths. While classical robust formulations have to deal with the introduction of new variables, we show that, under specific hypotheses, the deterministic robust counterpart can be formulated in the space of original variables. This offers the possibility of constructing tractable robust models. Starting from Soyster’s conservative model, we write and compare different uncertainty sets and formulations offering each a different protection level for the delay constrained routing problem. Computational experiments are developed in order to evaluate the “price of robustness” and to assess the quality of the new formulations.     

Existence and global exponential stability of anti‐periodic solutions for delayed quaternion‐valued cellular neural networks with impulsive effects

In this paper, we consider a class of delayed quaternion‐valued cellular neural networks (DQVCNNs) with impulsive effects. By using a novel continuation theorem of coincidence degree theory, the existence of anti‐periodic solutions for DQVCNNs is obtained with or without assuming that the activation functions are bounded. Furthermore, by constructing a suitable Lyapunov function, some sufficient conditions are derived to guarantee the global exponential stability of anti‐periodic solutions for DQVCNNs. Our results are new and complementary to the known results even when DQVCNNs degenerate into real‐valued or complex‐valued neural networks. Finally, an example is given to illustrate the effectiveness of the obtained results.     

Discovery Through Gossip

We study randomized gossip‐based processes in dynamic networks that are motivated by information discovery in large‐scale distributed networks such as peer‐to‐peer and social networks. A well‐studied problem in peer‐to‐peer networks is resource discovery, where the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. Also, some of the recent work on self‐stabilization algorithms for P2P/overlay networks proceed via discovery of the complete network. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network — new edges are added to the network — and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes in a continuously changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip‐based discovery processes. In the push discovery or triangulation process, each node repeatedly chooses two random neighbors and connects them (i.e., “pushes” their mutual information to each other). In the pull discovery process or the two‐hop walk, each node repeatedly requests or “pulls” a random contact from a random neighbor and connects itself to this two‐hop neighbor. Both processes are lightweight in the sense that the amortized work done per node is constant per round, local, and naturally robust due to the inherent randomized nature of gossip. Our main result is an almost‐tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n‐node graph both processes take rounds to connect every node to all other nodes with high probability, whereas is a lower bound. We also study the two‐hop walk in directed graphs, and show that it takes time with high probability, and that the worst‐case bound is tight for arbitrary directed graphs, whereas Ω(n²) is a lower bound for strongly connected directed graphs. A key technical challenge that we overcome in our work is the analysis of a randomized process that itself results in a constantly changing network leading to complicated dependencies in every round. We discuss implications of our results and their analysis to discovery problems in P2P networks as well as to evolution in social networks. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 565–587, 2016     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

有限理性条件下演化博弈行为分析

基于博弈双方有限理性的假设,运用动力系统的相关理论和方法对一般2×2非对称演化博弈过程建立了动态复制方程,并对博弈双方在演化过程中的行为进行了分析,得出博弈双方交互系统均衡点及稳定性相应的结论及其全部动力学行为.     

Global lagrange stability of complex‐valued neural networks of neutral type with time‐varying delays

In this article, the problem of global exponential stability in Lagrange sense of neutral type complex‐valued neural networks (CVNNs) with delays is investigated. Two different classes of activation functions are considered, one can be separated into real part and imaginary part, and the other cannot be separated. Based on Lyapunov theory and analytic techniques, delay‐dependent criteria are provided to ascertain the aforementioned CVNNs to be globally exponentially stable GES in Lagrange sense. Moreover, the proposed sufficient conditions are presented in the form of linear matrix inequalities which could be easily checked by Matlab. Finally, two simulation examples are given out to demonstrate the validity of theory results. © 2016 Wiley Periodicals, Inc. Complexity 21: 438–450, 2016     

First order limits of sparse graphs: Plane trees and path‐width

Ne?et?il and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree‐depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path‐width has a limit modeling. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 612–635, 2017     

The Banzhaf index in complete and incomplete shareholding structures: A new algorithm

In this global world, many firms present a complex shareholding structure with indirect participation, such that it may become difficult to assess a firm’s controllers. Furthermore, if there are numerous dominant shareholders, the control can be shared between them. Determining who has the most influence is often a difficult task. To measure this influence, game theory allows the modeling of voting games and the computing of the Banzhaf index. This paper firstly offers a new algorithm to compute this index in all structures and then suggests some modelisations of the floating shareholder. Then, our model is applied to a real case study: the French group Lafarge. This exemplary case demonstrates how the float’s structure and hidden coalition can impact the power relationship between dominant shareholders.     

基于复杂网络演化博弈的企业低碳创新合作行为网络演化机理研究

针对企业低碳创新合作所面临的复杂问题,基于现实复杂网络结构特征,运用演化博弈理论研究有限理性下企业低碳创新合作行为网络演化机理,利用Matlab仿真技术探究无标度网络载体上微观因素对低碳创新合作行为的影响。研究结果表明:低碳创新利益分配、协同效益和违约惩罚对低碳创新合作行为网络演化结果的影响最为显著,网络规模越大网络演化速度越慢,网络规模越小对协同系数和利益分配系数的敏感性越强,网络规模越大对技术溢出系数和违约惩罚的敏感性越强。研究结论可以为企业低碳创新合作策略制定提供解决依据。     

Triple integral approach to reachable set bounding for linear singular systems with time‐varying delay

This paper is concerned with the reachable set estimation problem of singular systems with time‐varying delay and bounded disturbance inputs. Based on a novel Lyapunov–Krasovskii functional that contains four triple integral terms, reciprocally convex approach and free‐weighting matrix method, two sufficient conditions are derived in terms of linear matrix inequalities to guarantee that the reachable set of singular systems with time‐varying delay is bounded by the intersection of ellipsoid. Finally, two numerical examples are given to demonstrate the effectiveness and superiority of the proposed method. Copyright © 2016 John Wiley & Sons, Ltd.     

Analysis of decision-making in economic chaos control

In some economic chaotic systems, players are concerned about whether their performance is improved besides taking some methods to control chaos. In the face of chaos occurring in competition, whether one player takes controlling measures or not affects not only their own earning but also other opponents’ income. An output duopoly competing evolution model with bounded rationality is introduced in this paper. Using modern game theory, decision-making analyses about chaos control of the model are taken by taking aggregate profits as players’ payoff. It is found that the speed of players’ response to the market and whether the decisive parameters are in the stable region of the Nash equilibrium or not have a distinct influence on the results of the game. The impact of cost function’ type on results of the game is also found. The mechanism of influences is discovered by using numerical simulation.     

Detecting evolving patterns of self‐organizing networks by flow hierarchy measurement

Hierarchies occur widely in evolving self‐organizing ecological, biological, technological, and social networks, but detecting and comparing hierarchies is difficult. Here we present a metric and technique to quantitatively assess the extent to which self‐organizing directed networks exhibit a flow hierarchy. Flow hierarchy is a commonly observed but theoretically overlooked form of hierarchy in networks. We show that the ecological, neurobiological, economic, and information processing networks are generally more hierarchical than their comparable random networks. We further discovered that hierarchy degree has increased over the course of the evolution of Linux kernels. Taken together, our results suggest that hierarchy is a central organizing feature of real‐world evolving networks, and the measurement of hierarchy opens the way to understand the structural regimes and evolutionary patterns of self‐organizing networks. Our measurement technique makes it possible to objectively compare hierarchies of different networks and of different evolutionary stages of a single network, and compare evolving patterns of different networks. It can be applied to various complex systems, which can be represented as directed networks. © 2011 Wiley Periodicals, Inc. Complexity, 2011     

Fitness model for tiered structure in the interbank market

Tiered structure is observed in a range of countries' banking systems. In that case, relatively few first‐tier banks are not only interconnected, but are connected with second‐tier banks, whereas second‐tier banks are almost exclusively connected with first‐tier banks. This study uses the theory of complex networks to quantitatively characterize the formation of tiered structure in banking systems. The interbank market network model constructed in this article reproduces tiered structure and various statistical properties, namely, a small‐world property and a disassortative mixing property as well as a reciprocal property. This network modeling of the interbank market could be an efficient way to understand the bank behavior in the interbank market. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

An Alternating Direction Method for Nash Equilibrium of Two-Person Games with Alternating Offers

In this paper, we propose a method for finding a Nash equilibrium of two-person games with alternating offers. The proposed method is referred to as the inexact proximal alternating direction method. In this method, the idea of alternating direction method simulates alternating offers in the game, while the inexact solutions of subproblems can be matched to the assumptions of incomplete information and bounded individual rationality in practice. The convergence of the proposed method is proved under some suitable conditions. Numerical tests show that the proposed method is competitive to the state-of-the-art algorithms.