First-Order Coalition Logic

2025/05/11 by Davide Catta, Catta, Davide, Rustam Galimullin +3
Computer Science · Economics, Econometrics and Finance · #03B45 #03B70 #F.4.1 #FOS: Computer and information sciences #Game Theory and Voting Systems #I.2.4 #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Multi-Agent Systems and Negotiation

paper · pdf · doi:10.48550/arxiv.2505.06960

openalex publication_date 2025/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce First-Order Coalition Logic (FOCL), which combines key intuitions behind Coalition Logic (CL) and Strategy Logic (SL). Specifically, FOCL allows for arbitrary quantification over actions of agents. FOCL is interesting for several reasons. First, we show that FOCL is strictly more expressive than existing coalition logics. Second, we provide a sound and complete axiomatisation of FOCL, which, to the best of our knowledge, is the first axiomatisation of any variant of SL in the literature. Finally, while discussing the satisfiability problem for FOCL, we reopen the question of the recursive axiomatisability of SL.

Citations

• A Logic for Conditional Local Strategic Reasoning
• Reasoning About Strategies: On the Model-Checking Problem
• Tableau-based decision procedures for logics of strategic ability in multi-agent systems

Related

• Completeness of coalition logics with seriality, independence of agents, or determinism
• Seven kinds of equivalent models for generalized coalition logics
• A minimal coalition logic
• Completeness of Epistemic Coalition Logic with Group Knowledge
• Tableau-based decision procedure for the multi-agent epistemic logic with all coalitional operators for common and distributed knowledge