-
作者：Amarante, Massimiliano
作者单位：Universite de Montreal; Universite de Montreal
摘要：In the context of decision making under uncertainty, I formalize the concept of analogy: an analogy between two decision problems is a mapping that transforms one problem into the other while preserving the problem's structure. After identifying the basic structure of a decision problem, I introduce the concepts of analogical reasoning operator and of analogical reasoning preference. The former maps the decision problem at hand into a family of decision problems, which are analogous to the pro...
-
作者：Bhaskar, Umang; Fleischer, Lisa; Hoy, Darrell; Huang, Chien-Chung
作者单位：California Institute of Technology; Dartmouth College; Northwestern University; Chalmers University of Technology
摘要：In routing games with infinitesimal players, it follows from well-known convexity arguments that equilibria exist and are unique. In routing games with atomic players with splittable flow, equilibria exist, but uniqueness of equilibria has been demonstrated only in limited cases: in two-terminal nearly parallel graphs, when all players control the same amount of flow, and when latency functions are polynomials of degree at most three. There are no known examples of multiple equilibria in these...
-
作者：Huynh Van Ngai; Phan Nhat Tinh
作者单位：Hue University
摘要：Metric subregularity and regularity of multifunctions are fundamental notions in variational analysis and optimization. Using the concept of strong slope, in this paper we first establish a criterion for metric subregularity of multifunctions between metric spaces. Next, we use a combination of abstract coderivatives and contingent derivatives to derive verifiable first order conditions ensuring metric subregularity of multifunctions between Banach spaces. Then using second order approximation...
-
作者：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...
