Coalitions in Repeated Games

This paper introduces a framework and solution concept for repeated coalitional behavior that utilizes history-dependent schemes of continuation promises and punishments to deter coalitions from blocking, with applications demonstrated in repeated matching and negotiation settings.

The Gist

Imagine a world where people don't just make decisions once and walk away, but instead interact over and over again, like neighbors who see each other every day at the mailbox. In these situations, you can't just think about what's best right now; you have to think about what will happen tomorrow.

This paper, titled "Coalitions in Repeated Games," by S. Nageeb Ali and Ce Liu, explores a specific question: What happens when groups of people (coalitions) try to gang up to cheat the system, but they are playing a game that repeats forever?

Here is the breakdown using simple analogies.

1. The Problem: The "Roommate" Dilemma

The authors start with a classic puzzle called the Roommates Problem. Imagine three friends: Ann, Bella, and Carol.

• They need to pair up to share a room, but only two can fit. One person is always left out.
• Ann loves Bella. Bella loves Carol. Carol loves Ann.
• If Ann and Bella pair up, Carol is sad. But Bella and Carol would both be happier if they paired up instead. So, they break up Ann and Bella to room together.
• But then, Ann and Carol would be happier pairing up, so they break up Bella and Carol.
• The Result: In a one-time game, there is no stable arrangement. Everyone is constantly switching partners, and no one is ever truly happy. It's a cycle of betrayal.

2. The Solution: The "Future Promise"

The paper asks: What if they play this game every month forever?

If they play forever, they can use threats and promises to stop the cheating.

• The Strategy: "Okay, Ann and Bella will room together this month. But if Bella and Carol try to sneak off and room together, we have a plan."
• The Punishment: "If you two cheat, next month Ann and Carol will room together, and Bella will be left out alone forever."
• The Logic: Bella thinks, "If I cheat today, I get a little happiness now, but I lose my roommate forever. That's not worth it."

This is the core idea: History-dependent schemes. The punishment isn't just a slap on the wrist; it's a change in the future based on what happened in the past.

3. The Big Discovery: "Scapegoats" vs. "United Fronts"

The authors found a fascinating rule about when these threats actually work. It depends on how much the people in the cheating group agree with each other.

Scenario A: The "United Front" (Aligned Interests)

Imagine a group of people who are identical twins. They want exactly the same things.

• If they try to cheat, they can't be tricked into turning on each other.
• The Analogy: Imagine a gang of three identical twins. If you threaten to kick one out, the other two don't care because they are so similar; they will just protect their brother.
• The Result: If a group is perfectly aligned, they can guarantee themselves a high payoff. You can't break them apart. They act like a single super-player.

Scenario B: The "Divide and Conquer" (Misaligned Interests)

Now imagine a group of friends who mostly like each other, but have small differences.

• The Strategy: The authors show that you can use a "Scapegoat" strategy.
• The Analogy: Imagine a trio of friends planning a heist. The "police" (the game rules) say: "If you three try to cheat, we will punish only the person who made the biggest mistake, but we will let the other two off the hook."
• The Result: The friends realize, "Wait, if we try to cheat, one of us is going to get screwed while the others are fine." Because they are afraid of being the "scapegoat," they won't cheat in the first place.
• Key Insight: As long as there is any tiny difference in what the group members want, you can break the group apart and stop them from cheating.

4. The Twist: Secret Money (Transfers)

The paper also looks at what happens if people can pass money around secretly.

• Public Money: If everyone sees who pays whom, the "Scapegoat" strategy still works. The enforcer can say, "I see you paid your friend $10 to help you cheat. Now I know exactly who to punish."
• Secret Money: If the group can pass money around under the table (secretly), the whole system collapses.
  • The Analogy: Imagine the friends can whisper, "I'll give you my share of the loot if you help me cheat, and no one will ever know."
  • The Result: Because they can secretly align their interests, they become a "United Front" again. The threats stop working. The only stable outcome becomes the "Core" (the basic, boring, one-time game result), and all the fancy long-term cooperation disappears.

5. Real-World Application: The Labor Market

The authors apply this to wages and jobs.

• The Setup: Firms hire workers. Workers want high wages; firms want low wages.
• Public Wages (Transparency): If everyone knows what everyone else is paid, firms and workers can use "Scapegoat" strategies to keep wages high or low depending on who is stronger.
  • If workers are plentiful: Firms can collude to keep wages low.
  • If workers are scarce: Workers can collude to keep wages high.
