-
作者：Klaus, Bettina; Klijn, Flip
作者单位：University of Lausanne; Consejo Superior de Investigaciones Cientificas (CSIC); CSIC - Institut d'Analisi Economica (IAE); Barcelona School of Economics
摘要：A classical school choice problem consists of a set of schools with priorities over students and a set of students with preferences over schools. Schools' priorities are often based on multiple criteria, for example, merit-based test scores as well as minimal-access rights (siblings attending the school, students' proximity to the school, etc.). Traditionally, minimal-access rights are incorporated into priorities by always giving minimal-access students higher priority over non-minimal-access...
-
作者：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...
-
作者：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., ...
-
作者：Daniilidis, Aris; Tapia, Sebastian
作者单位：Technische Universitat Wien
摘要：Daniilidis and Drusviatskiy, in 2017, extended the celebrated Kurdyka- Lojasiewicz inequality from definable functions to definable multivalued maps by establishing that the coderivative mapping admits a desingularization around every critical value. As was the case in the gradient dynamics, this desingularization yields a uniform control of the lengths of all bounded orbits of the corresponding sweeping process. In this paper, working outside the framework of o-minimal geometry, we characteri...
-
作者：Komiyama, Junpei; Ariu, Kaito; Kato, Masahiro; Qin, Chao
作者单位：New York University; Royal Institute of Technology; Columbia University
摘要：We consider best arm identification in the multiarmed bandit problem. Assuming certain continuity conditions of the prior, we characterize the rate of the Bayesian simple regret. Differing from Bayesian regret minimization, the leading term in the Bayesian simple regret derives from the region in which the gap between optimal and suboptimal p ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi arms is smaller than (log T)/T. We propose a simple and easy-to-compute algorithm with its lead...
-
作者：Ragel, Thomas
作者单位：Universite PSL; Universite Paris-Dauphine
摘要：In this paper, we extend previous results on weak approachability in generalized quitting games with vector payoffs to the general case of absorbing games. Specifically, we show that a necessary condition and a different sufficient condition for weak approachability of a convex set, established by Flesch, Laraki, and Perchet, remain valid in the general case. To do so, we extend results on Blackwell approachability to a setup in which stage weights depend on past actions as well as the current...
-
作者：Phan, Duy Nhat; Thi, Hoai An Le
作者单位：University System of Ohio; University of Dayton; Universite de Lorraine; Institut Universitaire de France
摘要：In this paper, we focus on the problem of minimizing the sum of a nonconvex differentiable function and a difference of convex (DC) function, where the differentiable function is not restricted to the global Lipschitz gradient continuity assumption. This problem covers a broad range of applications in machine learning and statistics, such as compressed sensing, signal recovery, sparse dictionary learning, matrix factorization, etc. We first take inspiration from the Nesterov acceleration techn...
