-
作者：Muhle-Karbe, Johannes; Wang, Zexin; Webster, Kevin
作者单位：Imperial College London
摘要：Optimal execution and trading algorithms rely on price impact models, such as the propagator model, to quantify trading costs. Empirically, price impact is concave in trade sizes, leading to nonlinear models for which optimization problems are intractable, and even qualitative properties, such as price manipulation, are poorly understood. However, we show that in the diffusion limit of small and frequent orders, the nonlinear model converges to a tractable linear model. In this high-frequency ...
-
作者：Romeijnders, Ward; Van Foreest, Nicky D.; Wijngaard, Jacob
作者单位：University of Groningen
摘要：When Dutch parents divorce, Dutch law dictates that the parental contributions to cover the financial needs of the children have to be proportionally consistent. This rule is clear when parents only have common children. However, cases can be considerably more complicated, for example, when parents have financial responsibilities to children from previous marriages. We show that, mathematically, this settlement problem can be modeled as a bipartite rationing problem for which a unique global p...
-
作者：Christodoulou, George; Gkatzelis, Vasilis; Sgouritsa, Alkmini
作者单位：Aristotle University of Thessaloniki; Drexel University; Athens University of Economics & Business
摘要：We study the performance of cost-sharing methods in a selfish scheduling setting where a group of users schedule their jobs on machines with load-dependent cost functions, aiming to minimize their own cost. Anticipating this user behavior, the system designer chooses a decentralized protocol that defines how the cost generated on each machine is to be shared among its users, and the performance of the protocol is evaluated over the Nash equilibria of the induced game. Previous work on selfish ...
-
作者：Zhang, Amy B. Z.; Gurvich, Itai
作者单位：Cornell University; Northwestern University
摘要：We introduce a framework to approximate Markov decision processes (MDPs) that stands on two pillars: (i) state aggregation, as the algorithmic infrastructure, and (ii) central-limit-theorem-type approximations, as the mathematical underpinning of optimality guarantees. The theory is grounded in recent work by Braverman et al. (2020) that relates the solution of the Bellman equation to that of a partial differential equation (PDE) where, in the spirit of the central limit theorem, the transitio...
-
作者：London, Palma; Vardi, Shai; Eghbali, Reza; Wierman, Adam
作者单位：California Institute of Technology; Purdue University System; Purdue University; University of California System; University of California Berkeley
摘要：This paper presents a black-box framework for accelerating packing optimization solvers. Our method applies to packing linear programming problems and a family of convex programming problems with linear constraints. The framework is designed for high-dimensional problems, for which the number of variables n is much larger than the number of measurements m. Given an (m x n) problem, we construct a smaller (m x epsilon n) problem, whose solution we use to find an approximation to the optimal sol...
-
作者：Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Alexandros; Zeng, David
作者单位：Boston University; State University System of Florida; University of Florida; Harvard University; Purdue University System; Purdue University
摘要：We study trade-offs between fairness and efficiency when allocating indivisible items online. We attempt to minimize envy, the extent to which any agent prefers another's allocation to their own, while being Pareto efficient. We provide matching lower and upper bounds against a sequence of progressively weaker adversaries. Against worst-case adversaries, we find a sharp trade-off; no allocation algorithm can simultaneously provide both nontrivial fairness and nontrivial efficiency guarantees. ...
-
作者：Chen, Zaiwei; Maguluri, Siva T.; Shakkottai, Sanjay; Shanmugam, Karthikeyan
作者单位：University System of Georgia; Georgia Institute of Technology; University of Texas System; University of Texas Austin
摘要：This paper develops a unified Lyapunov framework for finite-sample analysis of a Markovian stochastic approximation (SA) algorithm under a contraction operator with respect to an arbitrary norm. The main novelty lies in the construction of a valid Lyapunov function called the generalized Moreau envelope. The smoothness and an approximation property of the generalized Moreau envelope enable us to derive a one-step Lyapunov drift inequality, which is the key to establishing the finite-sample bou...
-
作者：Braverman, Anton; Dai, J. G.; Fang, Xiao
作者单位：Northwestern University; Cornell University; Shenzhen Research Institute of Big Data; The Chinese University of Hong Kong, Shenzhen; Chinese University of Hong Kong
摘要：We derive and analyze new diffusion approximations of stationary distributions of Markov chains that are based on second- and higher-order terms in the expansion of the Markov chain generator. Our approximations achieve a higher degree of accuracy compared with diffusion approximations widely used for the last 50 years while retaining a similar computational complexity. To support our approximations, we present a combination of theoretical and numerical results across three different models. O...
-
作者：Qi, Mingyao; Jiang, Ruiwei; Shen, Siqian
作者单位：Tsinghua University; University of Michigan System; University of Michigan
摘要：We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation and exploit the problem structures to derive two valid inequalities based on submodularity and concave overes...
-
作者：Bu, Jinzhi; Gong, Xiting; Chao, Xiuli
作者单位：Hong Kong Polytechnic University; Chinese University of Hong Kong; University of Michigan System; University of Michigan
摘要：We consider three classes of inventory systems under long-run average cost: (i) periodic-review systems with lost sales, positive lead times, and a nonstationary demand process; (ii) periodic-review systems for a perishable product with partial backorders and a nonstationary demand process; and (iii) continuous-review systems with fixed lead times, Poisson demand process, and lost sales. The state spaces for these systems are multidimensional, and computations of their optimal control policies...
