-
作者：Bolte, Jerome; Gaubert, Stephane; Vigeral, Guillaume
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Inria; Institut Polytechnique de Paris; Ecole Polytechnique; Universite PSL; Universite Paris-Dauphine
摘要：Definable zero-sum stochastic games involve a finite number of states and action sets, and reward and transition functions, that are definable in an o-minimal structure. Prominent examples of such games are finite, semi-algebraic, or globally subanalytic stochastic games. We prove that the Shapley operator of any definable stochastic game with separable transition and reward functions is definable in the same structure. Definability in the same structure does not hold systematically: we provid...
-
作者：Mastrogiacomo, Elisa; Gianin, Emanuela Rosazza
作者单位：University of Milano-Bicocca
摘要：In this paper, we focus on the portfolio optimization problem associated with a quasiconvex risk measure (satisfying some additional assumptions). For coherent/convex risk measures, the portfolio optimization problem has been already studied in the literature. Following the approach of Ruszczynski and Shapiro [Ruszczynski A, Shapiro A (2006) Optimization of convex risk functions. Math. Oper. Res. 31(3): 433-452.], but by means of quasiconvex analysis and notions of subdifferentiability, we cha...
-
作者：Post, Ian; Ye, Yinyu
作者单位：University of Waterloo; Stanford University
摘要：We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n(3) m(2) log(2) n) iterations if the discount factor is uniform and O(n(5) m(3) log(2) n) iterations if each action has a distinct discount factor. Previously the simplex method was know...
-
作者：Sumita, Hanna; Kakimura, Naonori; Makino, Kazuhisa
作者单位：University of Tokyo; University of Tokyo; Kyoto University
摘要：In this paper, we consider the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrices are restricted to have at most k nonzero entries per row. It is known that the 1-LCP is solvable in linear time, and the 3-LCP is strongly NP-hard. We show that the 2-LCP is strongly NP-hard, and it can be solved in polynomial time if it is sign-balanced, i. e., each row of the matrix has at most one positive and one negative entry. Our second result matches the currently best-known...
-
作者：Takahashi, Akihiko; Yamada, Toshihiro
作者单位：University of Tokyo
摘要：This paper proposes a unified method for precise estimates of the error bounds in asymptotic expansions of an option price and its Greeks (sensitivities) under a stochastic volatility model. More generally, we also derive an error estimate for an asymptotic expansion around a general partially elliptic diffusion and a more general Wiener functional, which is applicable to various important valuation and risk management tasks in the financial business such as the ones for multidimensional diffu...
-
作者：Ghossoub, Mario
作者单位：Imperial College London
摘要：In the classical theory of monotone equimeasurable rearrangements of functions, equimeasurability (i.e., that two functions have the same distribution) is defined relative to a given additive probability measure. These rearrangement tools have been successfully used in many problems in economic theory dealing with uncertainty where the monotonicity of a solution is desired. However, in all of these problems, uncertainty refers to the classical Bayesian understanding of the term, where the idea...
-
作者：Iancu, Dan A.; Petrik, Marek; Subramanian, Dharmashankar
作者单位：Stanford University; International Business Machines (IBM); IBM USA
摘要：This paper compares two frameworks for measuring risk in a multiperiod setting. The first corresponds to applying a single coherent risk measure to the cumulative future costs, and the second involves applying a composition of one-step coherent risk mappings. We characterize several necessary and sufficient conditions under which one measurement always dominates the other and introduce a metric to quantify how close the two measures are. Using this notion, we address the question of how tightl...
-
作者：Defourny, Boris; Ryzhov, Ilya O.; Powell, Warren B.
作者单位：Lehigh University; University System of Maryland; University of Maryland College Park; Princeton University
摘要：A sequential information collection problem, where a risk-averse decision maker updates a Bayesian belief about the unknown objective function of a linear program, is used to investigate the informational value of measurements performed to refine a robust optimization model. The information is collected in the form of a linear combination of the objective coefficients, subject to random noise. We have the ability to choose the weights in the linear combination, creating a new, nonconvex contin...
-
作者：Atar, Rami; Biswas, Anup; Kaspi, Haya
作者单位：Technion Israel Institute of Technology; Technion Israel Institute of Technology
摘要：A single-server queueing model is considered with customers that have deadlines. If a customer's deadline elapses before service is offered, the customer abandons the system (customers do not abandon while being served). When the server becomes available, it offers service to the customer having the earliest deadline among those that are in the queue. We obtain a fluid limit of the queue length and abandonment processes and for the occupation measure of deadlines, in the form of measure-valued...
-
作者：Girardeau, P.; Leclere, V.; Philpott, A. B.
作者单位：Institut Polytechnique de Paris; Ecole des Ponts ParisTech; University of Auckland
摘要：We prove the almost-sure convergence of a class of sampling-based nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions and uncertainty is modelled by a scenario tree. As special cases, our results imply the almost-sure convergence of stochastic dual dynamic programming, cutting-plane and partial-sampling (CUPPS) algorithm, and dynamic outer-approximation sampling algorithms when applied to problems with...
