Dynamic sequential decision problems with asymmetric information: some existence results

Gupta, Abhishek

Permalink

https://hdl.handle.net/2142/50522 Copy

Description

Title

Dynamic sequential decision problems with asymmetric information: some existence results

Author(s)

Gupta, Abhishek

Issue Date

2014-09-16

Director of Research (if dissertation) or Advisor (if thesis)

• Basar, Tamer
• Langbort, Cedric

Doctoral Committee Chair(s)

• Basar, Tamer
• Langbort, Cedric

Committee Member(s)

• Raginsky, Maxim
• Namachchivaya, N. Sri
• Teneketzis, Demosthenis

Department of Study

Aerospace Engineering

Discipline

Aerospace Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Game theory
• Team theory
• Optimization with information constraints
• Nash equilibrium
• Decision problems
• Control theory

Abstract

The thesis focuses on a few fundamental problems in multi-player dynamic sequential decision problems -- games and teams -- with asymmetric information. It is divided into two parts and addresses six broad theoretical problems. In the first part of the thesis, the focus is on dynamic games, in which the decision makers do not observe the same set of random variables at every time step of the play. In the second part of the thesis, the focus is on static and dynamic teams in which the decision makers may or may not share their observations with each other. This part of the thesis partially resolves a long-standing open question in stochastic control theory, which is to establish the existence of team-optimal solutions in teams with non-classical information structures. To solve all problems, a two-step solution approach is adopted; the first step involves identifying an equivalent decision problem with expanded state, observation, and action spaces of the decision makers, and the second step consists of solving this equivalent problem and then projecting the solution back to the original problem. Information asymmetry among decision makers naturally arises in numerous social, economic, and engineering settings. An auction is an example of a game of asymmetric information. The value of the object to a bidder is known only to that bidder, but not known to other bidders. However, the decisions of all the bidders affect the outcome of the auction. A communication system comprising an encoder and a decoder is a team with asymmetric information. The encoder wants to communicate a randomly generated message to the decoder via a noisy channel. The decision makers here are the encoder and the decoder, who decide, respectively, on the encoding and decoding strategies to minimize the expected distortion between the original and the decoded messages subject to certain communication or energy constraints. Despite ubiquity of scenarios in which information asymmetry appears, very few results exist on the existence of suitable solutions in such problems. The purpose of this thesis is to identify sufficiently general conditions under which suitable solutions exist in dynamic stochastic games and teams with asymmetric information. The first part of the thesis studies three problems pertinent to games with asymmetric information. In the first problem, a refinement concept for Nash equilibrium is presented, called common information based Markov perfect equilibrium (CIMPE), for a class of two-player dynamic linear-Gaussian (LG) games of asymmetric information satisfying two general conditions. The most appealing property of CIMPE is that it can be computed using a backward induction algorithm. Further, if the cost functions of the decision makers are quadratic in their arguments (called LQG games) and satisfy certain conditions, then the game is proven to admit a unique CIMPE, which can be computed by solving for the unknowns in a succession of linear equations. A two-step solution approach is adopted to prove the results and devise the algorithm. In the first step, a two-player virtual game of symmetric and perfect information is constructed. It is shown that every Nash equilibrium of the original LQG game can be mapped to a Nash equilibrium of the virtual game and vice-versa. Thereafter, in the second step, a Markov perfect equilibrium of the virtual game is used to construct a Nash equilibrium of the original LQG game. The algorithm to compute a Markov perfect equilibrium of the virtual game is used to devise an algorithm to compute a CIMPE for the original game. An example game, which admits a unique CIMPE but multiple Nash equilibria, is also presented to illustrate that there may be several other Nash equilibria in a game of asymmetric information, that cannot be computed using the proposed scheme. The second problem pertains to a finite-horizon dynamic incentive design problem, in which the decision makers have asymmetric information at every stage of the game. A central agency designs incentives dynamically, so that decision makers behave in a desired manner at every stage of the game. The goal of the central agency is to optimize its own utility function, which may depend on the utility functions of all the decision makers. We introduce a new equilibrium concept for dynamic incentive design games, which we call {\it common information based incentive scheme}. We show that under certain assumptions, the central agency is able to design a common information based incentive scheme which forces decision makers to behave according to the desired strategies at all time steps. In the third problem, the refinement concept (CIMPE) is extended to a multi-player dynamic game in which decision makers have resource constraints across time. A similar two-step approach is used as in the first problem to show the existence of a Nash equilibrium under certain assumptions on the game. A key step in the proof is to show that the amount of resource used by decision makers up to a time step into the game forms a set of states of the game, which is then augmented with other states of the game to compute a Nash equilibrium. The second part of the thesis resolves three issues pertaining to teams with asymmetric information. The first problem of this second part, and also the fourth problem of the thesis, considers a static team of asymmetric information, in which the decision makers do not share their observations with each other. Such an information pattern is referred to as the no-observation sharing information structure. Under certain assumptions on the observation channels of the decision makers, existence of a team-optimal solution is established. First, the strategy spaces of the decision makers are expanded to behavioral (randomized) strategy spaces. A challenge is to ensure that the limiting strategy of a convergent sequence of behavioral strategies of a decision maker under a certain topology does not depend on the random variables that are not acquired by the decision maker. Appropriate assumptions on the joint measures over state and observations of the decision makers are made to overcome the challenge. Thereafter, tools from probability theory and general topology are used to establish the existence result. In the fifth problem of the thesis, dynamic teams with no-observation sharing information structures are considered. The proof techniques developed for static teams are used sequentially in a specific manner to prove the existence of optimal solutions in a large class of dynamic teams with no-observation sharing information structures. Consequently, a large class of dynamic linear-quadratic-Gaussian (LQG) teams with no-observation sharing information structures and cost functions with a specific structure is proven to admit optimal solutions. In the sixth and final problem of the thesis, the results for teams with no-observation sharing information structure are used to establish the existence of team-optimal solutions in a class of teams with observation sharing information structures. Consequently, several teams, with or without observation sharing information structures, are shown to admit optimal solutions, for which proofs of existence did not exist previously. Furthermore, optimal encoding-decoding policies are shown to exist in a large class of multivariate Gaussian channels, where existence of optimal policies were known only for a few cases and under stringent assumptions, and the proof relied on certain information-theoretic techniques.

Graduation Semester

2014-08

Permalink

http://hdl.handle.net/2142/50522

Copyright and License Information

Copyright 2014 Abhishek Gupta

Owning Collections