Network Bargaining with General Capacities

Linda Farczadi, Konstantinos Georgiou, Jochen Könemann

Introduction

Network bargaining games model how agents in a network negotiate to split the value of potential contracts. In these games, two primary solution concepts ensure "fairness" and "robustness": stability and balance. A stable outcome ensures no agent can improve their payoff by switching to a different partner. A balanced outcome, a refinement of stability based on the Nash bargaining solution, requires that partners split any "surplus" value equally relative to their best alternative options (outside options).

While these concepts are well-defined for unit-capacity networks—where each agent can sign only one contract—real-world scenarios often involve agents managing multiple relationships simultaneously. This paper addresses the long-standing challenge of finding balanced solutions in these "general capacity" games.

The Challenge of General Capacities

In unit-capacity networks, balanced solutions are well-understood and can be computed efficiently. However, general capacities introduce significant mathematical complexity. It was previously unclear if a balanced solution always existed when a stable one did, and no polynomial-time algorithm existed to find them.

A network bargaining graph with edge weights and potential contracts.

A key discovery in this research is the breakdown of the equivalence between cooperative game theory concepts. In unit-capacity games, balanced solutions correspond to the intersection of the core and the prekernel. The authors demonstrate that this equivalence fails in general capacity networks, necessitating a new approach.

Methodology: Reduction to Auxiliary Graphs

The authors' primary innovation is a reduction technique that transforms the complex general capacity problem into a simpler unit-capacity one.

  1. Auxiliary Graph Construction: For an agent with capacity $k$, the authors create $k$ separate "slots" (node copies) in a new graph.
  2. Contract Mapping: Existing contracts are assigned to specific slots, while potential alternatives are mapped to all possible slot combinations between agents.
  3. Algorithmic Solution: This transformation allows the use of established polynomial-time algorithms (e.g., Kleinberg and Tardos, 2008) designed for unit-capacity games.
  4. Reverse Mapping: The authors prove that the solution from the simplified graph can be mapped back to a valid, balanced solution in the original network.
An allocation of values across the network, illustrating the complexity of finding balanced solutions.

Key Results and Theoretical Insights

The paper provides several fundamental contributions:

  • First Polynomial-Time Algorithm: The reduction technique yields the first efficient method to compute balanced solutions for general capacity networks.
  • Existence Theorem: The authors prove that a balanced solution exists if and only if a stable one exists. Specifically, existence is guaranteed whenever the linear program for the maximum weight matching has an integral optimal solution.
  • Structural Conditions: The research identifies "gadgets" and graph properties, such as the acyclicity of the matching, that determine the applicability of traditional cooperative game theory methods.

Conclusion and Future Directions

By successfully extending network bargaining theory to general capacities, this work bridges a significant gap between theoretical models and complex real-world negotiations. Future work may explore decentralized "local dynamics" to determine how agents might naturally reach these balanced states without a centralized algorithm, and further investigate the theoretical implications of "loopy" graphs where current acyclic constraints might be relaxed.

Summary updated

BibTeX
@inproceedings{farczadi2013network,
  author = {Linda Farczadi and Konstantinos Georgiou and Jochen Könemann},
  title = {{Network Bargaining with General Capacities}},
  booktitle = {ESA},
  year = {2013},
  doi = {10.1007/978-3-642-40450-4\_37},
}
Figure