-
作者：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., ...
-
作者：Pradhan, Somnath; Yueksel, Serdar
作者单位：Queens University - Canada
摘要：In control theory, typically a nominal model is assumed based on which an optimal control is designed and then applied to an actual (true) system. This gives rise to the problem of performance loss because of the mismatch between the true and assumed models. A robustness problem in this context is to show that the error because of the mismatch between a true and an assumed model decreases to zero as the assumed model approaches the true model. We study this problem when the state dynamics of t...
-
作者：Cesa-Bianchi, Nicolo; Cesari, Tommaso; Colomboni, Roberto; Fusco, Federico; Leonardi, Stefano
作者单位：University of Milan; University of Ottawa; Istituto Italiano di Tecnologia - IIT; Sapienza University Rome
摘要：Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. In this paper, we cast the bilateral trade problem in a regret minimization framework over T rounds of seller/buyer interactions, with no prior knowledge on their private valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with diff...
-
作者：Berger, Ben; Ezra, Tomer; Feldman, Michal; Fusco, Federico
作者单位：Harvard University; Tel Aviv University; Sapienza University Rome
摘要：Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper, we initiate the study of Pandora's problem with combinatorial costs, capturing applications where search cost is nonadditive. Weitzman's celebrated algorithm (1979) demonstrates that for additive costs, the optimal search strategy is nonadaptive and computationally feasible. We inquire to which extent this structural and computational simplicity extends beyond ad...
-
作者：Brubach, Brian; Grammel, Nathaniel; Ma, Will; Srinivasanb, Aravind
作者单位：Wellesley College; University System of Maryland; University of Maryland College Park; Columbia University; Columbia University
摘要：Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the input, which has led to the study of stochastic matching models. Here, each edge in the graph has a known, independent probability of existing derived from some prediction. Algorithms must probe edges to determine existence and match them irrevocably if they exist. Further, each vertex may have a patience constraint...
