-
作者：Bonamy, Marthe; Pilipczuk, Michal; Sereni, Jean-Sebastien; Weber, Richard
作者单位：Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); University of Warsaw; University of Cambridge
摘要：We consider a classic rendezvous game in which two players try to meet each other on a set of n locations. In each round, every player visits one of the locations, and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymmetric case, when the strategies of the players may differ, it is known that the optimum expected waiting time of (n + 1)/2 is achieved by the wai...
-
作者：Flesch, Janos; Predtetchinski, Arkadi; Suomala, Ville
作者单位：Maastricht University; Maastricht University; University of Oulu
摘要：The paper proposes a natural measure space of zero-sum perfect information games with upper semicontinuous payoffs. Each game is specified by the game tree and by the assignment of the active player and the capacity to each node of the tree. The payoff in a game is defined as the infimum of the capacity over the nodes that have been visited during the play. The active player, the number of children, and the capacity are drawn from a given joint distribution independently across the nodes. We c...
-
作者：Yu, Lun; Perry, Ohad
作者单位：Tsinghua University; Northwestern University
摘要：We characterize heavy-traffic process and steady-state limits for systems staffed according to the square-root safety rule, when the service requirements of the customers are perfectly correlated with their individual patience for waiting in queue. Under the usual many-server diffusion scaling, we show that the system is asymptotically equivalent to a system with no abandonment. In particular, the limit is the Halfin-Whitt diffusion for the M/M/n queue when the traffic intensity approaches its...
-
作者：Drusvyatskiy, Dmitriy; Xiao, Lin
作者单位：University of Washington; University of Washington Seattle; Facebook Inc
摘要：Stochastic optimization problems often involve data distributions that change in reaction to the decision variables. This is the case, for example, when members of the population respond to a deployed classifier by manipulating their features so as to improve the likelihood of being positively labeled. Recent works on performative prediction identify an intriguing solution concept for such problems: find the decision that is optimal with respect to the static distribution that the decision ind...
-
作者：Guo, Xin; Hu, Anran; Xu, Renyuan; Zhang, Junzi
作者单位：University of California System; University of California Berkeley; Amazon.com; University of Southern California; University of Oxford; Stanford University
摘要：This paper presents a general mean-field game (GMFG) framework for simultaneous learning and decision making in stochastic games with a large population. It first establishes the existence of a unique Nash equilibrium to this GMFG, and it demonstrates that naively combining reinforcement learning with the fixed-point approach in classical mean-field games yields unstable algorithms. It then proposes value-based and policy-based reinforcement learning algorithms (GMF-V and GMF-P, respectively) ...
-
作者：Nutz, Marcel; Zhang, Yuchong
作者单位：Columbia University; University of Toronto
摘要：We formulate a mean field game where each player stops a privately observed Brownian motion with absorption. Players are ranked according to their level of stopping and rewarded as a function of their relative rank. There is a unique mean field equilibrium, and it is shown to be the limit of associated n-player games. Conversely, the mean field strategy induces n-player epsilon-Nash equilibria for any continuous reward function-but not for discontinuous ones. In a second part, we study the pro...
-
作者：Duvocelle, Benoit; Mertikopoulos, Panayotis; Staudigl, Mathias; Vermeulen, Dries
作者单位：Maastricht University; Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Maastricht University
摘要：We examine the long-run behavior of multiagent online learning in games that evolve over time. Specifically, we focus on a wide class of policies based on mirror descent, and we show that the induced sequence of play (a) converges to a Nash equilibrium in time-varying games that stabilize in the long run to a strictly monotone limit, and (b) it stays asymptotically close to the evolving equilibrium of the sequence of stage games (assuming they are strongly monotone). Our results apply to both ...
-
作者：Ghossoub, Mario; Hall, Jesse; Saunders, David
作者单位：University of Waterloo
摘要：We consider the problemof determining an upper bound for the value of a spectral risk measure of a loss that is a general nonlinear function of two factors whose marginal distributions are known but whose joint distribution is unknown. The factors may take values in complete separable metric spaces. We introduce the notion of Maximum Spectral Measure (MSM), as a worst-case spectral risk measure of the loss with respect to the dependence between the factors. The MSM admits a formulation as a so...
-
作者：Gao, Rui; Kleywegt, Anton
作者单位：University of Texas System; University of Texas Austin; University System of Georgia; Georgia Institute of Technology
摘要：Distributionally robust stochastic optimization (DRSO) is an approach to optimization under uncertainty in which, instead of assuming that there is a known true underlying probability distribution, one hedges against a chosen set of distributions. In this paper, we first point out that the set of distributions should be chosen to be appropriate for the application at hand and some of the choices that have been popular until recently are, for many applications, not good choices. We next conside...
-
作者：Cominetti, Roberto; Scarsini, Marco; Schroder, Marc; Stier-Moses, Nicolas
作者单位：Universidad Adolfo Ibanez; Luiss Guido Carli University; Maastricht University
摘要：We consider the question of whether and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. In the first setting, we consider games in which each player's weight is small. We prove that when the number of players goes to infinity and their weights to zero, the random flows in all (mixed) Nash equilibria for the finite games converge...
