-
作者：Correa, Jose; Dutting, Paul; Fischer, Felix; Schewior, Kevin
作者单位：Universidad de Chile; University of London; London School Economics & Political Science; University of London; Queen Mary University London; University of Cologne
摘要：A central object of study in optimal stopping theory is the single-choice prophet inequality for independent and identically distributed random variables. given a sequence of random variables X-1, . . . , X-n drawn independently from the same distribution, the goal is to choose a stopping time tau such that for the maximum value of alpha and for all distributions, E[X-tau] >= alpha center dot E[max X-t(t)]. What makes this problem challenging is that the decision whether tau = t may only depen...
-
作者：Frieze, Alan M.; Tkocz, Tomasz
作者单位：Carnegie Mellon University
摘要：We study the minimum spanning arborescence problem on the complete digraph (K) over right arrow (n), where an edge e has a weight W-e and a cost C-e, each of which is an independent uniform random variable U-s, where 0 < s <= 1 and U is uniform [0,1]. There is also a constraint that the spanning arborescence T must satisfy C(T) <= c(0). We establish, for a range of values for c(0),s, the asymptotic value of the optimum weight via the consideration of a dual problem.
-
作者：De Angelis, Tiziano; Ekstrom, Erik; Glover, Kristoffer
作者单位：University of Turin; Collegio Carlo Alberto; Uppsala University; University of Technology Sydney
摘要：We study the value and the optimal strategies for a two-player zero-sum optimal stopping game with incomplete and asymmetric information. In our Bayesian setup, the drift of the underlying diffusion process is unknown to one player (incomplete information feature), but known to the other one (asymmetric information feature). We formulate the problem and reduce it to a fully Markovian setup where the uninformed player optimises over stopping times and the informed one uses randomised stopping t...
-
作者：Arunachaleswaran, Eshwar Ram; Kannan, Sampath; Roth, Aaron; Ziani, Juba
作者单位：University of Pennsylvania; University System of Georgia; Georgia Institute of Technology
摘要：We introduce the pipeline intervention problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. In our model, individuals are born into an initial position (i.e., some node in the first layer of the graph) according to a fixed probability distribution and then stochastically progress...
-
作者：Andersson, Tommy; Ehlers, Lars; Svensson, Lars-Gunnar; Tierney, Ryan
作者单位：Lund University; Universite de Montreal; Universite de Montreal; University of Southern Denmark
摘要：We consider taxation of exchanges among a set of agents in which each agent owns one object. Agents may have different valuations for the objects, and they need to pay taxes for exchanges. We show that, if a rule satisfies individual rationality, strategy-proofness, constrained efficiency, weak anonymity, and weak consistency, then it is either the no-trade rule or a fixed-tax core rule. For the latter rules, whenever any agent exchanges an object, the agent pays the same fixed tax (a lump sum...
-
作者：Pena, Javier; Soheili, Negar
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
摘要：We propose a simple projection and rescaling algorithm that finds maximum support solutions to the pair of feasibility problems: find x is an element of L boolean AND R-+(n) and find (x) over cap is an element of L-perpendicular to boolean AND R-+(n) , where L is a linear subspace in R-n and L(perpendicular to)is its orthogonal complement. The algorithm complements a basic procedure that involves only projections onto L and L-perpendicular to with a periodic rescaling step. The number of resca...
-
作者：Dai, Min; Kou, Steven; Yang, Chen
作者单位：Hong Kong Polytechnic University; Boston University; Chinese University of Hong Kong
摘要：We establish a stochastic representation for a class of nonlocal parabolic terminal-boundary value problems, whose terminal and boundary conditions depend on the solution in the interior domain; in particular, the solution is represented as the expectation of functionals of a diffusion process with random jumps from boundaries. We discuss three applications of the representation, the first one on the pricing of dual-purpose funds, the second one on the connection to regenerative processes, and...
-
作者：Bui, Minh N.; Combettes, Patrick L.
作者单位：North Carolina State University
摘要：We propose a novel approach to monotone operator splitting based on the notion of a saddle operator. Under investigation is a highly structured multivariate monotone inclusion problem involving a mix of set-valued, cocoercive, and Lipschitzian monotone operators, as well as various monotonicity-preserving operations among them. This model encompasses most formulations found in the literature. A limitation of existing primal-dual algorithms is that they operate in a product space that is too sm...
-
作者：Lubin, Miles; Vielma, Juan Pablo; Zadik, Ilias
作者单位：Alphabet Inc.; Google Incorporated; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); New York University
摘要：Motivated by recent advances in solution methods for mixed-integer convex optimization (MICP), we study the fundamental and open question of which sets can be represented exactly as feasible regions of MICP problems. We establish several results in this direction, including the first complete characterization for the mixed-binary case and a simple necessary condition for the general case. We use the latter to derive the first nonrepresentability results for various nonconvex sets, such as the ...
-
作者：Cao, Zhigang; Chen, Bo; Chen, Xujin; Wang, Changjun
作者单位：Beijing Jiaotong University; University of Warwick; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
摘要：In this paper, we are concerned with bounding agents' residence times in the network for a broad class of atomic dynamic routings. We explore novel token techniques to circumvent direct analysis on complicated chain effects of dynamic routing choices. Even though agents may enter the network over time for an infinite number of periods, we prove that under a mild condition, the residence time of every agent is upper bounded (by a network-dependent constant plus the total number of agents inside...
