2020

最新文章

• Limit Equilibrium Payoffs in Stochastic Games AI翻译
  作者：Renault, Jerome; Ziliotto, Bruno
  作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite PSL; Universite Paris-Dauphine; Centre National de la Recherche Scientifique (CNRS)
  摘要：We study the limit of equilibrium payoffs, as the discount factor goes to one, in non-zero-sum stochastic games. We first show that the set of stationary equilibrium payoffs always converges. We then provide two-player examples in which the whole set of equilibrium payoffs diverges. The construction is robust to perturbations of the payoffs and to the introduction of normal-form correlation.
• Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs AI翻译
  作者：Frangioni, Antonio; Gentile, Claudio; Hungerford, James
  作者单位：University of Pisa; Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR)
  摘要：We study the problem of decomposing the Hessian matrix of a mixed integer convex quadratic program (MICQP) into the sum of positive semidefinite 2 x 2 matrices. Solving this problem enables the use of perspective reformulation techniques for obtaining strong lower bounds for MICQPs with semicontinuous variables but a nonseparable objective function. An explicit formula is derived for constructing 2 x 2 decompositions when the underlying matrix is weakly scaled diagonally dominant, and necessar...
• Stabilizing Weighted Graphs AI翻译
  作者：Koh, Zhuan Khye; Sanita, Laura
  作者单位：University of London; London School Economics & Political Science; University of Waterloo
  摘要：An edge-weighted graph G is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an important role in network bargaining games and cooperative matching games, because they characterize instances that admit stable outcomes. We give the first polynomial-time algorithm to find a minimum cardinality subset of vertices whose removal from G yields a stable graph, for any weighted graph G. The algorithm is combinatorial a...
• The Pareto Comparisons of a Group of Exponential Discounters AI翻译
  作者：Chambers, Christopher P.; Echenique, Federico
  作者单位：Georgetown University; California Institute of Technology
  摘要：Agents with different discount factors disagree about some intertemporal trade-offs, but they will also agree sometimes. We seek to understand precisely the nature of their agreements and disagreements. A group of agents is identified with a set of discount factors. We characterize the comparisons that a given interval of discount factors will agree on, including what all discount factors in the interval [0,1] will agree on. Our result is analogous to how all risk-averse and monotone agents ag...
• Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min (Max) Polynomial Bellman Equations AI翻译
  作者：Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
  作者单位：University of Edinburgh; University of Southern California; Columbia University
  摘要：We show that one can compute the least nonnegative solution (also known as the least fixed point) for a system of probabilistic min (max) polynomial equations, to any desired accuracy epsilon > 0 in time polynomial in both the encoding size of the system and in log(1/epsilon). These are Bellman optimality equations for important classes of infinite-state Markov decision processes (MDPs), including branching MDPs (BMDPs), which generalize classic multitype branching stochastic processes. We thu...
• Utility Maximization with Proportional Transaction Costs Under Model Uncertainty AI翻译
  作者：Deng, Shuoqing; Tan, Xiaolu; Yu, Xiang
  作者单位：Universite PSL; Universite Paris-Dauphine; Chinese University of Hong Kong; Hong Kong Polytechnic University
  摘要：We consider a discrete time financial market with proportional transaction costs under model uncertainty and study a numeraire-based semistatic utility maximization problem with an exponential utility preference. The randomization techniques recently developed in Bouchard, Deng, and Tan [Bouchard B, Deng S, Tan X (2019) Super-replication with proportional transaction cost under model uncertainty. Math. Finance 29(3): 837-860.], allow us to transform the original problem into a frictionless cou...
• Trimmed Statistical Estimation via Variance Reduction AI翻译
  作者：Aravkin, Aleksandr; Davis, Damek
  作者单位：University of Washington; University of Washington Seattle; Cornell University
  摘要：In this paper, we show how to transform any optimization problem that arises from fitting a machine learning model into one that (1) detects and removes contaminated data from the training set while (2) simultaneously fitting the trimmed model on the uncontaminated data that remains. To solve the resulting nonconvex optimization problem, we introduce a fast stochastic proximal-gradient algorithm that incorporates prior knowledge through nonsmooth regularization. For data sets of size n, our ap...