Fleiner, Tamás and Jankó, Zsuzsanna and Schlotter, Ildikó Anna and Teytelboym, Alexander (2023) Complexity of stability in trading networks. INTERNATIONAL JOURNAL OF GAME THEORY, 52. pp. 629-648. ISSN 0020-7276
|
Text
s00182-022-00833-0.pdf Available under License Creative Commons Attribution. Download (1MB) | Preview |
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: | Matching markets, Market design, Computational complexity, Trading networks, Flow networks, Supply chains, Trail stability, Chain stability, Stability, Contracts |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 05 Sep 2023 12:05 |
| Last Modified: | 05 Sep 2023 12:05 |
| URI: | http://real.mtak.hu/id/eprint/172672 |
Actions (login required)
 |
Edit Item |
