Complexity of stability in trading networks

Fleiner, Tamás, Jankó, Zsuzsanna ORCID:, Schlotter, Ildikó Anna and Teytelboym, Alexander (2023) Complexity of stability in trading networks. International Journal of Game Theory, 52 . pp. 629-648. DOI

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL:


Efficient computability is an important property of solution concepts. We consider the computational complexity of finding and verifying various solution concepts in trading networks—multi-sided matching markets with bilateral contracts and without transferable utility—under the assumption of full substitutability of agents’ preferences. It is known that outcomes that satisfy trail stability always exist and can be found in linear time. However, we show that 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.

Item Type:Article
Uncontrolled Keywords:stability, trail stability, chain stability, supply chains, flow networks, market design,
JEL classification:C78 - Bargaining Theory; Matching Theory
L14 - Transactional Relationships; Contracts and Reputation; Networks
Divisions:Institute of Operations and Decision Sciences
Subjects:Commerce and tourism
Mathematics, Econometrics
Funders:MTA-BCE Strategic Interaction Research Group, BME-Artificial Intelligence FIKP grant of EMMI, BME NC TKP2020 grant of NKFIH Hungary, Economic and Social Research Council, ES/R007470/1
Projects:OTKA K128611, OTKA K143858, OTKA K124171, LP2021-2
ID Code:9600
Deposited By: MTMT SWORD
Deposited On:01 Mar 2024 09:22
Last Modified:01 Mar 2024 09:22

Repository Staff Only: item control page


Downloads per month over past year

View more statistics