-
作者：Conforti, Giovanni; Kazeykina, Anna; Ren, Zhenjie
作者单位：Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Universite Paris Saclay; Universite PSL; Universite Paris-Dauphine
摘要：In this paper, we study a class of games regularized by relative entropy where the players strategies are coupled through a random environment. Besides existence and uniqueness of equilibria for such games, we prove, under different sets of hypotheses that the marginal laws of the corresponding mean-field Langevin systems can converge toward the games equilibria. As an application, we show that dynamic games fall in this framework by considering the time horizon as environment. Concerning appl...
-
作者：Rhee, Chang-Han; Glynn, Peter W.
作者单位：Northwestern University; Stanford University
摘要：We consider a family of Markov chains whose transition dynamics are affected by model parameters. Understanding the parametric dependence of (complex) performance measures of such Markov chains is often of significant interest. The derivatives and their continuity of the performance measures w.r.t. the parameters play important roles, for example, in numerical optimization of the performance measures, and quantification of the uncertainties in the performance measures when there are uncertaint...
-
作者：Kong, Weiwei; Melo, Jefferson G.; Monteiro, Renato D. C.
作者单位：United States Department of Energy (DOE); Oak Ridge National Laboratory; Universidade Federal de Goias; University System of Georgia; Georgia Institute of Technology
摘要：This paper proposes and analyzes a proximal augmented Lagrangian (NL-IAPIAL) method for solving constrained nonconvex composite optimization problems, where the constraints are smooth and convex with respect to the order given by a closed convex cone. Each NL-IAPIAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite gradient method followed by a Lagrange multiplier update. Under some mild assumptions, a complexity bound for NL-IAPIAL ...
-
作者：Laurent, Monique; Vargas, Luis Felipe
作者单位：Tilburg University
摘要：De Klerk and Pasechnik introduced in 2002 semidefinite bounds theta((r))(G)(r >= 0) for the stability number alpha(G) of a graph G and conjectured their exactness at order r = alpha(G) - 1. These bounds rely on the conic approximations K-n((r)) introduced by Parrilo in 2000 for the copositive cone COPn. A difficulty in the convergence analysis of the bounds is the bad behavior of Parrilo's cones under adding a zero row/column: when applied to a matrix not in K-n((r)) this gives a matrix that d...
-
作者：Lehrer, Ehud; Shaiderman, Dimitry
作者单位：Tel Aviv University
摘要：Consider a stationary process taking values in a finite state space. Each state is associated with a finite one-shot zero-sum game. We investigate the infinitely repeated zero-sum game with incomplete information on one side in which the state of the game evolves according to the stationary process. Two players, named the observer and the adversary, play the following game. At the beginning of any stage, only the observer is informed of the state xi(n) and is therefore the only one who knows t...
-
作者：Avvakumov, Sergey; Karasev, Roman
作者单位：University of Copenhagen; Kharkevich Institute for Information Transmission Problems of the RAS; Russian Academy of Sciences; Moscow Institute of Physics & Technology
摘要：We prove that, for any positive integer m, a segment may be partitioned into m possibly degenerate or empty segments with equal values of a continuous function f evaluated on segments, assuming that f may take positive and negative values, but its value on degenerate or empty segments is zero.
-
作者：Blanchard, Moise; Jacquillat, Alexandre; Jaillet, Patrick
作者单位：Massachusetts Institute of Technology (MIT)
摘要：The k-traveling salesman problem (k-TSP) seeks a tour of minimal length that visits a subset of k & LE; n points. The traveling repairman problem (TRP) seeks a complete tour with minimal latency. This paper provides constant-factor probabilistic approximations of both problems. We first show that the optimal length of the k-TSP path grows at a � rate of & UTheta; k/nk/(2(k �1))�. The proof provides a constant-factor approximation scheme, which solves a TSP in a high-concentration zone, leve...
-
作者：Jansen, Klaus; Rohwedder, Lars
作者单位：University of Kiel; Maastricht University
摘要：Integer programs with a fixed number of constraints are solvable in pseudo-polynomial time in the largest coefficient of any constraint. We give a new algorithm which improves the running time of the state of the art. Moreover, we show that improving on our algorithm for any number of constraints is equivalent to improving over the quadratic time algorithm for (min, +)-convolution. This is strong evidence that our algorithm's running time is the best possible. We also present a specialized alg...
-
作者：Muhle-Karbe, Johannes; Shi, Xiaofei; Yang, Chen
作者单位：Imperial College London; University of Toronto; Columbia University; Chinese University of Hong Kong
摘要：We study a risk-sharing economy where an arbitrary number of heterogeneous agents trades an arbitrary number of risky assets subject to quadratic transaction costs. For linear state dynamics, the forward-backward stochastic differential equations characterizing equilibrium asset prices and trading strategies in this context reduce to a coupled system of matrix-valued Riccati equations. We prove the existence of a unique global solution and provide explicit asymptotic expansions that allow us t...
-
作者：Baiter, Anne G.; Schweizer, Nikolaus; Veraa, Juan C.
作者单位：Tilburg University
摘要：This paper studies the existence and uniqueness of equilibrium prices in a model of the banking sector in which banks trade contingent convertible bonds with stock price triggers among each other. This type of financial product was proposed as an instrument for stabilizing the global banking system after the financial crisis. Yet it was recognized early on that these products may create circularity problems in the definition of stock prices-even in the absence of trade. We find that, if conver...
