-
作者：Gensbittel, Fabien; Renault, Jerome
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：We consider zero-sum repeated games with incomplete information on both sides, where the states privately observed by each player follow independent Markov chains. It generalizes the model, introduced by Aumann and Maschler in the sixties and solved by Mertens and Zamir in the seventies, where the private states of the players were fixed. It also includes the model introduced in Renault [19] [Renault J (2006) The value of Markov chain games with lack of information on one side. Math. Oper. Res...
-
作者：Zhang, Xiaowei; Blanchet, Jose; Giesecke, Kay; Glynn, Peter W.
作者单位：Hong Kong University of Science & Technology; Columbia University; Stanford University
摘要：We establish a central limit theorem and a large deviations principle for affine point processes, which are stochastic models of correlated event timing widely used in finance and economics. These limit results generate closed-form approximations to the distribution of an affine point process. They also facilitate the construction of an asymptotically optimal importance sampling estimator of tail probabilities. Numerical tests illustrate our results.
-
作者：Elmachtoub, Adam N.; Levi, Retsef
作者单位：Columbia University; Massachusetts Institute of Technology (MIT)
摘要：We consider a general class of online optimization problems, called online selection problems, where customers arrive sequentially, and one has to decide upon arrival whether to accept or reject each customer. If a customer is rejected, then a rejection cost is incurred. The accepted customers are served with minimum possible cost, either online or after all customers have arrived. The goal is to minimize the total production costs for the accepted customers plus the rejection costs for the re...
-
作者：Dieker, A. B.; Vempala, Santosh S.
作者单位：Columbia University; University System of Georgia; Georgia Institute of Technology
摘要：Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov Chain Monte Carlo paradigm. This paper studies how many steps of the underlying Markov chain are required to get samples (approximately) from the uniform distribution on the boundary of the set, for sets with an upper bound on the curvature of the boundary. Our main theorem implies a polynomial-time algorithm for sampling from the boundary of such sets.
-
作者：Kwon, H. Dharma; Zhang, Hongzhong
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Columbia University
摘要：We investigate a game of singular control and strategic exit in a model of competitive market share control. In the model, each player can make irreversible investments to increase his market share, which is modeled as a diffusion process. In addition, each player has an option to exit the market at any point in time. We formulate a verification theorem for best responses of the game and characterize Markov perfect equilibria (MPE) under a set of verifiable assumptions. We find a class of MPEs...
-
作者：Bauso, Dario; Lehrer, Ehud; Solan, Eilon; Venel, Xavier
作者单位：University of Palermo; Tel Aviv University; INSEAD Business School
摘要：We introduce the concept of attainable sets of payoffs in two-player repeated games with vector payoffs. A set of payoff vectors is called attainable by a player if there is a positive integer such that the player can guarantee that in all finite game longer than that integer, the distance between the set and the cumulative payoff is arbitrarily small, regardless of the strategy Player 2 is using. We provide a necessary and sufficient condition for the attainability of a convex set, using the ...
-
作者：Kalai, Gil; Mossel, Elchanan
作者单位：Hebrew University of Jerusalem; Yale University; University of Pennsylvania; University of California System; University of California Berkeley
摘要：A key fact in the theory of Boolean functions f : {0, 1}(n) -> {0, 1} is that they often undergo sharp thresholds. For example, if the function f : {0, 1}(n) -> {0, 1} is monotone and symmetric under a transitive action with E-p[f] = epsilon and E-q[f] = 1 - epsilon, then q - p -> 0 as n -> infinity. Here E-p denotes the product probability measure on {0, 1}(n) where each coordinate takes the value 1 independently with probability p. The fact that symmetric functions undergo sharp thresholds i...
-
作者：Drusvyatskiy, Dmitriy; Ioffe, Alexander D.; Lewis, Adrian S.
作者单位：University of Washington; University of Washington Seattle; University of Waterloo; Technion Israel Institute of Technology; Cornell University
摘要：Using a geometric argument, we show that under a reasonable continuity condition, the Clarke subdifferential of a semi-algebraic (or more generally stratifiable) directionally Lipschitzian function admits a simple form: The normal cone to the domain and limits of gradients generate the entire Clarke subdifferential. The characterization formula we obtain unifies various apparently disparate results that have appeared in the literature. Our techniques also yield a simplified proof that closed s...
-
作者：Muthuraman, Kumar; Seshadri, Sridhar; Wu, Qi
作者单位：University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin; Indian School of Business (ISB); University System of Ohio; Case Western Reserve University
摘要：This article analyzes a continuous time back-ordered inventory system with stochastic demand and stochastic delivery lags for placed orders. This problem in general has an infinite dimensional state space and is hence intractable. We first obtain the set of minimal conditions for reducing such a system's state space to one dimension and show how this reduction is done. Next, by modeling demand as a diffusion process, we reformulate the inventory control problem as an impulse control problem. W...
-
作者：Basu, Amitabh; Hildebrand, Robert; Koeppe, Matthias
作者单位：Johns Hopkins University; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Davis
摘要：We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We also present an extreme function that is a piecewise linear function with some irrational breakpoints, whose extremality...
