Static Agreement

• The agreement set is defined as

  That is it is the set of fixed points in the dynamics — the set where all units “agree” on their states

• The rate of change of each unit’s state is assumed to be governed by the sum of its relative states with respect to a subset of other neighboring units. That is if is a unit with neighborhood , then

  The agreement dynamics can also be represented using the Laplacian of the information network and assuming

  • If , , then we can represent the above as

Static Agreement over Undirected Graphs §

• Consider the eigendecomposition of . We have

  Which can be decomposed along each eigen-axis as follows

• (Mesbahi 3.4) Let be a connected graph. Then the undirected agreement protocol converges to an agreement set with a rate of convergence proportional to .

• We define the centroid as

  The centroid is a constant of motion for the agreement dynamics

• The state trajectory generated by the agreement protocol converges to the projection of its initial state onto the agreement subspace. That is

• (Mesbahi 3.5) A necessary and sufficient condition for the agreement protocol to converge to the agreement subspace from an arbitrary initial condition is that the underlying graph contains a spanning tree.

  • Intuition: Convergence is governed by which implies that the graph is connected, that there is a spanning tree
  • Consensus is possible as long as a graph is connected

Static Agreement over Directed Graphs §

• (Mesbahi 3.12) For a digraph containing an arborescence, the state trajectory satisfies

  Where and are the right and left eigenvectors associated with the zero eigenvalue of normalized such that .

  Thus for all initial conditions if and only if contains an arborescence.

• (Mesbahi 3.13) Let be the left eigenvector of the digraph in-degree Laplacian associated with its zero eigenvalue. Then is invariant under the agreement dynamics.

• (Mesbahi 3.17) The agreement protocol over a digraph reaches the average consensus for every initial condition if and only if it is weakly connected and balanced.

• The progress of the agreement dynamics can be monitored using discrete time intervals using a markov process defined by

  • (Mesbahi 3.18) For all digraphs and sampling intervals we have
    Thus is a stochastic matrix whose right and left eigenvectors are those of associated with
  • (Mesbahi 3.19) The state of the nodes during the evolution of the agreement protocol over a digraph at any time instance is a convex combination of the values of all nodes at the previous instance.
  • (Mesbahi 3.21) The behavior of the agreement dynamics is characterized by its action on the unit simplex.

• (Mesbahi 3.26) Factorization Lemma for Agreement Dynamics.

  Let be a finite set of graphs. Let be the states of the agreement protocols initialized from .

  Then the state trajectory generated by the agreement protocol of the Cartesian Product

  is

  Initialized from

  • Intuition: The proof follows from direct computation.

• (Mesbahi 3.27) The agreement dynamics over a composite graph can always be represented as a Kronecker product of agreement dynamics over its prime factors. Such a factorization is unique up to reordering.

Links §

• Graph Theoretic Methods in Multiagent Networks by Mesbahi and Egerstedt