Cover Image

Complexity of stability in trading networks

CC BY

Saved in:
Bibliographic Details
Main Authors: Tamás, Fleiner, Zsuzsanna, Jankó, Ildikó, Schlotter
Format: Book
Language:English
Published: Springer 2023
Subjects:
NP -hard problem
trading networks
Online Access:https://link.springer.com/article/10.1007/s00182-022-00833-0
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7732
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-7732
record_format dspace
spelling oai:localhost:PNK-77322023-04-11T01:41:48Z Complexity of stability in trading networks Tamás, Fleiner Zsuzsanna, Jankó Ildikó, Schlotter NP -hard problem trading networks CC BY 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. 2023-04-11T01:41:48Z 2023-04-11T01:41:48Z 2023 Book https://link.springer.com/article/10.1007/s00182-022-00833-0 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7732 en application/pdf Springer
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic NP -hard problem
trading networks
spellingShingle NP -hard problem
trading networks
Tamás, Fleiner
Zsuzsanna, Jankó
Ildikó, Schlotter
Complexity of stability in trading networks
description CC BY
format Book
author Tamás, Fleiner
Zsuzsanna, Jankó
Ildikó, Schlotter
author_facet Tamás, Fleiner
Zsuzsanna, Jankó
Ildikó, Schlotter
author_sort Tamás, Fleiner
title Complexity of stability in trading networks
title_short Complexity of stability in trading networks
title_full Complexity of stability in trading networks
title_fullStr Complexity of stability in trading networks
title_full_unstemmed Complexity of stability in trading networks
title_sort complexity of stability in trading networks
publisher Springer
publishDate 2023
url https://link.springer.com/article/10.1007/s00182-022-00833-0
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7732
_version_ 1762909081702498304
score 8.891145

Similar Items