Everyone is welcome to attend the next N&O seminar with Pieter Kleer with the title 'Optimal Stopping Theory for a Distributionally Robust Seller'.
The talk will take place in L016 at CWI, along with zoom support for remote participants. For more information and registration to get the Zoom link via e-mail, please contact Willem Feijen (willem.feijen at cwi.nl), Samarth Tiwari (samarth.tiwari at cwi.nl) or Sven Polak (sven.polak at cwi.nl).
Abstract: We consider the classical problem of selling an item in an online fashion. Buyers arrive one-by-one and report a value, drawn from a known value distribution, that they are willing to pay for the item. Upon arrival of a buyer, we have to irrevocably decide whether or not to sell the item to them. The goal is to design a stopping rule (specifying which buyer to sell to) that maximizes the seller's expected payoff, i.e., the value at which the item is sold.
The assumption that the seller knows the full value distributions of the buyers is often unrealistic in practice. Therefore, we consider a more robust version of the problem by taking a maximin perspective. We assume that the value distributions of the buyers come from a so-called ambiguity set, which is often characterized by certain summary statistics, such as the mean and variance of the (unknown) value distributions. The robust version of this problem can be seen as a game between the seller and nature (the adversary): The seller first chooses a stopping rule, after which nature chooses value distributions from the ambiguity set that minimize the seller's expected payoff under the chosen stopping rule. The goal of the seller is now to choose a stopping rule that maximizes their expected maximin payoff.
As our first main result, we show that for arbitrary ambiguity sets the optimal robust stopping rule is a threshold-based strategy determined by means of backwards induction. Such a stopping rule is described by a threshold for every buyer, and we sell the item to a buyer if their value exceeds the threshold. This strategy is a natural analogue of the optimal stopping rule for the classical version of the problem, which is well-known to be solvable by means of backwards induction. Secondly, for various ambiguity sets described by mean and dispersion (variance or mean absolute deviation) information of the unknown distributions, we give closed-form expressions for the optimal robust thresholds. One of our main tools here is the use of semi-infinite linear programs.
Joint work with Johan van Leeuwaarden (Tilburg University)
