Rich Coalitional Resource Games

Nicolas TroquardAAAI 2018 · DOI

Abstract

Rich Coalitional Resource Games (RCRGs) provide a formal framework for modeling multi-agent cooperation using Linear Logic. Unlike traditional models that treat resources as simple scalar quantities, RCRGs leverage the resource-sensitive nature of Linear Logic to account for consumption, transformation, and choice. This paper establishes the theoretical foundations of RCRGs and provides a comprehensive complexity analysis of key decision problems such as coalition winning, player essentiality, and core stability.

Introduction

In multi-agent systems, agents often possess limited resources and individual goals that necessitate the formation of coalitions. Traditional Coalitional Resource Games (CRGs) typically model resources as simple numerical endowments. However, real-world scenarios involve complex resource dynamics: using an ingredient consumes it, and raw materials can be transformed into finished products.

Classical logic is ill-suited for these "resource-sensitive" environments because it allows for the arbitrary duplication of premises (e.g., $A \implies A \land A$). To address this, we introduce Rich Coalitional Resource Games (RCRGs), which utilize Linear Logic (LL) to respect the "physics" of resources—where the act of proving a goal logically consumes the resources used in the proof.

Methodology: Linear Logic as a Game Language

RCRGs integrate Linear Logic into game theory by representing agent endowments and goals as logical formulas. This allows for a high degree of expressiveness:

  • Simultaneous Availability ($A \otimes B$): Having both resource A and resource B.
  • Deterministic Choice ($A \& B$): Having the choice between resource A or resource B.
  • Resource Transformation ($A \multimap B$): The ability to turn resource A into resource B.

A coalition is defined as "winning" if the combined resource formulas of its members can logically entail the combined goal formulas within a specific fragment of Linear Logic, such as Multiplicative Linear Logic (MLL) or Multiplicative Additive Linear Logic (MALL).

Complexity Analysis and Results

The primary contribution of this work is the mapping of computational complexity for various decision problems within the RCRG framework.

The WIN Problem

The WIN problem asks whether a specific coalition can achieve its goals. The complexity varies significantly depending on the logic fragment used. For the MLL fragment, the problem resides in $\Sigma_2^P$. However, for the more expressive MALL fragment, determining a winning coalition becomes PSPACE-complete.

Complexity of the WIN problem across different RCRG classes.

Stability and Player Roles

Beyond winning, we analyze the stability of coalitions (Core Non-Empty, or CNE) and the roles of individual players (VETO and DUMMY). In "one-goal affine" versions of the game—where agents have a single goal and can discard excess resources—the complexity remains high. For MALL-based games, these problems are generally PSPACE-complete.

Complexity of VETO, DUMMY, and CNE problems for one-goal affine RCRGs.

Key Insights

  • Logic-Resource Duality: The proof theory of Linear Logic mirrors resource management; proving a formula is equivalent to "spending" resources to "produce" an outcome.
  • Generalization: RCRGs formally generalize standard CRGs. While any CRG can be translated into an RCRG, the latter can describe complex transformations that the former cannot.
  • Expressive Goals: Even in "one-goal" games, the use of logical connectives like choice ($\oplus$ and $\&$) allows a single formula to represent a sophisticated set of alternative objectives.

Conclusion and Future Work

RCRGs offer a robust framework for reasoning about resource-constrained cooperation. While the computational complexity is high, the model provides a precise language for complex multi-agent scenarios. Future research will explore non-transferable utility models and the use of the Curry-Howard correspondence to automatically generate cooperative plans from logical proofs.

Summary updated

BibTeX
@inproceedings{troquard2018rich,
  author = {Nicolas Troquard},
  title = {{Rich Coalitional Resource Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11437},
}
Figure