TY - JOUR

T1 - A computational analysis of the tournament equilibrium set

AU - Brandt, Felix

AU - Fischer, Felix

AU - Harrenstein, Paul

AU - Mair, Maximilian

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77952551361&partnerID=8YFLogxK

U2 - 10.1007/s00355-009-0419-z

DO - 10.1007/s00355-009-0419-z

M3 - Article

AN - SCOPUS:77952551361

SN - 0176-1714

VL - 34

SP - 597

EP - 609

JO - Social Choice and Welfare

JF - Social Choice and Welfare

IS - 4

ER -