3期

最新文章

• Overbooking with Bounded Loss AI翻译
  作者：Freund, Daniel; Zhao, Jiayu (Kamessi)
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
  摘要：We study a classic problem in revenue management: quantity-based, single resource revenue management with no-shows. In this problem, a firm observes a sequence of T customers requesting a service. Each arrival is drawn independently from a known distribution of k different types, and the firm needs to decide irrevocably whether to accept or reject requests in an online fashion. The firm has a capacity of resources B and wants to maximize its profit. Each accepted service request yields a type-...
• A Complementary Pivot Algorithm for Competitive Allocation of a Mixed Manna AI翻译
  作者：Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign
  摘要：We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bads (chores) that everyone dislikes as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. argues why allocating a mixed manna is genuinely more complicated than a good or a bad manna and why competitive equilibrium is the best mechanism. It also provides the existence of eq...
• Sums of Separable and Quadratic Polynomials AI翻译
  作者：Ahmadi, Amir Ali; Dibek, Cemil; Hall, Georgina
  作者单位：Princeton University; INSEAD Business School
  摘要：We study separable plus quadratic (SPQ) polynomials, that is, polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sums of squares, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative quadratic polynomial and (ii) a sum of squares. We establish that the answer to question (i) is positive for univari...
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization AI翻译
  作者：Zhao, Renbo
  作者单位：University of Iowa
  摘要：We propose a primal-dual smoothing framework for finding a near-stationary point of a class of nonsmooth nonconvex optimization problems with max-structure. We analyze the primal and dual gradient complexities of the framework via two approaches, that is, the dual-then-primal and primal-the-dual smoothing approaches. Our framework improves the best-known oracle complexities of the existing method, even in the restricted problem setting. As an important part of our framework, we propose a first...
• Contextual Bandits with Cross-Learning AI翻译
  作者：Balseiro, Santiago; Golrezaei, Negin; Mahdian, Mohammad; Mirrokni, Vahab; Schneider, Jon
  作者单位：Columbia University; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
  摘要：In the classic contextual bandits problem, in each round t, a learner observes some context c, chooses some action i to perform, and receives some reward r(i,t)(c). We consider the variant of this problem in which in addition to receiving the reward r(i,t)(c), the learner also learns the values of r(i,t)(c ') for some other contexts c ' in set Oi(c), that is, the rewards that would be achieved by performing that action under different contexts c 'is an element of O-i(c). This variant arises in...
• Truthfulness of a Network Resource-Sharing Protocol AI翻译
  作者：Cheng, Yukun; Deng, Xiaotie; Qi, Qi; Yan, Xiang
  作者单位：Suzhou University of Science & Technology; Peking University; Renmin University of China; Huawei Technologies
  摘要：We consider a sharing economy over a network in which each vertex agent allocates resources to its neighbors in response to their contributions. General equilibrium theory can be applied here to solve the problem of deciding how to fairly and efficiently allocate resources among agents as resource sharing over the network can be modeled as a pure exchange economy. It is known that proportional sharing dynamics converges to a market equilibrium solution. We are particularly interested in propor...
• Fair Integral Network Flows AI翻译
  作者：Frank, Andras; Murota, Kazuo
  作者单位：Eotvos Lorand University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; Tokyo Metropolitan University
  摘要：A strongly polynomial algorithm is developed for finding an integer-valued feasible st-flow of a given flow amount, which is decreasingly minimal on a specified subset F of edges in the sense that the largest flow value on F is as small as possible; within this, the second largest flow value on F is as small as possible; within this, the third largest flow value on F is as small as possible, and so on. A characterization of the set of these st-flows gives rise to an algorithm to compute a chea...
• Exactness Conditions for Semidefinite Programming Relaxations of Generalization of the Extended Trust Region Subproblem AI翻译
  作者：Jiang, Rujun; Li, Duan
  作者单位：Fudan University; City University of Hong Kong
  摘要：The extended trust region subproblem (ETRS) of minimizing a quadratic objective over the unit ball with additional linear constraints has attracted a lot of attention in the last few years because of its theoretical significance and wide spectra of applications. Several sufficient conditions to guarantee the exactness of its semidefinite programming (SDP) relaxation have been recently developed in the literature. In this paper, we consider a generalization of the extended trust region subprobl...
• From Perspective Maps to Epigraphical Projections AI翻译
  作者：Friedlander, Michael P.; Goodwin, Ariel; Hoheisel, Tim
  作者单位：University of British Columbia; McGill University
  摘要：The projection onto the epigraph or a level set of a closed proper convex function can be achieved by finding a root of a scalar equation that involves the proximal operator as a function of the proximal parameter. This paper develops the variational analysis of this scalar equation. The approach is based on a study of the variational-analytic properties of general convex optimization problems that are (partial) infimal projections of the sum of the function in question and the perspective map...
• A Unifying Framework for Submodular Mean Field Games AI翻译
  作者：Dianetti, Jodi; Ferrari, Giorgio; Fischer, Markus; Nendel, Max
  作者单位：University of Bielefeld; University of Padua
  摘要：We provide an abstract framework for submodular mean field games and identify verifiable sufficient conditions that allow us to prove the existence and approximation of strong mean field equilibria in models where data may not be continuous with respect to the measure parameter and common noise is allowed. The setting is general enough to encompass qualitatively different problems, such as mean field games for discrete time finite space Markov chains, singularly controlled and reflected diffus...