# Secretary problems, prophet inequalities, and contention resolution schemes

## Abstract/Contents

- Abstract
- In this thesis, we study online selection problems, focusing on variants of secretary problems, prophet inequalities, and contention resolution schemes. In chapter 2, we study variants of the secretary problem where the observations are draws from distributions, and we wish to find algorithms which maximize the probability of selecting the largest draw. In case we have access to the distributions and the draws are randomly ordered, we give an optimal algorithm with success probability 0.5801, matching the case where the distributions are identical, and establishing a conjecture of Esfandiari et al. We then study variants where we only have sample access to the distributions. Our main results in the context are: (i) an algorithm with success probability 0.5009 in the single sample random order case (nearly matching the upper bound of 0.5024); (ii) an optimal algorithm with success probability 0.25 in the single sample adversarial order case. In chapter 3, we study prophet inequalities with cancellation costs. Most of the literature on online selection problems focuses on settings with irrevocable decisions. In contrast, we consider a model in which after deciding to select some variable, we may still choose to discard it and accept another variable at a cost of (a parameter) f times the accepted variable. The goal is to maximize the expected value of the final accepted variable minus the cost of discarding all the other accepted variables. Our main results are: (i) in case f > 1, an optimal prophet inequality with competitive ratio (1+f)/(1+2f); (ii) in case f is near 0, an asymptotically optimal prophet inequality. In chapter 4, we study contention resolution schemes (CRSs) for matchings focusing on the regime with vanishing edge probabilities. Our main results in this regime are: (i) an optimal 0.544-selectable CRS in the offline case; (ii) a conjecturally optimal 0.382-selectable OCRS in the adversarial order case, along with an upper bound of 0.390 on the selectability; (iii) an optimal 0.5-selectable RCRS in the random order case; and (iv) a 0.510-selectable CRS in the free order case. In the non-vanishing regime, we construct a 0.509-selectable contention resolution scheme for bipartite matchings, establishing for the first time, a separation between offline and random order online contention resolution schemes.

## Description

Type of resource | text |
---|---|

Form | electronic resource; remote; computer; online resource |

Extent | 1 online resource. |

Place | California |

Place | [Stanford, California] |

Publisher | [Stanford University] |

Copyright date | 2024; ©2024 |

Publication date | 2024; 2024 |

Issuance | monographic |

Language | English |

## Creators/Contributors

Author | Nuti, Pranav |
---|---|

Degree supervisor | Vondrák, Jan, (Mathematician) |

Thesis advisor | Vondrák, Jan, (Mathematician) |

Thesis advisor | Fox, Jacob, 1984- |

Thesis advisor | Soundararajan, Kannan, 1973- |

Degree committee member | Fox, Jacob, 1984- |

Degree committee member | Soundararajan, Kannan, 1973- |

Associated with | Stanford University, School of Humanities and Sciences |

Associated with | Stanford University, Department of Mathematics |

## Subjects

Genre | Theses |
---|---|

Genre | Text |

## Bibliographic information

Statement of responsibility | Pranav Nuti. |
---|---|

Note | Submitted to the Department of Mathematics. |

Thesis | Thesis Ph.D. Stanford University 2024. |

Location | https://purl.stanford.edu/jb690vg6095 |

## Access conditions

- Copyright
- © 2024 by Pranav Nuti

## Also listed in

Loading usage metrics...