首页 | 本学科首页   官方微博 | 高级检索  
     


A computational analysis of the tournament equilibrium set
Authors:Felix Brandt  Felix Fischer  Paul Harrenstein  Maximilian Mair
Affiliation:1. Institut für Informatik, Ludwig-Maximilians-Universit?t München, Munich, Germany
2. Mathematisches Institut, Ludwig-Maximilians-Universit?t München, Munich, Germany
Abstract:A recurring theme in the mathematical social sciences is how to select the “most desirable” elements given a binary dominance relation on a set of alternatives. Schwartz’s tournament equilibrium set (TEQ) ranks among the most intriguing, but also among the most enigmatic, tournament solutions proposed so far. Due to its unwieldy recursive definition, little is known about TEQ. In particular, its monotonicity remains an open problem to date. Yet, if TEQ were to satisfy monotonicity, it would be a very attractive solution concept refining both the Banks set and Dutta’s minimal covering set. We show that the problem of deciding whether a given alternative is contained in TEQ is NP-hard, and thus does not admit a polynomial-time algorithm unless P equals NP. Furthermore, we propose a heuristic that significantly outperforms the naive algorithm for computing TEQ.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号