Introduction
In coalitional game theory, agents collaborate to achieve superior outcomes. While Transferable Utility (TU) games—where a single numeric value is divided among players—are well-studied, many real-world scenarios are better modeled as Non-Transferable Utility (NTU) games. In NTU games, a coalition achieves a set of possible outcomes (consequences) that cannot be simply traded as currency. For example, in task-assignment scenarios, physical labor or specific shifts cannot be exchanged like cash. However, representing NTU games is computationally challenging due to the exponential explosion of possible outcomes for every potential coalition.
Methodology: Answer Set Games
To address these representation challenges, researchers have introduced Answer Set Games, leveraging the declarative power of Answer Set Programming (ASP). In this framework, each agent is associated with a logic program. When a coalition forms, their individual programs are merged. The "Answer Sets" (stable models) of the resulting combined program represent the valid outcomes for that group.
To derive payoffs from these logical outcomes, weight functions map specific atoms in the logic program to real numbers for each player. This approach allows for a succinct representation: a game that would require astronomical space to list explicitly can often be encoded in $O(N^2)$ rules for $N$ nodes. The researchers implemented this framework in the ntu2DLV system, built upon the DLV reasoner, to check for stability concepts like the Core—a state where no sub-group has an incentive to deviate and form their own coalition.
Complexity Boundaries
The researchers mapped the computational hardness of various reasoning tasks within this framework. They found that while checking properties is relatively efficient for "stratified" (simpler) logic programs, finding stable outcomes remains a significant challenge.
As shown in the complexity table, many problems range from P for stratified programs to coNP-complete or higher in the general case, reflecting the inherent difficulty of group negotiation and stability checking.
Experimental Results and Performance
The framework was evaluated using synthetic benchmarks based on combinatorial problems like Matching and Independent-Set games on various graph distributions, including normal, uniform, and power-law networks.
Key findings from the experimental evaluation include:
- Full Expressivity: Any finite NTU game can be represented as an Answer Set Game.
- Scaling: Basic fairness checks (imputation checking) scale linearly with the number of agents.
- The Power-Law Advantage: As seen in the performance data, reasoning is significantly faster on power-law graphs compared to uniform or normal distributions. This is particularly relevant as many real-world social and infrastructure networks follow power-law distributions.
- Core Computation: While computing the Core is exponentially harder, the system successfully processed games with up to 15 agents within reasonable timeframes for specific graph types.
Conclusion and Future Work
Answer Set Programming provides a natural and succinct fit for modeling the "set of consequences" inherent in NTU games. While the "computational wall" of Core calculation for large groups remains a challenge, the ntu2DLV system demonstrates the feasibility of this approach for moderately sized problems. Future research will focus on optimizing interactions for immediate neighbors in networks, implementing advanced pruning heuristics, and extending the framework to other solution concepts like the Shapley Value or Nucleolus.
Summary updated