摘要翻译：
有效可计算性是匹配市场中解概念的一个重要性质。考虑了在代理偏好完全可替代的假设下，交易网络--双边合约的多侧匹配市场--中寻找和验证各种解概念的计算复杂性。已知满足轨迹稳定性的结果总是存在的，并且可以在线性时间内找到。这里我们考虑一个稍微强一点的解决方案概念，在这个概念中，代理可以同时提供上游和下游合同。我们证明了即使在我们的模型的一个特殊（流网络）情况下，判定满足此解概念的结果的存在性也是一个NP完全问题。因此，稳定结果的存在性--对任意代理集合的偏差免疫--在交易网络（和流网络）中也是一个NP难问题。最后，我们证明了在交易网络中，即使验证给定结果是否稳定也是NP完全的。
---
英文标题：
《Complexity of Stability in Trading Networks》
---
作者：
Tam\'as Fleiner, Zsuzsanna Jank\'o, Ildik\'o Schlotter and Alexander
  Teytelboym
---
最新提交年份：
2019
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computational Complexity        计算复杂度
分类描述：Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
涵盖计算模型，复杂度类别，结构复杂度，复杂度折衷，上限和下限。大致包括ACM学科类F.1（抽象设备的计算）、F.2.3（复杂性度量之间的权衡）和F.4.3（形式语言）中的材料，尽管形式语言中的一些材料可能更适合于计算机科学中的逻辑。在F.2.1和F.2.2中的一些材料可能也适用于这里，但更有可能以数据结构和算法作为主要主题领域。
--
一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--

---
英文摘要：
  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.
---
PDF链接：
https://arxiv.org/pdf/1805.08758