-
作者：Badenbroek, Riley; de Klerk, Etienne
作者单位：Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam; Tilburg University
摘要：We develop a short-step interior point method to optimize a linear function over a convex body assuming that one only knows a membership oracle for this body. The approach is based a sketch of a universal interior point method using the so-called entropic barrier. It is well known that the gradient and Hessian of the entropic barrier can be approximated by sampling from Boltzmann-Gibbs distributions and the entropic barrier was shown to be self-concordant. The analysis of our algorithm uses pr...
-
作者：Basei, Matteo; Cao, Haoyang; Guo, Xin
作者单位：University of California System; University of California Berkeley; Electricite de France (EDF); Alan Turing Institute
摘要：We consider a general class of nonzero-sum N-player stochastic games with impulse controls, where players control the underlying dynamics with discrete interventions. We adopt a verification approach and provide sufficient conditions for the Nash equilibria (NEs) of the game. We then consider the limiting situation when N goes to infinity, that is, a suitable mean-field game (MFG) with impulse controls. We show that under appropriate technical conditions, there exists a unique NE solution to t...
-
作者：Gutekunst, Samuel C.; Williamson, David P.
作者单位：Bucknell University; Bucknell University; Cornell University
摘要：The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suita...
-
作者：Abdou, Joseph; Pnevmatikos, Nikolaos; Scarsini, Marco; Venel, Xavier
作者单位：Universite Paris-Pantheon-Assas; Luiss Guido Carli University
摘要：Orthogonal direct-sum decompositions of finite games into potential, harmonic and nonstrategic components exist in the literature. In this paper we study the issue of decomposing games that are strategically equivalent from a game-theoretical point of view, for instance games obtained via transformations such as duplications of strategies or positive affine mappings of the payoffs. We show the need to define classes of decompositions to achieve commutativity of game transformations and decompo...
-
作者：Klimm, Max; Warode, Philipp
作者单位：Technical University of Berlin
摘要：We develop algorithms solving parametric flow problems with separable, continuous, piecewise quadratic, and strictly convex cost functions. The parameter to be considered is a common multiplier on the demand of all nodes. Our algorithms compute a family of flows that are each feasible for the respective demand and minimize the costs among the feasible flows for that demand. For single commodity networks with homogenous cost functions, our algorithm requires one matrix multiplication for the in...
-
作者：Hellman, Ziv; Levy, Yehuda John
作者单位：Bar Ilan University; University of Glasgow
摘要：We study dynamic properties of the group action on the simplex that is induced by Bayesian updating. We show that, generically, the orbits are dense in the simplex, although one must make use of the entire group, hence departing from straightforward Bayesian updating. We demonstrate also the necessity of the genericity of the signalling structure, a relationship to descriptive set theoretical concepts, and applications thereof to repeated games of incomplete information, as well a strengthenin...
-
作者：Feinstein, Zachary; Rudloff, Birgit; Zhang, Jianfeng
作者单位：Stevens Institute of Technology; Vienna University of Economics & Business; University of Southern California
摘要：Nonzero sum games typically have multiple Nash equilibriums (or no equilibrium), and unlike the zero-sum case, they may have different values at different equilibriums. Instead of focusing on the existence of individual equilibriums, we study the set of values over all equilibriums, which we call the set value of the game. The set value is unique by nature and always exists (with possible value 0). Similar to the standard value function in control literature, it enjoys many nice properties, su...
-
作者：Hellman, Ziv; Levy, Yehuda John
作者单位：Bar Ilan University; University of Glasgow
摘要：The solution concept of a Bayesian equilibrium of a Bayesian game is inherently an interim concept. The corresponding ex ante solution concept has been termed a Harsanyi equilibrium; examples have appeared in the literature showing that there are Bayesian games with uncountable state spaces that have no Bayesian approximate equilibria but do admit a Harsanyi approximate equilibrium, thus exhibiting divergent behaviour in the ex ante and interim stages. Smoothness, a concept from descriptive se...
-
作者：Giannakopoulos, Yiannis; Noarov, Georgy; Schulz, Andreas S.
作者单位：University of Erlangen Nuremberg; University of Pennsylvania; Technical University of Munich
摘要：We present a deterministic polynomial-time algorithm for computing d(d+o(d))-approximate (pure) Nash equilibria in (proportional sharing) weighted congestion games with polynomial cost functions of degree at most d. This is an exponential improvement of the approximation factor with respect to the previously best deterministic algorithm. An appealing additional feature of the algorithm is that it only uses best-improvement steps in the actual game, as opposed to the previously best algorithms,...
-
作者：Atar, Rami; Budhiraja, Amarjit; Dupuis, Paul; Wu, Ruoyu
作者单位：Technion Israel Institute of Technology; University of North Carolina; University of North Carolina Chapel Hill; Brown University; Iowa State University
摘要：For the M/M/1+M model at the law-of-large-numbers scale, the long-run reneging count per unit time does not depend on the individual (i.e., per customer) reneging rate. This paradoxical statement has a simple proof. Less obvious is a large deviations analogue of this fact, stated as follows: the decay rate of the probability that the long-run reneging count per unit time is atypically large or atypically small does not depend on the individual reneging rate. In this paper, the sample path larg...
