Functionals on function and sequence spaces connected with the exponential stability of evolutionary processes

The exponential stability property of an evolutionary process is characterized in terms of the existence of some functionals on certain function spaces. Thus are generalized some well-known results obtained by Datko, Rolewicz, Littman and Van Neerven.     

On the communication complexity of Bar-Yehuda, Goldreich and Itai's randomized broadcasting algorithm

The algorithm by Bar-Yehuda, Goldreich and Itai is one of the best known randomized broadcast algorithms for radio networks. Its probability of success and time complexity are nearly optimal. We propose a modification of this algorithm, which decreases the communication complexity, preserving other properties. Moreover, we show that the local communication complexity of the modified algorithm is deterministic.     

On the stability of evolutionary dynamics in games with incomplete information

In an interaction it is possible that one agent has features it is aware of but the opponent is not. These features (e.g. cost, valuation or fighting ability) are referred to as the agent’s type. The paper compares two models of evolution in symmetric situations of this kind. In one model the type of an agent is fixed and evolution works on strategies of types. In the other model every agent adopts with fixed probabilities both types, and type-contingent strategies are exposed to evolution. It is shown that the dynamic stability properties of equilibria may differ even when there are only two types and two strategies. However, in this case the dynamic stability properties are generically the same when the payoff of a player does not depend directly on the type of the opponent. Examples illustrating these results are provided.     

Energy rate density as a complexity metric and evolutionary driver

The proposition that complexity generally increases with evolution seems indisputable. Both developmental and generational changes often display a rise in the number and diversity of properties describing a wide spectrum of ordered systems, whether physical, biological, or cultural. This article explores a quantitative metric that can help to explain the emergence and evolution of galaxies, stars, planets, and life throughout the history of the Universe. Energy rate density is a single, measurable, and unambiguous quantity uniformly characterizing Nature's many varied complex systems, potentially dictating their natural selection on vast spatial and temporal scales. © 2010 Wiley Periodicals, Inc. Complexity 16: 27–40, 2011     

Stability,structural stability,and games: Toward a theory of differential hypergames

Differential games (DG's) are investigated from a stability point of view. Several resemblances between the theory of optimal control and that of structural stability suggest a differential game approach in which the operators have conflicting interests regarding the stability of the system only. This qualitative approach adds several interesting new features. The solution of a differential game is defined to be the equilibrium position of a dynamical system in the framework of a given stability theory: this is the differential hypergame (DHG). Three types of DHG are discussed: abstract structural DHG, Liapunov DHG, and Popov DHG. The first makes the connection between DG and the catastrophe theory of Thom; the second makes the connection between the value function approach and Liapunov theory; and the third provides invariant properties for DG's. To illustrate the fact that the theory sketched here may find interesting applications, the up-to-date problem of the world economy is outlined.This research was supported by the National Research Council of Canada.     

Computational complexity of logical theories of one successor and another unary function

The first-order logical theory Th\(({\mathbb{N}},x + 1,F(x))\) is proved to be complete for the class ATIME-ALT\((2^{O(n)},O(n))\) when \(F(x) = 2^{x}\), and the same result holds for \(F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)\), and F(x) =  tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.     

Communication and time complexity of a distributed election protocol

we evaluate several variants of a standard election algorithm on a ring of processors. The performance measures of interest are the number of messages exchanged (communication complexity) and the execution time (time complexity). Classical models use a synchronism assumption according to which all processors start at the same time and message delays are constant.We attempt to capture the essential asynchronism of this class of algorithms by using probabilistic models. Two such models are discussed, one in discrete and one in continuous time. In each case, both the uni- and the bidirectional cases are studied and compared. We obtain expressions for the distributions of the number of exchanged messages and derive their asymptotic behavior whenn, the number of processors in the ring, grows large. The results show how the communication complexity actually depends on the speed of communcations on the ring, and what is the interest of having bidirectional communications.We also address in part the evaluation of the completion time of the algorithm. This time decomposes into astartup time and anexploration time. We show that the average of the startup time is of the order of logn.     

The Co‐evolution of cooperation and complexity in a multi‐player,local‐interaction prisoners' dilemma

Agents located on a 20 × 20 toroidal lattice play a Prisoners' Dilemma game with their Moore neighbors, adopting policies of cooperation and defection that depend only on their own action and the number of cooperators in the neighborhood in the last round of the game. These policies (“characters”) are encoded in 19‐bit strings, which are subjected to evolution according to a genetic algorithm, with selection based on the cumulative scores of the agents in the neighborhood over 10 rounds of the basic game. Simulations examine the evolution of the population of characters over 1000 generations. Even with selection disabled, the genetic algorithm organizes the population into a small number of surviving characters clustered in spatially homogeneous regions. Selection for fitness rapidly achieves uniform cooperation. The characters evolved cooperate on the initial play, continue to cooperate when five or more of their neighbors cooperate, tend to defect defensively when they have cooperated and most of their neighbors have defected, and switch back to cooperation when five or more neighbors cooperate. When selection operates at the level of the whole society, however, the diversity of the population rapidly collapses, a single character predominates, and the cooperativeness of the dominating character is a matter of chance, so that there is no systematic tendency to evolve cooperation. © 2001 John Wiley & Sons, Inc.     

Communication, credible improvements and the core of an economy with asymmetric information

We analyze an economy with asymmetric information and endogenize the possibilities for information transmission between members of a coalition. We then define a concept of the Core that takes into account these communication possibilities. The internal consistency of the improvements is considered and an Internally Consistent Core, which requires credibility from the improvements is introduced. Received: September 1998/revised version: June 1999     

Formulation and optimization control of a class of networked evolutionary games with switched topologies

This paper studies the algebraic formulation and optimization control for a class of networked evolutionary games with switched topologies via the semi-tensor product method. First, an algebraic expression is formulated for the given networked evolutionary games, based on which, the behavior of corresponding evolutionary games is analyzed. Then, under some certain assumptions, the existence of fixed points for the given systems is proved and a free-type control sequence is designed to guarantee the best strategy profile reachable globally. Finally, an illustrative example is studied to support our new results.     

Evolutionary and asymptotic stability in symmetric multi-player games

We provide a classification of symmetric three-player games with two strategies and investigate evolutionary and asymptotic stability (in the replicator dynamics) of their Nash equilibria. We discuss similarities and differences between two-player and multi-player games. In particular, we construct examples which exhibit a novel behavior not found in two-player games.Received October 2001/Revised May 2003     

Active constraints,indefinite quadratic test problems,and complexity

The observation that at leasts constraints are active when the Hessian of the Lagrangian hass negative eigenvalues at a local minimizer is used to obtain two results: (i) a class of nearly concave quadratic minimization problem can be solved in polynomial time; (ii) a class of indefinite quadratic test problems can be constructed with a specified number of positive and negative eigenvalues and with a known global minimizer.The authors thank the reviewers for their constructive comments. The first author was supported by the National Science Foundation Grant DMS-85-20926 and by the Air Force Office of Scientific Research Grant AFOSR-ISSA-86-0091.     

Minimum concave-cost network flow problems: Applications,complexity, and algorithms

We discuss a wide range of results for minimum concave-cost network flow problems, including related applications, complexity issues, and solution techniques. Applications from production and inventory planning, and transportation and communication network design are discussed. New complexity results are proved which show that this problem is NP-hard for cases with cost functions other than fixed charge. An overview of solution techniques for this problem is presented, with some new results given regarding the implementation of a particular branch-and-bound approach.     

Multi-period lot-sizing with supplier selection: Structural results,complexity and algorithms

We consider a multi-period lot-sizing problem with multiple products and multiple suppliers. Demand is deterministic and time-varying. The objective is to determine order quantities to minimize the total cost over a finite planning horizon. This problem is strongly NP-hard. For a special case, we extend the classical zero-inventory-ordering principle and solve it by dynamic programming. Based on this new extension, we also develop a heuristic algorithm for the general problem and computationally show that it works well.     

Communication structure,trust and the free rider problem

Despite the recent wave of interest in the social and physical sciences regarding “complexity,” relatively title attention has been given to the logical foundation of complexity measurement. With this in mind, a number of fairly simple, “reasonable” axioms for the measurement of network complexity are here presented, and some of the implications of these axioms are considered. It is shown that the only family of graph complexity measures satisfying the “reasonable” axioms is of limited theoretical utility, and hence that those seeking more interesting measures of complexity must be willing to sacrifice at least one intuitively reasonable constraint. Several existing complexity measures are also described, and are differentiated from one another on an axiomatic basis. Finally, some suggestions are offered regarding future efforts at measuring graph complexity.     

Successive minima profile,lattice profile,and joint linear complexity profile of pseudorandom multisequences

In this paper we use the successive minima profile to measure structural properties of pseudorandom multisequences. We show that both the lattice profile and the joint linear complexity profile of a multisequence can be expressed in terms of the successive minima profile.     

On the bargaining set, kernel and core of superadditive games

We prove that for superadditive games a necessary and sufficient condition for the bargaining set to coincide with the core is that the monotonic cover of the excess game induced by a payoff be balanced for each imputation in the bargaining set. We present some new results obtained by verifying this condition for specific classes of games. For N-zero-monotonic games we show that the same condition required at each kernel element is also necessary and sufficient for the kernel to be contained in the core. We also give examples showing that to maintain these characterizations, the respective assumptions on the games cannot be lifted. Received: March 1998/Revised version: December 1998     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999