Mathematics of Operations Research

最新文章

• 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(...
• On the Existence of Pairwise Stable Weighted Networks AI翻译
  作者：Bich, Philippe; Morhaim, Lisa
  作者单位：Paris School of Economics; Universite Paris-Pantheon-Assas
  摘要：In network theory, Jackson and Wolinsky introduced a now widely used notion of stability for unweighted network formation called pairwise stability. We prove the existence of pairwise stable weighted networks under assumptions on payoffs that are similar to those in Nash's and Glicksberg's existence theorem (continuity and quasi concavity). Then, we extend our result, allowing payoffs to depend not only on the network, but also on some game-theoretic strategies. The proof is not a standard app...
• Multiconstrained Finite-Horizon Piecewise Deterministic Markov Decision Processes with Unbounded Transition Rates AI翻译
  作者：Huang, Yonghui; Guo, Xianping
  作者单位：Sun Yat Sen University
  摘要：This paper studies a multiconstrained problem for piecewise deterministic Markov decision processes (PDMDPs) with unbounded cost and transition rates. The goal is to minimize one type of expected finite-horizon cost over history-dependent policies while keeping some other types of expected finite-horizon costs lower than some tolerable bounds. Using the Dynkin formula for the PDMDPs, we obtain an equivalent characterization of occupancy measures and express the expected finite-horizon costs in...
• Approximate Markov-Nash Equilibria for Discrete-Time Risk-Sensitive Mean-Field Games AI翻译
  作者：Saldi, Naci; Basar, Tamer; Raginsky, Maxim
  作者单位：Ozyegin University; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：In this paper, we study a class of discrete-time mean-field games under the infinite-horizon risk-sensitive optimality criterion. Risk sensitivity is introduced for each agent (player) via an exponential utility function. In this game model, each agent is coupled with the rest of the population through the empirical distribution of the states, which affects both the agent's individual cost and its state dynamics. Under mild assumptions, we establish the existence of a mean-field equilibrium in...
• Stochastic Recursive Inclusions in Two Timescales with Nonadditive Iterate-Dependent Markov Noise AI翻译
  作者：Yaji, Vinayaka G.; Bhatnagar, Shalabh
  作者单位：Indian Institute of Science (IISC) - Bangalore
  摘要：In this paper, we study the asymptotic behavior of a stochastic approximation scheme on two timescales with set-valued drift functions and in the presence of non-additive iterate-dependent Markov noise. We show that the recursion on each timescale tracks the flow of a differential inclusion obtained by averaging the set-valued drift function in the recursion with respect to a set of measures accounting for both averaging with respect to the stationary distributions of the Markov noise terms an...
• Greed Works-Online Algorithms for Unrelated Machine Stochastic Scheduling AI翻译
  作者：Gupta, Varun; Moseley, Benjamin; Uetz, Marc; Xie, Qiaomin
  作者单位：University of Chicago; Carnegie Mellon University; University of Twente; Massachusetts Institute of Technology (MIT)
  摘要：This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of...
• Acyclic Gambling Games AI翻译
  作者：Laraki, Rida; Renault, Jerome
  作者单位：Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine; University of Liverpool; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
  摘要：We consider two-player, zero-sumstochastic games in which each player controls the player's own state variable living in a compact metric space. The terminology comes from gambling problems in which the state of a player represents its wealth in a casino. Under standard assumptions (e.g., continuous running payoff and nonexpansive transitions), we consider for each discount factor the value v(lambda) of the lambda-discounted stochastic game and investigate its limit when lambda goes to zero. W...
• The Computational Complexity of Integer Programming with Alternations AI翻译
  作者：Danny Nguyen; Pak, Igor
  作者单位：University of Michigan System; University of Michigan; University of California System; University of California Los Angeles
  摘要：We prove that integer programming with three alternating quantifiers is NP-complete, even for a fixed number of variables. This complements earlier results by Lenstra [16] [Lenstra H (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538-5481 and Kannan [13,14] [Kannan R (1990) Test sets for integer programs, for all there exists sentences. Polyhedral Combinatorics (American Mathematical Society, Providence, RI), 39-47. Kannan R (1992) Lattice translates of a po...