We consider two well-known mathematical representations of informational structures in game theory. The first is based on the set of historical sequences of information encountered in the game while ...the second is given by the informational digraph of the game. We show that while the latter can always be embedded into the former under some mild technical condition, the converse does not hold in general. We give a necessary and sufficient condition for an informational digraph to be equivalent to a sequence theoretic informational structure and discuss the relevance of this result to game theory.
A general model of decentralized stochastic control called partial history sharing information structure is presented. In this model, at each step the controllers share part of their observation and ...control history with each other. This general model subsumes several existing models of information sharing as special cases. Based on the information commonly known to all the controllers, the decentralized problem is reformulated as an equivalent centralized problem from the perspective of a coordinator. The coordinator knows the common information and selects prescriptions that map each controller's local information to its control actions. The optimal control problem at the coordinator is shown to be a partially observable Markov decision process (POMDP) which is solved using techniques from Markov decision theory. This approach provides 1) structural results for optimal strategies and 2) a dynamic program for obtaining optimal strategies for all controllers in the original decentralized problem. Thus, this approach unifies the various ad-hoc approaches taken in the literature. In addition, the structural results on optimal control strategies obtained by the proposed approach cannot be obtained by the existing generic approach (the person-by-person approach) for obtaining structural results in decentralized problems; and the dynamic program obtained by the proposed approach is simpler than that obtained by the existing generic approach (the designer's approach) for obtaining dynamic programs in decentralized problems.
We describe a convex programming approach to the calculation of lower bounds on the minimum cost of constrained decentralized control problems with nonclassical information structures. The class of ...problems that we consider entail the decentralized output feedback control of a linear time-varying system over a finite horizon, subject to polyhedral constraints on the state and input trajectories, and sparsity constraints on the controller's information structure. As the determination of optimal control policies for such systems is known to be computationally intractable in general, considerable effort has been made in the literature to identify efficiently computable, albeit suboptimal, feasible control policies. The construction of computationally tractable bounds on their suboptimality is the primary motivation for the techniques developed in this note. Specifically, given a decentralized control problem with nonclassical information, we characterize an expansion of the given information structure, which ensures its partial nestedness, while maximizing the optimal value of the resulting decentralized control problem under the expanded information structure. The resulting decentralized control problem is cast as an infinite-dimensional convex program, which is further relaxed via a partial dualization and a restriction to affine dual control policies. The resulting problem is a finite-dimensional conic program whose optimal value is a provable lower bound on the minimum cost of the original constrained decentralized control problem.
In this article, we consider sequential dynamic team decision problems with nonclassical information structures. First, we address the problem from the point of view of a "manager" who seeks to ...derive the optimal strategy of the team in a centralized process. We derive structural results that yield an information state for the team, which does not depend on the control strategy, and thus, it can lead to a dynamic programming decomposition where the optimization problem is over the space of the team's decisions. We, then, derive structural results for each team member that yield an information state which does not depend on their control strategy, and thus, it can lead to a dynamic programming decomposition where the optimization problem for each team member is over the space of their decisions. Finally, we show that the solution of each team member is the same as the one derived by the manager. We present an illustrative example of a dynamic team with a delayed sharing information structure.
Multi-agent learning (MAL) studies how agents learn to behave optimally and adaptively from their experience when interacting with other agents in dynamic environments. The outcome of a MAL process ...is jointly determined by all agents’ decision-making. Hence, each agent needs to think strategically about others’ sequential moves, when planning future actions. The strategic interactions among agents makes MAL go beyond the direct extension of single-agent learning to multiple agents. With the strategic thinking, each agent aims to build a subjective model of others decision-making using its observations. Such modeling is directly influenced by agents’ perception during the learning process, which is called the information structure of the agent’s learning. As it determines the input to MAL processes, information structures play a significant role in the learning mechanisms of the agents. This review creates a taxonomy of MAL and establishes a unified and systematic way to understand MAL from the perspective of information structures. We define three fundamental components of MAL: the information structure (i.e., what the agent can observe), the belief generation (i.e., how the agent forms a belief about others based on the observations), as well as the policy generation (i.e., how the agent generates its policy based on its belief). In addition, this taxonomy enables the classification of a wide range of state-of-the-art algorithms into four categories based on the belief-generation mechanisms of the opponents, including stationary, conjectured, calibrated, and sophisticated opponents. We introduce Value of Information (VoI) as a metric to quantify the impact of different information structures on MAL. Finally, we discuss the strengths and limitations of algorithms from different categories and point to promising avenues of future research.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Many emerging problems involve teams of agents taking part in a game. Such problems require a stochastic analysis with regard to the correlation structures among the agents belonging to a given team. ...In the context of standard Borel state, measurement and action spaces (thus, including real vector spaces and finite spaces), this paper makes the following contributions for two teams of finitely many agents taking part in a zero-sum game: (i) An existence result will be presented for saddle-point equilibria in zero-sum games involving teams against teams when common randomness is assumed to be available in each team with an analysis on conditions for compactness of strategic team measures to be presented. (ii) Blackwell’s ordering of information structures is generalized to n-player teams with standard Borel spaces, where correlated garbling of information structures is introduced as a key attribute; (iii) building on this result Blackwell’s ordering of information structures is established for team-against-team zero-sum game problems. (iv) Finally, continuity of the equilibrium value of team-against-team zero-sum game problems in the space of information structures under total variation is established.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In this article, we investigate the optimal linear quadratic control problem for stochastic systems with multiple controllers, where each controller has its own information structure, which differs ...from each other. More specifically, we consider the optimal control problem for systems with multiple controllers of different delayed state information. First, the necessary and sufficient solvability conditions are given in terms of forward and backward difference equations (FBSDEs). Further, an innovation method is proposed to decouple the FBSDEs, and the optimal control strategies are derived based on a given nonsymmetric Riccati equation. Finally, a numerical example is provided to show the effectiveness of the main results. It is stressed that the proposed methods and results can be seen as an important addition to the optimal control theory with asymmetric-information-structure controllers.
•Multimodal prominence markers are analyzed in a corpus of Swedish news reading.•Interaction is found between eyebrow and head movements and focal pitch accents.•Head and eyebrow movements differ in ...patterns of occurrence and usage.•Combinations of markers are subject to variation reflecting speaker expressiveness.•Relationship to information structure and common ground is discussed.
Facial beat gestures align with pitch accents in speech, functioning as visual prominence markers. However, it is not yet well understood whether and how gestures and pitch accents might be combined to create different types of multimodal prominence, and how specifically visual prominence cues are used in spoken communication. In this study, we explore the use and possible interaction of eyebrow (EB) and head (HB) beats with so-called focal pitch accents (FA) in a corpus of 31 brief news readings from Swedish television (four news anchors, 986 words in total), focusing on effects of position in text, information structure as well as speaker expressivity. Results reveal an inventory of four primary (combinations of) prominence markers in the corpus: FA+HB+EB, FA+HB, FA only (i.e., no gesture), and HB only, implying that eyebrow beats tend to occur only in combination with the other two markers. In addition, head beats occur significantly more frequently in the second than in the first part of a news reading. A functional analysis of the data suggests that the distribution of head beats might to some degree be governed by information structure, as the text-initial clause often defines a common ground or presents the theme of the news story. In the rheme part of the news story, FA, HB, and FA+HB are all common prominence markers. The choice between them is subject to variation which we suggest might represent a degree of freedom for the speaker to use the markers expressively. A second main observation concerns eyebrow beats, which seem to be used mainly as a kind of intensification marker for highlighting not only contrast, but also value, magnitude, or emotionally loaded words; it is applicable in any position in a text. We thus observe largely different patterns of occurrence and usage of head beats on the one hand and eyebrow beats on the other, suggesting that the two represent two separate modalities of visual prominence cuing.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
This paper generalizes the concept of Bayes correlated equilibrium (Bergemann and Morris, 2016) to multi-stage games. We apply our characterization results to a number of illustrative examples and ...applications.
Full text
Available for:
BFBNIB, CEKLJ, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
•We provide a new characterization of Blackwell's order for two subsets of stochastic information structures with meaningful economic interpretations.•One doubly stochastic information structure is ...strictly more informative than another if and only if the convex hull of the former and its permutations strictly contains that of the latter and its permutations.•We show that Blackwell's order is complete for the subset of stochastic information structures of the type αP+(1−α)E, where P is any information structure, E is a null-information structure, and 0<α≤1.
We provide a new characterization of Blackwell's order for two subsets of stochastic information structures with meaningful economic interpretations. First, we show that one doubly stochastic information structure is strictly more informative than another, if and only if the convex hull of the former and all of its permutations, which are equally informative, contains that of the latter. We further present another subset of stochastic information structures for which we show that Blackwell's order is complete.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP