-
作者：Perez-Salazar, Sebastian; Menache, Ishai; Singh, Mohit; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology; Microsoft
摘要：Cloud computing has motivated renewed interest in resource allocation problems with new consumption models. A common goal is to share a resource, such as CPU or I/O bandwidth, among distinct users with different demand patterns as well as different quality of service requirements. To ensure these service requirements, cloud offerings often come with a service level agreement (SLA) between the provider and the users. A SLA specifies the amount of a resource a user is entitled to utilize. In man...
-
作者：Beyhaghi, Hedyeh; Golrezaei, Negin; Leme, Renato Paes; Pai, Martin; Sivan, Balasubramanian
作者单位：Toyota Technological Institute - Chicago; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
摘要：We study revenue maximization through sequential posted-price (SPP) mechanisms in single-dimensional settings with n buyers and independent but not necessarily identical value distributions. We construct the SPP mechanisms by considering the best of two simple pricing rules: one that imitates the revenue optimal mechanism, namely, the Myersonian mechanism, via the taxation principle and the other that posts a uniform price. Our pricing rules are rather generalizable and yield the first improve...
-
作者：Calma, Angelito; Ho, William; Shao, Lusheng; Li, Huashan
作者单位：University of Melbourne; University of Melbourne
摘要：This paper is a retrospective look at 68 years of publication output of Operations Research, revealing changes in its publications, its authors, and their impact over time and how these changes might affect researchers and practitioners in the present. A total of 5,440 journal articles from its inception in 1952 to 2019 are used. The analysis initially focuses on the most studied topics and then continues with the top research methods and research problems investigated. The top contributing co...
-
作者：Cao, Zhigang; Chen, Bo; Chen, Xujin; Wang, Changjun
作者单位：Beijing Jiaotong University; University of Warwick; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Beijing University of Technology
摘要：We propose a game model for selfish routing of atomic agents, who compete for use of a network to travel from their origins to a common destination as quickly as possible. We follow a frequently used rule that the latency an agent experiences on each edge is a constant transit time plus a variable waiting time in a queue. A key feature that differentiates our model from related ones is an edge-based tie-breaking rule for prioritizing agents in queueing when they reach an edge at the same time....
-
作者：Eden, Alon; Feldman, Michal; Friedler, Ophir; Talgam-Cohen, Inbal; Weinberg, S. Matthew
作者单位：Harvard University; Tel Aviv University; Technion Israel Institute of Technology; Princeton University
摘要：We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation for the items may exhibit both substitutes and complements. We show that the better of selling the items separately and bundling them together-guarantees a Theta(d)-fraction of the optimal revenue, where d is a measure of the degree of complementarity; it extends prior work showing that the same simple mechanism achieves a constant-factor approximation when buyer valuations are subadditive (th...
-
作者：Zheng, Zemin; Lv, Jinchi; Lin, Wei
作者单位：Chinese Academy of Sciences; University of Science & Technology of China, CAS; University of Southern California; Peking University; Peking University
摘要：As a popular tool for producing meaningful and interpretable models, large-scale sparse learning works efficiently in many optimization applications when the underlying structures are indeed or close to sparse. However, naively applying the existing regularization methods can result in misleading outcomes because of model mis-specification. In this paper, we consider nonsparse learning under the factors plus sparsity structure, which yields a joint modeling of sparse individual effects and com...
-
作者：Ding, Yichuan; McCormick, S. Thomas; Nagarajan, Mahesh
作者单位：McGill University; University of British Columbia
摘要：We consider a one-sided bipartite matching queueing system (OBMQ) with customers and resources of multiple types, where different customer-resource combinations can generate different rewards. Each resource is allocated on arrival to the customer with the highest score (or index), which is the sum of the customer's waiting score and matching score, so we call it an M+W index. We assume that the waiting score is an increasing function of a customer's waiting time and that the matching score is ...
-
作者：Khaleghei, Akram; Kim, Michael Jong
作者单位：University of Toronto; University of British Columbia
摘要：We formulate a maintenance control model as an optimal stopping problem under partial observations. The key challenge in our formulation is that the underlying state process is not restricted to be Markovian but rather is allowed to follow a semi-Markov process, which is more realistic in practice. Consequently, the stopping problem is not representable as a partially observable Markov decision process (POMDP) with finite state space, a commonly adopted modeling framework in the maintenance op...
-
作者：Wu, Zijun; Moehring, Rolf H.; Chen, Yanyan; Xu, Dachuan
作者单位：Hefei University; Technical University of Berlin; Beijing University of Technology; Beijing University of Technology
摘要：We investigate the price of anarchy (PoA) in nonatomic congestion games when the total demand T gets very large. First results in this direction have recently been obtained by Colini-Baldeschi et al. (2016, 2017, 2020) for routing games and show that the PoA converges to one when the growth of the total demand T satisfies certain regularity conditions. We extend their results by developing a new framework for the limit analysis of the PoA that offers strong techniques such as the limit of game...
-
作者：Cen, Shicong; Cheng, Chen; Chen, Yuxin; Wei, Yuting; Chi, Yuejie
作者单位：Carnegie Mellon University; Stanford University; Princeton University; University of Pennsylvania
摘要：Natural policy gradient (NPG) methods are among the most widely used policy optimization algorithms in contemporary reinforcement learning. This class of methods is often applied in conjunction with entropy regularization-an algorithmic scheme that encourages exploration-and is closely related to soft policy iteration and trust region policy optimization. Despite the empirical success, the theoretical underpinnings for NPG methods remain limited even for the tabular setting. This paper develop...
