On the computational complexity of qualitative coalitional games

We study coalitional games in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices, with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games (qcgs) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining qcgs, we systematically formulate fourteen natural decision problems associated with them, and determine the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a qcg is non-empty is D^p₁-complete. (As an aside, we present what we believe is the first “natural” problem that is proven to be complete for D^p₂.) We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research.     

On the computational complexity of coalitional resource games

We study Coalitional Resource Games (crgs), a variation of Qualitative Coalitional Games (qcgs) in which each agent is endowed with a set of resources, and the ability of a coalition to bring about a set of goals depends on whether they are collectively endowed with the necessary resources. We investigate and classify the computational complexity of a number of natural decision problems for crgs, over and above those previously investigated for qcgs in general. For example, we show that the complexity of determining whether conflict is inevitable between two coalitions with respect to some stated resource bound (i.e., a limit value for every resource) is co-np-complete. We then investigate the relationship between crgs and qcgs, and in particular the extent to which it is possible to translate between the two models. We first characterise the complexity of determining equivalence between crgs and qcgs. We then show that it is always possible to translate any given crg into a succinct equivalent qcg, and that it is not always possible to translate a qcg into an equivalent crg; we establish some necessary and some sufficient conditions for a translation from qcgs to crgs to be possible, and show that even where an equivalent crg exists, it may have size exponential in the number of goals and agents of its source qcg.     

Overlapping community detection in social networks using coalitional games

Community detection is a significant research problem in various fields such as computer science, sociology and biology. The singular characteristic of communities in social networks is the multimembership of a node resulting in overlapping communities. But dealing with the problem of overlapping community detection is computationally expensive. The evolution of communities in social networks happens due to the self-interest of the nodes. The nodes of the social network acts as self-interested players, who wish to maximize their benefit through interactions in due course of community formation. Game theory provides a systematic framework tox capture the interactions between these selfish players in the form of games. In this paper, we propose a Community Detection Game (CDG) that works under the cooperative game framework. We develop a greedy community detection algorithm that employs Shapley value mechanism and majority voting mechanism in order to disclose the underlying community structure of the given network. Extensive experimental evaluation on synthetic and real-world network datasets demonstrates the effectiveness of CDG algorithm over the state-of-the-art algorithms.     

Internal structure of coalitions in competitive and altruistic graphical coalitional games

This paper introduces a certain graphical coalitional game where the internal topology of the coalition depends on a prescribed communication graph structure among the agents. The game Value Function is required to satisfy four Axioms of Value. These axioms make it possible to provide a refined study of coalition structures on graphs by defining a formal graphical game and by assigning a Positional Advantage, based on the Shapley value, to each agent in a coalition based on its connectivity properties within the graph. Using the Axioms of Value the graphical coalitional game can be shown to satisfy properties such as convexity, fairness, cohesiveness, and full cooperativeness. Three measures of the contributions of agents to a coalition are introduced: marginal contribution, competitive contribution, and altruistic contribution. The mathematical framework given here is used to establish results regarding the dependence of these three types of contributions on the graph topology, and changes in these contributions due to changes in graph topology. Based on these different contributions, three online sequential decision games are defined on top of the graphical coalitional game, and the stable graphs under each of these sequential decision games are studied. It is shown that the stable graphs under the objective of maximizing the marginal contribution are any connected graph. The stable graphs under the objective of maximizing the competitive contribution are the complete graph. The stable graphs under the objective of maximizing the altruistic contribution are any tree.     

Stochastic coalitional better-response dynamics and stable equilibrium

We consider coalition formation among players in an n-player finite strategic game over infinite horizon. At each time a randomly formed coalition makes a joint deviation from a current action profile such that at new action profile all the players from the coalition are strictly benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a K-stable equilibrium or becomes stuck in a closed cycle. We also assume that at each time a selected coalition makes mistake in deviation with small probability that add mutations (perturbations) into CBR dynamics. We prove that all K-stable equilibria and all action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Similar statement holds for strict K-stable equilibrium. We apply the CBR dynamics to study the dynamic formation of the networks in the presence of mutations. Under the CBR dynamics all strongly stable networks and closed cycles of networks are stochastically stable.     

On the robustness of sampled-data control to unmodeledhigh-frequency dynamics

Robustness of sampled-data control designs to unmodeled high-frequency dynamics is studied using singular perturbation theory. It is argued that when the plant is preceded by a zero-order hold, a direct transmission term of the reduced-order model, which results from neglecting high-frequency dynamics, should be modeled as a delay element in order to ensure robustness     

On best response dynamics in weighted congestion games with polynomial delays

We investigate the speed of convergence of best response dynamics to approximately optimal solutions in weighted congestion games with polynomial delay functions. Awerbuch et?al. (Fast convergence to nearly optimal solutions in potential games. ACM Conference on Electronic Commerce, 2008) showed that the convergence time of such dynamics to Nash equilibrium may be exponential in the number of players n even for unweighted players and linear delay functions. Nevertheless, we show that ??(n log log W) (where W is the sum of all the players?? weights) best responses are necessary and sufficient to achieve states that approximate the optimal solution by a constant factor, under the assumption that every O(n) steps each player performs a constant (and non-null) number of best responses. For congestion games in which computing a best response is a polynomial time solvable problem, such a dynamics naturally implies a polynomial time distributed algorithm for the problem of computing the social optimum in congestion games, approximating the optimal solution by a constant factor.     

Concurrent imitation dynamics in congestion games

