Complexity of stability in trading networks

Fleiner, Tamás, Jankó, Zsuzsanna ORCID: https://orcid.org/0000-0002-6149-4257, Schlotter, Ildikó Anna and Teytelboym, Alexander (2023) Complexity of stability in trading networks. International Journal of Game Theory, 52 . pp. 629-648. DOI https://doi.org/10.1007/s00182-022-00833-0

Preview

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

Official URL: https://doi.org/10.1007/s00182-022-00833-0

Abstract

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

DOI:

https://doi.org/10.1007/s00182-022-00833-0

ID Code:

9600

Deposited By:

MTMT SWORD

Deposited On:

01 Mar 2024 09:22

Last Modified:

01 Mar 2024 09:22