Subtopic Deep Dive

Coalition Formation Games
Research Guide

What is Coalition Formation Games?

Coalition formation games model the endogenous process by which players in cooperative games form subsets or coalitions to maximize joint payoffs while ensuring stability concepts like the core or nucleolus.

This subtopic studies stability, bargaining protocols, and farsighted dynamics in characteristic function games. Key solution concepts include the nucleolus (Schmeidler, 1969, 1868 citations) and gross substitutes conditions for equilibrium existence (Kelso and Crawford, 1982, 1348 citations). Over 10 highly cited papers from 1961-2009 address applications in labor markets, multi-agent systems, and communication networks.

Curated Papers

Key Challenges

Why It Matters

Coalition formation games explain power distribution in legislative voting (Shepsle and Weingast, 1981, 789 citations) and supply chain cooperation (Nagarajan and Sošić, 2006, 611 citations). In communication networks, they enable self-organizing resource allocation (Saad et al., 2009, 1036 citations). Task allocation in multi-agent systems uses these models for efficient coalitions (Shehory and Kraus, 1998, 1084 citations; Sandholm et al., 1999, 728 citations).

Key Research Challenges

Core Stability Computation

Computing the core in coalition games is NP-hard for large player sets due to exponential coalition subsets. Schmeidler's nucleolus provides a unique imputation but requires solving linear programs (Schmeidler, 1969). Worst-case guarantees for structure generation address scalability (Sandholm et al., 1999).

Farsighted Dynamics Modeling

Players deviate from coalitions anticipating future blocking coalitions, complicating stability predictions. Gamson's minimal winning coalition theory assumes myopic behavior but fails under farsightedness (Gamson, 1961). Kelso and Crawford extend to gross substitutes for equilibrium (1982).

Application Domain Adaptation

Transferring cooperative game models to heterogeneous settings like job matching or networks requires new stability notions. Shehory and Kraus develop task allocation methods for agents (1998). Saad et al. adapt to communication networks with decentralized cooperation (2009).

Essential Papers

The Nucleolus of a Characteristic Function Game

David Schmeidler · 1969 · SIAM Journal on Applied Mathematics · 1.9K citations

Previous article Next article The Nucleolus of a Characteristic Function GameDavid SchmeidlerDavid Schmeidlerhttps://doi.org/10.1137/0117107PDFBibTexSections ToolsAdd to favoritesExport CitationTra...

Job Matching, Coalition Formation, and Gross Substitutes

Alexander S. Kelso, Vincent P. Crawford · 1982 · Econometrica · 1.3K citations

Competitive adjustment processes in labor markets with perfect information but heterogeneous firms and workers are studied. Generalizing results of Shapley and Shubik [7], and of Crawford and Knoer...

Methods for task allocation via agent coalition formation

Onn Shehory, Sarit Kraus · 1998 · Artificial Intelligence · 1.1K citations

A Theory of Coalition Formation

William A. Gamson · 1961 · American Sociological Review · 1.1K citations

Coalition formation is a pervasive aspect of social life. This paper presents a theory of coalition formation with a statement of conditions and assumptions. While applicable to groups of varying s...

Coalitional game theory for communication networks

Walid Saad, Zhu Han, Mérouane Debbah et al. · 2009 · IEEE Signal Processing Magazine · 1.0K citations

Game theoretical techniques have recently become prevalent in many\nengineering applications, notably in communications. With the emergence of\ncooperation as a new communication paradigm, and the ...

Birds of the Same Feather Tweet Together: Bayesian Ideal Point Estimation Using Twitter Data

Pablo Barberá · 2014 · Political Analysis · 933 citations

Politicians and citizens increasingly engage in political conversations on social media outlets such as Twitter. In this article, I show that the structure of the social networks in which they are ...

Anomalies: The Ultimatum Game

Richard H. Thaler · 1988 · The Journal of Economic Perspectives · 812 citations

