-
作者：Hertrich, Christoph; Tao, Yixin; Vegh, Laszlo A.
作者单位：Shanghai University of Finance & Economics; University of Bonn
摘要：Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that the...
-
作者：Perez-Salazar, Sebastian; Singh, Mohit; Toriello, Alejandro
作者单位：Rice University; University System of Georgia; Georgia Institute of Technology
摘要：In online sales, sellers usually offer each potential buyer a posted price in a takeit-or-leave fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price frequently could be considered unfair. The literature on posted-price mechanisms and prophet inequality problems has studied the two extremes of pricing policies, the fixed-price policy and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than the latter. This work exami...
-
作者：Kijima, Shuji; Shimizu, Nobutaka; Shiraga, Takeharu
作者单位：Shiga University; Institute of Science Tokyo; Chuo University
摘要：Real networks are often dynamic. In response to it, analyses of algorithms on dynamic networks attract more and more attention in network science and engineering. Random walks on dynamic graphs have also been actively investigated for over a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by the setting of random walks on growing networks, this paper introduces a simple model of graphs with an incr...
-
作者：Xing, Jie; Ma, Jingtang; Zheng, Harry
作者单位：Guizhou University of Finance & Economics; Southwestern University of Finance & Economics - China; Imperial College London
摘要：In this paper, we study a finite horizon optimal investment stopping problem with an unobservable random variable for the return of a risky asset. Using the Bayesian filter and the dual control approach, we transform the original primal problem into a dual finite horizon optimal stopping problem, which results in the dual value function satisfying a variational inequality with two state variables. For a class of utility functions that includes power utility and non-hyperbolic absolute risk ave...
-
作者：Boros, Endre; Lee, Joonhee
作者单位：Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick; Pace University
摘要：Hailperin (1965) introduced a linear programming formulation to a difficult family of problems, originally proposed by Boole (1854, 1868). Hailperin's model is computationally still difficult and involves an exponential number of variables (in terms of a typical input size for Boole's problem). Numerous papers provided efficiently computable bounds for the minimum and maximum values of Hailperin's model by using aggregation that is a monotone linear mapping to a lower dimensional space. In man...
-
作者：Xia, Li; Ma, Shuai
作者单位：Sun Yat Sen University
摘要：Dynamic optimization of mean and variance in Markov decision processes (MDPs) is a long-standing challenge caused by the failure of dynamic programming. In this paper, we propose a new approach to finding the globally optimal policy for combined metrics of steady-state mean and variance in an infinite-horizon undiscounted MDP. By introducing the concepts of pseudo mean and pseudo variance, we convert the original problem to a bilevel MDP problem, where the inner one is a standard MDP optimizin...
-
作者：Agrawal, Shipra; Avadhanula, Vashist; Goyal, Vineet; Zeevi, Assaf
作者单位：Columbia University; Columbia University
摘要：We consider a dynamic combinatorial optimization problem where at each time step, the decision maker selects a subset of cardinality K from N possible items and observes a feedback in the form of the index of one of the items in the said subset or none. Each of the N items is ascribed a certain value (reward), which is collected if the item is chosen. This problem is motivated by that of assortment selection in online retail, where items are products. Akin to that literature, it is assumed tha...
-
作者：Li, Hanyang; Cui, Ying
作者单位：University of California System; University of California Berkeley
摘要：We investigate a class of composite nonconvex functions, where the outer function is the sum of univariate extended-real-valued convex functions and the inner function is the limit of difference-of-convex functions. A notable feature of this class is that the inner function may fail to be locally Lipschitz continuous. It covers a range of important, yet challenging, applications, including inverse optimal value optimization and problems under value-at-risk constraints. We propose an asymptotic...
-
作者：Angelelli, Enrico; Mansini, Renata; Rizzi, Romeo
作者单位：University of Brescia; University of Brescia; University of Verona
摘要：The profitable tour problem (PTP) is a well-known NP-hard routing problem that searches for a tour visiting a subset of customers while maximizing profit measured as the difference between total revenue collected and traveling costs. PTP is known to be solvable in polynomial time when special structures of the underlying graph are considered. However, the computational complexity of the corresponding probabilistic generalizations is still an open issue in many cases. In this paper, we analyze ...
-
作者：Zhou, Danqing; Ma, Shiqian; Yang, Tunfeng
作者单位：Nanjing University; Rice University
摘要：In this paper, we propose AdaBB, an adaptive gradient method based on the Barzilai-Borwein stepsize. The algorithm is line-search-free and parameter-free, and it essentially provides a convergent variant of the Barzilai-Borwein method for general convex optimization problems. We analyze the ergodic convergence of the objective function value and the convergence of the iterates for solving general convex optimization problems. Compared with existing works along this line of research, our algori...
