Dynamics of Coalition Formation in Combinatorial Trading

Yiming Ye, Yuhai TuIJCAI 2003

Abstract

This study explores the application of statistical physics principles to model coalition formation among autonomous agents in combinatorial marketplaces. By conceptualizing price incentives as "energy" and employing dynamic transition equations, the research provides a macroscopic framework for predicting the evolution of buyer groups. The findings indicate that agent-mediated trading effectively reduces average costs for participants and leads the market toward a stable equilibrium state.

Introduction

In combinatorial markets, retailers often offer discounts for bundles of complementary goods, such as travel packages or furniture sets. For individual buyers, the challenge lies in forming "buying groups" or coalitions to unlock these discounts. While previous research has focused on coalition stability (game theory) or communication overhead (multi-agent systems), the dynamic process of how large populations of agents transition between groups remains under-explored. This paper addresses this gap by modeling the movement of agents over time and identifying the resulting market equilibrium.

Methodology

The authors propose a physics-based dynamic model to capture agent movement. The market state is represented as a lattice where each point (nA, nB) denotes a coalition with nA agents of type A and nB agents of type B. Agents are assumed to join or leave coalitions incrementally, creating a flow between adjacent lattice points.

State transition diagram illustrating the flow of agents between coalitions of different sizes (nA, nB).

The rate at which agents join a group is modeled using a Boltzmann distribution, where the "energy" corresponds to the price change (ΔP). A significant price drop increases the probability of agents joining. Conversely, an "escape rate" (K_escape) represents the constant tendency of agents to leave a coalition in search of better deals. Macroscopic differential equations track the distribution of coalition sizes while maintaining a constant total agent population.

Experimental Framework

The theoretical model was validated through synthetic simulations. The environment consisted of a fixed population (mA = 50, mB = 50) with specific retailer preferences, such as a target ratio r0 for item bundles. Price penalties were applied if coalitions deviated significantly from this preferred ratio, creating a complex incentive landscape.

Key Insights and Results

A central finding is that financial incentives act as a physical force driving the system toward equilibrium. The inclusion of a "preferred ratio" ensures that the most efficient coalitions are not necessarily the largest, but the most balanced. Entropy was used to measure stability; as the system transitioned from a chaotic initial state to a structured equilibrium, entropy increased and eventually plateaued.

Evolution of the coalition size distribution from iteration 10 to 10,000, demonstrating convergence toward a macroscopic equilibrium.

Simulations revealed that average prices consistently decreased as agents organized into coalitions. Regardless of the initial state, the system reliably converged to a macroscopic equilibrium. When the retailer's preferred ratio was asymmetric (e.g., r0 = 0.5), the resulting agent distribution reflected this, showing that certain agent types become more critical for bundle formation.

Conclusion and Future Directions

The study demonstrates that local agent logic—based only on immediate price changes—can lead to global market efficiency. However, the current model assumes static retailer pricing and simple agent acceptance logic. Future work could explore dynamic pricing strategies where retailers adjust discounts in real-time, and more sophisticated agent behaviors where coalitions can reject members that negatively impact their price ratios. Additionally, extending the model to N types of goods and open systems with fluctuating agent populations remains a key area for further research.

Summary updated

BibTeX
@inproceedings{ye2003dynamics,
  author = {Yiming Ye and Yuhai Tu},
  title = {{Dynamics of Coalition Formation in Combinatorial Trading}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure