A Four-Valued Graph Model for Conflict Resolution: Core Framework and a Machine-Checked Formalization in Lean 4

arXiv:2609.11174 · cs.LO · Submitted 2026-09-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "A Four-Valued Graph Model for Conflict Resolution".

Jane: Here's the gist of the paper. A Four-Valued Graph Model for Conflict Resolution: Core Framework and a Machine-Checked Formalization in Lean 4 consolidates the Quasi-Closed World Graph Model for Conflict Resolution (QCW-GMCR), a framework that extends the standard Graph Model for Conflict Resolution (GMCR) with Belnap’s four-valued logic to represent epistemic ambiguity at the option level, and pairs it with a machine-checked formalization in Lean 4.

Tom: Core Framework Components The framework comprises four components that extend standard GMCR.

Jane: These components include: (1) option-level epistemic assignments in FOUR = Y, N, YN, U with compositional propagation to state-level feasibility.

Tom: (2) graded reachability (definite/credible/possible) derived from an FDE-inspired transition-warrant semantics.

Paper summary: Tom: So to recap, this paper introduces the Quasi-Closed World Graph Model for Conflict Resolution, or QCW-GMCR, which extends the standard GMCR by incorporating Belnap’s four-valued logic >

Jane: The core thesis is that this approach can represent epistemic ambiguity at the option level in a way that binary models simply can't capture cleanly >

Lu: They ground option status using FOUR, which includes Yes, No, Yes and No, and Unknown. This allows them to handle decisions where we don't have a clear numerical degree of uncertainty >

Tom: And they build this framework on four components: option-level assignments with compositional propagation to state-level feasibility >

Jane: Then they introduce graded reachability—definite, credible, and possible—which is inspired by FDE semantics and links definite reachability to no option being de-selected >

Lu: They then have these formal reduction operators that map the four values into binary decisions based on distinct risk attitudes like conservative or optimistic >

Tom: And finally, they establish a catastrophe-avoiding equilibrium concept with this structural safety guarantee, which is the quasi-closed world invariant >

Jane: It’s about building a system where you can represent uncertainty as logical status rather than just a fuzzy number, and the machine check in Lean four gives them some strong backing on the formal structure > <ref:2609.11174#pg1>

Lu: The fact that they mapped these ideas into Lean four and verified properties like the four-valued conjunction shows that this isn't just theoretical exercise; it’s a rigorously defined model > <ref:2609.11174#pg1>

Tom: It’s about showing how to handle those tough, irreversible decisions where we know we need an action but we can't quantify the exact risk of failure >

Jane: So what this means for us is that we can start thinking about conflict resolution not just as finding the best outcome in a known world, but as managing ambiguity directly within the decision structure itself >

Conclusion: Tom: The title itself, "A Four-Valued Graph Model for Conflict Resolution: Core Framework and a Machine-Checked Formalization in Lean four" tells you exactly the scope of this work > <ref:2609.11174#pg1,A Four-Valued Graph Model for Conflict Resolution: Core Framework and a>

Jane: It shows they didn't just propose a new concept; they developed a complete framework, from the logic to the proof assistant implementation >

Lu: They’ve managed to formalize these complex ideas using Lean four which is impressive because it provides that machine-checked verification of things like graded reachability > <ref:2609.11174#pg1>

Tom: It gives us a reference implementation for safety-critical decision support because of that verification status on classical GMCR stability hierarchies >

Jane: The implication for the world is moving away from trying to force a single probability distribution onto every hard choice, and instead focusing on managing the inherent uncertainty directly within the model's structure >

Lu: It suggests that for things like irreversible decisions where controlled experiments aren't possible, this four-valued approach provides a way to choose actions that are structurally safe according to the quasi-closed world invariant >

Tom: So it’s about giving decision makers a tool to explicitly state and manage the different kinds of uncertainty they face, rather than hiding it behind a single number >

Jane: It shifts the focus from prediction as much as possible to robust action under deep uncertainty, which is a very concrete shift for anyone dealing with real-world choices >

Institute of Science Tokyo, Japan

cs.LO

Submitted: 2026-09-10

Updated: 2026-11-11

Code: https://github.com/ykato0623/qcw-gmcr-lean

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: A Four-Valued Graph Model for Conflict Resolution: Core Framework and a Machine-Checked Formalization in Lean 4 consolidates the Quasi-Closed World Graph Model for Conflict Resolution (QCW-GMCR)…

Key concepts

FOUR = Y, N, YN, U
This is Belnap's four-valued logic used to represent the status of options or states in the conflict resolution model. It allows for nuanced descriptions beyond simple true/false by including possibilities like 'Yes', 'No', 'Yes and No', and 'Unknown'. This logic is fundamental for capturing epistemic ambiguity at the option level.
Graded Reachability
This concept describes how reachable states are categorized based on certainty. Instead of just being reachable or not, states are graded as Definite (DY), Credible (DYN), Possible (DU), or Unknown (U). This grading is derived from a transition-warrant semantics inspired by FDE, providing a more detailed measure of possibility.
Quasi-Closed World Invariant
This is a structural safety guarantee ensuring the model remains safe. It states that if strategic moves are restricted to the 'quasi-closed' state space, no forbidden state can ever be reached. This invariant is achieved by defining a reduced set of states (Squasi) that excludes forbidden states and their boundaries.
Reduction Operators ($\delta$ operators)
These operators map the complex four-valued assignments to simple binary decisions (Yes/No). There are four canonical types: conservative, precautionary, optimistic, and contradiction-averse. These operators resolve ambiguity by imposing specific risk attitudes onto the decision process.

Terminology

Summary

