-
作者：Kunimoto, Takashi; Serrano, Roberto
作者单位：Singapore Management University; Brown University
摘要：A new condition, which we call uniform monotonicity, is shown to be necessary and almost sufficient for rationalizable implementation of correspondences. Uniform monotonicity is much weaker than Maskin monotonicity and reduces to it in the case of functions. Maskin monotonicity, the key condition for Nash implementation, had also been shown to be necessary for rationalizable implementation of social choice functions. Our conclusion is that the conditions for rationalizable implementation are n...
-
作者：Syrgkanis, Vasilis; Kempe, David; Tardos, Eva
作者单位：Microsoft; University of Southern California; Cornell University
摘要：We consider common-value hybrid auctions among two asymmetrically informed bidders, in which the winning bidder pays his bid with some positive probability kappa and the losing bid otherwise. Under the assumption of discrete and affiliated signals, we give an explicit characterization of the (unique) equilibrium based on a simple recurrence relation, which gives rise to a linear-time algorithm for explicitly computing the equilibrium. By analyzing the execution of the algorithm, we derive seve...
-
作者：Lewis, Mark E.; Paul, Anand
-
作者：Cevallos, Alfonso; Eisenbrand, Friedrich; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so that the sum of all of their ((k)(2) ) Euclidean distances is maximized. This problem has recently received a lot of attention in the context of information retrieval and web search. We focus on distances of negative type, a class that includes...
-
作者：Correa, Jose R.; de Jong, Jasper; de Keijzer, Bart; Uetz, Marc
作者单位：Universidad de Chile; University of Twente; University of Essex
摘要：This paper provides new bounds on the quality of equilibria in finite congestion games with affine cost functions, specifically for atomic network routing games. It is well known that the price of anarchy equals exactly 5/2 in general. For symmetric network routing games, it is at most (5n - 2)/(2n + 1), where n is the number of players. This paper answers to two open questions for congestion games. First, we show that the price of anarchy bound (5n - 2)/(2n + 1) is tight for symmetric network...
-
作者：Nutz, Marcel; Zhang, Yuchong
作者单位：Columbia University; Columbia University; University of Toronto
摘要：We introduce a mean field game with rank-based reward: competing agents optimize their effort to achieve a goal, are ranked according to their completion time, and are paid a reward based on their relative rank. First, we propose a tractable Poissonian model in which we can describe the optimal effort for a given reward scheme. Second, we study the principal-agent problem of designing an optimal reward scheme. A surprising, explicit design is found to minimize the time until a given fraction o...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco; Paat, Joseph
作者单位：Johns Hopkins University; University of Padua; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The infinite models in integer programming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper, we study the relationships between these two descriptions. Our results have implications for corner polyhedra. One consequence is that nonnegative, continuous valid functions suffice to describe corner polyhedra (with or without rational data).
-
作者：Ahmadinejad, AmirMahdi; Dehghani, Sina; Hajiaghayi, MohammadTaghi; Loder, Brendan; Mahini, Hamid; Seddighin, Saeed
作者单位：Stanford University; University System of Maryland; University of Maryland College Park; Microsoft; University of Tehran
摘要：In the well-studied Colonel Blotto game, players must divide a pool of troops among a set of battlefields with the goal of winning a majority. Despite the importance of this game, only a few solutions for special variants of the problem are known. We provide a general technique for computing equilibria of the Colonel Blotto game. Our approach applies to variations of the Colonel Blotto game as well, including an infinite-strategy variant called the General Lotto game. We also apply our techniq...
-
作者：Bruggmann, Simon; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The simplex algorithm for linear programming is based on the fact that any local optimum with respect to the polyhedral neighborhood is also a global optimum. We show that a similar result carries over to submodular maximization. In particular, every local optimum of a constrained monotone submodular maximization problem yields a 1/2-approximation, and we also present an appropriate extension to the nonmonotone setting. Moreover, we describe a very general local search procedure that applies t...
-
作者：Hungerford, James T.; Rinaldi, Francesco
作者单位：University of Padua
摘要：In this paper, we develop a general regularization-based continuous optimization framework for the maximum clique problem. In particular, we consider a broad class of regularization terms that can be included in the classic Motzkin-Straus formulation, and we develop conditions that guarantee the equivalence between the continuous regularized problem and the original one in both a global and a local sense. We further analyze, from a computational point of view, two different regularizers that s...
