-
作者：Alcantara, Jan Harold; Takeda, Akiko
作者单位：RIKEN; University of Tokyo
摘要：Bilevel programming has recently received a great deal of attention because of its abundant applications in many areas. We study a class of bilevel problems in which the lower-level feasible set is independent of the upper-level variables. The optimal value function approach provides a useful reformulation of the bilevel problem, but its utility is often limited because of the nonsmoothness of the value function even in cases when the associated lower-level function is smooth. In this paper, w...
-
作者：He, Chuan; Huang, Heng; Lu, Zhaosong
作者单位：Linkoping University; University System of Maryland; University of Maryland College Park; University of Minnesota System; University of Minnesota Twin Cities
摘要：In this paper, we consider a nonconvex unconstrained optimization problem minimizing a twice differentiable objective function with Holder continuous Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG) method for finding an approximate firstand second-order stationary point of this problem, assuming the associated Holder parameters are explicitly known. Then, we develop a parameter-free Newton-CG method without requiring any prior knowledge of these parameters. To t...
-
作者：Guang, Jin; Chen, Xinyun; Dai, J. G.
作者单位：The Chinese University of Hong Kong, Shenzhen; Cornell University
摘要：We establish uniform moment bounds for steady-state queue lengths of generalized Jackson networks (GJNs) in multiscale heavy traffic as recently proposed by Dai et al. in 2023. Uniform moment bounds lay the foundation for further analysis of the limit stationary distribution. Our result can be used to verify the crucial moment state space collapse (SSC) assumption in Dai et al. in 2023 to establish a product-form limit of GJN in the multiscale heavy traffic regime. Our proof critically utilize...
-
作者：Hertrich, Christoph; Tao, Yixin; Vegh, Laszlo A.
作者单位：Shanghai University of Finance & Economics; University of Bonn
摘要：Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that the...
-
作者：Perez-Salazar, Sebastian; Singh, Mohit; Toriello, Alejandro
作者单位：Rice University; University System of Georgia; Georgia Institute of Technology
摘要：In online sales, sellers usually offer each potential buyer a posted price in a takeit-or-leave fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price frequently could be considered unfair. The literature on posted-price mechanisms and prophet inequality problems has studied the two extremes of pricing policies, the fixed-price policy and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than the latter. This work exami...
-
作者：Xu, Liding; Liberti, Leo
作者单位：Zuse Institute Berlin; Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole Polytechnique
摘要：We consider the problem of minimizing a polynomial f over the (binary) hyper-cube. We show that, for a specific set of polynomials, their binary nonnegativity (i.e., on the hypercube) can be checked in polynomial time via minimum cut algorithms, from which we construct a linear programming representation for this set of polynomials. We categorize binary polynomials according to their signed support patterns and develop parameterized linear programming representations for binary nonnegative pol...
-
作者：Cohen, Asaf; Sun, Chuhao
作者单位：University of Michigan System; University of Michigan
摘要：In this paper, we examine the stationary relaxed singular control problem within a multidimensional framework for a single agent as well as its mean field game equivalent. We demonstrate that optimal relaxed controls exist for two problem classes: one driven by queueing control and the other by harvesting models. These relaxed controls are defined by random measures across the state and control spaces with the state process described as a solution to the associated martingale problem. By lever...
-
作者：Sanita, Laura; Verberk, Lucy
作者单位：Bocconi University; Eindhoven University of Technology
摘要：Capacitated network bargaining games are popular combinatorial games that involve the structure of matchings in graphs. We show that it is always possible to stabilize unit weight instances of this problem (that is, ensure that they admit a stable outcome) via capacity reduction and edge removal operations without decreasing the total value that the players can get. Furthermore, for general weighted instances, we show that computing a minimum amount of vertex capacity to reduce to make an inst...
-
作者：Liu, Wei; Lin, Qihang; Xu, Yangyang
作者单位：Rensselaer Polytechnic Institute; University of Iowa
摘要：Many recent studies on first-order methods (FOMs) focus on composite nonconvex nonsmooth optimization with linear and/or nonlinear function constraints. Upper (or worst-case) complexity bounds have been established for these methods. However, little can be claimed about their optimality, as no lower bound is known except for a few special smooth nonconvex cases. In this paper, we make the first attempt to establish lower complexity bounds of FOMs for solving a class of composite nonconvex nons...
-
作者：Kijima, Shuji; Shimizu, Nobutaka; Shiraga, Takeharu
作者单位：Shiga University; Institute of Science Tokyo; Chuo University
摘要：Real networks are often dynamic. In response to it, analyses of algorithms on dynamic networks attract more and more attention in network science and engineering. Random walks on dynamic graphs have also been actively investigated for over a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by the setting of random walks on growing networks, this paper introduces a simple model of graphs with an incr...
