-
作者：Govindan, Srihari; Laraki, Rida; Pahl, Lucas
作者单位：University of Rochester; Mohammed VI Polytechnic University; University of Sheffield
摘要：We present the following analog of O'Neill's theorem (O'Neill B (1953) Essential sets and fixed points. Amer. J. Math. 75(3):497-509 (theorem 5.2)) for finite games. Let C-1,. . . , C-k be the components of Nash equilibria of a finite normal-form game G. For each i, let ci be the index of C-i. For each epsilon > 0, there exist pairwise disjoint neighborhoods V-1,. . ., V-k of the components such that for any choice of finitely many distinct completely mixed strategy profiles {sigma(ij)}(ij), s...
-
作者：Gomes, Alexandra A.; Gomes, Diogo A.
作者单位：King Abdullah University of Science & Technology
摘要：We introduce a derivative-free optimization algorithm that efficiently computes minima for various classes of one-dimensional functions, including nonconvex and nonsmooth functions. This algorithm numerically approximates the gradient flow of a relaxed functional, integrating strategies such as Monte Carlo methods, rejection sampling, and adaptive techniques. These strategies enhance performance in solving a diverse range of optimization problems while significantly reducing the number of requ...
-
作者：Agrawal, Shipra; Avadhanula, Vashist; Goyal, Vineet; Zeevi, Assaf
作者单位：Columbia University; Columbia University
摘要：We consider a dynamic combinatorial optimization problem where at each time step, the decision maker selects a subset of cardinality K from N possible items and observes a feedback in the form of the index of one of the items in the said subset or none. Each of the N items is ascribed a certain value (reward), which is collected if the item is chosen. This problem is motivated by that of assortment selection in online retail, where items are products. Akin to that literature, it is assumed tha...
-
作者：Aprile, Manuel; Fiorini, Samuel; Joret, Gwenael; Kober, Stefan; Seweryn, Michal; Weltge, Stefan; Yuditsky, Yelena
作者单位：University of Padua; Universite Libre de Bruxelles; Universite Libre de Bruxelles; Technical University of Munich; University of Leeds
摘要：It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant triangle in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix. Our approach focuses on the case in which A arises from M after removing k rows only an...
-
作者：Atar, Rami; Miyazawa, Masakiyo
作者单位：Technion Israel Institute of Technology; Tokyo University of Science
摘要：This paper studies a single server queue in heavy traffic, with general interarrival and service time distributions, where arrival and service rates vary discontinuously as a function of the (diffusively scaled) queue length. It is proved that the weak limit is given by the unique-in-law solution to a stochastic differential equation in [0, infinity) with discontinuous drift and diffusion coefficients. The main tool is a semimartingale decomposition for point processes introduced by Daley and ...
-
作者：Balcan, Maria-Florina; Prasad, Siddharth; Sandholm, Tuomas
作者单位：Carnegie Mellon University; Toyota Technological Institute; Toyota Technological Institute - Chicago
摘要：We develop a versatile methodology for multidimensional mechanism design that incorporates side information about agents to generate high welfare and high revenue simultaneously. Side information sources include advice from domain experts, predictions from machine learning models, and even the mechanism designer's gut instinct. We design a tunable mechanism that integrates side information with an improved Vickrey-Clarke-- Groves-like mechanism based on weakest types, which are agent types tha...
-
作者：Larsson, Martin; Ramdas, Aaditya; Ruf, Johannes
作者单位：Carnegie Mellon University; Carnegie Mellon University; University of London; London School Economics & Political Science
摘要：E-variables are nonnegative random variables with expected value at most one under any distribution from a given null hypothesis. Every nonasymptotically valid test can be obtained by thresholding some e-variable. As such, e-variables arise naturally in applications in statistics and operations research, and a key open problem is to characterize their form. We provide a complete solution to this problem for hypotheses generated by constraints-a broad and natural framework that encompasses many...
-
作者：Sanjari, Sina; Saldi, Naci; Yuksel, Serdar
作者单位：Royal Military College - Canada; Ihsan Dogramaci Bilkent University; Queens University - Canada
摘要：We study a class of stochastic exchangeable teams with a finite number of decision makers (DMs) as well as their mean-field limits with infinitely many DMs. In the finite-population regime, we study exchangeable teams under the centralized information structure. For the infinite-population setting, we study both the centralized information structure and the decentralized mean-field information-sharing structure. The paper makes the following main contributions. (i) For finite-population exchan...
-
作者：Hirai, Hiroshi; Sakabe, Keiya
作者单位：Nagoya University; University of Munich
摘要：In this paper, we study the asymptotic behavior of continuous- and discretetime gradient flows of a lower-unbounded convex function f on a Hadamard manifold M, particularly their convergence properties to the boundary M infinity at infinity of M. We establish a duality theorem that the infimum of the gradient-norm & Vert; del f(x) & Vert; of f over M is equal to the supremum of the negative of the recession function f infinity of f over the boundary M infinity, provided the infimum is positive...
-
作者：Hadiji, Hedi; Sachs, Sarah; Guzman, Cristobal
作者单位：Universite Paris Saclay; University of Bristol; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：Tracking the solution of time-varying variational inequalities is an important problem with applications in game theory, optimization, and machine learning. Existing work considers time-varying games or time-varying optimization problems. For strongly convex optimization problems or strongly monotone games, such results provide tracking guarantees under the assumption that the variation of the time-varying problem is restrained, that is, problems with a sublinear solution path. We extend exist...
