Distributed multi-agent optimization with state-dependent communication

We study distributed algorithms for solving global optimization problems in which the objective function is the sum of local objective functions of agents and the constraint set is given by the intersection of local constraint sets of agents. We assume that each agent knows only his own local objective function and constraint set, and exchanges information with the other agents over a randomly varying network topology to update his information state. We assume a state-dependent communication model over this topology: communication is Markovian with respect to the states of the agents and the probability with which the links are available depends on the states of the agents. We study a projected multi-agent subgradient algorithm under state-dependent communication. The state-dependence of the communication introduces significant challenges and couples the study of information exchange with the analysis of subgradient steps and projection errors. We first show that the multi-agent subgradient algorithm when used with a constant stepsize may result in the agent estimates to diverge with probability one. Under some assumptions on the stepsize sequence, we provide convergence rate bounds on a “disagreement metric” between the agent estimates. Our bounds are time-nonhomogeneous in the sense that they depend on the initial starting time. Despite this, we show that agent estimates reach an almost sure consensus and converge to the same optimal solution of the global optimization problem with probability one under different assumptions on the local constraint sets and the stepsize sequence.     

Stochastic mirror descent method for distributed multi-agent optimization

This paper considers a distributed optimization problem encountered in a time-varying multi-agent network, where each agent has local access to its convex objective function, and cooperatively minimizes a sum of convex objective functions of the agents over the network. Based on the mirror descent method, we develop a distributed algorithm by utilizing the subgradient information with stochastic errors. We firstly analyze the effects of stochastic errors on the convergence of the algorithm and then provide an explicit bound on the convergence rate as a function of the error bound and number of iterations. Our results show that the algorithm asymptotically converges to the optimal value of the problem within an error level, when there are stochastic errors in the subgradient evaluations. The proposed algorithm can be viewed as a generalization of the distributed subgradient projection methods since it utilizes more general Bregman divergence instead of the Euclidean squared distance. Finally, some simulation results on a regularized hinge regression problem are presented to illustrate the effectiveness of the algorithm.     

Finite-time consensus for switching network topologies with disturbances

In this paper we investigate the properties of a decentralized consensus algorithm for a network of continuous-time integrators subject to unknown-but-bounded time-varying disturbances. The proposed consensus algorithm is based on a discontinuous local interaction rule. Under certain restrictions on the switching topology, it is proven that after a finite transient time the agents achieve an approximated consensus condition by attenuating the destabilizing effect of the disturbances. This main result is complemented by an additional result establishing the achievement of consensus under different requirements on the switching communication topology. In particular, we provide a convergence result that encompasses situations in which the time varying graph is always disconnected. Lyapunov analyses are carried out to support the suggested algorithms and results. Simulative tests considering, as case study, the synchronization problem for a network of clocks are illustrated and commented on to validate the developed analysis.     

On the consensus protocol of conspecific agents

We present a class of consensus protocols over groups of agents with stochastically switching, directed, and weighted communication topologies. In this protocol, an agent’s traits, that is, the cardinality of its neighbor set and the weight assigned to its neighbors in the updating process, are given by two jointly distributed random variables and the neighbors of an agent are selected with equal probability. We provide closed form results for the asymptotic convergence rate and for the steady state mean square deviation in the presence of additive noise. These results are specialized to consensus protocols based on Erd?s–Rényi and numerosity-constrained networks.     

Leaderless and leader-following consensus of multi-agent chaotic systems with unknown time delays and switching topologies

In this paper the distributed consensus problem for a class of multi-agent chaotic systems with unknown time delays under switching topologies and directed intermittent communications is investigated. Each agent is modeled as a general nonlinear system including many chaotic systems with or without time delays. Based on the Lyapunov stability theory and graph theory, some sufficient conditions guarantee the exponential convergence. A graph-dependent Lyapunov proof provides the definite relationship among the bound of unknown time delays, the admissible communication rate and each possible topology duration. Moreover, the relationship reveals that these parameters have impacts on both the convergence speed and control cost. The case with leader-following communication graph is also addressed. Finally, simulation results verify the effectiveness of the proposed method.     

Cucker–Smale flocking under rooted leadership and time-varying heterogeneous delays

In this paper, a Cucker–Smale model with time-varying heterogeneous delays in the communication process is investigated, where the delay on each communication link is time-varying and independent of other communication links. A general update rule based on the distance between agents is used to determine the edge weights of the communication network. The method of constructing augmented system is used so that the system stability is transformed into a product convergence problem of time-varying sub-stochastic matrices equivalently. By analyzing this convergence problem, a sufficient condition is established to achieve flocking, which relates to the initial states, the structure of communication network and the upper bound of time delays.     

The influence of random interactions and decision heuristics on norm evolution in social networks

In this paper we explore the effect that random social interactions have on the emergence and evolution of social norms in a simulated population of agents. In our model agents observe the behaviour of others and update their norms based on these observations. An agent’s norm is influenced by both their own fixed social network plus a second random network that is composed of a subset of the remaining population. Random interactions are based on a weighted selection algorithm that uses an individual’s path distance on the network to determine their chance of meeting a stranger. This means that friends-of-friends are more likely to randomly interact with one another than agents with a higher degree of separation. We then contrast the cases where agents make highest utility based rational decisions about which norm to adopt versus using a Markov Decision process that associates a weight with the best choice. Finally we examine the effect that these random interactions have on the evolution of a more complex social norm as it propagates throughout the population. We discover that increasing the frequency and weighting of random interactions results in higher levels of norm convergence and in a quicker time when agents have the choice between two competing alternatives. This can be attributed to more information passing through the population thereby allowing for quicker convergence. When the norm is allowed to evolve we observe both global consensus formation and group splintering depending on the cognitive agent model used.     

Distributed subgradient method for multi‐agent optimization with quantized communication

This paper focuses on a distributed optimization problem associated with a time‐varying multi‐agent network with quantized communication, where each agent has local access to its convex objective function, and cooperatively minimizes a sum of convex objective functions of the agents over the network. Based on subgradient methods, we propose a distributed algorithm to solve this problem under the additional constraint that agents can only communicate quantized information through the network. We consider two kinds of quantizers and analyze the quantization effects on the convergence of the algorithm. Furthermore, we provide explicit error bounds on the convergence rates that highlight the dependence on the quantization levels. Finally, some simulation results on a l₁‐regression problem are presented to demonstrate the performance of the algorithm. Copyright © 2016 John Wiley & Sons, Ltd.     

Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs and his own objective function, but both share the same processor. The goal is to minimize the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. In this paper we study two-agent scheduling problems on a proportionate flowshop. Three objective functions of the first agent are considered: minimum maximum cost of all the jobs, minimum total completion time, and minimum number of tardy jobs. For the second agent, an upper bound on the maximum allowable cost is assumed. We introduce efficient polynomial time solution algorithms for all cases.     

A model of influence based on aggregation functions

The paper concerns a dynamic model of influence in which agents make a yes–no decision. Each agent has an initial opinion which he may change during different phases of interaction, due to mutual influence among agents. We investigate a model of influence based on aggregation functions. Each agent modifies his opinion independently of the others, by aggregating the current opinion of all agents. Our framework covers numerous existing models of opinion formation, since we allow for arbitrary aggregation functions. We provide a general analysis of convergence in the aggregation model and find all terminal classes and states. We show that possible terminal classes to which the process of influence may converge are terminal states (the consensus states and nontrivial states), cyclic terminal classes, and unions of Boolean lattices (called regular terminal classes). An agent is influential for another agent if the opinion of the first one matters for the latter. A generalization of influential agent to an irreducible coalition whose opinion matters for an agent is called influential coalition. The graph (hypergraph) of influence is a graphical representation of influential agents (coalitions). Based on properties of the hypergraphs of influence we obtain conditions for the existence of the different kinds of terminal classes. An important family of aggregation functions–the family of symmetric decomposable models–is discussed. Finally, based on the results of the paper, we analyze the manager network of Krackhardt.     

Robust consensus of nonlinear multi‐agent systems via reliable control with probabilistic time delay

In this paper, the consensus problem of uncertain nonlinear multi‐agent systems is investigated via reliable control in the presence of probabilistic time‐varying delay. First, the communication topology among the agents is assumed to be directed and fixed. Second, by introducing a stochastic variable which satisfies Bernoulli distribution, the information of probabilistic time‐varying delay is equivalently transformed into the deterministic time‐varying delay with stochastic parameters. Third, by using Laplacian matrix properties, the consensus problem is converted into the conventional stability problem of the closed‐loop system. The main objective of this paper is to design a state feedback reliable controller such that for all admissible uncertainties as well as actuator failure cases, the resulting closed‐loop system is robustly stable in the sense of mean‐square. For this purpose, through construction of a suitable Lyapunov–Krasovskii functional containing four integral terms and utilization of Kronecker product properties along with the matrix inequality techniques, a new set of delay‐dependent consensus stabilizability conditions for the closed‐loop system is obtained. Based on these conditions, the desired reliable controller is designed in terms of linear matrix inequalities which can be easily solved by using any of the effective optimization algorithms. Moreover, a numerical example and its simulations are included to demonstrate the feasibility and effectiveness of the proposed control design scheme. © 2016 Wiley Periodicals, Inc. Complexity 21: 138–150, 2016     

A note on the consensus finding problem in communication networks with switching topologies

In this note, we discuss the problem of consensus finding in communication networks of agents with dynamically switching topologies. In particular, we consider the case of directed networks with unbalanced matrices of communication rates. We formulate sufficient conditions for consensus finding in terms of strong connectivity of the underlying directed graphs and prove that, given these conditions, consensus is found asymptotically. Moreover, we show that this consensus is an emergent property of the system, being encoded in its dynamics and not just an invariant of its initial configuration.     

Single-machine scheduling of proportionally deteriorating jobs by two agents

We consider a problem of scheduling a set of independent jobs by two agents on a single machine. Every agent has its own subset of jobs to be scheduled and uses its own optimality criterion. The processing time of each job proportionally deteriorates with respect to the starting time of the job. The problem is to find a schedule that minimizes the total tardiness of the first agent, provided that no tardy job is allowed for the second agent. We prove basic properties of the problem and give a lower bound on the optimal value of the total tardiness criterion. On the basis of these results, we propose a branch-and-bound algorithm and an evolutionary algorithm for the problem. Computational experiments show that the exact algorithm solves instances up to 50 jobs in a reasonably short time and that solutions obtained by the metaheuristic are close to optimal ones.     

Numerical Analysis of a Nonlinear Singularly Perturbed Delay Volterra Integro-Differential Equation on an Adaptive Grid

In this paper, we study a nonlinear first-order singularly perturbed Volterra integro-differential equation with delay. This equation is discretized by the backward Euler for differential part and the composite numerical quadrature formula for integral part for which both an a priori and an a posteriori error analysis in the maximum norm are derived. Based on the a priori error bound and mesh equidistribution principle, we prove that there exists a mesh gives optimal first order convergence which is robust with respect to the perturbation parameter. The a posteriori error bound is used to choose a suitable monitor function and design a corresponding adaptive grid generation algorithm. Furthermore, we extend our presented adaptive grid algorithm to a class of second-order nonlinear singularly perturbed delay differential equations. Numerical results are provided to demonstrate the effectiveness of our presented monitor function. Meanwhile, it is shown that the standard arc-length monitor function is unsuitable for this type of singularly perturbed delay differential equations with a turning point.     

Clustering and asymptotic behavior in opinion formation

We investigate the long time behavior of models of opinion formation. We consider the case of compactly supported interactions between agents which are also non-symmetric, including for instance the so-called Krause model. Because of the finite range of interaction, convergence to a unique consensus is not expected in general. We are nevertheless able to prove the convergence to a final equilibrium state composed of possibly several local consensus. This result had so far only been conjectured through numerical evidence. Because of the non-symmetry in the model, the analysis is delicate and is performed in two steps: First using entropy estimates to prove the formation of stable clusters and then studying the evolution in each cluster. We study both discrete and continuous in time models and give rates of convergence when those are available.     

Corruption and its detection: a graph-theoretic approach

We consider a corruption network where agents, both internal or external to the network, use connections and bribes to obtain goods or services outside the formal procedures. We develop a graph-theoretic model for the system and present sufficient conditions for detectability of the corruption status of at least one agent. Where detectability is not possible, we determine the topology of the network and all the possible corruption statuses of the agents. Further we provide, if we have information on the corruption status of a single agent, an algorithm that identifies the corruption status of every other agent in the network. Our results provide tools for detecting corrupt agents in organizations such as revenue authorities, municipalities, police, vehicle inspection departments, financial institutions and firms, while allowing the system to operate in normal mode.     

A numerical solution of the constrained weighted energy problem

A numerical algorithm is presented to solve the constrained weighted energy problem from potential theory. As one of the possible applications of this algorithm, we study the convergence properties of the rational Lanczos iteration method for the symmetric eigenvalue problem. The constrained weighted energy problem characterizes the region containing those eigenvalues that are well approximated by the Ritz values. The region depends on the distribution of the eigenvalues, on the distribution of the poles, and on the ratio between the size of the matrix and the number of iterations. Our algorithm gives the possibility of finding the boundary of this region in an effective way.We give numerical examples for different distributions of poles and eigenvalues and compare the results of our algorithm with the convergence behavior of the explicitly performed rational Lanczos algorithm.     

Special issue: In honour of Ward Whitt reaching 75

We introduce the first class of perfect sampling algorithms for the steady-state distribution of multi-server queues with general interarrival time and service time distributions. Our algorithm is built on the classical dominated coupling from the past protocol. In particular, we use a coupled multi-server vacation system as the upper bound process and develop an algorithm to simulate the vacation system backward in time from stationarity at time zero. The algorithm has finite expected termination time with mild moment assumptions on the interarrival time and service time distributions.     

Two-agent single-machine scheduling problems under increasing linear deterioration

A new scheduling model in which both two-agent and increasing linear deterioration exist simultaneously is investigated in this paper. The processing time of a job is defined as an increasing linear function of its starting time. Two agents compete to perform their respective jobs on a common single machine and each agent has his own criterion to optimize. We introduce an increasing linear deterioration model into the two-agent single-machine scheduling, where the goal is to minimize the objective function of the first agent with the restriction that the objective function of the second agent cannot exceed a given upper bound. We study two scheduling problems with the different combinations of two agents’ objective functions: makespan, maximum lateness, maximum cost and total completion time. We propose the optimal properties and present the optimal polynomial time algorithms to solve the scheduling problems, respectively.     

Time Discretisation and Rate of Convergence for the Optimal Control of Continuous-Time Stochastic Systems with Delay

We study a semi-discretisation scheme for stochastic optimal control problems whose dynamics are given by controlled stochastic delay (or functional) differential equations with bounded memory. Performance is measured in terms of expected costs. By discretising time in two steps, we construct a sequence of approximating finite-dimensional Markovian optimal control problems in discrete time. The corresponding value functions converge to the value function of the original problem, and we derive an upper bound on the discretisation error or, equivalently, a worst-case estimate for the rate of convergence.