-
作者：Anthony, Barbara; Goyal, Vineet; Gupta, Anupam; Nagarajan, Viswanath
作者单位：Massachusetts Institute of Technology (MIT); Carnegie Mellon University; International Business Machines (IBM); IBM USA
摘要：This paper studies an extension of the k-median problem under uncertain demand. We are given an n-vertex metric space (V, d) and m client sets {S-i subset of V}(i=1)(m). The goal is to open a set of k facilities F such that the worst-case connection cost over all the client sets is minimized, i.e., min(F subset of V,vertical bar F vertical bar=k) max(i is an element of[m]){Sigma(d(j,f))(j is an element of si)}, where for any F subset of V, d(j, F) = min(f is an element of F) d(j, f). This is a...
-
作者：Bogomolnaia, Anna; Holzman, Ron; Moulin, Herve
作者单位：Rice University; Technion Israel Institute of Technology
摘要：We consider a communication network where each pair of users requests a connection guaranteeing a certain capacity. The cost of building capacity is identical across pairs. Efficiency is achieved by any maximal cost spanning tree. We construct cost sharing methods ensuring standalone core stability, monotonicity of one's cost share in one's capacity requests, and continuity in everyone's requests. We define a solution for simple problems where each pairwise request is zero or one, and extend i...
-
作者：Bayraktar, Erhan; Egami, Masahiko
作者单位：University of Michigan System; University of Michigan; Kyoto University
摘要：We explicitly solve the optimal switching problem for one-dimensional diffusions by directly using the dynamic programming principle and the excessive characterization of the value function. The shape of the value function and the smooth fit principle then can be proved using the properties of concave functions.
-
作者：Dayanik, Savas
作者单位：Ihsan Dogramaci Bilkent University; Ihsan Dogramaci Bilkent University
摘要：Suppose that a Wiener process gains a known drift rate at some unobservable disorder time with some zero-modified exponential distribution. The process is observed only at known fixed discrete time epochs, which may not always be spaced in equal distances. The problem is to detect the disorder time as quickly as possible by means of an alarm that depends only on the observations of Wiener process at those discrete time epochs. We show that Bayes optimal alarm times, which minimize expected tot...
-
作者：Kindler, Guy; Naor, Assaf; Schechtman, Gideon
作者单位：Hebrew University of Jerusalem; New York University; Weizmann Institute of Science
摘要：For p >= 2 we consider the problem of, given an n x n matrix A = (a(ij)) whose diagonal entries vanish, approximating in polynomial time the number Opt(p)(A):= max{(i,j=1)Sigma(n) a(ij)x(i)x(j): (x(1), ..., x(n)) is an element of R-n boolean AND ((i=1)Sigma(n) vertical bar x(i)vertical bar(p))(1/p) <= 1}. When p = 2 this is simply the problem of computing the maximum eigenvalue of A, whereas for p = infinity ( actually it suffices to take p approximate to log n) it is the Grothendieck problem ...
-
作者：Bonifaci, Vincenzo; Harks, Tobias; Schafer, Guido
作者单位：Max Planck Society; Technical University of Berlin
摘要：We investigate the impact of Stackelberg routing to reduce the price of anarchy in network routing games. In this setting, an alpha fraction of the entire demand is first routed centrally according to a predefined Stackelberg strategy and the remaining demand is then routed selfishly by (nonatomic) players. Although several advances have been made recently in proving that Stackelberg routing can, in fact, significantly reduce the price of anarchy for certain network topologies, the central que...
-
作者：Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
作者单位：Cornell University; Hebrew University of Jerusalem; Yale University; University of California System; University of California Berkeley
摘要：In a combinatorial auction m heterogenous indivisible items are sold to n bidders. This paper considers settings in which the valuation functions of the bidders are known to be complement free (a.k.a. subadditive). We provide several approximation algorithms for the social-welfare maximization problem in such settings. First, we present a logarithmic upper bound for the case that the access to the valuation functions is via demand queries. For the weaker value queries model we provide a tight ...
-
作者：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...
