On January 30, 2023, Jun.-Prof. Dr. Gleb Polevoy from the Paderborn University will give a SFB-lecture about "Changing Equilibria Using Control Sets" in the context of the SFB 901.
Location: Room O4.267
Abstract:
Many interactions result in a socially suboptimal outcome, and we want the situation to move to a socially optimal outcome. When having loyal players or being able to bribe some players, we let a selected group of the loyal participants act in a way that will motivate the rest of the players to act accordingly to the socially optimal situation we aim at. Formally, we consider two equilibria of a game, and starting in the undesired equilibrium, we ask which subset of the players can adopt strategies that will make acting according to the desired equilibrium a best response for the other players. We call such a subset a control set and study its possible sizes and structures. We prove that, while the problem of finding such a set is very hard, we can still solve it in important special cases.
Having dealt with the general case, we shift our focus to the class of coordination games on graphs, which effectively capture the dynamics of social influence. These games are expressive, but amenable to refined theoretical analysis. We delve into the properties of control sets in these games, and although the problem of finding a control set remains \NP-hard, we manage to solve it algorithmically in key scenarios.