-
作者：Kiseleva, Tatiana; Wagener, Florian
作者单位：Vrije Universiteit Amsterdam; University of Amsterdam
摘要：We study the structure of the solution set of a class of infinite-horizon dynamic programming problems with one-dimensional state spaces, as well as their bifurcations, as problem parameters are varied. The solutions are represented as the integral curves of a multivalued optimal vector field on state space. Generically, there are three types of integral curves: stable points, open intervals that are forward asymptotic to a stable point and backward asymptotic to an unstable point, and half-op...
-
作者：Mordukhovich, B. S.; Nghia, T. T. A.; Rockafellar, R. T.
作者单位：Wayne State University; King Fahd University of Petroleum & Minerals; Oakland University; University of Washington; University of Washington Seattle
摘要：The paper is devoted to full stability of optimal solutions in general settings of finite-dimensional optimization with applications to particular models of constrained optimization problems, including those of conic and specifically semidefinite programming. Developing a new technique of variational analysis and generalized differentiation, we derive second-order characterizations of full stability, in both Lipschitzian and Holderian settings, and establish their relationships with the conven...
-
作者：Jevtic, Petar; Steele, J. Michael
作者单位：McMaster University; University of Pennsylvania
摘要：A caterpillar network (or graph) G is a tree with the property that removal of the leaf edges of G leaves one with a path. Here we focus on minimum weight spanning caterpillars where the vertices are points in the Euclidean plane and the costs of the path edges and the leaf edges are multiples of their corresponding Euclidean lengths. The flexibility in choosing the weight for path edges versus the weight for leaf edges gives some useful flexibility in modeling. In particular, one can accommod...
-
作者：Murota, Kazuo; Yokoi, Yu
作者单位：University of Tokyo
摘要：The stable allocation model is a many-to-many matching model in which each pair's partnership is represented by a nonnegative integer. This paper establishes a link between two different formulations of this model: the choice function model studied thoroughly by Alkan and Gale and the discrete-concave (M-concave) value function model introduced by Eguchi, Fujishige, and Tamura. We show that the choice functions induced from M-concave value functions are endowed with consistency, persistence, a...
-
作者：Shioura, Akiyoshi
作者单位：Tohoku University
摘要：We consider the maximization of a gross substitutes utility function under budget constraints. This problem naturally arises in applications such as exchange economies in mathematical economics and combinatorial auctions in (algorithmic) game theory. We show that this problem admits a polynomial-time approximation scheme (PTAS). More generally, we present a PTAS for maximizing a discrete concave function called an M-right angle-concave function under budget constraints. Our PTAS is based on ro...
-
作者：Coucheney, Pierre; Gaujal, Bruno; Mertikopoulos, Panayotis
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Paris Saclay; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：Starting from a heuristic learning scheme for strategic N-person games, we derive a new class of continuous-time learning dynamics consisting of a replicator-like drift adjusted by a penalty term that renders the boundary of the game's strategy space repelling. These penalty-regulated dynamics are equivalent to players keeping an exponentially discounted aggregate of their ongoing payoffs and then using a smooth best response to pick an action based on these performance scores. Owing to this i...
-
作者：He, Xue Dong; Jin, Hanqing; Zhou, Xun Yu
作者单位：Columbia University; University of Oxford; University of Oxford; University of Oxford
摘要：We seek to characterize the trading behavior of an agent, in the context of a continuous-time portfolio choice model, if she measures the risk by a so called weighted value-at-risk (VaR), which is a generalization of both VaR and conditional VaR. We show that when bankruptcy is allowed the agent displays extreme risk-taking behaviors, unless the downside risk is significantly penalized, in which case an asymptotically optimal strategy is to invest a very small amount of money in an extremely r...
-
作者：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...
