Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProphets and Secretaries with Overbooking
67
0
0.0
(
0
)
Added by
Tomer Ezra
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the $ell-out-of-k$ setting, where the decision maker can select up to $k$ elements immediately and irrevocably, but her performance is measured by the top $ell$ elements in the selected set. Equivalently, the decision makes can hold up to $ell$ elements at any given point in time, but can make up to $k-ell$ returns as new elements arrive. We give upper and lower bounds on the competitive ratio of $ell$-out-of-$k$ prophet and secretary scenarios. These include a single-sample prophet algorithm that gives a competitive ratio of $1-ellcdot e^{-Thetaleft(frac{left(k-ellright)^2}{k}right)}$, which is asymptotically tight for $k-ell=Theta(ell)$. For secretary settings, we devise an algorithm that obtains a competitive ratio of $1-ell e^{-frac{k-8ell}{2+2ln ell}} - e^{-k/6}$, and show that no secretary algorithm obtains a better ratio than $1-e^{-k}$ (up to negligible terms). In passing, our results lead to an improvement of the results of Assaf et al. [2000] for $1-out-of-k$ prophet scenarios. Beyond the contribution to online algorithms and optimal stopping theory, our results have implications to mechanism design. In particular, we use our prophet algorithms to derive {em overbooking} mechanisms with good welfare and revenue guarantees; these are mechanisms that sell more items than the sellers capacity, then allocate to the agents with the highest values among the selected agents.
rate research
Read More
We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. Agent departures are not announced in advance. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically.
In this work, we study a scenario where a publisher seeks to maximize its total revenue across two sales channels: guaranteed contracts that promise to deliver a certain number of impressions to the advertisers, and spot demands through an Ad Exchange. On the one hand, if a guaranteed contract is not fully delivered, it incurs a penalty for the publisher. On the other hand, the publisher might be able to sell an impression at a high price in the Ad Exchange. How does a publisher maximize its total revenue as a sum of the revenue from the Ad Exchange and the loss from the under-delivery penalty? We study this problem parameterized by emph{supply factor $f$}: a notion we introduce that, intuitively, captures the number of times a publisher can satisfy all its guaranteed contracts given its inventory supply. In this work we present a fast simple deterministic algorithm with the optimal competitive ratio. The algorithm and the optimal competitive ratio are a function of the supply factor, penalty, and the distribution of the bids in the Ad Exchange. Beyond the yield optimization problem, classic online allocation problems such as online bipartite matching of [Karp-Vazirani-Vazirani 90] and its vertex-weighted variant of [Aggarwal et al. 11] can be studied in the presence of the additional supply guaranteed by the supply factor. We show that a supply factor of $f$ improves the approximation factors from $1-1/e$ to $f-fe^{-1/f}$. Our approximation factor is tight and approaches $1$ as $f to infty$.
People are often reluctant to sell a house, or shares of stock, below the price at which they originally bought it. While this is generally not consistent with rational utility maximization, it does reflect two strong empirical regularities that are central to the behavioral science of human decision-making: a tendency to evaluate outcomes relative to a reference point determined by context (in this case the original purchase price), and the phenomenon of loss aversion in which people are particularly prone to avoid outcomes below the reference point. Here we explore the implications of reference points and loss aversion in optimal stopping problems, where people evaluate a sequence of options in one pass, either accepting the option and stopping the search or giving up on the option forever. The best option seen so far sets a reference point that shifts as the search progresses, and a biased decision-makers utility incurs an additional penalty when they accept a later option that is below this reference point. We formulate and study a behaviorally well-motivated version of the optimal stopping problem that incorporates these notions of reference dependence and loss aversion. We obtain tight bounds on the performance of a biased agent in this model relative to the best option obtainable in retrospect (a type of prophet inequality for biased agents), as well as tight bounds on the ratio between the performance of a biased agent and the performance of a rational one. We further establish basic monotonicity results, and show an exponential gap between the performance of a biased agent in a stopping problem with respect to a worst-case versus a random order. As part of this, we establish fundamental differences between optimal stopping problems for rational versus biased agents, and these differences inform our analysis.
Martin Weitzmans Pandoras problem furnishes the mathematical basis for optimal search theory in economics. Nearly 40 years later, Laura Doval introduced a version of the problem in which the searcher is not obligated to pay the cost of inspecting an alternatives value before selecting it. Unlike the original Pandoras problem, the version with nonobligatory inspection cannot be solved optimally by any simple ranking-based policy, and it is unknown whether there exists any polynomial-time algorithm to compute the optimal policy. This motivates the study of approximately optimal policies that are simple and computationally efficient. In this work we provide the first non-trivial approximation guarantees for this problem. We introduce a family of committing policies such that it is computationally easy to find and implement the optimal committing policy. We prove that the optimal committing policy is guaranteed to approximate the fully optimal policy within a $1-frac1e = 0.63ldots$ factor, and for the special case of two boxes we improve this factor to 4/5 and show that this approximation is tight for the class of committing policies.
Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the bodys ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
