-
作者：Wang, Xianfu; Wang, Ziyuan
作者单位：University of British Columbia
摘要：We introduce a generalized version of the concave Kurdyka-Lojasiewicz (KL) property by employing nonsmooth desingularizing functions. We also present the exact modulus of the generalized concave KL property, which provides an answer to the open question regarding the optimal concave desingularizing function. The exact modulus is designed to be the smallest among all possible concave desingularizing functions. Examples are given to illustrate this pleasant property. In turn, using the exact mod...
-
作者：Lu, Zhaosong; Sun, Zhe; Zhou, Zirui
作者单位：University of Minnesota System; University of Minnesota Twin Cities; Jiangxi Normal University; Huawei Technologies
摘要：In this paper, we consider a class of structured nonsmooth difference-of-convex (DC) constrained DC programs in which the first convex component of the objective and constraints is the sum of a smooth and a nonsmooth function, and their second convex component is the supremum of finitely many convex smooth functions. The existing methods for this problem usually have a weak convergence guarantee or require a feasible initial point. Inspired by the recent work by Pang et al. [Pang J-S, Razaviya...
-
作者：Feinstein, Zachary; Rudloff, Birgit; Zhang, Jianfeng
作者单位：Stevens Institute of Technology; Vienna University of Economics & Business; University of Southern California
摘要：Nonzero sum games typically have multiple Nash equilibriums (or no equilibrium), and unlike the zero-sum case, they may have different values at different equilibriums. Instead of focusing on the existence of individual equilibriums, we study the set of values over all equilibriums, which we call the set value of the game. The set value is unique by nature and always exists (with possible value 0). Similar to the standard value function in control literature, it enjoys many nice properties, su...
-
作者：Hellman, Ziv; Levy, Yehuda John
作者单位：Bar Ilan University; University of Glasgow
摘要：The solution concept of a Bayesian equilibrium of a Bayesian game is inherently an interim concept. The corresponding ex ante solution concept has been termed a Harsanyi equilibrium; examples have appeared in the literature showing that there are Bayesian games with uncountable state spaces that have no Bayesian approximate equilibria but do admit a Harsanyi approximate equilibrium, thus exhibiting divergent behaviour in the ex ante and interim stages. Smoothness, a concept from descriptive se...
-
作者：Liu, Junyi; Cui, Ying; Pang, Jong-Shi
作者单位：Tsinghua University; University of Minnesota System; University of Minnesota Twin Cities; University of Southern California
摘要：This paper studies a structured compound stochastic program (SP) involving multiple expectations coupled by nonconvex and nonsmooth functions. We present a successive convex programming-based sampling algorithm and establish its subsequential convergence. We describe stationary properties of the limit points for several classes of the compound SP. We further discuss probabilistic stopping rules based on the computable error bound for the algorithm. We present several risk measure minimization ...
-
作者：Liu, Fangda; Mao, Tiantian; Wang, Ruodu; Wei, Linxiao
作者单位：University of Waterloo; Chinese Academy of Sciences; University of Science & Technology of China, CAS; Wuhan University of Technology
摘要：Inspired by the recent developments in risk sharing problems for the value at risk (VaR), the expected shortfall (ES), and the range value at risk (RVaR), we study the optimization of risk sharing for general tail risk measures. Explicit formulas of the infconvolution and Pareto-optimal allocations are obtained in the case of a mixed collection of left and right VaRs, and in that of a VaR and another tail risk measure. The inf-convolution of tail risk measures is shown to be a tail risk measur...
-
作者：Amanatidis, Georgios; Kleer, Pieter; Schafer, Guido
作者单位：University of Essex; Tilburg University; University of Amsterdam; University of Amsterdam
摘要：The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible, and O(1)-approximation...
-
作者：Harshaw, Christopher; Kazemi, Ehsan; Feldman, Moran; Karbasi, Amin
作者单位：Yale University; Alphabet Inc.; Google Incorporated; University of Haifa; Yale University; Yale University
摘要：We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SAMPLEGREEDY, which obtains a (p + 2 + o(1))-...
-
作者：Giannakopoulos, Yiannis; Noarov, Georgy; Schulz, Andreas S.
作者单位：University of Erlangen Nuremberg; University of Pennsylvania; Technical University of Munich
摘要：We present a deterministic polynomial-time algorithm for computing d(d+o(d))-approximate (pure) Nash equilibria in (proportional sharing) weighted congestion games with polynomial cost functions of degree at most d. This is an exponential improvement of the approximation factor with respect to the previously best deterministic algorithm. An appealing additional feature of the algorithm is that it only uses best-improvement steps in the actual game, as opposed to the previously best algorithms,...
-
作者：Atar, Rami; Budhiraja, Amarjit; Dupuis, Paul; Wu, Ruoyu
作者单位：Technion Israel Institute of Technology; University of North Carolina; University of North Carolina Chapel Hill; Brown University; Iowa State University
摘要：For the M/M/1+M model at the law-of-large-numbers scale, the long-run reneging count per unit time does not depend on the individual (i.e., per customer) reneging rate. This paradoxical statement has a simple proof. Less obvious is a large deviations analogue of this fact, stated as follows: the decay rate of the probability that the long-run reneging count per unit time is atypically large or atypically small does not depend on the individual reneging rate. In this paper, the sample path larg...
