-
作者：Chen, Ningyuan; Gallego, Guillermo
作者单位：University of Toronto; Hong Kong University of Science & Technology
摘要：We consider the problem of a firm seeking to use personalized pricing to sell an exogenously given stock of a product over a finite selling horizon to different consumer types. We assume that the type of an arriving consumer can be observed, but the demand function associated with each type is initially unknown. The firm sets personalized prices dynamically for each type and attempts to maximize the revenue over the season. We provide a learning algorithm that is near optimal when the demand a...
-
作者：Chandrasekaran, Karthekeyan; Chekuri, Chandra
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider the HYPERGRAPH-k-CUT problem. The input consists of a hypergraph G = (V, E) with nonnegative hyperedge-costs c : E ??? R+ and a positive integer k. The objective is to find a minimum cost subset F ??? E such that the number of connected components in G ??? F is at least k. An alternative formulation of the objective is to find a partition of V into k nonempty sets V1, V2, ..., Vk so as to minimize the cost of the hyperedges that cross the partition. GRAPH-k-CUT, the special case of...
-
作者：Guo, Xin; Xu, Renyuan; Zariphopoulou, Thaleia
作者单位：University of California System; University of California Berkeley; University of Southern California; University of Oxford; University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin; University of Oxford
摘要：Entropy regularization has been extensively adopted to improve the efficiency, the stability, and the convergence of algorithms in reinforcement learning. This paper analyzes both quantitatively and qualitatively the impact of entropy regularization for mean field games (MFGs) with learning in a finite time horizon. Our study provides a theoretical justification that entropy regularization yields time-dependent policies and, furthermore, helps stabilizing and accelerating convergence to the ga...
-
作者：Wu, Xian; Charikar, Moses; Natchu, Vishnu
作者单位：University of California System; University of California Berkeley; Stanford University
摘要：An important question that arises in the study of high-dimensional vector representations learned from data are, given a set D of vectors and a query q, estimate the number of points within a specified distance threshold of q. We develop two estimators, LSH count and multiprobe count that use locality-sensitive hashing to preprocess the data to accurately and efficiently estimate the answers to such questions via importance sampling. A key innovation is the ability to maintain a small number o...
-
作者：Ezra, Tomer; Feldman, Michal; Gravin, Nick; Tang, Zhihao Gavin
作者单位：Tel Aviv University; Shanghai University of Finance & Economics
摘要：We provide prophet inequality algorithms for online weighted matching in general (nonbipartite) graphs, under two well-studied arrival models: edge arrival and vertex arrival. The weights of the edges are drawn froma priori known probability distribution. Under edge arrival, the weight of each edge is revealed on arrival, and the algorithm decides whether to include it in thematching or not. Under vertex arrival, theweights of all edges fromthe newly arriving vertex to all previously arrived v...
-
作者：Ozkan, Erhun
作者单位：Koc University
摘要：A fork-join processing network is a queueing network in which tasks associated with a job can be processed simultaneously. Fork-join processing networks are prevalent in computer systems, healthcare, manufacturing, project management, justice systems, and so on. Unlike the conventional queueing networks, fork-join processing networks have synchronization constraints that arise because of the parallel processing of tasks and can cause significant job delays. We study scheduling in fork-join pro...
-
作者：Abdou, Joseph; Pnevmatikos, Nikolaos; Scarsini, Marco; Venel, Xavier
作者单位：Universite Paris-Pantheon-Assas; Luiss Guido Carli University
摘要：Orthogonal direct-sum decompositions of finite games into potential, harmonic and nonstrategic components exist in the literature. In this paper we study the issue of decomposing games that are strategically equivalent from a game-theoretical point of view, for instance games obtained via transformations such as duplications of strategies or positive affine mappings of the payoffs. We show the need to define classes of decompositions to achieve commutativity of game transformations and decompo...
-
作者：Klimm, Max; Warode, Philipp
作者单位：Technical University of Berlin
摘要：We develop algorithms solving parametric flow problems with separable, continuous, piecewise quadratic, and strictly convex cost functions. The parameter to be considered is a common multiplier on the demand of all nodes. Our algorithms compute a family of flows that are each feasible for the respective demand and minimize the costs among the feasible flows for that demand. For single commodity networks with homogenous cost functions, our algorithm requires one matrix multiplication for the in...
-
作者：Hellman, Ziv; Levy, Yehuda John
作者单位：Bar Ilan University; University of Glasgow
摘要：We study dynamic properties of the group action on the simplex that is induced by Bayesian updating. We show that, generically, the orbits are dense in the simplex, although one must make use of the entire group, hence departing from straightforward Bayesian updating. We demonstrate also the necessity of the genericity of the signalling structure, a relationship to descriptive set theoretical concepts, and applications thereof to repeated games of incomplete information, as well a strengthenin...
-
作者：Bassett, Robert; Deride, Julio
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School; Universidad Tecnica Federico Santa Maria
摘要：We study statistical estimators computed using iterative optimization methods that are not run until completion. Classical results on maximum likelihood estimators (MLEs) assert that a one-step estimator (OSE), in which a single Newton-Raphson iteration is performed from a starting point with certain properties, is asymptotically equivalent to the MLE. We further develop these early-stopping results by deriving properties of one-step estimators defined by a single iteration of scaled proximal ...
