-
作者：Vera, Alberto; Banerjee, Siddhartha; Gurvich, Itai
作者单位：Cornell University; Northwestern University
摘要：We develop a framework for designing simple and efficient policies for a family of online allocation and pricing problems that includes online packing, budget-constrained probing, dynamic pricing, and online contextual bandits with knapsacks. In each case, we evaluate the performance of our policies in terms of their regret (i.e., additive gap) relative to an offline controller that is endowed with more information than the online controller. Our framework is based on Bellman inequalities, whi...
-
作者：Mueller, Alfred; Scarsini, Marco; Tsetlin, Ilia; Winkler, Robert L.
作者单位：Universitat Siegen; Luiss Guido Carli University; INSEAD Business School; Duke University
摘要：Consider a choice between two random variables, for which only means and variances are known. Is it possible to rank them by putting some constraints on risk preferences? We provide such a ranking by bounding how much marginal utility can change. Such bounds enable us to rank all distributions with given means and variances by first-order almost-stochastic dominance. We show how our results can be used to compare a risky project and a sure payoff and also provide a new connection between the S...
-
作者：Krishnasamy, Subhashini; Sen, Rajat; Johari, Ramesh; Shakkottai, Sanjay
作者单位：University of Texas System; University of Texas Austin; Stanford University
摘要：Consider a queueing system consisting of multiple servers. Jobs arrive over time and enter a queue for service; the goal is to minimize the size of this queue. At each opportunity for service, at most one server can be chosen, and at most one job can be served. Service is successful with a probability (the service probability) that is a priori unknown for each server. An algorithm that knows the service probabilities (the genie) can always choose the server of highest service probability. We s...
-
作者：Ahani, Narges; Andersson, Tommy; Martinello, Alessandro; Teytelboym, Alexander; Trapp, Andrew C.
作者单位：Worcester Polytechnic Institute; Lund University; University of Oxford; Worcester Polytechnic Institute
摘要：Every year, tens of thousands of refugees are resettled to dozens of host countries. Although there is growing evidence that the initial placement of refugee families profoundly affects their lifetime outcomes, there have been few attempts to optimize resettlement decisions. We integrate machine learning and integer optimization into an innovative software tool, Annie (TM) Matching and Outcome Optimization for Refugee Empowerment (Annie (TM) MOORE), that assists a U.S. resettlement agency with...
-
作者：Terca, Goncalo; Wozabal, David
作者单位：Technical University of Munich
摘要：We propose a method to compute derivatives of multistage linear stochastic optimization problems with respect to parameters that influence the problem's data. Our results are based on classical envelope theorems and can be used in problems directly solved via their deterministic equivalents as well as in stochastic dual dynamic programming for which the derivatives of the optimal value are sampled. We derive smoothness properties for optimal values of linear optimization problems, which we use...
-
作者：Wei, Lai; Jasin, Stefanus; Xin, Linwei
作者单位：Boston College; University of Michigan System; University of Michigan; University of Chicago
摘要：Service-level constraint is often used as a metric to directly control the quality of service (e.g., managing the probability of stockout) in practice. Many inventory problems with service-level constraints are often difficult to solve and are typically approximated by deterministic formulations. This raises an important question regarding the quality of such an approach. To shed light on this question, in this paper, we consider two simplified yet fundamental inventory models (with backorder ...
-
作者：de Kemp, A. Madelon; Mandjes, Michel; Olver, Neil
作者单位：University of Amsterdam; University of London; London School Economics & Political Science
摘要：A classic problem in appointment scheduling with applications in healthcare concerns the determination of the patients' arrival times that minimize a cost function that is a weighted sum of mean waiting times and mean idle times. One aspect of this problem is the sequencing problem, which focuses on ordering the patients. We assess the performance of the smallest-variance-first (SVF) rule, which sequences patients in order of increasing variance of their service durations. Although it is known...
-
作者：Ciocan, Dragos Florin; Iyer, Krishnamurthy
作者单位：INSEAD Business School; University of Minnesota System; University of Minnesota Twin Cities
摘要：We consider an ad network's problem of allocating the auction for each individual impression to an optimal subset of advertisers with the goal of revenue maximization. This is a variant of bipartite matching except that advertisers may strategize by choosing their bidding profiles and their total budget. Because the ad network's allocation rule affects the bidders' strategies, equilibrium analysis is challenging. We show that this analysis is tractable when advertisers face a linear budget cos...
-
作者：Anton, Elene; Ayesta, Urtzi; Jonckheere, Matthieu; Verloop, Ina Maria
作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National Polytechnique de Toulouse; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute of Physics (INP); Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Basque Foundation for Science; University of Basque Country; Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); University of Buenos Aires
摘要：We investigate the stability condition of redundancy-d multiserver systems. Each server has its own queue and implements popular scheduling disciplines such as first-come-first-serve (FCFS), processor sharing (PS), and random order of service (ROS). New jobs arrive according to a Poisson process, and copies of each job are sent to d servers chosen uniformly at random. The service times of jobs are assumed to be exponentially distributed. A job departs as soon as one of its copies finishes serv...
-
作者：Kim, Anthony; Mirrokni, Vahab; Nazerzadeh, Hamid
作者单位：Amazon.com; Alphabet Inc.; Google Incorporated; University of Southern California
摘要：We present a formal study of first-look and preferred deals that are a recently introduced generation of contracts for selling online advertisements, which generalize traditional reservation contracts and are suitable for advertisers with advanced targeting capabilities. Under these deals, one or more advertisers gain priority access to an inventory of impressions before others and can choose to purchase in real time. In particular, we propose constant-factor approximation algorithms for maxim...
