Mathematics of Operations Research

最新文章

• Nontruthful Position Auctions Are More Robust to Misspecification AI翻译
  作者：Dutting, Paul; Fischer, Felix; Parkes, David C.
  作者单位：Alphabet Inc.; Google Incorporated; University of London; Queen Mary University London; Harvard University
  摘要：We consider the classical model of sponsored search due to Edelman et al. and Varian and examine how robust standard position auctions are to a misspecification of the position-dependent quality factors used by this model. We show that under both complete and incomplete information a nontruthful position auction admits an efficient equilibrium for a strictly broader range of parameter values than the Vickrey-Clarke-Groves (VCG) mechanism, which would be truthful if the parameters were specifie...
• Asymptotically Optimal Control of Make-to-Stock Systems AI翻译
  作者：Nie, Jiawang; Tang, Xindong
  作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University
  摘要：We consider multiclass make-to-stock production/inventory systems in which the manager makes three decisions, including pricing, outsourcing, and scheduling, to maximize the long-run average profit. For a sequence of systems in the heavy-traffic regime, with linear or strictly convex holding/waiting cost functions, we propose a sequence of policies and establish its asymptotic optimality. Our proof combines the lower bound approach and a thorough steady-state analysis of the systems. We also e...
• Rate-Optimal Bayesian Simple Regret in Best Arm Identification AI翻译
  作者：Komiyama, Junpei; Ariu, Kaito; Kato, Masahiro; Qin, Chao
  作者单位：New York University; Royal Institute of Technology; Columbia University
  摘要：We consider best arm identification in the multiarmed bandit problem. Assuming certain continuity conditions of the prior, we characterize the rate of the Bayesian simple regret. Differing from Bayesian regret minimization, the leading term in the Bayesian simple regret derives from the region in which the gap between optimal and suboptimal p ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi arms is smaller than (log T)/T. We propose a simple and easy-to-compute algorithm with its lead...
• Weak Approachability of Convex Sets in Absorbing Games AI翻译
  作者：Ragel, Thomas
  作者单位：Universite PSL; Universite Paris-Dauphine
  摘要：In this paper, we extend previous results on weak approachability in generalized quitting games with vector payoffs to the general case of absorbing games. Specifically, we show that a necessary condition and a different sufficient condition for weak approachability of a convex set, established by Flesch, Laraki, and Perchet, remain valid in the general case. To do so, we extend results on Blackwell approachability to a setup in which stage weights depend on past actions as well as the current...
• On the Diameter of the Stopped Spider Process AI翻译
  作者：Bednarz, Ewelina; Ernst, Philip A.; OseRkowskia, Adam
  作者单位：University of Warsaw; Imperial College London
  摘要：We consider the Brownian spider process, also known as Walsh Brownian motion, first introduced by J. B. Walsh [Walsh JB (1978) A diffusion with a discontinuous local time. Asterisque 52:37-45]. The paper provides the best constant Cn for the inequality root ffiffiffiffififfi ED tau <= Cn E tau ,where tau is the class of all adapted and integrable stopping times and D denotes the diameter of the spider process measured in terms of the British rail metric. This solves a variant of the long-stand...
• Extension of Additive Valuations to General Valuations on the Existence of EFX AI翻译
  作者：Mahara, Ryoga
  作者单位：University of Tokyo
  摘要：Envy freeness is one of the most widely studied notions in fair division. Because envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling notion is envy freeness up to any item (EFX). Informally speaking, EFX requires that no agent i envies another agent j after the removal of any item in j's bundle. The existence of EFX allocations is a major open problem. We study the existence of EFX allocations...
• Difference-of-Convex Algorithm with Extrapolation for Nonconvex, Nonsmooth Optimization Problems AI翻译
  作者：Phan, Duy Nhat; Thi, Hoai An Le
  作者单位：University System of Ohio; University of Dayton; Universite de Lorraine; Institut Universitaire de France
  摘要：In this paper, we focus on the problem of minimizing the sum of a nonconvex differentiable function and a difference of convex (DC) function, where the differentiable function is not restricted to the global Lipschitz gradient continuity assumption. This problem covers a broad range of applications in machine learning and statistics, such as compressed sensing, signal recovery, sparse dictionary learning, matrix factorization, etc. We first take inspiration from the Nesterov acceleration techn...
• l p-Sphere Covering and Approximating Nuclear p-Norm AI翻译
  作者：Guan, Jiewen; He, Simai; Jiang, Bo; Li, Zhening
  作者单位：Shanghai University of Finance & Economics; Shanghai Jiao Tong University; Shanghai University of Finance & Economics; Shanghai University of Finance & Economics; University of Portsmouth
  摘要：The spectral p-norm and nuclear p-norm of matrices and tensors appear in various applications, albeit both are NP-hard to compute. The former sets a foundation of & ell; p-sphere-constrained polynomial optimization problems, and the latter has been found in many rank minimization problems in machine learning. We study approximation algorithms of the tensor nuclear p-norm with an aim to establish the approximation bound matching the best one of its dual norm, the tensor spectral p-norm. Driven ...
• An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities AI翻译
  作者：Lamperski, Jourdain; Freund, Robert M.; Todd, Michael J.
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Massachusetts Institute of Technology (MIT); Cornell University
  摘要：The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) : A(T)x <= u when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two fundamental algorithms for tackling (P), namely, the simplex and interior-point methods, each of which can be easily implemented in a way that either produce...
• Assortment Planning for Recommendations at Checkout Under Inventory Constraints AI翻译
  作者：Chen, Xi; Ma, Will; Simchi-Levi, David; Xin, Linwei
  作者单位：New York University; Columbia University; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of Chicago
  摘要：In this paper, we consider a personalized assortment planning problem under inventory constraints, where each arriving customer type is defined by a primary item of interest. As long as that item is in stock, the customer adds it to the shopping cart, at which point the retailer can recommend to the customer an assortment of add-ons to go along with the primary item. This problem is motivated by the new recommendation at checkout systems that have been deployed at many online retailers, and it...