-
作者：Towle, Eli; Luedtke, James
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We present a framework to obtain valid inequalities for a reverse convex set: the set of points in a polyhedron that lie outside a given open convex set. Reverse convex sets arise in many models, including bilevel optimization and polynomial optimization. An intersection cut is a well-known valid inequality for a reverse convex set that is generated from a basic solution that lies within the convex set. We introduce a framework for deriving valid inequalities for the reverse convex set from ba...
-
作者：Lim, Tongseok; McCann, Robert J.
作者单位：Purdue University System; Purdue University; University of Toronto
摘要：We bound the variance and other moments of a random vector based on the range of its realizations, thus generalizing inequalities of Popoviciu and of Bhatia and Davis concerning measures on the line to several dimensions. This is done using convex duality and (infinite-dimensional) linear programming. The following consequence of our bounds exhibits symmetry breaking, provides a new proof of Jung's theorem, and turns out to have applications to the aggregation dynamics modelling attractive-rep...
-
作者：Dahan, Mathieu; Amin, Saurabh; Jaillet, Patrick
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset's elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence ...
-
作者：Goldenshluger, Alexander; Zeevi, Assaf
作者单位：University of Haifa; Columbia University
摘要：The subject of this paper is the problem of optimal stopping of a sequence of independent and identically distributed random variables with unknown distribution. We propose a stopping rule that is based on relative ranks and study its performance as measured by the maximal relative regret over suitable nonparametric classes of distributions. It is shown that the proposed rule is first-order asymptotically optimal and nearly rate optimal in terms of the rate at which the relative regret converg...
-
作者：Frankowska, Helene; Sagara, Nobusumi
作者单位：Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS); Universite Paris Cite; Hosei University
摘要：We investigate the value function of an infinite horizon variational problem in the infinite-dimensional setting. First, we provide an upper estimate of its Dini-Hadamard subdifferential in terms of the Clarke subdifferential of the Lipschitz continuous integrand and the Clarke normal cone to the graph of the set-valued mapping describing dynamics. Second, we derive a necessary condition for optimality in the form of an adjoint inclusion that grasps a connection between the Euler-Lagrange cond...
-
作者：Koessler, Frederic; Laclau, Marie; Tomala, Tristan
作者单位：Paris School of Economics; Centre National de la Recherche Scientifique (CNRS)
摘要：We study the interaction between multiple information designers who try to influence the behavior of a set of agents. When each designer can choose information policies from a compact set of statistical experiments with countable support, such games always admit subgame-perfect equilibria. When designers produce public information, every equilibrium of the simple game in which the set of messages coincides with the set of states is robust in the sense that it is an equilibrium with larger and ...
-
作者：Faenza, Yuri; Kavitha, Telikepalli
作者单位：Columbia University; Tata Institute of Fundamental Research (TIFR)
摘要：Let G be an instance of the stable marriage problem in which every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if M does not lose a head-to-head election against any matching. Popular matchings generalize stable matchings. Unfortunately, when there are edge costs, to find or even approximate up to any factor a popular matching of minimum cost is NP-hard. Let opt be the cost of a min-cost popular matching. Our goal is to efficiently compute a matchin...
-
作者：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...
-
作者：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...
-
作者：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 ...
