Mathematics of Operations Research

最新文章

• Strong Convexity of Feasible Sets in Off-line and Online Optimization AI翻译
  作者：Molinaro, Marco
  作者单位：Pontificia Universidade Catolica do Rio de Janeiro
  摘要：It is known that the curvature of the feasible set in convex optimization allows for algorithms with better convergence rates, and there is renewed interest in this topic for both off-line and online problems. In this paper, leveraging results on geometry and convex analysis, we further our understanding of the role of curvature in optimization: center dot We first show the equivalence of two notions of curvature, namely, strong convexity and gauge bodies, proving a conjecture of Abernethy et ...
• New Constructions of Obviously Strategyproof Mechanisms AI翻译
  作者：Ferraioli, Diodato; Meier, Adrian; Penna, Paolo; Ventre, Carmine
  作者单位：University of Salerno; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of London; King's College London
  摘要：Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. Obviously strategy-proof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the right definition rather than on the construction of these mechanisms. Here, we give the first set of tight results ...
• Power Forward Performance in Semimartingale Markets with Stochastic Integrated Factors AI翻译
  作者：Bo, Lijun; Capponi, Agostino; Zhou, Chao
  作者单位：Xidian University; Columbia University; National University of Singapore; National University of Singapore
  摘要：We study the forward investment performance process (FIPP) in an incomplete semimartingale market model with closed and convex portfolio constraints, when the investor's risk preferences are of the power form. We provide necessary and sufficient conditions for the existence of such a FIPP. In a semimartingale factor model, we show that the FIPP can be recovered as a triplet of processes that admit an integral representation with respect to semimartingales. Using an integrated stochastic factor...
• Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds AI翻译
  作者：Agrawal, Shipra; Jia, Randy
  作者单位：Columbia University
  摘要：We present an algorithm based on posterior sampling (aka Thompson sampling) that achieves near-optimal worst-case regret bounds when the underlying Markov decision process (MDP) is communicating with a finite, although unknown, diameter. Our main result is a high probability regret upper bound of (O) over tilde (DS root AT) for any communicating MDP with S states, A actions, and diameter D. Here, regret compares the total reward achieved by the algorithm to the total expected reward of an opti...
• Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes AI翻译
  作者：Emek, Yuval; Lavi, Ron; Niazadeh, Rad; Shi, Yangguang
  作者单位：Technion Israel Institute of Technology; University of Bath; University of Chicago; Shandong University
  摘要：An online problem called dynamic resource allocation with capacity constraints (DRACC) is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. Because existing online learning techniques do not yield vanishing regret for this problem, we develop a novel online learning framework over deterministic Markov dec...
• 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...
• The Big Match with a Clock and a Bit of Memory AI翻译
  作者：Hansen, Kristoffer Arnsfelt; Ibsen-Jensen, Rasmus; Neymanc, Abraham
  作者单位：Aarhus University; University of Liverpool; Hebrew University of Jerusalem
  摘要：The Big Match is a multistage two-player game. In each stage, player 1 hides one or two pebbles in his hand, and his opponent has to guess that number. Player 1 loses a point if player 2 is correct; otherwise, he wins a point. As soon as player 1 hides one pebble, the players cannot change their choices in any future stage. The undiscounted Big Match has been much-studied. Blackwell and Ferguson (1968) give an epsilon-optimal strategy for player 1 that hides, in each stage, one pebble with a p...
• Modelling Multiperiod Carbon Markets Using Singular Forward-Backward SDEs AI翻译
  作者：Chassagneux, Jean-Francois; Chotai, Hinesh; Crisan, Dan
  作者单位：Universite Paris Cite; Imperial College London; Citigroup Incorporated
  摘要：We introduce a model for the evolution of emissions and the price of emissions allowances in a carbon market, such as the European Union Emissions Trading System (EU ETS). The model accounts for multiple trading periods, or phases, with multiple times at which compliance can occur. At the end of each trading period, the participating firms must surrender allowances for their emissions made during that period, and additional allowances can be used for compliance in the following periods. We sho...
• The Edgeworth Conjecture with Small Coalitions and Approximate Equilibria in Large Economies AI翻译
  作者：Barman, Siddharth; Echenique, Federico
  作者单位：Indian Institute of Science (IISC) - Bangalore; California Institute of Technology
  摘要：We revisit the connection between bargaining and equilibrium in exchange economies and study its algorithmic implications. We consider bargaining outcomes to be allocations that cannot be blocked (i.e., profitably retraded) by coalitions of small size, and show that these allocations must be approximate Walrasian equilibria. Our results imply that deciding whether an allocation is approximately Walrasian can be done in polynomial time, even in economies for which finding an equilibrium is know...
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-Rank Matrix Optimization AI翻译
  作者：Luo, Yuetian; Li, Xudong; Zhang, Anru R.
  作者单位：University of Chicago; Fudan University; Duke University
  摘要：In this paper, we propose a general procedure for establishing the geometric landscape connections of a Riemannian optimization problem under the embedded and quotient geometries. By applying the general procedure to the fixed-rank positive semidefinite (PSD) and general matrix optimization, we establish an exact Riemannian gradient connection under two geometries at every point on the manifold and sandwich inequalities between the spectra of Riemannian Hessians at Riemannian first-order stati...