Minimal extending sets in tournaments

Felix Brandt, Paul Harrenstein and Hans Georg Seedig

Mathematical Social Sciences, 2017, vol. 87, issue C, 55-63

Abstract: 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.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489617300422
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:87:y:2017:i:c:p:55-63

DOI: 10.1016/j.mathsocsci.2016.12.007

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().