Complexity of Stability in Trading Networks

• Tác giả: Tamás Fleiner, Zsuzsanna Jankó, Ildikó Schlotter, Alexander Teytelboym
• Ngôn ngữ: eng
• Ký hiệu phân loại: 003.72 Systems
• Thông tin xuất bản: 2018
• Bộ sưu tập: Metadata
• ID: 161947

Tóm tắt

Comment: 19 pagesEfficient 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.