3期

最新文章

• Approximate Nash Equilibria in Large Nonconvex Aggregative Games AI翻译
  作者：Liu, Kang; Oudjane, Nadia; Wan, Cheng
  作者单位：Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Institut Polytechnique de Paris; ENSTA Paris
  摘要：This paper shows the existence of O(1/n(gamma))-Nash equilibria in n-player noncooperative sum-aggregative games in which the players' cost functions, depending only on their own action and the average of all players' actions, are lower semicontinuous in the former, whereas gamma-Holder continuous in the latter. Neither the action sets nor the cost functions need to be convex. For an important class of sum-aggregative games, which includes congestion games with gamma equal to one, a gradient-p...
• Liquidity Provision with Adverse Selection and Inventory Costs AI翻译
  作者：Herdegen, Martin; Muhle-Karbe, Johannes; Stebeggc, Florian
  作者单位：University of Warwick; Imperial College London; Columbia University
  摘要：We study one-shot Nash competition between an arbitrary number of identical dealers that compete for the order flow of a client. The client trades either because of proprietary information, exposure to idiosyncratic risk, or a mix of both trading motives. When quoting their price schedules, the dealers do not know the client's type but only its distribution, and in turn choose their price quotes to mitigate between adverse selection and inventory costs. Under essentially minimal conditions, we...
• Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization AI翻译
  作者：Belomestny, Denis; Bender, Christian; Schoenmakers, John
  作者单位：University of Duisburg Essen; Saarland University; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
  摘要：In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem can be reformulated as a problem of stochastic average approximation (SAA) that can be solved via linear programming. By randomizing the initial value of the underlying process, we enforce solutions with zero variance while preserving the linear programming structure of the problem. A careful analysis of the randomized SAA algorithm shows that it enjoys favorable properties such a...
• Convergence of a Packet Routing Model to Flows over Time AI翻译
  作者：Sering, Leon; Koch, Laura Vargas; Ziemke, Theresa
  作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Berlin; Technical University of Berlin
  摘要：Mathematical approaches for modeling dynamic traffic can be roughly divided into two categories: discrete packet routing models and continuous flow over time models. Despite very vital research activities on models in both categories, their connection was poorly understood so far. We build this connection by specifying a (competitive) packet routing model, which is discrete in terms of flow and time, and proving its convergence to the intensively studied model of flows over time with determini...
• On Singular Control for Levy Processes AI翻译
  作者：Noba, Kei; Yamazaki, Kazutoshi
  作者单位：Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of Queensland
  摘要：We revisit the classical singular control problem of minimizing running and controlling costs. Existing studies have shown the optimality of a barrier strategy when driven by Brownian motion or Levy processes with one-sided jumps. Under the assumption that the running cost function is convex, we show the optimality of a barrier strategy for a general class of Levy processes.
• A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games AI翻译
  作者：Wu, Zijun; Moehring, Rolf H.
  作者单位：Hefei University; Technical University of Berlin
  摘要：The price of anarchy (PoA) is a standard measure to quantify the inefficiency of equilibria in nonatomic congestion games. Most publications have focused on worst-case bounds for the PoA. Only a few have analyzed the sensitivity of the PoA against changes of the demands or cost functions, although that is crucial for empirical computations of the PoA. We analyze the sensitivity of the PoA with respect to (w.r.t.) simultaneous changes of demands and cost functions. The key to this analysis is a...
• Provably Efficient Reinforcement Learning with Linear Function Approximation AI翻译
  作者：Jin, Chi; Yang, Zhuoran; Wang, Zhaoran; Jordan, Michael, I
  作者单位：Princeton University; Yale University; Northwestern University; University of California System; University of California Berkeley
  摘要：Modern reinforcement learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation trade-off. As a result, a core RL question remains open: how can we design provably e...
• Exact Optimal Stopping for Multidimensional Linear Switching Diffusions AI翻译
  作者：Ernst, Philip; Mei, Hongwei
  作者单位：Rice University; Imperial College London; Texas Tech University System; Texas Tech University
  摘要：The paper studies a class of multidimensional optimal stopping problems with infinite horizon for linear switching diffusions. There are two main novelties in the optimal problems considered: The underlying stochastic process has discontinuous paths, and the cost function is not necessarily integrable on the entire time horizon, where the latter is often a key assumption in classical optimal stopping theory for diffusions. Under relatively mild conditions, we show, for the class of multidimens...
• Optimality of Independently Randomized Symmetric Policies for Exchangeable Stochastic Teams with Infinitely Many Decision Makers AI翻译
  作者：Sanjari, Sina; Saldi, Naci; Yuksel, Serdar
  作者单位：Queens University - Canada; Ihsan Dogramaci Bilkent University
  摘要：We study stochastic teams (known also as decentralized stochastic control problems or identical interest stochastic dynamic games) with large or countably infinite numbers of decision makers and characterize the existence and structural properties of (globally) optimal policies. We consider both static and dynamic nonconvex teams where the cost function and dynamics satisfy an exchangeability condition. To arrive at existence and structural results for optimal policies, we first introduce a to...
• On Integer Programming, Discrepancy, and Convolution AI翻译
  作者：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...