-
作者：Fujii, Kaito; Yoshida, Yuichi
作者单位：Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we consider a setting where predictions of candidate values are provided in advance. We propose an algorithm that achieves a nearly optimal value if the predictions are accurate and results in a constant-factor competitive ratio otherwise. We also show that the worst-case competitive ratio of an algorithm cannot be hig...
-
作者：Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Goethe University Frankfurt; Max Planck Society
摘要：We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not...
-
作者：Kong, Siyu; Lewis, A. S.
作者单位：Cornell University
摘要：We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a 2020 black-box algorithm of Zhang-Lin-Jegelka-Sra-Jadbabaie that approximates an e-stationary point of any directionally differentiable Lipschitz objective using O(e-4) calls to a specialized subgradient oracle and a randomized line search. Seeking by contras...
-
作者：Chen, Xi; Kroer, Christian; Kumar, Rachitesh
作者单位：Columbia University
摘要：Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in th...
-
作者：Pollner, Tristan; Roghani, Mohammad; Saberi, Amin; Wajc, David
作者单位：Stanford University; Alphabet Inc.; Google Incorporated
摘要：Motivated by applications in the gig economy, we study approximation algorithms for a sequential pricing problem. The input is a bipartite graph G. (I, J, E) between individuals I and jobs J. The platform has a value of v(j) for matching job j to an individual worker. In order to find a matching, the platform can consider the edges (ij) is an element of E in any order and make a one-time take-it-or-leave-it offer of a price pi(ij) = w of its choosing to i for completing j. The worker accepts t...
-
作者：Cai, Qi; Yang, Zhuoran; Lee, Jason D.; Wang, Zhaoran
作者单位：Northwestern University; Yale University; Princeton University
摘要：Temporal difference learning (TD), coupled with neural networks, is among the most fundamental building blocks of deep reinforcement learning. However, because of the nonlinearity in value function approximation, such a coupling leads to nonconvexity and even divergence in optimization. As a result, the global convergence of neural TD remains unclear. In this paper, we prove for the first time that neural TD converges at a sublinear rate to the global optimum of the mean-squared projected Bell...
-
作者：Guo, Lei; Ye, Jane J.; Zhang, Jin
作者单位：East China University of Science & Technology; University of Victoria; Southern University of Science & Technology; Peng Cheng Laboratory
摘要：In this paper, we perform a sensitivity analysis for the maximal value function, which is the optimal value function for a parametric maximization problem. Our aim is to study various subdifferentials for the maximal value function. We obtain upper estimates of Fre ' chet, limiting, and horizon subdifferentials of the maximal value function by using some sensitivity analysis techniques sophisticatedly. The derived upper estimates depend only on the union of all solutions and not on its convex ...
-
作者：Gunluk, Oktay; Hauser, Raphael Andreas; Kovacs, Reka Agnes
作者单位：Cornell University; University of Oxford; Alan Turing Institute
摘要：Binary matrix factorization is an essential tool for identifying discrete patterns in binary data. In this paper, we consider the rank-k binary matrix factorization problem (kBMF) under Boolean arithmetic: we are given an n x m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n x k and k x m, respectively, which minimize the distance between X and the Boolean product of A and B in the squared Frobenius distance. We present a compact and tw...
-
作者：Basu, Ranojoy; Mukherjee, Conan
作者单位：Indian Institute of Management (IIM System); Indian Institute of Management Udaipur (IIMU); Indian Institute of Management (IIM System); Indian Institute of Management Calcutta
摘要：We consider direct mechanisms to sell heterogeneous objects when buyers have private additive valuations and nonunit demand. We completely characterize the class of strategy-proof and agent sovereign mechanisms that satisfy a local side-flatness condition. Further, we introduce a notion of continuity up to utility and show that any such mechanism allocating all objects at all profiles is continuous and anonymous only if it is efficient. We find that the only mechanism satisfying these properti...
-
作者：Delong, Steven; Farhadi, Alireza; Niazadeh, Rad; Sivan, Balasubramanian; Udwani, Rajan
作者单位：Alphabet Inc.; Google Incorporated; Carnegie Mellon University; University of Chicago; Alphabet Inc.; Google Incorporated; University of California System; University of California Berkeley
摘要：We study the classic online bipartite matching problem with a twist: off-line vertices, called resources, are reusable. In particular, when a resource is matched to an online vertex, it is unavailable for a deterministic time duration d, after which it becomes available again for a rematch. Thus, a resource can be matched to many different online vertices over a period of time. Whereas recent work on the problem has resolved the asymptotic case in which we have large starting inventory (i.e., ...
