Mathematics of Operations Research

最新文章

• Strongly Convergent Homogeneous Approximations to Inhomogeneous Markov Jump Processes and Applications AI翻译
  作者：Bladt, Martin; Peraltab, Oscar
  作者单位：University of Copenhagen; Cornell University
  摘要：The study of time-inhomogeneous Markov jump processes is a traditional topic within probability theory that has recently attracted substantial attention in various applications. However, their flexibility also incurs a substantial mathematical burden which is usually circumvented by using well-known generic distributional approximations or simulations. This article provides a novel approximation method that tailors the dynamics of a time-homogeneous Markov jump process to meet those of its tim...
• The Information Projection in Moment Inequality Models: Existence, Dual Representation, and Approximation AI翻译
  作者：Tabri, Rami
  作者单位：Monash University
  摘要：Relative entropy minimization is a widely used method in decisions and operations research that incorporates information through constraints on the underlying probability model. The solution is called information projection, and we present new results for its existence, exponential family representation, and approximation in the infinite-dimensional setting for moment inequality constraint sets, nesting both conditional and unconditional moments and allowing for an infinite number of such ineq...
• Converging Better Response Dynamics in Sender-Receiver Games AI翻译
  作者：Semirat, Stephan; Forges, Francoise
  作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); INRAE; Centre National de la Recherche Scientifique (CNRS); Institut National Polytechnique de Grenoble; Universite PSL; Universite Paris-Dauphine; Centre National de la Recherche Scientifique (CNRS); Institut de Recherche pour le Developpement (IRD); Laboratoire dEconomie de Dauphine LEDa
  摘要：We consider information transmission between a sender, who has finitely many types, and a receiver, who must choose a decision in a real interval. The payoffs depend on the sender's type and the receiver's decision. We assume that the payoff functions are wellbehaved. We characterize the pure strategy perfect Bayesian equilibrium outcomes as incentive-compatible partitions of the sender's types. We propose an algorithm, which starts from the finest partition. Then, at every step, if the curren...
• Online Regret Bounds for Satisficing in Markov Decision Processes AI翻译
  作者：Hajiabolhassan, Hossein; Ortner, Ronald
  作者单位：Medical University of Graz; University of Leoben
  摘要：We consider general reinforcement learning under the average reward criterion in Markov decision processes (MDPs), when the learner's goal is not to learn an optimal policy, but accepts any policy whose average reward is above a given satisfaction level a. We show that with this more modest objective, it is possible to give algorithms that only have constant regret with respect to the level a, provided that there is a policy above this level. This is a generalization of known results from the ...
• A Universally Efficient Dynamic Auction for All Unimodular Demand Types AI翻译
  作者：Fujishie, Satoru; Yang, Zaifu
  作者单位：Kyoto University; University of York - UK
  摘要：We propose a novel strategy-proof dynamic auction for efficiently allocating heterogeneous indivisible commodities. The auction applies to all unimodular demand types of Baldwin and Klemperer's necessary and sufficient condition for the existence of competitive equilibrium which accommodate a wide variety of complements, substitutes, gross substitutes and complements, and any other kinds. Although bidders are not assumed to be price takers so they can act strategically, this auction induces bi...
• The Competition Complexity of Prophet Inequalities AI翻译
  作者：Brustle, Johannes; Correa, Jose; Dutting, Paul; Ezra, Tomer; Feldman, Michal; Verdugo, Victor
  作者单位：Sapienza University Rome; Universidad de Chile; Harvard University; Tel Aviv University; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
  摘要：We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the (1- E)-competition complexity of different types of online algorithms. This metric asks for the smallest k such that the expected value of the online algorithm on k copies of the original instance is at least a (1 - E)-approximation to the expected off-line optimum on a single copy. We show that block threshold algorithms, which set one threshold per copy, are optimal an...
• On the Set of Balanced Games AI翻译
  作者：Garcia-Segador, Pedro; Grabisch, Michel; Miranda, Pedro
  作者单位：Paris School of Economics; Complutense University of Madrid
  摘要：We study the geometric structure of the set of cooperative transferable utility games having a nonempty core, characterized by Bondareva and Shapley as balanced games. We show that this set is a nonpointed polyhedral cone, and we find the set of its extremal rays and facets. This study is also done for the set of balanced games whose value for the grand coalition is fixed, which yields an affine nonpointed polyhedral cone. Finally, the case of nonnegative balanced games with fixed value for th...
• On the Convex Formulations of Robust Markov Decision Processes AI翻译
  作者：Grand-Clement, Julien; Petrik, Marek
  作者单位：University System Of New Hampshire; University of New Hampshire
  摘要：Robust Markov decision processes (MDPs) are used for applications of dynamic optimization in uncertain environments and have been studied extensively. Many of the main properties and algorithms of MDPs, such as value iteration and policy iteration, extend directly to RMDPs. Surprisingly, there is no known analog of the MDP convex optimization formulation for solving RMDPs. This work describes the first convex optimization formulation of RMDPs under the classical sa-rectangularity and s-rectang...
• An Approximation to the Invariant Measure of the Limiting Diffusion of G/Ph/n plus GI Queues in the Halfin-Whitt Regime and Related Asymptotics AI翻译
  作者：Jin, Xinghu; Pang, Guodong; Xu, Lihu; Xu, Xin
  作者单位：Hefei University of Technology; University of Macau; Rice University; South China Normal University
  摘要：In this paper, we develop a stochastic algorithm based on the Euler-Maruyama scheme to approximate the invariant measure of the limiting multidimensional diffusion of G/Ph/n + GI queues in the Halfin-Whitt regime. Specifically, we prove a nonasymptotic error bound between the invariant measures of the approximate model from the algorithm and the limiting diffusion. To establish the error bound, we employ the recently developed Stein's method for multidimensional diffusions, in which the regula...
• Sample-Path Large Deviations for Unbounded Additive Functionals of the Reflected Random Walk AI翻译
  作者：Bazhba, Mihail; Blanchet, Jose; Rhee, Chang-Han; Zwart, Bert
  作者单位：University of Amsterdam; Stanford University; Northwestern University; Eindhoven University of Technology
  摘要：We prove a sample -path large deviation principle (LDP) with sublinear speed for unbounded functionals of certain Markov chains induced by the Lindley recursion. The LDP holds in the Skorokhod space D[0, 1] equipped with the M ' 1 topology. Our technique hinges on a suitable decomposition of the Markov chain in terms of regeneration cycles. Each regeneration cycle denotes the area accumulated during the busy period of the reflected random walk. We prove a large deviation principle for the area...