2022/05/17 by Hans Ulrich Simon, Simon, Hans Ulrich
Decision Sciences · Computer Science · #Auction Theory and Applications #Machine Learning and Algorithms #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2205.08357
A tournament is said to have the Sk-property if, for any set of k players, there is another player who beats them all. Minimum tournaments having this property have been explored very well in the 1960's and the early 1970's. In this paper, we define a strengthening of the Sk-property that we name "strong Sk-property". We show, first, that several basic results on the weaker notion remain valid for the stronger notion (and the corresponding modification of the proofs requires only little extra-effort). Second, it is demonstrated that the stronger notion has applications in the area of Teaching. Specifically, we present an infinite family of concept classes all of which can be taught with a single example in the No-Clash model of teaching while, in order to teach a class \cC of this family in the recursive model of teaching, order of log|\cC| many examples are required. This is the first paper that presents a concrete and easily constructible family of concept classes which separates the No-Clash from the recursive model of teaching by more than a constant factor. The separation by a logarithmic factor is remarkable because the recursive teaching dimension is known to be bounded by log |\cC| for any concept class \cC.