-
作者：Manshadi, Vahideh H.; Gharan, Shayan Oveis; Saberi, Amin
作者单位：Massachusetts Institute of Technology (MIT); Stanford University
摘要：We consider the online stochastic matching problem proposed by Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 - 1/e. Annual IEEE Sympos. Foundations Comput. Sci. 117-126] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins, and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribut...
-
作者：Henrion, Rene; Moeller, Andris
作者单位：Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
摘要：We provide an explicit gradient formula for linear chance constraints under a (possibly singular) multivariate Gaussian distribution. This formula allows one to reduce the calculus of gradients to the calculus of values of the same type of chance constraints (in smaller dimension and with different distribution parameters). This is an important aspect for the numerical solution of stochastic optimization problems because existing efficient codes for, e.g., calculating singular Gaussian distrib...
-
作者：Fibich, Gadi; Gavish, Nir
作者单位：Tel Aviv University
摘要：We introduce a new approach for analysis and numerical simulations of asymmetric first-price auctions, which is based on dynamical systems. We apply this approach to asymmetric auctions in which players' valuations are power-law distributed. We utilize a dynamical-systems formulation to provide a proof of the existence and uniqueness of the equilibrium strategies in the cases of two coalitions and of two types of players. In the case of n different players, the singular point of the original s...
-
作者：Del Pia, Alberto
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Let L be a family of lattice-free polyhedra in R-m containing the splits. Given a polyhedron P in Rm+n, we characterize when a valid inequality for P boolean AND (Z(n) x R-n) can be obtained with a finite number of disjunctive cuts corresponding to the polyhedra in L. We also characterize the lattice-free polyhedra M such that all the disjunctive cuts corresponding to M can be obtained with a finite number of disjunctive cuts corresponding to the polyhedra in L for every polyhedron P. Our resu...
-
作者：Feinberg, Eugene A.; Kasyanov, Pavlo O.; Zadoianchuk, Nina V.
作者单位：State University of New York (SUNY) System; Stony Brook University; Ministry of Education & Science of Ukraine; Igor Sikorsky Kyiv Polytechnic Institute; National Academy of Sciences Ukraine; Institute for Applied System Analysis of the National Technical University of Ukraine Igor Sikorsky Kyiv Polytechnic Institute
摘要：This paper presents sufficient conditions for the existence of stationary optimal policies for average cost Markov decision processes with Borel state and action sets and weakly continuous transition probabilities. The one-step cost functions may be unbounded, and the action sets may be noncompact. The main contributions of this paper are: (i) general sufficient conditions for the existence of stationary discount optimal and average cost optimal policies and descriptions of properties of value...
-
作者：Busic, Ana; Vliegen, Ingrid; Scheller-Wolf, Alan
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); University of Twente; Carnegie Mellon University
摘要：Solving Markov chains is, in general, difficult if the state space of the chain is very large (or infinite) and lacking a simple repeating structure. One alternative to solving such chains is to construct models that are simple to analyze and provide bounds for a reward function of interest. We present a new bounding method for Markov chains inspired by Markov reward theory: Our method constructs bounds by redirecting selected sets of transitions, facilitating an intuitive interpretation of th...
-
作者：Xu, Huan; Caramanis, Constantine; Mannor, Shie
作者单位：National University of Singapore; University of Texas System; University of Texas Austin; Technion Israel Institute of Technology
摘要：Motivated by data-driven decision making and sampling problems, we investigate probabilistic interpretations of robust optimization (RO). We establish a connection between RO and distributionally robust stochastic programming (DRSP), showing that the solution to any RO problem is also a solution to a DRSP problem. Specifically, we consider the case where multiple uncertain parameters belong to the same fixed dimensional space and find the set of distributions of the equivalent DRSP problem. Th...
-
作者：Sezer, Ali Devin; Haksoz, Cagn
作者单位：Middle East Technical University; Sabanci University
摘要：We consider a hypothetical company that is assumed to have just manufactured and sold a number of copies of a product. It is known that, with a small probability, the company has committed a manufacturing fault that will require a recall. The company is able to observe the expiration times of the sold items whose distribution depends on whether the fault is present or absent. At the expiration of each item, a public inspection takes place that may reveal the fault, if it exists. Based on this ...
-
作者：Harks, Tobias; Klimm, Max
作者单位：Maastricht University; Technical University of Berlin
摘要：We study the existence of pure Nash equilibria in weighted congestion games. Let C denote a set of cost functions. We say that C is consistent if every weighted congestion game with cost functions in C possesses a pure Nash equilibrium. Our main contribution is a complete characterization of consistency of continuous cost functions. We prove that a set C of continuous functions is consistent for two-player games if and only if C contains only monotonic functions and for all nonconstant functio...
-
作者：Bouchard, Bruno; Thanh Nam Vu
作者单位：Universite PSL; Universite Paris-Dauphine; Institut Polytechnique de Paris; ENSAE Paris
摘要：Within a Brownian diffusion Markovian framework, we provide a direct PDE characterization of the minimal initial endowment required so that the terminal wealth of a financial agent (possibly diminished by the payoff of a random claim) can match a set of constraints in probability. Such constraints should be interpreted as a rough description of a targeted profit and loss (P&L) distribution. This allows us to give a price to options under a P&L constraint, or to provide a description of the dis...
