Abstract
Game Logic provides a robust framework for studying proofs-about-programs by interpreting those proofs as executable strategies. In this setting, constructive proofs for games correspond to effective winning strategies that respond dynamically to an opponent's actions. This paper develops Constructive Game Logic (CGL), which extends Parikh's Game Logic (GL) with constructivity and first-order programs. Our contributions include a novel realizability semantics capturing adversarial dynamics, a natural deduction calculus with an operational semantics for proof-terms, and theoretical results including soundness, progress, and preservation. These results provide the first Curry-Howard interpretation for Game Logic, enabling the extraction of computational artifacts from game-theoretic proofs.
Introduction
In the verification of complex systems, we often model interactions as games between two players: Angel, representing the system we control, and Demon, representing a hostile or unpredictable environment. While classical Game Logic (GL) is a powerful tool for verifying these adversarial systems, it suffers from a significant limitation regarding practical synthesis. Because classical logic permits the Law of Excluded Middle, a proof that "Angel wins" may rely on non-constructive steps, resulting in strategies that branch on undecidable conditions. Such strategies are mathematically valid but computationally impossible to execute.
This paper introduces Constructive Game Logic (CGL), the first first-order program logic for games to support a full Curry-Howard correspondence. By enforcing constructivity, CGL ensures that every proof of a player’s victory is not merely a declaration of existence, but a functional program that can be automatically extracted and executed as a winning strategy.
Formal Framework and Methods
1. Syntax and First-Order Programs
CGL extends propositional Game Logic into a first-order setting. This allows for programs that modify state (such as variable assignments) and games involving infinite loops. This extension is critical for modeling real-world software and physical systems where state change is fundamental.
2. Realizability Semantics
The authors introduce a novel realizability semantics where a "realizer"—a program in a higher-order lambda calculus—witnesses the truth of a game formula. A key innovation here is the asymmetric treatment of players:
- Angel must play constructively, meaning her moves must be computable.
- Demon is allowed to play classically, as we cannot control the environment's internal logic.
3. Natural Deduction and Operational Semantics
The logic is formalized through a natural deduction calculus where every proof rule is associated with a specific proof term. As a user constructs a proof that Angel can win a game, they are simultaneously writing a functional program. The authors define how these proof terms "run" (normalize), providing a clear computational interpretation of game-theoretic concepts like choice, composition, and iteration.
Case Studies: Nim and Cake-Cutting
To validate the logic, the authors apply CGL to two classic game-theoretic benchmarks:
- Nim (Subtraction Game): This discrete, zero-sum game demonstrates how CGL handles winning invariants and loop termination. The extracted proof term provides a perfect strategy for winning the game from any valid starting state.
- Cake-Cutting: This fair-division problem illustrates how the logic handles fractional values (rational numbers) and strategies that must react to an opponent's choices to ensure a "fair" outcome.
In both cases, the authors demonstrate that the extracted computational artifacts (the strategies) are well-behaved and effectively computable.
Key Insights
The Strategy Property
The central achievement of the paper is the proof that if a formula is provable in CGL, there exists an algorithm to extract a computable function implementing the winning strategy. This effectively turns the task of formal verification into automated strategy synthesis.
Decidability as a Constraint
In CGL, a player can only branch their strategy based on decidable properties. This constraint ensures that synthesized code will never encounter an uncomputable decision point during gameplay, a common pitfall in classical synthesis methods.
Monotonicity as a Program
The logic treats the "monotonicity" of games—the principle that if you can win a game with a difficult goal, you can also win it with an easier one—as a computational transformation. This allows for the reuse and adaptation of strategies across different game configurations.
Theoretical Results
The paper establishes several foundational properties for CGL:
- Soundness: The proof calculus is sound with respect to the realizability semantics; if a strategy is provable, it is guaranteed to be a valid realizer in the model.
- Progress and Preservation: The operational semantics of the proof terms are well-defined, ensuring that extracted strategies are functional programs that do not "crash" or reach undefined states during evaluation.
- Existence Properties: The logic supports the extraction of specific computational artifacts, providing the most general account of a Curry-Howard interpretation for any program logic to date.
Limitations and Future Work
While CGL represents a major leap forward, it currently operates within discrete domains (rational numbers). A significant next step is extending the logic to constructive reals, where exact equality is undecidable. Furthermore, the authors aim to extend this framework to Differential Game Logic (dGL). Such an extension would allow for the synthesis of "correct-by-construction" controllers for cyber-physical systems, such as autonomous vehicles or medical robotics, where safety-critical interactions with the environment are paramount.
Summary updated