On Partial Order Characterizations of Information Structures

Abstract

The degree of concurrency possible in an informationally decentralized nonsequential system is determined by the precedence constraints imposed by the system's information structure on its controlled and uncontrolled inputs. One approach to characterizing these constraints is to attempt to associate each realization of the system's inputs with the strongest partial ordering of the system's decision-making agents that is consistent with the system's information structure. If such an association is possible, it leads to a partial order characterization of the corresponding information structure. In this paper we show that, in general, no such partial order characterization exists and we identify a sufficient (but not necessary) condition for existence. The condition has design implications that are important and intuitive and are discussed in the paper. Our results demonstrate that partial-order-based descriptions of concurrency, sometimes used in computer science, are not always correct.