-
作者：Dao, Minh N.; Phan, Hung M.
作者单位：University of Newcastle; University of Massachusetts System; University of Massachusetts Lowell
摘要：Projection algorithms are well known for their simplicity and flexibility in solving feasibility problems. They are particularly important in practice owing to minimal requirements for software implementation and maintenance. In this work, we study linear convergence of several projection algorithms for systems of finitely many closed sets. The results complement contemporary research on the same topic.
-
作者：Bubeck, Sebastien; Eldan, Ronen
作者单位：Microsoft; Weizmann Institute of Science
摘要：We prove that the Cramer transform of the uniform measure on a convex body in R-n is a (1 + o(1))n-self-concordant barrier, improving a seminal result of Nesterov and Nemirovski. This gives the first explicit construction of a universal barrier for convex bodies with optimal self-concordance parameter. The proof is based on basic geometry of log-concave distributions and elementary duality in exponential families. As a side result, our calculations also show that the universal barrier of Neste...
-
作者：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...
-
作者：Bet, Gianmarco; van der Hofstad, Remco; van Leeuwaarden, Johan S. H.
作者单位：Eindhoven University of Technology
摘要：We consider a single-server queue that serves a finite population of n customers that will enter the queue (require service) only once, also known as the Delta((i))/G/1 queue. This paper presents a method for analyzing heavy-traffic behavior by using uniform acceleration, which simultaneously lets n and the service rate grow large, while the initial resource utilization approaches one. A key feature of the model is that, as time progresses, more customers have joined the queue, and fewer custo...
-
作者：Haimanko, Ori
作者单位：Ben-Gurion University of the Negev
摘要：We consider semivalues on pM(infinity)-a vector space of games with a continuum of players (among which there may be atoms) that possess a robust differentiability feature. We introduce the notion of a derivative semivalue on pM(infinity) and extend the standard Banzhaf value from the domain of finite games onto pM(infinity) as a certain particularly simple derivative semivalue. Our main result shows that any semivalue on pM(infinity) is a derivative semivalue. It is also shown that the Banzha...
-
作者：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...
-
作者：Chen, Qi (George); Jasin, Stefanus; Duenyas, Izak
作者单位：University of London; London Business School; University of Michigan System; University of Michigan
摘要：We study a multiperiod network revenue management problem where a seller sells multiple products made from multiple resources with finite capacity in an environment where the underlying demand function is a priori unknown (in the nonparametric sense). The objective of the seller is to simultaneously learn the unknown demand function and dynamically price the products to minimize the expected revenue loss. For the problem where the number of selling periods and initial capacity are scaled by k ...
-
作者：Lacker, Daniel; Ramanan, Kavita
作者单位：Columbia University; Brown University
摘要：We study a static game played by a finite number of agents, in which agents are assigned independent and identically distributed random types and each agent minimizes its objective function by choosing from a set of admissible actions that depends on its type. The game is anonymous in the sense that the objective function of each agent depends on the actions of other agents only through the empirical distribution of their type-action pairs. We study the asymptotic behavior of Nash equilibria, ...
-
作者：Gensbittel, Fabien; Grun, Christine
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：We study a model of two-player, zero-sum, stopping games with asymmetric information. We assume that the payoff depends on two independent continuous-time Markov chains, where the first Markov chain is only observed by player 1 and the second Markov chain is only observed by player 2, implying that the players have access to stopping times with respect to different filtrations. We show the existence of a value in mixed stopping times and provide a variational characterization for the value as ...
