-
作者：Dutting, Paul; Fischer, Felix; Parkes, David C.
作者单位：University of London; London School Economics & Political Science; University of London; Queen Mary University London; Harvard University
摘要：Ideally, the properties of an economic mechanism should hold in a robust way across multiple equilibria and under varying assumptions regarding the information available to participants. Focusing on the design of robust position auctions, we seek mechanisms that possess an efficient equilibrium and guarantee high revenue in every efficient equilibrium, under complete and incomplete information. A generalized first-price auction that is expressive in the sense of allowing multidimensional bids ...
-
作者：Bazzi, Abbas; Fiorini, Samuel; Pokutta, Sebastian; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universite Libre de Bruxelles; University System of Georgia; Georgia Institute of Technology
摘要：The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349] proved that the problem is NP-hard to approximate within a factor 2- epsilon, assuming the unique games conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inappr...
-
作者：Kang, Wanmo; Lee, Jong Mun
作者单位：Korea Advanced Institute of Science & Technology (KAIST)
摘要：In this paper, we propose unbiased sensitivity estimators of the expected functionals of one-dimensional diffusion processes. Under general diffusion models, it is common to rely on discretization methods such as the Euler scheme for the generation of sample paths because of the lack of knowledge in the probability distributions associated with the diffusions. The Euler discretization method is easy to apply, but it is difficult to avoid discretization biases. As an alternative approach, we pr...
-
作者：Li, Jian; Deshpande, Amol
作者单位：Tsinghua University; University System of Maryland; University of Maryland College Park
摘要：We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input data set are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, minimum weight matchings, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk-averse or risk-prone behaviors, and, instead, we consider a more general objective, which is to max...
-
作者：Schied, Alexander; Zhang, Tao
作者单位：University of Waterloo; University of Mannheim
摘要：We consider a Nash equilibrium between two high-frequency traders (HFTs) in a simple market impact model with transient price impact and additional quadratic transaction costs. We prove existence and uniqueness of the Nash equilibrium and show that, for small transaction costs, the HFTs engage in a hot potato game, in which the same asset position is sold back and forth. We then identify a critical value for the size of the transaction costs above, for which all oscillations disappear and stra...
-
作者：Pena, Javier; Rodriguez, Daniel
作者单位：Carnegie Mellon University; Carnegie Mellon University
摘要：It is well known that the gradient descent algorithm converges linearly when applied to a strongly convex function with Lipschitz gradient. In this case, the algorithm's rate of convergence is determined by the condition number of the function. In a similar vein, it has been shown that a variant of the Frank-Wolfe algorithm with away steps converges linearly when applied to a strongly convex function with Lipschitz gradient over a polytope. In a nice extension of the unconstrained case, the al...
-
作者：Neto, Antonio Francisco
作者单位：Universidade Federal de Ouro Preto
摘要：MacMahon's Partition Analysis (MPA) is a combinatorial tool used in partition analysis to describe the solutions of a linear diophantine system. We show that MPA is useful in the context of weighted voting games. We introduce a new generalized generating function that gives, as special cases, extensions of the generating functions of the Banzhaf, Shapley-Shubik, Banzhaf-Owen, symmetric coalitional Banzhaf, and Owen power indices. Our extensions involve any coalition formation related to a line...
-
作者：Zhao, Yun-Bin; Jiang, Houyuan; Luo, Zhi-Quan
作者单位：University of Birmingham; University of Cambridge; Shenzhen Research Institute of Big Data; The Chinese University of Hong Kong, Shenzhen
摘要：As one of the most plausible convex optimization methods for sparse data reconstruction, l(1)-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as the restricted isometry property, null space property, and mutual coherence. In this paper, we propose a unified means to develop the so-called weak stability theory for l(1)-minimization methods under the condition ...
-
作者：Liu, Yongchao; Pichler, Alois; Xu, Huifu
作者单位：Dalian University of Technology; Technische Universitat Chemnitz; University of Southampton
摘要：Discrete approximation of probability distributions is an important topic in stochastic programming. In this paper, we extend the research on this topic to distributionally robust optimization (DRO), where discretization is driven by either limited availability of empirical data (samples) or a computational need for improving numerical tractability. We start with a one-stage DRO where the ambiguity set is defined by generalized prior moment conditions and quantify the discrepancy between the d...
-
作者：Fournier, Gaetan; Scarsini, Marco
作者单位：Aix-Marseille Universite; Luiss Guido Carli University
摘要：We consider a game where a finite number of retailers choose a location, given that their potential consumers are distributed on a network. Retailers do not compete on price but only on location, therefore each consumer shops at the closest store. We show that when the number of retailers is large enough, the game admits a pure Nash equilibrium and we construct it. We then compare the equilibrium cost borne by the consumers with the cost that could be achieved if the retailers followed the dic...
