Main content start

Online selection problems and how Ramsey’s theorem solves a card game

Pranav Nuti (Stanford)
Thu, Mar 2 2023, 3:00pm

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.  Two classical problems of this type are the secretary problem and the prophet problem. 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.