Overview
This work focuses on the time structure in infinite extensive games. It extends existing graph-theoretic characterizations of time-structurable extensive games from finite informational digraphs to those involving countable and continuum digraphs. These digraphs are constructed upon continuum rooted real trees. A central concept introduced is the symmetric class quotient poset of information sets, identified as the canonical object that an external clock must order. The research develops a theory of transitive reduction specifically for these quotients and establishes conditions for the existence and uniqueness of this reduction, contingent upon an interval finiteness condition. Furthermore, under specified topological regularity assumptions, such as closed reachability classes, order density, and sigma compactness, the study provides necessary and sufficient conditions for the assignment of real-valued time labelings. It also details the construction of measurable selection procedures applicable in Polish spaces. The work includes constructive algorithms and an illustrative example from differential game theory to demonstrate applications and computational implications.
Research Context
The research builds upon prior graph theoretic characterizations developed for finite informational digraphs in the context of time-structurable extensive games. This extension is significant as it addresses scenarios where the information sets are more complex, moving beyond finite structures to encompass countable and continuum digraphs. These extended digraphs are specifically built on continuum rooted real trees, which intrinsically introduces complexities not present in finite settings. The core challenge addressed is how to impose a meaningful time structure on such infinite games, essentially by identifying an object that an external clock can consistently order.
Approach
- Extension of Graph-Theoretic Characterizations: The research extends existing graph-theoretic tools from finite informational digraphs to more complex countable and continuum digraphs.
- Foundation on Continuum Rooted Real Trees: The extended digraphs are constructed specifically on continuum rooted real trees, providing a specific topological and structural basis for the analysis.
- Introduction of Symmetric Class Quotient Poset: The symmetric class quotient poset of information sets is introduced as the canonical entity requiring ordering by an external clock. This object serves as the central focus for developing a consistent time structure.
- Development of Transitive Reduction Theory: A specific theory for transitive reduction is developed for these identified quotients. This theory is crucial for simplifying and understanding the underlying order relations.
- Conditions for Existence and Uniqueness: The existence and uniqueness of the transitive reduction are proven under an interval finiteness condition, specifying the structural properties required for such a reduction to be well-defined.
- Topological Regularity Assumptions: The study invokes natural topological regularity assumptions. These include closed reachability classes, which imply certain continuity in the game's states; order density, ensuring a sufficiently rich ordering; and sigma compactness, a measure-theoretic property often associated with countable unions of compact sets.
- Necessary and Sufficient Conditions for Time Labeling: Under these topological regularity assumptions, the research establishes necessary and sufficient conditions that permit the assignment of real-valued time labelings to the game's events.
- Construction of Measurable Selection Procedures: The work outlines how to construct measurable selection procedures within Polish spaces, which are complete, separable metric spaces, relevant for ensuring well-behaved choices in stochastic or continuous settings.
- Constructive Algorithms: The research provides specific algorithms for implementing the derived concepts and procedures.
- Differential Game Example: An example drawn from differential game theory is used to illustrate the practical applications and computational implications of the developed framework.
Findings
- Graph theoretic characterizations of time structurable extensive games, previously applied to finite informational digraphs, can be extended to countable and continuum digraphs built on continuum rooted real trees.
- The symmetric class quotient poset of information sets is identified as the canonical object that an external clock must order in these extended game structures.
- A theory for transitive reduction exists for these quotients, and both existence and uniqueness of this reduction are provable under an interval finiteness condition.
- Under natural topological regularity assumptions (closed reachability classes, order density, and sigma compactness), necessary and sufficient conditions exist for assigning real-valued time labelings.
- Measurable selection procedures can be constructed in Polish spaces using the developed framework.
- Constructive algorithms can be derived from the theoretical development, with their applications and computational implications shown through a differential game example.
Potential Applications
The research provides constructive algorithms, and a differential game example is used to illustrate both applications and computational implications. This suggests that the framework has practical relevance for analyzing and structuring infinite extensive games. The ability to assign real-valued time labelings and develop measurable selection procedures could be applicable in domains where continuous time or information sets are relevant, such as certain economic models or control systems.