On partial order characterizations of information structures

The degree of concurrency possible in an informationally decentralized nons equential 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 orderin g 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 characteriza tion exists and we identify a sufficient (but not necessary) condition for existence. The condition has design implications that are important and int uitive and are discussed in the paper. Our results demonstrate that partial -order-based descriptions of concurrency, sometimes used in computer scienc e, are not always correct.