We consider a scenario in which leaders are required to recruit teams of followers. Each leader cannot recruit all followers, but interaction is constrained according to a bipartite network. The objective for each leader is to reach a state of local stability in which it controls a team whose size is equal to a given constraint. We focus on distributed strategies, in which agents have only local information of the network topology and propose a distributed algorithm in which leaders and followers act according to simple local rules. The performance of the algorithm is analyzed with respect to the convergence to a stable solution. Our results are as follows. For any network, the proposed algorithm is shown to converge to an approximate stable solution in polynomial time, namely the leaders quickly form teams in which the total number of additional followers required to satisfy all team size constraints is an arbitrarily small fraction of the entire population. In contrast, for general graphs there can be an exponential time gap between convergence to an approximate solution and to a stable solution.
Finally, related to our work is also the research on social exchange networks @cite_31 @cite_9 , that considers a networked scenario in which each edge is associated to an economic value, nodes have to come to an agreement on how to share these values, and each agent can only finalize a single mutual exchange with a single neighbor. Recently, @cite_35 proposed a distributed algorithm that reaches approximate stability in linear time. However, we consider a different setup since we allow leaders to build teams of multiple followers.
@cite_9 @cite_31 @cite_35
1949110650 2090459604 2084044206 2135097535
We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 3-majority dynamics: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let k be the number of valid opinions. We show that, if k ≤ nα, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to o([EQUATION]) nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 2 only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for |Σ| > 2. One of the main reasons of the recent success of peer to peer (P2P)file sharing systems such as BitTorrent is their built-in tit-for-tat mechanism. In this paper, we model the bandwidth allocation in a P2P system as an exchange economy and study a tit-for-tat dynamics, namely the proportional response dynamics, in this economy. In aproportional response dynamics each player distributes its good to its neighbors proportional to the utility it received from them in thelast period. We show that this dynamics not only converges but converges to a market equilibrium, a standard economic characterization of efficient exchanges in a competitive market. In addition, for some classes of utility functions we consider, it converges much faster than the classical tat process and any existingalgorithms for computing market equilibria. As a part of our proof we study the double normalization of a matrix, an operation that linearly scales the rows of a matrix sothat each row sums to a prescribed positive number, followed by a similar scaling of the columns. We show that the iterative double normalization process of any non-negative matrix always converges. This complements the previous studies in matrix scaling that has focused on the convergence condition of the process when the row and column normalizations are considered as separate steps. We study the average consensus problem of multi-agent systems for general network topologies with unidirectional information flow. We propose two linear distributed algorithms, deterministic and gossip, respectively for the cases where the inter-agent communication is synchronous and asynchronous. In both cases, the developed algorithms guarantee state averaging on arbitrary strongly connected digraphs; in particular, this graphical condition does not require that the network be balanced or symmetric, thereby extending previous results in the literature. The key novelty of our approach is to augment an additional variable for each agent, called "surplus", whose function is to locally record individual state updates. For convergence analysis, we employ graph-theoretic and nonnegative matrix tools, plus the eigenvalue perturbation theory playing a crucial role. We consider stationary consensus protocols for networks of dynamic agents with fixed topologies. At each time instant, each agent knows only its and its neighbors’ state, but must reach consensus on a group decision value that is function of all the agents’ initial state. We show that the agents can reach consensus if the value of such a function is time-invariant when computed over the agents’ state trajectories. We use this basic result to introduce a non-linear protocol design rule allowing consensus on a quite general set of values. Such a set includes, e.g., any generalized mean of order p of the agents’ initial states. As a second contribution we show that our protocol design is the solution of individual optimizations performed by the agents. This notion suggests a game theoretic interpretation of consensus problems as mechanism design problems. Under this perspective a supervisor entails the agents to reach a consensus by imposing individual objectives. We prove that such objectives can be chosen so that rational agents have a unique optimal protocol, and asymptotically reach consensus on a desired group decision value. We use a Lyapunov approach to prove that the asymptotical consensus can be reached when the communication links between nearby agents define a time-invariant undirected network. Finally we perform a simulation study concerning the vertical alignment maneuver of a team of unmanned air vehicles.