-
作者：Gupta, Varun
作者单位：University of Chicago
摘要：In this paper, we prove the efficacy of a simple greedy algorithm for a finite horizon online resource allocation/matching problem when the corresponding static planning linear program (SPP) exhibits a nondegeneracy condition called the general position gap (GPG). The key intuition that we formalize is that the solution of the reward-maximizing SPP is the same as a feasibility linear program restricted to the optimal basic activities, and under GPG, this solution can be tracked with bounded re...
-
作者：Schulz, Andreas S.; Telha, Claudio
作者单位：Technical University of Munich; Technical University of Munich; Universidad de los Andes - Chile
摘要：Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are fundamental in inventory management, manufacturing, and logistics and capture these effects. However, finding an efficient algorithm that optimally solves these models or showing that none may exist have long been open regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint repleni...
-
作者：Keskin, N. Bora; Li, Meng
作者单位：Duke University; University of Houston System; University of Houston
摘要：. In this paper, we study a firm's dynamic pricing problem in the presence of unknown and time-varying heterogeneity in customers' preferences for quality. The firm offers a standard product as well as a premium product to deal with this heterogeneity. First, we consider a benchmark case in which the transition structure of customer heteroge-neity is known. In this case, we analyze the firm's optimal pricing policy and characterize its key structural properties. Thereafter, we investigate the ...
-
作者：Freund, Daniel; Lykouris, Thodoris; Weng, Wentao
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We study decentralized multiagent learning in bipartite queueing systems, a standard model for service systems. In particular, N agents request service from K servers in a fully decentralized way, that is, by running the same algorithm without communication. Previous decentralized algorithms are restricted to symmetric systems, have performance that is degrading exponentially in the number of servers, require communication through shared randomness and unique agent identities, and are computat...
-
作者：Paccagnan, Dario; Gairing, Martin
作者单位：Imperial College London; University of Liverpool
摘要：In this work, we address the problem of minimizing social cost in atomic congestion games. For this problem, we present lower bounds on the approximation ratio achievable in polynomial time and demonstrate that efficiently computable taxes result in polynomial time algorithms matching such bounds. Perhaps surprisingly, these results show that indirect interventions, in the form of efficiently computed taxation mechanisms, yield the same performance achievable by the best polynomial time algori...
