2020

最新文章

• Characterization, Robustness, and Aggregation of Signed Choquet Integrals AI翻译
  作者：Wang, Ruodu; Wei, Yunran; Willmot, Gordon E.
  作者单位：University of Waterloo
  摘要：This article contains various results on a class of nonmonotone, law-invariant risk functionals called the signed Choquet integrals. A functional characterization via comonotonic additivity is established along with some theoretical properties, including six equivalent conditions for a signed Choquet integral to be convex. We proceed to address two practical issues currently popular in risk management, namely robustness (continuity) issues and risk aggregation with dependence uncertainty, for ...
• The Euclidean k-Supplier Problem AI翻译
  作者：Nagarajan, Viswanath; Schieber, Baruch; Shachnai, Hadas
  作者单位：University of Michigan System; University of Michigan; International Business Machines (IBM); IBM USA; Technion Israel Institute of Technology
  摘要：The k-supplier problem is a fundamental location problem that involves opening k facilities to minimize the maximum distance of any client to an open facility. We consider the k-supplier problem in Euclidean metrics (of arbitrary dimension) and present an algorithm with approximation ratio 1 + root 3 < 2.74. This improves upon the previously known 3-approximation algorithm, which also holds for general metrics. Our result is almost best possible as the Euclidean k-supplier problem is NP-hard t...
• Control-Stopping Games for Market Microstructure and Beyond AI翻译
  作者：Gayduk, Roman; Nadtochiy, Sergey
  作者单位：University of Michigan System; University of Michigan; Illinois Institute of Technology
  摘要：In this paper, we present a family of control-stopping games that arise naturally in equilibrium-based models of market microstructure as well as in other models with strategic buyers and sellers. A distinctive feature of this family of games is the fact that the agents do not have any exogenously given fundamental value for the asset, and they deduce the value of their position from the bid and ask prices posted by other agents (i.e., they are pure speculators). As a result, in such a game, t...
• Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration AI翻译
  作者：Hirai, Hiroshi; Oshiro, Ryunosuke; Tanaka, Ken'ichiro
  作者单位：University of Tokyo
  摘要：In this paper, we address the problem of counting integer points in a rational polytope described by P(y) = {x is an element of R-m: Ax = y, x >= 0}, where A is an n x in integer matrix and y is an n-dimensional integer vector. We study the Z transformation approach initiated in works by Brion and Vergne, Beck, and Lasserre and Zeron from the numerical analysis point of view and obtain a new algorithm on this problem. If A is nonnegative, then the number of integer points in P(y) can be comput...
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems AI翻译
  作者：Paul, Alice; Freund, Daniel; Ferber, Aaron; Shmoys, David B.; Williamson, David P.
  作者单位：Brown University; Massachusetts Institute of Technology (MIT); Cornell University
  摘要：We consider constrained versions of the prize-collecting traveling salesman and the prize-collecting minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. Rooted variants of the problems have the additional constraint that a given vertex, the root, must be contained in the tour/tree. We present a 2-approximation algorithm for the rooted and unrooted versions of both the tree and tour variants. The algo...
• Nonzero-Sum Stochastic Differential Games with Impulse Controls: A Verification Theorem with Applications AI翻译
  作者：Aid, Rene; Basei, Matteo; Callegaro, Giorgia; Campi, Luciano; Vargiolu, Tiziano
  作者单位：Universite PSL; Universite Paris-Dauphine; University of California System; University of California Berkeley; University of Padua; University of London; London School Economics & Political Science
  摘要：We consider a general nonzero-sum impulse game with two players. The main mathematical contribution of this paper is a verification theorem that provides, under some regularity conditions, a suitable system of quasi-variational inequalities for the payoffs and the strategies of the two players at some Nash equilibrium. As an application, we study an impulse game with a one-dimensional state variable, following a real-valued scaled Brownian motion, and two players with linear and symmetric runn...
• Asymptotic Optimality of Power-of-d Load Balancing in Large-Scale Systems AI翻译
  作者：Mukherjee, Debankur; Borst, Sem C.; van Leeuwaarden, Johan S. H.; Whiting, Philip A.
  作者单位：University System of Georgia; Georgia Institute of Technology; Eindhoven University of Technology; Nokia Corporation; Nokia Bell Labs; Tilburg University; Macquarie University
  摘要：We consider a system of N identical server pools and a single dispatcher in which tasks with unit-exponential service requirements arrive at rate.(N). In order to optimize the experienced performance, the dispatcher aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among d(N) randomly selected server pools. We construct a stochastic coupling to bound the differenc...
• Reinforcement with Fading Memories AI翻译
  作者：Xu, Kuang; Yun, Se-Young
  作者单位：Stanford University; Korea Advanced Institute of Science & Technology (KAIST)
  摘要：We study the effect of imperfect memory on decision making in the context of a stochastic sequential action-reward problem. An agent chooses a sequence of actions, which generate discrete rewards at different rates. She is allowed to make new choices at rate beta, whereas past rewards disappear from her memory at rate mu. We focus on a family of decision rules where the agent makes a new choice by randomly selecting an action with a probability approximately proportional to the amount of past ...
• Exchangeable Processes: de Finetti's Theorem Revisited AI翻译
  作者：Lehrer, Ehud; Shaiderman, Dimitry
  作者单位：Tel Aviv University; INSEAD Business School
  摘要：A sequence of random variables is exchangeable if the joint distribution of any finite subsequence is invariant to permutations. De Finetti's representation theorem states that every exchangeable infinite sequence is a convex combination of independent and identically distributed processes. In this paper, we explore the relationship between exchangeability and frequency-dependent posteriors. We show that any stationary process is exchangeable if and only if its posteriors depend only on the em...
• An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in R3 AI翻译
  作者：Rahul, Saladi
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign
  摘要：The orthogonal point enclosure query (OPEQ) problem is a fundamental problem in the context of data management for modeling user preferences. Formally, preprocess a set S of n axis-aligned boxes (possibly overlapping) in R-d into a data structure so that the boxes in S containing a given query point q can be reported efficiently. In the pointer machine model, optimal solutions for the OPEQ in R-1 and R-2 were discovered in the 1980s: linear-space data structures that can answer the query in O(...