-
作者：Lam, Henry; Zhang, Junhui
作者单位：Columbia University; Columbia University
摘要：We consider stochastic gradient estimation using only black-box function evaluations, where the function argument lies within a probability simplex. This problem is motivated from gradient-descent optimization procedures in multiple applications in distributionally robust analysis and inverse model calibration involving decision variables that are probability distributions. We are especially interested in obtaining gradient estimators where one or few sample observations or simulation runs app...
-
作者：MacRury, Calum; Ma, Will; Grammel, Nathaniel
作者单位：Columbia University; Columbia University; University System of Maryland; University of Maryland College Park
摘要：Online Contention Resolution Schemes (OCRSs) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRSs have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions-accept/reject, probing, pricing-in a unified manner. This paper analyzes OCRSs for resource constraints defined by matchings...
-
作者：Xie, Xinchang; Gurvich, Itai; Kucukyavuz, Simge
作者单位：Northwestern University; Northwestern University
摘要：We study the problem of dynamically allocating reusable resources to customers of n types. There are d pools of resources and a finite number of units from each resource. If a customer request is accepted, the decision maker collects a type-dependent reward, and the customer occupies, for a random service time, one unit from each resource in a set of these. Upon service completion, these resource units become available for future allocation. This is a loss network: requests that are not accept...
-
作者：Brubach, Brian; Grammel, Nathaniel; Ma, Will; Srinivasan, Aravind
作者单位：Wellesley College; University System of Maryland; University of Maryland College Park; Columbia University; Columbia University
摘要：We study generalizations of online bipartite matching in which each arriving vertex (customer) views a ranked list of offline vertices (products) and matches to (purchases) the first one they deem acceptable. The number of products that the customer has patience to view can be stochastic and dependent on the products seen. We develop a framework that views the interaction with each customer as an abstract resource consumption process and derive new results for these online matching problems un...
-
作者：Baveja, Alok; Chavan, Amit; Nikiforov, Andrei; Srinivasan, Aravind; Xu, Pan
作者单位：Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University Camden; Rutgers University New Brunswick; University System of Maryland; University of Maryland College Park; New Jersey Institute of Technology
摘要：Real-world network-optimization problems often involve uncertain parameters during the optimization phase. Stochastic optimization is a key approach introduced in the 1950s to address such uncertainty. This paper presents improved upper bounds on the number of samples required for the sample-average approximation method in stochastic optimization. It enhances the sample complexity of existing approaches in this setting, providing faster approximation algorithms for any method that employs this...
-
作者：Kerimov, Suleyman; Ashlagi, Itai; Gurvich, Itai
作者单位：Rice University; Stanford University; Northwestern University
摘要：We study centralized dynamic matching markets with finitely many agent types and heterogeneous match values. A network topology describes the pairs of agent types that can form a match and the value generated from each match. A matching policy is hindsight optimal if the policy can (nearly) maximize the total value simultaneously at all times. We find that suitably designed greedy policies are hindsight optimal in two-way matching networks. This implies that there is essentially no positive ex...
-
作者：Gryglewicz, Sebastian; Kolb, Aaron
作者单位：Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam; Indiana University System; Indiana University Bloomington; IU Kelley School of Business
摘要：We study dynamic entry deterrence through limit pricing in markets subject to persistent demand shocks. An incumbent is privately informed about its costs, high or low, and can deter a Bayesian potential entrant by setting its prices strategically. The entrant can irreversibly enter the market at any time for a fixed cost, earning a payoff that depends on the market conditions and the incumbent's unobserved type. Market demand evolves as a geometric Brownian motion. When market demand is low, ...
-
作者：Sun, Xu; Liu, Weiliang
作者单位：University of Miami; National University of Singapore
摘要：An on-demand workforce can greatly benefit a traditional call center by allowing it to adjust its service capacity on demand quickly. Despite its conceptual elegance, the operationalization of this process is challenging due to the various sources of randomness involved. The purpose of this paper is to help call centers enhance service levels while keeping operating expenses low by taking advantage of an on-call pool of temporary agents in day-to-day operations. For that purpose, we develop a ...
-
作者：Huang, Chengpiao; Wang, Kaizheng
作者单位：Columbia University; Columbia University
摘要：We develop a versatile framework for statistical learning in nonstationary environments. In each time period, our approach applies a stability principle to select a look-back window that maximizes the utilization of historical data while keeping the cumulative bias within an acceptable range relative to the stochastic error. Our theory showcases the adaptivity of this approach to unknown nonstationarity. We prove regret bounds that are minimax optimal up to logarithmic factors when the populat...
-
作者：Hu, Jiaqiao; Song, Meichen; Fu, Michael C.
作者单位：State University of New York (SUNY) System; Stony Brook University; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
摘要：We consider quantile optimization of black-box functions that are estimated with noise. We propose two new iterative three-timescale local search algorithms. The first algorithm uses an appropriately modified finite-difference-based gradient estimator that requires 2d + 1 samples of the black-box function per iteration of the algorithm, where d is the number of decision variables (dimension of the input vector). For higher-dimensional problems, this algorithm may not be practical if the black-...
