On Ocotber 7th, 2016, Prof. Dr. Martin Hoefer (MPI Saarbrücken) will give a talk about "Secretary Markets with Local Information" in the context of the SFB 901.
Abstract:
The secretary model is a popular and well-studied approach to analyze online admission problems. In many markets, however, decisions about admission are made in a decentralized fashion with limited information. We address such scenarios in a basic model with a set of firms that each has a job to offer. n applicants arrive sequentially in random order. Upon arrival of an applicant, each firm decides whether or not to offer its job to the current applicant without information about other firms. The applicant accepts its most preferred offer (if any).
For this model, we analyze a thresholding-based algorithm with competitive ratio O(log n) that works in a very general sampling model. It can even be used by firms hiring several applicants based on a local matroid. In contrast, even in the basic model we show a lower bound of \Theta(log n/(log log n)) for all thresholding-based algorithms. Moreover, we provide secretary algorithms with constant competitive ratios in special cases.