A Four-Valued Graph Model for Conflict Resolution: Core Framework and a Machine-Checked Formalization in Lean 4 consolidates the Quasi-Closed World Graph Model for Conflict Resolution (QCW-GMCR), a framework that extends the standard Graph Model for Conflict Resolution (GMCR) with Belnap’s four-valued logic to represent epistemic ambiguity at the option level, and pairs it with a machine-checked formalization in Lean 4. p. 0

Core Framework Components

The framework comprises four components that extend standard GMCR. These components include:

(1) option-level epistemic assignments in FOUR = Y, N, YN, U with compositional propagation to state-level feasibility.

(2) graded reachability (definite/credible/possible) derived from an FDE-inspired transition-warrant semantics. p. 0

(3) formally constrained reduction operators mapping four-valued assignments to binary decisions, with four canonical operators characterized by distinct risk attitudes. p. 0

(4) catastrophe-avoiding equilibrium concepts with a structural safety guarantee, the quasi-closed world invariant. p. 0

Epistemic Foundations and Reachability

The model utilizes Belnap’s four-valued logic, FOUR = Y, N, YN, U to ground option status in Belnap’s four-valued logic. Option-level assignments are defined as ψi,o ∈ FOUR for each i ∈ N and o ∈ Oi. p. 3 Compositional feasibility is handled by a feasibility composition operator Γ: FOURO → FOUR, defaulting to conjunctive composition where a state is feasible only to the degree that all of its constituent options are. p. 3 The transition-warrant connective ⇒w on FOUR is inspired by FDE semantics, defined as E(s →i s′) = V ψi,o(s) ⇒w ψi,o(s′). p. 4 This leads to graded reachability where DY = Y, DYN = Y, N, DU = Y, N, U. p. 4 Proposition 4. p. 37 certifies the FDE characterization of definite reachability as s →Yi s′ is equivalent to no option being de-selected. p. 5

Structural Safety and Reduction Operators

The QCW-GMCR transforms an ambiguity-rich open world into a safety-preserving quasi-closed world through four layers. Layer 3 is the quasi-closed state space Squasi = Sreduced - (F U B), where F are forbidden states and B is the boundary. p. 7 Reduction operators δ: FOUR → Y, N resolve ambiguous values to binary decisions, with four canonical operators: conservative δcons, precautionary δprec, optimistic δopt, and contradiction-averse δcont. p. 6 These operators must satisfy two formal requirements: (A0) classical extension and (A1) truth monotonicity. p. 6 Theorem 5.5 establishes that there are exactly four admissible deterministic reductions, corresponding to maximal caution, contradiction tolerance with ignorance aversion, contradiction aversion with ignorance tolerance, and maximal inclusion. p. 7

Equilibria and Robustness

The framework defines stability concepts at each level l ∈ Y, YN, U. Catastrophe-avoiding equilibria require moves to be restricted to safe level-l reachability within Squasi. p. 9 Theorem 5.8 states the quasi-closed world invariant, guaranteeing that no forbidden state is reachable from any s ∈ Squasi if admissible strategic paths are restricted to Squasi. p. 7 Cross-level robustness is achieved when a state remains stable at all three levels, and cross-operator robustness requires stability under all four canonical operators. p. 8

Formal Verification Status

The Lean 4 formalization has been machine-checked with mathlib, verifying the classical GMCR stability hierarchy (Nash ⊆ SMR ⊆ GMR and Nash ⊆ SEQ ⊆ GMR). It also verifies the algebraic properties of four-valued conjunction, compositional propagation properties, and the graded reachability hierarchy. p. 0 The formalization exposed an issue with the reduction-operator monotonicity for δcons, δopt, and δcont. p. 6 Future work includes formalizing the corrected FDE characterization and the hypergame existence counterexample. p. 5 The development serves as a verified reference implementation for safety-critical decision support. p. 6

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Ability to model epistemic ambiguity at option levels by assigning four-valued assignments (Y, N, YN, U) to options rather than relying on binary feasibility or numerical probabilities. This allows the system to represent situations where it is unknown whether an opponent has committed or when intelligence is contradictory.

  2. Implementation of graded reachability (definite/credible/possible) derived from FDE-inspired transition-warrant semantics. This enables the system to distinguish between moves that are certain, supported despite contradiction, and merely possible, providing a richer strategic assessment than all-or-nothing reachability models.

  3. Formal constrained reduction operators mapping four-valued assignments to binary decisions based on distinct risk attitudes (conservative, precautionary, optimistic, contradiction-averse). The AI can select the most appropriate decision strategy for a given conflict by choosing the operator that aligns with its operational context and risk tolerance.

  4. Structural safety guarantees via the quasi-closed world invariant. This mechanism ensures that if analysts restrict reasoning to a set of states where no moves into forbidden catastrophic states are possible, then no forbidden state is reachable from any s in Squasi.

  5. Capacity for path entailment decay analysis, where entailment is non-increasing under concatenation, meaning that a path is no more secure than its weakest constituent warrant. This allows the system to evaluate multi-step plans and recognize that joint maneuvers carry a warrant bounded by their weakest link.

  6. Integration of coalitional stability concepts graded by epistemic level (level-l coalitional improvement). The AI can assess not just individual moves but also a nonempty sequence of unilateral moves by members of H, each carrying move entailment in Dl, allowing it to distinguish between nominal power and epistemically executable power.

  7. Subjective modeling for interactive unawareness within hypergame frameworks. The system can model how a DM may be unaware of options available to others or whether they have grounds for neither accepting nor rejecting the status of an option already in view (U).

  8. Automated diagnosis of structural epistemic conflict via the shared safe core membership predicate. If S core = ∅, no state is simultaneously recognized as feasible and safe by all DMs, the system can diagnose a situation requiring belief alignment (joint factfinding, operator harmonization, catastrophe-threshold alignment) before equilibrium analysis can proceed.

Sources

Related papers