TL;DR
This paper introduces First-Order Coalition Logic (FOCL), a novel logic that combines the expressiveness of Coalition Logic (CL) with the flexibility of first-order quantification over actions, allowing for arbitrary quantification prefixes and explicit action labels. The authors provide a sound and complete axiomatization for FOCL, demonstrate its strict expressivity over existing coalition logics, and establish its PSPACE-complete model-checking problem and undecidable satisfiability problem, reopening questions about the recursive axiomatisability of Strategy Logic.
What Problem Does This Paper Address?
Reasoning about the strategic interactions of multiple autonomous agents is crucial in various fields, from artificial intelligence and game theory to economics and cybersecurity. Formal logics have been developed to model these scenarios, with Coalition Logic (CL) and Strategy Logic (SL) being prominent examples. CL allows reasoning about what coalitions of agents can achieve together, but its quantification over agents' actions is limited to fixed prefixes. Strategy Logic (SL) offers more flexibility by allowing arbitrary quantification prefixes over agents' strategies, enabling reasoning about complex game-theoretic concepts like Nash equilibria. However, SL and its variants have lacked formal axiomatizations, making them difficult to work with systematically. This paper addresses this gap by introducing FOCL, a logic that bridges the expressivity of CL and the flexibility of SL's quantification while remaining amenable to formal axiomatization.
Methods
The core contribution of this paper is the introduction and formalization of First-Order Coalition Logic (FOCL). FOCL extends Coalition Logic by incorporating first-order quantification over actions and allowing explicit action labels in its syntax. This means that instead of just saying "a coalition can achieve X," FOCL can express statements like "there exists an action 'a' such that if agent 1 performs 'a' and agent 2 performs 'b', then X is achieved."
Key methodological contributions include:
- Syntax and Semantics: A formal definition of FOCL's language and its semantics based on Concurrent Game Structures (CGS), which are extensions of Kripke frames to model multi-agent systems.
- Axiomatization: A sound and complete axiomatization for FOCL is presented. This is a significant achievement, as it's claimed to be the first axiomatization for any variant of Strategy Logic. The axiomatization draws inspiration from first-order modal logic.
- Expressiveness Analysis: The paper rigorously proves that FOCL is strictly more expressive than existing coalition logics like CL, QCL, ConStR, SFCL, GPCL, and Action Logic (AL). This is demonstrated through translations and counterexamples that leverage FOCL's unique features like strategy sharing and explicit action references.
- Complexity Analysis: The authors establish that the model-checking problem for FOCL is PSPACE-complete. They also prove that the satisfiability problem for FOCL is undecidable, using a reduction from the tiling problem. This undecidability result for FOCL's next-time fragment also reopens the question of whether SL itself is recursively axiomatisable.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Bridging the Gap: FOCL successfully bridges the expressivity gap between Coalition Logic (CL) and Strategy Logic (SL) by allowing arbitrary first-order quantification over actions and explicit action labels. This provides a more nuanced way to model agent interactions than CL, without sacrificing the possibility of formal reasoning as much as full SL might.
- First Axiomatization for Strategy Logic Variants: The development of a sound and complete axiomatization for FOCL is a major breakthrough. It suggests that even complex logics with arbitrary quantification can be systematically reasoned about, paving the way for similar efforts for other strategy logics.
- Undecidability and Recursive Axiomatisability: The undecidability of FOCL's satisfiability problem, even for its next-time fragment, has significant implications. It suggests that full SL might indeed be undecidable and, more importantly, that the assumption of recursive axiomatisability for SL might be incorrect, prompting a re-evaluation of existing research in this area.
- Expressivity Beyond Existing Logics: FOCL's strict superiority in expressiveness over established logics like CL and Action Logic highlights the power of combining arbitrary quantification with explicit action references. This allows for modeling more subtle strategic scenarios, such as strategy sharing, which are not easily captured by other logics.
Key Results
- Strict Expressivity: FOCL is strictly more expressive than Coalition Logic (CL), Quantified Coalition Logic (QCL), Conditional Strategic Reasoning (ConStR), Socially Friendly CL (SFCL), Group Protecting CL (GPCL), and Action Logic (AL).
- Model Checking: The model-checking problem for FOCL is PSPACE-complete.
- Satisfiability: The satisfiability problem for FOCL is undecidable.
- Axiomatization: A sound and complete axiomatization for FOCL has been provided.
Limitations and Future Work
The authors acknowledge several avenues for future research:
- LTL Modalities: Extending FOCL with Linear Temporal Logic (LTL) modalities would allow for reasoning about more complex temporal goals and could lead to axiomatisations of richer SL fragments like one-goal SL and flat conjunctive-goal SL.
- Imperfect Information: Investigating FOCL in the context of imperfect information systems is a promising direction.
- Next-Time Fragment of SL: The paper highlights that the next-time fragment of SL has not been extensively studied. Future work could focus on identifying axiomatisable variations of this fragment and comparing them to FOCL.
- STIT Logics: Exploring the relationship between FOCL and STIT (Seeing To It That) logics, which deal with agency and responsibility, is another exciting research direction.
- Recursive Axiomatisability of SL: The undecidability result for FOCL's next-time fragment has reopened the question of whether SL is recursively axiomatisable. The authors suggest that proving this might require richer features of SL beyond its next-time fragment.
Summary updated