-
作者：Klep, Igor; Schweighofer, Markus
作者单位：University of Auckland; University of Konstanz
摘要：Farkas' lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality A(x)>= 0 is infeasible if and only if -1 lies in the quadratic module associa...
-
作者：Chen, Nan; Huang, Zhengyu
作者单位：Chinese University of Hong Kong
摘要：Generating sample paths of stochastic differential equations (SDE) using the Monte Carlo method finds wide applications in financial engineering. Discretization is a popular approximate approach to generating those paths: it is easy to implement but prone to simulation bias. This paper presents a new simulation scheme to exactly generate samples for SDEs. The key observation is that the law of a general SDE can be decomposed into a product of the law of standard Brownian motion and the law of ...
-
作者：Awad, Hernan P.; Glynn, Peter W.; Rubinstein, Reuven Y.
作者单位：University of Miami; Stanford University; Technion Israel Institute of Technology
摘要：We consider the use of importance sampling to compute expectations of functionals of Markov processes. For a class of expectations that can be characterized as positive solutions to a linear system, we show there exists an importance measure that preserves the Markovian nature of the underlying process, and for which a zero-variance estimator can be constructed. The class of expectations considered includes expected infinite horizon discounted rewards as a particular case. In this setting, the...
-
作者：Pai, Mallesh M.; Vohra, Rakesh
作者单位：University of Pennsylvania; Northwestern University
摘要：A monopolist seller has multiple units of an indivisible good to sell over a discrete, finite time horizon. Buyers with unit demand arrive over time and each buyer privately knows her arrival time, her value for a unit, and her deadline. We study whether the seller's optimal allocation rule is a simple index rule. Each buyer is assigned an index and the allocation rule is calculated by a dynamic knapsack algorithm using those indices. Simple indicates that the index of a buyer depends only on ...
-
作者：Anselmi, Jonatha; D'Auria, Bernardo; Walton, Neil
作者单位：Basque Center for Applied Mathematics (BCAM); Universidad Carlos III de Madrid; University of Amsterdam
摘要：We analyze the behavior of closed multiclass product-form queueing networks when the number of customers grows to infinity and remains proportionate on each route (or class). First, we focus on the stationary behavior and prove the conjecture that the stationary distribution at nonbottleneck queues converges weakly to the stationary distribution of an ergodic, open product-form queueing network, which is geometric. This open network is obtained by replacing bottleneck queues with per-route Poi...
-
作者：Kou, Steven; Peng, Xianhua; Heyde, Chris C.
作者单位：Columbia University; Hong Kong University of Science & Technology
摘要：Choosing a proper external risk measure is of great regulatory importance, as exemplified in the Basel II and Basel III Accords, which use value-at-risk with scenario analysis as the risk measures for setting capital requirements. We argue that a good external risk measure should be robust with respect to model misspecification and small changes in the data. A new class of data-based risk measures called natural risk statistics is proposed to incorporate robustness. Natural risk statistics are...
-
作者：Veatch, Michael H.
摘要：We consider the linear programming approach to approximate dynamic programming with an average cost objective and a finite state space. Using a Lagrangian form of the linear program (LP), the average cost error is shown to be a multiple of the best fit differential cost error. This result is analogous to previous error bounds for a discounted cost objective. Second, bounds are derived for average cost error and performance of the policy generated from the LP that involve the mixing time of the...
-
作者：von Falkenhausen, Philipp; Harks, Tobias
作者单位：Technical University of Berlin; Maastricht University
摘要：Joint use of resources with usage-dependent cost raises the question: who pays how much? We study cost sharing in resource selection games where the strategy spaces are either singletons or bases of a matroid defined on the ground set of resources. Our goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate three classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium; separable...
-
作者：Zhang, Bo; Zwart, Bert
作者单位：International Business Machines (IBM); IBM USA
摘要：We study the steady-state behavior of multiserver queues with general job size distributions under size interval task assignment (SITA) policies. Assuming Poisson arrivals and the existence of the alpha th moment of the job size distribution for some alpha > 1, we show that if the job arrival rate and the number of servers increase to infinity with the traffic intensity held fixed, the SITA policy parameterized by alpha minimizes in a large deviation sense the steady-state probability that the...
-
作者：Colombo, Giovanni; Marigonda, Antonio; Wolenski, Peter R.
作者单位：University of Padua; University of Verona; Louisiana State University System; Louisiana State University
摘要：We consider the class of continuous functions that map an open set Omega subset of R-n to R with an epigraph having (locally) positive reach with an additional property. This class contains all finite convex and C-1,C- 1 functions, but also ones that are not necessarily Lipschitz continuous. We provide a representation formula for the Clarke generalized gradient of such functions using convex combinations and limits of gradients at differentiability points, thus offering an alternative to the ...
