Preference-based Teaching
  We introduce a new model of teaching named "preference-based teaching" and a
corresponding complexity parameter---the preference-based teaching dimension
(PBTD)---representing the worst-case number of examples needed to teach any
concept in a given concept class. Although the PBTD coincides with the
well-known recursive teaching dimension (RTD) on finite classes, it is
radically different on infinite ones: the RTD becomes infinite already for
trivial infinite classes (such as half-intervals) whereas the PBTD evaluates to
reasonably small values for a wide collection of infinite classes including
classes consisting of so-called closed sets w.r.t. a given closure operator,
including various classes related to linear sets over $\mathbb{N}_0$ (whose RTD
had been studied quite recently) and including the class of Euclidean
half-spaces. On top of presenting these concrete results, we provide the reader
with a theoretical framework (of a combinatorial flavor) which helps to derive
bounds on the PBTD.
