EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Complexity of stability in trading networks

Tamás Fleiner, Zsuzsanna Jankó, Ildikó Schlotter, Alexander Teytelboym

International Journal of Game Theory · 2023-09 · 52 (3) · 629-648

DOI: 10.1007/s00182-022-00833-0 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Game Theory, online erschienen am 08.04.2023. Verfasst von Tamás Fleiner und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Economic and Social Research Council, Országos Tudományos Kutatási Alapprogramok, Hungarian Scientific Research Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 $${{\textsf{N}}}{{\textsf{P}}}$$ N P -hard problem in trading networks. We also show that even verifying whether a given outcome is stable is $${{\textsf{N}}}{{\textsf{P}}}$$ N P -hard in trading networks.

Förderung

  • Economic and Social Research Council
  • Országos Tudományos Kutatási Alapprogramok
  • Hungarian Scientific Research Fund
  • Magyar Tudományos Akadámia
  • Magyar Tudományos Akadémia

Zitieren

APA

Fleiner, T., Jankó, Z., Schlotter, I., & Teytelboym, A. (2023). Complexity of stability in trading networks. International Journal of Game Theory, 52(3), 629-648. https://doi.org/10.1007/s00182-022-00833-0

Vancouver

Fleiner T, Jankó Z, Schlotter I, Teytelboym A. Complexity of stability in trading networks. International Journal of Game Theory. 2023;52(3):629-648. doi:10.1007/s00182-022-00833-0

BibTeX
@article{Fleiner2023,
  author = {Fleiner, Tamás and Jankó, Zsuzsanna and Schlotter, Ildikó and Teytelboym, Alexander},
  title = {Complexity of stability in trading networks},
  journal = {International Journal of Game Theory},
  year = {2023},
  volume = {52},
  number = {3},
  pages = {629--648},
  doi = {10.1007/s00182-022-00833-0}
}
Kostenlos starten →