-
作者：Cardaliaguet, Pierre; Rainer, Catherine; Rosenberg, Dinah; Vieille, Nicolas
作者单位：Universite PSL; Universite Paris-Dauphine; Universite de Bretagne Occidentale; Hautes Etudes Commerciales (HEC) Paris
摘要：We study the asymptotics of a class of two-player, zero-sum stochastic game with incomplete information on one side when the time span between two consecutive stages vanishes. The informed player observes the realization of a Markov chain on which the payoffs depend, whereas the noninformed player only observes his opponent's actions. We show the existence of a limit value; this value is characterized through an auxiliary optimization problem and as the solution of a Hamilton-Jacobi equation.
-
作者：Arlotto, Alessandro; Steele, J. Michael
作者单位：Duke University; University of Pennsylvania
摘要：We prove a central limit theorem for a class of additive processes that arise naturally in the theory of finite horizon Markov decision problems. The main theorem generalizes a classic result of Dobrushin for temporally nonhomogeneous Markov chains, and the principal innovation is that here the summands are permitted to depend on both the current state and a bounded number of future states of the chain. We show through several examples that this added flexibility gives one a direct path to asy...
-
作者：Yildiz, Sercan; Cornuejols, Gerard
作者单位：Carnegie Mellon University
摘要：For an integer linear program, Gomory's corner relaxation is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In this paper, we do not relax these nonnegativity constraints. We generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our result is based on the notion of generalized symmetry condition. We also prove a 2-slope theorem for extreme cut-generating ...
-
作者：Grandits, Peter
作者单位：Technische Universitat Wien
摘要：We give an algorithmic solution of the optimal consumption problem sup(C) integral([0, tau]) e(-beta t) dC(t), where C-t denotes the accumulated consumption until time t, and tau denotes the time of ruin. Moreover, the endowment process X-t is modeled by X-t = x + integral(t)(0) mu(X-s) ds - C-t. We solve the problem by showing that the function provided by the algorithm solves the Hamilton-Jacobi (HJ) equation in a viscosity sense and that the same is true for the value function of the proble...
-
作者：Feinberg, Eugene A.; Kasyanov, Pavlo O.; Zgurovsky, Michael Z.
作者单位：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; Ministry of Education & Science of Ukraine; Igor Sikorsky Kyiv Polytechnic Institute
摘要：This paper describes sufficient conditions for the existence of optimal policies for partially observable Markov decision processes (POMDPs) with Borel state, observation, and action sets, when the goal is to minimize the expected total costs over finite or infinite horizons. For infinite-horizon problems, one-step costs are either discounted or assumed to be nonnegative. Action sets may be noncompact and one-step cost functions may be unbounded. The introduced conditions are also sufficient f...
-
作者：Balkenborg, Dieter; Vermeulen, Dries
作者单位：University of Exeter; Maastricht University
摘要：A minimal diversity game is an n player strategic form game in which each player has m pure strategies at his disposal. The payoff to each player is always 1, unless all players select the same pure strategy, in which case, all players receive zero payoff. Such a game has a unique isolated completely mixed Nash equilibrium in which each player plays each strategy with equal probability, and a connected component of Nash equilibria consisting of those strategy profiles in which each player rece...
-
作者：Cominetti, Roberto; Torrico, Alfredo
作者单位：Universidad de Chile; Universidad de Chile
摘要：We investigate the use of risk measures and theories of choice to model risk-averse routing and traffic equilibrium on networks with random travel times. We interpret the postulates of these theories in the context of routing, identifying additive consistency as a plausible condition that allows to reduce risk-averse route choice to a standard shortest path problem. Within the classical theories of choice, we show that the only preferences that satisfy this condition are the ones induced by th...
-
作者：Gupta, Anupam; Molinaro, Marco
作者单位：Carnegie Mellon University; Pontificia Universidade Catolica do Rio de Janeiro
摘要：We consider the problem of solving packing/covering LPs online, when the columns of the constraint matrix are presented in random order. This problem has received much attention, and the main focus is to figure out how large the right-hand sides of the LPs have to be (compared to the entries on the left-hand side of the constraints) to allow (1 + epsilon)-approximations online. It is known that the right-hand sides have to be Omega (epsilon(-2) log m) times the left-hand sides, where m is the ...
-
作者：Gortz, Inge Li; Molinaro, Marco; Nagarajan, Viswanath; Ravi, R.
作者单位：Technical University of Denmark; University System of Georgia; Georgia Institute of Technology; University of Michigan System; University of Michigan; Carnegie Mellon University
摘要：The capacitated vehicle routing problem (CVRP) involves distributing identical items from a depot to a set of demand locations using a single capacitated vehicle. We introduce the heterogeneous capacitated vehicle routing problem, a generalization of CVRP to the setting of multiple vehicles having nonuniform speeds, and present for it a constant-factor approximation algorithm. Our main contribution is an approximation algorithm for the heterogeneous traveling salesman problem, which is the spe...
-
作者：Flesch, Janos; Predtetchinski, Arkadi
作者单位：Maastricht University; Maastricht University
摘要：We prove the existence of a pure subgame-perfect epsilon-equilibrium, for every epsilon > 0, in multiplayer perfect information games, provided that the payoff functions are bounded and exhibit common preferences at the limit. If, in addition, the payoff functions have finite range, then there exists a pure subgame-perfect 0-equilibrium. These results extend and unify recent existence theorems for bounded and semicontinuous payoffs.
