-
作者：Drakopoulos, Kimon; Ozdaglar, Asuman; Tsitsiklis, John N.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider the propagation of a contagion process (epidemic) on a network and study the problem of dynamically allocating a fixed curing budget to the nodes of the graph, at each time instant. For bounded degree graphs, we provide a lower bound on the expected time to extinction under any such dynamic allocation policy, in terms of a combinatorial quantity that we call the resistance of the set of initially infected nodes, the available budget, and the number of nodes n. Specifically, we cons...
-
作者：Flesch, Janos; Predtetchinski, Arkadi
作者单位：Maastricht University; Maastricht University
摘要：We provide a characterization of subgame-perfect equilibrium plays in a class of perfect information games where each player's payoff function is Borel measurable and has finite range. The set of subgame-perfect equilibrium plays is obtained through a process of iterative elimination of plays. Extensions to games with bounded Borel measurable payoff functions are discussed. As an application of our results, we show that if every player's payoff function is bounded and upper semicontinuous, the...
-
作者：Suk, Tonghoon; Shin, Jinwoo
作者单位：International Business Machines (IBM); IBM USA; Korea Advanced Institute of Science & Technology (KAIST)
摘要：Ever since Tassiulas and Ephremides in 1992 proposed the maximum weight scheduling algorithm of throughput optimality for constrained queueing networks that arise in the context of communication networks, extensive efforts have been devoted to resolving its most important drawback: high complexity. This paper proposes a generic framework for designing throughput-optimal and low-complexity scheduling algorithms for constrained queueing networks. Under our framework, a scheduling algorithm updat...
-
作者：Yam, S. C. P.; Zhou, W.
作者单位：Chinese University of Hong Kong; JP Morgan Chase & Company
摘要：The present paper studies the optimal placement problem of a child order. In practice, short-term momentum indicators inferred from order book data play important roles in order placement decisions. In the present work, we first propose to explicitly model the short-term momentum indicator and then formulate the order placement problem as an optimal multiple stopping problem. In contrast to the common formulation in the existing literature, we allow zero refracting period between consecutive s...
-
作者：Bo, Lijun; Capponi, Agostino
作者单位：Chinese Academy of Sciences; University of Science & Technology of China, CAS; Columbia University
摘要：We introduce a dynamic credit portfolio framework where optimal investment strategies are robust against misspecifications of the reference credit model. The risk-averse investor models his fear of credit risk misspecification by considering a set of plausible alternatives whose expected log likelihood ratios are penalized. We provide an explicit characterization of the optimal robust bond investment strategy, in terms of default state dependent value functions associated with the max-min robu...
-
作者：Vegh, Laszlo A.
作者单位：University of London; London School Economics & Political Science
摘要：A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution and thus can be contracted. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per...
-
作者：Yokoi, Yu
作者单位：University of Tokyo
摘要：Classified stable matching, proposed by Huang, describes a matching model between academic institutes and applicants, in which each institute has upper and lower quotas on classes, i.e., subsets of applicants. Huang showed that the problem to decide whether there exists a stable matching or not is NP-hard in general. On the other hand, he showed that the problem is solvable if classes form a laminar family. For this case, Fleiner and Kamiyama gave a concise interpretation in terms of matroids ...
-
作者：Belomestny, Denis; Kraetschmer, Volker
作者单位：University of Duisburg Essen; Russian Academy of Sciences
摘要：In this paper we study optimal stopping problems with respect to distorted expectations with concave distortion functions. Our starting point is a seminal work of Xu and Zhou in 2013, who gave an explicit solution of such a stopping problem under a rather large class of distortion functionals. In this paper, we continue this line of research and prove a novel representation, which relates the solution of an optimal stopping problem under distorted expectation to the sequence of standard optima...
-
作者：Feigenbaum, Itai; Sethuraman, Jay; Ye, Chun
作者单位：City University of New York (CUNY) System; Lehman College (CUNY); City University of New York (CUNY) System; Columbia University; Amazon.com
摘要：This paper is concerned with the problem of locating a facility on a line in the presence of strategic agents, also located on that line. Each agent incurs a cost equal to her distance to the facility whereas the planner wishes to minimize the L-p norm of the vector of agent costs. The location of each agent is only privately known, and the goal is to design a strategyproof mechanism that approximates the optimal cost well. It is shown that the median mechanism provides a 2(1-1/p) approximatio...
-
作者：Zhao, Yun-Bin; Luo, Zhi-Quan
作者单位：University of Birmingham; University of Minnesota System; University of Minnesota Twin Cities
摘要：The l(0)-minimization problem that seeks the sparsest point of a polyhedral set is a long-standing, challenging problem in the fields of signal and image processing, numerical linear algebra, and mathematical optimization. The weighted l(1)-method is one of the most plausible methods for solving this problem. In this paper we develop a new weighted l(1)-method through the strict complementarity theory of linear programs. More specifically, we show that locating the sparsest point of a polyhedr...