• Secret Wages (Private Contracts): If firms can offer secret, private deals to workers (like a "poaching" offer that no one else sees), the workers can secretly band together to demand more.
  • The Paradox: The paper finds that transparency can actually help workers if they are plentiful. Why? Because if wages are public, firms can't secretly poach each other's workers without triggering a "salary war" (a punishment). If wages are secret, firms can quietly undercut each other, driving wages down to the minimum.

Summary

This paper teaches us that long-term relationships are powerful tools for cooperation, but they are fragile.

1. Threats work if the cheaters have even a tiny disagreement among themselves (you can play them against each other).
2. Threats fail if the cheaters are perfectly united or if they can make secret side-deals to align their interests.
3. Transparency is a double-edged sword: it can prevent secret collusion, but it can also enable public collusion, depending on who holds the power.

In short: To keep a group from cheating, you need to find the crack in their unity. If they can hide their secrets, the cracks disappear, and the system breaks.

Technical Summary

1. Problem Statement

The paper addresses a fundamental gap in game theory: the lack of a unified framework for analyzing repeated coalitional behavior.

• The Conflict: Standard repeated game theory (e.g., Folk Theorems) focuses on individual deviations and history-dependent strategies (promises and punishments) to sustain cooperation. Conversely, cooperative game theory (e.g., the Core, Pairwise Stability) focuses on group deviations (blocking) but typically in static settings without dynamic incentives.
• The Question: How can dynamic incentives (future rewards and punishments) deter groups (coalitions) from blocking an arrangement in a repeated setting? Specifically, under what conditions can history-dependent schemes sustain outcomes that are unstable in a one-shot game, and when do they fail?
• Motivating Example: The "Roommates Problem" (Ann, Bella, Carol). In a static setting, no pairing is stable because any pair can block to form a better match. The authors ask: Can a repeated interaction with a discount factor $\delta$ support a stable matching (e.g., Ann and Bella rooming together) by threatening that a deviation (e.g., Bella and Carol rooming together) will trigger a punishment phase where the deviators are left out?

2. Methodology and Framework

A. The Model

The authors propose a general framework for repeated games with coalitional blocking:

• Stage Game: Players $N$ choose an alternative $a \in A$. A coalition $C$ can "block" an alternative $a$ if they can choose a new alternative $a' \in E_C(a)$ (where $E_C$ is the effectivity correspondence) that improves their payoffs.
• Repeated Interaction: The game is played infinitely with a common discount factor $\delta$.
• Plans: A plan $\sigma$ specifies a default alternative for every history $h$. If a coalition blocks, the game moves to a new history, and the plan dictates the next default.
• Solution Concept: Perfect Coalitional Equilibrium (PCE):
  • A plan $\sigma$ is a PCE if no coalition $C$ can profitably block at any history $h$.
  • Profitable Blocking: A coalition blocks if there exists an alternative $a'$ and a continuation path such that every member $i \in C$ receives a strictly higher discounted payoff than under the plan $\sigma$.
  • Recursive Nature: The continuation of a PCE after any history (on or off-path) must itself be a PCE. This allows the use of dynamic programming (self-generation) techniques à la Abreu, Pearce, and Stacchetti (1990).

B. Key Analytical Tools

• Coalitional Minmax ($v^\circ_i$): The lowest payoff a player $i$ can be forced to accept when the coalition of players with equivalent utilities (those whose payoffs move in perfect sync) collectively best responds.
• Scapegoat Schemes: A mechanism to deter coalitional blocking by punishing only one member of a deviating coalition (the "scapegoat") while granting amnesty to the others. This works if coalition members have misaligned interests.
• Transferable Utility (TU) & Observability: The paper distinguishes between:
  • Public Transfers: Transfers within a blocking coalition are observed by outsiders.
  • Secret Transfers: Transfers are observed only by the coalition members, not by outsiders.

3. Key Contributions and Results

I. The Role of Preference Alignment (The "Knife-Edge" Result)

The central finding is that the effectiveness of dynamic incentives depends entirely on the alignment of interests within a coalition.

• Misaligned Preferences (NEU Condition): If coalition members have non-equivalent utilities (even slightly), a PCE can support a vast set of payoffs (a Folk Theorem result).
  • Mechanism: The planner can use scapegoat schemes. If a coalition $C$ considers blocking, the planner threatens to punish a specific member $i \in C$ (who would suffer the most from the punishment) while sparing the others. Since $i$'s interests are not perfectly aligned with the rest, $i$ will refuse to block, causing the coalition to collapse.
