Distributed and Collaborative Systems of Agents

• Applicant: Professorin Dr. Petra Berenbrink
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 411362735

We will study systems that are composed of a finite number of agents or individuals, each holding an opinion, or being in a state, as a variable. A set of local rules governs how agents may change their state after interactions with their peers. Each individual has a limited number of peers with whom it interacts (``neighbors'', ``friends''), and this number is usually assumed to be negligible compared with the total number of individuals. These collaborative systems are often modeled by graphs or social networks. The objective is to reach a common goal, e.g., agreeing on an opinion or selecting a leader. The research suggested here focuses on studying the long-term behavior of such systems in terms of stable states such as, e.g., stationary distributions or Nash equilibria. Compared to the previous proposal, we will however also consider systems that do not necessarily reach a stable state but only so-called \emph{metastable} states instead. In physics a metastable state denotes an intermediate energetic state other than the system's state of minimal energy. A well-known example is a ball resting in a hollow on a slope. If the ball is only slightly pushed, it will settle back into its hollow, but a stronger push may start the ball rolling down the slope. For us, metastable states are simply states of a dynamics that are reached quickly, and the dynamics remains in them for a long time. In most cases our specific interest lies in analyzing the rate of convergence to some sort of steady state, equilibrium, or metastable state.

• DFG Programme: Research Units
• Subproject of: FOR 2975: Algorithms, Dynamics, and Information Flow in Networks