-
作者：Abdi, Ahmed; Cornuejols, Gerard; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; Institute for Basic Science - Korea (IBS)
摘要：Ideal matrices and clutters are prevalent in combinatorial optimization, ranging from balanced matrices, clutters of T-joins, to clutters of rooted arborescences. Most of the known examples of ideal clutters are combinatorial in nature. In this paper, rendered by the recently developed theory of cuboids, we provide a different class of ideal clutters, one that is geometric in nature. The advantage of this new class of ideal clutters is that it allows for infinitely many ideal minimally nonpack...
-
作者：De Angelis, Tiziano; Gensbittel, Fabien; Villeneuve, Stephane
作者单位：University of Leeds; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：This paper studies a two-player zero-sum Dynkin game arising from pricing an option on an asset whose rate of return is unknown to both players. Using filtering techniques, we first reduce the problem to a zero-sum Dynkin game on a bidimensional diffusion (X,Y). Then we characterize the existence of a Nash equilibrium in pure strategies in which each player stops at the hitting time of (X,Y) to a set with a moving boundary. A detailed description of the stopping sets for the two players is pro...
-
作者：Oliu-Barton, Miquel
作者单位：Universite PSL; Universite Paris-Dauphine
摘要：Zero-sum stochastic games, henceforth stochastic games, are a classical model in game theory in which two opponents interact and the environment changes in response to the players' behavior. The central solution concepts for these games are the discounted values and the value, which represent what playing the game is worth to the players for different levels of impatience. In the present manuscript, we provide algorithms for computing exact expressions for the discounted values and for the val...
-
作者：Zhang, Hui; Dai, Yu-Hong; Guo, Lei; Peng, Wei
作者单位：National University of Defense Technology - China; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; East China University of Science & Technology
摘要：We introduce a unified algorithmic framework, called the proximal-like incremental aggregated gradient (PLIAG) method, for minimizing the sum of a convex function that consists of additive relatively smooth convex components and a proper lower semicontinuous convex regularization function over an abstract feasible set whose geometry can be captured by using the domain of a Legendre function. The PLIAG method includes many existing algorithms in the literature as special cases, such as the prox...
-
作者：Duetting, Paul; Kesselheim, Thomas; Tardos, Eva
作者单位：University of London; London School Economics & Political Science; University of Bonn; Cornell University
摘要：Many algorithms that are originally designed without explicitly considering incentive properties are later combined with simple pricing rules and used as mechanisms. A key question is therefore to understand which algorithms, or, more generally, which algorithm design principles, when combined with simple payment rules such as pay your bid, yield mechanisms with a small price of anarchy. Our main result concerns mechanisms that are based on the relax-and-round paradigm. It shows that oblivious...
-
作者：Callegaro, Giorgla; Grasselli, Martino; Pages, Gilles
作者单位：University of Padua; Universite Paris Cite; Sorbonne Universite
摘要：We solve a family of fractional Riccati equations with constant (possibly complex) coefficients. These equations arise, for example, in fractional Heston stochastic volatility models, which have received great attention in the recent financial literature because of their ability to reproduce a rough volatility behavior. We first consider the case of a zero initial value corresponding to the characteristic function of the log-price. Then we investigate the case of a general starting value assoc...
-
作者：Olvera-Cravioto, Mariana; Ruiz-Lacedelli, Octavio
作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine; Columbia University
摘要：Motivated by database locking problems in today's massive computing systems, we analyze a queueing network with many servers in parallel (files) to which jobs (writing access requests) arrive according to a Poisson process. Each job requests simultaneous access to a random number of files in the database and will lock them for a random period of time. Alternatively, one can think of a queueing system where jobs are split into several fragments that are then randomly routed to specific servers ...
-
作者：Atar, Rami; Lipshutz, David
作者单位：Technion Israel Institute of Technology
摘要：We consider a load-balancing problem for a network of parallel queues in which information on the state of the queues is subject to a delay. In this setting, adopting a routing policy that performs well when applied to the current state of the queues can perform quite poorly when applied to the delayed state of the queues. Viewing this as a problem of control under partial observations, we propose using an estimate of the current queue lengths as the input to the join-the-shortest-queue policy...
-
作者：Suzuki, Kiyoshi
摘要：Very few studies have explored the structure of optimal switching regimes. We extend the existing research on the infinite-horizon multiple-regime switching problem with an arbitrary number of switch options by replacing the linear running reward function with a quadratic function in the objective function. To make our analysis more rigorous, we establish the theoretical basis for the application of the simultaneous multiple-regime switches to the problem with the extended objective function, ...
-
作者：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...
