Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 8 of 8 for “"Prophet Inequalities"”.
-
Non-Adaptive Matroid Prophet Inequalities
We consider the problem of matroid prophet inequalities. This problem has been ex- tensively studied in case of adaptive prices, with [KW12] obtaining a tight 2-competitive mechanism for all the matroids. However, the case non-adaptive is far from resolved, although there is a known constant- …
-
Prophet Inequalities for Multivariate Random Variables with Cost for Observations
In prophet problems, two players with different levels of information make decisions to optimize their return from an underlying optimal stopping problem. The player with more information is called the "prophet" while the player with less information is known as the "gambler." In this thesis, as in …
-
Online contention resolution schemes for matchings and matroids
… and their intersections. OCRSs immediately imply prophet inequalities in Bayesian online selection problem. They also have other important applications such as stochastic probing and oblivious posted price mechanisms. We present several novel OCRSs which improve the current state-of-the-art …
-
Algorithms for Two-sided Online Marketplaces
… problem is an extension of the multiple-choice prophet inequality to the setting in which each item might disappear after an a priori unknown amount of time. This can be viewed as a way to model the supply uncertainty arising because of the fact that different sellers might depart after some …
-
Essays In Optimization Methods For Resource Allocation
… the presence of uncertainty for future rewards. Prophet inequalities involve a set of results relating the reward attained in an on-line selection setting to the reward generated by a prophet possessing perfect information. I develop new, approximately efficient rules leveraging the reduced-form …
-
Algorithms for Online Marketplaces: New Approaches to Order Fulfillment and Recommendation Systems
… that combine randomized fulfillment strategies, prophet inequalities, and subgradient methods. Our approaches not only achieve asymptotic optimality and strong approximation guarantees in the multi-item fulfillment setting, but also provide insights on how to construct robust policies in …
-
Algorithm and Mechanism Design in Decision-making Environments
… In the first part of this thesis we focus on Prophet Inequalities, a collection of results for online decision-making problems under uncertainty and we explore two aspects of those problems. The first has to do with the power of the decision-maker to decide the order in which to inspect parts …
-
Optimal stopping problems and combinatorial optimization under uncertainty
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-09-16 without embargo terms