Distributed bargaining in dyadic-exchange networks

Dean Richert, Jorge Cortés

Abstract

This paper considers dyadic-exchange networks in which individual agents autonomously form coalitions of size two and agree on how to split a transferable utility. Valid results for this game include stable (if agents have no unilateral incentive to deviate), balanced (if matched agents obtain similar benefits from collaborating), or Nash (both stable and balanced) outcomes. We design provably-correct continuous-time algorithms to find each of these classes of outcomes in a distributed way. Our algorithmic design to find Nash bargaining solutions builds on the other two algorithms by having the dynamics for finding stable outcomes feeding into the one for finding balanced ones. Our technical approach to establish convergence and robustness combines notions and tools from optimization, graph theory, nonsmooth analysis, and Lyapunov stability theory and provides a useful framework for further extensions. We illustrate our results in a wireless communication scenario where single-antenna devices have the possibility of working as 2-antenna virtual devices to improve channel capacity.

Introduction

In many networked systems—from wireless sensors to social groups—agents can perform better by collaborating. However, in a "dyadic-exchange network," agents can only match with one partner at a time. This creates two major challenges: matching (who should pair up with whom to maximize the total benefit?) and bargaining (once paired, how should they split the "transferable utility" or profit?).

The authors seek solutions that satisfy specific game-theoretic properties:

  • Stable: No agent can get a better deal by unilaterally ditching their partner for a neighbor.
  • Balanced: The split is fair based on each agent's next-best alternative.
  • Nash: A solution that is both stable and balanced.
Comparison of Stable, Balanced, and Nash outcomes in a 4-node network.

While centralized methods for finding these outcomes exist, they often fail to scale and can compromise agent privacy. This paper introduces a set of distributed, continuous-time algorithms that allow agents to autonomously reach these outcomes using only local information.

Methodology

The proposed solution decomposes the complex Nash bargaining problem into two interconnected dynamical systems:

1. Finding Stable Outcomes via Distributed LP

The problem of finding a stable matching is equivalent to solving a Linear Programming (LP) relaxation of the "maximum weight matching" problem. The authors adapt a continuous-time distributed LP solver that allows agents to update their states based on their neighbors' values. One of the most elegant insights is linking the game-theoretic concept of stability directly to the dual variables of this classic graph theory optimization problem.

2. Finding Balanced Outcomes via Error Correction

Once a matching is suggested, agents use a gradient-descent-like approach to minimize "balancing errors." If one agent is getting a "better deal" relative to their outside options than their partner is, they adjust the split until the benefits are equalized. This requires 2-hop information (knowing the states of a neighbor's other neighbors).

3. The Cascade Architecture

To find a Nash outcome, the authors "cascade" these systems. The stable matching dynamics run in the background, and agents use a local prediction mechanism to "guess" who their final partner will be. Even though matching variables converge asymptotically, agents can correctly predict their final partners in finite time, allowing the balancing dynamics to settle efficiently.

The mathematical framework utilizes Lyapunov stability theory and Filippov set-valued maps to prove convergence even when the underlying matching logic is discontinuous.

Simulation and Results

The algorithms were evaluated through a synthetic wireless communication simulation involving five single-antenna devices. These devices can pair up to act as a "virtual 2-antenna device," increasing channel capacity according to a logarithmic model. Cooperation costs are based on distance, defining the edges of the bargaining graph.

Key results include:

  • Convergence: Rigorous mathematical proof that the distributed dynamics always converge to a Nash bargaining outcome, provided one exists.
  • Performance Gains: In the 5-device scenario, distributed bargaining led to a 15.8% network-wide improvement in effective channel capacity.
  • Fairness: The Nash approach ensured that no device was worse off than if they had acted alone, even while some devices saw gains as high as 39.2%.
  • Robustness: Simulations demonstrated that the system reaches a neighborhood of the Nash outcome even under Gaussian noise, confirming the "well-posedness" of the continuous-time formulation.

Conclusion and Future Work

This work provides a provably correct way to reach fair and stable resource splits in distributed networks. However, some limitations remain. The balancing dynamics require 2-hop information, which may be costly in sparse or mobile networks. Additionally, the current framework is limited to dyadic (pair-wise) exchanges and assumes a static topology. Future research will focus on extending these algorithms to hypergraphs (multi-agent coalitions) and dynamically changing environments.

Summary updated

Abstract

This paper considers dyadic-exchange networks in which individual agents autonomously form coalitions of size two and agree on how to split a transferable utility. Valid results for this game include stable (if agents have no unilateral incentive to deviate), balanced (if matched agents obtain similar benefits from collaborating), or Nash (both stable and balanced) outcomes. We design provably-correct continuous-time algorithms to find each of these classes of outcomes in a distributed way. Our algorithmic design to find Nash bargaining solutions builds on the other two algorithms by having the dynamics for finding stable outcomes feeding into the one for finding balanced ones. Our technical approach to establish convergence and robustness combines notions and tools from optimization, graph theory, nonsmooth analysis, and Lyapunov stability theory and provides a useful framework for further extensions. We illustrate our results in a wireless communication scenario where single-antenna devices have the possibility of working as 2-antenna virtual devices to improve channel capacity.
BibTeX
@article{richert2016distributed,
  author = {Dean Richert and Jorge Cortés},
  title = {{Distributed bargaining in dyadic-exchange networks}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2016},
  url = {https://openreview.net/forum?id=VvDzmDBUeU},
}
Figure