This paper discusses simple ultimatum games, two-stage bargaining ultimatum games, and multistage ultimatum games. Finally, I discuss ultimatums in the market. Any time a monopolist (or monopsonist...

Reading Guide

Foundational Papers

Start with Schmeidler (1969) for nucleolus as core alternative; Gamson (1961) for bargaining theory; Kelso and Crawford (1982) for equilibrium existence in matching.

Recent Advances

Saad et al. (2009) for communication networks; Nagarajan and Sošić (2006) for supply chains; Sandholm et al. (1999) for scalable generation.

Core Methods

Characteristic function games with core/nucleolus; gross substitutes conditions; integer programming for structures (Sandholm et al.); agent negotiation protocols (Shehory and Kraus).

How PapersFlow Helps You Research Coalition Formation Games

Discover & Search

Research Agent uses searchPapers('coalition formation nucleolus') to retrieve Schmeidler's 1969 paper (1868 citations), then citationGraph to map citers like Kelso and Crawford (1982), and findSimilarPapers for extensions like Saad et al. (2009). exaSearch uncovers niche applications in supply chains from Nagarajan and Sošić (2006).

Analyze & Verify

Analysis Agent applies readPaperContent on Shehory and Kraus (1998) to extract coalition algorithms, verifyResponse with CoVe to check stability claims against Gamson (1961), and runPythonAnalysis to simulate nucleolus computation via linear programming in NumPy sandbox with GRADE scoring for payoff verification.

Synthesize & Write

Synthesis Agent detects gaps in farsighted dynamics between Gamson (1961) and Sandholm et al. (1999), flags contradictions in core existence; Writing Agent uses latexEditText for theorem proofs, latexSyncCitations for 10+ papers, latexCompile for camera-ready drafts, and exportMermaid for coalition stability diagrams.

Use Cases

"Simulate nucleolus payoffs for 5-player coalition game with given characteristic function."

Research Agent → searchPapers('nucleolus Schmeidler') → Analysis Agent → readPaperContent + runPythonAnalysis (NumPy linprog solver) → researcher gets plotted payoff allocations and GRADE-verified stability metrics.

"Write LaTeX review of coalition formation in communication networks citing Saad 2009."

Research Agent → citationGraph('Saad 2009') → Synthesis Agent → gap detection → Writing Agent → latexEditText + latexSyncCitations + latexCompile → researcher gets compiled PDF with diagrams via exportMermaid.

"Find GitHub code for worst-case coalition structure generation algorithms."

Research Agent → searchPapers('Sandholm coalition structure') → Code Discovery workflow (paperExtractUrls → paperFindGithubRepo → githubRepoInspect) → researcher gets inspected repos with runnable Python coalition generators.

Automated Workflows

Deep Research workflow scans 50+ papers via searchPapers on 'coalition formation games', structures report with nucleolus citations (Schmeidler 1969) and applications (Saad et al. 2009). DeepScan applies 7-step CoVe analysis to verify core stability claims in Kelso and Crawford (1982). Theorizer generates new bargaining protocols from Gamson (1961) and Shehory-Kraus (1998) dynamics.

Try Doxa for Coalition Formation Games Research

Frequently Asked Questions

What defines coalition formation games?

Models where players endogenously form coalitions in characteristic function games, analyzed via core, nucleolus (Schmeidler, 1969), or bargaining outcomes (Gamson, 1961).

What are key methods in coalition formation?

Nucleolus via lexicographic minimization of dissatisfaction (Schmeidler, 1969); gross substitutes for equilibrium (Kelso and Crawford, 1982); worst-case structure generation (Sandholm et al., 1999).

What are the most cited papers?

Schmeidler (1969, 1868 citations) on nucleolus; Kelso and Crawford (1982, 1348 citations) on job matching; Shehory and Kraus (1998, 1084 citations) on agent coalitions.

What open problems exist?

Scalable farsighted stability beyond myopic cores; domain adaptation to networks (Saad et al., 2009) and supply chains (Nagarajan and Sošić, 2006); efficient computation for large agents (Sandholm et al., 1999).