-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University
摘要：A min-max formula is proved for the minimum of an integer-valued separable discrete convex function in which the minimum is taken over the set of integral elements of a box total dual integral polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in nonlinear optimization), but we also provide another version that avoids conjugates, and its spirit is conceptually closer to the standard form of classic min-max theorems in combinatorial optimization....
-
作者：Carmona, Rene; Cooney, Daniel B.; Graves, Christy, V; Lauriere, Mathieu
作者单位：Princeton University; University of Pennsylvania
摘要：We consider static finite-player network games and their continuum analogs graphon games. Existence and uniqueness results are provided as well as convergence of the finite-player network game optimal strategy profiles to their analogs for the graphon games. We also show that equilibrium strategy profiles of a graphon game provide approximate Nash equilibria for the finite-player games. Connections with mean field games are discussed. A motivating application of Cournot competition is presente...
-
作者：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...