Imitating successful behavior is a natural and frequently applied approach when facing complex decision problems. In this paper, we design protocols for distributed latency minimization in atomic congestion games based on imitation. We propose to study concurrent dynamics that emerge when each agent samples another agent and possibly imitates this agent’s strategy if the anticipated latency gain is sufficiently large. Our focus is on convergence properties. We show convergence in a monotonic fashion to stable states, in which none of the agents can improve their latency by imitating others. As our main result, we show rapid convergence to approximate equilibria, in which only a small fraction of agents sustains a latency significantly above or below average. Imitation dynamics behave like an FPTAS, and the convergence time depends only logarithmically on the number of agents. Imitation processes cannot discover unused strategies, and strategies may become extinct with non-zero probability. For singleton games we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton games with linear latency functions. We concentrate on the case of symmetric network congestion games, but our results do not use the network structure and continue to hold accordingly for general symmetric games. They even apply to asymmetric games when agents sample within the set of agents with the same strategy space. Finally, we discuss how the protocol can be extended such that, in the long run, dynamics converge to a pure Nash equilibrium.     

On evolvability and robustness in the matrix-GRT model

Quantifying evolution and understanding robustness are best done with a system that is both rich enough to frustrate rigging of the answer and simple enough to permit comparison against either existing systems or absolute measures. Such a system is provided by the self-referential model matrix-genome, replication and translation, based on the concept of operators, which is introduced here. Ideas are also taken from the evolving micro-controller research. This new model replaces micro-controllers by simple matrix operations. These matrices, seen as abstract proteins, work on abstract genomes, peptides or other proteins. Studying the evolutionary properties shows that the protein-only hypothesis (proteins as active elements) shows poor evolvability and the RNA-before-protein hypothesis (genomes controlling) exhibits similar intricate evolutionary dynamics as in the micro-controller model. A simple possible explanation for this surprising difference in behavior is presented. In addition to existing evolutionary models, dynamical and organizational changes or transitions occurring late in long-term experiments are demonstrated.     

On continuity/discontinuity in robustness indicators

Continuity/discontinuity of robustness indicators is reviewed. For the case of real or mixed uncertainty, a regularization of a conservative bound to the robustness margin is proposed, and its properties are discussed. In the case of polynomial families with affine dependency on the uncertainty, a regularization of the robustness margin results     

The (un)Economic Internet?

The Internet economics track will address how economic and policy issues relate to the emergence of the Internet as critical infrastructure. The authors provide a historical overview of internetworking, identifying key transitions that have contributed to the Internet's development and penetration. Its core architecture wasn't designed to serve as critical communications infrastructure for society; rather, the infrastructure developed far beyond the expectations of the original funding agencies, architects, developers, and early users. The incongruence between the Internet's underlying architecture and society's current use and expectations of it means we can no longer study Internet technology in isolation from the political and economic context in which it is deployed     

On three concepts in robust design optimization: absolute robustness,relative robustness,and less variance

Structural and Multidisciplinary Optimization - This paper provides a clear perspective on existing several different approaches to robust design optimization of structures. We primarily consider...     

Convergence of best-response dynamics in games with conflicting congestion effects

We study the model of resource allocation games with conflicting congestion effects that was introduced by Feldman and Tamir [9]. In this model, an agent's cost consists of its resource's load (which increases with congestion) and its share in the resource's activation cost (which decreases with congestion). The current work studies the convergence rate of best-response dynamics (BRD) in the case of homogeneous agents. Even within this simple setting, interesting phenomena arise. We show that, in contrast to standard congestion games with identical jobs and resources, the convergence rate of BRD under conflicting congestion effects might be super-linear in the number of jobs. Nevertheless, a specific form of BRD is proposed, which is guaranteed to converge in linear time.     

Updating a balanced search tree in O(1) rotations

Olivié has recently introduced the class of ‘half-balanced’ binary search trees, which have O(log n) access time but require only a constant number of single rotations for rebalancing after an insertion or a deletion. In this paper we show that a well-known class of balanced binary trees, the ‘symmetric binary B-trees’ of Bayer, have the same properties. This is not surprising, for Bayer's class and Oliviés class contain exactly the same binary trees.     

Dependence in games and dependence games

In the multi-agent systems community, dependence theory and game theory are often presented as two alternative perspectives on the analysis of agent interaction. The paper presents a formal analysis of a notion of dependence between players, given in terms of standard game-theoretic notions of rationality such as dominant strategy and best response. This brings the notion of dependence within the realm of game theory providing it with the sort of mathematical foundations which still lacks. Concretely, the paper presents two results: first, it shows how the proposed notion of dependence allows for an elegant characterization of a property of reciprocity for outcomes in strategic games; and second, it shows how the notion can be used to define new classes of coalitional games, where coalitions can force outcomes only in the presence of reciprocal dependencies.     

Characterizing game dynamics in two-player strategy games using network motifs.

Many complex systems, whether biological, sociological, or physical ones, can be represented using networks. In these networks, a node represents an entity, and an arc represents a relationship/constraint between two entities. In discrete dynamics, one can construct a series of networks with each network representing a time snapshot of interaction among the different components in the system. Understanding these networks is a key to understand the dynamics of real and artificial systems. Network motifs are small graphs-usually three to four nodes-representing local structures. They have been widely used in studying complex systems and in characterizing features on the system level by analyzing locally how the substructures are formed. Frequencies of different network motifs have been shown in the literature to vary from one network to another, and conclusions hypothesized that these variations are due to the evolution/dynamics of the system. In this paper, we show for the first time that in strategy games, each game (i.e., type of dynamism) has its own signature of motifs and that this signature is maintained during the evolution of the game. We reveal that deterministic strategy games have unique footprints (motifs' count) that can be used to recognize and classify the game's type and that these footprints are consistent along the evolutionary path of the game. The findings of this paper have significance for a wide range of fields in cybernetics.