The price of democracy in coalition formation

Georgios Chalkiadakis, Edith Elkind, Maria Polukarov, Nicholas R. JenningsAAMAS 2009

Introduction

In the field of multiagent systems, a fundamental tension exists between centralized efficiency and decentralized autonomy. While a central controller can mandate the most resource-efficient configuration for a team, real-world agents are typically self-interested and autonomous. These agents will only participate in coalitions that they perceive as fair or personally beneficial. This shift from a top-down mandate to a bottom-up negotiation process introduces inherent inefficiencies.

This paper introduces and quantifies the Price of Democracy (PoD): a metric that measures the efficiency loss incurred when self-interested agents form coalitions through decentralized negotiation rather than a centralized mandate. By focusing on Weighted Voting Games (WVGs), the authors provide a rigorous mathematical framework to understand how much extra resource cost is paid for the sake of a democratic process.

The Bargaining Framework

To analyze the PoD, the researchers utilize Weighted Voting Games (WVGs). In this model, each agent possesses a specific "weight" representing their resources. A coalition is considered successful (or "winning") if the sum of its members' weights meets or exceeds a predefined threshold.

The authors propose a Coalitional Bargaining Process to model how these agents interact:

  1. Proposals: Agents are ordered by weight (from heaviest to lightest). They take turns proposing a specific coalition and a distribution of the resulting payoff.
  2. Voting: Every member of the proposed coalition must vote to accept or reject the deal. A unanimous "yes" within the proposed group ends the game. A single rejection moves the process to the next round, where the next agent in the sequence makes a proposal.
  3. Equilibrium Analysis: The study focuses on Subgame-Perfect Nash Equilibrium (SPNE). Specifically, it looks for "stationary" strategies—decisions based on the current state of the game rather than past grievances or complex histories.

Key Insights: The Efficiency of Negotiation

The "No Delay" Phenomenon

One of the most significant findings is the "no delay" property. Despite the potential for multiple rounds of negotiation, rational agents in this model will almost always reach an agreement in the very first round. This occurs because the first proposer understands the "threat" of what might happen in subsequent rounds. To avoid being excluded or receiving a worse deal later, the first proposer is incentivized to make a "reasonable" offer immediately that satisfies the necessary partners.

The Magic of the Second Round

The research reveals a fascinating relationship between the number of allowed negotiation rounds and the resulting efficiency:

  • One-Round Bargaining: If agents are only allowed a single chance to reach a deal, the PoD can be as high as 2. This means the decentralized process might use up to twice the resources required by an optimal centralized solution.
  • Two-Round Bargaining: Surprisingly, simply allowing for a second round—even if that round is never actually reached—drops the PoD bound to 1.5 (3/2). The mere existence of a fallback round changes the bargaining power of the agents in the first round, forcing a more efficient outcome.
  • Diminishing Returns: The authors prove that adding a third, fourth, or even an infinite number of rounds provides no further efficiency gains. The bound remains at 1.5. Thus, two rounds represent the "sweet spot" for maximizing resource efficiency in decentralized coalition formation.

Computational and Resource Considerations

Beyond theoretical bounds, the paper addresses the practical implementation of these systems. The authors demonstrate that finding these equilibrium strategies is computationally efficient. They provide an algorithm that computes the bargaining equilibrium in polynomial time, making it a viable approach for real-world multiagent coordination where decisions must be made quickly.

Furthermore, the study explores scenarios with multiple tasks. While the PoD can theoretically become infinite if resources are extremely scarce (as selfish agents may "block" the most efficient global configuration to secure their own payoff), the PoD remains capped at 2 as long as resources are relatively abundant (at least twice the minimum required amount).

Limitations and Future Directions

While the paper provides a robust foundation for the Price of Democracy, it acknowledges several constraints:

  • Information Symmetry: The model assumes "perfect information," where all agents know the weights of all other participants. In many real-world applications, weights or thresholds might be private information.
  • Fixed Ordering: The current results rely on a fixed bargaining order (heaviest to lightest). Future research could investigate how random proposer orders or different sequencing rules affect the efficiency bounds.
  • Game Generalization: While the 1.5 and 2 bounds are specific to Weighted Voting Games, the concept of PoD is broadly applicable. The authors suggest that future work should examine PoD in other contexts, such as network flow games or minimum-cost spanning trees, to see if similar "magic numbers" exist in those domains.

Summary updated

BibTeX
@inproceedings{chalkiadakis2009price,
  author = {Georgios Chalkiadakis and Edith Elkind and Maria Polukarov and Nicholas R. Jennings},
  title = {{The price of democracy in coalition formation}},
  booktitle = {AAMAS},
  year = {2009},
}
Figure