Joshua Gardner will present his MSE talk "The Prophet Paradox: Optimal Stopping with Multi-Dimensional Comparative Loss Aversion." on April 22, 2022 at 1:50pm via Zoom
Committee members: Matt Weinberg (adviser) and Mark Braverman (reader)
All are welcome to attend.
Abstract:
Recent work by Kleinberg et al. [9] explores the effects of loss aversion and reference dependence on the
prophet inequality problem, where an online decision maker sees options one by one in sequence and must
decide immediately whether to select the current option or forego it and lose it forever. In their model,
the online decision-maker forms a reference point equal to the best candidate previously rejected, and the
decision-maker suffers from loss aversion based on the quality of their reference point, and a parameter 1
that quantifies their loss aversion. We consider the same prophet inequality setup, but with options that have
multiple features. The decision maker still forms a reference point, and still suffers loss aversion in comparison
to that reference point as a function of 1, but now that reference point is a (hypothetical) combination of the
best candidate seen so far in each feature.
Despite having the same basic prophet inequality setup and model of loss aversion, conclusions in our
multi-dimensional model differs drastically from the one-dimensional model of Kleinberg et al. [9]. For
example, Kleinberg et al. [9] gives a tight closed-form on the competitive ratio that an online decision-maker
can achieve as a function of 1, for any 1 ≥ 0. In our multi-dimensional model, there is a sharp phase transition:
if k denotes the number of dimensions, then when ^ ≥ 7_,, no non-trivial competitive ratio is possible. On
the other hand, when 1 <E, we give a tight bound on the achievable competitive ratio (similar to [91).
As another example, 9 uncovers an exponential improvement in their competitive ratio for the random-
order vs. worst-case prophet inequality problem. In our model with k ≥ 2 dimensions, the gap is at most a
constant-factor. We uncover several additional key differences in the multi- and single-dimensional models.