-
作者：Garber, Dan
作者单位：Technion Israel Institute of Technology
摘要：We revisit the problem of online linear optimization in the case where the set of feasible actions is accessible through an approximated linear optimization oracle with a factor alpha multiplicative approximation guarantee. This setting in particular is interesting because it captures natural online extensions of well-studied offline linear optimization problems that are NP-hard yet admit efficient approximation algorithms. The goal here is to minimize the alpha-regret, which is the natural ex...
-
作者：Dadush, Dan; Vegh, Laszlo A.; Zambelli, Giacomo
作者单位：University of London; London School Economics & Political Science
摘要：We present a new class of polynomial-time algorithms for submodular function minimization (SFM) as well as a unified framework to obtain strongly polynomial SFM algorithms. Our algorithms are based on simple iterative methods for the minimum-norm problem, such as the conditional gradient and Fujishige-Wolfe algorithms. We exhibit two techniques to turn simple iterative methods into polynomial-time algorithms. First, we adapt the geometric rescaling technique, which has recently gained attentio...
-
作者：Gupta, Varun; Moseley, Benjamin; Uetz, Marc; Xie, Qiaomin
作者单位：University of Chicago; Carnegie Mellon University; University of Twente; Cornell University
摘要：This corrigendum fixes an incorrect claim in the paper Gupta et al. [Gupta V, Moseley B, Uetz M, Xie Q (2020) Greed works-online algorithms for unrelated machine stochastic scheduling. Math. Oper. Res. 45(2):497-516.], which led us to claim a performance guarantee of 6 for a greedy algorithm for deterministic online scheduling with release times on unrelated machines. The result is based on an upper bound on the increase of the objective function value when adding an additional job j to a mach...
-
作者：Liu, Fangda; Wang, Ruodu
作者单位：University of Waterloo
摘要：The notion of tail risk has been a crucial consideration in modern risk management and financial regulation, as very well documented in the recent regulatory documents. To achieve a comprehensive understanding of the tail risk, we carry out an axiomatic study for risk measures that quantify the tail risk, that is, the behaviour of a risk beyond a certain quantile. Such risk measures are referred to as tail risk measures in this paper. The two popular classes of regulatory risk measures in bank...
-
作者：Ma, Jin; Wong, Ting-Kam Leonard; Zhang, Jianfeng
作者单位：University of Southern California; University of Toronto
摘要：We introduce a new notion of conditional nonlinear expectation under probability distortion. Such a distorted nonlinear expectation is not subadditive in general, so it is beyond the scope of Peng's framework of nonlinear expectations. A more fundamental problem when extending the distorted expectation to a dynamic setting is time inconsistency, that is, the usual tower property fails. By localizing the probability distortion and restricting to a smaller class of random variables, we introduce...
-
作者：Babaioff, Moshe; Nisan, Noam; Taigam-Cohen, Inbal
作者单位：Hebrew University of Jerusalem; Technion Israel Institute of Technology
摘要：Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods (Foley 1967, Varian 1974). Every agent receives an equal budget of artificial currency with which to purchase goods, and prices match demand and supply. However, a CEEI is not guaranteed to exist when the goods are indivisible even in the simple two-agent, single-item market. Yet it is easy to see that, once the two budgets are slightly perturbed (made generic), a co...
-
作者：Alizamir, Saed; Chen, Ningyuan; Kim, Sang-Hyun; Manshadi, Vahideh
作者单位：Yale University; University of Toronto
摘要：We analyze a firm's optimal pricing of a new service when consumers interact in a network and impose positive externality on one another. The firm initially provides its service for free, leveraging network externality to promote rapid service consumption growth. The firm raises the price and starts earning revenue only when a sufficient level of consumer interactions is established. Incorporating the local network effects in a nonstationary dynamic model, we study the impact of network struct...
-
作者：Liu, Peng; Schied, Alexander; Wang, Ruodu
作者单位：University of Essex; University of Waterloo
摘要：In this paper we provide a general mathematical framework for distributional transforms, which allows for many examples that are used extensively in the literature of finance, economics, and optimization. We put a special focus on the class of probability distortions, which is a fundamental tool in decision theory. As our main results, we characterize distributional transforms satisfying various properties, and this includes an equivalent set of conditions which forces a distributional transfo...
-
作者：Kim, Daehyun; Li, Xiaoxi
作者单位：Wuhan University
摘要：This paper defines a general framework to study infinitely repeated games with time-dependent discounting in which we distinguish and discuss both time-consistent and -inconsistent preferences. To study the long-term properties of repeated games, we introduce an asymptotic condition to characterize the fact that players become more and more patient; that is, the discount factors at all stages uniformly converge to one. Two types of folk theorems are proven without the public randomization assu...
-
作者：Lipshutz, David; Ramanan, Kavita
作者单位：Technion Israel Institute of Technology; Brown University
摘要：Reflected Brownian motion (RBM) in a convex polyhedral cone arises in a variety of applications ranging from the theory of stochastic networks to mathematical finance, and under general stability conditions, it has a unique stationary distribution. In such applications, to implement a stochastic optimization algorithm or quantify robustness of a model, it is useful to characterize the dependence of stationary performance measures on model parameters. In this paper, we characterize parametric s...
