Strategic Interactions and Incentive Mechanisms on Multi-scale Networks

Abstract

The strategic interactions among a large number of interdependent agents are commonly modeled as network games. The research in network games has seen significant advances over the last decade and the network game framework allows us to model and solve real-world problems such as the provisioning of public goods, decision-making in cyber-physical systems, and the understanding of shock propagation in financial markets. In this thesis, we are interested in games on networks that enjoy various structural properties that arise naturally in many applications, such as groups, communities, and multi-relational interdependence, and seek to explore such structural properties in the analysis of these games. These properties often result in a multi-scale structure, in which agents can be grouped into larger communities/units, which can then be further grouped, and so on. These communities can be physical or logical, depending on what the graphical connectivity represents. We aim to develop analytical and algorithmic tools for studying this type of network game, with a particular interest in equilibrium analysis and the design of intervention and incentive mechanisms.

On the equilibrium analysis and computation front, the novelty of our work lies in the utilization of structural properties. In particular, we utilize the similarity among community members and propose structured conditions that significantly reduce the verification complexity of equilibrium properties such as existence, uniqueness, and stability. Similarly, for computation, we develop several algorithmic approaches that greatly reduce the computational complexity by leveraging the sparsity in a multi-scale structure, and we derive sufficient conditions for the convergence of these algorithms.

On the mechanism design and intervention front, we develop a novel multi-scale intervention model where agents form local groups and each group has a local planner. The planners are non-cooperative and their decisions are interdependent through the connections of the agents. We characterize the Stackelberg equilibrium of the system and study how the equilibrium efficiency is influenced by the network structure and the budget allocation of the planners. We also study the mechanism design and intervention using strategic classification and regression framework, where agents’ actions include not only (honest) effort but also (dishonest) cheating, both may help the agent achieve the same decision outcome but only honest effort improves the planner’s objective. We establish Stackelberg game models where the planner moves first by publishing and committing to an incentive mechanism that includes a decision rule (algorithm) as well as a subsidy mechanism, followed by the agents’ simultaneously best response. We model the agents’ interdependence in such a game and show how the subsidy influences the agents’ decision making and the resulting Stackelberg equilibria.