Stationary models for prophet inequality and matching problems
Abstract/Contents
- Abstract
- Individuals and companies are increasingly faced with the challenge of making decisions with only partial information about the future. This is only further complicated when decision makers care less about immediate gains than long-term outcomes. With this motivation, in this thesis, we study online algorithms, where inputs are revealed over time and must be responded to immediately and irrevocably. In particular, we consider two continuous-time, infinite time horizon counterparts of classic online matching problems, which we refer to as the stationary prophet inequality problem and the dynamic spatial matching problem. In both problems, we investigate the performance of simple and natural algorithms, with the main challenge being how to (approximately) characterize the stationary distributions under these algorithms. We take two different approaches. For the stationary prophet inequality problem, we use a linear program benchmark and techniques from queueing theory. For the dynamic spatial matching problem, we provide a novel reduction to an instance of a Coagulation-Fragmentation Process (CFP), which we indirectly analyze via a simpler CFP and recently developed techniques for the study of their equilibrium solutions.
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 | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Kessel, Kristen Elizabeth |
|---|---|
| Degree supervisor | Saberi, Amin |
| Thesis advisor | Saberi, Amin |
| Thesis advisor | Ashlagi, Itai |
| Thesis advisor | Lo, Irene, (Management science professor) |
| Degree committee member | Ashlagi, Itai |
| Degree committee member | Lo, Irene, (Management science professor) |
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Kristen Kessel. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/dn617fg6052 |
Access conditions
- Copyright
- © 2022 by Kristen Elizabeth Kessel
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...