-
作者：Giesecke, Kay; Shkolnik, Alexander
作者单位：Stanford University; University of California System; University of California Santa Barbara
摘要：Stochastic point process models of event timing are common in many areas, including finance, insurance, and reliability. Monte Carlo simulation is often used to perform computations for these models. The standard sampling algorithm, which is based on a time-change argument, is widely applicable but generates biased simulation estimators. This article develops and analyzes a change of probability measure that can reduce or even eliminate the bias without restricting the scope of the algorithm. ...
-
作者：Benjamin, Bachi; Shiran, Rachmilevitch
作者单位：University of Haifa
摘要：Myerson proved that every linear and weakly Paretian choice function is utilitarian. We revisit his model and result for the two-person case and supplement it with an only if direction. That is, we characterize the class of linear and weakly Paretian two-person choice functions. It turns out that these are the utilitarian functions with an egalitarian tie-breaking.
-
作者：Ghuge, Rohan; Nagarajan, Viswanath
作者单位：University of Michigan System; University of Michigan
摘要：We consider the following general network design problem. The input is an asymmetric metric (V, c), root r is an element of V, monotone submodular function f: 2(V) -> R+, and budget B. The goal is to find an r-rooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasi-polynomial time O(log k/log log k)-approximation algorithm for this problem, in which k <= |V| is the number of vertices in an optimal solution. As a consequence, we obtain an O(log (2)k/log lo...
-
作者：Pennanen, Teemu
作者单位：University of London; King's College London
摘要：This paper proposes a simple descriptive model of discrete-time double auction markets for divisible assets. As in the classical models of exchange economies, we consider a finite set of agents described by their initial endowments and preferences. Instead of the classical Walrasian-type market models, however, we assume that all trades take place in a centralized double auction where the agents communicate through sealed limit orders for buying and selling. We find that, under nonstrategic bi...
-
作者：Guo, Lei; Deng, Zhibin
作者单位：East China University of Science & Technology; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
摘要：We propose a new augmented Lagrangian (AL) method for solving the mathematical program with complementarity constraints (MPCC), where the complementarity constraints are left out of the AL function and treated directly. Two observations motivate us to propose this method: The AL subproblems are closer to the original problem in terms of the constraint structure; and the AL subproblems can be solved efficiently by a nonmonotone projected gradient method, in which we have closed-form solutions a...
-
作者：Zhao, Renbo
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We develop stochastic first-order primal-dual algorithms to solve a class of convex-concave saddle-point problems. When the saddle function is strongly convex in the primal variable, we develop the first stochastic restart scheme for this problem. When the gradient noises obey sub-Gaussian distributions, the oracle complexity of our restart scheme is strictly better than any of the existing methods, even in the deterministic case. Furthermore, for each problem parameter of interest, whenever t...
-
作者：Blanchet, Jose; Murthy, Karthyek; Zhang, Fan
作者单位：Stanford University; Singapore University of Technology & Design
摘要：We consider optimal transport-based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded in the DRO problem (e.g., strong convexity even if the non-DRO problem is not...
-
作者：Puha, Amber L.; Ward, Amy R.
作者单位：California State University System; California State University San Marcos; University of Chicago
摘要：We describe a fluid model with time-varying input that approximates a multiclass many-server queue with general reneging distribution and multiple customer classes (specifically, the multiclass G/GI/N+GI queue). The system dynamics depend on the policy, which is a rule for determining when to serve a given customer class. The class of admissible control policies are those that are head-of-the-line (HL) and nonanticipating. For a sequence of many-server queues operating under admissible HL cont...
-
作者：Bai, Kuang; Ye, Jane J.
作者单位：Hong Kong Polytechnic University; University of Victoria
摘要：The bilevel program is an optimization problem in which the constraint involves solutions to a parametric optimization problem. It is well known that the value function reformulation provides an equivalent single-level optimization problem, but it results in a non-smooth optimization problem that never satisfies the usual constraint qualification, such as the Mangasarian-Fromovitz constraint qualification (MFCQ). In this paper, we show that even the first order sufficient condition for metric ...
-
作者：Ezra, Tomer; Feldman, Michal; Gravin, Nick; Tang, Zhihao Gavin
作者单位：Tel Aviv University; Shanghai University of Finance & Economics
摘要：We provide prophet inequality algorithms for online weighted matching in general (nonbipartite) graphs, under two well-studied arrival models: edge arrival and vertex arrival. The weights of the edges are drawn froma priori known probability distribution. Under edge arrival, the weight of each edge is revealed on arrival, and the algorithm decides whether to include it in thematching or not. Under vertex arrival, theweights of all edges fromthe newly arriving vertex to all previously arrived v...
