Mathematics of Operations Research

最新文章

• Scalar Multivariate Risk Measures with a Single Eligible Asset AI翻译
  作者：Feinstein, Zachary; Rudloff, Birgit
  作者单位：Stevens Institute of Technology; Vienna University of Economics & Business
  摘要：In this paper, we present results on scalar risk measures in markets with transaction costs. Such risk measures are defined as the minimal capital requirements in the cash asset. First, some results are provided on the dual representation of such risk measures, with particular emphasis given on the space of dual variables as (equivalent) martingale measures and prices consistent with the market model. Then, these dual representations are used to obtain the main results of this paper on time co...
• Regular Matroids Have Polynomial Extension Complexity AI翻译
  作者：Aprile, Manuel; Fiorini, Samuel
  作者单位：University of Padua; Universite Libre de Bruxelles
  摘要：We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n(6)). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n(2)) bound for the special case of (co)graphic matroids. However, the case of a general regular matroid was open, despite recent attempts. We also consider the extension complexity of circuit dominants of regular matroids, for which we give a O(n(2)) bound.
• The Buck-Passing Game AI翻译
  作者：Cominetti, Roberto; Quattropani, Matteo; Scarsini, Marco
  作者单位：Universidad Adolfo Ibanez; Luiss Guido Carli University
  摘要：We consider two classes of games in which players are the vertices of a directed graph. Initially, nature chooses one player according to some fixed distribution and gives the player a buck. This player passes the buck to one of the player's out-neighbors in the graph. The procedure is repeated indefinitely. In one class of games, each player wants to minimize the asymptotic expected frequency of times that the player receives the buck. In the other class of games, the player wants to maximize...
• Time-Varying Semidefinite Programs AI翻译
  作者：Ahmadi, Amir Ali; El Khadir, Bachir
  作者单位：Princeton University
  摘要：We study time-varying semidefinite programs (TV-SDPs), which are semidefinite programs whose data (and solutions) are functions of time. Our focus is on the setting where the data vary polynomially with time. We show that under a strict feasibility assumption, restricting the solutions to also be polynomial functions of time does not change the optimal value of the TV-SDP. Moreover, by using a Positivstellensatz (positive locus theorem) on univariate polynomial matrices, we show that the best ...
• On Degenerate Doubly Nonnegative Projection Problems AI翻译
  作者：Cui, Ying; Liang, Ling; Sun, Defeng; Toh, Kim-Chuan
  作者单位：University of Minnesota System; University of Minnesota Twin Cities; National University of Singapore; Hong Kong Polytechnic University; National University of Singapore
  摘要：The doubly nonnegative (DNN) cone, being the set of all positive semidefinite matrices whose elements are nonnegative, is a popular approximation of the computationally intractable completely positive cone. The major difficulty for implementing a Newton-type method to compute the projection of a given large-scale matrix onto the DNN cone lies in the possible failure of the constraint nondegeneracy, a generalization of the linear independence constraint qualification for nonlinear programming. ...
• The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users AI翻译
  作者：Caragiannis, Ioannis; Voudouris, Alexandros A.
  作者单位：University of Patras; University of Oxford
  摘要：We study the efficiency of mechanisms for allocating a divisible resource. Given scalar signals submitted by all users, such a mechanism decides the fraction of the resource that each user will receive and a payment that will be collected from her. Users are self-interested and aim to maximize their utility (defined as their value for the resource fraction they receive minus their payment). Starting with the seminal work of Johari and Tsitsiklis, a long list of papers studied the price of anar...
• Nonparametric Learning Algorithms for Joint Pricing and Inventory Control with Lost Sales and Censored Demand AI翻译
  作者：Chen, Boxiao; Chao, Xiuli; Shi, Cong
  作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; University of Michigan System; University of Michigan
  摘要：We consider a joint pricing and inventory control problem in which the customer's response to selling price and the demand distribution are not known a priori. Unsatisfied demand is lost and unobserved, and the only available information for decision making is the observed sales data (also known as censored demand). Conventional approaches, such as stochastic approximation, online convex optimization, and continuum-armed bandit algorithms, cannot be employed, because neither the realized value...
• Terminal Ranking Games AI翻译
  作者：Bayraktar, Erhan; Zhang, Yuchong
  作者单位：University of Michigan System; University of Michigan; University of Toronto
  摘要：We analyze a mean field tournament: a mean field game in which the agents receive rewards according to the ranking of the terminal value of their projects and are subject to cost of effort. Using Schrodinger bridges we are able to explicitly calculate the equilibrium. This allows us to identify the reward functions which would yield a desired equilibrium and solve several related mechanism design problems. We are also able to identify the effect of reward inequality on the players' welfare as ...
• Fully Polynomial-Time Approximation Schemes for Fair Rent Division AI翻译
  作者：Arunachaleswaran, Eshwar Ram; Barman, Siddharth; Rathi, Nidhi
  作者单位：University of Pennsylvania; Indian Institute of Science (IISC) - Bangalore; Indian Institute of Science (IISC) - Bangalore
  摘要：We study the problem of fair rent division that entails splitting the rent and allocating the rooms of an apartment among agents in a fair manner (i.e., under the imposed rents, no agent has a strictly stronger preference for any other agent's room). The utility functions specify the cardinal preferences of the agents for the rooms for every possible room rent. Although envy-free solutions are guaranteed to exist under reasonably general utility functions, efficient algorithms for finding them...
• Pure Nash Equilibria and Best-Response Dynamics in Random Games AI翻译
  作者：Amiet, Ben; Collevecchio, Andrea; Scarsini, Marco; Zhong, Ziwen
  作者单位：Monash University; Luiss Guido Carli University
  摘要：In finite games, mixed Nash equilibria always exist, but pure equilibria may fail to exist. To assess the relevance of this nonexistence, we consider games where the payoffs are drawn at random. In particular, we focus on games where a large number of players can each choose one of two possible strategies and the payoffs are independent and identically distributed with the possibility of ties. We provide asymptotic results about the random number of pure Nash equilibria, such as fast growth an...