• Perfectly Aligned Preferences: If a coalition $C$ consists of players with equivalent utilities, they act as a single unitary agent.
  • Result: They can guarantee themselves their coalitional minmax ($v^\circ_i$) regardless of the discount factor.
  • Implication: Dynamic incentives cannot push their payoffs below this level. If the stage game has an empty core but players are perfectly aligned, the set of PCE payoffs shrinks significantly.

II. Structural Properties of PCE

• Stationarity: In games with default-independent power (where the set of payoffs a coalition can achieve by blocking does not depend on the current alternative, e.g., matching games, characteristic function games) and convex payoffs, all PCE payoffs can be supported by stationary plans. History dependence is not strictly necessary for the existence of the payoff set, though it is crucial for the enforcement mechanism.
• Strongly Symmetric Equilibria: The paper proves an "Anti-Folk Theorem" for strongly symmetric PCEs. If a plan requires symmetric play (punishments must be symmetric), it often fails to deter coalitions because symmetric punishments align the coalition's interests (making them act as a unit). To sustain cooperation, asymmetric punishments (scapegoating) are usually required.

III. The Impact of Transfers

The paper analyzes whether the ability to transfer utility helps or hinders coalitional stability.

• Public Transfers: Surprisingly, publicly observed transfers undermine coalitions. Because transfers are visible, the planner can condition future punishments on the distribution of the surplus within the blocking coalition. The planner can identify a "scapegoat" based on who receives the transfer, effectively splitting the coalition even if their underlying preferences were aligned.
  • Result: With public transfers, the set of supportable payoffs expands to all feasible and individually rational payoffs (a full Folk Theorem).
• Secret Transfers: If a coalition can make secret side-payments, they can perfectly align their incentives internally.
  • Result: This creates an "Anti-Folk Theorem." The coalition acts as a unitary agent with a high minmax. The set of supportable payoffs collapses to the Core of the stage game. Dynamic incentives lose their power to enforce outcomes outside the static core.

IV. Application: Labor Market Matching

The authors apply the framework to the Kelso-Crawford (1982) labor market model.

• Wage Transparency:
  • Public Wages: If wages are transparent, firms and workers can use repeated interaction to sustain a wide range of wage distributions (e.g., workers can collectively bargain for high wages, or firms can collude for low wages).
  • Private Wages: If wages are private (secret side-payments between firm and worker are possible), the set of sustainable outcomes collapses to the static core.
• Who Benefits?
  • If labor supply is high or marginal returns fall quickly, workers benefit from wage transparency (it allows them to enforce collective bargaining).
  • If labor is scarce or marginal returns fall slowly, firms benefit from wage transparency (it allows them to collusively suppress wages).
  • Without transparency, competitive forces drive wages down to the marginal product of the least productive worker.

V. Application: Distributive Politics (Veto Players)

In a political economy setting with veto players:

• Without Secret Transfers: History dependence can support egalitarian splits (e.g., 1/3 each) even if the static core gives everything to the veto player.
• With Secret Transfers: If minimal winning coalitions can make secret transfers, the veto players regain "de facto dictatorial" power, and the set of sustainable outcomes collapses back to the static core (veto players get everything).

4. Significance and Conclusion

• Theoretical Synthesis: The paper successfully bridges the gap between non-cooperative repeated games and cooperative game theory, providing a rigorous solution concept (PCE) that handles both individual and coalitional deviations with history dependence.
• The "Alignment" Principle: The paper establishes that dynamic incentives are powerful only when coalition members have misaligned interests. Perfect alignment creates a "knife-edge" where coalitions become immune to standard punishments.
• Policy Implications: The analysis of transparency offers a novel perspective on wage transparency and political accountability. It suggests that transparency is not inherently good or bad; its welfare effects depend on which side of the market (labor vs. capital, or voters vs. veto players) can use it to collude.
  • Transparency enables collusion if it allows the "strong" side to coordinate (e.g., firms suppressing wages).
  • Transparency enables collective bargaining if it allows the "weak" side to coordinate (e.g., workers demanding higher wages).
• Secret Side-Payments: The paper highlights that the ability to make secret transfers is a potent force that can destroy intertemporal incentives, reverting the system to static equilibrium outcomes (the Core).

In summary, Ali and Liu demonstrate that the power of repeated games to sustain cooperation against coalitional threats relies on the ability to "divide and conquer" coalitions through asymmetric punishments. When coalitions can align their interests perfectly (via secret transfers or inherent preference alignment), this power vanishes.