-
作者：Lu, Zhaosong; Mei, Sanyou
作者单位：University of Minnesota System; University of Minnesota Twin Cities; Hong Kong University of Science & Technology
摘要：In this paper, we propose a sequential minimax optimization (SMO) method for solving a class of constrained bilevel optimization problems in which the lower level part is a possibly nonsmooth convex optimization problem, whereas the upper level part is a possibly nonconvex optimization problem. Specifically, SMO applies a first order method to solve a sequence of minimax subproblems, which are obtained by employing a hybrid of modified augmented Lagrangian and penalty schemes on the bilevel op...
-
作者：Wang, Mingrui; Chakraborty, Prakash
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：In this study, we investigate N-player stochastic differential games with regime switching, in which the player dynamics are modulated by a finite-state Markov chain. We analyze the associated Nash system, which consists of a system of coupled nonlinear partial differential equations, and establish the existence and uniqueness of solutions to this system, thereby proving the existence of a unique Nash equilibrium. Additionally, we examine the mean field game (MFG) problem under the same regime...
-
作者：Cardaliaguet, Pierre; Jackson, Joe; Souganidis, Panagiotis E.
作者单位：Universite PSL; Universite Paris-Dauphine; University of Chicago
摘要：In this paper, we study a mean field control problem in which particles are absorbed when they reach the boundary of a smooth domain. The value of the N-particle problem is described by a hierarchy of Hamilton-Jacobi equations which are coupled through their boundary conditions. The value function of the limiting problem, meanwhile, solves a Hamilton-Jacobi equation set on the space of subprobability measures on the smooth domain-that is, the space of nonnegative measures with total mass of at...
-
作者：Liu, Weiliang; Ward, Amy R.; Zhang, Xun
作者单位：City University of Hong Kong; University of Chicago; Southern University of Science & Technology
摘要：This paper develops a framework that integrates finite-sample statistical learning with queueing asymptotic analysis to design matching policies. The stochastic matching model we consider assumes heterogeneous demand (customers) and heterogeneous supply (workers) arrive randomly over time, each with a randomly sampled patience time, and are lost (renege) if forced to wait longer than that time to be matched. Because the interarrival and patience-time distributions are unknown, matching decisio...
-
作者：Kakimura, Naonori; Zhu, Donghao
作者单位：Keio University; University of Tsukuba
摘要：We study a dynamic bipartite matching market model where agents arrive and depart randomly through Poisson processes. Our proposed mechanisms are for minimizing unmatched agents by determining whom and when to match. Our main contribution is establishing performance bounds for different local mechanisms with varying timing strategies. We find that the Patient algorithm, which delays matching to increase market thickness, outperforms the Greedy algorithm by an exponential factor. Notably, the P...
-
作者：Encz, Koppany Istvan; Mastrolilli, Monaldo; Vercesi, Eleonora
作者单位：Universita della Svizzera Italiana
摘要：Branch-and-bound algorithms (B&B) and polynomial-time approximation schemes (PTAS) are two seemingly distant areas of combinatorial optimization. We intend to (partially) bridge the gap between them while expanding the boundary of theoretical knowledge on the B&B framework. Branch-and-bound algorithms typically guarantee that an optimal solution is eventually found. However, we show that the standard implementation of branch-and-bound for certain knapsack and scheduling problems also exhibits ...
-
作者：Rokada, Kiran; Parise, Francesca
作者单位：Cornell University
摘要：A graphon game can be seen either as a limit of a sequence of network games when the number of players tends to infinity or as a stochastic model for sampling network games. Under suitable assumptions, we show that every convergent sequence of Nash equilibria of network games sampled from a graphon game converges to an equilibrium of the graphon game with probability 1, and every equilibrium of a graphon game is a limit of a sequence of epsilon-Nash equilibria of network games sampled from the...
-
作者：Scheinberg, Katya
-
作者：Grimmer, Benjamin; Shu, Kevin; Wang, Alex L.
作者单位：Johns Hopkins University; California Institute of Technology; Purdue University System; Purdue University
摘要：Recent works by Altschuler and Parrilo and Grimmer, Shu, Wang have shown that it is possible to accelerate the convergence of gradient descent on smooth convex functions, even without momentum, just by picking special stepsizes. In this paper, we provide a general theory for composing stepsize schedules, capturing all recent advances in this area and more. We propose three notions of composable stepsize schedules with elementary associated composition operations for combining them. From these ...
-
作者：Diao, Ruoyu; Dai, Yu-Hong; Zhang, Liwei
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Northeastern University - China; Northeastern University - China
摘要：Consider the stability properties of the Karush-Kuhn-Tucker (KKT) solution mapping SKKT for Nash equilibrium problems (NEPs) with canonical perturbations. Firstly, we obtain an exact characterization of the strong regularity of SKKT as well as an easily verified sufficient condition. Secondly, we propose equivalent conditions for the continuously differentiable single-valued localization of SKKT. Thirdly, the isolated calmness of SKKT is studied based on the I-property. The P-property is propo...
