Abstract
We consider a model of matching in trading networks in which firms can enter into bilateral contracts. In trading networks, stable outcomes, which are immune to deviations of arbitrary sets of firms, may not exist. We define a solution concept called trail-stability. Trail-stable outcomes are immune to consecutive, pairwise deviations between linked firms. We show that any trading network with bilateral contracts has a trail-stable outcome whenever firms’ choice functions satisfy the full substitutability condition.
However, the existence of stable outcomes—immune to deviations by arbitrary sets of agents—is an NP-hard problem in trading networks. We also show that even verifying whether a given outcome is stable is NP-hard in trading networks.