TY - JOUR

T1 - Minimal extending sets in tournaments

AU - Brandt, Felix

AU - Harrenstein, Paul

AU - Seedig, Hans Georg

N1 - Publisher Copyright:
© 2017 Elsevier B.V.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - Tournament solutions play an important role within social choice theory and the mathematical social sciences at large. In 2011, Brandt proposed a new tournament solution called the minimal extending set (ME) and an associated graph-theoretic conjecture. If the conjecture had been true, ME would have satisfied a number of desirable properties that are usually considered in the literature on tournament solutions. However, in 2013, the existence of an enormous counter-example to the conjecture was shown using a non-constructive proof. This left open which of the properties are actually satisfied by ME. It turns out that ME satisfies idempotency, irregularity, and inclusion in the iterated Banks set (and hence the Banks set, the uncovered set, and the top cycle). Most of the other standard properties (including monotonicity, stability, and computational tractability) are violated, but have been shown to hold for all tournaments on up to 12 alternatives and all random tournaments encountered in computer experiments.

AB - Tournament solutions play an important role within social choice theory and the mathematical social sciences at large. In 2011, Brandt proposed a new tournament solution called the minimal extending set (ME) and an associated graph-theoretic conjecture. If the conjecture had been true, ME would have satisfied a number of desirable properties that are usually considered in the literature on tournament solutions. However, in 2013, the existence of an enormous counter-example to the conjecture was shown using a non-constructive proof. This left open which of the properties are actually satisfied by ME. It turns out that ME satisfies idempotency, irregularity, and inclusion in the iterated Banks set (and hence the Banks set, the uncovered set, and the top cycle). Most of the other standard properties (including monotonicity, stability, and computational tractability) are violated, but have been shown to hold for all tournaments on up to 12 alternatives and all random tournaments encountered in computer experiments.

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

U2 - 10.1016/j.mathsocsci.2016.12.007

DO - 10.1016/j.mathsocsci.2016.12.007

M3 - Article

AN - SCOPUS:85015644687

SN - 0165-4896

VL - 87

SP - 55

EP - 63

JO - Mathematical social sciences

JF - Mathematical social sciences

ER -