Many real world networks change over time. This may arise due to individuals joining or leaving the network or due to links forming or being broken. These events may arise because of interactions between the vertices ...Many real world networks change over time. This may arise due to individuals joining or leaving the network or due to links forming or being broken. These events may arise because of interactions between the vertices which occasion payoffs which subsequently determine the fate of the vertices, due to ageing or crowding, or perhaps due to isolation. Such phenomena result in a dynamical system which may lead to complex behaviours, to selfreplication, to chaotic or regular patterns, or to emergent phenomena from local interactions. They hopefully give insight to the nature of the real-world phenomena which the network, and its dynamics, may approximate. To a large extent the models considered here are motivated by biological and social phenomena, where the vertices may be genes, proteins, genomes or organisms, and the links interactions of various kinds. In this, the third paper of a series, we consider the vertices to be players of some game. Offspring inherit their parent’s strategies and vertices which behave poorly in games with their neighbours get destroyed. The process is analogous to the way different kinds of animals reproduce whilst unfit animals die. Some game based systems are analytically tractable, others are highly complex-causing small initial structures to grow and break into large collections of self replicating structures.展开更多
With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of i...With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of interacting players have been proposed and best response games are amongst the simplest. In best response games each vertex simultaneously updates to employ the best response to their current surroundings. We concentrate upon trying to understand the dynamics of best response games on regular graphs with many strategies. When more than two strategies are present highly complex dynamics can ensue. We focus upon trying to understand exactly how best response games on regular graphs sample from the space of possible cellular automata. To understand this issue we investigate convex divisions in high dimensional space and we prove that almost every division of k - 1 dimensional space into k convex regions includes a single point where all regions meet. We then find connections between the convex geometry of best response games and the theory of alternating circuits on graphs. Exploiting these unexpected connections allows us to gain an interesting answer to our question of when cellular automata are best response games.展开更多
Given a graph g=( V,A ) , we define a space of subgraphs M with the binary operation of union and the unique decomposition property into blocks. This space allows us to discuss a notion of minimal subgraphs (minimal c...Given a graph g=( V,A ) , we define a space of subgraphs M with the binary operation of union and the unique decomposition property into blocks. This space allows us to discuss a notion of minimal subgraphs (minimal coalitions) that are of interest for the game. Additionally, a partition of the game is defined in terms of the gain of each block, and subsequently, a solution to the game is defined based on distributing to each player (node and edge) present in each block a payment proportional to their contribution to the coalition.展开更多
Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one playe...Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one player. Alice’s goal is to color all vertices with the k colors, while Bob’s goal is to prevent her. The game chromatic number denoted by?χg(G), is the smallest k such that Alice has a winning strategy with k colors. In this paper, we determine the game chromatic number?χg of circulant graphs?Cn(1,2), , and generalized Petersen graphs GP(n,2), GP(n,3).展开更多
In this paper, we analyse the deployment of middlebox. For a given network information and policy requirements, an attempt is made to determine the optimal location of middlebox to achieve the best performance. In ter...In this paper, we analyse the deployment of middlebox. For a given network information and policy requirements, an attempt is made to determine the optimal location of middlebox to achieve the best performance. In terms of the end-to-end delay as a performance optimization index, a distributed middlebox placement algorithm based on potential game is proposed. Through extensive simulations, it demonstrates that the proposed algorithm achieves the near-optimal solution, and the end-to-end delay decreases significantly.展开更多
文摘Many real world networks change over time. This may arise due to individuals joining or leaving the network or due to links forming or being broken. These events may arise because of interactions between the vertices which occasion payoffs which subsequently determine the fate of the vertices, due to ageing or crowding, or perhaps due to isolation. Such phenomena result in a dynamical system which may lead to complex behaviours, to selfreplication, to chaotic or regular patterns, or to emergent phenomena from local interactions. They hopefully give insight to the nature of the real-world phenomena which the network, and its dynamics, may approximate. To a large extent the models considered here are motivated by biological and social phenomena, where the vertices may be genes, proteins, genomes or organisms, and the links interactions of various kinds. In this, the third paper of a series, we consider the vertices to be players of some game. Offspring inherit their parent’s strategies and vertices which behave poorly in games with their neighbours get destroyed. The process is analogous to the way different kinds of animals reproduce whilst unfit animals die. Some game based systems are analytically tractable, others are highly complex-causing small initial structures to grow and break into large collections of self replicating structures.
文摘With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of interacting players have been proposed and best response games are amongst the simplest. In best response games each vertex simultaneously updates to employ the best response to their current surroundings. We concentrate upon trying to understand the dynamics of best response games on regular graphs with many strategies. When more than two strategies are present highly complex dynamics can ensue. We focus upon trying to understand exactly how best response games on regular graphs sample from the space of possible cellular automata. To understand this issue we investigate convex divisions in high dimensional space and we prove that almost every division of k - 1 dimensional space into k convex regions includes a single point where all regions meet. We then find connections between the convex geometry of best response games and the theory of alternating circuits on graphs. Exploiting these unexpected connections allows us to gain an interesting answer to our question of when cellular automata are best response games.
文摘Given a graph g=( V,A ) , we define a space of subgraphs M with the binary operation of union and the unique decomposition property into blocks. This space allows us to discuss a notion of minimal subgraphs (minimal coalitions) that are of interest for the game. Additionally, a partition of the game is defined in terms of the gain of each block, and subsequently, a solution to the game is defined based on distributing to each player (node and edge) present in each block a payment proportional to their contribution to the coalition.
文摘Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one player. Alice’s goal is to color all vertices with the k colors, while Bob’s goal is to prevent her. The game chromatic number denoted by?χg(G), is the smallest k such that Alice has a winning strategy with k colors. In this paper, we determine the game chromatic number?χg of circulant graphs?Cn(1,2), , and generalized Petersen graphs GP(n,2), GP(n,3).
文摘In this paper, we analyse the deployment of middlebox. For a given network information and policy requirements, an attempt is made to determine the optimal location of middlebox to achieve the best performance. In terms of the end-to-end delay as a performance optimization index, a distributed middlebox placement algorithm based on potential game is proposed. Through extensive simulations, it demonstrates that the proposed algorithm achieves the near-optimal solution, and the end-to-end delay decreases significantly.
