Games in Multi-Agent Dynamic Systems: Decision-Making with Compressed Information

Abstract

The model of multi-agent dynamic systems has a wide range of applications in numerous socioeconomic and engineering settings including spectrum markets, e-commerce, transportation networks, power systems, among many others. In this model, each agent takes actions over time to interact with the underlying system as well as each other in order to achieve their respective objectives. In many applications of this model, agents have access to a huge amount of information that increases over time. Determining solutions of such multi-agent dynamic games can be complicated due to the huge domains of strategies. Meanwhile, agents have restrictions on their computational power, communication capability, and time to make a decision, which prevent them from implementing complicated strategies. Therefore, it is important to identify suitable compression schemes so that each agent can make decisions based on a compressed version of their information instead of the full information at equilibrium. However, compression of information can be a double-edged sword. On one hand, it is appealing to practitioners as it allows agents to implement strategies efficiently. On the other hand, it can result in loss of some or all equilibrium outcomes. In this thesis, we design and analyze information compression schemes for multi-agent dynamic games. We aim to (i) enhance our understanding on the types of compression schemes that preserve some or all equilibrium outcomes, and (ii) identify compression schemes in specific game models. Our results highlight the tension among information compression, preservation of equilibrium outcomes, and applicability of sequential decomposition algorithms to find compression based equilibrium.

To achieve our first goal, we provide sufficient conditions for information compression schemes to be viable in general dynamic games. We provide two definitions of information states which guarantee the existence of compression-based equilibria and the preservation of the set of equilibrium payoffs respectively. Our results extend the theory of information states in control theory literature to games. We also investigate a class of compression schemes where the common information of all agents are compressed into beliefs. Through a few examples, we show that such compression schemes can result in non-existence of compression-based equilibria. We also show that even when such equilibria exist, they may not be obtained through sequential decomposition procedures.

To achieve our second goal, we analyze two special game models. First, we analyze a stylized model of stochastic dynamic games among teams, where team members communicate with each other about their information with a delay of $d$. In this model, we identified two compression schemes: The first scheme compresses only the private information, while the second scheme compresses both the common and private information. We show that the first scheme preserves the set of Nash equilibria payoffs, while the second scheme cannot guarantee the existence of equilibria. For the second scheme, we developed a sequential decomposition procedure whose solution (if it exists) is a compression based equilibrium. We identify some instances where this procedure is guaranteed to have at least one solution. Secondly, we analyze an information disclosure game among two players, where the principal sequentially disclose information about the state of a dynamic system to the receiver. We identify compression schemes for both players to play at equilibrium. We develop a sequential decomposition procedure to find such equilibria. We show that the sequential decomposition procedure is guaranteed to have at least one solution.