Files in this item
Files  Description  Format 

application/pdf Abhishek_Gupta.pdf (2MB)  (no description provided) 
Description
Title:  Dynamic sequential decision problems with asymmetric information: some existence results 
Author(s):  Gupta, Abhishek 
Director of Research:  Basar, Tamer; Langbort, Cedric 
Doctoral Committee Chair(s):  Basar, Tamer; Langbort, Cedric 
Doctoral Committee Member(s):  Raginsky, Maxim; Namachchivaya, N. Sri; Teneketzis, Demosthenis 
Department / Program:  Aerospace Engineering 
Discipline:  Aerospace Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(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 multiplayer 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 longstanding open question in stochastic control theory, which is to establish the existence of teamoptimal solutions in teams with nonclassical information structures. To solve all problems, a twostep 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 twoplayer dynamic linearGaussian (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 twostep solution approach is adopted to prove the results and devise the algorithm. In the first step, a twoplayer 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 viceversa. 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 finitehorizon 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 multiplayer dynamic game in which decision makers have resource constraints across time. A similar twostep 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 noobservation sharing information structure. Under certain assumptions on the observation channels of the decision makers, existence of a teamoptimal 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 noobservation 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 noobservation sharing information structures. Consequently, a large class of dynamic linearquadraticGaussian (LQG) teams with noobservation 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 noobservation sharing information structure are used to establish the existence of teamoptimal 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 encodingdecoding 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 informationtheoretic techniques. 
Issue Date:  20140916 
URI:  http://hdl.handle.net/2142/50522 
Rights Information:  Copyright 2014 Abhishek Gupta 
Date Available in IDEALS:  20140916 
Date Deposited:  201408 
This item appears in the following Collection(s)

Dissertations and Theses  Aerospace Engineering

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois