Veranstaltungen

In a basic online selection problem, we observe a sequence of numbers one-by-one, and we have to make an irrevocable decision to select one of the numbers. Both the secretary problem and the prophet problem are of this type, but they differ along a few dimensions: the order in which the numbers appear, how much information we have about the numbers before we observe them, and the objective we desire to maximize. Several models that are in between the secretary and prophet problems along these dimensions have previously been investigated. In this talk, I will say a little bit about these different models, and then explain how we can use Ramsey’s theorem (for hypergraphs) to obtain optimal results for one such model. This model has an interpretation as a simple card game.