Complexity of Stability in Trading Networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2018
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909818967556096 |
|---|---|
| author | Fleiner, Tamás Jankó, Zsuzsanna Schlotter, Ildikó Teytelboym, Alexander |
| author_facet | Fleiner, Tamás Jankó, Zsuzsanna Schlotter, Ildikó Teytelboym, Alexander |
| contents | Efficient computability is an important property of solution concepts in matching markets. We consider the computational complexity of finding and verifying various solution concepts in trading networks-multi-sided matching markets with bilateral contracts-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. Here we consider a slightly stronger solution concept in which agents can simultaneously offer an upstream and a downstream contract. We show that deciding the existence of outcomes satisfying this solution concept is an NP-complete problem even in a special (flow network) case of our model. It follows that the existence of stable outcomes--immune to deviations by arbitrary sets of agents-is also an NP-hard problem in trading networks (and in flow networks). Finally, we show that even verifying whether a given outcome is stable is NP-complete in trading networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1805_08758 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Complexity of Stability in Trading Networks Fleiner, Tamás Jankó, Zsuzsanna Schlotter, Ildikó Teytelboym, Alexander Computational Complexity Computer Science and Game Theory Theoretical Economics Efficient computability is an important property of solution concepts in matching markets. We consider the computational complexity of finding and verifying various solution concepts in trading networks-multi-sided matching markets with bilateral contracts-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. Here we consider a slightly stronger solution concept in which agents can simultaneously offer an upstream and a downstream contract. We show that deciding the existence of outcomes satisfying this solution concept is an NP-complete problem even in a special (flow network) case of our model. It follows that the existence of stable outcomes--immune to deviations by arbitrary sets of agents-is also an NP-hard problem in trading networks (and in flow networks). Finally, we show that even verifying whether a given outcome is stable is NP-complete in trading networks. |
| title | Complexity of Stability in Trading Networks |
| topic | Computational Complexity Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/1805.08758 |