-
作者：Alon, Noga; Feldman, Michal; Procaccia, Ariel D.; Tennenholtz, Moshe
作者单位：Microsoft; MICROSOFT ISRAEL; Tel Aviv University; Hebrew University of Jerusalem; Hebrew University of Jerusalem; Harvard University; Technion Israel Institute of Technology
摘要：We consider the problem of locating a facility on a network represented by a graph. A set of strategic agents have different ideal locations for the facility; the cost of an agent is the distance between its ideal location and the facility. A mechanism maps the locations reported by the agents to the location of the facility. We wish to design mechanisms that are strategyproof (SP) in the sense that agents can never benefit by lying and, at the same time, provide a small approximation ratio wi...
-
作者：Flesch, J.; Kuipers, J.; Schoenmakers, G.; Vrieze, K.
作者单位：Maastricht University; Maastricht University
摘要：We consider a class of n-player stochastic games with the following properties: (1) in every state, the transitions are controlled by one player; (2) the payoffs are equal to zero in every nonabsorbing state; (3) the payoffs are nonnegative in every absorbing state. We propose a new iterative method to analyze these games. With respect to the expected average reward, we prove the existence of a subgame-perfect epsilon-equilibrium in pure strategies for every epsilon > 0. Moreover, if all trans...
-
作者：Flesch, Janos; Kuipers, Jeroen; Mashiah-Yaakovi, Ayala; Schoenmakers, Gijs; Solan, Eilon; Vrieze, Koos
作者单位：Maastricht University; Maastricht University; Tel Aviv University
摘要：We prove that every multiplayer perfect-information game with bounded and lower-semicontinuous payoffs admits a subgame-perfect epsilon-equilibrium in pure strategies. This result complements Example 3 in Solan and Vieille [Solan, E., N. Vieille. 2003. Deterministic multi-player Dynkin games. J. Math. Econom. 39 911-929], which shows that a subgame-perfect epsilon-equilibrium in pure strategies need not exist when the payoffs are not lower-semicontinuous. In addition, if the range of payoffs i...
-
作者：Bertsimas, Dimitris; Goyal, Vineet
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right-hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as hypercube, ellipsoid or norm ball) and the probability measure is also ...
-
作者：Rusmevichientong, Paat; Tsitsiklis, John N.
作者单位：Cornell University; Massachusetts Institute of Technology (MIT)
摘要：We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an r-dimensional random vector Z is an element of R-r, where r >= 2. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order Theta(r root T), by establishing a lower bound for an arbitrary policy, and showing that a matching upper ...
-
作者：Faure, Mathieu; Roth, Gregory
作者单位：University of Neuchatel
摘要：A successful method to describe the asymptotic behavior of a discrete time stochastic process governed by some recursive formula is to relate it to the limit sets of a well-chosen mean differential equation. Under an attainability condition, Benaim proved that convergence to a given attractor of the flow induced by this dynamical system occurs with positive probability for a class of Robbins Monro algorithms. Benaim, Hofbauer, and Sorin generalised this approach for stochastic approximation al...
-
作者：Goberna, M. A.; Terlaky, T.; Todorov, M. I.
作者单位：Universitat d'Alacant; Lehigh University; Bulgarian Academy of Sciences; Universidad Americas Puebla (UDLAP)
摘要：This paper provides sufficient conditions for the optimal value function of a given linear semi-infinite programming (LSIP) problem to depend linearly on the size of the perturbations, when these perturbations involve either the cost coefficients or the right-hand side function or both, and they are sufficiently small. Two kinds of partitions are considered. The first concerns the effective domain of the optimal value as a function of the cost coefficients and consists of maximal regions on wh...
-
作者：Yu, Huizhen; Bertsekas, Dimitri P.
作者单位：University of Helsinki; Massachusetts Institute of Technology (MIT)
摘要：We consider linear fixed point equations and their approximations by projection on a low dimensional subspace. We derive new bounds on the approximation error of the solution, which are expressed in terms of low dimensional matrices and can be computed by simulation. When the fixed point mapping is a contraction, as is typically the case in Markov decision processes (MDP), one of our bounds is always sharper than the standard contraction-based bounds, and another one is often sharper. The form...
-
作者：Andersen, Kent; Louveaux, Quentin; Weismantel, Robert
作者单位：Otto von Guericke University; University of Liege
摘要：A maximal lattice free polyhedron L has max-facet-width equal to w if max(x is an element of L) pi(T) x-min(x is an element of L) pi(T) x <= w for all facets pi(T) x <= pi(0) of L, and max(x is an element of L) pi(T) x-min(x is an element of L) pi(T) x = w for some facet pi(T) x <= pi(0) of L. The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the wth split closure. We show the wth split closure is a polyhe...
-
作者：Vazirani, Vijay V.
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：The notion of a market has undergone a paradigm shift with the Internet. Totally new and highly successful markets have been defined and launched by Internet companies, which already form an important part of today's economy and are projected to grow considerably in the future. Another major change is the availability of massive computational power for running these markets in a centralized or distributed manner. In view of these new realities, the study of market equilibria, an important, tho...
