PhD thesis defense to be held on December 16, 2022, at 12:00 (Lab premises 2.1.42, Old ECE building)

Picture Credit: Athanasios-Rafail Lagos

Thesis title: Game Theory and Dynamic Mechanisms on Graphs

Abstract: In this thesis, game theoretic and control methods have been applied in problems arising in decentralised networked systems. Three applications have been considered. The first deals with opinion dynamics and manipulation in social networks. The second is related to the spontaneous response of a population to an epidemic outbreak through social distancing. The third introduces a stochastic consensus protocol for finite-time coordination of agents with high-order dynamics. In these three applications, the structure of the system is interconnected, the agents possess some kind of intelligence and act in a decentralised way. So, either game situations arise and the equilibria are studied or decentralised control protocols are necessary to achieve some collective goal.

In the first application, a social choice procedure is modeled as a Nash game among the agents. The agents are communicating with each other through a communication network e.g., a social network, modeled by an undirected graph and their opinions follow a dynamic rule modelling conformity. The agents' criteria for this game are describing a trade off between self-consistent and manipulative behaviors. Their best response strategies are resulting in a dynamic rule for their actions. The stability properties of these dynamics are studied. In the case of instability, which arises when the agents are highly manipulative, the stabilization of these dynamics through the design of the network topology is formulated as a constrained integer programming problem. The constraints have the form of a Bilinear Matrix Inequality (BMI), which is known to result in a nonconvex feasible set in the general case. To deal with this problem a genetic algorithm, which uses a Linear Matrix Inequality (LMI) solver during the selection procedure, is designed.

The second application deals with the choice of a population to apply social distancing, which is modeled as a Nash game where the agents determine their social interactions. The interconnections among the agents are modeled by a network. The information available to the agents plays a crucial role. Two information patterns are examined, the case that the agents know exactly the health states of their neighbors and the case they have only statistical information for the global prevalence of the epidemic. The agents are considered to be myopic, and thus, the Nash equilibria of static games for each day are studied. The Nash equilibria are characterized and algorithms are introduced to compute them. Moreover, the effects of the network structure, the virus transmissibility, the number of vulnerable agents, the health care system capacity and the information quality (fake news) are examined through simulations.

In the third application, a novel stochastic minimum-maximum consensus protocol is introduced and analyzed. The stochastic mixing and the low computational effort make this protocol well suited for secure consensus in cyber-physical systems, composed by autonomous agents with limited resources. It is proven that the protocol converges almost-surely in finite time. Furthermore, the application of the stochastic consensus protocol coupled with a finite-time control law on a distributed system of agents with high-order dynamics is considered and it is proven that the agents' states converge in finite time. Finally, simulations showing the efficiency of this decentralised finite-time control scheme on double-integrator agents are presented.

Supervisor: Professor Emeritus G. Papavassilopoulos

PhD Student: Athanasios-Rafail Lagos