-
作者：Shao, Hui; Zhang, Zhe George
作者单位：Zhejiang University; Western Washington University; Simon Fraser University
摘要：Extreme-case risk measures provide an approach for quantifying the upper and lower bounds of risk in situations where limited information is available regarding the underlying distributions. Previous research has demonstrated that for popular risk measures, such as value-at-risk and conditional value-at-risk, the worst-case counterparts can be evaluated in closed form when only the first two moments of the underlying distributions are known. In this study, we extend these findings by presentin...
-
作者：Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt; Mehta, Ruta; Misra, Pranabendu
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Max Planck Society; University of Illinois System; University of Illinois Urbana-Champaign; Chennai Mathematical Institute
摘要：We study the problem of fairly allocating a set of indivisible goods among n agents with additive valuations. Envy freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of an EFX allocation has not been settled and is one of the most important problems in fair division. Toward resolving this question, many impressive results show the existence of its relaxations. In particular, it is known that 0.618-EFX allocations exist and that...
-
作者：Brustle, Johannes; Correa, Jose; Duetting, Paul; Verdugo, Victor
作者单位：University of London; London School Economics & Political Science; Universidad de Chile; Alphabet Inc.; Google Incorporated; Universidad de O'Higgins
摘要：We study the competition complexity of dynamic pricing relative to the optimal auction in the fundamental single-item setting. In prophet inequality terminology, we compare the expected reward Am(F) achievable by the optimal online policy on m independent and identically distributed (i.i.d.) random variables distributed according to F to the expected maximum Mn(F)of n i.i.d. draws from F. We ask how big m has to be to ensure that (1 + epsilon)Am(F) >_ Mn(F) for all F. We resolve this question ...
-
作者：Bilo, Vittorio; Moscardelli, Luca; Vinci, Cosimo
作者单位：University of Salento; G d'Annunzio University of Chieti-Pescara; Gran Sasso Science Institute (GSSI)
摘要：Motivated by possible applications in fault-tolerant selfish routing, we introduce the notion of uniform mixed equilibrium in network congestion games with adversarial link failures, where agents need to route traffic from a source to a destination node. Given an integer p >_ 1, a p-uniform mixed strategy is a mixed strategy in which an agent plays exactly p edge-disjoint paths with uniform probability; therefore, a p-uniform mixed equilibrium is a tuple of p-uniform mixed strategies, one for ...
-
作者：Chen, Xin; Stolyar, Alexander L.; Xin, Linwei
作者单位：University System of Georgia; Georgia Institute of Technology; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of Chicago
摘要：We consider a classic joint pricing and inventory control problem with lead times, which is extensively studied in the literature but is notoriously difficult to solve because of the complex structure of the optimal policy. In this work, rather than analyzing the optimal policy, we propose a class of constant-order dynamic pricing policies, which are fundamentally different from base-stock list price policies, the primary emphasis in the existing literature. Under such a policy, a constant-ord...
-
作者：Zhu, Daoli; Zhao, Lei; Zhang, Shuzhong
作者单位：Shanghai Jiao Tong University; Shanghai Jiao Tong University; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shanghai Jiao Tong University; Shanghai Jiao Tong University; University of Minnesota System; University of Minnesota Twin Cities
摘要：Nonlinearly constrained nonconvex and nonsmooth optimization models play an increasingly important role in machine learning, statistics, and data analytics. In this paper, based on the augmented Lagrangian function, we introduce a flexible first-order primal-dual method, to be called nonconvex auxiliary problem principle of augmented Lagrangian (NAPP-AL), for solving a class of nonlinearly constrained nonconvex and nonsmooth optimization problems. We demonstrate that NAPP-AL converges to a sta...
-
作者：Bo, Lijun; Huang, Yijie; Yu, Xiang
作者单位：Xidian University; Chinese Academy of Sciences; University of Science & Technology of China, CAS; Hong Kong Polytechnic University
摘要：This paper studies stochastic control problems motivated by optimal consumption with wealth benchmark tracking. The benchmark process is modeled by a combination of a geometric Brownian motion and a running maximum process, indicating its increasing trend in the long run. We consider a relaxed tracking formulation such that the wealth compensated by the injected capital always dominates the benchmark process. The stochastic control problem is to maximize the expected utility of consumption ded...
-
作者：Happach, Felix; Schulz, Andreas S.
作者单位：Technical University of Munich; Technical University of Munich
摘要：We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set-cover problem. For these scheduling problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed linear programming relaxations. We show how a variant of alpha-point scheduling leads to the best known approximation ratios, including a guarantee of four for an interesting special case of the so-called generalized min-sum set-cover problem. We also mak...
-
作者：Jin, Ying; Yang, Zhuoran; Wang, Zhaoran
作者单位：Harvard University; Yale University; Northwestern University
摘要：We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a data set collected a priori. Because of the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the data set, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply fl...
-
作者：Muthukumar, Vidya; Phade, Soham; Sahai, Anant
作者单位：University System of Georgia; Georgia Institute of Technology; University of California System; University of California Berkeley
摘要：We study the limiting behavior of the mixed strategies that result from optimal no-regret learning in a repeated game setting where the stage game is any 2 x 2 competitive game. We consider optimal no-regret algorithms that are mean-based and monotonic in their argument. We show that for any such algorithm, the limiting mixed strategies of the players cannot converge almost surely to any Nash equilibrium. This negative result is also shown to hold under a broad relaxation of these assumptions,...
