-
作者：Shin, Sungho; Na, Sen; Anitescu, Mihai
作者单位：Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology; United States Department of Energy (DOE); Argonne National Laboratory; University of Chicago
摘要：This article presents a regret analysis for stochastic model predictive control (SMPC) in linear systems with quadratic performance index and additive and multiplicative uncertainties. Under a finite support assumption, the problem can be cast as a finitedimensional quadratic program, but the problem becomes quickly intractable as the problem size grows exponentially in the horizon length. SMPC aims to compute approximate solutions by solving a sequence of problems with truncated prediction ho...
-
作者：Brandt, Felix; Greger, Matthias; Segal-Halevi, Erel; Suksompong, Warut
作者单位：Technical University of Munich; Universite PSL; Universite Paris-Dauphine; Ariel University; National University of Singapore
摘要：We study the problem of aggregating distributions, such as budget proposals, into a collective distribution. An ideal aggregation mechanism would be Pareto efficient, strategyproof, and fair. Most previous work assumes that agents evaluate budgets according to the 1 distance to their ideal budget. We investigate and compare different models from the larger class of star-shaped utility functions-a multidimensional generalization of single-peaked preferences. For the case of two alternatives, we...
-
作者：Segev, Danny; Singla, Sahil
作者单位：Tel Aviv University; Tel Aviv University; University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we propose a general framework to design efficient polynomialtime approximation schemes (EPTASs) for fundamental stochastic combinatorial optimization problems. Technically speaking, our approach relies on presenting tailor-made reductions to a newly introduced multidimensional Santa Claus problem. Even though the single-dimensional version of this problem is already known to be APX-Hard, we prove that an EPTAS can be designed for a constant number of machines and dimensions, wh...
-
作者：Giannakopoulos, Yiannis; Melissourgos, Themistoklis; Grosz, Alexander
作者单位：University of Glasgow; Technical University of Munich; University of Essex
摘要：We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a variety of problems within the complexity class PLS (Polynomial Local Search) can be cast within this model. This abstraction enables identifying key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. Our black-box tool provides concrete bounds on the expected maximum number of steps needed until local search reac...
-
作者：Jiao, Liguo; Lee, Jae Hyoung; Pham, Tien-Son
作者单位：Northeast Normal University - China; Pukyong National University; Dalat University
摘要：We are interested in optimality conditions for semialgebraic vector optimization problems with a situation in which generalized (weakly) nondominated points do exist but are not attained as image points of (weakly) efficient solutions. To this end, cones associated with unbounded semialgebraic sets at infinity are introduced and studied. Then, optimality conditions at infinity in terms of the Newton polyhedra of the objective mappings and of the cones associated with the constraint sets at inf...
-
作者：Ma, Jianhao; Fattahi, Salar
作者单位：University of Michigan System; University of Michigan
摘要：We explore the local landscape of low-rank matrix recovery, focusing on reconstructing a d1 x d2 matrix X* with rank r from m linear measurements, some potentially noisy. When the noise is distributed according to an outlier model, minimizing a nonsmooth & ell;1-loss with a simple subgradient method can often perfectly recover the ground truth matrix X*. Given this, a natural question is what optimization property (if any) enables such learning behavior. The most plausible answer is that the g...
-
作者：Faenza, Yuri; He, Chengyue; Sethuraman, Jay
作者单位：Columbia University
摘要：Scarf's algorithm gives a pivoting procedure to find a special vertex-a dominating vertex-in a down-monotone polytope. This paper studies the behavior of Scarf's algorithm when employed to find stable matchings in bipartite graphs. First, it proves that Scarf's algorithm can be implemented to run in polynomial time, showing the first positive result on its runtime in significant settings. Second, it shows an infinite family of instances where, no matter the pivoting rule and runtime, Scarf's a...
-
作者：Wang, Xingyu; Rhee, Chang-Han
作者单位：University of Amsterdam; Northwestern University
摘要：In this paper, we address rare-event simulation for heavy-tailed Levy processes with infinite activities. The presence of infinite activities poses a critical challenge, making it impractical to simulate or store the precise sample path of the Levy process. We present a rare-event simulation algorithm that incorporates an importance sampling strategy based on heavy-tailed large deviations, the stick-breaking approximation for the extrema of Levy processes, the Asmussen-Rosinski approximation, ...
-
作者：Ickstadt, Constantin; Theobald, Thorsten; von Stengel, Bernhard
作者单位：Goethe University Frankfurt; London School Economics & Political Science; University of London; London School Economics & Political Science
摘要：Quint and Shubik conjectured that a nondegenerate nxn game has at most 2n-1 Nash equilibria in mixed strategies. The conjecture is true for n <= 4 but false for n >= 6. We answer it positively for the remaining case n=5, which had been open since 1999. The problem can be translated to a combinatorial question about the vertices of a pair of simple n-polytopes with 2n facets. We introduce a novel obstruction based on the index of an equilibrium, which states that equilibrium vertices belong to ...
-
作者：Hofer, Felix; Soner, H. Mete
作者单位：Princeton University
摘要：We propose a new mean-field game model with two states to study synchronization phenomena, and we provide a comprehensive characterization of stationary and dynamic equilibria along with their stability properties. The game undergoes a phase transition with increasing interaction strength. In the subcritical regime, the uniform distribution, representing incoherence, is the unique and stable stationary equilibrium. Above the critical interaction threshold, the uniform equilibrium becomes unsta...
