Title: Prophets, philosophers, and online algorithms
| Speaker: | David Wajc |
| Affiliation: | Technion |
| Location: | MC 6029 |
Abstract: In online Bayesian selection problems, a seller is faced with a stream of buyers arriving sequentially. Each arriving buyer makes, for each item on sale, a take-it-or-leave-it offer drawn from some known distribution, which the seller must immediately either accept or decline. It is common to compare the seller's benefit to the optimal offline solution, obtained by a "prophet'' who knows the future. However, the seller might not even be able to compete with the optimal online algorithm, which may be computationally intractable to run. In this case the optimal online algorithm is obtained by a "philosopher'' with sufficient time to think (compute). In this talk I will discuss some developments on online algorithms efficiently approximating this philosopher.